Polynomial Time Queries over Inconsistent Databases with Functional Dependencies and Foreign Keys

This paper addresses the problem of efficiently computing consistent answers to queries over relational databases which may be inconsistent with respect to functional dependencies and foreign key constraints. Since consistent query answers over inconsistent databases are obtained from repaired databases, we first present a repair strategy. More specifically, in this paper we consider particular sets of functional dependencies, called canonical, and a repair strategy whereby only tuple updates and insertions are allowed in order to restore consistency: if foreign key constraints are violated, new tuples (possibly containing null values) are inserted into the database, whereas if functional dependency violations occur, tuple updates (possibly introducing unknown values, i.e. special symbols which can take values from a limited set of constants of the source database) are performed. Therefore, we propose a semantics of constraint satisfaction for incomplete databases containing null and unknown values since the repair process can lead to such databases. The proposed approach allows us to obtain a unique (incomplete) repaired database which may be computed in polynomial time. Drawing on the results on the complexity of querying incomplete databases containing OR-objects, we identify classes of constraints for which the consistent answers to particular classes of conjunctive queries can be computed in polynomial time.