chapter13 实践习题1
需积分: 0 10 浏览量
2022-08-03
12:59:17
上传
评论
收藏 528KB PDF 举报
C H A P T E R
13
Query Optimization
Practice Exercises
13.1 Show that the following equivalences hold. Explain how you can apply
them to improve the efficiency of certain queries:
a. E
1
1
u
(E
2
− E
3
) = (E
1
1
u
E
2
− E
1
1
u
E
3
).
b. s
u
(
A
G
F
(E)) =
A
G
F
(s
u
(E)), where u uses only attributes from A.
c. s
u
(E
1
1 E
2
) = s
u
(E
1
) 1 E
2
, where u uses only attributes from E
1
.
Answer:
a. E
1
1
u
(E
2
− E
3
) = (E
1
1
u
E
2
− E
1
1
u
E
3
).
Let us rename (E
1
1
u
(E
2
−E
3
)) as R
1
, (E
1
1
u
E
2
) as R
2
and (E
1
1
u
E
3
)
as R
3
. It is clear that if a tuple t belongs to R
1
, it will also belong to R
2
.
If a tuple t belongs to R
3
, t[E
3
’s attributes] will belong to E
3
, hence
t cannot belong to R
1
. From these two we can say that
∀t, t ∈ R
1
⇒ t ∈ (R
2
− R
3
)
It is clear that if a tuple t belongs to R
2
− R
3
, then t[R
2
’s attributes] ∈
E
2
and t[R
2
’s attributes] 6∈ E
3
. Therefore:
∀t, t ∈ (R
2
− R
3
) ⇒ t ∈ R
1
The above two equations imply the given equivalence.
This equivalence is helpful because evaluation of the right hand
side join will produce many tuples which will finally be removed
from the result. The left hand side expression can be evaluated more
efficiently.
b. s
u
(
A
G
F
(E)) =
A
G
F
(s
u
(E)), where u uses only attributes from A.
u uses only attributes from A. Therefore if any tuple t in the output
of
A
G
F
(E) is filtered out by the selection of the left hand side, all the
tuples in E whose value in A is equal to t[A] are filtered out by the
selection of the right hand side. Therefore:
1
阿葱的葱白
- 粉丝: 26
- 资源: 313
评论0