補(bǔ)充查詢處理和查詢優(yōu)化

會(huì)計(jì)學(xué)1補(bǔ)充查詢處理和查詢優(yōu)化2一、查詢處理步驟

查詢處理分為4個(gè)階段，在處理過程中，一旦發(fā)現(xiàn)問題，則報(bào)告錯(cuò)誤，中止處理?！?關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理查詢處理的任務(wù)：

將用戶提交給RDBMS的查詢語(yǔ)句轉(zhuǎn)換為高效的執(zhí)行計(jì)劃（方案）。第1頁(yè)/共60頁(yè)3

詞法分析：識(shí)別出語(yǔ)句中的SQL關(guān)鍵字、屬性名、關(guān)系名、運(yùn)算符、常量等語(yǔ)言符號(hào)。語(yǔ)法分析：檢查語(yǔ)句是否符合SQL語(yǔ)法規(guī)則。(1)查詢分析第2頁(yè)/共60頁(yè)4語(yǔ)義檢查：根據(jù)數(shù)據(jù)字典，檢查語(yǔ)句中的數(shù)據(jù)庫(kù)對(duì)象，如屬性名、關(guān)系名等，是否有效。符號(hào)名轉(zhuǎn)換：將外部名轉(zhuǎn)換為內(nèi)部名。安全性檢查：檢查用戶是否有請(qǐng)求的存取權(quán)限。完整性檢查：檢查是否違反完整性約束。查詢樹轉(zhuǎn)換：用基于關(guān)系代數(shù)的查詢樹來表示查詢，查詢樹也叫語(yǔ)法分析樹。(2)查詢檢查第3頁(yè)/共60頁(yè)5(3)查詢優(yōu)化從多個(gè)可能的執(zhí)行方案中選擇一個(gè)執(zhí)行效率較高的方案。分為兩個(gè)層次。第4頁(yè)/共60頁(yè)6(4)查詢執(zhí)行依據(jù)查詢優(yōu)化得到的結(jié)果，生成執(zhí)行代碼，執(zhí)行之。代數(shù)優(yōu)化：按照一定的規(guī)則，改變代數(shù)表達(dá)式中關(guān)系操作的次序和組合，使執(zhí)行效率更高，又稱邏輯優(yōu)化。物理優(yōu)化：依據(jù)事先確定的策略，選擇底層存取路徑和算法。第5頁(yè)/共60頁(yè)7二、實(shí)現(xiàn)查詢操作的算法舉例1.選擇操作的實(shí)現(xiàn)Select*fromstudentwhere<條件表達(dá)式>；考慮<條件表達(dá)式>的幾種情況：C1:無條件；C2:Sno=‘200215121’；C3：Sage>20;C4:Sdept=‘CS’ANDSage>20;第6頁(yè)/共60頁(yè)8二、實(shí)現(xiàn)查詢操作的算法舉例1.選擇操作的實(shí)現(xiàn)(1)簡(jiǎn)單的全表掃描方法對(duì)查詢基本表順序掃描，逐一檢查每個(gè)元組是否滿足選擇的條件，對(duì)滿足條件的元組作為結(jié)果輸出。對(duì)于小表，簡(jiǎn)單有效。對(duì)于大表，費(fèi)時(shí)。(2)索引或散列掃描方法如果選擇條件中的屬性上有索引（B+樹索引或Hash索引），可以用索引掃描方法。通過索引先找到滿足條件的元組的主碼或元組指針，再通過元組指針直接在查詢的基本表中找到元組。第7頁(yè)/共60頁(yè)9二、實(shí)現(xiàn)查詢操作的算法舉例2.連接操作的實(shí)現(xiàn)Select*fromStudent,ScWhereStudent.Sno=SC.sno(1)嵌套循環(huán)方法

