[en] Most data analytical pipelines often encounter the problem of querying inconsistent data that violate pre-determined integrity constraints. Data cleaning is an extensively studied paradigm that singles out a consistent repair of the inconsistent data. Consistent query answering (CQA) is an alternative approach to data cleaning that asks for all tuples guaranteed to be returned by a given query on all (in most cases, exponentially many) repairs of the inconsistent data. In this paper, we identify a class of acyclic select-project-join (SPJ) queries for which CQA can be solved via SQL rewriting with a linear time guarantee. Our rewriting method can be viewed as a generalization of Yannakakis' algorithm for acyclic joins to the inconsistent setting. We present LinCQA, a system that takes as input any query in our class and outputs rewritings in both SQL and non-recursive Datalog with negation. We show that LinCQA often outperforms the existing CQA systems on both synthetic and real-world workloads, and in some cases, by orders of magnitude.
Disciplines :
Computer science
Author, co-author :
Fan, Zhiwei ; University of Wisconsin-Madison, Madison, WI, USA
Koutris, Paraschos ; University of Wisconsin-Madison, Madison, WI, USA
Ouyang, Xiating ; University of Wisconsin-Madison, Madison, WI, USA
WIJSEN, Jef ; Université de Mons - UMONS > Faculté des Science > Service des Systèmes d'information
Language :
English
Title :
LinCQA: Faster Consistent Query Answering with Linear Time Guarantees
