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.
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:
- Bag Interpretations: Redefining the semantics of ontologies so that concepts and roles are bags of elements rather than sets.
- 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.
- 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.
- 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