Foundations of SPARQL query optimization

By Michael Schmidt. International Conference on Database Theory, 2008

376 citations recorded by the source corpus.

We study fundamental aspects related to the efficient processing of the SPARQL query language for RDF, proposed by the W3C to encode machine-readable information in the Semantic Web. Our key contributions are (i) a complete complexity analysis for all operator fragments of the SPARQL query language, which -- as a central result -- shows that the SPARQL operator Optional alone is responsible for the PSpace-completeness of the evaluation problem, (ii) a study of equivalences over SPARQL algebra, including both rewriting rules like filter and projection pushing that are well-known from relational algebra optimization as well as SPARQL-specific rewriting schemes, and (iii) an approach to the semantic optimization of SPARQL queries, built on top of the classical chase algorithm. While studied in the context of a theoretically motivated set semantics, almost all results carry over to the official, bag-based semantics and therefore are of immediate practical relevance.

Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/2ee495cdf71dbab740771c4f02176a6f48827467

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Naser Ahmadi
2. Stefano Ortona
3. Olaf Hartig
4. Ruben Verborgh
5. Paolo Papotti
6. Pieter Colpaert
7. Miel Vander Sande
8. Laurens De Vocht

In Computer Networks and Communications

1. Olaf Hartig
2. Ruben Verborgh
3. Paolo Papotti
4. Pieter Colpaert
5. Miel Vander Sande
6. Laurens De Vocht
7. Gerald Haesendonck
8. Ben De Meester

In Management Science and Operations Research

1. Naser Ahmadi
2. Paolo Papotti
3. Ihab F. Ilyas
4. Xu Chu

Citations in the corpus

• RuleHub (2020, background): “KG dependencies (or logical rules ) are used for identifying errors [28], adding new facts [20], executing queries faster [31], and reasoning for many tasks, such as explaining decisions in fact-checking [5].”
• Triple Pattern Fragments: A low-cost knowledge graph interface for the Web (2016, background): “2 and, afterwards, these new variables have to be projected out of the query result by an additional iterator that implements a projection operator [36].”