Alladi Ramakrishnan Hall

Consistent Query Answering for Inconsistent Databases

Anantha Padmanabha

IIT Dharwad

Data in a big data dump or a data-warehouse is often incomplete and/or inconsistent. If we want to build a database from such a source, the resulting database is likely to violate integrity constraints (like the primary key constraint).

In particular, if a database violates primary key constraint, it will contain more than one tuple for the same primary key. In this setting, the notion of a repair is defined by picking exactly one tuple for each primary key (maximal consistent subset of the database). A Boolean conjunctive query q is "certain" for an inconsistent database D if q evaluates to true over all repairs of D. In this context, there is a dichotomy conjecture that states that for a fixed boolean conjunctive query q, testing whether q is certain for an input database D is either polynomial time or coNP-complete.

The conjecture is open in general and has been open for more than two decades. In this talk we will discuss some recent progress that we have made towards proving the conjecture using some new algorithms that we have introduced.

Results discussed in this talk is a joint work with Diego Figueira, Luc Segoufin and Cristina Sirangello.