Approximate Query Answering in Locally Closed Databases

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

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.