【數(shù)據(jù)庫設(shè)計(jì)與開發(fā)】關(guān)系代數(shù)

1、北京郵電大學(xué)軟件學(xué)院 郭文明 2003.06,數(shù)據(jù)庫設(shè)計(jì)與開發(fā)講義,1.2關(guān)系代數(shù),關(guān)系模型的重要部分是關(guān)系操縱，關(guān)系代數(shù)是一種抽象的查詢語言，是關(guān)系數(shù)據(jù)操縱語言的一種傳統(tǒng)表達(dá)方式，它是用對關(guān)系的運(yùn)算來表達(dá)查詢的。利用關(guān)系代數(shù)可以演示一個(gè)查詢語言從關(guān)系數(shù)據(jù)庫系統(tǒng)中檢索信息的潛力，可以用最簡單的形式來表達(dá)所有關(guān)系數(shù)據(jù)庫查詢語言必須完成的運(yùn)算的集合，這些基本的運(yùn)算對解釋標(biāo)準(zhǔn)查詢語言SQL如何被執(zhí)行很有幫助，同時(shí)也有利于培養(yǎng)關(guān)系運(yùn)算的思維能力。,北京郵電大學(xué)軟件學(xué)院 郭文明 2003.06,數(shù)據(jù)庫設(shè)計(jì)與開發(fā)講義,1.2關(guān)系代數(shù),關(guān)系代數(shù)的運(yùn)算對象是關(guān)系，運(yùn)算結(jié)果亦為關(guān)系。關(guān)系代數(shù)用到的運(yùn)算符包括四類

2、；集合運(yùn)算符、專門的關(guān)系運(yùn)算符、算術(shù)比較符和邏輯運(yùn)算符。關(guān)系代數(shù)的運(yùn)算按運(yùn)算符的不同可分為傳統(tǒng)的集合運(yùn)算和專門的關(guān)系運(yùn)算兩類。其中傳統(tǒng)的集合運(yùn)算將關(guān)系看成元組的集合，其運(yùn)算是從關(guān)系的“水平”方向即行的角度來進(jìn)行。而專門的關(guān)系運(yùn)算不僅涉及行而且涉及列。比較運(yùn)算符和邏輯運(yùn)算符是用來輔助專門的關(guān)系運(yùn)算符進(jìn)行操作的。,北京郵電大學(xué)軟件學(xué)院 郭文明 2003.06,數(shù)據(jù)庫設(shè)計(jì)與開發(fā)講義,關(guān)系代數(shù)運(yùn)算符,關(guān)系代數(shù)中,這些運(yùn)算經(jīng)有限次復(fù)合后形成的式子稱為關(guān)系代數(shù)表達(dá)式。,北京郵電大學(xué)軟件學(xué)院 郭文明 2003.06,數(shù)據(jù)庫設(shè)計(jì)與開發(fā)講義,1.2.1傳統(tǒng)的集合運(yùn)算,傳統(tǒng)的集合運(yùn)算是二目運(yùn)算，包括并、差、交、廣

3、義笛卡爾積。 定義1.2.1 設(shè)關(guān)系R和關(guān)系S具有相同的目n(即兩個(gè)關(guān)系都有n個(gè)屬性)，且相應(yīng)的屬性取自同一個(gè)域，則可以定義并、差、交運(yùn)算如下： 并(Union): 關(guān)系R與關(guān)系S的并記作：RS=t|tRtS 其結(jié)果仍為n目關(guān)系，由屬于R或?qū)儆赟的元組組成。 差(Difference): 關(guān)系R與關(guān)系S的差記作：RS= t|tRt!S 其結(jié)果仍為n目關(guān)系，由屬于R而不屬于S的所有元組組成。,北京郵電大學(xué)軟件學(xué)院 郭文明 2003.06,數(shù)據(jù)庫設(shè)計(jì)與開發(fā)講義,1.2.1傳統(tǒng)的集合運(yùn)算,交(Intersection):關(guān)系R與關(guān)系S的交記作：RS= t|tRtS 其結(jié)果仍為n目關(guān)系，由既屬于R又屬

4、于S的元組組成。關(guān)系的交可以用差來表示，即RS=R-(R-S)。 廣義笛卡爾積(Extended Cartesian Product):兩個(gè)分別為n目和m目的關(guān)系R和S的廣義笛卡爾積是一個(gè)(n+m)列的元組的集合。元組的前n列是關(guān)系R的一個(gè)元組，后m列是關(guān)系S的一個(gè)元組。若R有k1個(gè)元組，S有k2個(gè)元組，則關(guān)系R和關(guān)系S的廣義笛卡爾積有k1k2個(gè)元組。記作：RS=trts|trRtsS ,北京郵電大學(xué)軟件學(xué)院 郭文明 2003.06,數(shù)據(jù)庫設(shè)計(jì)與開發(fā)講義,傳統(tǒng)集合運(yùn)算舉例,北京郵電大學(xué)軟件學(xué)院 郭文明 2003.06,數(shù)據(jù)庫設(shè)計(jì)與開發(fā)講義,傳統(tǒng)集合運(yùn)算舉例,北京郵電大學(xué)軟件學(xué)院 郭文明 200

5、3.06,數(shù)據(jù)庫設(shè)計(jì)與開發(fā)講義,1.2.2 專門的關(guān)系運(yùn)算,專門的關(guān)系運(yùn)算包括選擇、投影、連接、除等。為了敘述上的方便，先引入幾個(gè)常用記號。 設(shè)關(guān)系模式為R(Al，A2，An)。它的一個(gè)關(guān)系設(shè)為R。tR表示t是R的一個(gè)元組。tAi則表示元組t中相應(yīng)于屬性Ai的一個(gè)分量。 若A=Ai1，Ai2，Aik，其中Ail，Ai2，Aik是A1，A2，An中的一部分，則A稱為屬性列或域列。,北京郵電大學(xué)軟件學(xué)院 郭文明 2003.06,數(shù)據(jù)庫設(shè)計(jì)與開發(fā)講義,1.2.2 專門的關(guān)系運(yùn)算,R為n目關(guān)系，S為m目關(guān)系。trR,tsS,trts稱為元組的連接。它是一個(gè)n+m列的元組，前n個(gè)分量為R中的一個(gè)n元組，

6、后m個(gè)分量為S中的一個(gè)m元組。 給定一個(gè)關(guān)系R(X，Z)，X和Z為屬性組。定義tX=x時(shí),x在R中的象集(Images Set)為： Zx=tZtR,tX=x 它表示R中屬性組X上值為x的諸元組在Z上分量的集合。,北京郵電大學(xué)軟件學(xué)院 郭文明 2003.06,數(shù)據(jù)庫設(shè)計(jì)與開發(fā)講義,學(xué)生-課程數(shù)據(jù)庫,北京郵電大學(xué)軟件學(xué)院 郭文明 2003.06,數(shù)據(jù)庫設(shè)計(jì)與開發(fā)講義,選擇(Selection),定義1.2.2 選擇 選擇又稱為限制(Restriction),它是在關(guān)系R中選擇滿足給定條件的諸元組,記作: F(R)=ttRF(t)=真 其中F表示選擇條件,它是一個(gè)邏輯表達(dá)式,取邏輯值真或假。邏輯表

7、達(dá)式F由邏輯運(yùn)算符,連接各算術(shù)表達(dá)式組成。算術(shù)表達(dá)式的基本形式為：X1Y1,其中表示比較運(yùn)算符，它可以是、=或；X1,Y1等是屬性名，或?yàn)槌Ａ?，或?yàn)楹唵魏瘮?shù)；屬性名也可以用它的序號來代替。,北京郵電大學(xué)軟件學(xué)院 郭文明 2003.06,數(shù)據(jù)庫設(shè)計(jì)與開發(fā)講義,選擇(Selection),選擇運(yùn)算實(shí)際上是從關(guān)系R中選取使邏輯表達(dá)式F為真的元組。這是從行的角度進(jìn)行的運(yùn)算,是對行的水平分解。 例1 查詢信息系(IS)全體學(xué)生 Sdept=”IS”(S) 或 5=”IS”(S) 其中下角標(biāo)“5”為Sdept的屬性序號。 或 S where Sdept=”IS” 例2 查詢年齡在19到20歲之間的學(xué)生 S

8、age19Sage20(S) 或 419420(S) 或 S where Sage=19 and Sage=20,北京郵電大學(xué)軟件學(xué)院 郭文明 2003.06,數(shù)據(jù)庫設(shè)計(jì)與開發(fā)講義,投影(Projection),定義1.2.3 投影 關(guān)系R上的投影是從R中選擇出若干屬性列組成新的關(guān)系，是對關(guān)系的垂直分解。記作： A(R)=tA|tR 其中A為R中的屬性列集合。 投影之后不僅取消了原關(guān)系中的某些列，而且還可能取消某些元組，因?yàn)槿∠四承傩粤泻?，就可能出現(xiàn)重復(fù)行，應(yīng)取消這些完全相同的行。,北京郵電大學(xué)軟件學(xué)院 郭文明 2003.06,數(shù)據(jù)庫設(shè)計(jì)與開發(fā)講義,投影(Projection),例3 查詢

9、學(xué)生的姓名和所在系。 Sname,Sdept(S) 或 2，5(S) 或 SSname,Sdept 例4 查詢學(xué)生關(guān)系Student中都有哪些系。 Sdept(S) 或 SSdept,北京郵電大學(xué)軟件學(xué)院 郭文明 2003.06,數(shù)據(jù)庫設(shè)計(jì)與開發(fā)講義,連接(Join),定義1.2.4 連接 連接也稱為連接。它是從兩個(gè)關(guān)系的笛卡爾積中選取屬性間滿足一定條件的元組。記作： RS=trts|trRtsStrAtsB AB 其中A和B分別為R和S上度數(shù)相等且可比的屬性組。是比較運(yùn)算符。連接運(yùn)算的結(jié)果是從R和S的廣義笛卡爾積RS中選取R關(guān)系在A屬性組上的值與S關(guān)系在B屬性組上值滿足比較關(guān)系的元組。,北京

10、郵電大學(xué)軟件學(xué)院 郭文明 2003.06,數(shù)據(jù)庫設(shè)計(jì)與開發(fā)講義,連接(Join),連接運(yùn)算中有兩種最為重要也最為常用的連接，一種是等值連接(equijoin)，另一種是自然連接(Naturaljoin)。另外還有外連接、左連接、右連接等。 為“=”的連接運(yùn)算稱為等值連接。它是從關(guān)系R與S的廣義笛卡爾積中選取A，B屬性值相等的那些元組. 自然連接(Natural join)是一種特殊的等值連接，它要求兩個(gè)關(guān)系中進(jìn)行比較的分量必須是相同的屬性組，并且在結(jié)果中把重復(fù)的屬性列去掉。,北京郵電大學(xué)軟件學(xué)院 郭文明 2003.06,數(shù)據(jù)庫設(shè)計(jì)與開發(fā)講義,外連接,定義1.2.5 外連接 表R(A1,A2,A

11、n,B1, B2,Bk)和S(B1,B2,Bk,C1,C2,Cm)的外連接RoS,行t屬于表RoS，如果下列情況之一發(fā)生： 1）可連接的行u,v分別在R和S中，有uBi=vBi（0=i=k）成立,此時(shí)tA=uA,tB=uB,tC=vC。 2）表R中的一個(gè)行u使得S中沒有一個(gè)可以與之連接的行，此時(shí)，tA=uA,tB=uB,tC=null。 3) 表S中的一個(gè)行v使得R中沒有一個(gè)可以與之連接的行，此時(shí)，tA=null,tB=vB,tC=vC。,北京郵電大學(xué)軟件學(xué)院 郭文明 2003.06,數(shù)據(jù)庫設(shè)計(jì)與開發(fā)講義,外連接,由定義知，外連接保留了未匹配的行。也就是說，在外連接一端的表上的行，即使在另一端

12、上的表沒有與之相匹配的連接列值也會出現(xiàn)在外連接的結(jié)果中。左連接和右連接運(yùn)算只是因?yàn)槲覀冃枰谀骋贿吷媳Ａ粑雌ヅ涞男卸?。左連接保留了在操作符左邊的未匹配行，右連接保留了在操作符右邊的未匹配行。 一般的連接操作是從行的角度進(jìn)行運(yùn)算。但自然連接還需要取消重復(fù)列，所以是同時(shí)從行和列的角度進(jìn)行運(yùn)算。,北京郵電大學(xué)軟件學(xué)院 郭文明 2003.06,數(shù)據(jù)庫設(shè)計(jì)與開發(fā)講義,關(guān)系代數(shù)連接運(yùn)算符,符號 含義 鍵盤格式 示例 AiBj 連接 JOIN(AiBj) RA1B2 S o 外連接 OUTER JOIN R o S Lo 左連接 LOUTER JOIN R Lo S Ro 右連接 ROUTER JOIN

13、R Ro S,北京郵電大學(xué)軟件學(xué)院 郭文明 2003.06,數(shù)據(jù)庫設(shè)計(jì)與開發(fā)講義,連接運(yùn)算舉例,北京郵電大學(xué)軟件學(xué)院 郭文明 2003.06,數(shù)據(jù)庫設(shè)計(jì)與開發(fā)講義,連接運(yùn)算舉例,北京郵電大學(xué)軟件學(xué)院 郭文明 2003.06,數(shù)據(jù)庫設(shè)計(jì)與開發(fā)講義,除(Division),定義1.2.6 除 給定關(guān)系R(X，Y)和S(Y，Z)，其中X，Y，Z為屬性組。R 中的Y與S中的Y可以有不同的屬性名，但必須出自相同的域集。R與S的除運(yùn)算得到一個(gè)新的關(guān)系P(X)，P是R中滿足下列條件的元組在X屬性列上的投影：元組在X上分量值x的象集Yx包含S在Y上投影的集合。記作： RS=trX|trRy(S)Yx 其中Yx

14、為x在R中的象集，x=trX。,北京郵電大學(xué)軟件學(xué)院 郭文明 2003.06,數(shù)據(jù)庫設(shè)計(jì)與開發(fā)講義,除(Division),除操作是同時(shí)從行和列角度進(jìn)行運(yùn)算。 除運(yùn)算是乘運(yùn)算的逆運(yùn)算，給定兩個(gè)表T和S，如果表R是通過R=TS定義的，那么有T=RS成立。在這個(gè)意義上可解釋為什么稱作除運(yùn)算。,北京郵電大學(xué)軟件學(xué)院 郭文明 2003.06,數(shù)據(jù)庫設(shè)計(jì)與開發(fā)講義,除運(yùn)算舉例,北京郵電大學(xué)軟件學(xué)院 郭文明 2003.06,數(shù)據(jù)庫設(shè)計(jì)與開發(fā)講義,除運(yùn)算舉例,在關(guān)系R中，A可以取四個(gè)值a1,a2,a3,a4。其中： a1的象集為(b1，c2)，(b2，c3，)，(b2，c1) a2的象集為(b3，c7)，(

15、b2，c3) a3的象集為(b4，c6) a4的象集為(b6，c6) S在(B，C)上的投影為(b1，c2)，(b2，c1)，(b2，c3) 顯然a1的象集包含了S在(B，C)屬性組上的投影,所以RS=a1.,北京郵電大學(xué)軟件學(xué)院 郭文明 2003.06,數(shù)據(jù)庫設(shè)計(jì)與開發(fā)講義,除運(yùn)算舉例,北京郵電大學(xué)軟件學(xué)院 郭文明 2003.06,數(shù)據(jù)庫設(shè)計(jì)與開發(fā)講義,1.2.3關(guān)系代數(shù)綜合例子,以下例子建立在下面CAP數(shù)據(jù)庫上。,北京郵電大學(xué)軟件學(xué)院 郭文明 2003.06,數(shù)據(jù)庫設(shè)計(jì)與開發(fā)講義,1.2.3關(guān)系代數(shù)綜合例子,例1 查詢所有定購了至少一個(gè)價(jià)值為0.50的商品的顧客的名字。 cname(pid

16、(price=0.50(P)O)C) 例2 找出全部沒有在代理商a03處訂購商品的顧客cid值。 cid(O)cid(aid=a03(O) 或 cid（C）cid（aid=a03（O） 例3 找出只在代理商a03處訂購商品的顧客。 cid(O)cid(aida03(O),北京郵電大學(xué)軟件學(xué)院 郭文明 2003.06,數(shù)據(jù)庫設(shè)計(jì)與開發(fā)講義,1.2.3關(guān)系代數(shù)綜合例子,例4 找出沒有被任何一個(gè)在北京的顧客通過在上海的代理商訂購的所有商品。 在北京的顧客通過在上海的代理商訂購的商品： pid(cid(city=北京(C) O)city=上海(A) 從所有商品中剔除以上商品： pid(P)pid(ci

17、d(city=北京(C) O)city=上海(A) 例5 找出訂購了所有價(jià)格為0.50的商品的顧客名字。 cname（cid,pid（O）pid（price=0.50（P） C） 例6 找出訂購所有被任何人訂購過一次的商品的顧客cid。 cid,pid（O）pid（O） 例7 找出所有接到至少顧客c004訂購的商品集合的訂單的代理商的aid。 aid,pid（O）pid（cid=c004（O）,北京郵電大學(xué)軟件學(xué)院 郭文明 2003.06,數(shù)據(jù)庫設(shè)計(jì)與開發(fā)講義,1.2.3關(guān)系代數(shù)綜合例子,例8 找出訂購了p01和p07這兩種商品的顧客的cid。 錯(cuò)誤 cid（pid=p01 and pid=p

18、07（O） 錯(cuò)誤 cid（pid=p01 or pid=p07（O） 正確 cid（pid=p01（O） cid（pid=p07（O） 例9 找出從至少一個(gè)接受訂購商品p03訂單的代理商處訂購過商品的顧客cid。 解題思路： cid（aid（pid=p03（O） O）,訂購商品p03的代理商,從這些代理商處訂購商品的顧客,p03,北京郵電大學(xué)軟件學(xué)院 郭文明 2003.06,數(shù)據(jù)庫設(shè)計(jì)與開發(fā)講義,1.2.3關(guān)系代數(shù)綜合例子,例10 找出所有具有和在北京和天津的顧客相同的折扣率的顧客的cid。 本題可理解為：找出那些具有和在北京和天津的顧客相同的折扣率的顧客的cid。 在北京和天津的顧客的所有折扣率： discnt（city=北京 or city=天津（C） 所以有：c