關(guān)系數(shù)據(jù)模型.PPT

1、湖南工學(xué)院計算機(jī)系湖南工學(xué)院計算機(jī)系數(shù)據(jù)庫原理數(shù)據(jù)庫原理Principles of Database第第2 2章章 關(guān)系數(shù)據(jù)模型關(guān)系數(shù)據(jù)模型 n1970年，美國IBM公司的E. F. Codd在發(fā)表的著名論文A Relational Model of Data for Large Shared Data Banks中首先提出了關(guān)系數(shù)據(jù)模型，之后他又發(fā)表了多篇文章，奠定了關(guān)系數(shù)據(jù)庫的理論基礎(chǔ)，標(biāo)志著數(shù)據(jù)庫系統(tǒng)新時代的來臨。20世紀(jì)80年代以來，計算機(jī)廠商推出的數(shù)據(jù)庫管理系統(tǒng)（DBMS）幾乎都支持關(guān)系模型，非關(guān)系系統(tǒng)的產(chǎn)品也都加上了關(guān)系接口。關(guān)系數(shù)據(jù)庫系統(tǒng)幾乎成了當(dāng)今數(shù)據(jù)庫的代名詞。 第第2 2章

2、章 關(guān)系數(shù)據(jù)模型關(guān)系數(shù)據(jù)模型n【本章掌握內(nèi)容】 1、關(guān)系的定義 2、關(guān)系代數(shù) 3、關(guān)系演算【本章了解內(nèi)容】 1、關(guān)系運(yùn)算的安全限制 2、關(guān)系代數(shù)表達(dá)式的優(yōu)化第第2 2章章 關(guān)系數(shù)據(jù)模型關(guān)系數(shù)據(jù)模型2.1 關(guān)系數(shù)據(jù)模型的基本概念關(guān)系數(shù)據(jù)模型的基本概念 n2.1.1 關(guān)系、元組、屬性、域、分量、關(guān)系模式n2.1.2 關(guān)鍵字 n2.1.3 關(guān)系數(shù)據(jù)模型的集合論定義 n2.1.4 關(guān)系數(shù)據(jù)模型的完整性約束 1關(guān)系關(guān)系 n每一個關(guān)系用一張二維表來表示，常稱為表。每一個關(guān)系表都有個區(qū)別于其他關(guān)系表的名稱，稱為關(guān)系名。關(guān)系是概念模型中同一類實體及實體之間聯(lián)系集合的數(shù)據(jù)模型表示，如圖2-1所示的員工人事數(shù)據(jù)表

3、。 屬性 元組 員工編號 姓名 年齡 性別 部門號 430425 王天喜 25 男 Deno1 430430 莫玉 27 女 Deno2 430211 肖劍峰 33 男 Deno3 430121 楊瓊英 23 女 Deno2 430248 趙繼平 41 男 Deno3 關(guān)系模式 關(guān)系 n2元組n二維表中的每一行數(shù)據(jù)總稱為一個元組或記錄。一個元組是對應(yīng)概念模型中一個實體的所有屬性值的總稱。由若干個元組就可構(gòu)成一個具體的關(guān)系，一個關(guān)系中不允許有兩個完全相同的元組。 n3屬性 n二維表中的每一列即為一個屬性，每個屬性都有一個顯示在每一列首行的屬性名。在一個關(guān)系表當(dāng)中不能有兩個同名屬性。關(guān)系的屬性對應(yīng)

4、概念模型中實體型及聯(lián)系的屬性。n4域 n關(guān)系中每個屬性的值是有一定變化范圍，每一個屬性所對應(yīng)的變化范圍叫做屬性的變域或簡稱域，它是屬性值的集合，關(guān)系中所有屬性的實際取值必須來自于它對應(yīng)的域。n5分量 n一個元組在一個屬性域上的取值稱為該元組在此屬性上的分量。 n6關(guān)系模式 n二維表的表頭那一行稱為關(guān)系模式，即一個關(guān)系的關(guān)系名及其全部屬性名的集合。關(guān)系模式是概念模型中實體型及實體型之間聯(lián)系的數(shù)據(jù)模型表示。 一般表示為：關(guān)系名（屬性名1，屬性名2，屬性名n）關(guān)系模式和關(guān)系是型與值的聯(lián)系關(guān)系模式和關(guān)系是型與值的聯(lián)系 n關(guān)系模式指出了一個關(guān)系的結(jié)構(gòu)；而關(guān)系則是由滿足關(guān)系模式結(jié)構(gòu)的元組構(gòu)成的集合。關(guān)系模

