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

1、第2章 關(guān)系模型和關(guān)系運算理論 本章重要概念（一） （1）基本概念關(guān)系模型，關(guān)鍵碼（主鍵和外鍵），關(guān)系的定義和性質(zhì)，三類完整性規(guī)則，ER模型到關(guān)系模型的轉(zhuǎn)換規(guī)則，過程性語言與非過程性語言。（2）關(guān)系代數(shù)五個基本操作，四個組合操作，七個擴(kuò)充操作。 本章重要概念（二）（3）關(guān)系演算元組關(guān)系演算和域關(guān)系演算的原子公式、公式的定義。關(guān)系演算的安全性和等價性。（4）關(guān)系代數(shù)表達(dá)式的優(yōu)化關(guān)系代數(shù)表達(dá)式的等價及等價轉(zhuǎn)換規(guī)則，啟化式優(yōu)化算法。（5）關(guān)系邏輯謂詞、原子、規(guī)則和查詢，規(guī)則的安全性，用規(guī)則模擬關(guān)系代數(shù)表達(dá)式。 本章概要 l本章先介紹關(guān)系模型的基本概念；然后介紹關(guān)系運算的三種理論：關(guān)系代數(shù)、關(guān)系演算和

2、關(guān)系邏輯。 關(guān)系模型和關(guā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ù)語 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)系模型的三級體系結(jié)構(gòu) l2.1.6 關(guān)系模型的形式定義和優(yōu)點 l2.1.7 關(guān)系查詢語言和關(guān)系運算 返回基本術(shù)語(1) l定義2.1 用二維表格表示實體集，用關(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ù)的過程和方法。 工 號 姓 名 年 齡 性 別 工 資 4001 zhang 50 M 2000 4002 li 40 F 1500 4124 liu 35 M 2000 5018 wang 25 M 1000 圖2.1 職工登記表 基本術(shù)語(2)l 在關(guān)系模型中，字段稱為屬性，字段值稱為屬性值，記錄類型稱為關(guān)系模式。在圖2.2中，關(guān)系模式名是R。記錄稱為元組（tuple），元組的集合稱為關(guān)系（relation）或?qū)嵗╥nstance）。一般用大寫字母A、B、C、 表示單個屬性，用大寫字母 、X、Y、Z表示屬性集，用小寫字母表示屬性值，有時也習(xí)慣

4、稱呼關(guān)系為表或表格，元組為行(row)，屬性為列(column)。l關(guān)系中屬性個數(shù)稱為“元數(shù)”（arity），元組個數(shù)為“基數(shù)”(cardinality)。 基本術(shù)語(3)l關(guān)系元數(shù)為5，基數(shù)為4 圖2.2 關(guān)系模型的術(shù)語 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ù)語 關(guān)系模型術(shù)語字段、數(shù)據(jù)項屬性記錄類型關(guān)

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

6、一個屬性數(shù)目相同的元組的集合。 l 在關(guān)系模型中，對關(guān)系作了下列規(guī)范性限制：（1）關(guān)系中每一個屬性值都是不可分解的；（2）關(guān)系中不允許出現(xiàn)重復(fù)元組（即不允許出現(xiàn)相同的元組）；（3）由于關(guān)系是一個集合，因此不考慮元組間的順序，即沒有行序；（4）元組中的屬性在理論上也是無序的，但使用時按習(xí)慣考慮列的順序。返回關(guān)系模型的三類完整性規(guī)則(1) l 實體完整性規(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)系中某個主鍵值。 這條規(guī)則的實質(zhì)是“不允許引用不存在的實體”。 在上述形式定義中，關(guān)系模式R1的關(guān)系稱為“參照關(guān)系”，關(guān)系模式R2的關(guān)系稱為“依賴關(guān)系”?！爸鞅怼焙汀案北怼?，“父表”和“子表”。 關(guān)系模型的三類完整性規(guī)則 (3)l例2.1 下面各種情況說明了參照完整性規(guī)則在關(guān)系中如何實現(xiàn)的。 在關(guān)系數(shù)據(jù)庫中有下列兩個關(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中有一個元組（S7,C4,80），而學(xué)號S7卻在關(guān)系S中找不到，那么我們就認(rèn)為在關(guān)系SC中引用了一個不存在的學(xué)生實體，這就違反了參照完整性規(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的屬性為工號、姓名、工資、所在車間的編號。每個模式的主鍵與外鍵已標(biāo)出。在EMP中，由于D# 不在主鍵中，因

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

10、數(shù)，范圍還太大，我們可以寫如下規(guī)則把年齡限制在1530歲之間：CHECK（AGE BETWEEN 15 AND 30） 返回ER模型向關(guān)系模型的轉(zhuǎn)換規(guī)則 (1)lER模型向關(guān)系模型的轉(zhuǎn)換，實際上就是把ER圖轉(zhuǎn)換成關(guān)系模式的集合。l規(guī)則2.1（實體類型的轉(zhuǎn)換）：將每個實體類型轉(zhuǎn)換成一個關(guān)系模式，實體的屬性即為關(guān)系模式的屬性，實體標(biāo)識符即為關(guān)系模式的鍵。l規(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)系 學(xué)校（校名，地址，電話，校長名，任職年月）校長（姓名，性別，年齡，職稱）ER模型向關(guān)

11、系模型的轉(zhuǎn)換規(guī)則 (3)圖2.4 一對多聯(lián)系 系（系號，系名，電話）教師（工號，姓名，性別，年齡，系號，聘期）ER模型向關(guān)系模型的轉(zhuǎn)換規(guī)則 (4)圖2.5 多對多聯(lián)系 返回學(xué)生（學(xué)號，姓名，年齡，性別）選課（學(xué)號，課程號，成績）課程（課程號，課程名，教師名）關(guān)系模型的三級體系結(jié)構(gòu) - 關(guān)系模式 l在關(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)系。 學(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)系模型的三級體系結(jié)構(gòu) -子模式 l子模式是用戶所用到的那部分?jǐn)?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) -存儲模式 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)系存儲是作為文件看待的，每個元組就是一個記錄。由于關(guān)系模式有鍵，因此存儲一個關(guān)系可用散列方法或索引方法實現(xiàn)。如果關(guān)系的元組數(shù)目較少（100個以內(nèi)），那么也可以用“堆文件”方式實現(xiàn)（即沒有特定的次序）。此外，還可對任意的屬性集建立輔助索引。 關(guān)系模型的形式定義l 關(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ù)、

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

15、類。查詢語句用于描述用戶的各種檢索要求；更新語句用于描述用戶進(jìn)行插入、刪除、修改等操作。關(guān)于查詢的理論稱為“關(guān)系運算理論”。l關(guān)系查詢語言根據(jù)其理論基礎(chǔ)的不同分成三類：（1）關(guān)系代數(shù)語言。（2）關(guān)系演算語言。（3）關(guān)系邏輯語言。 返回2.2 關(guān)系代數(shù) l2.2.1 關(guān)系代數(shù)的五個基本操作 l2.2.2 關(guān)系代數(shù)的四個組合操作 l2.2.3 關(guān)系代數(shù)運算的應(yīng)用實例 l2.2.4 關(guān)系代數(shù)的七個擴(kuò)充操作 返回關(guān)系代數(shù)的五個基本操作 (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ù)的五個基本操作 (2)l 投影（Projection） 這個操作是對一個關(guān)系進(jìn)行垂直分割，消去某些列，并重新安排列的順序。 設(shè)關(guān)系R是k元關(guān)系，R在其分量Ai1，Aim（mk，i1，im為1到k間的整數(shù)）上的投影用i1，im（R）表示，它是一個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）是等價的。關(guān)系代數(shù)的五個基本操作 (3)l 選擇（Selection） 選擇操作是根據(jù)某些條件對關(guān)系做水平分割，即選取符合條件的元組。條件可用命題公式（即計算機語言中的條件表達(dá)式）F表示。F中有兩種成分：l關(guān)系R關(guān)于公式F的選擇操作用F（R）表示，形式定義如下：F（R） t | tR F（t）= true 為選擇運算符，F(xiàn)（R）表示從R中挑選滿足公式F為真的元組所構(gòu)成的關(guān)系。例如，23（R）表示從R中挑選第2個分量值大于3的元組所構(gòu)

18、成的關(guān)系。書寫時，為了與屬性序號區(qū)別起見，常量用引號括起來，而屬性序號或?qū)傩悦灰靡柪ㄆ饋?。關(guān)系代數(shù)的五個基本操作 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 兩個關(guān)系 關(guān)系代數(shù)的五個基本操作 (例)l例2.3 圖2.12有兩個關(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ù)的五個基本操作 (例)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ù)的四個組合操作 (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），因此交操作不是一個獨立的操

21、作。 在圖2.12中，RS的結(jié)果是只有一個元組（d，a，f）。 關(guān)系代數(shù)的四個組合操作 (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的公式，每個FP是形為ij的式子，而i和j分別為關(guān)系R和S的第i、第j個分量的序號。 關(guān)系代數(shù)的四個組合操作 (3)l 自然連接（natural join） 兩個關(guān)系R和S的自然連接操作具體計算過程如下： 計算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ù)的四個組合操作 (4)l除法（division） 設(shè)關(guān)系R和S的元數(shù)分別為r和s（設(shè)rs0），那么RS是一個（r-s）元的元組的集合。（RS）是滿足下列條件的最大關(guān)系：其中每個元組t與S中每個元組u組成的新元組必在關(guān)系R中。 lRS1，2，r-s（R）-1，2，r-s（1，2，r-s（R）S）-R） 返回關(guān)系代數(shù)運算的應(yīng)用實例 l 在關(guān)系代數(shù)運算中，把由五個基本操作經(jīng)過有限次復(fù)合的式子

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

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

25、，否則稱為約束元組變量。 元組關(guān)系演算 (3)l定義2.5 公式（Formulas）的遞歸定義如下： 每個原子是一個公式。其中的元組變量是自由變量。 如果P1和P2是公式，那么P1、P1P2、P1P2和P1P2也都是公式。 如果P1是公式，那么（s）（P1）和（s）（P1）也都是公式。 公式中各種運算符的優(yōu)先級從高到低依次為：，和，和，。在公式外還可以加括號，以改變上述優(yōu)先順序。 公式只能由上述四種形式構(gòu)成，除此之外構(gòu)成的都不是公式。 元組關(guān)系演算 (4)l例2.16 圖2.20的（a）、（b）是關(guān)系R和S，（c）（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)系演算的公式中，有下列三個等價的轉(zhuǎn)換規(guī)則： P1P2等價于(P1P2)； P1P2等價于（P1P2）。 （s）（P1（s）等價于(s)（P1（s）； （s）（P

28、1（s）等價于(s）（P1（s）。 P1P2等價于 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的等價表示形式。譬如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。 公式中也可使用、和等邏輯運算符,(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）是三個關(guān)系R、S、W，（d）、（e）、（f）分別表示下面三個域表達(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ī)則如下： 對于k元的元組變量t，可引入k個域變量t1tk，在公式中t用t1tk替換，元組分量ti用ti替換。 對于每個量詞（u）或（u）

32、，若u是m元的元組變量，則引入m個新的域變量u1um。在量詞的轄域內(nèi)，u用u1um替換，ui用ui替換，（u）用（u1）（um）替換，（u）用（u1）（um）替換。 返回關(guān)系運算的安全約束和等價性 l定義2.6 在數(shù)據(jù)庫技術(shù)中，不產(chǎn)生無限關(guān)系和無窮驗證的運算稱為安全運算，相應(yīng)的表達(dá)式稱為安全表達(dá)式，所采取的措施稱為安全約束。l并、差、笛爾卡積、投影和選擇是關(guān)系代數(shù)最基本的操作，并構(gòu)成了關(guān)系代數(shù)運算的最小完備集。已經(jīng)證明，在這個基礎(chǔ)上，關(guān)系代數(shù)、安全的元組關(guān)系演算、安全的域關(guān)系演算在關(guān)系的表達(dá)和操作能力上是完全等價的。 返回2.4 關(guān)系代數(shù)表達(dá)式的優(yōu)化 l2.4.1 關(guān)系代數(shù)表達(dá)式的優(yōu)化問題 l

33、2.4.2 關(guān)系代數(shù)表達(dá)式的等價變換規(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)該以什么樣的操作順序，才能做到既省時間，又省空間，而且效率也比較高呢？這個問題稱為查詢優(yōu)化問題。l在關(guān)系代數(shù)運算中，笛卡兒積和連接運算是最費時間的。關(guān)系代數(shù)表達(dá)式的優(yōu)化(2)l例2.23 設(shè)關(guān)系R和S都是二元關(guān)系，屬性名分別為A，B和C，D。設(shè)有一個查詢可用關(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） 這三個關(guān)系代數(shù)表達(dá)式是等價的，但執(zhí)行的效率大不一樣。顯然，求El，E2，E3的大部分時間是花在連接操作上的。 返回關(guān)系代數(shù)表達(dá)式的等價變換規(guī)則 (1)l連接和笛卡兒積的交換律 l連接和笛卡兒積的結(jié)合律 l投影的級聯(lián) l選擇的級聯(lián) l選擇和投影操作的交換 l選擇對笛卡兒積的分配律 l選擇對并的分配律 圖2.6 關(guān)系模式集關(guān)系代數(shù)表達(dá)式的等價變換規(guī)則 (2)l選擇對集合差的分配律 l選擇對自然連接的分配律 l投影對笛卡兒積的分配律 l投影對并的分配律 l選擇與連接操作的結(jié)合 l并和交的交換律 l并和交的結(jié)合律 返回關(guān)系代數(shù)表達(dá)式的優(yōu)

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

36、所授一門課程的女學(xué)生的學(xué)號和姓名返回2.5 關(guān)系邏輯 l2.5.1 關(guān)系運算的成分 l2.5.2 規(guī)則的安全性 l2.5.3 從關(guān)系代數(shù)到關(guān)系邏輯的轉(zhuǎn)換 l2.5.4 遞歸過程 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ù)庫中；EDB指代外延數(shù)據(jù)庫l內(nèi)涵謂詞（Intensional Predicate）,僅由邏輯規(guī)則定義；IDB指代內(nèi)涵數(shù)據(jù)庫關(guān)系邏輯關(guān)系邏輯的成分l原子（Atoms）l關(guān)系原子，是一個謂詞符號，帶一個參數(shù)表，每個參數(shù)可以是變

37、量或常量l算術(shù)原子，是一個算術(shù)比較表達(dá)式 假如關(guān)系R(A,B,C)，則R(2345,b,c)和R(x,b,x)均是關(guān)系原子； xy是一個算術(shù)原子關(guān)系邏輯關(guān)系邏輯的成分l規(guī)則（Rules）l規(guī)則是形為W- P1 P2 Pn的式子l頭部l符號- l包括一個或多個原子的體l例2.25設(shè)關(guān)系S(S#,SNAME,AGE,SEX),一個規(guī)則 W(a,b)20 關(guān)系邏輯關(guān)系邏輯的成分l查詢（Queries）l是一個或多個規(guī)則的聚集，規(guī)則之間的順序無關(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ù)原