Algebraic Optimization of Recursive Database Queries
Publication: Research - peer-review › Journal article – Annual report year: 1988
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
| Original language | English |
|---|---|
| Journal | I N F O R Journal |
| Publication date | 1988 |
| Volume | 26 |
| Journal number | 4 |
| Pages | 286-298 |
| ISSN | 0315-5986 |
| State | Published |
ID: 2700918