5、式是穩(wěn)定的、靜態(tài)的，而關(guān)系則是隨時間變化的、動態(tài)的。但通常在不引起混淆的情況下，兩者可都稱為關(guān)系。2.1.2 關(guān)鍵字關(guān)鍵字n在關(guān)系數(shù)據(jù)庫中，對每個指定的關(guān)系經(jīng)常需要根據(jù)某些屬性的值來唯一地操作一個元組，也就是要通過某個或某幾個屬性來唯一地標(biāo)識一個元組，把這樣的屬性或?qū)傩越M稱為指定關(guān)系的關(guān)鍵字。n1超關(guān)鍵字 n2候選關(guān)鍵字 n3合成關(guān)鍵字 n4主關(guān)鍵字 n5主屬性 n6外部關(guān)鍵字 1超關(guān)鍵字超關(guān)鍵字n在一個關(guān)系中若通過一個屬性集合的取值就能唯一確定每一個元組，即該關(guān)系中所有元組在這個屬性集合上的分量是不同的，則稱該屬性集合為該關(guān)系的超關(guān)鍵字或者簡稱為超鍵（super key）。因此超關(guān)鍵字具有唯

6、一的標(biāo)識性。 例：圖2-12候選關(guān)鍵字候選關(guān)鍵字 n如果某一集合是超關(guān)鍵字，但去掉其中任意屬性后就不再是超關(guān)鍵字，則稱該屬性集合為候選關(guān)鍵字（Candidate key）。候選關(guān)鍵字不但要求屬性集合具有唯一的標(biāo)識性，還要求屬性集合的元素數(shù)目最少。 例：圖2-13合成關(guān)鍵字 n當(dāng)某個候選關(guān)鍵字包含多個屬性時，則稱該候選關(guān)鍵字為合成關(guān)鍵字（Composite key）。 4主關(guān)鍵字 n為關(guān)系組織物理文件存儲時，通常選用一個候選關(guān)鍵字作為插入、刪除、檢索元組的操作變量。這個被選用的候選關(guān)鍵字稱為主關(guān)鍵字（Primary key），有時也稱為“主碼”。5主屬性 n包含在任何一個候選關(guān)鍵字之中的屬性稱為

7、主屬性（Main attribute），不包含在任何一個候選關(guān)鍵字之中的屬性稱為非主屬性。 6外部關(guān)鍵字外部關(guān)鍵字 n如果關(guān)系R1的某一（些）屬性A不是R1的候選關(guān)鍵字，但是在另一關(guān)系R2中屬性A是候選關(guān)鍵字，則稱A是R1的外部關(guān)鍵字（Foreign key），有時也稱“外碼”。 學(xué)生（學(xué)號，姓名，性別，年齡，籍貫） 學(xué)生選課（學(xué)號，課程號，成績） 2.1.3 關(guān)系數(shù)據(jù)模型的集合論定義關(guān)系數(shù)據(jù)模型的集合論定義 n關(guān)系數(shù)據(jù)模型是從集合論中的關(guān)系（Relation）概念發(fā)展過來的，它有嚴(yán)格的數(shù)學(xué)理論基礎(chǔ)。 1笛卡兒積 2關(guān)系 3關(guān)系模式 1笛卡兒積笛卡兒積 n定義2.1 設(shè)有一個有限集合D1，D2

8、，D3、，Dn，則在D1，D2，D3，Dn上的笛卡兒積（Cartesian Product）為： 其中每一個元素 (d1，d2，d3，dn)- 叫做一個n元組（n-tuple）或簡稱元組（Tuple）。元素中的每一個值叫做一個分量（Component）。 12123(,) |,1,2,3, nniiDDDdddddD in笛卡兒積的元素個數(shù)笛卡兒積的元素個數(shù)若Di（i=1,2,3,n）為有限集，其基數(shù)（Cardinal Number）為mi (i=1,2,3,n)，則D1D2D3Dn的基數(shù)為：1niiMm 例2.1 設(shè)有三個集合如下：A=a1，a2，B=b1，b2，C=c1，c2則集合A、B、

9、C上的笛卡兒積為 ABCa1 b1 c1 a1 b1 c2 a1 b2 c1 a1 b2 c2 a2 b1 c1 a2 b1 c2 a2 b2 c1 a2 b2 c2 2關(guān)系關(guān)系 n笛卡兒積D1D2D3Dn的任意一個子集叫做在D1，D2，D3，Dn上的一個n元關(guān)系，簡稱關(guān)系（Relation）。每個關(guān)系都有一個關(guān)系名。 n二維表的名稱就是關(guān)系的名稱，二維表的每一列都是一個屬性。n元關(guān)系就會有n個屬性。一個關(guān)系中的每一個屬性都有一個名字，且各個屬性的屬性名都不同，對應(yīng)參與笛卡兒積運(yùn)算的每個集合的名稱。一個屬性的取值范圍Di (i=1,2,3,n)稱為該屬性的域（Domain）。 3關(guān)系模式關(guān)系模

10、式 n實際上完整的關(guān)系模式的數(shù)學(xué)定義為： R (U、D、dom、F) 其中：R為關(guān)系模式名，U為組成該關(guān)系的屬性名的集合，D為屬性組U中屬性所來自的域的集合，dom為屬性向域映像的集合，F(xiàn)為屬性間函數(shù)依賴關(guān)系的集合。n關(guān)系模式通常簡寫為： R (U)或R (A1，A2，A3，An) 其中：R為關(guān)系名，Ai (i=1,2,3,n)為屬性名。域名構(gòu)成的集合及屬性向域映像的集合一般為關(guān)系模式定義中的屬性的類型和長度。 2.1.4 關(guān)系數(shù)據(jù)模型的完整性約束關(guān)系數(shù)據(jù)模型的完整性約束 n關(guān)系模型中共有四類完整性約束：域完整性、實體完整性、參照完整性、用戶自定義完整性。其中實體完整性和參照完整性是關(guān)系模型必

11、須滿足的完整性約束條件，任何關(guān)系系統(tǒng)都應(yīng)該能自動維護(hù)。 n1域完整性 關(guān)系數(shù)據(jù)模型規(guī)定元組在屬性上的分量必須來自于屬性的域，這是由完整性約束指出的。域完整性約束（Domain Integrity Constraint）是最簡單、最基本的約束。n2實體完整性 因此在具體的RDBMS中，實體完整性（Entity Integrity）應(yīng)變?yōu)椋喝我魂P(guān)系主關(guān)鍵字之中的屬性不能為空。 3參照完整性參照完整性 參照完整性約束（Referential Integrity Constraint）就是不同關(guān)系之間或同一關(guān)系的不同元組必須滿足的約束。它要求關(guān)系的外部關(guān)鍵字和被引用關(guān)系的主關(guān)鍵字之間遵循參照完整性約束

12、：設(shè)關(guān)系R1有一外部關(guān)鍵字FK，它引用關(guān)系R2的主關(guān)鍵字PK，則R1中任一元組在外部關(guān)鍵字FK上的分量必須滿足以下兩種情況： n等于R2中某一元組在主關(guān)鍵字PK上的分量。n取空值（FK中每一個屬性的分量都是空值）。4用戶自定義完整性用戶自定義完整性 n用戶自定義的完整性約束就是對某一具體關(guān)系數(shù)據(jù)庫的約束條件，它反映了某一具體應(yīng)用所涉及的數(shù)據(jù)必須滿足的語義要求。 2.2 關(guān)系的運(yùn)算關(guān)系的運(yùn)算 關(guān)系操作可以使用兩種方法定義。n一種方式是基于代數(shù)的定義，稱為關(guān)系代數(shù)；n另一種方法是基于邏輯的定義，稱為關(guān)系演算。根據(jù)使用的變量的不同，關(guān)系演算又分為元組關(guān)系演算和域關(guān)系演算。 2.2.1 關(guān)系代數(shù)關(guān)系代

13、數(shù) 關(guān)系代數(shù)運(yùn)算是通過對關(guān)系的運(yùn)算來表達(dá)查詢的。它的運(yùn)算對象是關(guān)系，運(yùn)算結(jié)果也是關(guān)系。關(guān)系代數(shù)的運(yùn)算可分為兩類：n（1）傳統(tǒng)的集合運(yùn)算：并、差、交和乘積。n（2）專門的關(guān)系運(yùn)算，即專門針對關(guān)系數(shù)據(jù)庫設(shè)計的運(yùn)算：選擇、投影、連接和除。1傳統(tǒng)的集合運(yùn)算傳統(tǒng)的集合運(yùn)算 （1）并 （2）差 （3）交 （4）乘積設(shè)關(guān)系R有m個屬性、i個元組；關(guān)系S有n個屬性、j個元組，則關(guān)系R和S的乘積是一個有（m+n）個屬性的元組集合。每個元組的前r個分量來自關(guān)系R的一個元組，后s個分量來自S的一個元組，且元組的數(shù)目有ij個。 |( )( )RSt R tS t |( )( )RSt R tS t |( )( )RS

14、t R tS t2專門的關(guān)系運(yùn)算專門的關(guān)系運(yùn)算 n在關(guān)系運(yùn)算中，由于關(guān)系數(shù)據(jù)結(jié)構(gòu)的特殊性，在關(guān)系代數(shù)中除了需要一般的集合運(yùn)算外，還需要一些專門的關(guān)系運(yùn)算，包括選擇、投影、連接和除等。 （1）選擇）選擇 n選擇運(yùn)算是在關(guān)系R中選擇滿足條件F的所有元組組成的一個關(guān)系。記作F(R)=t | tRF(t)=true其中，F(xiàn)表示選擇條件，它是一個邏輯表達(dá)式，取值為“true”或“false”。邏輯表達(dá)式F的基本形式為：X1Y1X2Y2表示比較運(yùn)算符，它可以是、和。X1、Y1等是屬性名或簡單函數(shù)。屬性名也可以用它在關(guān)系中從左到右的序號來代替。表示邏輯運(yùn)算符，它可以是。 表示任選項 （2）投影）投影 投影運(yùn)

15、算是從一個關(guān)系中選取某些屬性（列），并對這些屬性進(jìn)行重新排列，最后從得出的結(jié)果中刪除重復(fù)的行，從而得到一個新的關(guān)系。設(shè)R是n元關(guān)系，R在其分量Ai1，Ai2，Aim (mn；i1，i2，im為1到m之間的整數(shù)，可不連續(xù))上的投影操作定義為：il,i2im=t | t=R即取出所有元組在特定分量Ai1，Ai2，Aim上的值。（3）連接）連接 連接是從兩個關(guān)系的廣義笛卡兒積中選取屬性間滿足一定條件的元組。連接又稱連接。記作：其中，A和B分別是R和S上個數(shù)相等且可比的屬性組（名稱可不相同）。AB作為比較公式F，F(xiàn)的一般形式為F1F2Fn，每個Fi是形為trAitsBj的公式。對于連接條件的重要限制是

16、條件表達(dá)式中所包含的對應(yīng)屬性必須來自同一個屬性域，否則是非法的，即屬性的來源必須相同。 | ()r srsrsA BA BRSt tt ttRtStA t BRS n 等值連接 n一個連接表達(dá)式中的所有運(yùn)算符都取“=”時的連接就是等值連接，是從兩個關(guān)系的廣義笛卡兒乘積中選取A、B屬性集間相等的元組。 n 自然連接n等值連接可能出現(xiàn)數(shù)據(jù)冗余，而自然連接將去掉重復(fù)的列。Att() (Att( ) )()RSBt Bt BRSRS自然連接與等值連接的區(qū)別自然連接與等值連接的區(qū)別 n等值連接進(jìn)行相等比較的屬性可以是相同的屬性，也可以是不同的屬性；而自然連接進(jìn)行相等比較的屬性必須是相同的屬性。n自然連接

17、必須去掉重復(fù)的屬性，即去掉進(jìn)行相等比較的屬性，而等值連接則無此要求。n自然連接一般用于有公共屬性的情況。如果兩個關(guān)系沒有公共屬性，那么它們的自然連接就退化為廣義笛卡兒乘積。如果是兩個關(guān)系模式完全相同的關(guān)系自然連接運(yùn)算，則變?yōu)榻贿\(yùn)算。（4）除）除 給定關(guān)系R（X，Y）和S（Y，Z），其中X，Y，Z為屬性或?qū)傩约?。R中的Y和S中的Y可以有不同的屬性名，但必須出自相同的域集。RS是滿足下列條件的最大關(guān)系：其中每個元組t與S中的各個元組s組成的新元組必在R中。定義形式為：n RS的新關(guān)系屬性是由屬于R但不屬于S的所有屬性構(gòu)成的。n RS的任一元組都是R中某元組的一部分。但必須符合下列要求：即任取屬于R

