Abstract
Computing logical consequences, or materialization, in large-scale knowledge bases is a critical task for the Semantic Web. However, expressive logics like Horn $SHOIF$ pose significant scalability challenges due to features like nominals and functional roles. This paper presents a novel abstraction refinement framework that compresses massive datasets into smaller abstract versions for efficient reasoning. Our approach is the first to be complete for Horn $SHOIF$, utilizing a unique type-based abstraction that preserves complex dependencies. Experimental results demonstrate that our prototype, Orar, achieves up to four orders of magnitude in data compression and outperforms state-of-the-art reasoners on several large-scale benchmarks.
Introduction
In Description Logics (DLs), materialization involves computing all implicit facts (the ABox) from explicit data and a schema (the TBox). As datasets grow to millions of assertions, traditional reasoners often fail to scale. Abstraction refinement has emerged as a promising strategy: it involves creating a smaller "abstract" dataset where one individual represents many similar ones, reasoning over this summary, and mapping results back. The difficulty lies in maintaining completeness for expressive logics where simple summaries lose critical information.
The Logic: Horn $SHOIF$
The authors focus on Horn $SHOIF$, a logic that includes complex features such as nominals (referring to specific individuals), transitive roles, and functionality. These features break the "tree-model property" common in simpler DLs, making abstraction significantly harder.
Methodology
The proposed framework extends abstraction refinement in three key ways:
- Advanced Type-Based Abstraction: Individuals are grouped into types based on their properties. To handle role and equality assertions correctly, each type is represented by two distinct individuals in the abstract model. This allows the reasoner to distinguish between reflexive relationships and those between distinct but similar individuals.
- Iterative Refinement: The process is an "under-approximation" loop. If the initial abstraction is insufficient, the system uses the results to refine the model until a fixpoint is reached, ensuring completeness.
- Decoupled Materialization Rules: A new set of formal rules for Horn $SHOIF$ consequences provides the theoretical foundation for the abstraction, separating data-dependent reasoning from schema-level logic.
Experimental Results
The researchers evaluated their prototype, Orar, against several benchmarks including NPD, DBPedia+, and IMDb+. The results highlight the efficiency of the abstraction process.
As shown in the table above, the abstract ABox can be over 10,000 times smaller than the original (e.g., IMDb+). In many cases, Orar reached a fixpoint in just one or two steps. Crucially, Orar successfully materialized ontologies where high-performance reasoners like Konclude timed out or exceeded memory limits.
Conclusion
This work demonstrates that abstraction refinement is a powerful tool for scaling reasoning in expressive DLs. By cleverly handling non-tree-like structures through multi-representative types, the authors provide a complete and efficient materialization method for Horn $SHOIF$. Future work will explore extending these techniques to non-Horn logics, which involve even more complex non-deterministic reasoning.
Summary updated