[ Russian ] [ English ]

Обработка и оптимизация SPARQL-запросов к семантическим RDF хранилищам

Михаил Галкин,
PhD Candidate
Fraunhofer Institute for Intelligent Analysis and Information Systems
Smart Data Analytics @ University of Bonn
Germany
galkin ‘at’ cs.uni-bonn.de
mikhail.galkin ‘at’ iais.fraunhofer.de

RDF - графовая слабо-структурированная модель представления знаний с формализованной семантикой, использующая утверждения-тройки формата “субъект-предикат-объект”. SPARQL - стандартный язык запросов к RDF-данным. Большие объемы связанных RDF-данных хранятся в распределенных или федеративных системах.

В докладе дается краткий обзор стандартов RDF и SPARQL, а также рассматриваются подходы к оптимизации федеративных SPARQL-запросов на этапах декомпозиции запроса, выбора подходящих источников и создания плана исполнения запроса.

На этапе оптимизации плана запроса рассматривается новый алгоритм выполнения мультиарных join-операций, что в настоящее время не используется стандартными системами обработки SPARQL запросов, но хорошо известно в оптимизации SQL-запросов.

Авторы также представляют подход к созданию адаптивных федеративных систем обработки SPARQL-запросов, объединяющих бинарные и мультиарные операторы в одном плане и способных изменять планы запросов на лету в зависимости от текущих условий выполнения запросов.

Традиционные join-операторы требуют точного соответствия объединяемых значений, тогда как модель RDF допускает существование множества описаний одной сущности. Для работы с такими хранилищами авторы описывают similarity join алгоритм, который позволяет в blocking и non-blocking вариантах объединять синтаксически разные, но семантически эквивалентные значения. В дополнение, будет представлен подход к созданию мультиарного similarity join оператора.

Слайды доклада.

Видео доклада.

Литература:

  1. J. Perez, M. Arenas and C. Gutie?rrez, Semantics and complexity of SPARQL, ACM Trans. Database Syst. 34.3, 2009
  2. Acosta et al., “ANAPSID: An Adaptive Query Processing Engine for SPARQL Endpoints”, ISWC - 10th International Semantic Web Conference, Bonn, Germany, 2011
  3. A. Schwarte et al., “FedX: Optimization Techniques for Federated Query Processing on Linked Data”. ISWC - 10th International Semantic Web Conference, Bonn, Germany, 2011
  4. Acosta M., and Vidal M. E. "Networks of linked data eddies: An adaptive web query processing engine for RDF data." International Semantic Web Conference. Springer, Cham, 2015.
  5. Endris, K. M., Galkin, M., Lytra, I., Mami, M. N., Vidal, M. E., & Auer, S. MULDER: Querying the Linked Data Web by Bridging RDF Molecule Templates. In International Conference on Database and Expert Systems Applications (pp. 3-18). Springer, Cham, 2017
  6. Galkin, M., Endris, K. M., Acosta, M., Collarana, D., Vidal, M. E., & Auer, S. SMJoin: A multi-way join operator for sparql queries. In Proceedings of the 13th International Conference on Semantic Systems (pp. 104-111). ACM, 2017
  7. Galkin, M., Collarana, D., Traverso-Ribon, I., Vidal, M. E., & Auer, S. SJoin: A Semantic Join Operator to Integrate Heterogeneous RDF Graphs. In International Conference on Database and Expert Systems Applications (pp. 206-221). Springer, Cham, 2017.
  8. Galkin, M., Vidal, M. E., & Auer, S. Towards a Multi-way Similarity Join Operator. In Advances in Databases and Information Systems (pp. 267-274). Springer, Cham, 2017
Supported by Synthesis Group