廈門大學計算機科學系

1、廈門大學計算機科學系 2011年11月E-mail: 分布式數(shù)據(jù)庫技術(shù)專題三 分布式查詢處理 專題三 分布式查詢處理第4章 分布式查詢處理4.1 分布式查詢特點4.2 全局查詢轉(zhuǎn)換的基礎(chǔ)知識4.3 全局查詢到邏輯查詢的轉(zhuǎn)換4.4 邏輯查詢到物理查詢的轉(zhuǎn)換4.5 聯(lián)接操作4.1.1 分布式查詢處理的定義4.1.1.1 集中式數(shù)據(jù)庫查詢的基本原理4.1.1.2 分布式查詢處理4.1.1.3 三種查詢之間的聯(lián)系4.1.1.4 分布式查詢定義4.1.2 分布式查詢的代價因素綜述4.1 分布式查詢特點4.1.1 分布式查詢處理的定義4.1.1.1 集中式數(shù)據(jù)庫查詢的基本原理 在集中式數(shù)據(jù)庫環(huán)境中的查詢處

2、理，是將用戶查詢（由查詢語言表達）轉(zhuǎn)換成物理查詢處理，其中包括了物理優(yōu)化和邏輯優(yōu)化兩個層次。 物理優(yōu)化：對關(guān)系（數(shù)據(jù)庫）的基本操作符的運算在實現(xiàn)中的優(yōu)化（如索引、排序、聚集（聚簇）等） 邏輯優(yōu)化：在進行物理優(yōu)化前先應有一個合理的（最優(yōu)的）操作符次序或一些操作策略的選擇 4.1.1 分布式查詢處理的定義4.1.1.2 分布式查詢處理 分布式數(shù)據(jù)庫環(huán)境是由虛擬的全局數(shù)據(jù)庫和實際存在的各局部數(shù)據(jù)庫組成的。DDB的分布性，使虛擬的全局數(shù)據(jù)庫在抽象時還有邏輯數(shù)據(jù)庫（LgDB)和物理數(shù)據(jù)庫（PDB）的概念； DDB的四層模式結(jié)構(gòu)中的局部概念層是由物理數(shù)據(jù)庫映射到局部場地上的，即形成局部數(shù)據(jù)庫； 分布式查詢

3、處理包含了全局查詢處理和局部查詢處理兩個部分。但是，對使用 DDB 來說，用戶（應用）只看到 GDB，且也只在全局關(guān)系上執(zhí)行查詢。而用戶的這種查詢是通過查詢語言表示，并由系統(tǒng)將其轉(zhuǎn)換。因而在查詢執(zhí)行過程中，實際上最終要涉及到具體場地上的物理關(guān)系的查詢。 因此，分布式查詢對應全局層三種數(shù)據(jù)庫有三種查詢：用戶查詢、邏輯查詢和物理查詢。4.1.1 分布式查詢處理的定義集中式三層摸式結(jié)構(gòu)圖分布式四層摸式結(jié)構(gòu)圖4.1.1 分布式查詢處理的定義4.1.1.2 分布式查詢處理 用戶查詢（Qu）： 是DDB中在全局數(shù)據(jù)庫（GDB）上的查詢； 邏輯查詢（QL）： 是DDB中在邏輯數(shù)據(jù)庫（LgDB）上的查詢； 物

4、理查詢（Qp）： 是DDB中在物理數(shù)據(jù)庫（PDB）上的查詢。 4.1.1 分布式查詢處理的定義4.1.1.3 三種查詢之間的聯(lián)系 上述三種查詢之間有一定的聯(lián)系，這種聯(lián)系依賴于DDB的分片模式定義和分配模式定義，我們可用以下定理來描述： 定理 4.1 ：對于任一用戶查詢Qu，相應的邏輯查詢?yōu)镼L = Qu FS-1， 相應的物理查詢?yōu)镼P = Qu FS-1 AS1。證明：由3.1節(jié)分片模式定義，有GDB=FS-1 (LgDB)， 所以，有Qu(GDB)= Qu(FS-1 (LgDB)= Qu FS-1 (LgDB)； 同樣，由3.1節(jié)分配模式定義，有LgDB=AS-1 (PDB)； 所以有 G

5、DB=FS-1 (LgDB)=FS-1AS-1 (PDB)， 因而，有Qu(GDB)= Qu(FS-1AS-1 (PDB)= Qu.FS-1AS-1 (PDB) 。4.1.1 分布式查詢處理的定義4.1.1.4 分布式查詢定義 定理4.1討論的是全局層的查詢處理，其中對用戶查詢，在系統(tǒng)中實際存在了兩次轉(zhuǎn)換：全局查詢到邏輯查詢的轉(zhuǎn)換和邏輯查詢到物理查詢的轉(zhuǎn)換。如下圖所示： FS AS GDB LgDB PDB 轉(zhuǎn)換1 轉(zhuǎn)換2 Qu QL Qp4.1.1 分布式查詢處理的定義定義4.1：分布式數(shù)據(jù)庫系統(tǒng)的查詢處理Q是一算法：算法的輸入是用戶查詢Qu，算法的輸出是相應的物理查詢Qp; 算法的功能是將

6、用戶查詢按照每個全局關(guān)系的分布結(jié)構(gòu)轉(zhuǎn)換成一個最優(yōu)的物理查詢。 DDB查詢優(yōu)化主要討論以下問題：全局查詢處理的轉(zhuǎn)換、優(yōu)化由于分布性引起的數(shù)據(jù)在場地間移動時的數(shù)據(jù)副本選擇和查詢操作序的確定等策略 對于物理查詢的具體執(zhí)行，就相當于在一個集中式數(shù)據(jù)庫上的操作（即對局部數(shù)據(jù)庫的操作），其上的查詢處理屬于局部查詢處理。集中式數(shù)據(jù)庫所討論的查詢處理及優(yōu)化策略是本專題的技術(shù)基礎(chǔ)。 4.1.2 分布式查詢的代價因素綜述 分布式查詢的代價因素如下： IO代價（即估算輸入/輸出操作次數(shù)）CPU的使用情況傳輸代價（包括數(shù)據(jù)量的傳輸費用、傳輸?shù)难舆t時間，以及涉及傳輸數(shù)據(jù)的控制信息及控制次數(shù)）分布事務處理的管理策略（事務

7、可串行化、分布式并發(fā)控制、分布式恢復）分布查詢操作方法（如聯(lián)接操作、并操作、二元操作以及全局查詢和局部查詢的不同操作）對效率的影響4.2 全局查詢轉(zhuǎn)換的基礎(chǔ)知識4.2.1 查詢表達式的等價性4.2.2 查詢樹4.2.3 等價變換規(guī)則4.2.4 限定關(guān)系的簡化表示4.2.5 謂詞合取性4.2.6 擴充的關(guān)系代數(shù)規(guī)則4.2.1 查詢表達式的等價性關(guān)系數(shù)據(jù)模型有三種查詢語言：代數(shù)語言、元組演算語言、域演算語言，這三種語言是等價的用代數(shù)語言表達查詢處理最為方便SQL 語言是關(guān)系數(shù)據(jù)庫的標準語言，它是完備的，對用戶而言，提供非過程的查詢語言最為方便這里假設(shè) DDBMS 提供完全透明, 全局用戶可以用SQ

8、L語言操縱語句來表達全局查詢，SQL語句是對DDB進行查詢的外部表達式4.2.1 查詢表達式的等價性查詢要得到結(jié)果，必須對關(guān)系進行具體操作： 五種基本操作 并（）、差（）、迪卡爾積（）、選擇（ ）、投影（ ） 五種導出操作 交（）、商（）、聯(lián)接（ ）、自然聯(lián)接（）、半聯(lián)接（） ij為了便于查詢處理的轉(zhuǎn)換，將上面的十種關(guān)系操作數(shù)分為兩類：一元操作，用U表示二元操作，用B表示 屬于一元操作的只有和，而其余的操作都是二元操作 4.2.1 查詢表達式的等價性例：對全局關(guān)系 Emp,有如下SQL查詢表達式 Select ENAME,DNO From Emp Where DNO=15; （4-1） 其相應

9、的代數(shù)操作表達式為： ENAME，DNO（DNO=15 Emp） （4-2） 或 DNO=15（ENAME，DNO Emp） （4-3）本例表示了不同的操作順序仍可獲得相同的結(jié)果。這就是等價的概念。定義4.2：兩個查詢表達式 E1 和 E2 是等價的，如果其 查詢的結(jié)果是相同的，記為 E1 E2。4.2.2 查詢樹定義4.3： 查詢樹是一棵樹 T=(V,E)，其中： 1）V是節(jié)點集，每個非葉結(jié)點是關(guān)系操作符，葉節(jié)點是關(guān)系名（即查詢涉及的關(guān)系）； 2）E是邊集，二節(jié)點有邊（V1,V2），當且僅當 V2 是 V1 的操作分量。通常，人們用查詢樹表示查詢表達式的內(nèi)部結(jié)構(gòu)。例4.1：有查詢Q1：查詢北

10、部地區(qū)（AREA=North）所屬部門發(fā)出訂單的供應商號。這里涉及兩個全局關(guān)系Dept(D#,DNAME,MGTRSSN,AREA)和Sp(S#,P#,D#,QUAN)，SQL表達式為： Select S From Dept, Sp Where SpD=Dept.D And AREA=North; （復習多表連接內(nèi)容）其相應的代數(shù)表達式為： S#AREA=North（Sp Dept） D=D 其相應的查詢樹如下： s# AREA=Nouth D=D Sp Dept4.2.2 查詢樹顯然，邊為 E1（ ，Sp ） D=D時，則Sp是非葉節(jié)點 的分量。4.2.2 查詢樹例子：多表連接操作Stude

11、ntIDStudentNameStudentAge1張三252李四263王五274趙六285無名氏27表Student，存放學生基本信息 BorrowBookIDBorrowBookNameStudentIDBorrowBookPublish1馬克思主義政治經(jīng)濟學1電子工業(yè)出版社2毛澤東思想概論2高等教育出版社3鄧小平理論3人民郵電出版社4大學生思想道德修養(yǎng)4中國鐵道出版社5C語言程序設(shè)計5高等教育出版社表BorrowBook，存放學生所借的書 4.2.2 查詢樹例子：多表連接操作Select Student.StudentName,Student.StudentAge,BorrowBook.

12、BorrowBookName,BorrowBook.BorrowBookPublishFROM Student,BorrowBookWHERE Student.StudentID = BorrowBook.StudentID 運行的結(jié)果如下： StudentNameStudentAgeBorrowBookNameBorrowBookPublish張三25馬克思主義政治經(jīng)濟學電子工業(yè)出版社李四26毛澤東思想概論高等教育出版社王五27鄧小平理論人民郵電出版社趙六28大學生思想道德修養(yǎng)中國鐵道出版社用查詢樹表示更加復雜的查詢表達式： E=A(S（R）)A（TRS） A A S T R R S4.2.

13、2 查詢樹查詢樹可以理解為全局查詢樹，其葉節(jié)點是全局關(guān)系。根據(jù)等價定義，可用三種方式描述查詢：SQL表達式（查詢語句） 代數(shù)表達式 查詢樹注意:查詢樹不同于分解樹4.2.2 查詢樹圖 分解樹4.2.3 等價變換規(guī)則利用等價性定義，等價規(guī)則可以歸納為兩類（1）單個關(guān)系的代數(shù)操作的變換規(guī)則 RRR RR R R RRR R R R RRR R P（） RR R A（） 其中，關(guān)系R與空關(guān)系進行操作（聯(lián)接）表示了一種空操作，在查 詢轉(zhuǎn)換過程中是可以消去的操作（某種程度的優(yōu)化）例4.2：（）（） 4.2.3 等價變換規(guī)則（2）多個關(guān)系模式的操作的變換規(guī)則 設(shè)有多個關(guān)系，其關(guān)系模式分別為R， S，T，在

14、一定條件下有如下規(guī)則： 一元操作交換律： U1（ U2（R) U2（ U1（R) 二元操作結(jié)合律： (R)B(S)B(T) (R)B(S)B(T) 二元操作交換律： (R)B(S) (S)B(R) 一元操作冪等律： U(R) U1U2 (R) 一元操作對二元操作的分配律： U(R)B(S) (U(R)B(U(S) 一元操作的因式分解律： (U(R)B(U(S) U(R)B(S) 利用等價變換規(guī)則可以改變操作序?qū)崿F(xiàn)查詢優(yōu)化4.2.4 限定關(guān)系的簡化表示邏輯關(guān)系（邏輯片段）是對全局關(guān)系進行、的操作得到的從對關(guān)系的操作而言，邏輯關(guān)系是帶有一定限定條件的關(guān)系，我們可稱它為限定關(guān)系，它的限定條件是謂詞或

15、屬性集定理 4.1 指出用戶查詢必有相應的對邏輯關(guān)系和物理關(guān)系的查詢，其中對邏輯關(guān)系的查詢就是對這種限定關(guān)系的操作，也就是說，對關(guān)系的操作可以進一步地再作用到限定關(guān)系上給出限定關(guān)系的簡化表示為R:Q，其中：R是全局關(guān)系；Q是限定關(guān)系即邏輯關(guān)系應滿足的謂詞。R:Q讀作“全局關(guān)系R對應于限定條件Q的邏輯關(guān)系（即限定關(guān)系）”限定關(guān)系 R:Q被作為一個操作數(shù)，因此，它可以被關(guān)系代數(shù)所操作，這是一種擴充的操作4.2.5 謂詞合取性什么叫謂詞合取性 假設(shè)有全局關(guān)系模式 R，F(xiàn) 是一謂詞，Q 是關(guān)系所滿足的限定條件，也是一謂詞；在關(guān)系運算中由 Q 與 F 共同組成謂詞，即稱具有謂詞合取性質(zhì)。例如 QR F

16、、QR QS F 等。這種合取性本身可能引起一些矛盾： 如例3.1中，Supplier劃分為兩個邏輯關(guān)系就有兩個限定關(guān)系，其中Q1：CITY=London，Q2：CITY=Paris，就可能有表達式： CITY=Paris S1：CITY=London= 即，當限定關(guān)系的謂詞合取是具有矛盾的限定條件，實際上將是一種空操作。 這種謂詞合取可能為空的性質(zhì)對查詢轉(zhuǎn)換（執(zhí)行）時很有用，我們可以根據(jù)邏輯片段所具有的內(nèi)涵性質(zhì)，對其操作可能遺留下一些有矛盾的表達式為空的情況以簡化查詢的執(zhí)行。4.2.6 擴充的關(guān)系代數(shù)規(guī)則對RQ的操作是關(guān)系代數(shù)操作的一種擴充，其中使用限定關(guān)系作為操作數(shù)。將關(guān)系代數(shù)操作作用到限

17、定關(guān)系上有如下八條擴充規(guī)則 可以根據(jù)八個對限定關(guān)系的操作規(guī)則，討論擴充的關(guān)系代數(shù)表達式轉(zhuǎn)換的等價性 兩個限定關(guān)系是等價的，即當它們的兩個基礎(chǔ)關(guān)系是等價的，且其限定條件都表示了相同的真值函數(shù)（即當對同一元組用兩個限定條件時，能得到相同的真值）用于限定關(guān)系的命題： 命題4.l： 所有關(guān)系代數(shù)具有的等價轉(zhuǎn)換同樣適用于限定關(guān)系。 直觀地說，對一個全局關(guān)系進行選擇操作（謂詞為QR）得到的邏輯關(guān)系再做選擇操作（謂詞為F），相當于對全局關(guān)系做了一次選擇操作，但其謂詞為F AND QR，即謂詞的合取性; 4.2.6 擴充的關(guān)系代數(shù)規(guī)則RQRRFQR規(guī)則（1）規(guī)則（2）對限定關(guān)系投影出某些屬性（A），即使計算謂

18、詞條件的屬性不在A中，所得到的限定關(guān)系的謂詞不會改變，仍是QR。ARQR ARQR4.2.6 擴充的關(guān)系代數(shù)規(guī)則RQRSQS（R）（S）QRQS同樣有謂詞合取性。規(guī)則（3）規(guī)則（4）RQRSQS（R）（S）QR 兩個限定關(guān)系的差操作是不對稱的。 規(guī)則（5）RQRSQS （R）（S）QRQs 兩個限定關(guān)系的并操作，其謂詞具有合取性。 規(guī)則（6）RQRSQs (R)(S) QRQS 兩個限定關(guān)系的交操作是由差操作推導出的。 規(guī)則（7）R:QRS:QS(R)(S):QRQSF 兩個限定關(guān)系的聯(lián)接操作也是導出操作 。R:QRS:QS (R)(S):QRQSF 規(guī)則（8）FF4.3 全局查詢到邏輯查詢的

19、轉(zhuǎn)換討論“查詢轉(zhuǎn)換”，是討論分布式數(shù)據(jù)庫查詢處理的優(yōu)化。即在轉(zhuǎn)換過程中，利用等價變換規(guī)則，綜合并充分地考慮分布查詢的代價因素，使分布查詢處理逐步實現(xiàn)優(yōu)化。4.3.1 全局查詢到邏輯查詢的轉(zhuǎn)換步驟4.3.2 等價轉(zhuǎn)換準則4.3.2.1 全局查詢轉(zhuǎn)換成查詢樹4.3.2.2 生成優(yōu)化的邏輯查詢樹4.3.1 全局查詢到邏輯查詢的轉(zhuǎn)換步驟原則上可以按兩步實現(xiàn)分布式查詢的第一次轉(zhuǎn)換（全局查詢到邏輯查詢），每一步可遵守一些轉(zhuǎn)換規(guī)則，以實現(xiàn)部分優(yōu)化：第一步：將全局查詢表達式（SQL語法和代數(shù)操作表達式）轉(zhuǎn)換成全局查詢內(nèi)部結(jié)構(gòu)形式（查詢樹）在其轉(zhuǎn)換過程中需要利用等價變換規(guī)則及其所歸納出來的兩個轉(zhuǎn)換準則（C1，C

20、2）第二步：將全局查詢樹與模式分解樹合并轉(zhuǎn)換成部分優(yōu)化的邏輯關(guān)系查詢樹，或稱分解樹的化簡操作。其中包括：將全局查詢樹葉節(jié)點按分片模式定義的邏輯關(guān)系名，取代全局關(guān)系名（查詢樹與分解樹合并），并分別運用變換規(guī)則，化簡成部分優(yōu)化的邏輯查詢樹。其實現(xiàn)過程中，除了應用轉(zhuǎn)換準則C1，C2以外，還有C3C6準則。 4.3.2.1 全局查詢轉(zhuǎn)換成查詢樹例4.4：對例4.1的查詢樹(a)，利用代數(shù)操作等價變換規(guī)則可有如圖4.4所示。 圖4.4 全局查詢樹轉(zhuǎn)換范例4.3.2.1 全局查詢轉(zhuǎn)換成查詢樹分析：圖4.4（a）是下列代數(shù)表達式的查詢樹： S#AREA=North（Sp Dept） D=D 圖4.4（b）是

21、利用一元操作對二元操作的分配律規(guī)則：U(R)B(S)把一元操作向下移動，這時的代數(shù)操作表達式為： (U(R)B(U(S)，S#（Sp AREA=North（Dept） D=D圖4.4（c）是利用一元操作冪等律：U(R) U1 U2 (R) 對“操作數(shù)關(guān)系”分解為多個一元操作，以縮減“操作數(shù)關(guān)系”。即通過替換運算得： S#（S#，D# （Sp） S#AREA=North（Dept）D=D準則C1：縮減二元操作數(shù)關(guān)系，利用一元操作對二元操作的分配律，將一元操作向下移動。U(R)B(S) (U(R)B(U(S)準則C2：用一元操作冪等律對操作數(shù)關(guān)系產(chǎn)生適當?shù)囊辉僮骰蚍纸獬啥鄠€一元操作，以縮減操作數(shù)

22、關(guān)系。U(R)U1U2 (R)4.3.2.1 全局查詢轉(zhuǎn)換成查詢樹結(jié)論：查詢樹相當于對一個集中式數(shù)據(jù)庫的查詢，集中式數(shù)據(jù)庫的邏輯優(yōu)化技術(shù)可以作用于其上。具體說是要：對全局查詢樹中的一元操作盡量下移到葉節(jié)點；如果查詢樹中有二元操作，則應盡量先縮減二元操作的操作數(shù)。由此，可獲得等價轉(zhuǎn)換準則C1和C2。 4.3.2.2 生成優(yōu)化的邏輯查詢樹生成優(yōu)化的邏輯查詢樹，就是把查詢樹與全局模式的分解樹一起來考慮，需要用到限定關(guān)系等價變換性質(zhì)。這一步的操作比較復雜，基本上分為以下幾個子過程：4.3.2.2.1 分解樹的化簡處理過程4.3.2.2.2 分解樹與查詢樹的合并過程4.3.2.2.3 一元操作合并的過程

23、4.3.2.2.4 分布聯(lián)接的化簡過程 4.3.2.2.5 一個實例4.3.2.2.1 分解樹的化簡處理過程分解樹表明了全局關(guān)系由哪些邏輯關(guān)系組成，按什么方式組合 。要將全局查詢轉(zhuǎn)換成邏輯查詢，需要對分解樹進行處理。對于一個全局查詢而言，并非構(gòu)成全局關(guān)系的所有邏輯關(guān)系都將涉及到，往往只使用其中某一些，所以應根據(jù)查詢樹對分解樹進行處理。我們稱它為分解樹的化簡處理。 圖 分解樹結(jié)構(gòu)4.3.2.2.1 分解樹的化簡處理過程當全局查詢用查詢樹表示，經(jīng)過C1、C2 準則處理后，查詢要用到的邏輯關(guān)系的條件在查詢樹中就表現(xiàn)出來了。接著，可以根據(jù)這些條件消去一些與查詢無關(guān)的邏輯關(guān)系，即去掉一些操作為空的子樹。

24、 假設(shè)在查詢樹中，存在一棵關(guān)于全局關(guān)系R（U，True，T）的一元操作UnUn-1U1的子查詢樹。令F為Ul，Un中所有選擇操作謂詞的邏輯合取，即有 F= 。如果沒有選擇操作，則F=True，令A為U1,，Un中所有投影操作中的屬性和謂詞Pj中所涉及的屬性的并，即有： 令Qs=Un,U1(R)為關(guān)系R上的子查詢，下面給出分解樹化簡的定義：定義4.4：一個關(guān)系Ri（Ui，Qi，Si）對于子查詢Qs是無用的，當FQi=False，UiA=；否則是有用的。如果Ri是誘導分片所得的關(guān)系，當其主關(guān)系是無用的，它也是無用的。 4.3.2.2.1 分解樹的化簡處理過程例4.5 設(shè)有關(guān)系R0上的子查詢Qs=

25、其查詢子樹如圖4.7（a）所示，R0的分解樹見圖3.6，有 F=P1P2，A=A1A2A（P1）A（P2）。 (R0)，假設(shè)有FQ1=Flase，AU221=,則化簡后的分解樹如圖4.7（b）所示。 圖4.7 分解樹化簡4.3.2.2.1 分解樹的化簡處理過程圖3.6 獨立分片操作后的分解樹結(jié)構(gòu)4.3.2.2.1 分解樹的化簡處理過程根據(jù)上述論述，可從中歸結(jié)兩個化簡分解樹時有用的準則C3，C4：準則 C3：在全局查詢轉(zhuǎn)換成邏輯查詢的過程中，可以消去謂詞合取具有矛盾的子樹，即可消去選擇操作結(jié)果為空的子查詢樹。準則C4：在全局關(guān)系轉(zhuǎn)換成邏輯關(guān)系查詢過程中，也可以消去聯(lián)接操作結(jié)果為空的子樹。 4.3

26、.2.2.2 分解樹與查詢樹的合并過程在分解樹簡化處理后應該與查詢樹合并。這是兩種性質(zhì)不同的樹，但由于分解樹是由全局關(guān)系經(jīng)過分片操作形成的，即一組代數(shù)操作。查詢樹是對全局關(guān)系的查詢操作，也是一組代數(shù)操作。所以，我們可以用以下算法實現(xiàn)轉(zhuǎn)化。算法4.2：簡化的分解樹轉(zhuǎn)化為邏輯查詢樹。 輸入：已經(jīng)化簡后的分解樹。 輸出：從全局查詢轉(zhuǎn)換為邏輯查詢樹。方法：從根節(jié)點開始：(1) 如果節(jié)點上操作Oj=H或DH，則將其轉(zhuǎn)換為U（一元）操作節(jié)點； (2) 如果節(jié)點上的操作Oj=V，則將其轉(zhuǎn)換為聯(lián)接操作節(jié)點，聯(lián)接屬性是k；(3) 如果節(jié)點操作Oj=AO，則不必轉(zhuǎn)換；(4) 直至將所有節(jié)點處理完畢，最后輸出（獲得

27、）對邏輯片段的查詢樹。(5) 當然，當?shù)玫搅诉壿嬈?關(guān)系)的查詢樹后，還應按C1、C2準則反復變換，使得一元操作下移，二元操作的操作數(shù)盡量縮減。4.3.2.2.3 一元操作的合并過程一元操作的合并 在得到邏輯查詢樹后可能還有一些性質(zhì)，如在邏輯關(guān)系與二元操作之間或在二元操作之上存在若干一元操作。這時，就應按集中式數(shù)據(jù)庫邏輯優(yōu)化中的某些技術(shù)，使對同一邏輯關(guān)系的多個選擇、投影，應合并成一個選擇操作后接一個投影操作，且盡量使查詢樹上相連的一元操作最多只有2個。 4.3.2.2.4 分布聯(lián)接的化簡過程所謂分布聯(lián)接是指具有兩個以上（含兩個）全局關(guān)系的聯(lián)接（特別是它們不在同一場地上）。例如：在查詢樹中，如

28、果有兩個全局關(guān)系R，S聯(lián)接時，對R，S的所有元組都應進行比較；當這兩個全局關(guān)系的邏輯關(guān)系不在同一場地上，就須經(jīng)通訊形成分布聯(lián)接。圖4.8中，節(jié)點表示全局關(guān)系的邏輯關(guān)系（分片后），邊表示兩節(jié)點間聯(lián)接不為空。 圖4.8（a）是R，S的全聯(lián)接圖，即R的所有邏輯關(guān)系（R1，Rn）與S的所有邏輯關(guān)系（s1，Sn）進行完全分布聯(lián)接。對于DDB來講，這種聯(lián)接的代價是極大的。所以，在設(shè)計DDB時，對于有兩個聯(lián)接操作的關(guān)系（常常體現(xiàn)在實體間的關(guān)聯(lián)性質(zhì)）應盡量使其劃分合理。 圖4.8 分布聯(lián)接圖4.3.2.2.4 分布聯(lián)接的化簡過程對于完全聯(lián)接的化簡法有兩種：一種是部分分布聯(lián)接圖如圖4.8（b），其中部分節(jié)點間沒

29、有聯(lián)通，使完全聯(lián)接圖形成兩個或兩個以上子圖。另一種是簡化為簡單分布聯(lián)接圖如圖4.8（C），每對節(jié)點間只有一條邊。 圖4.8 分布聯(lián)接圖4.3.2.2.4 分布聯(lián)接的化簡過程 DDB中分片操作支持的誘導操作實際上是這種簡單分布聯(lián)接，R與S的邏輯關(guān)系只存在一對一的聯(lián)接，這就可以先做局部聯(lián)接，再完成分布聯(lián)接，其通訊開銷一定會降低。所謂先做局部聯(lián)接，就是先在邏輯關(guān)系之間完成聯(lián)接，然后再合并。 例4.6 設(shè)有圖4.9（a）所示的查詢樹，S1，S2是按R1，R2誘導分片操作所得到的邏輯關(guān)系，該查詢樹可以依等價變換規(guī)則轉(zhuǎn)換成圖4.9（b）所示。圖4.9（c）表示簡單分布聯(lián)接的查詢樹。 圖4.9 簡單分布聯(lián)接

30、內(nèi)容回顧（3.2.2.4 誘導分片）4.3.2.2.4 分布聯(lián)接的化簡過程從例4.6我們可以看到：對于圖4.9（c）的查詢樹表示了先做聯(lián)接操作再做并操作，有利于進一步優(yōu)化查詢樹，其中使用了一些等價變化規(guī)則。所以可歸納出分布聯(lián)接的轉(zhuǎn)換準則C5。準則C5：在全局查詢中具有分布聯(lián)接時，可將聯(lián)接下屬的并操作上推。 附： 二元操作結(jié)合律： (R)B(S)B(T) (R)B(S)B(T) 二元操作交換律： (R)B(S) (S)B(R)4.3.2.2.5 一個實例例子：至此，我們可以將例4.4的全局查詢轉(zhuǎn)換再根據(jù)上述準則進行優(yōu)化。假設(shè)全局關(guān)系Dept按部門號水平分片，其謂詞為： Q1：D110 Q2：D1

31、120 Q3：D2130且D=110在“North”地區(qū)。同時有約定；North地區(qū)的零件由London供應者供應。圖4.10是利用上列準則對圖 4.4的進一步轉(zhuǎn)換。 圖4.4 全局查詢樹轉(zhuǎn)換范例4.3.2.2.5 一個實例圖4.10是例4.l的全局查詢到邏輯查詢的最后查詢樹，其中經(jīng)過了從C1C5準則。 準則C1：縮減二元操作數(shù)關(guān)系，利用一元操作對二元操作的分配律，將一元操作向下移動。準則C2：用一元操作冪等律對操作數(shù)關(guān)系產(chǎn)生適當?shù)囊辉僮骰蚍纸獬啥鄠€一元操作，以縮減操作數(shù)關(guān)系。準則 C3：在全局查詢轉(zhuǎn)換成邏輯查詢的過程中，可以消去謂詞合取具有矛盾的子樹，即可消去選擇操作結(jié)果為空的子查詢樹。準

32、則C4：在全局關(guān)系轉(zhuǎn)換成邏輯關(guān)系查詢過程中，也可以消去聯(lián)接操作結(jié)果為空的子樹。準則C5：在全局查詢中具有分布聯(lián)接時，可將聯(lián)接下屬的并操作上推。4.4 邏輯查詢到物理查詢的轉(zhuǎn)換 邏輯轉(zhuǎn)換是把注意力集中于如何將一元操作盡量合并，先選擇后投影提取公共因子、消去無用子表達式（子樹）、減少二元操作數(shù)等方面，最后獲得簡化了的查詢樹和操作表達式。 那么，物理查詢轉(zhuǎn)換的內(nèi)容是什么呢？轉(zhuǎn)換的策略是什么呢？轉(zhuǎn)換的方法是什么呢？本節(jié)討論以下內(nèi)容：4.4.1 物理轉(zhuǎn)換中的基本內(nèi)容和方法4.4.2 物理轉(zhuǎn)換的策略與方法分析4.4.1 物理轉(zhuǎn)換中的基本內(nèi)容和方法一、什么是物理查詢轉(zhuǎn)換？ 所謂從邏輯查詢到物理查詢轉(zhuǎn)換，是指

33、將邏輯查詢轉(zhuǎn)換得到的簡化了的查詢樹，轉(zhuǎn)換成具體的每個場地上的局部操作命令和數(shù)據(jù)傳輸命令的過程。也就是說，全局查詢須兩次轉(zhuǎn)換后才形成一個具體的分布執(zhí)行計劃（DEP），然后才是交付給各個局部場地去執(zhí)行。在實際執(zhí)行過程中也同樣存在查詢處理的優(yōu)化，這就是前面提到過的分布式查詢處理中的局部層優(yōu)化。 4.4.1 物理轉(zhuǎn)換中的基本內(nèi)容和方法二、物理轉(zhuǎn)換的基本內(nèi)容和策略綜述 物理查詢轉(zhuǎn)換的過程，將涉及到物理副本和查詢的處理場地，即執(zhí)行環(huán)境。特別對于二元操作數(shù)不在同一場地時或者有多個副本可選擇的情況時，其“執(zhí)行環(huán)境”的概念更為重要。所以，物理轉(zhuǎn)換時一般注意以下因素：操作副本選擇操作執(zhí)行次序的選擇操作方法的選擇通

34、訊代價評估數(shù)據(jù)量4.4.2 物理轉(zhuǎn)換的策略與方法分析4.4.2.1 選擇操作副本的原則和策略4.4.2.2 操作執(zhí)行次序的選擇4.4.2.3 操作方法的選擇4.4.2.4 通訊代價的計算4.4.2.5 操作場地選擇 4.4.2.1 選擇操作副本的原則和策略操作副本的選擇是選定邏輯關(guān)系相對應的物理關(guān)系有多個副本時的具體化。原則上，對不同查詢有不同的具體選擇。各個物理關(guān)系的副本其使用情況、路徑代價和使用要求不完全一樣，若按隨機選定顯然不合理，應該遵守一定的協(xié)定，選擇一個理想的（合理的）副本。副本的使用狀態(tài)可分為可用和不可用。不可用指的是可能副本所在場地出現(xiàn)故障或到該場地的通訊有了故障；可用則又可能

35、處于繁忙或輕松狀態(tài)，這主要是指對副本可用時等候查詢的多少。 為此，可以給出副本選擇的一般原則： 本場地物理關(guān)系優(yōu)先。如果查詢始發(fā)場地上有邏輯關(guān)系的一個相應的物理關(guān)系，就應盡量的選擇該物理關(guān)系同場地上有二元操作，則應盡量選擇同一場地上的相應物理關(guān)系完成二元操作，以減少數(shù)據(jù)傳送在查詢等候中數(shù)據(jù)最小的物理關(guān)系應被優(yōu)先選中代價最小的應優(yōu)先選中4.4.2.2 操作執(zhí)行次序的選擇在全局查詢到邏輯查詢轉(zhuǎn)換時產(chǎn)生的查詢樹已經(jīng)部分地蘊含了部分操作次序，如執(zhí)行時從葉到根向上執(zhí)行。然而，這并沒有全部地給出最好的執(zhí)行次序。一方面，從葉子到根向上執(zhí)行未必會產(chǎn)生最好效果；另一方面，對查詢樹上有二元操作如并操作的聯(lián)接操作時

36、，其執(zhí)行次序還有許多方面可以“優(yōu)化”。 另外，為了對數(shù)據(jù)庫存取進行定量分析，需要定義數(shù)據(jù)庫的統(tǒng)計信息，以確定數(shù)據(jù)量的大小。即利用一種統(tǒng)計方法使查詢執(zhí)行前后對物理關(guān)系尺寸的變化能有所估計，給出一個滿意的執(zhí)行次序。一種行之有效的方法是計算物理關(guān)系的靜態(tài)特征，估算出對物理關(guān)系操作后的變化，從而決定中間關(guān)系的特性。 4.4.2.3 操作方法的選擇關(guān)于操作方法的選擇，更多地取決于對局部數(shù)據(jù)庫的存取方式在物理轉(zhuǎn)換時應盡量注意到對同一次數(shù)據(jù)庫存取中的一些代數(shù)操作是否能組合在一起完成盡量避免多次內(nèi)/外存調(diào)用，這與局部層優(yōu)化有很大關(guān)系一般來說，在物理轉(zhuǎn)換時，對同一場地上的數(shù)據(jù)庫存取時要注意對同一物理關(guān)系的全部操

37、作序列統(tǒng)一考慮，對于如何完成相應的數(shù)據(jù)庫的存取，可以由局部層去考慮 4.4.2.4 通訊代價的計算 這里介紹分布式數(shù)據(jù)庫最特殊的代價因素：場地間信息的傳輸費用的估算。 在傳輸過程中一般有兩種影響：費用（cost）和延遲（delay）。 一次傳輸?shù)膫鬏斮M用（TC）和傳輸延遲（TD）可以用函數(shù)法表示，它們與數(shù)據(jù)量的大小成線性關(guān)系： TC（X）C0+XC1 （4-9a）TD（X）D0+XD1 （4-9b） 其中，C0，C1，D0，D1對均是與系統(tǒng)有關(guān)的常數(shù)。C0相當于場地間傳輸數(shù)據(jù)的初始（啟動一次）所需的固定費；C1是網(wǎng)絡傳輸數(shù)據(jù)的統(tǒng)一費用；D0是兩場地建立一次連接所需的固定時間；D1是網(wǎng)絡傳輸數(shù)據(jù)

38、統(tǒng)一的單位傳輸速率。 4.4.2.5 操作場地選擇 場地選擇包含在邏輯關(guān)系轉(zhuǎn)換為物理關(guān)系的過程中，選擇了物理關(guān)系，邏輯關(guān)系就有了確定的場地。 但是還需考慮一系列問題，比如，查詢結(jié)果場地是否就是查詢始發(fā)場地呢？中間的每個操作在何處完成？完成后送何處？ 場地確定也包含有優(yōu)化的策略。根據(jù)系統(tǒng)設(shè)計的總目標和相應的優(yōu)化策略，有具體的場地選定的算法。4.5 聯(lián)接操作4.5.1 聯(lián)接操作重要性4.5.2 聯(lián)接操作4.5.3 半聯(lián)接操作原理和不對稱性4.5.4 半聯(lián)接操作的縮減作用4.5.5 半聯(lián)接程序的作用4.5.6 半聯(lián)接程序的具體過程4.5.1 聯(lián)接操作重要性關(guān)系數(shù)據(jù)庫由許多關(guān)系組成，關(guān)系與關(guān)系之間的聯(lián)

39、系主要通過聯(lián)接操作表現(xiàn)出來，因而在二元操作中，聯(lián)接操作遠比其它操作用得多。討論聯(lián)接，其實包括了“選擇投影聯(lián)接”的綜合問題，即二元操作和一元操作的綜合優(yōu)化問題。分布式查詢處理的聯(lián)接操作，更是影響分布式查詢效率的最關(guān)鍵因素。在DDB中，聯(lián)接操作的大量數(shù)據(jù)會引起場地間的傳輸，它直接影響整個系統(tǒng)性能。當前對聯(lián)接操作的優(yōu)化有兩種趨向：一種是采用半聯(lián)接技術(shù)來減少聯(lián)接操作的操作數(shù)，以降低通訊費用；另一種是直接進行聯(lián)接操作的代價計算4.5.2 聯(lián)接操作聯(lián)接操作是從兩個關(guān)系的笛卡爾積中選取屬性間滿足一定條件的元組。記作： 其中A和B分別為R和S上可比的屬性組。 自然聯(lián)接（Natural join）是一種特殊的等

40、值聯(lián)接，它要求兩個關(guān)系中進行比較的分量必須是相同的屬性組，并且要在結(jié)果中把重復的屬性去掉。即若R和S具有相同的屬性組B，則自然連接可記作：（實例）等值連接（equi-join），為“”的連接運算稱為等值連接。它是從關(guān)系R與S的笛卡爾積中選取A、B屬性值相等的那些元組。即等值連接為：（實例） （回顧）自然聯(lián)接圖 自然聯(lián)接實例自然聯(lián)接的結(jié)果是在 R 和 S 中的在它們的公共屬性名字上相等的所有元組的組合。例如下面是表格“雇員”和“部門”和它們的自然聯(lián)接:（回顧）等值聯(lián)接圖 -聯(lián)接實例-聯(lián)接和等值聯(lián)接如果我們要組合來自兩個關(guān)系的元組，而組合條件不是簡單的共享屬性上的相等，則有一種更一般形式的連接算子才方便，這就是 -聯(lián)接(或 theta-聯(lián)接)。 是在集合 , 中的二元關(guān)系。的結(jié)果由在 R 和 S 中滿足關(guān)系 的元素的所有組合構(gòu)成。只有 S 和 R 的表頭是不相交的，