第2章關(guān)系數(shù)據(jù)模型

Chapter2RelationDataModel本章重點

本章講解了關(guān)系模型的基本概念，包括關(guān)系的定義、關(guān)系模型的三要素（數(shù)據(jù)結(jié)構(gòu)、關(guān)系操作和關(guān)系的完整性）和關(guān)系的特點等；介紹了關(guān)系代數(shù)的各種運算和關(guān)系數(shù)據(jù)庫查詢的優(yōu)化。本章重點要求掌握關(guān)系模型的重要概念，掌握關(guān)系代數(shù)表達式的運用，理解關(guān)系數(shù)據(jù)庫查詢優(yōu)化的內(nèi)容。2.1關(guān)系模型的基本概念

2.1.1關(guān)系的通俗解釋

在關(guān)系模型中，信息被組織成若干張二維表的結(jié)構(gòu)，每一張二維表稱為一個關(guān)系，每個表中的信息只用來描述客觀世界中的一件事情。例如，在學(xué)校中，為了表達學(xué)生與專業(yè)的“所屬”關(guān)系，學(xué)生與課程的“選修”關(guān)系，教師與課程的“任教”關(guān)系，可以制成如下表格：

表2.1學(xué)生選課登記表

下面結(jié)合該表介紹關(guān)系模型中的基本概念。

1．表(Table)，也稱關(guān)系，由表名、列名及若干行組成。表的結(jié)構(gòu)也稱關(guān)系模式，如表2.l的關(guān)系模式為：學(xué)生選課登記表(學(xué)號，姓名，專業(yè)，選修課程，任課教師)。

2．列(Field)，也稱屬性。表中的每個列都包含同一類的信息。表中的列是無序的。

3．行(Row)，也稱元組。表中每個行由若干個字段值組成，用來描述一個對象的信息。每個字段值描述該對象的某種性質(zhì)或?qū)傩?。表中的行也是無序的,一般不能出現(xiàn)完全相同的兩個行。

4．鍵碼(Key)，也稱關(guān)鍵字。對表中的某個屬性或?qū)傩越M，若它們的值唯一地標識一個元組，則它就是鍵碼。如表2.l中，屬性組(學(xué)號，選修課程)就是鍵碼，它可決定整個元組的性質(zhì)。

5．值域(Domain)，屬性的取值范圍。在表中每個列都以某個值域為基礎(chǔ)從某個域中取得數(shù)據(jù)。例如，學(xué)號的值域是11位整數(shù)等，在關(guān)系模型中允許多個列從同一值域中取值。

6．表名和列名的命名規(guī)定：表名在整個數(shù)據(jù)庫中必須唯一；列名在一個表中必須唯一，但在不同的表中可以出現(xiàn)相同的名字；表名和列名應(yīng)盡可能帶有一定的意義并盡量簡單。

2.1.2關(guān)系的數(shù)學(xué)定義定義2.1域(Domain)是值的集合。定義2.2給定一組域D1,D2,...,Dn，這些域中可以有相同的域，D1,D2,...,Dn的笛卡兒積為：D1×D2×...×Dn＝{(d1,d2,…,dn)|di∈Di,i=1,2,…,n}，其中每一個元素(d1，d2,...，dn)叫作一個n元組或簡稱為元組；元素中每一個值di叫做一個分量。若Di(i=1，2，…，n)為有限集，其基數(shù)為mi(i＝1,...，n)，則D1×D2×…×Dn的基數(shù)為:定義2.3若D1×D2×…×Dn為笛卡兒積，則它的有意義子集叫做在域

D1×D2×…×Dn上的關(guān)系，可以用R(D1，D2，…，Dn)來表示。這里R表示關(guān)系名，n是關(guān)系的目。

關(guān)系是一個二維表，表的每行對應(yīng)一個元組，表的每列對應(yīng)一個域。因域可以相同，故為了加以區(qū)分，對每列起一個名字，稱為屬性Ai，n目關(guān)系必有n個屬性。對關(guān)系的最基本要求是R1NF。關(guān)系的一般表示形式為:

R(A1，A2，…，An)關(guān)系有以下性質(zhì)：

（1）每列中的分量是同類型數(shù)據(jù)，來自同一個域；

（2）不同列可出自同一個域，每一列稱為屬性，要給予不同的屬性名；（3）列的順序可任意交換，行的順序也可任意交換；（4）關(guān)系中的任意兩個元組不能完全相同；（5）每一分量必須是不可分的數(shù)據(jù)項。2.1.3關(guān)系模型

1、關(guān)系模型的組成（1）數(shù)據(jù)結(jié)構(gòu)

在關(guān)系模型中，無論是實體還是實體之間的聯(lián)系均由單一的結(jié)構(gòu)類型即關(guān)系來表示。也就是說，任何一個關(guān)系數(shù)據(jù)庫都是由若干張互相關(guān)聯(lián)的表組成。

關(guān)系模式與關(guān)系是兩個不同的概念，它們之間的關(guān)系是一種“型與值”的關(guān)聯(lián)關(guān)系。

（2）關(guān)系操作

關(guān)系操作方式的特點是集合操作，即操作的對象和結(jié)果是集合，也稱為一次一集合的方式。非關(guān)系型的數(shù)據(jù)操作方式則為一次一記錄的方式。

（3）

關(guān)系模型的三類完整性

關(guān)系模型的三類完整性包括實體完整性、引用完整性（參照完整性）和用戶定義的完整性。

實體完整性和引用完整性是關(guān)系模型必須滿足的完整性約束條件，應(yīng)該由關(guān)系系統(tǒng)自動支持。

1）實體完整性：在任何關(guān)系的任何一個元組中，主鍵碼值的任一分量都不允許為空值。

2）引用完整性：若某個屬性或?qū)傩越M不是本身表的主鍵碼，但它是另一張表的主鍵碼，則該屬性或?qū)傩越M稱為本身表的外鍵碼。在關(guān)系模型中，外鍵碼或者取空值或者取另一張表中某個元組的主鍵碼值。

3）用戶定義完整性：由用戶針對某一具體數(shù)據(jù)庫的約束條件來定義完整性。它由應(yīng)用環(huán)境決定，反映了某一具體應(yīng)用所涉及的數(shù)據(jù)必須滿足的語義要求。

2．關(guān)系模型的特點

關(guān)系模型的突出優(yōu)點在于：（1）關(guān)系模型對各種用戶提供統(tǒng)一的單一的數(shù)據(jù)結(jié)構(gòu)形式，即二維表。（2）數(shù)據(jù)庫的操作都可歸結(jié)為關(guān)系的運算，而關(guān)系是建立在集合代數(shù)基礎(chǔ)上的。（3）具有高度的數(shù)據(jù)獨立性，用戶的應(yīng)用程序完全不必關(guān)心物理存儲細節(jié)。（4）數(shù)據(jù)庫管理人員的工作得到了簡化，易于對數(shù)據(jù)庫重組和控制。

關(guān)系模型不足之處主要有：（1）相當多的關(guān)系數(shù)據(jù)庫管理系統(tǒng)在多表查詢時效率往往低于網(wǎng)狀系統(tǒng)；

（2）統(tǒng)一的表格形式結(jié)構(gòu)無法有效地區(qū)分現(xiàn)實世界中事物之間的各種不同類型的聯(lián)系。

盡管如此，關(guān)系數(shù)據(jù)模型仍為當前數(shù)據(jù)庫技術(shù)中最重要的數(shù)據(jù)模型，它在數(shù)據(jù)庫領(lǐng)域中發(fā)揮著巨大的作用。2.2關(guān)系代數(shù)

關(guān)系的數(shù)據(jù)操縱語言按照表達查詢的方式可分為兩大類：

