函數

    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 若A0

　　直接推導出來。一般地，經abs（）和sign（）而實作的特征函數是

　　d ［A＝B］＝1－abs（sign（A－B））

　　d ［A！＝B］＝abs（sign（A－B）） (5)

　　d ［AB］＝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 ［A23］）＋( (parentinceome＋selfinco me)/2.0*(1一d [status=1]）