The Bag Semantics of Ontology-Based Data Access

Charalampos Nikolaou, Egor V. Kostylev, George Konstantinidis, Mark Kaminski, Bernardo Cuenca Grau, Ian Horrocks

Introduction

Ontology-Based Data Access (OBDA) provides a high-level conceptual view of heterogeneous data sources, allowing users to query complex databases through a simplified ontology. While theoretical models of OBDA often assume set semantics, real-world SQL databases operate under bag semantics (multisets). This discrepancy is critical for business intelligence and applications involving aggregation, where duplicate tuples must be preserved to ensure accurate counts and sums. This paper bridges the gap by formalizing OBDA under bag semantics.

The Challenge of Bag Semantics

In traditional OBDA, the "universal model" property allows for efficient query answering. However, moving to bag semantics breaks this property. For instance, if an employee named "Lee" appears twice in the source data (perhaps in different departments), a set-based system would return "Lee" once. A COUNT aggregate would then incorrectly report 1 instead of 2.

Example of mapping rules in OBDA, where source table attributes are mapped to ontological concepts and roles.

The figure above illustrates typical mapping rules used to bridge the gap between relational data and an ontology. Under bag semantics, these mappings must carefully preserve the multiplicity of tuples to maintain data integrity for analytical queries. The authors address the loss of the universal model property and the increased computational complexity that arises when duplicates must be tracked through ontological inferences.

Methodology: $DL-Lite_R^{bag}$ and Rooted Queries

The authors formalize $DL-Lite_R^{bag}$, an extension of the popular $DL-Lite_R$ description logic that incorporates multiplicities. Their approach involves several key innovations:

  1. Bag Interpretations: Redefining the semantics of ontologies so that concepts and roles are bags of elements rather than sets.
  2. Canonical Bag Models: Developing a "chase" procedure for bags to create a representative model of the data. Unlike the set-based chase, this version tracks how many times each fact is inferred.
  3. Rooted Conjunctive Queries (CQs): To overcome the fact that general bag-querying is $coNP$-hard, the authors focus on "rooted" CQs. In these queries, every "hidden" (existential) variable must be connected to a known constant or an answer variable. This covers the vast majority of practical OBDA use cases.
  4. Rewritability: They provide an algorithm to rewrite rooted CQs into a generalized relational calculus for bags ($BALG^1_\epsilon$), which can be executed directly by standard database engines.

Key Results and Complexity

The research establishes several critical complexity bounds that define the feasibility of bag-based OBDA:

  • General Complexity: Proved that checking if a query answer has at least $k$ occurrences is $coNP$-hard for general conjunctive queries in $DL-Lite_{core}^{bag}$.
  • Rooted Query Complexity: For the class of rooted CQs, the problem remains in LOGSPACE for data complexity. This is a vital result because it means that for large datasets, bag-based OBDA is just as scalable as traditional set-based OBDA.
  • The "Double Counting" Trap: A major hurdle in the rewriting process is ensuring that the system doesn't over-count or under-count when navigating the ontology's hierarchy. The authors use the "bag difference" operator in their algebra to prune duplicate paths.

Conclusion and Future Work

This work provides a theoretical foundation for implementing bag semantics in OBDA systems like Ontop. By identifying "rootedness" as a key property, the authors recover the ability to "compile away" the ontology into standard SQL-like queries without losing duplicate information.

Future work is needed to formally incorporate other SQL aggregates like SUM, AVG, and MAX into this framework and to extend these results to more expressive ontology languages like $OWL\ 2\ QL$ without hitting $coNP$-hardness.

Summary updated

Abstract

Ontology-based data access (OBDA) is a popular approach for integrating and querying multiple data sources by means of a shared ontology. The ontology is linked to the sources using mappings, which assign views over the data to ontology predicates. Motivated by the need for OBDA systems supporting database-style aggregate queries, we propose a bag semantics for OBDA, where duplicate tuples in the views defined by the mappings are retained, as is the case in standard databases. We show that bag semantics makes conjunctive query answering in OBDA coNP-hard in data complexity. To regain tractability, we consider a rather general class of queries and show its rewritability to a generalisation of the relational calculus to bags.
BibTeX
@inproceedings{nikolaou2017bag,
  author = {Charalampos Nikolaou and Egor V. Kostylev and George Konstantinidis and Mark Kaminski and Bernardo Cuenca Grau and Ian Horrocks},
  title = {{The Bag Semantics of Ontology-Based Data Access}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/170},
}
Figure