Peer data exchange
Peer data exchange
复制标题
同行数据交换
DOI：
10.1145/1065167.1065188
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
W. Tan
中科院分区：
文献类型：
--
作者：
Ariel Fuxman;Phokion G. Kolaitis;Renée J. Miller;W. Tan
本文介绍并研究了一个用于在对等点之间共享和交换数据的框架，称为对等数据交换。这个框架是一个成熟的对等数据管理系统的特例，也是源模式和目标模式之间数据交换的一般化。对等体数据交换背后的动机是对对等体之间的权限关系进行建模，其中源对等体可以向使用源到目标约束指定的目标对等体贡献数据，并且目标对等体可以使用目标到源约束来限制它愿意接收的数据，但不能修改源对等体的数据。在这个框架中的一个基本的算法问题是，决定一个解决方案的存在：给定一个源实例和一个目标实例为一个固定的对等数据交换设置，目标实例可以被增强的方式，源实例和增强的目标实例满足所有的约束条件的设置？我们调查的计算复杂性的问题，对等数据交换设置中的约束是由元组生成依赖关系。我们表明，这个问题总是在NP，它可以是NP完全的，即使是“非循环”的对等数据交换设置。我们还表明，目标合取查询的某些答案的数据复杂性是在coNP，它可以是coNP完全的，即使是“非循环”的对等数据交换设置。在此之后，我们探讨了确定解的存在性问题的易处理性和难处理性之间的界限。为此，我们确定了对等体之间约束的广泛语法条件，在此条件下，解决方案的测试可以在多项式时间内求解。这些语法条件包括对等数据交换的重要特殊情况，其中源到目标约束是任意元组生成依赖关系，但目标到源约束是本地视图依赖关系。最后，我们表明，我们确定的句法条件是紧的，在这个意义上说，最小的放松，他们导致棘手。
In this paper, we introduce and study a framework, called peer data exchange, for sharing and exchanging data between peers. This framework is a special case of a full-fledged peer data management system and a generalization of data exchange between a source schema and a target schema. The motivation behind peer data exchange is to model authority relationships between peers, where a source peer may contribute data to a target peer, specified using source-to-target constraints, and a target peer may use target-to-source constraints to restrict the data it is willing to receive, but cannot modify the data of the source peer. A fundamental algorithmic problem in this framework is that of deciding the existence of a solution: given a source instance and a target instance for a fixed peer data exchange setting, can the target instance be augmented in such a way that the source instance and the augmented target instance satisfy all constraints of the setting? We investigate the computational complexity of the problem for peer data exchange settings in which the constraints are given by tuple generating dependencies. We show that this problem is always in NP, and that it can be NP-complete even for "acyclic" peer data exchange settings. We also show that the data complexity of the certain answers of target conjunctive queries is in coNP, and that it can be coNP-complete even for "acyclic" peer data exchange settings. After this, we explore the boundary between tractability and intractability for the problem of deciding the existence of a solution. To this effect, we identify broad syntactic conditions on the constraints between the peers under which testing for solutions is solvable in polynomial time. These syntactic conditions include the important special case of peer data exchange in which the source-to-target constraints are arbitrary tuple generating dependencies, but the target-to-source constraints are local-as-view dependencies. Finally, we show that the syntactic conditions we identified are tight, in the sense that minimal relaxations of them lead to intractability.