NetNews Usenet Archive 1992 #30/NN_1992_30.iso/spool/comp/lang/prolog/2265

Text File | 1992-12-21 | 3.0 KB | 65 lines

Newsgroups: comp.lang.prolog
Path: sparky!uunet!usc!cs.utexas.edu!qt.cs.utexas.edu!yale.edu!ira.uka.de!math.fu-berlin.de!mailgzrz.TU-Berlin.DE!cs.tu-berlin.de!hoppet
From: [e-mail] (Thomas Hoppe)
Subject: Looking for clause or n-ary tree indexing code
Message-ID: <[e-mail]>
Keywords: indexing, clauses, n-ary trees, Quintus 'indexer'
Sender: [e-mail]
Organization: Techn. University of Berlin, Germany
Date: Fri, 18 Dec 1992 23:26:58 GMT
Lines: 53

Dear Prolog net'ers

for the purpose of explicit and fast storage of proof-trees, I'm
looking for some sophisticated indexing mechanism on Prolog clauses.
Clauses asserted in the Prolog DB are implicitly indexed on the
predicate symbol contained in the clause head as primary key and
usually explicitly on the first argument as secondary key. For the
purpose of a fast access to clauses over some predicate symbol
contained in the body of a clause, I need now some indexing mechanism.
I.e.\ if a clause p :- q, r. is given, I like to retrieve this clause
directly from the Prolog DB and from a given goal r without inspecting
every asserted clause and its body.

Since a clause p :- q, r. can be regarded as tree of depth one with
root p and sons q and r, such an indexing mechanism could also be used
to index trees with an arbitrary number of sons per node.  Such an
indexing mechanism is also useful for implementing forward chaining
inference systems, thus I thought that it is maybe a good idea to ask
the Prolog community out there whether someone has implemented already
such a mechanism.

Although the Quintus libraries contain some package called 'indexer',
which realizes an advanced indexing mechanism on arbitrary arguments
(and thus extends the secondary explicite indexing mechanism above), I
haven't found yet any library package realizing an extended indexing
mechanism of the implicite, primary type. Clearly, indexing on the
arguments of a predicate is much easier (since their number of
arguments is fixed) than indexing over an arbitrary long list of body
predicates.

Although a Prolog clause is a term structure of nested binary symbols
(usually :- , and ;) and literals as leaves, the first idea is to
regard a clause as binary tree. On this way 'indexer' can be easily
extended for indexing binary tree's, since the number of subtree's is
fixed. But that's a level to low for my purpose: first, this has the
consequence that a large number of (:- , and ;) entries exists in the
DB, and second, for finding the clause head an algorithm would need to
'crawl up' the tree.  If instead the indexing mechanism indexes n-ary
tree's, a quicker look-up is possible.

If you have implemented such a thing or if you know a reference for
some code, I would appreciate it. If of interest, I summarize the
responses I receive.

ADVthanxANCE,

    Thomas Hoppe

--
Thomas Hoppe  Projekt KIT-BACK        email: [e-mail]
Technische Universitaet Berlin        phone: [phone]
Franklinstr. 28/29            fax  : [phone]
1000 Berlin 10    Germany            priv.: 030-3236564