We can optionally leave out either the relation name or the list of attributes. For example, the following expression is correct and results in a relation named books with attributes book_id, author_id, title, and publication_year:
\[\rho_ <\text<(year>\rightarrow \text3.2.2. Cross products and joins¶
We now turn our attention to operations which extend tuples in one relation with tuples from another relation. For this section, we will be using books and a second relation, authors:
authors ¶N. Scott Momaday
Ursula K. Le Guin
The authors relation has a primary key of author_id. The books relation is related to authors via a foreign key on author_id.
3.2.2.1. Cross product¶
The cross product (or Cartesian product) of two relations A and B is a new relation containing all tuples that can be created by concatenating some tuple from B onto some tuple from A [ 1 ] . Here we are using the definition of tuple as an ordered list of values. The attributes of the new relation are normally the attributes of A and B concatenated. However, if there is a name collision, e.g., if both A and B have some attribute x, we will disambiguate the attributes in the new relation by prepending the relation names, that is, the cross product will have attributes A.x and B.x; we can avoid having to do this if we first apply renaming to one relation or the other.
The cross product operator is denoted \(\times\) , and is written between its two operands. To start, consider two rather abstract relations S and T:
S ¶ T ¶We write the cross product of S and T as:
\[\textwhich gives us the relation containing every pairing of a tuple from S with every tuple from T:
From the definition, it is trivial to determine that the size of the cross product is the product of the sizes of the operands.
3.2.2.2. Join¶
The cross product is a fundamental operation in relational algebra, but not a generally useful one when we consider actual data. Consider the cross product of books and authors:
\[\textThe full set of tuples in this relation is large (the number of books multiplied by the number of authors), so we only show a subset below:
The House of the Spirits
The House of the Spirits
The House of the Spirits
The author of The House of the Spirits is Isabel Allende. What meaning, then, can we make of a tuple that pairs The House of the Spirits with the author Ralph Ellison (the author of Invisible Man)?
We are typically interested in pairing only certain tuples of a relation with certain tuples of another. In the above example, we are interested in tuples where the author_id attribute from books agrees with the author_id attribute from authors. This relationship is indicated not only by the names we have used for attributes, but also by the foreign key constraint on books and authors. To retain only the tuples with matching author_id values, we can apply a selection operation to the result of our cross product:
\[\sigma_=\text>(\text \times \text)\]This yields a useful result:The House of the Spirits
The Fellowship of the Ring
House Made of Dawn
N. Scott Momaday
A Wizard of Earthsea
Ursula K. Le Guin
Since this pattern of applying a selection after a cross product is so common, we have an operator that combines the two into an operation known as a join [ 2 ] . Using the join operator, the above expression becomes:
\[\textor, you can instead format the expression as:
\[\textNote that one tuple from authors does not contribute to the join. This tuple’s author_id matches none of the tuples in books, and thus no combined tuple using it can appear in the join result. We call this tuple a dangling tuple. Dangling tuples may be an indication of a problem in the data; in this example, it may suggest that we are missing information about books by one author.
3.2.2.3. Theta-join and equijoin¶
While an equality condition is typically used in joins, more generally any condition of the following form can be used:
\[\textwhere A.x is an attribute from one relation, B.y is an attribute from the other relation, and \(\Theta\) is a comparison operator (such as =, theta condition, and a join using such a condition or a conjunction (AND) of such conditions is known as a theta-join.
A theta-join using only equality comparisons (as in our example above) is further known as an equijoin.
This terminology is not especially important in understanding the algebra, but is something you may encounter if you intend a deeper study of relational algebra.
3.2.2.4. Natural join¶
When we join books with authors we run into the issue that both relations contain an attribute named author_id. Since a relation cannot have more than one attribute with the same name, joining (or taking a cross product of) these two relations requires us to rename the attributes in some fashion. This can be done either by an explicit renaming operation prior to joining or by prepending the original relation name (as we did in our example). Because our join condition was equality on the author_id attributes, both the books.author_id and authors.author_id in the resulting relation always agree. This unnecessary redundancy can be removed using projection and renaming.
In this special situation in which we wish to join specifically by equating the attributes with the same names in both relations - subsequently removing the “duplicate” attributes - we can instead do a natural join. We can indicate a natural join using the join operator with no conditions [ 3 ] :
\[\textwhich yields the simplified relation:
The House of the Spirits
The Fellowship of the Ring
House Made of Dawn
N. Scott Momaday
A Wizard of Earthsea
Ursula K. Le Guin
3.2.3. Set operations¶
Unsurprisingly, given that relations are sets, relational algebra includes the usual set operations - union, intersection, and set difference - with some restrictions. These binary operations are denoted by:
- \(\cup\) : union
- \(\cap\) : intersection
- \(-\) : set difference
For example, let A and B be the relations below:
A ¶ B ¶ \(\text - \text\) ¶Note that union and intersection are commutative, but set difference is not.
The important restriction on set operations in relational algebra is that the relations must be compatible in terms of their schemas. The meaning of “compatible” varies, but for our purposes, assume we view the tuples in a relation as ordered lists, where each position in the list is associated with a particular attribute and type domain. Then, if we have two relations, we require that, for a given position in the tuples in either relation, the attribute and type domain are the same. For A and B shown above, we might assert that the first position corresponds to attribute x and contains character strings, while the second position (y) contains integers.
A looser requirement allows attribute names (but not type domains) to differ between relations. This requirement aligns less closely with the second definition of tuple given in the previous chapter, but it eliminates the occasional need for renaming operations prior to applying set operations. If the attribute names do not match in the two relations, we adopt the attribute names from the left-hand operand for the result relation.
While intersection is a useful operation, it is not strictly needed for the algebra, as the same result can be obtained using set difference:
3.2.4. Division¶
The operations described above are sufficient for most query needs. However, one other binary operation, division, is typically included in the basic relational algebra. To divide a relation P by another relation R, we write:
Division is the most difficult operation to describe; in a very loose sense it acts as a kind of inverse to a cross product. That is, if P, Q, and R are relations and
\[\text= \text \times \text\]
then it is true that
\[\text\div \text = \text\]
However, the reverse is not necessarily true. Rather, let P be some relation, with attributes x and y [ 4 ] . We require that R has attribute y. Then \(\text \div \text\) will contain the values of x which are paired (in P) with every value of y listed in R.
We will start with an abstract example. Let P be the relation pictured below:
