Approximate Query Answering in Locally Closed Databases

Abstract

The Closed-World Assumption (CWA) on databases expresses that an atom not in the database is false. A more appropriate assumption for databases that are sound but partially incomplete, is the Local Closed-World Assumption (LCWA), which is a local form of the CWA, expressing that the database is complete in a certain area, called the ‘window of expertise’. Databases consisting of a standard database instance augmented with a collection of LCWA’s are called locally closed databases. In this paper, we investigate the complexity of certain and possible query answering in such databases. As it turns out that these problems are intractable, we develop efficient approximate methods to underestimate certain answers and overestimate possible answers. We prove that under certain conditions, our methods produce complete answers.