應(yīng)用離散數(shù)學(xué)第3章-集合與關(guān)系

集合與關(guān)系《應(yīng)用離散數(shù)學(xué)（第2版）》第3章21世紀(jì)高等教育計(jì)算機(jī)規(guī)劃教材

方景龍周麗編著目錄3.1集合及其運(yùn)算3.2二元關(guān)系及其運(yùn)算3.3二元關(guān)系的性質(zhì)與閉包3.4等價(jià)關(guān)系與劃分3.5偏序關(guān)系與拓?fù)渑判?.6函

數(shù)3.7集合的等勢(shì)與基數(shù)3.8多元關(guān)系及其應(yīng)用

集合是現(xiàn)代數(shù)學(xué)中最重要的基本概念之一，數(shù)學(xué)概念的建立由于使用了集合而變得完善并且統(tǒng)一起來。集合論已成為現(xiàn)代各個(gè)數(shù)學(xué)分支的基礎(chǔ)，同時(shí)還滲透到各個(gè)科學(xué)技術(shù)領(lǐng)域，成為不可缺少的數(shù)學(xué)工具和表達(dá)語言。對(duì)于計(jì)算機(jī)科學(xué)工作者來說，集合論也是必備的基礎(chǔ)知識(shí)，它在開關(guān)理論、形式語言、編譯原理等領(lǐng)域中有著廣泛的應(yīng)用。

本章首先介紹集合及其運(yùn)算，然后介紹二元關(guān)系及其關(guān)系矩陣和關(guān)系圖，二元關(guān)系的運(yùn)算、二元關(guān)系的性質(zhì)、二元關(guān)系的閉包，等價(jià)關(guān)系與劃分、函數(shù)，最后介紹多元關(guān)系及其在數(shù)據(jù)庫中的應(yīng)用等。3.1集合及其運(yùn)算3.1.1基本概念

集合是數(shù)學(xué)中最基本的概念之一，如同幾何中的點(diǎn)、線、面等概念一樣，是不能用其他概念精確定義的原始概念。集合是什么呢？直觀地說，把一些東西匯集到一起組成一個(gè)整體就叫做集合，而這些東西就是這個(gè)集合的元素或叫成員。例3.1（1）一個(gè)班級(jí)里的全體學(xué)生構(gòu)成一個(gè)集合。（2）平面上的所有點(diǎn)構(gòu)成一個(gè)集合。（3）方程

的實(shí)數(shù)解構(gòu)成一個(gè)集合。（4）自然數(shù)的全體（包含0）構(gòu)成一個(gè)集合，用N表示。（5）整數(shù)的全體構(gòu)成一個(gè)集合，用Z表示。（6）有理數(shù)的全體構(gòu)成一個(gè)集合，用Q表示。（7）實(shí)數(shù)的全體構(gòu)成一個(gè)集合，用R表示。（8）復(fù)數(shù)的全體構(gòu)成一個(gè)集合，用C表示。（9）正整數(shù)集合Z+，正有理數(shù)集合Q+，正實(shí)數(shù)集合R+。（10）非零整數(shù)集合Z*，非零有理數(shù)集合Q*，非零實(shí)數(shù)集合R*。（11）所有n階(n≥2)實(shí)矩陣構(gòu)成一個(gè)集合，用Mn(R)表示，即

而所有n階(n≥2)可逆實(shí)矩陣也構(gòu)成一個(gè)集合，用

表示。

通常用大寫英文字母表示集合的名稱，用小寫英文字母表示集合里的元素。若元素a屬于集合A

，記作

；若元素

a不屬于集合

A，記作

。并用

或

記集合

A中元素的個(gè)數(shù)。

集合的表示方法通常有下列兩種。1．列舉法

列舉法是列出集合中的所有元素，元素之間用逗號(hào)隔開，并把它們用花括號(hào)括起來。下面是用列舉法表示的集合：

有時(shí)列出集合中所有元素是不現(xiàn)實(shí)或不可能的，如上面的B和C，但只要在省略號(hào)前或后列出一定數(shù)量的元素，能使人們一看就能了解哪些元素屬于這個(gè)集合就可以。

2．描述法

描述法是用謂詞描述出元素的公共特性，其形式為

，表示

S是使

為真的

x的全體。下面是用描述法表示的集合：

下面介紹表示集合的有關(guān)符號(hào)和方法。

在一個(gè)具體問題中，若一個(gè)集合包含我們討論的每一個(gè)集合，則稱它是全集，記作

E。全集具有相對(duì)性，不同的問題有不同的全集，即使是同一個(gè)問題，也可以取不同的全集。例如，當(dāng)討論有關(guān)整數(shù)的問題時(shí)，可以整數(shù)集作為全集，也可以把有理數(shù)集取作全集。

沒有元素的集合叫做空集，記作

。3.1.2集合的運(yùn)算

集合的基本運(yùn)算有并、交、補(bǔ)、差和對(duì)稱差，它們的定義如下。

以上集合之間的關(guān)系和運(yùn)算可以用文氏圖（VennDiagram）形象、直觀地描述。文氏圖通常用一個(gè)矩形表示全集

，矩形中的點(diǎn)表示全集

E中的元素，

E的子集用矩形區(qū)域內(nèi)的圓形區(qū)域表示，圖中陰影區(qū)域表示新組成的集合。

圖3.1就是一些文氏圖的實(shí)例。

圖3.1文氏圖由文氏圖容易看出下列關(guān)系成立：等等。這說明使用文氏圖能夠?qū)σ恍﹩栴}給出簡(jiǎn)單、直觀的解釋，這種解釋對(duì)分析問題有很大幫助。不過，文氏圖只是起一種示意作用，可以啟發(fā)我們發(fā)現(xiàn)集合之間的某些關(guān)系，但不能用文氏圖來證明恒等式，因?yàn)檫@種證明是不嚴(yán)密的。

集合的并、交、差、補(bǔ)等具有許多性質(zhì)，下面列出這些性質(zhì)中最主要的幾條。定理3.1中的恒等式均可一一加以證明，下面我們選證其中的一小部分，其他的留給讀者自己證明。我們采用形式化的證明方法，在敘述中將大量用到數(shù)理邏輯的有關(guān)符號(hào)和等價(jià)公式。

上面給出的集合運(yùn)算的一些恒等式，如交換律、結(jié)合律、分配律、等冪律、德·摩根律等都可以推廣到多個(gè)集合中去，這里就不再列出具體的式子了。3.1.3集合的計(jì)算機(jī)表示

計(jì)算機(jī)表示集合的方式各種各樣。一種方式是把集合的元素?zé)o序地存儲(chǔ)起來?？墒侨绻@樣做，在做集合的運(yùn)算時(shí)會(huì)浪費(fèi)很多時(shí)間，因?yàn)檫@些運(yùn)算需要大量的元素檢索。我們這里介紹一種利用位串表示集合的方法，集合的這種表示方法使計(jì)算集合的運(yùn)算變得很容易。

位串是0個(gè)或多個(gè)字位的序列，而每個(gè)字位都有兩個(gè)可能的值，即0或1，字位的這種取值來自二進(jìn)制數(shù)字，因?yàn)?和1是用在數(shù)的二進(jìn)制表示中的數(shù)字。位串是計(jì)算機(jī)表示信息的基本方式。3.2二元關(guān)系及其運(yùn)算3.2.1笛卡爾積證明

（這里只給出（1）的第一個(gè)等式的證明，其他的可類似地進(jìn)行。所用證明方法與證明兩個(gè)集合相等一樣，因?yàn)榈芽柗e也是集合。）因?yàn)樗?/p>

。由數(shù)學(xué)歸納法不難證明定理3.2對(duì)有限多個(gè)集合的并運(yùn)算、交運(yùn)算和差運(yùn)算也是成立的。3.2.2二元關(guān)系及其表示R和S的關(guān)系圖如圖3.2（a）和圖3.2（b）所示。圖3.2關(guān)系圖3.2.3二元關(guān)系的運(yùn)算

由于關(guān)系也是集合，所以對(duì)關(guān)系也可以進(jìn)行并運(yùn)算、交運(yùn)算、補(bǔ)運(yùn)算、差運(yùn)算、對(duì)稱差運(yùn)算等集合的有關(guān)運(yùn)算。

除了一般的集合運(yùn)算外，關(guān)系本身還具有兩種特殊的運(yùn)算：復(fù)合運(yùn)算和逆運(yùn)算。定義3.8設(shè)

R是從集合A

到集合B的關(guān)系，S

是從集合

B到集合

C的關(guān)系，則從A

到

C的關(guān)系稱為

R與

S的復(fù)合關(guān)系。即有

此例說明，復(fù)合關(guān)系不滿足交換律，但復(fù)合關(guān)系滿足結(jié)合律，即如下定理3.3。定理3.3設(shè)

R是從集合

A到集合

B的關(guān)系，

S是從集合B到集合

C的關(guān)系，

T是從集合C

到集合

D的關(guān)系，則證明

（與定理3.2的證明方法類似，這里用的仍然是證明兩個(gè)集合相等的方法。）

根據(jù)定理3.3，利用數(shù)學(xué)歸納法容易證明下面結(jié)論。3.3二元關(guān)系的性質(zhì)與閉包3.3.1二元關(guān)系的性質(zhì)

有若干用于把集合上的關(guān)系進(jìn)行分類的性質(zhì)。這里我們只介紹其中最重要的幾個(gè)。例3.14對(duì)于下列五種二元關(guān)系，試判斷哪些是自反的，哪些是反自反的，哪些是對(duì)稱的，哪些是反對(duì)稱的，哪些是傳遞的。（1）實(shí)數(shù)集合R上的小于等于關(guān)系≤。（2）集族上的包含于關(guān)系

。（3）正整數(shù)集合Z+上的整除關(guān)系|。（4）平面上直線集合L上的垂直關(guān)系⊥。（5）平面上直線集合L上的平行關(guān)系

（認(rèn)為直線不與自己平行）。解（1）是自反的，不是反自反的，不是對(duì)稱的，是反對(duì)稱的，是傳遞的。（2）是自反的，不是反自反的，不是對(duì)稱的，是反對(duì)稱的，是傳遞的。（3）是自反的，不是反自反的，不是對(duì)稱的，是反對(duì)稱的，是傳遞的。（4）不是自反的，是反自反的，是對(duì)稱的，不是反對(duì)稱的，不是傳遞的。（5）不是自反的，是反自反的，是對(duì)稱的，不是反對(duì)稱的，不是傳遞的。

關(guān)系的性質(zhì)不僅像定理3.7所表述的那樣反應(yīng)在它的集合表達(dá)式上，也明顯地反應(yīng)在它的關(guān)系矩陣和關(guān)系圖上。

表3.1列出了關(guān)系R的五種性質(zhì)在關(guān)系矩陣和關(guān)系圖中的特點(diǎn)。表3.1 關(guān)系R的五種性質(zhì)在關(guān)系矩陣和關(guān)系圖中的特點(diǎn)表3.2 關(guān)系的五種性質(zhì)和運(yùn)算之間的聯(lián)系3.3.2二元關(guān)系的閉包

關(guān)系圖如圖3.3所示。圖3.3閉包的關(guān)系圖3.4等價(jià)關(guān)系與劃分

在日常生活或者科學(xué)研究中，我們常常需要對(duì)一些事物或某個(gè)集合上的元素按照某種方式進(jìn)行分類。如進(jìn)行舉重比賽時(shí)，需要將運(yùn)動(dòng)員按重量級(jí)別進(jìn)行分類，每一個(gè)運(yùn)動(dòng)員必定屬于某一個(gè)重量級(jí)別，而任何一個(gè)運(yùn)動(dòng)員不能同時(shí)屬于兩個(gè)不同的重量級(jí)別。又如，對(duì)一些幾何圖形構(gòu)成的集合，按面積相等關(guān)系將它們進(jìn)行分類，即面積相等的幾何圖形屬于一類，這樣，每個(gè)幾何圖形必定屬于一類，而且不同類沒有公共點(diǎn)。

這種對(duì)某個(gè)集合上的元素按照某種方式進(jìn)行分類就叫作集合的劃分，它是一個(gè)非常重要而且應(yīng)用非常廣泛的概念。

集合的劃分與一種重要的二元關(guān)系即等價(jià)關(guān)系密切相關(guān)，等價(jià)關(guān)系具有十分良好的性質(zhì)和廣泛的應(yīng)用，因而成為最重要的二元關(guān)系之一。定義3.14設(shè)R是集合A上的關(guān)系，如果R是自反的、對(duì)稱的、傳遞的，則稱R是等價(jià)關(guān)系。設(shè)R是一個(gè)等價(jià)關(guān)系，若

，稱

a等價(jià)于

b。例3.17（1）在全體中國人組成的集合上定義“同姓”關(guān)系，它具備自反、對(duì)稱、傳遞的性質(zhì)，因此是一個(gè)等價(jià)關(guān)系。（2）平面上直線集合L上的“平行或恒等”關(guān)系是等價(jià)關(guān)系，而L上的“垂直”關(guān)系不是等價(jià)關(guān)系，因?yàn)樗炔皇亲苑吹?，也不是傳遞的。（3）平面上三角形的“全等”關(guān)系、“相似”關(guān)系等都是等價(jià)關(guān)系。（4）“朋友”關(guān)系不是等價(jià)關(guān)系，因?yàn)樗皇莻鬟f的。（5）集合的“包含于”關(guān)系不是等價(jià)關(guān)系，因?yàn)樗皇菍?duì)稱的。

所以R為A上的等價(jià)關(guān)系。該關(guān)系的關(guān)系圖如圖3.5所示。

不難看到，上述關(guān)系圖被分為三個(gè)互不連通的部分，每部分中的數(shù)兩兩都等價(jià)（有關(guān)系），不同部分中的數(shù)則不等價(jià)（沒有關(guān)系）。這種通過等價(jià)關(guān)系給出的每一部分叫做等價(jià)類，下面給出等價(jià)類和由等價(jià)類構(gòu)成的商集的嚴(yán)格定義。圖3.5一個(gè)等價(jià)關(guān)系的關(guān)系圖定理3.9指出，集合A上的等價(jià)關(guān)系R所形成的等價(jià)類，它們兩兩互不相交而且覆蓋住整個(gè)集合A。這種將一個(gè)集合劃分為若干個(gè)不相交的子集的并叫做集合的劃分，下面給出集合劃分的精確定義。定義3.16設(shè)A是一個(gè)非空集合，

是它的非空子集，如果它們滿足下列條件：圖3.6集合的劃分定義3.17設(shè)R是非空集合A上的等價(jià)關(guān)系，以R的所有等價(jià)類作為元素的集合稱為A關(guān)于R的商集，記作A/R，即

根據(jù)定理3.9，一個(gè)商集就是原集合的一個(gè)劃分，并且不同的商集將對(duì)應(yīng)不同的劃分。反之，我們有如下的定理。3.5偏序關(guān)系與拓?fù)渑判?.5.1偏序關(guān)系圖3.7偏序集的哈斯圖定義3.19假設(shè)

a和b是偏序集

上的兩個(gè)元素。如果或

我們就說a

和b是可比較的。否則就說

和b是不可比較的，并記作

。若偏序集

的每一對(duì)元素都是可比較的，則稱

X為全序集，相應(yīng)的偏序就稱為全序。全序集也叫做線性序集或叫做鏈。

雖然偏序集可能不是全序集，但它的子集仍有可能是全序集。很明顯，全序集的每一個(gè)子集都是全序集。

偏序集的子集S可以有多于一個(gè)的極小元和極大元。如果S是無限集合，那么S可能沒有極小元和極大元，例如，偏序集<R，≤>沒有極小元和極大元。如果S是有限集合，那么S一定至少有一個(gè)極小元和一個(gè)極大元。即有下面的定理3.11。

下界、上界、下確界和上確界都可能不存在，即使對(duì)有限集合也是這樣；下界和上界可以有多個(gè)，但下確界和上確界如果存在則唯一。而且如果a是集合S的最小（大）元，則a也是S的下（上）確界；反之，如果a是集合S的下（上）確界且

，則a也是S的最?。ù螅┰?。

有些書將下確界叫做最大下界，并記作

，而不是

，將上確界叫做最小上界，并記作

，而不是

。圖3.8根據(jù)哈斯圖求上、下確界3.5.3拓?fù)渑判?/p>

拓?fù)渑判蚺c安排任務(wù)有關(guān)。假設(shè)一個(gè)項(xiàng)目由20個(gè)任務(wù)構(gòu)成。某些任務(wù)只能在其他任務(wù)結(jié)束之后才能進(jìn)行。怎樣能夠找到完成這些任務(wù)的一個(gè)順序？為了建立這個(gè)問題的數(shù)學(xué)模型，我們首先建立一個(gè)任務(wù)集合上的偏序

，使得

，當(dāng)且僅當(dāng)直到任務(wù)a結(jié)束后任務(wù)b才能開始；然后構(gòu)造與這個(gè)偏序相容的一個(gè)全序R，就得到一個(gè)與這個(gè)偏序相容的完成這20個(gè)任務(wù)的順序，從而安排好這個(gè)項(xiàng)目。這種從一個(gè)偏序構(gòu)造一個(gè)與其相容的全序的過程就叫做拓?fù)渑判颉?/p>

這個(gè)排序所使用的步驟如圖3.9所示。圖3.9拓?fù)渑判蚶?.27一個(gè)計(jì)算機(jī)公司的開發(fā)項(xiàng)目需要完成7個(gè)任務(wù)。其中的某些任務(wù)只能在其他任務(wù)結(jié)束后才能開始。建立任務(wù)上的偏序如下：如果任務(wù)y在x結(jié)束后才能開始，則任務(wù)xp

任務(wù)y。這7個(gè)任務(wù)關(guān)于這個(gè)偏序的哈斯圖如圖3.10所示，求一個(gè)全序使得可以按照這個(gè)全序執(zhí)行這些任務(wù)以完成這個(gè)項(xiàng)目。解

可以通過執(zhí)行一個(gè)拓?fù)渑判虻玫?個(gè)任務(wù)的排序。排序的步驟顯示如圖3.11所示。這個(gè)排序的結(jié)果是

，給出了執(zhí)行任務(wù)的一種可能次序。圖3.10一個(gè)項(xiàng)目開發(fā)的哈斯圖圖3.11一個(gè)項(xiàng)目開發(fā)的工作安排3.6函

數(shù)3.6.1基本概念

函數(shù)（也叫映射）是數(shù)學(xué)中重要的概念，是一種具有特殊性質(zhì)的二元關(guān)系。我們這里所討論的函數(shù)不僅僅是定義在數(shù)集之上，而是可以定義在任意集合之上，它是初等數(shù)學(xué)中函數(shù)概念的推廣。

從定義可以得知，函數(shù)是一種特殊的關(guān)系，它與一般關(guān)系比較具備如下特征：（1）在函數(shù)中，序偶的第一個(gè)元素一定是互不相同的，但關(guān)系中序偶的第一個(gè)元素可以相同。（2）函數(shù)是二元關(guān)系，當(dāng)然也是集合。一個(gè)從X

到Y(jié)的函數(shù)，它作為集合，其元素個(gè)數(shù)一定是

；但從X到

Y的二元關(guān)系，作為集合，其元素個(gè)數(shù)確可以是從0到

中的任何一個(gè)正整數(shù)。（3）

的任何子集都是從X

到

Y的二元關(guān)系，因此從X

到

Y的不同二元關(guān)系有

個(gè)，但從

X到Y(jié)的不同函數(shù)僅有

個(gè)。3.6.2復(fù)合函數(shù)

我們知道，關(guān)系復(fù)合后可以得到一個(gè)新的關(guān)系。函數(shù)復(fù)合后也得到一個(gè)新的函數(shù)—復(fù)合函數(shù)。3.6.3逆函數(shù)

我們用復(fù)合關(guān)系直接定義了復(fù)合函數(shù)，那么逆函數(shù)（反函數(shù)）能否通過逆關(guān)系來直接定義呢？3.7集合的等勢(shì)與基數(shù)

通俗地講，集合的基數(shù)是量度集合所含元素多少的量。集合的基數(shù)越大，所含的元素就越多。為了講清楚無限集合的基數(shù)，我們先講集合的等勢(shì)概念。定理3.20有理數(shù)集合Q與自然數(shù)集合N等勢(shì)，但實(shí)數(shù)集合與自然數(shù)集合N不等勢(shì)。證明比較復(fù)雜，這里從略。

一般地，我們把與有限集合等勢(shì)的集合稱為有限可數(shù)集（有限可列集），把與自然數(shù)集合N等勢(shì)的集合稱為無限可數(shù)集（無限可列集），把與實(shí)數(shù)集合R等勢(shì)的集合稱為連續(xù)集。有限可數(shù)集和無限可數(shù)集又通稱為可數(shù)集（可列集），非可數(shù)集合統(tǒng)稱為不可數(shù)集合（不可列集合）。定義3.27設(shè)想把一切集合進(jìn)行分類，凡彼此等勢(shì)的歸于一類，不等勢(shì)的歸于不同的類，對(duì)于每一類集合，我們給予一個(gè)標(biāo)志來度量其元素的多少，稱這個(gè)標(biāo)志為這類集合的基數(shù)。對(duì)有限集，其基數(shù)就是集合中元素的個(gè)數(shù)n；對(duì)于與自然數(shù)集合等勢(shì)的集合，其基數(shù)用

（讀作“阿列夫零”）表示；對(duì)于與實(shí)數(shù)集合等勢(shì)的集合，其基數(shù)用

（讀作“阿列夫”）表示。一般，集合A的基數(shù)，記為Card(A)或｜A｜。

下面的康托定理說明不存在最大的基數(shù)，即有比實(shí)數(shù)集合R的基數(shù)

更大的基數(shù)存在。3.8多元關(guān)系及其應(yīng)用3.8.1多元關(guān)系

在兩個(gè)以上集合的元素中常常也會(huì)產(chǎn)生某種關(guān)系。例如，學(xué)生的姓名、專業(yè)以及成績(jī)之間的關(guān)系，一個(gè)航班的航空公司、航班號(hào)、出發(fā)地、目的地、起飛時(shí)間和到達(dá)時(shí)間之間的關(guān)系。

本節(jié)研究?jī)蓚€(gè)以上集合的元素之間的關(guān)系，這種關(guān)系叫多元關(guān)系，并且可以用這種多元關(guān)系表示計(jì)算機(jī)數(shù)據(jù)庫中的數(shù)據(jù)。這種表示在我們對(duì)數(shù)據(jù)庫中的數(shù)據(jù)進(jìn)行查詢時(shí)非常有用，例如，哪個(gè)航班在下午3點(diǎn)到4點(diǎn)之間降落在杭州蕭山國際機(jī)場(chǎng)？杭電主修軟件工程或網(wǎng)絡(luò)工程的哪些二年級(jí)學(xué)生平均成績(jī)高于80分？聯(lián)想公司的哪些雇員為這個(gè)公司工作不到5年但月報(bào)酬超過20000人民幣？

將定義3.4進(jìn)行推廣，可以定義有序n元組和n個(gè)集合的笛卡兒積。3.8.2關(guān)系數(shù)據(jù)庫

數(shù)據(jù)庫（Database）是按照數(shù)據(jù)結(jié)構(gòu)來組織、存儲(chǔ)和管理數(shù)據(jù)的倉庫。

用戶可以通過數(shù)據(jù)庫管理系統(tǒng)所提供的語言使用數(shù)據(jù)庫中存放的數(shù)據(jù)。這種使用包括下列幾個(gè)方面。（1）數(shù)據(jù)的檢索：從數(shù)據(jù)庫中取出滿足一定條件要求的數(shù)據(jù)。（2）數(shù)據(jù)的插入：將一些數(shù)據(jù)存儲(chǔ)到數(shù)據(jù)庫中供以后使用。（3）數(shù)據(jù)的修改：修改數(shù)據(jù)庫中指定的數(shù)據(jù)。（4）數(shù)據(jù)的刪除：刪除數(shù)據(jù)庫內(nèi)指定的數(shù)據(jù)。

數(shù)據(jù)庫使用操作所需要的時(shí)間依賴于這些信息的存儲(chǔ)方式。插入數(shù)據(jù)、刪除數(shù)據(jù)、修改數(shù)據(jù)、檢索數(shù)據(jù)，以及從一些重疊的數(shù)據(jù)庫中組合數(shù)據(jù)的操作，在一個(gè)大型數(shù)據(jù)庫中每天要執(zhí)行幾百萬次。由于這些操作的重要性，已經(jīng)開發(fā)了數(shù)據(jù)庫表示的各種方法。這里討論其中的一種基于關(guān)系概念的方法，叫做關(guān)系數(shù)據(jù)模型。

數(shù)據(jù)庫內(nèi)的數(shù)據(jù)都按一定格式組織與存放，實(shí)體是數(shù)據(jù)庫中數(shù)據(jù)的基本存放單位，如教師簡(jiǎn)歷、工資單、學(xué)生概況、課程概貌、合同執(zhí)行情況、物資供銷情況等均是實(shí)體。在關(guān)系數(shù)據(jù)庫中，實(shí)體按二維表的形式存放。二維表的每一行叫一個(gè)記錄，它代表一個(gè)完整的數(shù)據(jù)，m行表示實(shí)體包含m個(gè)記錄。n列表示實(shí)體有n個(gè)屬性，屬性的取值叫做字段，n個(gè)屬性表示每個(gè)記錄都有n個(gè)字段，如職工簡(jiǎn)歷這個(gè)實(shí)體就有姓名、性別、年齡等屬性，而一個(gè)記錄中的字段“男”就是“性別”屬性的一個(gè)取值。一個(gè)包含m行n列的實(shí)體，即一張有m行n列的二維表，實(shí)際上就是一個(gè)包含m個(gè)有序n元組的n元關(guān)系。例3.36（1）一個(gè)學(xué)生概況實(shí)體S，它有4個(gè)屬性：學(xué)號(hào)、姓名、年齡、所屬系名，分別用S#、SN、SA及SD表示，這個(gè)實(shí)體存放10個(gè)學(xué)生的概況，即有10個(gè)記錄，它可以用有10行4列的二維表表示，如表3.3所示。（2）一個(gè)課程概貌實(shí)體C，它有3個(gè)屬性：課程號(hào)、課程名、先修課程號(hào)，分別用C#、CN及PC#表示，這個(gè)實(shí)體存放6門課的概貌，即有6個(gè)記錄，它可以用有6行3列的二維表表示，如表3.4所示。S#SNSASD

C#CNPC＃01AB20CS

01OS0202AC21MA

02PL0503AD22MA

03DB0604AE21CS

04ML0505AF20CS

05MC0606AG20CS

06DS0407AH22MA

08AI23MA

09AJ21CS

10AK19MA

表3.3實(shí)體S

表3.4實(shí)體C

在實(shí)體中，如果根據(jù)某個(gè)屬性的取值就能檢索每個(gè)記錄，我們就叫這個(gè)屬性為主鍵碼。這就是說，當(dāng)實(shí)體中沒有兩個(gè)記錄在這個(gè)屬性有相同的值時(shí)，這個(gè)屬性就是主鍵碼。在例3.36中，S#屬性就是實(shí)體S的主鍵碼，而SD屬性則不是主鍵碼。

因?yàn)橹麈I碼用于唯一地標(biāo)識(shí)實(shí)體中的記錄，當(dāng)新的記錄被加到這個(gè)實(shí)體時(shí)，主鍵碼要繼續(xù)保持有效是非常重要的。因此，應(yīng)該做檢測(cè)以保證在主鍵碼中每個(gè)新記錄與二維表中所有其他的記錄不同。例如，使用學(xué)號(hào)作為學(xué)生概況實(shí)體的主鍵碼是有意義的，因?yàn)闆]有兩個(gè)學(xué)生有同樣的學(xué)號(hào)。一個(gè)大學(xué)不應(yīng)該使用姓名屬性作為主鍵碼，因?yàn)橛锌赡軆蓚€(gè)學(xué)生有同樣的姓名。

用戶使用關(guān)系數(shù)據(jù)庫實(shí)際上就是對(duì)一些二維表進(jìn)行檢索、插入、修改和刪除等操作，也就是對(duì)一些多元關(guān)系進(jìn)行這些操作。3.8.3數(shù)據(jù)庫的檢索

用戶對(duì)關(guān)系數(shù)據(jù)庫進(jìn)行檢索不外乎選擇某個(gè)二維表中滿足某些條件的一些行和一些列組成一個(gè)新的二維表。例如，對(duì)表3.3表示的二維表，要求給出年齡大于20歲的學(xué)生的學(xué)號(hào)與姓名就是一種檢索操作，它要求在表3.3中選擇滿足SA>20的那些行，再由這些行中選出屬性學(xué)號(hào)與姓名。

這種檢索操作的結(jié)果還是一張二維表，這個(gè)新的二維表有兩個(gè)屬性以及一些滿足SA>20的記錄。由此可見，檢索是由一張表到另一張表的操作，從數(shù)學(xué)的觀點(diǎn)看，檢索是一種一元運(yùn)算，它根據(jù)一個(gè)多元關(guān)系得出另一個(gè)多元關(guān)系。

下面我們來定義兩種一元檢索運(yùn)算，一種叫投影運(yùn)算，另一種叫選擇運(yùn)算，然后由這兩種運(yùn)算對(duì)關(guān)系數(shù)據(jù)庫進(jìn)行各種各樣的檢索。例3.37在學(xué)生概貌實(shí)體S中取出學(xué)生姓名是投影運(yùn)算

sn(S)，在課程概貌實(shí)體C中取出課程號(hào)和課程名是投影運(yùn)算

c#,cn(C)。在學(xué)生概貌實(shí)體S中取出年齡大于20歲的數(shù)學(xué)系的學(xué)生概貌是選擇運(yùn)算

sa>20^sd=ma(S)，在課程概貌實(shí)體C中取出先修課程號(hào)為05的課程概況是選擇運(yùn)算

pc#=05(C)。運(yùn)算結(jié)果

sn(S)、

c#,cn(C)、

sa>20^sd=ma(S)和

pc#=05(C)如表3.5、表3.6、表3.7和表3.8所示。SN

C#CN

S#SNSASD

C#CNPC#AB

01OS

02AC21MA

02PL05AC

02PL

03AD22MA

04ML05AD

03DB

07AH22MA

AE

04ML

08AI23MA

AF

05MC

AG

06DS

AH

AI

AJ

AK

表3.5

sn(S)

表3.6

c#,cn(C)

表3.7

sa

20

sd=ma(S)

表3.8

pc#=05(C)

聯(lián)合應(yīng)用投影運(yùn)算

和選擇運(yùn)算

就可以在關(guān)系數(shù)據(jù)庫檢索出所要求的任意行與任意列的內(nèi)容，例如，本小節(jié)前面的給出年齡大于20歲的學(xué)生的學(xué)號(hào)與姓名就是運(yùn)算

sn

SA>20(S)，取出所有計(jì)算機(jī)系的學(xué)生的名單是運(yùn)算

sn

sd=cs(S)。

C#CNPC

C#CNPC07PP05

01OS0208RP07

02PL05

03DB06

04ML05

05MC06

06DS04

07PP05

08RP07表3.9增設(shè)的課程

表3.10實(shí)體C∪C'3.8.4插入、刪除與修改

所謂插入操作就是在實(shí)體中增加一些記錄，換句話說，就是在多元關(guān)系中增加一些有序元組，這種操作相當(dāng)于集合的并運(yùn)算。而所謂刪除操作就是在實(shí)體中除去一些記錄，換句話說，就是在關(guān)系中除去一些有序元組，這種操作相當(dāng)于集合的差運(yùn)算。例3.38設(shè)某系開設(shè)課程之概況由表3.4表示的實(shí)體C表示，現(xiàn)增設(shè)兩門課，其概況如表3.9所示，請(qǐng)將此兩門課之概況插入實(shí)體C中。解

表3.