對(duì)于外層循環(huán)(Student)的每個(gè)元組(s),檢索內(nèi)層循環(huán)(SC)中的每個(gè)元組(sc)，并檢查這兩個(gè)元組在連接屬性(sno)上是否相等。如果滿足連接條件，則串接后作為結(jié)果輸出，直到外層循環(huán)表中的元組處理完為止。第8頁(yè)/共60頁(yè)10二、實(shí)現(xiàn)查詢操作的算法舉例(2)排序-合并方法

①如果連接的表沒有排好序，則將Student和SC表按連接屬性Sno排序；②取Student表中的第一個(gè)Sno，依次掃描SC表中具有相同Sno的元組，把它們連接起來；③當(dāng)掃描到Sno不相同的第一個(gè)SC元組時(shí)，返回Student表掃描下一個(gè)元組，再掃描SC表中具有相同Sno的元組，把它們連接起來。重復(fù)上述步驟直到Student表掃描完。第9頁(yè)/共60頁(yè)11二、實(shí)現(xiàn)查詢操作的算法舉例(3)索引連接方法①在SC表上建立屬性Sno的索引，如果原來沒有的話；②對(duì)Student表中的每一個(gè)元組，由Sno的值通過SC的索引查找相應(yīng)的SC元組；③把這些SC元組和Student元組連接起來。循環(huán)執(zhí)行②、③；直到Student表中的元組處理完為止。第10頁(yè)/共60頁(yè)12二、實(shí)現(xiàn)查詢操作的算法舉例(4)HashJoin方法把連接屬性作為hash碼，用同一個(gè)hash函數(shù)把R和S中的元組散列到同一個(gè)hash文件中。劃分階段：對(duì)包含較少元組的表(比如R)進(jìn)行一遍處理，把它的元組按hash函數(shù)分散到hash表的桶中；試探階段：對(duì)另一個(gè)表(S)進(jìn)行一遍處理，把S的元組散列到適當(dāng)?shù)膆ash桶中，并將元組與桶中所有來自R并與之匹配的元組連接起來。第11頁(yè)/共60頁(yè)13§2關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化

關(guān)系數(shù)據(jù)語(yǔ)言只需用戶提出“做什么”，不必指出“怎么做”，為什么能做到這一點(diǎn)？一個(gè)重要原因就是系統(tǒng)能自動(dòng)進(jìn)行查詢優(yōu)化。系統(tǒng)自動(dòng)優(yōu)化比用戶自己優(yōu)化會(huì)做得更好，見P267。在集中式數(shù)據(jù)庫(kù)中，查詢執(zhí)行的總代價(jià)(開銷)為：總代價(jià)=I/O代價(jià)+CPU代價(jià)+內(nèi)存代價(jià)三者中，I/O代價(jià)是最主要的。查詢優(yōu)化的總目標(biāo)：選擇有效的策略，求得給定的關(guān)系表達(dá)式的值，使得查詢代價(jià)較小。第12頁(yè)/共60頁(yè)14例：求選修了2號(hào)課程的學(xué)生姓名。其SQL語(yǔ)句為：SELECT姓名FROMStudent,SCWHEREStudent.學(xué)號(hào)=SC.學(xué)號(hào)AND課號(hào)=‘2’;為什么要進(jìn)行查詢優(yōu)化？也可用SQL語(yǔ)言如下實(shí)現(xiàn):SELECT姓名FROMStudentWHERE學(xué)號(hào)IN(SELECT學(xué)號(hào)FROMSCWHERE課號(hào)=‘2’);第13頁(yè)/共60頁(yè)15

對(duì)于一個(gè)復(fù)雜的查詢，不同用戶可能會(huì)寫出各種不同的查詢方法。這些方法有的簡(jiǎn)單，有的復(fù)雜。它們的執(zhí)行結(jié)果是一樣的，但執(zhí)行效率可能是不一樣的。系統(tǒng)能解決這一問題嗎？第14頁(yè)/共60頁(yè)16對(duì)這一查詢，可以考慮下面幾種實(shí)現(xiàn)方式：1、先求Student和SC的笛卡爾積，然后從中選出兩學(xué)號(hào)字段值相等、課程號(hào)為2的元組，再投影姓名。Q1=姓名(Student.學(xué)號(hào)=SC.學(xué)號(hào)∧課號(hào)=‘2’(StudentSC))2、先做Student和SC的自然連接，然后從中選出課程號(hào)為2的元組，再投影姓名。Q2=姓名（課號(hào)=‘2’

