TL;DR
This paper tackles the challenge of representing complex relationships in knowledge bases, specifically in medical terminology. They show that extending a powerful description logic ({$\mathcal SHIQ$}) with certain role inclusion axioms leads to undecidability, but a restricted version with acyclic axioms is decidable. They introduce a tableau-based algorithm for this decidable logic, demonstrating its practical applicability.
What Problem Does This Paper Address?
Knowledge representation systems, particularly those used for complex domains like medical terminology, need to express nuanced relationships between concepts. Description Logics (DLs) are a popular choice for this, with {$\mathcal SHIQ$} being a highly expressive one. {$\mathcal SHIQ$} already handles features like inverse roles and transitive roles. However, it struggles to capture "propagation" of properties, such as inferring that a fracture in a specific body part (e.g., neck of the femur) is also a fracture of the larger structure (e.g., the femur). This kind of inference is crucial for medical applications.
The authors propose extending {$\mathcal SHIQ$} with role inclusion axioms of the form $R \circ S \sqsubseteq P$, which allows expressing this propagation. For example, hasLocation composed with isDivisionOf implies hasLocation. The problem is that even a restricted form of these axioms ($R \sqsubseteq S$ or $S \sqsubseteq R$) makes {$\mathcal SHIQ$} undecidable, meaning there's no guaranteed way to determine if a statement is true or false. This paper investigates how to regain decidability while retaining useful expressiveness.
Methods
The core of the paper is demonstrating decidability for a restricted version of the logic and providing an algorithm.
- Undecidability Proof: They first prove that {$\mathcal SHIQ$} with general role inclusion axioms of the form $R \circ S \sqsubseteq P$ is undecidable. This is achieved by reducing the undecidable "domino problem" to {$\mathcal SHIQ$} satisfiability.
- Regaining Decidability: They show that restricting role inclusion axioms to acyclic sets ($R \sqsubseteq S$ or $S \sqsubseteq R$ where there are no cyclic dependencies) makes the logic decidable. This decidable logic is named {$\mathcal RIQ$}.
- Tableau Algorithm: A tableau-based decision procedure is developed for {$\mathcal RIQ$}. This algorithm works by transforming concepts involving roles into concepts involving non-deterministic finite automata (NFAs). These NFAs are derived from the role hierarchy. The algorithm attempts to construct a "tableau" (an abstraction of a model) for a given concept. If it can construct a complete and clash-free tableau, the concept is satisfiable.
- Syntactic Transformations: To handle the role hierarchy, they introduce a process to "unfold" or "expand" it into an explicit form, {$\text{exp}(R)$}. This involves converting role inclusions into regular expressions and then into automata.
- Avoiding Exponential Blow-up: A potential issue is that {$\text{exp}(R)$} can be exponentially large in the size of $R$. They identify a "simple" acyclic role hierarchy that avoids this blow-up, making the algorithm's complexity more manageable.
- FaCT Implementation: The authors extended the existing {$\mathcal{FaCT}$} description logic reasoner to implement the {$\mathcal RIQ$} algorithm, including optimizations like using minimal deterministic NFAs.
Datasets
Not discussed in the paper. The paper focuses on theoretical decidability and algorithmic development, using the Galen medical terminology knowledge base for evaluation of the implemented system.
Key Insights and Ideas
- The "Propagation" Problem: The core insight is that expressing property propagation (e.g., a fracture in a part implies a fracture in the whole) is highly desirable but leads to undecidability in expressive DLs.
- Acyclicity is Key: The crucial finding is that restricting role inclusion axioms to be acyclic is sufficient to regain decidability, while still allowing for useful inferences. This suggests that cycles in role hierarchies might indicate modeling flaws.
- Automata for Roles: The novel approach of using non-deterministic finite automata (NFAs) to represent role hierarchies within concepts is a key technical contribution. This allows the tableau algorithm to reason about complex role paths.
- Practical Implications: The paper demonstrates that even with the complexity of automata, a practical implementation is feasible and can provide valuable inferential capabilities for real-world applications like medical terminologies.
Key Results
- {$\mathcal SHIQ$} extended with general role inclusion axioms ($R \circ S \sqsubseteq P$) is undecidable.
- {$\mathcal SHIQ$} extended with acyclic role inclusion axioms ($R \sqsubseteq S$ or $S \sqsubseteq R$) is decidable ({$\mathcal RIQ$}).
- A tableau-based decision procedure for {$\mathcal RIQ$} is presented.
- The {$\mathcal RIQ$} algorithm was implemented in the {$\mathcal{FaCT}$} reasoner.
- Preliminary evaluation on the Galen medical terminology KB showed that the {$\mathcal RIQ$} extension could handle role propagation axioms and provide new inferences (e.g., inferring a fracture of the neck of the femur from a fracture of the femur) with a manageable performance overhead.
Limitations and Future Work
- Exponential Blow-up: The size of {$\text{exp}(R)$} can be exponential in the size of $R$, which impacts the algorithm's complexity. While a "simple" role hierarchy avoids this, the general case remains a challenge. Future work aims to investigate if this blow-up can be avoided in general.
- Automata Minimization: The paper notes that the performance of the {$\mathcal RIQ$} algorithm depends on efficient handling of automata. While they use minimal deterministic NFAs, further optimization in this area could be beneficial.
- Complexity Analysis: A detailed analysis of the exact complexity of the {$\mathcal RIQ$} algorithm is left for future work.
Summary updated