第三章關系運算第1頁，課件共63頁，創作于2023年2月第三章關系運算教學內容：基本概念：

關系代數：

關系演算：查詢優化：

關系模型、關鍵碼、關系的定義和性質、三類完整性規則。基本操作、組合操作、擴充操作。元組演算、域演算、關系演算的安全性和等價性。關系代數表達式的等價轉換規則、優化算法。教學重點：關系代數運算第2頁，課件共63頁，創作于2023年2月§1關系數據模型的基本概念一、基本術語

用二維表格表示實體集，外鍵表示實體間聯系的模型稱為關系模型；關系：對應二維表格；元組：表中的行；屬性：表中的列；域：屬性的取值范圍。第3頁，課件共63頁，創作于2023年2月

二、數學定義

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

定義二：關系的定義

①用集合論的觀點定義關系：②用值域的觀點定義關系：

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

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

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

關系代數語言：關系演算語言：

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

域關系演算語言SQL第9頁，課件共63頁，創作于2023年2月二、關系代數的基本運算并（union）：設關系R和關系S具有相同的元數，且相應的屬性列具有相同的特征：

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

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

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

設關系R和關系S的元數分別為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個元組。

舉例：第12頁，課件共63頁，創作于2023年2月

4.投影（projection）：

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

根據某些條件對關系做水平分割,選擇符合條件的元組。條件用命題公式F（即計算在括號中的條件表達式）表示.

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

R∩S≡{t︱t∈R∧t∈S}t是元組變量，R和S的元數相同。關系的交可以由關系的差來表示，即：R∩S≡R-（R-S）舉例:第15頁，課件共63頁，創作于2023年2月2、聯接(join)

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

①θ聯接：

②F聯接：?

iθjRS≡σiθ(r+j)(R×S)如果θ為等號“=”，那么這個聯結操作稱為等值連接。

?

F

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

這里F是形為F1∧F2∧…∧Fn公式，每個Fi是形為iθj的式子。而i和j分別為關系R和S的第i個分量和第j個分量的序號。舉例：第16頁，課件共63頁，創作于2023年2月

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

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

R

?

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

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

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

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

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)舉例：第19頁，課件共63頁，創作于2023年2月四、關系代數表達式及其應用實例

第20頁，課件共63頁，創作于2023年2月工程項目零件供應數據庫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,2(σ3='J1’(SPJ))試用關系代數表達式表示每個查詢語句。.檢索供應零件給工程J1的供應商編號SNO與零件編號PNO。第21頁，課件共63頁，創作于2023年2月π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))第22頁，課件共63頁，創作于2023年2月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))第23頁，課件共63頁，創作于2023年2月舉例假設學生數據庫中的關系模式如下：

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

?

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

第26頁，課件共63頁，創作于2023年2月i、如果R和S做自然聯接時，把R中原該舍棄的元組放到新關系中，那么這種操作稱為“左外聯接”操作，用符號:RS表示。

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

如果R和S的關系模式不同，構成的新關系屬性有R和S的所有屬性組成（公共屬性只取一次），新關系的元組由屬于R或屬于S的元組構成，同時元組在新增加的屬性上填上空值(null)。ABCDabcnullbbfnullcadnullnullbcdnullbcenulladbnullefg第29頁，課件共63頁，創作于2023年2月3.半聯接（semijoin）關系R和S的半聯接操作記為R?S:

R和S的自然聯接在關系R的屬性集上的投影即：R?S≡πR（R?S）第30頁，課件共63頁，創作于2023年2月關系R關系SR?SR

?SS

?RABCDabcdabcedbcddbcecadbABCabcdbccadBCDbcdbceadbBCDbcdbceadbABCabcdbcbbfcad第31頁，課件共63頁，創作于2023年2月§4關系演算

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

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

(t)}

其中t：元組變量；

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

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

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

第33頁，課件共63頁，創作于2023年2月3.運算符及優先次序為：i.括號中運算符優先級最高ii.算術比較運算符最高；iii.量詞：存在量詞ョ全稱量詞

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

②如果

1和

2是元組關系演算公式，則:

1∧

2,

1∨

2,┓

1也是元組關系演算公式;③若

是元組關系演算公式，則(

t)(

)也是元組關系演算公式;④若

是元組關系演算公式，則(

t)(

)也是元組關系演算公式;⑤在元組演算公式中，各種運算符的優先次序為：括號,算術比較運算符,ョ,,、∧、∨⑥有限次地使用上述五條規則得到的公式是元組關系演算公式，其他公式不是元組關系演算公式。第35頁，課件共63頁，創作于2023年2月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在元組演算中的等價表示形式。

第36頁，課件共63頁，創作于2023年2月如果P1和P2是公式，在元組關系演算的公式中，存在下列等價轉換規則：

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頁，課件共63頁，創作于2023年2月6.實例:用元組表達式形式表示下列查詢第38頁，課件共63頁，創作于2023年2月例:用元組表達式形式表示下列查詢：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。第39頁，課件共63頁，創作于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.檢索不使用編號為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供應商所供應的全部零件的工程編號。第40頁，課件共63頁，創作于2023年2月二、域關系演算域演算表達式的定義類似于元組演算表達式的定義，

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

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

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

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

和=>等邏輯運算符也可用(

x)和（

x）形成新的公式，但變量x是域變量，不是元組變量。自由域變量、約束域變量等概念和元組演算中一樣。第42頁，課件共63頁，創作于2023年2月2.元組表達式到域表達式的轉換規則：①對于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.舉例

第43頁，課件共63頁，創作于2023年2月安全運算：

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

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

R(t)}無限關系

驗證(

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

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

無窮驗證

第44頁，課件共63頁，創作于2023年2月2.關系運算的等價性并、差、笛卡兒積、投影和選擇是關系代數最基本的操作，并構成了關系代數運算的最小完備集。可以證明，在這個基本上，關系代數、安全的元組關系演算、安全的域關系演算在關系的表達和操作能力上是等價的。

第45頁，課件共63頁，創作于2023年2月

§5查詢優化關系代數表達式的優化問題:

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

如何花費較少的時間和空間，有效地執行笛卡兒積操作.第46頁，課件共63頁，創作于2023年2月一、查詢優化的總目標選擇有效的策略，求得給定關系代數表達式的值，達到提高DBMS系統效率的目標。第47頁，課件共63頁，創作于2023年2月例:學生數據庫：S(SNO,SNAME,SEX,AGE,SDEPT)C(CNO,CNAME,CDEPT,TNAME)SC(SNO,CNO,GRADE)檢索選修C2課程的學生的學號和姓名,用關系代數表達式表示：

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））這三個關系代數表達式是等價的，但執行的效率大不一樣。顯然，求El，E2，E3的大部分時間是花在聯接操作上的。第48頁，課件共63頁，創作于2023年2月二、代數表達式的等價變換規則

1、

聯接和笛卡兒積的交換律

E1

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

F?

F??2．聯接和笛卡兒積的結合律

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

（E1×E2）

×

E3≡E1×（E2×E3）?

F1?

F1?

F2?

F2????

第49頁，課件共63頁，創作于2023年2月3.投影的串接設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頁，課件共63頁，創作于2023年2月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）第51頁，課件共63頁，創作于2023年2月7.

選擇對并的分配律

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

πL1∪L2（E1×E2）≡πL1（E1）×πL2（E2）第52頁，課件共63頁，創作于2023年2月11．投影對并的分配律

πL（E1∪E2）≡πL（E1）∪πL（E2）12．選擇與聯接操作的結合σ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第53頁，課件共63頁，創作于2023年2月三、優化的一般策略(1--6)(1)在關系代數表達式中盡可能早地執行選擇操作。(2)把笛卡兒積和其后的選擇操作合并成F聯接運算。(3)同時計算一連串的選擇和投影操作，以免分開運算造成多次掃描文件，節省操作時間。(4)如在一個表達式中多次出現某個子表達式，可先對該子表達式進行計算并保存結果，以免重復計算。

(5)適當地對關系文件進行預處理。

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

第54頁，課件共63頁，創作于2023年2月三、關系代數表達式的優化算法輸入：一棵關系代數表達式的語法樹。

輸出：計算表達式的一個優化序列。

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