分布式數(shù)據(jù)庫查詢優(yōu)化處理

1、 分布式數(shù)據(jù)庫查詢優(yōu)化處理 摘要： 在進(jìn)行分布式數(shù)據(jù)庫應(yīng)用時(shí)，快速而準(zhǔn)確的得 到查詢結(jié)果一直是分布式數(shù)據(jù)庫得以應(yīng)用的關(guān)鍵問題。本文 闡述了分布式查詢優(yōu)化的一種策略和算法基于關(guān)系代 數(shù)等價(jià)變換的查詢優(yōu)化處理。 關(guān)鍵詞：分布式數(shù)據(jù)庫；查詢優(yōu)化；關(guān)系代數(shù)等價(jià)變換 中圖分類號(hào)： TP311.131 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1009-3044（2007）04-10916-02 1 基本原理 基于關(guān)系代數(shù)等價(jià)變換優(yōu)化算法的基本原理是：把查詢 問題轉(zhuǎn)變?yōu)殛P(guān)系代數(shù)表達(dá)式，分析得到查詢樹（語法樹） 進(jìn)行從全局到片段的變換得到基于片段上的查詢樹，然后利 用關(guān)系代數(shù)等價(jià)變換規(guī)則的優(yōu)化算法，盡可能先執(zhí)行選擇和

2、投影操作。這樣，一方面可以減少其后操作的操作量，另一 方面可以減少操作次數(shù)。對該查詢樹進(jìn)行優(yōu)化，從而達(dá)到查 詢優(yōu)化的目的。 關(guān)系代數(shù)等價(jià)變換規(guī)則的優(yōu)化算法是：利用關(guān)系代數(shù)等 價(jià)變換規(guī)則，把查詢樹中連接和合并操作盡可能上提（向樹 根方向移）。選擇和投影操作盡可能下移（向樹葉方向移） 到片段的定義處。 這就是說， 盡可能先執(zhí)行選擇和投影操作， 后執(zhí)行連接和合并操作。經(jīng)過選擇和投影操作不但可以減少 其后操作的操作量，而且還可以減少操作次數(shù)，這是因?yàn)椋?（1）如果是水平分片，把分片的限定語句（分片條件） 與選擇條件進(jìn)行比較，判別它們之間是否存在矛盾，去掉存 在矛盾的片段，如果只剩下一個(gè)水平分片的片段，

3、就可以去 掉一個(gè)“并”操作（至少可以減少一次并操作） ，達(dá)到優(yōu)化 查詢的目的。 （2）如果是垂直分片，把片段中的屬性集與投影操作 涉及的屬性集進(jìn)行比較，去掉無關(guān)的所有片段。如果只剩下 一個(gè)垂直分片的片段，就可以去掉一個(gè)“連接”操作（至少 可以減少一次連接操作） ，以達(dá)到優(yōu)化查詢的目的。 2 實(shí)現(xiàn)步驟和方法 （1）將一個(gè)查詢問題轉(zhuǎn)換成關(guān)系代數(shù)表達(dá)式。 （ 2）從關(guān)系代數(shù)表達(dá)式到查詢樹的變換：對一個(gè)關(guān)系 代數(shù)表達(dá)式進(jìn)行語法分析，可以得到一棵語法樹（查詢樹 ）。 即 樹的葉子：是已知關(guān)系 （或片段 ） 樹的結(jié)點(diǎn)：是關(guān)系操作符 樹的根：是查詢的最終結(jié)果。 將關(guān)系代數(shù)表達(dá)式轉(zhuǎn)換為查詢樹的方法是：查詢樹的

4、根 節(jié)點(diǎn)是最終的查詢結(jié)果，葉節(jié)點(diǎn)是查詢涉及的所有關(guān)系或片 段，中間節(jié)點(diǎn)是按代數(shù)表達(dá)式中的操作順序組成的一組關(guān)系 操作符。 (3) 從全局查詢到片段查詢的變換：在具有分片透明 性的系統(tǒng)中，這個(gè)變換的典型方法是：把基于全局關(guān)系的查 詢樹中的全局關(guān)系名，用其重構(gòu)該全局關(guān)系的各片段名替 換，變換成相應(yīng)在片段上的查詢樹。 (4) 利用關(guān)系代數(shù)等價(jià)變換規(guī)則的優(yōu)化算法，對片段 上的查詢樹進(jìn)行優(yōu)化處理，最后達(dá)到優(yōu)化查詢的目的。 3 基于關(guān)系代數(shù)等價(jià)變換的查詢優(yōu)化處理舉例 例 1 ：考慮教學(xué)數(shù)據(jù)庫中的全局關(guān)系S (s#,sname,age,sex) 和SC(s#,c#,grade)被水平分片，如圖1所示。 查詢

5、問題：“查找至少有一門功課的成績在 90 分以上的 男學(xué)生姓名” 。 這個(gè)查詢問題的 SQL 語句是： SELECT DISTINCT sname FROM S,SC WHERE S.s#=SC.s# AND sex= M AND grade90 它的關(guān)系代數(shù)表達(dá)式是： n sname( a sex= M Agrade90( a S.s#=SC.s#(SX SC) 乘積兩個(gè)操作合并成了一個(gè)自然連接操作了，轉(zhuǎn)換成相 應(yīng)片段上的查詢樹如圖 2(b)所示。現(xiàn)在把圖2(b)的查詢樹， 按等價(jià)變換準(zhǔn)則繼續(xù)變換成如圖3(c)和圖(d)。圖3(d)就是利 用關(guān)系代數(shù)等價(jià)變換規(guī)則，得到的最終優(yōu)化結(jié)果 水平分片

6、關(guān)系優(yōu)化的基本思想是：首先，盡可能把選擇 條件下移到分片的限定關(guān)系處，再把分片的限定關(guān)系與選擇 條件進(jìn)行比較，然后去掉它們之間存在的矛盾的相應(yīng)片段。 如果最后剩下一個(gè)水平片段，則重構(gòu)全局關(guān)系的操作中，就 可去掉“并”操作(至少可減少“并”操作的次數(shù)) 。 例 2 ：有全局關(guān)系 EMP(emp#,ename,salary,dept#,dname)， 如果被垂直分片，分成如下兩個(gè)片段： E1(emp#,dept#,dname)E2(emp#,ename,salary)?，F(xiàn)在要查詢： “雇員的姓名和工資情況” 。 這個(gè)查詢語句是： SELECT ename,salary FROM EMP 它的關(guān)系代

7、數(shù)表達(dá)式是：n ename,salary(EMP) 它的查詢樹如圖 4 中的左上圖所示，轉(zhuǎn)換成相應(yīng)的片段 上的查詢樹如圖 4 的右上圖所示。利用關(guān)系代數(shù)等價(jià)變換規(guī) 則，繼續(xù)變換成如圖 4 右下角和圖 4左下圖。圖 4 左下圖就 是利用關(guān)系代數(shù)等價(jià)變換規(guī)則，得到的最終優(yōu)化結(jié)果。 垂直分片關(guān)系優(yōu)化的基本思想是：把垂直分片所用到的 屬性集，與查詢條件中的投影操作所涉及的屬性集相比較， 去掉無關(guān)的垂直片段。如果只剩下一個(gè)垂直片段與查詢有關(guān) 時(shí)，去掉重構(gòu)全局關(guān)系的“連接”操作(至少可減少“連接” 操作的次數(shù) )。 4 結(jié)論 本文闡述了分布式查詢優(yōu)化的一種策略和算法- 基于 關(guān)系代數(shù)等價(jià)變換的查詢優(yōu)化處理。其基本原理是把查詢問 題轉(zhuǎn)變?yōu)殛P(guān)系代數(shù)表達(dá)式，分析得到查詢樹，進(jìn)行從全局到 片段的變換得到基于片段上的查詢樹，然后利用關(guān)系代數(shù)等 價(jià)變換規(guī)則的優(yōu)化算法，對該查詢樹進(jìn)行優(yōu)化，從而達(dá)到優(yōu) 化的目的。 參考文獻(xiàn)： 1薩師煊，王珊 . 數(shù)據(jù)庫系統(tǒng)概論 M. 高等教育出版社 . 2 邵佩英著 . 分布式數(shù)