Michael Schmidt
ABSTRACT
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.
- R. Angles and C. Gutierrez. The Expressive Power of SPARQL. In ISWC, pages 114--129, 2008. Google Scholar
Digital Library
- C. Beeri and M. Y. Vardi. A Proof Procedure for Data Dependencies. J. ACM, 31(4):718--741, 1984.Google Scholar
- C. Weiss et al. Hexastore: Sextuple Indexing for Semantic Web Data Management. In VLDB, pages 1008--1019, 2008. Google ScholarDigital Library
- U. S. Chakravarthy, J. Grant, and J. Minker. Logic-based Approach to Semantic Query Optimization. TODS, 15(2):162--207, 1990.Google ScholarDigital Library
- R. Cyganiac. A relational algebra for SPARQL. Technical report, HP Laboratories Bristol, 2005.Google Scholar
- D. J. Abadi et al. Scalable Semantic Web Data Management Using Vertical Partitioning. In VLDB, pages 411--422, 2007. Google ScholarDigital Library
- A. Deutsch, A. Nash, and J. Remmel. The Chase Revisited. In PODS, pages 149--158, 2008. Google ScholarDigital Library
- A. Deutsch, L. Popa, and V. Tannen. Query Reformulation with Constraints. SIGMOD Record, 35(1):65--73, 2006. Google ScholarDigital Library
- E. I. Chong et al. An Efficient SQL-based RDF Querying Scheme. In VLDB, pages 1216--1227, 2005. Google ScholarDigital Library
- François Bry et al. Foundations of Rule-based Query Answering. In Reasoning Web, pages 1--153, 2007. Google ScholarDigital Library
- G. Serfiotis et al. Containment and Minimization of RDF/S Query Patterns. In ISWC, pages 607--623, 2005. Google ScholarDigital Library
- C. Gutierrez, C. A. Hurtado, and A. O. Mendelzon. Foundations of Semantic Web Databases. In PODS, pages 95--106, 2004. Google ScholarDigital Library
- A. Harth and S. Decker. Optimized Index Structures for Querying RDF from the Web. In LA-WEB, pages 71--80, 2005. Google ScholarDigital Library
- D. S. Johnson and A. Klug. Testing Containment of Conjunctive Queries under Functional and Inclusion Dependencies. In PODS, pages 164--169, 1982.Google ScholarDigital Library
- J. J. King. QUIST: a system for semantic query optimization in relational databases. In VLDB, pages 510--517, 1981.Google ScholarDigital Library
- L. Sidirourgos et al. Column-store Support for RDF Data Management: not all swans are white. In VLDB, page 1553, 2008. Google ScholarDigital Library
- G. Lausen, M. Meier, and M. Schmidt. SPARQLing Constraints for RDF. In EDBT, pages 499--509, 2008. Google ScholarDigital Library
- Linked Data, http://linkeddata.org/.Google Scholar
- M. Schmidt et al. An Experimental Comparison of RDF Data Management Approaches in a SPARQL Benchmark Scenario. In ISWC, pages 82--97, 2008. Google ScholarDigital Library
- M. Stocker et al. SPARQL Basic Graph Pattern Optimization Using Selectivity Estimation. In WWW, pages 595--604, 2008. Google ScholarDigital Library
- D. Maier, A. Mendelzon, and Y. Sagiv. Testing Implications of Data Dependencies. In SIGMOD, pages 152--152, 1979.Google ScholarDigital Library
- M. Meier, M. Schmidt, and G. Lausen. On Chase Termination Beyond Stratification. In VLDB, 2009. Google ScholarDigital Library
- T. Neumann and G. Weikum. RDF-3X: a RISC-style engine for RDF. PVLDB, 1(1):647--659, 2008. Google ScholarDigital Library
- J. Pérez, M. Arenas, and C. Gutierrez. Semantics and Complexity of SPARQL. Technical report, arXiv:0605124 cs.DB, 2006.Google Scholar
- J. Pérez, M. Arenas, and C. Gutierrez. Semantics of SPARQL, 2006. TR/DCC-2006-16, Universidad de Chile.Google Scholar
- J. Pérez, M. Arenas, and C. Gutierrez. Semantics and Complexity of SPARQL. ACM Trans. Database Syst., 34(3), 2009. Google ScholarDigital Library
- A. Polleres. From SPARQL to Rules (and back). In WWW, pages 787--796, 2007. Google ScholarDigital Library
- R. Fagin et al. Data Exchange: Semantics and Query Answering. Theor. Comput. Sci., 336(1):89--124, 2005. Google ScholarDigital Library
- Resource Description Framework (RDF). http://www.w3.org/RDF/.Google Scholar
- S. Alexaki et al. On Storing Voluminous RDF descriptions: The case of Web Portal Catalogs. In WebDB, pages 43--48, 2001.Google Scholar
- J. Smith and P. Chang. Optimizing the Performance of a Relational Algebra Database Interface. Commun. ACM, 18(10):568--579, 1975.Google ScholarDigital Library
- SPARQL Query Language for RDF. W3C Recommendation, 15 Januray 2008.Google Scholar
- L. J. Stockmeyer. The polynomial-time hierarchy. Theor. Comput. Sci., 3:1--22, 1976.Google ScholarCross Ref
- Y. Theoharis et al. Benchmarking Database Representations of RDF/S Stores. In ISWC, pages 685--701, 2005. Google ScholarDigital Library
Index Terms
- Foundations of SPARQL query optimization
Recommendations
Using SPARQL to query bioportal ontologies and metadata
ISWC'12: Proceedings of the 11th international conference on The Semantic Web - Volume Part IIBioPortal is a repository of biomedical ontologies--the largest such repository, with more than 300 ontologies to date. This set includes ontologies that were developed in OWL, OBO and other languages, as well as a large number of medical terminologies ...
RDF, Jena, SparQL and the 'Semantic Web'
SIGUCCS '09: Proceedings of the 37th annual ACM SIGUCCS fall conference: communication and collaborationThe Resource Description Format (RDF) is used to represent information modeled as a "graph": a set of individual objects, along with a set of connections among those objects. In that role, RDF is one of the pillars of the so-called Semantic Web. This ...
SPARQL-to-SQL Query Translation: Bottom-Up or Top-Down?
SCC '11: Proceedings of the 2011 IEEE International Conference on Services ComputingEmerging Semantic Web Services rely on the availability of metadata that describes various functional and non-functional characteristics of computational resources. A number of semantic vocabularies and datasets describing existing services and ...
Comments