CP363 : Relational Algebra (cont'd)n

Some of the Relational Algebra operations are based upon mathematical set theory. They are:

• cross product
• set union
• set intersection
• set difference

Cross Product

Pairs all tuples from two tables. This is generally not useful on its own, but becomes useful when further selection is applied to its result.

Algebra: R_{<attribute list>} × S_{<attribute list>}

SQL: SELECT * FROM table1, table2

Examples:

SELECT * FROM member, keyword

Returns all possible pair combinations of members and keywords, i.e. all members are listed against all keywords (where a keyword represents an area of expertise).

SELECT * FROM
  ( SELECT * FROM member, keyword ) AS temp
  WHERE Last_Name = 'Brown'

This uses the previous selection statement as a intermediate result set (renamed temp) from which further selections can be made. This could be useful in a situation such as a web page form that looks like the following:

Brown, David - Expertises

Military History Nuclear Arms Landmines Strategic Alliances Third World Defence

This form allows the DCRIS administrator to select the expertise set for this member.

SELECT Last_Name, Description FROM member, keyword

Projection may be used within a cross product.

Set Union

Merges the result sets of two selection statements. All the tuples in both result sets are included in the final result set.

Algebra: R ∪ S

SQL: SELECT * FROM table UNION SELECT * FROM table

Examples:

SELECT Last_Name FROM member
  WHERE Institution = 'Waterloo'
  UNION
  SELECT Last_Name FROM member
  WHERE Institution = 'Wilfrid Laurier'

Returns a list of member's surnames who work at the University of Waterloo or Wilfrid Laurier University. Any duplicate last names are eliminated. Both selection statements must return the same number of attributes and should have the same data type. If the union involves two different tables, the column names used for the attributes are the column names of the first SELECT statement.

SELECT Last_Name FROM member
  WHERE Institution = 'Waterloo'
  UNION ALL
  SELECT Last_Name FROM member
  WHERE Institution = 'Wilfrid Laurier'

With the use of UNION ALL duplicates are not eliminated.

SELECT member_id FROM member
  WHERE Institution = 'Waterloo'
  UNION ALL
  SELECT member_id FROM member
  WHERE Title = 'Dr.'

Returns a set of all members who work at UW, have the title 'Dr.', or both. Duplicate member IDs are not eliminated.

Although at first glance it may seem that this last example could be rewritten as:

SELECT member_id FROM member
  WHERE Institution = 'Waterloo'
  OR Title = 'Dr.'

The results could differ slightly in that it is possible in the UNION ALL version for the same member ID to appear twice. There can be no duplicates in the version with the OR operator as each member tuple can be selected only once. Removing the ALL clause from the previous example would give the same result.

Set Intersection

Merges the result sets of two selection statements. Only the tuples common to both result sets are included in the final result set.

Algebra: R ∩ S

SQL: SELECT * FROM table INTERSECT SELECT * FROM table

Examples:

SELECT member_id FROM member
  WHERE Institution = 'Waterloo'
  INTERSECT ALL
  SELECT member_id FROM member
  WHERE Title = 'Dr.'

Returns a set of all members who work at UW and have the title 'Dr.'. Duplicate member IDs are not eliminated.

SELECT member_id FROM member
  WHERE Institution = 'Waterloo'
  INTERSECT
  SELECT member_id FROM member
  WHERE Title = 'Dr.'

Returns a set of all members who work at UW and have the title 'Dr.'. Duplicate member IDs are eliminated.

This last example could be rewritten as:

SELECT member_id FROM member
  WHERE Institution = 'Waterloo'
  AND Title = 'Dr.'

As with the union example above, the use of the ALL clause changes how such a statement may be rewritten.

Set Difference

The final result set contains only those tuples from the first result set that are not in the second result set.

Algebra: R - S

SQL: SELECT * FROM table EXCEPT SELECT * FROM table

Examples:

SELECT member_id FROM member
  WHERE Institution = 'Waterloo'
  EXCEPT
  SELECT member_id FROM member
  WHERE Title = 'Dr.'

Returns a list of all member IDs for members who work at UW but do not have the title 'Dr.'

EXCEPT ALL has some interesting behaviour that will be passed over for now.

Symbol Reference

Note:

Not all dialects of SQL support the syntax shown here. This syntax is based upon DB2. Sybase SQL Anywhere, for example, does not support the use of the INTERSECT or EXCEPT clauses. It can still perform these operations but with a different syntax. Other syntaxes will be demonstrated later.