Inverting Schema Mappings: Bridging the Gap between Theory and Practice

Marcelo Arenas, Jorge Pérez, Juan L. Reutter, Cristian Riveros

TL;DR

This paper tackles the practical challenges of inverting schema mappings, which are crucial for data exchange and integration. They introduce a new, query-language-based notion of inversion (CQ-maximum recovery) that allows for inverses to be expressed in a practical, chaseable language, and provide a polynomial-time algorithm to compute them. This bridges a significant gap between theoretical notions of schema mapping inversion and their real-world applicability.

What Problem Does This Paper Address?

Schema mappings are essential for tasks like data exchange and integration, defining how data from one schema can be transformed into another. However, in many scenarios, we need to "undo" these mappings – to recover the original data or perform operations in the reverse direction. This is where schema mapping inversion comes in.

Previous research proposed several notions of inversion (Fagin-inverse, quasi-inverse, maximum recovery), but these suffered from two major practical limitations:

  1. Computational Complexity: Algorithms for computing these inverses were often exponential in time complexity, and the resulting inverse mappings could also be exponentially large.
  2. Expressiveness of Inverse Mappings: The languages used to express these inverses often included features like disjunctions in rule conclusions, which are difficult to handle with standard data exchange tools (like the chase procedure) and complicate data manipulation.

This paper aims to bridge this gap by providing solutions that are both computationally efficient and result in inverses expressible in practical, chaseable languages.

Methods

The authors introduce a novel approach based on query language-based inversion. Instead of aiming for a perfect reversal, they define an inverse based on how much information can be recovered for a specific class of queries.

  • C-maximum recovery: This is the core new notion. An inverse mapping M' is a C-maximum recovery of M if, for any query Q from a class C, the information recovered by composing M and M' (M o M') is a subset of the original information. This ensures that recovered data is "sound."
  • CQ-maximum recovery: They focus on the class of conjunctive queries (CQ). This choice is motivated by its practical relevance in data exchange and the fact that it allows for inverses to be expressed in a more manageable language.
  • Polynomial-time Algorithm: The paper presents a polynomial-time algorithm that computes CQ-maximum recoveries for mappings specified by tuple-generating dependencies (tgds). This algorithm involves several key steps:
  • Computing a maximum recovery using existing techniques.
  • Eliminating equalities from the conclusions of dependencies by introducing inequalities into the premises.
  • Eliminating disjunctions from conclusions by using a novel "product" operation on conjunctive queries.
  • Intermediate Language (Plain SO-tgds): The algorithm uses an intermediate language called "plain SO-tgds" (second-order tuple-generating dependencies) which extends tgds with function symbols. This language is powerful enough to express the necessary inverse operations and is shown to be equivalent to nested mappings, a practical language used in tools like Clio.

Datasets

Not discussed in the paper. The paper focuses on theoretical contributions and algorithmic development rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Shifting Focus from Perfect Reversal to Query-Aware Recovery: The most significant insight is that a perfect, lossless reversal of a schema mapping might be impractical or impossible. Instead, focusing on recovering information relevant to specific query types (like conjunctive queries) offers a more achievable and practically useful goal.
  • CQ-Maximum Recovery as a Unifying Concept: The paper demonstrates that their new notion of CQ-maximum recovery can characterize previously proposed inverse notions (Fagin-inverse, quasi-inverse, maximum recovery) under different query classes, providing a unified theoretical framework.
  • Bridging Theory and Practice: The core contribution is bridging the gap between theoretical, often complex, notions of inversion and the practical need for efficient algorithms and expressible, chaseable inverse mappings.
  • Polynomial Time for Inversion: Achieving polynomial time complexity for computing inverses of schema mappings is a significant algorithmic breakthrough, especially considering the exponential complexity of prior methods.
  • Necessity of Inequalities and C(.) Predicate: The paper proves that inequalities and the C(.) predicate (to distinguish constants from nulls) are essential in the premises of dependencies for expressing CQ-maximum recoveries of tgds, highlighting the trade-offs in expressive power.

Key Results

  • New Notion of CQ-Maximum Recovery: A novel definition of schema mapping inversion based on recovering sound information for conjunctive queries.
  • Polynomial-Time Algorithm: The first polynomial-time algorithm for computing CQ-maximum recoveries of mappings specified by tgds. This algorithm also computes Fagin-inverses, quasi-inverses, and maximum recoveries efficiently.
  • Expressive Inverse Language: The resulting inverse mappings are expressed in a language that extends tgds with inequalities and a C(.) predicate in the premises, which is shown to be chaseable and suitable for data exchange.
  • Theoretical Characterization: The paper shows that C-maximum recovery can unify and characterize existing notions of schema mapping inversion.

Limitations and Future Work

  • Expressiveness of the Output Language: While the output language is more practical than previous approaches, it still uses inequalities and the C(.) predicate, which are extensions beyond standard tgds. The paper argues these are necessary for CQ-maximum recoveries.
  • Focus on Tgds: The primary focus is on mappings specified by tgds. While the intermediate language (plain SO-tgds) is more general, extending the polynomial-time algorithm to a wider range of input mapping languages could be future work.
  • Practical Implementation and Benchmarking: The paper presents theoretical algorithms. Further work would involve implementing these algorithms and evaluating their performance on real-world datasets and benchmarks.
  • Exploring Other Query Classes: While CQ is a practical choice, exploring C-maximum recovery for other query classes could reveal different trade-offs and properties.

Summary updated

BibTeX
@article{arenas2009inverting,
  author = {Marcelo Arenas and Jorge Pérez and Juan L. Reutter and Cristian Riveros},
  title = {{Inverting Schema Mappings: Bridging the Gap between Theory and Practice}},
  journal = {Proc. VLDB Endow.},
  year = {2009},
  url = {https://openreview.net/forum?id=LDLBNqWkgzM},
}
Figure