| सारांश: | PROLOG is the most well known, widely used programming language for logic programming.
PROLOG is a programming language that uses a small set of basic mechanisms
to create surprisingly powerful programs. These mechanisms are pattern-matching, treebased
data structuring and backtracking. PROLOG is used for the development of scheduling
systems, knowledge systems, expert systems and many other applications. However,
being goal-driven (query driven) PROLOG’S query engine suffers from some well-known
problems such as susceptibility to infinite looping, repeated subcomputation and unsatisfactory
semantics of negation. These limitations have been addressed by the tabled extensions
(TLP) to PROLOG evaluation. The main idea of tabling is to cache the answers
for computations and then reuse them when a repeated computation appears. The TLP
approach assumes that the database of facts/rules, of which the query results drawn from,
remains constant through time and therefore the tabulated results are assumed to remain
valid. This prohibits the use of TLP in non-monotonic logic where such an assumption
cannot be guaranteed. To overcome this problem the idea of incremental tabulation has
been introduced. An incrementally maintained table is one that continually contains the
correct answers in the presence of updates to underlying predicates on which the tabled
predicate depends. The critical challenges for incremental evaluation are how to detect
and update the tabled answers due to the changes in the database of facts and rules associated
with the tabled answers.
ii
This thesis presents an alternative approach to incremental tabulation that is capable
of working in non-monotonic situations. The basic idea of our approach is that, as the
PROLOG inference engine evaluates the query for the first time, the answers returned by
the engine for the query are converted into a justification-based truth-maintenance system
(JTMS) network. Every successful branch is translated into a JTMS network that links the
facts used in the proof branch to the answer generated by that branch. When the same
query is re-evaluated, the query engine collects the valid answers for the query at that
moment and returns them by using the cached proof structure for the query. When the
state of database is changed, the JTMS component propagates the effect of the change
through its network to maintain the consistency of old proofs. At the same time, the
database monitor keeps watching the addition of the new data (facts/rules) to the system
and triggers the resumption of previously proven queries in order to update their proof
structure.
The outcome of this thesis is JLOG. JLOG is a sub-system integrated with PROLOG
inference engine which supports incremental tabled extensions to PROLOG evaluation.
The thesis presents the design, necessary data structures, algorithms and implementation
details of JLOG. The results of comparing the performance of JLOG to regular PROLOG
and Tabled PROLOG systems are also presented.
|
|---|
