第六章-全局查詢到段查詢的變換

1、第六章 全局查詢到段查詢的變換一般說來，把對(duì)全局關(guān)系的查詢（稱為全局查詢）變換為段的查詢（稱為段的查詢），有幾種不同的方法，采用某些規(guī)則就可把一個(gè)全局查詢表達(dá)式重新寫成一種等價(jià)的段查詢表達(dá)式。6.1 查詢的算符樹及其等價(jià)變換例： S(學(xué)號(hào),姓名,年令,性別,系號(hào)，獎(jiǎng)學(xué)金,班長(zhǎng)學(xué)號(hào)，民族)C(課號(hào),課名,學(xué)時(shí),任課教師)SC(學(xué)號(hào), 課號(hào),成績(jī)) D(系號(hào)，系名，系主任)查詢：學(xué)生劉建所學(xué)課號(hào)及成績(jī)SELECT 課號(hào)，成績(jī)FROM S，SCWHERE S. 學(xué)號(hào) = SC. 學(xué)號(hào) AND S. 姓名 = 劉建 ； 以上是用SQL完成的查詢（語義），在內(nèi)部實(shí)現(xiàn)上，同一個(gè)語義可有多種不同方式。對(duì)上面

2、的查詢，系統(tǒng)可用下面三種方式來實(shí)現(xiàn)：T1 = PJ課號(hào),成績(jī)(SLS.學(xué)號(hào)= SC.學(xué)號(hào)S.姓名=劉建（S CP SC）T2 = PJ課號(hào),成績(jī)(SL姓名=劉建（S NJN SC）T3 = PJ課號(hào),成績(jī)（SL姓名=劉建S） NJN SC）分析上式，T1、T2、T3是等價(jià)的，但T3優(yōu)于T2，T2優(yōu)于T1。 怎樣才能寫出優(yōu)化的表達(dá)式呢? 這就要相應(yīng)有些準(zhǔn)則。引入查詢的算符樹的概念,并利用準(zhǔn)則，通過對(duì)算符樹進(jìn)行等價(jià)變換達(dá)到優(yōu)化目的。6.1.1 查詢的算符樹 Q1：查詢對(duì)北部地區(qū)的各個(gè)部門供貨的供應(yīng)商號(hào)。圖6.1是查詢Q1的算符樹的一個(gè)例子， 其中樹葉是全局關(guān)系，而每個(gè)節(jié)點(diǎn)表示了一個(gè)一元或二元的操作

3、。在本例中，先執(zhí)行結(jié)合操作，再執(zhí)行選擇和投影操作。 圖6.1 查詢Q1的一種算符樹我們可以把關(guān)系代數(shù)表達(dá)式的算符樹看作是表達(dá)式本身的語法分析樹，語法規(guī)則（產(chǎn)生式）。R 標(biāo)識(shí)符R （R）R UNOP RR R BINOP R UNOP SLFPJA BINOP CPUN DFJNFNJNINSJFNSJ上述的R可以是算符樹的葉節(jié)點(diǎn)，運(yùn)算符是枝節(jié)點(diǎn)，可通過對(duì)算符樹進(jìn)行等價(jià)變換達(dá)到優(yōu)化目的。6.1.2 關(guān)系代數(shù)的等價(jià)變換令U和B分別表示一元代數(shù)運(yùn)算符和二元代數(shù)運(yùn)算符，我們有：l 一元運(yùn)算的交換律（commutativity）： U1U2R U2U1Rl 二元運(yùn)算的操作數(shù)的交換律 R B S S B

4、Rl 二元運(yùn)算的結(jié)合律（associativity）： R B（S BT） （R B S）B Tl 一遠(yuǎn)運(yùn)算的冪等（idempotence）： UR U1U2Rl 一元運(yùn)算相對(duì)于二元運(yùn)算的分配律（distributivity）： U(R B S） U(R）B U(S）l 一元運(yùn)算的因子分解（factorization），（這種變換正好與分配律相反）： U(R）B U(S） U (R B S）下面討論對(duì)于上述各條的具體可行的情況。（見表6.1-表6.5）表6.1 一元運(yùn)算的交換律 SLF2 PJA2 SLF1（*（R） Y Y *（SLF1（R）PJ A1（*（R） SNG1 SNG2 *（PJ

5、A1（R） SNG1：Attr（F2） A1 ；SNG2：A1 º A2表6.2 二元運(yùn)算的結(jié)合律及操作數(shù)的交換律 UN DF CP JNF SJF R*S Y N Y Y N S*R （R*S)*T Y N Y SNG1 N R*(S*T)SNG1：for（R JNF1 S）JNF2T R JNF1（S JNF2 T）：Attr（F2） Attr（S）U Attr（T）：？ 表6.3 一元運(yùn)算的冪等 PJA（R） PJA1PJA2（R） SNG：A º A1，A A2 SLF（R） SLF1SLF2（R） SNG：F=F1Ù F26.4、6.5見教材。在非分布式

6、數(shù)據(jù)庫(kù)中，為了優(yōu)化查詢的執(zhí)行，給出了一些相關(guān)的等價(jià)變換的一般準(zhǔn)則： 準(zhǔn)則1 使用選擇和投影的冪等來為每個(gè)操作數(shù)關(guān)系產(chǎn)生相應(yīng)的選擇和投影。準(zhǔn)則2 把樹中的選擇和投影運(yùn)算盡可能的向下推移。圖6.2 查詢Q1的修改后的算符樹（見教材80頁） 圖6.2 就是經(jīng)過運(yùn)用準(zhǔn)則1和準(zhǔn)則2變換之后的算符樹。6.2 把全局查詢變換成段查詢 段查詢的規(guī)范表達(dá)式段查詢的規(guī)范表達(dá)式：已知在全局模式上的一個(gè)代數(shù)表達(dá)式，只要對(duì)其中出現(xiàn)的每個(gè)全局關(guān)系名代入由段重構(gòu)全局關(guān)系的代數(shù)表達(dá)式，就得到了規(guī)范表達(dá)式。采用同樣的方法可以把全局模式上的算符樹映射成分段模式上的算符樹。( a) 查詢Q1的規(guī)范形式（用段重構(gòu)代替全局關(guān)系名）（P

7、83）( b) 把算符樹中的選擇和投影向下推移（準(zhǔn)則2）圖6. 3 查詢Q1算符樹的進(jìn)一步變換（P83）6.2.2 限定關(guān)系代數(shù)學(xué)限定關(guān)系：是一種帶有限定語的關(guān)系，限定語確定了限定關(guān)系中所有元組的共同內(nèi)涵特性，并表示為：R：qR ，這個(gè)整體為限定關(guān)系。其中，R是一個(gè)關(guān)系，稱為此限定關(guān)系的實(shí)體，qR是一謂語，稱為此限定關(guān)系的限定語。這里不要求對(duì)關(guān)系的元組求出關(guān)系的限定語的值，但若可求值，則其值必為真。水平分段是限定關(guān)系的典型例子，限定語相應(yīng)于分段謂語。例如：對(duì)于SUPPLIER1，可寫成限定形式：SUPPLIER1：CITY=“SF “ 對(duì)于DEPT1，可寫成限定形式：DEPT1：DEPTNUM

8、<10這意味著SUPPLIER1中每一元組對(duì)于限定語CITY=“SF “均為真值。DEPT1 中每一元組對(duì)于限定語DEPTNUM<10均為真值。CITY=“SF“是SUPPLIER1中所有元組的共同內(nèi)涵特性。同理，DEPTNUM<10是DEPT1中所有元組的共同內(nèi)涵特性。更值得注意的是導(dǎo)出式水平分段，各段的限定語涉及多個(gè)非同類關(guān)系中的屬性。例如：SUPPLY1，可寫成限定形式：SUPPLY1：SNUM=SUPPLIER.SNUM AND SUPPLER. CITY=“SF“這里,僅局限于SUPPLY1而言,它的元組對(duì)限定語是不能求值的,但每個(gè)元組都有限定語所表達(dá)的共同內(nèi)涵特性

9、。限定關(guān)系的代數(shù)學(xué)是關(guān)系代數(shù)的一種擴(kuò)充，其中使用限定關(guān)系作為操作數(shù)，這種代數(shù)除了對(duì)關(guān)系進(jìn)行操作以外，還要對(duì)限定語進(jìn)行操作。限定關(guān)系代數(shù)學(xué)也有相應(yīng)的運(yùn)算規(guī)則，這些規(guī)則實(shí)際上是關(guān)系代數(shù)的推廣。其運(yùn)算規(guī)則為：規(guī)則1： SLFR：qR SLFR: F AND qR 證：若元組t SLFR:qR，則t R ,且t必使F為真，t也必須使 qR 為真。 SLFR：qR的限定形式為： SLF R：F AND qR 例：SUPPLIER1 = SLCITY=“SF“（SUPPLIER） 則可知有限定關(guān)系：SUPPLIER1：CITY=“SF “ SLSNUM=20SUPPLIER1：CITY=“SF “ 可寫成

10、SLSNUM=20SUPPLIER1：SNUM=20 AND CITY=“SF “ 規(guī)則2： PJAR：qR PJAR：qR A可以包含、也可以不包含限定語qR中的屬性，但都不會(huì)影響PJAR的內(nèi)涵特性，這可由限定關(guān)系的定義及其進(jìn)一步說明加以解釋。例1：PJDEPTNUM，NAMEDEPT1：DEPTNUM 10 => PJDEPTNUM，NAME DEPT1：DEPTNUM 10 例2： PJAREA，MGRNUMDEPT1：DEPTNUM 10 => PJAREA，MGRNUM DEPT1：DEPTNUM 10 規(guī)則3： R：qR CP S：qS Þ R CP S：qR

11、 AND qS 注意：這里是把兩個(gè)限定語應(yīng)用到R CP S 的不相交屬性上。 證：令 t1 R，則t1具有內(nèi)涵特性qR ， t2 S，則t2具有內(nèi)涵特性qS ，并由乘法定義知，元組< t1 ，t2 > R CP S且它必具有內(nèi)涵特性qR AND qS 。例： S（學(xué)號(hào)，系，性別） S1 = SL系=“計(jì)算機(jī)“（S） S1：系 = “計(jì)算機(jī)“ C（課程，專業(yè)，學(xué)分） C1 = SL專業(yè)=“軟件與理論“（S） C1：專業(yè) = “軟件與理論“ S1：系 = “計(jì)算機(jī)“ CP C1：專業(yè) = “軟件與理論“ S1 CP C1：系 = “計(jì)算機(jī) “ AND 專業(yè) = “軟件與理論“ 注意：兩

12、限定語不相交的屬性。規(guī)則4： R：qR DF S：qS R DF S：qR （R DF S ） R 但（R DF S ） S 有R DF S：qR 注意事項(xiàng)： R IN S = R DF（ R DF S ）= S DF（S DF R） 即交集運(yùn)算具有可交換性，即 R IN S = S IN R 如果應(yīng)用擴(kuò)充代數(shù)學(xué)的定義，將會(huì)出現(xiàn)R：qR IN S：qS Þ R：qR DF （R：qR DF S：qS）Þ R：qR DF R DF S：qRÞ R DF（R DF S）：qR Þ R IN S：qR （1）而 S：qS IN R：qR Þ S：qS

13、 DF S：qS DF R：qRÞ S：qS DF S DF R：qS Þ SDF （S DF R）：qS Þ S IN R：qS （2）事實(shí)上，我們想得到的結(jié)果是：Þ R IN S ：qR AND qS 證： 設(shè)t R IN S ,則t R且 t S t具有特性 qR且具有特性qS 。規(guī)則5： R：qR UN S：qS Þ R UN S：qR OR qS 這是顯然的。以上是把關(guān)系代數(shù)的五種基本運(yùn)算推廣到限定關(guān)系的運(yùn)算中，下面是關(guān)系代數(shù)復(fù)合運(yùn)算的推廣。規(guī)則6： R：qR JNF S：qS Þ R JNF S：qR AND qS AND

14、 F 證：R：qR JNF S：qS Þ SLF（R：qR CP S：qS） Þ SLF（R CP S：qR AND qS） Þ SLF（R CP S）：（qR AND qS） AND F Þ R JNF S ：qR AND qS AND F規(guī)則7： R：qR SJF S：qS Þ R SJF S：qR AND qS AND F 證：R：qR SJF S：qS ÞPJATTR（R）（R：qR JNF S：qS） ÞPJATTR（R）R JNF S：qR AND qS AND F （由規(guī)則6） ÞPJATTR（R）（

15、R JNF S）：qR AND qS AND F （由規(guī)則2） Þ R SJF S：qR AND qS AND F （由半結(jié)合定義）運(yùn)用規(guī)則1, 就可把圖6.3 ( b)的最右分支剪掉，因DEPT3中沒有北部地區(qū)。關(guān)系代數(shù)表達(dá)式可以進(jìn)行很多種有條件和無條件的等價(jià)變換，限定關(guān)系代數(shù)表達(dá)式也可進(jìn)行同樣的變換。例：SLCITY = “LA“SUPPLIER1：CITY=”SF“ Þ SLCITY = “LA“SUPPLIER1：CITY=”SF” AND CITY = ”LA” Þ ø （限定語為永假）通過識(shí)別空關(guān)系的過程可大大簡(jiǎn)化查詢樹，運(yùn)用規(guī)則1,可把圖6

16、.3 ( b)最右分支剪掉，因DEPT3中沒有北部地區(qū)。針對(duì)限定關(guān)系的代數(shù)運(yùn)算，可考慮如下幾個(gè)優(yōu)化的新準(zhǔn)則：準(zhǔn)則3 把選擇向下推到樹葉處， 然后對(duì)它們使用限定關(guān)系的代數(shù)運(yùn)算：如果結(jié)果的限定語是永假式，則用空關(guān)系來代替此選擇的結(jié)果。準(zhǔn)則4 利用限定關(guān)系的代數(shù)運(yùn)算來求結(jié)合的操作數(shù)的限定語之值；如果這個(gè)結(jié)合的結(jié)果的限定語是永假式，則用空關(guān)系來代替此子樹（包括此結(jié)合及它的操作數(shù)在內(nèi)）。 水平分段關(guān)系的化簡(jiǎn)例Q3：查閱部門號(hào)為1的部門名、地區(qū)及經(jīng)理號(hào)。 對(duì)全局關(guān)系 DEPT 進(jìn)行操作： SLDEPTNUM=1DEPT 現(xiàn)將這一全局查詢變換到段查詢（查詢的規(guī)范化格式） SLDEPTNUM=1 SLDEPT

17、NUM=1 UN DEPT1:DEPTNUM10DEPT1: DEPT2 DEPT3DEPTNUM10 10< DEPTNUM20 DEPTNUM>20 (a) 查詢Q3的規(guī)范形式 （b）查詢Q3的化簡(jiǎn) 圖6.5 水平分段關(guān)系的化簡(jiǎn)再如：運(yùn)用限定關(guān)系的運(yùn)算規(guī)則1和優(yōu)化準(zhǔn)則3,可把圖6.3 ( b)最右分支剪掉，因DEPT3可寫成限定形式DEPT3：DEPTNUM>20，限定語表明DEPT3中的元組都是南部地區(qū)（沒有北部地區(qū)）的部門，AREA=NORTH 意味NOT（DEPTNUM>20）。水平分段關(guān)系之間結(jié)合的化簡(jiǎn)分布結(jié)合的例子：Q4：查詢至少有一個(gè)供應(yīng)訂單的供應(yīng)商號(hào)和

18、名：SNUM，NAME。 Q4 ：PJSNUM，NAME（SUPPLY NJN SUPPLIERE） PJSNUM，NAME NJNDEPTNUM=DEPTNUM UN UNSUPPLY1：SNUM= SUPPLY2：SNUM= SUPPLIER1： SUPPLIER2：SUPPLIER.SNUM AND SUPPLIER.SNUM AND CITY=”SP” CITY=”LA”SUPPLIER.CITY=”SF” SUPPLIER.CITY=”LA”（a） 查詢Q4的規(guī)范形式準(zhǔn)則5：為了分布出現(xiàn)在全局查詢中的結(jié)合，可以把并運(yùn)算（代表段的收集）推向結(jié)合之上。上述準(zhǔn)則可用于簡(jiǎn)化水平分段關(guān)系與水平

19、分段關(guān)系之間的結(jié)合。UN PJSNUM，NAME PJSNUM，NAME NJN NJNSUPPLY1：SNUM= SUPPLIER1： SUPPLY2：SNUM= SUPPLIER2：CITY=”LA”SUPPLIER1.SNUM AND CITY=”SF” SUPPLIER2.SNUM ANDSUPPLIER1.CITY=”SF” SUPPLIER2.CITY=”SF” （b） 查詢Q4的分布式結(jié)合（運(yùn)用準(zhǔn)則5，把并運(yùn)算推向結(jié)合之上） 圖6.5 水平分段關(guān)系之間結(jié)合的化簡(jiǎn)這里已經(jīng)剪掉了2個(gè)限定關(guān)系結(jié)合對(duì)子：SUPPLY1 NJN SUPPLIER2 和 SUPPLY2 NJN SUPPLI

20、ER1因?yàn)槔脺?zhǔn)則4，可知限定語為永假。采用推論方法（inference）進(jìn)一步化簡(jiǎn) 已經(jīng)看到，在對(duì)限定關(guān)系進(jìn)行選擇性查詢或結(jié)合性查詢時(shí)，利用準(zhǔn)則3和準(zhǔn)則4對(duì)限定語進(jìn)行是否為永假式的判斷是極為有用的，但有些情況確定一個(gè)公式是否為永假式并非可直接判斷，可以采用更為復(fù)雜的內(nèi)涵信息，并要求使用定理證明程序加以判斷。仍以Q1為例：Q1：查詢對(duì)北部地區(qū)分公司供貨的供應(yīng)商號(hào)。PJSNUMSLAREA=“NORTH“（SUPPLY JNDEPTNUM=DEPTNUM DEPT） 假設(shè)：1. 北部地區(qū)僅包含了部門110 。 2. 來自部門110 的訂單全部送給“SF“的供應(yīng)商。 利用上面假設(shè)來推導(dǎo)哪些是永假，

21、以便消除相應(yīng)子表達(dá)式。 首先，由第1條有下面蘊(yùn)涵式： AREA = “NORTH“ Þ NOT（10<DEPTNUM20） AREA = “NORTH“ Þ NOT（DEPTNUM>20） 利用準(zhǔn)則3，把選擇操作應(yīng)用到段DEPT1，DEPT2，DEPT3，并求出結(jié)果的限定語的值，借助上面的蘊(yùn)涵式，知其中兩個(gè)段DEPT2、DEPT3為永假，可消去相應(yīng)的子表達(dá)式，得到圖6.6（a）所示的算符樹。 PJSNUM JNDEPTNUM=DEPTNUM UN UN PJSNUM,DEPTNUM PJSNUM,DEPTNUM SLAREA=”NORTH”SUPPLY1:SNU

22、M= SUPPLY2:SNUM= DEPT1:SUPPLIER1.SNUM AND SUPPLIER2.SNUM AND 1DEPTNUM<10SUPPLIER1.CITY=”SF” SUPPLIER2.CITY=”LA” （a） PJSNUM JNDEPTNUM=DEPTNUM PJSNUM,.DEPTNUM PJDEPTNUMSUPPLY1:SNUM= SLAREA=”NORTH”SUPPLIER1.SNUM AND SUPPLIER1.CITY=”SF” DEPT1：1DEPTNUM<10 （b） 圖6.6 采用推論方法進(jìn)行算符樹的化簡(jiǎn)然后，利用準(zhǔn)則5將合并運(yùn)算上移至結(jié)合之上

23、，再分配該結(jié)合：SUPPLY1與DEPT1結(jié)合，SUPPLY2與DEPT1結(jié)合，由假設(shè)1可知： AREA = “NORTH“ Þ DEPTNUM 10而由假設(shè)2可知：DEPTNUM 10 Þ NOT（SNUM=SUPPLIER.SNUM AND SUPPLIER.CITY=”LA”)通過運(yùn)用準(zhǔn)則4，可知SUPPLY2與DEPT1結(jié)合將為空。于是得到圖6.6（b）所示的算符樹。6.2.6垂直分段關(guān)系的化簡(jiǎn)將垂直分段關(guān)系的查詢表達(dá)式變化成規(guī)范表達(dá)式之后，一般都要用到結(jié)合操作（重構(gòu)全局關(guān)系）。希望尋找一個(gè)適當(dāng)?shù)淖蛹湍茏阋曰卮饐栴}，這樣就可刪除其余段，達(dá)到簡(jiǎn)化目的。例：Q5：列出

24、雇員姓名及工資收入。(見P47分段模式) PJNAME，SALEMP PJNAME,SAL JNEMPTNUM=EMPTNUM EMP4：true UN PJNAME,SAL EMP4：true EMP1: EMP2 EMP3 DEPTNUM10 10<DEPTNUM20 DEPTNUM>20（a）查詢Q5的規(guī)范算符樹 （b）化簡(jiǎn)算符樹 圖6.8 垂直分段關(guān)系的化簡(jiǎn)EMP被垂直地分成第一個(gè)段EMP4（描述雇員的工資管理）和第2個(gè)段，而第2個(gè)段又進(jìn)一步水平地分片成EMP1，EMP2，EMP3 。由于EMP4的屬性包含了NAME和SAL，所以僅用段EMP4就可回答該查詢，并且可以通過剪

25、掉結(jié)合的一個(gè)分支進(jìn)而剪掉了結(jié)合及其下面的各段合并運(yùn)算?；?jiǎn)算符樹如圖6.8（b）所示。由此可見：垂直分段的運(yùn)算規(guī)則可簡(jiǎn)化大多數(shù)查詢，即把大多的查詢局部于某個(gè)段內(nèi)。半結(jié)合操作半結(jié)合是關(guān)系代數(shù)的一種導(dǎo)出式運(yùn)算，它在分布式查詢中有著特殊的重要性。有時(shí)將結(jié)合運(yùn)算轉(zhuǎn)換成半結(jié)合運(yùn)算可使查詢大大簡(jiǎn)化。給定一“相等結(jié)合” R JNA=B S ，這里A和B分別是R和S的屬性（或更一般地說，是屬性組），其半結(jié)合程序如下： S JNA=B（R SJA=B PJB S） 直觀分析：設(shè)R，S分布在 JNA=B 不同站點(diǎn)上，將S 投影到 B上，可將結(jié)果發(fā)送給R站 SJA=B 點(diǎn)，再在R的站點(diǎn)上執(zhí)行此 R PJB 請(qǐng)求點(diǎn)

26、半結(jié)合運(yùn)算，再把半結(jié)合結(jié)果 S 送到S站點(diǎn)，最后在S的站點(diǎn)執(zhí)行結(jié)合操作 圖6.8 半結(jié)合程序的算符樹優(yōu)點(diǎn)是：（1）S投影后數(shù)據(jù)量大大減少（只傳有用的，淘汰無用的） （2）半結(jié)合后，R的元組中只有一個(gè)子集“存活”（只留有用的，淘汰無用的），而存活元組恰恰要與S結(jié)合。例： S(學(xué)號(hào),姓名,年令,性別,系號(hào),獎(jiǎng)學(xué)金,班長(zhǎng)學(xué)號(hào),民族)C(課號(hào),課名,學(xué)時(shí),任課教師)SC(學(xué)號(hào), 課號(hào),成績(jī)) D(系號(hào)，系名，系主任)設(shè)表S、R分別在站點(diǎn)S和站點(diǎn)R上，請(qǐng)同學(xué)們分別寫出請(qǐng)求： 列出少數(shù)民族學(xué)生的學(xué)號(hào)，姓名，性別，課號(hào)，成績(jī) PJ學(xué)號(hào)，姓名，性別，課號(hào)，成績(jī)（SL民族<>“漢“ （S NJN S

27、C）發(fā)生在站點(diǎn)S和站點(diǎn)R上的含有半結(jié)合運(yùn)算的關(guān)系代數(shù)表達(dá)式。6.3分布式分組和聚集函數(shù)的求值數(shù)據(jù)庫(kù)應(yīng)用往往需要執(zhí)行不能用關(guān)系代數(shù)來表示的數(shù)據(jù)庫(kù)訪問操作，所以關(guān)系數(shù)據(jù)庫(kù)的查詢語言一般允許使用不能化簡(jiǎn)成關(guān)系代數(shù)表達(dá)式的查詢式子。這些附加特性中最重要的特性是能把元組分組成關(guān)系的不相交子集（水平或?qū)С鍪剿椒侄危约澳芡ㄟ^對(duì)它們求聚集函數(shù)的值進(jìn)而求出對(duì)全局關(guān)系的聚集函數(shù)的值。聚集函數(shù)有：SUM（屬性），AVG（屬性），COUNT（*），MAX（屬性），MIN（屬性）如求學(xué)習(xí)課號(hào)為C2課的學(xué)生總數(shù)。 SELECT COUNT（*） FROM SC WHERE 課號(hào) = “C2“；求平均年齡 SELEC

28、T AVG（年齡） FROM S ；求最大年齡的學(xué)生的姓名、性別 SELECT 姓名，性別，MAX（年齡） FROM S； Q6：查詢產(chǎn)品“P1“的平均訂貨量。 SELECT AVG（QUAN） FROM SUPPLYWHERE PNUM = “P1“ ； Q7：查每一供應(yīng)商所供應(yīng)每種零件的總數(shù)量。 SELECT SNUM，PNUM，SUM（QUAN）：TOTAL FROM SUPPLY GROUP BY SNUM，PNUM；Q8：接Q7，但僅保留總和值大于300的那些組。 SELECT SNUM，PNUM，SUM（QUAN） FROM SUPPLY GROUP BY SNUM，PNUM HA

29、VING SUM（QUAN）> 300 ；聚集函數(shù)、分組功能都不能用關(guān)系代數(shù)來表達(dá)，需對(duì)關(guān)系代數(shù)進(jìn)行擴(kuò)充。 關(guān)系代數(shù)的擴(kuò)充用group-by GBG,AFR操作來擴(kuò)充關(guān)系代數(shù)。用G表示某一屬性集合，由此集合的值來決定R的分組。用AF表示要對(duì)每個(gè)組求值的聚集函數(shù)。GBG,AFR是一個(gè)關(guān)系，該關(guān)系的框架結(jié)構(gòu)是由G的屬性和AF的聚集函數(shù)組成，元組數(shù)目就是R按G值進(jìn)行分組的數(shù)目，AF所決定的屬性值就是對(duì)相應(yīng)組求出的聚集函數(shù)的值（不分組，則默認(rèn)為一個(gè)組）。G或AF可以不指定。 利用上述操作可以用代數(shù)形式來書寫Q6、Q7、Q8 。Q6：求產(chǎn)品P1的平均訂貨量。 GBAVG（QUAN）SLPNUM =

30、P1SUPPLY （G為空，作用于選擇后的所有元組）。 Q7：求每一供應(yīng)商供應(yīng)每種零件的總量GBSNUM，PNUM，SUM（QUAN）SUPPLY Q8：求由同一廠商供應(yīng)的每種零件的總量達(dá)300以上的供應(yīng)商號(hào)，零件號(hào)，總量。 SL SUM（QUAN）>300GBSNUM，PNUM，SUM（QUAN） TSUPPLY Q9：求訂單量達(dá)300以上的供應(yīng)商號(hào)，零件號(hào)，訂貨量。 PJ SNUM，PNUM，QUAN SLQUAN300 SUPPLY請(qǐng)自己寫出對(duì)于教學(xué)模型的相關(guān)詢問。6.3.2 GROUP BY 操作的特性（1） 分組操作的分布計(jì)算首先考察GB相對(duì)于合并運(yùn)算的分配率。GBG，AF（R

31、1 UN R2） （GBG，AFR1） UN （GBG，AF R2）當(dāng)且僅當(dāng)：對(duì)任意的i ，j （i是被分組的下標(biāo)， j是待合并運(yùn)算的段的下標(biāo)，Gi是第i個(gè)分組中原始記錄的集合），或者（Gi Rj）或者（Gi U Rj = ø）（*）即每個(gè)組所涉及的記錄必須全部在同一個(gè)段里，不能跨段。顯然，對(duì)全局關(guān)系進(jìn)行分組計(jì)算只要滿足上述條件，則可先分布式分組計(jì)算，然后再合并。更重要的是站點(diǎn)間并行工作（各段在不同站點(diǎn)上）。為此給出如下準(zhǔn)則：準(zhǔn)則6：為了在一個(gè)全局查詢中進(jìn)行分布分組和組內(nèi)聚合函數(shù)的求值，在滿足（Gi Rj）或者（Gi U Rj = ø）的條件下，應(yīng)把合并（段收集水平分段的重

32、構(gòu)）向上推至相應(yīng)的GROUP BY 操作范圍之上。例：Q8：求同一廠商供應(yīng)的每種零件供應(yīng)總量達(dá)300以上的供應(yīng)商號(hào)，零件號(hào)，總量。 SL SUM（QUAN）>300GBSNUM，PNUM，SUM（QUAN）SUPPLY SNUM的值相同元組絕不跨段，可用準(zhǔn)則6。 SLSUM（QUAN）300 UN GBSNUM,PNUM,SUM(QUAN) SLSUM(QUAN)300 SLSUM(QUAN)300 UN GBSNUM,PNUM,SUM(QUAN) GBSNUM,PNUM,SUM（QUAN）SUPLLY1 SUPPLY2 SUPPLY1： SUPPLY2： （a）Q8的規(guī)范形式 （b）Q

33、8的分布形式 圖6.9 具有分組及聚集函數(shù)的查詢但注意，求每一零件的訂貨總量則不能分布式計(jì)算聚合函數(shù)，因同一個(gè)零件號(hào)可在不同段中。表達(dá)式：GBPNUM，SNM（QUAN）SUPPLY 只能寫成： GBPNUM，SUM（QUAN）（SUPPLY1 UN SUPPLY2） 而不能將GB對(duì)合并進(jìn)行分配計(jì)算，即不能寫成：R = GBPNUM,SUM(QUAN)(SUPPLY1) UN GBPNUM，SUM（QUAN）（SUPPLY2） 通過這個(gè)例子，我們來考慮把一個(gè)聚合函數(shù)F分解成F1，F(xiàn)2， ，F(xiàn)m ，使得Fi（i = 1,2，m）僅對(duì)段實(shí)施操作，然后再對(duì)各段操作后的結(jié)果進(jìn)行加工，如上面的MAX（）

34、函數(shù)，對(duì)各段求MAX（）值后再選一次最大。但若求每一零件的平均訂貨量則上式不好用，不能按上述方法進(jìn)行分布計(jì)算，能否有其它解決辦法？下面考慮聚集函數(shù)的分布計(jì)算表達(dá)形式:對(duì)于聚合函數(shù)F、關(guān)系R，及R的子集R1, R2 , , Rn 可表示為：F(R)=E(F1(R1),F1(Rn),F2(R1) , F2(Rn) ,Fm(R1) , Fm(Rn) 其中：（1）SUM計(jì)算 SUM(R)= SUM(SUM(R1), SUM(R2),SUM(Rn) 這里，m=1，F(xiàn)1是SUM，E也是SUM(2) MAX計(jì)算 MAX(R) = MAX(MAX(R1), MAX(R2), MAX(Rn)（3）Min計(jì)算 M

35、IN(R) = MIN(MIN(R1), MIN(R2), MAX(Rn)(4) COUNT計(jì)算 COUNT(R)=SUM(COUNT(R1),COUNT(R2), COUNT(Rn) (5)AVG(R) = SUM(SUM(R1), SUM(R2),SUM(Rn)/ SUM(COUNT(R1),COUNT(R2),COUNT(Rn)這里，m=2，F(xiàn)1是SUM，F(xiàn)2是COUNT ，E是SUM與COUNT等的組合運(yùn)算。聚集函數(shù)的分布式計(jì)算在分布式數(shù)據(jù)庫(kù)中是一個(gè)重要的特性，因?yàn)榭梢园押瘮?shù)F1（R1）， ,F1（Rn）的部分結(jié)果傳送給一公共站點(diǎn)，然后在這個(gè)公共站點(diǎn)處求表達(dá)式E的值，而不用象原先那樣把

36、所有的數(shù)據(jù)傳遞給該站點(diǎn)，并在該站點(diǎn)計(jì)算聚集函數(shù)。下面是Q6的例子：求產(chǎn)品P1的平均訂貨量。GBAVG（QUAN）SLPNUM =P1SUPPLY （*，p1為選擇的條件）（G為空，作用于選擇后的所有元組） GBAVG(QUAN) E:AVG(QUAN)=SUM(S1,S2)/SUM(C1,C2）SLPNUM=P1 S1,C1:GBSUM(QUAN),COUNT S2,C2:GBSUM(QUAN),COUNT UN SLPNUM=P1 SLPNUM=P1 SUPPLY1 SUPPLY2 SUPPLY1 SUPPLY2 （a） 查詢Q6的規(guī)范形式 （b）查詢Q6的分布式形式 圖6.10 聚集函數(shù)的

37、分布式求值 圖6.10（a）表示了此查詢的規(guī)范形式，在這種情況下，不可能使用準(zhǔn)則6，因?yàn)椴痪邆浞植加?jì)算條件，為解決這個(gè)查詢，可對(duì)兩個(gè)段SUPPLY1和SUPPLY2進(jìn)行獨(dú)立的子查詢操作：GBSUM（QUAN），COUNT（*）SLPNUM=P1SUPPLY1 （結(jié)果存于S1,C1中）。GBSUM（QUAN），COUNT（*）SLPNUM=P1SUPPLY2 （結(jié)果存于S2,C2中）。 令S1、C1分別為對(duì)SUPPLY1的GB操作的屬性：SUM（QUAN）和COUNT 中的值，同理，S2和C2分別為對(duì)SUPPLY2的GB操作的屬性：SUM（QUAN）和COUNT中的值，因而數(shù)量的平均值A(chǔ)VG（Q

38、UAN）由式子（S1+S2）/（C1+C2）給出。這樣，把S1，S2，C1和C2傳送到要產(chǎn)生查詢結(jié)果的站點(diǎn)上，并在那兒計(jì)算AVG（QUAN）的值。如果沒有這種變換，則在函數(shù)的非分布式求值時(shí)就需要在同一站點(diǎn)上從段SUPPLY1和SUPPLY2收集實(shí)際的元組，顯然網(wǎng)上傳輸量大，相應(yīng)的聚集函數(shù)求值效率也低。6.4 參數(shù)性查詢?cè)诓樵兊倪x擇準(zhǔn)則公式中包含了在此查詢編譯時(shí)尚不知其值的一些參數(shù)，當(dāng)執(zhí)行參數(shù)查詢時(shí)，只能由用戶提供這些參數(shù)的值，在這種情況下，編譯時(shí)準(zhǔn)備好帶有參數(shù)的限定語，運(yùn)行時(shí)可以使用不同的參數(shù)值重復(fù)執(zhí)行，由于參數(shù)值的不同，每次執(zhí)行完后將送回不同的執(zhí)行結(jié)果。 參數(shù)性查詢的化簡(jiǎn)和代數(shù)的擴(kuò)充例：Q9

39、：查部門號(hào)為為任意給定的 $X或 $Y 的部門信息。顯然對(duì)DEPTNUM上的選擇查詢是參數(shù)性的： Q9：SLDEPTNUM=$X OR DEPTNUM=$YSUPPLY運(yùn)行時(shí)由發(fā)出此查詢的程序來給參數(shù) $X 和 $Y 賦以實(shí)際的值。參數(shù)性查詢化簡(jiǎn)可以在編譯時(shí)完成一部分，另一部分需要在運(yùn)行時(shí)完成。參數(shù)性查詢的化簡(jiǎn)涉及了限定關(guān)系代數(shù)的應(yīng)用，以便決定子表達(dá)式的限定語是否為永假式。上例中，假設(shè)在發(fā)出此查詢時(shí)，參數(shù)值為：X = 1 和 Y= 13。于是，由于選擇公式“DEPTNUM=1 OR DEPTNUM = 13”與它的限定語矛盾，因此有可能在運(yùn)行時(shí)化簡(jiǎn)DEPT3的直樹，我們期望大部分的優(yōu)化工作在編

40、譯時(shí)進(jìn)行，尤其是對(duì)經(jīng)常被激活的參數(shù)性查詢。 SLDEPTNUM=$X OR DEPTNUM=$YUN DEPT1： DEPT2： DEPT3： DEPTNUM10 10< DEPTNUM 20 DEPTNUM> 20 （a） 查詢Q9的規(guī)范形式 CUT $X10 $X>20 OR OR $Y10 $Y>20 ($X>10 AND $X20 OR $Y>10 AND $Y20SLDEPTNUM=$X OR DEPTNUM=$Y SLDEPTNUM=$X OR DEPTNUM=$YSLDEPTNUM=$XOR DEPTNUM=$YDEPT1： DEPT2： DE

41、PT3：DEPTNUM10 10< DEPTNUM 20 DEPTNUM> 20 （b） 帶有CUT操作的 查詢樹 圖6.12 參數(shù)性查詢中CUT的使用為了表示在算符樹上存在用于運(yùn)行時(shí)化簡(jiǎn)的測(cè)試，用一新的n元算符稱作剪枝（CUT）來替代結(jié)合算符，該新算符只對(duì)其幾個(gè)操作數(shù)執(zhí)行結(jié)合。每個(gè)公式在編譯時(shí)準(zhǔn)備好而在運(yùn)行時(shí)求值，若送回的結(jié)果為真，則其相應(yīng)的操作數(shù)就包含在此結(jié)合操作中，如果計(jì)算結(jié)果為假值，則相應(yīng)的操作數(shù)就從樹中消去。圖6.12（b）表示了這個(gè)參數(shù)性查詢的新算符樹，在該例中，應(yīng)用準(zhǔn)則2把選擇操作推至結(jié)合操作的下面，然后用CUT操作取代該結(jié)合操作，CUT操作用到的三個(gè)公式（對(duì)應(yīng)結(jié)合操作