Embracing Change by Abstraction Materialization Maintenance for Large ABoxes

Markus Brenner, Birte GlimmIJCAI 2018 · DOI

TL;DR

This paper introduces ARDRed, a novel algorithm that combines Abstraction Refinement with the Delete/Rederive (DRed) technique to efficiently maintain materializations of large ontology ABoxes when data changes. It significantly speeds up incremental reasoning by compressing the ABox and handling updates more effectively than existing methods.

What Problem Does This Paper Address?

Ontology materialization, the process of explicitly storing all entailed atomic concept and role assertions, is crucial for fast query answering. However, materializing large ABoxes is computationally expensive. Existing techniques like Abstraction Refinement compress the ABox to speed up initial materialization. The challenge arises when the ABox changes: recomputing the entire materialization is slow. While incremental maintenance algorithms exist, they often struggle with expressive ontology languages (like those with existential quantifiers) and haven't been effectively combined with data compression techniques like Abstraction Refinement. This paper addresses the need for an efficient method to incrementally update materializations of large, expressive ontologies in the face of data additions and deletions.

Methods

The core contribution is the ARDRed (Abstraction Refinement Delete and Rederive) algorithm. It builds upon two key ideas:

  • Abstraction Refinement: This technique compresses a large ABox into a smaller "abstraction" that captures essential information. Materialization is performed on this abstraction, and results are then transferred back to the original ABox.
  • Delete/Rederive (DRed): This is a database-inspired algorithm for incremental ABox maintenance. It handles deletions by first "overdeleting" (removing more than necessary) and then "rederiving" the facts that are still entailed by the modified ABox.

ARDRed integrates these by:

  1. Bi-types and Bi-abstractions: To handle both the original ABox and the set of deletions, the authors introduce "bi-types" and "bi-abstractions." These structures capture information about both the current state of the ABox and the assertions that have been deleted.
  2. Phased Approach: ARDRed operates in three phases, mirroring DRed but adapted for abstractions:
  3. Overdeletion Phase: Uses bi-abstractions and the overdelete function to determine a set of assertions to remove.
  4. Rederivation Phase: Re-derives deletions using the modified ABox and the information from deleted assertions, again leveraging bi-abstractions.
  5. Reinsertion Phase: Re-inserts facts that are still entailed after deletions, using the reinsert function on abstractions.

The algorithm iteratively refines these abstractions until a fix-point is reached, ensuring correctness.

Datasets

The authors evaluated their approach using:

  • UOBM benchmark: Instances of 10, 50, and 100 universities (UOBM10, UOBM50, UOBM100).
  • NPD and Reactome ontologies: Well-known real-world ontologies.

All ontologies were preprocessed to retain only Horn ALCHI axioms and normalized. The experimental setup involved an initial ABox and 100 change ABoxes (additions or deletions) representing 1% of individuals.

Key Insights and Ideas

  • Combining Abstraction and Incremental Maintenance is Powerful: The paper demonstrates that by abstracting the ABox before applying incremental maintenance techniques like DRed, significant performance gains can be achieved, especially for large datasets.
  • Bi-types are Crucial for Handling Deletions: The introduction of bi-types and bi-abstractions is a key innovation, allowing the algorithms to reason effectively about both the current state of the ABox and the impact of deleted assertions.
  • Abstraction Benefits Scale with ABox Size: The performance advantage of ARDRed over DRed becomes more pronounced as the ABox size increases, aligning with the typical benefits of Abstraction Refinement.
  • Unoptimized Bi-types can be a Bottleneck: The authors note that unoptimized bi-types can sometimes lead to less favorable performance on certain real-world ontologies, suggesting areas for future improvement.

Key Results

  • Significant Speedups: ARDRed consistently outperforms the classical DRed implementation. For instance, in the "add-only" case with UOBM100, ARDRed achieves a materialization time of 176.26 seconds compared to DRed's 191.79 seconds. The "remove-only" case shows even more dramatic differences, with UOBM100 taking 281.48 seconds for ARDRed versus 3191.51 seconds for DRed (note: UOBM results are scaled by 0.1 in the figure for visual clarity).
  • Scalability: The advantage of ARDRed over DRed increases with ABox size.
  • Trade-offs: The add-remove case generally shows lower runtimes than add-only, and add-only is faster than remove-only, reflecting the higher cost of deletions.

Limitations and Future Work

  • Unoptimized Bi-types: The current implementation of bi-types can be a performance bottleneck for some real-world ontologies, as they might not sufficiently differentiate similar cases.
  • Future Optimizations: The authors suggest several avenues for future work:
  • Further optimizations for the Abstraction Refinement part, such as caching of types and more sophisticated type summarization in the overdeletion phase.
  • Integrating backward/forward optimization techniques into the DRed part of the algorithm.
  • Exploring more efficient ways to handle the creation and management of bi-types.

Summary updated

BibTeX
@inproceedings{brenner2018embracing,
  author = {Markus Brenner and Birte Glimm},
  title = {{Embracing Change by Abstraction Materialization Maintenance for Large ABoxes}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/244},
}
Figure