《數(shù)據(jù)庫系統(tǒng)原理》教案教學(xué)內(nèi)容第四章關(guān)系系統(tǒng)的查詢優(yōu)化教材章節(jié)第四章關(guān)系系統(tǒng)的查詢優(yōu)化教學(xué)周次教學(xué)學(xué)時2授課對象教學(xué)環(huán)境多媒體教室教學(xué)目的掌握關(guān)系系統(tǒng)的優(yōu)化解決過程教學(xué)重點關(guān)系系統(tǒng)的基本概念，關(guān)系系統(tǒng)的優(yōu)化解決。教學(xué)難點關(guān)系系統(tǒng)的優(yōu)化解決教學(xué)過程一次課：關(guān)系系統(tǒng)的基本概念，關(guān)系系統(tǒng)的優(yōu)化解決。作業(yè)與規(guī)定備注第四章關(guān)系系統(tǒng)的查詢優(yōu)化4.1關(guān)系系統(tǒng)4.1.1關(guān)系系統(tǒng)的定義籠統(tǒng)的說，支持關(guān)系模型的數(shù)據(jù)庫管理系統(tǒng)(DBMS)稱為關(guān)系系統(tǒng)?？梢?，關(guān)系系統(tǒng)和關(guān)系模型是親密有關(guān)而又互相區(qū)別的兩個概念。設(shè)計關(guān)系模型時，我們不苛求關(guān)系模型中每一部分的同等重要性，但是要滿足以下幾個方面：(1)以提高顧客的生產(chǎn)率作為關(guān)系系統(tǒng)的重要目的，方便顧客使用。(2)確保和提高數(shù)據(jù)的物理獨立性，即實現(xiàn)關(guān)系系統(tǒng)能夠自動地選擇途徑。(3)確保關(guān)系系統(tǒng)能夠解決絕大部分的實際問題。定義4.1一種系統(tǒng)是關(guān)系系統(tǒng)當(dāng)且僅當(dāng)·支持關(guān)系數(shù)據(jù)庫(關(guān)系數(shù)據(jù)構(gòu)造)?！ぶС诌x擇、投影和(自然)連接運算，對這些運算不必規(guī)定定義任何物理存取途徑。需要闡明的是，該定義是關(guān)系系統(tǒng)的最小規(guī)定。一種系統(tǒng)僅支持關(guān)系數(shù)據(jù)構(gòu)造，但沒有選擇、投影和連接運算功效的系統(tǒng)仍不能算作關(guān)系系統(tǒng)。支持選擇、投影和連接運算，但規(guī)定定義物理存取途徑，需要顧客建立索引才干檢索統(tǒng)計，也不能算作真正的關(guān)系系統(tǒng)。固然并不規(guī)定關(guān)系系統(tǒng)的選擇、投影、連接運算和關(guān)系代數(shù)的對應(yīng)運算完全同樣，而只規(guī)定有等價的這三種運算功效就行。4.1.2關(guān)系系統(tǒng)的分類具體地說：現(xiàn)在的關(guān)系系統(tǒng)多是按照E.F.Codd的思想劃分的(如圖4-1)。圖中的圓表達關(guān)系數(shù)據(jù)模型。每個圓分為三部分，分別表達關(guān)系模型的三個構(gòu)成部分：構(gòu)造S(Structure)、完整性I(Integrity)、數(shù)據(jù)操縱M(Manipulation)。圖中陰影部分表達各類系統(tǒng)支持模型的程度。(1)表式系統(tǒng)這類系統(tǒng)僅支持關(guān)系數(shù)據(jù)構(gòu)造，不支持集合的操作。表式系統(tǒng)不能算關(guān)系系統(tǒng)。(2)最小關(guān)系系統(tǒng)即定義中的關(guān)系系統(tǒng)。它們僅支持關(guān)系數(shù)據(jù)構(gòu)造和三種關(guān)系操作。(3)關(guān)系完備的系統(tǒng)這類系統(tǒng)支持關(guān)系數(shù)據(jù)構(gòu)造和全部的關(guān)系代數(shù)操作。(4)全關(guān)系系統(tǒng)這類系統(tǒng)支持關(guān)系模型的全部特性。即不僅是關(guān)系上完備的并且支持?jǐn)?shù)據(jù)構(gòu)造中域的概念，支持實體完整性和參考完整性?，F(xiàn)在，大多數(shù)關(guān)系系統(tǒng)已不同程度上靠近或達成了這個目的。根據(jù)分類能夠看到不同關(guān)系系統(tǒng)對模型的支持不同如表4-1：表4-1不同關(guān)系系統(tǒng)對模型的支持?jǐn)?shù)據(jù)構(gòu)造數(shù)據(jù)操縱數(shù)據(jù)完整性表式系統(tǒng)表不支持不支持最小關(guān)系系統(tǒng)表選擇、投影、連接不支持關(guān)系完備的系統(tǒng)表全部不支持全關(guān)系系統(tǒng)全部全部完全支持現(xiàn)在，國內(nèi)外涌現(xiàn)出了許多關(guān)系系統(tǒng)：如倒排列表(Invertedlist)，F(xiàn)oxPro，DB2，ORACLE，SYBASE，以及我國自己開發(fā)的PBASE(中國人民大學(xué))、COBASE(北大、人大與中軟)、OPENBASE(東大阿爾派)、DM2(華中理工大學(xué))等。根據(jù)關(guān)系系統(tǒng)的定義及E.F.Codd的思想，我們能夠?qū)@些系統(tǒng)作嚴(yán)格的分辨。如倒排表列(Invertedlist)系統(tǒng)就屬于表式系統(tǒng)。如FoxBASE、FoxPro等就屬于最小關(guān)系系統(tǒng)。90年代初的許多關(guān)系數(shù)據(jù)庫管理系統(tǒng)屬于關(guān)系完備的系統(tǒng)。*4.1.3全關(guān)系系統(tǒng)的十二條基本準(zhǔn)則全關(guān)系型的系統(tǒng)應(yīng)當(dāng)完全地支持關(guān)系模型的全部特性，這是個原則。關(guān)系模型的奠基人E.F.Codd具體地給出了全關(guān)系型的關(guān)系系統(tǒng)應(yīng)遵照的十二條基本準(zhǔn)則。從實際意義上看，這十二條準(zhǔn)則能夠作為評價或購置關(guān)系型產(chǎn)品的原則。從理論意義上看，它是對關(guān)系數(shù)據(jù)模型的具體而又進一步的敘述。準(zhǔn)則0一種關(guān)系型的DBMS必須能完全通過它的關(guān)系能力來管理數(shù)據(jù)庫。準(zhǔn)則0是下面十二條準(zhǔn)則的基礎(chǔ)。準(zhǔn)則0的一種推論是：任何聲稱是關(guān)系型的DBMS必須在關(guān)系這個級別上支持?jǐn)?shù)據(jù)的插入、修改和刪除(即一次多個統(tǒng)計的操作級別)。不管一種系統(tǒng)與否還含有非關(guān)系的管理數(shù)據(jù)的能力，它必須滿足準(zhǔn)則0。任何不滿足準(zhǔn)則0的DBMS不配稱為關(guān)系型DBMS。準(zhǔn)則0的另一種推論是：關(guān)系型DBMS必須遵照信息準(zhǔn)則和確保訪問(存取)準(zhǔn)則。準(zhǔn)則1信息準(zhǔn)則關(guān)系型DBMS的全部信息都應(yīng)在邏輯一級上用一種辦法即表中的值顯式地表達。進一步地，表名、列名和域名等都用系統(tǒng)內(nèi)部表中的值表達。數(shù)據(jù)字典本身是一種動態(tài)的用來描述元數(shù)據(jù)的關(guān)系數(shù)據(jù)庫。滿足信息準(zhǔn)則不僅為了提高顧客的生產(chǎn)率，使得DBA維護數(shù)據(jù)庫的工作更簡樸、更有效，并且也為了使軟件廠商在定義其它軟件包時能夠檢索存儲在數(shù)據(jù)字典中的信息，需要的話能夠借助DBMS的操作把新的信息存入字典中，簡便合理。準(zhǔn)則2確保訪問準(zhǔn)則依靠表名、主鍵和列名的組合，確保能以邏輯方式訪問關(guān)系數(shù)據(jù)庫中的每個數(shù)據(jù)項。確保訪問準(zhǔn)則表明關(guān)系系統(tǒng)所采用的是相聯(lián)尋址的訪問模式，而不是那種面對機器的尋址辦法。這是關(guān)系系統(tǒng)獨有的方式。準(zhǔn)則3空值的系統(tǒng)化解決全關(guān)系型的DBMS應(yīng)支持空值的概念，并用系統(tǒng)化的方式解決空值。以往解決空值的方法經(jīng)常是對每個允許取空值的字段定義一種特殊的值來表達空值。這不是系統(tǒng)化的好方法。由于這樣的話，顧客必須對每個字段或域采用不同的辦法來解決空值。這種辦法必然會大大減少顧客生產(chǎn)率。準(zhǔn)則4基于關(guān)系模型的動態(tài)的聯(lián)機數(shù)據(jù)字典數(shù)據(jù)庫的描述在邏輯級上應(yīng)當(dāng)和普通數(shù)據(jù)采用同樣的表達方式，使得授權(quán)顧客能夠使用查詢普通數(shù)據(jù)所用的關(guān)系語言來查詢數(shù)據(jù)庫的描述信息。準(zhǔn)則5統(tǒng)一的數(shù)據(jù)子語言準(zhǔn)則一種關(guān)系系統(tǒng)必須有一種語言，它的語句能夠表達為含有嚴(yán)格語法規(guī)定的字符串，并能全方面地支持下列功效：·數(shù)據(jù)定義、視圖定義

