论超越分层的追逐终结

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

摘要翻译：
我们研究了chase算法的终止问题，该算法是各种数据库问题的核心工具，如约束蕴涵问题、合取查询优化、使用视图重写查询、数据交换和数据集成。chase的基本思想是，给定一个数据库实例和一组约束作为输入，以修复数据库实例中违反约束的情况。众所周知，对于一组任意的约束，追逐不一定会终止（通常，即使终止也是不可判定的）。为了解决这个问题，我们回顾了现有的充分终止条件的局限性，并开发了新的技术，允许我们建立较弱的充分条件。特别地，我们引入了安全和归纳限制两个新的终止条件，并用它们定义了所谓的终止条件的T-层次。然后，我们研究终止条件与先前条件的相互关系，以及检查条件的复杂性。这种分析导致了一种算法，该算法检查T层次结构的一个级别中的成员资格，并考虑了终止条件的复杂性。作为另一个贡献，我们研究了数据相关的chase终止问题，给出了充分的终止条件W.R.T.固定实例。它们可能保证终止，尽管在一般情况下追捕不会终止。作为上述技术的一个应用，我们将我们的结果转移到对底层数据库的追逐可能不会终止的知识库上的查询回答领域，使现有的算法适用于更广泛的约束类。
---
英文标题：
《On Chase Termination Beyond Stratification》
---
作者：
Michael Meier, Michael Schmidt, Georg Lausen
---
最新提交年份：
2009
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Databases        数据库
分类描述：Covers database management, datamining, and data processing. Roughly includes material in ACM Subject Classes E.2, E.5, H.0, H.2, and J.1.
涵盖数据库管理、数据挖掘和数据处理。大致包括ACM学科类E.2、E.5、H.0、H.2和J.1中的材料。
--
一级分类：Computer Science        计算机科学
二级分类：Artificial Intelligence        人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--

---
英文摘要：
  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.
---
PDF链接：
https://arxiv.org/pdf/0906.4228

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：Optimization Intelligence Presentation Contribution Constraints 作为 termination 优化 研究 data