TL;DR
This paper tackles the challenge of efficiently reasoning with complex Description Logics (DLs) by translating them into rule-based systems. The authors introduce novel rewritings for the DL ALCHIQ (which includes disjunctions, number restrictions, and inverse roles) into disjunctive Datalog, achieving polynomial-sized rule sets and bounded rule sizes, a significant improvement over previous methods.
What Problem Does This Paper Address?
Description Logics (DLs) are powerful knowledge representation formalisms, but reasoning with them can be computationally expensive. A common approach to improve reasoning efficiency is to translate DL knowledge bases (ontologies) into rule languages, which often have more scalable reasoning engines. However, for expressive DLs like ALCHIQ, which combine features like disjunctions, number restrictions, and inverse roles, existing translation methods either produce excessively large rule sets or are not polynomial. This paper aims to bridge this gap by developing polynomial-sized rewritings for ALCHIQ into disjunctive Datalog, a rule language that can handle these complex features. The goal is to enable the use of existing Datalog reasoners for ALCHIQ ontologies while maintaining good performance.
Methods
The paper proposes two main rewriting approaches for ALCHIQ:
- Rewriting to Datalog<sup>∨</sup> (with unbounded rule sizes): This method translates ALCHIQ into a disjunctive Datalog language. While the resulting rule sets are not guaranteed to be of bounded size (meaning their size can grow with the complexity of the DL axioms), they are still polynomial in the size of the input ontology. This approach is a step towards handling the expressiveness of ALCHIQ in a rule-based setting.
- Rewriting to Datalog<sup>∨∃</sup> (with bounded rule sizes): This is the more significant contribution. The authors introduce a rewriting that produces disjunctive Datalog rules with existential quantifiers in their heads, and crucially, these rules are of bounded size. This means the size of each rule is independent of the input ontology's complexity, a property highly desirable for practical implementations. This is achieved by using a "type-based" approach, where rules encode the local structure of DL interpretations and their relationships. The paper also presents a technique for Horn-ALCHIQ (the disjunction-free fragment) that results in terminating Datalog<sup>∨∃</sup> rules of bounded size.
The rewritings are established through detailed formal definitions and proofs of correctness, demonstrating that the translated rule sets preserve the entailment properties of the original DL ontologies.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- The power of existential quantifiers in rule heads: The paper highlights that allowing existential quantifiers in the heads of disjunctive Datalog rules is key to achieving bounded-size rewritings for expressive DLs like ALCHIQ. This is a crucial insight for bridging the gap between DL expressivity and rule-based reasoning efficiency.
- Type-based reasoning for DLs: The core of the bounded-size rewriting relies on encoding DL "types" (local environments of individuals) into Datalog predicates. This allows for a more compact representation of complex DL axioms, leading to smaller rule sets.
- Bridging the gap between DLs and Datalog: The work demonstrates that even highly expressive DLs with features like number restrictions and inverse roles can be effectively translated into Datalog variants, opening up possibilities for using existing, scalable Datalog reasoners.
- The importance of bounded rule sizes: The paper emphasizes that while polynomial rewritings are good, bounded rule sizes are even better for practical implementations, as they ensure predictable performance and avoid rule explosion.
Key Results
- Polynomial rewriting of ALCHIQ to Datalog<sup>∨</sup>: The paper provides a method to translate ALCHIQ into disjunctive Datalog, preserving entailments.
- Polynomial rewriting of ALCHIQ to Datalog<sup>∨∃</sup> with bounded rule sizes: This is a significant result, offering a translation into disjunctive Datalog with existential quantifiers where the rules themselves have a fixed, bounded size, independent of the input ontology.
- Polynomial rewriting of Horn-ALCHIQ to terminating Datalog<sup>∨∃</sup> with bounded rule sizes: A specific result for the Horn fragment, ensuring termination and bounded rule sizes.
Limitations and Future Work
- Complexity of reasoning: While the rewritings are polynomial in the size of the ontology, the resulting Datalog reasoning problem can still be computationally expensive (e.g., co-NP data complexity for ALCHIQ). The paper notes that these are not worst-case optimal for all cases, and the quest for optimal rule-based approaches for such expressive DLs remains open.
- Future Work: The authors suggest extending these rewriting techniques to even more expressive DL languages (like ALCHOIQ) and decidable rule languages. They also mention exploring alternative techniques for achieving bounded-size rewritings, potentially using weaker chase variants or binary counters. The potential for adapting existing consequence-based reasoning procedures for Horn-ALCHIQ to Datalog<sup>∨∃</sup> is also highlighted.
Summary updated