On p. 815, we introduced three operations on relations that are used frequently in relational databases:
• select, which chooses a subset of the elements of an n-ary relation. For R ⊆ A1 × · · · × An and a
function ϕ : A1 × · · · × An → {True, False}, we can select only those elements of R that satisfy ϕ.
• project, which turns an n-ary relation into an n′
-ary relation for some n′ ≤ n by eliminating components. For R ⊆ A1 × · · · × An and S ⊆ {1, 2, . . . , n}, we can project R into a smaller set of columns by removing the ith component of each pair in R for any i ∈/ S.
• join, which combines two binary relations R ⊆ A × B and S ⊆ B × C into a single ternary relation containing triples ha, b, ci such that ha, bi ∈ R and hb, ci ∈ S. For example, let R = {h1, 2, 3i,h4, 5, 6i}, let S = {h6, 7i,h6, 8i}, and let T = {h7, 9i,h7, 10i}. Then
• select(R, xzEven) = {h4, 5, 6i} for xzEven(x, y, z) = (2 | x) ∧ (2 | z).
• project(R, {1, 2}) = {h1, 2i,h4, 5i} and project(R, {1, 3}) = {h1, 3i,h4, 6i}.
• join(S, T) = {h6, 7, 9i,h6, 7, 10i}.
Solve the following using the relation operators −1
(inverse), ◦ (composition), select, project, and join: