On the Complexity and axiomatizability of consistent database states extended abstract

Abstract

A database is consistent with respect to a set ∑ of dependencies if it has a weak instance. A weak instance is a universal relation that satisfies ∑, and whose projections on the relation schemes are supersets of the relations in the database. In this paper we investigate the complexity of testing consistency and the logics that can axiomatize consistency, relative to a fixed set C of dependencies. If I: is allowed to include embedded dependencies, then consistency can be non-recursive. If I: consists only of total dependencies then consistency can be tested in polynomial time. The degree of the polynomial can, however, be arbitrarily high. Consistency can be axiomatized but not finitely axiomatized by equality generating dependencies. If embedded dependencies are allowed then consistency cannot be finitely axiomatized by any effective logic. If, on the other hand, only total dependencies are allowed then consistency can be finitely axiomatized by fixpoint logic.