Abstract
Standard SPARQL 1.1 faces significant challenges when querying RDF data under the OWL 2 QL entailment regime, particularly regarding general recursion and the decoupling of reasoning from queries. This paper introduces TriQ-Lite 1.0, a rule-based query language based on warded $Datalog^{\exists, \neg sg, \perp}$. By introducing the novel syntactic restriction of wardedness, the authors achieve a language that is both expressively complete for SPARQL under OWL 2 QL and computationally tractable (PTIME-complete).
Introduction
While SPARQL is the industry standard for RDF data, it suffers from two major limitations. First, its support for recursion is limited to property paths, which cannot express complex navigational patterns. Second, reasoning under OWL 2 QL often requires users to manually encode inference logic into their queries, violating the principle of decoupling the query from the knowledge base.
To address these, the authors propose TriQ-Lite 1.0. Unlike previous "composite" versions, TriQ-Lite 1.0 is a "plain" language—a single Datalog program that simplifies use while maintaining high expressive power.
Methodology: Taming Recursion with Wardedness
The core of TriQ-Lite 1.0 is warded $Datalog^{\exists, \neg sg, \perp}$. This flavor of Datalog supports existential quantification (creating new "null" objects), stratified grounded negation, and negative constraints. However, existential variables in recursive rules can lead to non-termination, known as the "infinite chase."
The authors introduce wardedness to solve this. A rule is warded if all "dangerous" variables—those that might be bound to non-constant values during the chase—are isolated within a single "ward" atom in the rule body. This ward ensures that dangerous variables only interact with the rest of the rule via "harmless" variables bound to database constants.
Key Insights and Results
The wardedness property represents a "sweet spot" in complexity. Relaxing this restriction leads to EXPTIME-hardness, while maintaining it keeps query evaluation PTIME-complete in terms of data complexity.
Key achievements of TriQ-Lite 1.0 include:
- Expressive Completeness: It can express any SPARQL query under the OWL 2 QL entailment regime.
- Decoupling: Reasoning logic is handled by the rules, allowing for simpler, more natural queries.
- Practicality: The language can be reduced to Unions of Conjunctive Queries (UCQs), making it compatible with existing RDBMS technologies.
Conclusion
TriQ-Lite 1.0 provides a robust, rule-based alternative to SPARQL for complex reasoning tasks. By balancing expressivity with computational efficiency through wardedness, it paves the way for more powerful and maintainable Semantic Web applications. Future work will focus on experimental evaluation and optimizing the reduction to UCQs for real-world database engines.
Summary updated