1,第一章集合與關(guān)系在計(jì)算機(jī)科學(xué)中的應(yīng)用,1-2,集合論分為兩種體系：一種是樸素集合論體系，也稱為康托集合論體系；另一種是公理集合論體系。自從19世紀(jì)末著名德國(guó)數(shù)學(xué)家康托（Cantor,18451918）創(chuàng)立集合論，迄今已有100多年的歷史，集合的概念已深入到現(xiàn)代科學(xué)的各個(gè)方面，成為表達(dá)各種科學(xué)概念的必不可少的“數(shù)學(xué)語(yǔ)言”，然而有趣的是，集合本身卻是一個(gè)不能精確定義的基本概念，但這并不妨礙我們對(duì)它的理解和使用。,1-3,集合論的特點(diǎn)是研究對(duì)象的廣泛性，人們把研究的對(duì)象視作一個(gè)集合，本意可以是包羅萬(wàn)象的，但是最早所研究多半是分析數(shù)學(xué)的“數(shù)集”和幾何學(xué)的“點(diǎn)集”。而集合中的元素真正成為包羅萬(wàn)象的對(duì)象，應(yīng)當(dāng)說(shuō)是從“計(jì)算機(jī)革命”開始：數(shù)字、符號(hào)、圖像、語(yǔ)音以及光、電、熱各種信息，它們都可以作為“數(shù)據(jù)”，這些數(shù)據(jù)就構(gòu)成集合。,1-4,集合論總結(jié)出由各種對(duì)象構(gòu)成的集合的共同性質(zhì)，并用統(tǒng)一的方法來(lái)處理。正因?yàn)槿绱耍险摫粡V泛應(yīng)用于各種科學(xué)和技術(shù)領(lǐng)域。由于集合論的語(yǔ)言適合于描述和研究離散對(duì)象及其關(guān)系，因此它是計(jì)算機(jī)科學(xué)與工程的理論基礎(chǔ)，它在程序設(shè)計(jì)、形式語(yǔ)言、關(guān)系數(shù)據(jù)庫(kù)、操作系統(tǒng)等計(jì)算機(jī)學(xué)科中得到廣泛地應(yīng)用。集合論的原理和方法成為名符其實(shí)的數(shù)學(xué)技術(shù)。,1-5,關(guān)系和函數(shù)是數(shù)學(xué)中的最重要的兩個(gè)概念。在計(jì)算機(jī)科學(xué)的各個(gè)分支中，它們也是應(yīng)用極為廣泛的概念。人與人之間有父子、兄弟、同學(xué)關(guān)系；兩數(shù)之間有大于、等于、小于關(guān)系；元素與集合之間有屬于關(guān)系；計(jì)算機(jī)程序間有調(diào)用關(guān)系。集合論為刻畫這種聯(lián)系提供了一種數(shù)學(xué)模型關(guān)系，它仍然是一個(gè)集合，以那種具有聯(lián)系的對(duì)象組合為其成員。例如，在關(guān)系數(shù)據(jù)庫(kù)模型中，每個(gè)數(shù)據(jù)庫(kù)都是一個(gè)關(guān)系。計(jì)算機(jī)程序的輸入和輸出構(gòu)成一個(gè)二元關(guān)系。在各種計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言中，關(guān)系和函數(shù)都是必不可少的概念。,1-6,如何在計(jì)算機(jī)上表示有限集合的子集,下面介紹一種二進(jìn)制編碼方法：我們?cè)诒硎疽粋€(gè)集合時(shí)，元素的排列順序是無(wú)關(guān)緊要的，但是為了便于在計(jì)算機(jī)上操作，有時(shí)我們給元素排定順序，這樣就可以用二進(jìn)制數(shù)為足碼表示任意集合的子集，這種方法稱為子集的編碼表示法。,1-7,設(shè)集合Aa1，a2，an，用Bxxx表示A的一個(gè)子集，其中B是子集的符號(hào)，足碼xxx是n位二進(jìn)制數(shù)，n是集合A的基數(shù)，對(duì)于A，如果子集含有ai，則在足碼的第i位上記入1，否則為0。所以P(A)=Bk0k2n-1也可將Bi的二進(jìn)制數(shù)換算成十進(jìn)制數(shù)。,1-8,【例1.1.4】設(shè)A=a,b,c，則各子集的編碼表示為=B000=B0，a=B100=B4b=B010=B2，c=B001=B1a,b=B110=B6a,c=B101=B5b,c=B011=B3a,b,c=B111=B7,1-9,關(guān)系在計(jì)算機(jī)科學(xué)中的應(yīng)用,一、概念數(shù)據(jù)庫(kù)是計(jì)算機(jī)管理數(shù)據(jù)的一種結(jié)構(gòu)，一般講，它需要兩部分組成，一個(gè)是供存放數(shù)據(jù)用的大量存儲(chǔ)空間，它們可以是磁盤，磁帶等外存空間，另一個(gè)是管理數(shù)據(jù)庫(kù)中數(shù)據(jù)的一組程序，這組程序叫數(shù)據(jù)庫(kù)管理系統(tǒng)，簡(jiǎn)稱DBMS，用戶可以通過(guò)數(shù)據(jù)庫(kù)管理系統(tǒng)所提供的語(yǔ)言使用數(shù)據(jù)庫(kù)中的數(shù)據(jù)，這種使用包括下列幾個(gè)方面：,1-10,DBMS的一些基本功能,(1)數(shù)據(jù)的檢索：從數(shù)據(jù)庫(kù)中取出滿足一定條件要求的數(shù)據(jù)；(2)數(shù)據(jù)插入：將一些數(shù)據(jù)存儲(chǔ)到數(shù)據(jù)庫(kù)中供以后使用；(3)數(shù)據(jù)的修改：修改數(shù)據(jù)庫(kù)中指定的數(shù)據(jù)；(4)數(shù)據(jù)的刪除：刪除數(shù)據(jù)庫(kù)內(nèi)指定的數(shù)據(jù)。,1-11,數(shù)據(jù)庫(kù)內(nèi)數(shù)據(jù)的基本組織格式如下：,(1)實(shí)體：實(shí)體是數(shù)據(jù)庫(kù)中數(shù)據(jù)的基本存放單位，如職工的簡(jiǎn)歷、工資單、課程概貌、庫(kù)存情況等均是實(shí)體，數(shù)據(jù)庫(kù)內(nèi)實(shí)體是一個(gè)整體，它內(nèi)部的數(shù)據(jù)相互間是邏輯聯(lián)系的。(2)屬性：實(shí)體都有一些性質(zhì)，這些性質(zhì)叫作此實(shí)體的屬性，如職工簡(jiǎn)歷這個(gè)實(shí)體就有姓名、性別和年齡等屬性，所有實(shí)體的屬性就組成這個(gè)實(shí)體，如職工簡(jiǎn)歷這個(gè)實(shí)體實(shí)際上就由上述屬性組成。,1-12,(3)屬性域：實(shí)體的每個(gè)屬性的表現(xiàn)形式都是統(tǒng)一的，如姓名是由n個(gè)字母所組成的字符串，性別為M，F(xiàn)中之一(M代表男性，F(xiàn)代表女性)，年齡由兩個(gè)數(shù)字所組成。對(duì)于每個(gè)屬性它都有一個(gè)表示范圍(即取值范圍)。(4)聯(lián)系：在數(shù)據(jù)庫(kù)中實(shí)體是基本數(shù)據(jù)單位，但是各實(shí)體間是有一定聯(lián)系的，如實(shí)體學(xué)生與課程之間有聯(lián)系，這個(gè)聯(lián)系是學(xué)生修讀課程，教師也是實(shí)體，而教師與學(xué)生、課程也有聯(lián)系。,1-13,在數(shù)據(jù)庫(kù)中存儲(chǔ)數(shù)據(jù)時(shí)不僅要存放實(shí)體的數(shù)據(jù)，而且要存放聯(lián)系的數(shù)據(jù)，如上例中，不僅要存放有關(guān)教師、學(xué)生、課程的實(shí)體，而且還要存放學(xué)生修讀何種課程的情況及教師教授何種課程的情況，只有這樣數(shù)據(jù)庫(kù)中的這個(gè)數(shù)據(jù)庫(kù)中的這個(gè)數(shù)據(jù)信息才是完整的。數(shù)據(jù)庫(kù)目前可以三種結(jié)構(gòu)模型，它們分別叫層次模型、網(wǎng)絡(luò)模型和關(guān)系模型。,1-14,關(guān)系數(shù)據(jù)庫(kù),在關(guān)系數(shù)據(jù)庫(kù)中數(shù)據(jù)按二維表的形式存放，這種二維表就叫關(guān)系，數(shù)據(jù)庫(kù)中的實(shí)體與聯(lián)系按這種二維表的形式存放。,1-15,二維表的形式如表1所示，它包括有行和列。一張二維表可有m行n列，二維表的每一行叫元組(記錄)，它代表一個(gè)完整的數(shù)據(jù)，一個(gè)元組有n個(gè)分量，因此這個(gè)元又叫n元組。二維表的每一列表示數(shù)據(jù)的分量。這種二維表叫n元關(guān)系。表1二維表的形式,m列,1-16,設(shè)一個(gè)實(shí)體A有n個(gè)屬性，分別為A1,A2,A3,An，它可表示如下：A(A1,A2,A3,An)這個(gè)實(shí)體可以允許存放m個(gè)數(shù)據(jù)，此時(shí)這個(gè)實(shí)體可用一個(gè)關(guān)系來(lái)表示，亦即可用一張二維表來(lái)表示，這張二維表的每一列是一個(gè)屬性，二維表的每一行可存放實(shí)體中一個(gè)數(shù)據(jù)，這個(gè)表示實(shí)體的二維表見(jiàn)表2。表2實(shí)體A的關(guān)系,m行,1-17,二、具體例子,例1.1設(shè)有實(shí)體學(xué)生概貌，它有四個(gè)屬性：學(xué)號(hào)、姓名、年齡和所屬系名，這個(gè)實(shí)體存放10學(xué)生的概貌，它們可用下列關(guān)系(即二維表3)表示。,1-18,又設(shè)有實(shí)體課程的概況，它有三個(gè)屬性：課程編號(hào)、課程名和先修課程號(hào)，我們假定每門課的先修課只有一門，這個(gè)實(shí)體存放六門課的概況，它們可用表4表示。表4課程概況表C,1-19,實(shí)體與實(shí)體間的聯(lián)系也可用關(guān)系表示，如學(xué)生修讀課程的情況可用學(xué)號(hào)與課程號(hào)構(gòu)成一個(gè)新關(guān)系SC，它刻劃學(xué)生修課情況，這個(gè)關(guān)系可用二維表表5表示。,1-20,1-21,從上面表示可以看出，數(shù)據(jù)實(shí)體與聯(lián)系均可用二維表表示，在數(shù)據(jù)庫(kù)中，用這種二維表構(gòu)造數(shù)據(jù)的模型就是關(guān)系數(shù)據(jù)庫(kù)。它是由E.F.Cold于1970年提出的。用戶使用關(guān)系數(shù)據(jù)庫(kù)就是對(duì)一些二維表進(jìn)行檢索、插入、修改和刪除等操作，關(guān)系數(shù)據(jù)庫(kù)的DBMS必須向用戶提供使用數(shù)據(jù)庫(kù)的語(yǔ)言，一般稱為數(shù)據(jù)子語(yǔ)言，這種語(yǔ)言目前是以關(guān)系代數(shù)或謂詞邏輯中方法表示的，更確切說(shuō)就是這種語(yǔ)言以關(guān)系代數(shù)或謂詞邏輯作為它的數(shù)學(xué)基礎(chǔ)。,1-22,由于可用數(shù)學(xué)的方法來(lái)表示，使得對(duì)數(shù)據(jù)子語(yǔ)言的研究成為對(duì)數(shù)與謂詞邏輯的化簡(jiǎn)問(wèn)題。而引入數(shù)學(xué)表示方法，使得關(guān)系數(shù)據(jù)庫(kù)具有比其它幾種數(shù)據(jù)庫(kù)較為優(yōu)越的條件，正因?yàn)槿绱耍P(guān)系數(shù)據(jù)庫(kù)近幾年發(fā)展迅速，成為最有前途最有希望的一種數(shù)據(jù)庫(kù)，目前已基本上代替其它類型的數(shù)據(jù)庫(kù)。當(dāng)今流行的各種大型網(wǎng)絡(luò)數(shù)據(jù)庫(kù)如：Sybase、Oracle、Informix、Foxpro等都是屬于關(guān)系型數(shù)據(jù)庫(kù)。關(guān)系數(shù)據(jù)庫(kù)已成為數(shù)據(jù)庫(kù)中最有實(shí)用價(jià)值和理論價(jià)值的數(shù)據(jù)庫(kù)。,1-23,三、關(guān)系代數(shù)與數(shù)據(jù)子語(yǔ)言,關(guān)系數(shù)據(jù)庫(kù)的數(shù)據(jù)子語(yǔ)言，它的基本操作對(duì)象是二維表，它的基本操作有檢索、插入、修改與刪除，為了用數(shù)學(xué)的方法表示語(yǔ)言，有必要對(duì)其操作對(duì)象與基本操作加以研究，并將其抽象成數(shù)學(xué)符號(hào)與運(yùn)算。1.二維表與n元有序組集合二維表是數(shù)據(jù)子語(yǔ)言的操作對(duì)象，一張二維表可看成若干元組的集合，而n元元組可視為一個(gè)n元有序組，因此一張二維表可看成是n元有序組的集合，因此我們說(shuō)，數(shù)據(jù)子語(yǔ)言的操作對(duì)象是n元有序組的集合。,1-24,2.基本操作與集合運(yùn)算,數(shù)據(jù)子語(yǔ)言的操作對(duì)象是集合，而對(duì)其對(duì)象操作可視為對(duì)集合的運(yùn)算。(1)檢索與集合運(yùn)算對(duì)一張二維表的檢索不外乎選擇表中滿足某些條件和一些行和列。例如對(duì)表3表示的學(xué)生花名冊(cè)S，要求年齡大于21歲的學(xué)生的學(xué)號(hào)與姓名，這是一種檢索，它要求選擇滿足“年齡21”的那些行，再由這些行中選出屬性學(xué)號(hào)與姓名，這種檢索操作的結(jié)果還是一張二維表，這張二維表有兩個(gè)屬性以及一些滿足“年齡21”的行，可用表6表示。,1-25,由此可見(jiàn)，檢索是由一張表到另一張表的操作，從數(shù)學(xué)觀點(diǎn)看，檢索是一種一元運(yùn)算，即一個(gè)集合通過(guò)此運(yùn)算而得到另一個(gè)集合。下面我們就定義兩種一元檢索運(yùn)算，一個(gè)叫選擇(Select)，另一個(gè)叫投影(Project)。,表6年齡21的學(xué)生,1-26,投影運(yùn)算(ProjectingOperation),定義1.1設(shè)有關(guān)系R，它由m個(gè)n元元組組成，則也是一個(gè)關(guān)系，它由m個(gè)k元元組組成，其各元組由屬性組成，這個(gè)運(yùn)算叫做R在屬性上的投影運(yùn)算(ProjectingOperation)。可見(jiàn)投影運(yùn)算是從二維表中選擇一些指定列而組成的新表。見(jiàn)下面兩個(gè)例子：,1-27,例1.2打印全體學(xué)生名單。解：將這要求寫為姓名(學(xué)生花名冊(cè)S)例1.3打印所有課程編號(hào)與課程名。解：將此要求寫為課程編號(hào)，課程名(課程概況表C)上述詳細(xì)內(nèi)容見(jiàn)表7和表8,1-28,表7全體學(xué)生名單,表8,1-29,選擇運(yùn)算(SelectingOperation),定義1.2設(shè)有關(guān)系R，則F(R)也是關(guān)系，它由R中滿足條件F的元組所組成，F(xiàn)為邏輯條件，它是一個(gè)命題公式，它按下列方法組成：它的基本操作數(shù)是常量或元組分量(即屬性)；由基本操作數(shù)通過(guò)比較運(yùn)算：，而構(gòu)成命題；由命題通過(guò)命題聯(lián)結(jié)詞(與)，(或)，(非)構(gòu)成新命題。這種運(yùn)算叫做R的選擇運(yùn)算(SelectingOperation),1-30,所以選擇運(yùn)算是從二維表中選出那些滿足條件F的元組而組成的新表，即從二維表中選擇滿足條件F的行而組成。例1.4取出年齡大于21的數(shù)學(xué)系學(xué)生的概況。年齡21系名=數(shù)學(xué)系(學(xué)生花名冊(cè)S)例1.5取出先修課程為05的課程概況。先修課程號(hào)=05(課程概況表C)上述結(jié)果見(jiàn)表9和表10。,1-31,表9年齡大于21的數(shù)學(xué)系學(xué)生的概況,表10先修課程為05的課程概況,1-32,將運(yùn)算和F聯(lián)合應(yīng)用于關(guān)系就可以從關(guān)系中檢索出所要求的任意行與列的內(nèi)容。例如：例1.6取出材料系學(xué)生的學(xué)號(hào)與姓名。學(xué)號(hào)，姓名系名=材料系(學(xué)生花名冊(cè)S)見(jiàn)表11,1-33,表11材料系學(xué)生,1-34,我們可以用兩個(gè)二元運(yùn)算和F檢索一張二維表的內(nèi)容，由于各實(shí)體之間是有聯(lián)系的(即各表之間是有聯(lián)系的)，因此我們可以檢索與幾張表有關(guān)的內(nèi)容。例如我們可以檢索學(xué)生林麗梅選修的課程編號(hào)，這種檢索就涉及到兩張表，一張是學(xué)生花名冊(cè)S，另一張是選課表SC。對(duì)于這種檢索，上述一元運(yùn)算已經(jīng)無(wú)法滿足，我們需要引入另外的新的運(yùn)算，即笛卡兒乘積。,1-35,定義1.3設(shè),為集合，用中元素為第一元素，中元素為第二元素構(gòu)成有序?qū)ΑＫ羞@樣的有序?qū)M成的集合稱為集合和的笛卡兒乘積(Descartesianproduct)，又稱作直積，記作。和的笛卡兒積的符號(hào)化表示為：AB=（x,y）|xAyB,定義1.3笛卡兒乘積,1-36,定義1.4n階笛卡兒積若nN，且n1，A1,A2,An是n個(gè)集合，它們的n階笛卡兒積記作A1A2An,并定義為：A1A2An=（x1,x2,xn）|x1A1x2A2,xnAn當(dāng)A1=A2=An=A時(shí)，A1A2An簡(jiǎn)記為An。,1-37,關(guān)系R與S的笛卡兒乘積,例1.7設(shè)有關(guān)系R與S，見(jiàn)表12和表13，求R與S的笛卡兒乘積。,表12R,表13S,1-38,表14RS,解：兩個(gè)關(guān)系R與S的笛卡兒乘積見(jiàn)表14。,1-39,從笛卡兒乘積的定義看出，這種運(yùn)算是將兩張表聯(lián)成一張表的運(yùn)算，如果我們所要檢索的內(nèi)容牽涉到兩張表，此時(shí)只要先用這個(gè)運(yùn)算將兩張表統(tǒng)一成一張表，然后再用“投影”和“選擇”就可找出所需的檢索內(nèi)容了。但是，在大多數(shù)情況下兩張相聯(lián)表之間均有一定關(guān)系，即兩張表均有相同的分量(字段)，如表3學(xué)生花名冊(cè)S和表5選課表SC間有相同的分量“學(xué)號(hào)”，表C與SC間也有相同分量“課程編號(hào)”，而我們所需要相聯(lián)后的表是在公共分量外有相等內(nèi)容的那些元組構(gòu)成。因此我們?cè)诘芽▋撼朔e的基礎(chǔ)上再引入一個(gè)二元運(yùn)算叫自然聯(lián)接(NatureJoin)。,1-40,自然聯(lián)接(NatureJoin),定義1.5設(shè)有n元關(guān)系R和m元關(guān)系S，R有屬性R1，R2，Rn，S有屬性S1，S2，Sm，其中S中的屬性S1，S2，Sp分別與R中的屬性Rn-p+1，Rn-P+2，Rn相同，此時(shí)可定義R與S的自然聯(lián)接(NatureJoin)R|S如下：,1-41,自然聯(lián)接的例子,例1.8設(shè)R與S均為三元關(guān)系，見(jiàn)表15和表16，求R|S。,表15R,表16S,1-42,表17R|S,解：關(guān)系R與S的自然聯(lián)接R|S為五元關(guān)系，見(jiàn)表17,1-43,例1.9找出學(xué)生的姓名為林麗梅所修讀課程的課程編號(hào)。解：這個(gè)檢索與表3學(xué)生花名冊(cè)S和表5選課表SC的關(guān)，所以首先自然聯(lián)接將S與SC聯(lián)成一張表，然后再在聯(lián)接后的表中用投影和選擇F找出所需的內(nèi)容，故可寫成：課程編號(hào)姓名=林麗梅(S|SC),1-44,例1.10打印學(xué)生姓名為林麗梅所修讀課程的課程名。解：這個(gè)檢索涉及到三張表，因此可以用兩次自然聯(lián)接將三張表聯(lián)成一張表，然后再用投影和選擇檢索所要求的內(nèi)容。則課程名姓名=林麗梅(S|SC|C)至此，我們介紹有關(guān)檢索的幾個(gè)例子，其中兩個(gè)一元運(yùn)算，兩個(gè)二元運(yùn)算，由于自然聯(lián)接可以用其它三個(gè)運(yùn)算表示，即自然聯(lián)接不是基本運(yùn)算，所以實(shí)際上只要三個(gè)運(yùn)算就足夠?qū)ΧS表進(jìn)行檢索。,1-45,(2)插入、修改和刪除操作與集合運(yùn)算,所謂插入操作(InsertOperation)就是在關(guān)系中增加一些元組，為完成這種操作我們可引入另一個(gè)集合運(yùn)算。這種操作相當(dāng)于集合的并運(yùn)算。例1.11設(shè)某系開設(shè)課程之概況由關(guān)系C表示之(見(jiàn)表4)，現(xiàn)增設(shè)兩門課，其概況為表18。表18