代数优化(数据库)
时间：2022-12-14 20:30:01 | 来源：信息时代
时间：2022-12-14 20:30:01 来源：信息时代
代数优化 : 根据关系代数的等价变换规则及一套启发式规则,通过对关系代数表达式进行等价变换,达到优化查询执行的目的。
关系代数表达式的等价表示用相同的关系代替两个表达式中相应的关系所得到的结果是相同的。两个关系表达式E1和E2是等价的,可记为E1＝E2。常用的等价变换规则包括:
(1)连接、笛卡儿积交换律:设E1和E2是关系代数表达式,F是连接运算的条件,则有:
(2)连接、笛卡儿积的结合律: 设E
1、E
2、E
3是关系代数表达式,F
1和F
2是连接运算的条件,则有:
(3)投影的串接定律:
π
A_((1,A
2,……,A
n))(π
B_((1,B
2,…B
n))(E))≡π
A1,A2,…,An(E)。
其中,E是关系代数表达式,A
i(i=1,2,…,n),B
j(j=1,2,…,m)是属性名,且{A
1,A
2,…,A
n}构成{B
1,B
2,…,B
m}的子集。
(4)选择的串接定律:
σ
F1(σ
F2(E))≡σ
F1∧σ
F2(E)。
其中,E是关系代数表达式,F
1和F
2是选择条件。选择的串接律说明选择条件可以合并。这样一次就可检查全部条件。
(5)选择与投影操作的交换律:
σ
F(π
A1,A2,…,An(E))≡π
A1,A2,…,An(σ
F(E))。
其中,选择条件F只涉及属性A
1,A
2,…,A
n。
若F中有不属于A
1,A
2,…,A
n的属性B
1,B
2,…,B
m则有更一般的规则:
π
A_((1,A
2,…,A
n))(σ
F(E))
≡π
A_((1,A
2,…,A
n))(σ
F(π
A1,A2,…,A_((n,B
1,B
2,…,B
m))(E)))。
(6)选择与笛卡儿积的交换律: 如果F中涉及的属性都是E
1中的属性,则
σF(E1×E2)≡σF(E1)×E2。
如果F=F
1∧F
2,并且F
1只涉及E
1中的属性,F
2只涉及E
2中的属性,则由上面的等价变换规则(1)、(4)、(6)可推出:
σF(E1×E2)≡σF1(E1)×σ_((F2))(E2)。
若F
1只涉及E
1中的属性,F
2涉及E
1和E
2两者的属性,则仍有
σF(E1×E2)≡σF2))(σ_((F1(E1)×(E2))。
它使部分选择在笛卡儿积前先做。
(7)选择与并的分配律:设E=E
1∪E
2,E
1和E
2有相同的属性名,则
σF(E1∪E2)≡σF(E1)∪σF(E2)。
(8)选择与差运算的分配律:若E
1与E
2有相同的属性名,则
σF(E1-E2)≡σF(E1)-σF(E2)。
(9)选择对自然连接的分配律:
σF(E1⋈E2)≡σF(E1)⋈σF(E2)。
F只涉及E
1与E
1的公共属性。
(10)投影与笛卡儿积的分配律: 设E
1和E
2是两个关系表达式,A
1,A
2,…,A
n是E
1的属性,B
1,B
2,…,B
m是E
2的属性,则
(11)投影与并的分配律: 设E
1和E
2有相同的属性名,则
进行代数优化时常用的启发式规则(heuristic rules)包括:
规则1: 选择运算应尽可能先做。在优化策略中这是最重要、最基本的一条。它常常可以使执行时间节约几个数量级,因为选择运算通常可以使计算的中间结果大大变小。
规则2: 把投影运算和选择运算同时进行。如有若干投影和选择运算,并且它们都对同一个关系操作,则可以在扫描此关系的同时完成所有的这些运算以避免重复扫描关系。
规则3: 把投影同其前或其后的双目运算结合起来,没有必要为了去掉某些字段而扫描一遍关系。
规则4: 把某些选择同在它前面要执行的笛卡儿积结合起来成为一个连接运算,连接特别是等值连接运算要比同样关系上的笛卡儿积省很多时间。
规则5: 找出公共子表达式。如果这种重复出现的子表达式的结果不是很大的关系,并且从外存中读入这个关系比计算该子表达式的时间少得多,则先计算一次公共子表达式并把结果写入中间文件是合算的。当查询对象是视图时,定义视图的表达式就可能是一种公共子表达式。
代数优化的过程是依据上面的等价变换规则,应用这些启发式规则,对查询语法树进行等价变换。
在线咨询