1．用對關(guān)系的運算來表達查詢的方式，稱為關(guān)系代數(shù)；

2．用謂詞來表達查詢要求的方式，稱為關(guān)系演算。關(guān)系演算又可按謂詞變元的基本對象是元組變量還是域變量而分為元組關(guān)系演算和城關(guān)系演算兩種。

這三種語言在表達能力上是彼此等價的。關(guān)系代數(shù)的運算可分為以下兩類。

2.2.1傳統(tǒng)的集合運算

傳統(tǒng)的集合運算是二目運算。設(shè)關(guān)系R和關(guān)系S具有相同的度，且相應(yīng)的屬性值取自同一個域,則稱它們是并相容的。對于并相容的兩個關(guān)系可以定義如下三種運算：

1．并運算(Union)

兩個關(guān)系R和S的并記為R∪S，它是一個新的關(guān)系，由屬于R或?qū)儆赟的元組組成，可形式地定義成：

R∪S＝{t∣t∈R∨t∈S}

其中t是元組變量，表示關(guān)系中的元組。

2．交運算(Intersection)

兩個并相容的關(guān)系R和S，它們的交記為R∩S，由屬于R且屬于S的元組組成，可形式地定義為：

R∩S={t∣t∈R∧t∈S}其中t是元組變量，表示關(guān)系中的元組。

3．差運算(Difference)

兩個并相容關(guān)系R和S的差是由屬于R但不屬于S的元組組成，它可形式地定義為：

R-S={t∣t∈R∧t

S}其中t是元組變量，表示關(guān)系中的元組。

4．笛卡兒積(CartesianProduct)

設(shè)R為m元關(guān)系，S為n元關(guān)系，它們的笛卡兒積表示為R×S，這個新關(guān)系具有m+n元，元組的前m個分量是R中的一個元組，后n個分量是S中的一個元組，它可以用下列形式表示：R×S={(a1,a2,…,am,b1,b2,…,bn)|(a1,a2,…,am)∈R∧(b1,b2,…,bn)∈S}

具體參見書上圖2.l中并、交、差運算的一個實例和圖2.2中笛卡兒積的一個實例。2.2.2專門的關(guān)系運算

1．選擇運算(Selection)

選擇運算是從某個給定的關(guān)系中篩選出滿足限定條件的元組子集，它是一元關(guān)系運算。定義為：

σF(R)＝{t|t∈R∧F(t)＝”真”}其中F是篩選關(guān)系R中元組的限定條件的布爾表達式，它由邏輯運算符∨（或）、∧（與）和￢（非）連接各算術(shù)表達式組成。

2．投影運算(Projection)

投影運算是從給定的關(guān)系中保留指定的屬性子集而刪去其余屬性的操作。設(shè)定某關(guān)系

R(X)，X是R的屬性集，A是X的一個子集，則R在A上的投影可表示成：

πA（R)＝{t[A]|t∈R}其中t[A]表示只取元組t中相應(yīng)A屬性中的分量。

3．聯(lián)接運算(Join)

聯(lián)接運算是從兩個關(guān)系的笛卡兒積中選取屬性間滿足一定條件的元組，可記作：其中A是關(guān)系R中的屬性組，B是關(guān)系S中的屬性組，它們的度數(shù)相同且可比較，θ為算術(shù)比較運算符(即＜，≤，=，＞，≥，≠)。

4．自然聯(lián)接運算(Naturaljoin)

