Towards a logical reconstruction of a theory for locally closed databases

The Closed World Assumption(CWA) on databases expresses the assumption that an atom not in the database is false. This assumption is applicable only in cases where the database has complete knowledge about the domain of discourse. In this paper, we investigate locally closed databases, that is: databases that are sound but partially incomplete about their domain. Such databases consist of a standard database instance, augmented with a collection of Local Closed World Assumptions~(LCWAs). A LCWA is a `local' form of the CWA, expressing that a database relation is complete in a certain area, called a window of expertise. In this work, we study locally closed databases both from a knowledge representation and from a computational perspective. At the representation level, the approach taken in this paper distinguishes between the data that is conveyed by a database and the meta-knowledge about the area in which the data is complete. We study the semantics of the LCWA's and relate it to several knowledge representation formalisms. At the reasoning level, we study the complexity of, and algorithms for two basic reasoning tasks: computing certain and possible answers to queries and determining whether a database has complete knowledge on a query. As the complexity of these tasks is unacceptably high, we develop efficient approximate methods for query answering. We also prove that for useful classes of queries and locally closed databases, these methods are optimal, and thus they solve the original query in a tractable way. As a result, we obtain classes of queries and locally closed databases for which query answering is tractable.status: publishe