Re: Survey of indexing features for dynamic clauses

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

.

Relevant Pages

  • Re: [Feature Request] "first:" "last:" sections in a "foreach" block
    ... implementations don't lend themselves well to indexing (anything which using ... No. Needing to treat the first or last item differently is fairly common. ... If you see an advantage in having it in the language, ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Survey of indexing features for dynamic clauses
    ... indexing scheme called matching trees. ... The joining part does not really transpose to Prolog execution, ... If by chance one comes across the ideas in RETE indexing BEFORE one learns ...
    (comp.lang.prolog)
  • Re: indexing
    ... If a Prolog implementation recognizes property X, ... multiple argument indexing, ...
    (comp.lang.prolog)
  • Re: indexing
    ... >> This shows one of the biggest scandals in Prolog ... >> multiple argument indexing has been around since about two ...
    (comp.lang.prolog)
  • Re: The way to append number after the name of a variable ?
    ... Var_1,Var_2,...Var_N, thus if we can find a way to append ... the indexing numbers to the "Var_", then ... Prolog for 15 years ... ... Yes (0.04s cpu) ...
    (comp.lang.prolog)