掌握關(guān)系系統(tǒng)的有關(guān)概念、了解全關(guān)系系統(tǒng)的十二條基本課件

1、1、掌握關(guān)系系統(tǒng)的有關(guān)概念2、了解全關(guān)系系統(tǒng)的十二條基本準(zhǔn)則3、掌握查詢優(yōu)化的一般策略4、掌握關(guān)系代數(shù)的等價(jià)變換規(guī)則5、掌握關(guān)系代數(shù)表達(dá)式的優(yōu)化算法和優(yōu)化的一般步驟本章要求：本章內(nèi)容：請(qǐng)選擇內(nèi)容返回1 關(guān)系系統(tǒng)2 關(guān)系系統(tǒng)的查詢優(yōu)化7/24/20221數(shù)據(jù)庫(kù)系統(tǒng)一、關(guān)系系統(tǒng)的定義1、關(guān)系模型： 數(shù)據(jù)結(jié)構(gòu)： 關(guān)系（二維表） 數(shù)據(jù)操縱： 關(guān)系代數(shù)（或關(guān)系演算） 完整性約束：實(shí)體完整性、參照完整性、用戶定義的完整性2、關(guān)系系統(tǒng)的定義 關(guān)系系統(tǒng)是關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的簡(jiǎn)稱 從概念上講，支持關(guān)系模型的系統(tǒng)稱為關(guān)系系統(tǒng)。 一個(gè)系統(tǒng)稱為關(guān)系系統(tǒng)，當(dāng)且僅當(dāng)（1）支持關(guān)系數(shù)據(jù)結(jié)構(gòu)；（2）支持選擇、投影和連接運(yùn)算。 對(duì)

2、運(yùn)算不要求定義任何物理存取路徑。1 關(guān)系系統(tǒng)要求過(guò)于嚴(yán)格 按最小要求定義關(guān)系系統(tǒng)：7/24/20222數(shù)據(jù)庫(kù)系統(tǒng)二、關(guān)系系統(tǒng)的分類 按對(duì)關(guān)系模型的支持程度來(lái)分SMI數(shù)據(jù)操縱完整性結(jié)構(gòu)1、表式系統(tǒng) 僅支持關(guān)系結(jié)構(gòu)， 不支持集合級(jí)操作SMIS如：倒排表7/24/20223數(shù)據(jù)庫(kù)系統(tǒng)SMIS2、（最?。╆P(guān)系系統(tǒng) 支持關(guān)系結(jié)構(gòu)， 支持選擇、投影和連接運(yùn)算M3、關(guān)系上完備的系統(tǒng) 支持關(guān)系結(jié)構(gòu)， 支持所有的關(guān)系代數(shù)操作SMISMM如：SYBASE、ORACLE、DB2如：FoxBASE、FoxPro7/24/20224數(shù)據(jù)庫(kù)系統(tǒng)4、全關(guān)系系統(tǒng) 支持關(guān)系模型的所有特征 SYBASE、ORACLE、DB2等系

3、統(tǒng)已接近這個(gè)目標(biāo)SMISMSI三、全關(guān)系系統(tǒng)的十二條基本準(zhǔn)則基礎(chǔ)（準(zhǔn)則 0）：關(guān)系型DBMS必須能完全通過(guò)它的關(guān)系能 力來(lái)管理數(shù)據(jù)庫(kù)在關(guān)系一級(jí)上支持?jǐn)?shù)據(jù)的插入、刪除、修改，沒有任何操作必須通過(guò)非關(guān)系的能力才能實(shí)現(xiàn)7/24/20225數(shù)據(jù)庫(kù)系統(tǒng)準(zhǔn)則1：信息準(zhǔn)則。邏輯上可用一種方法（表中的值）來(lái)表示 所有信息。用戶數(shù)據(jù)、元數(shù)據(jù)、索引、應(yīng)用元數(shù)據(jù)統(tǒng)一用表格來(lái)表示好處： 提高用戶生產(chǎn)率 便于DBA維護(hù)數(shù)據(jù)庫(kù) 便于與其它軟件接口準(zhǔn)則2：保證訪問(wèn)準(zhǔn)則。依靠表名、主鍵、列名的組合，保證 能以邏輯方式（而不是物理方式）訪 問(wèn)到每一個(gè)數(shù)據(jù)項(xiàng)。準(zhǔn)則3：空值的系統(tǒng)化處理。好處： 完善完整性約束 對(duì)庫(kù)函數(shù)計(jì)算的準(zhǔn)確性

4、極為重要7/24/20226數(shù)據(jù)庫(kù)系統(tǒng)準(zhǔn)則5：統(tǒng)一的數(shù)據(jù)子語(yǔ)言準(zhǔn)則。 一種語(yǔ)言全面支持以下功能： 數(shù)據(jù)定義、視圖定義 數(shù)據(jù)操作 完整性約束 授權(quán) 事務(wù)處理功能準(zhǔn)則4：基于關(guān)系模型的動(dòng)態(tài)的聯(lián)機(jī)數(shù)據(jù)字典。 數(shù)據(jù)庫(kù)自身的描述（元數(shù)據(jù)）也用關(guān)系，且授權(quán)用戶 也可以查詢。好處： 學(xué)習(xí)簡(jiǎn)單 授權(quán)用戶可擴(kuò)充數(shù)據(jù)字典7/24/20227數(shù)據(jù)庫(kù)系統(tǒng)準(zhǔn)則6：視圖更新準(zhǔn)則。所有理論上可更新的視圖也應(yīng)該允許 由系統(tǒng)更新。提高邏輯獨(dú)立性準(zhǔn)則7：高級(jí)的插入、修改、刪除操作。把一個(gè)基本關(guān)系或?qū)?出關(guān)系作為單一的操作對(duì)象進(jìn)行處理。好處： 簡(jiǎn)化用戶操作 便于系統(tǒng)優(yōu)化 便于分布式處理準(zhǔn)則8：數(shù)據(jù)物理獨(dú)立性。準(zhǔn)則9：數(shù)據(jù)邏輯獨(dú)立性

5、。準(zhǔn)則10：數(shù)據(jù)完整性的獨(dú)立性。 完整性約束條件必須是用數(shù)據(jù)子語(yǔ)言定義并存儲(chǔ)在數(shù) 據(jù)字典中。7/24/20228數(shù)據(jù)庫(kù)系統(tǒng)準(zhǔn)則11：分布獨(dú)立性。 數(shù)據(jù)子語(yǔ)言能使應(yīng)用程序和終端活動(dòng)在下列情況下保持 邏輯不變性： 首次分布數(shù)據(jù)時(shí)； 數(shù)據(jù)重新分布時(shí)。準(zhǔn)則12：無(wú)破壞準(zhǔn)則。 如果一個(gè)關(guān)系系統(tǒng)具有一個(gè)低級(jí)（指一次一記錄）語(yǔ)言， 則這個(gè)低級(jí)語(yǔ)言不能違背或繞過(guò)完整性準(zhǔn)則。E. F. Codd提出的12條準(zhǔn)則本節(jié)開頭下一節(jié)本章開頭7/24/20229數(shù)據(jù)庫(kù)系統(tǒng) 關(guān)系數(shù)據(jù)語(yǔ)言只需用戶指出“干什么”，不必指出“怎么干”，為什么能做到這一點(diǎn)？ 一個(gè)重要原因就是系統(tǒng)能自動(dòng)進(jìn)行查詢優(yōu)化。查詢優(yōu)化的總目標(biāo)： 選擇有效的策

6、略，求得給定的關(guān)系表達(dá)式的值。一、為什么要進(jìn)行查詢優(yōu)化？ 例：求選修了課程C2的學(xué)生姓名SELECT S.SNFROM S, SCWHERE S.S# = SC.S# AND SC.C# = C2;2 關(guān)系系統(tǒng)的查詢優(yōu)化7/24/202210數(shù)據(jù)庫(kù)系統(tǒng)也可用SQL語(yǔ)言如下實(shí)現(xiàn):SELECT SNFROM SWHERE S.S# IN ( SELECT SC.S# FROM SC WHERE C# = C2 ) ; 對(duì)于一個(gè)復(fù)雜的查詢，不同的用戶可能會(huì)寫出許許多多不同的查詢方法。這些方法有的簡(jiǎn)單，有的復(fù)雜。它們的執(zhí)行結(jié)果是一樣的，但執(zhí)行效率可能是不一樣的。系統(tǒng)能解決這一問(wèn)題嗎？7/24/2022

