Computing Repairs of Inconsistent DL-Programs over EL Ontologies

Thomas Eiter, Michael Fink, Daria Stepanova

TL;DR

This paper tackles the problem of inconsistency in hybrid knowledge bases that combine Description Logics (DLs) with non-monotonic rules. The authors propose a novel approach to compute "repairs" for these inconsistent systems, specifically for DL-programs over EL ontologies, by generalizing existing techniques to handle incomplete information and large ontologies. This work is crucial for enabling robust reasoning in complex knowledge representation scenarios.

What Problem Does This Paper Address?

In the realm of Artificial Intelligence, combining the expressive power of Description Logics (DLs) for representing ontologies with the flexibility of non-monotonic rules for reasoning has led to powerful hybrid knowledge bases. However, this combination can easily lead to inconsistencies, where the system produces no meaningful answers. This paper focuses on addressing these inconsistencies by computing "repairs" – modifications to the knowledge base that restore consistency. Specifically, the authors tackle the challenge of repairing DL-programs that use EL ontologies, a widely used DL fragment. The core problem is that existing repair methods, which rely on "support sets" to guide the repair process, become computationally intractable for EL ontologies because the number of support sets can be prohibitively large or even infinite.

Methods

The paper introduces a generalized approach for computing repair answer sets that operates on partial (incomplete) support families. This is a key departure from previous work that required complete support families. To achieve this, the authors employ several novel techniques:

  • Datalog Query Rewriting: They leverage datalog query rewriting techniques to compute support sets for DL-atoms, which is more efficient than relying on TBox classification for EL ontologies.
  • TBox Approximation: To handle the complexity of EL ontologies, they approximate relevant parts of the TBox to the DL-Lite core language. This is done by exploiting the concept of "logical difference" between EL terminologies, allowing them to focus on the essential parts of the ontology for support set computation.
  • Support Hypergraphs: They introduce the notion of a "support hypergraph" derived from ontology hypergraphs. Analyzing these hypergraphs helps estimate the size and number of support sets needed, providing bounds for computational efficiency.
  • Declarative Implementation: A system prototype is developed using a declarative approach, leveraging rules to implement the repair computation. This system uses a replacement program that guesses the truth value of DL-atoms and then employs minimal hitting sets and postchecks to find valid repairs.

Datasets

The paper does not explicitly mention training datasets. However, for evaluation, they introduce and utilize:

  • Policy Benchmark: A variant of an example from the paper, modified to create inconsistencies.
  • OpenStreetMap Benchmark: Rules and axioms built on top of the MyITS ontology, using data extracted from the OpenStreetMap project. This benchmark is notable for its realistic data and potential for inaccuracies.
  • LUBM Benchmark: Rules applied to an EL version of the LUBM ontology, extended with specific axioms and constructed ABoxes.

Key Insights and Ideas

  • Partial Support Families are Sufficient: The most significant insight is that complete support families are often not necessary for effective repair computation, especially for EL ontologies. Partial families, even if incomplete, can guide the repair process efficiently.
  • TBox Approximation for Scalability: Approximating complex EL TBoxes to simpler DL-Lite core fragments is a powerful strategy to manage computational complexity without sacrificing too much accuracy.
  • Support Hypergraphs as Analytical Tools: The introduction of support hypergraphs provides a novel way to analyze the structure of support sets and derive bounds on their size and number, which is crucial for optimizing repair algorithms.
  • Declarative Repair for Practicality: A declarative implementation using ASP solvers makes the repair computation more accessible and potentially easier to extend.

Key Results

The paper presents a sound and, under certain conditions, complete algorithm for computing deletion repair answer sets for DL-programs over EL ontologies. Experimental evaluations on the introduced benchmarks demonstrate the practical feasibility of their approach:

  • Efficiency: The proposed method, especially when using partial support families, shows promising performance, often outperforming unrestricted settings and naive repair techniques.
  • Scalability: The approach scales well with increasing data sizes (e.g., A10, A250, A500 in the policy benchmark), with running times increasing gracefully.
  • Effectiveness: The system successfully identifies repairs for inconsistent DL-programs, even in complex scenarios with real-world data (OpenStreetMap).
  • Boundedness Benefits: Limiting the size or number of support sets can significantly improve performance, especially when these bounds are not too restrictive.

Limitations and Future Work

The authors acknowledge several limitations and suggest promising avenues for future research:

  • Completeness Guarantees: While the algorithm is sound, completeness (finding all repair answer sets) is guaranteed only if complete support families are known. For partial families, the algorithm might miss some repair answer sets, though an easy extension can ensure completeness.
  • Complexity of Support Set Computation: For expressive DLs beyond EL, efficient methods for support set construction remain a challenge due to their high complexity.
  • Modular DL-Programs: The current approach treats DL-programs as monolithic structures. Extending it to handle modular DL-programs is an interesting research direction.
  • Repairing Rules and Interfaces: The focus has been on repairing the data part (ABox) of the ontology. Future work could explore repairing rules and interfaces, which is a more challenging task.
  • Other Hybrid Formalisms: Investigating repair mechanisms for other hybrid formalisms, especially those involving heterogeneous sources, is a significant future challenge.
  • Theoretical Bounds: Further theoretical analysis on conditions for tractable support set computation and complexity of counting support sets is needed.

Summary updated

BibTeX
@article{eiter2016computing,
  author = {Thomas Eiter and Michael Fink and Daria Stepanova},
  title = {{Computing Repairs of Inconsistent DL-Programs over EL Ontologies}},
  journal = {J. Artif. Intell. Res.},
  year = {2016},
  doi = {10.1613/jair.5047},
}
Figure