Amalgamating Knowledge Bases, III - Algorithms, Data Structures, and
Query Processing
Amalgamating Knowledge Bases, III - Algorithms, Data Structures, and
Query Processing
Files
Publication or External Link
Date
1998-10-15
Authors
Adali, Sibel
Subrahmanian, V.S.
Advisor
Citation
DRUM DOI
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)