【文章內(nèi)容簡(jiǎn)介】 dition 等價(jià)規(guī)則 7. 在下面兩個(gè)條件下 , 選擇操作對(duì) ? 連接操作有分配律 : (a) 當(dāng) ?0中的所有屬性僅涉及被連接表達(dá)式之一 (E1)的屬性時(shí) : ??0?E1 ? E2) = (??0(E1)) ? E2 (b) 當(dāng) ?1 僅涉及 E1的屬性且 ?2僅涉及 E2的屬性時(shí) : ??1??? ?E1 ? E2) = (??1(E1)) ? (??? (E2)) 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 等價(jià)規(guī)則 8. 投影操作對(duì) ? 連接操作的分配律如下 : (a) 若 ? 僅涉及來(lái)自 L1 ? L2的屬性 : (b) 考慮連接 E1 ? E2 ?若 L1 和 L2 分別是來(lái)自 E1和 E2的屬性集合 ?令 L3 是連接條件 ?中涉及的 E1的屬性 , 但不在 L1 ? L2中 , 并且 ?令 L4是連接條件 ?中涉及的 E2的屬性 ,但不在 L1 ? L2中 ))(())(()( 2......12.......1 2121 EEEE LLLL ???? ? ??)))(())(((). .. ..( 2......121 42312121 EEEE LLLLLLLL ???? ????? ??169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 等價(jià)規(guī)則 9. 集合運(yùn)算并和交都是可交換的 : E1 ? E2 = E2 ? E1 E1 ? E2 = E2 ? E1 ? 集合差不是可交換的 10. 集合并和交都是可結(jié)合的 : (E1 ? E2) ? E3 = E1 ? (E2 ? E3) (E1 ? E2) ? E3 = E1 ? (E2 ? E3) 11. 選擇操作對(duì) ?, ? 和 –可分配 : ?? (E1 – E2) = ?? (E1) – ??(E2) 類似地可用 ?和 ? 替換 – 同樣 : ?? (E1 – E2) = ??(E1) – E2 類似地可用 ? 替換 – , 但不能用 ? 12. 投影操作對(duì)并可分配 : ?L(E1 ? E2) = (?L(E1)) ? (?L(E2)) 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 等價(jià)規(guī)則的圖示 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 轉(zhuǎn)換例 ? 查詢 : 找出所有在位于 Brooklyn的某分行具有帳戶的客戶的姓名 ?customername(?branchcity = “Brooklyn‖ (branch (account depositor))) ? 利用規(guī)則 7a轉(zhuǎn)換 . ?customername ((?branchcity =“Brooklyn‖ (branch)) (account depositor)) ? 盡可能早地執(zhí)行選擇可以減少待連接關(guān)系的大小 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 多步轉(zhuǎn)換例 ? 查詢 : 找出所有在位于 Brooklyn的某分行具有帳戶且?guī)粲囝~超過(guò)$1000的客戶的姓名 : ?customername((?branchcity = “Brooklyn” ? balance 1000 (branch (account depositor))) ? 利用連接結(jié)合性 (Rule 6a)的轉(zhuǎn)換 : ?customername((?branchcity = “Brooklyn” ? balance 1000 (branch (account)) depositor) ? 第二種形式提供了應(yīng)用 “盡早執(zhí)行選擇 ”規(guī)則的機(jī)會(huì) , 導(dǎo)致子表達(dá)式 ?branchcity = “Brooklyn” (branch) ? balance 1000 (account) ? 因此一系列的轉(zhuǎn)換是有用的 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 多步轉(zhuǎn)換 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 投影操作 :例 ? 當(dāng)計(jì)算 (?branchcity = “Brooklyn” (branch) account ) 時(shí)得到一個(gè)關(guān)系 , 其模式為 : (branchname, branchcity, assets, accountnumber, balance) ? 利用等價(jià)規(guī)則 8a和 8b下推投影 。 從中間結(jié)果刪除不必要的屬性可得 : ? customername (( ? accountnumber ( (?branchcity = “Brooklyn” (branch) account )) depositor) ?customername((?branchcity = “Brooklyn” (branch) account) depositor) 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 連接次序 :例 ? 對(duì)所有關(guān)系 r1, r2, 及 r3 (r1 r2) r3 = r1 (r2 r3 ) ? 若 r2 r3 很大且 r1 r2 較小 , 選擇 (r1 r2) r3 ? 從而計(jì)算并存儲(chǔ)一個(gè)較小的臨時(shí)關(guān)系 ? 結(jié)合律的使用原則 : ?先做連接結(jié)果較小的 ?如果先作的這部分小到只有一行或幾行， 總 運(yùn)算量小 ? 問(wèn)題：要機(jī)器自動(dòng)作優(yōu)化，比較難 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 連接次序 :例 ? 考慮表達(dá)式 ?customername ((?branchcity = ―Brooklyn‖ (branch)) account depositor) ? 可以先計(jì)算 account depositor, 再將結(jié)果與 ?branchcity = ―Brooklyn‖ (branch) 連接 ? 但 account depositor 可能是個(gè)大關(guān)系 ? 由于更可能僅僅少部分銀行客戶在位于的分行開(kāi)帳戶, 因此更好的做法是先計(jì)算 : ?branchcity = ―Brooklyn‖ (branch) account 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 連接次序例 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 等價(jià)表達(dá)式的枚舉 ? 查詢優(yōu)化器利用等價(jià)規(guī)則來(lái)系統(tǒng)地生成等價(jià)于給定表達(dá)式的表達(dá)式 ? 從概念上說(shuō) , 通過(guò)重復(fù)執(zhí)行下列步驟直至找不到更多表達(dá)式來(lái)生成所有等價(jià)表達(dá)式 ? 對(duì)每個(gè)當(dāng)前找到的表達(dá)式 , 利用所有可用的等價(jià)規(guī)則 , 并增加新生成的表達(dá)式到當(dāng)前找到的表達(dá)式集合中 ? 上述方法的時(shí)間空間代價(jià)都很大 ? 通過(guò)共享 公共子表達(dá)式 可減少空間需求 : ?當(dāng)利用一等價(jià)規(guī)則可從 E2生成 E1, 通常兩者僅有頂層不同 , 下面的子樹(shù)是相同的 , 故可以共享 ?例如 , 當(dāng)應(yīng)用連接結(jié)合律時(shí) ? 通過(guò)不生成所有表達(dá)式可減少時(shí)間需求 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 求值計(jì)劃 ? 求值計(jì)劃確切定義了對(duì)每個(gè)操作采用什么算法 , 以及各操作的執(zhí)行是如何協(xié)調(diào)的 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 求值計(jì)劃的選擇 ? 選擇求值計(jì)劃時(shí)必須考慮求值算法的相互影響 ? 原因：獨(dú)立地為每個(gè)操作都選擇最廉價(jià)算法未必總體最佳 ? 例如 ?歸并連接可能比散列連接代價(jià)高 , 但是可以提供有序輸出 , 從而減少外層聚合操作的代價(jià) ?嵌套循環(huán)連接可能提供流水線化的機(jī)會(huì) ? 實(shí)際的查詢優(yōu)化器結(jié)合了下列兩大類方法的要素 : 1. 搜索所有計(jì)劃并以基于代價(jià)的方式選擇最佳計(jì)劃 2. 利用啟發(fā)式規(guī)則選擇計(jì)劃 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 基于代價(jià)的優(yōu)化 ?考慮為 r1 r2 . . . rn找到最佳連接次序 ?組合爆炸 :上面的表達(dá)式共有 (2(n – 1))!/(n – 1)! 種不同的連接次序 , 當(dāng) n = 7, 即有 665280, 當(dāng) n = 10, 結(jié)果大于 1760億 ! ?沒(méi)有必要生成所有連接次序 ?利用 動(dòng)態(tài)規(guī)劃 , {r1, r2, . . . rn}的任何子集的最小代價(jià)連接次序只計(jì)算一次并保存為將來(lái)所用 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 優(yōu)化中的動(dòng)態(tài)規(guī)劃 ?要找到 n個(gè)關(guān)系的最佳連接樹(shù) : ?為找到 n個(gè)關(guān)系的集合 S 進(jìn)行連接的最佳方案 , 考慮所有可能的形如 S1 (S – S1)的方案 , 其中 S1 是 S 的任意非空子集 ?遞歸計(jì)算連接 S 的所有子集的代價(jià) , 以找出每個(gè)方案的代價(jià) , 然后選擇 2n – 1 種可能方案中代價(jià)最小者 ?當(dāng)計(jì)算出任意子集的方案 , 保存該方案 ,并在需要的時(shí)候重用之 , 而不是重新計(jì)算 ?動(dòng)態(tài)規(guī)劃 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 連接次序優(yōu)化算法 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 左深連接樹(shù) ?左深連接樹(shù)中 , 每個(gè)連接的右手邊輸入是個(gè)關(guān)系 , 而不是中間連接的結(jié)果 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 優(yōu)化的代價(jià) ?為找到 n個(gè)關(guān)系的集合的最佳左深連接樹(shù) : ?Consider n alternatives with one relation as righthand side input and the other n1 relations as lefthand side input ?Using (recursively puted and stored) leastcost join order for each alternative on lefthandside, choose the cheapest of the n alternatives ?利用動(dòng)態(tài)規(guī)劃 , 優(yōu)化的時(shí)間復(fù)雜度為 O(3n) ?當(dāng) n = 10, 此數(shù)為 59000而不是 1760億 ! ?空間復(fù)雜度為 : O(2n) 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 基于代價(jià)優(yōu)化中有收益的排序次序 ? 考慮表達(dá)式 (r1 r2 r3) r4 r5 ? 有收益的排序次序 是指元組的一個(gè)特定排序次序 , 對(duì)以后的操作可能有用 ?生成 r1 r2 r3 結(jié)果時(shí)再與 r4 或 r5的公共屬性上排序 , 也許