（Student∞SC））3、先從SC中選出課程號(hào)為2的元組，然后將該結(jié)果與Student連接，再投影姓名。Q3=姓名（Student∞課號(hào)=‘2’

（SC））第15頁(yè)/共60頁(yè)17分析三種實(shí)現(xiàn)策略的執(zhí)行時(shí)間：

設(shè)有1000個(gè)學(xué)生記錄，10000個(gè)選課記錄，選修2號(hào)課程的學(xué)生有50名。1、第一種策略：Q1=姓名(Student.學(xué)號(hào)=SC.學(xué)號(hào)∧課號(hào)=‘2’(StudentSC))（1）計(jì)算廣義笛卡爾積StudentSC：

執(zhí)行方式：讀Student若干塊和SC的1塊到內(nèi)存，然后執(zhí)行連接，結(jié)果裝滿1塊后就立即寫入磁盤的臨時(shí)文件中，當(dāng)內(nèi)存中的Student記錄與SC記錄全部連接后，再讀入SC的下一塊，繼續(xù)連接，直到SC的所有記錄與內(nèi)存中的Student都連接，再讀入Student的另若干塊，重復(fù)上面的過程。第16頁(yè)/共60頁(yè)18

設(shè)一塊能裝10個(gè)Student記錄或100個(gè)SC記錄。則Student的總塊數(shù)為1000/10=100塊，SC的總塊數(shù)為10000/100=100塊若每次在內(nèi)存中裝入5塊Student記錄和1塊SC的記錄，則Student被讀取1遍，SC被讀取100/5=20遍。讀取兩表的總塊數(shù)為

100+10020=2100塊連接結(jié)果為1000*10000=10000000個(gè)記錄，若每塊可裝10個(gè)結(jié)果記錄，共需寫入磁盤10000000/10=1000000塊。若每秒可讀寫20塊，則讀、寫總時(shí)間分別為：

2100/20=105秒1000000/20=50000秒第17頁(yè)/共60頁(yè)19（2）依次讀入StudentSC的記錄，然后執(zhí)行選擇。讀的時(shí)間：1000000/20=50000秒滿足條件的記錄為50個(gè)，全部放入內(nèi)存，不再臨時(shí)存儲(chǔ)。（3）在上步基礎(chǔ)上執(zhí)行投影得最終結(jié)果（此步時(shí)間不計(jì)）。第一種策略的總時(shí)間為：105+50000+5000010萬秒（近28小時(shí)）第18頁(yè)/共60頁(yè)202、第二種策略（1）計(jì)算自然連接讀取Student表和SC表的策略不變，執(zhí)行時(shí)間還是2100/20=105秒。因?yàn)镾C表中的每一個(gè)學(xué)號(hào)都在Student表中出現(xiàn)，而Student表中無重復(fù)學(xué)號(hào)，故連接后的結(jié)果和SC表的行數(shù)一樣，為10000行，將它們臨時(shí)存入盤中需（10000/10）塊/20塊/秒=50秒計(jì)算自然連接需時(shí)：105+50=155秒Q2=姓名（課號(hào)=‘2’

（Student∞SC））第19頁(yè)/共60頁(yè)21（2）執(zhí)行選擇運(yùn)算將存儲(chǔ)在磁盤上臨時(shí)文件中的自然連接結(jié)果，讀入內(nèi)存進(jìn)行選擇，結(jié)果為50個(gè)記錄，不再臨時(shí)存儲(chǔ)。主要為讀取自然連接結(jié)果的時(shí)間：為50秒（3）把上一步結(jié)果投影，時(shí)間忽略不計(jì)第二種策略的總時(shí)間為：155+50=205秒第20頁(yè)/共60頁(yè)223、第三種策略（1）先對(duì)SC表作選擇只需讀一遍SC表，需時(shí)100塊

/20塊/秒=5秒中間結(jié)果只有50個(gè)記錄，不需使用中間文件（2）作自然連接只需讀一遍Student表，邊讀邊和內(nèi)存中的中間結(jié)果連接，結(jié)果仍為50個(gè)元組，需時(shí)5秒Q3=姓名（Student∞課號(hào)=‘2’

（SC））（3）把上一步結(jié)果投影，時(shí)間忽略不計(jì)第三種策略的總時(shí)間為：5+5=10秒結(jié)論：不同的查詢策略其執(zhí)行時(shí)間可能差別很大第21頁(yè)/共60頁(yè)23說明：剛才使用的是全表掃描的方法，比較費(fèi)時(shí)，如果在選擇字段和連接字段上建立了適當(dāng)?shù)乃饕涂梢詼p少記錄的讀取量，從而降低查詢開銷。這就是存取路徑選擇問題，由物理優(yōu)化解決。第22頁(yè)/共60頁(yè)24總結(jié)：通過剛才的例子可知，前兩種策略的中間結(jié)果集（笛卡爾積和自然連接）包含了許多對(duì)查詢結(jié)果無用的記錄，造成結(jié)果集太大，不得不進(jìn)行磁盤緩存處理，從而使得花費(fèi)時(shí)間較多。由此啟發(fā)我們，在查詢處理時(shí)，應(yīng)盡可能早地去掉對(duì)查詢結(jié)果沒有用的數(shù)據(jù)（記錄或字段），以降低中間結(jié)果集的規(guī)模，這可通過優(yōu)先執(zhí)行一元運(yùn)算（選擇和投影）來實(shí)現(xiàn)，象第三種策略那樣。第23頁(yè)/共60頁(yè)25§3代數(shù)優(yōu)化一、關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則

設(shè)E1、E2是關(guān)系代數(shù)表達(dá)式。若用相同的關(guān)系代替E1、E2中相應(yīng)的關(guān)系所得到的結(jié)果相同，則稱E1、E2等價(jià)，記作E1

E2。1、投影的串接定律（冪等律）A1,A2,…,An(B1,B2,…,Bm(E))A1,A2,…,An(E)

其中{A1,A2,…,An}{B1,B2,…,Bm}例：姓名

(學(xué)號(hào)，姓名

(Student))姓名

(Student)第24頁(yè)/共60頁(yè)262、選擇的串接定律（冪等律）F1

（F2

（E））F1F2

（E）性別=‘男’

(年齡>20(Student))性別=‘男’年齡>20(Student)第25頁(yè)/共60頁(yè)273、連接、笛卡爾積的交換律笛卡爾積：E1E2E2E1自然連接：E1∞E2E2∞E1一般連接：E1∞E2E2∞E1FF4、連接、笛卡爾積的結(jié)合律笛卡爾積：(E1E2)E3E1(E2E3)自然連接：(E1∞E2)

∞E3E1∞(E2∞E3)一般連接：(E1∞E2)

∞E3E1∞(E2∞E3)F1F2F1F2第26頁(yè)/共60頁(yè)285、選擇與投影的交換律F(A1,A2,…,An(E))A1,A2,…,An(F(E))其中F只涉及A1,A2,…,An中的屬性例：性別=‘男’

(學(xué)號(hào)，姓名，性別

(Student))學(xué)號(hào)，姓名，性別

(性別=‘男’

(Student))若F中有不屬于A1,A2,…,An的屬性B1,B2,…,Bm，則A1,A2,…,An(F(E))A1,A2,…,An(A1,A2,…,An,B1,B2,…,Bm(F(E)))A1,A2,…,An(F(A1,A2,…,An,B1,B2,…,Bm(E)))第27頁(yè)/共60頁(yè)29例：學(xué)號(hào)，姓名(性別=‘男’

(Student))學(xué)號(hào)，姓名性別=‘男’

(學(xué)號(hào)，姓名，性別

(Student))第28頁(yè)/共60頁(yè)306、選擇與笛卡爾積的交換律（分配律）

設(shè)F=F1∧F2∧F3，其中F1只涉及E1中的屬性，F(xiàn)2只涉及E2中的屬性，F(xiàn)3涉及E1和E2兩者中的屬性，則F(E1×E2)F3(F1E1×F2E2)如果某個(gè)Fi不存在，則去掉相應(yīng)的Fi。例：Student.學(xué)號(hào)=SC.學(xué)號(hào)∧成績(jī)<60(Student×SC)Student.學(xué)號(hào)=SC.學(xué)號(hào)(Student

×成績(jī)<60SC)第29頁(yè)/共60頁(yè)317、選擇對(duì)自然連接的分配律

設(shè)F=F1∧F2，其中F1只涉及E1的屬性，F(xiàn)2只涉及E2的屬性，則F(E1∞E2)F1E1∞F2E2例：性別=‘男’∧成績(jī)>=90(Student

∞SC)性別=‘男’

Student

∞成績(jī)>=90SC8、選擇對(duì)并、交、差的分配律F(E1∪E2)FE1∪FE2F(E1∩E2)FE1∩FE2F(E1-E2)FE1-FE2第30頁(yè)/共60頁(yè)329、投影對(duì)笛卡爾積的分配律

設(shè)A1,A2,…，An是E1的屬性，B1,B2,…，Bm是E2的屬性，則A1,A2,…,An,B1,B2,…,Bm(E1×E2)A1,A2,…,AnE1×B1,B2,…,BmE210、投影對(duì)并、交、差的分配律A(E1∪E2)AE1∪AE2A(E1∩E2)AE1∩AE2A(E1-E2)AE1-AE2第31頁(yè)/共60頁(yè)33二、查詢樹的啟發(fā)式優(yōu)化1、啟發(fā)式規(guī)則（1）一元運(yùn)算應(yīng)盡可能先做。這樣可及時(shí)丟掉對(duì)查詢結(jié)果無用的記錄或字段，極大地減小中間結(jié)果集。（2）將選擇、投影及其前后的笛卡爾積、連接運(yùn)算同時(shí)進(jìn)行。這樣可減少對(duì)關(guān)系的掃描遍數(shù)和中間結(jié)果的存儲(chǔ)量。（3）找出公共子表達(dá)式，將計(jì)算結(jié)果臨時(shí)保存，再遇到該表達(dá)式時(shí)，不再計(jì)算，直接使用保存的結(jié)果。第32頁(yè)/共60頁(yè)342、關(guān)系代數(shù)語(yǔ)法樹

用來表示關(guān)系代數(shù)表達(dá)式的一棵樹，其內(nèi)結(jié)點(diǎn)表示一種運(yùn)算，葉結(jié)點(diǎn)表示一個(gè)關(guān)系。如：

SELECT姓名

FROMStudent，SCWHEREStudent.學(xué)號(hào)=SC.學(xué)號(hào)AND課號(hào)=‘2’；姓名Student.學(xué)號(hào)=SC.學(xué)號(hào)

∧課號(hào)=‘2’×StudentSC方法：將目標(biāo)列轉(zhuǎn)換為投影，將WHERE中的條件轉(zhuǎn)換為選擇，將FROM后的表用笛卡爾積連接起來。也可轉(zhuǎn)換為自然連接?！拚n號(hào)=‘2’第33頁(yè)/共60頁(yè)353、關(guān)系代數(shù)表達(dá)式的優(yōu)化算法輸入：一棵關(guān)系代數(shù)表達(dá)式的語(yǔ)法樹輸出：優(yōu)化的語(yǔ)法樹

利用選擇的串接定律，把形如F1F2Fn

