All-Instances Termination of Chase is Undecidable
All-Instances Termination of Chase is Undecidable
复制标题
Chase 的所有实例终止是不可判定的
DOI：
10.1007/978-3-662-43951-7_25
复制
发表时间：
2014
影响因子：
--
通讯作者：
J. Marcinkowski
中科院分区：
文献类型：
--
作者：
Tomasz Gogacz;J. Marcinkowski
我们表明，所有实例的追逐终止都是不可判定的。更准确地说，没有算法决定，对于由元组生成依赖项（又名 Datalog ∃ 程序）组成的给定集合 \(\cal T\)，D 上的 \(\cal T\) 追踪是否会针对每个有限数据库实例 D 终止。我们的方法适用于遗忘追踪、半遗忘追踪，并且在稍作修改后也适用于标准追踪。这意味着我们为通常考虑的所有追逐版本的所有实例终止问题提供（负）解决方案。
We show that all–instances termination of chase is undecidable. More precisely, there is no algorithm deciding, for a given set \(\cal T\) consisting of Tuple Generating Dependencies (a.k.a. Datalog ∃ program), whether the \(\cal T\)-chase on D will terminate for every finite database instance D. Our method applies to Oblivious Chase, Semi-Oblivious Chase and – after a slight modification – also for Standard Chase. This means that we give a (negative) solution to the all–instances termination problem for all version of chase that are usually considered.