Journal article
Algebraic Optimization of Recursive Database Queries
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
Language: | English |
---|---|
Year: | 1988 |
Pages: | 286-298 |
ISSN: | 19160615 and 03155986 |
Types: | Journal article |
DOI: | 10.1080/03155986.1988.11732071 |
ORCIDs: | Hansen, Michael Reichhardt |