Prolog - Survey of indexing features for dynamic clauses

Author

Survey of indexing features for dynamic clauses

Chip Eastham

2007-08-28, 7:11 pm

In a recent thread Jan mentioned creating a table and indexing it
(as a pragmatic alternative to managing distinct solutions in lists
via findall, bagof, setof, etc.).

I'm wondering if someone has written (or read) a survey of how
various Prolog implementations support indexing of dynamic
clauses or surrogate data structures.

I'm using "indexing" in a broad database table-like sense, as
a feature that speeds up selection of a matching fact (or the
determination that no matching fact is available).

regards, chip

Mats

2007-08-29, 8:06 am

On Aug 28, 11:00 pm, Chip Eastham <hardm...@gmail.com> wrote:
> In a recent thread Jan mentioned creating a table and indexing it
> (as a pragmatic alternative to managing distinct solutions in lists
> via findall, bagof, setof, etc.).
>
> I'm wondering if someone has written (or read) a survey of how
> various Prolog implementations support indexing of dynamic
> clauses or surrogate data structures.
>
> I'm using "indexing" in a broad database table-like sense, as
> a feature that speeds up selection of a matching fact (or the
> determination that no matching fact is available).
>
> regards, chip

See also the following reference. --Mats

@inproceedings{DBLP:conf/iclp/LindholmO87,
author = {Timothy G. Lindholm and
Richard A. O'Keefe},
title = {Efficient Implementation of a Defensible Semantics for
Dynamic
PROLOG Code.},
booktitle = {ICLP},
year = {1987},
pages = {21-39},
bibsource = {DBLP, http://dblp.uni-trier.de}
}

bart demoen

2007-08-29, 7:06 pm

On Tue, 28 Aug 2007 22:00:32 +0000, Chip Eastham wrote:

> I'm wondering if someone has written (or read) a survey of how
> various Prolog implementations support indexing of dynamic
> clauses or surrogate data structures.

I don't think there is a survey and if there is one, I would be
very interested in seeing it: please submit it to TPLP. Anyone considering
to write one would have to look at actual implementations of course, and
additionally to the following [sorry for bibtex - it was the quickest I
could do]

@inproceedings{DBLP:conf/slp/WiseP84,
author = {Michael J. Wise and
David M. W. Powers},
title = {Indexing Prolog Clauses via Superimposed Code Words and
Filed Encoded Words.},
booktitle = {SLP},
year = {1984},
pages = {203-210},
bibsource = {DBLP, http://dblp.uni-trier.de}
}

@INPROCEEDINGS { demandindex,
AUTHOR = "Santos Costa, Vitor and Sagonas, Kostantinos and Lopes, Ricardo",
YEAR = {2007 - to be published ICLP'07},
TITLE = "{Demand-driven Indexing of Prolog Clauses}"

@INPROCEEDINGS { dynamicindexing,
AUTHOR = "Demoen, Bart and Mari{\"{e}}n, A and Callebaut, Alain",
YEAR = {1989},
MONTH = oct,
TITLE = {{I}ndexing in {P}rolog},
BOOKTITLE = {Proceedings of NACLP'89 (North American Conference on Logic Programming, Cleveland, Ohio)},
PAGES = {1001--1012},
}

@inproceedings{DRR95,
Author={S. Dawson and C. R. Ramakrishnan and I. V. Ramakrishnan},
Title={Design and Implementation of Jump Tables for Fast Indexing of Logic Programs},
BOOKTITLE = "Proc. of PLILP 95",
YEAR = 1995 }

@INPROCEEDINGS { kligershapiro@naclp90,
author = "Kliger, Shmuel and Shapiro, Ehud",
title = "{From decision trees to decision graphs}",
EDITOR = "Debray, Saumya K. and Hermenegildo, Manuel V.",
BOOKTITLE = {Proceedings of North American Conference on Logic Programming}\
,
SERIES = {MIT Press},
Pages = {97-116},
year = {1990}
}

@inproceedings{ CRR92,
AUTHOR = "T. Chen and I. V. Ramakrishnan and R. Ramesh",
TITLE = "Multistage Indexing Algorithms for Speeding {P}rolog
Execution",
BOOKTITLE = "Proc. of the International
Conference and Symposium on Logic Programming",
PAGES = "639-653",
YEAR = 1992 }

The reference that Mats gave is not so useful regarding indexing, although
in the context of Prolog - and given that ISO requires the so-called
"logical" (as if) database update view, it is relevant, because it imposes
a quite hefty pain on implementors [ISO I mean, not the referenced paper].

Be sure to include all relevant XSB work: it isn't covered thoroughly in
my references above.

Cheers

Bart Demoen

J. Burse

2007-08-29, 7:06 pm

Chip Eastham schrieb:
> In a recent thread Jan mentioned creating a table and indexing it
> (as a pragmatic alternative to managing distinct solutions in lists
> via findall, bagof, setof, etc.).
>
> I'm wondering if someone has written (or read) a survey of how
> various Prolog implementations support indexing of dynamic
> clauses or surrogate data structures.
>
> I'm using "indexing" in a broad database table-like sense, as
> a feature that speeds up selection of a matching fact (or the
> determination that no matching fact is available).
>
> regards, chip
>
Hi

Anybody knows about lessons learned for prolog
indexing from RETE algorithms?

Bye

bart demoen

2007-08-29, 7:06 pm

On Wed, 29 Aug 2007 21:32:42 +0200, J. Burse wrote:

> Anybody knows about lessons learned for prolog
> indexing from RETE algorithms?

My first guess is that nothing can be learned from RETE in the strict
Prolog indexing context. But I will try to make my students answer this:
they know more about RETE, less about Prolog, and don't always read
comp.lang.prolog

Cheers

Bart Demoen

Neng-Fa Zhou

2007-08-30, 8:09 pm

"J. Burse" <janburse@fastmail.fm> wrote in message
news:46D5BBCA.8090205@fastmail.fm...
> Anybody knows about lessons learned for prolog
> indexing from RETE algorithms?

More than 15 years ago, inspired by the RETE algorithm I came up with an
indexing scheme called matching trees. This scheme has been in B-Prolog for
many years for compiling static clauses. To assist the compiler in building
multi-level matching trees the user is required to either give mode
declarations or write programs in matching clauses which are very similar to
clauses in committed-choice languages.

Cheers,
Neng-Fa

J. Burse

2007-08-30, 8:09 pm

Neng-Fa Zhou schrieb:
> "J. Burse" <janburse@fastmail.fm> wrote in message
> news:46D5BBCA.8090205@fastmail.fm...
>
> More than 15 years ago, inspired by the RETE algorithm I came up with an
> indexing scheme called matching trees. This scheme has been in B-Prolog for
> many years for compiling static clauses. To assist the compiler in building
> multi-level matching trees the user is required to either give mode
> declarations or write programs in matching clauses which are very similar to
> clauses in committed-choice languages.
>
> Cheers,
> Neng-Fa
>
>
http://www.sci.brooklyn.cuny.edu/~zhou/
I book marked you.

bart demoen

2007-08-30, 8:09 pm

On Thu, 30 Aug 2007 11:39:03 -0400, Neng-Fa Zhou wrote:

> More than 15 years ago, inspired by the RETE algorithm I came up with an
> indexing scheme called matching trees. This scheme has been in B-Prolog for
> many years for compiling static clauses. To assist the compiler in building
> multi-level matching trees the user is required to either give mode
> declarations or write programs in matching clauses which are very similar to
> clauses in committed-choice languages.

I would like to understand this better. RETE is about two things (as
far as I know and understand it). The indexing part (which I thought was
run-off-the-mill database style lookup, possibly enhanced with things also
known in the Prolog context - see the references I posted earlier - for
multiple or structured arguments) and the part which keeps incrementally
the join of a subset of heads of rules in a production rule.

The joining part does not really transpose to Prolog execution, unless one
is prepared to treat conjunctions of Prolog goals in a new way. As far as
I know, B-Prolog (or any other Prolog system) doesn't do that.

If by chance one comes across the ideas in RETE indexing BEFORE one learns
about database indexing (+ the aforementioned enhancements for Prolog) one
could think that RETE has something to add to Prolog indexing. But I
learned it chronologically the other way around, and that's why I thought
that RETE has nothing to add to Prolog indexing.

Perhaps I always missed something essential here and I would like to
learn what exactly, now that I am not yet too old :-)

I would also like to understand the relation with Mercury better: Mercury
requires mode declarations (or must be able to derive them), and for input
arguments does matching (without changing the semantics, because proven at
compile time). To what extend are Mercury input unification, matching
trees in B-Prolog, RETE interrelated ?

I really thought I understood all this, but the recent posts make me doubt
I do.

Cheers

Bart Demoen

Sponsored Links