Complexity and Expressive Power of Weakly Well-Designed SPARQL

Area of Science:

• Computer Science
• Database Systems
• Artificial Intelligence

Background:

• SPARQL is the standard query language for RDF data.
• The OPTIONAL operator in SPARQL allows partial answers but is computationally expensive (PSPACE-complete).
• Well-designed SPARQL fragments improve efficiency (coNP-complete) but capture limited real-world queries.

Purpose of the Study:

• To address the limitations of well-designed SPARQL by studying queries outside this fragment.
• To introduce and analyze a new class of queries: weakly well-designed SPARQL.
• To improve the efficiency and expressiveness of SPARQL query answering for RDF data.

Main Methods:

• Introduction of the weakly well-designed SPARQL query class.
• Analysis of query answering complexity for the new fragment.
• Comparison of expressive power with well-designed SPARQL and full SPARQL.
• Development of a normal form for weakly well-designed queries.
• Study of query containment and equivalence for the new fragment.

Main Results:

• The weakly well-designed fragment subsumes well-designed SPARQL and captures over 99% of DBpedia queries using OPTIONAL.
• Query answering for weakly well-designed SPARQL remains coNP-complete, representing a maximal fragment for this complexity.
• The expressive power of weakly well-designed SPARQL is strictly between well-designed SPARQL and full SPARQL.

Conclusions:

• Weakly well-designed SPARQL offers a practical and efficient solution for a vast majority of real-world SPARQL queries with OPTIONAL.
• The new fragment provides a balance between expressive power and computational tractability.
• Further research includes studying the complexity of containment and equivalence for this new query class.