Introduction
In the field of Ontology-Based Data Access (OBDA), ontologies serve as a conceptual layer providing a unified view over distributed and often messy data sources. Historically, these ontologies have been grounded in set semantics, where the focus is solely on the existence of a piece of information rather than its frequency. However, real-world relational databases and the SQL language operate under bag semantics (multisets), where duplicates are significant. In practical applications, ignoring duplicates leads to incorrect results for aggregate operations such as SUM, COUNT, or AVG.
While recent research has begun to adapt the $DL-Lite$ family of Description Logics to support bag semantics, a critical component remained under-addressed: functional roles. These are the logical equivalents of primary keys in databases. This paper investigates how to incorporate functional roles into bag-based ontologies without causing the computational complexity of query answering to become unmanageable.
Semantic Frameworks for Functional Roles
The authors identify that the interaction between duplicates and functional constraints is non-trivial. They introduce and compare two distinct ways to interpret functional constraints within a bag-based ontology:
- SQL Semantics: This approach mimics the behavior of primary keys in standard SQL. If a role is defined as functional (e.g., "hasSocialSecurityNumber"), a specific relationship can appear at most once in the data, forcing its multiplicity to be exactly 1.
- Multiplicity-Respectful (MR) Semantics: This is a more flexible interpretation. While it still insists that an entity can be related to only one other entity via a functional role, it allows that specific relationship to be recorded multiple times (multiplicity $\ge 1$).
To analyze these semantics, the authors utilize BCALC (Bag Calculus), a logical language that serves as the counterpart to bag relational algebra, providing a formal framework for proving rewritability into SQL.
The Complexity Trap and Tractability Conditions
Transitioning from set semantics to bag semantics introduces a significant "Complexity Trap." In standard $DL-Lite$, query answering is typically in $AC^0$ data complexity, which is nearly instantaneous. However, simply adding bags can make query answering coNP-hard. This jump is largely due to "multiplicity explosion," where following chains of relationships can cause the number of duplicates to grow in ways that are difficult to track.
To restore efficiency, the paper identifies two key conditions:
- Rooted Conjunctive Queries (CQs): These are queries where every part of the "question" is connected to a known constant or an answer variable. The authors show that non-rooted queries remain computationally expensive, but rooted queries offer a path to tractability.
- Functional Weak Acyclicity: Under the more flexible MR semantics, even simple queries can become LogSpace-hard. The authors propose this new condition to ensure that functional dependencies do not form loops, preventing infinite or overly complex multiplicity calculations.
Key Results and Rewritability
The primary goal of this research is to achieve rewritability—the ability to transform a complex ontological query into a standard bag algebra query (SQL). This allows the use of existing, highly optimized database engines to solve logic problems. The paper's findings are summarized as follows:
- SQL Semantics: For rooted CQs, query answering is in $TC^0$ (a very efficient complexity class) and is fully rewritable to BCALC.
- MR Semantics: While generally harder, if the ontology is functionally weakly acyclic, rooted CQs also fall into $TC^0$ and remain rewritable.
- Satisfiability: Checking if an ontology is consistent (satisfiable) under SQL semantics remains efficient, specifically $TC^0$ for fixed TBoxes.
Conclusion and Future Work
This paper provides a theoretical foundation for bridging the gap between formal logic and practical database management. By identifying the specific conditions—rootedness and acyclicity—under which functional roles can be safely integrated with bag semantics, the authors enable more accurate data integration that respects the duplicate-aware nature of real-world data.
Future research directions include extending these results to more expressive logics, exploring $n$-ary predicates (relationships between more than two entities), and developing practical implementations to evaluate the size and performance of the resulting SQL rewritings in large-scale environments.
Summary updated