7、11數(shù)據(jù)庫(kù)系統(tǒng) 對(duì)這一查詢，可以考慮下面幾種實(shí)現(xiàn)方式：1、先求S和SC的笛卡爾積，然后從中選出兩學(xué)號(hào)字段值相等、 課程號(hào)為C2的元組：Q1 = （ （SSC）SN S.S#=SC.S# SC.C#=C22、先做S和SC的自然連接，然后從中選出課程號(hào)為C2的元組：Q2 = （ （S SC）SN SC.C#=C23、先從SC中選出課程號(hào)為C2的元組，然后將該結(jié)果與S 連接：Q3 = （S （SC）SN SC.C#=C27/24/202212數(shù)據(jù)庫(kù)系統(tǒng) 分析三種實(shí)現(xiàn)策略的執(zhí)行時(shí)間：設(shè)有1000學(xué)生記錄，10000選課記錄，選修C2課程的學(xué)生有50名。1、第一種策略：Q1 = （ （SSC）SN S.

8、S#=SC.S# SC.C#=C2（1）計(jì)算廣義笛卡爾積 SSC： 執(zhí)行方式：讀S表讀SC表S1 A CS 20S2 B CS 21S3 C MA 19S4 D CI 19S5 E MA 22S6 F CS 19S1 C1 AS1 C2 AS1 C3 A每次讀若干塊每次讀一塊SSC存于臨時(shí)文件中S1 A CS 20 S1 C1 AS1 A CS 20 S1 C2 AS1 A CS 20 S1 C3 AS2 B CS 21 S1 C1 AS2 B CS 21 S1 C2 AS2 B CS 21 S1 C3 A S6 F CS 19 S1 C1 AS6 F CS 19 S1 C2 AS6 F CS

9、 19 S1 C3 A7/24/202213數(shù)據(jù)庫(kù)系統(tǒng)讀S表讀SC表S1 A CS 20S2 B CS 21S3 C MA 19S4 D CI 19S5 E MA 22S6 F CS 19S1 C1 AS1 C2 AS1 C3 ASSC存于臨時(shí)文件中S1 A CS 20 S1 C1 AS1 A CS 20 S1 C2 AS1 A CS 20 S1 C3 AS2 B CS 21 S1 C1 AS2 B CS 21 S1 C2 AS2 B CS 21 S1 C3 A S6 F CS 19 S1 C1 AS6 F CS 19 S1 C2 AS6 F CS 19 S1 C3 AS1 C5 BS2 C1

10、 BS2 C2 C讀下一塊S1 A CS 20 S1 C5 BS1 A CS 20 S2 C1 BS1 A CS 20 S2 C2 C 相當(dāng)于外循環(huán)相當(dāng)于內(nèi)循環(huán)7/24/202214數(shù)據(jù)庫(kù)系統(tǒng) 設(shè)一塊能裝10個(gè)學(xué)生記錄或100個(gè)選課記錄，每次在內(nèi)存中存放5塊S的元組、1塊SC的元組，則S表和SC表的總塊數(shù)各為100。外循環(huán)一次，內(nèi)循環(huán)20次，要讀取的總塊數(shù)為 100 + 10020 = 2100塊連接后的元組數(shù)為 1000 10000 = 1千萬(wàn)，設(shè)每塊能裝10個(gè)元組，則 S SC的總塊數(shù)為1百萬(wàn)塊 設(shè)每秒能讀寫20塊，則讀的時(shí)間：2100塊 20塊/秒 = 105秒寫的時(shí)間：1000000塊

11、 20塊/秒 = 50000秒（2）依次讀入S SC的元組，然后執(zhí)行選擇：讀的時(shí)間：1000000塊 20塊/秒 = 50000秒滿足條件的元組50個(gè)，設(shè)全部放入內(nèi)存（不再臨時(shí)存儲(chǔ)）7/24/202215數(shù)據(jù)庫(kù)系統(tǒng)（3）在上步基礎(chǔ)上執(zhí)行投影得最終結(jié)果（此步時(shí)間不計(jì)）。第一種策略的總時(shí)間為： 105 + 50000 + 50000 10萬(wàn)秒（近28小時(shí)）Q2 = （ （S SC）SN SC.C#=C22、第二種策略（1）計(jì)算自然連接 讀取S表和SC表的策略不變，執(zhí)行時(shí)間還是105秒。 因?yàn)镾C表中的每一個(gè)學(xué)號(hào)都在S表中出現(xiàn)，而S表中無(wú)重復(fù)學(xué)號(hào)，故連接后的表和SC表的行數(shù)一樣，為10000行，將它

