Enriching Ontology-based Data Access with Provenance

Diego Calvanese, Davide Lanti, Ana Ozaki, Rafael Peñaloza, Guohui XiaoIJCAI 2019 · DOI

TL;DR

This paper introduces a novel approach to enrich Ontology-Based Data Access (OBDA) systems with provenance information, allowing users to understand how query results are derived. They achieve this by extending database provenance techniques to OBDA, enabling the computation of provenance polynomials that track the origin of data and reasoning steps. This work is crucial for building more transparent and trustworthy data integration systems.

What Problem Does This Paper Address?

Ontology-Based Data Access (OBDA) systems allow users to query heterogeneous data sources using a high-level conceptual view (an ontology). While effective, a significant challenge is understanding why a particular piece of data appears in a query result. This "provenance" is important for debugging, auditing, and trusting the data. In OBDA, provenance is complicated by implicit reasoning steps derived from ontology axioms and the use of mappings to data sources. Existing methods for tracking provenance in traditional databases don't directly translate to the complexities of OBDA, where ontology reasoning adds another layer of derivation.

Methods

The core contribution is the extension of "provenance semirings" from database theory to OBDA. This involves annotating not just database tuples but also ontology axioms and mappings with provenance information. The authors then tackle two main problems:

  1. Query Entailment: Deciding if a provenance-annotated OBDA instance entails a provenance-annotated query. They achieve this by transforming the problem into a set of standard conjunctive queries over a modified OBDA instance, leveraging a modified version of the PerfectRef algorithm.
  2. Provenance Computation: Computing a "provenance polynomial" that represents all possible derivations of a query result. This polynomial captures the combinations of annotated data sources, mappings, and ontology axioms that lead to an answer. They address the issue of potentially infinite polynomials by considering idempotent semirings, which guarantee finiteness.

Datasets

The authors evaluate their approach using two standard benchmarks:

  • BSBM (Berlin SPARQL Benchmark): Used to test the performance of their system with varying ontology and mapping complexity.
  • NPD (Not Provided Data): A benchmark specifically designed for OBDA systems, featuring complex ontologies and mappings, used to assess the system's feasibility in more challenging scenarios.

Key Insights and Ideas

  • Provenance as Polynomials: Representing provenance as polynomials is a powerful abstraction that elegantly captures the combinatorial nature of data derivations in OBDA.
  • Idempotency for Finiteness: The insight that multiplicative idempotency in provenance semirings is sufficient to guarantee finite provenance polynomials is crucial for practical computation. This means that repeated derivations don't lead to infinitely complex provenance representations.
  • Adapting Database Techniques: The successful adaptation of database provenance techniques (provenance semirings, PerfectRef algorithm) to the OBDA setting demonstrates a strong theoretical link and opens doors for further cross-pollination of ideas.
  • Provenance vs. Axiom Pinpointing: A key distinction is made between provenance (all possible derivations) and axiom pinpointing (minimal causes). This paper focuses on the former, which is essential for understanding the full picture of data derivation.

Key Results

The paper presents theoretical results on the complexity of provenance-annotated query entailment (NP-complete) and demonstrates the feasibility of their approach through an implementation called OntoProv.

  • OntoProv: A prototype system extending the state-of-the-art OBDA system Ontop.
  • Performance: Evaluation on BSBM showed that the overhead for computing provenance is small when ontologies and mappings are not overly complex.
  • NPD Benchmark: While OntoProv showed significantly higher execution times and timeouts on the complex NPD benchmark compared to Ontop (which disables optimizations for provenance), the experiments demonstrated that the approach is feasible even with complex ontologies and mappings. The number of provenance results (#prov) indicated a high degree of complexity in derivations for some queries.

Limitations and Future Work

  • Computational Complexity: The authors acknowledge that for complex OBDA instances and queries, the provenance polynomials can be exponentially large, and the computation can be time-consuming.
  • Monus Operator and Numerical Provenance: Future work includes investigating provenance with the monus operator and exploring numerical provenance (e.g., probabilities), where multiplicative idempotency is not suitable. This would require handling potentially infinite polynomials and finding ways to represent them finitely.
  • SPARQL Provenance: Extending the approach to handle SPARQL query answering over OBDA systems is also a planned direction.

Summary updated

BibTeX
@inproceedings{calvanese2019enriching,
  author = {Diego Calvanese and Davide Lanti and Ana Ozaki and Rafael Peñaloza and Guohui Xiao},
  title = {{Enriching Ontology-based Data Access with Provenance}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/224},
}
Figure