TL;DR
This paper introduces a novel framework for defining and reasoning with "views" in Description Logic (DL) knowledge bases, specifically DL-Lite. They propose a way to enrich ontologies with user-defined abstractions that go beyond standard DL capabilities, enabling more expressive data access and integration while maintaining decidability for key reasoning tasks.
What Problem Does This Paper Address?
Ontology-Based Data Access (OBDA) systems allow users to query data through a conceptual ontology. However, standard DL languages have limitations: they typically only support unary and binary predicates, and their expressive power is restricted for decidability, preventing complex operations like joins within concepts. Furthermore, users often need to define custom, higher-level abstractions (views) over the data that aren't directly expressible in the base ontology. Existing approaches to views in DLs are limited. This paper addresses the need for a flexible yet decidable way to define and reason with these user-defined views in DL-Lite ontologies, bridging the gap between expressive user needs and the computational tractability of DL reasoning.
Methods
The authors propose a framework for enriching DL-Lite knowledge bases with views. A view is defined as a pair: a view name and an epistemic formula that specifies its definition. Crucially, these epistemic formulas can leverage the modal operator 'K' (representing "knowledge" or "certainty" in the knowledge base) and can express more complex operations like joins, projections, and selections, going beyond standard DL concept expressions. They distinguish between intensional negation (negation within DL constructs) and epistemic negation (negation applied to the 'K' operator). The paper then analyzes the computational complexity of fundamental reasoning tasks like View Consistency, View Containment, Query Answering, and Query Containment for different classes of views, particularly focusing on "lightweight views" and views with epistemic negation.
Datasets
Not discussed in the paper. The paper focuses on theoretical framework development and complexity analysis, using examples to illustrate concepts rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Views as Epistemic Formulas: The core innovation is defining views using epistemic logic formulas, allowing them to refer to "known" information (via the 'K' operator) and express richer relationships than standard DL concepts. This enables views to act as sophisticated abstractions over the data.
- Bridging Expressivity and Decidability: The paper demonstrates that by carefully restricting the form of views (e.g., "lightweight views" or views with "epistemic negation"), it's possible to introduce significant expressive power without sacrificing the decidability of crucial reasoning tasks like query answering.
- Impact of Negation: Intensional negation within views quickly leads to undecidability for query answering. However, restricting negation to the epistemic operator ('K') preserves decidability for many tasks, offering a practical way to incorporate negative information.
- Reasoning Tasks Extended: The paper systematically extends standard DL reasoning tasks (consistency, containment, query answering) to the context of view-enriched knowledge bases, providing a formal basis for understanding their behavior.
Key Results
The paper establishes the computational complexity of various reasoning tasks for different classes of views:
- Lightweight Views:
- View Consistency is in PTime.
- View Containment is NP-Complete.
- VE-UCQ Answering is NP-Complete (and AC⁰ in data complexity).
- VE-UCQ Containment is NP-Complete.
- Lightweight Views with Epistemic Negation:
- VE-CQ Answering is Σ₂-complete (and AC⁰ in data complexity).
- VE-UCQ Containment is undecidable.
- Lightweight Epistemic Negation Views:
- VE-CQ Containment is in Π₂.
- View Containment is in Π₂.
- View Consistency is in coNP.
Limitations and Future Work
- Undecidability with Intensional Negation: The paper highlights that intensional negation within views leads to undecidability for query answering, limiting its practical application.
- Complexity with Epistemic Negation: While decidable, VE-UCQ Containment becomes undecidable when using lightweight views with epistemic negation, indicating a trade-off.
- Future Work: The authors suggest implementing the framework in real OBDA systems and further investigating negation in view definitions, particularly its relationship with merging DLs and rules. They also point to exploring other decidable languages for view definitions.
Summary updated