TL;DR
This paper introduces the first approach to automatically repair inconsistent temporal knowledge bases (TKBs) expressed in a temporal Description Logic called TDL-Lite. By translating TDL-Lite into standard Description Logic (DL), they leverage existing DL reasoners to detect inconsistencies and then propose a novel "best temporal repair" semantic that prioritizes assertions based on their temporal weight and rigidity, aiming for more meaningful repairs in time-aware applications.
What Problem Does This Paper Address?
Many real-world applications, such as banking and medical records, require modeling knowledge that changes over time. Temporal Description Logics (TDLs) are designed for this purpose, but they often struggle with inconsistencies that arise in the data (ABox) over time, especially when dealing with complex temporal relationships. While previous work has focused on detecting inconsistencies or querying inconsistent data, automatically repairing these temporal knowledge bases has remained an open challenge. This paper tackles this gap by proposing a method to clean up inconsistent temporal data in a principled way, ensuring the repaired knowledge base is consistent and the repair process is temporally aware.
Methods
The authors propose a two-step approach:
- Inconsistency Detection via Translation: They first translate TDL-Lite knowledge bases into standard Description Logic (DL) knowledge bases. This translation is crucial because it allows them to utilize highly optimized DL reasoners (specifically, Pellet) to detect inconsistencies. This translation provides a tight NP-complete upper bound for TDL-Lite concept satisfiability and, importantly, allows DL reasoners to provide precise explanations for why an inconsistency exists, identifying the specific data assertions involved.
- Temporal Repair Semantics: Based on the detected inconsistencies and their explanations, they propose a method for automatically computing the "best temporal repair." This involves:
- Inconsistency Graph: Building a graph that visually represents the conflicts between inconsistent assertions.
- Temporal Weighting: Assigning a temporal weight to each inconsistent assertion. This weight considers the assertion's timestamp and whether it involves "rigid predicates" (concepts or roles whose interpretation doesn't change over time). Rigid predicates contribute a "duration" to the weight, effectively penalizing older assertions involving them.
- Best Repair Selection: Using the temporal weights to guide the repair process. When multiple assertions are equally inconsistent (i.e., have the same "inconsistency degree"), the algorithm prioritizes removing assertions with lower temporal weights, aiming to preserve more recent or non-rigid data. This is framed as finding a minimal set of assertions to remove to restore consistency, guided by temporal relevance.
Datasets
Not discussed in the paper. The paper uses a running example (Example 1) to illustrate its concepts, but no formal datasets are mentioned for training or evaluation.
Key Insights and Ideas
- Bridging Temporal and Atemporal Logics: The translation from TDL-Lite to DL is a powerful technique. It allows leveraging mature and efficient DL reasoners for temporal reasoning tasks, which is a significant practical advantage.
- Explanation-Driven Repair: Inconsistency detection is not just about finding errors but understanding why they occur. The paper emphasizes using DL reasoner explanations to pinpoint the problematic assertions, which is essential for targeted repair.
- Temporal Awareness in Repair: Simply removing inconsistent data might not be ideal. The concept of "temporal weight" is key, as it introduces a notion of temporal relevance. Assertions involving rigid predicates or recent timestamps are implicitly favored, leading to repairs that are more aligned with the temporal nature of the data.
- "Best" Repair is Subjective: The paper acknowledges that "best" repair can be subjective. By introducing temporal weights and allowing user-defined durations for rigid predicates, they offer a semi-automatic approach that can be guided by user preferences, making the repair process more adaptable.
Key Results
The paper presents a formal framework and methodology for detecting and repairing inconsistencies in TDL-Lite knowledge bases. While specific quantitative results are not detailed, the key findings are:
- A novel translation from TDL-Lite to DL-Lite that preserves satisfiability and allows for NP-complete upper bounds on satisfiability checking.
- The first approach to automatically repair ABoxes in TDL knowledge bases based on a "maximal repair" semantic, extended with temporal considerations.
- A method for assigning temporal weights to inconsistent assertions, guiding the repair process towards preserving more recent or non-rigid data.
- The proposed repair computation is shown to be polynomial in the number of inconsistent data assertions.
Limitations and Future Work
- TDL-Lite Fragment: The current work focuses on a specific fragment of TDL-Lite, primarily using future temporal operators (◇F, □F) and restricting their use to the right-hand side of inclusions.
- Rigid Predicates and Temporal Weights: The definition of temporal weights relies on the identification of rigid predicates and a user-defined duration (σ). The paper suggests that a user would fix these values based on preferences, implying a semi-automatic process.
- Future Work: The authors propose several avenues for future research:
- Enriching TDL-Lite with temporal past operators and allowing them on the left-hand side of GCIs.
- Investigating practical repair of KBs using combinations of LTL and DL-Lite logics that are first-order rewritable.
- Adding metric operators to TDL-Lite to augment temporal operators with time intervals.
- Implementing a repair framework and evaluating its scalability and effectiveness against other temporal query answering semantics.
Summary updated