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

1、第3章 關系數(shù)據(jù)庫的根本實際馮萬利馮萬利本章重要概念(1) 根本概念根本概念關系數(shù)據(jù)模型，關鍵碼主鍵和外鍵，關系數(shù)據(jù)模型，關鍵碼主鍵和外鍵，關系的定義和性質，三類完好性規(guī)那么，關系的定義和性質，三類完好性規(guī)那么，ER模型到模型到關系模型的轉換規(guī)那么，過程性言語與非過程性言語。關系模型的轉換規(guī)那么，過程性言語與非過程性言語。(2 ) 關系代數(shù)關系代數(shù)五個根本操作，四個組合操作，七個擴展五個根本操作，四個組合操作，七個擴展操作。操作。 (3) 關系代數(shù)表達式的優(yōu)化關系代數(shù)表達式的優(yōu)化關系代數(shù)表達式的等價及等價轉換規(guī)那么，關系代數(shù)表達式的等價及等價轉換規(guī)那么，啟化式優(yōu)化算法。啟化式優(yōu)化算法。主要內(nèi)容

2、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)化的普通戰(zhàn)略3.5.2 代數(shù)表達式的等價變換規(guī)那么3.5.3 優(yōu)化算法3.1關系數(shù)據(jù)模型3.1.1 關系方式 每個關系都有一個方式，稱為關系方式每個關系都有一個方式，稱為關系方式(Relation Schema)，由一個關

3、系名及它的一切屬性名構成。，由一個關系名及它的一切屬性名構成。在關系方式中，字段稱為屬性，字段值稱為屬性值，在關系方式中，字段稱為屬性，字段值稱為屬性值，記錄類型稱為關系方式。在圖記錄類型稱為關系方式。在圖3.1中：中：關系方式名是關系方式名是R記錄稱為元組記錄稱為元組tuple元組的集合稱為關系元組的集合稱為關系relation或實例或實例instance普通用前面的大寫英語字母普通用前面的大寫英語字母A、B、C、表示單個屬表示單個屬性，用后面的大寫字母性，用后面的大寫字母、W、X、Y、Z表示屬性集，表示屬性集，用小寫字母表示屬性值。用小寫字母表示屬性值。數(shù)據(jù)庫技術的術語數(shù)據(jù)庫技術的術語 關

4、系模型的術語關系模型的術語ABCDEa1 b1 c1 d1 e1a2 b2 c2 d2 e2a3 b3 c3 d3 e3 數(shù)據(jù)庫技術的術語數(shù)據(jù)庫技術的術語 關系模型的術語關系模型的術語 字段字段,數(shù)據(jù)項數(shù)據(jù)項 屬性屬性記錄類型記錄類型 關系方式關系方式記錄記錄1 元組元組1記錄記錄2 元組元組2記錄記錄3 元組元組3字段值字段值屬性值屬性值文文件件關系或實例關系或實例關系具有的特點 關系表可以看成是由行和列交叉組成的二維關系表可以看成是由行和列交叉組成的二維表格。它表示的是一個實體集合。表格。它表示的是一個實體集合。 表中一行稱為一個元組，可用來表示實體集中的表中一行稱為一個元組，可用來表示實

5、體集中的一個實體。一個實體。 表中的列稱為屬性，給每一列起一個稱號即屬性表中的列稱為屬性，給每一列起一個稱號即屬性名，表中的屬性名不能一樣。名，表中的屬性名不能一樣。 列的取值范圍稱為域，同列具有一樣的域，不同列的取值范圍稱為域，同列具有一樣的域，不同的列可有一樣的域。的列可有一樣的域。例如，例如，SEX的取值范圍是的取值范圍是M男，男，F(xiàn)女女，AGE為整數(shù)域。為整數(shù)域。 表中恣意兩行元組不能一樣。能獨一標識表表中恣意兩行元組不能一樣。能獨一標識表中不同行的屬性或屬性組稱為主鍵。中不同行的屬性或屬性組稱為主鍵。 關系的性質屬性值是原子的，不可分解。屬性值是原子的，不可分解。沒有反復元組。沒有反

6、復元組。沒有行序。沒有行序。實際上沒有列序，但普通運用時都有列序。實際上沒有列序，但普通運用時都有列序。關鍵碼和表之間的聯(lián)絡 超鍵：在一個關系中，能獨一標識元組的屬性超鍵：在一個關系中，能獨一標識元組的屬性或屬性集稱為關系的超鍵?；驅傩约Q為關系的超鍵。 候選鍵：假設一個屬性集能獨一標識元組，且候選鍵：假設一個屬性集能獨一標識元組，且又不含有多余的屬性，那么這個屬性集稱為關又不含有多余的屬性，那么這個屬性集稱為關系的候選鍵。系的候選鍵。 主鍵：假設一個關系中有多個候選鍵，那么選主鍵：假設一個關系中有多個候選鍵，那么選其中的一個為關系的主鍵。其中的一個為關系的主鍵。外鍵：假設一個關系外鍵：假設一

7、個關系R中包含有另一個關系中包含有另一個關系S的主鍵所對應的屬性組的主鍵所對應的屬性組F，那么稱，那么稱F為為R的外鍵。的外鍵。并稱關系并稱關系S為參照關系，關系為參照關系，關系R為依賴關系。為依賴關系。關系方式舉例例如，學生關系和系部關系分別為：例如，學生關系和系部關系分別為： 學生學生SNO，SNAME，SEX，AGE，SDNO 系部系部SDNO，SDNAME，CHAIR學生關系的主鍵是學生關系的主鍵是SNO，系部關系的主鍵為，系部關系的主鍵為SDNO，在學生關系中，在學生關系中，SDNO是它的外鍵。是它的外鍵。更確切地說，更確切地說，SDNO是系部表的主鍵，將它作為外鍵是系部表的主鍵，將

8、它作為外鍵放在學生表中，實現(xiàn)兩個表之間的聯(lián)絡。放在學生表中，實現(xiàn)兩個表之間的聯(lián)絡。在關系數(shù)據(jù)庫中，表與表之間的聯(lián)絡就是經(jīng)過公共屬在關系數(shù)據(jù)庫中，表與表之間的聯(lián)絡就是經(jīng)過公共屬性實現(xiàn)的。性實現(xiàn)的。我們商定，在主鍵的屬性下面加下劃線，在外鍵的屬我們商定，在主鍵的屬性下面加下劃線，在外鍵的屬性下面加波浪線。性下面加波浪線。 關系方式、關系子方式和存儲方式SNOSNAMEAGESEXSDEPTSCCNOCNAMECDEPTETNAMESCMNGRADE例3.1 以下圖是一個教學模型的實體聯(lián)絡圖。實體類型“學生的屬性SNO、SNAME、SEX、AGE、SDEPT分別表示學生的學號、姓名、性別、年齡和學生

9、所在系部；實體類型“課程的屬性CNO、CNAME、CDEPT、TNAME分別表示課程號、課程名、課程所屬系和任課教師。學生用S表示，課程用C表示。S和C之間有M:N的聯(lián)絡一個學生可選多門課程，一門課程可以被多個學生選修，聯(lián)絡類型SC的屬性成果用GRADE表示。右圖表示的實體聯(lián)絡圖ER圖。 關系方式是對關系的描畫，它包括方式名，組成該關系的諸屬性名、值域名關系方式是對關系的描畫，它包括方式名，組成該關系的諸屬性名、值域名和方式的集合。詳細的關系稱為實例。和方式的集合。詳細的關系稱為實例。關系方式該圖表示的學生情況的部分轉換成相應的關系方式為：該圖表示的學生情況的部分轉換成相應的關系方式為： S(

10、SNO,SNAME,SEX,AGE,SDPET)關系方式關系方式S描畫了學生的數(shù)據(jù)構造，它是描畫了學生的數(shù)據(jù)構造，它是下表中學生實體的關系方式。其中下表中學生實體的關系方式。其中SNO，CNO為關系為關系SC的主鍵，的主鍵，SNO、CNO又分別為關系又分別為關系SC的兩個外鍵。的兩個外鍵。SNOSNAMESEXAGESDEPTS1程曉程曉晴晴F21CSS2姜姜 云云F20ISS3李小李小剛剛M21CS學生關系方式學生關系方式 S(SNO，SNAME，SEX，AGE，SDPET)選修關系方式選修關系方式 SC( SNO，CNO，GRADE)課程關系方式課程關系方式 C(CNO，CNAME，CDE

11、PT，TNAME)SNOCNOGRADES1C187S1C278S1C390S2C167S2C279S2C356S3C180S3C276S3C392學生關系實例如下表；選修關系實例如右表。學生關系實例如下表；選修關系實例如右表。關系方式(9) CNOCNAMECDEPTTNAMEC1高等數(shù)學高等數(shù)學IS王紅衛(wèi)王紅衛(wèi)C2數(shù)據(jù)庫原理數(shù)據(jù)庫原理CS李紹麗李紹麗C3數(shù)據(jù)結構數(shù)據(jù)結構CS劉劉 良良課程關系實例如下表：課程關系實例如下表：關系子方式用戶運用的數(shù)據(jù)不直接來自關系方式中的數(shù)據(jù)，用戶運用的數(shù)據(jù)不直接來自關系方式中的數(shù)據(jù)，而是從假設干關系方式中抽取滿足一定條件的而是從假設干關系方式中抽取滿足一定條

12、件的數(shù)據(jù)構成關系子方式。關系子方式是用戶所需數(shù)據(jù)構成關系子方式。關系子方式是用戶所需數(shù)據(jù)構造的描畫，其中包括這些數(shù)據(jù)來自哪些數(shù)據(jù)構造的描畫，其中包括這些數(shù)據(jù)來自哪些方式和應滿足哪些條件。方式和應滿足哪些條件。 例例3.2 用戶需求用到成果子方式用戶需求用到成果子方式G(SNO,SNAME,CNO,GRADE)。子方式。子方式G對對應的數(shù)據(jù)來源于表應的數(shù)據(jù)來源于表S和表和表SC，構造時應滿足它，構造時應滿足它們的們的SNO值相等。子方式值相等。子方式G的構造過程如以下的構造過程如以下圖所示。圖所示。 SNOSNAMECNOGRADES1程曉晴程曉晴C187S2姜姜 云云C167SNOSNAMES

13、EXAGESDEPTS1程曉程曉晴晴F21CSS2姜姜 云云F20IS 關系子方式SNOCNOGRADES1C187S2C167一一 一對應一對應描畫關系是如何在物理存儲設備上存儲的。關描畫關系是如何在物理存儲設備上存儲的。關系存儲時的根本組織方式是文件。由于關系方系存儲時的根本組織方式是文件。由于關系方式有鍵，因此存儲一個關系可以用散列方法或式有鍵，因此存儲一個關系可以用散列方法或索引方法實現(xiàn)。假設關系中元組數(shù)目較少索引方法實現(xiàn)。假設關系中元組數(shù)目較少100以內(nèi)，那么也可以用堆文件方式實現(xiàn)。以內(nèi)，那么也可以用堆文件方式實現(xiàn)。此外，還可以對恣意的屬性集建立輔助索引。此外，還可以對恣意的屬性集建

14、立輔助索引。 存儲方式 關系模型中常用的關系操作包括查詢關系模型中常用的關系操作包括查詢Query操作操作和插入和插入Insert、刪除、刪除Delete、修正、修正Update操作。操作。查詢操作又可以分為：選擇查詢操作又可以分為：選擇Select、投影、投影Project、銜接、銜接Join、除、除Divide、并、并Union、差、差Except、交、交Intersection、笛卡爾積等。笛卡爾積等。根本操作：選擇、投影、并、差、笛卡爾積。根本操作：選擇、投影、并、差、笛卡爾積。其他操作：可以用根本操作來定義和導出的。其他操作：可以用根本操作來定義和導出的。關系操作的特點是集合操作方式

15、，即操作的對象和結關系操作的特點是集合操作方式，即操作的對象和結果都是集合。這種操作方式也稱稱為一次一集合果都是集合。這種操作方式也稱稱為一次一集合set-at-a-time的方式。相應地，非關系數(shù)據(jù)模型的方式。相應地，非關系數(shù)據(jù)模型的數(shù)據(jù)操作方式那么為一次一紀錄的數(shù)據(jù)操作方式那么為一次一紀錄record-at-a-time的方式。的方式。 3.1.2 關系操作 關系代數(shù)言語關系代數(shù)言語 例如例如 ISBL 元組關系演算言語元組關系演算言語 例如例如 APLHA，QUEL關系數(shù)據(jù)言語關系數(shù)據(jù)言語 關系演算言語關系演算言語 域關系演算言語域關系演算言語 例如例如 QBE 具有關系代數(shù)和關系演算雙

16、重特點的言語具有關系代數(shù)和關系演算雙重特點的言語 例如例如 SQL 關系言語是一種高度非過程化的言語，用戶關系言語是一種高度非過程化的言語，用戶不用懇求不用懇求DBA為其建立特殊的存取途徑，存取途為其建立特殊的存取途徑，存取途徑的選擇由徑的選擇由RDBMS的優(yōu)化機制來完成。的優(yōu)化機制來完成。 關系數(shù)據(jù)言語的分類關系數(shù)據(jù)言語分為三類：關系代數(shù)、元組關系關系數(shù)據(jù)言語分為三類：關系代數(shù)、元組關系演算和域關系演算。該三種言語在表達才干上演算和域關系演算。該三種言語在表達才干上是完全等價的。是完全等價的。 3.2 關系模型的完好性規(guī)那么主要內(nèi)容3.2.1 關系的三類完好性約束關系的三類完好性約束3.2.

17、2 實體完好性實體完好性3.2.3 參照完好性參照完好性3.2.4 用戶定義完好性用戶定義完好性關系模型的完好性規(guī)那么關系模型中有三類完好性約束：實體完好性、關系模型中有三類完好性約束：實體完好性、參照完好性和用戶定義的完好性。參照完好性和用戶定義的完好性。實體完好性和參照完好性是關系模型必需滿足實體完好性和參照完好性是關系模型必需滿足的完好性約束條件，被稱作是關系的兩個不變的完好性約束條件，被稱作是關系的兩個不變性，應該由關系系統(tǒng)自動支持。性，應該由關系系統(tǒng)自動支持。用戶定義的完好性是運用領域需求遵照的約束用戶定義的完好性是運用領域需求遵照的約束條件，表達了詳細領域中的語義約束。條件，表達了

18、詳細領域中的語義約束。 規(guī)那么規(guī)那么3.1 實體完好性實體完好性Entity Integrity規(guī)規(guī)那么：假設屬性指一個或一組屬性那么：假設屬性指一個或一組屬性A是根是根本關系本關系R的主屬性。那么的主屬性。那么A不能取空值。不能取空值。例如例如:在關系在關系S(SNO,SNAME,SEX,AGE,SDPET)中，中，SNO這個屬性為主碼，那么這個屬性為主碼，那么SNO不能取空值。不能取空值。3.2.1 關系的三類完好性約束 實體完好性要求關系中元組在組成主鍵的屬性上不能有空值。假設出現(xiàn)實體完好性要求關系中元組在組成主鍵的屬性上不能有空值。假設出現(xiàn)空值，那么主鍵值就起不了獨一標織元組的作用?？?/p>

19、值，那么主鍵值就起不了獨一標織元組的作用。對于實體完好性規(guī)那么幾點闡明 實體完好性規(guī)那么是針對根本關系而言的。一個實體完好性規(guī)那么是針對根本關系而言的。一個根本關系通常對應現(xiàn)實世界的一個實體集。例如學生根本關系通常對應現(xiàn)實世界的一個實體集。例如學生關系對應于學生的集合。關系對應于學生的集合。 現(xiàn)實世界中的實體是可區(qū)分的，即它們具有某種現(xiàn)實世界中的實體是可區(qū)分的，即它們具有某種獨一性標識。例如每個學生都是獨立的個體，是不一獨一性標識。例如每個學生都是獨立的個體，是不一樣的。樣的。 關系模型中以主碼作為獨一性標識。關系模型中以主碼作為獨一性標識。 主碼中的屬性即主屬性不能取空值。假設主屬性主碼中的

20、屬性即主屬性不能取空值。假設主屬性取空值，就闡明存在某個不可標識的實體，即存在不取空值，就闡明存在某個不可標識的實體，即存在不可區(qū)分的實體，這與第點相矛盾，因此這個規(guī)那么可區(qū)分的實體，這與第點相矛盾，因此這個規(guī)那么稱為實體完好性。稱為實體完好性。定義定義2.3 參照完好性規(guī)那么的方式定義如下：參照完好性規(guī)那么的方式定義如下：假設屬性集假設屬性集K是關系方式是關系方式R1的主鍵，的主鍵，K也是關也是關系方式系方式R2的外鍵，那么在的外鍵，那么在R2的關系中，的關系中，K的的取值只允許兩種能夠，或者為空值，或者等于取值只允許兩種能夠，或者為空值，或者等于R1關系中某個主鍵值。關系中某個主鍵值。 這

21、條規(guī)那么的本質是這條規(guī)那么的本質是“不允許援用不存在的實不允許援用不存在的實體。體。 在上述方式定義中，關系方式在上述方式定義中，關系方式R1的關系稱為的關系稱為“參照關系，關系方式參照關系，關系方式R2的關系稱為的關系稱為“依賴依賴關系。關系。參照完好性規(guī)那么由參照完好性建立了多表之間的對應關系由參照完好性建立了多表之間的對應關系參照完好性規(guī)那么舉例例例2.1 下面各種情況闡明了參照完好性規(guī)那么在關系下面各種情況闡明了參照完好性規(guī)那么在關系中如何實現(xiàn)的。中如何實現(xiàn)的。 在關系數(shù)據(jù)庫中有以下兩個關系方式：在關系數(shù)據(jù)庫中有以下兩個關系方式： SS#，SNAME，AGE，SEX SCS#，C#，G

22、RADE據(jù)規(guī)那么要求，關系據(jù)規(guī)那么要求，關系SC中的中的S# 值應該在關系值應該在關系S中出中出現(xiàn)。假設關系現(xiàn)。假設關系SC中有一個元組中有一個元組S7,C4,80，而學，而學號號S7卻在關系卻在關系S中找不到，那么我們就以為在關系中找不到，那么我們就以為在關系SC中援用了一個不存在的學生實體，這就違反了參中援用了一個不存在的學生實體，這就違反了參照完好性規(guī)那么。照完好性規(guī)那么。另外，在關系另外，在關系SC中中S#不僅是外鍵，也是主鍵的一部不僅是外鍵，也是主鍵的一部分，因此這里分，因此這里S# 值不允許空。值不允許空。 設工廠數(shù)據(jù)庫中有兩個關系方式：設工廠數(shù)據(jù)庫中有兩個關系方式：DEPT(D#

23、，DNAME)EMP(E#，ENAME，SALARY，D# )車間方式車間方式DEPT的屬性為車間編號、車間名，的屬性為車間編號、車間名，職工方式職工方式EMP的屬性為工號、姓名、工資、的屬性為工號、姓名、工資、所在車間的編號。每個方式的主鍵與外鍵已標所在車間的編號。每個方式的主鍵與外鍵已標出。在出。在EMP中，由于中，由于D#不在主鍵中，因此不在主鍵中，因此D# 值允許空。值允許空。參照完好性規(guī)那么舉例參照完好性規(guī)那么舉例 設課程之間有先修、后繼聯(lián)絡。方式如下：設課程之間有先修、后繼聯(lián)絡。方式如下：R(C# ，CNAME，PC# )其屬性表示課程號、課程名、先修課的課程號。其屬性表示課程號、

24、課程名、先修課的課程號。假設規(guī)定，每門課程的直接先修課只需一門，假設規(guī)定，每門課程的直接先修課只需一門，那么方式那么方式R的主鍵是的主鍵是C#，外鍵是，外鍵是PC#.。這里。這里參照完好性在一個方式中實現(xiàn)。即每門課程的參照完好性在一個方式中實現(xiàn)。即每門課程的直接先修課必需在關系中出現(xiàn)。直接先修課必需在關系中出現(xiàn)。 用戶定義的完好性規(guī)那么 在建立關系方式時，對屬性定義了數(shù)據(jù)類型，在建立關系方式時，對屬性定義了數(shù)據(jù)類型，即使這樣能夠還滿足不了用戶的需求。此時，即使這樣能夠還滿足不了用戶的需求。此時，用戶可以針對詳細的數(shù)據(jù)約束，設置完好性規(guī)用戶可以針對詳細的數(shù)據(jù)約束，設置完好性規(guī)那么，由系統(tǒng)來檢驗實

25、施，以運用一致的方法那么，由系統(tǒng)來檢驗實施，以運用一致的方法處置它們，不再由運用程序承當這項任務。例處置它們，不再由運用程序承當這項任務。例如學生的年齡定義為兩位整數(shù)，范圍還太大，如學生的年齡定義為兩位整數(shù)，范圍還太大，我們可以寫如下規(guī)那么把年齡限制在我們可以寫如下規(guī)那么把年齡限制在1530歲之間：歲之間：CHECKAGE BETWEEN 15 AND 303.3 關系代數(shù)的根本運算 主要內(nèi)容 傳統(tǒng)的集合運算傳統(tǒng)的集合運算專門的關系運算專門的關系運算關系代數(shù)表達式及其運用實例關系代數(shù)表達式及其運用實例 并并Union設關系設關系R和和S具有一樣的關系方式，具有一樣的關系方式，R和和S的并的并是

26、由屬于是由屬于R或屬于或屬于S的元組構成的集合，記為的元組構成的集合，記為RS。方式定義如下：。方式定義如下：RSt | tR tS，t是元組變量，是元組變量，R和和S的元數(shù)一樣。的元數(shù)一樣。差差Difference設關系設關系R和和S具有一樣的關系方式，具有一樣的關系方式，R和和S的差的差是由屬于是由屬于R但不屬于但不屬于S的元組構成的集合，記的元組構成的集合，記為為RS。方式定義如下：。方式定義如下：RS t | tR tS，R和和S的元數(shù)一樣。的元數(shù)一樣。 傳統(tǒng)的集合運算舉例關系運算舉例關系運算舉例交運算 交交intersection關系關系R和和S的交是由屬于的交是由屬于R又屬于又屬于

27、S的元組構成的元組構成的集合，記為的集合，記為RS，這里要求，這里要求R和和S定義在一定義在一樣的關系方式上。方式定義如下：樣的關系方式上。方式定義如下：RSttR tS，R和和S的元數(shù)一樣。的元數(shù)一樣。ABCa1a1a2b1b2b2c1c2c1ABCa1a1a2b2b3b2c2c2c1bBCa1 a2b2 b2c2 c1例例 R S R S 笛卡兒積運算 假設假設R有有m個元組，個元組，S有有n個元組，那么個元組，那么RS有有mn個元組。個元組。笛卡兒積笛卡兒積(Cartesian Product) 設關系設關系R和和S的元數(shù)分別為的元數(shù)分別為r和和s,定義定義R和和S的的一個一個(r+s)

28、元的元組集合，每個元組的前元的元組集合，每個元組的前r個分個分量來自量來自R的一個元組，后的一個元組，后s個分量來自個分量來自S的一個的一個元組，記為元組，記為RS。RS t|t=trRtsS專門的關系運算選擇選擇Selection選擇操作是根據(jù)某些條件對關系做程度分割，即選取符合條件的元組。選擇操作是根據(jù)某些條件對關系做程度分割，即選取符合條件的元組。條件可用命題公式即計算機言語中的條件表達式條件可用命題公式即計算機言語中的條件表達式F表示。表示。F中的根本方式為：中的根本方式為：X1Y1：其中其中表示比較運算符表示比較運算符:，。，。X1，Y1等是屬性名，常量，或列序號。等是屬性名，常量，

29、或列序號。關系關系R關于公式關于公式F的選擇操作用的選擇操作用FR表示，方式定義為：表示，方式定義為：FR t | tR Ft= true 為選擇運算符，為選擇運算符，F(xiàn)R表示從表示從R中挑選滿足公式中挑選滿足公式F為真的元組所構為真的元組所構成的關系。成的關系。例如，例如，23R表示從表示從R中挑選第中挑選第2個分量值大于個分量值大于3的的元組所構成的關系。書寫時，為了與屬性序號區(qū)別起見，常量用引號元組所構成的關系。書寫時，為了與屬性序號區(qū)別起見，常量用引號括起來，而屬性序號或屬性名不要用引號括起來。括起來，而屬性序號或屬性名不要用引號括起來。投影Projection)這個操作是對一個關系進

30、展垂直分割，消去某些列，這個操作是對一個關系進展垂直分割，消去某些列，并重新安陳列的順序。并重新安陳列的順序。 設關系設關系R是是k元關系，元關系，R在其分量在其分量Ai1，Aimmk i1，im ，為，為1到到k間的整數(shù)上的投影用間的整數(shù)上的投影用i1,.,imR表示，它是一個表示，它是一個m元元組集合，方式元元組集合，方式定義為：定義為：i1，imR t | tti1，timt1，tkR 例如，例如，3，1R表示關系表示關系R中取第中取第1、3列，組成列，組成新的關系，新關系中第新的關系，新關系中第1列為列為R的第的第3列，新關系的第列，新關系的第2列為列為R的第的第1列。假設列。假設R的

31、每列標上屬性名，那么操的每列標上屬性名，那么操作符作符的下標處也可以用屬性名表示。例如，關系的下標處也可以用屬性名表示。例如，關系RA，B，C，那么，那么C，AR與與3，1R是是等價的。等價的。 銜接有兩種：銜接有兩種：銜接和銜接和F銜接這里銜接這里是算術比較符，是算術比較符，F(xiàn)是公式。是公式。 銜接銜接 R St t= trR tsS 表達式表達式 表示元組表示元組tr的第的第i個分量、元組個分量、元組ts的第的第j個個分量滿足分量滿足操作。操作。 F銜接銜接 F銜接是從關系銜接是從關系R和和S的笛卡兒積中選取屬性間滿足的笛卡兒積中選取屬性間滿足某一公式某一公式F的元組的元組, 這里這里F是

32、形為是形為F1F2Fn的的公式，每個公式，每個FP是形是形ij的式子，而的式子，而i和和j分別為關系分別為關系R和和S的第的第i、第、第j個分量的序號。個分量的序號。銜接join運算ij例例 銜接和銜接和F銜接的例子銜接的例子.闡明: 1. 也可以寫成。24RS)2.。銜接運算舉例 兩個關系兩個關系R和和S的自然銜接的自然銜接 操作詳細操作詳細計算過程如下：計算過程如下： 計算計算RS ； 設設R和和S的公共屬性是的公共屬性是A1,AK，挑選，挑選RS中滿足中滿足R.A1=S.A1，R.AK=S.AK的那些的那些元組；元組； 去掉去掉S.A1，S.AK這些列。這些列。定義：定義：中中i1,im

33、為為R和和S的全部屬性，但公共屬性只的全部屬性，但公共屬性只出現(xiàn)一次。出現(xiàn)一次。)(.R.A.,.,ik111SRkmASASARi自然銜接natural joinABCa1a1a2a2b1b2b3b456812BEb1b2b3b3b5371022AR.BCS.BEa1a1a1a1a2b1 b1 b2 b2 b355668b2 b3 b2 b3 b37 10 7 10 10AR.BCS.BEa1a1a2a2b1b2b3b35688b1b2b3b337102ABCEa1a1a2a2b1b2b3b3568837102關系關系R關系關系S普通銜接普通銜接 R SCER.Cs0，那么那么RS是一個是一

34、個r-s元的元組的集合。元的元組的集合。RS是滿足以下條件的最大關系：其中每是滿足以下條件的最大關系：其中每個元組個元組t與與S中每個元組中每個元組u組成的新元組組成的新元組必在關系必在關系R中。中。 RS1,2,r-sR- 1,2,r-s (1,2,r-s(R)S)-R) 除法舉例除法舉例關系代數(shù)運算的運用實例(1) 在關系代數(shù)運算中，把由五個根本操作經(jīng)過有限次復合的式子稱為關系代數(shù)表達式。在關系代數(shù)運算中，把由五個根本操作經(jīng)過有限次復合的式子稱為關系代數(shù)表達式。這種表達式的運算結果仍是一個關系。這種表達式的運算結果仍是一個關系。 例例2.7 設教學數(shù)據(jù)庫中有三個關系：設教學數(shù)據(jù)庫中有三個關

35、系： 學生關系學生關系 S(S#,SNAME,AGE,SEX) 選課關系選課關系 SC(S#,C#,GRADE) 課程關系課程關系 C(C#,CNAME,TEACHER) 用關系代數(shù)表達式表示查詢語句。用關系代數(shù)表達式表示查詢語句。 (1) 檢索學習課程號為檢索學習課程號為C2的學生學號與成果。的學生學號與成果。 S#,GRADE(C#=C2 (SC) (2) 檢索學習課程號為檢索學習課程號為C2的學生的學號與姓名。的學生的學號與姓名。 S#,SNAME(C#=C2 (S SC) (3) 檢索選修課程名為檢索選修課程名為MATHS的學生學號與姓名。的學生學號與姓名。 S#,SNAME(CNAM

36、E=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,可以用自然銜接和投影操作

37、組合而成: 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ù)運算的運用實例關系代數(shù)運算的運用實例(2)關系代數(shù)運算的運用實例關系代數(shù)運算的運用實例(3)普通地有以下規(guī)律：普通地有以下規(guī)律：(1) 對于只涉及到選

38、擇、投影、銜接的查詢可用以下表達式表示：對于只涉及到選擇、投影、銜接的查詢可用以下表達式表示： (RS) 或者或者(R S)(2) 對于否認的操作，普通要用差操作表示，例如對于否認的操作，普通要用差操作表示，例如“檢索不學檢索不學C2課的課的學生姓名。用以下表達式表示：學生姓名。用以下表達式表示： SNAME(S)-SNAME(CNO=C2(S SC)但不能用下式但不能用下式表示：表示： SNAME(CNOC2(S SC) 對于檢索具有對于檢索具有“全部特征的操作，普通要用除法操作表示，例如全部特征的操作，普通要用除法操作表示，例如“檢索學習全部課程的學生學號。用以下表達式表示：檢索學習全部課

39、程的學生學號。用以下表達式表示： 要用要用SNO,CNO(SC)CNO(C)表示，而不能寫成表示，而不能寫成 SNO (SCCNO(C)方式。方式。 這是由于一個學生學的課程的成果能夠是不一樣的。這是由于一個學生學的課程的成果能夠是不一樣的。 3.5 查詢優(yōu)化 主要內(nèi)容查詢優(yōu)化的普通戰(zhàn)略查詢優(yōu)化的普通戰(zhàn)略代數(shù)表達式的等價變換規(guī)那么代數(shù)表達式的等價變換規(guī)那么優(yōu)化算法優(yōu)化算法 例例 設關系設關系R和和S都是二元關系，屬性名分別為都是二元關系，屬性名分別為A，B和和C，D。 設有一個查詢可用關系代數(shù)表達式表示：設有一個查詢可用關系代數(shù)表達式表示： E1=AB=CD=99RS 也可以把選擇條件也可以把

40、選擇條件D=99移到笛卡兒積中的關系移到笛卡兒積中的關系S前面：前面： E2=AB=CRD=99S 還可以把選擇條件還可以把選擇條件BC與笛卡兒積結合成等值銜接方式：與笛卡兒積結合成等值銜接方式： E3=AR D=99S 這三個關系代數(shù)表達式是等價的，但執(zhí)行的效率大不一樣。顯然，這三個關系代數(shù)表達式是等價的，但執(zhí)行的效率大不一樣。顯然，求求El，E2，E3的大部分時間是花在銜接操作上的。的大部分時間是花在銜接操作上的。 查詢優(yōu)化例子 可以分析出，在時空性能上，E3最優(yōu)，其次是E2，最后是E1。此例還可以看出，如何安排選擇、投影和銜接的順序是個很重要的問題。查詢優(yōu)化的普通戰(zhàn)略 (1)在關系代數(shù)表

41、達式中需求指出假設干關系的操在關系代數(shù)表達式中需求指出假設干關系的操作步驟。那么，系統(tǒng)應該以什么樣的操作順序，作步驟。那么，系統(tǒng)應該以什么樣的操作順序，才干做到既省時間，又省空間，而且效率也比才干做到既省時間，又省空間，而且效率也比較高呢？這個問題稱為查詢優(yōu)化問題。較高呢？這個問題稱為查詢優(yōu)化問題。查詢優(yōu)化是實現(xiàn)關系系統(tǒng)的關鍵技術查詢優(yōu)化是實現(xiàn)關系系統(tǒng)的關鍵技術,它大大它大大減輕了用戶選擇存取途徑的負擔減輕了用戶選擇存取途徑的負擔,用戶運用關用戶運用關系系統(tǒng)時系系統(tǒng)時,只需提出只需提出“做什么做什么,不用指出不用指出“怎樣怎樣做。做。在關系代數(shù)運算中，笛卡兒積和銜接運算是最在關系代數(shù)運算中，笛

42、卡兒積和銜接運算是最費時間的。費時間的。查詢優(yōu)化的普通戰(zhàn)略 (2)查詢優(yōu)化采用的普通戰(zhàn)略是：查詢優(yōu)化采用的普通戰(zhàn)略是： 盡能夠早地執(zhí)行選擇運算。在查詢中這種變換最為重要，由于它可以盡能夠早地執(zhí)行選擇運算。在查詢中這種變換最為重要，由于它可以以元組為單位減小中間結果，從而使執(zhí)行時間成數(shù)量級地減少。以元組為單位減小中間結果，從而使執(zhí)行時間成數(shù)量級地減少。 把先做笛卡兒積，后做選擇結合起來。使之成為一個銜接運算。銜接把先做笛卡兒積，后做選擇結合起來。使之成為一個銜接運算。銜接運算特別是等值銜接要比笛卡兒積運算效率高得很多。當對笛卡兒運算特別是等值銜接要比笛卡兒積運算效率高得很多。當對笛卡兒積積RS的

43、結果再做選擇時，并且這個選擇是對的結果再做選擇時，并且這個選擇是對R和和S的屬性進展比較，在的屬性進展比較，在這樣的條件下，這個笛卡兒積和選擇運算等價于一個銜接。這樣的條件下，這個笛卡兒積和選擇運算等價于一個銜接。 普通對不含普通對不含R的屬性或不含的屬性或不含S的屬性的比較，可以移到笛卡兒積運算前去做，這樣做的屬性的比較，可以移到笛卡兒積運算前去做，這樣做比轉換到銜接更好。比轉換到銜接更好。 同時計算一串選擇和一串投影運算，以免分開運算呵斥多次掃描文件，同時計算一串選擇和一串投影運算，以免分開運算呵斥多次掃描文件，從而節(jié)省了操作時間。從而節(jié)省了操作時間。 找出表達式里的公共子表達式。假設公共

44、子表達式的結果不是很大，找出表達式里的公共子表達式。假設公共子表達式的結果不是很大，并且從外存讀入比起計算它要節(jié)省許多時間，那么，預先計算一下這個并且從外存讀入比起計算它要節(jié)省許多時間，那么，預先計算一下這個公共子表達式是有益處的。公共子表達式是有益處的。子表達式內(nèi)涉及到銜接，但又不能把限定條件向內(nèi)移入的那類表達式，子表達式內(nèi)涉及到銜接，但又不能把限定條件向內(nèi)移入的那類表達式，普通屬于這一類。普通屬于這一類。 銜接和笛卡兒積的交換律銜接和笛卡兒積的交換律 E1 E2E2 E1 E1 E2 E2 E1 E1 E2E2 E1 E1 E2 E2 E1 E1E1E2 E1E2 E1E2E2銜接和笛卡兒

45、積的結合律銜接和笛卡兒積的結合律 (E1 E2 (E1 E2 E3E1 (E2 E3) E3E1 (E2 E3) (E1 E2) E3E1 (E2 E3) (E1 E2) E3E1 (E2 E3) (E1 (E1E2)E2)E3 E1E3 E1(E2(E2E3)E3)投影的串接投影的串接 設設L1,L1,設設L2,LnL2,Ln為屬性集，并為屬性集，并且且 , ,那么下式也成立那么下式也成立. .選擇的串接選擇的串接代數(shù)表達式的等價變換規(guī)那么 (1)LnLL.21)().)(.(121EELLnLL）（成立：，因此選擇的交換律也由于E)E(F1F2F2F1)()(F1F2F2F12121EEF

46、FFFv 選擇和投影操作的交換選擇和投影操作的交換代數(shù)表達式的等價變換規(guī)那么 (2)(（ )(1)()(1 LEE：，LLF，LFEELLFFLLFFL那么有下式成立中的屬性集還涉及到不在如果條件中的屬性只涉及到這里要求v 選擇對笛卡兒積的分配律 2) 1()21(EEEEFF 這里要求F只涉及到E1中的屬性。假設F形為F1F2，且F1只涉及到E1的屬性，F(xiàn)2只涉及到E2的屬性，那么有)2() 1()21(21EEEEFFF 此外，假設F形為F1F2，且F1只涉及到E1的屬性，F(xiàn)2只涉及到E1和E2的屬性，那么有：)2) 1()21(12EEEEFFFv 選擇對并的分配律v E1和E2具有一樣

47、的屬性名，或者E1和E2表達的關系的屬性有對應性，那么有：)2() 1()21(EEEEFFF代數(shù)表達式的等價變換規(guī)那么(3)v 選擇對集合差的分配律v E1和E2的屬性有對應性，那么有：2) 1()21()2() 1()21(EEEEEEEEFFFFF或v 選擇對自然聯(lián)接的分配律v F只涉及到表達式E1和E2的公共屬性，那么有：v E1 E2 E1 E2FFFv 投影對笛卡爾的分配律v L1是E1中的屬性集，L2是E2中的屬性集，那么有：)2() 1()21(2121EEEELLLLv 投影對并的分配律v E1和E2的屬性有對應性，那么有：)2() 1()21(EEEELLL代數(shù)表達式的等價

48、變換規(guī)那么 (4)v 選擇與聯(lián)接操作的結合 FE1E2E1E21FE1E2E1E2v 并和交的交換律v E1E2E2E1v E1E2E2E1v 并和交的結合律v E1E2E3E1E2E3v E1E2E3E1E2E3優(yōu)化算法 (1) 代數(shù)優(yōu)化是利用上面的等價變換規(guī)那么，對代數(shù)優(yōu)化是利用上面的等價變換規(guī)那么，對關系表達式進展優(yōu)化，以減少執(zhí)行時的開銷。雖關系表達式進展優(yōu)化，以減少執(zhí)行時的開銷。雖然不能保證最優(yōu)，但在多數(shù)情況下能使表達式更然不能保證最優(yōu)，但在多數(shù)情況下能使表達式更好些。在關系代數(shù)表達式中，最破費時間和空間好些。在關系代數(shù)表達式中，最破費時間和空間的運算是笛卡兒積和銜接操作，為此，引出三條的運算是笛卡兒積和銜接操作，為此，引出三條啟發(fā)式規(guī)那么，用于對表達式進展轉換，以減少啟發(fā)式規(guī)那么，用于對表達式進展轉換，以減少中間關系的大小。中間關系的大小。優(yōu)先運用單項的選擇和投影；優(yōu)先運用單項的選擇和投影；優(yōu)先運用普通選擇和投影；優(yōu)先運用普通選擇和投影；對笛卡兒積、并運算、差運算，假設它們前對笛卡兒積、并運算、差運算，假設它們前面加有選擇和投影，那么先做選擇和投影。面加有選擇和投影，那么先做選擇和投影。 優(yōu)化算法 (2)算法：關系代數(shù)表達式的優(yōu)化。算法：關系代數(shù)表達式的優(yōu)化。 輸入：一個關系代數(shù)表達式的語法樹輸入：一個關系代數(shù)表達式的語法樹 輸出：計算表達式的一個