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

1、第2章 關(guān)系模型和關(guān)系運(yùn)算理論 本章重要概念（一） （1）基本概念關(guān)系模型，關(guān)鍵碼（主鍵和外鍵），關(guān)系的定義和性質(zhì)，三類完整性規(guī)則，ER模型到關(guān)系模型的轉(zhuǎn)換規(guī)則，過(guò)程性語(yǔ)言與非過(guò)程性語(yǔ)言。（2）關(guān)系代數(shù)五個(gè)基本操作，四個(gè)組合操作，七個(gè)擴(kuò)充操作。 本章重要概念（二）（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á)式。 本章概要 l本章先介紹關(guān)系模型的基本概念；然后介紹關(guān)系運(yùn)算的三種理論：關(guān)系代數(shù)、關(guān)系演算和

2、關(guān)系邏輯。 關(guān)系模型和關(guān)系運(yùn)算理 l2.1 關(guān)系模型的基本概念 l2.2 關(guān)系代數(shù) l2.3 關(guān)系演算 l2.4 關(guān)系代數(shù)表達(dá)式的優(yōu)化 l2.5 關(guān)系邏輯 2.1 關(guān)系模型的基本概念 l2.1.1 基本術(shù)語(yǔ) l2.1.2 關(guān)系的定義和性質(zhì)l2.1.3 關(guān)系模型的三類完整性規(guī)則 l2.1.4 ER模型向關(guān)系模型的轉(zhuǎn)換規(guī)則 l2.1.5 關(guān)系模型的三級(jí)體系結(jié)構(gòu) l2.1.6 關(guān)系模型的形式定義和優(yōu)點(diǎn) l2.1.7 關(guān)系查詢語(yǔ)言和關(guān)系運(yùn)算 返回基本術(shù)語(yǔ)(1) l定義2.1 用二維表格表示實(shí)體集，用關(guān)鍵碼進(jìn)行數(shù)據(jù)導(dǎo)航的數(shù)據(jù)模型稱為關(guān)系模型（relational Model）。這里數(shù)據(jù)導(dǎo)航(data n

3、avigation)是指從已知數(shù)據(jù)查找未知數(shù)據(jù)的過(guò)程和方法。 工 號(hào) 姓 名 年 齡 性 別 工 資 4001 zhang 50 M 2000 4002 li 40 F 1500 4124 liu 35 M 2000 5018 wang 25 M 1000 圖2.1 職工登記表 基本術(shù)語(yǔ)(2)l 在關(guān)系模型中，字段稱為屬性，字段值稱為屬性值，記錄類型稱為關(guān)系模式。在圖2.2中，關(guān)系模式名是R。記錄稱為元組（tuple），元組的集合稱為關(guān)系（relation）或?qū)嵗╥nstance）。一般用大寫字母A、B、C、 表示單個(gè)屬性，用大寫字母 、X、Y、Z表示屬性集，用小寫字母表示屬性值，有時(shí)也習(xí)慣

4、稱呼關(guān)系為表或表格，元組為行(row)，屬性為列(column)。l關(guān)系中屬性個(gè)數(shù)稱為“元數(shù)”（arity），元組個(gè)數(shù)為“基數(shù)”(cardinality)。 基本術(shù)語(yǔ)(3)l關(guān)系元數(shù)為5，基數(shù)為4 圖2.2 關(guān)系模型的術(shù)語(yǔ) R R A A B B C C D D E E a a1 1 b b1 1 c c1 1 d d1 1 e e1 1 a a2 2 b b2 2 c c2 2 d d2 2 e e2 2 a a3 3 b b3 3 c c3 3 d d3 3 e e3 3 a a4 4 b b4 4 c c4 4 d d4 4 e e4 4 一般術(shù)語(yǔ) 關(guān)系模型術(shù)語(yǔ)字段、數(shù)據(jù)項(xiàng)屬性記錄類型關(guān)

5、系模式記錄1元組1記錄2元組2記錄3元組3記錄4元組4字段值屬性值基本術(shù)語(yǔ)(4)l 關(guān)鍵碼(key,簡(jiǎn)稱鍵)由一個(gè)或多個(gè)屬性組成。在實(shí)際使用中，有下列幾種鍵。 （1）超建（super Key）:唯一標(biāo)識(shí)元組的屬性集 （2）候選鍵（candidate Key） （3）主鍵(primary Key) 在圖2.1中，（工號(hào)，姓名）是模式的一個(gè)超鍵，但不是候選鍵，而（工號(hào)）是候選鍵。在實(shí)際使用中，如果選擇（工號(hào)）作為刪除或查找元組的標(biāo)志，那么稱（工號(hào)）是主鍵。 （4）外鍵（foreign Key） S(S#,SNAME,AGE) SC(S#,C#,GRADE)返回關(guān)系的定義和性質(zhì) l定義2.2 關(guān)系是

6、一個(gè)屬性數(shù)目相同的元組的集合。 l 在關(guān)系模型中，對(duì)關(guān)系作了下列規(guī)范性限制：（1）關(guān)系中每一個(gè)屬性值都是不可分解的；（2）關(guān)系中不允許出現(xiàn)重復(fù)元組（即不允許出現(xiàn)相同的元組）；（3）由于關(guān)系是一個(gè)集合，因此不考慮元組間的順序，即沒(méi)有行序；（4）元組中的屬性在理論上也是無(wú)序的，但使用時(shí)按習(xí)慣考慮列的順序。返回關(guān)系模型的三類完整性規(guī)則(1) l 實(shí)體完整性規(guī)則（entity integrity rule）要求關(guān)系中元組在組成主鍵的屬性上不能有空值。如果出現(xiàn)空值，那么主鍵值就起不了惟一標(biāo)織元組的作用。關(guān)系模型的三類完整性規(guī)則 (2)l參照完整性規(guī)則（reference integrity rule）l

7、定義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)系”?！爸鞅怼焙汀案北怼?，“父表”和“子表”。 關(guān)系模型的三類完整性規(guī)則 (3)l例2.1 下面各種情況說(shuō)明了參照完整性規(guī)則在關(guān)系中如何實(shí)現(xiàn)的。 在關(guān)系數(shù)據(jù)庫(kù)中有下列兩個(gè)關(guān)系模式：S（S#，SNAME，AGE，SEX）SC（S#，C#，GRADE） 這里帶下劃線者為主鍵，斜體者

8、為外鍵。據(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# 值不允許空。關(guān)系模型的三類完整性規(guī)則 (4) 設(shè)工廠數(shù)據(jù)庫(kù)中有兩個(gè)關(guān)系模式：DEPT(D#，DNAME)EMP(E#，ENAME，SALARY，D# ) 車間模式DEPT的屬性為車間編號(hào)、車間名，職工模式EMP的屬性為工號(hào)、姓名、工資、所在車間的編號(hào)。每個(gè)模式的主鍵與外鍵已標(biāo)出。在EMP中，由于D# 不在主鍵中，因

9、此D# 值允許空。關(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)。 關(guān)系模型的三類完整性規(guī)則 (6)l用戶定義的完整性規(guī)則 在建立關(guān)系模式時(shí)，對(duì)屬性定義了數(shù)據(jù)類型，即使這樣可能還滿足不了用戶的需求。此時(shí)，用戶可以針對(duì)具體的數(shù)據(jù)約束，設(shè)置完整性規(guī)則，由系統(tǒng)來(lái)檢驗(yàn)實(shí)施，以使用統(tǒng)一的方法處理它們，不再由應(yīng)用程序承擔(dān)這項(xiàng)工作。例如學(xué)生的年齡定義為兩位整

10、數(shù)，范圍還太大，我們可以寫如下規(guī)則把年齡限制在1530歲之間：CHECK（AGE BETWEEN 15 AND 30） 返回ER模型向關(guān)系模型的轉(zhuǎn)換規(guī)則 (1)lER模型向關(guān)系模型的轉(zhuǎn)換，實(shí)際上就是把ER圖轉(zhuǎn)換成關(guān)系模式的集合。l規(guī)則2.1（實(shí)體類型的轉(zhuǎn)換）：將每個(gè)實(shí)體類型轉(zhuǎn)換成一個(gè)關(guān)系模式，實(shí)體的屬性即為關(guān)系模式的屬性，實(shí)體標(biāo)識(shí)符即為關(guān)系模式的鍵。l規(guī)則2.2（二元聯(lián)系類型的轉(zhuǎn)換） 若實(shí)體間聯(lián)系是1:1。 若實(shí)體間聯(lián)系是1:N。 若實(shí)體間聯(lián)系是M:N。ER模型向關(guān)系模型的轉(zhuǎn)換規(guī)則 (2)圖2.3 一對(duì)一聯(lián)系 學(xué)校（校名，地址，電話，校長(zhǎng)名，任職年月）校長(zhǎng)（姓名，性別，年齡，職稱）ER模型向關(guān)

11、系模型的轉(zhuǎn)換規(guī)則 (3)圖2.4 一對(duì)多聯(lián)系 系（系號(hào)，系名，電話）教師（工號(hào)，姓名，性別，年齡，系號(hào)，聘期）ER模型向關(guān)系模型的轉(zhuǎn)換規(guī)則 (4)圖2.5 多對(duì)多聯(lián)系 返回學(xué)生（學(xué)號(hào)，姓名，年齡，性別）選課（學(xué)號(hào)，課程號(hào)，成績(jī)）課程（課程號(hào)，課程名，教師名）關(guān)系模型的三級(jí)體系結(jié)構(gòu) - 關(guān)系模式 l在關(guān)系模型中，記錄類型稱為關(guān)系模式，而關(guān)系模式的集合就是數(shù)據(jù)庫(kù)的概念模式。在系統(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)系。 學(xué)生關(guān)系模式S(S#，SNAME，AGE，SEX) 選課關(guān)系模式SC(S#，C

12、#，GRADE) 課程關(guān)系模式C(C#，CNAME，TEACHER)圖2.6 關(guān)系模式集關(guān)系模型的三級(jí)體系結(jié)構(gòu) -子模式 l子模式是用戶所用到的那部分?jǐn)?shù)據(jù)的描述。除此之外，還應(yīng)指出數(shù)據(jù)與關(guān)系模式中相應(yīng)數(shù)據(jù)的聯(lián)系。例如，用戶需要用到子模式G（圖2.8）。成績(jī)子模式 G(S#，SNAME，C#，GRADE) 圖2.8 子模式關(guān)系模型的三級(jí)體系結(jié)構(gòu) -存儲(chǔ)模式 SC PTR S# C# GRADE S S# SNAME AGE SEX PTR S1 C1 80 S1 Wang 20 M S3 C1 90 S2 Liu 21 F S1 C2 70 S3 Chen 22 M S3 C2 85 S3 C3

13、 95 圖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)（即沒(méi)有特定的次序）。此外，還可對(duì)任意的屬性集建立輔助索引。 關(guān)系模型的形式定義l 關(guān)系模型有三個(gè)重要組成部分：數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)操縱，數(shù)據(jù)完整性規(guī)則。（1）數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)庫(kù)中全部數(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ù)庫(kù)的各種操作。關(guān)系運(yùn)算分成關(guān)系代數(shù)、

14、關(guān)系演算和關(guān)系邏輯等三類。 （3）數(shù)據(jù)完整性規(guī)則：數(shù)據(jù)庫(kù)中數(shù)據(jù)必須滿足實(shí)體完整性，參照完整性和用戶定義的完整性等三類完整性規(guī)則。 關(guān)系模型的優(yōu)點(diǎn)l與其它數(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ù)庫(kù)的研究建立在比較堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)上。（4）關(guān)系數(shù)據(jù)庫(kù)語(yǔ)言與一階謂詞邏輯的固有內(nèi)在聯(lián)系，為以關(guān)系數(shù)據(jù)庫(kù)為基礎(chǔ)的推理系統(tǒng)和知識(shí)庫(kù)系統(tǒng)的研究提供了方便。 返回關(guān)系查詢語(yǔ)言和關(guān)系運(yùn)算 l關(guān)系數(shù)據(jù)庫(kù)的數(shù)據(jù)操縱語(yǔ)言（DML）的語(yǔ)句分成查詢語(yǔ)句和更新語(yǔ)句兩大

15、類。查詢語(yǔ)句用于描述用戶的各種檢索要求；更新語(yǔ)句用于描述用戶進(jìn)行插入、刪除、修改等操作。關(guān)于查詢的理論稱為“關(guān)系運(yùn)算理論”。l關(guān)系查詢語(yǔ)言根據(jù)其理論基礎(chǔ)的不同分成三類：（1）關(guān)系代數(shù)語(yǔ)言。（2）關(guān)系演算語(yǔ)言。（3）關(guān)系邏輯語(yǔ)言。 返回2.2 關(guān)系代數(shù) l2.2.1 關(guān)系代數(shù)的五個(gè)基本操作 l2.2.2 關(guān)系代數(shù)的四個(gè)組合操作 l2.2.3 關(guān)系代數(shù)運(yùn)算的應(yīng)用實(shí)例 l2.2.4 關(guān)系代數(shù)的七個(gè)擴(kuò)充操作 返回關(guān)系代數(shù)的五個(gè)基本操作 (1)l 并（Union）設(shè)關(guān)系R和S具有相同的關(guān)系模式，R和S的并是由屬于R或?qū)儆赟的元組構(gòu)成的集合，記為RS。形式定義如下：RSt | tR tS，t是元組變量，R

16、和S的元數(shù)相同。l 差（Difference）設(shè)關(guān)系R和S具有相同的關(guān)系模式，R和S的差是由屬于R但不屬于S的元組構(gòu)成的集合，記為RS。形式定義如下：RS t | tR tS，R和S的元數(shù)相同。關(guān)系代數(shù)的五個(gè)基本操作 (2)l 投影（Projection） 這個(gè)操作是對(duì)一個(gè)關(guān)系進(jìn)行垂直分割，消去某些列，并重新安排列的順序。 設(shè)關(guān)系R是k元關(guān)系，R在其分量Ai1，Aim（mk，i1，im為1到k間的整數(shù)）上的投影用i1，im（R）表示，它是一個(gè)m元元組集合，形式定義如下：i1，im（R） t | tti1，timt1，tkR 例如，3，1（R）表示關(guān)系R中取第1、3列，組成新的關(guān)系，新關(guān)系中第1

17、列為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à)的。關(guān)系代數(shù)的五個(gè)基本操作 (3)l 選擇（Selection） 選擇操作是根據(jù)某些條件對(duì)關(guān)系做水平分割，即選取符合條件的元組。條件可用命題公式（即計(jì)算機(jī)語(yǔ)言中的條件表達(dá)式）F表示。F中有兩種成分：l關(guān)系R關(guān)于公式F的選擇操作用F（R）表示，形式定義如下：F（R） t | tR F（t）= true 為選擇運(yùn)算符，F(xiàn)（R）表示從R中挑選滿足公式F為真的元組所構(gòu)成的關(guān)系。例如，23（R）表示從R中挑選第2個(gè)分量值大于3的元組所構(gòu)

18、成的關(guān)系。書寫時(shí)，為了與屬性序號(hào)區(qū)別起見(jiàn)，常量用引號(hào)括起來(lái)，而屬性序號(hào)或?qū)傩悦灰靡?hào)括起來(lái)。關(guān)系代數(shù)的五個(gè)基本操作 l迪卡爾積A A B B C C A A B B C C a a b b C C b b g g a a d d a a F F d d a a f f c c b b d d （a）關(guān)系R （b）關(guān)系S 圖2.12 兩個(gè)關(guān)系 關(guān)系代數(shù)的五個(gè)基本操作 (例)l例2.3 圖2.12有兩個(gè)關(guān)系R和S，圖2.13的（a）、（b）表示RS和RS。（c）表示RS，此處R和S的屬性名相同，就應(yīng)在屬性名前注上相應(yīng)的關(guān)系名，例如R.A、S.A等。圖2.13的（d）表示C，A（R），即3，1（

19、R）。（e）表示B=b（R）。關(guān)系代數(shù)的五個(gè)基本操作 (例)A A B B C C A A B B C C R R. .A A R R. .B B R R. .C C S S. .A A S S. .B B S S. .C C C C A A A A B B C C a a b b c c a a b b c c a a b b c c b b g g a a c c a a a a b b c c d d a a f f c c d d b b a a b b c c d d a a f f f f d d c c b b d d c c b b d d d d a a f f b b g

20、g a a d d c c b b g g a a d d a a f f d d a a f f c c b b d d b b g g a a c c b b d d d d a a f f （a）RS （b）RS（c）RS （d）C，A（R）（e）B=b（R） 圖2.13 關(guān)系代數(shù)操作的結(jié)果 返回關(guān)系代數(shù)的四個(gè)組合操作 (1)l 交（intersection）關(guān)系R和S的交是由屬于R又屬于S的元組構(gòu)成的集合，記為RS，這里要求R和S定義在相同的關(guān)系模式上。形式定義如下：RSttR tS，R和S的元數(shù)相同。由于RS = R-（R-S），或RS = S-（S-R），因此交操作不是一個(gè)獨(dú)立的操

21、作。 在圖2.12中，RS的結(jié)果是只有一個(gè)元組（d，a，f）。 關(guān)系代數(shù)的四個(gè)組合操作 (2)l連接（join）連接有兩種：連接和F連接（這里是算術(shù)比較符，F(xiàn)是公式）。 連接 R St t= trR tsS tr its j F連接 F連接是從關(guān)系R和S的笛卡兒積中選取屬性間滿足某一公式F的元組, 這里F是形為F1F2Fn的公式，每個(gè)FP是形為ij的式子，而i和j分別為關(guān)系R和S的第i、第j個(gè)分量的序號(hào)。 關(guān)系代數(shù)的四個(gè)組合操作 (3)l 自然連接（natural join） 兩個(gè)關(guān)系R和S的自然連接操作具體計(jì)算過(guò)程如下： 計(jì)算RS ； 設(shè)R和S的公共屬性是A1,AK，挑選RS中滿足R.A1=

22、S.A1，R.AK=S.AK 的那些元組； 去掉S.A1，S.AK這些列。定義： i1,im (R.A1=S.A1. R.AK=S.AK(RS),其中i1,im為R和S的全部屬性，但公共屬性只出現(xiàn)一次。 關(guān)系代數(shù)的四個(gè)組合操作 (4)l除法（division） 設(shè)關(guān)系R和S的元數(shù)分別為r和s（設(shè)rs0），那么RS是一個(gè)（r-s）元的元組的集合。（RS）是滿足下列條件的最大關(guān)系：其中每個(gè)元組t與S中每個(gè)元組u組成的新元組必在關(guān)系R中。 lRS1，2，r-s（R）-1，2，r-s（1，2，r-s（R）S）-R） 返回關(guān)系代數(shù)運(yùn)算的應(yīng)用實(shí)例 l 在關(guān)系代數(shù)運(yùn)算中，把由五個(gè)基本操作經(jīng)過(guò)有限次復(fù)合的式子

23、稱為關(guān)系代數(shù)表達(dá)式。這種表達(dá)式的運(yùn)算結(jié)果仍是一個(gè)關(guān)系。我們可以用關(guān)系代數(shù)表達(dá)式表示各種數(shù)據(jù)查詢操作。 例2.7 返回關(guān)系代數(shù)的七個(gè)擴(kuò)充操作 l改名 l廣義投影 l賦值 l外連接（outer join） l外部并（outer union） l半連接（semijoin） l聚集操作 返回2.3 關(guān)系演算 l把數(shù)理邏輯的謂詞演算引入到關(guān)系運(yùn)算中，就可得到以關(guān)系演算為基礎(chǔ)的運(yùn)算。關(guān)系演算又可分為元組關(guān)系演算和域關(guān)系演算，前者以元組為變量，后者以屬性（域）為變量。l2.3.1 元組關(guān)系演算 l2.3.2 域關(guān)系演算 l2.3.3 關(guān)系運(yùn)算的安全約束和等價(jià)性 返回元組關(guān)系演算 (1)l 在元組關(guān)系演算（T

24、uple Relational Calculus）中，元組 關(guān)系演算表達(dá)式簡(jiǎn)稱為元組表達(dá)式，其一般形式為 t | P（t） 其中，t是元組變量，表示一個(gè)元數(shù)固定的元組；P是公式，在數(shù)理邏輯中也稱為謂詞，也就是計(jì)算機(jī)語(yǔ)言中的條件表達(dá)式。 t | P（t）表示滿足公式P的所有元組t的集合。 元組關(guān)系演算 (2)l在元組表達(dá)式中，公式由原子公式組成。l定義2.4 原子公式（Atoms）有下列三種形式： R（s） siuj sia或auj。 l在定義關(guān)系演算操作時(shí)，要用到“自由”（Free）和“約束”（Bound）變量概念。在一個(gè)公式中，如果元組變量未用存在量詞或全稱量詞符號(hào)定義，那么稱為自由元組變量

25、，否則稱為約束元組變量。 元組關(guān)系演算 (3)l定義2.5 公式（Formulas）的遞歸定義如下： 每個(gè)原子是一個(gè)公式。其中的元組變量是自由變量。 如果P1和P2是公式，那么P1、P1P2、P1P2和P1P2也都是公式。 如果P1是公式，那么（s）（P1）和（s）（P1）也都是公式。 公式中各種運(yùn)算符的優(yōu)先級(jí)從高到低依次為：，和，和，。在公式外還可以加括號(hào)，以改變上述優(yōu)先順序。 公式只能由上述四種形式構(gòu)成，除此之外構(gòu)成的都不是公式。 元組關(guān)系演算 (4)l例2.16 圖2.20的（a）、（b）是關(guān)系R和S，（c）（g）分別是下面五個(gè)元組表達(dá)式的值 A A B B C C A A B B C

26、C A A B B C C A A B B C C 1 1 2 2 3 3 1 1 2 2 3 3 3 3 4 4 6 6 4 4 5 5 6 6 4 4 5 5 6 6 3 3 4 4 6 6 5 5 6 6 9 9 7 7 8 8 9 9 7 7 8 8 9 9 5 5 6 6 9 9 （a a）關(guān)關(guān)系系 R R （b b）關(guān)關(guān)系系 S S （c c）R R1 1 （d d）R R2 2 A A B B C C A A B B C C R R. .B B S S. .C C R R. .A A 1 1 2 2 3 3 4 4 5 5 6 6 5 5 3 3 4 4 3 3 4 4 6 6

27、7 7 8 8 9 9 8 8 3 3 7 7 8 8 6 6 7 7 8 8 9 9 7 7 （e e）R R3 3 （f f）R R4 4 （g g）R R5 5 圖2.20 元組關(guān)系演算的例子 R1 = t | S（t）t12 R2 = t | R（t）S（t）R3 = t |（u）（S（t）R（u）t3u1）R5 = t |（u）（v）（R（u） S（v）u1v2t1=u2t2=v3t3=u1） 元組關(guān)系演算 (5)l 在元組關(guān)系演算的公式中，有下列三個(gè)等價(jià)的轉(zhuǎn)換規(guī)則： P1P2等價(jià)于(P1P2)； P1P2等價(jià)于（P1P2）。 （s）（P1（s）等價(jià)于(s)（P1（s）； （s）（P

28、1（s）等價(jià)于(s）（P1（s）。 P1P2等價(jià)于 P1P2。元組關(guān)系演算 (6)l關(guān)系代數(shù)表達(dá)式到元組表達(dá)式的轉(zhuǎn)換例2.17 RS可用 t | R（t）S（t）表示； R-S可用 t | R（t）S（t） 表示； RS可用 t |（u）（v）（R（u）S(V) t1=u1 t2=u2t3=u3t4=v1 t5=v2 t6=v3） 表示。設(shè)投影操作是2,3（R），那么元組表達(dá)式可寫成： t |(u)（R（u）tl=u2t2=u3） F（R）可用 t |R(t)F表示，F(xiàn)是F的等價(jià)表示形式。譬如2=d（R）可寫成 t |（R（t）t2=d）。 返回元組關(guān)系演算 (7)bpS0Ib0(1):( ,

29、),( ,),(),()(|()/()1),() (|(pbbbbpccccppppbppbbBbI IbbbbMbBbMbbbIIbppbbbbbbBbMbIAlgorithmletIc vc vnullif III Ielseif IIIDDuII Ielseif IIID bpSIb000max0)/()1)( ,( ),1,1, , ),0() , ( ,),(?,?),?|(,( ),1( ), , , )pbbI IbbIbpppbMbbbpbpbbpbccbpppbbbbbDuImcgu IIIelse letItwhile ItttIIc vImcgu IIt rr nttt

30、域關(guān)系演算 (1)l原子公式有兩種形式： R（x1xk）； xy。 公式中也可使用、和等邏輯運(yùn)算符,(x)和（x），但變量x是域變量，不是元組變量。l自由域變量、約束域變量等概念和元組演算中一樣。l域演算表達(dá)式是形為t1tkP（t1，tk） 的表達(dá)式，其中P（t1，tk）是關(guān)于自由域變量t1，tk 的公式。域關(guān)系演算 (2)l例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)系演算的例子 A B C A B C D E A B C A

31、B C B D A 1 2 3 1 2 3 7 5 4 5 6 1 2 3 5 7 4 4 5 6 3 4 6 4 8 4 5 6 8 7 7 7 8 9 5 6 9 7 8 9 8 4 7 3 4 6 R1= xyz| R（xyz） x3 R2= xyz| R（xyz）（S（xyz） y = 4）R3= xyz|（u）（v）（R（zxu） w（yv） uv ） 域關(guān)系演算 (3)l元組表達(dá)式到域表達(dá)式的轉(zhuǎn)換l我們可以很容易地把元組表達(dá)式轉(zhuǎn)換成域表達(dá)式，轉(zhuǎn)換規(guī)則如下： 對(duì)于k元的元組變量t，可引入k個(gè)域變量t1tk，在公式中t用t1tk替換，元組分量ti用ti替換。 對(duì)于每個(gè)量詞（u）或（u）

32、，若u是m元的元組變量，則引入m個(gè)新的域變量u1um。在量詞的轄域內(nèi)，u用u1um替換，ui用ui替換，（u）用（u1）（um）替換，（u）用（u1）（um）替換。 返回關(guān)系運(yùn)算的安全約束和等價(jià)性 l定義2.6 在數(shù)據(jù)庫(kù)技術(shù)中，不產(chǎn)生無(wú)限關(guān)系和無(wú)窮驗(yàn)證的運(yùn)算稱為安全運(yùn)算，相應(yīng)的表達(dá)式稱為安全表達(dá)式，所采取的措施稱為安全約束。l并、差、笛爾卡積、投影和選擇是關(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à)的。 返回2.4 關(guān)系代數(shù)表達(dá)式的優(yōu)化 l2.4.1 關(guān)系代數(shù)表達(dá)式的優(yōu)化問(wèn)題 l

33、2.4.2 關(guān)系代數(shù)表達(dá)式的等價(jià)變換規(guī)則 l2.4.3 關(guān)系代數(shù)表達(dá)式的優(yōu)化算法 返回關(guān)系代數(shù)表達(dá)式的優(yōu)化(1)l在關(guān)系代數(shù)表達(dá)式中需要指出若干關(guān)系的操作步驟。那么，系統(tǒng)應(yīng)該以什么樣的操作順序，才能做到既省時(shí)間，又省空間，而且效率也比較高呢？這個(gè)問(wèn)題稱為查詢優(yōu)化問(wèn)題。l在關(guān)系代數(shù)運(yùn)算中，笛卡兒積和連接運(yùn)算是最費(fèi)時(shí)間的。關(guān)系代數(shù)表達(dá)式的優(yōu)化(2)l例2.23 設(shè)關(guān)系R和S都是二元關(guān)系，屬性名分別為A，B和C，D。設(shè)有一個(gè)查詢可用關(guān)系代數(shù)表達(dá)式表示： E1=A（B=CD=99（RS） 也可以把選擇條件D=99移到笛卡兒積中的關(guān)系S前面： E2=A（B=C（RD=99（S） 還可以把選擇條件BC與笛

34、卡兒積結(jié)合成等值連接形式： B=C E3=A（R D=99（S） 這三個(gè)關(guān)系代數(shù)表達(dá)式是等價(jià)的，但執(zhí)行的效率大不一樣。顯然，求El，E2，E3的大部分時(shí)間是花在連接操作上的。 返回關(guān)系代數(shù)表達(dá)式的等價(jià)變換規(guī)則 (1)l連接和笛卡兒積的交換律 l連接和笛卡兒積的結(jié)合律 l投影的級(jí)聯(lián) l選擇的級(jí)聯(lián) l選擇和投影操作的交換 l選擇對(duì)笛卡兒積的分配律 l選擇對(duì)并的分配律 圖2.6 關(guān)系模式集關(guān)系代數(shù)表達(dá)式的等價(jià)變換規(guī)則 (2)l選擇對(duì)集合差的分配律 l選擇對(duì)自然連接的分配律 l投影對(duì)笛卡兒積的分配律 l投影對(duì)并的分配律 l選擇與連接操作的結(jié)合 l并和交的交換律 l并和交的結(jié)合律 返回關(guān)系代數(shù)表達(dá)式的優(yōu)

35、化算法 (1)l 在關(guān)系代數(shù)表達(dá)式中，最花費(fèi)時(shí)間和空間的運(yùn)算是笛卡兒積和連接操作，為此，引出三條啟發(fā)式規(guī)則，用于對(duì)表達(dá)式進(jìn)行轉(zhuǎn)換，以減少中間關(guān)系的大小。 盡可能早地執(zhí)行選擇操作； 盡可能早地執(zhí)行投影操作； 避免直接做笛卡兒積，把笛卡兒積操作之前和之后的一連串選擇和投影合并起來(lái)一起 做。 關(guān)系代數(shù)表達(dá)式的優(yōu)化算法 (2)l算法2.1 關(guān)系代數(shù)表達(dá)式的啟發(fā)式優(yōu)化算法。 輸入：一個(gè)關(guān)系代數(shù)表達(dá)式的語(yǔ)法樹(shù) 輸出：計(jì)算表達(dá)式的一個(gè)優(yōu)化序列l(wèi)例2.24 對(duì)于如下關(guān)系數(shù)據(jù)庫(kù) S(S#,SNAME,AGE,SEX) SC(S#,C#,GRADE) C(C#,CNAME,TEACHER) 檢索至少學(xué)習(xí)LIU老師

36、所授一門課程的女學(xué)生的學(xué)號(hào)和姓名返回2.5 關(guān)系邏輯 l2.5.1 關(guān)系運(yùn)算的成分 l2.5.2 規(guī)則的安全性 l2.5.3 從關(guān)系代數(shù)到關(guān)系邏輯的轉(zhuǎn)換 l2.5.4 遞歸過(guò)程 l2.5.5 關(guān)系邏輯與關(guān)系代數(shù)的差異 關(guān)系邏輯關(guān)系邏輯的成分l謂詞（Predicates）l表示關(guān)系模式，如P(x,y,z)l外延謂詞（Extensional Predicate）,其關(guān)系存貯在數(shù)據(jù)庫(kù)中；EDB指代外延數(shù)據(jù)庫(kù)l內(nèi)涵謂詞（Intensional Predicate）,僅由邏輯規(guī)則定義；IDB指代內(nèi)涵數(shù)據(jù)庫(kù)關(guān)系邏輯關(guān)系邏輯的成分l原子（Atoms）l關(guān)系原子，是一個(gè)謂詞符號(hào)，帶一個(gè)參數(shù)表，每個(gè)參數(shù)可以是變

37、量或常量l算術(shù)原子，是一個(gè)算術(shù)比較表達(dá)式 假如關(guān)系R(A,B,C)，則R(2345,b,c)和R(x,b,x)均是關(guān)系原子； xy是一個(gè)算術(shù)原子關(guān)系邏輯關(guān)系邏輯的成分l規(guī)則（Rules）l規(guī)則是形為W- P1 P2 Pn的式子l頭部l符號(hào)- l包括一個(gè)或多個(gè)原子的體l例2.25設(shè)關(guān)系S(S#,SNAME,AGE,SEX),一個(gè)規(guī)則 W(a,b)20 關(guān)系邏輯關(guān)系邏輯的成分l查詢（Queries）l是一個(gè)或多個(gè)規(guī)則的聚集，規(guī)則之間的順序無(wú)關(guān)緊要 2.5 關(guān)系邏輯 l規(guī)則的安全性l得到的頭部關(guān)系必須是有限的，因此，頭部的變量必須在體部收到約束l關(guān)系體部由原子構(gòu)成，原子有四種形式，關(guān)系原子，求反關(guān)系原子，算術(shù)原子和求反算術(shù)原子。后三種形式的取值必須限制在一定的范圍之內(nèi)l規(guī)則安全的條件l在頭部、求反關(guān)系原子和任何算術(shù)原