Document Open Access Logo

Beyond Well-designed SPARQL

Authors Mark Kaminski, Egor V. Kostylev

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2016.5.pdf
  • Filesize: 0.58 MB
  • 18 pages

Document Identifiers

Author Details

Mark Kaminski
Egor V. Kostylev

Cite As Get BibTex

Mark Kaminski and Egor V. Kostylev. Beyond Well-designed SPARQL. In 19th International Conference on Database Theory (ICDT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 48, pp. 5:1-5:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICDT.2016.5

Abstract

SPARQL is the standard query language for RDF data. The distinctive feature of SPARQL is the OPTIONAL operator, which allows for partial answers when complete answers are not available due to lack of information. However, optional matching is computationally expensive - query answering is PSPACE-complete. The well-designed fragment of SPARQL achieves much better computational properties by restricting the use of optional matching - query answering becomes coNP-complete. However, well-designed SPARQL captures far from all real-life queries - in fact, only about half of the queries over DBpedia that use OPTIONAL are well-designed.

In the present paper, we study queries outside of well-designed SPARQL. We introduce the class of weakly well-designed queries that subsumes well-designed queries and includes most common meaningful non-well-designed queries: our analysis shows that the new fragment captures about 99% of DBpedia queries with OPTIONAL. At the same time, query answering for weakly well-designed SPARQL remains coNP-complete, and our fragment is in a certain sense maximal for this complexity. We show that the fragment's expressive power is strictly in-between well-designed and full SPARQL. Finally, we provide an intuitive normal form for weakly well-designed queries and study the complexity of containment and equivalence.

Subject Classification

Keywords
  • RDF
  • Query languages
  • SPARQL
  • Optional matching

Metrics

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

References

  1. AllegroGraph. URL: http://franz.com/agraph/allegrograph/.
  2. Apache Jena. URL: http://jena.apache.org.
  3. RDF4J. URL: http://rdf4j.org.
  4. Virtuoso Universal Server. URL: http://virtuoso.openlinksw.com.
  5. Renzo Angles and Claudio Gutierrez. The expressive power of SPARQL. In ISWC, pages 114-129, 2008. Google Scholar
  6. 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 WWW, pages 629-638, 2012. Google Scholar
  7. Marcelo Arenas, Georg Gottlob, and Andreas Pieris. Expressive languages for querying the semantic web. In PODS, pages 14-26, 2014. Google Scholar
  8. Marcelo Arenas and Jorge Pérez. Querying semantic web data with SPARQL. In PODS, pages 305-316, 2011. Google Scholar
  9. Mario Arias Gallego, Javier D. Fernández, Miguel A. Martínez-Prieto, and Pablo de la Fuente. An empirical study of real-world SPARQL queries. In USEWOD, 2011. arXiv:1103.5043. Google Scholar
  10. Bettina Berendt, Laura Hollink, Markus Luczak-Rösch, Knud Möller, and David Vallet. USEWOD2013: 3rd international workshop on usage analysis and the web of data. In ESWC, 2013. Google Scholar
  11. Bettina Berendt, Laura Hollink, Markus Luczak-Rösch, Knud Möller, and David Vallet. USEWOD2014: 4th international workshop on usage analysis and the web of data. In ESWC, 2014. Google Scholar
  12. Stefan Bischof, Markus Krötzsch, Axel Polleres, and Sebastian Rudolph. Schema-agnostic query rewriting in SPARQL 1.1. In ISWC, pages 584-600, 2014. Google Scholar
  13. Carlos Buil-Aranda, Marcelo Arenas, and Oscar Corcho. Semantics and optimization of the SPARQL 1.1 federation extension. In ESWC, pages 1-15. Springer, 2011. Google Scholar
  14. Carlos Buil Aranda, Axel Polleres, and Jürgen Umbrich. Strategies for executing federated queries in SPARQL1.1. In ISWC, pages 390-405, 2014. Google Scholar
  15. 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
  16. Melisachew Wudage Chekol, Jérôme Euzenat, Pierre Genevès, and Nabil Layaïda. SPARQL query containment under SHI axioms. In AAAI, pages 10-16, 2012. Google Scholar
  17. Richard Cyganiak, David Wood, and Markus Lanthaler. RDF 1.1 concepts and abstract syntax. W3C recommendation, W3C, February 2014. URL: http://www.w3.org/TR/rdf11-concepts/.
  18. 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
  19. Harry Halpin and James Cheney. Dynamic provenance for SPARQL updates. In ISWC, pages 425-440, 2014. Google Scholar
  20. Steve Harris and Andy Seaborne. SPARQL 1.1 query language. W3C recommendation, W3C, March 2013. URL: http://www.w3.org/TR/sparql11-query/.
  21. Patrick J. Hayes and Peter F. Patel-Schneider. RDF 1.1 semantics. W3C recommendation, W3C, February 2014. URL: http://www.w3.org/TR/rdf11-mt/.
  22. Roman Kontchakov, Martin Rezk, Mariano Rodriguez-Muro, Guohui Xiao, and Michael Zakharyaschev. Answering SPARQL queries over databases under OWL 2 QL entailment regime. In ISWC, pages 552-567, 2014. Google Scholar
  23. Egor V. Kostylev and Bernardo Cuenca Grau. On the semantics of SPARQL queries with optional matching under entailment regimes. In ISWC, pages 374-389, 2014. Google Scholar
  24. Egor V. Kostylev, Juan L. Reutter, Miguel Romero, and Domagoj Vrgoc. SPARQL with property paths. In ICWC, pages 3-18, 2015. Google Scholar
  25. Egor V. Kostylev, Juan L. Reutter, and Martín Ugarte. CONSTRUCT queries in SPARQL. In ICDT, pages 212-229, 2015. Google Scholar
  26. Jens Lehmann, Robert Isele, Max Jakob, Anja Jentzsch, Dimitris Kontokostas, Pablo N. Mendes, Sebastian Hellmann, Mohamed Morsey, Patrick van Kleef, Sören Auer, and Christian Bizer. DBpedia - A large-scale, multilingual knowledge base extracted from Wikipedia. Semantic Web, 6(2):167-195, 2015. Google Scholar
  27. Andrés Letelier, Jorge Pérez, Reinhard Pichler, and Sebastian Skritek. Static analysis and optimization of semantic web queries. ACM Transactions on Database Systems, 38(4:25), 2013. Google Scholar
  28. Katja Losemann and Wim Martens. The complexity of evaluating path expressions in SPARQL. In PODS, pages 101-112, 2012. Google Scholar
  29. Frank Manola, Eric Miller, and Brian McBride. RDF 1.1 primer. W3C working group note, W3C, June 2014. URL: http://www.w3.org/TR/rdf11-primer/.
  30. Jorge Pérez, Marcelo Arenas, and Claudio Gutierrez. Semantics and complexity of SPARQL. In ISWC, pages 30-43, 2006. Google Scholar
  31. Jorge Pérez, Marcelo Arenas, and Claudio Gutierrez. Semantics and complexity of SPARQL. ACM Transactions on Database Systems, 34(3), 2009. Google Scholar
  32. François Picalausa and Stijn Vansummeren. What are real SPARQL queries like? In SWIM, 2011. Google Scholar
  33. Reinhard Pichler and Sebastian Skritek. Containment and equivalence of well-designed SPARQL. In PODS, pages 39-50, 2014. Google Scholar
  34. 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
  35. Eric Prud'hommeaux and Andy Seaborne. SPARQL query language for RDF. W3C recommendation, W3C, January 2008. URL: http://www.w3.org/TR/rdf-sparql-query/.
  36. Michael Schmidt, Michael Meier, and Georg Lausen. Foundations of SPARQL query optimization. In ICDT, pages 4-33, 2010. Google Scholar
  37. Xiaowang Zhang and Jan Van den Bussche. On the primitivity of operators in SPARQL. Information Processing Letters, 114(9):480-485, 2014. Google Scholar
  38. Xiaowang Zhang and Jan Van den Bussche. On the satisfiability problem for SPARQL patterns, 2014. arXiv:1406.1404. Google Scholar
  39. Xiaowang Zhang and Jan Van den Bussche. On the power of SPARQL in expressing navigational queries. The Computer Journal, 58(11):2841-2851, 2015. Google Scholar
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