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

馮凱平，李曉良

（1.四川烹飪高等?？茖W(xué)校信息技術(shù)系 四川 成都 610072；2.中國(guó)科學(xué)院上海微系統(tǒng)與信息技術(shù)研究所 上海 200050）

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

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

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

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

1.1 涉及選擇的定律

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

1.2 涉及投影的定律

1.3 有關(guān)連接和積的定律

2 查詢計(jì)劃的改進(jìn)

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

2.1 實(shí)例1

查詢答對(duì)難度級(jí)別為2的某道題目的所有考生。

假設(shè)有以下關(guān)系：

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

AnswerTable（考生姓名，題號(hào)，作答，bInit，……）

對(duì)于關(guān)系A(chǔ)nswerTable，每答一道題產(chǎn)生一個(gè)元組。

1）按關(guān)系的乘積查詢

select考生姓名

from TitleTable，AnswerTable

圖1 由式（1）對(duì)應(yīng)的邏輯查詢計(jì)劃Fig.1 By type（1） the corresponding logic inquires the plan

圖2 對(duì)圖1的一個(gè)改進(jìn)查詢計(jì)劃Fig.2 In figure 1 improvement inquires the plan

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

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

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

其對(duì)應(yīng)的SQL語句如式（2）。

select考生姓名

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

2）按關(guān)系的連接查詢

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

select考生姓名

from TitleTable as a inner join AnswerTable as b on b.題號(hào)=a.題目號(hào)

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

經(jīng)測(cè)試，圖3的查詢速率比圖1高10%左右，這主要是關(guān)系TitleTable中關(guān)于題號(hào)沒有重復(fù)元組，否則圖3的查詢效率比圖1會(huì)更高。

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

圖4 對(duì)圖3的改進(jìn)查詢計(jì)劃Fig.4 In figure 3 improvement inquires the plan

2.2 實(shí)例2

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

1）帶子查詢的查詢計(jì)劃

帶IN條件的代數(shù)樹結(jié)構(gòu)比較特殊，如圖5所示，上方的σ操作符屬于一個(gè)兩參數(shù)選擇，該結(jié)點(diǎn)之下有一個(gè)左子結(jié)點(diǎn)，它表示要對(duì)其做選擇操作的關(guān)系A(chǔ)nswerTable；以及一個(gè)右結(jié)點(diǎn)，它表示作用到關(guān)系A(chǔ)nswerTable的每個(gè)元組上的條件表達(dá)式。

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

select考生姓名

from AnswerTable

圖5 應(yīng)用IN條件Fig.5 Application condition IN

2）去除子查詢的查詢計(jì)劃

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

在實(shí)際操作中盡量避免子查詢[5]，否則，將子查詢應(yīng)用到關(guān)系中的每個(gè)元組時(shí)都要計(jì)算一篇子查詢，這無疑是一筆巨大的開銷。

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

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

a）用S的表達(dá)式樹替換＜Condition＞。

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

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

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

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

select考生姓名

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

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

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

2.3 實(shí)例3

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

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

AnswerTable（考生姓名，題號(hào)，作答，bInit，……）

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

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

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

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

圖7是可以改進(jìn)的，條件是：

1）δ在樹的頂部；

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

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

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

圖8 圖7的簡(jiǎn)化Fig.8 Figure 7 simplification

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

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

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

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

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

3 操作代價(jià)的估計(jì)

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

3.1 投影大小的估計(jì)

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

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

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

3.2 連接大小的估計(jì)

對(duì)于關(guān)系TitleTable（題目號(hào)，答案），并在以下簡(jiǎn)稱為Ti，假設(shè)共計(jì)8 000個(gè)元組。

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

作以下假定：

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

2）在自適應(yīng)性測(cè)試中，每位參試者的題量是不等的，假設(shè)平均值為20道題。

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

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

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

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

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

3.3 選擇大小的估計(jì)

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

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

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

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

3.4 優(yōu)化后的代價(jià)估計(jì)

采用類似的方法對(duì)圖4進(jìn)行大小估計(jì)。但是，由于優(yōu)化后，關(guān)系Ti與An的共同屬性值題目號(hào)違反了“值集的保持[1]”的假設(shè)，其估計(jì)值不太準(zhǔn)確?？砂匆韵路椒ù笾鹿烙?jì)：

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

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

4 結(jié)束語

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

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

[2]司訓(xùn)練，徐文靜.代數(shù)樹架構(gòu)下高價(jià)謂詞查詢優(yōu)化機(jī)制的算法設(shè)計(jì)[J].情報(bào)雜志，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]王崢，王亞平.關(guān)系代數(shù)與SQL查詢優(yōu)化的研究[J].電子設(shè)計(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]徐麗萍，金雄兵.一個(gè)并行查詢優(yōu)化器的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與科學(xué).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ù)庫(kù)多屬性劃分查詢優(yōu)化算法[J].微計(jì)算機(jī)應(yīng)用，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ù)查詢中值匹配查詢代價(jià)估計(jì)算法[J].軟件學(xué)報(bào)，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ù)庫(kù)中查詢代價(jià)的估算[J].計(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]伍軍云，徐少平.一種新的關(guān)系數(shù)據(jù)庫(kù)查詢優(yōu)化方法[J].計(jì)算機(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ù)庫(kù)優(yōu)化查詢計(jì)劃方法 [EB/OL].[2010-08-26].http://wenku.baidu.com/view.

[10]樊新華.關(guān)系數(shù)據(jù)庫(kù)的查詢優(yōu)化技術(shù)[J].計(jì)算機(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í)時(shí)數(shù)據(jù)庫(kù)查詢執(zhí)行方法的設(shè)計(jì)[J].計(jì)算機(jī)應(yīng)用，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.