12、們臨時(shí)存入盤中需 （10000 10）塊 20塊/秒 = 50秒計(jì)算自然連接需時(shí)：105 + 50 = 155秒7/24/202216數(shù)據(jù)庫(kù)系統(tǒng)（2）執(zhí)行選擇運(yùn)算主要為讀取中間文件的時(shí)間：為50秒（3）把上一步結(jié)果投影，時(shí)間忽略不計(jì)第二種策略的總時(shí)間為： 155 + 50 = 205秒Q3 = （S （SC）SN SC.C#=C23、第三種策略（1）先對(duì)SC表作選擇 只需讀一遍SC表，需時(shí) 100塊 20塊/秒 = 5秒 中間結(jié)果只有50個(gè)記錄，不需使用中間文件（2）作自然連接 只需讀一遍S表，邊讀邊和內(nèi)存中的中間結(jié)果連接，結(jié)果仍為50個(gè)元組需時(shí) 5秒7/24/202217數(shù)據(jù)庫(kù)系統(tǒng)（3）把上

13、一步結(jié)果投影，時(shí)間忽略不計(jì)第三種策略的總時(shí)間為： 5 + 5 = 10秒結(jié)論：不同的查詢策略其執(zhí)行時(shí)間可能差別很大二、優(yōu)化的一般策略好處：減少下一步運(yùn)算的數(shù)據(jù)量1、選擇、投影運(yùn)算應(yīng)盡可能先做2、把選擇和投影運(yùn)算同時(shí)進(jìn)行好處：減少掃描關(guān)系的次數(shù) （ （S ）SN SD=CSS1 A CS 20S2 B CS 21S3 C MA 19S4 D CI 22表S S# SN SD SA 7/24/202218數(shù)據(jù)庫(kù)系統(tǒng)3、在執(zhí)行連接前對(duì)文件適當(dāng)?shù)仡A(yù)處理例如：計(jì)算 S SCSC：S# C# GS4 C3 BS1 C2 AS1 C5 BS6 C4 AS2 C1 BS5 C3 BS2 C2 CS1 C1 A

14、S2 C4 CS3 C2 BS1 C3 AS3 C3 CS4 C5 DS5 C2 CS3 C4 BS5 C5 BS6 C5 AS： S# SN SD SAS1 A CS 20S2 B CS 21S3 C MA 19S4 D CI 19S5 E MA 20S6 F CS 22執(zhí)行連接時(shí)，對(duì)S 表只需掃描一遍，但若S的元組不能整個(gè)放入內(nèi)存，則S需多少次讀入內(nèi)存，對(duì)SC表就要掃描多少遍7/24/202219數(shù)據(jù)庫(kù)系統(tǒng)SC：S# C# GS1 C1 AS1 C2 AS1 C3 AS1 C5 BS2 C1 BS2 C2 CS2 C4 CS3 C2 BS3 C3 CS3 C4 BS4 C3 BS4 C5

15、DS5 C2 CS5 C3 BS5 C5 BS6 C4 AS6 C5 AS： S# SN SD SAS1 A CS 20S2 B CS 21S3 C MA 19S4 D CI 19S5 E MA 20S6 F CS 22 若對(duì)S表和SC表按連接字段先排序或索引，效果如何？對(duì)S表和SC表都只需一遍掃描效率就是高！7/24/202220數(shù)據(jù)庫(kù)系統(tǒng)4、把投影同其前或其后的雙目運(yùn)算結(jié)合起來(lái) （S SC）S#，SN，C#，G 如：每形成一個(gè)連接后的元組，就立即取出投影字段。而不是先連接形成一個(gè)臨時(shí)關(guān)系，然后在再此臨時(shí)關(guān)系上投影。又如：每取出S的一個(gè)元組，先取出投影字段，然后與SC進(jìn)行連接（ （ S）S#

