Reinhard Pichler
Sebastian Skritek
ABSTRACT
Query containment and query equivalence constitute important computational problems in the context of static query analysis and optimization. While these problems have been intensively studied for fragments of relational calculus, almost no works exist for the semantic web query language SPARQL. In this paper, we carry out a comprehensive complexity analysis of containment and equivalence for several fragments of SPARQL: we start with the fundamental fragment of well-designed SPARQL restricted to the AND and OPTIONAL operator. We then study basic extensions in the form of the UNION operator and/or projection. The results obtained range from NP-completeness to undecidability.
- R. Angles and C. Gutierrez. The expressive power of SPARQL. In ISWC, volume 5318 of LNCS, pages 114--129. Springer, 2008. Google Scholar
Digital Library
- M. Arenas and J. Pérez. Querying semantic web data with SPARQL. In PODS, pages 305--316. ACM, 2011. Google ScholarDigital Library
- A. Calı, G. Gottlob, and M. Kifer. Taming the infinite chase: Query answering under expressive relational constraints. In KR, pages 70--80. AAAI Press, 2008.Google Scholar
- A. K. Chandra and P. M. Merlin. Optimal implementation of conjunctive queries in relational data bases. In STOC, pages 77--90. ACM, 1977. Google ScholarDigital Library
- M. W. Chekol, J. Euzenat, P. Genevès, and N. Layaıda. SPARQL query containment under RDFS entailment regime. In IJCAR, volume 7364 of LNCS, pages 134--148. Springer, 2012. Google ScholarDigital Library
- M. W. Chekol, J. Euzenat, P. Genevès, and N. Layaıda. SPARQL query containment under SHI axioms. In AAAI. AAAI Press, 2012.Google Scholar
- R. Cyganiak, D. Wood, and M. Lanthaler. RDF 1.1 concepts and abstract syntax. W3C Recommendation, W3C, Feb. 2014. http://www.w3.org/TR/rdf11-concepts.Google Scholar
- S. Harris and A. Seaborne. SPARQL 1.1 Query Language. W3C Recommendation, W3C, Mar. 2013. http://www.w3.org/TR/sparql11-query.Google Scholar
- D. S. Johnson and A. C. Klug. Testing containment of conjunctive queries under functional and inclusion dependencies. JCSS, 28(1):167--189, 1984.Google ScholarCross Ref
- G. Karvounarakis, A. Magkanaraki, S. Alexaki, V. Christophides, D. Plexousakis, M. Scholl, and K. Tolle. Querying the semantic web with RQL. Computer Networks, 42(5):617--640, 2003. Google ScholarDigital Library
- A. C. Klug. On conjunctive queries containing inequalities. J. ACM, 35(1):146--160, 1988. Google ScholarDigital Library
- A. Letelier, J. Pérez, R. Pichler, and S. Skritek. Static analysis and optimization of semantic web queries. In PODS, pages 89--100. ACM, 2012. Google ScholarDigital Library
- A. Letelier, J. Pérez, R. Pichler, and S. Skritek. Static analysis and optimization of semantic web queries. ACM Trans. Database Syst., 38(4):25, 2013. Google ScholarDigital Library
- J. Pérez, M. Arenas, and C. Gutierrez. Semantics and complexity of SPARQL. In ISWC, volume 4273 of LNCS, pages 30--43. Springer, 2006. Google ScholarDigital Library
- J. Pérez, M. Arenas, and C. Gutierrez. Semantics and complexity of SPARQL. ACM TODS, 34(3), 2009. Google ScholarDigital Library
- A. Polleres. From SPARQL to rules (and back). In WWW, pages 787--796. ACM, 2007. Google ScholarDigital Library
- E. Prud'hommeaux and A. Seaborne. SPARQL Query Language for RDF. W3C Recommendation, %W3C, Jan. 2008. http://www.w3.org/TR/rdf-sparql-query.Google Scholar
- Y. Sagiv and M. Yannakakis. Equivalences among relational expressions with the union and difference operators. J. ACM, 27(4):633--655, 1980. Google ScholarDigital Library
- M. Schmidt, M. Meier, and G. Lausen. Foundations of SPARQL query optimization. In ICDT, pages 4--33. ACM, 2010. Google ScholarDigital Library
- G. Serfiotis, I. Koffina, V. Christophides, and V. Tannen. Containment and minimization of RDF/S query patterns. In ISWC, volume 3729 of LNCS, pages 607--623. Springer, 2005. Google ScholarDigital Library
Index Terms
- Containment and equivalence of well-designed SPARQL
Recommendations
Static analysis and optimization of semantic web queries
Invited papers issueStatic analysis is a fundamental task in query optimization. In this article we study static analysis and optimization techniques for SPARQL, which is the standard language for querying Semantic Web data. Of particular interest for us is the optionality ...
Static analysis and optimization of semantic web queries
PODS '12: Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on Principles of Database SystemsStatic analysis is a fundamental task in query optimization. In this paper we study static analysis and optimization techniques for SPARQL, which is the standard language for querying Semantic Web data. Of particular interest for us is the optionality ...
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 ...
Comments