第七章-關(guān)系系統(tǒng)及其優(yōu)化課件

關(guān)系系統(tǒng)的定義關(guān)系系統(tǒng):支持關(guān)系數(shù)據(jù)模型的數(shù)據(jù)庫管理系統(tǒng)(粗略)關(guān)系系統(tǒng)(確切定義):一個系統(tǒng)可以定義為一個關(guān)系系統(tǒng),當(dāng)且僅當(dāng)它:支持關(guān)系數(shù)據(jù)庫支持選擇、投影和連接運算(自然連接),對這些運算不要求定義任何物理存取路徑關(guān)系系統(tǒng)的分類:許多關(guān)系系統(tǒng)的產(chǎn)品按E.F.Codd的思想將關(guān)系系統(tǒng)分為:表式系統(tǒng)(a)最小關(guān)系系統(tǒng)(b)關(guān)系完備的系統(tǒng)(c)全關(guān)系系統(tǒng)(d)SMISMISMISMIabcd關(guān)系系統(tǒng)的查詢處理:查詢處理的步驟:

queryParser&translatorRelationalalgebraexpressionOptimizerExecutionplanEvaluationengineQueryoutputdataStatisticsaboutdataDBMS關(guān)系系統(tǒng)的查詢優(yōu)化:為什么需要查詢優(yōu)化關(guān)系系統(tǒng)的查詢優(yōu)化由系統(tǒng)完成,而不是由用戶完成優(yōu)化器可以數(shù)據(jù)字典獲取許多統(tǒng)計信息如果數(shù)據(jù)庫的物理統(tǒng)計信息改變了,優(yōu)化器可以對查詢進行重新優(yōu)化以選擇適應(yīng)的執(zhí)行計劃優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計劃優(yōu)化器包括了許多復(fù)雜的技術(shù)優(yōu)化目標(biāo):尋求最優(yōu)的執(zhí)行計劃,使查詢執(zhí)行開銷盡量小關(guān)系系統(tǒng)的查詢優(yōu)化:查詢優(yōu)化的一般步驟將查詢轉(zhuǎn)化成內(nèi)部表示--語法樹根據(jù)等價變化規(guī)則,將語法樹轉(zhuǎn)化成優(yōu)化形式選擇低層操作算法生成查詢計劃查詢執(zhí)行開銷主要包括:

總代價=I/O代價+CPU代價多用戶數(shù)據(jù)庫執(zhí)行開銷:

總代價=I/O代價+CPU代價+內(nèi)存代價關(guān)系系統(tǒng)的查詢優(yōu)化:一個查詢實例:求選修2號課程的學(xué)生姓名SQL表示:selectSnamefromStudents,SCwhereStudents.Sno=SC.SnoandCno=‘2’;關(guān)系代數(shù)表示:Q1=sname(Students.Sno=SC.SnoandCno=‘2’(StudentsSC))Q2=sname(Cno=‘2’(StudentsSC))Q3=sname(StudentsCno=‘2’(SC))代價計算Q1代價計算(僅考慮I/O代價)計算廣義笛卡爾積代價假定:在內(nèi)存中,存放5塊Students元組和一塊SC元組,一塊可以裝10個Students元組或100個SC元組.假定:Students有1000個元組,SC有10000個元組,其中選2號課程的有50個元組數(shù)據(jù)只有讀到內(nèi)存才能進行連接Q1=sname(Students.Sno=SC.SnoandCno=‘2’(StudentsSC))通過讀取塊數(shù)計算I/O代價讀取塊數(shù)計算方法:Students1000個元組

SC10000個元組讀取總塊數(shù):若每秒讀寫20塊,則花費:10100SCStudents5塊Q1=sname(Students.Sno=SC.SnoandCno=‘2’(StudentsSC))連接后的元組個數(shù)為:103

104=107連接后的中間結(jié)果內(nèi)存放不下,需暫時寫到外存若每塊可裝10個元組,則寫出這些元組需:(107/10)/20=5104s選擇操作:讀回需5104s,選擇后剩50個元組,假定均可放在內(nèi)存投影操作:查詢共花費:105+25104

105sQ1=sname(Students.Sno=SC.SnoandCno=‘2’(StudentsSC))Q2=sname(Cno=‘2’(StudentsSC))Q2代價計算(僅考慮I/O代價)計算自然連接代價也要把數(shù)據(jù)讀到內(nèi)存進行連接,但連接結(jié)果比笛卡爾積要小得多讀取塊數(shù)依然為:花費為2100/20105s連接結(jié)果大小為104個元組,寫到外存需:(104/10)/20=50s

Q2=sname(Cno=‘2’(StudentsSC))

Q3=sname(StudentsCno=‘2’(SC))讀取自然連接結(jié)果,執(zhí)行選擇運算,需50s,選擇結(jié)果均可放在內(nèi)存投影運算:總花費為:105+50+50=205sQ3代價計算(僅考慮I/O代價)計算對SC做選擇運算的代價需讀SC到內(nèi)存進行選擇運算讀SC塊數(shù)為:10000/100=100花費為:100/20=5s選擇結(jié)果為50個SC元組,均可放在內(nèi)存Q3=sname(StudentsCno=‘2’(SC))計算和Students自然連接的代價需讀Students到內(nèi)存進行連接運算讀Students塊數(shù)為:1000/10=100花費為:100/20=5s連接結(jié)果為50個元組,均可放在內(nèi)存投影運算:總花費:5+5=10s1050SCStudents5塊關(guān)系系統(tǒng)的查詢優(yōu)化:查詢優(yōu)化的一般準(zhǔn)則:下面的優(yōu)化策略一般能提高查詢效率,但不一定是最優(yōu)的選擇運算盡可能先做,降低中間結(jié)果大小在連接前,對關(guān)系適當(dāng)?shù)倪M行預(yù)處理:對關(guān)系排序(排序合并連接方法)或在連接屬性上建索引(索引連接方法)95004…95002...95003...95001…...Students950031…950032…950042...950043...950011…...SC循環(huán)嵌套連接(不做任何預(yù)處理):...關(guān)系系統(tǒng)的查詢優(yōu)化:95001…95002...95003...95004…...Students950011…950031…950032…950042...950043......SC排序合并連接(連接的關(guān)系分別排序):...索引連接(在SC的連接列Sno上建立索引):Students9500195003950039500495004...SC索引...95004…95002...95003...95001…...950031…950032…950042...950043...950011…...SC關(guān)系系統(tǒng)的查詢優(yōu)化:把投影運算和選擇運算同時進行

sno(cno=‘2’(SC))把投影和其前或后的雙目運算結(jié)合起來Cname(CourseSC)把某些選擇同在它前面要執(zhí)行的笛卡爾積結(jié)合起來成為一個連接運算Students.Sno=SC.SnoandCno=‘2’(StudentsSC)找出公共子表達式關(guān)系系統(tǒng)的查詢優(yōu)化:關(guān)系代數(shù)等價變換規(guī)則:給定sname(Students.Sno=SC.SnoandCno=‘2’(StudentsSC))如何將上述提到的運算先做,即得到:sname(StudentsCno=‘2’(SC))規(guī)則1:連接、笛卡爾積的交換律

E1E2E2E1E1E2=E2E1E1E2=E2E1E:關(guān)系代數(shù)表達式F:連接條件規(guī)則2:連接、笛卡爾積的結(jié)合律(E1E2)E3=E1(E2E3)(E1E2)E3E1(E2E3)(E1E2)E3E1(E2E3)F1FFF2F1F2關(guān)系系統(tǒng)的查詢優(yōu)化:規(guī)則3:投影的串接定律

A1,A2,...,An(B1,B2,...,Bn(E))A1,A2,...,An(E)規(guī)則4:選擇的串接定律F1(F2(E))F1F2(E)規(guī)則5:選擇和投影的交換律F(A1,A2,...,An(E))A1,A2,...,An(F(E))特殊情況

A1,A2,...,An(F(E))A1,A2,...,An(F(A1,A2,...,An,B1,B2,...,Bm(E)))規(guī)則6:選擇與笛卡爾積的交換律F(E1E2)F(E1)E2

F僅和E1有關(guān)F(E1E2)F1(E1)F2(E2)F=F1F2

F(E1E2)F2(F1(E1)E2)F1--E1F2--E1E22021關(guān)系系統(tǒng)的查詢優(yōu)化:規(guī)則7:選擇與并的交換

F(E1E2)F(E1)F(E2)規(guī)則8:選擇與差的交換F(E1-E2)F(E1)-F(E2)規(guī)則9:投影與笛卡爾積的交換

A1,A2,...,An,B1,B2,...,Bm(E1E2)A1,A2,...,An(E1)B1,B2,...,Bm(E2)規(guī)則10:投影與并的交換A1,A2,...,An(E1E2)A1,A2,...,An(E1)A1,A2,...,An(E2)

20關(guān)系系統(tǒng)的查詢優(yōu)化:關(guān)系代數(shù)表達式的優(yōu)化算法:應(yīng)用關(guān)系代數(shù)等價變換規(guī)則來優(yōu)化關(guān)系代數(shù)表達式,使優(yōu)化后的表達式能遵循查詢優(yōu)化的一般準(zhǔn)則,在語法樹上進行優(yōu)化關(guān)系代數(shù)表達式的優(yōu)化算法輸入:語法樹

1利用規(guī)則4把形如F1F2…Fn(E)變換成F1(F2(…(Fn(E))...))2對每一個選擇,利用規(guī)則4~8盡可能移到樹的葉端

