Database Systems: The Complete Book
▼ ❑ Chapter 16
▼ ❑ Section 1
▼ ❑ 1
• ❑ a <Query> ::= SELECT <SelList> FROM <FromList> WHERE <Condi-
tion>
▼ ❑ 2
• ❑ a <Condition> ::= <Condition> OR <Condition>
<Condition> ::= NOT <Condition>
▼ ❑ 3
• ❑ b
▼ ❑ Section 2
• ❑ 1 σc(R∩S) and there is an index on S. Assuming that there C attributes in
both R and S, the options are:
▼ ❑ 2
• ❑ a πL(R∪S) ≠ πL(R)∪πL(S)
R(C1, C2) = {(1,1) (1,2) (1,2)}
S(C1, C2) = {(1,3) (1,4) (1,5)}
L = C1
• ❑ b πL(R–S) ≠ πL(R)-πL(S)
S(C1, C2) = {(1,1) (1,3)}
• ❑ 3 πL(R∪BS) = πL(R)∪BπL(S)
Attributes eliminated do not appear in results. Attributes eliminated are not
▼ ❑ 4
• ❑ a Counterexample: R(C1) = {1}
• ❑ b Every record in R has a corresponding record in R. The intersection is
▼ ❑ 5
• ❑ a If R ⊆ S, then R ∪ S = S
True. Every R element has a corresponding S element that appear at
least more times than the R element. Thus, the U operator does not
▼ ❑ 6
• ❑ a πL(πb,c(R) JOIN πb,c,d(S))
• ❑ b πL(R JOIN πb,c,d(S))
• ❑ 7 Push the aggregation before the join.
▼ ❑ 8
• ❑ b Counterexample:
R(C1,C2) = {(1,2) (1,3)}
S(C1,C3) = {(1,2) (2,3)}
• ❑ c True. The record selected could be:
S(C1,C3) = {(1,2) (2,2)}
• ❑ f True. Full outer join is associative. No data is lost.
• ❑ g True. Full outer join is commutative. No data is lost.
• ❑ 10 The SUM function will skip over null values. Let ak = null.
SUM(a1,a2,…,an). a1 + a2 + … + an = null. The law doesn’t hold.
▼ ❑ Section 3
▼ ❑ 1
• ❑ a ( (πa,b,c( R(a,b) JOIN R.b = S.b S(b,c)) ) JOIN S.c = T.c T(c,d) )
πa( R JOIN (δ (πa( R(2) JOIN S ) ))
▼ ❑ 3
• ❑ a πR(σcount( R CROSS JOIN ɣcount(<Query>)))
• ❑ b πR( R JOIN δ(πa(<Query>)) )
• ❑ c σcount(a)=1( R JOIN ɣ(δ(πa(<Query>))))
▼ ❑ 4
• ❑ a πR(σcount>0(ɣcount(R CROSS JOIN <Query>)))
• ❑ 5 4! x 3! x 4! x 3!
▼ ❑ Section 4
▼ ❑ 1
• ❑ i 20000
• ❑ 2 0
• ❑ 3 T(R)/V(S)
• ❑ 4 V(R,a) = 100. V(S,a) = 100.
▼ ❑ 4
• ❑ a 832
▼ ❑ 5
• ❑ a 700
The query plan that uses the fewest I/O’s is highlighted in yellow.
• ❑ 7 The best plan for E or F may not provide sorted output, but the join method
selected (e.g. SMJ) may required sorted input.
▼ ❑ Section 6
• ❑ 2
▼ ❑ 4
• ❑ a ((SR)T)U). Cost: 10000.
• ❑ b Optimal: ((RS)(TU)). Cost: 2000.
▼ ❑ 5
• ❑ a 7! x (T(1)T(7) + T(2)T(6) + T(3)T(5) + T(4)T(4) + T(5)T(3) + T(6)T(2) +
Left-deep: 8!
Right-deep: 8!
▼ ❑ 6
• ❑ a B(R JOIN S) + B((R JOIN S) JOIN U)
▼ ❑ Section 7
▼ ❑ 1
• ❑ a access method: index on b
• ❑ b access method: index on b
• ❑ c access method: index on a
▼ ❑ 2