Efficient core computation in data exchange
Efficient core computation in data exchange
复制标题
数据交换中高效的核心计算
DOI：
10.1145/1346330.1346334
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Alan Nash
中科院分区：
文献类型：
--
作者：
G. Gottlob;Alan Nash
数据交换涉及将数据从一个数据库插入到具有不同模式的另一个数据库中。Fagin等人。[2005]已经表明，在可解决的数据交换问题的通用解决方案中，存在-直到同构-唯一的最紧凑的一个，“核心”，并令人信服地认为，这个核心应该是要实现的数据库。他们指出，作为一个重要的开放问题，核心是否可以在多项式时间内计算，在一般的设置中，源和目标模式之间的映射是由源到目标的约束，这些约束是任意元组生成依赖关系（tgds）和目标约束组成的等式生成依赖关系（egds）和弱非循环tgds集。在本文中，我们通过开发新的方法来有效地计算通用解决方案的核心来解决这个问题。这一积极的结果表明，基于核的数据交换是可行的，适用于一个非常普遍的设置。除了我们的主要结果，我们使用超树分解的方法来获得新的算法和上界的查询包含检查和计算任意数据库实例的核心。我们还表明，计算核心的数据交换问题是固定参数棘手的一些相关参数，计算核心是NP-完全的，如果目标tgds的规则体增加了一个特殊的谓词，区分空值从一个恒定的数据值。
Data exchange deals with inserting data from one database into another database having a different schema. Fagin et al. [2005] have shown that among the universal solutions of a solvable data exchange problem, there exists—up to isomorphism—a unique most compact one, “the core”, and have convincingly argued that this core should be the database to be materialized. They stated as an important open problem whether the core can be computed in polynomial time in the general setting where the mapping between the source and target schemas is given by source-to-target constraints that are arbitrary tuple generating dependencies (tgds) and target constraints consisting of equality generating dependencies (egds) and a weakly acyclic set of tgds. In this article, we solve this problem by developing new methods for efficiently computing the core of a universal solution. This positive result shows that data exchange based on cores is feasible and applicable in a very general setting. In addition to our main result, we use the method of hypertree decompositions to derive new algorithms and upper bounds for query containment checking and computing cores of arbitrary database instances. We also show that computing the core of a data exchange problem is fixed-parameter intractable with respect to a number of relevant parameters, and that computing cores is NP-complete if the rule bodies of target tgds are augmented by a special predicate that distinguishes a null value from a constant data value.