SQL and Relational Theory

Chapter 7. SQL and Relational Algebra II: Additional Operators

AS I’VE SAID SEVERAL TIMES ALREADY, AN OPERATOR OF THE RELATIONAL ALGEBRA IS AN OPERATOR THAT TAKES ONE OR MORE RELATIONS AS INPUT AND PRODUCES ANOTHER RELATION AS OUTPUT. As I observed in Chapter 1, however, any number of operators can be defined that conform to this simple characterization. Chapter 6 described the original operators (join, project, etc.); the present chapter describes some of the many additional operators that have been defined since the relational model was first invented. It also considers how those operators can best be realized in SQL.

Semijoin and Semidifference

Join is one of the most familiar of all of the relational operators. In practice, however, it often turns out that many queries that require join at all really require an extended form of that operator called semijoin (you might not have heard of semijoin before, but in fact it’s quite important).

Definition: The semijoin of relations r1 and r2 (in that order), r1 MATCHING r2, is equivalent to (r1 JOIN r2){A,B,…,C}, where A, B, …, C are all of the attributes of r1.

In other words, r1 MATCHING r2 is the join of r1 and r2, projected back on the attributes of r1. Here’s an example (“Get suppliers who currently supply at least one part”):

S MATCHING SP                  |    SELECT S.* FROM S
                               |    WHERE  SNO IN
                               |         ( SELECT SNO FROM SP )

The result heading is the same as that of S. Note that the expressions r1 MATCHING r2 and r2 MATCHING r1 aren’t equivalent, in general. ...