论文标题
不均匀终止追逐：大小和复杂性
Non-Uniformly Terminating Chase: Size and Complexity
论文作者
论文摘要
最初引入的追逐程序是用于检查数据库约束的含义，后来用于计算数据交换解决方案的含义，最近已成为基于规则的本体论推理中的中心算法工具。在这种情况下，一个关键问题是非均匀的追逐终止：数据库W.R.T.基于规则的本体终止？如果是这种情况，那么追逐结果的大小是多少？我们专注于构成基于规则的本体语言的强大的元组依赖依赖性（TGD），并研究了Chase的半糊状版本的上述核心问题。我们的主要发现之一是，在多项式时间W.R.T.中，可行的TGD的不均匀的半斑点追逐终止是可行的。数据库和追逐结果的大小（每当有限时）是线性W.R.T.数据库。为了我们关于非均匀追逐终止的结果，我们表明，最初在本体论查询答案的背景下引入的基本技术，例如简化和线性化，可以安全地应用于追逐终止问题。
The chase procedure, originally introduced for checking implication of database constraints, and later on used for computing data exchange solutions, has recently become a central algorithmic tool in rule-based ontological reasoning. In this context, a key problem is non-uniform chase termination: does the chase of a database w.r.t. a rule-based ontology terminate? And if this is the case, what is the size of the result of the chase? We focus on guarded tuple-generating dependencies (TGDs), which form a robust rule-based ontology language, and study the above central questions for the semi-oblivious version of the chase. One of our main findings is that non-uniform semi-oblivious chase termination for guarded TGDs is feasible in polynomial time w.r.t. the database, and the size of the result of the chase (whenever is finite) is linear w.r.t. the database. Towards our results concerning non-uniform chase termination, we show that basic techniques such as simplification and linearization, originally introduced in the context of ontological query answering, can be safely applied to the chase termination problem.
