笛卡儿积结合律:
(
E
1
×
E
2
)
×
E
3
=
E
1
×
(
E
2
×
E
3
)
(E_1 \times E_2) \times E_3 = E_1 \times (E_2 \times E_3)
(E1?×E2?)×E3?=E1?×(E2?×E3?)
自然连接结合律:
(
E
1
?
E
2
)
?
E
3
=
E
1
?
(
E
2
?
E
3
)
(E_1 \bowtie E_2) \bowtie E_3 = E_1 \bowtie (E_2 \bowtie E_3)
(E1??E2?)?E3?=E1??(E2??E3?)
条件连接结合律:
(
E
1
?
F
1
E
2
)
?
F
2
E
3
=
E
1
?
F
1
(
E
2
?
F
2
E
3
)
(E_1 \bowtie_{{F}_1} E_2) \bowtie_{{F}_2} E_3 = E_1 \bowtie_{{F}_1} (E_2 \bowtie_{{F}_2} E_3)
(E1??F1??E2?)?F2??E3?=E1??F1??(E2??F2??E3?)
选择操作串接定律(Cascading of Selection):选择操作可以串接执行,且可以按任何顺序进行。合取条件(AND连接的条件)可以分解为多个选择操作。
选择运算顺序交换定律:
σ
F
1
(
σ
F
2
(
E
)
)
=
σ
F
2
(
σ
F
1
(
E
)
)
\sigma_{F1}(\sigma_{F2}(E)) = \sigma_{F2}(\sigma_{F1}(E))
σF1?(σF2?(E))=σF2?(σF1?(E))
合取条件分解定律:
σ
F
1
∧
F
2
(
E
)
=
σ
F
1
(
E
)
∩
σ
F
2
(
E
)
\sigma_{F1 \land F2}(E) = \sigma_{F1}(E) \cap \sigma_{F2}(E)
σF1∧F2?(E)=σF1?(E)∩σF2?(E)
投影操作串接定律:如果投影的属性集是另一个投影属性集的子集,那么这两个投影操作可以合并为一个。
π
A
1
,
A
2
,
.
.
.
,
A
n
(
π
B
1
,
B
2
,
.
.
.
,
B
m
(
E
)
)
=
π
A
1
,
A
2
,
.
.
.
,
A
n
(
E
)
,
当
(
A
i
?
B
j
)
\pi_{A1, A2, ..., An}(\pi_{B1, B2, ..., Bm}(E)) = \pi_{A1, A2, ..., An}(E) ,当 (A_i \subseteq B_j)
πA1,A2,...,An?(πB1,B2,...,Bm?(E))=πA1,A2,...,An?(E),当(Ai??Bj?)
选择与其他操作的交换律(Commutation with Other Operations):在某些情况下,选择操作可以与笛卡儿积、投影和连接操作交换,使得可以先对小的数据集进行筛选,减少后续操作的数据量。
选择与笛卡儿积:
σ
F
(
E
1
×
E
2
)
=
(
σ
F
(
E
1
)
)
×
E
2
\sigma_{F}(E_1 \times E_2) = (\sigma_{F}(E_1)) \times E_2
σF?(E1?×E2?)=(σF?(E1?))×E2? 如果 (F) 中涉及的属性都是 (
E
1
E_1
E1?) 中的属性
选择与投影:
σ
F
(
π
A
(
E
)
)
=
π
A
(
σ
F
(
E
)
)
\sigma_{F}(\pi_{A}(E)) = \pi_{A}(\sigma_{F}(E))
σF?(πA?(E))=πA?(σF?(E)) 如果 (F) 只涉及 (A) 的属性
如果选择条件是“主码=值”,则平均搜索代价 (
c
o
s
t
=
B
2
cost = \frac{B}{2}
cost=2B? )。
索引扫描算法代价的估算:
如果选择条件是“码=值”,则采用该表的主索引,若为B+树,层数为L,那么代价 ( cost = L + 1 )。
嵌套循环连接算法代价的估算:
对于两个表的嵌套循环连接,如果其中一个表较小,则可以将较小的表放在内循环中,代价 (
c
o
s
t
=
B
r
+
B
r
×
B
s
K
?
1
cost = B_{r} + \frac{B_{r} \times B_{s}}{K - 1}
cost=Br?+K?1Br?×Bs?? )。
排序-合并连接算法代价的估算:
如果连接的表已经按照连接属性排好序,则代价 (
c
o
s
t
=
B
r
+
B
s
+
F
r
s
×
N
r
×
N
s
M
r
s
cost = B_{r} + B_{s} + \frac{F_{rs} \times N_{r} \times N_{s}}{M_{rs}}
cost=Br?+Bs?+Mrs?Frs?×Nr?×Ns?? )。
其中:
(
B
r
B_{r}
Br? ) 和 (
B
s
B_{s}
Bs? ) 分别是两个连接表占用的数据块数。
( K ) 是内存中可用于存储数据块的数量。
(
F
r
s
F_{rs}
Frs? ) 是连接选择性,代表连接结果元组数的比例。
(
M
r
s
M_{rs}
Mrs? ) 是存放连接结果的块因子,表示每块中可以存放的结果元组数目。