Document Open Access Logo

CONSTRUCT Queries in SPARQL

Authors Egor V. Kostylev, Juan L. Reutter, Martín Ugarte

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2015.212.pdf
  • Filesize: 0.64 MB
  • 18 pages

Document Identifiers

Author Details

Egor V. Kostylev
Juan L. Reutter
Martín Ugarte

Cite As Get BibTex

Egor V. Kostylev, Juan L. Reutter, and Martín Ugarte. CONSTRUCT Queries in SPARQL. In 18th International Conference on Database Theory (ICDT 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 31, pp. 212-229, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.ICDT.2015.212

Abstract

SPARQL has become the most popular language for querying RDF datasets, the standard data model for representing information in the Web. This query language has received a good deal of attention in the last few years: two versions of W3C standards have been issued, several SPARQL query engines have been deployed, and important theoretical foundations have been laid. However, many fundamental aspects of SPARQL queries are not yet fully understood. To this end, it is crucial to understand the correspondence between SPARQL and well-developed frameworks like relational algebra or first order logic. But one of the main obstacles on the way to such understanding is the fact that the well-studied fragments of SPARQL do not produce RDF as output.

In this paper we embark on the study of SPARQL CONSTRUCT queries, that is, queries which output RDF graphs. This class of queries takes rightful place in the standards and implementations, but contrary to SELECT queries, it has not yet attracted a worth-while theoretical research. Under this framework we are able to establish a strong connection between SPARQL and well-known logical and database formalisms. In particular, the fragment which does not allow for blank nodes in output templates corresponds to first order queries, its well-designed sub-fragment corresponds to positive first order queries, and the general language can be re-stated as a data exchange setting. These correspondences allow us to conclude that the general language is not composable, but the aforementioned blank-free fragments are. Finally, we enrich SPARQL with a recursion operator and establish fundamental properties of this extension.

Subject Classification

Keywords
  • RDF
  • SPARQL
  • Query Languages

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of databases, volume 8. Addison-Wesley Reading, 1995. Google Scholar
  2. Renzo Angles and Claudio Gutierrez. The expressive power of SPARQL. In ISWC, pages 114-129, 2008. Google Scholar
  3. Marcelo Arenas, Pablo Barcelo, Leonid Libkin, and Filip Murlak. Relational and XML data exchange. Synthesis Lectures on Data Management, 2(1):1-112, 2010. Google Scholar
  4. Marcelo Arenas, Sebastián Conca, and Jorge Pérez. Counting beyond a yottabyte, or how SPARQL 1.1 property paths will prevent adoption of the standard. In Proceedings of the 21st international conference on World Wide Web, pages 629-638. ACM, 2012. Google Scholar
  5. Marcelo Arenas and Jorge Pérez. Querying semantic web data with SPARQL. In PODS, pages 305-316, 2011. Google Scholar
  6. Pablo Barceló Baeza. Querying graph databases. In Proceedings of the 32nd symposium on Principles of database systems, pages 175-188. ACM, 2013. Google Scholar
  7. Carlos Buil-Aranda, Marcelo Arenas, and Oscar Corcho. Semantics and optimization of the SPARQL 1.1 federation extension. In The Semanic Web: Research and Applications, pages 1-15. Springer, 2011. Google Scholar
  8. Melisachew Wudage Chekol, Jérôme Euzenat, Pierre Genevès, and Nabil Layaïda. SPARQL query containment under SHI axioms. In AAAI, 2012. Google Scholar
  9. Melisachew Wudage Chekol, Jérôme Euzenat, Pierre Genevès, and Nabil Layaïda. SPARQL query containment under RDFS entailment regime. In IJCAR, pages 134-148, 2012. Google Scholar
  10. Rada Chirkova and George HL Fletcher. Towards well-behaved schema evolution. In WebDB, 2009. Google Scholar
  11. Mariano P. Consens and Alberto O. Mendelzon. GraphLog: a visual formalism for real life recursion. In Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, pages 404-416. ACM, 1990. Google Scholar
  12. Orri Erling and Ivan Mikhailov. RDF support in the virtuoso DBMS. In Networked Knowledge-Networked Media, pages 7-24. Springer, 2009. Google Scholar
  13. Ronald Fagin, Phokion G Kolaitis, Renée J Miller, and Lucian Popa. Data exchange: semantics and query answering. Theoretical Computer Science, 336(1):89-124, 2005. Google Scholar
  14. Ronald Fagin, Phokion G Kolaitis, Lucian Popa, and Wang-Chiew Tan. Composing schema mappings: Second-order dependencies to the rescue. ACM Transactions on Database Systems (TODS), 30(4):994-1055, 2005. Google Scholar
  15. Floris Geerts, Grigoris Karvounarakis, Vassilis Christophides, and Irini Fundulaki. Algebraic structures for capturing the provenance of SPARQL queries. In ICDT, pages 153-164, 2013. Google Scholar
  16. Birte Glimm and Chimezie Ogbuji. SPARQL 1.1 Entailment Regimes. W3C Recommendation, 2013. Available at URL: http://www.w3.org/TR/sparql11-entailment/.
  17. Harry Halpin and James Cheney. Dynamic provenance for SPARQL updates. In ISWC, 2014. Google Scholar
  18. Steve Harris, Nick Lamb, and Nigel Shadbolt. 4store: The design and implementation of a clustered rdf store. In 5th International Workshop on Scalable Semantic Web Knowledge Base Systems (SSWS2009), pages 94-109, 2009. Google Scholar
  19. Aidan Hogan, Marcelo Arenas, Alejandro Mallea, and Axel Polleres. Everything you always wanted to know about blank nodes. Web Semantics: Science, Services and Agents on the World Wide Web, 2014. Google Scholar
  20. Egor V. Kostylev and Bernardo Cuenca Grau. On the semantics of SPARQL queries with optional matching under entailment regimes. In ISWC, 2014. Google Scholar
  21. Maurizio Lenzerini. Data integration: A theoretical perspective. In Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 233-246. ACM, 2002. Google Scholar
  22. Andrés Letelier, Jorge Pérez, Reinhard Pichler, and Sebastian Skritek. Static analysis and optimization of semantic web queries. ACM Trans. Database Syst., 38(4):25, 2013. Google Scholar
  23. Leonid Libkin, Juan Reutter, and Domagoj Vrgoč. TriAL for RDF: adapting graph query languages for RDF data. In Proceedings of the 32nd symposium on Principles of database systems, pages 201-212. ACM, 2013. Google Scholar
  24. Katja Losemann and Wim Martens. The complexity of evaluating path expressions in SPARQL. In Proceedings of the 31st symposium on Principles of Database Systems, pages 101-112. ACM, 2012. Google Scholar
  25. Frank Manola and Eric Miller. RDF Primer. W3C Recommendation, 10 February 2004. Available at URL: http://www.w3.org/TR/2004/REC-rdf-primer-20040210/.
  26. Paolo Missier, Khalid Belhajjame, and James Cheney. The w3c prov family of specifications for modelling provenance metadata. In Proceedings of the 16th International Conference on Extending Database Technology, pages 773-776. ACM, 2013. Google Scholar
  27. Jorge Pérez, Marcelo Arenas, and Claudio Gutierrez. Semantics and complexity of SPARQL. ACM Trans. Database Syst., 34(3), 2009. Google Scholar
  28. Jorge Pérez, Marcelo Arenas, and Claudio Gutierrez. nSPARQL: A navigational language for RDF. Web Semantics: Science, Services and Agents on the World Wide Web, 8(4):255-270, 2010. Google Scholar
  29. François Picalausa and Stijn Vansummeren. What are real SPARQL queries like? In SWIM, 2011. Google Scholar
  30. Reinhard Pichler and Sebastian Skritek. Containment and equivalence of well-designed SPARQL. In Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 39-50. ACM, 2014. Google Scholar
  31. Axel Polleres and Johannes Peter Wallner. On the relation between SPARQL1.1 and answer set programming. Journal of Applied Non-Classical Logics, 23(1-2):159-212, 2013. Google Scholar
  32. Eric Prud'hommeaux and Andy Seaborne. SPARQL query language for RDF. W3C Recommendation, 2008. Available at URL: http://www.w3.org/TR/rdf-sparql-query/.
  33. Eric Prud'hommeaux, Andy Seaborne, et al. SPARQL query language for RDF, 2006. Google Scholar
  34. Raghu Ramakrishnan, Johannes Gehrke, and Johannes Gehrke. Database management systems, volume 3. McGraw-Hill New York, 2003. Google Scholar
  35. Edward L Robertson. Triadic relations: An algebra for the semantic web. In Semantic Web and Databases, pages 91-108. Springer, 2005. Google Scholar
  36. Michael Schmidt, Michael Meier, and Georg Lausen. Foundations of SPARQL query optimization. In ICDT, pages 4-33, 2010. Google Scholar
  37. Andy Seaborne. ARQ-A SPARQL processor for Jena. Obtained through the Internet: http://jena. sourceforge. net/ARQ/, 2010. Google Scholar
  38. Moshe Y Vardi. The complexity of relational query languages. In Proceedings of the fourteenth annual ACM symposium on Theory of computing, pages 137-146. ACM, 1982. Google Scholar
  39. W3C SPARQL Working Group. SPARQL 1.1 Query language. W3C Recommendation, 21 March 2013. Available at URL: http://www.w3.org/TR/sparql11-query/.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact