Alvaro Cortes-Calabuig, Marc Denecker, Ofer Arieli, Maurice Bruynooghe
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 thatthese 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.
Subjects: 11. Knowledge Representation; 9.3 Mathematical Foundations
Submitted: Apr 20, 2007