Beyond Well-Designed SPARQL
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-compl...
| Main Authors: | , |
|---|---|
| Format: | Conference item |
| Published: |
Dagstuhl Publishing
2015
|
| _version_ | 1826276348087238656 |
|---|---|
| author | Kostylev, E Kaminski, M |
| author_facet | Kostylev, E Kaminski, M |
| author_sort | Kostylev, E |
| collection | OXFORD |
| description | 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 welldesigned and full SPARQL. Finally, we provide an intuitive normal form for weakly well-designed queries and study the complexity of containment and equivalence. |
| first_indexed | 2024-03-06T23:12:36Z |
| format | Conference item |
| id | oxford-uuid:66009c7f-493c-4f45-8130-e95d326074d9 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T23:12:36Z |
| publishDate | 2015 |
| publisher | Dagstuhl Publishing |
| record_format | dspace |
| spelling | oxford-uuid:66009c7f-493c-4f45-8130-e95d326074d92022-03-26T18:29:08ZBeyond Well-Designed SPARQLConference itemhttp://purl.org/coar/resource_type/c_5794uuid:66009c7f-493c-4f45-8130-e95d326074d9Symplectic Elements at OxfordDagstuhl Publishing2015Kostylev, EKaminski, MSPARQL 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 welldesigned and full SPARQL. Finally, we provide an intuitive normal form for weakly well-designed queries and study the complexity of containment and equivalence. |
| spellingShingle | Kostylev, E Kaminski, M Beyond Well-Designed SPARQL |
| title | Beyond Well-Designed SPARQL |
| title_full | Beyond Well-Designed SPARQL |
| title_fullStr | Beyond Well-Designed SPARQL |
| title_full_unstemmed | Beyond Well-Designed SPARQL |
| title_short | Beyond Well-Designed SPARQL |
| title_sort | beyond well designed sparql |
| work_keys_str_mv | AT kostyleve beyondwelldesignedsparql AT kaminskim beyondwelldesignedsparql |