关系系统及查询优化课件

關係系統及查詢優化1.關係系統關係模型的三個組成部分：關係數據結構、關係操作集合、完整性約束關係系統

——

支持關係模型的系統

定義

一個系統可以定義為關係系統，當且僅當它支持：1）關係資料庫，即從用戶觀點看，資料庫由二維表構成且只有表結構；2）支持選擇、投影和（自然）連接運算，且對它們不必要求定義任何物理存取路徑。關係系統的分類關係模型的三個部分：

S—

關係數據結構、M—

關係操作、I—

完整性約束按支持模型的程度分類關係系統：√×√√√√√√×××2.關係系統的查詢優化必要性

——

關係系統為了達到較好的性能（即用戶可接受的性能）必須進行查詢優化。可能性

——

關係系統從關係運算式中分析查詢語義，自動選取存取路徑，為執行查詢優化提供了可能性。關係系統的查詢優化既是系統實現的關鍵技術又是關係系統的優點所在。查詢優化的總目標：

選擇有效的策略，求得給定的關係運算式的值。為什麼要進行查詢優化？查詢時間T1:105T2:205T3:10(秒)實例：查找選修C2課程的學生姓名。

SELECTS.SNFROMS，SCWHERES.Sno=SC.SnoANDSC.Cno=‘C2’

幾個等價的關係代數運算式：

T1=ΠSN（σS.Sno=SC.Sno∧SC.Cno=‘C2’（SXSC））

T2=ΠSN（σSC.Cno=‘C2’（SSC））

T3=Π

SN（SσSC.Cno=‘C2’（SC））查詢優化的一般策略一般策略——可提高查詢效率，並非最優策略

1.選擇運算儘量先做；

2.

連接前對關係先做預處理；

——預處理方法：檔排序、在連接屬性上建立索引

3.

投影運算和選擇運算同時進行；

4.

投影與其前後的雙目運算同時進行；

5.

把某些選擇同它前面的笛卡爾積合併為連接運算；

——即用自然連接替代笛卡爾積

6.

存儲公共子運算式。——

權衡考慮3.關係代數運算式的等價變換規則關係代數運算式的等價

——

若用相同關係替代兩個運算式中相應的關係所得到的結果關係相同，則稱這兩個運算式等價，兩個關係運算式E1和E2是等價的，記為E1≡E2。關係代數中最基本的五種運算是：

∪、－、×、σ、∏常用的等價變換規則連接、笛卡爾積的交換律E1

E2≡E2

E1E1XE2≡E2XE1連接、笛卡爾積的結合律(E1

E2)

E3≡E1

(E2

E3)

(E1XE2)XE3≡

E1X(E2XE3)等價變換規則（續1）(3)投影的串接定律

A1,A2,…,Am(

B1,B2,…,Bn(E))

≡

A1,A2,…,Am(E)

其中屬性名A1，A2，…，Am是B1，B2，…，Bn的子集如：

SN(

Sno，SN(S))

≡

SN(S)(4)選擇的串接定律

F1（

F2（E））≡

F1

F2（E）

等價變換規則（續2）(5)選擇與投影的交換律

F

(

A1,A2,…,Am(E))

A1,A2,…,Am(

F(E))

其中F只涉及A1，A2，…，Am屬性

A1,A2,…,Am(

F

(E))

A1,A2,…,Am(

F(

A1,A2,…,Am,B1,B2,…,Bn(E)))

其中F涉及A1,A2,…,Am以外的屬性B1,B2,…,Bn等價變換規則（續3）(6)選擇與笛卡爾積的交換律

F

(E1

XE2)

F(E1)XE2

——F只涉及E1中的屬性

F

(E1

XE2)

F1(E1)X

F2(E2)

——F=F1

F2且F1只涉及E1的屬性、F2只涉及E2的屬性

F

(E1

XE2)

F2(

F1(E1)XE2)

——F=F1

F2且F1只涉及E1的屬性、F2涉及E1和E2的屬性等價變換規則（續4）(7)選擇與並的交換

F

(E1

E2)

F(E1)

F(E2)

——E1、E2有相同的屬性集

