Talks and Poster Presentations (with Proceedings-Entry):
R. Pichler, S. Skritek:
"Containment and equivalence of well-designed SPARQL";
Talk: ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems,
Snowbird, UT, USA,;
2014-06-22
- 2014-06-27; in: "Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems",
R. Hull, M. Grohe (ed.);
ACM,
(2014),
ISBN: 978-1-4503-2375-8;
39
- 50.
English 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.
Keywords:
SPARQL, RDF, Semantic Web, query containment
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1145/2594538.2594542
Related Projects:
Project Head Reinhard Pichler:
SEE: SPARQL Evaluation and Extensions
Created from the Publication Database of the Vienna University of Technology.