Chase termination
Chase termination
复制标题
追逐终止
DOI：
--
复制
发表时间：
2010
影响因子：
2.5
通讯作者：
S. Greco
中科院分区：
文献类型：
--
作者：
Francesca Spezzano;S. Greco
一些数据库领域（如数据交换和集成）都面临着修复数据库实例违反一组约束的问题。chase算法通过插入元组并设置空值来解决这种冲突。不幸的是，追逐算法可能不会终止，并且决定追逐过程是否终止的问题是不可判定的。最近，人们越来越感兴趣的是确定足够的结构属性的约束，保证追逐算法终止[8，10，14，15]。在本文中，我们提出了一个原始的技术，可以改善目前的条件检测追逐终止。我们的建议包括重写的原始集合的约束<$A到一个'等价'的集合<$A和验证的结构性质的追逐终止<$A。重写的约束允许识别更大类的约束，其中追逐终止是有保证的。特别地，我们证明了如果满足追踪终止条件T，则重写集<$α也满足T，但反之亦然，也就是说，存在重要的约束类，其中<$α满足T，而<$α不满足T。
Several database areas such as data exchange and integration share the problem of fixing database instance violations with respect to a set of constraints. The chase algorithm solves such violations by inserting tuples and setting the value of nulls. Unfortunately, the chase algorithm may not terminate and the problem of deciding whether the chase process terminates is undecidable. Recently there has been an increasing interest in the identification of sufficient structural properties of constraints which guarantee that the chase algorithm terminates [8, 10, 14, 15]. In this paper we propose an original technique which allows to improve current conditions detecting chase termination. Our proposal consists in rewriting the original set of constraints Σ into an 'equivalent' set Σα and verifying the structural properties for chase termination on Σα. The rewriting of constraints allows to recognize larger classes of constraints for which chase termination is guaranteed. In particular, we show that if Σ satisfies chase termination conditions T, then the rewritten set Σα satisfies T as well, but the vice versa is not true, that is there are significant classes of constraints for which Σα satisfies T and Σ does not.