基于關系代數(shù)樹的查詢優(yōu)化方法實例分析

馮凱平，李曉良

（1.四川烹飪高等專科學校信息技術系 四川 成都 610072；2.中國科學院上海微系統(tǒng)與信息技術研究所 上海 200050）

基于網(wǎng)絡的自適應性測試是一種先進的考試方式，在考試過程中，系統(tǒng)對題庫的訪問頻率很高，當參試者較多時，對數(shù)據(jù)庫的訪問將更加頻繁，特別是隨著數(shù)據(jù)庫不斷增容，數(shù)據(jù)庫中的數(shù)據(jù)量迅猛增長，這將導致數(shù)據(jù)庫系統(tǒng)的性能下降，直接影響到系統(tǒng)的性能及應用。因此，數(shù)據(jù)庫查詢速率的高低成為決定自適應測試成功與否的重要因素之一。

基于關系代數(shù)樹的查詢優(yōu)化方法，其基本思想是將選擇、連接等操作的運算符在遵循關系代數(shù)等價變換規(guī)則的原則下，盡可能深地移到關系樹的底部[1]。對使用諸如SQL的某種語言書寫的查詢進行語法分析，將查詢語句轉(zhuǎn)換成按某種有用方式表示查詢語句結構的關系代數(shù)樹，把關系代數(shù)樹轉(zhuǎn)換成基于關系代數(shù)表達式的邏輯查詢計劃[2]。

1 關系代數(shù)等價變換規(guī)則

設R和S各表示一個關系、πL為投影（L為投影屬性）、σC為選擇 （c為選擇條件）、δ為消除重復、γL為聚集與分組（L為屬性）、∞C為連接（c為連接條件）、×為關系的積。

1.1 涉及選擇的定律

對涉及兩參數(shù)的選擇定律：

1.2 涉及投影的定律

1.3 有關連接和積的定律

2 查詢計劃的改進

將關系代數(shù)操作符進行組合，把一個操作符應用到其他的一個或多個操作符之上形成一個表達式樹。這棵樹的葉節(jié)點是關系的名字，內(nèi)部節(jié)點被標記為操作符，這個操作符應用到它的子女代表的關系上。通過各個操作符的上移或下移，實現(xiàn)查詢優(yōu)化[1-4]。

2.1 實例1

查詢答對難度級別為2的某道題目的所有考生。

假設有以下關系：

TitleTable（題目號，答案，難度，區(qū)分度，猜度，類別，……）

AnswerTable（考生姓名，題號，作答，bInit，……）

對于關系AnswerTable，每答一道題產(chǎn)生一個元組。

1）按關系的乘積查詢

select考生姓名

from TitleTable，AnswerTable

圖1 由式（1）對應的邏輯查詢計劃Fig.1 By type（1） the corresponding logic inquires the plan

圖2 對圖1的一個改進查詢計劃Fig.2 In figure 1 improvement inquires the plan

式（1）所對應的代數(shù)樹結構如圖1所示。在這個邏輯查詢計劃中，首先在最底層實行兩個數(shù)據(jù)表的積，通過使用乘積操作符來連接FROM列表中的關系。下一步做一個表示W(wǎng)HERE子句的選擇操作，最后一步是投影到SELECT子句的列表上。

為了實現(xiàn)相同的操作，并提高查詢效率，可以將選擇操作符σ盡量下移[1-3]，其依據(jù)來自于關系表達式等價變換規(guī)則①和④。如圖2所示為一個改進了的查詢計劃。在這個計劃中，由于提前對數(shù)據(jù)表TitleTable關于難度值進行了篩選，減少了關系積的規(guī)模[3]，使得查詢速率得以提高。

經(jīng)過在 HP6500服務器、WINDOWSE 2000 SERVER操作系統(tǒng)平臺、SQL SERVER環(huán)境下測試，查詢速率提高大約65-75%。事實上，由于查詢優(yōu)化器的作用，其效率的提高遠不止于此。

其對應的SQL語句如式（2）。

select考生姓名

from （select*from TitleTable where 難度=’2’）as a，Answer-Table as b

2）按關系的連接查詢

根據(jù)等價變換規(guī)則⑧，可將圖1的關系積轉(zhuǎn)換為圖3的關系連接，此關系代數(shù)樹實現(xiàn)相同的結果。在樹中，WHERE子句中的條件“題號=題目號”應用到兩個關系的乘積上，成為等值連接，形成將一個選擇和一個乘積結合成一個連接的操作。通常，連接比乘積產(chǎn)生的元組要少，因此，連接的查詢效率要高于乘積的查詢效率。對應的SQL語句如式（3）。

select考生姓名

from TitleTable as a inner join AnswerTable as b on b.題號=a.題目號

圖3 基于連接的查詢計劃Fig.3 Based on the inquires connection plan

經(jīng)測試，圖3的查詢速率比圖1高10%左右，這主要是關系TitleTable中關于題號沒有重復元組，否則圖3的查詢效率比圖1會更高。

根據(jù)等價變換規(guī)則⑤將圖3轉(zhuǎn)換為圖4，圖4在圖3的基礎上得到了較大改進。

圖4 對圖3的改進查詢計劃Fig.4 In figure 3 improvement inquires the plan

2.2 實例2

查找對題目猜度最高并且答對該題的考生

1）帶子查詢的查詢計劃

帶IN條件的代數(shù)樹結構比較特殊，如圖5所示，上方的σ操作符屬于一個兩參數(shù)選擇，該結點之下有一個左子結點，它表示要對其做選擇操作的關系AnswerTable；以及一個右結點，它表示作用到關系AnswerTable的每個元組上的條件表達式。

圖5和式（4）分別示出其關系代數(shù)樹和SQL表達式。

select考生姓名

from AnswerTable

圖5 應用IN條件Fig.5 Application condition IN

2）去除子查詢的查詢計劃

存在IN條件的代數(shù)表達式通常出現(xiàn)在子查詢中。

在實際操作中盡量避免子查詢[5]，否則，將子查詢應用到關系中的每個元組時都要計算一篇子查詢，這無疑是一筆巨大的開銷。

消除IN條件的基本方法如下：

假設有一個兩參數(shù)選擇（圖5上方的σ），其中第一個參數(shù)為 R，第二個參數(shù)是形如t IN S的＜Condition＞，t是R的（某些）屬性組成的一個元組，按如下方式對樹作變換：

a）用S的表達式樹替換＜Condition＞。

b）用一個單參數(shù)選擇σC替換兩參數(shù)選擇 （圖6上方的σ），其中C是元組t的每個分量與關系S中相應的屬性取等值的條件。

圖6 去除IN條件Fig.6 Remove IN conditions

c）給一個參數(shù)，它是R與S的積。

根據(jù)以上規(guī)則，對圖5進行相應變換，得到圖6邏輯查詢計劃。表達式如式（5）。

select考生姓名

from AnswerTable as a，（select題目號， 答案 from Title Table where猜度=”5”）as b

經(jīng)測試，按圖6建立的查詢計劃比圖5查詢速率提高大約70%。

為了進一步提高查詢速率，對圖6的乘積操作，可按圖1到圖3的變換規(guī)則變換成連接操作。

2.3 實例3

為了確定題目的有效度，需要查找作答了某道題所有考生的平均特質(zhì)水平與該試題難度級別接近的題目。

數(shù)據(jù)表如下：

AnswerTable（考生姓名，題號，作答，bInit，……）

StudentTable（姓名，地址，性別，特質(zhì)水平，……）

將平均特質(zhì)水平與難度參數(shù)值之差的絕對值小于0.3作為確認標準，其SQL表達式如式（5）。

在式（5）所對應的關系代數(shù)樹中，如圖7所示，把子查詢的WHERE子句分解成兩個，并使用該子句的一部分把關系的積轉(zhuǎn)換成等值連接。在這棵樹的結點上使用了別名s1、s2、d。代數(shù)表達式在代數(shù)樹的頂部結束，投影到所期望的屬性上并消除重復。

圖7 把式（5）轉(zhuǎn)換成邏輯查詢計劃Fig.7 Mules（5） convert logic inquires the plan

圖7是可以改進的，條件是：

1）δ在樹的頂部；

2）AnswerTable s1中的“考生姓名”不出現(xiàn)在投影 πs1.題號，s1.bInit中；

3）AnswerTable s1與它的連接對象（圖7中的右下部分）之間的連接能夠?qū)?AnswerTable s1中的“題號”、“bInit”屬性與AnswerTable s2中的屬性取等值。

由于這些條件均成立，則可以分別用 “s2.題號”、“s2.bInit”替換“s1.題號”、“s1.bInit”。 因此，圖 7 中的上方的一個連接符可以去除。改進后的邏輯查詢計劃如圖8所示。

圖8 圖7的簡化Fig.8 Figure 7 simplification

2.4 查詢優(yōu)化原則小結

1）選擇σ應盡可能下移到表達式樹中的下方。如果一個選擇條件是多個條件用and連接，則可以把該條件分解并分別將每個條件下移。

2）投影π也可被下移到樹中的下方，可加入新的投影。

3）消除重復δ有時可以不用，或者移到更方便的位置。

4）某些σ可以與其下方的積相結合以便把操作轉(zhuǎn)換成等值連接。

3 操作代價的估計

圖3對兩個關系TitleTable、AnswerTable分別進行投影、選擇和連接。投影的代價是可以精確估計的，而選擇代價和連接代價需要通過“統(tǒng)計量收集”過程來估計[1-6，8]。

3.1 投影大小的估計

對于關系 AnswerTable（考生姓名，題號，作答，bInit），并在以下簡稱為An。假設4個屬性的長度分別為 6、4、1、1個字節(jié)，設每個元組的頭需要12字節(jié)，如此，關系An的每一個元組占24字節(jié)。設塊為2 048字節(jié)長，其中塊頭占24字節(jié)。因此，每塊可存放168個元組。假設總的元組數(shù)為10 000，即T（An）=10 000，需要的塊數(shù)為 60，即 B（An）=60。

現(xiàn)在考慮投影S=π姓名（An），關系S的元組長度僅為6字節(jié)長，而T（S）仍為10 000。但是，現(xiàn)在卻可以在一個塊中放入 337 個元組，故 B（S）=30。

從而該投影縮減了關系約1倍，顯著減少了系統(tǒng)的I/O操作頻率，加快了DBMS掃描器掃描速率[3]。

3.2 連接大小的估計

對于關系TitleTable（題目號，答案），并在以下簡稱為Ti，假設共計8 000個元組。

用V（Ti，題目號）表示Ti中“題目號”屬性不同值的元組種類數(shù)目。由于Ti關于題目號無重復元組，所以V（Ti，題目號）=8 000。然而，對于An關于題號是有重復的，其重復度需要根據(jù)參試人數(shù)、試卷的題量、考生的特質(zhì)水平級別數(shù)來確定。

作以下假定：

1）根據(jù)全校可試機器臺數(shù)，假設一次參試人數(shù)為500人。

2）在自適應性測試中，每位參試者的題量是不等的，假設平均值為20道題。

3）每位參試者的特質(zhì)水平不同，簡單地分為5級。

一次考試系統(tǒng)總抽題量為T（An）=20×500=10 000。 考慮到每個考生特質(zhì)水平的不同，所答題目的級別也不同，同一題目在不同特質(zhì)水平考生中的分布系數(shù)大約為4/5=0.8，因此，每道題被抽取的概率大約為20×0.8/8 000=0.002，出現(xiàn)的次數(shù)為 0.002×10 000=20。 V（An， 題號）被確定為

最終對連接后元組數(shù)T（An∞Ti）的估計為

T（An∞Ti）=T（An）T（Ti）/Max（V（An， 題號），V（Ti， 題目號））[1]=10 000×8 000/Max（500，8 000）=10 000

根據(jù)題目元組大小、磁盤頁面大小、每頁元組行數(shù)，DBMS掃描器在連接An、Ti的過程中至少全表掃描磁盤大約800 萬次[3-9，10]。

3.3 選擇大小的估計

圖3所涉及的選擇是邏輯等值比較，其大小相對容易估算。

假設題庫中每道題目均僅有A、B、C、D 4種答案，并且4種答案是均勻分布的。因此，在發(fā)生了連接的關系An∞Ti中，邏輯表達式“作答=答案”就只有4種情形，按3/4的答對率計算，令x=4/3。另假設題目的難度級別有5種，令y=5。

已知 T （An∞Ti）=10 000。 對于 S=σ 作答=答案 and 難度=’2’（An∞Ti）， 通過下式求得經(jīng)選擇后新關系 S的元組數(shù)目：

分別將 x、y 代入（6）式，得 T（S）=10 000/x/y=1 500。

3.4 優(yōu)化后的代價估計

采用類似的方法對圖4進行大小估計。但是，由于優(yōu)化后，關系Ti與An的共同屬性值題目號違反了“值集的保持[1]”的假設，其估計值不太準確。可按以下方法大致估計：

在圖 4查詢計劃中，對 Ti先進行選擇 σ難度=’2’操作，假設難度值按均勻分布考慮，得到 T（Tiσ）=8 000/5=1 600。

此時再將其與關系An按題號連接，DBMS掃描器僅需掃描160萬次即可，較大幅度地實現(xiàn)了優(yōu)化。再向上進行σ作答=答案操作，仍能得到 T（S）=1 500。

4 結束語

SQL查詢優(yōu)化的實質(zhì)就是在結果正確的前提下，用優(yōu)化器可以識別的語句，盡量減少表掃描的I/O次數(shù)，進而減少表搜索。在數(shù)據(jù)庫的管理、開發(fā)和應用過程中，SQL查詢語句性能的優(yōu)劣直接影響整個信息系統(tǒng)的效率，特別是大型數(shù)據(jù)庫優(yōu)化過程更為重要，其效率高的查詢語句和效率低的查詢語句速度相差可以達到幾倍甚至上百倍。文中以應用實例為基礎，以關系代數(shù)樹結構為主線，結合數(shù)據(jù)庫理論對關系數(shù)據(jù)庫的查詢優(yōu)化機制，分析并實現(xiàn)對SQL語句的優(yōu)化，進而保證數(shù)據(jù)庫高效可靠地運行。

[1]Molina H G，Ullman J D，Widom J.Database system implementation[M].Palo Alto， California:Stanford University，2007.

[2]司訓練，徐文靜.代數(shù)樹架構下高價謂詞查詢優(yōu)化機制的算法設計[J].情報雜志，2007（1）：61-63.

SI Xun-lian，XU Wen-jing.Algorithm design of expensive predicate query optimization mechanism based on algebra tree framework[J].Intelligence magazine，2007（1）：61-63.

[3]王崢，王亞平.關系代數(shù)與SQL查詢優(yōu)化的研究[J].電子設計工程，2009，17（8）：110-112.

WANG Zheng，WANG Ya-ping.Research on relational algebra and SQL query optimization[J].Electronic Design Engineering，2009，17（8）：110-112.

[4]徐麗萍，金雄兵.一個并行查詢優(yōu)化器的設計與實現(xiàn)[J].計算機工程與科學.2007，29（2）：104-106.

XU Li-ping，JIN Xiong-bing.Design and realizat ion of a parallel query opt im izer[J].Computer Engineering&Sciencf，2007，29（2）：104-106.

[5]孫海東，張楊.一種分布式數(shù)據(jù)庫多屬性劃分查詢優(yōu)化算法[J].微計算機應用，2010，31（3）：47-49.

SUN Hai-dong，ZHANG Yang.A distributed database query optimization algorithm for multi-attribute classification[J].Microcomputer Applicati NS，2010，31（3）：47-49.

[6]曲衛(wèi)民，孫樂.XML數(shù)據(jù)查詢中值匹配查詢代價估計算法[J].軟件學報，2005，16（4）：561-569.

QU Wei-min，SUN Le.A result size estimation algorithm for value predication in XML query[J].Journal of Software，2005，16（4）：561-569.

[7]吳勝利，王能斌.面向?qū)ο髷?shù)據(jù)庫中查詢代價的估算[J].計算機研究與發(fā)展，1998，35（1）：69-73.

WU Sheng-li，WANG Neng-bin.Estiation of query cost in object-oriented database systems[J].Computer Research&Development，1998，35（1）：69-73.

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

WU Jun-yun，XU Shao-ping.A new query processing optimization algorithm based on statistic[J].Computer&Modernzation，2006（7）：33-35.

[9]佚名.數(shù)據(jù)庫優(yōu)化查詢計劃方法 [EB/OL].[2010-08-26].http://wenku.baidu.com/view.

[10]樊新華.關系數(shù)據(jù)庫的查詢優(yōu)化技術[J].計算機與數(shù)字工程，2009，37（12）：188-190.

FAN Xin-hua.Optimizati on technology for queries in relational database[J].Computer&Digital Engineering，2009，37（12）：188-190.

[11]劉云生，彭楚冀.一種實時數(shù)據(jù)庫查詢執(zhí)行方法的設計[J].計算機應用，2005，25（2）：279-282.

LIU Yun-sheng，PENG Chu-ji.Design of a query execution method for real-time database[J].Computer Applications，2005，25（2）：279-282.