聯(lián)接運算中最有實用價值的運算是自然聯(lián)接運算,它只要求參與運算的兩個關(guān)系在同名屬性上具有相同的值，由于同名屬性上的值相同，所以在產(chǎn)生的結(jié)果關(guān)系中同名屬性也只出現(xiàn)一次，它可定義為：思考題：聯(lián)接運算和自然聯(lián)接運算有何異同點？1、相同點聯(lián)接運算和自然聯(lián)接運算的基礎(chǔ)均是笛卡爾積，他們均屬于聯(lián)接運算。2、不同點（1）聯(lián)接運算中的二個關(guān)系不需要公共屬性，而自然聯(lián)接運算則需要公共屬性；（2）聯(lián)接運算中的聯(lián)接條件可以取6中關(guān)系運算符，而自然聯(lián)接運算則只能取等號；（3）聯(lián)接運算后屬性個數(shù)是二個關(guān)系屬性個數(shù)之和，而自然聯(lián)接運算后屬性個數(shù)應(yīng)該去掉重復(fù)的一份屬性。

5.除法運算(Division)

一個m元關(guān)系R除以一個n元關(guān)系S(其中m＞n，S非空關(guān)系并且R中存在n個屬性與S的n個屬性定義在相同的域)所得到的結(jié)果是一個(m-n)元的新關(guān)系，它表示滿足以下條件的元組集合：R÷S={t(m-n﹞｜對任一t﹝n﹞∈S都有t(m–n).t(n)∈R}其中t(m-n).t(n)表示將一個(m-n)元的元組和一個

n元的元組拼合成為一個m元的新元組。

具體參見書上圖2.3中選擇、投影、聯(lián)接和自然聯(lián)接的一個實例和圖2.4中三個除法運算的實例。

SC

R1運算先在SC中減去R1屬性C#，再在減去R1屬性后的SC關(guān)系中按元組值分組（有9組）；若某一分組關(guān)于C#的像集包含C3的話，則此組的元組值（S#,G）就是要求的一個結(jié)果。對每一組執(zhí)行上述操作，就能得到最終結(jié)果。

2.2.3關(guān)系代數(shù)表達式

在關(guān)系代數(shù)中,把由上述關(guān)系代數(shù)運算經(jīng)過有限次復(fù)合而成的式子稱作關(guān)系代數(shù)表達式,它的運算結(jié)果仍是一個關(guān)系。設(shè)有學(xué)生-課程關(guān)系數(shù)據(jù)庫實例，其中S、C和SC分別代表學(xué)生關(guān)系、課程關(guān)系和學(xué)生選課關(guān)系。

S(S#,SN,SD,SA)SC(S#,C#,G)

C(C#,CN,CT)

例1求計算機科學(xué)系CS的學(xué)生：

σSD=’cs’(S)或σ3=’cs’(S)其中σ的下角3是SD屬性的序號。例2檢索學(xué)習(xí)課程號為C2的同學(xué)的學(xué)號、姓名、課程號、課程名和成績：

S＃,SN,C#,CN,G(S

σC＃='C2'(SC)

C)例3給出學(xué)習(xí)全部課程的同學(xué)的名單：

S#,SN(S

(

S#,C#(SC)

C#(C)))例4將新開課程記錄(’C6’,’Q’,’R’)插入到關(guān)系C中：

C∪{(’C6’,’Q’,’R’)}例5將學(xué)號為S3同學(xué)的C4課程的成績修改’A’:(SC-{(’

S3’

,

’

C4’

,?)})∪(’

S3’

,’

C4’

,’

A’

)}

修改操作用關(guān)系代數(shù)分兩步實現(xiàn)，先刪去原元組，再插入新元組。在本例中，SC的鍵碼為（S#，C#），故成績用？代替，不影響系統(tǒng)檢索，不會產(chǎn)生二義性。在上面介紹的9種關(guān)系代數(shù)運算中，并、差、笛卡兒積、選擇和投影是5種基本的關(guān)系代數(shù)運算。

在以關(guān)系為基本數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)庫中，以上述5種基本關(guān)系代數(shù)運算為基礎(chǔ)構(gòu)造的數(shù)據(jù)子語言，可以實現(xiàn)人們所需要的對數(shù)據(jù)的所有查詢和更新操作。E.F.Codd把關(guān)系代數(shù)的這種處理能力為關(guān)系的完備性。

在一個實際系統(tǒng)中，如果它的關(guān)系操作語言能實現(xiàn)關(guān)系代數(shù)的5種基本關(guān)系代數(shù)運算,則說明該系統(tǒng)的關(guān)系操作是完備的，可以實現(xiàn)人們對數(shù)據(jù)庫的任何查詢和更新操作。

2.3關(guān)系數(shù)據(jù)庫查詢的優(yōu)化2.3.1查詢優(yōu)化問題的提出

什么是數(shù)據(jù)庫查詢的實現(xiàn)？由于一個數(shù)據(jù)庫查詢常?？梢杂卸喾N實現(xiàn)算法，其時間運行效率可能差異很大，在一些性能比較好的DBMS中，大多采取了一些措施，自動選擇較優(yōu)的算法，以花費較小的代價實現(xiàn)用戶所需的查詢。這一過程，就稱作數(shù)據(jù)庫查詢的優(yōu)化。

查詢優(yōu)化的總目標：選擇有效的策略，求得給定的關(guān)系表達式的值。

例6已知關(guān)系模式S(SNO，SNAME，SAGE，SEX)和SC(SNO，CNO，GRADE)，若某用戶要求查詢選修‘C2’課程的所有學(xué)生的姓名和成績，則這一查詢可用如下三種等價的關(guān)系代數(shù)表達式來實現(xiàn)：（1）

SNAME,GRADE(

S.SNO=SC.SNO

SC.CNO=‘C2’(S

SC))（2）

SNAME,GRADE(

SC.CNO=‘C2’(S

SC))（3）

SNAME,GRADE(S

SC.CNO=‘C2’(SC))

假設(shè)S關(guān)系有l(wèi)00個元組，SC關(guān)系有l(wèi)000個元組，其中選修‘C2’課程的記錄有20個。我們忽略內(nèi)存處理時間，只計算內(nèi)外存數(shù)據(jù)交換的時間。假定在內(nèi)存中可容納兩個數(shù)據(jù)塊進行計算，每個數(shù)據(jù)塊可容納10個S記錄，或者100個SC記錄，或者10個S×SC記錄。計算機每秒可讀或?qū)?0個數(shù)據(jù)塊。

