Multivariable Expressions Strategies for evaluating multivariable expressions are the largest building blocks for a general query processing system. There are two basic approaches, called parallel processing and gradual reduction. Parallel processing of query components serves to 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 fully evaluated, and all dyadic terms in which the same variable appears are partially processed at the same time as the variable's interval relation is scanned. Existing AND connections between terms can also be evaluated in parallel, which further reduces the size of the 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 work on the partial output of previous operations are another technique that takes advantage of parallel processing opportunities [Smith and Chang 1975; Yao 1979]. For example, restriction and projection can be implemented such that only a relatively small buffer is required for data exchange rather than the creation and subsequent reading of a possibly large temporary relation. Aspects of simultaneous evaluation and pipeline are combined in the so-called "feedback" method [Clausen 1980; Rothnie 1974, 1975], which uses partial results of a merge operation to limit its input. The degree to which this can be done depends on...... half-sheet ......th semijoins 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. Gradual reduction is possible only when the processing of the edges of the query tree (first leaf-root) matches the order of the quantifiers in the expression (right to left). Methods for efficiently implementing operations, such as those presented in this section, are candidates for hardware components in specialized database machines. However, such components often allow parallelism and therefore require slightly different join and semijoin algorithms [Bitton et al. 1983; Maekawa 1982; Missikoff and Scholl 1983; Valduriez 1982; Valduriez and Gardarin 1984].