Minimal-change integrity maintenance using tuple deletions
Minimal-change integrity maintenance using tuple deletions
复制标题
DOI：
10.1016/j.ic.2004.04.007
复制
发表时间：
2002-12
期刊：
影响因子：
--
通讯作者：
J. Chomicki;J. Marcinkowski
中科院分区：
文献类型：
--
作者：
J. Chomicki;J. Marcinkowski
我们在关系数据库的完整性约束的背景下解决最小变化完整性维护的问题。我们假设完整性恢复操作仅限于元组删除。我们关注两个基本的计算问题：修复检查（数据库实例是给定数据库的修复吗？）和一致的查询答案[in: ACM Symposium onprinciples of Database Systems (PODS), 1999, 68]（元组是给定数据库的每次修复中给定查询的答案吗？）。我们研究了这两个问题的计算复杂性，划定了易处理和难处理情况之间的界限。我们考虑拒绝约束、一般功能和包含依赖性以及键和外键约束。我们的结果揭示了最小变化完整性维护的计算可行性。易处理的案例应该转化为实际的实施。棘手的结果凸显了任何完整性执行机制（例如触发器或引用约束操作）作为执行最小更改完整性维护的方式的固有局限性。
We address the problem of minimal-change integrity maintenance in the context of integrity constraints in relational databases. We assume that integrity-restoration actions are limited to tuple deletions. We focus on two basic computational issues: repair checking (is a database instance a repair of a given database?) and consistent query answers [in: ACM Symposium on Principles of Database Systems (PODS), 1999, 68] (is a tuple an answer to a given query in every repair of a given database?). We study the computational complexity of both problems, delineating the boundary between the tractable and the intractable cases. We consider denial constraints, general functional and inclusion dependencies, as well as key and foreign key constraints. Our results shed light on the computational feasibility of minimal-change integrity maintenance. The tractable cases should lead to practical implementations. The intractability results highlight the inherent limitations of any integrity enforcement mechanism, e.g., triggers or referential constraint actions, as a way of performing minimal-change integrity maintenance.