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)