A Linear Notation for Algebraic Expressions

A Linear Notation for Algebraic Expressions

In "Combining Operations to Form Queries" we used trees to represent complicated expressions of relational algebra. Another option is to invent names for the temporary relations that correspond to the interior nodes of the tree and write a sequence of assignments that create a value for each. The order of the assignments is flexible, as long as the children of a node N have had their values created before we try to create the value for N itself.

The notation we shall use for assignment statements is:

1.  A relation name and parenthesized list of attributes for that relation. The name Answer will be used conventionally for the result of the final step: i.e.; the name of the relation at the root of the expression tree.

2.  The assignment symbol : =.

3.  Any algebraic expression on the right. We can choose to use only one operator per assignment, in which case each interior node of the tree gets its own assignment statement. On the other hand, it is also allowable to merge many algebraic operations in one right side, if it is convenient to do so.

Example (a): Look at the tree of "Combining Operations to Form Queries" Figure (a). One possible sequence of assignments to appraise this expression is:

The first step calculates the relation of the interior node labeled  in "Combining Operations to Form Queries" Figure (a), and the second step calculates the node labeled . Notice that we get renaming "for free", since we can use any attributes and relation name we wish for the left side of an assignment. The last two steps calculate the intersection and the projection in the obvious way.

It is also allowable to merge some of the steps. For example, we could merge the last two steps and write: