Conference item
Beyond well-designed SPARQL
- 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.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, pdf, 598.8KB, Terms of use)
-
- Publisher copy:
- 10.4230/LIPIcs.ICDT.2016.5
Authors
- Publisher:
- Schloss Dagstuhl
- Host title:
- 19th International Conference on Database Theory (ICDT 2016)
- Pages:
- 5:1-5:18
- Series:
- Leibniz International Proceedings in Informatics
- Series number:
- 48
- Publication date:
- 2016-03-14
- Event title:
- 19th International Conference on Database Theory (ICDT 2016)
- Event location:
- Bordeaux, France
- Event start date:
- 2016-03-15
- Event end date:
- 2016-03-18
- DOI:
- EISSN:
-
1868-8969
- ISSN:
-
1868-8969
- ISBN:
- 978-3-95977-002-6
- Language:
-
English
- Keywords:
- Pubs id:
-
pubs:580314
- UUID:
-
uuid:66009c7f-493c-4f45-8130-e95d326074d9
- Local pid:
-
pubs:580314
- Source identifiers:
-
580314
- Deposit date:
-
2015-12-21
Terms of use
- Copyright holder:
- Mark Kaminski and Egor V Kostylev
- Copyright date:
- 2016
- Rights statement:
- © Mark Kaminski and Egor V. Kostylev; licensed under Creative Commons License CC-BY.
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record