第三章關系運算

第3章關系運算2023年2月1日數(shù)據庫原理第三章關系運算教學內容：基本概念：關系代數(shù)：關系演算：查詢優(yōu)化：

關系模型、關鍵碼、關系的定義和性質、三類完整性規(guī)則?；静僮鳌⒔M合操作、擴充操作。元組演算、域演算、關系演算的安全性和等價性。關系代數(shù)表達式的等價轉換規(guī)則、優(yōu)化算法。教學重點：關系代數(shù)運算§1關系數(shù)據模型的基本概念一、基本術語

用二維表格表示實體集，外鍵表示實體間聯(lián)系的模型稱為關系模型；關系：對應二維表格；元組：表中的行；屬性：表中的列；域：屬性的取值范圍。

三、關系的性質

1、同列具有相同的性質，不同的列可有相同的域，

2、任意兩個元組不能相同，元組的次序可交換；

3、每個屬性值(分量)都是不可分的數(shù)據項(即屬性值為最小單位).4.屬性的次序可交換；

四、關鍵碼超鍵：侯選鍵：主鍵：外鍵：能唯一標識元組的屬性組合（可能存在多余的屬性）。能唯一標識元組的最小屬性組合。不含有多余屬性的超鍵若一個關系中有多個侯選鍵,則選其中的一個為關系的主鍵。若某個屬性組F是關系R的主鍵,F又在關系S中出現(xiàn),則F是S的外鍵.若一個關系R中包含有另一個關系S的主鍵所對應的屬性組F，則稱F為R的外鍵。稱關系S為參照關系，R為依賴關系。學生關系模式

S（SNO，SNAME，AGE，SEX，SDEPT）課程關系模式

C（CNO，CNAME，CDEPT，TNAME）學習關系模式

SC（SNO，CNO，GRADE）SNOSNAMEAGESEXSDEPTS1程宏19男計算機S3劉莎莎18女通訊S4李剛畸20男法學S6蔣天云19男國際貿易S9王莉21女計算機

CNOCNAMECDEPTTNAMEC1離散數(shù)學計算機汪宏偉C2高等數(shù)學通訊錢紅C3數(shù)據結構計算機馬良C4計算機原理計算機李兵

SNOCNOGRADES3C387S1C288S4C379S9C483S1C376S6C368S9C178S6C188S3C264S1C486S9C278

五、關系模型的三類完整性規(guī)則實體完整性規(guī)則：參照完整性規(guī)則：

若某個屬性組F是關系R的主鍵,F又在關系S中出現(xiàn),則F是S的外鍵.F在S中的取值只有兩種可能,一為空,二為R中的某個主鍵值R:主表S:副表；副表通過在副表S中添加外鍵子句來實現(xiàn)(foreignkey)。

關系中元組的主鍵值不能為空且不能重復。通過主鍵子句來實現(xiàn)(primarykey)在數(shù)據庫中有如下圖所示的兩個表，若職工表的主鍵(主碼)是職工號，外鍵(外碼)是部門號，部門表的主鍵(主碼)是部門號，則SQL操作不能成功執(zhí)行的是________。

A.從職工表中刪除行（'025'，'王百萬'，'03'，2900）

B.將行（'005'，'喬興'，'04'，750）插入到職工表中

C.將職工號為“001”的工資改為5700

D.將職工號為“003”的部門號改為'03'假設三個關系中已經存在如下表所示元組：

若再向SC表中插入如下元組：

I（'0901'，'C001'，82）II（'0904'，'C002'，76）

III（'0902'，'C003'，65）IV（'0903'，'C002'，70）

能夠插入的元組是________。

A.I，II，IV

B.I，III

C.I，II

D.I，IV用戶定義的完整性規(guī)則：由應用環(huán)境決定，反映某一具體應用涉及的數(shù)據必須滿足的約束條件。六、關系模型的形式定義(有三個組成部分)數(shù)據結構：數(shù)據操作：完整性規(guī)則：數(shù)據庫中全部數(shù)據及其相互聯(lián)系都被組織成關系（即二維表格）的形式。提供了一組完備的高級關系運算，以支持對數(shù)據庫的各種操作。關系運算分為關系代數(shù)和關系演算兩類。三類完整性規(guī)則§2關系代數(shù)一、關系數(shù)據語言關系數(shù)據庫語言由查詢語句（描述用戶的檢索操作）和更新語句（描述用戶的插入、修改和刪除等操作）兩大類組成。

關系查詢語言分為：

關系代數(shù)語言：關系演算語言：

基于關系代數(shù)和關系演算語言雙重特點的語言：以集合操作為基礎；以謂詞演算為基礎；元組關系演算語言

域關系演算語言SQL二、關系代數(shù)的基本運算并（union）：設關系R和關系S具有相同的元數(shù)，且相應的屬性列具有相同的特征：

R∪S≡{t︱t∈R∨t∈S}

其中：t是元組變量，R和S的元數(shù)相同。并運算要求兩個關系屬性的性質必須一致且并運算的結果要消除重復的元組。舉例：ABCa1b1c1a1b2c2a2b2c1ABCa1b1c1a1b2c2a1b3c2a2b2c1ABCa1b2c2a1b3c2a2b2c1RSR∪S

2.差(differedce)：設關系R和關系S具有相同的元數(shù)，且相應的屬性列具有相同的特征：

R―S≡{t︱t∈R∧tS}

其中：t是元組變量，R和S的元數(shù)相同。舉例：差(續(xù))ABCa1b1c1a1b2c2a2b2c1ABCa1b1c1ABCa1b2c2a1b3c2a2b2c1RSR-S

3.笛卡兒積（cartesianproduct）

設關系R和關系S的元數(shù)分別為r和s。定義R和S的笛卡兒積R×S是一個（r+s）元的元組集合，每個元組的前r個分量（屬性值）來自R的一個元組，后s個分量是S的一個元組，記為R×S。形式定義如下：

R×S≡{t︱t=<tr,ts>∧tr∈R∧ts∈S}

若R有n個元組，S有m個元組，則R×S有n×m個元組。

舉例：ABCa1b1c1a1b2c2a2b2c1ABCa1b1c1a1b1c1a1b1c1a1b2c2a1b2c2a1b2c2a2b2c1a2b2c1a2b2c1ABCa1b2c2a1b3c2a2b2c1RSR×S

ABCa1b2c2a1b3c2a2b2c1a1b2c2a1b3c2a2b2c1a1b2c2a1b3c2a2b2c1

4.投影（projection）：

對一個關系進行垂直分割,消去某些列，并重新安排列的順序,再刪去重復元組。πi1,…,im(R)≡{t|t=<ti1,…,tim>∧<t1,…,tm>∈R,1mk}設關系R是k元關系，R在其分量Ai1,…,Aim(m≤k,…,i1,…,im為1到k之間的整數(shù))上的投影用πi1,…,im（R）表示，它是從R中選擇若干屬性列組成的一個m元元組的集合，形式定義如下：舉例：2.投影（Projection）2）投影操作主要是從列的角度進行運算但投影之后不僅取消了原關系中的某些列，而且還可能取消某些元組（避免重復行）π投影（續(xù)）3)舉例[例3]查詢學生的姓名和所在系 即求Student關系上學生姓名和所在系兩個屬性上的投影

πSname，Sdept(Student)

或π2，5(Student)結果：投影（續(xù)）SnameSdept李勇CS劉晨IS王敏MA張立IS投影（續(xù)）[例4]查詢學生關系Student中都有哪些系

πSdept(Student)

結果：SdeptCSISMA5.選擇(selection)

根據某些條件對關系做水平分割,選擇符合條件的元組。

條件用命題公式F（即計算在括號中的條件表達式）表示.

F中的運算對象:

常量(用引號括起來）,

元組分量（屬性名或列的序號），算術比較運算符:＜，≤，＞，≥，＝，≠,

邏輯運算符:∧，∨，┐。關系R關于公式F的選擇操作用σF（R）表示，形式定義如下：

σF（R）={t|t∈R∧F(t)=‘T’}舉例：

三、關系代數(shù)的組合操作

1、交（intersection）設關系R和關系S具有相同的元數(shù)n（即兩個關系都有n個屬性），而且相應的屬性取自同一個域。關系R和S的交記為R∩S，結果仍為n元的關系。由即屬于R又屬于S的元組組成。形式定義如下：

R∩S≡{t︱t∈R∧t∈S}t是元組變量，R和S的元數(shù)相同。關系的交可以由關系的差來表示，即：

R∩S≡R-（R-S）舉例:2、聯(lián)接(join)

聯(lián)接操作是笛卡兒積、選擇和投影操作的組合。聯(lián)接分成θ聯(lián)接和F聯(lián)接兩種。

①θ聯(lián)接：

②F聯(lián)接：?

iθjRS≡σiθ(r+j)(R×S)

如果θ為等號“=”，那么這個聯(lián)結操作稱為等值連接。

?

F

F聯(lián)接是從關系R和S的笛卡兒積中選取屬性間滿足某一公式F的元組,記為:RS

這里F是形為F1∧F2∧…∧Fn公式，每個Fi是形為iθj的式子。而i和j分別為關系R和S的第i個分量和第j個分量的序號。舉例：

3、自然聯(lián)接(naturaljoin)---特殊的等值連接

將關系R和S中公共屬性組滿足對應分量相等的元組聯(lián)接起來，并且要在結果中將重復的屬性去掉。

R

?

S≡πi1,...im(σR.A1=S.A1∧...∧R.AK=S.AK(R×S))

舉例：4、除(division)

設關系R和S的元數(shù)分別為:r、s（r>s>0），

R÷S:

是一個（r-s）元的元組的集合，是滿足下列條件的最大關系：其中每個元組t與S中每個元組u組成的新元組<t,u>必在關系R中。

R÷S的具體計算過程如下：

①T=π1，2，…，r-s（R）②W=(T×S)-R③V=π1，2，…，r-s（W）④R÷S=T–VR÷S≡π1,2,…,r-s(R)-π1,2,…,r-s((π1,2,…,r-s(R)×S)-R)舉例：四、關系代數(shù)表達式及其應用實例

工程項目零件供應數(shù)據庫PROJECTY有四個關系模式：

供應商關系：

S(SNO,SNAME,SADDR)

零件關系：

P(PNO,PNAME,COLOR,WEIGHT)

工程項目關系：J(JNO,JNAME,JCITY,BALANCE)

供應情況關系：SPJ(SNO,PNO,JNO,PRICE,QTY)πSN0,PN0(σJNO=‘J1’

(SPJ))或:πl(wèi),2(σ3='J1’(SPJ))試用關系代數(shù)表達式表示每個查詢語句。.檢索供應零件給工程J1的供應商編號SNO與零件編號PNO。πSNO（σJNO=‘J1’∧PNO=‘P1’（SPJ））3.檢索使用了編號為P3零件的工程編號和名稱。2.檢索供應零件給工程J1，且零件編號為P1的供應商編號SNO。4.檢索供應零件給工程J1,且零件顏色為紅色的供應商名稱和地址。5.檢索使用了零件編號為P3或P5零件的工程編號JNO。πJNO,JNAME（σPNO=‘P3’（J?SPJ))πSNAME,SADDR(σJNO=‘J1'∧COLOR=‘紅色’(S?SPJ?P))πJNO（σPNO=‘P3'∨PNO=‘P5’(SPJ))6.檢索至少使用了編號為P3和P5

零件的工程編號JNO。π3（σ3=8∧2=‘P3'∧7=‘P5'

(SPJ×SPJ))7.檢索不使用編號為P3零件的工程編號JNO和工程名稱JNAME。πJNO,JNAME(J)―πJNO,JNAME(σPNO=‘P3’(J?SPJ))8.檢索使用了全部零件的工程名稱JNAME。πJNAME(J?(πJNO,PNO(SPJ)÷πPNO(P))9.檢索使用零件包含編號為S1的供應商所供應的全部零件的工程編號JNO。πJNO,PNO(SPJ)÷πPNO(σSNO=‘S1’(SPJ))學生關系模式

S（SNO，SNAME，AGE，SEX，SDEPT）課程關系模式

C（CNO，CNAME，CDEPT，TNAME）學習關系模式

SC（SNO，CNO，GRADE）SNOSNAMEAGESEXSDEPTS1程宏19男計算機S3劉莎莎18女通訊S4李剛畸20男法學S6蔣天云19男國際貿易S9王莉21女計算機

CNOCNAMECDEPTTNAMEC1離散數(shù)學計算機汪宏偉C2高等數(shù)學通訊錢紅C3數(shù)據結構計算機馬良C4計算機原理計算機李兵

SNOCNOGRADES3C387S1C288S4C379S9C483S1C376S6C368S9C178S6C188S3C264S1C486S9C278五、擴充的關系代數(shù)操作1.外聯(lián)接（outerjoin）

R

?

S≡πi1,...im(σR.A1=S.A1∧...∧R.AK=S.AK(R×S))在R和S做自然聯(lián)接時，把原該舍棄的元組也保留在新關系中，同時在這些元組新增加的屬性上填上空值（null），這種操作稱為“外聯(lián)接”操作，用符號RS表示。

i、如果R和S做自然聯(lián)接時，把R中原該舍棄的元組放到新關系中，那么這種操作稱為“左外聯(lián)接”操作，用符號:RS表示。

ii、如果R和S做自然聯(lián)接時，把S中原該舍棄的元組放到新關系中，那么這種操作稱為“右外聯(lián)接”操作，用符號:RS表示。ABCabcbbfcadBCDbcdbceadbefgABCDabcdabcecadbbbfnullnullefg關系R關系SABCDabcdabcecadbbbfnullABCDabcdabcecadbnullefg2.外部并（outerunion）

如果R和S的關系模式不同，構成的新關系屬性有R和S的所有屬性組成（公共屬性只取一次），新關系的元組由屬于R或屬于S的元組構成，同時元組在新增加的屬性上填上空值(null)。ABCDabcnullbbfnullcadnullnullbcdnullbcenulladbnullefg3.半聯(lián)接（semijoin）關系R和S的半聯(lián)接操作記為R?S:

R和S的自然聯(lián)接在關系R的屬性集上的投影即：R?S≡πR（R?S）關系R關系SR?SR

?SS

?RABCDabcdabcedbcddbcecadbABCabcdbccadBCDbcdbceadbBCDbcdbceadbABCabcdbcbbfcad§4關系演算

以數(shù)理邏輯中的謂詞演算為基礎，用公式表示關系演算的條件。關系演算按所用到的變量不同可分為：元組關系演算－－－以元組為變量；域關系演算－－－以域為變量。

一、元組關系演算形式：{t∣(t)}

其中t：元組變量；

：公式，公式有原子公式及運算符組成。1.原子公式有下列三種形式：①R（t）：

R是關系名，t是元組變量。②t[i]θu[j]:t和u是元組變量，θ是算術比較運算符。③t[i]θC或Cθu[i]：

t和u是元組變量，c是常量。

2.約束變量和自由變量在一個公式中，如果一個元組變量的前面沒有存在量詞ョ或全稱量詞的符號定義，稱之為自由元組變量，否則稱為約束元組變量。

3.運算符及優(yōu)先次序為：

i.括號中運算符優(yōu)先級最高

ii.算術比較運算符最高；

iii.量詞：存在量詞ョ全稱量詞

iv.邏輯運算符：、∧、∨優(yōu)先級最高4.公式中變量的遞歸定義如下：①每個原子公式是一個公式。其中的元組變量是自由變量;

②如果1和2是元組關系演算公式，則:

1∧2,1∨2,┓1也是元組關系演算公式;③若是元組關系演算公式，則(t)()也是元組關系演算公式;④若是元組關系演算公式，則(t)()也是元組關系演算公式;⑤在元組演算公式中，各種運算符的優(yōu)先次序為：括號,算術比較運算符,ョ,,、∧、∨⑥有限次地使用上述五條規(guī)則得到的公式是元組關系演算公式，其他公式不是元組關系演算公式。5.用元組關系演算表達式表示關系運算并:R∪S{t|R（t）∨S(t)}差:R-S{t|R（t）∧S(t)}笛卡兒積:R×S

{t|(u)(v)(R(u)∧S(v)∧t[1]=u[1]∧…∧t[r]=u[r]∧t[r+1]=v[1]∧…∧t[r+s]=v[s])}

投影:πi1,i2,…ik(R)

{t|(u)|R(u)∧t[l]=u[i1]∧…∧t[iK]=u[iK]}}選擇:σF（R）

