關(guān)系數(shù)據(jù)庫(kù)的基本理論.pptVIP

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