Algebraic Optimization of Recursive Database Queries

Publication: Research - peer-reviewJournal article – Annual report year: 1988

Standard

Algebraic Optimization of Recursive Database Queries. / Hansen, Michael Reichhardt.

In: I N F O R Journal, Vol. 26, No. 4, 1988, p. 286-298.

Publication: Research - peer-reviewJournal article – Annual report year: 1988

Harvard

APA

CBE

MLA

Vancouver

Author

Hansen, Michael Reichhardt / Algebraic Optimization of Recursive Database Queries.

In: I N F O R Journal, Vol. 26, No. 4, 1988, p. 286-298.

Publication: Research - peer-reviewJournal article – Annual report year: 1988

Bibtex

@article{b2ee95ee97fe414caa5bed182e1c1d4a,
title = "Algebraic Optimization of Recursive Database Queries",
publisher = "University of Toronto Press Journals Division",
author = "Hansen, {Michael Reichhardt}",
year = "1988",
volume = "26",
number = "4",
pages = "286--298",
journal = "I N F O R Journal",
issn = "0315-5986",

}

RIS

TY - JOUR

T1 - Algebraic Optimization of Recursive Database Queries

A1 - Hansen,Michael Reichhardt

AU - Hansen,Michael Reichhardt

PB - University of Toronto Press Journals Division

PY - 1988

Y1 - 1988

N2 - Queries are expressed by relational algebra expressions including a fixpoint operation. A condition is presented under which a natural join commutes with a fixpoint operation. This condition is a simple check of attribute sets of sub-expressions of the query. The work may be considered a generalization of Aho and Ullman, (1979). The result is interpreted in function free logic database terms as a transformation of the recursively defined predicate involving: (a) elimination of an argument, and (b) propagation of selections (instantiations) to the extensionally defined predicates. A collection of examples shows that this transformation abstracts some optimizations which otherwise are done by more complex graph algorithms (e.g. Bancilhon et al., (1986); Chang, (1985); Gardarin and DeMaindreville, (1986); Henschen and Naqvi, (1984); Kifer and Lozinskii, (1986)). Thus, this optimization is expressed in a form which is not biased towards any evaluation method

AB - Queries are expressed by relational algebra expressions including a fixpoint operation. A condition is presented under which a natural join commutes with a fixpoint operation. This condition is a simple check of attribute sets of sub-expressions of the query. The work may be considered a generalization of Aho and Ullman, (1979). The result is interpreted in function free logic database terms as a transformation of the recursively defined predicate involving: (a) elimination of an argument, and (b) propagation of selections (instantiations) to the extensionally defined predicates. A collection of examples shows that this transformation abstracts some optimizations which otherwise are done by more complex graph algorithms (e.g. Bancilhon et al., (1986); Chang, (1985); Gardarin and DeMaindreville, (1986); Henschen and Naqvi, (1984); Kifer and Lozinskii, (1986)). Thus, this optimization is expressed in a form which is not biased towards any evaluation method

UR - http://www2.imm.dtu.dk/pubdb/p.php?1897

JO - I N F O R Journal

JF - I N F O R Journal

SN - 0315-5986

IS - 4

VL - 26

SP - 286

EP - 298

ER -