第9章關(guān)系數(shù)據(jù)庫(kù)理論9.1關(guān)系模式的規(guī)范化理論概述關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì)的核心是關(guān)系模式的設(shè)計(jì)。在設(shè)計(jì)關(guān)系模式時(shí)，必須考慮以下幾個(gè)問(wèn)題：應(yīng)該構(gòu)造幾個(gè)關(guān)系？每個(gè)關(guān)系由哪些屬性組成？關(guān)系模式中的所有關(guān)系應(yīng)該滿足哪些約束條件？如何體現(xiàn)這些約束條件？評(píng)價(jià)關(guān)系模型好壞的依據(jù)是什么？如何將不好的關(guān)系模型改進(jìn)為好的關(guān)系模型？上述這些問(wèn)題都可以從關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì)理論中找到答案。9.1.1關(guān)系模式規(guī)范化的必要性例9-1學(xué)生-課程-教師關(guān)系如表9-1所示，其中包含學(xué)生、課程和教師實(shí)體的屬性有：學(xué)號(hào)、課程號(hào)、成績(jī)、教師姓名、職稱等。9.1.1關(guān)系模式規(guī)范化的必要性分析表9-1,可以發(fā)現(xiàn)上述關(guān)系中存在許多問(wèn)題。數(shù)據(jù)冗余同一信息重復(fù)出現(xiàn)。例如，教師的姓名、職稱和所在系等信息重復(fù)出現(xiàn)，如果有100個(gè)學(xué)生選修張三豐老師的課，那么張三豐老師的相關(guān)信息要出現(xiàn)100次。更新異常對(duì)學(xué)生-課程-教師關(guān)系中的記錄進(jìn)行修改可能出現(xiàn)數(shù)據(jù)不一致的情況。例如，把第二個(gè)記錄中屬性職稱的值改為教授，就會(huì)出現(xiàn)李麗萍老師的職稱不一致的問(wèn)題，除非把李麗萍老師的所有職稱都改為同一值。插入異常某些信息無(wú)法正常插入。例如，課程C5由王路耀老師擔(dān)任，但在還不知道哪些學(xué)生選修前，無(wú)法將王路耀老師的記錄插入關(guān)系中。因?yàn)?，在學(xué)生-課程-教師關(guān)系中（學(xué)號(hào),課程號(hào)）是主碼，當(dāng)學(xué)號(hào)不確定時(shí)，根據(jù)關(guān)系模型的實(shí)體完整性規(guī)則，不允許主碼為空值，因此不能插入該記錄。刪除異常某些信息被意外刪除。例如，如果要?jiǎng)h除某門課程的所有成績(jī)，則會(huì)將教這門課的教師信息也刪掉。例如，若要?jiǎng)h除C4的記錄，結(jié)果會(huì)丟失趙新朋老師的有關(guān)信息。顯然，這是不希望發(fā)生的事情。9.1.1關(guān)系模式規(guī)范化的必要性如果將學(xué)生-課程-教師關(guān)系分解為表9-2a所示的學(xué)生-課程、表9-2b所示的課程-教師和表9-2c所示的教師三個(gè)關(guān)系，則上述的4個(gè)異常問(wèn)題就基本解決了。9.1.2關(guān)系模式規(guī)范化的概念例9-1將學(xué)生-課程-教師關(guān)系分解為學(xué)生-課程、課程-教師和教師3個(gè)關(guān)系的過(guò)程就是關(guān)系模式規(guī)范化的過(guò)程。9.2函數(shù)依賴及范式9.2.1屬性間的聯(lián)系1.一對(duì)一聯(lián)系設(shè)X、Y是關(guān)系R的兩個(gè)屬性（集）。如果對(duì)于X中的任一具體值，Y中至多有一個(gè)值與之對(duì)應(yīng)，且反之亦然，則稱X、Y兩屬性間是一對(duì)一聯(lián)系，記為1:1。在表9-1所示的學(xué)生-課程-教師關(guān)系中，課程號(hào)和課程名稱之間就是一對(duì)一的聯(lián)系，一個(gè)課程號(hào)唯一地決定一門課程名稱，而一門課程名稱只有唯一的一個(gè)課程號(hào)與之對(duì)應(yīng)。9.2.1屬性間的聯(lián)系2.一對(duì)多聯(lián)系如果對(duì)于X中的任一具體值，Y中至多有一個(gè)值與之對(duì)應(yīng)，而Y中的一個(gè)值卻可以和X中的n個(gè)值（n≥0）相對(duì)應(yīng)，則稱Y對(duì)X是一對(duì)多聯(lián)系，記為1:n。在表9-1所示的學(xué)生-課程-教師關(guān)系中，教師和職稱之間就是一對(duì)多的聯(lián)系，一個(gè)教師只能有一個(gè)職稱，而同一個(gè)職稱可能對(duì)應(yīng)多個(gè)教師。同理，(學(xué)號(hào),課程號(hào))與成績(jī)之間，教師與所在系之間，都是一對(duì)多的聯(lián)系。3.多對(duì)多聯(lián)系如果對(duì)于X中的任一具體值，Y中有m（m≥0）個(gè)值與之對(duì)應(yīng)，而Y中的一個(gè)值也可以和X中的n個(gè)值（n≥0）相對(duì)應(yīng)，則稱Y對(duì)X是多對(duì)多關(guān)系，記為m:n。在表9-1所示的學(xué)生-課程-教師關(guān)系中，學(xué)號(hào)和課程號(hào)之間就是多對(duì)多聯(lián)系，一個(gè)學(xué)生可以選修多門課程，而一個(gè)課程也可以同時(shí)被多個(gè)學(xué)生選修。9.2.1屬性間的聯(lián)系9.2.2函數(shù)依賴1.函數(shù)依賴

用U表示屬性集的全集{A1，A2，...，An}，設(shè)R(U)是屬性集U上的關(guān)系模式。X,Y是U的子集。若對(duì)于R(U)的所有具體關(guān)系r都滿足如下約束：對(duì)于X的每一個(gè)具體值，Y有唯一的具體值與之對(duì)應(yīng)，則稱Y函數(shù)依賴于X，或X函數(shù)決定Y，記作X

Y，X稱作決定因素。例9-2

設(shè)有讀者-圖書-借書關(guān)系如表9-3所示，其中（讀者號(hào),書號(hào)）是候選碼。9.2.2函數(shù)依賴表9-3中各屬性之間的聯(lián)系如下：2.平凡函數(shù)依賴與非平凡函數(shù)依賴

如果X

Y，并且Y不是X的子集，則稱X

Y是非平凡函數(shù)依賴。如果X

Y，且Y是X的子集，則稱X

Y是平凡函數(shù)依賴。例9-2中的所有函數(shù)依賴都是非平凡函數(shù)依賴。3.完全函數(shù)依賴與部分函數(shù)依賴

設(shè)X

Y是關(guān)系模式R(U)的一個(gè)函數(shù)依賴，如果存在X的真子集X’，使得X’

Y成立，則稱Y部分依賴于X，記作XY。否則，稱Y完全依賴于X，記作XY。在例9-2中，只有非主屬性“借出日期”完全函數(shù)依賴于候選碼（讀者號(hào)，書號(hào)），即（讀者號(hào)，書號(hào)）借出日期，而其他非主屬性都是部分函數(shù)依賴于主碼。4.傳遞函數(shù)依賴

在同一關(guān)系模式R(U)中，如果存在非平凡函數(shù)依賴X

Y，Y

Z而YX，則稱Z傳遞依賴于X。在例9-2中，存在函數(shù)依賴：讀者號(hào)

單位，單位

地址。根據(jù)傳遞函數(shù)依賴的定義，可知讀者號(hào)

地址是傳遞函數(shù)依賴。9.2.3第一范式（1NF）定義9-1

在關(guān)系模式R(U)中的每一個(gè)具體關(guān)系r中，如果每個(gè)屬性值都是不可再分的最小數(shù)據(jù)單位，則稱R(U)是第一范式的關(guān)系，記為R(U)

lNF。例9-2中的讀者-圖書-借書關(guān)系是滿足1NF的.9.2.4第二范式（2NF）定義9-2

如果關(guān)系模式R(U)中的所有非主屬性都完全函數(shù)依賴于主碼，則稱R(U)是第二范式的關(guān)系，記為R(U)

2NF。

從圖9-1可以發(fā)現(xiàn)，例9-2中的讀者-圖書-借書關(guān)系不滿足2NF，因?yàn)槠浞侵鲗傩浴靶彰薄ⅰ皢挝弧?、“地址”、“書名”都沒(méi)有完全函數(shù)依賴于候選碼（讀者號(hào),書號(hào)）。作如圖9-2所示的投影運(yùn)算，就可將其分解為2NF的關(guān)系。9.2.5第三范式（3NF）定義9-3

如果關(guān)系模式R(U)中的所有非主屬性對(duì)主碼不存在傳遞函數(shù)依賴，則稱R(U)是第三范式的關(guān)系，記為R(U)

3NF。3NF是一個(gè)可用的關(guān)系模式應(yīng)該滿足的最低范式。3NF是一個(gè)可用的關(guān)系模式應(yīng)該滿足的最低范式。例9-2中的讀者-圖書-借書關(guān)系經(jīng)過(guò)1NF，2NF和3NF的規(guī)范化后，就得到一個(gè)可用的關(guān)系模式，并包含4個(gè)關(guān)系：讀者（讀者號(hào)，姓名，單位名稱），單位（單位名稱，地址），圖書（書號(hào)，書名），借書（讀者號(hào)，書號(hào)，借出日期）。滿足3NF的關(guān)系就是一個(gè)可用的關(guān)系。但是，滿足3NF的關(guān)系仍有可能存在缺陷，因?yàn)?NF只限制了非主屬性對(duì)碼的依賴關(guān)系，而沒(méi)有限制碼屬性對(duì)碼的依賴關(guān)系。9.2.6BoyceCodd范式

例9-3有教務(wù)關(guān)系(學(xué)號(hào)，教工號(hào)，課程號(hào))，其中（學(xué)號(hào)，教工號(hào)）和（學(xué)號(hào)，課程號(hào)）為候選碼，且具有下列的函數(shù)依賴關(guān)系：每位老師只教授一門課，即教工號(hào)

課程號(hào)。某學(xué)生選定一位老師，就對(duì)應(yīng)一門課，即（學(xué)號(hào)，教工號(hào)）

課程號(hào)。某學(xué)生選定一門課，就對(duì)應(yīng)一位老師，即（學(xué)號(hào)，課程號(hào)）

教工號(hào)。(學(xué)號(hào)，教工號(hào))和(學(xué)號(hào)，課程號(hào))兩個(gè)候選碼相交，有公共的屬性學(xué)號(hào)。教務(wù)關(guān)系中不存在非主屬性，也就不可能存在非主屬性對(duì)碼的部分依賴或傳遞依賴，所以教務(wù)關(guān)系

3NF。但是，這個(gè)教務(wù)關(guān)系仍然存在許多問(wèn)題：插入異常：如果沒(méi)有學(xué)生選修某位教師的任課，則該教師擔(dān)任課程的信息就無(wú)法插入；刪除異常：刪除學(xué)生選課信息，會(huì)刪除相關(guān)教師的任課信息；修改復(fù)雜：如果教師所教授的課程有所改動(dòng)，則所有選修該教師課程的學(xué)生信息都要做改動(dòng)；數(shù)據(jù)冗余：每位學(xué)生都存儲(chǔ)了有關(guān)教師所教授的課程的信息。所以，仍需要進(jìn)一步做規(guī)范化處理。這就需要用到BCNF范式。定義9-4

如果關(guān)系模式R(U)中的所有屬性都不傳遞函數(shù)依賴于R(U)的任何主碼，則稱R(U)是BCNF的關(guān)系。記為R(U)

BCNF。BCNF是BoyceCodd范式的縮寫。與其等價(jià)的定義是，關(guān)系模式R(U)中，如果每個(gè)決定因素都包含主碼(而不是被主碼所包含)，則R(U)

BCNF。BCNF是對(duì)3NF的修正。在函數(shù)依賴的范疇內(nèi)，BCNF能夠完全消除一個(gè)關(guān)系模式中的數(shù)據(jù)插入和刪除異常。

在例9-3中，教務(wù)關(guān)系之所以出現(xiàn)問(wèn)題就是因?yàn)闆Q定因素被主碼包含：教工號(hào)

課程號(hào)中教工號(hào)是決定因素，但又被包含在候選主碼（學(xué)號(hào)，教工號(hào)）中。所以不滿足BCNF。如果將教務(wù)關(guān)系分解為教學(xué)（學(xué)號(hào)，教工號(hào)）和教課（教工號(hào)，課程號(hào)）兩個(gè)關(guān)系，那么這兩個(gè)新關(guān)系就都滿足BCNF。9.3多值依賴及范式9.3.1多值依賴的定義和性質(zhì)1.多值依賴的定義

在關(guān)系模式R(U)中，X,Y,Z

U且X+Y+Z=U。如果對(duì)R(U)中的任一關(guān)系r，給定一對(duì)(x,z)值，有一組Y的值，并且這組值僅由x值決定而與z值無(wú)關(guān)，那么關(guān)系模式R(U)中存在多值依賴X

Y。如果此時(shí)Z為空集（即），則X

Y被稱為平凡多值依賴。例9-4設(shè)有滿足BCNF的關(guān)系模式超市-助理-電話(超市名稱，助理姓名，超市電話)，其中一家超市可能有多個(gè)助理，并且有多個(gè)電話號(hào)碼，此時(shí)，就有如表9-4所示的關(guān)系。在表9-4中，U={超市名稱，助理姓名，超市電話}，X={超市名稱}，Y={助理姓名}，Z={超市電話}，且X+Y+Z=U，存在多值依賴：超市名稱

助理姓名和超市名稱

超市電話。根據(jù)平凡多值依賴的定義，本例中的兩個(gè)多值依賴都是非平凡多值依賴。2.多值依賴的性質(zhì)1）多值依賴具有對(duì)稱性：若X

Y，則X

Z，其中Z＝U－X－Y。多值依賴的對(duì)稱性可以從例9-4中的兩個(gè)多值依賴反映出來(lái)。2）多值依賴具有傳遞性：若X

Y，Y

Z，則X

Z－Y。3）函數(shù)依賴可以看作是多值依賴的特殊情況：若X

Y，則X

Y。這是因?yàn)楫?dāng)X

Y時(shí)，對(duì)X的每一個(gè)值x，Y有一個(gè)確定的值y與之對(duì)應(yīng)，所以X

Y。4）若X

Y，X

Z，則X

Y

Z

5）若X

Y，X

Z，則X

Y

Z

6）若X

Y，X

Z，則X

Y－Z，X

Z－Y

9.3.2第四范式（4NF）定義9-5關(guān)系模式R(U)

lNF,如果對(duì)于R的每個(gè)非平凡多值依賴X

Y(Y

X)，X都含有碼,則稱R(U)

4NF。4NF限制關(guān)系模式的屬性之間不允許有非平凡且非函數(shù)依賴的多值依賴。因?yàn)楦鶕?jù)定義，對(duì)于每一個(gè)非平凡的多值依賴X

Y，X都含有候選碼，于是就有X

Y，所以4NF所允許的非平凡的多值依賴實(shí)際上是函數(shù)依賴。

在例9-4中，關(guān)系模式超市-助理-電話的候選碼為（超市名稱，助理姓名，超市電話），而X={超市名稱}，即X不包含碼，所以不滿足4NF。將超市-助理-電話解為超市-助理(超市名稱，助理姓名)和超市-電話(超市名稱，超市電話)兩個(gè)關(guān)系。在超市-助理關(guān)系中，超市名稱

助理姓名，{助理姓名}不是{超市名稱}的子集，而且超市名稱是超市-助理關(guān)系的候選碼，所以超市-助理關(guān)系滿足4NF。同理，超市-電話關(guān)系也滿足4NF。9.4連接依賴及范式設(shè)R、R1、

、Rn是關(guān)系模式，U、U1、…、Un分別是R、R1、

、Rn的屬性集合，而且U=U1

Un。如果R的任意關(guān)系實(shí)例r滿足：

則稱R滿足連接依賴，記作:

其中

是自然連接符號(hào)。此時(shí)，如果某個(gè)Ui=U，則稱該連接依賴是平凡連接依賴。9.4.1連接依賴的定義

例9-5

設(shè)有滿足4NF的銷售關(guān)系如表9-5所示，其中銷售員代表汽車生產(chǎn)商（即單位），負(fù)責(zé)銷售該生產(chǎn)商生產(chǎn)的汽車產(chǎn)品。

表9-5可以由表9-6所示的三個(gè)關(guān)系完全重建，即因此銷售關(guān)系中存在連接依賴。9.4.2第五范式（5NF）定義9-6

如果關(guān)系模式R(U)中的每一個(gè)連接依賴都是由R的候選碼所蘊(yùn)含,則稱R(U)

5NF。

在例9-5中，銷售關(guān)系的候選碼是（銷售員，單位，產(chǎn)品名稱），銷售關(guān)系的連接依賴:

都不由銷售的候選碼所蘊(yùn)含，所以銷售關(guān)系不滿足5NF。但是，銷售關(guān)系分解后的R1，R2和R3這三個(gè)關(guān)系都滿足5NF。9.4.3小結(jié)關(guān)系模式規(guī)范化的基本思想如圖9-3所示關(guān)系模式的規(guī)范化會(huì)帶來(lái)以下好處：由于關(guān)系中的各個(gè)數(shù)據(jù)項(xiàng)都是一個(gè)簡(jiǎn)單的數(shù)或符號(hào)串，故可以方便地進(jìn)行存取。由于模式的分解，可以簡(jiǎn)化檢索操作，故加快了檢索速率?？上龑?duì)數(shù)據(jù)進(jìn)行插入、修改和刪除時(shí)的相互牽扯，便于保持?jǐn)?shù)據(jù)的一致性?？赏ㄟ^(guò)對(duì)于分解模式的連接來(lái)產(chǎn)生出新的模式，便于引入新型數(shù)據(jù)。避免重復(fù)存儲(chǔ)，減少數(shù)據(jù)的冗余度，存儲(chǔ)空間的利用率。9.4.3小結(jié)9.5模式分解9.5.1模式分解的概念1.模式分解的定義所謂模式分解是指根據(jù)規(guī)范化理論將一個(gè)結(jié)構(gòu)復(fù)雜的關(guān)系分解為幾個(gè)結(jié)構(gòu)簡(jiǎn)單的關(guān)系的過(guò)程。模式分解的目的是消除關(guān)系模式中存在的存入、刪除、修改異常和數(shù)據(jù)冗余等弊病。模式分解的準(zhǔn)則是既要保持函數(shù)依賴（即不破壞屬性間存在的依賴關(guān)系），又要具有無(wú)損連接性（即不增減信息）2.模式分解的理論基礎(chǔ)模式分解的理論涉及到邏輯蘊(yùn)含、Armstrong公理體系、閉包的計(jì)算、函數(shù)依賴的等價(jià)和覆蓋、函數(shù)依賴集的最小化等，下面分別加以說(shuō)明。（1）函數(shù)依賴的邏輯蘊(yùn)含關(guān)系模式R(U)，F(xiàn)是其函數(shù)依賴，X,Y是其屬性U的子集，如果從F的函數(shù)依賴能夠推出X

Y，則稱F邏輯蘊(yùn)涵X

Y。（2）Armstrong公理體系A(chǔ)rmstrong公理體系是用來(lái)推導(dǎo)函數(shù)依賴F是否蘊(yùn)含X

Y。它包括:Armstrong公理系統(tǒng)基于Amstrong公理的推理規(guī)則Armstrong公理系統(tǒng)的有效性和完備性1）Armstrong公理系統(tǒng)關(guān)系模式R(U)，F(xiàn)為R的一組函數(shù)依賴，X，Y，Z是屬性集U的子集，則有下列公式成立：①自反律（Reflexivity）：若Y

X

U，則X

Y為F所蘊(yùn)含。②增廣律：若X

Y為F所蘊(yùn)含，且Z

Y，則X

Z

Y

Z為F所蘊(yùn)含。③傳遞性：若X

Y和Y

Z為F所蘊(yùn)含，則X

Z為F所蘊(yùn)含。2）基于Amstrong公理的推理規(guī)則根據(jù)Armstrong公理系統(tǒng)的自反律、增廣律和傳遞性規(guī)則，可以得到下面三條推理規(guī)則：①合并規(guī)則：若X

Y，X

Z，則X

Y

Z②偽傳遞規(guī)則：若X

Y，W

Y

Z，則X

W

Z③分解規(guī)則：若X

Y，Z

Y，則X→Z根據(jù)合并規(guī)則和分解規(guī)則，可以得到引理1：引理1：X

A1A2…Ak成立的充分必要條件是:

X

Ai（i=1,2,…,k）成立。3）Armstrong公理系統(tǒng)的有效性和完備性自反律、傳遞律和增廣律統(tǒng)稱為Armstrong公理系統(tǒng)。Armstrong公理系統(tǒng)是有效的和完備的。Armstrong公理系統(tǒng)的有效性是指由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出的每一個(gè)函數(shù)依賴必在F+中（F+是F所邏輯蘊(yùn)含的函數(shù)依賴的全體,即F的閉包）。完備性是指F+中每一個(gè)函數(shù)依賴必定可以由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來(lái)。（3）屬性集的閉包1）閉包的定義設(shè)F為屬性集U上的一組函數(shù)依賴，X?U，XF+

={A|X

A能由F根據(jù)Armstrong公理導(dǎo)出}，XF+稱為屬性集X關(guān)于函數(shù)依賴集F的閉包。2）閉包的計(jì)算計(jì)算屬性集閉包的算法如圖9-4所示

例9-6

有關(guān)系模式R(U)，其中屬性集U=(A,B,C,G,H,I),

屬性集U上的函數(shù)依賴F={A

B,A

CCG

H,CG

I,B

H}，計(jì)算(AG)F+

。解：根據(jù)圖9-4所示的算法，具體計(jì)算步驟如下：令X(0)

=AGX(1)

=X(0)

)

B=AGB，用依賴A

BX(2))=X(1)

)

C=AGBC，用依賴A

CX(3)

=X(2)

)

H=AGBCH，用依賴B

HX(4)

=X(3)

)

I=AGBCHI，用依賴CG

I輸出(AG)F+

=AGBCHI

有關(guān)系模式R(U)，其中屬性集U=(A,B,C,D,E,G),

屬性集U上的函數(shù)依賴F={A

E,BE

AG,CE

A,G

D},計(jì)算(AB)F+

。解：根據(jù)圖9-4所示的算法，具體計(jì)算步驟如下：令X(0)

=ABX(1)

=X(0)

)

E=ABE，用依賴A

EX(2)

=X(1)

)

G=ABEG，用依賴BE

AGX(3)

=X(2)

)

D=ABEGD，用依賴G

D輸出(AB)F+

=ABEGD

引理2：關(guān)系模式R(U)，X和Y是U的子集，F(xiàn)為屬性U上的一組函數(shù)依賴，則X

Y能由Armstrong公理導(dǎo)出的充分必要條件是Y?XF+

。

這樣，判定X

Y能否由Armstrong公理導(dǎo)出的問(wèn)題，就轉(zhuǎn)化為求XF+

，判定Y是否為XF+的子集的問(wèn)題。而XF+

+可以由圖9-4所示的算法求得。

例9-8

有關(guān)系模式R(U)，其中屬性集U=(A,B,C,D,E),

屬性集U上的函數(shù)依賴F={AB

C,B

D,C

E,EC

B,AC

B},判定AB

DE能否由Armstrong公理導(dǎo)出。解：判定AB

DE能否由Armstrong公理導(dǎo)出，可以轉(zhuǎn)化為先求出(AB)F+

，然后判定DE是否為

(AB)F+的子集。令X(0)

=ABX(1)

=X(0)

CD=ABCD，用依賴AB

C，B

DX(2)

=X(1)

E=ABCDE，用依賴C

E輸出(AB)F+

=ABCDEDE?(AB)F+

，所以AB→DE能由Armstrong公理導(dǎo)出（4）函數(shù)依賴的等價(jià)和覆蓋若G+=F+

，則稱函數(shù)依賴集F覆蓋G，或者G覆蓋F，即F和G等價(jià)。

引理3：G+=F+的充分必要條件是：

G+?F+

和F+?G+

這條引理給出了判斷兩個(gè)函數(shù)依賴等價(jià)的可行算法：先判斷F+?G+

，具體步驟是逐一對(duì)F中的函數(shù)依賴X

Y，考察Y是否屬于XG+

。再判斷G+?F+

，具體步驟是逐一對(duì)G中的函數(shù)依賴X

Y，考察Y是否屬于XF+

。（5）最小函數(shù)依賴集（最小覆蓋）滿足下列條件的函數(shù)依賴集F稱為最小覆蓋，記作Fmin：?jiǎn)螌傩曰篎中任一函數(shù)依賴X

A，A必是單屬性。無(wú)冗余化：F中不存在這樣的函數(shù)依賴X

A，使得F與F?{X

A}等價(jià)。既約化：F中不存在這樣的函數(shù)依賴X

A，在X中有真子集Z，使得F與F?{X

A}

{Z

A}等價(jià)。

求函數(shù)依賴集F的最小覆蓋Fmin的算法如圖9-5所示

例9-9

設(shè)有函數(shù)依賴集F={A

B,B

A,A

C,B

C}，求Fmin。解：根據(jù)圖9-5所示的算法，具體求解步驟如下：?jiǎn)螌傩曰?所有函數(shù)依賴中的Y已經(jīng)是單屬性的。無(wú)冗余化:檢查A

B,G=F?{A

B}={B

A,A

C,B

C},AG+={A,C},B

{A,C}

檢查A

C,G=F?{A

C}={A

B,B

A,B

C},AG+={A,B,C},C

{A,B,C}

從F中刪除A

C

既約化所有函數(shù)依賴中的X是單屬性的，該步驟可略

Fmin

={A

B，B

A，B

C}或者

Fmin={A

B，B

A，A

C}9.5.2模式分解的算法模式分解的基本要求是分解前后的關(guān)系模式必須等價(jià)，即分解必須具有無(wú)損連接和函數(shù)依賴保持特性。因此，必須注意以下幾個(gè)結(jié)論：（1）若要求分解具有無(wú)損連接性，那么分解一定可以達(dá)到BCNF。（2）若要求分解保持函數(shù)依賴，那么分解可以達(dá)到3NF，但不一定能達(dá)到BCNF。（3）若要求分解即保持函數(shù)依賴，又具有無(wú)損連接性，那么分解可以達(dá)到3NF，但不一定能達(dá)到BCNF。模式分解的算法主要有三種：將關(guān)系模式轉(zhuǎn)化為3NF的保持函數(shù)依賴的算法，將關(guān)系模式轉(zhuǎn)化為3NF且具有無(wú)損連接性又能保持函數(shù)依賴的算法，將關(guān)系模式轉(zhuǎn)化為BCNF的無(wú)損連接的算法。9.5.2模式分解的算法9.5.2模式分解的算法1.將關(guān)系模式轉(zhuǎn)化為3NF的保持函數(shù)依賴的算法

分解的函數(shù)依賴保持性設(shè)F是關(guān)系模式R(U)的函數(shù)依賴集，

={R1(U1),R2(U2),…,Rk(Uk)}為R(U)的一個(gè)分解，且F1,F2,…,Fk分別是R1(U1),R2(U2),…,Rk(Uk)的函數(shù)依賴集。如果Fi=∏Ri(F)(i=1,2,…,k)的并集(F1

F2

…

Fk)+

F+,則稱分解

具有函數(shù)依賴保持性。

3NF保持函數(shù)依賴分解算法如圖9-6所示

例9-10

將關(guān)系模式R(課程C,教師T,時(shí)間H,教室R，學(xué)生S，成績(jī)G)分解為一組保持函數(shù)依賴達(dá)到3NF的關(guān)系模式。函數(shù)依賴集F為：

C

T：每門課程僅有一位教師擔(dān)任

HT

R：在任一時(shí)間，一個(gè)教師只能在一個(gè)教室上課

HR

C：在任一時(shí)間，每個(gè)教師只能上一門課

HS

R：在任一時(shí)間，每個(gè)學(xué)生只能在一個(gè)教室聽課

CS

G：每個(gè)學(xué)生學(xué)習(xí)一門課程只有一個(gè)成績(jī)解：根據(jù)圖9-6所示的3NF保持函數(shù)依賴分解算法，輸入

R(U)

1NF，U=(C,T,H,R,S,G),

最小函數(shù)依賴集

F={C

T,CS

G,HR

C,HS

R,HT

R}。具體分解步驟如下：不存在不出現(xiàn)在任何一個(gè)函數(shù)依賴中的屬性。不存在F中有一個(gè)函數(shù)依賴X

A，且X

A=U。對(duì)F中的每一個(gè)函數(shù)依賴X

A，構(gòu)造一個(gè)關(guān)系模式R(X,A)，這樣F中共有5個(gè)函數(shù)依賴，所以該模式可以保持函數(shù)依賴地分解為如下一組3NF的關(guān)系模式：

={CT,CGS,CHR,HRS,HRT}。9.5.2模式分解的算法2.將關(guān)系模式轉(zhuǎn)化為3NF且具有無(wú)損連接性又能保持函數(shù)依賴的算法分解的無(wú)損連接性無(wú)損連接的定義設(shè)F是關(guān)系模式R(U)的函數(shù)依賴集，

={R1(U1),R2(U2),…,Rk(Uk)}為R(U)的一個(gè)分解，且F1,F2,…,Fk分別是R1(U1),R2(U2),…,Rk(Uk

)的函數(shù)依賴集。設(shè)r是R(U)的一個(gè)關(guān)系實(shí)例，且有如下定義：如果對(duì)R的滿足F的任一個(gè)關(guān)系r，均有r=

m

(r)

，則稱分解

具有無(wú)損連接。

判定無(wú)損連接的算法設(shè)

={R1(U1,F1),...,Rk(Uk,Fk)}是R(U,F)的一個(gè)分解,U={A1,A2,...,An},F={FD1,FD2,...,FDp}

，其中F為一最小依賴集，記FDi為Xi→Ali。判定無(wú)損連接的算法如下：①建立n列k行的一張表，每列對(duì)應(yīng)于一個(gè)屬性，每行對(duì)應(yīng)于分解中的一個(gè)關(guān)系模式，若Aj

Ui

，則在j列i行上填aj，否則填bij；②對(duì)每一個(gè)FDi做下列操作，找到Xi所對(duì)應(yīng)的列中具有相同符號(hào)的那些行進(jìn)行考查，考查這些行中l(wèi)j列的元素，若其中有ali,則全部改為ali，否則全部改為bm,li

，l是這些行中最小的行號(hào)值；③如果在某次更改后，有一行成為a1,a2,...an

，則算法終止，

具有無(wú)損連接，否則

不具有無(wú)損連接；對(duì)F中р個(gè)FD逐一進(jìn)行一次這樣的處理，稱為對(duì)F的一次掃描。④比較掃描前后，表有無(wú)變化，如有變化則轉(zhuǎn)②，否則算法終止。9.5.2模式分解的算法

定理9-1

為無(wú)損連接分解的充分必要條件是上述算法終止時(shí)，表中有一行為a1,a2,...an9.5.2模式分解的算法

具有無(wú)損連接性和保持函數(shù)依賴性的分解算法如圖9-7所示。9.5.2模式分解的算法

例9-11

將例9-10的關(guān)系模式R分解為一組3NF的關(guān)系模式，要求分解同時(shí)具有無(wú)損連接性和保持函數(shù)依賴性。解：根據(jù)圖9-7所示的算法，具體解題步驟如下：跟據(jù)圖9-6所示的3NF保持函數(shù)依賴分解算法，得到

={CT,CGS,CHR,HRS,HRT}；

HS是原模式的候選碼，所以

τ={CT,CGS,CHR,HRS,HRT,HS}；由于HS是模式HRS的一個(gè)子集，所以應(yīng)該消去HS，那么最后的分解{CT,CGS,CHR,HRS,HRT}

就是具有無(wú)損連接性和保持函數(shù)依賴性的分解，且其中所有模式都是3NF。9.5.2模式分解的算法3.將關(guān)系模式轉(zhuǎn)化為BCNF的無(wú)損連接的算法具有無(wú)損連接性的BCNF分解算法如圖9-8所示9.5.2模式分解的算法

例9-12

設(shè)關(guān)系模式R(ABCDE),R的函數(shù)依賴關(guān)系F={A

D,E

D,D

B,BC

D,DC

A}，請(qǐng)求出該關(guān)系的候選碼。解：判斷關(guān)系R中的屬性是否為候選碼的步驟如下：如果某個(gè)屬性不在被決定因子中，該屬性一定是侯選碼的一部分。如果某個(gè)屬性不在決定因子中，該屬性一定不是侯選碼的一部分。使用Armtrong公理去掉多余的函數(shù)依賴和左部多余的屬性。在本例中，尋找候選碼的具體步驟如下：因?yàn)镋

D

,

所以EC

DC

因?yàn)镈C

A,

所以EC

A

因?yàn)镈

B，所以DC→BC→B

，EC→B

所以得EC

ABD

所以：EC為候選碼，這里候選碼僅有一個(gè)

主屬性：EC,

非主屬性：A,B,D

例9-13

將例9-10的關(guān)系模式R分解為具有無(wú)損連接的BCNF。解：根據(jù)圖9-8所示的具有無(wú)損連接性的BCNF分解算法，具體解題步驟如下：關(guān)系模式R的最小函數(shù)依賴集

F={C

T,CS

G,HR

C,HS

R,HT

R}

關(guān)系模式R的候選碼為HS。由于CS不包含候選碼且CS

G，根據(jù)算法的第三步將R分解為R1(U1)和R2(U2)，其中U1={C,S,G},U2={C,T,H,R,S}，并求得R1(U1)和R2(U2)上的最小函數(shù)依賴集：

R1(CSG,{CS

G})(屬于BCNF)

R2(CTHRS,{HS

R,HT

R,C

T,HR

C})

ρ={R1,R2}

關(guān)系模式R2的候選碼為HS。

由于C不包含候選碼C

T，將R2分解為R3(U3)和R4(U4)，其中U3={C,T},U4={C,H,R,S}，并求得R3和R4上的最小函數(shù)依賴集：

R3(CT,{C

T})(屬于BCNF)，

R4(CHRS,{HS

R,HR

C}),

={R1,R3,R4}

關(guān)系模式R4的候選碼為HS。由于HR不包含候選碼且HR

C，將R4分解為R5(U5)和

R6(U6),其中U5={H,C,R},U6={H,R,S}，并求得R5和R6上的最小函數(shù)依賴集：

R5(HRC,{HR

C})(屬于BCNF)，

R6(HRS,{HS

R})(屬于BCNF)，

ρ={R1,R3,R5,R6}。由此可得，

={R1,R3,R5,R6}，即

={CSG,CT,HRC,HSR}，

中的所有關(guān)系模式都是BCNF。

9.6查詢優(yōu)化關(guān)系查詢優(yōu)化屬于關(guān)系數(shù)據(jù)庫(kù)的操作理論。關(guān)系查詢優(yōu)化是影響DBMS性能的關(guān)鍵因素。9.6.1查詢優(yōu)化的必要性例9-14

設(shè)有教學(xué)管理關(guān)系模式如下，求“李剛”選修的課程號(hào)和成績(jī)。學(xué)生（學(xué)號(hào)，姓名，性別，所在系，班號(hào)，出生日期）課程（課程號(hào)，課程名，學(xué)時(shí)，學(xué)分，先修課程號(hào)）選修（學(xué)號(hào)，課程號(hào)，成績(jī)）用SQL實(shí)現(xiàn)查詢，其語(yǔ)句為：

SELECT

課程號(hào)，成績(jī)

FROM

學(xué)生，選課

WHERE

學(xué)生.學(xué)號(hào)=選課.學(xué)號(hào)AND

姓名=

李剛

該查詢語(yǔ)句可以用多種等價(jià)的關(guān)系代數(shù)表達(dá)式來(lái)完成：

Q1=

課程號(hào),成績(jī)(

學(xué)生.學(xué)號(hào)=選課.學(xué)號(hào)

姓名=

李剛

(學(xué)生×選修))

Q2

=

課程號(hào),成績(jī)(

姓名=

李剛

(學(xué)生選修))

Q3

=

課程號(hào),成績(jī)((

姓名=

李剛

(學(xué)生))選修)

Q1、Q2和Q3操作的結(jié)果是一樣的。但分析這三種關(guān)系代數(shù)表達(dá)式可以發(fā)現(xiàn)，由于查詢執(zhí)行的策略不同,所需的查詢時(shí)間相差很大。

對(duì)于Q1而言，當(dāng)計(jì)算(學(xué)生×選修)時(shí)，需要把這兩個(gè)關(guān)系的全部元組連接起來(lái)。假設(shè)每個(gè)存儲(chǔ)塊能保存10個(gè)元組，學(xué)生關(guān)系的物理文件在存貯器中需B1個(gè)存貯存塊，選修關(guān)系的物理文件需B2塊。內(nèi)存中提供的運(yùn)算緩沖區(qū)最多能裝n塊，而B1,B2均大于n。計(jì)算廣義笛卡爾積的辦法是：將學(xué)生文件分成若干個(gè)n-1塊,首先將第一個(gè)n-l塊裝入內(nèi)存，并逐次裝入選修文件的一個(gè)塊，使之與學(xué)生文件已裝入的n-l塊進(jìn)行乘積運(yùn)算。當(dāng)選課文件的每塊都裝入一遍后，再往內(nèi)存裝入學(xué)生文件的下一個(gè)n-l塊，并同樣從第一塊開始逐次地裝入選修文件的每一塊，重復(fù)執(zhí)行上述連接運(yùn)算，這樣直到計(jì)算完乘積的全部元組為止，其讀塊數(shù)目為：B1+[B1/(n-1)]×B2。設(shè)B1=B2=1000，n=50，則所需讀塊的總數(shù)目為1000+[1000/49]×1000=21000。假設(shè)1s鐘能讀20塊時(shí)，大約需要18min時(shí)間。同樣假設(shè)每個(gè)存儲(chǔ)塊能保存連接后的10個(gè)元組和一秒鐘能寫入20塊，則連接后一共有1000×1000=2000000塊，將連接后的中間結(jié)果寫入存儲(chǔ)器需要1667min，然后再將中間結(jié)果讀出來(lái)進(jìn)行選擇和投影，也需1667min。與讀塊和寫塊相比，連接、選擇、投影等運(yùn)算時(shí)間均可忽略不計(jì)。完成Q1表達(dá)式的運(yùn)算時(shí)間大約需要3352min，即近56h。

對(duì)Q2而言，為了執(zhí)行自然連接，讀取學(xué)生文件和選修文件的策略不變,總的讀取塊數(shù)仍為21000塊，花費(fèi)1080s。但自然連接的結(jié)果比Q1的情況大大減少，為100000個(gè)元組,占10000塊，因此寫出這些元組時(shí)間均約為500s,將中間結(jié)果讀出來(lái)進(jìn)行選擇和投影也需500s。所以完成Q2表達(dá)式的運(yùn)算時(shí)間大約需要2080s，即35min，僅為Q1的百分之一。對(duì)Q3而言，先對(duì)學(xué)生文件做姓名=

李剛

的選擇操作，讀塊數(shù)目為B1。然后把結(jié)果與選課文件作連接、投影運(yùn)算，讀塊數(shù)目為B2，所以總的讀塊數(shù)目為B1+B2=2000。由于滿足條件的元組很少(大約50個(gè)元組)，不用保存中間結(jié)果文件，因而完成Q3表達(dá)式共需約1.7min(1s仍讀20塊)，僅等于Q1的二千分之一。9.6.2查詢優(yōu)化的一般準(zhǔn)則1.選擇運(yùn)算應(yīng)盡可能先做在優(yōu)化策略中這是最重要、最基本的一條。它常?？墒箞?zhí)行時(shí)間節(jié)約幾個(gè)數(shù)量級(jí)，因?yàn)檫x擇運(yùn)算一般使計(jì)算的中間結(jié)果減小很多。2.在執(zhí)行連接操作前對(duì)關(guān)系適當(dāng)?shù)仡A(yù)處理預(yù)處理方法一般有兩種：其一是連接屬性上建立索引，其二是對(duì)關(guān)系排序。前者稱為索引連接方法，后者稱為排序合并(SORT-MERGE)連接方法

9.6.2查詢優(yōu)化的一般準(zhǔn)則對(duì)于(學(xué)生選修)這樣的自然連接，用索引連接方法的步驟是：（1）在選修表上建立學(xué)號(hào)的索引。（2）對(duì)學(xué)生表中每一個(gè)元組,由學(xué)號(hào)通過(guò)選修表的索引查找相應(yīng)的選修表中的元組。（3）把這些選修表的元組和學(xué)生表的元組連接起來(lái)。這樣學(xué)生表和選修表均只要掃描一遍，處理時(shí)間只是兩個(gè)關(guān)系大小的線性函數(shù)。9.6.2查詢優(yōu)化的一般準(zhǔn)則

對(duì)于(學(xué)生選修)這樣的自然連接，用排序合并連接方法的步驟是：（1）首先對(duì)學(xué)生表和選修表按連接屬性學(xué)號(hào)排序。（2）取學(xué)生表中第一個(gè)學(xué)號(hào),依次掃描選修表中具有相同學(xué)號(hào)的元組，把它們連接起來(lái)。（3）當(dāng)掃描到學(xué)號(hào)不相同的第一個(gè)選修表中的元組時(shí)，返回學(xué)生表，并掃描它的下一個(gè)元組，再掃描選修表中具有相同學(xué)號(hào)的元組，把它們連接起來(lái)。重復(fù)上述步驟直到學(xué)生表掃描完.這樣學(xué)生表和選課表也只要掃描一遍。當(dāng)然，執(zhí)行時(shí)間要加上對(duì)兩個(gè)表的排序時(shí)間。即使這樣，使用預(yù)處理方法執(zhí)行連接的時(shí)間一般仍大大減少。9.6.2查詢優(yōu)化的一般準(zhǔn)則

3.投影運(yùn)算和選擇運(yùn)算同時(shí)做如有若干投影和選擇運(yùn)算，并且它們都對(duì)同一個(gè)關(guān)系操作，則可以在掃描此關(guān)系的同時(shí)完成所有的這些運(yùn)算以避免重復(fù)掃描關(guān)系。9.6.2查詢優(yōu)化的一般準(zhǔn)則4.投影同雙目運(yùn)算結(jié)合把投影同其前或其后的雙目運(yùn)算結(jié)合起來(lái)，以減少掃描關(guān)系的次數(shù)。9.6.2查詢優(yōu)化的一般準(zhǔn)則5.選擇操作同某些笛卡爾積結(jié)合起來(lái)構(gòu)成一個(gè)連接運(yùn)算把某個(gè)選擇操作同在它前面要執(zhí)行的笛卡爾積結(jié)合起來(lái)成為一個(gè)連接運(yùn)算，連接特別是等值連接運(yùn)算要比同樣關(guān)系上的笛卡爾積省很多時(shí)間。9.6.2查詢優(yōu)化的一般準(zhǔn)則6.找出公共子表達(dá)式如果重復(fù)出現(xiàn)的子表達(dá)式的查詢結(jié)果不是很大的關(guān)系，并且從外存中讀入這個(gè)關(guān)系比計(jì)算該子表達(dá)式的時(shí)間少得多，則先計(jì)算一次公共子表達(dá)式并把結(jié)果寫入中間文件是合算的。當(dāng)查詢的是視圖時(shí)，定義視圖的表達(dá)式就是公共子表達(dá)式的情況。9.6.2查詢優(yōu)化的一般準(zhǔn)則9.6.3關(guān)系代數(shù)等價(jià)變換規(guī)則1.關(guān)系代數(shù)等價(jià)的定義如果兩個(gè)查詢表達(dá)式E1和E2查詢的結(jié)果是相同的，那么它們是等價(jià)的，記為：E1

