License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2016.5
URN: urn:nbn:de:0030-drops-57744
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5774/
Go to the corresponding LIPIcs Volume Portal

Kaminski, Mark ; Kostylev, Egor V.

Beyond Well-designed SPARQL

pdf-format:
4.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{kaminski_et_al:LIPIcs:2016:5774,
  author =	{Mark Kaminski and Egor V. Kostylev},
  title =	{{Beyond Well-designed SPARQL}},
  booktitle =	{19th International Conference on Database Theory (ICDT 2016)},
  pages =	{5:1--5:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-002-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{48},
  editor =	{Wim Martens and Thomas Zeume},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5774},
  URN =		{urn:nbn:de:0030-drops-57744},
  doi =		{10.4230/LIPIcs.ICDT.2016.5},
  annote =	{Keywords: RDF, Query languages, SPARQL, Optional matching}
}

Keywords: RDF, Query languages, SPARQL, Optional matching
Collection: 19th International Conference on Database Theory (ICDT 2016)
Issue Date: 2016
Date of publication: 14.03.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI