第3章關系數(shù)據(jù)庫的基本理論-資料下載頁
2025-07-20 09:53本頁面
【正文】 E3) (E1 E2) E3≡E1 (E2 E3) (E1 E2) E3 ≡ E1 (E2 E3) ※ 投影的串接 設 L1,設 L2,?,Ln 為屬性集，并且 ,那么下式也成立 . ※ 選擇的串接 代數(shù)表達式的等價變換規(guī)則 (1) LnLL ??? . . .21)() ) . . . )(( . . . (( 121 EE LLnLL ???? ?））（（（成立：，因此選擇的交換律也由于E))E(F1F2F2F1)())((F1F2F2F12121???????????? ? EE FFFF ? 選擇和投影操作的交換 代數(shù)表達式的等價變換規(guī)則 (2) )))((（ ))((1))(())((1 L EE：，LLF，LFEELLFFLLFFL????????????那么有下式成立中的屬性集還涉及到不在如果條件中的屬性只涉及到這里要求? 選擇對笛卡兒積的分配律 2)1()21( EEEE FF ??? ?? 這里要求 F只涉及到 E1中的屬性。 如果 F形為 F1∧F2 ，且 F1只涉及到 E1的屬性， F2只涉及到 E2的屬性，則有 )2()1()21( 21 EEEE FFF ??? ??? 此外，如果 F形為 F1∧F2 ，且 F1只涉及到 E1的屬性， F2只涉及到 E1和 E2的屬性，則有： )2)1(()21( 12 EEEE FFF ??? ??? ? 選擇對并的分配律 E1和 E2具有相同的屬性名，或者 E1和 E2表達的關系的屬性有對應性，則有： )2()1()21( EEEE FFF ??? ???代數(shù)表達式的等價變換規(guī)則 (3) ? 選擇對集合差的分配律 E1和 E2的屬性有對應性，則有： 2)1()21()2()1()21(EEEEEEEEFFFFF ??? ??? ?? ???或? 選擇對自然聯(lián)接的分配律 F只涉及到表達式 E1和 E2的公共屬性，則有： （ E1 E2） ≡ （ E1） （ E2） F? F? F?? 投影對笛卡爾的分配律 L1是 E1中的屬性集， L2是 E2中的屬性集，則有： )2()1()21( 2121 EEEE LLLL ??? ????? 投影對并的分配律 E1和 E2的屬性有對應性，則有： )2()1()21( EEEE LLL ??? ??? 代數(shù)表達式的等價變換規(guī)則 (4) ? 選擇與聯(lián)接操作的結合 F? （ E1 E2） ≡ E1 E2 1F? （ E1 E2） ≡E1 E2 ? 并和交的交換律 E1∪E2≡E2∪E1 E1∩E2≡E2 ∩E1 ? 并和交的結合律 （ E1∪E2 ） ∪ E3≡E1∪ （ E2∪E3 ） （ E1∩E2） ∩ E3≡E1 ∩（ E2∩E3） 優(yōu)化算法 (1) ※ 代數(shù)優(yōu)化是利用上面的等價變換規(guī)則 ， 對關系表達式進行優(yōu)化 ， 以減少執(zhí)行時的開銷 。 雖然不能保證最優(yōu) ， 但在多數(shù)情況下能使表達式更好些 。 在關系代數(shù)表達式中 ， 最花費時間和空間的運算是笛卡兒積和連接操作 ， 為此 ， 引出三條啟發(fā)式規(guī)則 ， 用于對表達式進行轉換 ， 以減少中間關系的大小 。 ? 優(yōu)先應用單項的選擇和投影； ? 優(yōu)先應用一般選擇和投影； ? 對笛卡兒積、并運算、差運算，若它們前面加有選擇和投影，則先做選擇和投影。 優(yōu)化算法 (2) ※ 算法：關系代數(shù)表達式的優(yōu)化 。 輸入：一個關系代數(shù)表達式的語法樹 輸出：計算表達式的一個優(yōu)化序列 方法： ⑴ 把 ) . . . )(( . . . )(1 . ..21 E ：EFnF FnFF ??? 形式的選擇變成選擇串接的???⑵ 對每個選擇，盡可能地將選擇向樹的葉端移動。 ⑶ 對每個投影，盡可能地向樹的葉端移動。 說明：過程中可能使某些投影操作消失；也可能把一個投影分成兩個，其中一個將 靠近葉端；也可能消去該投影操作。 ⑷ 把選擇和投影合并成單個選擇、單個投影或一個選擇后跟一個投影。 ⑸ 將上述步驟得到的語法樹的內結點分組。 ⑹ 產生一個程序，上述每一組是這程序的一步，且先執(zhí)行后代結點組。 優(yōu)化算法 (3) 例 對于如下關系數(shù)據(jù)庫： S（ S， SNAME， AGE， SEX） SC（ S， C， GRADE） C（ C， CNAME， TEACHER） 現(xiàn)有一個查詢語句：檢索至少學習 LIU老師所授一門課程的女生的學號和姓名。該查詢語句的關系代數(shù)表達式如下： CFS E XL I UT E A C H E RS N A M ES (( 39。39。39。39。, ????? SC S)) 也可以得下式 : ))))(((( ....39。39。39。39。, SSCCSSSSCCSCCCLFSEXL I UT E A C H E RS N A M ES ???????? ????,SNAME L π σ π σ C SC S TEACHER=‘LIU’∧ SEX=‘F’ ,CNAME,TEACHER, GRADE,SNAME,AGE,SEX =∧ = 語法樹 優(yōu)化算法 (4) (1)將每個選擇操作分裂成兩個選擇運算 : ....39。39。39。39。SSSSCCSCCCFSE XLIUTE A C H E R????????(2)將四個選擇操作盡可能向樹的葉端靠攏， 并把兩個投影合并為一個投影。 見圖 過程中的語法樹 (3)把投影和選擇進行交換，并在 σ 前增加一個投影操作。 SNAM ESSSSC ,.,.?SNAMESS ,.?.. SSSSC ??新增加的投影 S N A M E,S.SS C . S ?? 和分解成π σ σ σ C SC ， SNAME = = SEX=‘F’ TEACHER=‘LIU’ σ S 優(yōu)化算法 (5) C = SEX=‘F’ σ S π σ σ SC = TEACHER=‘LIU’ π σ ， SNAME ,SNAME .SSC?SNAMESS ,.?做投影 做投影 .,.,. CSCSSCCC?.SSC?.. CSCCC ??SNAMESS ,.?SEXSNAMES ,?39。39。FSEX??再把該投影往葉端移 優(yōu)化算法 (6) = ,SNAME’ π SEX=‘F’ = (4) 執(zhí)行時從葉端以次向上進行，每組運算只對關系一次掃描 。 優(yōu)化的語法樹及其分組 C π σ π π π σ ， SNAME σ σ S TEACHER=‘LIU’ SC ,
醫(yī)療健康相關推薦
鄂ICP備17016276號-1