3對于每個投影,利用規(guī)則3,9,10,5盡可能移到樹的葉端20頁關(guān)系系統(tǒng)的查詢優(yōu)化:

4利用規(guī)則3~5把選擇和投影的串接合并成單個選擇,單個投影,或一個選擇后跟一個投影

5把處理后的語法樹內(nèi)節(jié)點分組:每一雙目運算(,,,)和它的所有直接祖先(,)為一組,后代直到葉子全是單目運算也并入該組;若雙目運算為,且其后的選擇不能與它結(jié)合為等值連接時,這些單目運算單獨為一組.6生成一個程序,每組節(jié)點的計算是程序中的一步輸出:計算關(guān)系代數(shù)表達式的程序21頁關(guān)系系統(tǒng)的查詢優(yōu)化:SSPP不能結(jié)合成等值連接S.Sno=SC.SnoSCS能結(jié)合成等值連接22頁關(guān)系系統(tǒng)的查詢優(yōu)化:優(yōu)化的一般步驟:因DBMS不同把查詢轉(zhuǎn)換成某種內(nèi)部表示(例如關(guān)系代數(shù)語法樹)把語法樹轉(zhuǎn)化成標(biāo)準(zhǔn)(優(yōu)化)形式選擇底層的存取路徑生成查詢計劃,選擇代價最小的例子:設(shè)有供應(yīng)商S,零件P和供應(yīng)關(guān)系SP三個關(guān)系,其關(guān)系模式:S(Snum,Sname,City)P(Pnum,Pname,Weight,Size)SP(Snum,Pnum,Dept,Quan)23頁關(guān)系系統(tǒng)的查詢優(yōu)化:selectSnamefromS,SP,PwhereS.Snum=SP.SnumandSP.Snum=P.SnumandS.City=‘NANJING’andP.Pname=‘Bolt’andSP.Quan>1000;原始語法樹:select--投影

from--笛卡爾積

where--選擇24頁關(guān)系系統(tǒng)的查詢優(yōu)化:SnamecSSPPC=S.Snum=SP.SnumandSP.Snum=P.SnumandS.City=‘NANJING’andP.Pname=‘Bolt’andSP.Quan>1000SnamecSSPPSnamec’SSPPssppSnamec’’SSPPssppSnameSSPPssppspspc’c’’優(yōu)化:25頁練習(xí)1查詢要求:查詢信息系學(xué)生選修的所有的課程的課程名稱寫出關(guān)系代數(shù)及其原始語法樹,并進行優(yōu)化處理,畫出優(yōu)化后的語法樹.SELECTCnameFROMStudents,Course,SCWHEREStudents.sno=SC.snoandCo=SC.cnoandSdept=‘IS’;26頁練習(xí)1:

Cname(Sdept=‘IS’(StudentsSCCourse))CnamecStudentsSCCourse原始語法樹:27頁Cnamec1StudentsSCCourseC:Students.sno=Sc.snoSC.cno=CoSdept=‘IS’C’:

SC.cno=Co,C1:Sdept=‘IS’Cnamec1StudentsSCCoursec’練習(xí)2查詢要求:一圖書管理數(shù)據(jù)庫，其關(guān)系如下：BOOKS(Title,Author,Pname,LC_No)PUBLISHERS(Pname,Paddr,Pcity)BORROWERS(Name,Addr,City,Card_No)LOANS(Card_No,LC_No,Date)要求：1.列出2003年1月1日前借出的所有書名和借書人姓名2.寫出關(guān)系代數(shù)及其原始語法樹,并進行優(yōu)化處理,畫出優(yōu)化后的語法樹.SELECTTitle,NamefromBOOKS,BORROWERS,LOANSWHEREBOOKS.LC_No=LOANS.LC_NoANDBORROWERS.Card_No=LOANS.Card_NoANDDate>’01/01/2003’26頁圖書編號圖書證號練習(xí)2:

Title,Name(Date>’01/01/2003’(BOOKSBORROWERSLOANS))Title,NameDate>’01/01/2003’BOOKSBORROWERSLOANS原始語法樹:27頁BOOKS.LC_No=LOANS.LC_NoANDBORROWERS.Card_No=LOANS.Card_No

Title,Author,Pname,LC_No,Name,Addr,City,Card_No,Date練習(xí)2:

Title,Name(Date>’01/01/2003’(BOOKSBORROWERSLOANS))28頁Date>’01/01/2003’(BOOKSBORROWERSLOANS)=BOOKSDate>’01/01/2003’(BORROWERSLOANS)=BOOKSBORROWERSDate>’01/01/2003’(LOANS)Title,NameDate>’01/01/2003’BOOKSBORROWERSLOANSBOOKS.LC_No=LOANS.LC_NoBORROWERS.Card_No=LOANS.Card_No

練習(xí)2:

Title,Name(Date>’01/01/2003’(BOOKSBORROWERSLO