關(guān)系代數(shù)與SQL查詢優(yōu)化的研究

1 引言
隨著各個(gè)應(yīng)用領(lǐng)域信息化程度日益提高，數(shù)據(jù)庫(kù)中的數(shù)據(jù)量迅猛增長(zhǎng)，導(dǎo)致數(shù)據(jù)庫(kù)系統(tǒng)的查詢性能下降。但是一個(gè)數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng)的查詢性能直接影響到系統(tǒng)的推廣和應(yīng)用，因此數(shù)據(jù)庫(kù)系統(tǒng)性能和查詢優(yōu)化成為數(shù)據(jù)庫(kù)應(yīng)用領(lǐng)域備受關(guān)注的熱點(diǎn)問(wèn)題。
影響數(shù)據(jù)庫(kù)系統(tǒng)性能的因素很多，包括數(shù)據(jù)庫(kù)連接方式、應(yīng)用系統(tǒng)架構(gòu)、數(shù)據(jù)庫(kù)設(shè)計(jì)、管理等。其中最本質(zhì)又至關(guān)重要的是數(shù)據(jù)庫(kù)管理系統(tǒng)本身的查詢優(yōu)化技術(shù)。在數(shù)據(jù)庫(kù)系統(tǒng)開(kāi)發(fā)中，用戶業(yè)務(wù)邏輯必須轉(zhuǎn)換成數(shù)據(jù)庫(kù)查詢語(yǔ)言執(zhí)行，或?qū)?shù)據(jù)庫(kù)查詢語(yǔ)言嵌入在宿主語(yǔ)言程序中執(zhí)行。通過(guò)分析關(guān)系代數(shù)表達(dá)式的等價(jià)變換準(zhǔn)則及查詢代價(jià)，于給定的SQL查詢與關(guān)系代數(shù)表達(dá)式對(duì)應(yīng)關(guān)系，研究并分析基于關(guān)系代數(shù)等價(jià)變換規(guī)則的SQL查詢優(yōu)化。

2 關(guān)系代數(shù)表達(dá)式的等價(jià)變換規(guī)則
數(shù)據(jù)庫(kù)查詢是指從數(shù)據(jù)庫(kù)中提取數(shù)據(jù)的一系列活動(dòng)，包括：將高級(jí)數(shù)據(jù)庫(kù)語(yǔ)言表示的查詢語(yǔ)句翻譯為能在文件系統(tǒng)這一物理層次上實(shí)現(xiàn)的表達(dá)式，為優(yōu)化查詢進(jìn)行各種轉(zhuǎn)換，生成可供執(zhí)行的查詢計(jì)劃。對(duì)于數(shù)據(jù)庫(kù)的查詢要求可通過(guò)關(guān)系代數(shù)的運(yùn)算(操作)表達(dá)，而在SQL語(yǔ)言中通過(guò)SELECT語(yǔ)句實(shí)現(xiàn)查詢要求。南于關(guān)系代數(shù)運(yùn)算與SELECT語(yǔ)句描述之間存在著對(duì)應(yīng)關(guān)系，兇此可將數(shù)據(jù)庫(kù)查詢轉(zhuǎn)換成關(guān)系代數(shù)運(yùn)算，并利用關(guān)系代數(shù)等價(jià)變換規(guī)則生成優(yōu)化SOL的查詢計(jì)劃。
2．1 關(guān)系代數(shù)等價(jià)變換規(guī)則
設(shè)E、E1、E2和E3是關(guān)系代數(shù)表達(dá)式，A1,…，An和B1，…，Bm是屬性名，且A1,…，An是B1，…，Bm的子集，F(xiàn)、F1、F2和F3是條件表達(dá)式。則有常用的等價(jià)變換規(guī)則如表1所示。

2．2 查詢代價(jià)分析
從優(yōu)化的角度考慮，規(guī)則1與規(guī)則2等價(jià)變換前后的中間結(jié)果規(guī)模幾乎不發(fā)生變化，因此無(wú)需考慮優(yōu)化問(wèn)題。但規(guī)則3～規(guī)則10變換前后中間結(jié)果規(guī)模會(huì)發(fā)生變化，例如規(guī)則3若選取的條件F只與E1有關(guān)，那么先進(jìn)行E1的條件選取，再與E2笛卡爾積的時(shí)間代價(jià)將大大減少，下面通過(guò)例子進(jìn)行查詢代價(jià)分析。