Consistent Query Answering for Primary Keys and Conjunctive Queries with Negated Atoms
Consistent Query Answering for Primary Keys and Conjunctive Queries with Negated Atoms
复制标题
主键和带有否定原子的联合查询的一致查询应答
DOI：
10.1145/3196959.3196982
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Jef Wijsen
中科院分区：
文献类型：
--
作者：
Paraschos Koutris;Jef Wijsen
本文研究了可能与主键约束不一致的数据库的查询应答。修复是通过删除最小元组集获得的任何一致数据库。给定一个布尔查询 q，问题 CERTAINTY(q) 将数据库作为输入，并询问在数据库的每次修复中 q 是否为真。一个重要的复杂性分类任务是确定给定 q，CERTAINTY(q) 是否是一阶可定义的（因此可以通过单个 SQL 查询求解）。这个问题已经针对无自连接的联合查询进行了广泛的研究。此类查询的一个重要扩展是允许否定原子。事实证明，如果允许否定原子，CERTAINTY(q) 可以表达一些经典的匹配问题。本文研究了带有否定原子的自连接自由联合查询类中 q 的 CERTAINTY(q) 一阶定义的存在性和构造。
This paper studies query answering on databases that may be inconsistent with respect to primary key constraints. A repair is any consistent database that is obtained by deleting a minimal set of tuples. Given a Boolean query q, the problem CERTAINTY(q) takes a database as input and asks whether q is true in every repair of the database. A significant complexity classification task is to determine, given q, whether CERTAINTY(q) is first-order definable (and thus solvable by a single SQL query). This problem has been extensively studied for self-join-free conjunctive queries. An important extension of this class of queries is to allow negated atoms. It turns out that if negated atoms are allowed, CERTAINTY(q) can express some classical matching problems. This paper studies the existence and construction of first-order definitions for CERTAINTY(q) for q in the class of self-join-free conjunctive queries with negated atoms.
准NC中的二分完美匹配
DOI：
10.1145/2897518.2897564
发表时间：
2016
期刊：
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing
影响因子：
--
作者：
Stephen A. Fenner;Rohit Gurjar;Thomas Thierauf
通讯作者：
Thomas Thierauf