代數(shù)優(yōu)化(數(shù)據(jù)庫(kù))
時(shí)間:2022-12-14 20:30:01 | 來(lái)源:信息時(shí)代
時(shí)間:2022-12-14 20:30:01 來(lái)源:信息時(shí)代
代數(shù)優(yōu)化 : 根據(jù)關(guān)系代數(shù)的等價(jià)變換規(guī)則及一套啟發(fā)式規(guī)則,通過(guò)對(duì)關(guān)系代數(shù)表達(dá)式進(jìn)行等價(jià)變換,達(dá)到優(yōu)化查詢執(zhí)行的目的。
關(guān)系代數(shù)表達(dá)式的等價(jià)表示用相同的關(guān)系代替兩個(gè)表達(dá)式中相應(yīng)的關(guān)系所得到的結(jié)果是相同的。兩個(gè)關(guān)系表達(dá)式E1和E2是等價(jià)的,可記為E1=E2。常用的等價(jià)變換規(guī)則包括:
(1)連接、笛卡兒積交換律:設(shè)E1和E2是關(guān)系代數(shù)表達(dá)式,F是連接運(yùn)算的條件,則有:
(2)連接、笛卡兒積的結(jié)合律: 設(shè)E
1、E
2、E
3是關(guān)系代數(shù)表達(dá)式,F
1和F
2是連接運(yùn)算的條件,則有:
(3)投影的串接定律:
π
A_((1,A
2,……,A
n))(π
B_((1,B
2,…B
n))(E))≡π
A1,A2,…,An(E)。
其中,E是關(guān)系代數(shù)表達(dá)式,A
i(i=1,2,…,n),B
j(j=1,2,…,m)是屬性名,且{A
1,A
2,…,A
n}構(gòu)成{B
1,B
2,…,B
m}的子集。
(4)選擇的串接定律:
σ
F1(σ
F2(E))≡σ
F1∧σ
F2(E)。
其中,E是關(guān)系代數(shù)表達(dá)式,F
1和F
2是選擇條件。選擇的串接律說(shuō)明選擇條件可以合并。這樣一次就可檢查全部條件。
(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則有更一般的規(guī)則:
π
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中的屬性,則由上面的等價(jià)變換規(guī)則(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)選擇與并的分配律:設(shè)E=E
1∪E
2,E
1和E
2有相同的屬性名,則
σF(E1∪E2)≡σF(E1)∪σF(E2)。
(8)選擇與差運(yùn)算的分配律:若E
1與E
2有相同的屬性名,則
σF(E1-E2)≡σF(E1)-σF(E2)。
(9)選擇對(duì)自然連接的分配律:
σF(E1⋈E2)≡σF(E1)⋈σF(E2)。
F只涉及E
1與E
1的公共屬性。
(10)投影與笛卡兒積的分配律: 設(shè)E
1和E
2是兩個(gè)關(guān)系表達(dá)式,A
1,A
2,…,A
n是E
1的屬性,B
1,B
2,…,B
m是E
2的屬性,則
(11)投影與并的分配律: 設(shè)E
1和E
2有相同的屬性名,則
進(jìn)行代數(shù)優(yōu)化時(shí)常用的啟發(fā)式規(guī)則(heuristic rules)包括:
規(guī)則1: 選擇運(yùn)算應(yīng)盡可能先做。在優(yōu)化策略中這是最重要、最基本的一條。它常常可以使執(zhí)行時(shí)間節(jié)約幾個(gè)數(shù)量級(jí),因?yàn)檫x擇運(yùn)算通??梢允褂?jì)算的中間結(jié)果大大變小。
規(guī)則2: 把投影運(yùn)算和選擇運(yùn)算同時(shí)進(jìn)行。如有若干投影和選擇運(yùn)算,并且它們都對(duì)同一個(gè)關(guān)系操作,則可以在掃描此關(guān)系的同時(shí)完成所有的這些運(yùn)算以避免重復(fù)掃描關(guān)系。
規(guī)則3: 把投影同其前或其后的雙目運(yùn)算結(jié)合起來(lái),沒(méi)有必要為了去掉某些字段而掃描一遍關(guān)系。
規(guī)則4: 把某些選擇同在它前面要執(zhí)行的笛卡兒積結(jié)合起來(lái)成為一個(gè)連接運(yùn)算,連接特別是等值連接運(yùn)算要比同樣關(guān)系上的笛卡兒積省很多時(shí)間。
規(guī)則5: 找出公共子表達(dá)式。如果這種重復(fù)出現(xiàn)的子表達(dá)式的結(jié)果不是很大的關(guān)系,并且從外存中讀入這個(gè)關(guān)系比計(jì)算該子表達(dá)式的時(shí)間少得多,則先計(jì)算一次公共子表達(dá)式并把結(jié)果寫(xiě)入中間文件是合算的。當(dāng)查詢對(duì)象是視圖時(shí),定義視圖的表達(dá)式就可能是一種公共子表達(dá)式。
代數(shù)優(yōu)化的過(guò)程是依據(jù)上面的等價(jià)變換規(guī)則,應(yīng)用這些啟發(fā)式規(guī)則,對(duì)查詢語(yǔ)法樹(shù)進(jìn)行等價(jià)變換。