數(shù)據(jù)庫原理與程序設(shè)計(jì)第10章-關(guān)系代數(shù)操作的實(shí)現(xiàn)算法

1、第10章 關(guān)系代數(shù)操作的實(shí)現(xiàn)算法生物醫(yī)學(xué)軟件工程本章概要查詢處理過程選擇操作的實(shí)現(xiàn)算法笛卡爾積的實(shí)現(xiàn)算法連接操作的實(shí)現(xiàn)算法投影操作的實(shí)現(xiàn)算法集合交、并、差的實(shí)現(xiàn)算法10.1 查詢處理的過程查詢是由高級查詢語言(如, SQL)表示的是對數(shù)據(jù)庫的一個或一組操作。查詢處理要經(jīng)過掃描和語法分析、查詢優(yōu)化、查詢代碼生成、查詢執(zhí)行四個步驟來實(shí)現(xiàn)。查詢掃描和語法檢查查詢的內(nèi)部表示查詢優(yōu)化查詢執(zhí)行計(jì)劃查詢代碼生成查詢執(zhí)行查詢結(jié)果執(zhí)行查詢計(jì)劃的代碼10.2 選擇操作的實(shí)現(xiàn)算法線性搜索按原始順序掃描關(guān)系，取出滿足條件的元組。二分搜索主索引或HASH搜索用主索引查找多個元組使用聚集索引按等值比較條件尋找多個元組使用

2、B樹索引搜索 合取選擇算法復(fù)合索引算法：指針交集算法：先按一個簡單條件用前述方法選擇，然后檢查是否滿足其它條件。若合取條件都是等值比較，可考慮使用有關(guān)屬性上的復(fù)合索引。若合取條件是等值比較，可用各索引域的輔助索引得到元組指針集合，然后取這些集合的交集。10.3 笛卡爾積的實(shí)現(xiàn)算法算法定義為對結(jié)果關(guān)系result初始化;for rR do for sS do (rs) 寫入result endforendfor返回result.RS輸出RS10.4 連接的實(shí)現(xiàn)算法設(shè)A、B分別是R、S的屬性子集。RA=BS的算法是：對result初始化；for rR do for sS do if rA=sB t

3、hen (rs) 寫入result endif endforEndfor返回result.RSRS10.5 投影操作的實(shí)現(xiàn)算法 若投影域含鍵，僅需對R存取一次，否則結(jié)果可能有重復(fù)元組。下邊是刪除重復(fù)的排序算法：輸入：具有n個元組的關(guān)系R輸出：R的投影T= A1,A2,AK (R)員工號 工資001 70002 80003 80004 80009 92006 92007 96008 98005 98已排序例子算法：for R中每個元組 do RA1,AK寫入TMP endfor ;if A1,AK含鍵 then begin T:=TMP;return;endElse /去重復(fù):僅取重復(fù)組的首項(xiàng)

4、begin 排序TMP； i=1；j=2; while i=n do 寫TMP(i)到T； while TMP(j)=TMP(i) do j=j+1; endwhile； i=j；j=j+1; endwhile end；10.6 集合的并、交、差的實(shí)現(xiàn)算法并操作RS：假設(shè)關(guān)系R和S分別有n和m個元組，R的序號為i，S的序號為j.關(guān)于鍵k對兩關(guān)系的元組作升序排列； i=1；j=1；while in and jm do 比較Ri(k)與Sj(k) 較小一方稱為小方 若不等， 輸出小方元組；小方序號加1； 若相等， 輸出元組Ri ； 兩序號都加1；endwhile；若in ， 則輸出R的剩余元組；若

5、jm ，則輸出S的剩余元組.算法簡例：設(shè)R與S都僅有一個屬性(是鍵)。排序后分別是： R：1,4,5,6 (n=4) S：2,4 (m=2)執(zhí)行過程是：i=j=1;比較1和2,輸出1,i改為2;比較4和2,輸出2,j改為2;比較4和4,輸出4, i=j=3;循環(huán)停止;輸出R剩余元組5,6.算法停止.操作結(jié)果：1,2,4,5,6.交操作RS算法如下關(guān)于鍵k對兩關(guān)系作升序排列；i=1；j=1；while in and jm do 比較Ri(k)與Sj(k) 較小一方稱為小方 若不等， 小方序號加1； 若相等， 輸出元組Ri；兩序號都加1；endwhile.算法簡例：設(shè)R與S都僅有一個屬性(是鍵)。排序后分別是： R：1,4,5,6 (n=4) S：2,4 (m=2)執(zhí)行過程是：i=j=1;比較1和2，i改為2;比較4和2，j改為2;比較4和4，i=j=3;循環(huán)停止.算法停止.操作結(jié)果：4. 差操作R-S算法如下算法簡例：設(shè)R與S都僅有一個屬性(是鍵)。排序后分別是： R：1,4,5,6 (n=4) S：2,4 (m=2)執(zhí)行過程是：i=j=1;比較1和2,輸出1,i改為2;比較4和2, j改為2;比較4和4, i=j=3；循環(huán)停止;輸出R剩余元組5,6.算法停止.操作結(jié)果：1,5,6.關(guān)于鍵k對兩關(guān)系作升序排列； i=1；j=1；while in and j