UC Santa Cruz

An inconsistent database is a database that violates one or more of its integrity constraints. In reality, violations of integrity constraints arise frequently under several different circumstances. Inconsistent databases have long posed the challenge to develop suitable tools for meaningful query answering. A principled approach for querying inconsistent databases is the consistent query answering framework. The approach suggests that the inconsistent database is left as-is, and inconsistencies are handled at query time by considering all possible repairs of the inconsistent database.

In this dissertation, we study consistent query answering for conjunctive queries and primary key constraints. For this class, the problem can be coNP-complete in data complexity. We study heuristics for efficiently computing the consistent answers. Our heuristics model the consistent query answering problem with Binary Integer Programming (BIP). We develop EQUIP, a system for computing the consistent answers, which relies on fast BIP solvers to compute the consistent answers. We carry out an extensive experimental investigation that validates the effectiveness of our approach, and shows that EQUIP scales well to large databases. In addition, we study data complexity of consistent query answering, aiming to delineate the boundary between tractability and intractability. We establish a dichotomy on the data complexity of consistent answers for queries with two atoms, by giving a syntactic condition based on which, one can precisely determine the complexity as being either in P, or coNP-complete. For for acyclic and self-join free conjunctive queries, we prove sufficient conditions for tractability and intractability of consistent answers. Moreover, for this class, we conjecture that there exists a dichotomy, and give a criterion for determining the complexity of each instance of the class.