SNAME,GRADE(

S.SNO=SC.SNO

SC.CNO=‘C2’(S

SC))(l)計算笛卡兒積的時間

每次從外存讀入一塊S記錄和一塊SC記錄，對其進行笛卡兒積運算，將結(jié)果寫入外存。

讀取總塊數(shù)為：

10(S表)+10*10(SC表)=110(塊)

若每秒讀20塊，則讀塊時間為：

110／20=5.5(秒)

連接后的元組數(shù)為100×1000=105，這些結(jié)果寫塊時間為：

105/10/20=500(秒)

計算笛卡兒積總時間為:5.5十500＝5O5.5(秒)

(2)計算選擇的時間選擇運算要從外存中將S×SC的所有元組讀入內(nèi)存，它與寫塊時間是相同的，即為5OO秒。由前面的假設(shè)條件可知，滿足CNO＝‘c2’條件的元組有20個，均可放入內(nèi)存兩個數(shù)據(jù)塊中，故計算選擇運算所花費的時間為:105/10/20=500(秒)(3)由于選擇后的中間結(jié)果全在內(nèi)存中，而投影運算可直接在內(nèi)存中進行，投影時間忽略不計。

第一種算法執(zhí)行查詢的總時間為：

505.5十500＝1005.5(秒)≈17(分鐘)2.

SNAME,GRADE(

SC.CNO=’C2’(S

SC))(l)計算自然連接的時間讀取S和SC表的策略不變，總讀取塊數(shù)仍為l10塊花費5.5秒，但自然連接結(jié)果只有1000個元組，故寫出這些元組花費的時間為：

1000÷10÷20＝5(秒)計算自然連接所花費的總時間為5.5十5＝10.5(秒)。(2)計算選擇的時間讀取中間塊，執(zhí)行選擇運算所花時間為5秒。(3)計算投影運算在內(nèi)存中進行，投影時間忽略。

