關系數(shù)據(jù)庫的基本理論.ppt

第3章 關系數(shù)據(jù)庫的基本理論,馮萬利,本章重要概念,(1) 基本概念 關系數(shù)據(jù)模型，關鍵碼（主鍵和外鍵），關系的定義和性質，三類完整性規(guī)則，ER模型到關系模型的轉換規(guī)則，過程性語言與非過程性語言。 (2 ) 關系代數(shù) 五個基本操作，四個組合操作，七個擴充操作。 (3) 關系代數(shù)表達式的優(yōu)化 關系代數(shù)表達式的等價及等價轉換規(guī)則，啟化式優(yōu)化算法。,主要內容,3.1關系數(shù)據(jù)模型 3.1.1 關系模式 3.1.2 關系操作 3.2關系模型的完整性規(guī)則 3.2.1 關系的三類完整性約束 3.2.2 實體完整性 3.2.3 參照完整性 3.2.4 用戶自定義完整性 3.3關系代數(shù)的基本運算 3.3.1 傳統(tǒng)的集合運算 3.3.2 專門的關系運算 3.3.3 關系代數(shù)表達式及其應用實例,*3.4關系演算 元組關系演算 域關系演算 3.5 查詢優(yōu)化 3.5.1 查詢優(yōu)化的一般策略 3.5.2 代數(shù)表達式的等價變換規(guī)則 3.5.3 優(yōu)化算法,3.1關系數(shù)據(jù)模型,3.1.1 關系模式,每個關系都有一個模式，稱為關系模式(Relation Schema)，由一個關系名及它的所有屬性名構成。 在關系模式中，字段稱為屬性，字段值稱為屬性值，記錄類型稱為關系模式。在圖3.1中： 關系模式名是R 記錄稱為元組（tuple） 元組的集合稱為關系（relation）或實例（instance） 一般用前面的大寫英語字母A、B、C、表示單個屬性，用后面的大寫字母、W、X、Y、Z表示屬性集，用小寫字母表示屬性值。,數(shù)據(jù)庫技術的術語 關系模型的術語,關系具有的特點, 關系（表）可以看成是由行和列交叉組成的二維表格。它表示的是一個實體集合。 表中一行稱為一個元組，可用來表示實體集中的一個實體。 表中的列稱為屬性，給每一列起一個名稱即屬性名，表中的屬性名不能相同。 列的取值范圍稱為域，同列具有相同的域，不同的列可有相同的域。 例如，SEX的取值范圍是M（男），F(xiàn)（女），AGE為整數(shù)域。 表中任意兩行（元組）不能相同。能惟一標識表中不同行的屬性或屬性組稱為主鍵。,關系的性質,屬性值是原子的，不可分解。 沒有重復元組。 沒有行序。 理論上沒有列序，但一般使用時都有列序。,關鍵碼和表之間的聯(lián)系,超鍵：在一個關系中，能惟一標識元組的屬性或屬性集稱為關系的超鍵。 候選鍵：如果一個屬性集能惟一標識元組，且又不含有多余的屬性，那么這個屬性集稱為關系的候選鍵。 主鍵：若一個關系中有多個候選鍵，則選其中的一個為關系的主鍵。 外鍵：若一個關系R中包含有另一個關系S的主鍵所對應的屬性組F，則稱F為R的外鍵。并稱關系S為參照關系，關系R為依賴關系。,關系模式舉例,例如，學生關系和系部關系分別為： 學生（SNO，SNAME，SEX，AGE，SDNO） 系部（SDNO，SDNAME，CHAIR） 學生關系的主鍵是SNO，系部關系的主鍵為SDNO，在學生關系中，SDNO是它的外鍵。 更確切地說，SDNO是系部表的主鍵，將它作為外鍵放在學生表中，實現(xiàn)兩個表之間的聯(lián)系。 在關系數(shù)據(jù)庫中，表與表之間的聯(lián)系就是通過公共屬性實現(xiàn)的。 我們約定，在主鍵的屬性下面加下劃線，在外鍵的屬性下面加波浪線。,關系模式、關系子模式和存儲模式,例3.1 下圖是一個教學模型的實體聯(lián)系圖。實體類型“學生”的屬性SNO、SNAME、SEX、AGE、SDEPT分別表示學生的學號、姓名、性別、年齡和學生所在系部；實體類型“課程”的屬性CNO、CNAME、CDEPT、TNAME分別表示課程號、課程名、課程所屬系和任課教師。學生用S表示，課程用C表示。S和C之間有M:N的聯(lián)系（一個學生可選多門課程，一門課程可以被多個學生選修），聯(lián)系類型SC的屬性成績用GRADE表示。右圖表示的實體聯(lián)系圖（ER圖）。,關系模式是對關系的描述，它包括模式名，組成該關系的諸屬性名、值域名和模式的集合。具體的關系稱為實例。,關系模式,該圖表示的學生情況的部分轉換成相應的關系模式為： S(SNO,SNAME,SEX,AGE,SDPET)關系模式S描述了學生的數(shù)據(jù)結構，它是下表中學生實體的關系模式。其中SNO，CNO為關系SC的主鍵，SNO、CNO又分別為關系SC的兩個外鍵。,學生關系實例如下表；選修關系實例如右表。,關系模式(9),課程關系實例如下表：,關系子模式,用戶使用的數(shù)據(jù)不直接來自關系模式中的數(shù)據(jù)，而是從若干關系模式中抽取滿足一定條件的數(shù)據(jù)構成關系子模式。關系子模式是用戶所需數(shù)據(jù)結構的描述，其中包括這些數(shù)據(jù)來自哪些模式和應滿足哪些條件。 例3.2 用戶需要用到成績子模式G(SNO,SNAME,CNO,GRADE)。子模式G對應的數(shù)據(jù)來源于表S和表SC，構造時應滿足它們的SNO值相等。子模式G的構造過程如下圖所示。,關系子模式,一 一對應,描述關系是如何在物理存儲設備上存儲的。關系存儲時的基本組織方式是文件。由于關系模式有鍵，因此存儲一個關系可以用散列方法或索引方法實現(xiàn)。如果關系中元組數(shù)目較少（100以內），那么也可以用堆文件方式實現(xiàn)。此外，還可以對任意的屬性集建立輔助索引。,存儲模式,關系模型中常用的關系操作包括查詢（Query）操作和插入（Insert）、刪除（Delete）、修改（Update）操作。 查詢操作又可以分為：選擇（Select）、投影（Project）、連接（Join）、除（Divide）、并（Union）、差（Except）、交（Intersection）、笛卡爾積等。 基本操作：選擇、投影、并、差、笛卡爾積。 其他操作：可以用基本操作來定義和導出的。 關系操作的特點是集合操作方式，即操作的對象和結果都是集合。這種操作方式也稱稱為一次一集合（set-at-a-time）的方式。相應地，非關系數(shù)據(jù)模型的數(shù)據(jù)操作方式則為一次一紀錄（record-at-a-time）的方式。,3.1.2 關系操作,關系語言是一種高度非過程化的語言，用戶不必請求DBA為其建立特殊的存取路徑，存取路徑的選擇由RDBMS的優(yōu)化機制來完成。,關系數(shù)據(jù)語言的分類,關系數(shù)據(jù)語言分為三類：關系代數(shù)、元組關系演算和域關系演算。該三種語言在表達能力上是完全等價的。,3.2 關系模型的完整性規(guī)則,主要內容,3.2.1 關系的三類完整性約束 3.2.2 實體完整性 3.2.3 參照完整性 3.2.4 用戶定義完整性,關系模型的完整性規(guī)則,關系模型中有三類完整性約束：實體完整性、參照完整性和用戶定義的完整性。 實體完整性和參照完整性是關系模型必須滿足的完整性約束條件，被稱作是關系的兩個不變性，應該由關系系統(tǒng)自動支持。 用戶定義的完整性是應用領域需要遵循的約束條件，體現(xiàn)了具體領域中的語義約束。,規(guī)則3.1 實體完整性（Entity Integrity）規(guī)則：若屬性（指一個或一組屬性）A是基本關系R的主屬性。則A不能取空值。 例如: 在關系S(SNO,SNAME,SEX,AGE,SDPET)中，SNO這個屬性為主碼，則SNO不能取空值。,3.2.1 關系的三類完整性約束,實體完整性要求關系中元組在組成主鍵的屬性上不能有空值。如果出現(xiàn)空值，那么主鍵值就起不了惟一標織元組的作用。,對于實體完整性規(guī)則幾點說明, 實體完整性規(guī)則是針對基本關系而言的。一個基本關系通常對應現(xiàn)實世界的一個實體集。例如學生關系對應于學生的集合。 現(xiàn)實世界中的實體是可區(qū)分的，即它們具有某種唯一性標識。例如每個學生都是獨立的個體，是不一樣的。 關系模型中以主碼作為唯一性標識。 主碼中的屬性即主屬性不能取空值。如果主屬性取空值，就說明存在某個不可標識的實體，即存在不可區(qū)分的實體，這與第點相矛盾，因此這個規(guī)則稱為實體完整性。,定義2.3 參照完整性規(guī)則的形式定義如下： 如果屬性集K是關系模式R1的主鍵，K也是關系模式R2的外鍵，那么在R2的關系中，K的取值只允許兩種可能，或者為空值，或者等于R1關系中某個主鍵值。 這條規(guī)則的實質是“不允許引用不存在的實體”。 在上述形式定義中，關系模式R1的關系稱為“參照關系”，關系模式R2的關系稱為“依賴關系”。,參照完整性規(guī)則,由參照完整性建立了多表之間的對應關系,參照完整性規(guī)則舉例,例2.1 下面各種情況說明了參照完整性規(guī)則在關系中如何實現(xiàn)的。 在關系數(shù)據(jù)庫中有下列兩個關系模式： S（S#，SNAME，AGE，SEX） SC（S#，C#，GRADE） 據(jù)規(guī)則要求，關系SC中的S# 值應該在關系S中出現(xiàn)。如果關系SC中有一個元組（S7,C4,80），而學號S7卻在關系S中找不到，那么我們就認為在關系SC中引用了一個不存在的學生實體，這就違反了參照完整性規(guī)則。 另外，在關系SC中S#不僅是外鍵，也是主鍵的一部分，因此這里S# 值不允許空。, 設工廠數(shù)據(jù)庫中有兩個關系模式： DEPT(D#，DNAME) EMP(E#，ENAME，SALARY，D# ) 車間模式DEPT的屬性為車間編號、車間名，職工模式EMP的屬性為工號、姓名、工資、所在車間的編號。每個模式的主鍵與外鍵已標出。在EMP中，由于D#不在主鍵中，因此D# 值允許空。,參照完整性規(guī)則舉例,參照完整性規(guī)則舉例, 設課程之間有先修、后繼聯(lián)系。模式如下： R(C# ，CNAME，PC# ) 其屬性表示課程號、課程名、先修課的課程號。如果規(guī)定，每門課程的直接先修課只有一門，那么模式R的主鍵是C#，外鍵是PC#.。這里參照完整性在一個模式中實現(xiàn)。即每門課程的直接先修課必須在關系中出現(xiàn)。,用戶定義的完整性規(guī)則,在建立關系模式時，對屬性定義了數(shù)據(jù)類型，即使這樣可能還滿足不了用戶的需求。此時，用戶可以針對具體的數(shù)據(jù)約束，設置完整性規(guī)則，由系統(tǒng)來檢驗實施，以使用統(tǒng)一的方法處理它們，不再由應用程序承擔這項工作。例如學生的年齡定義為兩位整數(shù)，范圍還太大，我們可以寫如下規(guī)則把年齡限制在1530歲之間： CHECK（AGE BETWEEN 15 AND 30）,3.3 關系代數(shù)的基本運算,主要內容,傳統(tǒng)的集合運算 專門的關系運算 關系代數(shù)表達式及其應用實例,并（Union） 設關系R和S具有相同的關系模式，R和S的并是由屬于R或屬于S的元組構成的集合，記為RS。形式定義如下： RSt | tR tS，t是元組變量，R和S的元數(shù)相同。 差（Difference） 設關系R和S具有相同的關系模式，R和S的差是由屬于R但不屬于S的元組構成的集合，記為RS。形式定義如下： RS t | tR tS，R和S的元數(shù)相同。,傳統(tǒng)的集合運算,舉例,關系運算舉例,交運算,交（intersection） 關系R和S的交是由屬于R又屬于S的元組構成的集合，記為RS，這里要求R和S定義在相同的關系模式上。形式定義如下： RSttR tS，R和S的元數(shù)相同。,例,R,S,R S,笛卡兒積運算,若R有m個元組，S有n個元組，則RS有mn個元組。,笛卡兒積(Cartesian Product) 設關系R和S的元數(shù)分別為r和s,定義R和S的一個(r+s)元的元組集合，每個元組的前r個分量來自R的一個元組，后s個分量來自S的一個元組，記為RS。 RS t|t=trRtsS,專門的關系運算,選擇（Selection） 選擇操作是根據(jù)某些條件對關系做水平分割，即選取符合條件的元組。條件可用命題公式（即計算機語言中的條件表達式）F表示。 F中的基本形式為：X1Y1： 其中表示比較運算符:，。 X1，Y1等是屬性名，常量，或列序號。 關系R關于公式F的選擇操作用F（R）表示，形式定義為：F（R） t | tR F（t）= true 為選擇運算符，F(xiàn)（R）表示從R中挑選滿足公式F為真的元組所構成的關系。 例如，23（R）表示從R中挑選第2個分量值大于3的 元組所構成的關系。書寫時，為了與屬性序號區(qū)別起見，常量用引號括起來，而屬性序號或屬性名不要用引號括起來。,投影（Projection),這個操作是對一個關系進行垂直分割，消去某些列，并重新安排列的順序。 設關系R是k元關系，R在其分量Ai1，Aim（mk i1，im ，為1到k間的整數(shù)）上的投影用i1,.,im（R）表示，它是一個m元元組集合，形式定義為：i1，im（R） t | tti1，timt1，tkR 例如，3，1（R）表示關系R中取第1、3列，組成新的關系，新關系中第1列為R的第3列，新關系的第2列為R的第1列。如果R的每列標上屬性名，那么操作符的下標處也可以用屬性名表示。例如，關系R（A，B，C），那么C，A（R）與3，1（R）是等價的。,連接有兩種：連接和F連接（這里是算術比較符，F(xiàn)是公式）。 連接 R St t= trR tsS 表達式 表示元組tr的第i個分量、元組ts的第j個分量滿足操作。 F連接 F連接是從關系R和S的笛卡兒積中選取屬性間滿足某一公式F的元組, 這里F是形為F1F2Fn的公式，每個FP是形ij的式子，而i和j分別為關系R和S的第i、第j個分量的序號。,連接（join）運算,ij,例 連接和F連接的例子.,24（RS),連接運算舉例,兩個關系R和S的自然連接 操作具體計算過程如下： 計算RS ； 設R和S的公共屬性是A1,AK，挑選RS中滿足R.A1=S.A1，R.AK=S.AK的那些元組； 去掉S.A1，S.AK這些列。 定義： 中i1,im為R和S的全部屬性，但公共屬性只出現(xiàn)一次。,自然連接（natural join）,關系R,關系S,一般連接 R S,等值連接 R S,自然連接 R S,連接運算舉例,兩個關系R和S在做自然連接時，選擇兩個關系在公共屬性上值相等的元組構成新的關系。此時，關系R中某些元組有可能在S中不存在公共屬性上值相等的元組，從而造成R中這些元組在操作時被舍棄了，同樣，S中某些元組也可能被舍棄。 如果把舍棄的元組也保存在結果關系中，而在其他屬性上填空值（Null），那么這種連接就叫做外連接(Outer join)。如果只把左邊關系R中要舍棄的元組保留就叫做左外連接（Left outer join或Left join），如果只把右邊關系S中要舍棄的元組保留就叫做右外連接（Right outer join或Right join）。,專門的關系運算,關系R 關系S,外連接,左外連接,右外連接,外連接的例子,除法（division）,設關系R和S的元數(shù)分別為r和s（設rs0），那么RS是一個（r-s）元的元組的集合。（RS）是滿足下列條件的最大關系：其中每個元組t與S中每個元組u組成的新元組必在關系R中。 RS1,2,r-s（R）- 1,2,r-s (1,2,r-s(R)S)-R),除法舉例,關系代數(shù)運算的應用實例(1),在關系代數(shù)運算中，把由五個基本操作經(jīng)過有限次復合的式子稱為關系代數(shù)表達式。這種表達式的運算結果仍是一個關系。 例2.7 設教學數(shù)據(jù)庫中有三個關系： 學生關系 S(S#,SNAME,AGE,SEX) 選課關系 SC(S#,C#,GRADE) 課程關系 C(C#,CNAME,TEACHER) 用關系代數(shù)表達式表示查詢語句。 (1) 檢索學習課程號為C2的學生學號與成績。 S#,GRADE(C#=C2 (SC) (2) 檢索學習課程號為C2的學生的學號與姓名。 S#,SNAME(C#=C2 (S SC) (3) 檢索選修課程名為MATHS的學生學號與姓名。 S#,SNAME(CNAME=MATHS (S SC C),(4) 檢索選修課程號為C2或C4的學生學號。 S#(C#=C2 C#=C4(SC) (5) 檢索至少選修課程號為C2和C4的學生學號。 1(1=42=C2 5=C4 (SCSC) (6)檢索不學C2課的學生姓名與年齡。 SNAME,AGE ( S)-SNAME,AGE (C#=C2 (S SC) (7) 檢索學習全部課程的學生姓名。 學生選課情況可用操作S#,C#(SC); 全部課程可用操作C#(C)表示; 學了全部課程的學生學號可用除法操作表示,操作結果是學號S#集; S#,C# (SC) C# (C) 從S#求學生姓名SNAME,可以用自然連接和投影操作組合而成: SNAME(S (S#,C# (SC) C# (C) (8)檢索所學課程包含學生S3所學課程的學生學號。 學生選課情況可用操作S#,C# (SC)表示; 學生S3所學課程可用操作C#(S#=S3(SC)表示; 所學課程包含學生S3所學課程的學生學號,可以用除法操作求得: S#,C# (SC) C#(S#=S3(SC),S(S#,SNAME,AGE,SEX) SC(S#,C#,GRADE) C(C#,CNAME,TEACHER),關系代數(shù)運算的應用實例(2),關系代數(shù)運算的應用實例(3),一般地有下列規(guī)律： (1) 對于只涉及到選擇、投影、連接的查詢可用下列表達式表示： (RS) 或者(R S) (2) 對于否定的操作，一般要用差操作表示，例如“檢索不學C2課的學生姓名”。用下列表達式表示： SNAME(S)-SNAME(CNO=C2(S SC)但不能用下式表示： SNAME(CNOC2(S SC) 對于檢索具有“全部”特征的操作，一般要用除法操作表示，例如“檢索學習全部課程的學生學號”。用下列表達式表示： 要用SNO,CNO(SC)CNO(C)表示，而不能寫成 SNO (SCCNO(C)形式。 這是因為一個學生學的課程的成績可能是不一樣的。,3.5 查詢優(yōu)化,主要內容,查詢優(yōu)化的一般策略 代數(shù)表達式的等價變換規(guī)則 優(yōu)化算法,例 設關系R和S都是二元關系，屬性名分別為A，B和C，D。 設有一個查詢可用關系代數(shù)表達式表示： E1=A（B=CD=99（RS） 也可以把選擇條件D=99移到笛卡兒積中的關系S前面： E2=A（B=C（RD=99（S） 還可以把選擇條件BC與笛卡兒積結合成等值連接形式： E3=A（R D=99（S） 這三個關系代數(shù)表達式是等價的，但執(zhí)行的效率大不一樣。顯然，求El，E2，E3的大部分時間是花在連接操作上的。,查詢優(yōu)化例子,可以分析出，在時空性能上，E3最優(yōu)，其次是E2，最后是E1。此例還可以看出，如何安排選擇、投影和連接的順序是個很重要的問題。,查詢優(yōu)化的一般策略 (1),在關系代數(shù)表達式中需要指出若干關系的操作步驟。那么，系統(tǒng)應該以什么樣的操作順序，才能做到既省時間，又省空間，而且效率也比較高呢？這個問題稱為查詢優(yōu)化問題。 查詢優(yōu)化是實現(xiàn)關系系統(tǒng)的關鍵技術,它大大減輕了用戶選擇存取路徑的負擔,用戶使用關系系統(tǒng)時,只要提出“做什么”,不必指出“怎么做”。 在關系代數(shù)運算中，笛卡兒積和連接運算是最費時間的。,查詢優(yōu)化的一般策略 (2),查詢優(yōu)化采用的一般策略是： 盡可能早地執(zhí)行選擇運算。在查詢中這種變換最為重要，因為它可以以元組為單位減小中間結果，從而使執(zhí)行時間成數(shù)量級地減少。 把先做笛卡兒積，后做選擇結合起來。使之成為一個連接運算。連接運算（特別是等值連接）要比笛卡兒積運算效率高得很多。當對笛卡兒積RS的結果再做選擇時，并且這個選擇是對R和S的屬性進行比較，在這樣的條件下，這個笛卡兒積和選擇運算等價于一個連接。 一般對不含R的屬性或不含S的屬性的比較，可以移到笛卡兒積運算前去做，這樣做比轉換到連接更好。 同時計算一串選擇和一串投影運算，以免分開運算造成多次掃描文件，從而節(jié)省了操作時間。 找出表達式里的公共子表達式。如果公共子表達式的結果不是很大，并且從外存讀入比起計算它要節(jié)省許多時間，那么，預先計算一下這個公共子表達式是有好處的。 子表達式內涉及到連接，但又不能把限定條件向內移入的那類表達式，一般屬于這一類。,連接和笛卡兒積的交換律 E1 E2E2 E1 E1 E2 E2 E1 E1E2 E1E2 連接和笛卡兒積的結合律 (E1 E2） E3E1 (E2 E3) (E1 E2) E3E1 (E2 E3) (E1E2)E3 E1(E2E3) 投影的串接 設L1,設L2,Ln為屬性集，并且 ,那么下式也成立. 選擇的串接,代數(shù)表達式的等價變換規(guī)則 (1),選擇和投影操作的交換,代數(shù)表達式的等價變換規(guī)則 (2),選擇對笛卡兒積的分配律,這里要求F只涉及到E1中的屬性。 如果F形為F1F2，且F1只涉及到E1的屬性，F(xiàn)2只涉及到E2的屬性，則有,此外，如果F形為F1F2，且F1只涉及到E1的屬性，F(xiàn)2只涉及到E1和E2的屬性，則有：,選擇對并的分配律 E1和E2具有相同的屬性名，或者E1和E2表達的關系的屬性有對應性，則有：,代數(shù)表達式的等價變換規(guī)則(3),選擇對集合差的分配律 E1和E2的屬性有對應性，則有：,選擇對自然聯(lián)接的分配律 F只涉及到表達式E1和E2的公共屬性，則有： （E1 E2） （E1） （E2）,投影對笛卡爾的分配律 L1是E1中的屬性集，L2是E2中的屬性集，則有：,投影對并的分配律 E1和E2的屬性有對應性，則有：,代