Renaming refers simply to changing the name of an attribute of a table. If a table T has an attribute named A, we will denote the table resulting from the operation of renaming A to B by:

ren _A → _B(T)

For Table 5-5:

the result of performing:

ren _ISBN →BookID, Price→Cost(BOOKS)

is shown in Table 5-6.

If S and T are tables with the same attributes, then we may form the union S ∪ T, which is just the table obtained by including all of the rows from both S and T. Here is an example.

Note that if S and T do not have the same attributes, but do have the same degree —that is, the same number of columns—then we can first rename the attributes of one table to match the other and then take their union. Of course, this will not always make sense, since it may result in combining attribute values from different domains into one column.

Let us consider an example of how to take a union in Microsoft Access. Unions can be formed in one of two ways in Microsoft Access. The first is straightforward:

Another way to create a union is to use an Append Query as follows:

The intersection S∩ T of two tables S and T with the same attributes is the table formed by keeping only those rows that appear in both tables. Here is an example:

We will see an example of how to form an intersection in Microsoft Access when we discuss differences, in the next section.

The difference S - T of two tables S and T with the same attributes is the table consisting of all rows of S that do not appear in T, as shown in the following tables:

Let us consider an example of how to take an intersection or difference in Microsoft Access.

To define the Cartesian product of tables, we need to adjust the way we write attribute names, just in case both tables have an attribute of the same name. If a table T has an attribute named A, the fully qualified attribute name (or just qualified attribute name ) is T.A. Thus, we may write BOOKS.ISBN or AUTHORS.AuID.

If S(A₁,...,A_n) and T(B₁,...,B_m) are tables, then the Cartesian product S x T of S and T is the table whose attribute set contains the fully qualified attribute names of all attributes from S and T:

The rows of S x T are formed by combining each row s of S with each rowtof T, to form a new rowst. An example will help make this clear:

Notice that if S has k rows and T has j rows, then the Cartesian product has kj rows. Hence, the Cartesian product of two tables can be very large.

To form a Cartesian product of two tables in Microsoft Access, proceed as follows:

Projection is a very simple concept. Intuitively, a projection of a table onto a subset of its attributes (columns) is the table formed by throwing away all other columns.

More formally, let T(A₁,...A_n) be a table, where A = {A₁,...,A_n} is the attribute set. If B is a subset of A, then the projection of T onto B is just the table obtained from T by keeping only those columns headed by the attribute names in B. We denote this table by proj _B (T).

As an example, for the table:

the projection proj _ISBN,Price(BOOKS) is:

Note that, if the projection produces two identical rows, the duplicate rows must be removed, since a table is not allowed to have duplicate rows. (This rule of relational databases is not enforced by all commercial database products. In particular, it is not enforced by Microsoft Access. That is, some products allow identical rows in a table. By definition, these products are not true relational databases—but that is not necessarily a flaw.)

The Query Design window in Microsoft Access was tailor-made for creating projections. Just add the table to the design window, and drag the desired attribute names to the design grid. Run the query to get the projection. Figure 5-9 shows the Query Design window for computing the projection of Books onto the attributes ISBN and Price.

Figure 5-9. Creating a projection using the BOOKS table

Just as the operation of projection selects only a subset of the columns of a table, so the operation of selection selects a subset of the rows of a table. The first step in defining the operation of selection is to define a selection condition or selection criterion to be any legally formed expression that involves:

For example, the following are selection conditions:

If condition is a selection condition, then the result table obtained by applying the corresponding selection operation to a table T is denoted by:

sel _condition(T)

or sometimes by:

T where condition

and is the table obtained from T by keeping only those rows that satisfy the selection condition.

For example, see Table 5-7.

The table sel_Price $25.00(BOOKS) is shown in Table 5-8:

Some authors refer to selection as restriction, which does seem to be a more appropriate term and has the advantage that it is not confused with the SQL SELECT statement, which is much more general than just selection. However, it is less common than the term selection, so we will use this term.

The Query Design window in Microsoft Access was also tailor-made for creating selections. We just use the Criteria rows to apply the desired restrictions. For example, Figure 5-10 shows the design window for the selection:

sel_Price $25.00(BOOKS)

from the previous example.

Figure 5-10. Creating a selection in the Query Design window

You will probably agree that the operations we have covered so far are pretty straightforward—union, intersection, difference, and Cartesian product are basic set-theoretic operations. Selecting rows and columns are clearly valuable table operations.

Actually, the six operations of renaming, union, difference, Cartesian product, projection, and selection are enough to form the complete relational algebra by combining these operations with constants and attribute names to create relational-algebra expressions.

