第三章關(guān)系數(shù)據(jù)庫基本理論

第三章關(guān)系數(shù)據(jù)庫基本理論本章重要概念(1)基本概念 關(guān)系數(shù)據(jù)模型，關(guān)鍵碼（主鍵和外鍵），關(guān)系的定義和性質(zhì)，三類完整性規(guī)則，ER模型到關(guān)系模型的轉(zhuǎn)換規(guī)則，過程性語言與非過程性語言。(2) 五個基本操作，四個組合操作，七個擴充操作。(3)關(guān)系代數(shù)表達式的優(yōu)化 關(guān)系代數(shù)表達式的等價及等價轉(zhuǎn)換規(guī)則，啟化式優(yōu)化算法。主要內(nèi)容3.1關(guān)系數(shù)據(jù)模型3.1.1關(guān)系模式3.1.2關(guān)系操作3.2關(guān)系模型的完整性規(guī)則3.2.1關(guān)系的三類完整性約束3.2.2實體完整性3.2.3參照完整性3.2.4用戶自定義完整性3.3關(guān)系代數(shù)的基本運算3.3.1傳統(tǒng)的集合運算3.3.2專門的關(guān)系運算3.3.3關(guān)系代數(shù)表達式及其應用實例*3.4關(guān)系演算元組關(guān)系演算域關(guān)系演算3.5查詢優(yōu)化3.5.1查詢優(yōu)化的一般策略3.5.2代數(shù)表達式的等價變換規(guī)則3.5.3優(yōu)化算法3.1關(guān)系數(shù)據(jù)模型3.1.1關(guān)系模式

每個關(guān)系都有一個模式，稱為關(guān)系模式(RelationSchema)，由一個關(guān)系名及它的所有屬性名構(gòu)成。在關(guān)系模式中，字段稱為屬性，字段值稱為屬性值，記錄類型稱為關(guān)系模式。在圖3.1中：關(guān)系模式名是R記錄稱為元組（tuple）元組的集合稱為關(guān)系（relation）或?qū)嵗╥nstance）一般用前面的大寫英語字母A、B、C、…表示單個屬性，用后面的大寫字母…、W、X、Y、Z表示屬性集，用小寫字母表示屬性值。數(shù)據(jù)庫技術(shù)的術(shù)語關(guān)系模型的術(shù)語ABCDEa1b1c1d1e1a2b2c2d2e2a3b3c3d3e3

數(shù)據(jù)庫技術(shù)的術(shù)語關(guān)系模型的術(shù)語字段,數(shù)據(jù)項屬性記錄類型關(guān)系模式記錄1元組1記錄2元組2記錄3元組3字段值屬性值文件關(guān)系（或?qū)嵗╆P(guān)系具有的特點⑴關(guān)系（表）可以看成是由行和列交叉組成的二維表格。它表示的是一個實體集合。⑵表中一行稱為一個元組，可用來表示實體集中的一個實體。⑶表中的列稱為屬性，給每一列起一個名稱即屬性名，表中的屬性名不能相同。⑷列的取值范圍稱為域，同列具有相同的域，不同的列可有相同的域。例如，SEX的取值范圍是{M（男），F(xiàn)（女）}，AGE為整數(shù)域。⑸表中任意兩行（元組）不能相同。能惟一標識表中不同行的屬性或?qū)傩越M稱為主鍵。關(guān)系的性質(zhì)屬性值是原子的，不可分解。沒有重復元組。沒有行序。理論上沒有列序，但一般使用時都有列序。關(guān)鍵碼和表之間的聯(lián)系超鍵：在一個關(guān)系中，能惟一標識元組的屬性或?qū)傩约Q為關(guān)系的超鍵。候選鍵：如果一個屬性集能惟一標識元組，且又不含有多余的屬性，那么這個屬性集稱為關(guān)系的候選鍵。主鍵：若一個關(guān)系中有多個候選鍵，則選其中的一個為關(guān)系的主鍵。外鍵：若一個關(guān)系R中包含有另一個關(guān)系S的主鍵所對應的屬性組F，則稱F為R的外鍵。并稱關(guān)系S為參照關(guān)系，關(guān)系R為依賴關(guān)系。關(guān)系模式舉例例如，學生關(guān)系和系部關(guān)系分別為：學生（SNO，SNAME，SEX，AGE，SDNO）系部（SDNO，SDNAME，CHAIR）學生關(guān)系的主鍵是SNO，系部關(guān)系的主鍵為SDNO，在學生關(guān)系中，SDNO是它的外鍵。更確切地說，SDNO是系部表的主鍵，將它作為外鍵放在學生表中，實現(xiàn)兩個表之間的聯(lián)系。在關(guān)系數(shù)據(jù)庫中，表與表之間的聯(lián)系就是通過公共屬性實現(xiàn)的。我們約定，在主鍵的屬性下面加下劃線，在外鍵的屬性下面加波浪線。關(guān)系模式、關(guān)系子模式和存儲模式SNOSNAMEAGESEXSDEPTSCCNOCNAMECDEPTETNAMESCMNGRADE例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圖）。