·數(shù)據(jù)操作

·完整性約束

·授權(quán)

·事務(wù)解決功效(事務(wù)開始、提交、回滾)關(guān)系辦法是高度動態(tài)的，即極少需要停止數(shù)據(jù)庫的活動。非關(guān)系系統(tǒng)則不是這樣。準(zhǔn)則6視圖更新準(zhǔn)則全部理論上可更新的視圖也應(yīng)當(dāng)允許由系統(tǒng)更新。什么叫“一種視圖是理論上可更新的視圖”呢？它是指對此視圖的更新規(guī)定存在一種與時間無關(guān)的算法，該算法能夠無二義性地把更新規(guī)定轉(zhuǎn)換為對基本表的更新序列。準(zhǔn)則7高級的插入、修改和刪除操作關(guān)系系統(tǒng)的操作對象是單一的關(guān)系。以關(guān)系為操作對象不僅簡化了顧客查詢，提高了顧客生產(chǎn)率，并且也為系統(tǒng)提供了很大的余地來進行查詢優(yōu)化，提高了系統(tǒng)的運行效率。它允許系統(tǒng)來選擇存取途徑，方便得到最有效的運行代碼。準(zhǔn)則8數(shù)據(jù)物理獨立性無論數(shù)據(jù)庫的數(shù)據(jù)在存儲表達或存取辦法上作任何變化，應(yīng)用程序和終端活動都保持邏輯上的不變性。準(zhǔn)則9數(shù)據(jù)邏輯獨立性當(dāng)對基本關(guān)系進行理論上信息不受損害的任何變化時，應(yīng)用程序和終端活動都保持邏輯上的不變性。對基本關(guān)系來講，什么樣的變化在理論上是保持信息不受損害的變化呢？把一種基本表按行的內(nèi)容或者按列名分解為兩個表，若這兩個表都保存原基本表的主鍵，則這種變換在理論上是保持信息不受損失的。用無損連接辦法把兩個表合成一種表也不會破壞信息的變換。為了盡量提高數(shù)據(jù)邏輯獨立性，DBMS必須能對理論上可更新的視圖執(zhí)行插入、修改和刪除操作，即必須滿足準(zhǔn)則6。準(zhǔn)則l0數(shù)據(jù)完整性的獨立性關(guān)系數(shù)據(jù)庫的完整性約束條件必須是用數(shù)據(jù)庫語言定義并存儲在數(shù)據(jù)字典中的，而不是在應(yīng)用程序中加以定義的。準(zhǔn)則11分布獨立性所謂分布獨立性是指關(guān)系型DBMS含有這樣的數(shù)據(jù)庫語言，它使應(yīng)用程序和終端活動無論在最初的數(shù)據(jù)還是在后來的數(shù)據(jù)重新分布時都能在邏輯上保持不變準(zhǔn)則12無破壞準(zhǔn)則如果一種關(guān)系系統(tǒng)含有一種低檔(指一次一種統(tǒng)計)語言，則這個低檔語言不能違反或繞過完整性準(zhǔn)則。在關(guān)系辦法中，為獲得數(shù)據(jù)完整獨立性就要讓完整性約束條件和數(shù)據(jù)的邏輯構(gòu)造相獨立。用準(zhǔn)則12就很容易協(xié)助我們識別那些貼著“關(guān)系”標(biāo)簽的非關(guān)系系統(tǒng)。由于這一系統(tǒng)已經(jīng)在關(guān)系接口之下有一種應(yīng)用接口，因此很難滿足準(zhǔn)則12。這時DBA不能控制他們的數(shù)據(jù)庫，不能確保數(shù)據(jù)庫的完整性狀態(tài)。4.2查詢優(yōu)化解決關(guān)系系統(tǒng)的查詢普通指顧客向數(shù)據(jù)庫系統(tǒng)提交的某些對數(shù)據(jù)操作的請求。由于數(shù)據(jù)庫系統(tǒng)向顧客提供了非過程化的數(shù)據(jù)操縱語言，顧客只要提出“干什么”，不必指出“怎么干”，DBMS就會自動根據(jù)顧客的查詢請求來完畢任務(wù)，因此查詢的優(yōu)化解決就成了DBMS的重要任務(wù)。4.2.1問題的提出我們首先來看一種簡樸的例子，闡明為什么要進行查詢優(yōu)化。例4.1對于關(guān)系的Order-O_Details(訂單-訂單明細)：Order(OID,CID,ODate)屬性分別為訂單號，客戶號，訂單日期；O_Details(OID,PID,Qtity)屬性分別為訂單號，產(chǎn)品號，產(chǎn)品數(shù)量。如果查詢訂購5號產(chǎn)品的客戶的客戶號，則有下面的查詢語句：SELECTOrder.CIDFROMOrder,O_DetailWHEREOrder.OID=O_Details.OIDANDO_Details.PID=5；設(shè)O_O_Details中有l(wèi)000個訂單，l0000種產(chǎn)品，其中5號產(chǎn)品的統(tǒng)計為50個。對于此查詢，系統(tǒng)能夠提供多個等價方略。這里我們討論以下三種：(1)Q1=CID(Order.OID=O_Details.OID∧O_Details.PID=5(Order×O_Details))

