理論課數(shù)據(jù)庫(kù)chapter02

1、2.1 關(guān)系數(shù)據(jù)庫(kù)的基本概念,2.2 關(guān)系模型及其描述,2.3 關(guān)系代數(shù),2.4 關(guān)系演算,第二章 關(guān)系數(shù)據(jù)庫(kù),1,2.5 關(guān)系數(shù)據(jù)庫(kù)查詢(xún)優(yōu)化,上一章回顧,什么是數(shù)據(jù)庫(kù)？ 按一定結(jié)構(gòu)組織，并長(zhǎng)期存儲(chǔ)在計(jì)算機(jī)內(nèi)、可共享的大量數(shù)據(jù)的有機(jī)集合 常用的數(shù)據(jù)庫(kù)管理系統(tǒng)有哪些？ Oracle、SQL Server、MySQL等 導(dǎo)師與研究生是什么對(duì)應(yīng)關(guān)系？ 1：n,2,上一章回顧,E-R模型的四個(gè)組成部分？,3,實(shí)體名,屬性名,矩形框表示實(shí)體型,橢圓形表示屬性,菱形表示聯(lián)系,連接實(shí)體型與聯(lián)系類(lèi)型，也可用于表示實(shí)體與屬性的聯(lián)系 并注明種類(lèi)；對(duì)構(gòu)成碼的屬性，在屬性名下畫(huà)一橫線表示。,上一章回顧,三種基本數(shù)據(jù)模

2、型是？ 層次模型、網(wǎng)狀模型、關(guān)系模型 關(guān)系模型采用什么結(jié)構(gòu)表示實(shí)體及實(shí)體間聯(lián)系？ 表結(jié)構(gòu) DBMS的三級(jí)模式與兩級(jí)映象？ 外模式、模式、內(nèi)模式 外模式/模式映象、模式/內(nèi)模式映象,4,5,上一章回顧,模式、外模式、內(nèi)模式分別是什么的描述？ 模式：數(shù)據(jù)庫(kù)中全體數(shù)據(jù)的邏輯結(jié)構(gòu)和特征的描述 外模式：數(shù)據(jù)庫(kù)用戶(hù)使用的局部數(shù)據(jù)的邏輯結(jié)構(gòu)和特征的描述 內(nèi)模式：數(shù)據(jù)物理結(jié)構(gòu)和存儲(chǔ)方式的描述 DBMS系統(tǒng)怎樣確保了數(shù)據(jù)獨(dú)立性？ 外模式/模式映象：實(shí)現(xiàn)數(shù)據(jù)邏輯獨(dú)立性 模式/內(nèi)模式映象：實(shí)現(xiàn)數(shù)據(jù)物理獨(dú)立性,6,2.1基本概念,關(guān)系數(shù)據(jù)庫(kù)之父 E.F.Codd（埃德加.科德）英國(guó)人，1923 在牛津的?？巳貙W(xué)院研

3、習(xí)數(shù)學(xué)與化學(xué) 作為英國(guó)皇家空軍的飛行員參加了二戰(zhàn) 1948年加入了IBM公司，成為數(shù)學(xué)程序員 1953年，出于對(duì)參議員約瑟夫麥卡錫的不滿(mǎn), 他遷往加拿大渥太華居住了十年 之后回到密歇根大學(xué)并取得了計(jì)算機(jī)科學(xué)博士學(xué)位 1981年, 科德因在關(guān)系型數(shù)據(jù)庫(kù)方面的貢獻(xiàn)獲得了圖靈獎(jiǎng) 2003年4月18日, 科德因心臟病在佛羅里達(dá)威廉姆斯島的家中去世, 享年79歲,7,1、關(guān)系及其性質(zhì) （1）域 定義2.1: 域是一組具有相同數(shù)據(jù)類(lèi)型的值的集合。,在關(guān)系中用域來(lái)表示屬性的取值范圍 域中所包含的值的個(gè)數(shù)稱(chēng)域的基數(shù)(用m表示),例：D1=A , 2 , 3 , , Q , K M1= 13 D2=數(shù)據(jù)庫(kù)原理，

4、面向?qū)ο髷?shù)據(jù)庫(kù)技術(shù) M2= 2,2.1 關(guān)系數(shù)據(jù)庫(kù)的基本概念,8,（2）笛卡爾積 定義2.2: 給定一組域 D1，Dn (可有相同的域)。 其笛卡爾積為： D1D2Dn=(d1，d2，dn) | diDi，i=1,2,n,n元組,di為分量,笛卡兒積也是一個(gè)集合,其中每一個(gè)元素(d1，d2，dn)叫作一個(gè)n元組(n-Tuple), 或簡(jiǎn)稱(chēng)為元組。元素中的每一個(gè)值di叫作一個(gè)分量（Component）。,若Di（i1，2，n）為有限集，其基數(shù)（Cardinal number）為mi（i1，2，n），則D1D2Dn的基數(shù)為：,2.1 關(guān)系數(shù)據(jù)庫(kù)的基本概念,9,定義2.3 D1D2Dn的有意義的子集

5、稱(chēng)為在域D1，D2,Dn上的關(guān)系， 記為 R(D1,D2,Dn) 。,其中：R為關(guān)系的名；n為關(guān)系的度（目）；rR 表示 r 是 R 中的元組。,子集元素是關(guān)系中的元組； 關(guān)系中的元組個(gè)數(shù)是關(guān)系的基數(shù); 同樣可以把關(guān)系看作是一個(gè)二維表：,每一行對(duì)應(yīng)一個(gè)元組； 表的每一列對(duì)應(yīng)一個(gè)域，每個(gè)域起一個(gè)名字稱(chēng)為屬性;,（3）關(guān)系,2.1 關(guān)系數(shù)據(jù)庫(kù)的基本概念,10,例,例：設(shè) D1=男人集合(MAN) = 王強(qiáng)、李東、張兵 D2 =女人集合(WOMAN) = 趙紅、吳芳 D3=兒童集合(CHILD) = 王一、李一、李二 （1）求上面三個(gè)集合的笛卡兒積 （2）構(gòu)造一個(gè)家庭關(guān)系，可表示為： FAMILY（

6、MAN，WOMAN，CHILD）,2.1 關(guān)系數(shù)據(jù)庫(kù)的基本概念,11,（4）關(guān)系中常用術(shù)語(yǔ) 候選碼 主碼 外碼 全碼,2.1 關(guān)系數(shù)據(jù)庫(kù)的基本概念,12,S(Sno, Cardno, Dno, Sname, Sage, ) D(Dno, Dname, Location),主碼,主碼,外碼,PUR(Cno，Pno，Sno),全碼,參照關(guān)系,被參照關(guān)系,2.1 關(guān)系數(shù)據(jù)庫(kù)的基本概念,13,（5）關(guān)系的性質(zhì) 每列的值為同一類(lèi)型。 每列具有不同的屬性名(可同域) 任意兩元組不能完全相同。 行的次序可以互換。 列的次序可以互換。 分量值是原子的。,+5,學(xué)號(hào) 姓名 年齡,、網(wǎng)蟲(chóng),不允許,元組,分量值,屬

7、性名,關(guān)系的類(lèi)型 ： 基本關(guān)系（基表） 查詢(xún)表 視圖表,2.1 關(guān)系數(shù)據(jù)庫(kù)的基本概念,14,2、關(guān)系模式與關(guān)系數(shù)據(jù)庫(kù) 定義2.4： 關(guān)系的描述稱(chēng)關(guān)系模式，其表示為：R(U，D，Dom，F(xiàn)),關(guān)系模式可簡(jiǎn)記為關(guān)系的屬性名表。 R(U)=R(A1 ，A2，A3，.An) 例：學(xué)生（學(xué)號(hào)，姓名，總成績(jī)）,域名集,屬性名集,屬性間的依賴(lài)關(guān)系集,屬性向域的映像集,關(guān)系模式就是關(guān)系的框架（表框架） 它是對(duì)關(guān)系結(jié)構(gòu)的描述,2.1 關(guān)系數(shù)據(jù)庫(kù)的基本概念,15,在關(guān)系模型中，實(shí)體以及實(shí)體間的聯(lián)系都是用關(guān)系來(lái)表示。在一個(gè)給定的現(xiàn)實(shí)世界領(lǐng)域中，相應(yīng)于所有實(shí)體及實(shí)體之間的聯(lián)系的關(guān)系的集合構(gòu)成一個(gè)關(guān)系數(shù)據(jù)庫(kù)。 關(guān)系數(shù)據(jù)

8、庫(kù)也有型和值之分。關(guān)系數(shù)據(jù)庫(kù)的型也稱(chēng)為關(guān)系數(shù)據(jù)庫(kù)模式，是對(duì)關(guān)系數(shù)據(jù)庫(kù)的描述，是關(guān)系模式的集合。關(guān)系數(shù)據(jù)庫(kù)的值也稱(chēng)為關(guān)系數(shù)據(jù)庫(kù)，是關(guān)系的集合。關(guān)系數(shù)據(jù)庫(kù)模式與關(guān)系數(shù)據(jù)庫(kù)通常統(tǒng)稱(chēng)為關(guān)系數(shù)據(jù)庫(kù)。,關(guān)系數(shù)據(jù)庫(kù),2.1 關(guān)系數(shù)據(jù)庫(kù)的基本概念,16,術(shù)語(yǔ)間的聯(lián)系,一個(gè)關(guān)系只能對(duì)應(yīng)一個(gè)關(guān)系模式 一個(gè)關(guān)系模式可對(duì)應(yīng)多個(gè)關(guān)系 關(guān)系模式是關(guān)系的型，按其型裝入數(shù)據(jù)值后即形成關(guān)系 關(guān)系模式是相對(duì)靜態(tài)的、穩(wěn)定的，而關(guān)系是動(dòng)態(tài)的、隨時(shí)間變化的 一個(gè)具體的關(guān)系數(shù)據(jù)庫(kù)是若干相關(guān)關(guān)系的集合,17,1.關(guān)系模型的特點(diǎn)及組成 關(guān)系模型的特點(diǎn)： 結(jié)構(gòu)簡(jiǎn)單，表達(dá)力強(qiáng) 語(yǔ)言的一體化 非過(guò)程化的操作 堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ) 操作效率較低 關(guān)系模型

9、的組成： 關(guān)系數(shù)據(jù)結(jié)構(gòu) 關(guān)系數(shù)據(jù)操作 關(guān)系完整性約束,2. 關(guān)系模型的數(shù)據(jù)操作 (1)數(shù)據(jù)查詢(xún) (2)數(shù)據(jù)插入 (3)數(shù)據(jù)刪除 (4)數(shù)據(jù)修改,2.2 關(guān)系模型及其描述,18,3. 關(guān)系的完整性 三類(lèi)完整性約束： 實(shí)體完整性 參照完整性 用戶(hù)定義的完整性,說(shuō)明： 實(shí)體完整性規(guī)則是對(duì)基本關(guān)系的約束和限定。 實(shí)體具有唯一性標(biāo)識(shí)主碼。 主碼屬性不能取空值。,(1) 實(shí)體完整性 規(guī)則2.1 實(shí)體完整性規(guī)則 : 若屬性A是基本關(guān)系R的主碼屬性，則屬性A不能取空值。,不變性 由關(guān)系系統(tǒng)自動(dòng)支持,2.2 關(guān)系模型及其描述,是應(yīng)用領(lǐng)域需要遵循的約束條件,19,(2) 參照完整性 引用關(guān)系： 關(guān)系中的某屬性的值

10、需要參照另一關(guān)系的屬性來(lái)取值。 例1：學(xué)生(學(xué)號(hào)，姓名，性別，專(zhuān)業(yè)號(hào)，年齡) 專(zhuān)業(yè)(專(zhuān)業(yè)號(hào)，專(zhuān)業(yè)名),例2: 學(xué)生(學(xué)號(hào)，姓名，性別，專(zhuān)業(yè)號(hào)，年齡，班長(zhǎng)),引用,引用,2.2 關(guān)系模型及其描述,20,定義2.5 ： 設(shè)：基本關(guān)系R、S(可為同一關(guān)系)。 若F是R的一個(gè)(組)屬性，但不是R的碼。 如果F與S的主碼 K相對(duì)應(yīng)，則稱(chēng)F是R的外碼。 并稱(chēng)R為參照關(guān)系，S為被參照關(guān)系（目標(biāo)關(guān)系）。 說(shuō)明：S的主碼K和R的外碼F必須定義在同一個(gè)(或一組)域上。,例1：學(xué)生(學(xué)號(hào)，姓名，性別，專(zhuān)業(yè)號(hào)，年齡) 專(zhuān)業(yè)(專(zhuān)業(yè)號(hào)，專(zhuān)業(yè)名),被參照關(guān)系,參照關(guān)系,外碼,參照完整性規(guī)則定義了外碼與主碼之間的引用規(guī)則。,

11、2.2 關(guān)系模型及其描述,21,規(guī)則2.2 參照完整性規(guī)則 若屬性(組) F是R的外碼且它與S的主碼K相對(duì)應(yīng)，則對(duì)于R中每個(gè)元組在F上的值必須為： 或者取空值(F的每個(gè)屬性值均為空值)； 或者等于S中某個(gè)元組的主碼值。 例1：學(xué)生(學(xué)號(hào)，姓名，性別，專(zhuān)業(yè)號(hào)，年齡) 關(guān)系中每個(gè)元組的專(zhuān)業(yè)號(hào)取值： 空值(未給該學(xué)生分配專(zhuān)業(yè))； 非空值(是專(zhuān)業(yè)關(guān)系中某個(gè)元組的專(zhuān)業(yè)號(hào)值)。,2.2 關(guān)系模型及其描述,22,例2：職工EMP(EMP#,ENAME,JOB,DEPT#) 部門(mén)DEPT(DEPT#,DNAME,LOC) 則：EMP中的DEPT#為空或?yàn)镈EPT中的DEPT#的值,(3) 用戶(hù)定義的完整性,用

12、戶(hù)自定義完整性是針對(duì)某一具體數(shù)據(jù)的約束條件，反映某一具體應(yīng)用所涉及的數(shù)據(jù)必須滿(mǎn)足的語(yǔ)義要求，由應(yīng)用環(huán)境決定。,例： 屬性的取值范圍 屬性的非空限制,2.2 關(guān)系模型及其描述,23,關(guān)系數(shù)據(jù)語(yǔ)言的分類(lèi) （1）關(guān)系代數(shù)語(yǔ)言 用對(duì)關(guān)系的運(yùn)算來(lái)表達(dá)查詢(xún)要求方式的語(yǔ)言。 （2）關(guān)系演算語(yǔ)言 用謂詞來(lái)表達(dá)查詢(xún)要求方式的語(yǔ)言。 元組關(guān)系演算語(yǔ)言 域關(guān)系演算語(yǔ)言 （3）結(jié)構(gòu)化查詢(xún)語(yǔ)言 （SQL) 具有關(guān)系代數(shù)和關(guān)系演算雙重特點(diǎn)的語(yǔ)言,2.3 關(guān)系代數(shù),24,關(guān)系查詢(xún)語(yǔ)言,關(guān)系代數(shù)語(yǔ)言：查詢(xún)操作是以集合操作作為基礎(chǔ)的語(yǔ)言 關(guān)系演算語(yǔ)言：查詢(xún)操作是以謂詞演算作為基礎(chǔ)的語(yǔ)言,關(guān)系查詢(xún)語(yǔ)言是一種比Pascal、C等程

13、序設(shè)計(jì)語(yǔ)言更高級(jí)的語(yǔ)言。 Pascal、C、關(guān)系代數(shù)語(yǔ)言屬于過(guò)程性語(yǔ)言，在編程時(shí)必須給出獲得結(jié)果的操作步驟。 而關(guān)系演算語(yǔ)言屬于非過(guò)程性語(yǔ)言，編程時(shí)只需要指出需要什么信息，不必給出具體的操作步驟。,干什么？ 怎么干？,干什么？,2.3 關(guān)系代數(shù),25,2.3 關(guān)系代數(shù),關(guān)系代數(shù)、元組關(guān)系演算和域關(guān)系演算三種語(yǔ)言在表達(dá)能力上是完全等價(jià)的。 關(guān)系代數(shù)、元組關(guān)系演算和域關(guān)系演算都是抽象的查詢(xún)語(yǔ)言，與實(shí)際DBMS中實(shí)現(xiàn)的語(yǔ)言（SQL）不完全一樣，可以用來(lái)評(píng)估實(shí)際系統(tǒng)中查詢(xún)語(yǔ)言的能力 關(guān)系數(shù)據(jù)語(yǔ)言表達(dá)能力完全相同、非過(guò)程化、功能強(qiáng)且可嵌入使用,26,關(guān)系代數(shù)語(yǔ)言的組成,關(guān)系代數(shù)語(yǔ)言是通過(guò)對(duì)關(guān)系的運(yùn)算來(lái)表

14、達(dá)查詢(xún)，通過(guò)對(duì)關(guān)系進(jìn)行“分割”或者“重組”，得到新的關(guān)系 關(guān)系代數(shù)以元組的集合為運(yùn)算對(duì)象，通過(guò)各種運(yùn)算形成新的元組集合 關(guān)系運(yùn)算分為： 集合運(yùn)算 關(guān)系運(yùn)算 擴(kuò)充的關(guān)系運(yùn)算,27,1.集合運(yùn)算 關(guān)系代數(shù)是一種抽象的查詢(xún)語(yǔ)言。它以關(guān)系為運(yùn)算對(duì)象，通過(guò)對(duì)關(guān)系進(jìn)行“組合”或“分割”，得到所需的數(shù)據(jù)集合關(guān)系。 分類(lèi)： 集合運(yùn)算（并、交、差；廣義笛卡爾積） 關(guān)系運(yùn)算 （投影、選擇、連接和除運(yùn)算）,設(shè)：t 為元組變量；R、S為同類(lèi)關(guān)系(同元、相應(yīng)屬性同域）； 下列運(yùn)算結(jié)果為同類(lèi)關(guān)系： (1)并運(yùn)算: RUS =t |（tR）（t S） (2)差運(yùn)算: R-S=t |（tR）（t S） (3)交運(yùn)算: RS=

15、t |（tR）（t S）,R,S,2.3 關(guān)系代數(shù),28,關(guān)系的集合運(yùn)算實(shí)例,29,(4)廣義笛卡爾積: R、S可為不同類(lèi)關(guān)系，則結(jié)果為不同類(lèi)關(guān)系： RS=tr ts|（trR）（ts S）,連接為 m+n目關(guān)系,m目關(guān)系,n目關(guān)系,2.3 關(guān)系代數(shù),30,元組的前n列是關(guān)系R的一個(gè)元組 后m列是關(guān)系S的一個(gè)元組,2.3 關(guān)系代數(shù),31,記號(hào) 設(shè)t為R的元組變量，設(shè)：R（A1，A2，An) = R(U) tAi (Ai為屬性)： R在屬性Ai上的所有值。 tA (A為屬性集)，R在屬性集A上的所有值。 例：t學(xué)號(hào) -R中學(xué)號(hào)上的值 t 學(xué)號(hào)，姓名,學(xué)號(hào) 姓名 年齡,t,2.3 關(guān)系代數(shù),32,

16、2.專(zhuān)門(mén)的關(guān)系運(yùn)算 （1）選擇 是行上的選擇，產(chǎn)生同類(lèi)關(guān)系。 F(R)=t|(tR)F(t)=true 含義：由R中滿(mǎn)足F條件的元組組成。 其中：F由屬性名（值）、比較符、邏輯運(yùn)算符組成。 例： A25 A3 “f”(R) 或： 25 3 “f”(R) 選擇運(yùn)算是從行的角度進(jìn)行的運(yùn)算, 25 3 “f”(R),2.3 關(guān)系代數(shù),33,（2）投影運(yùn)算 是列上的選擇，產(chǎn)生不同類(lèi)關(guān)系。 A(R)=tA |(tR) 含義：R中取屬性名表A中指定的列，消除重復(fù)元組。 例： A3，A2(R),2.3 關(guān)系代數(shù),34,投影操作主要是從列的角度進(jìn)行運(yùn)算,用關(guān)系代數(shù)表示查詢(xún)： 例：查選2號(hào)課程的學(xué)生記錄。 例:

17、 成績(jī)?cè)?0分以上的學(xué)生號(hào)。,解： Cno=2(SC),解: Sno(Grade90(SC),2.3 關(guān)系代數(shù),35,（3）連接運(yùn)算： 一般連接 它從兩個(gè)關(guān)系的笛卡爾積中選取屬性間滿(mǎn)足一定條件的元組。 R S=tr ts|(trR)(tsS)trA tsB,比較運(yùn)算符,含義： 從R X S中選取R關(guān)系在A屬性組上的值與S關(guān)系在B屬性組上值滿(mǎn)足關(guān)系的元組。,2.3 關(guān)系代數(shù),36,A B,= R. A S. B(RS),連接舉例,R S,CE,37,X,連接 = 笛卡爾積 + 選擇, 等值連接：為“=”的連接。 為“”的連接運(yùn)算稱(chēng)為等值連接 等值連接的含義 從關(guān)系R與S的廣義笛卡爾積中選取A、B

18、屬性值相等的那些元組，即等值連接為： R S = | tr Rts StrA = tsB ,2.3 關(guān)系代數(shù),38,R S,R.B=S.B,等值連接舉例,39, 自然連接 設(shè)R、S有同名屬性集B R S= tr ts|(trR)(tsS)trB = tsB,其中B是R和S的公共屬性（同名屬性組），并且在形成的新關(guān)系中要去掉重復(fù)的屬性。 特殊的等值連接，要求兩個(gè)關(guān)系中進(jìn)行比較的分量必須是同名屬性組,2.3 關(guān)系代數(shù),40,R S,自然連接舉例,R S,R.B=S.B,41,等值連接與自然連接的區(qū)別： （1）自然連接一定是等值連接，但等值連接不一定是自然連接。因?yàn)樽匀贿B接要求相等的分量必須是公共屬

19、性，而等值連接相等的分量不一定是公共屬性。 （2）等值連接不把重復(fù)的屬性去掉，而自然連接要把重復(fù)屬性去掉。,注意,若R、S無(wú)公共屬性，R S=？,2.3 關(guān)系代數(shù)連接,42,R S= tr ts|(trR)(tsS)trB = tsB,回憶：關(guān)系的“乘”運(yùn)算 廣義笛卡爾積 R(X)乘以S(Y)：把X屬性組上的每一種取值都與Y屬性組上的每一種取值組合在一起,（4）除運(yùn)算,2.3 關(guān)系代數(shù),43,被除數(shù),商(X),除數(shù)(Y),關(guān)系的除運(yùn)算可以看成是“乘”運(yùn)算的逆運(yùn)算,（4）除運(yùn)算,2.3 關(guān)系代數(shù),44,余數(shù)？,象集（Image Set） 關(guān)系R(X , Z), X, Z是屬性組，x是X上的取值，

20、定義x在R中的象集為 Zx=tZ|tRtX=x 從R中選出在X上取值為x的元組，去掉X上的分量，只留Z上的分量,X Z,張軍同學(xué)所選修的全部課程,x=張軍,Zx,（4）除運(yùn)算,2.3 關(guān)系代數(shù),45,選擇 + 投影,做法：逐個(gè)考慮選課關(guān)系SC中的元組r，求r在姓名SN上的分量x，再求x在選課關(guān)系中的象集課程Cx，若Cx包含了所有的課程C，則x是滿(mǎn)足條件的一個(gè)元組, x | x=rSN rSC CxC ,選修全部課 程的學(xué)生,全部課程,x同學(xué)所選修 的全部課程,除定義: R(X,Y) S(Y) = trX | trRY(S)Yx 其中Yx為x在R中的象集, x=trX,除運(yùn)算,如何得到選修了全部

21、課程的學(xué)生？,2.3 關(guān)系代數(shù),46,2.3 關(guān)系代數(shù),設(shè)關(guān)系R(X，Y)和S(Y，Z)，X，Y，Z為屬性組 RS=tX|tR y(S)Yx , X(R) Yx為x在R中的象集: 對(duì)于每個(gè)值x， xX(R) 求：y (X=x(R) 結(jié)果為：象集Yx包含了y(S)的x。,關(guān)系代數(shù)定義了除運(yùn)算。但實(shí)際應(yīng)用中，當(dāng)關(guān)系R真包含了關(guān)系S時(shí)，RS才有意義。 R能被S除盡的充分必要條件是： R中的屬性包含S中的所有屬性；R中有一些屬性不出現(xiàn)在S中。 設(shè)R為r元、S為s元關(guān)系(rs0)，當(dāng)關(guān)系R真包含了關(guān)系S時(shí)，RS可用下式計(jì)算： RS =1,2,r-s(R)-1,2,r-s(1,2,r-s(R)S)-R)

22、【例2.8】設(shè)R(S#,P#)、W1(P#)、W2(P#)、W3(P#)。 則RW1可表示為： S#(R)-S#(S#(R)W1)-R) 同理可列出另外兩式。,R,S,2.3 關(guān)系代數(shù),（4）除運(yùn)算,例RWi的運(yùn)算結(jié)果可理解為： R中包含Wi屬性值的那些元組在R與Wi的屬性名之差（即S#）上的投影。,2.3 關(guān)系代數(shù),示例 求同時(shí)選修了001和002號(hào)課程的學(xué)生號(hào) 方案1： S#，C#(SC) C# = 001 C# = 002 (C) 方案2： S#(SC C# = 001 C# = 002 (C) 哪一個(gè)正確？,2.3 關(guān)系代數(shù),50,S#，C#(SC) C# = 001 C# = 002

23、 (C),2.3 關(guān)系代數(shù),51,S#(SC C# = 001 C# = 002 (C),2.3 關(guān)系代數(shù),52,X = S#, Grade,=,R,AB (R),S,AB (R) CD (S),AB (R) CD (S)-R,R S=,-,=,2.3 關(guān)系代數(shù),53,R(X,Y) S(Y)=X(R) X(X(R) Y (S) - R ),Student,2.3 關(guān)系代數(shù)(綜合舉例）,54,Course,2.3 關(guān)系代數(shù)(綜合舉例）,55,SC,2.3 關(guān)系代數(shù)(綜合舉例）,56,2.2 關(guān)系代數(shù),例: 查詢(xún)至少選修了一門(mén)其直接先行課為005號(hào)課程的學(xué)生名。,學(xué)生-課程數(shù)據(jù)庫(kù)表見(jiàn)教材: S(s

24、no，sname，sex，age，dept) C(cno，cname， credit ， pcno) SC(sno，cno，grade),sname(pcno=005 (C SC S),A(F (R),例：查選修002號(hào)課程的學(xué)生姓名與年齡。 sname,age(S cno=002 (SC),例1：查不選002號(hào)課程的學(xué)生姓名與年齡。,Cno002 ?,sname,age(S)- sname,age(S cno=002 (SC),2.3 關(guān)系代數(shù)(綜合舉例）,sname,age(S cno 002 (SC),58,例2：查詢(xún)至少選修了兩門(mén)課程的學(xué)生學(xué)號(hào)。,sno(1=425(SCSC),2.3

25、 關(guān)系代數(shù)(綜合舉例）,59,例3：查所選課程包含了學(xué)生210101所選全部課程的學(xué)生號(hào)和姓名。,sno,sname(S) (sno，cno(SC) cno (sno=210101 (SC),例4：查詢(xún)選修了全部課程的學(xué)生學(xué)號(hào)與姓名。,sno,sname(S) (sno，cno(SC) cno(C),2.3 關(guān)系代數(shù)(綜合舉例）,60,例9查詢(xún)至少選修了一門(mén)其直接先行課為5號(hào)課程的課程的學(xué)生姓名。 Sname(Cpno=5(Course SC Student) 或 Sname(Cpno=5(Course)SCSno，Sname(Student) 或 Sname(Sno(Cpno=5(Cours

26、e)SC)Sno，Sname (Student),2.3 關(guān)系代數(shù)(綜合舉例）,61,2.3 關(guān)系代數(shù),關(guān)系代數(shù)五種基本運(yùn)算： 投影,選擇,并,差,笛卡爾積 5種基本運(yùn)算的作用： 1)關(guān)系的屬性指定 A1 , A2 , , An (R) 2)關(guān)系的元組選擇 F (R),3)兩個(gè)關(guān)系的歸并 R1R2 4)關(guān)系中元組的插入 R1R2 5)關(guān)系中元組的刪除 R1R2,3.擴(kuò)充的關(guān)系運(yùn)算 （1）廣義投影 F1,Fn(R)，其中，F(xiàn)1,Fn是涉及R中常量和屬性的算術(shù)表達(dá)式。 例：sno,sname,sex,age=20(sno=200101(Student) （2）賦值 RS: 將關(guān)系S賦予R。 例：C

27、ourse Course099，電子商務(wù)，2，003（并） Student Student-(sno=200108(Student) （刪除）,2.3 關(guān)系代數(shù),63,(3) 外連接 為避免自然連接時(shí)因失配而發(fā)生的信息丟失，可以假定往參與連接的一方表中附加一個(gè)取值全為空值的行，它和參與連接的另一方表中的任何一個(gè)未匹配上的元組都能匹配，稱(chēng)之為外連接 外連接 = 自然連接 + 失配的元組 外連接的形式：左外連接、右外連接、全外連接 左外連接 = 自然連接 + 左側(cè)表中失配的元組 右外連接 = 自然連接 + 右側(cè)表中失配的元組 全外連接 = 自然連接 + 兩側(cè)表中失配的元組,2.3 關(guān)系代數(shù),64,

28、外連接例子,65,（4）半連接 R和S的自然連接只在關(guān)系R或關(guān)系S的屬性集上的投影， 稱(chēng)為半連接。 R和S的半連接記為R S。 S和R的半連接記為S R。 （5）聚集 根據(jù)關(guān)系中的一組值做統(tǒng)計(jì)、計(jì)算得到一個(gè)值作為結(jié)果。 常用聚集函數(shù)：max、min、avg、sum、count。 形式：G 聚集函數(shù)名(屬性)(關(guān)系),2.3 關(guān)系代數(shù),66,例：求男同學(xué)的平均年齡。 G avg(age)(sex=男(Student) 例：計(jì)算年齡不小于20歲的同學(xué)人數(shù)。 G count(sno)(age20(Student) 例：數(shù)據(jù)庫(kù)課程的平均分?jǐn)?shù)。 G avg(grade)(cno(cname=數(shù)據(jù)庫(kù)(Co

29、urse) SC) （6）外部并 由R和S中的所有屬性組成(公共屬性只取一次)，其元組由屬于R或?qū)儆赟的元組組成，且元組在新增加的屬性填上空值。,2.3 關(guān)系代數(shù),67,外部并例子,68,（7）重命名 x(E)：其含義為給一個(gè)關(guān)系表達(dá)式賦予名字。它返回表達(dá)式E的結(jié)果，并把名字x賦給E。 x(A1，A2，An)(E):其含義為返回表達(dá)式E的結(jié)果，并把名字x賦給E，同時(shí)將各屬性更名為A1，A2，An。 例：設(shè)關(guān)系R(姓名，課程，成績(jī))，求數(shù)學(xué)成績(jī)比王紅同學(xué)高的學(xué)生。 S.姓名(課程=數(shù)學(xué)姓名=王紅(R)(課程=數(shù)學(xué)S(R) R.成績(jī)S.成績(jī),2.3 關(guān)系代數(shù),69,關(guān)系演算：以謂詞演算為基礎(chǔ)表示的

30、關(guān)系運(yùn)算。 關(guān)系演算分類(lèi) 元組關(guān)系演算 域關(guān)系演算 1. 元組關(guān)系演算 用 t|(t) 表示關(guān)系。,命題公式,元組變量,表示所有使得為真的元組組成的集合。,2.4 關(guān)系演算,70,（1）元組關(guān)系演算中的原子公式 R(t) t元組變量 R關(guān)系名 R(t)表示：t是關(guān)系R的一個(gè)元組。 關(guān)系R可表示為：t|R(t) tiC 或 Cti C常量 表示：元組t的第i個(gè)分量與常量C之間滿(mǎn)足關(guān)系。 tiuj 其中：t，u元組變量 算術(shù)比較符 tit的第i個(gè)分量 uju的第j個(gè)分量 tiuj表示：元組t的第i個(gè)分量與元組u的第j個(gè)分量之間滿(mǎn)足關(guān)系。,2.4 關(guān)系演算-元組演算,71,（2）公式的遞歸定義 每個(gè)

31、原子公式是公式。 若1和2是公式，則1、12、12也是公式。 若是公式，則(t)()、(t)()也是公式。 有限次使用上述3條規(guī)則得到的公式都是元組關(guān)系演算表達(dá)式。 公式中各種運(yùn)算符的優(yōu)先級(jí)： 算術(shù)運(yùn)算符、量詞()、邏輯運(yùn)算符( ),高,低,括號(hào)優(yōu)先,2.4 關(guān)系演算-元組演算,72,關(guān)系代數(shù)表達(dá)式,關(guān)系演算表達(dá)式, 用關(guān)系演算表達(dá)式表達(dá)五種基本運(yùn)算：,RS= t | R(t)S(t) ,RS= t | R(t) S(t) ,RS = t(n+m) | ( u(n) ) ( v(m) ) ( R(u) S(v) t1=u1 tn=un tn+1=v1 tn+m=vm ) ,F (R) = t

32、| R (t) F ,i1, i2, , ik (R) = t(k) | ( u) (R(u) t1=ui1 tk=uik ),2.4 關(guān)系演算關(guān)系代數(shù),73,例1 查詢(xún)信息系（IS）全體學(xué)生,F (R) = t | R (t) F ,SIS= t | Student(t) t5=IS ,例2 查詢(xún)年齡小于20歲的學(xué)生,S20= t | Student(t) t420 ,2.4 關(guān)系演算關(guān)系代數(shù),74,例3 查詢(xún)學(xué)生的姓名和所在系,S1= t(2) | ( u) （Student(u) t1=u2 t2=u5）,i1, i2, , ik (R) = t(k) | ( u) (R(u) t1=u

33、i1 tk=uik ),2.4 關(guān)系演算關(guān)系代數(shù),75,例2：設(shè)R和S都是二元關(guān)系，將1,4(2=3(RS)轉(zhuǎn)換成元組演算表達(dá)式。,t|(u)(v)(R(u)S(v)u2=v1t1=u1t2=v2),2.4 關(guān)系演算-元組演算,76,例1：設(shè)有關(guān)系R和S，請(qǐng)寫(xiě)出下列元組演算表達(dá)式的結(jié)果。,R,S,R1=t|S(t)t12 R2=t|R(t) S(t) R3=t|(u)(S(t)R(u)t3u1),2.4 關(guān)系演算-元組演算,2.4 關(guān)系演算-域演算,78,2.域關(guān)系演算 以域變量作為謂詞變?cè)幕緦?duì)象。 用t1,t2,tk|(t1,t2,tk)表示關(guān)系。 t1,t2,tk是元組變量t的各個(gè)域分

34、量。 （1）域演算中的原子公式 R（ t1,t2,tk) 表示：由分量t1,t2,tk組成的元組屬于R。 tiuj 表示：元組變量t的第i個(gè)分量與元組u的第j個(gè)分量間滿(mǎn)足關(guān)系。 tiC 或 Cti 表示：元組變量t的第i個(gè)分量與常量C間滿(mǎn)足關(guān)系。 （2）公式的遞歸定義 與元組演算定義類(lèi)似。,例：設(shè)有關(guān)系R、S、W，試寫(xiě)出下列域演算表達(dá)式的結(jié)果。,R,W,S,R1=xyz|R(xyz)x3 R2=xyz|R(xyz)S(xyz)y=8 R3=xyz|(u)(v)(R(zxu)W(yv)uv),2.4 關(guān)系演算-域演算,79,2.4 關(guān)系演算-域演算,用域演算表達(dá)式表示下列查詢(xún)： （1）查詢(xún)女學(xué)生

35、的情況。 R1=t1t2t3t4t5|Student(t1t2t3t4t5)t3=女 （2）查詢(xún)學(xué)號(hào)為220101的學(xué)生選修的課程在85分以上的課程號(hào)。 R2=t2| (t1) (t3) (SC(t1t2t3) t1=220101 t385 ) （3）查詢(xún)選修課程號(hào)為003的所有學(xué)生的學(xué)號(hào)和姓名。 R3=t1t2| (t1) (u2) (Student(t1t2t3t4t5) SC(u1u2u3) t1=u1 u2=003 ),安全運(yùn)算 不產(chǎn)生無(wú)限關(guān)系和無(wú)窮驗(yàn)證的運(yùn)算。 安全表達(dá)式 安全運(yùn)算的表達(dá)式。 安全限制 安全運(yùn)算所采取的措施。,關(guān)系代數(shù)運(yùn)算總是安全的。關(guān)系演算則可能出現(xiàn)無(wú)限關(guān)系和無(wú)窮驗(yàn)

36、證問(wèn)題,3.關(guān)系演算的安全性,例：t|R(t),這是一個(gè)無(wú)限關(guān)系。,要使關(guān)系演算是安全的，只要定義一個(gè)安全約束有限集合，該有限集是表達(dá)式中涉及到的關(guān)系中的值的集合。經(jīng)過(guò)安全限制后的表達(dá)式其運(yùn)算是安全的。,關(guān)系代數(shù)和關(guān)系演算所依據(jù)的基礎(chǔ)理論是相同的，故可進(jìn)行相互轉(zhuǎn)換。已證明，關(guān)系代數(shù)、安全的元組演算、安全的域演算在關(guān)系的表達(dá)能力上是等價(jià)的。,2.4 關(guān)系演算,81,2.5 查詢(xún)優(yōu)化,數(shù)據(jù)查詢(xún)是DBS中最基本、最常用和最復(fù)雜的數(shù)據(jù)操作，查詢(xún)優(yōu)化是影響關(guān)系DBMS性能的關(guān)鍵因素。 關(guān)系數(shù)據(jù)理論基于關(guān)系代數(shù)，同一個(gè)查詢(xún)要求可以對(duì)應(yīng)多個(gè)不同形式卻相互等價(jià)的表達(dá)式。 關(guān)系數(shù)據(jù)查詢(xún)語(yǔ)言是非過(guò)程化的，由DBM

37、S自動(dòng)生成若干候選的查詢(xún)計(jì)劃并擇優(yōu)使用。,82,2.5 查詢(xún)優(yōu)化,1.關(guān)系DB的查詢(xún)優(yōu)化及其目標(biāo) 查詢(xún)優(yōu)化：從查詢(xún)的多個(gè)執(zhí)行策略中進(jìn)行合理選擇的過(guò)程。 目標(biāo)：選擇有效的策略，求得關(guān)系式的值，以提高其查詢(xún)效率。 基本途徑可以分為兩種：用戶(hù)處理和機(jī)器自動(dòng)處理 查詢(xún)優(yōu)化器： 由DBMS自動(dòng)生成并從中選取較優(yōu)查詢(xún)計(jì)劃的程序。 查詢(xún)的開(kāi)銷(xiāo)主要包括： 在單機(jī)數(shù)據(jù)庫(kù)中：總代價(jià) = I/O代價(jià) + CPU代價(jià) 在多用戶(hù)環(huán)境下：總代價(jià) = I/O代價(jià) + CPU代價(jià) + 內(nèi)存代價(jià) 在網(wǎng)絡(luò)環(huán)境下： 總代價(jià) = + 網(wǎng)絡(luò)代價(jià) 查詢(xún)的執(zhí)行開(kāi)銷(xiāo)與多個(gè)因素有關(guān)： 軟件環(huán)境、硬件環(huán)境、數(shù)據(jù)量、方法。,2.5 查詢(xún)優(yōu)化,關(guān)系

38、數(shù)據(jù)庫(kù)查詢(xún)過(guò)程：,為什么要查詢(xún)優(yōu)化？,例: Student表有l(wèi)03個(gè)學(xué)生記錄，每人平均選10門(mén)課， SC表共有1000*10=l04個(gè)選課記錄。要求: 查學(xué)生“王林”選課成績(jī)?cè)?5分以上的課程號(hào)。 SELECT cno FROM S，SC WHERE S.sno=SC.sno AND sname=王林 AND grade 85 ；,等價(jià)的關(guān)系代數(shù)表示： cno( F1 F2 F3 ( SSC ) ) cno( F2 F3 ( S SC ) ) cno(F2 (S) F3 (SC) ),哪種效率高？,連接時(shí)間復(fù)雜度為： 103104=O(107) 10310=O(104) 110=O(101)

39、,對(duì)執(zhí)行基本運(yùn)算(關(guān)系掃描與連接)的次數(shù)進(jìn)行分析：, cno( F1 F2 F3 ( SSC ) ) cno( F2 F3 ( S SC ) ) cno( F2 (S) F3 (SC) ) 先在兩表上做 ，產(chǎn)生1000*10000=107個(gè)連接記錄，再在其上進(jìn)行先后操作。其基本運(yùn)算的次數(shù)為：3*107。 先在兩個(gè)表上做 ，產(chǎn)生1000*10=104個(gè)連接記錄，再在其上進(jìn)行先后操作。其基本運(yùn)算的次數(shù)為：107+2*104。 先分別在兩個(gè)表上做,再做 ，產(chǎn)生1*10=10個(gè)連接記錄，再在其上進(jìn)行 。其基本運(yùn)算的次數(shù)為：104+103+2*101。,連接時(shí)間復(fù)雜度為： O(107) O(104) O

40、(101),2.5 查詢(xún)優(yōu)化,查詢(xún)處理包括三個(gè)基本步驟： 解析和翻譯 優(yōu)化 實(shí)現(xiàn)（求值）,解析和翻譯 解析：檢查語(yǔ)法、驗(yàn)證關(guān)系 翻譯：將查詢(xún)轉(zhuǎn)化為內(nèi)部形式，并進(jìn)一步翻譯為關(guān)系代數(shù) 實(shí)現(xiàn) 執(zhí)行引擎選取一個(gè)查詢(xún)計(jì)劃并執(zhí)行，而后將結(jié)果返回給查詢(xún).,87,2.5 查詢(xún)優(yōu)化,查詢(xún)優(yōu)化技術(shù)的分類(lèi)： 規(guī)則優(yōu)化：根據(jù)某些啟發(fā)式規(guī)則，如“先選擇，后投影”來(lái)完成優(yōu)化。特點(diǎn)是對(duì)查詢(xún)的關(guān)系代數(shù)表達(dá)式進(jìn)行等價(jià)變換，以減少執(zhí)行開(kāi)銷(xiāo)，也稱(chēng)為代數(shù)優(yōu)化 物理優(yōu)化：根據(jù)數(shù)據(jù)的物理組織和訪問(wèn)路徑進(jìn)行優(yōu)化，如用索引進(jìn)行優(yōu)化，也稱(chēng)物理優(yōu)化 代價(jià)估算優(yōu)化：對(duì)于多個(gè)候選策略逐個(gè)進(jìn)行執(zhí)行代價(jià)估算，從中選擇代價(jià)最小的作為執(zhí)行策略，稱(chēng)為代價(jià)估算

41、優(yōu)化,88,2.查詢(xún)優(yōu)化的一般策略 當(dāng)前一般都采用先代數(shù)優(yōu)化、后物理優(yōu)化的方法。 代數(shù)優(yōu)化的基本原理是對(duì)關(guān)系代數(shù)表達(dá)式進(jìn)行等價(jià)變換，選擇其中代價(jià)最小的。 基本原則就是盡量減少查詢(xún)過(guò)程中產(chǎn)生的中間結(jié)果，從而換取較小的時(shí)空開(kāi)銷(xiāo)。,89,2.5 查詢(xún)優(yōu)化,(1)盡可能先做選擇運(yùn)算、投影運(yùn)算 這是優(yōu)化策略中最重要、最基本的一條。 可以有效降低中間結(jié)果的數(shù)量，常?？墒箞?zhí)行時(shí)間節(jié)約幾個(gè)數(shù)量級(jí)。,90,2.5 查詢(xún)優(yōu)化,(2)合并笛卡爾積與其后的選擇為連接運(yùn)算 把要執(zhí)行的笛卡爾積與在它后面要執(zhí)行的選擇結(jié)合起來(lái)成為一個(gè)連接運(yùn)算，連接特別是等值連接要比笛卡爾積節(jié)省很多時(shí)間。 R.AS.C(RS)=R S AC,

42、91,2.5 查詢(xún)優(yōu)化,(3)把投影運(yùn)算和選擇運(yùn)算同時(shí)進(jìn)行 如果有若干投影和選擇運(yùn)算，且是對(duì)同一個(gè)關(guān)系執(zhí)行，則可以在掃描關(guān)系的同時(shí)進(jìn)行投影和選擇運(yùn)算，避免重復(fù)掃描關(guān)系 sno(grade=90(SC),92,2.5 查詢(xún)優(yōu)化,(4)讓投影運(yùn)算和其前后的其他運(yùn)算同時(shí)進(jìn)行 把投影同其前后的雙目運(yùn)算結(jié)合起來(lái)，不必為了去掉某些列而專(zhuān)門(mén)掃描關(guān)系 sno(S1-S2) S1 sno(S2),93,2.5 查詢(xún)優(yōu)化,(5)在執(zhí)行連接前對(duì)關(guān)系適當(dāng)?shù)念A(yù)處理 預(yù)處理主要有兩種：索引連接、歸并連接 如：經(jīng)過(guò)排序后的R和S進(jìn)行連接時(shí)，時(shí)間復(fù)雜度大大降低，從O(m*n)到O(m+n) (6)尋找公共子表達(dá)式 如果某個(gè)子

43、表達(dá)式常常出現(xiàn)，并且將其結(jié)果放在外存中的代價(jià)小于計(jì)算它的代價(jià)，則將其計(jì)算一次，并放入中間文件中。,94,2.5 查詢(xún)優(yōu)化,2.5 查詢(xún)優(yōu)化,3. 關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換 如果在每個(gè)合法的數(shù)據(jù)庫(kù)實(shí)例上, 兩個(gè)關(guān)系代數(shù)表達(dá)式都生成同樣的元組集合, 則這兩個(gè)關(guān)系代數(shù)表達(dá)式稱(chēng)為等價(jià)的 注意: 元組次序是無(wú)關(guān)的 等價(jià)規(guī)則說(shuō)明了兩種形式的表達(dá)式是等價(jià)的 可以用一個(gè)表達(dá)式替換另一個(gè) 12條等價(jià)規(guī)則,95,1.連接、笛卡爾積交換律 E1E2 E2E1 E1 E2 E2 E1 E1 E2 E2 E1 F F 2.連接、笛卡爾積的結(jié)合律 (E1E2) E3 E1(E2E3) (E1 E2) E3 E1 (E2 E3

44、) (E1 E2) E3 E1 (E2 E3) F1 F2 F1 F2,96,2.5 查詢(xún)優(yōu)化,3.投影的串接律 條件：t1是t2、 tn的子集 說(shuō)明：多個(gè)投影中，只有最后一個(gè)運(yùn)算是必須的 4.選擇的串接律 說(shuō)明：多個(gè)連續(xù)的條件可以合并成一個(gè)，這樣可以一次檢查所有條件；同樣，合取選擇運(yùn)算可以分解為多個(gè)選擇運(yùn)算，便于和其他運(yùn)算重新組合,97,2.5 查詢(xún)優(yōu)化,5.選擇與投影的交換律 形式（1） 說(shuō)明：其中選擇條件F只涉及屬性A1,A2,An 形式（2） 意義：將條件F中涉及的屬性的投影前移，以便投影和其他運(yùn)算合并 6.選擇與笛卡爾積的交換律 如果F中涉及的屬性都是E1中的屬性：,98,2.5 查

45、詢(xún)優(yōu)化,如果F=F1F2，F(xiàn)1只涉及E1中的屬性，F(xiàn)2只涉及E2中的屬性： 如果F1只涉及E1中的屬性，F(xiàn)2涉及E1和E2中的屬性： 該規(guī)則使得選擇盡量能在笛卡爾積之前先做，減小中間結(jié)果集。 7.選擇與并的交換律 設(shè)E1、E2有相同的屬性名：,99,2.5 查詢(xún)優(yōu)化,8.選擇與差的交換律 設(shè)E1、E2有相同的屬性名： 9.投影與笛卡爾積的交換 設(shè)A1,An是E1的屬性，B1,Bm是E2的屬性： 這個(gè)策略使投影在笛卡爾積之前先做 10.投影與并的交換 設(shè)E1和E2有相同的屬性名,100,2.5 查詢(xún)優(yōu)化,11.選擇對(duì)自然連接的分配律 如果F中涉及的都是E1的屬性： （1）F (E1 E2) F (E1 ) E2 如果F=F1F2，F(xiàn)1只涉及E1中的屬性，F(xiàn)2只涉及E2中的屬性： （2）F (E1 E2) F1 (E1 )