Paper Info
Title
Consistent Query Answering for Primary Keys and Conjunctive Queries with Negated Atoms.
Abstract
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.
Year
DOI
Venue
2018
10.1145/3196959.3196982
SIGMOD/PODS '18: International Conference on Management of Data Houston TX USA June, 2018
Keywords
Field
DocType
Conjunctive queries, consistent query answering, negation, primary keys
SQL,Discrete mathematics,Conjunctive query,Certainty,Primary Key,Negation,Computer science,Tuple,Theoretical computer science,Boolean conjunctive query
Conference
ISBN
Citations 
PageRank 
978-1-4503-4706-8
0
0.34
References 
Authors
17
2
Name
Order
Citations
PageRank
Paraschos Koutris134726.63
Jef Wijsen267895.21