等多個文件數(shù)據(jù)庫系統(tǒng)原理課件db chapter

數(shù)據(jù)庫系統(tǒng)原理主講：楊艷第三篇

實現(xiàn)篇HD-ITR2021/7/12實現(xiàn)篇HD-ITR2021/7/13第八章物理存儲結構第九章數(shù)據(jù)庫管理系統(tǒng)的數(shù)據(jù)字典第十章

關系代數(shù)操作的實現(xiàn)算法第十一章查詢優(yōu)化技術第十二章事務處理技術之一：并發(fā)控制技術第十三章事務處理技術之二：數(shù)據(jù)庫恢復技術第十四章其他事務處理技術第十章關系代數(shù)操作的實現(xiàn)算法HD-ITR2021/7/1410.1

查詢處理的過程10.2

選擇操作的實現(xiàn)算法10.3

笛卡兒積的實現(xiàn)算法10.4

連接操作的實現(xiàn)算法10.5

投影操作的實現(xiàn)算法10.6

集合的并、交、差的實現(xiàn)算法查詢：由高級查詢語言（如SQL）表示的對數(shù)據(jù)庫的一個或一組操作。查詢處理的步驟：掃描和語法分析查詢優(yōu)化查詢代碼生成查詢執(zhí)行10.1

查詢處理的過程HD-ITR2021/7/15查詢處理流程圖和各步驟所產(chǎn)生的結果10.1

查詢處理的過程HD-ITR2021/7/16關系數(shù)據(jù)庫系統(tǒng)的查詢處理包括兩個方面：實現(xiàn)各種關系代數(shù)操作的算法查詢優(yōu)化產(chǎn)生具有較高效率的查詢執(zhí)行計劃，不一定是最優(yōu)的執(zhí)行計劃。查詢優(yōu)化并不是所有的數(shù)據(jù)庫系統(tǒng)都能做到。過程性語言：查詢優(yōu)化的工作由用戶來做說明性語言：系統(tǒng)來做10.1

查詢處理的過程HD-ITR2021/7/17設每個關系存儲在一個文件中，每個文件僅存儲一個關系。參數(shù)說明：TR：關系Ｒ中的元組數(shù)。BR：關系Ｒ的磁盤塊數(shù)。M：主存緩沖區(qū)的塊數(shù)(每塊的容量等于一個磁盤塊的容量)。IR：關系Ｒ的每個元組的字節(jié)數(shù)。ｂ：每個磁盤塊的字節(jié)數(shù)。10.1

查詢處理的過程HD-ITR2021/7/18第十章關系代數(shù)操作的實現(xiàn)算法HD-ITR2021/7/1910.1

查詢處理的過程10.2

選擇操作的實現(xiàn)算法10.3

笛卡兒積的實現(xiàn)算法10.4

連接操作的實現(xiàn)算法10.5

投影操作的實現(xiàn)算法10.6

集合的并、交、差的實現(xiàn)算法使用SQL語言，選擇操作表示如下：SELECT

*FROM

RWHERE C1

AND

C2

OR

C3

...，選擇條件可以是簡單條件：僅包含關系R的一個屬性的條件也可以是復合條件：由簡單條件經(jīng)AND、OR、NOT等邏輯運算符連接而成的條件。10.2

選擇操作的實現(xiàn)算法HD-ITR2021/7/11010.2

選擇操作的實現(xiàn)算法HD-ITR2021/7/111具有簡單選擇條件的選擇操作實現(xiàn)算法1．線性搜索算法順序地讀取被操作關系的每個元組，測試該元組是否滿足選擇條件，如果滿足，則作為一個結果元組輸出。2．二元或插值搜索算法選擇條件是在某個屬性上的相等比較并且操作關系已經(jīng)按該屬性排序；如果操作關系具有N

個元組，二元搜索需要

O(log(N))時間完成選擇操作，插值搜索需要

O(log(log(N)))時間完成選擇操作。10.2

選擇操作的實現(xiàn)算法HD-ITR2021/7/112具有簡單選擇條件的選擇操作實現(xiàn)算法索引掃描算法主索引輔助索引聚集索引Hash文件B樹10.2

選擇操作的實現(xiàn)算法HD-ITR2021/7/113具有簡單選擇條件的選擇操作實現(xiàn)算法3．主索引或HASH搜索算法選擇條件是定義在主索引屬性或HASH屬性上的相等比較，可以使用主索引或HASH方法搜索操作關系。4．使用主索引查找多個滿足條件的元組選擇條件是定義在具有主索引屬性上的非相等比較，即>、≤、<、≥，可以使用主索引選擇滿足條件的所有元組。10.2

