Dependent and Independent Operations

Dependent and Independent Operations

Some of the operations that we have explained in previous sections can be expressed in terms of other relational-algebra operations. For instance, intersection can be expressed in terms of set difference:



That is, if R and S are any two relations with the same schema, the intersection of R and S can be computed by first subtracting S from R to form a relation T consisting of all those tuples in R but not S. We then subtract T from R, leaving only those tuples of R that are also in S.

The two forms of join are also expressible in terms of other operations. Theta-join can be expressed by product and selection:


The natural join of R and S can be expressed by starting with the product R x S. We then apply the selection operator with a condition C of the form



Where A1, A2, . . . ,An are all the attributes appearing in the schemas of both R and S. Finally, we must project out one copy of each of the equated attributes. Let L be the list of attributes in the schema of R followed by those attributes in the schema of S that are not also in the schema of R. Then


Example (a) : The natural join of the relations U and V from "Natural Joins / Theta-Joins" Figure (b) can be written in terms of product, selection, and projection as:



That is we take the product U x V. Then we select for equality between each pair of attributes with the same name - B and C in this example. Eventually, we project onto all the attributes except one of the B's and one of the C's: we have chosen to eliminate the attributes of V whose names also appear in the schema of U.

For another example, the theta-join of "Natural Joins / Theta-Joins" Example (d) can be written



That is, we take the product of the relations U and V and then apply the condition that appeared in the theta-join.

The rewriting rules mentioned in this section are the only "redundancies" among the operations that we have introduced. The six remaining operations -
union, difference, selection, projection, product, and renaming - form an independent set, none of which can be written in terms of the other five.


Tags