第二種算法執(zhí)行查詢的總時間為：

10.5十5=15.5(秒)

3.

SNAME,GRADE(S

SC.CNO=’C2’(SC))(1)計算選擇的時間對SC表作選擇運算，只需讀一遍SC表，存取10塊花費時間為10÷20＝0.5(秒)。因為滿足條件的元組僅20個，放不必再寫入外存。(2)計算自然連接的時間讀取S表，把讀入的S元組和內(nèi)存中的SC元組作連接，也只需讀一遍S表共10塊花費時間為

10÷20=0.5(秒)自然連接后的結(jié)果元組可全部放入內(nèi)存。(3)計算投影在內(nèi)存中進行，時間忽略不計。

第三種算法執(zhí)行查詢的總時間為：

0.5十0.5＝l(秒)

通過上述例子的討論，我們可以受到如下啟發(fā)：數(shù)據(jù)庫系統(tǒng)的查詢，即使是最簡單的查詢，也必須對查詢要求在處理過程中進行優(yōu)化。優(yōu)化工作不僅有邏輯方法的優(yōu)化(如關(guān)系代數(shù)表達式的等價表示)，也有物理方法的優(yōu)化(如存取路徑和存取方法的優(yōu)化)。根據(jù)分析，當有選擇和連接運算時，應(yīng)當先做選擇。這樣參加連接的元組就可以大大減少，從而提高查詢效率。

查詢的實現(xiàn)與優(yōu)化非常重要。

2.3.2關(guān)系代數(shù)的等價變換

下面的優(yōu)化規(guī)則形式化地表達了邏輯層優(yōu)化的一些重要策略，其中E1、E2和E均為任一關(guān)系代數(shù)表達式。

1.投影的合并：設(shè)A1…An

B1…Bm，則

πA1…An(πB1…Bm(E))

πA1…An(E)。

2.選擇的合并：σF1(σF2(E))

σF1

F2(E)。

3．選擇的提前：（1）σF(E1

E2)

σF1(E1)

σF2(E2)，其中Fl、F2F3分別只涉及E1,E2中出現(xiàn)的屬性，F(xiàn)3同時涉及E1和E2兩個表達式中的屬性，并且F

F1

F2

F3；（2）σF(E1∪E2)

σF(E1)∪σF(E2)。

4．投影的提前：(l)πA1…An(σF(E))

πA1…An(σF(πA1…AnB1…Bm(E))，其中B1…Bm為表達式F中所涉及的全部屬性；(2)其中B1,…,Bm為A1,…,An中的屬性與F中涉及E1的屬性的并，C1,…,Ck為A1,…,An中的屬性與F中涉及E2的屬性的并;(3)πA1…An(E1∪E2)

πA1…An(E1)∪πA1…An(E2)。

2.3.3查詢優(yōu)化的一般策略1、邏輯層優(yōu)化的一般策略（1）選擇運算應(yīng)盡可能先做。（2）如果在查詢表達式中，某一子表達式的形式為一個笛卡兒積運算后緊接著執(zhí)行某些選擇運算，則將這兩個運算合并為一個聯(lián)接運算，可以使運行時間大大地減少。（3）表達式中的投影運算，一般應(yīng)盡可能早地執(zhí)行。但需謹慎處理，因為可能有某些屬性雖然在最后結(jié)果中不需要保留，但在執(zhí)行指定的關(guān)系運算中卻不可缺少。（4）如果在一個表達式中有某個子表達式重復(fù)出現(xiàn)，則應(yīng)先將該子表達式算出結(jié)果保存起來，以免重復(fù)計算。（5）如有若干投影和選擇運算，且它們都對同一關(guān)系進行操作，則可在掃描此關(guān)系的同時完成所有的運算，以避免重復(fù)掃描關(guān)系。（6）把投影運算同其前或其后的二元運算結(jié)合起來，沒有必要為了去掉某些字段而掃描一遍關(guān)系。

例7考慮關(guān)系代數(shù)表達式

πA(σB=C∧D=15(AB×CD))根據(jù)策略1，我們可以將原式修改為：

πA(σB=C(AB×σD=15(CD)))；根據(jù)策略2，我們又可進一步將前式優(yōu)化為：但在運用策略3時，則不能簡單地將投影運算提前，正確的處理應(yīng)該將該式優(yōu)化為（*）式，最后按策略5和策略6做。

2、物理層優(yōu)化的一般方法（1）關(guān)系代數(shù)操作的實現(xiàn)算法的研究，目前主要集中在笛卡兒積和聯(lián)接運算上，因為這兩種運算在多關(guān)系查詢的場合是必不可少的，而且比較費時。（2）在算法實現(xiàn)過程中，為進一步改善查詢效率，一般要考慮索引、數(shù)據(jù)的存儲分布等存取路徑。在執(zhí)行連接前對關(guān)系進行適當?shù)念A(yù)處理，預(yù)處理方法主要有二種，先在連接的屬性上建立索引和對關(guān)系排序，然后執(zhí)行連接。

