Locally Consistent Transformations and Query Answering in Data Exchange

Marcelo Arenas, Pablo Barceló, Ronald Fagin, Leonid Libkin

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Data exchange is the problem of taking data structured under a source schema and creating an instance of a target schema. Given a source instance, there may be many solutions - target instances that satisfy the constraints of the data exchange problem. Previous work has identified two classes of desirable solutions: canonical universal solutions, and their cores. Query answering in data exchange amounts to rewriting a query over the target schema to another query that, over a materialized target instance, gives the result that is semantically consistent with the source. A basic question is then whether there exists a transformation sending a source instance into a solution over which target queries can be answered.We show that the answer is negative for many data exchange transformations that have structural properties similar to canonical universal solutions and cores. Namely, we prove that many such transformations preserve the local structure of the data. Using this notion, we further show that every target query rewritable over such a transformation cannot distinguish tuples whose neighborhoods in the source are similar. This gives us a first tool that helps check whether a query is rewritable, We also show that these results are robust: they hold for an extension of relational calculus with grouping and aggregates, and for two different semantics of query answering.
Original languageEnglish
Title of host publicationPODS '04 Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems
Place of PublicationNew York, NY, USA
Number of pages12
ISBN (Print)158113858X
Publication statusPublished - 2004


Dive into the research topics of 'Locally Consistent Transformations and Query Answering in Data Exchange'. Together they form a unique fingerprint.

Cite this