Multivariable ExpressionsStrategies for evaluating multivariable expressions are the most important building blocks of a general query processing system. There are two basic approaches, called parallel processing and stepwise reduction. Parallel processing of query components helps avoid repeated access to the same data. Repeated access to the same data can be avoided by evaluating multiple query components simultaneously. In Palermo [1972], all monadic terms associated with a variable are completely evaluated and all dyadic terms in which the same variable appears are partially processed simultaneously with the analysis of the variable's extent relationship. Even the AND connections existing between terms can be evaluated in parallel, which further reduces the size of intermediate results [Jarke and Schmidt 1982]. A similar approach at a higher level was described by Klug [1982b] in which aggregate functions and complex subqueries are computed in parallel. Scheduling strategies for parallel processing of query components are discussed by Schmidt [1979]. Pipeline operations that can operate on the partial output of previous operations are another technique that exploits parallel processing opportunities [Smith and Chang 1975; Yao 1979]. For example, restriction and projection can be channeled such that only a relatively small buffer for data exchange is required rather than the creation and subsequent reading of a possibly large temporary relationship. Aspects of simultaneous evaluation and pipeline are combined in the so-called “feedback” method [Clausen 1980; Rothnie 1974, 1975], which uses the partial results of a join operation to restrict its input. The degree to which this can be done depends on ...... middle of paper ...... th semi-joins which achieve very strong reduction [Chiu and Ho 1980; Chiu et al. 1981].Strategies for evaluating tree expressions containing both existential and universal quantifiers must take into account the order in which these quantifiers appear in the expression. Stepwise reduction is only possible when the processing of the edges of the query tree (width from first leaf to root) matches the order of quantifiers in the expression (right to left). like those presented in this section, are candidates for hardware components of specialized database machines. However, such components often allow parallelism and therefore require somewhat different join and semi-join algorithms [Bitton et al. 1983; Maekawa 1982; Missikoff and Scholl 1983; Valduriez 1982; Valduriez and Gardarin 1984].