Bidirectional Constraints for Exchanging Data: Beyond Monotone Queries

Marcelo Arenas, Gabriel Diéguez, Jorge PérezIJCAI 2015

Abstract

Standard data exchange frameworks utilize source-to-target tuple-generating dependencies (st-tgds) that operate under an open-world assumption. While effective for monotone queries, this approach fails to provide intuitive certain answers for queries involving negation or universal quantification. This paper introduces bidirectional constraints ($\leftrightarrow$) to tighten the relationship between source and target schemas. By defining a formal mapping closure, the authors establish a "closed-world" semantics that enables accurate query answering for non-monotone queries. We analyze the complexity of solution existence and certain answer computation, identifying tractable fragments and the inherent computational costs of negation.

Introduction

Data exchange is a fundamental task in database management, involving the transformation of data from a source schema to a target schema according to a set of declarative rules or "mappings." Traditionally, these mappings are expressed as source-to-target tuple-generating dependencies (st-tgds). An st-tgd typically takes the form of a first-order implication: if a certain pattern of facts exists in the source, then a corresponding pattern must exist in the target.

While this framework has been highly successful for positive, monotone queries (e.g., "Find all students enrolled in AI"), it struggles with non-monotone queries—those involving negation or universal quantification (e.g., "Find all students not enrolled in any course"). The root of the problem lies in the "open-world" assumption inherent in standard implications.

The Problem with Open-World Semantics

In standard logic, the implication $A \to B$ does not prevent $B$ from being true even if $A$ is false. In data exchange, this means a target database is considered "valid" even if it contains extra, arbitrary information not present in or required by the source.

Consider a source database tracking student enrollments. If the source does not state that "John" is enrolled, a standard mapping still allows for a valid target where "John" is enrolled. Consequently, the "certain answer" to the query "Is John NOT enrolled?"—defined as the answer true in all valid target databases—would be false. This is counter-intuitive for most real-world applications where the absence of a record usually implies the absence of the fact.

Example of relational data structures used in data exchange scenarios.

Methodology: Bidirectional Constraints

To address this, the authors propose bidirectional constraints. By replacing the one-way implication ($\to$) with a biconditional ($\leftrightarrow$), the mapping effectively states that a target fact exists if and only if a corresponding source fact exists. This shift enforces a "closed-world" semantics directly within the mapping language.

Mapping Closure and the CLOSURE(M) Algorithm

A key contribution of the paper is the concept of mapping closure. Inspired by Clark’s predicate completion in logic programming, the closure process completes a mapping by assuming that any information not explicitly required by the source should be treated as negative information.

The authors provide the CLOSURE(M) algorithm, which transforms a standard set of st-tgds into a set of bidirectional constraints. This algorithm utilizes query rewriting techniques to identify source-side definitions for target-side relations, ensuring that the target is strictly bounded by the source data.

Complexity Analysis and Key Results

Moving from monotone to non-monotone query answering introduces significant computational challenges. The authors provide a rigorous analysis of two primary problems:

  1. Existence of Solutions: Determining if a valid target exists for a given source under bidirectional constraints.
  2. Certain Answers: Computing facts that are guaranteed to be true across all valid targets.

The results reveal a complex landscape. While some scenarios, such as Global-As-View (GAV) mappings, remain tractable (PTIME), general cases often see a "complexity tax." Moving to non-monotone queries can elevate data complexity to NP-complete and combined complexity to NEXPTIME-complete.

Complexity landscape for solution existence and query answering under bidirectional constraints.

For "full" dependencies—those that do not involve the invention of new values (nulls)—the data complexity for checking solution existence remains in PTIME. However, for certain answer computation with negation, the problem becomes coNP-complete. General first-order (FO) query answering under these constraints is shown to be undecidable.

Conclusion

This work represents a significant step toward making data exchange more robust for real-world applications requiring negation. By introducing bidirectional constraints and the formal notion of mapping closure, the authors provide a principled way to handle non-monotone queries. While the increased expressivity comes with higher computational costs, the identification of tractable fragments provides a path forward for implementing these techniques in practical data integration systems. Future work remains in exploring the uniqueness of closures and optimizing performance for large-scale mapping sets.

Summary updated

BibTeX
@inproceedings{arenas2015bidirectional,
  author = {Marcelo Arenas and Gabriel Diéguez and Jorge Pérez},
  title = {{Bidirectional Constraints for Exchanging Data: Beyond Monotone Queries}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure