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

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

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

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

4、Rl 二元運算的結(jié)合律（associativity）： R B（S BT） （R B S）B Tl 一遠運算的冪等（idempotence）： UR U1U2Rl 一元運算相對于二元運算的分配律（distributivity）： U(R B S） U(R）B U(S）l 一元運算的因子分解（factorization），（這種變換正好與分配律相反）： U(R）B U(S） U (R B S）下面討論對于上述各條的具體可行的情況。（見表6.1-表6.5）表6.1 一元運算的交換律 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 二元運算的結(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 一元運算的冪等 PJA（R） PJA1PJA2（R） SNG：A º A1，A A2 SLF（R） SLF1SLF2（R） SNG：F=F1Ù F26.4、6.5見教材。在非分布式

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

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

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

9、。限定關(guān)系的代數(shù)學是關(guān)系代數(shù)的一種擴充，其中使用限定關(guān)系作為操作數(shù)，這種代數(shù)除了對關(guān)系進行操作以外，還要對限定語進行操作。限定關(guān)系代數(shù)學也有相應的運算規(guī)則，這些規(guī)則實際上是關(guān)系代數(shù)的推廣。其運算規(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中的屬性，但都不會影響PJAR的內(nèi)涵特性，這可由限定關(guā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 注意：這里是把兩個限定語應用到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（學號，系，性別） S1 = SL系=“計算機“（S） S1：系 = “計算機“ C（課程，專業(yè)，學分） C1 = SL專業(yè)=“軟件與理論“（S） C1：專業(yè) = “軟件與理論“ S1：系 = “計算機“ CP C1：專業(yè) = “軟件與理論“ S1 CP C1：系 = “計算機 “ 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 注意事項： R IN S = R DF（ R DF S ）= S DF（S DF R） 即交集運算具有可交換性，即 R IN S = S IN R 如果應用擴充代數(shù)學的定義，將會出現(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）事實上，我們想得到的結(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ù)的五種基本運算推廣到限定關(guān)系的運算中，下面是關(guān)系代數(shù)復合運算的推廣。規(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é)合定義）運用規(guī)則1, 就可把圖6.3 ( b)的最右分支剪掉，因DEPT3中沒有北部地區(qū)。關(guān)系代數(shù)表達式可以進行很多種有條件和無條件的等價變換，限定關(guān)系代數(shù)表達式也可進行同樣的變換。例：SLCITY = “LA“SUPPLIER1：CITY=”SF“ Þ SLCITY = “LA“SUPPLIER1：CITY=”SF” AND CITY = ”LA” Þ ø （限定語為永假）通過識別空關(guān)系的過程可大大簡化查詢樹，運用規(guī)則1,可把圖6

16、.3 ( b)最右分支剪掉，因DEPT3中沒有北部地區(qū)。針對限定關(guān)系的代數(shù)運算，可考慮如下幾個優(yōu)化的新準則：準則3 把選擇向下推到樹葉處， 然后對它們使用限定關(guān)系的代數(shù)運算：如果結(jié)果的限定語是永假式，則用空關(guān)系來代替此選擇的結(jié)果。準則4 利用限定關(guān)系的代數(shù)運算來求結(jié)合的操作數(shù)的限定語之值；如果這個結(jié)合的結(jié)果的限定語是永假式，則用空關(guān)系來代替此子樹（包括此結(jié)合及它的操作數(shù)在內(nèi)）。 水平分段關(guān)系的化簡例Q3：查閱部門號為1的部門名、地區(qū)及經(jīng)理號。 對全局關(guān)系 DEPT 進行操作： 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的化簡 圖6.5 水平分段關(guān)系的化簡再如：運用限定關(guān)系的運算規(guī)則1和優(yōu)化準則3,可把圖6.3 ( b)最右分支剪掉，因DEPT3可寫成限定形式DEPT3：DEPTNUM>20，限定語表明DEPT3中的元組都是南部地區(qū)（沒有北部地區(qū)）的部門，AREA=NORTH 意味NOT（DEPTNUM>20）。水平分段關(guān)系之間結(jié)合的化簡分布結(jié)合的例子：Q4：查詢至少有一個供應訂單的供應商號和

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ī)范形式準則5：為了分布出現(xiàn)在全局查詢中的結(jié)合，可以把并運算（代表段的收集）推向結(jié)合之上。上述準則可用于簡化水平分段關(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é)合（運用準則5，把并運算推向結(jié)合之上） 圖6.5 水平分段關(guān)系之間結(jié)合的化簡這里已經(jīng)剪掉了2個限定關(guān)系結(jié)合對子：SUPPLY1 NJN SUPPLIER2 和 SUPPLY2 NJN SUPPLI

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

21、以便消除相應子表達式。 首先，由第1條有下面蘊涵式： AREA = “NORTH“ Þ NOT（10<DEPTNUM20） AREA = “NORTH“ Þ NOT（DEPTNUM>20） 利用準則3，把選擇操作應用到段DEPT1，DEPT2，DEPT3，并求出結(jié)果的限定語的值，借助上面的蘊涵式，知其中兩個段DEPT2、DEPT3為永假，可消去相應的子表達式，得到圖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 采用推論方法進行算符樹的化簡然后，利用準則5將合并運算上移至結(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”)通過運用準則4，可知SUPPLY2與DEPT1結(jié)合將為空。于是得到圖6.6（b）所示的算符樹。6.2.6垂直分段關(guān)系的化簡將垂直分段關(guān)系的查詢表達式變化成規(guī)范表達式之后，一般都要用到結(jié)合操作（重構(gòu)全局關(guān)系）。希望尋找一個適當?shù)淖蛹湍茏阋曰卮饐栴}，這樣就可刪除其余段，達到簡化目的。例：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）化簡算符樹 圖6.8 垂直分段關(guān)系的化簡EMP被垂直地分成第一個段EMP4（描述雇員的工資管理）和第2個段，而第2個段又進一步水平地分片成EMP1，EMP2，EMP3 。由于EMP4的屬性包含了NAME和SAL，所以僅用段EMP4就可回答該查詢，并且可以通過剪

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

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

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

28、T AVG（年齡） FROM S ；求最大年齡的學生的姓名、性別 SELECT 姓名，性別，MAX（年齡） FROM S； Q6：查詢產(chǎn)品“P1“的平均訂貨量。 SELECT AVG（QUAN） FROM SUPPLYWHERE PNUM = “P1“ ； Q7：查每一供應商所供應每種零件的總數(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ù)來表達，需對關(guān)系代數(shù)進行擴充。 關(guān)系代數(shù)的擴充用group-by GBG,AFR操作來擴充關(guān)系代數(shù)。用G表示某一屬性集合，由此集合的值來決定R的分組。用AF表示要對每個組求值的聚集函數(shù)。GBG,AFR是一個關(guān)系，該關(guān)系的框架結(jié)構(gòu)是由G的屬性和AF的聚集函數(shù)組成，元組數(shù)目就是R按G值進行分組的數(shù)目，AF所決定的屬性值就是對相應組求出的聚集函數(shù)的值（不分組，則默認為一個組）。G或AF可以不指定。 利用上述操作可以用代數(shù)形式來書寫Q6、Q7、Q8 。Q6：求產(chǎn)品P1的平均訂貨量。 GBAVG（QUAN）SLPNUM =

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

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

32、構(gòu)）向上推至相應的GROUP BY 操作范圍之上。例：Q8：求同一廠商供應的每種零件供應總量達300以上的供應商號，零件號，總量。 SL SUM（QUAN）>300GBSNUM，PNUM，SUM（QUAN）SUPPLY SNUM的值相同元組絕不跨段，可用準則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ù)的查詢但注意，求每一零件的訂貨總量則不能分布式計算聚合函數(shù)，因同一個零件號可在不同段中。表達式：GBPNUM，SNM（QUAN）SUPPLY 只能寫成： GBPNUM，SUM（QUAN）（SUPPLY1 UN SUPPLY2） 而不能將GB對合并進行分配計算，即不能寫成：R = GBPNUM,SUM(QUAN)(SUPPLY1) UN GBPNUM，SUM（QUAN）（SUPPLY2） 通過這個例子，我們來考慮把一個聚合函數(shù)F分解成F1，F(xiàn)2， ，F(xiàn)m ，使得Fi（i = 1,2，m）僅對段實施操作，然后再對各段操作后的結(jié)果進行加工，如上面的MAX（）

34、函數(shù)，對各段求MAX（）值后再選一次最大。但若求每一零件的平均訂貨量則上式不好用，不能按上述方法進行分布計算，能否有其它解決辦法？下面考慮聚集函數(shù)的分布計算表達形式:對于聚合函數(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計算 SUM(R)= SUM(SUM(R1), SUM(R2),SUM(Rn) 這里，m=1，F(xiàn)1是SUM，E也是SUM(2) MAX計算 MAX(R) = MAX(MAX(R1), MAX(R2), MAX(Rn)（3）Min計算 M

35、IN(R) = MIN(MIN(R1), MIN(R2), MAX(Rn)(4) COUNT計算 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等的組合運算。聚集函數(shù)的分布式計算在分布式數(shù)據(jù)庫中是一個重要的特性，因為可以把函數(shù)F1（R1）， ,F1（Rn）的部分結(jié)果傳送給一公共站點，然后在這個公共站點處求表達式E的值，而不用象原先那樣把

36、所有的數(shù)據(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ī)范形式，在這種情況下，不可能使用準則6，因為不具備分布計算條件，為解決這個查詢，可對兩個段SUPPLY1和SUPPLY2進行獨立的子查詢操作：GBSUM（QUAN），COUNT（*）SLPNUM=P1SUPPLY1 （結(jié)果存于S1,C1中）。GBSUM（QUAN），COUNT（*）SLPNUM=P1SUPPLY2 （結(jié)果存于S2,C2中）。 令S1、C1分別為對SUPPLY1的GB操作的屬性：SUM（QUAN）和COUNT 中的值，同理，S2和C2分別為對SUPPLY2的GB操作的屬性：SUM（QUAN）和COUNT中的值，因而數(shù)量的平均值A(chǔ)VG（Q

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

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

40、譯時進行，尤其是對經(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的使用為了表示在算符樹上存在用于運行時化簡的測試，用一新的n元算符稱作剪枝（CUT）來替代結(jié)合算符，該新算符只對其幾個操作數(shù)執(zhí)行結(jié)合。每個公式在編譯時準備好而在運行時求值，若送回的結(jié)果為真，則其相應的操作數(shù)就包含在此結(jié)合操作中，如果計算結(jié)果為假值，則相應的操作數(shù)就從樹中消去。圖6.12（b）表示了這個參數(shù)性查詢的新算符樹，在該例中，應用準則2把選擇操作推至結(jié)合操作的下面，然后用CUT操作取代該結(jié)合操作，CUT操作用到的三個公式（對應結(jié)合操作