However, it is very convenient to define some additional operations on tables, even though they can theoretically be expressed in terms of the six operations previously mentioned. So let us proceed.

The various types of joins are among the most important and useful of the relational-algebra operations. Loosely speaking, joining two tables involves combining the rows of two tables based on comparing the values in selected columns.

Equi-join

In an equi-join, rows are combined if there are equal attribute values in certain selected columns from each table.

To be specific, let S and T be tables, and suppose that {C₁,...,C_k} are selected attributes of S and {D₁,...,D_k} are selected attributes of T. Each table may have additional attributes as well. Note that we select the same number of attributes from each table.

The equi-join of S and T on columns {C₁,...,C_k} and {D₁,...,D_k} is the table formed by combining a row of S with a row of T, provided that corresponding columns have equal value—that is, provided that:

S.C ₁ = T.D ₁,S.C ₂, ...,S.C _k = T.D_k

As an example, consider the tables:

A1	A2
1	4
4	5
6	3

B1	B2	B3
2	3	4
6	7	3
1	1	4

To form the equi-join:

S equi-join_{A2 = B3} T

we combine rows for which:

S.A ₂ = T.B ₃

This gives:

S.A1	S.A2	T.B1	T.B2	T.B3
1	4	2	3	4
1	4	1	1	4
6	3	6	7	3

Notice that the equi-join can be expressed in terms of the Cartesian product and the selection operation as follows:

This simply says that, to form the equi-join, we take the Cartesian product S x T of S and T (i.e., the set of all combinations of rows from S and T) and then select only those rows for which:

S.C ₁ T.D ₁,S.C ₂ = T.D ₂, ...,S.C_k = T.D₂ , ...,S.C_k = T.D_k

θ-Join

The θ-join (read theta join, since θ is the Greek letter theta) is similar to the equi-join and is used when we need to make a comparison other than equality between column values. In fact, the θ-join can use any of these arithmetic comparison relations:

=, ≠, <, ≤, >, ≥

Let S and T be tables, and suppose that {C₁,...,C_k} are selected attributes of S and {D₁,...,D_k} are selected attributes of T. Each table may have additional attributes as well. Note that we select the same number of attributes from each table. Let θ ₁,...,θ _k be comparison relations. Then the θ-join of tables S and T on columns C₁,...,C_k and D₁,...,D_k is:

Thus, to form the θ-join, we take the Cartesian product S x T of S and T and then select those rows for which the value in column C₁ stands in relation θ ₁ to the value in column D₁ and similarly for each of the other columns.

As an example, consider these tables:

A1	A2
1	2
4	5
6	3

B1	B2	B3
2	3	4
6	7	3

To form the θ-join:

we keep only those rows of the Cartesian product of the two tables for which the value in column A₂ is ≤ the value in column B₃:

S.A1	S.A2	T.B1	T.B2	T.B3
1	2	2	3	4
1	2	6	7	3
6	3	2	3	4
6	3	6	7	3

Notice that a θ-join, where all relations θ _i are equality (=), is precisely the equi-join.

The natural join, equi-join, and θ-join are referred to as inner joins. Each inner join has a corresponding left outer join and right outer join , which are formed by first taking the corresponding inner join and then including some additional rows.

In particular, for the left outer join, if s is a row of S that was not used in the inner join, we include the row s, filled out to the proper size with NULL values. An example may help to clarify this concept.

In an earlier example, we saw that the natural join of the tables:

is:

The corresponding left outer join is the same as the nat-join, but with a few extra rows:

In particular, the left outer join also contains the two rows of S that were not involved in the natural join, with NULL values used to fill out the rows. The right outer join is defined similarly, where the rows of T are included, with NULL values in place of the S values.

One of the simplest uses for an outer join is to help see what is not part of an inner join! For instance, the previous table shows us instantly that the second and fourth rows:

of table S are not involved in the natural join S nat-join T. Put another way, the values:

and:

are not present in any rows of table T.

Now let us consider how to implement the various types of joins in Microsoft Access. The Access Query Design window makes it easy to create equi-joins. Of course, a natural join is easily created from an appropriate equi-join by using a projection. Let us illustrate this statement with an example.

Begin by creating the following two simple tables, S and T, shown in Table 5-12 and Table 5-13.

Let us create the equi-join:

Open the Query Design window (by asking for a new query), and add these two tables. To establish the associations:

S.A ₁ = T.B ₁

and

S.A ₂ = T.B ₂

drag the attribute name A₁ to B_1, and drag the attribute name A₂ to B₂. This should create the lines shown in Figure 5-11. Drag the two asterisks down to the first two columns of the design grid, as in Figure 5-11. (Access provides the asterisk as a quick way to drag all of the fields to the design grid. It is the same as dragging each field separately with one exception—changes to the underlying table design are reflected in the asterisk. In other words, if new fields are added to the underlying table, they will be included automatically in the query.)

Figure 5-11. Establishing associations in the Access Query Design window

Now all we need to do is run the query. The result is shown in Table 5-14.

In other words, Microsoft Access uses the relationships defined graphically in the upper portion of the window to create an equi-join.

The Access Query Design window does not allow us to create a θ-join that does not use equality. However, we can easily create such a join from an equi-join by altering the corresponding SQL statement. We will discuss SQL in detail in Chapter 6. For now, let us modify the previous example to illustrate the technique.

From the design view for the query in the previous example, select SQL from the View menu. You should see the window shown in Figure 5-12.

Figure 5-12. The SQL statement generated from Figure 5-11

This is the SQL statement that Access created from our query design for the previous example. Now, edit the two equal signs by changing each of them to <= (less than or equal to). Note that, for text, the less-than-or-equal-to sign refers to alphabetical order.

Now run the query. The result table should appear as shown in Table 5-15.

Notice that for each row of the table, A₁ precedes or equals B₁ in alphabetical order, and A₂ precedes or equals B₂.

Finally, observe that if we try to return to the design view of this query, Access issues the message in Figure 5-13, because the design view cannot create θ-joins that are not based strictly on equality.

Figure 5-13. Access error for attempting to create unequal θ-joins

To create an outer join, return the SQL statement of the previous example back to its original form (with equal signs), and then return to design view. Click the right mouse button on one of the connecting lines between the table schemes, and choose Join Properties from the pop-up menu. This should produce the dialog box shown in Figure 5-14.

Figure 5-14. The Access dialog box for joining properties

Select option 2, which will produce a left outer join. (Option 1 creates an inner join, option 2 creates a left outer join, and option 3 creates a right outer join.) Do the same for the other connecting line. Take a peek at the SQL statement, which should appear as in Figure 5-15.

Figure 5-15. The SQL statement illustrating a left outer join

Now you can run the query, which should produce the result table in Table 5-16, where the empty cells contain the NULL value.

Of course, a right outer join is created similarly, by choosing option 3 in Figure 5-14.

A semi-join is formed from an inner join (or θ-join) by projecting onto one of the tables that participated in the join. In other words, we first form the join:

and then just keep the columns that came from S or from T. Thus, the formula for the left semi-join is:

Similarly, the formula for the right semi-join is:

The concept of a semi-join occurs in relation to the DISTINCTROW keyword of the SELECT clause in Access SQL, which we will discuss in Chapter 6. For now, let us consider an example of the semi-join, which should indicate why semi-joins are useful.

Imagine that we add a new publisher to the PUBLISHERS table (Another Press in Table 5-17), but do not add any books for this publisher to the BOOKS table. Consider the inner join of the tables PUBLISHERS and BOOKS:

PUBLISHERS join _{PUBLISHERS.PubID = BOOKS.PubID} BOOKS

For the LIBRARY database, the result table resulting from this join is shown in Table 5-18.

If we now project onto the PUBLISHERS table, we get the left semi-join:

PUBLISHERS left-semi-join _{PUBLISHERS.PubID = BOOKS.PubID} BOOKS

for which the result table is shown in Table 5-19.

This is the set of all publishers that have book entries in the BOOKS database.

There is one more operation in relational algebra that occurs from time to time, called the quotient . However, since this operation is less common, and a bit involved, we will cover it in Appendix B. (You may turn to that appendix after finishing this chapter, if you are interested.)

Let us conclude this discussion with a brief remark about optimization . As we have discussed, statements in the relational algebra are procedural; that is, they describe a procedure for carrying out the operations. However, this procedure is often not very efficient.

Let us illustrate with an extreme example. Consider the two table schemes:

{ISBN,Title,Price} and {ISBN,PageCount}

If S is a table based on the first scheme and T is a table based on the second scheme, then the natural join is:

According to this formula, the join is carried out in the following steps:

Now imagine two tables S and T, where S has 10,000 rows and T has 10,000 rows. Assume also that the tables have only one common attribute, for which no values are the same in both tables. In this case, according to the definition of natural join, the join is actually the empty table.

However, according to the procedure described, the first step in computing this join is to compute the product S x T, which has 10,000 x 10,000 = 100,000,000 rows—that is, one hundred million rows! Obviously, this is not the best procedure for computing the join!

Fortunately, database programs that use a procedural language have optimization routines to avoid problems such as this. Such a routine looks at the task it is requested to perform and tries to find an alternative procedure that will produce the same output with less computation. Thus, from a practical standpoint, procedural languages sometimes behave similarly to nonprocedural ones.