(2)Q2=CID(O_Details.PID=5(OrderO_Details))

(3)Q3=CID(OrderO_Details.PID=5(O_Details))對Q1的解決過程和時間開銷分析l.Order和O_Details的笛卡爾積操作(1)在內(nèi)存緩沖區(qū)中讀入某個表(如Order表)的未解決元組；(2)另一塊緩沖區(qū)中讀入另一種表(如O_Details表)的未解決元組；(3)把O_Details中的每個元組和Order中每個元組連接，連接后的元組裝滿一塊后，送入輸出緩沖區(qū)；如果溢出，則寫入臨時文獻上；(4)從O_Details中讀入一塊和內(nèi)存中的Order元組連接，直到O_Details表解決完。(5)再一次讀入若干塊Order元組，讀入一塊O_Details元組，量復(fù)上述解決過程，直到把Order表解決完。根據(jù)上述環(huán)節(jié)，設(shè)一種塊能裝l0個Order元組或l00個O_Details元組，在內(nèi)存中寄存5塊Order元組和l塊O_Details元組，需要讀Order表l00塊。讀O_Details表20遍，每遍l00塊。因此讀取總塊數(shù)為：2100塊。若每秒讀寫20塊，則讀取總計要花105秒。Order和O_Details連接后的元組數(shù)為1000×10000=107。設(shè)每塊能裝l0個元組，則寫出這些塊要花5×104秒。2.選擇操作如果滿足條件的元組假設(shè)僅50個，均可放在內(nèi)存。那么，依次讀入連接后的元組，按照選擇條件選用滿足規(guī)定的的統(tǒng)計。假定內(nèi)存解決時間無視，這一步讀取中間文獻耗費的時間(同寫中間文獻同樣)需5×104秒。3.投影操作把第2步的成果在CID上作投影輸出，得到最后成果。因此，無視全部內(nèi)存解決時間，Q1執(zhí)行查詢的總時間大概要105秒。對Q2的解決過程和時間開銷分析l.自然連接操作自然連接能夠看作是笛卡兒積特殊運算，因此讀取Order和O_Details表的方略不變，總的讀取塊數(shù)仍為2100塊耗費l05秒。但由于自然連接包含了選擇運算，相對Q1成果減少為104個。因此寫出這些元組時間為50秒。僅為Q1的千分之一。2.選擇操作選擇運算是對自然連接成果進行讀取，因此讀取中間文獻塊耗費時間為50秒。3.把第2步成果投影輸出。