{t|R(t)∧F’}

F’是F在元組演算中的等價表示形式。

如果P1和P2是公式，在元組關系演算的公式中，存在下列等價轉換規(guī)則：

P1∧P2┐(┐P1∨┐P2)P1∨P2┐(┐P1∧┐P2）

(s)(P1(s))┐(s)(┐P1(s))(s)(P1(s))┐(s)(┐P1(s))P1P2┐P1∨P26.實例:用元組表達式形式表示下列查詢例:用元組表達式形式表示下列查詢：1.檢索供應零件給工程J1，且零件編號為P1的供應商編號SNO。{t|(u)(SPJ(u)∧u[2]=‘P1’∧u[3]=‘J1’∧t[l]=u[1])}2.檢索使用了編號為P3零件的工程編號和名稱。{t|(u)(v)(J(u)∧SPJ(v)∧v[2]=‘P3’∧u[l]=v[3]∧t[l]=u[1]∧t[2]=u[2])}{t|(u)(v)(SPJ(u)∧SPJ(v)∧u[3]=v[3]∧u[2]=‘P3’∧v[2]=‘P5’∧t[l]=u[3])}3.檢索至少使用了編號為P3和P5零件的工程編號JNO。{t|(u)(v)(J(u)∧SPJ(v)∧((u[l]=v[3])v[2]≠’P3’)

∧t[1]=u[1]∧t[2]=u[2])}4.檢索不使用編號為P3零件的工程編號JNO和工程名稱SNAME。5.檢索使用了全部零件的工程名稱JNAME。{t|(u)(v)(w)(J(u)∧P(v)∧SPJ(w)∧u[l]=w[3]∧v[1]=w[2]∧t[1]=u[2])}{t|(u)(SPJ(u)∧(v)(SPJ(v)∧(v[1]=‘S1’(w)(SPJ(w)

∧w[3]=u[3]∧w[2]=v[2])))∧t[l]=u[3])}6.檢索使用零件包含編號為S1供應商所供應的全部零件的工程編號。

二、域關系演算域演算表達式的定義類似于元組演算表達式的定義，

所不同的是公式中用域變量代替元組變量的每一個分量，

域變量的變化范圍是某個值域而不是一個關系。

1、域演算表達式：一般形式:{t1t2…tk∣P(t1,t2,…,tk)｝

其中t1、t2、…、tk分別是元組變量t的各個分量的域變量，

P是域演算公式。①原子公式有下列兩種形式：

i．R（t1…tk）：R是K元關系，每個ti是域變量或常量。

ii．xθy,其中x,y是域變量或常量，但至少有一個是域變量，θ是算術比較運算符。②域關系演算的公式中也可使用∧、∨、和=>等邏輯運算符也可用(x)和（x）形成新的公式，但變量x是域變量，不是元組變量。自由域變量、約束域變量等概念和元組演算中一樣。2.元組表達式到域表達式的轉換規(guī)則：①對于k元的元組變量t,引入k個域變量t1,t2,…,tk,

在公式中t用t1,t2,…,tk替換，元組分量t[i]用ti替換。②對于每個量詞(u)或（u），若u是m元的元組變量，則引入m個新的域變量u1,u2,…,um。在量詞的轄域內，u用u1u2…um替換，u[i]用ui替換，

(u)用(u1)…(um)替換，

(u）用（u1）…(um)替換。3.舉例

安全運算：

不產生無限關系和無窮次驗證的運算稱為安全運算，相應的表達式稱為是安全表達式。所采用的措施稱為安全約束。安全約束集DOM():

公式中的常量和中所出現(xiàn)關系的所有屬性值組成的集合。三、關系運算的安全性和等價性

1.關系運算的安全性

{t|R(t)}無限關系

驗證(u)(w(u))為’T’

或（u）(w(u))為’F’

無窮驗證

2.關系運算的等價性并、差、笛卡兒積、投影和選擇是關系代數(shù)最基本的操作，并構成了關系代數(shù)運算的最小完備集?？梢宰C明，在這個基本上，關系代數(shù)、安全的元組關系演算、安全的域關系演算在關系的表達和操作能力上是等價的。

§5查詢優(yōu)化關系代數(shù)表達式的優(yōu)化問題:

在關系代數(shù)表達式中需要指出若干關系的操作步驟。系統(tǒng)應該以什么樣的操作順序，才能做到既省時間，又省空間，而且效率也比較高呢？

如何花費較少的時間和空間，有效地執(zhí)行笛卡兒積操作.

一、查詢優(yōu)化的總目標選擇有效的策略，求得給定關系代數(shù)表達式的值，達到提高DBMS系統(tǒng)效率的目標。例:學生數(shù)據庫：S(SNO,SNAME,SEX,AGE,SDEPT)C(CNO,CNAME,CDEPT,TNAME)SC(SNO,CNO,GRADE)檢索選修C2課程的學生的學號和姓名,用關系代數(shù)表達式表示：

E1=πS.SNO,SNAME（σS.SNO=SC.SNO∧SC.CNO=‘C2’（S×SC））

E2=πS.SNO,SNAME（σSC.CNO=‘C2’（S?SC））

E3=πS.SNO,SNAME（S?σSC.CNO=‘C2’（SC））這三個關系代數(shù)表達式是等價的，但執(zhí)行的效率大不一樣。顯然，求El，E2，E3的大部分時間是花在聯(lián)接操作上的。

二、代數(shù)表達式的等價變換規(guī)則

1、

聯(lián)接和笛卡兒積的交換律

E1

E2≡E2E1E1E2≡E2E1E1×E2≡E2×E1?

F?

F??2．聯(lián)接和笛卡兒積的結合律

（E1E2）E3≡E1（E2E3）（E1E2）E3≡E1（E2E3）

（E1×E2）

×

E3≡E1×（E2×E3）?

F1?

F1?

F2?

F2????

3.投影的串接設L1，L2，…，Ln為屬性集，并且L1L2…Ln，成立：

πL1（πL2（…（πLn（E））…））≡πL1（E）4．

選擇的串接

σF1（σF2（E））≡σF1∧F2（E）由于F1∧F2=F2∧F1，選擇的交換律也成立：

σF1（σF2（E））≡σF2（σF1（E））

5．

選擇和投影操作的交換

πL（σF（E））≡σF（πL（E））要求條件F只涉及到L中的屬性,如果F還涉及到不在L中的屬性集L1：

πL（σF（E））≡πL（σF（πL∪L1（E）））6．

選擇對笛卡兒積的分配律

σF（E1×E2）≡σF（E1）×E2σF（E1×E2）≡σF1（E1）×σF2（E2）

σF（E1×E2）≡σF2（σF1（E1）×E2）7.

選擇對并的分配律

σF（E1∪E2）≡σF1（E1）∪σF2（E2）

8．選擇對集合差的分配律

σF（E1－E2）≡σF（E1）－σF（E2）

9．選擇對自然聯(lián)接的分配律

σF（E1?E2）≡σF（E1）?

σF（E2）10．投影對笛卡兒積的分配律

πL1∪L2（E1×E2）≡πL1（E1）×πL2（E2）11．投影對并的分配律

πL（E1∪E2）≡πL（E1）∪πL（E2）12．選擇與聯(lián)接操作的結合

σF1（E1E2）≡E1

E2

13．并和交的交換律

E1∪E2≡E2∪E1E1∩E2≡E2∩E114．并和交的結合律

（E1∪E2）∪E3≡E1∪（E2∪E3）（E1∩E2）∩E3≡E1∩（E2∩E3）?

F2?F2∧F2

三、優(yōu)化的一般策略

(1--6)(1)在關系代數(shù)表達式中盡可能早地執(zhí)行選擇操作。(2)把笛卡兒積和其后的選擇操作合并成F聯(lián)接運算。(3)同時計算一連串的選擇和投影操作，以免分開運算造成多次掃描文件，節(jié)省操作時間。(4)如在一個表達式中多次出現(xiàn)某個子表達式，可先對該子表達式進行計算并保存結果，以免重復計算。

(5)適當?shù)貙﹃P系文件進行預處理。

(6)在計算表達式前應先估計一下怎么計算合算。

三、關系代數(shù)表達式的優(yōu)化算法輸入：一棵關系代數(shù)表達式的語法樹。

輸出：計算表達式的一個優(yōu)化序列。

方法:

依次執(zhí)行下面每一步。①使用等價變換規(guī)則⑷把每個形為σF1∧…∧Fn（E）的子表達式轉換成選擇串接形式：σF1（…σFn（E））…）②對每個選擇操作，使用規(guī)則⑷～⑼，盡可能把選擇操作移近樹的葉端（即盡可能早地執(zhí)行選擇操作）。③對每個投影操作，使用規(guī)則(3)，(5)，(10)和(11)，盡可能把投影操作移近樹的葉端。④使用規(guī)則⑶～⑸，把選擇和投影合并成單個選擇、單個投影或一個選擇后跟一個投影。⑤對上述步驟得到的語法樹的內結點進行分組。分組原則：

a、每個二元運算(×、∪、－)結點與其直接祖先(不超過其他的二元運算結點）的一元運算結點(σ或π)分為一組。如果它的子孫結點一直到葉都是一元運算符(σ或π),則也并入該組。b、如果二元運算是笛卡兒積，而且后面不是與它組合成等值聯(lián)接的選擇時，則不能將選擇與這個二元運算組成同一組。⑥生成一個程序，每一組結點的計算是程序中的一步，各步的順序是任意的只要保證任何一組不會在它的子孫組之前計算。

舉例:

學生數(shù)據庫：S(SNO,SNAME,SEX,AGE,SDEPT)C(CNO,CNAME,CDEP