E2。2.常用的等價(jià)變換規(guī)則

（1）連接、笛卡爾積交換律設(shè)E1和E2是關(guān)系代數(shù)表達(dá)式，F(xiàn)是連接運(yùn)算的條件，則有：9.6.3關(guān)系代數(shù)等價(jià)變換規(guī)則

(2)連接、笛卡爾積的結(jié)合律

E1，E2，E3是關(guān)系代數(shù)表達(dá)式，F(xiàn)l和F2是連接運(yùn)算的條件

，則有：9.6.3關(guān)系代數(shù)等價(jià)變換規(guī)則（3）投影的串接定律

這里E是關(guān)系代數(shù)表達(dá)式Ai(i=1,2,...,n),Bj(j=l,2,...,m)是屬性名且{A1,A2,...,An}構(gòu)成{Bl，B2，...，Bm}的子集。

9.6.3關(guān)系代數(shù)等價(jià)變換規(guī)則

（4）選擇的串接定律這里，E是關(guān)系代數(shù)表達(dá)式，F(xiàn)l，F(xiàn)2是選擇條件。選擇的串接律說(shuō)明選擇條件可以合并。這樣一次就可檢查全部條件。9.6.3關(guān)系代數(shù)等價(jià)變換規(guī)則

（5）選擇與投影的交換律這里，選擇條件F只涉及屬性A1,...,An。若F中有不屬于A1,...,An的屬性B1，…,Bm，則有更一般的規(guī)則：

9.6.3關(guān)系代數(shù)等價(jià)變換規(guī)則（6）選擇與笛卡爾積的交換律

如果F中涉及的屬性都是El中的屬性,則

如果F=F1∧F2，并且F1只涉及El中的屬性，F(xiàn)2只涉及E2中的屬性，則由上面的等價(jià)變換規(guī)則可推出：

如果F1只涉及El中的屬性，F(xiàn)2涉及El和E2兩者的屬性，則仍有9.6.3關(guān)系代數(shù)等價(jià)變換規(guī)則

（7）選擇與差運(yùn)算的交換

若E1與E2有相同的屬性名，則9.6.3關(guān)系代數(shù)等價(jià)變換規(guī)則

（8）選擇與差運(yùn)算的交換若E1與E2有相同的屬性名，則9.6.3關(guān)系代數(shù)等價(jià)變換規(guī)則

（9）投影與笛卡爾積的交換設(shè)E1和E2是兩個(gè)關(guān)系表達(dá)式，A1，...，An是E1的屬性，B1，...，Bm是E2的屬性，則9.6.3關(guān)系代數(shù)等價(jià)變換規(guī)則

（10）投影與并的交換設(shè)E1和E2有相同的屬性名，則9.6.3關(guān)系代數(shù)等價(jià)變換規(guī)則9.6.4關(guān)系代數(shù)表達(dá)式的優(yōu)化算法1.查詢樹的概念定義9-7

查詢樹是一棵樹T=(V,E)，其中：

1）V是節(jié)點(diǎn)集，每個(gè)非葉節(jié)點(diǎn)是關(guān)系操作符，葉節(jié)點(diǎn)是關(guān)系名（即查詢涉及的關(guān)系）。

2）E是邊集，二節(jié)點(diǎn)有邊(V1,V2)，當(dāng)且僅當(dāng)V2是V1的操作分量。查詢樹包括葉節(jié)點(diǎn)和非葉節(jié)點(diǎn)。葉節(jié)點(diǎn)是關(guān)系名（即查詢涉及的關(guān)系），非葉節(jié)點(diǎn)是關(guān)系操作符。

例9-15有查詢Q1：“查詢北部地區(qū)所屬部門發(fā)出訂單的供應(yīng)商號(hào)?！边@個(gè)查詢Q1的SQL表達(dá)式為：

SELECT

供應(yīng)商號(hào)

FROM

部門,供應(yīng)商

WHERE供應(yīng)商.供應(yīng)商號(hào)=部門.供應(yīng)商號(hào)

AND

地區(qū)=北部其相應(yīng)的關(guān)系代數(shù)表達(dá)式為：

其相應(yīng)的查詢樹如圖9-9所示。2.查詢優(yōu)化算法9.6.5優(yōu)化的一般步驟1.把查詢轉(zhuǎn)換成某種內(nèi)部表示首先對(duì)關(guān)系代數(shù)表達(dá)式進(jìn)行分析，給出語(yǔ)法樹，即查詢樹。例9-16

將例9-14中的實(shí)例變換成用內(nèi)部表示的語(yǔ)法樹，如圖9-12所示。經(jīng)過(guò)關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換，則可變成圖9-13所示的語(yǔ)法樹，即例9-14中Q1的語(yǔ)法樹表示。9.6.5優(yōu)化的一般步驟9.6.5優(yōu)化的一般步驟2.把語(yǔ)法樹轉(zhuǎn)換成標(biāo)準(zhǔn)(優(yōu)化)形式利用優(yōu)化算法，把原始的語(yǔ)法樹轉(zhuǎn)換成優(yōu)化的形式:

利用關(guān)系代數(shù)等價(jià)變換規(guī)則(4)、(6)，把選擇姓名=

李剛移到葉端，圖9-13中的語(yǔ)法樹便轉(zhuǎn)換成圖9-14所示的語(yǔ)法樹，這就是例9-14中Q3的語(yǔ)法樹表示。已知Q3比Ql查詢效率要高很多。9.6.5優(yōu)化的一般步驟9.6.5優(yōu)化的一般步驟3.選擇低層的存取路徑用第2步得到的語(yǔ)法樹（如圖9-14）計(jì)算關(guān)系表達(dá)式值的時(shí)候，要充分考慮索引、數(shù)據(jù)的存儲(chǔ)分布等存取路徑。利用它們進(jìn)一步改善查詢效率。這就要求優(yōu)化器去查找數(shù)據(jù)字典，獲得當(dāng)前數(shù)據(jù)庫(kù)狀態(tài)的信息。例如，選擇字段上是否有索