18、S的一個元組t，則t與S的任一元組相連后，結(jié)果都為R中的一個元組。n ( )( ) |( ),XXXXRSRRSRt tRsSt sR 且(, )( ,)(, )( )YR X YS Y ZR X YS例例2.14 查詢所有女生的基本情況。查詢所有女生的基本情況。 n分析：關(guān)系Student的屬性已包含了查詢所需的數(shù)據(jù)，現(xiàn)要查詢女生情況，只需對關(guān)系表做水平分解的條件運(yùn)算即可。 Student(Sex=女(Student)例例2.15 查詢年齡大于查詢年齡大于20歲的男生的基本歲的男生的基本情況。情況。 分析：本例和例2.14的求解思想一樣，應(yīng)先做關(guān)系的水平選擇分解運(yùn)算，再做投影運(yùn)算。20()s

19、tudentsexagestudent男例例2.16 查詢張小倩同學(xué)所選修的課程號和查詢張小倩同學(xué)所選修的課程號和相應(yīng)的成績。相應(yīng)的成績。分析：題目中所包含的數(shù)據(jù)信息有“張小倩”、“課程號”和“成績”。其中“張小倩”是包含在Student關(guān)系表中的姓名屬性值，“課程號”和“成績”是Study關(guān)系表中的屬性。因此本例中所包含的信息分布在兩個不同的關(guān)系表中。在Study關(guān)系表中又存在外碼“Sno”與Student關(guān)系表相聯(lián)系，所以可以使用自然連接運(yùn)算將兩個關(guān)系表連接在一起形成一個新的關(guān)系。 ,()Cno gradeSnameStudentStudy張小倩例例2.17 查詢選修了查詢選修了C語言的學(xué)

20、生的學(xué)號和語言的學(xué)生的學(xué)號和姓名。姓名。分析：題設(shè)中所包含的信息有“C語言”、“學(xué)號”和“姓名”。其中“C語言”是Course關(guān)系表中的課程名屬性值，“學(xué)號”和“姓名”是Student關(guān)系表中的屬性。這兩個關(guān)系表雖沒有直接的外碼聯(lián)系，但它們分別與Study關(guān)系表有外碼聯(lián)系。因此要進(jìn)行這樣的查詢必須將三個關(guān)系表都自然連接在一起才能具備題目中的所有信息。,()Sno SnameCnameCStudentStudyCourse語言例例2.18 查詢選修了全部課程的學(xué)生的學(xué)查詢選修了全部課程的學(xué)生的學(xué)號。號。分析：題目中要查詢的是study表中選修了全部課程的學(xué)號，使用除法可以達(dá)到這個目的。但Stud

21、y關(guān)系表有三個屬性“Sno”、“Cno”、“Grade”，直接用StudyCourse得出的關(guān)系模式會包含“Sno”和“Grade”屬性而且達(dá)不到題目的要求。因此在進(jìn)行除法運(yùn)算之前先要對Study關(guān)系表進(jìn)行投影操作，使得進(jìn)行除運(yùn)算之后只含有一個屬性“Sno”。 Sno,Cno(Study)Course 例例2.19 查詢所有沒選查詢所有沒選C04號課程的學(xué)生的號課程的學(xué)生的學(xué)號。學(xué)號。分析：要實現(xiàn)題目的查詢目的，可以先查詢出選了C04號課程的學(xué)生有哪些，再用總的學(xué)生集合減去選了C04號課程的學(xué)生集合。 Sno(Student)Sno(Cno=co4(Study) 2.2.3 關(guān)系演算關(guān)系演算

22、關(guān)系演算是利用謂詞演算來表達(dá)關(guān)系操作的一種方法。按謂詞變量的不同，關(guān)系演算又分為兩種：n一種是元組關(guān)系演算，以元組為變量，簡稱元組演算；n另一種是域關(guān)系演算，以域為變量，簡稱域演算。在元組演算中，元組關(guān)系演算表達(dá)式的一般形式為t/(t)。其中，t是元組變量，它表示一個定長的元組。(t)為元組演算公式，簡稱公式，它由原子公式和運(yùn)算符組成。 1原子公式原子公式 原子公式是構(gòu)成關(guān)系演算最基本的單位，它有三種形式。 n1）R(t)，其中R是關(guān)系名，t是元組變量。R(t)表示：t是關(guān)系R的一個元組。n（2）tiuj，其中t和u是元組變量，是比較運(yùn)算符。該原子公式表示：元組t的第i個分量與元組u的第j個分

23、量之間滿足關(guān)系。n（3）tic或cti，其中t是元組變量，c是一個常量，該原子公式表示：元組t的第i個分量與常量c之間滿足關(guān)系。2運(yùn)算符運(yùn)算符 關(guān)系演算使用的運(yùn)算符有：算術(shù)，比較運(yùn)算符、量詞、邏輯運(yùn)算符和括號。運(yùn)算符的優(yōu)先級關(guān)系為： n（1）算術(shù)，比較運(yùn)算符的優(yōu)先級最高。n（2）存在量詞和全稱量詞的優(yōu)先級次之，而存在量詞的優(yōu)先級高于全稱量詞。n（3）邏輯運(yùn)算符的優(yōu)先級最低。n（4）若有括號，則括號的優(yōu)先級最高。4元組關(guān)系演算與關(guān)系代數(shù)的等價性元組關(guān)系演算與關(guān)系代數(shù)的等價性 n （1）并 n（2）差n（3）廣義笛卡兒積 n（4）選擇 n（5）投影 |( )( )RSt R tS t |( )(

24、)RSt R tS t( ) |( )FRt R tFtrue12(), ,( )|()( ( )1 )mmi iiimRtu R utu it mu i(1)|()()( ( )( )11mmnRStuvR uS vtu 11 )t mu mt mvt mnv n元組演算實例元組演算實例 n（1）所有女學(xué)生的學(xué)生信息 xSrudent|Student(x)xSex=女 n（2）男生的學(xué)號，年齡 n（3）所有年齡小于22的男生姓名，課程號，成績 Sno,Age|()(Student( )SexSnoSnoAgeAge)xyyyyxyx男SnoSnoCnoCnoGradeGrade)SnameS

25、name)zyzxzxyx Sname,Sno,Age|()(Student( )SexAge22()(Study( )xyyyyzz 男2.3 查詢優(yōu)化查詢優(yōu)化 n查詢檢索是數(shù)據(jù)庫系統(tǒng)最主要的功能，查詢速度的快慢直接影響系統(tǒng)效率。關(guān)系模型雖有堅實的理論基礎(chǔ)，但其主要的缺點就是查詢效率較低。若不能解決這個問題，則關(guān)系模型也很難得到推廣。 2.3.2 查詢優(yōu)化的一般準(zhǔn)則查詢優(yōu)化的一般準(zhǔn)則 （1）盡可能早地執(zhí)行選擇操作。在查詢優(yōu)化中，這是最基本的一條。（2）在一些使用頻率較高的屬性上，建立索引和分類排序。（3）同一關(guān)系上的投影和選擇運(yùn)算同時進(jìn)行，這樣可避免重復(fù)掃描關(guān)系。（4）把選擇與選擇前面的笛卡

26、兒積結(jié)合起來成為一個連接運(yùn)算。（5）把投影運(yùn)算與其前后的雙目運(yùn)算結(jié)合起來進(jìn)行，以免重復(fù)掃描文件。（6）找出公共子表達(dá)式，并將該表達(dá)式結(jié)果預(yù)先計算并加以保留，需要時直接從文件讀取，以免重復(fù)計算。 2.3.4 關(guān)系代數(shù)表達(dá)式優(yōu)化的算法關(guān)系代數(shù)表達(dá)式優(yōu)化的算法 關(guān)系查詢優(yōu)化的步驟一般有以下四個： n（1）把查詢結(jié)果轉(zhuǎn)換成內(nèi)部表示形式，一般是語法樹。n（2）選擇合適的等價變換規(guī)則，把語法樹轉(zhuǎn)換成優(yōu)化形式。n（3）選擇底層的操作算法，根據(jù)存取路徑、數(shù)據(jù)的存儲分布情況等，為語法樹中的每個操作選擇合適的操作算法。n（4）生成查詢執(zhí)行方案。由以上三條最后生成了一系列的內(nèi)部操作。根據(jù)這些內(nèi)部操作要求的執(zhí)行次序，確定一個執(zhí)行方案。 2.3.4 關(guān)系代數(shù)表達(dá)式優(yōu)化的算法關(guān)系代數(shù)表達(dá)式優(yōu)化的算法（1）利用關(guān)系代數(shù)等價變換規(guī)則4把形如F1F2Fn(E)的式子變換為F1(F2(F(E) （2）對于每一個選擇，使用變化規(guī)則4到規(guī)則8，盡可能把它移到樹的葉端（即盡可能使它提早一點執(zhí)行）。（3）對每一個投影，利用變化規(guī)則3、5、9，也把它盡可能移到樹的葉端。（4）利用規(guī)則3、4、5把選擇和投影串接成單個選擇、單個投影或一個選擇后跟一個投影，使多個選擇或投影能同時執(zhí)行或在一次投影中同時完成。（5）將上述得到的語法樹的內(nèi)結(jié)點分組，每個二目運(yùn)算（、）結(jié)點與其直接祖先被分為一組（這些直接祖先由、表示）。如果它