Consistent Query Answering under Primary Keys: A Characterization of Tractable Queries
Authors
- Jef Wijsen (University of Mons-Hainaut, Belgium)
Abstract
This article deals with consistent query answering to conjunctive queries under primary key constraints. The repairs of an inconsistent database DB are obtained by selecting a maximum number of tuples from DB without ever selecting two tuples that agree on their primary key. For a Boolean conjunctive query Q, we are interested in the following question: does there exist a Boolean first-order query F such that for every database DB, F evaluates to true on DB if and only if Q evaluates to true on every repair of DB? We address this problem for acyclic conjunctive queries in which no relation name occurs more than once. Our results improve previous solutions that are based on Fuxman-Miller join graphs.
Session
ICDT Research Session 1: Inconsistency and Repairs (Monday, March 23, 11:00—12:30)