加速SQL查詢的特征函數法
2024-07-21 02:34:30
供稿：網友
1. 查詢問題的挑戰
關系數據庫的查詢優化始終是一個重要而實際的問題，在那些以查詢為主的應用系統中，這幾乎是一個成敗攸關的問題。 但迄今為止，關于這個問題的討論中所提出的種種解決方案大致可分為兩大類，即利用硬件體系結構上的優勢及DBMS對并行處理的支持能力的一類方案及完全由應用設計來處理的方案。在本文作者以前所發表的文章中曾推薦過利用臨時中介表和表更新方法和快查詢處理的策略。在同一篇文章中，我們也曾提到有可能利用程序變換支持查詢優化的想法。所有這些建議和想法都屬于應用設計類的處理辦法，這些方法從某種意義上說有一定的一般性。但是，實際應用不斷地提出這樣或那樣難而“怪”的問題，這些問題極富挑戰性，用常規方法往往要以很昂貴的系統資源為代價才有望解決。
本文的目的是向讀者介紹一種由E.Birger等人首先提出的方法，即加速查詢處理的特征函數法。這個方法適用于大多數SQL的數據庫系統，假如這類系統還包括為數不多的幾個（最少為2個）內部函數，如abs（）及sign（）等，則這個方法就是直接可用的了。在E．Birger等人關于這個方法的研究報告中，曾給出很多極有難度而又很典型的查詢要求及其求解辦法，其中包括分技條件查詢、求行內量的邊界值、求直方圖、表轉置、求中位值、有序集的等段截分以及去邊界值問題等。這些問題的共性是，若用常規方法求解，系統無論在存儲開銷上還是處理開銷上都很大，而某些問題（如中值）的求解還相當難。本文將重述這些有趣的查詢問題及其解決方案。同時，我們還將討論“特征函數”作為一種使能技術的其他一些應用可能。
2．特征函數及其表示
特征函數是來自點集拓撲學的一個純數學概念，集合S的特征函數定義如下：
1 若x? S
d s(x)= （0）
0 若x? S
在這里，任意元素x是否屬于集合S，決定函數取不同的值。同時，這里也隱含了一個前提，即任何元素的集合S為范圍的歸屬是完全確定的，不存在元素x的歸屬不明的情況。顯而易見，特征函數是一種識別（或判定）裝置。正是這一特性，使它能夠成為數據庫查詢中選擇準則的一種等價（和更有效的）替換成分。因此，我們說特征函數是加速查詢的實施技術。
為了更直接地針對數據庫查詢問題，我們將特征函數的一般形式變換成如下的“數據庫版本”：
1 若a=ture
d (a)= （1）
0 若a=false
其中α是布爾表達式。當構成布爾表達式的算術表達式由表屬性及數據庫內部函數組成時，特征函數的選擇作用就很清楚了。
眾所周知，一般關系數據庫采用三值邏輯，即布爾表達式有可能取不確定值（“maybe”）。但為了簡化表達并因此突出特征函數在加速查詢中的本質作用，本文不考慮表屬性取不確定值的情形。另外，實現特征函數的數據庫（內部）函數（我們稱之為特征函數的“元函數”）會因系統和我們主觀選擇上的不同而不同。例如，Sybase的Transact SQL有兩個很有用的內部函數abs（）和sign（），可以直接作為特征函數的元函數。若A和B是任意兩個表屬性，則
d ［A！＝B］＝abs（sign（A－B）） （2）
為了使元函數有定義，表屬性必須是數值變量。因此，除有非凡聲明而外，本文將一概假定所有舉例和一般性討論中的表屬性為非空數值變量。等式（2）可從元函數的定義
abs（A）＝｜A｜ (3)
-1 若A<0
sign(A)= 0 若A=0 (4)
+1 若A>0
直接推導出來。一般地，經abs（）和sign（）而實現的特征函數是
d ［A＝B］＝1－abs（sign（A－B））
d ［A！＝B］＝abs（sign（A－B）） (5)
d ［A d ［A<＝B］＝sign(1－sign（A－B））
d ［A>B］＝1－sign（1－sign（A－B））
d ［A>＝B］＝sign(1＋sign（A－B））)
此外，設α和b 是任意布爾表達式，則
d ［NOTα］＝1－d ［α］
d ［αANDb ］＝d ［α］*d ［b ］ (6)
d ［αOR b ］＝sign（d ［α］＋d [b ]）
這里的A和B是表屬性，為非空數值量。等式（5）給出了6個最簡單的特征函數的元函數表示，但這并不是唯一的表示，還可能其他的表示方法。等式（6）是布爾算子的一般導出規則。對于由最簡型式的關系表達式構成的布爾表達式而言，等式（5）和（6）就構成其特征函數的實現規則。對于一般布爾表達式，等式（5）和（6）也是導出其特征函數的基礎。一般而言，由（5）和（6）可以推演出一個特征函數類，某些特征函數直接對應于SQL的選擇算子。例如，形如d ［A<＝X<＝B］的特征函數顯然與判定變量X是否在閉區間［A，B］中有關。利用（5）中的第4個特征函數及（6）中的第2個導出規則，
d ［A<＝X<＝B］
＝d ［(A<＝X)AND(X<＝B)］
＝d ［A<＝X］*d ［X<＝B］
＝sign(1－sign（A－X））*sign(1－sign(x－B）） (7)
顯而易見，等式（7）右端的區則算術表達式恰是選擇算子BETWEEN的一種等價表達。可以仿照上述方法得到其他三個與區間值有關的特征函數，即δ［A
3． 實例分析
為了說明以上引入的特征函數在加速查詢處理中的作用，讓我們具體分析一個實例。
試考察一個描述學生收入狀況的表 Students（name，status，parentincome，selfincome）（8）
其中name是主鍵，屬性status是一種標法量，當status取值1時，表明學生的收入完全來自父母，當status取值0時，表明學生的收入完全是自己勞動所得。針對這個表，假定我們想得到形如（name，income）的查詢結果，其中income或為學生自己的收入（當相應的status取0值時）或是來自父母的收入（當相應的status取值為1時）。
從表students的結構及查詢結果的語義分析，完成查詢的常規方法應當是
SELECT name，income=parentincome
FROM student
WHERE student=1 UNION (9)
SELECT name , income=selfincome
FROM student
WHERE student=0
這是一個很自然、很直白的查詢表達，但同時也是一個非常低效和非常耗費資源的表達。執行這個查詢的一般過程是：首先分別執行由算子UNION所連結的兩個子查詢，然后產生一個存放查詢中間結果的臨時表并將兩個子查詢的結果存入以這個臨時表中，第3步對臨時表作排序以便消除可能存在的重復值。至此，才得到最終的查詢結果。在這樣的處理中，除對整個表students要遍歷兩次而且要對中間結果作排序處理，處理上的煩雜和資源的消耗都是顯而易見的。查詢（9）唯一的優點，是它表達上的自然直白，誰都想得到。
對本例而言，還有更緊湊和更有效的查詢表達。例如，不難驗證以下的查詢
SEIECT name，income=parentincome*status+selfincome*(1-status)
FROM students； （10）
從語義上與查詢（9）完全等價。但查詢（10）不但消耗的存儲少而且處理上要有效得多，因為它只遍歷一次表students而且避免了可怕的排序操作。這個例子說明，對同一個查詢結果，不同的查詢表達在處理效率和資源消耗上可能會相去甚遠。因此，尋求有效的查詢表達方式，不但是必要的而且是可行的。
查詢表達（10）與像（9）那樣的常規表達不同之處在于，后者的查詢條件由兩個WHERE子句和算子UNION顯式給出，首者將查詢條件間接地隱藏在SELECT子句的算術表達式中。無論查詢表達采用什么形式，本例都屬于“條件檢索”的查詢類型。假如對照一下查詢要求和查詢表達（10），不難發現只所以能給出如此簡潔而正確的回簽，實在是有點“事有湊巧”。假如問題稍作些許改變（例如，屬性student取0和1以外的值，或者student取兩個以上的標法值，如此等等）問題就不會這么簡單了。因此，是否有一種很一般、很系統的解決方案，能讓我們對任何顯式表達在WHERE子句和相關算子中的選擇條件找到與之語義等價的算術表達式？答案是肯定的，這就是我們在下面要介紹的“特征函數法”。
4． 幾個典型查詢的特征函數解
正如上面所講，特征函數能夠實現我們的愿望，即將顯式的布爾條件轉化為標量表達式。因此，特征函數最直接和簡便的運用是針對條件檢索型的查詢，但它的作用并不僅僅止于此。為了較全面地了解特征函數在解決復雜查詢中的作用，本節將由易到難介紹和分析若干典型實例。對某些實例，我們還將說明它的應用領域。為了表達上更緊湊，所有出現在標量表達式中的特征函數都沒有用元函數展開。因此，假如要通過實際運行驗證這里的實例，必須先借助于（5）、（6）替換這里的特征函數。
4．1 條件檢索
由（10）給出的查詢可借助于特征函數識為
SELECT name，
income＝parentincome*d ［status＝1］＋selfincome*d ［status＝0］
FROM student （11）
假如檢索條件僅止于此，用（11）代替（10）并沒有什么本質上的意義。但實際問題中的檢索條件遠比此處復雜而多樣。例如，若將上例的要求稍作修改，即在保留status原有語義而外，加上按學生的年齡分段的要求，即以19歲和23歲為年齡的分界點，凡年齡不超過19歲而且依靠父母的學生為一組，凡年齡超過23歲者完全自食其力的學生為第二組，所有其他學生為第三組。在查詢結果中，收入（income）一欄有不同的含義：對前兩組學生，分別對應于他們父母的收入和學生自己的收入，對第三組學生，則對應于前兩組學生收入的算術平均值。在習慣于用常規方法處理查詢的人看來，這樣的條件就顯得大復雜了。實際上，這是很自然的要求，相對于原問題而言，要求的擴展是很稍微的。對照查詢表達式（11），不難驗證
SELECT name，
income＝parentincome*d ［atatus＝1］*d ［age<＝19］＋selfincome*sign (d ［status＝O］＋d ［age>23］）＋( (parentinceome＋selfinco me)/2.0*(1一d [status=1]）
