Theory and Applications of Satisfiability Testing – SAT 2016
Theory and Applications of Satisfiability Testing – SAT 2016
复制标题
满意度测试的理论与应用 – SAT 2016
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
M. Denecker
中科院分区：
文献类型：
--
作者：
Jo Devriendt;B. Bogaerts;M. Bruynooghe;M. Denecker
管理数据库中的不一致性是一个长期的挑战。数据库修复的框架提供了一个处理数据库中不一致的原则性方法。直观地说，不一致数据库的修复是以最小的方式与给定的不一致数据库不同的一致数据库。修复检查和一致性查询回答是在这种情况下出现的两个基本的算法问题。这两个问题中的第一个问题是，给定两个数据库，一个是否是另一个的修复。第二个问题是，在给定的不一致数据库的每次修复时，查询是否为真。这次谈话的目的是给在这方面的一个身体的结果的概述，重点是修复检查和一致的查询回答，包括二分法定理的追求的计算复杂性。除了提出开放的问题，谈话的最后一部分将包括一个潜在的使用开发实用系统的一致的查询回答的求解器的讨论。
Managing inconsistency in databases is a long-standing challenge. The framework of database repairs provides a principled approach towards coping with inconsistency in databases. Intuitively, a repair of an inconsistent database is a consistent database that differs from the given inconsistent database in a minimal way. Repair checking and consistent query answering are two fundamental algorithmic problems arising in this context. The first of these two problems asks whether, given two databases, one is a repair of the other. The second asks whether, a query is true on every repair of a given inconsistent database. The aim of this talk is to give an overview of a body of results in this area with emphasis on the computational complexity of repair checking and consistent query answering, including the quest for dichotomy theorems. In addition to presenting open problems, the last part of the talk will include a discussion of the potential use of solvers in developing practical systems for consistent query answering.