關(guān)系模式是對關(guān)系的描述，它包括模式名，組成該關(guān)系的諸屬性名、值域名和模式的集合。具體的關(guān)系稱為實例。關(guān)系模式該圖表示的學生情況的部分轉(zhuǎn)換成相應的關(guān)系模式為：S(SNO,SNAME,SEX,AGE,SDPET)關(guān)系模式S描述了學生的數(shù)據(jù)結(jié)構(gòu)，它是下表中學生實體的關(guān)系模式。其中SNO，CNO為關(guān)系SC的主鍵，SNO、CNO又分別為關(guān)系SC的兩個外鍵。SNOSNAMESEXAGESDEPTS1程曉晴F21CSS2姜云F20ISS3李小剛M21CS

學生關(guān)系模式S(SNO，SNAME，SEX，AGE，SDPET)選修關(guān)系模式SC(SNO，CNO，GRADE)課程關(guān)系模式C(CNO，CNAME，CDEPT，TNAME)SNOCNOGRADES1C187S1C278S1C390S2C167S2C279S2C356S3C180S3C276S3C392學生關(guān)系實例如下表；選修關(guān)系實例如右表。關(guān)系模式(9)

CNOCNAMECDEPTTNAMEC1高等數(shù)學IS王紅衛(wèi)C2數(shù)據(jù)庫原理CS李紹麗C3數(shù)據(jù)結(jié)構(gòu)CS劉良課程關(guān)系實例如下表：關(guān)系子模式用戶使用的數(shù)據(jù)不直接來自關(guān)系模式中的數(shù)據(jù)，而是從若干關(guān)系模式中抽取滿足一定條件的數(shù)據(jù)構(gòu)成關(guān)系子模式。關(guān)系子模式是用戶所需數(shù)據(jù)結(jié)構(gòu)的描述，其中包括這些數(shù)據(jù)來自哪些模式和應滿足哪些條件。例3.2用戶需要用到成績子模式G(SNO,SNAME,CNO,GRADE)。子模式G對應的數(shù)據(jù)來源于表S和表SC，構(gòu)造時應滿足它們的SNO值相等。子模式G的構(gòu)造過程如下圖所示。SNOSNAMECNOGRADES1程曉晴C187S2姜云C167…………SNOSNAMESEXAGESDEPTS1程曉晴F21CSS2姜云F20IS…………

…關(guān)系子模式SNOCNOGRADES1C187S2C167………一一對應描述關(guān)系是如何在物理存儲設(shè)備上存儲的。關(guān)系存儲時的基本組織方式是文件。由于關(guān)系模式有鍵，因此存儲一個關(guān)系可以用散列方法或索引方法實現(xiàn)。如果關(guān)系中元組數(shù)目較少（100以內(nèi)），那么也可以用堆文件方式實現(xiàn)。此外，還可以對任意的屬性集建立輔助索引。存儲模式

關(guān)系模型中常用的關(guān)系操作包括查詢（Query）操作和插入（Insert）、刪除（Delete）、修改（Update）操作。查詢操作又可以分為：選擇（Select）、投影（Project）、連接（Join）、除（Divide）、并（Union）、差（Except）、交（Intersection）、笛卡爾積等?；静僮鳎哼x擇、投影、并、差、笛卡爾積。其他操作：可以用基本操作來定義和導出的。關(guān)系操作的特點是集合操作方式，即操作的對象和結(jié)果都是集合。這種操作方式也稱稱為一次一集合（set-at-a-time）的方式。相應地，非關(guān)系數(shù)據(jù)模型的數(shù)據(jù)操作方式則為一次一紀錄（record-at-a-time）的方式。3.1.2關(guān)系操作

關(guān)系代數(shù)語言例如ISBL

元組關(guān)系演算語言例如APLHA，QUEL關(guān)系數(shù)據(jù)語言關(guān)系演算語言域關(guān)系演算語言例如QBE

具有關(guān)系代數(shù)和關(guān)系演算雙重特點的語言例如SQL

關(guān)系語言是一種高度非過程化的語言，用戶不必請求DBA為其建立特殊的存取路徑，存取路徑的選擇由RDBMS的優(yōu)化機制來完成。

關(guān)系數(shù)據(jù)語言的分類關(guān)系數(shù)據(jù)語言分為三類：關(guān)系代數(shù)、元組關(guān)系演算和域關(guān)系演算。該三種語言在表達能力上是完全等價的。3.2關(guān)系模型的完整性規(guī)則主要內(nèi)容3.2.1關(guān)系的三類完整性約束3.2.2實體完整性3.2.3參照完整性3.2.4用戶定義完整性關(guān)系模型的完整性規(guī)則關(guān)系模型中有三類完整性約束：實體完整性、參照完整性和用戶定義的完整性。實體完整性和參照完整性是關(guān)系模型必須滿足的完整性約束條件，被稱作是關(guān)系的兩個不變性，應該由關(guān)系系統(tǒng)自動支持。用戶定義的完整性是應用領(lǐng)域需要遵循的約束條件，體現(xiàn)了具體領(lǐng)域中的語義約束。

規(guī)則3.1實體完整性（EntityIntegrity）規(guī)則：若屬性（指一個或一組屬性）A是基本關(guān)系R的主屬性。則A不能取空值。例如:在關(guān)系S(SNO,SNAME,SEX,AGE,SDPET)中，SNO這個屬性為主碼，則SNO不能取空值。3.2.1關(guān)系的三類完整性約束

實體完整性要求關(guān)系中元組在組成主鍵的屬性上不能有空值。如果出現(xiàn)空值，那么主鍵值就起不了惟一標織元組的作用。對于實體完整性規(guī)則幾點說明⑴實體完整性規(guī)則是針對基本關(guān)系而言的。一個基本關(guān)系通常對應現(xiàn)實世界的一個實體集。例如學生關(guān)系對應于學生的集合。⑵現(xiàn)實世界中的實體是可區(qū)分的，即它們具有某種唯一性標識。例如每個學生都是獨立的個體，是不一樣的。⑶關(guān)系模型中以主碼作為唯一性標識。⑷主碼中的屬性即主屬性不能取空值。如果主屬性取空值，就說明存在某個不可標識的實體，即存在不可區(qū)分的實體，這與第⑵點相矛盾，因此這個規(guī)則稱為實體完整性。定義2.3參照完整性規(guī)則的形式定義如下：如果屬性集K是關(guān)系模式R1的主鍵，K也是關(guān)系模式R2的外鍵，那么在R2的關(guān)系中，K的取值只允許兩種可能，或者為空值，或者等于R1關(guān)系中某個主鍵值。這條規(guī)則的實質(zhì)是“不允許引用不存在的實體”。在上述形式定義中，關(guān)系模式R1的關(guān)系稱為“參照關(guān)系”，關(guān)系模式R2的關(guān)系稱為“依賴關(guān)系”。參照完整性規(guī)則由參照完整性建立了多表之間的對應關(guān)系參照完整性規(guī)則舉例例2.1下面各種情況說明了參照完整性規(guī)則在關(guān)系中如何實現(xiàn)的。 ①在關(guān)系數(shù)據(jù)庫中有下列兩個關(guān)系模式：

S（S#，SNAME，AGE，SEX）

SC（S#，C#，GRADE）據(jù)規(guī)則要求，關(guān)系SC中的S#值應該在關(guān)系S中出現(xiàn)。如果關(guān)系SC中有一個元組（S7,C4,80），而學號S7卻在關(guān)系S中找不到，那么我們就認為在關(guān)系SC中引用了一個不存在的學生實體，這就違反了參照完整性規(guī)則。另外，在關(guān)系SC中S#不僅是外鍵，也是主鍵的一部分，因此這里S#值不允許空。②設(shè)工廠數(shù)據(jù)庫中有兩個關(guān)系模式：

DEPT(D#，DNAME) EMP(E#，ENAME，SALARY，D#)車間模式DEPT的屬性為車間編號、車間名，職工模式EMP的屬性為工號、姓名、工資、所在車間的編號。每個模式的主鍵與外鍵已標出。在EMP中，由于D#不在主鍵中，因此D#值允許空。參照完整性規(guī)則舉例參照完整性規(guī)則舉例③設(shè)課程之間有先修、后繼聯(lián)系。模式如下：

R(C#，CNAME，PC#)其屬性表示課程號、課程名、先修課的課程號。如果規(guī)定，每門課程的直接先修課只有一門，那么模式R的主鍵是C#，外鍵是PC#.。這里參照完整性在一個模式中實現(xiàn)。即每門課程的直接先修課必須在關(guān)系中出現(xiàn)。用戶定義的完整性規(guī)則

在建立關(guān)系模式時，對屬性定義了數(shù)據(jù)類型，即使這樣可能還滿足不了用戶的需求。此時，用戶可以針對具體的數(shù)據(jù)約束，設(shè)置完整性規(guī)則，由系統(tǒng)來檢驗實施，以使用統(tǒng)一的方法處理它們，不再由應用程序承擔這項工作。例如學生的年齡定義為兩位整數(shù)，范圍還太大，我們可以寫如下規(guī)則把年齡限制在15～30歲之間：CHECK（AGEBETWEEN15AND30）3.3關(guān)系代數(shù)的基本運算主要內(nèi)容

傳統(tǒng)的集合運算專門的關(guān)系運算關(guān)系代數(shù)表達式及其應用實例并（Union）設(shè)關(guān)系R和S具有相同的關(guān)系模式，R和S的并是由屬于R或?qū)儆赟的元組構(gòu)成的集合，記為R∪S。形式定義如下：R∪S≡{t|t∈R∨t∈S}，t是元組變量，R和S的元數(shù)相同。差（Difference）設(shè)關(guān)系R和S具有相同的關(guān)系模式，R和S的差是由屬于R但不屬于S的元組構(gòu)成的集合，記為R－S。形式定義如下：R－S≡{t|t∈R∧t∈S}，R和S的元數(shù)相同。傳統(tǒng)的集合運算舉例關(guān)系運算舉例交運算

交（intersection）關(guān)系R和S的交是由屬于R又屬于S的元組構(gòu)成的集合，記為R∩S，這里要求R和S定義在相同的關(guān)系模式上。形式定義如下：R∩S≡{t︱t∈R∧t∈S}，R和S的元數(shù)相同。ABCa1a1a2b1b2b2c1c2c1ABCa1a1a2b2b3b2c2c2c1bBCa1a2b2b2c2c1例

R

S

R

∩S笛卡兒積運算

若R有m個元組，S有n個元組，則R×S有m×n個元組。笛卡兒積(CartesianProduct)

設(shè)關(guān)系R和S的元數(shù)分別為r和s,定義R和S的一個(r+s)元的元組集合，每個元組的前r個分量來自R的一個元組，后s個分量來自S的一個元組，記為R×S。R×S≡{t|t=<tr,ts>∧tr∈R∧ts∈S}專門的關(guān)系運算選擇（Selection）選擇操作是根據(jù)某些條件對關(guān)系做水平分割，即選取符合條件的元組。條件可用命題公式（即計算機語言中的條件表達式）F表示。F中的基本形式為：X1θY1：其中θ表示比較運算符:＞，≥，＜，≤，＝，＜＞。X1，Y1等是屬性名，常量，或列序號。關(guān)系R關(guān)于公式F的選擇操作用σF（R）表示，形式定義為：σF（R）＝{t|t∈R∧F（t）=true}σ為選擇運算符，σF（R）表示從R中挑選滿足公式F為真的元組所構(gòu)成的關(guān)系。例如，σ2＞ˊ3ˊ（R）表示從R中挑選第2個分量值大于3的元組所構(gòu)成的關(guān)系。書寫時，為了與屬性序號區(qū)別起見，常量用引號括起來，而屬性序號或?qū)傩悦灰靡柪ㄆ饋?。投影（Projection)這個操作是對一個關(guān)系進行垂直分割，消去某些列，并重新安排列的順序。設(shè)關(guān)系R是k元關(guān)系，R在其分量Ai1，…，Aim（m≤ki1，…，im，為1到k間的整數(shù)）上的投影用πi1,...,im（R）表示，它是一個m元元組集合，形式定義為：πi1，…，im（R）≡{t|t＝〈ti1，…，tim〉∧〈t1，…，tk〉∈R}例如，π3，1（R）表示關(guān)系R中取第1、3列，組成新的關(guān)系，新關(guān)系中第1列為R的第3列，新關(guān)系的第2列為R的第1列。如果R的每列標上屬性名，那么操作符π的下標處也可以用屬性名表示。例如，關(guān)系R（A，B，C），那么πC，A（R）與π3，1（R）是等價的。

連接有兩種：θ連接和F連接（這里θ是算術(shù)比較符，F(xiàn)是公式）。①θ連接R?S≡{t︱t=<tr，ts>∧tr∈R∧ts∈S∧}表達式表示元組tr的第i個分量、元組ts的第j個分量滿足θ操作。②F連接

F連接是從關(guān)系R和S的笛卡兒積中選取屬性間滿足某一公式F的元組,這里F是形為F1∧F2∧…∧Fn的公式，每個FP是形iθj的式子，而i和j分別為關(guān)系R和S的第i、第j個分量的序號。連接（join）運算iθj例θ連接和F連接的例子.說明:1.也可以寫成?！驭?＜4（R×S)2.。連接運算舉例

兩個關(guān)系R和S的自然連接操作具體計算過程如下：①計算R×S；②設(shè)R和S的公共屬性是A1,…,AK，挑選R×S中滿足R.A1=S.A1，…，R.AK=S.AK的那些元組；③去掉S.A1，…，S.AK這些列。定義：中i1,…,im為R和S的全部屬性，但公共屬性只出現(xiàn)一次?！宰匀贿B接（naturaljoin）ABCa1a1a2a2b1b2b3b456812BEb1b2b3b3b5371022AR.BCS.BEa1a1a1a1a2b1b1b2b2b355668b2b3b2b3b371071010AR.BCS.BEa1a1a2a2b1b2b3b35688b1b2b3b337102ABCEa1a1a2a2b1b2b3b3568837102關(guān)系R關(guān)系S一般連接RSC<ER.C<S.B等值連接RS自然連接RS連接運算舉例兩個關(guān)系R和S在做自然連接時，選擇兩個關(guān)系在公共屬性上值相等的元組構(gòu)成新的關(guān)系。此時，關(guān)系R中某些元組有可能在S中不存在公共屬性上值相等的元組，從而造成R中這些元組在操作時被舍棄了，同樣，S中某些元組也可能被舍棄。如果把舍棄的元組也保存在結(jié)果關(guān)系中，而在其他屬性上填空值（Null），那么這種連接就叫做外連接(Outerjoin)。如果只把左邊關(guān)系R中要舍棄的元組保留就叫做左外連接（Leftouterjoin或Leftjoin），如果只把右邊關(guān)系S中要舍棄的元組保留就叫做右外連接（Rightouterjoin或Rightjoin）。專門的關(guān)系運算ABCEa1a1a2a2a2NULLb1b2b3b3b4b5568812NULL37102NULL2ABCEa1a1a2a2a2b1b2b3b3b456881237102NULLABCEa1a1a2a2NULLb1b2b3b3b55688NULL371022ABCa1a1a2a2b1b2b3b456812BEb1b2b3b3b5371022關(guān)系R關(guān)系S外連接左外連接右外連接外連接的例子除法（division）設(shè)關(guān)系R和S的元數(shù)分別為r和s（設(shè)r>s>0），那么R÷S是一個（r-s）元的元組的集合。（R÷S）是滿足下列條件的最大關(guān)系：其中每個元組t與S中每個元組u組成的新元組<t，u>必在關(guān)系R中。R÷S≡π1,2,…,r-s（R）-π1,2,…,r-s((π1,2,…,r-s(R)×S)-R)除法舉例關(guān)系代數(shù)運算的應用實例(1)

在關(guān)系代數(shù)運算中，把由五個基本操作經(jīng)過有限次復合的式子稱為關(guān)系代數(shù)表達式。這種表達式的運算結(jié)果仍是一個關(guān)系。例2.7設(shè)教學數(shù)據(jù)庫中有三個關(guān)系：學生關(guān)系S(S#,SNAME,AGE,SEX)

選課關(guān)系SC(S#,C#,GRADE)

課程關(guān)系C(C#,CNAME,TEACHER)

用關(guān)系代數(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=4∧2=‘C2’∧5=‘C4’(SC×SC))(6)檢索不學C2課的學生姓名與年齡。

πSNAME,AGE

(

S)-πSNAME,AGE

(σC#=‘C2’(S

?

SC))

(7)

檢索學習全部課程的學生姓名。①學生選課情況可用操作πS#,C#(SC);

②全部課程可用操作πC#(C)表示;③學了全部課程的學生學號可用除法操作表示,操作結(jié)果是學號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)

關(guān)系代數(shù)運算的應用實例(2)關(guān)系代數(shù)運算的應用實例(3)一般地有下列規(guī)律：(1)對于只涉及到選擇、投影、連接的查詢可用下列表達式表示：

π(σ(R×S)) 或者π(σ(RS))(2)對于否定的操作，一般要用差操作表示，例如“檢索不學C2課的學生姓名”。用下列表達式表示：

πSNAME(S)-πSNAME(σCNO='C2'(SSC))但不能用下式表示： πSNAME(σCNO≠'C2'(SSC))⑶對于檢索具有“全部”特征的操作，一般要用除法操作表示，例如“檢索學習全部課程的學生學號”。用下列表達式表示：要用πSNO,CNO(SC)÷πCNO(C)表示，而不能寫成

πSNO(SC÷πCNO(C))形式。這是因為一個學生學的課程的成績可能是不一樣的。3.5查詢優(yōu)化主要內(nèi)容查詢優(yōu)化的一般策略代數(shù)表達式的等價變換規(guī)則優(yōu)化算法例設(shè)關(guān)系R和S都是二元關(guān)系，屬性名分別為A，B和C，D。設(shè)有一個查詢可用關(guān)系代數(shù)表達式表示：

E1=πA（σB=C∧D=‘99’（R×S）））也可以把選擇條件D=‘99’移到笛卡兒積中的關(guān)系S前面：

E2=πA（σB=C（R×σD=‘99’（S）））還可以把選擇條件B＝C與笛卡兒積結(jié)合成等值連接形式：

E3=πA（RσD='99'（S））這三個關(guān)系代數(shù)表達式是等價的，但執(zhí)行的效率大不一樣。顯然，求El，E2，E3的大部分時間是花在連接操作上的。查詢優(yōu)化例子

可以分析出，在時空性能上，E3最優(yōu)，其次是E2，最后是E1。此例還可以看出，如何安排選擇、投影和連接的順序是個很重要的問題。查詢優(yōu)化的一般策略(1)在關(guān)系代數(shù)表達式中需要指出若干關(guān)系的操作步驟。那么，系統(tǒng)應該以什么樣的操作順序，才能做到既省時間，又省空間，而且效率也比較高呢？這個問題稱為查詢優(yōu)化問題。查詢優(yōu)化是實現(xiàn)關(guān)系系統(tǒng)的關(guān)鍵技術(shù),它大大減輕了用戶選擇存取路徑的負擔,用戶使用關(guān)系系統(tǒng)時,只要提出“做什么”,不必指出“怎么做”。在關(guān)系代數(shù)運算中，笛卡兒積和連接運算是最費時間的。查詢優(yōu)化的一般策略(2)查詢優(yōu)化采用的一般策略是：⑴盡可能早地執(zhí)行選擇運算。在查詢中這種變換最為重要，因為它可以以元組為單位減小中間結(jié)果，從而使執(zhí)行時間成數(shù)量級地減少。⑵把先做笛卡兒積，后做選擇結(jié)合起來。使之成為一個連接運算。連接運算（特別是等值連接）要比笛卡兒積運算效率高得很多。當對笛卡兒積R×S的結(jié)果再做選擇時，并且這個選擇是對R和S的屬性進行比較，在這樣的條件下，這個笛卡兒積和選擇運算等價于一個連接。一般對不含R的屬性或不含S的屬性的比較，可以移到笛卡兒積運算前去做，這樣做比轉(zhuǎn)換到連接更好。⑶同時計算一串選擇和一串投影運算，以免分開運算造成多次掃描文件，從而節(jié)省了操作時間。⑷找出表達式里的公共子表達式。如果公共子表達式的結(jié)果不是很大，并且從外存讀入比起計算它要節(jié)省許多時間，那么，預先計算一下這個公共子表達式是有好處的。子表達式內(nèi)涉及到連接，但又不能把限定條件向內(nèi)移入的那類表達式，一般屬于這一類。連接和笛卡兒積的交換律

E1E2≡E2E1E1E2≡E2E1E1×E2≡E1×E2連接和笛卡兒積的結(jié)合律

(E1E2）E3≡E1