Databases Reference
In-Depth Information
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:
1.
Form the Cartesian product.
2.
Take the appropriate selection.
3.
Take the appropriate projection.
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.
