Locally consistent transformations and query answering in data exchange
Locally consistent transformations and query answering in data exchange
复制标题
DOI：
10.1145/1055558.1055592
复制
发表时间：
2004-06
期刊：
影响因子：
--
通讯作者：
M. Arenas;P. Barceló;Ronald Fagin;L. Libkin
中科院分区：
文献类型：
--
作者：
M. Arenas;P. Barceló;Ronald Fagin;L. Libkin
数据交换是获取源模式下的结构化数据并创建目标模式的实例的问题。给定一个源实例，可能有许多解决方案-满足数据交换问题约束的目标实例。以前的工作已经确定了两类理想的解决方案：规范的通用解决方案，和他们的核心。数据交换中的查询应答相当于将目标模式上的查询重写为另一个查询，该查询在物化的目标实例上给出与源语义一致的结果。一个基本的问题是，是否存在一个转换发送到一个解决方案，目标查询可以回答。我们的答案是否定的许多数据交换转换，具有类似于规范的通用解决方案和核心的结构属性。也就是说，我们证明了许多这样的变换保持数据的局部结构。使用这一概念，我们进一步表明，每个目标查询在这样的转换无法区分元组的邻域中的源是相似的。这给了我们第一个工具，有助于检查是否查询是可扩展的，我们还表明，这些结果是强大的：他们持有的关系演算与分组和聚合的扩展，并为两个不同的语义查询回答。
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.