ON THE INTEGRITY OF DATABASES WITH INCOMPLETE INFORMATION

Abstract

We consider the meaningfulness of databases with incomplete information. The basic idea is that such a database is meaningful if it can be completed to a database with complete information that satisfies the integrity constraints. We look at two approaches to defining the notion of completion. The open-world assumption requires that the database with complete information be an extension of the database with incomplete information. The closed-world assumption requires that the database with complete information be a conservative extension of the database with incomplete information. We prove the somewhat surprising result that integrity under the closed-world assumption is harder than integrity under the open-world assumption from both aspects of computational complexity and logical axiomatizability, while both notions are harder than integrity for databases with complete information.