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

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

主要內(nèi)容：

●關(guān)系數(shù)據(jù)庫(kù)概述。

●關(guān)系模型的物理與數(shù)學(xué)定義。

●關(guān)系代數(shù)運(yùn)算。

●關(guān)系演算：元組演算與域演算。重點(diǎn)：關(guān)系代數(shù)運(yùn)算2.1

關(guān)系數(shù)據(jù)庫(kù)概述關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)是支持關(guān)系模型的數(shù)據(jù)庫(kù)系統(tǒng)。關(guān)系數(shù)據(jù)結(jié)構(gòu)關(guān)系操作關(guān)系完整性約束關(guān)系模型由三部分組成：1、關(guān)系數(shù)據(jù)結(jié)構(gòu)關(guān)系模型中的數(shù)據(jù)結(jié)構(gòu)是二維表格。關(guān)系模型數(shù)學(xué)定義為笛卡爾集中的有意義的子集。2、關(guān)系操作查詢操作更新（增、刪、改）操作其中，查詢是更新的基礎(chǔ)，它是關(guān)系最重要和最基本的操作。關(guān)系的操作：關(guān)系操作的結(jié)果：關(guān)系（集合）。關(guān)系代數(shù):選擇、投影、連接、除、并、交、差等。關(guān)系元組演算關(guān)系域演算關(guān)系演算：關(guān)系操作的數(shù)學(xué)表達(dá)：常用的關(guān)系操作的語(yǔ)言：SQL關(guān)系操作語(yǔ)言的特點(diǎn)：具有完備的表達(dá)能力。非過(guò)程化的集合操作語(yǔ)言。語(yǔ)句即可交互使用又可嵌套到高級(jí)語(yǔ)言中使用。3、關(guān)系完整性約束關(guān)系的完整性：指關(guān)系中數(shù)據(jù)的相容性和正確性。實(shí)體完整性參照完整性用戶定義完整性

關(guān)系三類(lèi)完整性：關(guān)系模型物理表示：二維表格。數(shù)學(xué)表示：笛卡爾積上有意義的子集。關(guān)系模型：直觀地說(shuō)就是用二維表格表示實(shí)體集，外鍵表示實(shí)體間聯(lián)系的數(shù)據(jù)模型。關(guān)系模型表示：一、關(guān)系模型的物理表示二維表格表示，如：一張學(xué)生注冊(cè)表學(xué)號(hào)姓名性別出生年月99019902

…張一王三…男女…80.179.12…行關(guān)系模式R(表頭)元組1元組2……實(shí)體集(文件)r:元組集合(關(guān)系)值域(列)

關(guān)系模型=關(guān)系模式+關(guān)系關(guān)系模式:它是靜態(tài)的(不隨時(shí)間變化),穩(wěn)定的,它由屬性名組成.關(guān)系是由元組組成的值集.它是隨操作而變化.1、關(guān)系模式(relationschema)

組成:取自二維表的表頭中的數(shù)據(jù).一般組成:關(guān)系模式是一個(gè)五元組:R(U,D,DOM,F)

其中:R為關(guān)系模式名:可取自二維表的表名;不同的關(guān)系模式其名不同.U為屬性名表:上例:學(xué)號(hào),姓名,出生年月,性別;屬性名各異.D為屬性的域名,指屬性取值的類(lèi)型;如:學(xué)號(hào)的類(lèi)型為字符串.DOM為屬性的取值的寬度(長(zhǎng)度);如:學(xué)號(hào)取值8個(gè)字符(最大).F為屬性間依賴關(guān)系的集合,表明屬性間的語(yǔ)義;如:學(xué)號(hào)姓名.

關(guān)系模式通常簡(jiǎn)記為:

R(A1,A2,….,An);其中：A1,A2,….,An為屬性名。

如:上例:student(sno,name,sex,date)2、關(guān)系關(guān)系（表體中的數(shù)據(jù)）：元組的集合。每一個(gè)元組描述一個(gè)實(shí)體，關(guān)系對(duì)應(yīng)實(shí)體集。

基本表：實(shí)際存在的表，實(shí)際存儲(chǔ)數(shù)據(jù)的邏輯表示。

查詢表：對(duì)DB操作后的結(jié)果表（結(jié)果關(guān)系）。

視圖(虛表)：由基本表或其他視圖導(dǎo)出的表，不對(duì)應(yīng)實(shí)際存儲(chǔ)數(shù)據(jù)。注：在實(shí)際中，常把關(guān)系和關(guān)系模式系統(tǒng)稱(chēng)為關(guān)系，可根據(jù)上下文區(qū)分。關(guān)系的三種類(lèi)型：3、基本關(guān)系的性質(zhì)（對(duì)關(guān)系的限定）關(guān)系中每一列（屬性）必須是不可再分的基本數(shù)據(jù)項(xiàng)，且具有同一類(lèi)型，列名各異，列的排列次序無(wú)關(guān)緊要。關(guān)系中不允許出現(xiàn)相同的元組，元組之間的次序任意。4、關(guān)鍵字（Key）超鍵：唯一標(biāo)識(shí)元組的屬性集。如(sno,name)侯選鍵：不含多余屬性的超鍵。如sno或name（無(wú)同名同姓時(shí)）。主鍵：被選用的侯選鍵。如：sno或可選name（無(wú)同名同姓時(shí)）。外鍵：用來(lái)聯(lián)系關(guān)系的鍵。如：stu(sno,name,sex,date,dno)dno是外鍵；dept(dno,dname,addr)5、名詞對(duì)照表人工管理信息世界關(guān)系領(lǐng)域?qū)哟?、網(wǎng)狀領(lǐng)域計(jì)算機(jī)表頭表框架關(guān)系模式記錄型記錄型表體實(shí)體集關(guān)系（元組集）記錄值集文件行實(shí)體元組記錄值記錄值列（欄目）屬性屬性數(shù)據(jù)項(xiàng)字段列值屬性值集屬性值集域值字段值識(shí)別項(xiàng)實(shí)體標(biāo)識(shí)符關(guān)鍵字（鍵）碼（鍵）碼二、關(guān)系模型的數(shù)學(xué)定義關(guān)系模型是建立在集合代數(shù)的基礎(chǔ)之上。關(guān)系用笛卡爾積來(lái)定義的。

笛卡爾積定義：給定一組域D1，D2，……Dn，這些域可以完全相同或不同或部分相同，則n個(gè)集合的笛卡爾積：

D1×D2×……×Dn={(d1,d2,…,dn)|di∈Di,i=1,2,…,n}

其中每一個(gè)元素（d1,d2,…,dn）稱(chēng)為一個(gè)元組；元素中每一個(gè)分 量值di稱(chēng)為元組的一個(gè)分量。笛卡爾積是一個(gè)以元組為元素的集合，且笛卡爾積可以表示一個(gè)二維表。例：給定D1={0,1},D2={a,b,c}，則：

D1×D2={(0,a),(0,b),(0,c),(1,a),(1,b),(1,c)}(即每個(gè)元組的第一個(gè)分量取值為D1,第二個(gè)分量取值為D2,……)笛卡爾積的二維表示：D1D201abc×=D1D2000111abcabc基數(shù)：2×3=6個(gè)元組關(guān)系模式的笛卡爾積定義：笛卡爾積D1×D2…×Dn的任一子集稱(chēng)為定義在D1，D2，…，Dn上的一個(gè)n元關(guān)系模式，簡(jiǎn)記為:

R（D1，D2，…，Dn)。

注：實(shí)際關(guān)系數(shù)據(jù)庫(kù)中的每一個(gè)關(guān)系都是一個(gè)笛卡爾積的有意義的子集,即其中的每個(gè)元組必須符合實(shí)際意義。例：設(shè)D1={張三，李四}，D2={男，女}則有：D1×D2={（張三，男），（張三，女），（李四，男），（李四，女）}假定：張三本是男，李四本是女，顯然（張三，女）和（李四，男）是沒(méi)有意義的元組,應(yīng)該去掉。即有意義的子集：

D1×D2={（張三，男），（李四，女）}注意：關(guān)系的基數(shù)：就是元組的個(gè)數(shù)。上例：關(guān)系的基數(shù)為6

關(guān)系的元數(shù)（度或目）：屬性的個(gè)數(shù)。

上例：關(guān)系的元數(shù)為2。三、關(guān)系完整性為了保證關(guān)系模型中數(shù)據(jù)的正確性和一致性，必須對(duì)關(guān)系中數(shù)據(jù)作完整性的約束。三類(lèi)完整性約束規(guī)則：實(shí)體完整性約束規(guī)則參照完整性約束規(guī)則用戶自定義約束規(guī)則：用戶定義，系統(tǒng)檢查。系統(tǒng)自動(dòng)支持1、實(shí)體完整性規(guī)則關(guān)系中所有主屬性都不能取空值。而不是僅主關(guān)鍵字不能取空值。組成候選關(guān)鍵字的屬性稱(chēng)為主屬性。如：選課（學(xué)號(hào)，課號(hào)，成績(jī)）中：主屬性學(xué)號(hào)和課號(hào)都應(yīng)有值，即不能為空值（無(wú)值）。2、參照完整性規(guī)則

不引用不存在的實(shí)體.例：有關(guān)系模式s(sno,name,sex,age)sc(sno,cno,grade)其中：sno是s的主關(guān)鍵字，也是sc中的外鍵，它聯(lián)系著s與sc，這時(shí)稱(chēng)s為參照關(guān)系；sc為被參照關(guān)系（或稱(chēng)依賴關(guān)系）。如果關(guān)系sc中有一個(gè)元組（s7,c4,80），此時(shí)學(xué)號(hào)s7在關(guān)系s中找不到,則認(rèn)為在sc中引用了一個(gè)不存在的學(xué)生實(shí)體，這就違反了參照完整性規(guī)則。3、用戶自定義完整性規(guī)則用戶自定義完整性規(guī)則反映某一具體應(yīng)用涉及的數(shù)據(jù)必須滿足的語(yǔ)義要求。如：學(xué)生的“年齡”定義兩位整數(shù)，則值范圍太大；寫(xiě)一條規(guī)則，把“年齡”屬性取值規(guī)定15～30之間。2.3關(guān)系代數(shù)

關(guān)系DB操作語(yǔ)言是以數(shù)學(xué)中的關(guān)系代數(shù)和謂詞演算為基礎(chǔ)研制的。關(guān)系查詢語(yǔ)言：關(guān)系代數(shù)語(yǔ)言：以集合代數(shù)操作為基礎(chǔ)運(yùn)算的DML（非過(guò)程性弱）關(guān)系演算語(yǔ)言：以謂詞演算為基礎(chǔ)的DML（非過(guò)程性強(qiáng)）分為：元組關(guān)系演算語(yǔ)言域關(guān)系演算語(yǔ)言一、關(guān)系代數(shù)的5種基本操作關(guān)系代數(shù)的操作：傳統(tǒng)的集合運(yùn)算：∪，-，∩，×擴(kuò)充的關(guān)系運(yùn)算：π（投影）、σ（選擇）、（聯(lián)接）、÷（除）關(guān)系代數(shù)完備的且基本的操作集：∪，－，×，∏,σ五種。其它的運(yùn)算并非基本，都可由這5種操作導(dǎo)出。1、并（∪）設(shè)R和S是同類(lèi)關(guān)系（模式相同：屬性相同，個(gè)數(shù)相等），R∪S結(jié)果為一同類(lèi)關(guān)系，它由既屬于R又屬于S中的元組構(gòu)成的集合。用元組變量形式定義：R∪S≡{t|t∈R∨t∈S};t為元組變量。?ABCadcbabcfdABCbdgaaf例：ABCadcbbabgcfdaRSR∪S相同元組只選一個(gè)特征：∪為二目運(yùn)算從“行”上取值作用：在一個(gè)關(guān)系中插入一個(gè)數(shù)據(jù)集合，自動(dòng)去掉相同元組。2、差（—）

設(shè)R與S為同類(lèi)關(guān)系，則R和S的差是由屬于R而不屬于S的所有元組組成的集合。用元組變量形式定義：例：ABCacbbcd作用：從某關(guān)系中刪去另一關(guān)系R-S3、笛卡爾積（×）

設(shè)R為K1元關(guān)系，S為K2元關(guān)系，則R×S是一個(gè)（K1+K2）元數(shù)的集合，其中元組的前K1個(gè)分量是R的一個(gè)元組，后K2個(gè)分量是S的一個(gè)元組。共有n×m個(gè)元組（n為R元組數(shù)，m為S元組數(shù)）。用元組變量形式定義：R×S≡{t|t=<t,t>∧t∈R∧t∈S}k1k1k2k2例：ABC142536DEacbdABCDE114422553366acacbdbdRSR×Sk1=3k2=2k1+k2=3+2=5屬性n×m=2×2=4個(gè)元組特征：“列”合并，“行”組合作用：將兩個(gè)關(guān)系（同類(lèi)或不同類(lèi)）無(wú)條件地連成一個(gè)新關(guān)系。4、投影（л

）

在n元關(guān)系R（A1，A2，…An）中選取k（k≤n）列屬性，并去掉重復(fù)元組構(gòu)成的新關(guān)系：R1(A1，A2，…，Ak）。用元組變量定義лi1,i2,…,im(R)≡{t|t=<ti1,…,Tim>∧<t1,…tk>∈R}例：ABC147258369AC147369RЛA，C（R）=Л[1]，[3]（R）若有重復(fù)元組應(yīng)去掉。特征：運(yùn)算對(duì)象為單個(gè)關(guān)系，在“列”上縱向分割關(guān)系。作用：在關(guān)系中選取某些列組成一個(gè)新關(guān)系。5、選擇（σ）其中：F由下列成分組成：運(yùn)算對(duì)象：常數(shù)（用引號(hào)括起來(lái)），屬性名或?qū)傩缘牧刑?hào)。

算術(shù)比較符：<,≤,>,≥,=,≠;

邏輯運(yùn)算符：￢，∧,∨用元組變量形式定義：

σF（R）≡{t|t∈R∧F(t)=true}從關(guān)系R中挑選滿足條件F為真的元組組成新關(guān)系，記為σF（R）例：ABCadcbcbcbdABCacbbcdRσB=‘b’(R)≡σ[2]=‘b’(R)特征：對(duì)一個(gè)關(guān)系進(jìn)行“行”運(yùn)算，即為橫向選擇。作用：在一個(gè)關(guān)系中，選擇滿足條件的元組構(gòu)成新關(guān)系（關(guān)系模式不變）運(yùn)算符：二、關(guān)系代數(shù)的4種組合運(yùn)算包括：交（∩），聯(lián)接（），自然聯(lián)接（

）和除法（÷）操作。1.交（∩

）求同類(lèi)關(guān)系R和S中相同的元組的集合.用元組變量形式定義：R∩S≡{t|t∈R∧t∈S}θ例：ABCb2cABCab32bcABCabc124bcdSRR∩S注：R∩S=R-（R-S）用差運(yùn)算表示。特征：關(guān)系模式不變，從兩關(guān)系中取相同的元組。??

2.聯(lián)接（

）設(shè)R（A1，A2，…Ak1）和S（B1，B2，…，Bk2（1≤i≤k1,1≤j≤k2），i，j分別是R和S的第i個(gè)分量和第j個(gè)分量；θ聯(lián)接是笛卡爾積中的一個(gè)子集，其元組必須符合R的第i個(gè)分量值和S的第j個(gè)分量值之間的θ關(guān)系，記為R

S。用元組變量形式定義：R

S≡{t|=<t,t>∧t∈R∧t∈S∧tθt}

其中：t和t分別表示R中的第i個(gè)分量值，和S中第j個(gè)分量值，

tθt

表示這兩個(gè)分量值滿足θ操作。θ[i]θ[j]k1k1k1k2k2k2ij[i]θ[j]k1k2ijk2k1ji即：R

S≡σ

(R×S)[i]θ[j][i]θ[j]運(yùn)算步驟：（1）求R×S

=T（A1，A2，…，Ak1，B1，B2，…Bk2）

RS（2）在T中選擇[i]θ[j]成立的元組。????例：求R

S=σ[3]>[5](R×S)ABC147258369DEab78ABCDE778899ab78ABCDE114477225588336699ababab787878RS（1）求R×S（2）

σ[3]>[5](R×S)ABCDE789a7[3]>[2]注：當(dāng)θ為“=”時(shí)，R

S稱(chēng)為等值聯(lián)接。[i]=[j]求：R

S[1]=[2]特征：兩個(gè)關(guān)系不一定有公共屬性不去掉重復(fù)屬性。作用：將兩個(gè)關(guān)系按一定的條件聯(lián)接在一起。???3.自然聯(lián)接（）自然聯(lián)接是

的特殊情況。設(shè)關(guān)系R和S有相同的屬性名Ai(i=1,2,…,k)，則R

S是從R×S中挑選R·A1=S·A1∧R·A2=S·A2∧…∧R·Ak=S.Ak的所有元組，并去掉重復(fù)屬性的元組集合。元組變量形式表示:

{t|t=<t,t>∧(R(t)∧S(t))∧R·A1=S·A1∧R·A2=S·A2∧…∧R·Ai=S·Ai}運(yùn)算過(guò)程：計(jì)算R×S挑選R·Ai=S·Ai（即屬性名相同，值相等）的所有元組去掉重復(fù)屬性即：R

S≡лi1,i2,…,im(σ

R·A1=S·A1∧…

∧

R·AK=S·AK(R×S))θ??R?s=

??例:BCD259368235ABC147258369ABCD14253623RS①R×S

③去掉重復(fù)屬性B,C：R?S

ABCS.BS.CD

1

2

3

2

3

2

1

2

3

56

3

1

2

3

9

8

5

4

5

6

2

3

2

4

5

6

5

6

3

4

5

6

9

8

5

7

8

9

2

3

2

7

8

9

5

6

3

7

8

9

9

8

5ABCS.BS.CD

1

2

3

2

3

2

4

5

6

5

6

3②σR.B=S.B∧R.C=S.C(R×S)注：（1）在無(wú)公共屬性時(shí)，自然聯(lián)接變化為笛卡爾積。（2）等值聯(lián)接與自然聯(lián)接的區(qū)別：a.等值聯(lián)接要求相等的屬性不一定相同。自然聯(lián)接要求相等的屬性一定相同。b.等值聯(lián)接不要求去掉重復(fù)屬性。自然聯(lián)接要求去掉重復(fù)屬性。

（3）自然聯(lián)接是關(guān)系DB中最重要的操作之一。4.除法（÷）

設(shè)關(guān)系R和S分別為m元和n元關(guān)系，則R÷S結(jié)果為一個(gè)m－n元關(guān)系。其元組決定為：先將被除關(guān)系R中的m－n列按值分成若干組，每個(gè)組中參入分組的m－n列以外的那些列中是否包含除關(guān)系S的全部元組，包含則取該m－n列的值作為商關(guān)系的一個(gè)元組，否則不取。用元組變量形式表示:R÷S≡{t|t=<t,t…t>∧若t∈s,則<t,t>∈R}m1n2nnm-nn例:ABCDaaaeebbbddcedcedfedfCDcedfABaebdRSR÷S

三、關(guān)系代數(shù)表達(dá)式及應(yīng)用用關(guān)系代數(shù)對(duì)關(guān)系運(yùn)算，即寫(xiě)出運(yùn)算表達(dá)方式。步驟：

①根據(jù)已知條件確定關(guān)系

②根據(jù)查詢結(jié)果確定關(guān)系

③根據(jù)運(yùn)算語(yǔ)義寫(xiě)出查詢代數(shù)表達(dá)式。是否其條件屬性與結(jié)果屬性在同一關(guān)系中，若不在同一關(guān)系中，根據(jù)什么屬性聯(lián)系的。例：設(shè)DB中有三個(gè)關(guān)系模式：學(xué)生關(guān)系：s(s#，sname，age，sex)學(xué)習(xí)關(guān)系：sc（s#，c#，grade）課程關(guān)系：c（c#，cname，teacher）用關(guān)系代數(shù)表達(dá)式，表示下列各種查詢。1．查找學(xué)習(xí)課程號(hào)為C2的學(xué)生的學(xué)號(hào)與成績(jī)∏s#,grade(σc#=′c2′(sc))(學(xué)號(hào)、成績(jī)與課程號(hào)在同一關(guān)系sc中)2．查找選修課程號(hào)為C2或?yàn)镃4的學(xué)生的學(xué)號(hào)∏s#(σc#=′c2′∨c#=′c4′(sc)(學(xué)號(hào)與課程號(hào)在同一關(guān)系sc中)或：∏s#(σc#=‘c2’∨c#=‘c4’（лs#,c#(sc)))(說(shuō)明表達(dá)式不唯一)3．查找至少學(xué)習(xí)C2和C4課程的學(xué)生的學(xué)號(hào)

∏

[1](σ[1]=[4]∧[2]=‘c2’∧[5]=

‘c4’(sc×sc))s#[1]c#[2]grade[3]s#[4]c#[5]grade[6]sc×sc4．查找不學(xué)習(xí)C2課的學(xué)生的姓名與學(xué)號(hào)

∏sname,s#(s)-∏sname,s#(σc#=‘c2’(s

sc））

錯(cuò)誤寫(xiě)法

:∏s#,sname(σc#≠‘c2’(s

sc）)5．查找選修全部課程的學(xué)生姓名

∏

sname(s(∏

s#,c#(sc)÷∏

c#(c)))(在三個(gè)關(guān)系中關(guān)聯(lián)查找)6．查找學(xué)習(xí)課程名為DB的學(xué)生姓名∏sname(s∏

s#(sc

∏

c#(σcname=′DB′(c))))在三個(gè)關(guān)系中找,或

∏

sname(∏

s#,sname(s)∏s#(лs#,c#(sc)

∏

c#(σcname=‘DB’(C))))課號(hào)與姓名不在同一關(guān)系中，分別在sc

和s

，但s和sc

通過(guò)s#

聯(lián)系的???????2.3.3關(guān)系代數(shù)式的查詢優(yōu)化一.關(guān)系DB的查詢優(yōu)化概述

關(guān)系DB的查詢優(yōu)化分為：代數(shù)優(yōu)化和物理優(yōu)化。代數(shù)優(yōu)化：指關(guān)系代數(shù)表達(dá)式的優(yōu)化。（本節(jié)重點(diǎn)）物理優(yōu)化：指存取路徑的選擇和低層操作算法的選擇。

1.關(guān)系DB的查詢處理過(guò)程查詢處理過(guò)程：查詢分析，查詢檢查，查詢優(yōu)化，查詢執(zhí)行。查詢分析：對(duì)查詢語(yǔ)句進(jìn)行掃描，詞法分析和語(yǔ)法分析。判斷查詢語(yǔ)句是否合法。查詢檢查：根據(jù)數(shù)據(jù)字典，檢查查詢語(yǔ)句的語(yǔ)義，用戶的存取權(quán)限和完整性的定義。檢查通過(guò)后，把SQL語(yǔ)句轉(zhuǎn)換成等價(jià)的關(guān)系代數(shù)表達(dá)式。一般用查詢樹(shù)（又稱(chēng)：語(yǔ)法分析樹(shù)）表示關(guān)系代數(shù)表達(dá)式。查詢優(yōu)化：選擇高效執(zhí)行的查詢處理策略。

查詢執(zhí)行：由代碼生成器執(zhí)行根據(jù)查詢策略生成的查詢計(jì)劃的代碼。查詢優(yōu)化過(guò)程：查詢語(yǔ)句

詞法分析，語(yǔ)法分析，語(yǔ)義分析，符號(hào)名轉(zhuǎn)換安全性檢查，完整性檢查

查詢樹(shù)代數(shù)優(yōu)化，物理優(yōu)化執(zhí)行策略描述代碼生成查詢計(jì)劃的執(zhí)行代碼數(shù)據(jù)庫(kù)數(shù)據(jù)字典查詢語(yǔ)句代數(shù)表達(dá)式的語(yǔ)法分析樹(shù)物理優(yōu)化策略查詢優(yōu)化代碼代碼生成器

2.關(guān)系代數(shù)運(yùn)算的優(yōu)化問(wèn)題

問(wèn)題：選擇怎樣的關(guān)系代數(shù)表達(dá)式表示查詢，省時(shí)，省空間，速度快呢？

例：有三個(gè)等價(jià)的關(guān)系代數(shù)表達(dá)式E1，E2，E3：

E1=лA（σB=C∧D=’99’（R×S）)，先做笛卡爾積，后做選擇和投影。

E2=лA（σB=C（R×σ

D=’99’（S））)，先做選擇，后做笛卡爾積。

E3=л

A（R（σ

D=’99’（S）），先做選擇，后做聯(lián)接。注：E1：先做笛卡爾積，占大量的內(nèi)存空間。

E2和E3:先對(duì)S做選擇操作會(huì)減少大量的元組，再與R做聯(lián)接時(shí)，內(nèi)存空間花費(fèi)小，存取的次數(shù)少，花費(fèi)CUP的時(shí)間少。

關(guān)系代數(shù)運(yùn)算的優(yōu)化原則：在保證語(yǔ)義正確的情況下，先安排選擇，投影運(yùn)算，然后進(jìn)行笛卡爾積，聯(lián)接運(yùn)算。

B=C?二.關(guān)系代數(shù)表達(dá)式的優(yōu)化算法利用等價(jià)變換規(guī)則（見(jiàn)p53）對(duì)關(guān)系代數(shù)表達(dá)式優(yōu)化的算法如下：算法：輸入：關(guān)系代數(shù)表達(dá)式的一棵語(yǔ)法樹(shù)。（樹(shù)中的葉子結(jié)點(diǎn)是關(guān)系，非葉子結(jié)點(diǎn)是操作符）輸出：計(jì)算該表達(dá)式的優(yōu)化程序。算法思想：

①.利用變換規(guī)則將表達(dá)式寫(xiě)成只包含五種關(guān)系代數(shù)的基本運(yùn)算(∪，－，×，∏，σ)，繪出表達(dá)式的語(yǔ)法樹(shù)；

②.將選擇操作盡量向葉子結(jié)點(diǎn)移動(dòng)（即，先做選擇操作）；然后，將投影操作盡量向葉子結(jié)點(diǎn)移動(dòng)（即，后做投影操作）。最后得到一棵表達(dá)式的優(yōu)化的語(yǔ)法樹(shù)。

③.對(duì)優(yōu)化的語(yǔ)法樹(shù)，由下至上掃描，就是計(jì)算該表達(dá)式的優(yōu)化程序。例子：教學(xué)數(shù)據(jù)庫(kù)：S(SNO,SNAME,AGE,SEX);SC(SNO,CNO,GRADE);C(CNO,CNAME,TEACHER)。

有一查詢：查詢至少學(xué)習(xí)LI老師所授一門(mén)課的女學(xué)生的學(xué)號(hào)與姓名。關(guān)系代數(shù)表達(dá)式：

л

SNO，SNAME（σ

TEACHER=’LI’

∧SEX＝‘

F’（SCCS））

(1)

建立語(yǔ)法樹(shù)將上式中的用л,σ,×操作表示：

л

SNO，SNAME（σ

TEACHER=’LI’

∧SEX＝‘

F’(лL(σ

SC.CNO=C.CNO∧SC.SNO＝S.SNO

（SC×C×S）))）其中：L為：SNO,SNAME,AGE,SEX,CNO,CNAME,GRADE,TEACHER.???語(yǔ)法樹(shù)如下：л

|SNO，SNAME

σ

|TEACHER=‘LI’∧SEX=‘F’

л|L:SNO,SNAME,AGE,SEX,CNO,CNAME,GRADE,TEACHER.

σ

|SC.CNO=C.CNO∧SC.SNO=S.SNO

××SSCC(2).優(yōu)化處理

.分裂選擇的條件，并盡量向葉子結(jié)點(diǎn)移動(dòng)；（先執(zhí)行選擇操作）

.分布投影條件；（后執(zhí)行投影操作）。優(yōu)化的語(yǔ)法樹(shù)：л

|SNO，SNAME

σ

|SC.SNO=S.SNO

×

л

л

|SC.SNO|S.SNO,SNAME

σ

σ

|SC.CNO=C.CNO|SEX=‘F’

×S

л

л

|

SC.CNO,SC.SNO

|C.CNO

SC

σ

|TEACHER=‘LI’C

執(zhí)行時(shí)，從葉子端依次向上掃描。2.4關(guān)系演算把數(shù)理邏輯的謂詞引入到關(guān)系中的運(yùn)算。元組關(guān)系運(yùn)算：以元組為變量。域關(guān)系運(yùn)算：以屬性（域）為變量。關(guān)系演算：一、元組關(guān)系運(yùn)算（tuplerelationcalculus）1．元組運(yùn)算表達(dá)式一般形式：{t|p(t)}其中：t為元組變量；P（t）是由原子公式和運(yùn)算符組成的公式。含義：滿足公式P所有元組的集合。（1）原子公式a．R（t）：R為關(guān)系名，t為元組變量。含義：t為R中的任意一個(gè)元組。b.t[i]θu[j]：t和u是元組變量，t[i]和u[j]為分量，θ是算術(shù)比較符。含義：元組t的第i個(gè)分量與元組u的第j個(gè)分量滿足θ關(guān)系為真。例：t[3]﹥u[2]：t的第3個(gè)分量值大于u的第2個(gè)分量值時(shí)為真。c.t[i]θc或cθu[j]:c為常量。含義：元組t的第i分量與常量c滿足θ關(guān)系時(shí)為真。例：t[2]=2:表示元組t的第2個(gè)分量的值等于2時(shí)為真。（2）運(yùn)算符θ算術(shù)比較符>，≥，<，≤，=，≠存在量詞：

和全程量詞:

邏輯運(yùn)算符：￢（非），

∧（與），∨（或）括號(hào)運(yùn)算優(yōu)先級(jí)最高低高高低2．元組運(yùn)算例：設(shè)有關(guān)系R和S如下A1A2A31790afec1895A1A2A31342aacb1540RS計(jì)算下列元組表達(dá)式的值:(1)R1={t|R(t)∧￢s(t)}≡R-SA1A2A3342acb540R1A1A2A313aa15R2(2)R2={t|R(t)∧

t[2]=a}≡σ[2]

=‘a(chǎn)’(R)說(shuō)明：若t作為R的元組變量：R(t)，則t[1],t[2],t[3]分量分別表示A1,A2,A3(3)R3={t|(

u)(R(t)∧s(u)∧t[1]<u[3]∧t[2]≠b)}

≡σR[1]<S[3]∧R[2]≠b(R×S)(4)R4={t|（

u)(R(u)∧t[1]=u[3]∧t[2]=u[1])}≡∏

[3],[1]

(R)(5)R5={t|(

u)(

v)(R(u)∧S(v)∧u[1]>V[1]∧t[1]=u[2]∧t[2]=v[2]∧t[3]=u[1])}R·A2S·A2R·A1aaaccbbcacacac1334422A1A2A3143aca145A3A115401342R5R4R3例：已知學(xué)生關(guān)系模式S（Sno,Sname,age,sex）用元組演算表達(dá)式表示查詢查詢所有男同學(xué)姓名和學(xué)號(hào):{t|(

u)(S(u)∧u[4]=‘男’∧

t[1]=u[2]∧t[2]=u[1])}二、域關(guān)系運(yùn)算(domainrelationcalculus)域關(guān)系表達(dá)式一般形式：{X1，X2……,XK∣φ(X1，X2……,XK

)}

其中：X1，X2……Xk表示關(guān)系中的域變量；φ是原子公式與運(yùn)算符組成的公式

含義：所有使得φ為真的那些X1，X2……XK組成的元組集合。

R（X1，X2，……XK）；R為K元關(guān)系,Xi為常量或域變量含義：由分量X1，X2……，XK組成的元組屬于R.

XiθC或CθXi：C為常量，Xi為域變量;θ為運(yùn)算符，含義同前

XiθXj

：xi和yj

分別為元組X和Y的域變量。原子公式：例：設(shè)關(guān)系R和S，W如下：DEF254abcdefABC552bdc634ABC541bac168RSW計(jì)算（1）R1={xyf|R(xyf)∧(f>5

∨

y=a)}(2)R2={xyf|R(xyf)∨S(xyf)∧x=5

∧

f≠6}(3)R3={xyf|(

v)(

u)(R(yxu)∧

w(vTf)

∧

u＞v)}ABC41ac68BAFaaaccc444111defdefABC5415bacd1683R1R2R32．域演算例子將元組表達(dá)式化為等價(jià)的域表達(dá)式方法：元組變量t,用域變量名替代：對(duì)于k元的元組變量t，引入k個(gè)域變量t1,t2,…,tk；在公式中t,用t1，t2，…，tk替換。元組分量t[i]，用域變量名ti替換。每個(gè)量詞（

u）或（

u）元組變量u,用域變量u1，u2，…um代替。u[i]用ui

替換例：{W|(

u)(v)(R(u)∧S(v)∧u[2]=v[1]∧w[1]=u[1]∧w[2]=v[2])}轉(zhuǎn)化成域表達(dá)式：

{W1W2|(

u1)(

u2)(

v1)(

v2)(R(u1u2)∧S(v1v2)∧u2=v1∧w1=u1∧w2=v2)}化簡(jiǎn)：{w1w2|(

u2)(R(w1u2)∧S(u2w2))}例：已知關(guān)系SC（Sno，Cno，grade）用域表達(dá)式表示下列查詢:查找課程號(hào)為“1”的學(xué)生學(xué)號(hào)和成績(jī)第一步首先寫(xiě)成元組表達(dá)式：

{t|(

u)(SC(u)∧u[2]=‘1’∧t[1]=u[1]∧t[2]=u[3])}第二步，將元組表達(dá)式轉(zhuǎn)換域表達(dá)式

{t1t2|(

u1)(

u2)(

u3)(SC(u1u2u3)∧u2=‘1’∧t1=u1∧t2=u3)