因此，Q2執(zhí)行查詢的總時間大概要205秒。對Q3的解決過程和時間開銷分析1．由于先對O_Details表作選擇運算，關(guān)系O_Details的每塊只需讀一遍，因此存取l00塊耗費時間為5秒。由于滿足條件的元組僅50個，不必使用中間文獻。2.讀取Order表，把讀入的Order元組和內(nèi)存中的O_Details元組作連接也只需讀一遍Order表，共l00塊，耗費時間為5秒。3.把連接成果投影輸出。

因此，Q3總的執(zhí)行時間大概為10秒。如果O_Details表的PID字段上有索引，第l步就不必讀取全部的O_Details元組而只需讀取PID=5的那些元組(50個)。存取的索引塊和O_Details中滿足條件的數(shù)據(jù)塊大概總共3～4塊。若Order表在OID上也有索引，則第2步也不必讀取全部的Order元組，由于滿足條件的O_Details統(tǒng)計僅50個，涉及最多50個Order統(tǒng)計，因此讀取Order表的塊數(shù)也可大大減少?？偟拇嫒r間將進一步減少到數(shù)秒。這個簡樸的例子充足闡明了查詢優(yōu)化的必要性，同時也給了我們某些查詢優(yōu)化辦法的初步概念。如當(dāng)有選擇和連接操作時，應(yīng)當(dāng)先做選擇操作，這樣參加連接的元組就能夠大大減少。下面給出優(yōu)化的普通方略。4.2.2關(guān)系代數(shù)的優(yōu)化規(guī)則1.關(guān)系代數(shù)等價變換規(guī)則關(guān)系代數(shù)體現(xiàn)式的優(yōu)化是查詢優(yōu)化的基本課題。而研究關(guān)系代數(shù)體現(xiàn)式的優(yōu)化最佳從研究關(guān)系體現(xiàn)式的等價變換規(guī)則開始。兩個關(guān)系體現(xiàn)式E1和E2是等價的，可記為E1≡E2。

