Consider the following SQL query over tables R(A), S(A), and T (A). Note that "Select Distinct" in SQL represents a duplicate-eliminating projection.
Select Distinct R.A
From R, S, T
Where R.A = S.A and R.A = T.A
If we have a table with R(A, B) tuples {{1, a}, {1, b}, {2, c}, {3, d}, {4, e}, {4, f }}, then a duplicate-preserving projection on R.A will return {1, 1, 2, 3, 4, 4}, while a duplicate-eliminating projection on R.A will return {1, 2, 3, 4}.
Figures 1(a)-(e) show five logical plans. The logical operator π in Figure 1 represents a duplicate-eliminating projection. For example, πR.A represents a duplicate-eliminating projection of attribute R.A. On the other hand, the logical operator τ represents a duplicate-preserving projection. The logical operator ?? represents a natural join. Assume that, in the general case, R, S, and T can contain duplicate tuples.
1. Is the logical plan in Figure 1(a) equivalent to the logical plan in Figure 1(b)? (Equivalent means that they produce the same query result.) If not, what is the minimal set of properties on the tables such that these plans are equivalent?
2. Is the logical plan in Figure 1(a) equivalent to the logical plan in Figure 1(c)? If not, what is the minimal set of properties on the tables such that these plans are equivalent?
3. Is the logical plan in Figure 1(a) equivalent to the logical plan in Figure 1(d)? If not, what is the minimal set of properties on the tables such that these plans are equivalent?
4. Is the logical plan in Figure 1(a) equivalent to the logical plan in Figure 1(e)? If not, what is the minimal set of properties on the tables such that these plans are equivalent?
1
τR.A
π R.A π R.A
T(A)
T(A) R(A) π R.A S(A)
R(A) S(A) T(A) S(A)
R(A)
(a) (b) (c)
τR.A τR.A
π R.A π R.A π
T(A) T.A
T(A)
R(A) S(A) R(A) S(A)
(d) (e)
Figure 1: Logical plans