Introduction
Data exchange is a cornerstone of modern data management, facilitating the movement of information from a source database to a target database with a different schema. While deterministic data exchange is well-understood, real-world data is frequently characterized by uncertainty. This paper introduces a formal framework for Probabilistic Ontological Data Exchange (PODE), which extends traditional data exchange to handle uncertain data governed by complex logical rules, or ontologies. By leveraging Bayesian networks for compact representation, the authors map out the computational complexity of this expressive new environment.
The Challenge: Uncertainty and Ontological Knowledge
Traditional data exchange frameworks often fall short in two critical areas:
- Ontological Expressivity: They typically ignore the "terminological" knowledge—the rules and constraints that define relationships within the data. This paper incorporates the Datalog+/– family of languages, enabling the use of "existential rules" (e.g., "Every publication must have at least one author").
- Scalability of Uncertainty: Representing every possible configuration of a probabilistic database (the "possible worlds" model) is exponentially expensive. To address this, the authors utilize Bayesian networks to provide a "compact encoding," where probabilities are associated with events and their causal relationships.
The PODE Framework
A PODE problem is defined by a source schema, a target schema, and three sets of rules: a source ontology, a target ontology, and a mapping between them. The framework uses Tuple-Generating Dependencies (TGDs) for data mapping and Negative Constraints (NCs) to maintain consistency.
To manage uncertainty efficiently, the authors annotate facts and rules with Boolean formulas. The variables within these formulas represent elementary events whose joint probability distribution is governed by a Bayesian network. This approach is conceptually linked to data provenance or lineage, allowing for a more practical representation of complex domains.
Compact Encoding via Bayesian Networks
The use of Bayesian networks (BNs) is central to the framework's efficiency. Instead of an exhaustive list of possible states, the BN captures the dependencies between uncertain events.
The "confidence" of a query result (specifically, a Union of Conjunctive Queries or UCQ) is defined as the infimum—the greatest lower bound—of the probability across all possible probabilistic solutions. This ensures that the framework remains robust even when multiple valid target databases exist.
Computational Complexity and Key Results
The authors provide a comprehensive analysis of the complexity landscape for PODE:
- Data Complexity: Deciding the existence of a probabilistic solution is generally coNP-complete for most classes of existential rules.
- Tractability and Topology: A significant finding is that the topology of the Bayesian network matters. If the network is a polytree (a graph with no undirected cycles) and the ontology is "first-order rewritable," the problem becomes solvable in polynomial time (PTIME).
- Combined Complexity: Depending on the Datalog fragment used, complexity ranges from PSPACE to 2EXP.
- Query Answering: Computing the exact confidence of a UCQ is #P-complete in terms of data complexity, reflecting the inherent difficulty of counting-based probabilistic inference.
Conclusion and Future Work
This research establishes a rigorous foundation for exchanging uncertain data under ontological constraints. While the general problem is computationally demanding, the identification of tractable sub-cases, such as those involving polytree Bayesian networks, provides a path toward practical implementation.
Future research directions include exploring more expressive mapping rules and investigating approximate query answering techniques to mitigate the #P-completeness of exact calculations. Additionally, the "Weakly Guarded" (WG) class of rules presents a unique challenge that warrants further specialized analysis.
Summary updated