TL;DR
This paper tackles the challenge of querying data that might be inconsistent, especially when that data is accessed through ontologies and mappings. They introduce a novel way to define "repairs" for this data and analyze the computational complexity of querying under different consistency-tolerant semantics, finding that complex mappings significantly increase the difficulty.
What Problem Does This Paper Address?
Imagine you have a vast database of information, but it's not perfectly clean – it contains errors and contradictions. Now, imagine you're trying to access this data not directly, but through a conceptual "ontology" that describes the data's meaning. To bridge the gap between your database and the ontology, you use "mappings." This is the realm of Ontology-Based Data Access (OBDA).
The problem is that inconsistencies in the data can make standard OBDA systems break down, producing no answers at all. Existing work on "inconsistency-tolerant query answering" has focused on scenarios where data is directly expressed using the ontology's language. However, this paper addresses a more realistic scenario: OBDA with mappings, where the data resides in a relational database and is linked to the ontology via these mappings. The core challenge is how to define and handle data "repairs" (ways to fix inconsistencies) in this OBDA-with-mappings setting, and how this impacts the complexity of answering queries.
Methods
The authors propose a "repair at source" approach, meaning they define repairs at the level of the original database, rather than after the data has been mapped to the ontology. This is crucial because it avoids semantic anomalies that can arise when combining facts derived from conflicting sources. They formalize two types of repairs:
- Symmetric Difference Repairs (⊕-repairs): These are databases that satisfy integrity constraints and minimize changes (both additions and deletions) from the original database.
- Subset Repairs (C-repairs): These are maximal consistent subsets of the original database, allowing only deletions to fix inconsistencies.
They then adapt three existing inconsistency-tolerant query answering semantics (AR, IAR, and brave) to this OBDA-with-mappings context. The key innovation lies in how they define these semantics to work with database repairs and mappings, particularly for the IAR (Intersection of All Repairs) semantics, which requires careful handling of both sure and possible facts.
Datasets
Not discussed in the paper. The paper focuses on theoretical analysis and complexity results, using examples to illustrate concepts rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- "Repair at Source" is Key: Defining repairs at the database level, before mapping to the ontology, is crucial for avoiding semantic anomalies and is more aligned with how real-world data integration systems work.
- Mappings Dramatically Impact Complexity: The presence of mappings, especially those with negated atoms (allowing for more expressive queries), significantly increases the computational complexity of inconsistency-tolerant query answering compared to scenarios without mappings or with simpler mappings.
- GAV Mappings are Tractable (Mostly): For standard Global-As-View (GAV) mappings without negation, the complexity of inconsistency-tolerant query answering remains manageable, often matching the complexity of querying without mappings.
- Negation in Mappings is a Game Changer: Introducing negation into GAV mapping bodies causes a "jump" in complexity, pushing problems into higher levels of the polynomial hierarchy.
- C-repairs vs. ⊕-repairs: While ⊕-repairs are more general, the paper shows that for GAV mappings, the complexity results are the same for both types of repairs.
Key Results
The paper provides a comprehensive complexity analysis for inconsistency-tolerant query answering in OBDA with GAV and GAV­ mappings, considering AR, IAR, and brave semantics.
- For GAV mappings (without negation):
- AR and IAR semantics: coNP-complete data complexity.
- Brave semantics: NP-complete data complexity.
- These results match the complexity of querying DL knowledge bases without mappings.
- For GAV­ mappings (with negation):
- AR and IAR semantics: Π-complete data complexity.
- Brave semantics: Σ-complete data complexity.
- This represents a significant increase in complexity compared to GAV mappings.
The paper also establishes lower bounds that match these upper bounds for various description logics, demonstrating the tightness of their complexity results.
Limitations and Future Work
- Focus on DL-Lite and "Data-Tractable" DLs: The analysis is primarily for DL-Lite and a class of DLs called "data-tractable" DLs. Extending these results to more expressive DLs would be valuable.
- Mapping Language Expressivity: The paper focuses on GAV mappings. Future work will explore richer mapping languages like R2RML, which allow for more complex constructs (e.g., subqueries, aggregation), and investigate their impact on complexity.
- Algorithmic Development: While theoretical complexity is established, the paper suggests developing practical algorithms, particularly for DL-Lite ontologies and leveraging the reduction to database query answering.
- IAR and Brave Semantics with Constraints: Further exploration of the IAR and brave semantics in the context of constraints is needed, as these are less explored areas.
Summary updated