A query tree is a tree in which each node of the tree contains an operator, and the number of children of the node is exactly the arity of this operator. Leaves are nodes containing operators of arity zero.
Query trees are used to specify the order in which operators are to be applied. Each input of an operator will always be the output of some other operator. Paraphrasing page 504 of Elmasri and Navathe [Elmasri 94], in their description of a query tree, (substituting Cascades terminology):
A query tree is a tree structure that corresponds to a query by having zero input operators (e.g. GET) as leaf nodes of the tree (representing the access of a stored relation) and arity one or more operators as internal nodes. An evaluation of the query tree consists of evaluating an internal node operation whenever its operands are available and the replacing that internal node by the table that results from evaluating the operation. The evaluation terminates when the root node is evaluated and replaced by the table that is the result of the query.
Query trees are used in many ways in Cascades. First, they are used for the input and output of a Cascades Optimizer.6 Also, a special form of query tree is used as the antecedent and consequent patterns in the specification of transformation rules. Note that query trees are sometimes referred to as operator trees [Kabra 95] or expression trees [Graefe 95]. Since only logical operators have been introduced, our first examples will be logical query trees -- query trees that contain only logical operators.
6. The initial SQL query is parsed into the initial query tree -- sometimes called the parse tree. In the rest of the thesis, the term initial query refers to the initial query tree.
| 
Page 5
|