Accuracy and Efficiency of Fixpoint Methods for Approximate Query Answering in Locally Complete Databases

Principles of Knowledge Representation and Reasoning: Proceedings of the Eleventh International Conference (KR2008)

Volume

Principles of Knowledge Representation and Reasoning: Proceedings of the Eleventh International Conference (KR2008)

Contents

Standard databases convey Reiter's closed-world assumption that an atom not in the database is false. This assumption is relaxed in locally closed databases that are sound but only partially complete about their domain. One of the consequences of the weakening of the closed-world assumption is that query answering in locally closed databases is undecidable. In this paper, we develop efficient approximate methods for query answering, based on fixpoint computations, and investigate conditions that assure the optimality of these methods. Our approach of approximative reasoning may be incorporated in different contexts where incompleteness plays a major role and efficient reasoning is imperative.