【正文】 適用于樹結(jié)構(gòu)索引 ,如 B+樹 ? HTi :索引 i 的層數(shù) — 即高度 ?對(duì)于關(guān)系 r上 A 屬性的平衡樹索引 (如 B+樹 ) HTi = ?logfi(V(A,r))? ?對(duì)于散列索引 , HTi 為 1 ? LBi :索引 i 的底層索引塊數(shù) — 即索引葉子層的塊數(shù) 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 查詢代價(jià)的度量 (回顧 ) ?典型地 , 磁盤存取是決定性的代價(jià) , 也相對(duì)容易估算 ?來自磁盤的塊傳送次數(shù)被用作求值的實(shí)際代價(jià)的度量 ?假設(shè)所有塊傳送都具有相同代價(jià) ?實(shí)際的優(yōu)化器不作此假設(shè) , 并區(qū)分順序與隨機(jī)磁盤存取 ?不包括寫輸出到磁盤的代價(jià) ?記算法 A的代價(jià)估算為 EA 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 統(tǒng)計(jì)信息例 ? faccount= 20 (一塊可放入 account 的 20個(gè)元組 ) ? V(branchname, account) = 50 (50個(gè)分行 ) ? V(balance, account) = 500 (500 個(gè)不同的 balance 值 ) ? ?account = 10000 (account 有 10,000條元組 ) ? 假設(shè) account 上存在下列索引 : ?屬性 branchname上的主 B+樹索引 ?屬性 balance上的輔助 B+樹索引 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 選擇的大小估算 ? 等值選擇 ?A=v(r) ?SC(A, r) : 滿足選擇的記錄數(shù) ??SC(A, r)/fr? : 這些記錄將占用的塊數(shù) ?二分搜索的代價(jià)估算為 ?鍵屬性上的等值條件 : SC(A,r) = 1 ? ? 1),()(lo g 22 ????????? rra f rASCbE169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 選擇的大小估算 ? 涉及比較的選擇 ?形如 ?A?V (r )的選擇 ?令 c 表示滿足條件的估算元組數(shù) ?若 min(A,r) 和 max(A,r) 在目錄中可得 – c = 0 if v min(A,r) – c = ? 若沒有統(tǒng)計(jì)信息 , c 可假設(shè)為 nr / 2 ? ?A ? V(r) 的情形是對(duì)稱的 ),m i n(),m a x(),m i n(.rArArAvnr ??169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 復(fù)雜選擇的實(shí)現(xiàn) ? 條件 ?I 的 選擇度 是關(guān)系 r 中一條元組滿足 ?I 的概率 ,如果 si 是 r 中滿足的元組數(shù) , 則 ?i 的選擇度為 si /nr ? 合取 : ??1? ?2?. . . ? ?n (r). 結(jié)果中元組數(shù)的估算值為 : ? 析取 : ??1? ?2 ?. . . ? ?n (r). 元組數(shù)的估算值為 : ? 否定 : ???(r). 元組數(shù)的估算值為 : nr – size(??(r)) nrnr nsssn ???? . . . 21???????? ???????? )1(...)1()1(1 21rnrrr nsnsnsn169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 連接的大小的估算 ? 卡氏積 r x s 包含 nr .ns 元組 , 每個(gè)元組占用 sr + ss 字節(jié) ? 若 R ? S = ?, 則 r s 等同于 r x s ? 若 R ? S 是 R 的鍵 , 則 s 的一條元組將與 r 的最多一條元組連接 ? 因此 , r s 中的元組數(shù)不大于 s 中的元組數(shù) ? 若 R ? S 在 S 中是引用 R 的外鍵 , 則 r s中的元組數(shù)正好等于 s中的元組數(shù) ?R ? S 是引用 S 的外鍵的情形是對(duì)稱的 ? 在查詢例 depositor customer 中 , depositor 中的customername 是 customer 的外鍵 ? 因此 , 結(jié)果具有 ndepositor 條元組 , 即 5000 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 連接操作 : 例子 ? 連續(xù)用例 : depositor customer ? 連接例的目錄信息 : ? ncustomer = 10,000 ? fcustomer = 25, 這意味著 bcustomer =10000/25 = 400 ? ndepositor = 5000. ? fdepositor = 50, 這意味著 bdepositor = 5000/50 = 100 ? V(customername, depositor) = 2500, 這意味著每個(gè)顧客平均有兩個(gè) depositor ?還假設(shè) depositor 中的 customername是 customer 上的外鍵 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 連接的大小的估算 ? 若 R ? S = {A} 不是 R 或 S的鍵 ? 如果我們假設(shè) R 中每個(gè)元組 t 都在 R S中產(chǎn)成元組 , 則 R S中的元組數(shù)估算為 : ? 若正好相反 , 估算值為 : ? 這兩個(gè)估算值的較小者可能更準(zhǔn)確 ),( sAVnn sr ?),( rAVnn sr ?169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 連接的大小的估算 ? 例 :不利用有關(guān)外鍵的信息計(jì)算 depositor customer 的大小估算 : ?V(customername, depositor) = 2500, 且 V(customername, customer) = 10000 ?兩個(gè)估算為 5000 * 10000/2500 = 20,000 及 5000 * 10000/10000 = 5000 ?我們選擇其中的較小估算 , 在本情形下等于我們以前利用外鍵的計(jì)算結(jié)果 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 其他操作的大小估算 ? 投影 : 估算大小 ?A(r) = V(A,r) ? 聚合 : 估算大小 AgF(r) = V(A,r) ? 集合運(yùn)算 ? 對(duì)于同一關(guān)系上選擇的并 /交 : 重寫并利用選擇的大小估算 ?例如 ??1 (r) ? ??2 (r) 可重寫為 ??1v?2 (r) ?對(duì)于在不同關(guān)系上的操作 : ?r ? s 的估算大小 = r 的大小 + s 的大小 ?r ? s 的估算大小 = r 的大小與 s 的大小之最小者 ?r – s 的估算大小 = r ?上面這三種估算都可能不精確 , 但提供了大小的上界 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 其他操作的大小估算 ? 外連接 : ?r s 的估算大小 = r s 的大小 + r 的大小 ?右外連接的情形是對(duì)稱的 ?r s的估算大小 = r s 的大小 + r 的大小 + s 的大小 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 不同值個(gè)數(shù)的估算 選擇 : ?? (r) ? 若 ? 強(qiáng)制 A 取一個(gè)特定值 (., A = 3) : ? V(A,?? (r)) = 1 ? 若 ? 強(qiáng)制 A 取一個(gè)特定集合中的某個(gè)值 (., (A = 1 V A = 3 V A = 4 )): ? V(A,?? (r)) = 指定值的個(gè)數(shù) ? 若選擇條件 ? 形如 A op v,其中 op 為比較運(yùn)算符 (.,A=5): ?估算 V(A,?? (r)) = V(A,r) * s ?其中 s 是本選擇 ?的選擇度 ? 其他情況 : 利用近似估算 min(V(A,r), n?? (r) ) ? 更準(zhǔn)確的估算可利用概率論得到 , 但是本估算一般就很管用 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 不同值個(gè)數(shù)的估算 連接 : r s ? 若 A中所有屬性都來自 r 估算 V(A, r s) = min (V(A,r), n r s) ? 若 A包含來自 r 的屬性 A1和來自 s 的屬性 A2, 則估算 V(A,r s) = min(V(A1,r)*V(A2 – A1,s), V(A1 – A2,r)*V(A2,s), nr s) ? 利用概率論可以得到更精確的估算 , 但這已經(jīng)很好了 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 不同值個(gè)數(shù)的估算 ? 投影的不同值個(gè)數(shù)的估算是直接的 ?在 ?A (r) 中與在 r 中是相同的 ? 對(duì)聚合的分組屬性也是一樣 ? 對(duì)于聚合值 ?對(duì) min(A) 和 max(A),不同值個(gè)數(shù)可估算為 min(V(A,r), V(G,r)), 其中 G表示分組屬性 ? 對(duì)其他聚合函數(shù) , 假設(shè)所有值都不同 , 并利用 V(G,r) 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換 ? 如果在每個(gè)合法的數(shù)據(jù)庫(kù)實(shí)例上 , 兩個(gè)關(guān)系代數(shù)表達(dá)式都生成同樣的元組集合 , 則這兩個(gè)關(guān)系代數(shù)表達(dá)式稱為 等價(jià)的 ?注意 : 元組次序是無關(guān)的 ? 在 SQL中 , 輸入和輸出都是元組的多重集合 ?如果在每個(gè)合法的數(shù)據(jù)庫(kù)實(shí)例上 , 兩個(gè)關(guān)系代數(shù)表達(dá)式都生成同樣的元組多重集合 , 則這兩個(gè)表達(dá)式在關(guān)系代數(shù)的多重集合版本下稱為等價(jià)的 ? 等價(jià)規(guī)則 說明了兩種形式的表達(dá)式是等價(jià)的 ?可以用一個(gè)表達(dá)式替換另一個(gè) 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 等價(jià)規(guī)則 1. 合取選擇操作可以分解稱個(gè)體選擇的序列 : 2. 選擇操作是可交換的 : 3. 一個(gè)投影操作序列中只有最后一個(gè)是必要的 , 其余皆可省略 : 4. 選擇可與笛卡兒積及 ? 連接結(jié)合 : a. ??(E1 X E2) = E1 ? E2 b. ??1(E1 ?2 E2) = E1 ?1? ?2 E2 ))(())(( 1221 EE ???? ???? ?))(()( 2121 EE ???? ??? ??)())))(((( 121 EE ttntt ????? ??169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 等價(jià)規(guī)則 5. ? 連接操作 (及自然連接 ) 可交換 : E1 ? E2 = E2 ? E1 6. (a) 自然連接操作是可結(jié)合的 : (E1 E2) E3 = E1 (E2 E3) (b) ? 連接按如下方式是可結(jié)合的 : (E1 ?1 E2) ?2? ? 3 E3 = E1 ?2? ?3 (E2 ?2 E3) 其中 ?2 僅涉及來自 E2 和 E3的屬性 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd E