精華推薦：加速軟件測試SQL查詢的特征函數法

關鍵字：sql

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?。紹］＝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?。紹］＝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 ]）

原文轉自：http://www.anti-gravitydesign.com