Type: Research Highlight

Title: Consistent Query Answering for Primary Keys

Paraschos Koutris, Jef Wijsen

Available in: PDF

We study the complexity of consistent query answering with respect to primary key violations, for self-join-free conjunctive queries. A repair of a possibly inconsistent database is obtained by selecting a maximal number of tuples without selecting two distinct tuples with the same primary key value. For any Boolean query q, CERTAINTY(q) is the problem that takes a database as input, and asks whether q is true in every repair of the database. The complexity of this problem has been extensively studied for q ranging over the class of self-join-free Boolean conjunctive queries. A research challenge is to determine, given q, whether CERTAINTY(q) belongs to complexity classes FO, P, or coNP-complete. We show that for any self-join-free Boolean conjunctive query q, it can be decided whether or not CERTAINTY(q) is in FO. Further, CERTAINTY(q) is either in P or coNP-complete, and the complexity dichotomy is effective. This settles a research question of practical relevance that has been open for ten years.


Paris Koutris - paris.koutrisParaschos Koutris is an assistant professor at the University of Wisconsin-Madison, where he started in Fall 2015. Before that, he was a Ph.D. student in the Computer Science & Engineering Department at the University of Washington, advised by Dan Suciu. His research focuses on the theoretical aspects of data management. He is particularly interested in applying formal methods to various problems of modern data management systems: data processing in massively parallel systems, data pricing, and managing data with uncertainty. He received his Diploma from the National Technical University of Athens and also completed a M.Sc. Degree in Logic, Algorithms and Computation at the University of Athens.

Jef Wijsen - jef.wijsenJef Wijsen is a professor in the Department of Informatics at the University of Mons (Belgium), where he is leading the research group on information systems. He holds a doctoral degree from KU Leuven (1995). He is currently on the editorial boards of The VLDB Journal and Information Processing Letters. He has served on the program committees of numerous workshops and conferences, and has co-chaired the program committees of TIME 2010 and SUM 2013. He has published in premier journals and conferences on various topics relating to relational database theory, temporal database systems, and data mining. Since 2007, much of his research has focused on the computational complexity of consistent query answering for primary keys.

Back to Gallery     Go to the Full Issue