TL;DR
This paper tackles the challenge of querying large knowledge bases with expressive Description Logics (DLs), bridging the gap between theoretical algorithms and practical implementations. They introduce a novel method to compile "profiles" representing families of ABoxes, enabling efficient querying of these complex knowledge bases using Answer Set Programming (ASP).
What Problem Does This Paper Address?
Answering ontology-mediated queries (OMQs) is crucial for leveraging knowledge bases. However, a significant divide exists: lightweight DLs have practical reasoning algorithms and tools, while expressive DLs (like ALC) are primarily studied theoretically, with algorithms that are difficult to implement. This gap hinders the application of expressive DLs in real-world scenarios. The authors aim to bridge this by developing a method to compile representations of models for expressive DLs that can be efficiently queried, even for large datasets.
Methods
The core of their approach involves two main components:
- Profile-based Model Compilation: Instead of reasoning about specific ABoxes (datasets), they introduce "profiles" – sets of basic concepts and role relationships – to describe families of ABoxes. An algorithm takes a TBox (ontology schema) and a set of profiles as input and compiles a "type table." This type table represents a set of relevant models for any ABox conforming to the given profiles. This compilation process is incremental, allowing new profiles to be added easily.
- ASP Rewriting for Querying: The compiled type tables are then used to generate Answer Set Programming (ASP) programs. This allows OMQs, specifically instance queries and reachability queries, to be answered by querying the ASP program. This approach leverages the power of off-the-shelf ASP solvers for efficient query evaluation.
Datasets
The paper mentions using several large real-world datasets for evaluation:
- NPD (petroleum ontology)
- IMDb (film ontology)
- MyITS (transport ontology)
They also evaluated their approach on 87 ontologies from the Oxford ontology library that contain axioms of forms NF2, NF4, and NF5.
Key Insights and Ideas
- Profiles as a General Abstraction: The concept of "profiles" offers a flexible way to generalize over families of ABoxes, making the compilation process data-independent to a degree while still being practical.
- Type Tables as Model Representations: The compiled "type tables" provide a structured representation of relevant models, which is sufficient for answering monotone queries.
- ASP for Practical Querying: Rewriting complex DL queries into ASP programs is a viable strategy for achieving efficient query answering, especially for large datasets.
- Incremental Reasoning: The ability to incrementally update the model compilation when new ABox families become relevant is a significant practical advantage.
- Small Profile Sets for Large Datasets: Surprisingly, large real-world datasets are often covered by a small number of profiles, suggesting that the structure of data in many applications is more constrained than initially assumed.
Key Results
- Feasible Compilation: The model compilation algorithm is feasible even for complex ontologies and large ABoxes. The time to compute the type table and generate the ASP program was short, averaging around 1.3 seconds for the tested ontologies.
- Scalable Query Answering: Query answering using the generated ASP programs scales well for large ABoxes. For instance queries, their prototype was significantly faster than the HermiT reasoner, with HermiT often timing out or crashing.
- Handling Complex Ontologies: The approach successfully compiled models for a large portion (70 out of 87) of complex ontologies from the Oxford library.
- Reachability Queries: The system effectively handles reachability queries, with answering times slightly slower than instance queries but still practical.
Limitations and Future Work
- Base Type Computation Bottleneck: The main limitation identified is the computation of "base types" from profiles, which can become computationally expensive if a profile has many relevant "guesses" (leading to 2^N base types). This was the reason for infeasibility in about 20% of the tested complex ontologies.
- Future Work: The authors plan to extend their technique to other query types like conjunctive queries (CQs) and regular path queries (RPQs) by incorporating ideas from existing work. They also aim to support more expressive DL features like number restrictions and nominals, though nominals are noted as more challenging. Investigating more refined alternatives to the current "guessing" mechanism for base types is crucial for improving scalability.
Summary updated