數(shù)據(jù)庫原理PPT.ppt

1、第4章 關(guān)系數(shù)據(jù)庫方法,本章主要內(nèi)容,本章將主要介紹關(guān)系數(shù)據(jù)數(shù)據(jù)庫的基本概念，關(guān)系運(yùn)算和關(guān)系表達(dá)式的優(yōu)化問題，其中關(guān)系運(yùn)算和關(guān)系表達(dá)式的優(yōu)化問題是本課程的重點(diǎn)內(nèi)容之一。關(guān)系運(yùn)算是關(guān)系數(shù)據(jù)模型的理論基礎(chǔ)。 （1）基本概念 關(guān)系形式定義，關(guān)鍵碼（主鍵和外鍵），三類完整性規(guī)則，關(guān)系模式、關(guān)系子模式和存儲(chǔ)模式 。 （2）關(guān)系代數(shù) 五個(gè)基本操作及其組合操作。 （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)化算法。,關(guān)系數(shù)據(jù)庫方法,4.1 關(guān)系數(shù)據(jù)庫的基本概念 4.2 關(guān)系代數(shù) 4.3 關(guān)

2、系演算 4.4 關(guān)系查詢優(yōu)化 本章小結(jié),4.1 關(guān)系數(shù)據(jù)庫的基本概念,4.1.1關(guān)系的形式化定義 4.1.2關(guān)系模式、關(guān)系子模式和存儲(chǔ)模式 4.1.3 關(guān)系模型的完整性規(guī)則 4.1.4 關(guān)系數(shù)據(jù)庫模式,4.1.1 關(guān)系的形式化定義(1),1）關(guān)系的集合表示 一個(gè)關(guān)系由若干個(gè)不同元組組成，因此，可把關(guān)系視為元組的集合。此外，關(guān)系中每個(gè)屬性都有其相應(yīng)的值域或簡(jiǎn)稱域(Domain)。 例如，學(xué)生性別的域是男，女，學(xué)生成績(jī)的域是0100的整數(shù)集合。,假設(shè)一組域，是由D1,D2，,Dn n個(gè)域組成。D1,D2，,Dn上的D1D2Dn定義為集合： D1D2Dn(d1 , d2, , ,dn) diDi，i

3、=1，2，n 其中:每個(gè)元素(d1，d2，dn)稱為一個(gè)元組。 若Di（i=1,2,n）為有限集，其基數(shù)為mi（i=1,2，n) 則D1D2Dn的基數(shù)為：,4.1.1 關(guān)系的形式化定義(2),【例4-1】設(shè)有二個(gè)域教師名域T胡恒，丁偉、課程名域CC語言，數(shù)據(jù)結(jié)構(gòu)，計(jì)算機(jī)原理，由T和C的笛卡兒積定義為集合： TC（胡恒，C語言），（胡恒，數(shù)據(jù)結(jié)構(gòu)），（胡恒，計(jì)算機(jī)原理）， （丁偉，C語言），（丁偉，數(shù)據(jù)結(jié)構(gòu)），（丁偉，計(jì)算機(jī)原理）,該笛卡兒積的基數(shù)為236，也就是說，TC一共236個(gè)元組.,4.1.1 關(guān)系的形式化定義(3),如果取該笛卡兒積的這六個(gè)元素，并將它們放到一張名為T_C的二維表中，,

4、顯然，這是一個(gè)關(guān)系。于是有下面的定義4-1。,4.1.1 關(guān)系的形式化定義(4),定義4-1：一個(gè)在域D1,D2，,Dn上的關(guān)系(Relation)就是笛卡兒積D1D2Dn的子集，用R(D1,D2，,Dn)表示,R D1D2Dn。 關(guān)系的成員為元組，即笛卡兒積的子集的元素(d1，d2，dn)。,例如，我們用教師名代替教師（假設(shè)無同名教師存在），用課程名代替課程，教師任教的課程可用關(guān)系TC（教師，課程）表示，它是教師名域和課程名域的笛卡兒積TC的子集，任一學(xué)期教師任教的課程記錄是這個(gè)關(guān)系的元組，如：,TC（胡恒，C語言），（丁偉，數(shù)據(jù)結(jié)構(gòu)）表示本學(xué)期胡恒老師上C語言課程，丁偉老師上數(shù)據(jù)結(jié)構(gòu)課程。

5、,4.1.1 關(guān)系的形式化定義(5),2）關(guān)系的一階謂詞表示 關(guān)系模型不但可以用關(guān)系代數(shù)表示，還可以用一階謂詞演算表示。,定義4-2：設(shè)有關(guān)系模式R，其原子謂詞表示形式為P (t)。其中，P是謂詞，t為個(gè)體變?cè)?，以元組為其表現(xiàn)形式。關(guān)系R(元組的集合)與謂詞P (t)之間的聯(lián)系描述為： RtP (t), 表示所有使謂詞P為真或滿足謂詞P的元組t都屬于關(guān)系R。 關(guān)系R與原子謂詞P之間的關(guān)系如下： P(t)True，t在R內(nèi), P(t)Fals，t不在R內(nèi)。,例：t姓名tStudent AND t.性別女 ,4.1.1 關(guān)系的形式化定義(6),可將關(guān)系看成是一張二維表格。,(1)關(guān)系（表）可以看成

6、是由行和列(5行和6列）交叉組成的二維表格。 (2)表中一行稱為一個(gè)元組。可用來表示實(shí)體集中的一個(gè)實(shí)體。 (3)表中的列稱為屬性，表中的屬性名不能相同。 (4)列的取值范圍稱為域，同列具有相同的域，不同的列可有相同的域 (5)表中任意兩行（元組）不能相同。能惟一標(biāo)識(shí)表中不同行的屬性或?qū)傩越M稱為主鍵。,4.1.1 關(guān)系的形式化定義(7),3）關(guān)鍵碼和表之間的聯(lián)系 在關(guān)系數(shù)據(jù)庫中，關(guān)鍵碼（簡(jiǎn)稱鍵）是關(guān)系模型的一個(gè)重要概念。通常鍵由一個(gè)或幾個(gè)屬性組成，通常有如下幾種鍵： (1)超鍵： 在一個(gè)關(guān)系中，能惟一標(biāo)識(shí)元組的屬性或?qū)傩约Q為關(guān)系的超鍵。 (2)候選鍵： 如果一個(gè)屬性集能唯一標(biāo)識(shí)元組，且又不含有

7、多余的屬性，那么這個(gè)屬性集稱為關(guān)系的候選鍵。 (3)主鍵： 若一個(gè)關(guān)系中有多個(gè)候選鍵，則選其中的一個(gè)為關(guān)系的主鍵。用主鍵實(shí)現(xiàn)關(guān)系定義中“表中任意兩行（元組）不能相同”的約束。包含在任何一個(gè)候選鍵中的屬性稱為主屬性，不包含在任何鍵中的屬性稱為非主屬性或非鍵屬性。,4.1.1 關(guān)系的形式化定義(8),例如：表4.1的關(guān)系中，設(shè)屬性集K=（職工編號(hào)，部門），雖然K能惟一標(biāo)識(shí)職工，但K只能是關(guān)系的超鍵，還不能作候選鍵使用。因?yàn)镵中“部門”是一個(gè)多余屬性，只有“職工編號(hào)”能惟一標(biāo)識(shí)職工。因而“職工編號(hào)”是一個(gè)候選鍵。 還有“身份證號(hào)”也可以是一個(gè)候選鍵。 另外，如果規(guī)定“不允許有同名同姓的職工”，那么“

8、姓名”也可以是一個(gè)候選鍵。 關(guān)系的候選鍵可以有多個(gè)，但不能同時(shí)使用，只能使用一個(gè)，譬如使用“職工編號(hào)”來標(biāo)識(shí)職工，那么“職工編號(hào)”就是主鍵了。,4.1.1 關(guān)系的形式化定義(9),(4)外鍵： 若一個(gè)關(guān)系R中包含有另一個(gè)關(guān)系S的主鍵所對(duì)應(yīng)的屬性集F,則稱F為R的外鍵。并稱關(guān)系S為參照關(guān)系，關(guān)系R為依賴關(guān)系。,例如，職工關(guān)系和部門關(guān)系分別為： 職工（職工編號(hào)，姓名，部門編號(hào)，性別，年齡，身份證號(hào)碼） 部門（部門編號(hào)，部門名稱，部門經(jīng)理）,職工關(guān)系的主鍵為職工編號(hào)，部門關(guān)系的主鍵為部門編號(hào)，在職工關(guān)系中，部門編號(hào)是它的外鍵。,4.1.2 關(guān)系模式、關(guān)系子模式和存儲(chǔ)模式,關(guān)系模型基本上遵循數(shù)據(jù)庫的三

9、級(jí)體系結(jié)構(gòu)。在關(guān)系模型中，概念模式是關(guān)系模式的集合，外模式是關(guān)系子模式的集合，內(nèi)模式是存儲(chǔ)模式的集合。,1）關(guān)系模式 關(guān)系模式是對(duì)關(guān)系的描述，它包括模式名，組成該關(guān)系的諸屬性名、值域名和模式的主鍵。具體的關(guān)系稱為實(shí)例。 一般形式是R(A1,A2，,An)，其中R是關(guān)系名, A1,A2，,An是該關(guān)系的屬性名。 例如關(guān)系模式T_C(T,C)。,4.1.2 關(guān)系模式、關(guān)系子模式和存儲(chǔ)模式,4.1.2 關(guān)系模式、關(guān)系子模式和存儲(chǔ)模式,關(guān)系模式是用數(shù)據(jù)定義語言(DDL)定義的。關(guān)系模式的定義包括：模式名、屬性名、值域名以及模式的主鍵。由于不涉及到物理存儲(chǔ)方面的描述，因此關(guān)系模式僅僅是對(duì)數(shù)據(jù)本身的特征的

10、描述。,4.1.2 關(guān)系模式、關(guān)系子模式和存儲(chǔ)模式,2）關(guān)系子模式 有時(shí)，用戶使用的數(shù)據(jù)不直接來自關(guān)系模式中的數(shù)據(jù)，而是從若干關(guān)系模式中抽取滿足一定條件的數(shù)據(jù)。這種結(jié)構(gòu)可用關(guān)系子模式實(shí)現(xiàn)。 關(guān)系子模式是用戶所需數(shù)據(jù)的結(jié)構(gòu)的描述，其中包括這些數(shù)據(jù)來自哪些模式和應(yīng)滿足哪些條件。,例如：用戶需要用到成績(jī)子模式G(SNO, SNAME, CNO, SCORE)。子模式G對(duì)應(yīng)的數(shù)據(jù)來源于表S和表SC,構(gòu)造時(shí)應(yīng)滿足它們的SNO值相等。子模式G的構(gòu)造過程如圖所示。,3）存儲(chǔ)模式 存儲(chǔ)模式描述了關(guān)系是如何在物理存儲(chǔ)設(shè)備上存儲(chǔ)的。關(guān)系存儲(chǔ)時(shí)的基本組織方式是文件。由于關(guān)系模式有鍵，因此存儲(chǔ)一個(gè)關(guān)系可以用散列方法或

11、索引方法實(shí)現(xiàn)。如果關(guān)系中元組數(shù)目較少（100以內(nèi)），那么也可以用堆文件方式實(shí)現(xiàn)此外，還可以對(duì)任意的屬性集建立輔助索引。,4.1.2 關(guān)系模式、關(guān)系子模式和存儲(chǔ)模式,SCORE,4.1.3 關(guān)系模型的完整性規(guī)則 (1),關(guān)系模型的完整性規(guī)則是對(duì)數(shù)據(jù)的約束。關(guān)系模型提供了三類完整性規(guī)則，實(shí)體完整性規(guī)則、參照完整性規(guī)則、用戶定義的完整性規(guī)則。其中實(shí)體完整性規(guī)則和參照完整性規(guī)則是關(guān)系模型必須滿足的完整性的約束條件，稱為關(guān)系完整性規(guī)則。,1）實(shí)體完整性規(guī)則 實(shí)體完整性規(guī)則：關(guān)系中元組的主鍵值不能為空。 2）參照完整性規(guī)則 在關(guān)系數(shù)據(jù)庫中，關(guān)系與關(guān)系之間的聯(lián)系是通過公共屬性實(shí)現(xiàn)的。這個(gè)公共屬性是一個(gè)表的主

12、鍵和另一個(gè)表的外鍵。外鍵必須是另一個(gè)表的主鍵的有效值，或者是一個(gè)“空值”。,4.1.3 關(guān)系模型的完整性規(guī)則 (2),例如，圖4.4所示研究生表的主鍵是學(xué)號(hào)，不包含空的數(shù)據(jù)項(xiàng)；導(dǎo)師表的主鍵是導(dǎo)師編號(hào)，也不包含空的數(shù)據(jù)項(xiàng)，所以，這兩個(gè)表都滿足實(shí)體完整性規(guī)則。,而學(xué)號(hào)為“98110”的研究生的導(dǎo)師編號(hào)為“318”，由于導(dǎo)師表中不存在導(dǎo)師編號(hào)“318”，所以這個(gè)值是非法的，違反了參照完整性規(guī)則 。,4.1.3 關(guān)系模型的完整性規(guī)則 (3),3）用戶定義的完整性規(guī)則 這是針對(duì)某一具體數(shù)據(jù)的約束條件，由應(yīng)用環(huán)境決定。它反映某一具體應(yīng)用所涉及的數(shù)據(jù)必須滿足的語義要求。系統(tǒng)應(yīng)提供定義和檢驗(yàn)這類完整性的機(jī)制，

13、以便用統(tǒng)一的系統(tǒng)方法處理它們，不再由應(yīng)用程序承擔(dān)這項(xiàng)工作。 例如學(xué)生成績(jī)應(yīng)該大于或等于零，職工的工齡應(yīng)小于年齡，等等。,4.1.4 關(guān)系數(shù)據(jù)庫模式(1),一個(gè)關(guān)系數(shù)據(jù)庫是多個(gè)關(guān)系的集合，這些具體關(guān)系構(gòu)成了關(guān)系數(shù)據(jù)庫的實(shí)例。由于每個(gè)關(guān)系都有一個(gè)模式，所以，構(gòu)成該關(guān)系數(shù)據(jù)庫的所有關(guān)系模式的集合構(gòu)成了關(guān)系數(shù)據(jù)庫模式。,例如，一個(gè)學(xué)生選課數(shù)據(jù)庫系統(tǒng)的模式有下面三個(gè)關(guān)系模式構(gòu)成： S(SNO，SNAME，SEX，AGE，DNAME) C(CNO，CNAME，PRE_CNO) SC(SNO，CNO，SCORE）,4.1.4 關(guān)系數(shù)據(jù)庫模式(2),關(guān)系數(shù)據(jù)庫管理系統(tǒng)一般向用戶提供四種基本數(shù)據(jù)操縱功能： (1

14、)數(shù)據(jù)檢索 數(shù)據(jù)檢索是指按照用戶指定的條件查詢一個(gè)關(guān)系內(nèi)的數(shù)據(jù)或多個(gè)關(guān)系間的數(shù)據(jù)。 (2)數(shù)據(jù)插入 在關(guān)系內(nèi)插入一些新的元組。 (3)數(shù)據(jù)刪除 在關(guān)系內(nèi)刪除一些元組。 (4)數(shù)據(jù)修改 該操作實(shí)際上可分解為兩個(gè)更基本的操作：先刪除要修改的元組，再將修改后的元組插入。,4.1.4 關(guān)系數(shù)據(jù)庫模式(3),上述四類數(shù)據(jù)操作的對(duì)象都是關(guān)系，這樣，對(duì)關(guān)系模型的數(shù)據(jù)操縱可描述為： （1）操縱對(duì)象是關(guān)系。 （2）基本操縱方式有五種： 屬性指定，指定一個(gè)關(guān)系內(nèi)的某些屬性，確定二維表中的列。主要用于檢索或定位。 元組選擇，用一個(gè)邏輯表達(dá)式給出一個(gè)關(guān)系中滿足此條件的那些元組，確定二維表中的行。主要用于檢索或定位。

15、關(guān)系合并，將兩個(gè)關(guān)系合并成一個(gè)關(guān)系。用以合并多張表，從而實(shí)現(xiàn)多張表間的檢索和定位。 元組插入。在一個(gè)關(guān)系中添加一些元組，用以完成數(shù)據(jù)插入或修改。 元組刪除。先確定所要?jiǎng)h除的元組，然后將它（們）刪除。用于數(shù)據(jù)刪除或修改。,4.2 關(guān)系代數(shù),4.2.1 關(guān)系代數(shù)的五個(gè)基本操作 4.2.2 關(guān)系代數(shù)的組合操作 4.2.3 關(guān)系代數(shù)表達(dá)式應(yīng)用舉例,4.2.1 關(guān)系代數(shù)的五個(gè)基本操作,關(guān)系代數(shù)操作集, , , 是個(gè)完備的操作集，任何其他關(guān)系代數(shù)操作都可以用這五種操作來表示。,設(shè)關(guān)系R和S具有相同結(jié)構(gòu)的關(guān)系模式，R和S的并是由屬于R或?qū)儆赟的元組構(gòu)成的集合，記為RS。形式定義如下： RSt | tR tS

16、，t是元組變量，R和S的元數(shù)相同。,例如：有庫存和進(jìn)貨兩個(gè)表（見下表），要將兩個(gè)表合并為一個(gè)表，可利用并運(yùn)算來實(shí)現(xiàn)。,1） 并（Union）,2）差（Difference）,設(shè)關(guān)系R和S具有相同結(jié)構(gòu)的關(guān)系模式，R和S的差是由屬于R但不屬于S的元組構(gòu)成的集合，記為RS。形式定義如下： RS t | tR t S，R和S的元數(shù)相同。,例如：有考生成績(jī)合格者名單和身體不合格名單兩個(gè)關(guān)系，按錄取條件將成績(jī)合格且身體健康的考生中產(chǎn)生錄取名單關(guān)系。,事例,3）笛卡兒積(Cartesian Product),例4.3:假定部門信息存放在表DEPTINFO中（見表4-6），則表MANAGER與表DEPTINF

17、O的笛卡兒積如表4.7所示。,笛卡兒積定義,設(shè)有關(guān)系R和S，它們分別是n目和m目關(guān)系（即它們的屬性個(gè)數(shù)分別為n和m），分別有p和q個(gè)元組。則關(guān)系R,S經(jīng)笛卡兒積運(yùn)算的結(jié)果T是一個(gè)nm目關(guān)系，共有pq個(gè)元組，這些元組是由R與S的元組組合而成的。,關(guān)系R與S的笛卡兒積記為RS，形式定義如下：,4）選擇運(yùn)算(Selection),這個(gè)操作是根據(jù)某些條件對(duì)關(guān)系做水平分割，即在一個(gè)關(guān)系內(nèi)選擇符合條件的元組稱為選擇運(yùn)算。選擇運(yùn)算可表示為： C（R）ttRCt=True,C表示邏輯條件表達(dá)式。這個(gè)表達(dá)式按以下規(guī)則組成： ，其中、是屬性名或常量，但、不能同為常量。是比較運(yùn)算符，它可以是、或。稱為基本邏輯條件。

18、 由若干基本邏輯條件經(jīng)過邏輯運(yùn)算（與）、（或）、（非）構(gòu)成復(fù)合邏輯條件。,選擇運(yùn)算事例,對(duì)表WORKER執(zhí)行下列選擇運(yùn)算：,5）投影(Project),這個(gè)操作是對(duì)一個(gè)關(guān)系進(jìn)行垂直分割，即對(duì)一個(gè)關(guān)系內(nèi)屬性的指定稱為投影運(yùn)算 。,設(shè)關(guān)系R有n個(gè)屬性：A1,A2，An，則對(duì)R上屬性Ai1 , i2，,Aim（AijA1,A2，An投影的結(jié)果記為：,對(duì)例4-2中的表WORKER執(zhí)行下列投影運(yùn)算： NAME,AGE（WORKER）、 DEPT(WORKER) 其結(jié)果如表所示。,投影運(yùn)算事例,c,關(guān)系代數(shù)操作的結(jié)果 （b）RS （c）RS （d）RS （e）C，A（R）（f）B=b（R）,事例,4.2.

19、2 關(guān)系代數(shù)的組合操作,1）交（intersection） 設(shè)關(guān)系R和S具有相同的元數(shù)n，相應(yīng)的屬性取自同一個(gè)域，則關(guān)系R和S的交記為RS，由既屬于R又屬于S的元組組成，其結(jié)果仍然一個(gè)n元關(guān)系。形式定義如下： RSttRtS,t是元組變量。,關(guān)系的交可以由關(guān)系的差來表示，即： RSR（RS）或RSS（SR）,例如：以上例中的WORKER和MANAGER為例，其交運(yùn)算WORKERMANAGER的結(jié)果表4-5（E）所示?？梢云浒床钸\(yùn)算WORKER（WORKERMANAGER）來計(jì)算，其結(jié)果分別如表4-5（E1）、表4-5（E2）所示。,交操作事例,2）連接(Join)運(yùn)算,就是說，連接操作是笛卡兒

20、積和選擇操作的組合。,（1）條件連接 條件連接運(yùn)算又可稱-連接，這是一個(gè)二目運(yùn)算，通過它將兩個(gè)關(guān)系合并成一個(gè)關(guān)系。設(shè)有關(guān)系S和n目關(guān)系R以及比較表達(dá)式ij ,其中i是R中的屬性,j是S的屬性, 含義同前（比較運(yùn)算符）。形式定義如下：,【例4.8】設(shè)關(guān)系EMP表4.14表示職工的年齡和工齡情況，關(guān)系ELIT表4.15表示一個(gè)職工工作年限和可以享受的福利級(jí)別。使用下列連接：,連接運(yùn)算事例,EMP ELIT,（2）自然連接(Natural Join),RS最常用的是-連接的一種特例，可以定義為: RS,RS計(jì)算的具體過程為: 計(jì)算RS； 設(shè)R和S的公共屬性是B1 , B2 , , Bn，挑選RS中滿

21、足 R.B1S.B1, R.BnS.Bn的那些元組； 去掉S.B1,S.Bn這些列（保留R.B1,R.Bn）。,【例4.9】查詢各部門經(jīng)理及他們所在部門的信息。該查詢可用一個(gè)自然連接運(yùn)算實(shí)現(xiàn)：MANAGER DEPTINFO，其查詢結(jié)果如表所示 。,自然連接事例,（3）半連接(SemiJoin),兩個(gè)關(guān)系R和S的半連接運(yùn)算定義為：,3）除法運(yùn)算(Division）,有關(guān)系R和S，R能被S除的條件有兩個(gè)： 一是R中的屬性包含S中的屬性； 二是R中的有些屬性不出現(xiàn)在S中。 R除以S表示為R/S或RS。 RS是由R中那些不出現(xiàn)在S中的屬性組成，其元組則是S中所有元組在R中對(duì)應(yīng)值相同的那些元組值。,除

22、法運(yùn)算計(jì)算過程,設(shè)有關(guān)系R和S的元數(shù)分別為r和s，則 RS是一個(gè)(r-s)元的元組集合，其計(jì)算過程如下： （a）T1,2,r-s（R） （b）W（TS）R （c）V1,2,r-s（W） （d）RSTV 即RS1,2,r-s（R）1,2,r-s（TS）R）,除法運(yùn)算不是基本運(yùn)算，它可由其他基本運(yùn)算推出。,除法運(yùn)算計(jì)算事例（SCC ）,4.2.3 關(guān)系代數(shù)表達(dá)式應(yīng)用舉例,關(guān)于教學(xué)數(shù)據(jù)庫的關(guān)系模式如下： S（SNO，SNAME，AGE，SEX，DNAME） C（CNO，CNAME，PRE_CNO，TEACHER） SC（SNO，CNO，SCORE）,（1）檢索“陳軍”老師所授課程的課程號(hào)（CNO）和

23、課程名（CNAME）,CNO, SNAME（TEACHER=陳軍（C）,（2）檢索年齡大于21的男學(xué)生學(xué)號(hào)（SNO）和姓名（SNAME）,SNO,SNAME（AGE21 SEX=男 （S）,（3）檢索至少選修“陳軍”老師所授全部課程的學(xué)生姓名（SNAME）,SNAME（S（SNO, CNO（SC） CNO（TEACHER=陳軍（C）,SNO, CNO（SC）CNO （CNO=k1 CNO=k5 （C）,應(yīng)用舉例,（4）檢索“李強(qiáng)”同學(xué)不學(xué)課程的課程號(hào)（CNO）,CNO（C）CNO（SNAME=李強(qiáng)（S）SC）,（5）檢索至少選修兩門課程的學(xué)生學(xué)號(hào)（SNO）,SNO（1=4 25 （SCSC）,

24、（6）檢索全部學(xué)生都選修的課程的課程號(hào)（CNO）和課程名（CNAME）,CNO, CNAME（C（SNO, CNO（SC）SNO（S）,（7）檢索選修課程包含“陳軍”老師所授課程之一的學(xué)生學(xué)號(hào)（SNO）,SNO（SCCNO（TEACHER=陳軍（C）,（8）檢索選修課程號(hào)為k1和k5的學(xué)生學(xué)號(hào)（SNO）,（9）檢索選修全部課程的學(xué)生姓名（SNAME）,SNAME（S（SNO, CNO （SC） CNO（C）,應(yīng)用舉例,（10）檢索選修課程包含學(xué)號(hào)為S2的學(xué)生所修課程的學(xué)生學(xué)號(hào)（SNO）,SNO, CNO（SC）CNO（SNO=S2（SC）,（11）檢索選修課程名為“C語言”的學(xué)生學(xué)號(hào)（SNO）

25、和姓名（SNAME）,SNO, SNAME（S（SNO（SC（CNAME=C語言（C）,（12）從關(guān)系SC中刪除課程號(hào)為“C2”的課程成績(jī),DELETETUPLECNO=C2（SC） SCSCDELETETUPLE,（13）將元組C6，數(shù)據(jù)庫原理及應(yīng)用，C4，胡拓插入課程關(guān)系C中,NEWTUPLEC6，數(shù)據(jù)庫原理及應(yīng)用，C4，胡拓 C = C NEWTUPLE,4.3 關(guān)系演算,把數(shù)理邏輯的謂詞演算引入到關(guān)系運(yùn)算中，就可得到以關(guān)系演算為基礎(chǔ)的運(yùn)算。 關(guān)系演算又可分為元組關(guān)系演算和域關(guān)系演算，前者以元組為變量，后者以屬性（域）為變量。 4.3.1 元組關(guān)系演算 4.3.2 域關(guān)系演算,4.3.1

26、 元組關(guān)系演算,在元組關(guān)系演算（Tuple Relational Calculus）中，元組關(guān)系演算表達(dá)式簡(jiǎn)稱為元組表達(dá)式，其一般形式為: t | P（t） 其中，t是元組變量，表示一個(gè)元數(shù)固定的元組；P是公式，在數(shù)理邏輯中也稱為謂詞，也就是計(jì)算機(jī)語言中的條件表達(dá)式。 t | P（t）表示滿足公式P的所有元組t的集合。,設(shè)r目關(guān)系R和s目關(guān)系S的謂詞分別為R(u)和S(v)，用它們表示并、差、選擇、投影和笛卡兒積如下： 1）并：RStR（t）S（t） 2）差：RStR（t） S（t） 3）選擇：F (R)tR（t）F 其中F是條件表達(dá)式F在謂詞演算中的表示形式。,4）投影： 5）笛卡兒積 ：,

27、下面首先介紹關(guān)系演算的原子公式定義，然后介紹關(guān)系演算公式定義。 定義4.3:關(guān)系演算的原子公式（簡(jiǎn)稱原子公式）定義如下： (1) 原子謂詞R(u)是原子公式，其中u為元組。 (2) uivj是原子公式，其中u和v為元組, 是比較運(yùn)算符。 (3) uia是原子公式，其中a是常量。 (4) 原子公式僅有上面三種定義方式。,定義4.4：關(guān)系演算公式（簡(jiǎn)稱公式）遞歸定義如下： (1) 每個(gè)原子公式都是一個(gè)公式。 (2) 如果1、2是公式，則12、12、1也都是公式。 (3) 如果是公式，中有元組變量t，則(t)()、(t)()均為公式。 (4) 公式僅由上面三種定義方式。,在公式中運(yùn)算符的優(yōu)先次序?yàn)椋?/p>

28、 比較運(yùn)算符最高 量詞、次之， 否定符再次之，最后是（與或）運(yùn)算。 加括號(hào)時(shí)，括號(hào)中運(yùn)算優(yōu)先。,元組關(guān)系演算表達(dá)查詢事例,設(shè)有關(guān)系模式S(S#,SN,SEX,SA,SD) 例4.11：列出計(jì)算機(jī)科學(xué)系CS的所有學(xué)生：,例4.12：列出所有年齡大于或等于20的學(xué)生：,例4.13：求學(xué)生姓名及所在的系：,例4.14：設(shè)有關(guān)系模式R(A,B,C)和S(B,E)，用元組關(guān)系演算表示連接運(yùn)算如下:,元組關(guān)系演算事例,例:下圖的（a）、（b）是關(guān)系R和S，（c）（g）分別是下面五個(gè)元組表達(dá)式的值,元組關(guān)系演算的例子,R1 = t | S（t）t12 R2 = t | R（t）S（t） R3 = t |（u

29、）（S（t）R（u）t3u1）,R5 = t |(u)(v)(R(u) S(v) t1=u2t2=v3 t3=u1u1v2),4.3.2 域關(guān)系演算,域演算的運(yùn)算符基本上與元組關(guān)系演算相同，主要區(qū)別是公式中的變?cè)辉偈窃M而是元組分量的域，簡(jiǎn)稱域變量。 域演算表達(dá)式的形式是： X1，X2，Xk（X1，X2，Xk）,原子公式有三類： (1) R（X1，X2，Xk）,R是K元關(guān)系，Xi是域變量或常量。R（X1，X2，Xk）表示由分量X1，X2，Xk組成的元組屬于R。 (2) XY，X、Y是域變量,是算術(shù)比較符，XY表示X與Y滿足比較關(guān)系。 (3) Xc或cX,這里c為常數(shù)，表示域變量x與常數(shù)c之間

30、滿足比較關(guān)系。,域關(guān)系演算事例,例：下圖（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 域關(guān)系演算的例子,R1= xyz| R（xyz） x3 R2= xyz| R（xyz）（S（xyz） y = 4） R3= xyz|（u）（v）（R（zxu） W（yv） uv ）,4.4 關(guān)系查詢優(yōu)化,查詢是數(shù)據(jù)庫的最基本、最常用、最復(fù)雜的操作。 數(shù)據(jù)庫的查詢一般從查詢語句出發(fā)，直到獲得查詢結(jié)果，需要一個(gè)處理過程，這個(gè)過程叫做查詢處理。 在關(guān)系數(shù)據(jù)庫的查詢中用戶不必關(guān)心查詢語言的

31、具體執(zhí)行過程，而由DBMS確定合理的、有效的執(zhí)行策略，稱為查詢優(yōu)化。,4.4.1 查詢優(yōu)化的一般策略,(1)盡可能早地執(zhí)行選擇、投影等一目運(yùn)算。 (2)把先做笛卡兒積，后做選擇結(jié)合起來，使之成為一個(gè)連接運(yùn)算。 (3)同時(shí)計(jì)算一串選擇和一串投影運(yùn)算，以免分開運(yùn)算造成多次掃描文件。 (4)找出表達(dá)式里的公共子表達(dá)式。 (5)適當(dāng)?shù)念A(yù)處理。 (6)把投影同其前面的雙目運(yùn)算結(jié)合起來，沒有必要為了去掉某一個(gè)或某幾個(gè)屬性而掃描一遍關(guān)系。,4.4.2關(guān)系代數(shù)優(yōu)化,1）表達(dá)式的求值 兩個(gè)等價(jià)的關(guān)系代數(shù)表達(dá)式E1和E2等價(jià)，記為E1=E2，就是說，當(dāng)兩個(gè)表達(dá)式中的同名變量代入相同關(guān)系后產(chǎn)生相同結(jié)果。基于這一定義

32、，可得到許多代數(shù)表達(dá)式的等價(jià)轉(zhuǎn)換規(guī)則。 第一種定義：關(guān)系是一個(gè)k一元組(k -tuples )的集合，其中k是固定的。兩個(gè)關(guān)系相等，當(dāng)且僅當(dāng)有相同的元組集合。 第二種定義：關(guān)系是從屬性名到其值域的映射的集合；按這種定義，如果兩個(gè)關(guān)系有相同的映射集，它們是相等的。,2）關(guān)系代數(shù)等價(jià)變換規(guī)則,連接和笛卡兒積的交換律,連接和笛卡兒積的結(jié)合律,(E1 E2) E3E1 (E2 E3),E1E2E2E1,等價(jià)變換規(guī)則,投影的串接,選擇的串接,選擇和投影的交換,其中：,更一般地，如果F1只涉及到E1中的屬性，而F2涉及到E1和E2兩者的屬性,則：,等價(jià)變換規(guī)則,(6)選擇移入笛卡兒積 如果F中所涉及的屬性

33、都在E1中，那么 :,如果F是F1 F2形式，并且F1只涉及E1中的屬性,F2只涉及E2的屬性,則：,等價(jià)變換規(guī)則,選擇與并運(yùn)算交換,選擇與差運(yùn)算交換,投影移入笛卡兒積 設(shè)A1，,An是E1的屬性，中出現(xiàn)的B1，Bm是E2的屬性，則：,投影移入并運(yùn)算,3）代數(shù)優(yōu)化的算法,下面給出一個(gè)通用的優(yōu)化算法： 優(yōu)先應(yīng)用單項(xiàng)的選擇和投影； 優(yōu)先應(yīng)用一般選擇和投影； 對(duì)笛卡兒積、并運(yùn)算、差運(yùn)算，若它們前面加有選擇和投影，則先做選擇和投影。,優(yōu)化算法,算法：關(guān)系表達(dá)式的優(yōu)化 輸入：表示關(guān)系代數(shù)表達(dá)式的語法分析樹 輸出：計(jì)算這個(gè)表達(dá)式的程序 方法：(1)使用規(guī)則把形式為 的選擇變成選擇串接的形式： (2)對(duì)每個(gè)

34、選擇用規(guī)則 ，盡可能地將選擇向樹的葉端移動(dòng)。 (3)對(duì)每個(gè)投影，利用規(guī)則，和一般化規(guī)則，將投影盡可能地向樹的葉端移動(dòng)。 (4)利用規(guī)則把串接的選擇和投影組合為一個(gè)選擇、一個(gè)投影或帶投影的選擇。 (5)把所得到的樹的內(nèi)部結(jié)點(diǎn)劃分成組。,圖書管理數(shù)據(jù)庫，其關(guān)系如下： BOOKS (LC_NO , TITLE，AUTHOR，PNAME） PUBLISHERS (PNAME，PADDR，PCITY) BORROWERS (CARD_NO, NAME，ADDR，CITY) LOANS(CARD_NO，LC_NO，DATE) 為了解借書情況，我們定義一個(gè)關(guān)系XLOANS存放借書信息。XLOANS是關(guān)系BO

35、OKS,BORROWERS和LOANS的自然連接，即： 其中,F是條件表達(dá)式： BORROWERS.CARD_NO=LOANS.CARD_NO BOOKS.LC_NO=LOANS.LC_NO S是投影表達(dá)式： TITLE,AUTHOR,PNAME,LC_NO,NAME,ADDR,CITY,CARD_NO,DATE,表達(dá)式的語法分析樹,BORROWERS.CARD_NO=LOANS.CARD_NO BOOKS.LC_NO=LOANS.LC_NO分解成 BORROWERS.CARD_NO=LOANS.CARD_NO和BOOKS.LC_NO=LOANS.LC_NO兩個(gè)運(yùn)算 將三個(gè)選擇盡可能向樹葉端移

36、動(dòng) 將該語法樹中的兩個(gè)投影合并為一個(gè)投影運(yùn)算 。,選擇下移且合并投影后的語法樹,在上面的笛卡兒積運(yùn)算乘積之下增加一個(gè)投影運(yùn)算： TITLE, NAME, BOOKS.LC_NO, LOANS.LC_NO 并將投影替換分解成兩個(gè)投影，一個(gè)是作用在BOOKS上： TITLE, BOOKS.LC_NO 另一個(gè)是作用在笛卡兒積右邊： NAME, LOANS.LC_NO,進(jìn)一步優(yōu)化后的語法樹,最下面的笛卡兒積運(yùn)算運(yùn)算前增加兩個(gè)投影運(yùn)算： NAME, BORROWERS.CARD_NO LOANS.LC_NO，LOANS.CARD_NO,最后的語法樹,4.4.3 基于存取路徑的規(guī)則優(yōu)化,1）選擇操作的實(shí)現(xiàn)

37、和優(yōu)化 選擇條件分為等值、范圍和集合三種。 選擇操作的實(shí)現(xiàn)方式： 順序掃描 索引技術(shù) 無序索引 排序索引 多屬性索引 散列技術(shù),排序和簇集雖然對(duì)某些查詢有利，但在插入新元組時(shí)，要移動(dòng)其他元組，而且修改該關(guān)系上的所有索引，就十分費(fèi)時(shí)了。 關(guān)系只對(duì)按排序或簇集的這個(gè)屬性上進(jìn)行查詢有利，而對(duì)其他屬性上的查詢沒有什么好處，還要額外地增加索引維護(hù)的開銷。,(1)如果是小關(guān)系，則直接使用順序掃描，不考慮其他存取路徑。 (2)如果無索引或散列等存取路徑可用，使用順序掃描。 (3)對(duì)于主關(guān)鍵字等值查找，如果最多只有一個(gè)元組中選，則優(yōu)先采用主關(guān)鍵字上的索引或散列。 (4)對(duì)于非主屬性等值查找，若選中元組個(gè)數(shù)在關(guān)

38、系中所占的比例。小于20，使用無序索引，否則，使用簇集索引或順序掃描。 (5)對(duì)于范圍查找，可以先通過索引找到范圍的邊界，再沿索引順序集搜索。 (6)對(duì)于用AND連接的合取條件，最好使用相應(yīng)的多屬性索引。 (7)對(duì)于用OR連接的析取條件表達(dá)式，只能按各個(gè)子條件分別選出相應(yīng)的元組集合，然后計(jì)算這些元組集的并。 (8)因?yàn)椴捎盟饕Y(jié)構(gòu)能夠提高檢索速度，所以，只要有可能，應(yīng)優(yōu)先使用索引查找。,選擇操作的啟發(fā)式規(guī)則,2）連接操作的實(shí)現(xiàn)和優(yōu)化,（1）嵌套循環(huán)(Nested Loop）法 對(duì)于R的每個(gè)元組，S要順序掃描一次。 嵌套循環(huán)算法: *設(shè)R有n個(gè)元組，S有m個(gè)元組* (1) i1，j1 (2) w

39、hile (in) (3) dowhile (jm) (4) doif R(i)AS (j)B (5) then輸出R(i),S(j)至T; (6) jj1 (7) j1，ii1; *T為R,S連接的結(jié)果*,以R為外關(guān)系，S為內(nèi)關(guān)系，用嵌套循環(huán)法進(jìn)行連接時(shí)所需訪問的物理塊數(shù)為： 若以S為外關(guān)系,R為內(nèi)關(guān)系，則所需訪問的物理塊數(shù)為： 其中：bR,bS分別為分配給R和S的物理塊數(shù),nB為可供連接用的緩沖塊數(shù),（2）利用索引或散列尋找匹配元組法,如果內(nèi)關(guān)系有合適的存取路徑（例如索引或散列），則可以考慮使用這些存取路徑取代順序掃描，以減少I/O次數(shù)，尤其當(dāng)連接屬性上有簇集索引或散列時(shí)，最為有利。 如果

40、連接屬性中只有無序索引，在一般情況下要比嵌套循環(huán)法好，但不如簇集索引和散列那樣效果顯著。 尤其當(dāng)可供連接用的緩沖塊增多時(shí)內(nèi)關(guān)系的掃描次數(shù)將減少，每次循環(huán)從內(nèi)關(guān)系所選的匹配元組數(shù)將增大，當(dāng)每次循環(huán)所選的匹配元組數(shù)在內(nèi)關(guān)系中占有較大比例（例如20）時(shí)，用無序索引還不如順序掃描。,（3）排序歸并法,排序歸并示意圖,排序歸并算法,(1) i1，j1; (2) while(in) and (jm) (3) doif R(i)AS(j)B (4) then jj1; (5) else if R(i)A至T; (12) pp1; *輸出S(j)與R中除R(i)外的其他元組所組成的連接元組* (13) ki1

41、； (14) while (kn) and (R(k) A=S (j) B) (15) do輸出至T; (16) kk1； (17) ii1，jj1； (18) ,（4）散列連接法(Hash Join),當(dāng)連接屬性R.A和S.B具有相同的域時(shí)，可以用A、B作為R、S的散列鍵，并用相同的散列函數(shù)把R和S散列到同一散列文件中。符合連接條件的R和S的元組必然位于同一桶中，但同一桶中的R和S的元組未必都滿足連接條件。 只要把桶中所有匹配的元組取出，就可以獲得連接的結(jié)果。 散列連接法的關(guān)鍵是要建立一個(gè)供連接用的散列文件。 建立散列文件時(shí)，也可以在桶中不填入R、S的實(shí)際元組，而代之以它們的tid（元組標(biāo)識(shí)

42、）?？扇〕鯝（R）和B(S)附在相應(yīng)的tid后。 在連接時(shí)，以桶為單位，按A（R）B(S)條件找出匹配的tid對(duì)，在得到匹配的tid對(duì)后，可按tid對(duì)中的tid取出元組進(jìn)行連接。,連接方法的啟發(fā)式規(guī)則,如果兩個(gè)關(guān)系都已按連接屬性排序，則優(yōu)先用排序歸并法。如果兩個(gè)關(guān)系中已有一個(gè)關(guān)系按連接屬性排序，另一個(gè)關(guān)系很小，方可考慮對(duì)此未排序的關(guān)系按連接屬性排序，再用排序歸并法連接。 如果兩個(gè)關(guān)系中有一個(gè)關(guān)系在連接屬性上有索引（特別是簇集索引）或散列，則可令另一關(guān)系為外關(guān)系，順序掃描，并利用內(nèi)關(guān)系上的索引或散列尋找其匹配元組，以代替多遍掃描。 如果應(yīng)用上述兩規(guī)則的條件都不具備，且兩個(gè)關(guān)系都比較小，可以用嵌套循環(huán)法。 如果、規(guī)則都不適用，可用散