16、，SN SC5、把某些選擇和笛卡爾乘積結(jié)合起來(lái)成為連接運(yùn)算6、找出公共子表達(dá)式7/24/202221數(shù)據(jù)庫(kù)系統(tǒng)三、關(guān)系代數(shù)等價(jià)變換規(guī)則設(shè)E、E1、E2是關(guān)系代數(shù)表達(dá)式。1、關(guān)系代數(shù)表達(dá)式的等價(jià) 若用相同的關(guān)系代替E1、E2中相應(yīng)的關(guān)系變量后所得的結(jié)果關(guān)系相同，則稱E1、E2等價(jià)，記作 E1 E2。2、一元運(yùn)算的串接定律（冪等律） （1）投影的串接定律 （ （E） （E）A1,A2,AnA1,A2,AnB1,B2,Bm其中A1,A2,An B1,B2,Bm7/24/202222數(shù)據(jù)庫(kù)系統(tǒng)圖示：B1B2B3B4A1A2A3 A1A2A3（2）選擇的串接定律 （ （E） （E）F1F2F1F27/2

17、4/202223數(shù)據(jù)庫(kù)系統(tǒng)3、二元運(yùn)算的交換律笛卡爾積： E1E2 E2E1自然連接： E1 E2 E2 E1連 接： E1 E2 E2 E1FF4、二元運(yùn)算的結(jié)合律笛卡爾積： （E1E2） E3 E1（E2 E3） 自然連接： （ E1 E2） E3 E1 （E2 E3）自然連接： （ E1 E2） E3 E1 （E2 E3）F1F2F1F27/24/202224數(shù)據(jù)庫(kù)系統(tǒng)5、兩個(gè)運(yùn)算間的交換律（1）選擇和投影： （ （E） （ （E）A1,A2,AnA1,A2,AnFFA1A2A3先投影后選擇A1A2A3先選擇后投影結(jié)果相同其中F只涉及A1,A2,An的屬性7/24/202225數(shù)據(jù)庫(kù)系統(tǒng)

18、若F中有不屬于A1,A2,An的屬性B1,B2,Bm，則 （ （E）A1,A2,AnF無(wú)意義，但根據(jù)投影的串接定律和上面的投影與選擇的交換律，有： （ （E）A1,A2,AnF （ （ （E）A1,A2,AnA1,A2,An ,B1,B2,BmF （ （ （E）A1,A2,AnA1,A2,An , B1,B2,BmF（2） 選擇與笛卡爾積若F只涉及到E1中的屬性，則 （E1E2） （E1） E2FF7/24/202226數(shù)據(jù)庫(kù)系統(tǒng)6、一元運(yùn)算對(duì)二元運(yùn)算的分配律（1）選擇對(duì)笛卡爾積的分配律 若F=F1F2，F(xiàn)1只涉及E1中的屬性，F(xiàn)2只涉及E2中的屬性，則 （E1E2） （E1） （ E2）FF

19、1F2如： （SSC）SD=CSG=A （S） （ SC）SD=CSG=A笛卡爾積S表S1 A CS 20S2 B MA 21S3 C CS 19SC表S1 C1 AS1 C2 AS2 C2 AS3 C1 BS3 C3 AS1 A CS 20 S1 C1 AS1 A CS 20 S1 C2 AS1 A CS 20 S2 C2 AS1 A CS 20 S3 C1 BS1 A CS 20 S3 C3 AS2 B MA 21 S1 C1 AS2 B MA 21 S1 C2 AS2 B MA 21 S2 C2 AS2 B MA 21 S3 C1 BS2 B MA 21 S3 C3 AS3 C CS 1

20、9 S1 C1 AS3 C CS 19 S1 C2 AS3 C CS 19 S2 C2 AS3 C CS 19 S3 C1 BS3 C CS 19 S3 C3 A7/24/202227數(shù)據(jù)庫(kù)系統(tǒng)（2）投影對(duì)笛卡爾積的分配律 （E1E2）A1,A2,An, B1,B2,Bm其中A1,A2,An是E1的屬性, B1,B2,Bm是E2的屬性。（3）選擇對(duì)連接的分配律若F=F1F2，F(xiàn)1只涉及E1的屬性，F(xiàn)2只涉及E2的屬性，則 （E1 E2） （E1） （ E2）FF1F2F3F3 （E1） （E2）A1,A2,AnB1,B2,Bm （ （ E1） （ E2） （E1） （ E2）F3F1F1F2F