2.3.4查詢優(yōu)化的步驟

查詢優(yōu)化是建立在對關(guān)系代數(shù)表達式的優(yōu)化基礎(chǔ)上的，而關(guān)系代數(shù)表達式的優(yōu)化是由DBMS的DML編譯器完成的?？梢岳们懊娴牡葍r變換規(guī)則和優(yōu)化策略對關(guān)系代數(shù)表達式進行優(yōu)化，其查詢優(yōu)化的步驟如下：1、將關(guān)系代數(shù)表達式轉(zhuǎn)化為關(guān)系代數(shù)語法樹。2、將關(guān)系代數(shù)語法樹轉(zhuǎn)換成優(yōu)化樹。3、將優(yōu)化樹轉(zhuǎn)換成優(yōu)化后的關(guān)系代數(shù)表達式。4、執(zhí)行查詢前對關(guān)系代數(shù)表達式中的連接關(guān)系進行適當?shù)念A(yù)處理。

例8對于教學(xué)數(shù)據(jù)庫

S(SNO，SNAME，AGE，SEX)SC(SNO，CNO，GRADE)C(CNO，CNAME，CREDIT)

現(xiàn)有一個查詢語句：檢索選修了“數(shù)據(jù)庫技術(shù)與設(shè)計”課程且成績大于90分的所有學(xué)生的學(xué)號和姓名。該查詢語句的關(guān)系代數(shù)表達式可以表示如下：

SNO,SNAME(

CNAME=“數(shù)據(jù)庫技術(shù)與設(shè)計”

GRADE>90(

S.SNO=SC.SNO

SC.CNO=C.CNO(S

SC

C)))

下面按查詢優(yōu)化的步驟進行優(yōu)化。

（1）將關(guān)系代數(shù)表達式轉(zhuǎn)化為關(guān)系代數(shù)語法樹

圖2.7關(guān)系代數(shù)語法樹

（2）將關(guān)系代數(shù)語法樹轉(zhuǎn)換成優(yōu)化樹

圖2.8關(guān)系代數(shù)優(yōu)化樹

（3）將優(yōu)化樹轉(zhuǎn)換成優(yōu)化后的關(guān)系代數(shù)表達式

SNO,SNAME(S

(

GRADE>90(SC)

CNAME=“數(shù)據(jù)庫原理及應(yīng)用”(C)))（4）執(zhí)行查詢前對關(guān)系代數(shù)表達式中的連接關(guān)系進行適當?shù)念A(yù)處理。若SC和C關(guān)系中記錄較多的話，則先對

GRADE>90(SC)和

CNAME=“數(shù)據(jù)庫原理及應(yīng)用”(C)關(guān)系按CNO進行索引或排序，