On Chase Termination Beyond Stratification
On Chase Termination Beyond Stratification
复制标题
论超越分层的大通终止
DOI：
--
复制
发表时间：
2009
影响因子：
2.5
通讯作者：
G. Lausen
中科院分区：
文献类型：
--
作者：
M. Meier;Michael Schmidt;G. Lausen
我们研究终止问题的追逐算法，在各种数据库问题，如约束蕴涵问题，连接查询优化，重写查询使用视图，数据交换和数据集成的中心工具。追踪的基本思想是，给定一个数据库实例和一组约束作为输入，修复数据库实例中的约束冲突。众所周知，对于任意一组约束，追逐不一定会终止（一般来说，追逐是否终止甚至是不可判定的）。为了解决这个问题，我们审查现有的充分终止条件的追逐和开发新的技术，使我们能够建立较弱的充分条件的局限性。特别是，我们引入了两个新的终止条件称为安全和归纳限制，并使用它们来定义所谓的T-层次的终止条件。然后，我们研究我们的终止条件与以前的条件和检查我们的条件的复杂性的相互关系。这种分析导致一个算法，检查成员在一个级别的T-层次结构和帐户的复杂性的终止条件。作为另一个贡献，我们研究了数据依赖的追逐终止问题，并给出了充分的终止条件w.r.t.固定实例。它们可能保证终止，尽管追逐在一般情况下不会终止。作为我们的技术超出那些已经提到的应用程序，我们将我们的结果转移到查询回答领域的知识基础上的追逐底层数据库可能不会终止，使现有的算法适用于更广泛的类的约束。
We study the termination problem of the chase algorithm, a central tool in various database problems such as the constraint implication problem, Conjunctive Query optimization, rewriting queries using views, data exchange, and data integration. The basic idea of the chase is, given a database instance and a set of constraints as input, to fix constraint violations in the database instance. It is well-known that, for an arbitrary set of constraints, the chase does not necessarily terminate (in general, it is even undecidable if it does or not). Addressing this issue, we review the limitations of existing sufficient termination conditions for the chase and develop new techniques that allow us to establish weaker sufficient conditions. In particular, we introduce two novel termination conditions called safety and inductive restriction, and use them to define the so-called T-hierarchy of termination conditions. We then study the interrelations of our termination conditions with previous conditions and the complexity of checking our conditions. This analysis leads to an algorithm that checks membership in a level of the T-hierarchy and accounts for the complexity of termination conditions. As another contribution, we study the problem of data-dependent chase termination and present sufficient termination conditions w.r.t. fixed instances. They might guarantee termination although the chase does not terminate in the general case. As an application of our techniques beyond those already mentioned, we transfer our results into the field of query answering over knowledge bases where the chase on the underlying database may not terminate, making existing algorithms applicable to broader classes of constraints.