關(guān)系模型和關(guān)系運(yùn)算理論

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

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

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

第四頁，共六十三頁，2022年，8月28日關(guān)系模型和關(guān)系運(yùn)算理2.1關(guān)系模型的基本概念2.2關(guān)系代數(shù)2.3關(guān)系演算2.4關(guān)系代數(shù)表達(dá)式的優(yōu)化2.5關(guān)系邏輯

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

2.1.1基本術(shù)語

2.1.2關(guān)系的定義和性質(zhì)2.1.3關(guān)系模型的三類完整性規(guī)則

2.1.4ER模型向關(guān)系模型的轉(zhuǎn)換規(guī)則

2.1.5關(guān)系模型的三級(jí)體系結(jié)構(gòu)

2.1.6關(guān)系模型的形式定義和優(yōu)點(diǎn)

2.1.7關(guān)系查詢語言和關(guān)系運(yùn)算

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

圖2.1職工登記表

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

在關(guān)系模型中，字段稱為屬性，字段值稱為屬性值，記錄類型稱為關(guān)系模式。在圖2.2中，關(guān)系模式名是R。記錄稱為元組（tuple），元組的集合稱為關(guān)系（relation）或?qū)嵗╥nstance）。一般用大寫字母A、B、C、…

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

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

一般術(shù)語

關(guān)系模型術(shù)語字段、數(shù)據(jù)項(xiàng) 屬性記錄類型 關(guān)系模式記錄1 元組1記錄2 元組2記錄3 元組3記錄4 元組4字段值 屬性值圖2.2關(guān)系模型的術(shù)語

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

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

定義2.2關(guān)系是一個(gè)屬性數(shù)目相同的元組的集合。

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

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

(2)參照完整性規(guī)則（referenceintegrityrule）定義2.3參照完整性規(guī)則的形式定義如下：如果屬性集K是關(guān)系模式R1的主鍵，K也是關(guān)系模式R2的外鍵，那么在R2的關(guān)系中，K的取值只允許兩種可能，或者為空值，或者等于R1關(guān)系中某個(gè)主鍵值。這條規(guī)則的實(shí)質(zhì)是“不允許引用不存在的實(shí)體”。在上述形式定義中，關(guān)系模式R1的關(guān)系稱為“參照關(guān)系”，關(guān)系模式R2的關(guān)系稱為“依賴關(guān)系”?！爸鞅怼焙汀案北怼保案副怼焙汀白颖怼?。

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

(3)例2.1下面各種情況說明了參照完整性規(guī)則在關(guān)系中如何實(shí)現(xiàn)的。①在關(guān)系數(shù)據(jù)庫中有下列兩個(gè)關(guān)系模式：

S（S#，SNAME，AGE，SEX）

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

(4)②設(shè)工廠數(shù)據(jù)庫中有兩個(gè)關(guān)系模式：

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

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

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

R(C#

，CNAME，PC#)

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

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

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

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

CHECK（AGEBETWEEN15AND30）

返回第十七頁，共六十三頁，2022年，8月28日ER模型向關(guān)系模型的轉(zhuǎn)換規(guī)則

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

(2)校名地址校長(zhǎng)任職學(xué)校電話任職年月姓名性別年齡11職稱圖2.3一對(duì)一聯(lián)系

第十九頁，共六十三頁，2022年，8月28日ER模型向關(guān)系模型的轉(zhuǎn)換規(guī)則

(3)系號(hào)系名教師聘用系電話聘期工號(hào)姓名性別年齡1N圖2.4一對(duì)多聯(lián)系

第二十頁，共六十三頁，2022年，8月28日ER模型向關(guān)系模型的轉(zhuǎn)換規(guī)則

(4)學(xué)號(hào)姓名課程學(xué)生年齡成績(jī)課程號(hào)課程名教師名選課性別MN圖2.5多對(duì)多聯(lián)系

返回第二十一頁，共六十三頁，2022年，8月28日關(guān)系模型的三級(jí)體系結(jié)構(gòu)

--關(guān)系模式

在關(guān)系模型中，記錄類型稱為關(guān)系模式，而關(guān)系模式的集合就是數(shù)據(jù)庫的概念模式。在系統(tǒng)實(shí)現(xiàn)時(shí)，關(guān)系模式和屬性的命名一般都用英文單詞。譬如圖2.5的ER圖轉(zhuǎn)換成的關(guān)系模式集可用圖2.6表示。而圖2.7是這個(gè)關(guān)系模型的三個(gè)具體關(guān)系。

第二十二頁，共六十三頁，2022年，8月28日關(guān)系模型的三級(jí)體系結(jié)構(gòu)

--子模式

子模式是用戶所用到的那部分?jǐn)?shù)據(jù)的描述。除此之外，還應(yīng)指出數(shù)據(jù)與關(guān)系模式中相應(yīng)數(shù)據(jù)的聯(lián)系。例如，用戶需要用到子模式G（圖2.8）。第二十三頁，共六十三頁，2022年，8月28日關(guān)系模型的三級(jí)體系結(jié)構(gòu)

--存儲(chǔ)模式

圖2.10關(guān)系S和SC的環(huán)結(jié)構(gòu)

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

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

第二十五頁，共六十三頁，2022年，8月28日關(guān)系模型的優(yōu)點(diǎn)與其它數(shù)據(jù)模型相比，關(guān)系模型突出的優(yōu)點(diǎn)如下：（1）關(guān)系模型提供單一的數(shù)據(jù)結(jié)構(gòu)形式，具有高度的簡(jiǎn)明性和精確性。（2）關(guān)系模型的邏輯結(jié)構(gòu)和相應(yīng)的操作完全獨(dú)立于數(shù)據(jù)存儲(chǔ)方式，具有高度的數(shù)據(jù)獨(dú)立性。（3）關(guān)系模型使數(shù)據(jù)庫的研究建立在比較堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)上。（4）關(guān)系數(shù)據(jù)庫語言與一階謂詞邏輯的固有內(nèi)在聯(lián)系，為以關(guān)系數(shù)據(jù)庫為基礎(chǔ)的推理系統(tǒng)和知識(shí)庫系統(tǒng)的研究提供了方便。

返回第二十六頁，共六十三頁，2022年，8月28日關(guān)系查詢語言和關(guān)系運(yùn)算

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

返回第二十七頁，共六十三頁，2022年，8月28日2.2關(guān)系代數(shù)

2.2.1關(guān)系代數(shù)的五個(gè)基本操作

2.2.2關(guān)系代數(shù)的四個(gè)組合操作

2.2.3關(guān)系代數(shù)運(yùn)算的應(yīng)用實(shí)例

2.2.4關(guān)系代數(shù)的七個(gè)擴(kuò)充操作

返回第二十八頁，共六十三頁，2022年，8月28日關(guān)系代數(shù)的五個(gè)基本操作

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

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

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

(3)選擇（Selection）選擇操作是根據(jù)某些條件對(duì)關(guān)系做水平分割，即選取符合條件的元組。條件可用命題公式（即計(jì)算機(jī)語言中的條件表達(dá)式）F表示。F中有兩種成分：關(guān)系R關(guān)于公式F的選擇操作用σF（R）表示，形式定義如下：σF（R）＝{t|t∈R∧F（t）=true}σ為選擇運(yùn)算符，σF（R）表示從R中挑選滿足公式F為真的元組所構(gòu)成的關(guān)系。例如，σ2＞ˊ3ˊ（R）表示從R中挑選第2個(gè)分量值大于3的元組所構(gòu)成的關(guān)系。書寫時(shí)，為了與屬性序號(hào)區(qū)別起見，常量用引號(hào)括起來，而屬性序號(hào)或?qū)傩悦灰靡?hào)括起來。第三十一頁，共六十三頁，2022年，8月28日關(guān)系代數(shù)的五個(gè)基本操作

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

圖2.12兩個(gè)關(guān)系

第三十二頁，共六十三頁，2022年，8月28日關(guān)系代數(shù)的五個(gè)基本操作

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

返回第三十三頁，共六十三頁，2022年，8月28日關(guān)系代數(shù)的四個(gè)組合操作

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

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

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

②F聯(lián)接

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

第三十五頁，共六十三頁，2022年，8月28日關(guān)系代數(shù)的四個(gè)組合操作

(3)自然聯(lián)接（naturaljoin）兩個(gè)關(guān)系R和S的自然聯(lián)接操作具體計(jì)算過程如下：①計(jì)算R×S；②設(shè)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的全部屬性，但公共屬性只出現(xiàn)一次。

第三十六頁，共六十三頁，2022年，8月28日關(guān)系代數(shù)的四個(gè)組合操作

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

返回第三十七頁，共六十三頁，2022年，8月28日關(guān)系代數(shù)運(yùn)算的應(yīng)用實(shí)例

在關(guān)系代數(shù)運(yùn)算中，把由五個(gè)基本操作經(jīng)過有限次復(fù)合的式子稱為關(guān)系代數(shù)表達(dá)式。這種表達(dá)式的運(yùn)算結(jié)果仍是一個(gè)關(guān)系。我們可以用關(guān)系代數(shù)表達(dá)式表示各種數(shù)據(jù)查詢操作。例2.7

返回第三十八頁，共六十三頁，2022年，8月28日關(guān)系代數(shù)的七個(gè)擴(kuò)充操作

改名

廣義投影

賦值

外聯(lián)接（outerjoin）

外部并（outerunion）

半聯(lián)接（semijoin）

聚集操作

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

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

2.3.2域關(guān)系演算

2.3.3關(guān)系運(yùn)算的安全約束和等價(jià)性

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

(1)在元組關(guān)系演算（TupleRelationalCalculus）中，元組關(guān)系演算表達(dá)式簡(jiǎn)稱為元組表達(dá)式，其一般形式為

{t|P（t）}

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

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

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

②s[i]θu[j]

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

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

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

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

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

④公式中各種運(yùn)算符的優(yōu)先級(jí)從高到低依次為：θ，和，┐，∧和∨，。在公式外還可以加括號(hào)，以改變上述優(yōu)先順序。

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

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

(4)例2.16

圖2.20的（a）、（b）是關(guān)系R和S，（c）～（g）分別是下面五個(gè)元組表達(dá)式的值

圖2.20元組關(guān)系演算的例子

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日元組關(guān)系演算

(5)在元組關(guān)系演算的公式中，有下列三個(gè)等價(jià)的轉(zhuǎn)換規(guī)則：①P1∧P2等價(jià)于┐(┐P1∨┐P2)；

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

(6)關(guān)系代數(shù)表達(dá)式到元組表達(dá)式的轉(zhuǎn)換例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]）}表示。設(shè)投影操作是π2,3（R），那么元組表達(dá)式可寫成：{t|(u)（R（u）∧t[l]=u[2]∧t[2]=u[3]）}σF（R）可用{t|R(t)∧F'}表示，F(xiàn)'是F的等價(jià)表示形式。譬如σ2='d'（R）可寫成{t|（R（t）∧t[2]='d'）。

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

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

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

圖2.21域關(guān)系演算的例子

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日域關(guān)系演算

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

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

返回第四十九頁，共六十三頁，2022年，8月28日關(guān)系運(yùn)算的安全約束和等價(jià)性

定義2.6在數(shù)據(jù)庫技術(shù)中，不產(chǎn)生無限關(guān)系和無窮驗(yàn)證的運(yùn)算稱為安全運(yùn)算，相應(yīng)的表達(dá)式稱為安全表達(dá)式，所采取的措施稱為安全約束。并、差、笛爾卡積、投影和選擇是關(guān)系代數(shù)最基本的操作，并構(gòu)成了關(guān)系代數(shù)運(yùn)算的最小完備集。已經(jīng)證明，在這個(gè)基礎(chǔ)上，關(guān)系代數(shù)、安全的元組關(guān)系演算、安全的域關(guān)系演算在關(guān)系的表達(dá)和操作能力上是完全等價(jià)的。

返回第五十頁，共六十三頁，2022年，8月28日2.4關(guān)系代數(shù)表達(dá)式的優(yōu)化

2.4.1關(guān)系代數(shù)表達(dá)式的優(yōu)化問題

2.4.2關(guān)系代數(shù)表達(dá)式的等價(jià)變換規(guī)則

2.4.3關(guān)系代數(shù)表達(dá)式的優(yōu)化算法

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

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

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

B=CE3=πA（RσD='99'（S））這三個(gè)關(guān)系代數(shù)表達(dá)式是等價(jià)的，但執(zhí)行的效率大不一樣。顯然，求El，E2，E3的大部分時(shí)間是花在聯(lián)接操作上的。

返回第五十三頁，共六十三頁，2022年，8月28日關(guān)系代數(shù)表達(dá)式的等價(jià)變換規(guī)則

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

聯(lián)接和笛卡爾積的結(jié)合律

投影的級(jí)聯(lián)

選擇的級(jí)聯(lián)

選擇和投影操作的交換

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

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

第五十四頁，共六十三頁，2022年，8月28日關(guān)系代數(shù)表達(dá)式的等價(jià)變換規(guī)則

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

選擇對(duì)自然聯(lián)接的分配律

投影對(duì)笛卡爾積的分配律

投影對(duì)并的分配律

選擇與聯(lián)接操作的結(jié)合

并和交的交換律

并和交的結(jié)合律

返回第五十五頁，共六十三頁，2022年，8月28日關(guān)系代數(shù)表達(dá)式的優(yōu)化算法

(1)在關(guān)系代數(shù)表達(dá)式中，最花費(fèi)時(shí)間和空間的運(yùn)算是笛卡爾積和聯(lián)接操作，為此，引出三條啟發(fā)式規(guī)則，用于對(duì)表達(dá)式進(jìn)行轉(zhuǎn)換，以減少中間關(guān)系的大小?！けM可能早地執(zhí)行選擇操作；·盡可能早地執(zhí)行投影操作；