The Limits on Combining Recursive Horn Rules with Description Logics

AAAI 1996

TL;DR

This paper investigates the boundaries of combining recursive, function-free Horn rules with expressive description logics (DLs). The authors identify specific DL constructors that, when combined with recursive rules, lead to undecidable reasoning. They then propose a decidable subset of these formalisms and a restriction on rules that preserves decidability, offering practical solutions for integrating knowledge representation paradigms.

What Problem Does This Paper Address?

Artificial Intelligence applications often benefit from combining different knowledge representation formalisms. Horn rule languages are excellent for representing general rules and are computationally tractable, but they struggle with rich hierarchical structures. Description Logics (DLs), on the other hand, excel at modeling these hierarchies. Many real-world applications, like integrating information from diverse sources or modeling complex systems, would gain significant power by merging these two approaches. However, the combination of recursive Horn rules (which are common for expressing transitive relationships or graph traversals) and expressive DLs can lead to undecidable reasoning problems, making practical implementation challenging. This paper aims to precisely delineate where this decidability boundary lies and to identify practical, decidable combinations.

Methods

The paper explores the decidability of combining recursive, function-free Horn rules with the description logic ALCNR. The authors take a systematic approach:

  1. Identifying Undecidable Constructors: They first demonstrate that certain core DL constructors, specifically role restrictions (∃R.C) and upper-bound number restrictions (≤ n R), when combined with recursive Horn rules, inherently lead to undecidable inference. This is shown by encoding Turing machine computations into knowledge bases.
  2. Proposing a Decidable Subset: To regain decidability, they propose a maximal subset of ALCNR, termed CARIN-MARC, that can be combined with recursive Horn rules. This subset excludes the problematic constructors (∃R.C and ≤ n R) and requires acyclic concept definitions in the terminology.
  3. Introducing Role-Safe Rules: As an alternative approach to achieve decidability, they introduce the concept of "role-safe" Horn rules. A rule is role-safe if any role atom in its antecedent has at least one variable that also appears in an ordinary (non-concept, non-role) predicate atom. This restriction, while seemingly minor, allows for the combination of all ALCNR constructors and cyclic terminologies while maintaining decidable reasoning.
  4. Inference Algorithm: For the decidable CARIN-MARC language, they outline a sound and complete inference algorithm. This algorithm involves a "propagation phase" to generate finite completions of ground facts and a second phase that evaluates Horn rules on each completion.

Datasets

Not discussed in the paper. The paper focuses on theoretical decidability and reasoning procedures rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Core DL Constructors Cause Undecidability: It's surprising that fundamental DL constructors like role restrictions (∃R.C) and upper-bound number restrictions (≤ n R) are the primary culprits for undecidability when combined with recursive rules. This highlights a fundamental tension between expressive hierarchical modeling and rule-based reasoning.
  • Role-Safety as a Practical Decidability Enabler: The concept of "role-safe" rules is a key insight. It provides a practical way to retain the expressiveness of full ALCNR and cyclic terminologies while ensuring decidability, by restricting how variables can be used in role atoms within rules. This is analogous to safety conditions in deductive databases.
  • Decidability is Achievable with Careful Restriction: The paper demonstrates that decidability is not an all-or-nothing proposition. By carefully selecting DL constructors or restricting rule forms, decidable hybrid reasoning systems can be constructed.
  • CARIN-MARC as a Maximal Decidable Subset: Identifying CARIN-MARC as a maximal subset of ALCNR that can be combined with recursive rules provides a clear theoretical boundary for decidable combinations without rule restrictions.

Key Results

  • The paper proves that the presence of ∃R.C or ≤ n R constructors in a DL, when combined with recursive function-free Horn rules, leads to undecidable reasoning problems (Theorems 1 & 2).
  • A decidable subset of CARIN-ALCNR, called CARIN-MARC, is identified by excluding ∃R.C and ≤ n R and requiring acyclic concept definitions. A sound and complete inference procedure for this subset is described.
  • The paper introduces the concept of "role-safe" Horn rules and proves that CARIN-ALCNR with role-safe rules (and even cyclic terminologies) is decidable (Theorem 7).
  • Reasoning in CARIN-MARC is shown to be CO-NP-Complete with respect to the number of ground facts and terminology size, and polynomial in the number of rules (Theorem 6).

Limitations and Future Work

  • Focus on Function-Free Rules: The results are specific to function-free Horn rules. The paper notes that recursive Horn rules with arbitrary function symbols lead to undecidability, but the focus here is on the decidable subset.
  • Complexity: While decidable, the reasoning complexity for CARIN-MARC can be high (CO-NP-Complete).
  • Future Work: The authors mention ongoing work on optimizing inference in CARIN-ACCNR, specifically by identifying irrelevant completions and interleaving reasoning steps. They also suggest exploring other methods for optimizing inference. The paper also implicitly points towards further research into other "safe" rule restrictions or DL subsets that might offer different trade-offs between expressiveness and decidability.

Summary updated

BibTeX
@inproceedings{1996limits,
  title = {{The Limits on Combining Recursive Horn Rules with Description Logics}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure