TL;DR
This paper tackles the challenge of maintaining consistency in Ontology-Based Data Access (OBDA) systems when the underlying ontology or data sources change. They introduce novel methods for "repairing" the mappings between ontologies and data sources to ensure continued data access, focusing on minimal changes and preserving logical consequences.
What Problem Does This Paper Address?
Ontology-Based Data Access (OBDA) systems allow users to query data from various sources using a unified conceptual view defined by an ontology. An OBDA system is typically composed of an ontology (TBox), a source schema (S), and a mapping (M) that links the ontology to the data. A critical issue arises when either the ontology or the data source schema evolves. These changes can invalidate the existing mappings, leading to inconsistencies and making it impossible to retrieve accurate data. While research exists on evolving ontologies and database schemas independently, this paper addresses the less-explored problem of evolving OBDA specifications, specifically focusing on how to adapt the mappings to maintain the system's integrity and functionality.
Methods
The authors propose two main approaches for mapping repair:
- Deletion-Based Mapping Repair (DMR): This method aims to find a minimal subset of the original mapping that remains consistent with the updated ontology and schema. It's like pruning the original mapping to remove problematic assertions.
- Entailment-Based Mapping Repair (EMR): This approach is more sophisticated. It considers not only the original mapping assertions but also those that are logical consequences (entailed) by the original specification. EMR aims to preserve as many of these entailed mappings as possible while ensuring consistency, prioritizing minimal changes (fewer deletions over fewer insertions).
They also define notions of "global mapping inconsistency" for OBDA specifications and formalize query entailment under these repair mechanisms. For specific cases involving DL-LiteR ontologies and GAV/GLAV mappings, they analyze the computational complexity of query answering.
Datasets
Not discussed in the paper. The paper focuses on theoretical frameworks and algorithmic approaches rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Mapping evolution is crucial: The paper highlights that mappings are often the most neglected component of OBDA systems, yet they are central to maintaining functionality during evolution.
- Minimal change is key: Both DMR and EMR are guided by the principle of minimal change, analogous to belief revision in AI, to ensure that repairs are as close as possible to the original specification.
- Entailment matters: EMR's focus on preserving entailed mappings is a significant advancement, as it captures more of the original system's intended behavior than just looking at the explicit mapping assertions.
- Syntax independence is tricky: While EMRs can achieve syntax independence for equivalent OBDA specifications under certain conditions, DMRs can be sensitive to the syntactic representation of the mapping.
- Complexity is manageable (for now): The paper provides complexity results for query entailment under these repair mechanisms, showing they are decidable, though often computationally intensive (e.g., $\Pi_2$-complete in combined complexity).
Key Results
- Formal definitions for two mapping repair notions: Deletion-Based Mapping Repair (DMR) and Entailment-Based Mapping Repair (EMR).
- Definitions for query entailment under both DMR and EMR.
- Complexity analysis for query entailment under DMR for DL-LiteR TBoxes and simple source schemas, showing it's $\Pi_2$-complete in combined complexity and $AC^0$ in data complexity.
- Results on query entailment under EMRs for GAV mappings, showing it's $\Pi_2$-complete in combined complexity and $AC^0$ in data complexity.
- Results on query entailment under EMRs for GLAV mappings, showing it's $AC^0$ in data complexity under certain conditions.
Limitations and Future Work
- Syntax dependence of DMRs: The paper notes that DMRs can be sensitive to the syntactic representation of mappings, which can lead to different repair outcomes for equivalent specifications.
- Infinite EMRs: For GLAV mappings, EMRs can be infinite, posing challenges for practical implementation. The paper proposes finite approximations but acknowledges this is an area for further research.
- Practical approximations: The authors suggest exploring approximations of DMR and EMR that guarantee the existence of a single, unique repair, which would be highly beneficial for practical applications.
- Broader DL support: The current work focuses on DL-LiteR. Future work could extend the repair semantics to other Description Logics.
- Semi-automatic mapping evolution: The authors envision their work contributing to semi-automatic mapping evolution management and suggest exploring how to identify repairs that lead to desired system behaviors.
Summary updated