Amalgamating Knowledge Bases, III - Algorithms, Data Structures, and Query Processing

Abstract

Integrating knowledge from multiple sources is an important aspect of automated reasoning systems. In the first part of this series of papers, we presented a uniform declarative framework, based on <em> annotated logics</em>, for amalgamating multiple knowledge bases when these knowledge bases (possibly) contain inconsistencies, uncertainties, and non-monotonic modes of negation. We showed that annotated logics may be used, with some modifications, to <em> mediate</em> between different knowledge bases. The multiple knowledge bases are amalgamated by embedding the individual knowledge bases into a lattice. In this paper, we briefly describe an SLD-resolution based proof procedure that is sound and complete w.r.t. our declarative semantics. We will then develop an <tt> OLDT </tt>-resolution based query processing procedure, <tt> MULTI-OLDT </tt>, that satisfies two important properties: (1) <em> efficient reuse</em> of previous computations is achieved by maintaining a table -- we describe the structure of this table and show that table operations can be efficiently executed, and (2) <em> approximate, interruptable query answering </em> is achieved, i.e. it is possible to obtain an ``intermediate, approximate'' answer from the query processing procedure by interrupting it at any point in time during its execution. The design of the <tt> MULTI-OLDT </tt> procedure will include the development of run-time algorithms to incrementally and efficiently update the table. (Also cross-referenced as UMIACS-TR-94-35)