Algebraic Optimization of Recursive Database Queries

    Research output: Contribution to journalJournal articleResearchpeer-review


    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 languageEnglish
    JournalI N F O R Journal
    Issue number4
    Pages (from-to)286-298
    Publication statusPublished - 1988

    Fingerprint Dive into the research topics of 'Algebraic Optimization of Recursive Database Queries'. Together they form a unique fingerprint.

    Cite this