## Algebraic Optimization of Recursive Database Queries

Publication: Research - peer-review › Journal article – Annual report year: 1988

### Standard

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

Publication: Research - peer-review › Journal article – Annual report year: 1988

### Harvard

*I N F O R Journal*, vol 26, no. 4, pp. 286-298.

### APA

*I N F O R Journal*,

*26*(4), 286-298.

### CBE

### MLA

*I N F O R Journal*. 1988, 26(4). 286-298.

### Vancouver

### Author

### Bibtex

}

### RIS

TY - JOUR

T1 - Algebraic Optimization of Recursive Database Queries

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

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 -