（E）的式子變換為F1(F2((Fn(E)))（1）分解選擇第34頁(yè)/共60頁(yè)36

對(duì)每一個(gè)選擇，利用“選擇的串接定律、選擇與投影的交換律、選擇對(duì)笛卡爾積的分配律、選擇對(duì)自然連接的分配律、選擇對(duì)并、交、差的分配律”盡可能把它移到樹的葉端。（2）選擇下移第35頁(yè)/共60頁(yè)37

對(duì)每一個(gè)投影，利用“投影的串接定律、選擇與投影的交換律、投影對(duì)笛卡爾積的分配律、投影對(duì)并、交、差的分配律”盡可能把它移到樹的葉端。（3）投影下移（1）分解選擇（2）選擇下移第36頁(yè)/共60頁(yè)38

利用“投影的串接定律、選擇的串接定律、選擇與投影的交換律”把選擇和投影合并成單個(gè)選擇、單個(gè)投影、或選擇后跟投影等三種情況，使多個(gè)選擇和/或投影能同時(shí)執(zhí)行、或在一次掃描中完成。（4）選擇、投影合并（3）投影下移（1）分解選擇（2）選擇下移第37頁(yè)/共60頁(yè)39

把上面得到的語(yǔ)法樹分組：每個(gè)二元運(yùn)算和它的一元直接祖先為一組。若它的后代直到葉子全是一元運(yùn)算，則也將它們并入該組。（5）按點(diǎn)分組（每組只有一個(gè)二元運(yùn)算）不超過別的二元運(yùn)算結(jié)點(diǎn)

但對(duì)于笛卡爾積，若后面（父結(jié)點(diǎn)）是不能與它結(jié)合為等值連接的選擇運(yùn)算時(shí)，其一直到葉子的一元運(yùn)算結(jié)點(diǎn)需單獨(dú)算一組。

第38頁(yè)/共60頁(yè)40例：考慮由以下關(guān)系組成的圖書館數(shù)據(jù)庫(kù)BOOKS（書名，作者，出版社，編號(hào)）BORROWERS（姓名，單位，證號(hào)）LOANS（證號(hào)，編號(hào)，借閱日期）找出2007年12月01日前借出書籍的書名和借閱人姓名。用SQL語(yǔ)言可表達(dá)如下：

SELECT書名，姓名

FROMBOOKS，BORROWERS，LOANSWHEREBOOKS.編號(hào)=LOANS.編號(hào)ANDBORROWERS.證號(hào)=LOANS.證號(hào)AND

借閱日期<{2007-12-01};第39頁(yè)/共60頁(yè)41上述SQL語(yǔ)句可轉(zhuǎn)化為如下關(guān)系代數(shù)表達(dá)式：書名，姓名(借閱日期<{2007-12-01}

(BOOKS∞（BORROWERS∞LOANS)))或書名，姓名(借閱日期<{2007-12-01}∧BOOKS.編號(hào)=LOANS.編號(hào)∧

BORROWERS.證號(hào)=LOANS.證號(hào)

(BOOKS×(BORROWERS×LOANS)))

通常先轉(zhuǎn)化為后一種形式，在優(yōu)化的后期會(huì)將笛卡爾積轉(zhuǎn)換為自然連接。第40頁(yè)/共60頁(yè)42書名，姓名借閱日期<{2007-12-01}∧BOOKS.編號(hào)=LOANS.編號(hào)∧

BORROWERS.證號(hào)=LOANS.證號(hào)上述表達(dá)式的語(yǔ)法樹LOANSBOOKSBORROWERS根據(jù)算法第1步，分解該選擇第41頁(yè)/共60頁(yè)43第1步優(yōu)化（分解選擇）后的語(yǔ)法樹書名，姓名LOANSBOOKSBORROWERS借閱日期<{2005-10-01}∧BOOKS.編號(hào)=LOANS.編號(hào)∧

BORROWERS.證號(hào)=LOANS.證號(hào)借閱日期<{2007-12-01}

BOOKS.編號(hào)=LOANS.編號(hào)BORROWERS.證號(hào)=LOANS.證號(hào)

