Solutions and query rewriting in data exchange
Solutions and query rewriting in data exchange
复制标题
数据交换中的解决方案和查询重写
DOI：
10.1016/j.ic.2013.06.002
复制
发表时间：
2013
影响因子：
1
通讯作者：
Arenas M
中科院分区：
文献类型：
--
作者：
Arenas M
数据交换是获取在源模式下结构化的数据并创建目标模式的实例的问题。给定源实例，可能有许多解决方案--满足数据交换问题约束的目标实例。以前的工作已经确定了两类理想的解：规范通用解和它们的核心。数据交换中的查询应答相当于将目标模式上的查询重写为另一个查询，该查询在物化的目标实例上给出与源的语义一致的结果(具体地说，就是“某些答案”)。基本问题是：(1)这些解决方案在查询重写方面的比较如何？以及(2)我们如何确定查询在特定解决方案上是否可重写？我们的目标是回答这些问题。我们的第一个主要结果是，在关系代数查询的可重写性方面，核心的表现力严格低于规范的通用解决方案，而标准通用解决方案的表现力又严格低于源。为了开发证明查询不可重写的技术，我们建立了解的结构性质；事实上，它们是从可重写证明中开发的技术机制中推导出来的。我们的第二个结果是，规范通用解决方案和核心都保留了数据的本地结构，并且每个可在这些解决方案上重写的目标查询都不能区分源中邻域相似的元组。这为我们提供了第一个简单的工具，用于检查查询是在规范通用解决方案上还是在核心上是不可重写的。我们还证明了这些工具可以推广到保持数据局部结构的任意转换，并研究了数据交换中查询回答的另一种语义。
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 (specifically, the “certain answers”). Basic questions are then: (1) how do these solutions compare in terms of query rewriting? and (2) how can we determine whether a query is rewritable over a particular solution?Our goal is to answer these questions. Our first main result is that, in terms of rewritability by relational algebra queries, the core is strictly less expressive than the canonical universal solution, which in turn is strictly less expressive than the source. To develop techniques for proving queries non-rewritable, we establish structural properties of solutions; in fact they are derived from the technical machinery developed in the rewritability proofs. Our second result is that both the canonical universal solution and the core preserve the local structure of the data, and that every target query rewritable over any of these solutions cannot distinguish tuples whose neighborhoods in the source are similar. This gives us a first simple tool for checking whether a query is non-rewritable over the canonical universal solution or over the core. We also show that these tools generalize to arbitrary transformations that preserve the local structure of the data, and investigate an alternative semantics of query answering in data exchange.
登录
查看更多内容
回答数据交换中的聚合查询
DOI：
10.1145/1376916.1376936
发表时间：
2008
期刊：
Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems
影响因子：
--
作者：
F. Afrati;Phokion G. Kolaitis
通讯作者：
Phokion G. Kolaitis
DOI：
10.1145/1055558.1055592
发表时间：
2004-06
期刊：
Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems
影响因子：
--
作者：
M. Arenas;P. Barceló;Ronald Fagin;L. Libkin
通讯作者：
M. Arenas;P. Barceló;Ronald Fagin;L. Libkin
数据交换中高效的核心计算
DOI：
10.1145/1346330.1346334
发表时间：
2008
期刊：
J. ACM
影响因子：
--
作者：
G. Gottlob;Alan Nash
通讯作者：
Alan Nash
DOI：
10.1145/2213556.2213583
发表时间：
2012
期刊：
Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on Principles of Database Systems
影响因子：
--
作者：
Ronald Fagin;Phokion G. Kolaitis
通讯作者：
Phokion G. Kolaitis
关系数据交换的逻辑基础
DOI：
10.1145/1558334.1558341
发表时间：
2009
期刊：
SIGMOD Rec.
影响因子：
--
作者：
P. Barceló
通讯作者：
P. Barceló