21、3F2 （E1 E2） （ （E1E2） （ （E1E2）FFF3F3F3F因?yàn)椋?/24/202228數(shù)據(jù)庫(kù)系統(tǒng) （ （S） （SC）SN,C#,GS.S#=SC.S#S#,SNS#,C#,G（4）投影對(duì)連接的分配律 （E1 E2）A1,A2,An, B1,B2,BmF （E1） （E2）A1,A2,AnB1,B2,BmF 其中F只涉及 A1,A2,An, B1,B2,Bm中的屬性 若F涉及A1,A2,An, B1,B2,Bm以外的屬性，可如下處理 （S SC）SN,C#,GS.S#=SC.S# （S SC）SN,C#,GS.S#=SC.S#S.S#,SN,SC.S#,C#,G此處投影可去掉

22、SC）7/24/202229數(shù)據(jù)庫(kù)系統(tǒng)（6）投影對(duì)并的分配律（5）選擇對(duì)并的分配律 （E1 E2） （E1） （ E2）FF F （E1E2）A1,A2,An （E1） （E2）A1,A2,AnA1,A2,An（7）選擇對(duì)差的分配律 （E1 E2） （E1） （ E2）FF F7/24/202230數(shù)據(jù)庫(kù)系統(tǒng)四、關(guān)系代數(shù)表達(dá)式的優(yōu)化1、語(yǔ)法樹 用來(lái)表示關(guān)系代數(shù)表達(dá)式的一棵樹，其內(nèi)結(jié)點(diǎn)表示一種運(yùn)算，葉結(jié)點(diǎn)表示一個(gè)關(guān)系。例： SELECT S.SNFROM S, SCWHERE S.S# = SC.S# AND SC.C# = C2;可轉(zhuǎn)化為如下關(guān)系運(yùn)算： Project (SN) (Restri

23、ct (SC.C#=C2) (Join (S.S#=SC.S#) (S，SC) ) )Project (SN)Restrict（SC.C#=C2）Join（S.S#=SC.S#）SSC語(yǔ)法樹7/24/202231數(shù)據(jù)庫(kù)系統(tǒng) 為簡(jiǎn)化優(yōu)化算法，可將關(guān)系代數(shù)運(yùn)算限制在“并、差、笛卡爾積、投影、選擇”五種基本運(yùn)算上。Project (SN)Restrict（SC.C#=C2）Join（S.S#=SC.S#）SSC規(guī)范化為SNSC.C#=C2S.S#=SC.S#SSC7/24/202232數(shù)據(jù)庫(kù)系統(tǒng)2、關(guān)系代數(shù)表達(dá)式的優(yōu)化算法輸入：一棵關(guān)系代數(shù)表達(dá)式的語(yǔ)法樹輸出：計(jì)算該表達(dá)式的程序利用選擇的串接定律，把

24、形如 （E）的式子變換為F1F2Fn （ （ （E）F1 F2Fn 對(duì)每一個(gè)選擇，利用“選擇的串接定律、選擇和投影的交換律、選擇對(duì)笛卡爾積的分配律、選擇對(duì)并的分配律、選擇對(duì)差的分配律”盡可能把它移到樹的葉端（1）分解選擇（2）選擇下移7/24/202233數(shù)據(jù)庫(kù)系統(tǒng) 對(duì)每一個(gè)投影，利用“投影的串接定律、選擇和投影的交換律、投影對(duì)笛卡爾積的分配律、投影對(duì)并的分配律”盡可能把它移到樹的葉端（3）投影下移 利用“投影的串接定律、選擇的串接定律、選擇和投影的交換律”把選擇和投影合并成單個(gè)選擇、單個(gè)投影、或選擇后跟投影等三種情況，使多個(gè)選擇和 / 或投影能同時(shí)執(zhí)行、或在一次掃描中完成（4）選擇、投影合并

25、7/24/202234數(shù)據(jù)庫(kù)系統(tǒng) 把上面得到的語(yǔ)法樹分組： 每個(gè)二元運(yùn)算和它的 一元直接祖先 為一組。若它的后代直到葉子全是一元運(yùn)算，則也將它們并入該組。 按照每組的求值應(yīng)在其后代組求值之后進(jìn)行的順序?yàn)槊拷M生成一個(gè)程序，以產(chǎn)生整個(gè)表達(dá)式的求值程序。（5）按點(diǎn)分組（每組只有一個(gè)二元運(yùn)算）（6）生成程序不超過(guò)別的二元運(yùn)算結(jié)點(diǎn) 但對(duì)于笛卡爾積，若后面（父結(jié)點(diǎn)）是不能與它結(jié)合為等值連接的選擇運(yùn)算時(shí)，其一直到葉子的一元運(yùn)算結(jié)點(diǎn)需單獨(dú)算一組。 7/24/202235數(shù)據(jù)庫(kù)系統(tǒng)例子：考慮由以下關(guān)系組成的圖書館數(shù)據(jù)庫(kù)BOOKS（TITLE，AUTHOR，PNAME，LC-NO）BORROWERS（NAME，A

