Jorge Pérez
Abstract
SPARQL is the standard language for querying RDF data. In this article, we address systematically the formal study of the database aspects of SPARQL, concentrating in its graph pattern matching facility. We provide a compositional semantics for the core part of SPARQL, and study the complexity of the evaluation of several fragments of the language. Among other complexity results, we show that the evaluation of general SPARQL patterns is PSPACE-complete. We identify a large class of SPARQL patterns, defined by imposing a simple and natural syntactic restriction, where the query evaluation problem can be solved more efficiently. This restriction gives rise to the class of well-designed patterns. We show that the evaluation problem is coNP-complete for well-designed patterns. Moreover, we provide several rewriting rules for well-designed patterns whose application may have a considerable impact in the cost of evaluating SPARQL queries.
- Abiteboul, S., Hull, R., and Vianu, V. 1995. Foundations of Databases. Addison-Wesley. Google Scholar
Digital Library
- Abiteboul, S., Kanellakis, P., and Grahne, G. 1991. On the representation and querying of sets of possible worlds. Theor. Comput. Sci. 78, 1, 158--187. Google ScholarDigital Library
- Angles, R. and Gutierrez, C. 2008. The expressive power of sparql. In Proceedings of the International Semantic Web Conference (ISWC), 114--129. Google ScholarDigital Library
- Arenas, M., Gutierrez, C., Parsia, B., Pérez, J., Polleres, A., and Seaborne, A. 2007. SPARQL—Where are we? Current state, theory and practice. Full day tutorial, European Semantic Web Conference.Google Scholar
- ARQ, 2006. A SPARQL processor for Jena, version 1.3 March 2006, Hewlett-Packard Development Company. http://jena.sourceforge.net/ARQ.Google Scholar
- Beeri, C., Fagin, R., Maier, D., and Yannakakis, M. 1983. On the desirability of acyclic database schemes. J. ACM 30, 3, 479--513. Google ScholarDigital Library
- Bhargava, G., Goel, P., and Iyer, B. 1995. Hypergraph based reorderings of outer join queries with complex predicates. In Proceedings of the SIGMOD International Conference of Management of Data, 304--315. Google ScholarDigital Library
- Chandra, A. and Merlin, P. 1977. Optimal implementation of conjunctive queries in relational data bases. In Proceedings of the Symposium on the Theory of Computing (STOC), 77--90. Google ScholarDigital Library
- Chen, L., Gupta, A., and Kurul, E. 2005. A semantic-aware RDF query algebra. In Proceedings of the International Conference on Management of Data (COMAD).Google Scholar
- Cyganiak, R. 2005. A relational algebra for sparql. Tech. rep. HPL-2005-170, HP-Labs. http://www.hpl.hp.com/techreports/2005/HPL-2005-170.html.Google Scholar
- de Bruijn, J., Franconi, E., and Tessaris, S. 2005. Logical reconstruction of normative RDF. In Proceedings of the OWL—Experiences and Directions Workshop (OWLED).Google Scholar
- Durst, M. and Suignard, M. 2005. Rfc 3987, internationalized resource identifiers (IRIS). http://www.ietf.org/rfc/rfc3987.txt.Google Scholar
- Frasincar, F., Houben, G.-J., Vdovjak, R., and Barna, P. 2004. RAL: An algebra for querying RDF. World Wide Web 7, 1, 83--109. Google ScholarDigital Library
- Furche, T., Linse, B., Bry, F., Plexousakis, D., and Gottlob, G. 2006. RDF querying: Language constructs and evaluation methods compared. In Reasoning Web, 1--52.Google Scholar
- Galindo-Legaria, C. A. and Rosenthal, A. 1997. Outerjoin simplification and reordering for query optimization. ACM Trans. Datab. Syst. 22, 1, 43--73. Google ScholarDigital Library
- Garey, M. R. and Johnson, D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman. Google ScholarDigital Library
- Gottlob, G., Leone, N., and Scarcello, F. 2001. The complexity of acyclic conjunctive queries. J. ACM 48, 3, 431--498. Google ScholarDigital Library
- Gutierrez, C., Hurtado, C. A., and Mendelzon, A. O. 2004. Foundations of semantic Web databases. In Proceedings of the ACM Symposium on Principles of Database Systems (PODS), 95--106. Google ScholarDigital Library
- Haase, P., Broekstra, J., Eberhart, A., and Volz, R. 2004. A comparison of RDF query languages. In Proceedings of the International Semantic Web Conference (ISWC), 502--517.Google Scholar
- Harris, S. and Shadbolt, N. 2005. SPARQL query processing with conventional relational database systems. In Proceedings of the WISE Workshops, 235--244. Google ScholarDigital Library
- Imielinski, T. and Lipski, W. 1984. Incomplete information in relational databases. J. ACM 31, 4, 761--791. Google ScholarDigital Library
- Karvounarakis, G., Alexaki, S., Christophides, V., Plexousakis, D., and Scholl, M. 2002. RQL: A declarative query language for RDF. In Proceedings of the International Conference on World Wide Web (WWW), 592--603. Google ScholarDigital Library
- Klyne, G., Carroll, J. J., and McBride, B. 2004. Resource description framework (RDF): Concepts and abstract syntax. W3C recommendation. http://www.w3.org/TR/rdf-concepts/.Google Scholar
- Manola, F. and Miller, E. 2004. RDF primer, W3C recommendation. http://www.w3.org/TR/rdf-concepts/.Google Scholar
- Marin, D. 2004. A formalization of RDF (applications de la logique á la sémantique du Web). Tech. rep., École Polytechnique, Universidad de Chile. Department of Computer Science, Universidad de Chile, TR/DCC-2006-8.Google Scholar
- Pérez, J., Arenas, M., and Gutierrez, C. 2006a. Semantics and complexity of SPARQL. In Proceedings of the International Semantic Web Conference (ISWC). 30--43. Google ScholarDigital Library
- Pérez, J., Arenas, M., and Gutierrez, C. 2006b. Semantics of SPARQL. Tech. rep., Universidad de Chile. Department of Computer Science, Universidad de Chile, TR/DCC-2006-17.Google Scholar
- Polleres, A. 2007. From SPARQL to rules (and back). In Proceedings of the International Conference on World Wide Web (WWW), 787--796. Google ScholarDigital Library
- Prud'hommeaux, E. and Seaborne, A. 2008. SPARQL query language for RDF. W3C recommendation. http://www.w3.org/TR/rdf-sparql-query/.Google Scholar
- Robertson, E. L. 2004. Triadic relations: An algebra for the semantic Web. In Proceedings of the International Workshop on Semantic Web and Databases (SWDB), 91--108. Google ScholarDigital Library
- Schmidt, M., Meier, M., and Lausen, G. 2008. Foundations of SPARQL query optimization. http://arxiv.org/abs/0812.3788.Google Scholar
- Seaborne, A. 2006. Personal communication.Google Scholar
- Serfiotis, G., Koffina, I., Christophides, V., and Tannen, V. 2005. Containment and minimization of RDF/S query patterns. In Proceedings of the International Semantic Web Conference (ISWC), 607--623. Google ScholarDigital Library
- Vardi, M. Y. 1982. The complexity of relational query languages (extended abstract). In Proceedings of the Symposium on the Theory of Computing (STOC), 137--146. Google ScholarDigital Library
- Yannakakis, M. 1981. Algorithms for acyclic database schemes. In Proceedings of the International Conference on Very Large Data Bases (VLDB), 82--94. Google ScholarDigital Library
- Zaniolo, C. 1984. Database relations with null values. J. Comput. Syst. Sci. 28, 1, 142--166.Google ScholarCross Ref
Index Terms
- Semantics and complexity of SPARQL
Recommendations
Foundations of SPARQL query optimization
ICDT '10: Proceedings of the 13th International Conference on Database TheoryWe 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 ...
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 ...
Extending SPARQL with regular expression patterns (for querying RDF)
RDF is a knowledge representation language dedicated to the annotation of resources within the framework of the semantic web. Among the query languages for RDF, SPARQL allows querying RDF through graph patterns, i.e., RDF graphs involving variables. ...
Comments