Paper Info
Title
First-Order Rewritability in Consistent Query Answering with Respect to Multiple Keys
Abstract
We study consistent query answering with respect to key dependencies. Given a (possibly inconsistent) database instance and a set of key dependencies, a repair is an inclusion-maximal subinstance that satisfies all key dependencies. Consistent query answering for a Boolean query is the following problem: given a database instance as input, is the query true in every repair? In [Koutris and Wijsen, ICDT 2019], it was shown that for every self-join-free Boolean conjunctive query and set of key dependencies containing exactly one key dependency per relation name (also called the primary key), this problem is in FO, L-complete, or coNP-complete, and it is decidable which of the three cases applies. In this paper, we consider the more general case where a relation name can be associated with more than one key dependency. It is shown that in this more general setting, it remains decidable whether or not the above problem is in FO, for self-join-free Boolean conjunctive queries. Moreover, it is possible to effectively construct a first-order query that solves the problem whenever such a query exists.
Year
DOI
Venue
2020
10.1145/3375395.3387654
SIGMOD/PODS '20: International Conference on Management of Data Portland OR USA June, 2020
Keywords
DocType
ISBN
conjunctive queries, consistent query answering, database repairing, first-order rewriting, keys
Conference
978-1-4503-7108-7
Citations 
PageRank 
References 
0
0.34
0
Authors
2
Name
Order
Citations
PageRank
Paraschos Koutris134726.63
Jef Wijsen267895.21