Meta-programming for reordering literals in deductive databases

Jesper Larsson Träff; Steven David Prestwich

doi:10.1007/3-540-56282-6_19

Meta-programming for reordering literals in deductive databases

Jesper Larsson Träff
, Steven David Prestwich

ECRC - European Computer-Industry Research Centre

Research output: Chapter in Book/Report/Conference proceedings › Chapter › peer-review

Abstract

Specifying efficient evaluation strategies by meta-interpreters, and then eliminating the interpretation overhead by partial evaluation with respect to given object programs, is an elegant technique for the transformation of logic programs. In this paper we show how to apply this technique to the compilation of instantiation based evaluation strategies for DATALOG with negation, and hence to query optimization in deductive databases. We demonstrate our approach on two well-known optimizations, dealing with the passing of information :between literals (sideways information passing strategies or SIPS), and the early evaluation of constraining literals (the C-transformation).

Original language	English
Title of host publication	Meta-Programming in Logic - 3rd International Workshop, META-1992, Proceedings
Editors	Alberto Pettorossi
Publisher	Springer Verlag
Pages	280-293
Number of pages	14
ISBN (Print)	9783540562825
DOIs	https://doi.org/10.1007/3-540-56282-6_19
Publication status	Published - 1992
Externally published	Yes
Event	3rd International Workshop on Meta-Programming in Logic, META 1992 - Uppsala, Sweden Duration: 10 Jun 1992 → 12 Jun 1992

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	649 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	3rd International Workshop on Meta-Programming in Logic, META 1992
Country/Territory	Sweden
City	Uppsala
Period	10/06/92 → 12/06/92

Access to Document

10.1007/3-540-56282-6_19

Cite this

Träff, J. L., & Prestwich, S. D. (1992). Meta-programming for reordering literals in deductive databases. In A. Pettorossi (Ed.), Meta-Programming in Logic - 3rd International Workshop, META-1992, Proceedings (pp. 280-293). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 649 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-56282-6_19

Träff, Jesper Larsson ; Prestwich, Steven David. / Meta-programming for reordering literals in deductive databases. Meta-Programming in Logic - 3rd International Workshop, META-1992, Proceedings. editor / Alberto Pettorossi. Springer Verlag, 1992. pp. 280-293 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{d832782ea7504f0db2fa38ad121fc7e9,

title = "Meta-programming for reordering literals in deductive databases",

abstract = "Specifying efficient evaluation strategies by meta-interpreters, and then eliminating the interpretation overhead by partial evaluation with respect to given object programs, is an elegant technique for the transformation of logic programs. In this paper we show how to apply this technique to the compilation of instantiation based evaluation strategies for DATALOG with negation, and hence to query optimization in deductive databases. We demonstrate our approach on two well-known optimizations, dealing with the passing of information :between literals (sideways information passing strategies or SIPS), and the early evaluation of constraining literals (the C-transformation).",

author = "Tr{\"a}ff, \{Jesper Larsson\} and Prestwich, \{Steven David\}",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1992.; 3rd International Workshop on Meta-Programming in Logic, META 1992 ; Conference date: 10-06-1992 Through 12-06-1992",

year = "1992",

doi = "10.1007/3-540-56282-6\_19",

language = "English",

isbn = "9783540562825",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "280--293",

editor = "Alberto Pettorossi",

booktitle = "Meta-Programming in Logic - 3rd International Workshop, META-1992, Proceedings",

address = "Germany",

}

Träff, JL & Prestwich, SD 1992, Meta-programming for reordering literals in deductive databases. in A Pettorossi (ed.), Meta-Programming in Logic - 3rd International Workshop, META-1992, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 649 LNCS, Springer Verlag, pp. 280-293, 3rd International Workshop on Meta-Programming in Logic, META 1992, Uppsala, Sweden, 10/06/92. https://doi.org/10.1007/3-540-56282-6_19

Meta-programming for reordering literals in deductive databases. / Träff, Jesper Larsson; Prestwich, Steven David.
Meta-Programming in Logic - 3rd International Workshop, META-1992, Proceedings. ed. / Alberto Pettorossi. Springer Verlag, 1992. p. 280-293 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 649 LNCS).

Research output: Chapter in Book/Report/Conference proceedings › Chapter › peer-review

TY - CHAP

T1 - Meta-programming for reordering literals in deductive databases

AU - Träff, Jesper Larsson

AU - Prestwich, Steven David

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1992.

PY - 1992

Y1 - 1992

N2 - Specifying efficient evaluation strategies by meta-interpreters, and then eliminating the interpretation overhead by partial evaluation with respect to given object programs, is an elegant technique for the transformation of logic programs. In this paper we show how to apply this technique to the compilation of instantiation based evaluation strategies for DATALOG with negation, and hence to query optimization in deductive databases. We demonstrate our approach on two well-known optimizations, dealing with the passing of information :between literals (sideways information passing strategies or SIPS), and the early evaluation of constraining literals (the C-transformation).

AB - Specifying efficient evaluation strategies by meta-interpreters, and then eliminating the interpretation overhead by partial evaluation with respect to given object programs, is an elegant technique for the transformation of logic programs. In this paper we show how to apply this technique to the compilation of instantiation based evaluation strategies for DATALOG with negation, and hence to query optimization in deductive databases. We demonstrate our approach on two well-known optimizations, dealing with the passing of information :between literals (sideways information passing strategies or SIPS), and the early evaluation of constraining literals (the C-transformation).

UR - https://www.scopus.com/pages/publications/84916515823

U2 - 10.1007/3-540-56282-6_19

DO - 10.1007/3-540-56282-6_19

M3 - Chapter

AN - SCOPUS:84916515823

SN - 9783540562825

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 280

EP - 293

BT - Meta-Programming in Logic - 3rd International Workshop, META-1992, Proceedings

A2 - Pettorossi, Alberto

PB - Springer Verlag

T2 - 3rd International Workshop on Meta-Programming in Logic, META 1992

Y2 - 10 June 1992 through 12 June 1992

ER -

Träff JL, Prestwich SD. Meta-programming for reordering literals in deductive databases. In Pettorossi A, editor, Meta-Programming in Logic - 3rd International Workshop, META-1992, Proceedings. Springer Verlag. 1992. p. 280-293. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-56282-6_19

Meta-programming for reordering literals in deductive databases

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this