第三章 關(guān)系運(yùn)算

第三章關(guān)系運(yùn)算第1頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月第三章關(guān)系運(yùn)算教學(xué)內(nèi)容：基本概念：

關(guān)系代數(shù)：

關(guān)系演算：查詢優(yōu)化：

關(guān)系模型、關(guān)鍵碼、關(guān)系的定義和性質(zhì)、三類(lèi)完整性規(guī)則?；静僮鳌⒔M合操作、擴(kuò)充操作。元組演算、域演算、關(guān)系演算的安全性和等價(jià)性。關(guān)系代數(shù)表達(dá)式的等價(jià)轉(zhuǎn)換規(guī)則、優(yōu)化算法。教學(xué)重點(diǎn)：關(guān)系代數(shù)運(yùn)算第2頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月§1關(guān)系數(shù)據(jù)模型的基本概念一、基本術(shù)語(yǔ)

用二維表格表示實(shí)體集，外鍵表示實(shí)體間聯(lián)系的模型稱為關(guān)系模型；關(guān)系：對(duì)應(yīng)二維表格；元組：表中的行；屬性：表中的列；域：屬性的取值范圍。第3頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月

二、數(shù)學(xué)定義

定義一：域（Domain）是值的集合。即域是屬性的取值范圍。

定義二：關(guān)系的定義

①用集合論的觀點(diǎn)定義關(guān)系：②用值域的觀點(diǎn)定義關(guān)系：

關(guān)系是一個(gè)元數(shù)為K的元組的集合。即這個(gè)關(guān)系中有若干個(gè)元組，每個(gè)元組有K個(gè)屬性值。把關(guān)系看成一個(gè)集合，集合中的元素是元組。關(guān)系是屬性值域笛卡兒積的一個(gè)子集。第4頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月三、關(guān)系的性質(zhì)1、列具有相同的性質(zhì)，不同的列可有相同的域，2、任意兩個(gè)元組不能相同，元組的次序可交換；3、每個(gè)屬性值(分量)都是不可分的數(shù)據(jù)項(xiàng)(即屬性值為最小單位).

第5頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月四、關(guān)鍵碼超鍵：侯選鍵：主鍵：外鍵：能唯一標(biāo)識(shí)元組的屬性組合（可能存在多余的屬性）。能唯一標(biāo)識(shí)元組的最小屬性組合。不含有多余屬性的超鍵若一個(gè)關(guān)系中有多個(gè)侯選鍵,則選其中的一個(gè)為關(guān)系的主鍵。若某個(gè)屬性組F是關(guān)系R的主鍵,F又在關(guān)系S中出現(xiàn),則F是S的外鍵.若一個(gè)關(guān)系R中包含有另一個(gè)關(guān)系S的主鍵所對(duì)應(yīng)的屬性組F，則稱F為R的外鍵。稱關(guān)系S為參照關(guān)系，R為依賴關(guān)系。第6頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月五、關(guān)系模型的三類(lèi)完整性規(guī)則實(shí)體完整性規(guī)則：參照完整性規(guī)則：用戶定義的完整性規(guī)則：

若某個(gè)屬性組F是關(guān)系R的主鍵,F又在關(guān)系S中出現(xiàn),則F是S的外鍵.F在S中的取值只有兩種可能,一為空,二為R中的某個(gè)主鍵值通過(guò)外鍵子句來(lái)實(shí)現(xiàn)(foreignkey)。由應(yīng)用環(huán)境決定，反映某一具體應(yīng)用涉及的數(shù)據(jù)必須滿足的約束條件。關(guān)系中元組的主鍵值不能為空且不能重復(fù)。通過(guò)主鍵子句來(lái)實(shí)現(xiàn)(primarykey)第7頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月六、關(guān)系模型的形式定義(有三個(gè)組成部分)數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)操作：完整性規(guī)則：數(shù)據(jù)庫(kù)中全部數(shù)據(jù)及其相互聯(lián)系都被組織成關(guān)系（即二維表格）的形式。提供了一組完備的高級(jí)關(guān)系運(yùn)算，以支持對(duì)數(shù)據(jù)庫(kù)的各種操作。關(guān)系運(yùn)算分為關(guān)系代數(shù)和關(guān)系演算兩類(lèi)。三類(lèi)完整性規(guī)則第8頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月§2關(guān)系代數(shù)一、關(guān)系數(shù)據(jù)語(yǔ)言關(guān)系數(shù)據(jù)庫(kù)語(yǔ)言由查詢語(yǔ)句（描述用戶的檢索操作）和更新語(yǔ)句（描述用戶的插入、修改和刪除等操作）兩大類(lèi)組成。關(guān)系查詢語(yǔ)言分為：

關(guān)系代數(shù)語(yǔ)言：關(guān)系演算語(yǔ)言：

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

域關(guān)系演算語(yǔ)言SQL第9頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月二、關(guān)系代數(shù)的基本運(yùn)算并（union）：設(shè)關(guān)系R和關(guān)系S具有相同的元數(shù)，且相應(yīng)的屬性列具有相同的特征：

R∪S≡{t︱t∈R∨t∈S}其中：t是元組變量，R和S的元數(shù)相同。并運(yùn)算要求兩個(gè)關(guān)系屬性的性質(zhì)必須一致且并運(yùn)算的結(jié)果要消除重復(fù)的元組。舉例：第10頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月2.差(differedce)：設(shè)關(guān)系R和關(guān)系S具有相同的元數(shù)，且相應(yīng)的屬性列具有相同的特征：

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

S}其中：t是元組變量，R和S的元數(shù)相同。舉例：第11頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月3.笛卡兒積（cartesianproduct）

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

R×S≡{t︱t=<tr,ts>∧tr∈R∧ts∈S}若R有n個(gè)元組，S有m個(gè)元組，則R×S有n×m個(gè)元組。

舉例：第12頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月

4.投影（projection）：

對(duì)一個(gè)關(guān)系進(jìn)行垂直分割,消去某些列，并重新安排列的順序,再刪去重復(fù)元組。πi1,…,im(R)≡{t|t=<ti1,…,tim>∧<t1,…,tm>∈R,1mk}設(shè)關(guān)系R是k元關(guān)系，R在其分量Ai1,…,Aim(m≤k,…,i1,…,im為1到k之間的整數(shù))上的投影用πi1,…,im（R）表示，它是從R中選擇若干屬性列組成的一個(gè)m元元組的集合，形式定義如下：舉例：第13頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月5.選擇(selection)

根據(jù)某些條件對(duì)關(guān)系做水平分割,選擇符合條件的元組。條件用命題公式F（即計(jì)算在括號(hào)中的條件表達(dá)式）表示.

F中的運(yùn)算對(duì)象:常量(用引號(hào)括起來(lái)）,元組分量（屬性名或列的序號(hào)），算術(shù)比較運(yùn)算符:＜，≤，＞，≥，＝，≠,邏輯運(yùn)算符:∧，∨，┐。關(guān)系R關(guān)于公式F的選擇操作用σF（R）表示，形式定義如下：σF（R）={t|t∈R∧F(t)=‘T’}舉例：第14頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月三、關(guān)系代數(shù)的組合操作1、交（intersection）設(shè)關(guān)系R和關(guān)系S具有相同的元數(shù)n（即兩個(gè)關(guān)系都有n個(gè)屬性），而且相應(yīng)的屬性取自同一個(gè)域。關(guān)系R和S的交記為R∩S，結(jié)果仍為n元的關(guān)系。由即屬于R又屬于S的元組組成。形式定義如下：

R∩S≡{t︱t∈R∧t∈S}t是元組變量，R和S的元數(shù)相同。關(guān)系的交可以由關(guān)系的差來(lái)表示，即：R∩S≡R-（R-S）舉例:第15頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月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)如果θ為等號(hào)“=”，那么這個(gè)聯(lián)結(jié)操作稱為等值連接。

?

F

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

這里F是形為F1∧F2∧…∧Fn公式，每個(gè)Fi是形為iθj的式子。而i和j分別為關(guān)系R和S的第i個(gè)分量和第j個(gè)分量的序號(hào)。舉例：第16頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月

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

將關(guān)系R和S中公共屬性組滿足對(duì)應(yīng)分量相等的元組聯(lián)接起來(lái)，并且要在結(jié)果中將重復(fù)的屬性去掉。

R

?

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

舉例：第17頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月4、除(division)

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

R÷S:是一個(gè)（r-s）元的元組的集合，是滿足下列條件的最大關(guān)系：其中每個(gè)元組t與S中每個(gè)元組u組成的新元組<t,u>必在關(guān)系R中。第18頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月

R÷S的具體計(jì)算過(guò)程如下：

①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)舉例：第19頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月四、關(guān)系代數(shù)表達(dá)式及其應(yīng)用實(shí)例

第20頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月工程項(xiàng)目零件供應(yīng)數(shù)據(jù)庫(kù)PROJECTY有四個(gè)關(guān)系模式：

供應(yīng)商關(guān)系：S(SNO,SNAME,SADDR)零件關(guān)系：P(PNO,PNAME,COLOR,WEIGHT)工程項(xiàng)目關(guān)系：J(JNO,JNAME,JCITY,BALANCE)供應(yīng)情況關(guān)系：SPJ(SNO,PNO,JNO,PRICE,QTY)πSN0,PN0(σJNO=‘J1’

(SPJ))或:πl(wèi),2(σ3='J1’(SPJ))試用關(guān)系代數(shù)表達(dá)式表示每個(gè)查詢語(yǔ)句。.檢索供應(yīng)零件給工程J1的供應(yīng)商編號(hào)SNO與零件編號(hào)PNO。第21頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月πSNO（σJNO=‘J1’∧PNO=‘P1’（SPJ））3.檢索使用了編號(hào)為P3零件的工程編號(hào)和名稱。2.檢索供應(yīng)零件給工程J1，且零件編號(hào)為P1的供應(yīng)商編號(hào)SNO。4.檢索供應(yīng)零件給工程J1,且零件顏色為紅色的供應(yīng)商名稱和地址。5.檢索使用了零件編號(hào)為P3或P5零件的工程編號(hào)JNO。πJNO,JNAME（σPNO=‘P3’（J?SPJ))πSNAME,SADDR(σJNO=‘J1'∧COLOR=‘紅色’(S?SPJ?P))πJNO（σPNO=‘P3'∨PNO=‘P5’(SPJ))第22頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月6.檢索至少使用了編號(hào)為P3和P5零件的工程編號(hào)JNO。π3（σ3=8∧2=‘P3'∧7=‘P5'

(SPJ×SPJ))7.檢索不使用編號(hào)為P3零件的工程編號(hào)JNO和工程名稱JNAME。πJNO,JNAME(J)―πJNO,JNAME(σPNO=‘P3’(J?SPJ))8.檢索使用了全部零件的工程名稱JNAME。πJNAME(J?(πJNO,PNO(SPJ)÷πPNO(P))9.檢索使用零件包含編號(hào)為S1的供應(yīng)商所供應(yīng)的全部零件的工程編號(hào)JNO。πJNO,PNO(SPJ)÷πPNO(σSNO=‘S1’(SPJ))第23頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月舉例假設(shè)學(xué)生數(shù)據(jù)庫(kù)中的關(guān)系模式如下：

S（SNO,SNAME,AGE,SEX,SDEPT）C（CNO,CNAME,CDEPT,TNAME）SC（SNO,CNO,GRADE）試用關(guān)系代數(shù)表達(dá)式表示每個(gè)查詢語(yǔ)句。.檢索計(jì)算機(jī)系的全體學(xué)生的學(xué)號(hào)、姓名和性別。2.檢索學(xué)習(xí)課程號(hào)為C2的學(xué)生的學(xué)號(hào)和姓名。3.檢索選修課程名為“數(shù)據(jù)結(jié)構(gòu)”的學(xué)生的學(xué)號(hào)和姓名。4.檢索選修課程號(hào)為C2或C4的學(xué)生的學(xué)號(hào)。5.檢索至少選修課程號(hào)為C2和C4的學(xué)生的學(xué)號(hào)。第24頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月7.檢索選修了全部課程的學(xué)生的姓名和所在系。6.檢索沒(méi)有選修C2課程的學(xué)生的姓名和年齡。8.檢索選修課程包含學(xué)生S2所選的全部課程的學(xué)生的學(xué)號(hào)。9.將新課程<‘C8’,‘?dāng)?shù)據(jù)挖掘’,‘計(jì)算機(jī)’,‘劉老師’>>插入到課程表C中。10.將學(xué)號(hào)為S4所選修的C4課程的成績(jī)修改為85分。第25頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月五、擴(kuò)充的關(guān)系代數(shù)操作1.外聯(lián)接（outerjoin）R

?

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

第26頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月i、如果R和S做自然聯(lián)接時(shí)，把R中原該舍棄的元組放到新關(guān)系中，那么這種操作稱為“左外聯(lián)接”操作，用符號(hào):RS表示。

ii、如果R和S做自然聯(lián)接時(shí)，把S中原該舍棄的元組放到新關(guān)系中，那么這種操作稱為“右外聯(lián)接”操作，用符號(hào):RS表示。第27頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月ABCabcbbfcadBCDbcdbceadbefgABCDabcdabcecadbbbfnullnullefg關(guān)系R關(guān)系SABCDabcdabcecadbbbfnullABCDabcdabcecadbnullefg第28頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月2.外部并（outerunion）

如果R和S的關(guān)系模式不同，構(gòu)成的新關(guān)系屬性有R和S的所有屬性組成（公共屬性只取一次），新關(guān)系的元組由屬于R或?qū)儆赟的元組構(gòu)成，同時(shí)元組在新增加的屬性上填上空值(null)。ABCDabcnullbbfnullcadnullnullbcdnullbcenulladbnullefg第29頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月3.半聯(lián)接（semijoin）關(guān)系R和S的半聯(lián)接操作記為R?S:

R和S的自然聯(lián)接在關(guān)系R的屬性集上的投影即：R?S≡πR（R?S）第30頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月關(guān)系R關(guān)系SR?SR

?SS

?RABCDabcdabcedbcddbcecadbABCabcdbccadBCDbcdbceadbBCDbcdbceadbABCabcdbcbbfcad第31頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月§4關(guān)系演算

以數(shù)理邏輯中的謂詞演算為基礎(chǔ)，用公式表示關(guān)系演算的條件。關(guān)系演算按所用到的變量不同可分為：元組關(guān)系演算－－－以元組為變量；域關(guān)系演算－－－以域?yàn)樽兞俊?/p>

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

(t)}

其中t：元組變量；

：公式，公式有原子公式及運(yùn)算符組成。第32頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月1.原子公式有下列三種形式：①R（t）：R是關(guān)系名，t是元組變量。②t[i]θu[j]:t和u是元組變量，θ是算術(shù)比較運(yùn)算符。③t[i]θC或Cθu[i]：t和u是元組變量，c是常量。

2.約束變量和自由變量在一個(gè)公式中，如果一個(gè)元組變量的前面沒(méi)有存在量詞ョ或全稱量詞

的符號(hào)定義，稱之為自由元組變量，否則稱為約束元組變量。

第33頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月3.運(yùn)算符及優(yōu)先次序?yàn)椋篿.括號(hào)中運(yùn)算符優(yōu)先級(jí)最高ii.算術(shù)比較運(yùn)算符最高；iii.量詞：存在量詞ョ全稱量詞

iv.邏輯運(yùn)算符：、∧、∨優(yōu)先級(jí)最高第34頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月4.公式中變量的遞歸定義如下：①每個(gè)原子公式是一個(gè)公式。其中的元組變量是自由變量;

②如果

1和

2是元組關(guān)系演算公式，則:

1∧

2,

1∨

2,┓

1也是元組關(guān)系演算公式;③若

是元組關(guān)系演算公式，則(

t)(

)也是元組關(guān)系演算公式;④若

是元組關(guān)系演算公式，則(

t)(

)也是元組關(guān)系演算公式;⑤在元組演算公式中，各種運(yùn)算符的優(yōu)先次序?yàn)椋豪ㄌ?hào),算術(shù)比較運(yùn)算符,ョ,,、∧、∨⑥有限次地使用上述五條規(guī)則得到的公式是元組關(guān)系演算公式，其他公式不是元組關(guān)系演算公式。第35頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月5.用元組關(guān)系演算表達(dá)式表示關(guān)系運(yùn)算并: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在元組演算中的等價(jià)表示形式。

第36頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月如果P1和P2是公式，在元組關(guān)系演算的公式中，存在下列等價(jià)轉(zhuǎn)換規(guī)則：

P1∧P2

┐(┐P1∨┐P2)P1∨P2

┐(┐P1∧┐P2）

(

s)(P1(s))

┐(

s)(┐P1(s))(

s)(P1(s))

┐(

s)(┐P1(s))P1

P2

┐P1∨P2第37頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月6.實(shí)例:用元組表達(dá)式形式表示下列查詢第38頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月例:用元組表達(dá)式形式表示下列查詢：1.檢索供應(yīng)零件給工程J1，且零件編號(hào)為P1的供應(yīng)商編號(hào)SNO。{t|(

u)(SPJ(u)∧u[2]=‘P1’∧u[3]=‘J1’∧t[l]=u[1])}2.檢索使用了編號(hào)為P3零件的工程編號(hào)和名稱。{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.檢索至少使用了編號(hào)為P3和P5零件的工程編號(hào)JNO。第39頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月{t|(

u)(

v)(J(u)∧SPJ(v)∧((u[l]=v[3])v[2]≠’P3’)

∧t[1]=u[1]∧t[2]=u[2])}4.檢索不使用編號(hào)為P3零件的工程編號(hào)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.檢索使用零件包含編號(hào)為S1供應(yīng)商所供應(yīng)的全部零件的工程編號(hào)。第40頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月二、域關(guān)系演算域演算表達(dá)式的定義類(lèi)似于元組演算表達(dá)式的定義，

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

域變量的變化范圍是某個(gè)值域而不是一個(gè)關(guān)系。

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

其中t1、t2、…、tk分別是元組變量t的各個(gè)分量的域變量，P是域演算公式。第41頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月①原子公式有下列兩種形式：i．R（t1…tk）：R是K元關(guān)系，每個(gè)ti是域變量或常量。ii．xθy,其中x,y是域變量或常量，但至少有一個(gè)是域變量，θ是算術(shù)比較運(yùn)算符。②域關(guān)系演算的公式中也可使用∧、∨、

和=>等邏輯運(yùn)算符也可用(

x)和（

x）形成新的公式，但變量x是域變量，不是元組變量。自由域變量、約束域變量等概念和元組演算中一樣。第42頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月2.元組表達(dá)式到域表達(dá)式的轉(zhuǎn)換規(guī)則：①對(duì)于k元的元組變量t,引入k個(gè)域變量t1,t2,…,tk,在公式中t用t1,t2,…,tk替換，元組分量t[i]用ti替換。②對(duì)于每個(gè)量詞(

u)或（

u），若u是m元的元組變量，則引入m個(gè)新的域變量u1,u2,…,um。在量詞的轄域內(nèi)，u用u1u2…um替換，u[i]用ui替換，(

u)用(

u1)…(

um)替換，(

u）用（

u1）…(

um)替換。3.舉例

第43頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月安全運(yùn)算：

不產(chǎn)生無(wú)限關(guān)系和無(wú)窮次驗(yàn)證的運(yùn)算稱為安全運(yùn)算，相應(yīng)的表達(dá)式稱為是安全表達(dá)式。所采用的措施稱為安全約束。安全約束集DOM(

):公式中的常量和中所出現(xiàn)關(guān)系的所有屬性值組成的集合。三、關(guān)系運(yùn)算的安全性和等價(jià)性1.關(guān)系運(yùn)算的安全性{t|

R(t)}無(wú)限關(guān)系

驗(yàn)證(

u)(w(u))為’T’或（

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

無(wú)窮驗(yàn)證

第44頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月2.關(guān)系運(yùn)算的等價(jià)性并、差、笛卡兒積、投影和選擇是關(guān)系代數(shù)最基本的操作，并構(gòu)成了關(guān)系代數(shù)運(yùn)算的最小完備集?？梢宰C明，在這個(gè)基本上，關(guān)系代數(shù)、安全的元組關(guān)系演算、安全的域關(guān)系演算在關(guān)系的表達(dá)和操作能力上是等價(jià)的。

第45頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月

§5查詢優(yōu)化關(guān)系代數(shù)表達(dá)式的優(yōu)化問(wèn)題:

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

如何花費(fèi)較少的時(shí)間和空間，有效地執(zhí)行笛卡兒積操作.第46頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月一、查詢優(yōu)化的總目標(biāo)選擇有效的策略，求得給定關(guān)系代數(shù)表達(dá)式的值，達(dá)到提高DBMS系統(tǒng)效率的目標(biāo)。第47頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月例:學(xué)生數(shù)據(jù)庫(kù)：S(SNO,SNAME,SEX,AGE,SDEPT)C(CNO,CNAME,CDEPT,TNAME)SC(SNO,CNO,GRADE)檢索選修C2課程的學(xué)生的學(xué)號(hào)和姓名,用關(guān)系代數(shù)表達(dá)式表示：

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））這三個(gè)關(guān)系代數(shù)表達(dá)式是等價(jià)的，但執(zhí)行的效率大不一樣。顯然，求El，E2，E3的大部分時(shí)間是花在聯(lián)接操作上的。第48頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月二、代數(shù)表達(dá)式的等價(jià)變換規(guī)則

1、

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

E1

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

F?

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

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

（E1×E2）

×

E3≡E1×（E2×E3）?

F1?

F1?

F2?

F2????

第49頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月3.投影的串接設(shè)L1，L2，…，Ln為屬性集，并且L1

L2

…

Ln，成立：πL1（πL2（…（πLn（E））…））≡πL1（E）4．

選擇的串接

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

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

第50頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月5．

選擇和投影操作的交換πL（σF（E））≡σF（πL（E））要求條件F只涉及到L中的屬性,如果F還涉及到不在L中的屬性集L1：πL（σF（E））≡πL（σF（πL∪L1（E）））6．

選擇對(duì)笛卡兒積的分配律

σF（E1×E2）≡σF（E1）×E2σF（E1×E2）≡σF1（E1）×σF2（E2）σF（E1×E2）≡σF2（σF1（E1）×E2）第51頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月7.

選擇對(duì)并的分配律

σF（E1∪E2）≡σF1（E1）∪σF2（E2）8．選擇對(duì)集合差的分配律σF（E1－E2）≡σF（E1）－σF（E2）9．選擇對(duì)自然聯(lián)接的分配律σF（E1?E2）≡σF（E1）?σF（E2）10．投影對(duì)笛卡兒積的分配律

πL1∪L2（E1×E2）≡πL1（E1）×πL2（E2）第52頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月11．投影對(duì)并的分配律

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

E2

13．并和交的交換律

E1∪E2≡E2∪E1E1∩E2≡E2∩E114．并和交的結(jié)合律

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

F2?F2∧F2第53頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月三、優(yōu)化的一般策略(1--6)(1)在關(guān)系代數(shù)表達(dá)式中盡可能早地執(zhí)行選擇操作。(2)把笛卡兒積和其后的選擇操作合并成F聯(lián)接運(yùn)算。(3)同時(shí)計(jì)算一連串的選擇和投影操作，以免分開(kāi)運(yùn)算造成多次掃描文件，節(jié)省操作時(shí)間。(4)如在一個(gè)表達(dá)式中多次出現(xiàn)某個(gè)子表達(dá)式，可先對(duì)該子表達(dá)式進(jìn)行計(jì)算并保存結(jié)果，以免重復(fù)計(jì)算。

(5)適當(dāng)?shù)貙?duì)關(guān)系文件進(jìn)行預(yù)處理。

(6)在計(jì)算表達(dá)式前應(yīng)先估計(jì)一下怎么計(jì)算合算。

第54頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月三、關(guān)系代數(shù)表達(dá)式的優(yōu)化算法輸入：一棵關(guān)系代數(shù)表達(dá)式的語(yǔ)法樹(shù)。

輸出：計(jì)算表達(dá)式的一個(gè)優(yōu)化序列。

方法:依次執(zhí)行下面每一步。①使用等價(jià)變換規(guī)則⑷把每個(gè)形為σF1∧…∧Fn（E）的子表達(dá)式轉(zhuǎn)換成選擇串接形式：σF1（…σFn（E））…）②對(duì)每個(gè)選擇操作，使用規(guī)則⑷～⑼，盡可能把選擇操作移近樹(shù)的葉端（即盡可能早地執(zhí)行選擇操作）。③對(duì)每個(gè)投影操作，使用規(guī)則(3)，(5)，(10)和(11)，盡可能把投影操作移近樹(shù)的葉端。第55頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月④使用規(guī)則⑶～⑸，把選擇和投影合并成單個(gè)選擇、單個(gè)投影或一個(gè)選擇后跟一個(gè)投影。⑤對(duì)上述步驟得到的語(yǔ)法樹(shù)的內(nèi)結(jié)點(diǎn)進(jìn)行分組。分組原則：a、每個(gè)二元運(yùn)算(×、∪、－)結(jié)點(diǎn)與其直接祖先(不超過(guò)其他的二元運(yùn)算結(jié)點(diǎn)）的一元運(yùn)算結(jié)點(diǎn)(σ或π)分為一組。如果它的