home *** CD-ROM | disk | FTP | other *** search
- Newsgroups: comp.lang.prolog
- Path: sparky!uunet!math.fu-berlin.de!mailgzrz.TU-Berlin.DE!cs.tu-berlin.de!hoppet
- From: hoppet@opal.cs.tu-berlin.de (Thomas Hoppe)
- Subject: Looking for code to index clauses or n-ary trees
- Message-ID: <1992Dec18.233312.12891@cs.tu-berlin.de>
- Keywords: Indexing, predicate symbols, clauses, n-ary trees, Quintus indexer
- Sender: news@cs.tu-berlin.de
- Organization: Techn. University of Berlin, Germany
- Date: Fri, 18 Dec 1992 23:33:12 GMT
- Lines: 53
-
- Dear 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: hoppet@cs.tu-berlin.de
- Technische Universitaet Berlin phone: 030-314-25494
- Franklinstr. 28/29 fax : 030-314-24929
- 1000 Berlin 10 Germany priv.: 030-3236564
-