26、DDR，CITY，CARD-NO）LOANS（CARD-NO，LC-NO，DATE）借書證號(hào)圖書編號(hào)查詢：找出2000年01月01日前借出書籍的書名和借書人姓名。借出日期用SQL 語(yǔ)言可如下表達(dá)： SELECT TITLE，NAME FROM BOOKS，BORROWERS，LOANS WHERE BOOKS.LC-NO=LOANS.LC-NO AND BORROWERS.CARD-NO=LOANS.CARD-NO AND DATE 2000-01-01;7/24/202236數(shù)據(jù)庫(kù)系統(tǒng)SELECT TITLE，NAMEFROM BOOKS，BORROWERS，LOANSWHERE BOOKS

27、.LC-NO=LOANS.LC-NO AND BORROWERS.CARD-NO=LOANS.CARD-NO AND DATE 2000-01-01;把上述SQL語(yǔ)句轉(zhuǎn)化為關(guān)系代數(shù)表達(dá)式：轉(zhuǎn)化為投影轉(zhuǎn)化為連接轉(zhuǎn)化為選擇 （TITLE，NAMEDATE2000-01-01（ BOOKS （ BORROWERS LOANS）7/24/202237數(shù)據(jù)庫(kù)系統(tǒng)若把連接用笛卡爾積來(lái)實(shí)現(xiàn)，上式變?yōu)椋篋ATE2000-01-01 （ BOOKS （ BORROWERS LOANS）BOOKS.LC-NO=LOANS.LC-NO ANDBORROWERS.CARD-NO=LOANS.CARD-NOTITLE，

28、AUTHOR，PNAME，LC-NO， （NAME，ADDR，CITY，CARD-NO，DATE （TITLE，NAME7/24/202238數(shù)據(jù)庫(kù)系統(tǒng)TITLE，NAMEDATE2000-01-01上述表達(dá)式的語(yǔ)法樹 LOANSBOOKS.LC-NO=LOANS.LC-NO ANDBORROWERS.CARD-NO=LOANS.CARD-NOTITLE，AUTHOR，PNAME，LC-NO，NAME，ADDR，CITY，CARD-NO，DATEBOOKSBORROWERS根據(jù)算法第1步，分解該選擇7/24/202239數(shù)據(jù)庫(kù)系統(tǒng)TITLE，NAMEDATE2000-01-01第1步優(yōu)化（分解

29、選擇）后的語(yǔ)法樹 LOANSBOOKS.LC-NO=LOANS.LC-NO TITLE，AUTHOR，PNAME，LC-NO，NAME，ADDR，CITY，CARD-NO，DATEBOOKSBORROWERSBORROWERS.CARD-NO=LOANS.CARD-NO分解之后選擇和投影可以交換7/24/202240數(shù)據(jù)庫(kù)系統(tǒng)TITLE，NAMEDATE2000-01-01選擇和投影交換后的語(yǔ)法樹 LOANSBOOKS.LC-NO=LOANS.LC-NO TITLE，AUTHOR，PNAME，LC-NO，NAME，ADDR，CITY，CARD-NO，DATEBOOKSBORROWERSBORR

30、OWERS.CARD-NO=LOANS.CARD-NODATE2000-01-01TITLE，AUTHOR，PNAME，LC-NO，NAME，ADDR，CITY，CARD-NO，DATEDATE2000-01-01根據(jù)算法第2步，該選擇可下移該選擇也可下移7/24/202241數(shù)據(jù)庫(kù)系統(tǒng)TITLE，NAME第2步優(yōu)化（選擇下移）后的語(yǔ)法樹 LOANSBOOKS.LC-NO=LOANS.LC-NO BOOKSBORROWERSBORROWERS.CARD-NO=LOANS.CARD-NOTITLE，AUTHOR，PNAME，LC-NO，NAME，ADDR，CITY，CARD-NO，DATEDATE2000-01-01 這兩個(gè)投影可以合并（串接）7/24/202242數(shù)據(jù)庫(kù)系統(tǒng)TITLE，NAME第4步優(yōu)化（合并投影）