Epistemic Integrity Constraints for Ontology-Based Data Management

Marco Console, Maurizio LenzeriniAAAI 2020 · DOI

Introduction

Ontology-Based Data Management (OBDM) has emerged as a powerful paradigm for integrating heterogeneous data sources. By providing a conceptual view (the ontology) over physical data via mappings, it allows users to query complex systems using a unified vocabulary. However, a significant challenge remains: how do we enforce integrity constraints (ICs) in such a system? Unlike traditional databases, OBDM typically operates under the Open World Assumption (OWA), where missing information is not necessarily false, but simply unknown.

The Semantic Dilemma

In traditional relational databases, the Closed World Assumption (CWA) makes IC enforcement straightforward: if a constraint is not satisfied by the explicit data, it is violated. In the OWA world of ontologies, standard "entailment semantics" can be overly restrictive, flagging violations if a bad state is even possible according to the ontology. Conversely, "minimal model semantics" can be too permissive, satisfying constraints through inferred data that may not exist in reality.

The Epistemic Approach

This paper proposes a middle ground using Epistemic Logic. By introducing a knowledge operator (K), the system can distinguish between what is true in some possible world and what the system actually knows based on its data and mappings. This leads to Knowledge Semantics (KS), where integrity constraints—termed Epistemic Dependencies (EDs)—are checked against the system's "Knowledge State."

For example, an ED might state: "For every individual the system knows is an employee, the system must also know their unique employee code." This shifts the focus from ontological possibility to data-driven certainty, allowing for a more practical approach to data quality.

Illustrative Example

The authors use a running example of a Human Resources system to demonstrate these concepts. Consider the following data sources which provide the raw facts for the system:

Example data sources for an HR system, including employee records (empA), department managers (dep), and personnel lists (pers).

In this scenario, the ontology defines relationships between employees, codes, and departments. Epistemic constraints ensure that for the data present in sources like empA or pers, the system can definitively resolve the required attributes (like codes or managers) without relying on speculative inferences that the OWA might otherwise allow.

Computational Complexity and Results

A key contribution of this work is the rigorous analysis of the computational costs associated with epistemic ICs. The researchers focused on DL-Lite$_A$, a lightweight description logic designed for efficient query answering in practical applications.

  • Satisfiability: Checking if a data instance satisfies a set of EDs is shown to be $\Pi^p_2$-complete in terms of combined complexity. Crucially, however, the data complexity (where the ontology and constraints are fixed) is $AC^0$. This means that in practice, checking these constraints is as efficient as executing standard SQL queries.
  • Protection: The paper investigates whether local constraints on the underlying databases are sufficient to guarantee global OBDM constraints. This "protection" problem is found to be 2EXPTIME-complete.
  • Implication: Determining if one set of EDs logically implies another is undecidable. This suggests that while checking constraints is efficient, automatically optimizing or reasoning about the constraints themselves remains a significant challenge.

Conclusion

By grounding integrity constraints in the system's knowledge rather than ontological entailment, the authors provide a framework that is both more intuitive for data engineers and computationally feasible for large-scale systems. This work bridges the gap between the flexible, open-world nature of ontologies and the rigorous, closed-world requirements of data quality management. Future research will likely explore more expressive logics and identify decidable fragments for constraint optimization.

Summary updated

BibTeX
@inproceedings{console2020epistemic,
  author = {Marco Console and Maurizio Lenzerini},
  title = {{Epistemic Integrity Constraints for Ontology-Based Data Management}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i03.5667},
}
Figure