慣用的等價變換規(guī)則有：(1)連接、笛卡爾積交換律E1×E2≡E2×E1E1E2≡E2E1E1E2≡E2E1其中E1和E2是關(guān)系代數(shù)體現(xiàn)式，F(xiàn)是連接運算的條件(2)連接、笛卡爾積的結(jié)合律(E1×E2)×E3≡E1×(E2×E3)(E1E2)E3≡E1(E2E3)(E1E2)E3≡E1(E2E3)其中E1、E2、E3是關(guān)系代數(shù)體現(xiàn)式，F(xiàn)l和F2是連接運算的條件(3)投影的級聯(lián)A1,A2,...,An(B1,B2,...,Bm(E))≡A1,A2,...,An(E)

其中，E是關(guān)系代數(shù)體現(xiàn)式，Ai(i=1,2,...,n)，Bj(j=l,2,...,m)是屬性名且{A1,A2,...,An}是{B1,B2,...,Bm}的子集。(4)選擇的級聯(lián)F1(F2(E))≡F1F2(E)這里，E是關(guān)系代數(shù)體現(xiàn)式，F(xiàn)l、F2是選擇條件。F1F2=F2F1換律成立。(5)選擇與投影的交換律F(A1,A2,...,An(E))≡A1,A2,...,An(F(E))

