關系模型和關系運算理論第一頁，共六十三頁，2022年，8月28日本章重要概念（一）（1）基本概念 關系模型，關鍵碼（主鍵和外鍵），關系的定義和性質，三類完整性規則，ER模型到關系模型的轉換規則，過程性語言與非過程性語言。（2）關系代數 五個基本操作，四個組合操作，七個擴充操作。

第二頁，共六十三頁，2022年，8月28日本章重要概念（二）（3）關系演算 元組關系演算和域關系演算的原子公式、公式的定義。關系演算的安全性和等價性。（4）關系代數表達式的優化 關系代數表達式的等價及等價轉換規則，啟化式優化算法。（5）關系邏輯 謂詞、原子、規則和查詢，規則的安全性，用規則模擬關系代數表達式。

第三頁，共六十三頁，2022年，8月28日本章概要本章先介紹關系模型的基本概念；然后介紹關系運算的三種理論：關系代數、關系演算和關系邏輯。

第四頁，共六十三頁，2022年，8月28日關系模型和關系運算理2.1關系模型的基本概念2.2關系代數2.3關系演算2.4關系代數表達式的優化2.5關系邏輯

第五頁，共六十三頁，2022年，8月28日2.1關系模型的基本概念

2.1.1基本術語

2.1.2關系的定義和性質2.1.3關系模型的三類完整性規則

2.1.4ER模型向關系模型的轉換規則

2.1.5關系模型的三級體系結構

2.1.6關系模型的形式定義和優點

2.1.7關系查詢語言和關系運算

返回第六頁，共六十三頁，2022年，8月28日基本術語(1)定義2.1用二維表格表示實體集，用關鍵碼進行數據導航的數據模型稱為關系模型（relationalModel）。這里數據導航(datanavigation)是指從已知數據查找未知數據的過程和方法。

圖2.1職工登記表

第七頁，共六十三頁，2022年，8月28日基本術語(2)

在關系模型中，字段稱為屬性，字段值稱為屬性值，記錄類型稱為關系模式。在圖2.2中，關系模式名是R。記錄稱為元組（tuple），元組的集合稱為關系（relation）或實例（instance）。一般用大寫字母A、B、C、…

表示單個屬性，用大寫字母…、X、Y、Z表示屬性集，用小寫字母表示屬性值，有時也習慣稱呼關系為表或表格，元組為行(row)，屬性為列(column)。關系中屬性個數稱為“元數”（arity），元組個數為“基數”(cardinality)。

第八頁，共六十三頁，2022年，8月28日基本術語(3)關系元數為5，基數為4

一般術語

關系模型術語字段、數據項 屬性記錄類型 關系模式記錄1 元組1記錄2 元組2記錄3 元組3記錄4 元組4字段值 屬性值圖2.2關系模型的術語

第九頁，共六十三頁，2022年，8月28日基本術語(4)

關鍵碼(key,簡稱鍵)由一個或多個屬性組成。在實際使用中，有下列幾種鍵。（1）超建（superKey）（2）候選鍵（candidateKey）（3）主鍵(primaryKey)在圖2.1中，（工號，姓名）是模式的一個超鍵，但不是候選鍵，而（工號）是候選鍵。在實際使用中，如果選擇（工號）作為刪除或查找元組的標志，那么稱（工號）是主鍵。（4）外鍵（foreignKey）返回第十頁，共六十三頁，2022年，8月28日關系的定義和性質

定義2.2關系是一個屬性數目相同的元組的集合。

在關系模型中，對關系作了下列規范性限制：（1）關系中每一個屬性值都是不可分解的；（2）關系中不允許出現重復元組（即不允許出現相同的元組）；（3）由于關系是一個集合，因此不考慮元組間的順序，即沒有行序；（4）元組中的屬性在理論上也是無序的，但使用時按習慣考慮列的順序。返回第十一頁，共六十三頁，2022年，8月28日關系模型的三類完整性規則(1)

實體完整性規則（entityintegrityrule）要求關系中元組在組成主鍵的屬性上不能有空值。如果出現空值，那么主鍵值就起不了惟一標織元組的作用。第十二頁，共六十三頁，2022年，8月28日關系模型的三類完整性規則

(2)參照完整性規則（referenceintegrityrule）定義2.3參照完整性規則的形式定義如下：如果屬性集K是關系模式R1的主鍵，K也是關系模式R2的外鍵，那么在R2的關系中，K的取值只允許兩種可能，或者為空值，或者等于R1關系中某個主鍵值。這條規則的實質是“不允許引用不存在的實體”。在上述形式定義中，關系模式R1的關系稱為“參照關系”，關系模式R2的關系稱為“依賴關系”。“主表”和“副表”，“父表”和“子表”。

第十三頁，共六十三頁，2022年，8月28日關系模型的三類完整性規則

(3)例2.1下面各種情況說明了參照完整性規則在關系中如何實現的。①在關系數據庫中有下列兩個關系模式：

S（S#，SNAME，AGE，SEX）

SC（S#，C#，GRADE）這里帶下劃線者為主鍵，帶波浪線者為外鍵。據規則要求關系SC中的S#值應該在關系S中出現。如果關系SC中有一個元組（S7,C4,80），而學號S7卻在關系S中找不到，那么我們就認為在關系SC中引用了一個不存在的學生實體，這就違反了參照完整性規則。另外，在關系SC中S#不僅是外鍵，也是主鍵的一部分，因此這里S#值不允許空。第十四頁，共六十三頁，2022年，8月28日關系模型的三類完整性規則

(4)②設工廠數據庫中有兩個關系模式：

DEPT(D#，DNAME) EMP(E#，ENAME，SALARY，D#)

車間模式DEPT的屬性為車間編號、車間名，職工模式EMP的屬性為工號、姓名、工資、所在車間的編號。每個模式的主鍵與外鍵已標出。在EMP中，由于D#不在主鍵中，因此D#值允許空。第十五頁，共六十三頁，2022年，8月28日關系模型的三類完整性規則

(5)③設課程之間有先修、后繼聯系。模式如下：

R(C#

，CNAME，PC#)

其屬性表示課程號、課程名、先修課的課程號。如果規定，每門課程的直接先修課只有一門，那么模式R的主鍵是C#，外鍵是PC#.。這里參照完整性在一個模式中實現。即每門課程的直接先修課必須在關系中出現。

第十六頁，共六十三頁，2022年，8月28日關系模型的三類完整性規則

(6)用戶定義的完整性規則

在建立關系模式時，對屬性定義了數據類型，即使這樣可能還滿足不了用戶的需求。此時，用戶可以針對具體的數據約束，設置完整性規則，由系統來檢驗實施，以使用統一的方法處理它們，不再由應用程序承擔這項工作。例如學生的年齡定義為兩位整數，范圍還太大，我們可以寫如下規則把年齡限制在15～30歲之間：

CHECK（AGEBETWEEN15AND30）

返回第十七頁，共六十三頁，2022年，8月28日ER模型向關系模型的轉換規則

(1)ER模型向關系模型的轉換，實際上就是把ER圖轉換成關系模式的集合。規則2.1（實體類型的轉換）：將每個實體類型轉換成一個關系模式，實體的屬性即為關系模式的屬性，實體標識符即為關系模式的鍵。規則2.2（二元聯系類型的轉換）①若實體間聯系是1:1。②若實體間聯系是1:N。③若實體間聯系是M:N。第十八頁，共六十三頁，2022年，8月28日ER模型向關系模型的轉換規則

(2)校名地址校長任職學校電話任職年月姓名性別年齡11職稱圖2.3一對一聯系

第十九頁，共六十三頁，2022年，8月28日ER模型向關系模型的轉換規則

(3)系號系名教師聘用系電話聘期工號姓名性別年齡1N圖2.4一對多聯系

第二十頁，共六十三頁，2022年，8月28日ER模型向關系模型的轉換規則

(4)學號姓名課程學生年齡成績課程號課程名教師名選課性別MN圖2.5多對多聯系

返回第二十一頁，共六十三頁，2022年，8月28日關系模型的三級體系結構

--關系模式

在關系模型中，記錄類型稱為關系模式，而關系模式的集合就是數據庫的概念模式。在系統實現時，關系模式和屬性的命名一般都用英文單詞。譬如圖2.5的ER圖轉換成的關系模式集可用圖2.6表示。而圖2.7是這個關系模型的三個具體關系。

第二十二頁，共六十三頁，2022年，8月28日關系模型的三級體系結構

--子模式

子模式是用戶所用到的那部分數據的描述。除此之外，還應指出數據與關系模式中相應數據的聯系。例如，用戶需要用到子模式G（圖2.8）。第二十三頁，共六十三頁，2022年，8月28日關系模型的三級體系結構

--存儲模式

圖2.10關系S和SC的環結構

在有些DBMS中，關系存儲是作為文件看待的，每個元組就是一個記錄。由于關系模式有鍵，因此存儲一個關系可用散列方法或索引方法實現。如果關系的元組數目較少（100個以內），那么也可以用“堆文件”方式實現（即沒有特定的次序）。此外，還可對任意的屬性集建立輔助索引。

第二十四頁，共六十三頁，2022年，8月28日關系模型的形式定義關系模型有三個重要組成部分：數據結構，數據操縱，數據完整性規則。（1）數據結構：數據庫中全部數據及其相互聯系都被組織成“關系”（二維表格）的形式。關系模型基本的數據結構是關系。（2）數據操縱：關系模型提供一組完備的高級關系運算，以支持對數據庫的各種操作。關系運算分成關系代數、關系演算和關系邏輯等三類。（3）數據完整性規則：數據庫中數據必須滿足實體完整性，參照完整性和用戶定義的完整性等三類完整性規則。

第二十五頁，共六十三頁，2022年，8月28日關系模型的優點與其它數據模型相比，關系模型突出的優點如下：（1）關系模型提供單一的數據結構形式，具有高度的簡明性和精確性。（2）關系模型的邏輯結構和相應的操作完全獨立于數據存儲方式，具有高度的數據獨立性。（3）關系模型使數據庫的研究建立在比較堅實的數學基礎上。（4）關系數據庫語言與一階謂詞邏輯的固有內在聯系，為以關系數據庫為基礎的推理系統和知識庫系統的研究提供了方便。

返回第二十六頁，共六十三頁，2022年，8月28日關系查詢語言和關系運算

關系數據庫的數據操縱語言（DML）的語句分成查詢語句和更新語句兩大類。查詢語句用于描述用戶的各種檢索要求；更新語句用于描述用戶進行插入、刪除、修改等操作。關于查詢的理論稱為“關系運算理論”。關系查詢語言根據其理論基礎的不同分成三類：（1）關系代數語言。（2）關系演算語言。（3）關系邏輯語言。

返回第二十七頁，共六十三頁，2022年，8月28日2.2關系代數

2.2.1關系代數的五個基本操作

2.2.2關系代數的四個組合操作

2.2.3關系代數運算的應用實例

2.2.4關系代數的七個擴充操作

返回第二十八頁，共六十三頁，2022年，8月28日關系代數的五個基本操作

(1)并（Union）設關系R和S具有相同的關系模式，R和S的并是由屬于R或屬于S的元組構成的集合，記為R∪S。形式定義如下：R∪S≡{t|t∈R∨t∈S}，t是元組變量，R和S的元數相同。差（Difference）設關系R和S具有相同的關系模式，R和S的差是由屬于R但不屬于S的元組構成的集合，記為R－S。形式定義如下：R－S≡{t|t∈R∧t∈S}，R和S的元數相同。第二十九頁，共六十三頁，2022年，8月28日關系代數的五個基本操作

(2)投影（Projection）這個操作是對一個關系進行垂直分割，消去某些列，并重新安排列的順序。設關系R是k元關系，R在其分量Ai1，…，Aim（m≤k，i1，…，im為1到k間的整數）上的投影用πi1，…，im（R）表示，它是一個m元元組集合，形式定義如下：πi1，…，im（R）≡{t|t＝〈ti1，…，tim〉∧〈t1，…，tk〉∈R}

例如，π3，1（R）表示關系R中取第1、3列，組成新的關系，新關系中第1列為R的第3列，新關系的第2列為R的第1列。如果R的每列標上屬性名，那么操作符π的下標處也可以用屬性名表示。例如，關系R（A，B，C），那么πC，A（R）與π3，1（R）是等價的。第三十頁，共六十三頁，2022年，8月28日關系代數的五個基本操作

(3)選擇（Selection）選擇操作是根據某些條件對關系做水平分割，即選取符合條件的元組。條件可用命題公式（即計算機語言中的條件表達式）F表示。F中有兩種成分：關系R關于公式F的選擇操作用σF（R）表示，形式定義如下：σF（R）＝{t|t∈R∧F（t）=true}σ為選擇運算符，σF（R）表示從R中挑選滿足公式F為真的元組所構成的關系。例如，σ2＞ˊ3ˊ（R）表示從R中挑選第2個分量值大于3的元組所構成的關系。書寫時，為了與屬性序號區別起見，常量用引號括起來，而屬性序號或屬性名不要用引號括起來。第三十一頁，共六十三頁，2022年，8月28日關系代數的五個基本操作

(例)例2.3圖2.12有兩個關系R和S，圖2.13的（a）、（b）表示R∪S和R－S。（c）表示R×S，此處R和S的屬性名相同，就應在屬性名前注上相應的關系名，例如R.A、S.A等。圖2.13的（d）表示πC，A（R），即π3，1（R）。（e）表示σB=ˊbˊ（R）。（a）關系R（b）關系S

圖2.12兩個關系

第三十二頁，共六十三頁，2022年，8月28日關系代數的五個基本操作

(例)（a）R∪S （b）R－S （c）R×S （d）πC，A（R）（e）σB='b'（R）圖2.13關系代數操作的結果

返回第三十三頁，共六十三頁，2022年，8月28日關系代數的四個組合操作

(1)交（intersection）關系R和S的交是由屬于R又屬于S的元組構成的集合，記為R∩S，這里要求R和S定義在相同的關系模式上。形式定義如下：R∩S≡{t︱t∈R∧t∈S}，R和S的元數相同。由于R∩S=R-（R-S），或R∩S=S-（S-R），因此交操作不是一個獨立的操作。在圖2.12中，R∩S的結果是只有一個元組（d，a，f）。第三十四頁，共六十三頁，2022年，8月28日關系代數的四個組合操作

(2)聯接（join）聯接有兩種：θ聯接和F聯接（這里θ是算術比較符，F是公式）。①θ聯接

R?S≡{t︱t=<tr，ts>∧tr∈R∧ts∈S∧triθtsj}

②F聯接

F聯接是從關系R和S的笛卡爾積中選取屬性間滿足某一公式F的元組,這里F是形為F1∧F2∧…∧Fn的公式，每個FP是形為iθj的式子，而i和j分別為關系R和S的第i、第j個分量的序號。

第三十五頁，共六十三頁，2022年，8月28日關系代數的四個組合操作

(3)自然聯接（naturaljoin）兩個關系R和S的自然聯接操作具體計算過程如下：①計算R×S；②設R和S的公共屬性是A1,…,AK，挑選R×S中滿足R.A1=S.A1，…，R.AK=S.AK

的那些元組；③去掉S.A1，…，S.AK這些列。定義：

πi1,…,im(σR.A1=S.A1∧...∧R.AK=S.AK(R×S)),其中i1,…,im為R和S的全部屬性，但公共屬性只出現一次。

第三十六頁，共六十三頁，2022年，8月28日關系代數的四個組合操作

(4)除法（division）設關系R和S的元數分別為r和s（設r>s>0），那么R÷S是一個（r-s）元的元組的集合。（R÷S）是滿足下列條件的最大關系：其中每個元組t與S中每個元組u組成的新元組<t，u>必在關系R中。R÷S≡π1，2，…，r-s（R）-π1，2，…，r-s（（π1，2，…，r-s（R）×S）-R）

返回第三十七頁，共六十三頁，2022年，8月28日關系代數運算的應用實例

在關系代數運算中，把由五個基本操作經過有限次復合的式子稱為關系代數表達式。這種表達式的運算結果仍是一個關系。我們可以用關系代數表達式表示各種數據查詢操作。例2.7

返回第三十八頁，共六十三頁，2022年，8月28日關系代數的七個擴充操作

改名

廣義投影

賦值

外聯接（outerjoin）

外部并（outerunion）

半聯接（semijoin）

聚集操作

返回第三十九頁，共六十三頁，2022年，8月28日2.3關系演算

把數理邏輯的謂詞演算引入到關系運算中，就可得到以關系演算為基礎的運算。關系演算又可分為元組關系演算和域關系演算，前者以元組為變量，后者以屬性（域）為變量。2.3.1元組關系演算

2.3.2域關系演算

2.3.3關系運算的安全約束和等價性

返回第四十頁，共六十三頁，2022年，8月28日元組關系演算

(1)在元組關系演算（TupleRelationalCalculus）中，元組關系演算表達式簡稱為元組表達式，其一般形式為

{t|P（t）}

其中，t是元組變量，表示一個元數固定的元組；P是公式，在數理邏輯中也稱為謂詞，也就是計算機語言中的條件表達式。{t|P（t）}表示滿足公式P的所有元組t的集合。

第四十一頁，共六十三頁，2022年，8月28日元組關系演算

(2)在元組表達式中，公式由原子公式組成。定義2.4原子公式（Atoms）有下列三種形式：①R（s）

②s[i]θu[j]

③s[i]θa或aθu[j]。

在定義關系演算操作時，要用到“自由”（Free）和“約束”（Bound）變量概念。在一個公式中，如果元組變量未用存在量詞?或全稱量詞符號定義，那么稱為自由元組變量，否則稱為約束元組變量。

第四十二頁，共六十三頁，2022年，8月28日元組關系演算

(3)定義2.5公式（Formulas）的遞歸定義如下：①每個原子是一個公式。其中的元組變量是自由變量。②如果P1和P2是公式，那么┐P1、P1∨P2、P1∧P2和P1P2也都是公式。

③如果P1是公式，那么（s）（P1）和（s）（P1）也都是公式。

④公式中各種運算符的優先級從高到低依次為：θ，和，┐，∧和∨，。在公式外還可以加括號，以改變上述優先順序。

⑤公式只能由上述四種形式構成，除此之外構成的都不是公式。

第四十三頁，共六十三頁，2022年，8月28日元組關系演算

(4)例2.16

圖2.20的（a）、（b）是關系R和S，（c）～（g）分別是下面五個元組表達式的值

圖2.20元組關系演算的例子

R1={t|S（t）∧t[1]>2}R2={t|R（t）∧┐S（t）}R3={t|（u）（S（t）∧R（u）∧t[3]<u[2]}}R4={t|（u）（R（t）∧S（u）∧t[3]>u[1]）}R5={t|（u）（v）（R（u）∧S（v）∧u[1]>v[2]∧t[1]=u[2]∧t[2]=v[3]∧t[3]=u[1]）}

第四十四頁，共六十三頁，2022年，8月28日元組關系演算

(5)在元組關系演算的公式中，有下列三個等價的轉換規則：①P1∧P2等價于┐(┐P1∨┐P2)；

P1∨P2等價于┐（┐P1∧┐P2）。② （s）（P1（s））等價于┐(s)（┐P1（s））；（s）（P1（s））等價于┐(s）（┐P1（s））。③ P1P2等價于┐P1∨P2。第四十五頁，共六十三頁，2022年，8月28日元組關系演算

(6)關系代數表達式到元組表達式的轉換例2.17

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[2]=u[2]∧t[3]=u[3]∧t[4]=v[1]∧t[5]=v[2]∧t[6]=v[3]）}表示。設投影操作是π2,3（R），那么元組表達式可寫成：{t|(u)（R（u）∧t[l]=u[2]∧t[2]=u[3]）}σF（R）可用{t|R(t)∧F'}表示，F'是F的等價表示形式。譬如σ2='d'（R）可寫成{t|（R（t）∧t[2]='d'）。

返回第四十六頁，共六十三頁，2022年，8月28日域關系演算

(1)原子公式有兩種形式：⑴R（x1…xk）；⑵xθy。公式中也可使用∧、∨、┐和等邏輯運算符,(x)和（x），但變量x是域變量，不是元組變量。自由域變量、約束域變量等概念和元組演算中一樣。域演算表達式是形為｛t1…tk∣P（t1，…，tk）｝的表達式，其中P（t1，…，tk）是關于自由域變量t1，…，tk的公式。第四十七頁，共六十三頁，2022年，8月28日域關系演算

(2)例2.20圖2.21的（a）、（b）、（c）是三個關系R、S、W，（d）、（e）、（f）分別表示下面三個域表達式的值。（a）關系R （b）關系S （c）關系W （d）R1 （e）R2 （f）R3

圖2.21域關系演算的例子

R1={xyz|R（xyz）∧x<5∧y>3}R2={xyz|R（xyz）∨（S（xyz）∧y=4）}R3={xyz|（u）（v）（R（zxu）∧w（yv）∧u>v）}第四十八頁，共六十三頁，2022年，8月28日域關系演算

(3)元組表達式到域表達式的轉換我們可以很容易地把元組表達式轉換成域表達式，轉換規則如下：⑴對于k元的元組變量t，可引入k個域變量t1…tk，在公式中t用t1…tk替換，元組分量t[i]用ti替換。⑵

對于每個量詞（u）或（u），若u是m元的元組變量，則引入m個新的域變量u1…um。在量詞的轄域內，u用u1…um替換，u[i]用ui替換，（u）用（u1）…（um）替換，（u）用（u1）…（um）替換。

返回第四十九頁，共六十三頁，2022年，8月28日關系運算的安全約束和等價性

定義2.6在數據庫技術中，不產生無限關系和無窮驗證的運算稱為安全運算，相應的表達式稱為安全表達式，所采取的措施稱為安全約束。并、差、笛爾卡積、投影和選擇是關系代數最基本的操作，并構成了關系代數運算的最小完備集。已經證明，在這個基礎上，關系代數、安全的元組關系演算、安全的域關系演算在關系的表達和操作能力上是完全等價的。

返回第五十頁，共六十三頁，2022年，8月28日2.4關系代數表達式的優化

2.4.1關系代數表達式的優化問題

2.4.2關系代數表達式的等價變換規則

2.4.3關系代數表達式的優化算法

返回第五十一頁，共六十三頁，2022年，8月28日關系代數表達式的優化(1)在關系代數表達式中需要指出若干關系的操作步驟。那么，系統應該以什么樣的操作順序，才能做到既省時間，又省空間，而且效率也比較高呢？這個問題稱為查詢優化問題。在關系代數運算中，笛卡兒積和聯接運算是最費時間的。第五十二頁，共六十三頁，2022年，8月28日關系代數表達式的優化(2)例2.23設關系R和S都是二元關系，屬性名分別為A，B和C，D。設有一個查詢可用關系代數表達式表示：

E1=πA（σB=C∧D='99'（R×S））也可以把選擇條件D=‘99’移到笛卡兒積中的關系S前面：

E2=πA（σB=C（R×σD='99'（S））還可以把選擇條件B＝C與笛卡兒積結合成等值聯接形式：

B=CE3=πA（RσD='99'（S））這三個關系代數表達式是等價的，但執行的效率大不一樣。顯然，求El，E2，E3的大部分時間是花在聯接操作上的。

返回第五十三頁，共六十三頁，2022年，8月28日關系代數表達式的等價變換規則

(1)聯接和笛卡爾積的交換律

聯接和笛卡爾積的結合律

投影的級聯

選擇的級聯

選擇和投影操作的交換

選擇對笛卡爾積的分配律

選擇對并的分配律

第五十四頁，共六十三頁，2022年，8月28日關系代數表達式的等價變換規則

(2)選擇對集合差的分配律

選擇對自然聯接的分配律

投影對笛卡爾積的分配律

投影對并的分配律

選擇與聯接操作的結合

并和交的交換律

并和交的結合律

返回第五十五頁，共六十三頁，2022年，8月28日關系代數表達式的優化算法

(1)在關系代數表達式中，最花費時間和空間的運算是笛卡爾積和聯接操作，為此，引出三條啟發式規則，用于對表達式進行轉換，以減少中間關系的大小。·盡可能早地執行選擇操作；·盡可能早地執行投影操作；