1 引言
隨著各個應用領域信息化程度日益提高，數據庫中的數據量迅猛增長，導致數據庫系統的查詢性能下降。但是一個數據庫應用系統的查詢性能直接影響到系統的推廣和應用，因此數據庫系統性能和查詢優(yōu)化成為數據庫應用領域備受關注的熱點問題。
影響數據庫系統性能的因素很多，包括數據庫連接方式、應用系統架構、數據庫設計、管理等。其中最本質又至關重要的是數據庫管理系統本身的查詢優(yōu)化技術。在數據庫系統開發(fā)中，用戶業(yè)務邏輯必須轉換成數據庫查詢語言執(zhí)行，或將數據庫查詢語言嵌入在宿主語言程序中執(zhí)行。通過分析關系代數表達式的等價變換準則及查詢代價，于給定的SQL查詢與關系代數表達式對應關系，研究并分析基于關系代數等價變換規(guī)則的SQL查詢優(yōu)化。
2 關系代數表達式的等價變換規(guī)則
數據庫查詢是指從數據庫中提取數據的一系列活動，包括：將高級數據庫語言表示的查詢語句翻譯為能在文件系統這一物理層次上實現的表達式，為優(yōu)化查詢進行各種轉換，生成可供執(zhí)行的查詢計劃。對于數據庫的查詢要求可通過關系代數的運算(操作)表達，而在SQL語言中通過SELECT語句實現查詢要求。南于關系代數運算與SELECT語句描述之間存在著對應關系，兇此可將數據庫查詢轉換成關系代數運算，并利用關系代數等價變換規(guī)則生成優(yōu)化SOL的查詢計劃。
2．1 關系代數等價變換規(guī)則
設E、E1、E2和E3是關系代數表達式，A1,…，An和B1，…，Bm是屬性名，且A1,…，An是B1，…，Bm的子集，F、F1、F2和F3是條件表達式。則有常用的等價變換規(guī)則如表1所示。
2．2 查詢代價分析
從優(yōu)化的角度考慮，規(guī)則1與規(guī)則2等價變換前后的中間結果規(guī)模幾乎不發(fā)生變化，因此無需考慮優(yōu)化問題。但規(guī)則3～規(guī)則10變換前后中間結果規(guī)模會發(fā)生變化，例如規(guī)則3若選取的條件F只與E1有關，那么先進行E1的條件選取，再與E2笛卡爾積的時間代價將大大減少，下面通過例子進行查詢代價分析。
假設關系E1有106個元組，關系E2有103個元組。那么執(zhí)行E1xE2，則有109個元組。若條件F只與E1有關，且滿足F的選擇性為0．1％，則意味著只有103個元組滿足條件，而另外的1O9-103個元組都不滿足條件。因此將σF(E1xE2)等價變換為σF(E1)xE2后，其中間結果σF (E1)的規(guī)模僅103元組。若1個物理塊可允許存放100個E1元組，10個E2元組，而主存中可允許存放10塊E1元組，1塊E2元組，以下估計分析等價變換前后的查詢代價。
2．2．1 等價變換前查詢代價估計分析
等價變換前查詢代價是指采用σF(E1)xE2方式所需花費的查詢代價。下面分別從E1×E2和σF兩個方面分析：
(1)E1×E2代價估計E1xE2代價估計主要是從磁盤讀塊和中間結果寫盤的時間考慮，而對主存中數據的處理時間忽略不計。
E1xE2讀塊總數=E1的塊數+E2的塊數×讀E2的遍數=104+100x103=110 000塊。若每秒可以讀50塊，讀塊時間為2 200 s(約0．6 h)。連接后的元組數為109，若每塊可存放10個元組，那么寫中間結果需要的時間是108/50=2x1 06 s。故E1xE2花費的時間為2×106 s+2．2×103s≈556．2 h。
(2)σF代價估計 σF運算時需將E1xE2的中間結果依次讀入內存進行運算，兇此需要108／50=2×106s；滿足條件的103個元組，共需100個塊寫回磁盤，需2 s。故σF花費的時間為2x106s+2．2x103s≈556．2 h。
作者：王崢,王亞平 西安外事學院 來源：國外電子元器件