分解之后根據(jù)算法第2步，該選擇可下移第42頁(yè)/共60頁(yè)44書名，姓名LOANSBOOKSBORROWERS借閱日期<{2007-12-01}BOOKS.編號(hào)=LOANS.編號(hào)BORROWERS.證號(hào)=LOANS.證號(hào)

第43頁(yè)/共60頁(yè)45書名，姓名LOANSBOOKSBORROWERS借閱日期<{2007-12-01}BOOKS.編號(hào)=LOANS.編號(hào)BORROWERS.證號(hào)=LOANS.證號(hào)

該選擇已不能下移該選擇也不能下移將該選擇下移交換第44頁(yè)/共60頁(yè)46書名，姓名LOANSBOOKSBORROWERS借閱日期<{2007-12-01}BOOKS.編號(hào)=LOANS.編號(hào)BORROWERS.證號(hào)=LOANS.證號(hào)

交換后繼續(xù)下移第45頁(yè)/共60頁(yè)47書名，姓名LOANSBOOKSBORROWERS借閱日期<{2007-12-01}BOOKS.編號(hào)=LOANS.編號(hào)BORROWERS.證號(hào)=LOANS.證號(hào)

交換第46頁(yè)/共60頁(yè)48書名，姓名LOANSBOOKSBORROWERS借閱日期<{2007-12-01}BOOKS.編號(hào)=LOANS.編號(hào)BORROWERS.證號(hào)=LOANS.證號(hào)

繼續(xù)下移第47頁(yè)/共60頁(yè)49書名，姓名LOANSBOOKSBORROWERS借閱日期<{2007-12-01}BOOKS.編號(hào)=LOANS.編號(hào)BORROWERS.證號(hào)=LOANS.證號(hào)

OK第2步優(yōu)化（選擇下移）后的語(yǔ)法樹該投影能否與選擇交換？不能！怎么辦？利用投影的冪等律插入一個(gè)投影算法第3步，投影下移第48頁(yè)/共60頁(yè)50書名，姓名LOANSBOOKSBORROWERS借閱日期<{2007-12-01}BOOKS.編號(hào)=LOANS.編號(hào)BORROWERS.證號(hào)=LOANS.證號(hào)

書名，姓名，BOOKS.編號(hào)，LOANS.編號(hào)交換第49頁(yè)/共60頁(yè)51書名，姓名LOANSBOOKSBORROWERS借閱日期<{2007-12-01}BOOKS.編號(hào)=LOANS.編號(hào)BORROWERS.證號(hào)=LOANS.證號(hào)

書名，姓名，BOOKS.編號(hào)，LOANS.編號(hào)對(duì)笛卡爾分配第50頁(yè)/共60頁(yè)52書名，BOOKS.編號(hào)書名，姓名LOANSBOOKSBORROWERS借閱日期<{2007-12-01}BOOKS.編號(hào)=LOANS.編號(hào)BORROWERS.證號(hào)=LOANS.證號(hào)

姓名，LOANS.編號(hào)OK還需下移第51頁(yè)/共60頁(yè)53書名，BOOKS.編號(hào)書名，姓名LOANSBOOKSBORROWERS借閱日期<{2007-12-01}BOOKS.編號(hào)=LOANS.編號(hào)BORROWERS.證號(hào)=LOANS.證號(hào)

姓名，LOANS.編號(hào)插入一個(gè)投影姓名，LOANS.編號(hào)，

BORROWERS.證號(hào)，LOANS.證號(hào)

下移第52頁(yè)/共60頁(yè)54書名，BOOKS.編號(hào)書名，姓名LOANSBOOKSBORROWERS借閱日期<{2007-12-01}BOOKS.編號(hào)=LOANS.編號(hào)BORROWERS.證號(hào)=LOANS.證號(hào)

姓名，LOANS.編號(hào)姓名，LOANS.編號(hào)，

BORROWERS.證號(hào)，LOANS.證號(hào)

對(duì)笛卡爾分配第53頁(yè)/共60頁(yè)55LOANS.編號(hào)，

LOANS.證號(hào)

姓名，

BORROWERS.