馮凱平

0 前言

在關系數(shù)據(jù)庫中,最難處理和優(yōu)化的一個邏輯操作符是連接（JOIN），由于多個關系連接時可以有很多不同的順序,因此對應于查詢的執(zhí)行計劃的數(shù)目會隨著該查詢包含的關系個數(shù)呈指數(shù)級增長,當關系個數(shù)很多時,將導致搜索空間極度膨脹。[1]因此，當連接操作涉及多個關系時，需要考慮連接順序。人們設計了多種連接順序及方法，如遺傳算法、模擬退火算法、蟻群算法、左偏樹連接法等，其中左偏樹連接其代價是較低的且容易實現(xiàn)。

1 連接順序的選擇

當對兩個關系選擇連接順序時，一般來說將較小的關系先讀入主存，這樣可以較好地匹配來自另一個關系中的元組，當與另一個關系連接時，每次讀入一個塊，并將關系中的元組和已存入內存中的元組進行連接操作。

1.1 連接樹

做如下符號約定:πL為投影(L為投影屬性)、σC為選擇(c為選擇條件)、∞C為連接(c為連接條件)、×為關系的迪卡爾積、T(R)為關系R的元組數(shù)目、V(R，A)為關系R中屬性A不同取值的種類數(shù)目。

假設有以下四個數(shù)據(jù)表，學籍表:XJ（姓名，年齡，專業(yè)，特質，…）、試題庫表:ST（題號，適合專業(yè)，難度，…）、選課表:XK（課程，適用專業(yè)，姓名，…）、答題表:DT（考生姓名，題號，作答，用時，分值，…）。

實例1:查詢專業(yè)為烹飪工藝、選修了“食品化學”課程的學生姓名。

Select b.姓名

From XK as a inner join XJ as b a.姓名=b.姓名

Where b.專業(yè)=”烹飪工藝”and課程=”食品化學”（1）

式（1）的邏輯代數(shù)樹結構[2]。如圖1所示:

圖1 式(1)的代數(shù)樹

選擇XJ作為第一個變元（左變元），其依據(jù)是，一個學生可以選擇多門課程，如果規(guī)定每位學生必須選擇一門以上的課程，那么關系XJ的規(guī)模必定小于XK，而且XJ又進行了σ年齡＝20的選擇操作，致使XJ的規(guī)模進一步縮小。所以選擇XJ作為第一變元為最佳。

對于兩個關系的連接，其樹結構只有兩種情形，原則上可以任意取一個關系作為第一變元。當關系多于兩個時，如n個，樹的形狀數(shù)目T（n）按下式遞歸增長:[3][4]

四個關系中其中的三種樹結構，如圖2所示:

圖2 四個關系的連接方法

把每一個關系（葉結點）放在樹中不同的位置進行排序，共有4!=24種排序方法。當n=4時，T（4）=5，此時，總的樹形結構共5*4！=120種。

1.2 左偏連接樹

左偏樹是一棵二叉樹，圖2a）中，所有的葉結點都在右方，是左偏樹，根據(jù)各個變元排列順序的不同，共有24種樹形可供選擇。圖2c）則為右偏樹，圖2b）為緊密樹。左偏樹有以下兩項優(yōu)點:[3]

第一，查詢計劃的搜索可以用于較大的查詢；

第二，基于左偏樹查詢算法的查詢計劃比其他種類的樹結構的算法更加有效。

實際應用中，作為一個葉結點，中間還可以帶有其他操作符號，如圖1，左結點加入了選擇操作。

考慮圖2a）左偏樹。假設4個關系規(guī)模的大小順序是XJ、XK、ST、DT，以左變元開始建立樹關系，其意義在于以樹左方的變元優(yōu)先存儲在主存中。在進行XJ∞XK連接操作之前，首先將XJ存入內存，然后計算XJ∞XK并存儲。用B表示緩沖區(qū)塊，此時占用的內存緩沖區(qū)大小為B(XJ)+B(XJ∞XK)。由于XJ和XK是四個關系較小的，所以主存緩沖區(qū)應當能夠容納這些塊。下一步計算XJ∞XK∞ST并存入主存中，現(xiàn)在XJ已無保留的必要，所以緩沖區(qū)塊的大小為B(XJ∞XK)+B(XJ∞XK∞XT)。同理，當再加入DT的連接后不再保留XJ∞XK。緩沖區(qū)可以存儲連接的最終結果。

如果采用圖2c）右偏樹，首先將XJ存入主存緩沖區(qū)，用于“建立關系”，緊接著將XK∞ST∞DT載入內存進行XJ的“關系試探”，但是要計算XK∞ST∞DT需要將XK放入緩沖區(qū)以建立關系，然后計算出ST∞DT作為XK的試探關系。但是ST∞DT需要先將ST讀入緩沖區(qū)。現(xiàn)在內存中同時有XJ、XK、ST3個關系。此意味著如果要進行n個葉結點的右偏樹連接，就必須先將n-1個關系同時讀入內存中，增加了緩沖區(qū)數(shù)目。而左偏樹任何時候最多每次連接僅需開辟兩個緩沖區(qū)容納兩個關系即可。

如果一個連接在主存中只能獲得有限個緩沖區(qū)，當緩沖區(qū)過多時，將增加磁盤訪問次數(shù)、加重CPU及I/O時間開銷，最終使得所有算法的性能降低。

2 多屬性連接的代價估計

實例2:自適應型考試是一種新型的先進測試方式，它為學生選取的題目適應學生特質?，F(xiàn)需查詢所選擇的題目適合本人專業(yè)，且題目難度與自身特質相適應的學生。以題目難度與特質相差0.3為判定標準。將特質與難度都分成30個等級區(qū)間（實際應用中會出現(xiàn)缺值）。其SQL表達式為:

XJ和ST的T、V參數(shù)。根據(jù)其數(shù)據(jù)值，XJ與ST的連接概率做如下估計，如表1所示:

表1 XJ與ST的T、V參數(shù)表

假設XJ中有一元組x，ST中有元組s，將屬性“專業(yè)”和“適合專業(yè)”用Zy表示。如果V（XJ，Zy）≥V（ST，Zy），根據(jù)“值集包含”原理那么s的Zy必然出現(xiàn)在XJ中的諸Zy值之一。因此，x具有與s相同Zy的概率是1/V（XJ，Zy）。類似，如果V（XJ，Zy）

由此得知，在Zy上的相同概率是1/max（V（XJ，Zy），V（ST，Zy））。

同理，將學生“特質”和題目“難度”用Na表示，關于x和s在Na上取相同值的概率的方法應當是1/max（V（XJ，Na），V（ST，Na））。

由于Zy和Na值是獨立的，元組在Zy和Na上相同的概率是這些因子之積。因此，源自XJ和ST的迪卡爾積T（XJ）·T（ST）元組中，在Zy和Na上匹配的期望值是:[4][5][6]

式（3）的最終估計值為1000*2000/(max(15,20)max(18,27))=3703個元組。

3 多個關系連接的代價估計

3.1 多關系連接代價估計方法

假設有n個關系R1、R2、……Rn，進行以下連接操作:S=R1∞R2∞…∞Rn。

假設屬性A出現(xiàn)在k（1≤k≤n）個Ri中，在此k個關系中，值的集合的個數(shù)（即V（Ri，A）的各個值，其中i=1,2,…k）滿足v1≤v2≤…≤vk，次序從最小到最大。假設從每個關系中選一個元組，所選的元組在屬性A上相同的概率是多少？

考慮從具有最小數(shù)目的A值v1的關系中選取的元組t1。根據(jù)值集包含原理，這v1個值中的每一個值是在其他具有屬性A的關系中所發(fā)現(xiàn)的A值中?？紤]屬性A上有vi個值的關系。它所選的元組ti在屬性A上與ti相同的概率是1/vi。由于這個結論對于所有i=2,3…,k均為真，因此所有k個元組在A上相同的概率是積1/v2v3…vk。由此可得到以下規(guī)則:

從每個關系中元組數(shù)的積出發(fā)，然后，對于至少出現(xiàn)兩次的屬性A，除以除了V（R，A）中最小值之外的所有值。[3][4]

3.2 多關系連接代價估計實例分析

實例3:假定有3個關系的T、V統(tǒng)計值。考慮連接R（a,b,c）∞S（b,c,d）∞U（b,e），如表2所示:

表2 R、S與U的T、V參數(shù)表

為估計此連接大小，先將3個關系的T值做積操作，即1000×2000×5000。接著，查找那些出現(xiàn)多于兩次的屬性，它們是b出現(xiàn)3次，c兩次。將積除以V（R,b）、V（S,b）、V（U,b）中較大的兩個值，它們是50和200。最后，再除以V（R,c）、V（S,c）中較大的一個，即200。其估計結果是:

1000×2000×5000/（50×200×200）＝5000

實例4有以下3個關系:

將XJ、ST、DT3個關系中具有同類性質的屬性特質、難度、分值用符號Na表示；屬性姓名、考生姓名用Xm表示；作答、答案用Da表示；題號用Th表示。某次考試后3個關系的屬性值，如表3所示:

統(tǒng)計中等特質水平（16-25）的考生作答較大難度題目（25-30）的得分情況。

作如下假設:沒有特低特質（1-12）區(qū)間的考生、沒有特低難度（1-3）區(qū)間的試題。

按左偏樹進行連接操作:

Select a.姓名,c.分值

From Xs as a,Ti as b,Dt as c

Where a.姓名=c.考生姓名and b.題號=c.題號and b.答案=c.作答and(b.難度>="25"and b.難度<="30")and(a.特質>="16"and a.特質<="25")

統(tǒng)計它們之間連接（即S＝Xs ∞Ti∞Dt）之后的大小:

4 結束語

多連接查詢的優(yōu)化是一個復雜問題。本文通過應用實例分析，重點闡述了基于左偏樹平均值統(tǒng)計的數(shù)據(jù)查詢優(yōu)化過程中連接操作代價的估計方法。這種算法通過各個關系之間的大小順序作為選擇連接下一個關系的依據(jù)，使得估計過程簡單、明了。在關系數(shù)目不是太多時是一種比較好的選擇。誠然，當連接關系較多時，可以考慮其他估計方法，如遺傳統(tǒng)計法、群蟻統(tǒng)計法等。

[1]王瑩,徐鑫.GAAA算法在數(shù)據(jù)庫多連接查詢優(yōu)化中的研究應用[J].云南師范大學學報.2011,31(1),54-56.

[2]伍軍云,徐少平,林振榮等.一種新的關系數(shù)據(jù)庫查詢優(yōu)化方法[J]計算機與現(xiàn)代化.2006,7,33-35.

[3]Hector Garcia-Molina,Jeffrey D.Ullman,Jennifer Widom.Database System Implementation[M].Palo Alto,California:Stanford University,2001,3.

[4]郭聰莉,朱莉,李向.基于蟻群算法的多連接查詢優(yōu)化方法計[J].計算機工程.2009,35(10),173-175.

[5]彭建平,王變琴.再探多連接查詢優(yōu)化方法[J].中山大學學報.2001,40(2),27-30.

[6]李志偉.基于貪婪策略的分布式數(shù)據(jù)庫查詢優(yōu)化研究[j]計算機工程與設計.2010,31(17),3838-3840.