(8)選擇與差的交換

F

(E1－

E2)

F(E1)－

F(E2)

——E1、E2有相同的屬性集等價變換規則（續5）(9)投影與笛卡爾積的交換

A1,A2,…,Am,B1,B2,…,Bn

(E1

XE2)

A1,A2,…,Am(E1)X

B1,B2,…,Bn(E2)

——屬性A1，A2，…，Am只涉及E1

屬性B1，B2，…，Bn只涉及E2(10)投影與並的交換

A1,A2,…,Am(E1

∪E2)

A1,A2,…,Am(E1)∪

A1,A2,…,Am(E2)

——E1、E2有相同的屬性集

4.關係代數運算式的優化演算法演算法：關係運算式的優化輸入：一個關係運算式的語法樹輸出：計算該運算式的程式例如：查找選修C2課程的學生姓名。關係代數語法樹

SN(

SC.Cno=‘C2’

S.Sno=SC.Sno(SXSC))

SN

SC.

Cno=‘C2’

S.Sno=SC.SnoXSCS優化演算法（續一）方法：

1.按規則(4)拆開選擇串接，以便後來進行更有效的合併；

F1

F2（E）

F1（

F2（E））

2.按(4)~(8)規則，將每個選擇儘量移到樹的葉端；如前例：

SN(

S.Sno=SC.Sno

SC.Cno=‘C2’(SXSC))

變換(4)

SN(

S.Sno=SC.Sno(

SC.Cno=‘C2’(SXSC))

變換(6)

SN(

S.Sno=SC.Sno(SX

SC.Cno=‘C2’(SC))3.

按(3)、(9)、(10)、(5)規則，將每個投影選擇儘量移到樹的葉端；優化演算法（續二）

4.按(3)~(5)規則，把選擇和投影的串接合並成單一選擇、單一投影或一個選擇後跟一個投影，使多個選擇投影同時執行，或在一次掃描中全部完成；

5.

語法樹內結點分組：每個二目運算結點與其所有的直接祖先（由σ和π表示）分為一組；若它的子孫結點直到葉子都是單目運算，則也併入該組。對笛卡爾積，其後的選擇不能與它結合成自然連接，則這些單目運算單獨分為一組。

6.生成一個程式，每組結點的計算是程式中的一步，計算順序只要求一組的計算不在其後代組計算之前。查詢優化——

實例1查找選修C2課程的學生姓名。

SN

SC.

Cno=‘C2’

S.Sno=SC.SnoXSCS

SN

SC.

Cno=‘C2’

S.Sno=SC.SnoXSCS關係代數表示的語法樹優化後的標準語法樹查詢優化——

實例2查找電腦系學生選修的課程名稱。

SELECTC.CNFROMS，SC，CWHERES.Sno=SC.SnoANDSC.Cno=C.Cno

ANDS.SD=‘CS’

等價的關係代數運算式：

CN（

F

A（SXSCXC））其中F=(S.Sno=SC.Sno

SC.Cno=C.Cno

S.SD=‘CS’)

A=(S.Sno,S.SD,SC.Sno,SC.Cno,C.Cno,C.CN)

實例2（續一）

CN

F×SCS

CN

S.

Sno=SC.Sno

SC.Cno=C.Cno×C×C

S.SD=‘CS’×SCS

A

A實例2（續二）

CN

S.

Sno=SC.Sno

SC.Cno=C.Cno×C

S.SD=‘CS’×SCS

A

S.

Sno=SC.Sno

S.SD=‘CS’×SCS

Sno

Sno,Cno

SC.Cno

CN

SC.Cno=C.Cno×C

Cno,CN實例2（續三）關係代數運算式：

CN（

F

A（SXSCXC））

其中F=(S.Sno=SC.Sno

SC.Cno=C.Cno

S.SD=‘CS’)A=(S.Sno,S.SD,SC.Sno,SC.Cno,C.Cno,C.CN)

優化後標準語法樹對應的關係代數運算式：

CN

(

SC.Cno(

Sno(

SD=‘CS’(S))

Sno,Cno

(SC))

Cno,CN(C))小結