A SAT-Based System for Consistent Query Answering
A SAT-Based System for Consistent Query Answering
复制标题
基于 SAT 的一致查询应答系统
DOI：
10.1007/978-3-030-24258-9_8
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Kolaitis, Phokion G.
中科院分区：
文献类型：
--
作者：
Dixit, Akhil A;Kolaitis, Phokion G.
不一致数据库是违反一个或多个完整性约束（如函数依赖性）的数据库。一致性查询是一种严格和原则性的方法，用于处理针对不一致数据库提出的查询的语义。对不一致数据库上的查询的一致回答是对每次修理的查询的回答的交集，即，在每一个一致的数据库，不同于给定的不一致的一个在最小的方式。计算一个固定的合取查询的一致性答案在一个给定的不一致的数据库可以是一个CONP困难的问题，即使每个固定的合取查询是有效的计算在一个给定的一致database.We设计，实现，并评估CAvSAT，SAT为基础的系统一致性查询回答。CAvSAT利用了一组从一致性查询回答到SAT和加权MaxSAT的补充的自然约简。该系统能够处理联合查询和任意拒绝约束的联合，其中包括函数依赖作为特殊情况。我们报告的结果从实验评估CAvSAT合成和现实世界的数据库。这些结果提供的证据表明，基于SAT的方法可以产生一个全面的和可扩展的系统，一致的查询回答。
An inconsistent database is a database that violates one or more integrity constraints, such as functional dependencies. Consistent Query Answering is a rigorous and principled approach to the semantics of queries posed against inconsistent databases. The consistent answers to a query on an inconsistent database is the intersection of the answers to the query on every repair, i.e., on every consistent database that differs from the given inconsistent one in a minimal way. Computing the consistent answers of a fixed conjunctive query on a given inconsistent database can be a coNP-hard problem, even though every fixed conjunctive query is efficiently computable on a given consistent database.We designed, implemented, and evaluated CAvSAT, a SAT-based system for consistent query answering. CAvSAT leverages a set of natural reductions from the complement of consistent query answering to SAT and to Weighted MaxSAT. The system is capable of handling unions of conjunctive queries and arbitrary denial constraints, which include functional dependencies as a special case. We report results from experiments evaluating CAvSAT on both synthetic and real-world databases. These results provide evidence that a SAT-based approach can give rise to a comprehensive and scalable system for consistent query answering.