選擇操作的實現(xiàn)算法HD-ITR2021/7/114具有簡單選擇條件的選擇操作實現(xiàn)算法5．使用聚集索引查找多個滿足條件的元組選擇條件是定義在具有聚集索引的非鍵屬性上的相等比較，可以使用這個聚集索引讀取所有滿足條件的元組。6．B+樹索引搜索算法選擇條件定義在一個具有B+樹索引的屬性上，無論這個屬性是否鍵屬性，也無論選擇條件是否相等比較，都可以使用這個B+樹索引搜索查找所有滿足條件的元組。10.2

選擇操作的實現(xiàn)算法HD-ITR2021/7/115具有復合選擇條件的選擇操作實現(xiàn)算法稱由一組簡單條件經(jīng)邏輯運算符AND連接在一起的復合條件為合取條件。7．合取選擇算法如果合取條件中存在一個簡單條件Ｃ，Ｃ所涉及的屬性上定義有某種存取方法，而且這種存取方法適應于上述六個算法之一，則使用相應算法搜索操作關系，選擇滿足Ｃ的元組，并檢驗是否滿足其他條件，如果滿足，作為結果元組。8．使用復合索引的合取選擇算法如果合取條件是定義在一組屬性上的相等比較，而且存在一個由這組屬性構成的復合索引，則使用這個復合索引完成選擇操作。10.2

選擇操作的實現(xiàn)算法HD-ITR2021/7/116具有復合選擇條件的選擇操作實現(xiàn)算法稱由一組簡單條件經(jīng)邏輯運算符AND連接在一起的復合條件為合取條件。9．使用元組指針交集的合取選擇算法如果合取條件是定義在一組屬性上的相等比較，每個屬性上都定義有一個輔助索引，則首先使用每個索引形成滿足對應條件的元組指針集合；然后計算這些指針集合的交集；最后使用交集中的指針產(chǎn)生結果元組集合。這個方法也可以用于合取條件中只有部分屬性具有輔助索引的情況在這種情況下，首先使用指針交集讀取滿足部分簡單條件的元組，然后進一步地檢驗是否滿足其他條件。第十章關系代數(shù)操作的實現(xiàn)算法HD-ITR2021/7/11710.1

查詢處理的過程10.2

選擇操作的實現(xiàn)算法10.3

笛卡兒積的實現(xiàn)算法10.4

連接操作的實現(xiàn)算法10.5

投影操作的實現(xiàn)算法10.6

集合的并、交、差的實現(xiàn)算法10.3

笛卡兒積的實現(xiàn)算法HD-ITR2021/7/118參數(shù)說明：TR：關系Ｒ中的元組數(shù)。BR：關系Ｒ的磁盤塊數(shù)。M：主存緩沖區(qū)的塊數(shù)(每塊的容量等于一個磁盤塊的容量)。IR：關系Ｒ的每個元組的字節(jié)數(shù)。ｂ：每個磁盤塊的字節(jié)數(shù)。R×S的每個元組的字節(jié)數(shù)是

IR＋ISR×S的磁盤塊數(shù)是BR×S＝

TRTS

(IR＋IS)/ｂ10.3

笛卡兒積的實現(xiàn)算法HD-ITR2021/7/119簡單算法（嵌套循環(huán)算法）FOR

R中每個元組r

DOFOR

S中每個元組s

DO產(chǎn)生元組(rs)，存入結果關系；ENDFOR；ENDFOR算法的磁盤存取塊數(shù)：BR＋BR×BS＋BR×SR和S在算法中的位置可以調換把小關系放在外層循環(huán)可以節(jié)省時間。10.3

笛卡兒積的實現(xiàn)算法HD-ITR2021/7/120主存算法如果M≥BS＋BR，可以首先把R和S讀入主存，然后在主存中產(chǎn)生R×S。讀入R和S；FOR

主存中R的每個元組r

DOFOR

主存中S的每個元組s

DO產(chǎn)生元組(rs)，存入結果關系；ENDFOR;ENDFOR算法的磁盤存取塊數(shù)：BR＋BS＋BR×S10.3

笛卡兒積的實現(xiàn)算法半主存算法如果BR≥BS，BS＜M，可以首先把S讀入主存，并保留至少一塊主存作為R的緩沖區(qū)。設SB是存儲S的主存區(qū)，RB是R的緩沖區(qū)，半主存算法如下：讀入S到SB；WHILE R中仍有元組待處理

DO讀R的元組到RB；/*

每次讀的元組數(shù)不超過RB的容量

*/FOR

RB中每個R元組r

DOFOR

SB中每個S元組s

DO產(chǎn)生元組(rs)，存入結果關系；ENDFOR;ENDFOR;–算法的磁盤存取塊數(shù)：BR＋BS＋BR×SENDWHILEHD-ITR2021/7/1212021/7/1HD-ITR22ENDFOR;ENDFOR;ENDFOR;ENDFOR10.3

笛卡兒積的實現(xiàn)算法：–

算法的磁盤存取塊數(shù)

BR

(BS/(M－1))＋BS＋BR×S大關系算法如果M≤BR，M≤BS，則R和S都不能一次讀入主存。設BS≤BR，則可把關系S劃分為BS／(Ｍ－1)個子集合，每個子集合具有M－1塊。令SB是容量為M－1塊的S的主存緩沖區(qū)，RB是容量為1塊的R的主存緩沖區(qū)。大關系算法如下：FOR

i＝1

TO

BS/(M－1)

DO讀S的第i個子集合到SB；FOR

j＝1

TO

BR

DO讀R的第j塊到RB；FOR

RB中每個R元組r

DOFOR

SB中每個S元組s

DO產(chǎn)生元組(rs),存入結果關系；第十章關系代數(shù)操作的實現(xiàn)算法HD-ITR2021/7/12310.1

查詢處理的過程10.2

選擇操作的實現(xiàn)算法10.3

笛卡兒積的實現(xiàn)算法10.4

連接操作的實現(xiàn)算法10.5

投影操作的實現(xiàn)算法10.6

集合的并、交、差的實現(xiàn)算法使用SQL語言，關系R和S的連接操作表示為：SELECT R.*,

S.*FROM R,

SWHERE

R.AθS.B–其中，θ是算術比較符。這種連接操作簡稱為θ連接。10.4

連接操作的實現(xiàn)算法HD-ITR2021/7/124ENDFOR;ENDFOR;ENDFOR10.4

連接操作的實現(xiàn)算法HD-ITR2021/7/125：–

算法的磁盤存取塊數(shù)

BR

(BS/(Ｍ－１))＋BS＋Bq修改笛卡兒積的大關系算法來實現(xiàn)θ連接。設M≤BR，Ｍ≤BS，BS≤BR。把S劃分為BS/(M－1)個子集合，每個子集合具有M－1塊。令SB是容量為M－1塊的S的主存緩沖區(qū)，RB是容量為1塊的R的主存緩沖區(qū)。θ連接的大關系算法如下：FOR

i＝1

TO

BS/(M－1)

DO讀S的第i個子集合到SB；FOR

j＝1

TO

BR

DO讀R的第j塊到RB；FOR

RB中每個元組r

DOFOR

SB中每個S元組s

DOIF

r.Aθs.B THEN(rs)存入結果關系；

ENDFOR;10.4

連接操作的實現(xiàn)算法HD-ITR2021/7/126等值連接和自然連接是應用最多的連接操作。自然連接與等值連接無本質區(qū)別。下文主要討論自然連接。2021/7/1

HD-ITR27循環(huán)嵌套算法（Nest-LoopJoin）輸入：關系R(A1,...,Ai,...,An)，S(B1,...,Bj,...,Bm)，連接條件R.Ai＝S.Bj。輸出：R與S的連接T。方法：FOR

每個t∈R

DOFOR

每個s∈S

DOIF

t[Ai]＝s[Bj]THEN (ts)

寫入T；ENDIF;ENDFOR;ENDFOR10.4

連接操作的實現(xiàn)算法–算法的磁盤存取塊數(shù)：BR＋BRBS＋U10.4

連接操作的實現(xiàn)算法HD-ITR2021/7/128排序合并算法（Sort-Merge

Join）如果關系R和S的元組已經(jīng)在連接屬性R.Ai和S.Bj上物理地排序設R.Ai和S.Bj中至少有一個是鍵屬性按照排序順序掃描R和S；查找在R.Ai和S.Bj上具有相同值的R和S的元組，進行連接。磁盤存取塊數(shù)：BR＋BS＋U。如果R.Ai和S.Bj都不是鍵屬性上述算法做一點小的修改。如果關系R和S的元組都未排序使用下文的Sort-Merge連接算法。–用X(i)表示已排序關系X的第i個元組。排序合并算法（Sort-Merge

Join）輸入：關系R(A1,...,Ai,...,An)，S(B1,...,Bj,...,Bm)，連接條件R.Ai＝S.Bj。輸出：R與S的連接T。方法：按屬性R.Ai值排序R；按屬性S.Bj值排序S；掃描R和S一遍，形成T={R(k)S(m)|

R(k)[Ai]=S(m)[Bj]}。10.4

連接操作的實現(xiàn)算法HD-ITR2021/7/129–算法的磁盤存取塊數(shù)：O(BR

logM

BR

+

BS

logM

BS

+BR

+BS

+U)10.4

連接操作的實現(xiàn)算法HD-ITR2021/7/130Hash連接算法(Hash

Join)第一階段：掃描R和S，使用定義在連接屬性上的Hash函數(shù)把R和S的元組分別構造成Hash文件HR和HS。第二階段：對于HR和HS的每對對應Hash桶，考察其中R和S的元組在連接屬性上的值，產(chǎn)生R和S的連接結果。ENDFOR;FOR

L=1

TO

N

DO接HR和HS的第L個HASH桶，結果寫入Hash連接算法(Hash

Join)輸入：關系R(A1,...,Ai,...,An)，S(B1,...,Bj,...,Bm)，連接條件R.Ai＝S.Bj，HASH函數(shù)H(X),

值域為{1,2,…,N}。輸出：R與S的連接T。方法：FOR

每個t∈R

DOt寫入HR的第H(t[Ai])個HASH桶；

ENDFOR；FOR

每個s∈S

DOs寫入HS的第H(s[Bj])個HASH桶；10.4

連接操作的實現(xiàn)算法–算法的磁盤存取塊數(shù)：連BR

+BS

+N

COST(B1,B2)+U

T;ENDFORHD-ITR2021/7/13110.4

連接操作的實現(xiàn)算法ENDFORHD-ITR2021/7/132索引連接算法仍然考慮關系R(A1,...,Ai,...,An)和S(B1,...,Bj,...,Bm)的連接，R.Ai=S.Bj是連接條件。若S在屬性Bj上具有聚集索引，索引文件名為IS：FOR R的每一個數(shù)據(jù)塊BLOCK

DOFOR

BLOCK中的每個元組t

DO用t[Ai]搜索IS,找到所有與t[Ai]匹配的索引值對應的S元組指針，送到P中;FOR P中每個指針p所對應的S元組s

DO(ts)寫入連接結果T;ENDFOR;ENDFOR;2021/7/1HD-ITR3310.4

連接操作的實現(xiàn)算法索引連接算法設I是S.Bj的連接值域大小，S在連接值域上均勻分布,R.Ai的連接值域是S.Bj的連接值域的子集合對于R的每個元組，算法平均需要讀S的BS/I個數(shù)據(jù)塊，總的需要讀取S的TRBS/I個數(shù)據(jù)塊。如果不計索引文件IS的存取數(shù)據(jù)塊數(shù)，算法需要存取的數(shù)據(jù)塊數(shù)是：BR

+(TRBS)/I+U，其中U是連接結果T的數(shù)據(jù)塊數(shù)。2021/7/1HD-ITR34ENDFOR10.4

連接操作的實現(xiàn)算法索引連接算法仍然考慮關系R(A1,...,Ai,...,An)和S(B1,...,Bj,...,Bm)的連接，R.Ai=S.Bj是連接條件。若R和S都在連接屬性上具有聚集索引；設IXR和IXS分別是R和S在R.Ai和S.Bj上的索引文件；IXS中的元素數(shù)小于IXR中的元素數(shù)。搜索IXS形成連接屬性的連接值域Y以及Y中每個值所對應的S元組指針集合PS;FOR

Y中每個值b

DO用b搜索IXR,

找到所有與b匹配的R元組的指針送PR;FOR

PS中每個與b對應的S元組指針所指的S元組s

DOFOR

PR每個指針所指的R元組r

DO(rs)寫入連接結果T;ENDFOR;ENDFOR;10.4

連接操作的實現(xiàn)算法HD-ITR2021/7/135索引連接算法設I是S.Bj的連接值域的大?。籎是R.Ai的連接值域的大??；S.Bj的連接值域是R.Ai的連接值域的子集合；S和R在連接值域上均勻分布。最外層循環(huán)的次數(shù)是I；在每次循環(huán)中，R的平均存取塊數(shù)是O(BR/J)，S的平均存取塊數(shù)是O(BS/I)。于是，如果不計索引文件的存取數(shù)據(jù)塊數(shù)，算法需要存取的數(shù)據(jù)塊數(shù)至多是

O(I×(BR/J+BS/I)+U),其中，U是連接結果T的數(shù)據(jù)塊數(shù)。10.4

連接操作的實現(xiàn)算法HD-ITR2021/7/136連接操作結果的估計連接操作結果的大小U在分析連接操作算法

的復雜性和查詢優(yōu)化處理中具有重要的作用。估計連接操作結果的大小。第十章關系代數(shù)操作的實現(xiàn)算法HD-ITR2021/7/13710.1

查詢處理的過程10.2

選擇操作的實現(xiàn)算法10.3

笛卡兒積的實現(xiàn)算法10.4

連接操作的實現(xiàn)算法10.5

投影操作的實現(xiàn)算法10.6

集合的并、交、差的實現(xiàn)算法10.5

投影操作的實現(xiàn)算法HD-ITR2021/7/138設P

A1,...,Ak(R)是關系R上的投影操作。如果投影屬性表{A1,...,Ak}中包括R的鍵存取R的所有元組一次即可完成；操作的結果具有與R同樣多的元組，只是每個元組僅包括屬性A1,A2,…,Ak的值。如果投影屬性表中不包含R的鍵需要刪除操作結果中的重復元組可以利用排序算法來實現(xiàn)投影操作利用排序實現(xiàn)投影操作的算法輸入:具有n個元組的關系R。輸出: R的投影T=P

A1,...,

Ak

(R)。方法：FOR

R中每個元組r

DOr[A1,

...,

Ak]寫入TMP;ENDFOR;IF {A1

,

...,

Ak}中包含R的鍵屬性

THEN T

:=

TMP;

結束；ELSE

排序TMP;

i=1;

j=2;WHILE

(i≤n)

DO寫TMP(i)到T;WHILE

(TMP(i)=TMP(j))

DO

j=j+1;

ENDWHILE;i=j;

j=j+1;ENDWHILE;ENDIF10.5

投影操作的實現(xiàn)算法HD-ITR2021/7/139利用排序實現(xiàn)投影操作的算法設L是元組r[A1,...,Ak]的字節(jié)數(shù)；b是一個數(shù)據(jù)塊所包含的字節(jié)數(shù)。如果{A1,...,Ak}包含R的候選鍵算法需要存取的磁盤塊數(shù)是O(BR

+nL/b)如果{A1,...,Ak}不包含R的候選鍵算法需要存取的磁盤塊數(shù)至多為O(BR

+

nL/b

logM(nL/b)

+

nL/b)10.5

投影操作的實現(xiàn)算法HD-ITR2021/7/140第十章關系代數(shù)操作的實現(xiàn)算法HD-ITR2021/7/14110.1

查詢處理的過程10.2

選擇操作的實現(xiàn)算法10.3

笛卡兒積的實現(xiàn)算法10.4

連接操作的實現(xiàn)算法10.5

投影操作的實現(xiàn)算法10.6

集合的并、交、差的實現(xiàn)算法10.6

集合的并、交、差的實現(xiàn)算法HD-ITR2021/7/142實現(xiàn)集合的并、交、差操作要求操作關系具有相同的屬性集合，并且屬性的排列順序必須也相同。實現(xiàn)這些操作的常用算法首先利用排序算法在相同的鍵屬性上排序兩個操作關系；然后掃描這兩個排序后的關系，完成并、交或差操作。10.6

集合的并、交、差的實現(xiàn)算法并操作輸入:

關系R和S,

R具有n個元組，S具有m個元組，K是R和S的鍵。輸出:

T=R∪S。方法:按照鍵K值排序R和S;i

:=1; j

:=

1;WHILE

(i≤n)

AND

(j≤m)

DO(4)(5)(6)(7)IF

R(i)[K]>S(j)[K]

THEN

寫S(j)到T; j

:=

j+1;ELSE

IF

R(i)[K]<S(j)[K]

THEN

寫R(i)到T; i

:=i+1;ELSE

寫R(i)到T; i

:=

i+1; j

:=j+1;ENDIF;((8)

ENDIF;9)

ENDWHILE;IF

i≤IF

j≤n

THEN

FOR

k=i

TO

n DO

寫R(k)到T;

ENDIF;m

THEN

FOR

k=j

TO

m

DO

寫S(k)到T;

ENDIF。–算法的磁盤存