這里，選擇條件F只涉及屬性A1,A2,...,An。若F中有不屬于A1,A2,...,An的屬性B1,B2,...,Bm，則有更普通的規(guī)則：A1,A2,...,An(F(E))≡A1,A2,...,An(F(A1,A2,...,An,B1,B2,...,Bm(E))(6)選擇與笛卡爾積的交換律如果F中涉及的屬性都是El中的屬性，則F(E1×E2)≡F(E1)×E2

如果F=F1∧F2，并且F1只涉及E1中的屬性，F(xiàn)2只涉及E2中的屬性，則由上面等價變換規(guī)則可推出：F(E1×E2)≡F1(E1)×F2(E2)若F1只涉及E1中的屬性，F(xiàn)2涉及E1和E2兩者的屬性，則仍有F(E1×E2)≡F2(F1(E1)×E2)即將一部分選擇條件放到笛卡爾積的前面。(7)選擇與并的交換設(shè)E=E1∪E2，E1、E2有相似的屬性名，則F(E1∪E2)≡F(E1)∪F(E2)(8)選擇與差運算的交換若E1與E2有相似的屬性名，則F(E1-E2)≡F(E1)-F(E2)(9)投影與笛卡爾積的交換設(shè)E1和E2是兩個關(guān)系體現(xiàn)式，A1,...,An是E1的屬性，B1,B2,...,Bm是E2的屬性，則A1,A2,...,An，B1,B2,...,Bm(E1×E2)≡A1,A2,...,An(E1)×B1,B2,...,Bm(E2)(10)投影與并的交換設(shè)E1和E2有相似的屬性名，則A1,A2,...,An(E1∪E2)≡A1,A2,...,An(E1)∪A1,A2,...,An(E2)2.關(guān)系代數(shù)的優(yōu)化規(guī)則從本章第一節(jié)我們能夠看出，關(guān)系代數(shù)體現(xiàn)式中，笛卡爾積和連接操作是最耗費時間和空間的運算，因此引出以下對體現(xiàn)式進行轉(zhuǎn)換的規(guī)則，以減少中間關(guān)系的大小。(1)盡量早的做選擇操作。在優(yōu)化方略中這是最重要、最基本的一條。它經(jīng)常可使執(zhí)行時間節(jié)省幾個數(shù)量級，由于選擇運算普通使計算的中間成果大大變小。(2)把某些選擇同在它前面要執(zhí)行的笛卡爾積結(jié)合起來成為一種連接運算。相似關(guān)系上的連接操作，特別是等值連接運算要比同樣關(guān)系上的笛卡爾積省諸多時間。(3)把投影運算和選擇運算同時進行。如有若干投影和選擇運算，并且它們都對同一種關(guān)系操作，則能夠在掃描此關(guān)系的同時完畢全部的這些運算以避免重復(fù)掃描關(guān)系。(4)把投影同其前或其后的雙目運算結(jié)合起來。這樣能夠節(jié)省為單獨完畢投影操作而進行的關(guān)系掃描。(5)找出公共子體現(xiàn)式。如果這種重復(fù)出現(xiàn)的子體現(xiàn)式的成果不是很大的關(guān)系，并且從外存中讀入這個關(guān)系比計算該子體現(xiàn)式的時間少得多，則先計算一次公共子體現(xiàn)式并把成果寫入中間文獻是合算的。當(dāng)查詢的是視圖時，定義視圖的體現(xiàn)式就是公共子體現(xiàn)式的狀況。4.2.3關(guān)系代數(shù)的優(yōu)化算法關(guān)系代數(shù)體現(xiàn)式的優(yōu)化是由DBMS的DML編譯器完畢的。我們能夠應(yīng)用關(guān)系到代數(shù)的變換法則來優(yōu)化關(guān)系體現(xiàn)式，使優(yōu)化后的體現(xiàn)式能滿足關(guān)系代數(shù)優(yōu)化原則。通過對關(guān)系代數(shù)進行語法分析得到一棵語法樹。這是關(guān)系優(yōu)化過程中最重要的一步。下面給出關(guān)系體現(xiàn)式的優(yōu)化算法。算法4.1關(guān)系體現(xiàn)式的優(yōu)化。

輸入：一種關(guān)系體現(xiàn)式的語法樹。

輸出：計算該體現(xiàn)式的程序。環(huán)節(jié)：(1)運用規(guī)則(4)把形如F1F2...Fn(E)變換為級聯(lián)形式F1(F2(...(Fn(E))...))(2)運用規(guī)則(4)～(8)盡量把對每一種選擇移到樹的葉端。(3)運用規(guī)則(3)、(5)、(9)、(10)中的普通形式盡量把對每一種投影移向樹的葉端。規(guī)則(3)使某些投影消失，而普通形式的規(guī)則(5)把一種投影分裂為兩個，其中一種有可能被移向樹的葉端。(4)運用規(guī)則(3)～(5)把選擇和投影的串接合并成單個選擇、單個投影或一種選擇后跟一種投影。使多個選擇或投影能同時執(zhí)行，或在一次掃描中全部完畢，盡管這種變換以乎違反“投影盡量早做”的原則，但這樣做效率更高。(5)把上述得到的語法樹的內(nèi)節(jié)點分組。每個雙目運算(×,∪,-)和它全部的直接祖先(、)為一組。如果其后裔直到葉子結(jié)點全是單目運算則也將它們并入該組；但當(dāng)雙目運算是笛卡爾積(×)，并且其后的選擇不能與它結(jié)合為等值連接時除外。把這些單目運算單獨分為一組。(6)生成一種程序，每組結(jié)點的計算是程序中的一步。各步的次序是任意的，只要確保任何一組的計算不會在它的后裔組之前計算。例4.2對于關(guān)系的Customer-Order-Order_Details(客戶-訂單-訂單明細)：Customer(CustomerID,CompanyName,Address)屬性分別為客戶號，公司名稱，公司地址；Order(OrderID,CustomerID,OrderDate)屬性分別為訂單號，客戶號，訂單日期；Order_Details(OrderID,ProductID,Quantity)屬性分別為訂單號，