第2章關(guān)系模型和關(guān)系運算理論

本章重要概念（一）

（1）基本概念 關(guān)系模型，關(guān)鍵碼（主鍵和外鍵），關(guān)系的定義和性質(zhì)，三類完整性規(guī)則，ER模型到關(guān)系模型的轉(zhuǎn)換規(guī)則，過程性語言與非過程性語言。（2）關(guān)系代數(shù) 五個基本操作，四個組合操作，七個擴充操作。

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

本章概要本章先介紹關(guān)系模型的基本概念；然后介紹關(guān)系運算的三種理論：關(guān)系代數(shù)、關(guān)系演算和關(guān)系邏輯。

關(guān)系模型和關(guān)系運算理2.1關(guān)系模型的基本概念2.2關(guān)系代數(shù)2.3關(guān)系演算2.4關(guān)系代數(shù)表達式的優(yōu)化2.5關(guān)系邏輯

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)系模型的三級體系結(jié)構(gòu)

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

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

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

圖2.1職工登記表

基本術(shù)語(2)

在關(guān)系模型中，字段稱為屬性，字段值稱為屬性值，記錄類型稱為關(guān)系模式。在圖2.2中，關(guān)系模式名是R。記錄稱為元組（tuple），元組的集合稱為關(guān)系（relation）或?qū)嵗╥nstance）。一般用大寫字母A、B、C、…表示單個屬性，用大寫字母…、X、Y、Z表示屬性集，用小寫字母表示屬性值，有時也習慣稱呼關(guān)系為表或表格，元組為行(row)，屬性為列(column)。關(guān)系中屬性個數(shù)稱為“元數(shù)”（arity），元組個數(shù)為“基數(shù)”(cardinality)。

基本術(shù)語(3)關(guān)系元數(shù)為5，基數(shù)為4

圖2.2關(guān)系模型的術(shù)語

一般術(shù)語

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

關(guān)鍵碼(key,簡稱鍵)由一個或多個屬性組成。在實際使用中，有下列幾種鍵。（1）超建（superKey）:唯一標識元組的屬性集（2）候選鍵（candidateKey）（3）主鍵(primaryKey)在圖2.1中，（工號，姓名）是模式的一個超鍵，但不是候選鍵，而（工號）是候選鍵。在實際使用中，如果選擇（工號）作為刪除或查找元組的標志，那么稱（工號）是主鍵。（4）外鍵（foreignKey）

S(S#,SNAME,AGE)SC(S#,C#,GRADE)返回關(guān)系的定義和性質(zhì)

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

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

實體完整性規(guī)則（entityintegrityrule）要求關(guān)系中元組在組成主鍵的屬性上不能有空值。如果出現(xiàn)空值，那么主鍵值就起不了惟一標織元組的作用。關(guān)系模型的三類完整性規(guī)則

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

關(guān)系模型的三類完整性規(guī)則

(3)例2.1下面各種情況說明了參照完整性規(guī)則在關(guān)系中如何實現(xiàn)的。①在關(guān)系數(shù)據(jù)庫中有下列兩個關(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中有一個元組（S7,C4,80），而學號S7卻在關(guān)系S中找不到，那么我們就認為在關(guān)系SC中引用了一個不存在的學生實體，這就違反了參照完整性規(guī)則。另外，在關(guān)系SC中S#不僅是外鍵，也是主鍵的一部分，因此這里S#值不允許空。關(guān)系模型的三類完整性規(guī)則

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

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

車間模式DEPT的屬性為車間編號、車間名，職工模式EMP的屬性為工號、姓名、工資、所在車間的編號。每個模式的主鍵與外鍵已標出。在EMP中，由于D#不在主鍵中，因此D#值允許空。關(guān)系模型的三類完整性規(guī)則

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

R(C#

，CNAME，PC#)

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

關(guān)系模型的三類完整性規(guī)則

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

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

CHECK（AGEBETWEEN15AND30）

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

(1)ER模型向關(guān)系模型的轉(zhuǎn)換，實際上就是把ER圖轉(zhuǎn)換成關(guān)系模式的集合。規(guī)則2.1（實體類型的轉(zhuǎn)換）：將每個實體類型轉(zhuǎn)換成一個關(guān)系模式，實體的屬性即為關(guān)系模式的屬性，實體標識符即為關(guān)系模式的鍵。規(guī)則2.2（二元聯(lián)系類型的轉(zhuǎn)換）①若實體間聯(lián)系是1:1。②若實體間聯(lián)系是1:N。③若實體間聯(lián)系是M:N。ER模型向關(guān)系模型的轉(zhuǎn)換規(guī)則

(2)圖2.3一對一聯(lián)系

學校（校名，地址，電話，校長名，任職年月）校長（姓名，性別，年齡，職稱）ER模型向關(guān)系模型的轉(zhuǎn)換規(guī)則

(3)圖2.4一對多聯(lián)系

系（系號，系名，電話）教師（工號，姓名，性別，年齡，系號，聘期）ER模型向關(guān)系模型的轉(zhuǎn)換規(guī)則

(4)圖2.5多對多聯(lián)系

返回學生（學號，姓名，年齡，性別）選課（學號，課程號，成績）課程（課程號，課程名，教師名）關(guān)系模型的三級體系結(jié)構(gòu)

--關(guān)系模式

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

學生關(guān)系模式S(S#，SNAME，AGE，SEX)

選課關(guān)系模式SC(S#，C#，GRADE)

課程關(guān)系模式C(C#，CNAME，TEACHER)圖2.6關(guān)系模式集關(guān)系模型的三級體系結(jié)構(gòu)

--子模式

子模式是用戶所用到的那部分數(shù)據(jù)的描述。除此之外，還應(yīng)指出數(shù)據(jù)與關(guān)系模式中相應(yīng)數(shù)據(jù)的聯(lián)系。例如，用戶需要用到子模式G（圖2.8）。成績子模式G(S#，SNAME，C#，GRADE)

圖2.8子模式關(guān)系模型的三級體系結(jié)構(gòu)

--存儲模式

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

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

關(guān)系模型的形式定義關(guān)系模型有三個重要組成部分：數(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)系模型提供一組完備的高級關(guān)系運算，以支持對數(shù)據(jù)庫的各種操作。關(guān)系運算分成關(guān)系代數(shù)、關(guān)系演算和關(guān)系邏輯等三類。（3）數(shù)據(jù)完整性規(guī)則：數(shù)據(jù)庫中數(shù)據(jù)必須滿足實體完整性，參照完整性和用戶定義的完整性等三類完整性規(guī)則。

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

返回關(guān)系查詢語言和關(guān)系運算

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

返回2.2關(guān)系代數(shù)

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

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

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

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

返回關(guān)系代數(shù)的五個基本操作

(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ù)相同。關(guān)系代數(shù)的五個基本操作

(2)投影（Projection）這個操作是對一個關(guān)系進行垂直分割，消去某些列，并重新安排列的順序。設(shè)關(guān)系R是k元關(guān)系，R在其分量Ai1，…，Aim（m≤k，i1，…，im為1到k間的整數(shù)）上的投影用πi1，…，im（R）表示，它是一個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的每列標上屬性名，那么操作符π的下標處也可以用屬性名表示。例如，關(guān)系R（A，B，C），那么πC，A（R）與π3，1（R）是等價的。關(guān)系代數(shù)的五個基本操作

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

迪卡爾積（a）關(guān)系R

（b）關(guān)系S

圖2.12兩個關(guān)系

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

(例)例2.3圖2.12有兩個關(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）。關(guān)系代數(shù)的五個基本操作

(例)（a）R∪S （b）R－S （c）R×S （d）πC，A（R）（e）σB='b'（R）

圖2.13關(guān)系代數(shù)操作的結(jié)果

返回關(guān)系代數(shù)的四個組合操作

(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），因此交操作不是一個獨立的操作。在圖2.12中，R∩S的結(jié)果是只有一個元組（d，a，f）。關(guān)系代數(shù)的四個組合操作

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

R?S≡{t︱t=<tr，ts>∧tr∈R∧ts∈S∧tr

iθtsj}②F連接

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

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

(3)自然連接（naturaljoin）兩個關(guān)系R和S的自然連接操作具體計算過程如下：①計算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)一次。

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

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

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

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

改名廣義投影賦值外連接（outerjoin）外部并（outerunion）半連接（semijoin）聚集操作返回2.3關(guān)系演算

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

2.3.2域關(guān)系演算

2.3.3關(guān)系運算的安全約束和等價性返回元組關(guān)系演算

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

{t|P（t）}

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

元組關(guān)系演算

(2)在元組表達式中，公式由原子公式組成。定義2.4原子公式（Atoms）有下列三種形式：①R（s）②s[i]θu[j]③s[i]θa或aθu[j]。在定義關(guān)系演算操作時，要用到“自由”（Free）和“約束”（Bound）變量概念。在一個公式中，如果元組變量未用存在量詞?或全稱量詞符號定義，那么稱為自由元組變量，否則稱為約束元組變量。

元組關(guān)系演算

(3)定義2.5公式（Formulas）的遞歸定義如下：①每個原子是一個公式。其中的元組變量是自由變量。②如果P1和P2是公式，那么┐P1、P1∨P2、P1∧P2和P1P2也都是公式。③如果P1是公式，那么（s）（P1）和（s）（P1）也都是公式。④公式中各種運算符的優(yōu)先級從高到低依次為：θ，和，┐，∧和∨，。在公式外還可以加括號，以改變上述優(yōu)先順序。⑤公式只能由上述四種形式構(gòu)成，除此之外構(gòu)成的都不是公式。元組關(guān)系演算

(4)例2.16

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

圖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]）}

元組關(guān)系演算

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

P1∨P2等價于┐（┐P1∧┐P2）。②（s）（P1（s））等價于┐(s)（┐P1（s））；（s）（P1（s））等價于┐(s）（┐P1（s））。③P1P2等價于┐P1∨P2。元組關(guān)系演算

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

返回元組關(guān)系演算

(7)域關(guān)系演算

(1)原子公式有兩種形式：⑴

R（x1…xk）；⑵xθy。公式中也可使用∧、∨、┐和等邏輯運算符,(x)和（x），但變量x是域變量，不是元組變量。自由域變量、約束域變量等概念和元組演算中一樣。域演算表達式是形為｛t1…tk∣P（t1，…，tk）｝的表達式，其中P（t1，…，tk）是關(guān)于自由域變量t1，…，tk

的公式。域關(guān)系演算

(2)例2.20圖2.21的（a）、（b）、（c）是三個關(guān)系R、S、W，（d）、（e）、（f）分別表示下面三個域表達式的值。（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）}域關(guān)系演算

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

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

返回關(guān)系運算的安全約束和等價性

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

返回2.4關(guān)系代數(shù)表達式的優(yōu)化

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

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

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

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

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

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

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

返回關(guān)系代數(shù)表達式的等價變換規(guī)則

(1)連接和笛卡兒積的交換律

連接和笛卡兒積的結(jié)合律

投影的級聯(lián)

選擇的級聯(lián)

選擇和投影操作的交換

選擇對笛卡兒積的分配律

選擇對并的分配律

圖2.6關(guān)系模式集關(guān)系代數(shù)表達式的等價變換規(guī)則

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

選擇對自然連接的分配律

投影對笛卡兒積的分配律

投影對并的分配律

選擇與連接操作的結(jié)合

并和交的交換律

并和交的結(jié)合律

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

(1)在關(guān)系代數(shù)表達式中，最花費時間和空間的運算是笛卡兒積和連接操作，為此，引出三條啟發(fā)式規(guī)則，用于對表達式進行轉(zhuǎn)換，以減少中間關(guān)系的大小。

·盡可能早地執(zhí)行選擇操作；

·盡可能早地執(zhí)行投影操作；

·避免直接做笛卡兒積，把笛卡兒積操作之前和之后的一連串選擇和投影合并起來一起做。

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

(2)算法2.1 關(guān)系代數(shù)表達式的啟發(fā)式優(yōu)化算法。輸入：一個關(guān)系代數(shù)表達式的語法樹輸出：計算表達式的一個優(yōu)化序列例2.24

對于如下關(guān)系數(shù)據(jù)庫

S(S#,SNAME,AGE,SEX)SC(S#,C#,GRADE)C(C#,CNAME,TEACHER)

檢索至少學習LIU老師所授一門課程的女學生的學號和姓名返回2.5關(guān)系邏輯

2.5.1關(guān)系運算的成分

2.5.2規(guī)則的安全性

2.5.3從關(guān)系代數(shù)到關(guān)系邏輯的轉(zhuǎn)換

2.5.4遞歸過程

2.5.5關(guān)系邏輯與關(guān)系代數(shù)的差異

關(guān)系邏輯關(guān)系邏輯的成分謂詞（Predicates）表示關(guān)系模式，如P(x,y,z)外延謂詞（ExtensionalPredicate）,其關(guān)系存貯在數(shù)據(jù)庫中；EDB指代外延數(shù)據(jù)庫內(nèi)涵謂詞（IntensionalPredicate）,僅由邏輯規(guī)則定義；IDB指代內(nèi)涵數(shù)據(jù)庫關(guān)系邏輯關(guān)系邏輯的成分原子（Atoms）關(guān)系原子，是一個謂詞符號，帶一個參數(shù)表，每個參數(shù)可以是變量或常量算術(shù)原子，是一個算術(shù)比較表達式

假如關(guān)系R(A,B,C)，則R(‘2345’,b,c)和R(x,b,x)均是關(guān)系原子；

x<y是一個算術(shù)原子關(guān)系邏輯關(guān)系邏輯的成分規(guī)則（Rules）規(guī)則是形為W<-P1∧P2∧…∧Pn的式子頭部符號<-包括一個或多個原子的體例2.25設(shè)關(guān)系S(S#,SNAME,AGE,SEX),一個規(guī)則

W(a,b)<-S(a,b,c,’M’)∧c>20

關(guān)系邏輯關(guān)系邏輯的成分查詢（Queries）是一個或多個規(guī)則的聚集，規(guī)則之間的順序無關(guān)緊要

2.5關(guān)系邏輯

規(guī)則的安全性得到的頭部關(guān)系必須是有限的，因此，頭部的變量必須在體部收到約束關(guān)系體部由原子構(gòu)成，原子有四種形式，關(guān)系原子，求反關(guān)系原子，算術(shù)原子和求反算術(shù)原子。后三種形式的取值必須限制在一定的范圍之內(nèi)規(guī)則安全的條件在頭部、求反關(guān)系原子和任何算術(shù)原子中出現(xiàn)的變量，必須出現(xiàn)在非求反的關(guān)系原子中例2.5關(guān)系邏輯

從關(guān)系代數(shù)到關(guān)系邏輯的轉(zhuǎn)換

交W(a,b,c)<-R(a,b,c)∧S(a,b,c)并W(a,b,c)<-R(a,b,c)W(a,b,c)<-S(a,b,c)差2.5關(guān)系邏輯

從關(guān)系代數(shù)到關(guān)系邏輯的轉(zhuǎn)換

投影W(c,a)<-R(a,b,c)選擇W(a,b,c)<-R(a,b,c)∧b>’5’笛卡爾積W(a,b,c,x,y,z)<-R(a,b,c)∧S(x,y,z)自然連接W(a,b,x,y,z)<-R(a,b,x)∧S(x,y,z)2.5關(guān)系邏輯

遞歸過程

COURSE(C#,CNAME,PC#)檢索每一門課程的直接先修課程可用下列關(guān)系代數(shù)表達式表示：

1，3（COURSE）檢索每一門課程先修課的先修課，可用下列關(guān)系代數(shù)表達式表示：

1，6（3＝4（COURSECOURSE））

C＃

CNAME

PC#C1

BASIC

null

C2

FORTRAN

C1

C3

PASCAL

C2

C4

C

C3關(guān)系邏輯關(guān)系邏輯實現(xiàn)遞歸查詢

PRE(x,y)COURSE(x,u,y)PRE(x,y)COURSE(x,u,z)PRE(z,y)

關(guān)系邏輯遞歸查詢實現(xiàn)例子第一，定義COURSE事實模板。(deftemplateCOURSE//定義COURSE模板(slotC#(typeString))(slotCNAM