Expanding queries to incomplete databases by interpolating general logic programs

Chitta Baral, Michael Gelfond and Olga Kosheleva

Abstract

In databases, queries are usually defined on complete databases. In this paper we introduce and motivate the notion of extended queries that are defined on incomplete databases. We argue that the language of extended logic program is appropriate for representing extended queries. We show through examples that given a query, a particular extension of it has important characteristics which corresponds to removal of the CWA from the original specification of the query. We refer to this particular extension as the {\em expansion} of the original query. Normally queries are expressed as general logic programs. We develop an algorithm that given a general logic program (satisfying certain syntactic properties) expressing a query constructs an extended logic program that expresses the expanded query. The extended logic program is referred to as the {\em interpolation} of the given general logic program.