查詢樹(shù)的優(yōu)化

會(huì)計(jì)學(xué)1查詢樹(shù)的優(yōu)化4.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理查詢處理步驟Sfromstudent,scWherestudent.sno=o=2;例：選修了2號(hào)課程的學(xué)生姓名第1頁(yè)/共46頁(yè)4.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理Sfromstudent,scWherestudent.sno=o=2;1.查詢分析：識(shí)別其中的關(guān)鍵字，屬性名，表名。2.查詢檢查：屬性名是否有效，表名是否有效等。3.查詢優(yōu)化：例如上例中先執(zhí)行連接還是先執(zhí)行

o=2從sc表中進(jìn)行選擇。選用何種方法進(jìn)行連接。4.查詢執(zhí)行。第2頁(yè)/共46頁(yè)4.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理查詢處理步驟查詢分析：對(duì)查詢語(yǔ)句進(jìn)行掃描、詞法分析和語(yǔ)法分析。查詢檢查：語(yǔ)義檢查查詢優(yōu)化：代數(shù)優(yōu)化和物理優(yōu)化查詢執(zhí)行第3頁(yè)/共46頁(yè)4.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理為什么進(jìn)行代數(shù)優(yōu)化？例：選修了2號(hào)課程的學(xué)生姓名Πsname(o=‘2’

（SC

Student））Πsname(student.sno=sc.snoΛ

o=‘2’

（SCХStudent））Πsname(o=‘2’(SC)

Student））第4頁(yè)/共46頁(yè)4.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理Πsname(student.sno=sc.snoΛ

o=‘2’

（SCХStudent））假設(shè)有1000個(gè)學(xué)生記錄，10000個(gè)選課記錄，2號(hào)課程的選課記錄為500個(gè)。1.笛卡爾積計(jì)算：1000*100002.選擇：掃描1000*10000個(gè)記錄3.投影第5頁(yè)/共46頁(yè)4.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理假設(shè)有1000個(gè)學(xué)生記錄，10000個(gè)選課記錄，2號(hào)課程的選課記錄為500個(gè)。1.連接，采用嵌套循環(huán)：10000*1000，得到10000個(gè)結(jié)果2.選擇：掃描10000個(gè)記錄3.投影Πsname(o=‘2’

（SC

Student））第6頁(yè)/共46頁(yè)4.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理假設(shè)有1000個(gè)學(xué)生記錄，10000個(gè)選課記錄，2號(hào)課程的選課記錄為500個(gè)。1.選擇：掃描10000個(gè)記錄，得到500個(gè)記錄2.連接，采用嵌套循環(huán)：500*1000次，得到500個(gè)記錄3.投影Πsname(o=‘2’(SC)

Student）

選擇操作先做可以提高效率。第7頁(yè)/共46頁(yè)4.2代數(shù)優(yōu)化4.2.1關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則

等價(jià)的概念：若關(guān)系表達(dá)式f（E1，E2，…，En）的結(jié)果與關(guān)系表達(dá)式g（E1，E2，…，En）的結(jié)果是同一個(gè)關(guān)系，那么稱(chēng)這兩個(gè)表達(dá)式等價(jià)。若關(guān)系表達(dá)式E1和E2是等價(jià)的可以記為：第8頁(yè)/共46頁(yè)等價(jià)變換規(guī)則1.連接、笛卡兒積交換率設(shè)E1和E2是關(guān)系代數(shù)表達(dá)式，F(xiàn)是連接運(yùn)算的條件，則有：第9頁(yè)/共46頁(yè)等價(jià)變換規(guī)則1.連接、笛卡兒積的結(jié)合率設(shè)E1，E2，E3是關(guān)系代數(shù)表達(dá)式，F(xiàn)1和F2是連接運(yùn)算的條件，則有：第10頁(yè)/共46頁(yè)等價(jià)變換規(guī)則2.連接、笛卡兒積的結(jié)合率設(shè)E1，E2，E3是關(guān)系代數(shù)表達(dá)式，F(xiàn)1和F2是連接運(yùn)算的條件，則有：≡Student(SCCourse)StudentSCCourseSC(StudentCourse)≡StudentSCCourse第11頁(yè)/共46頁(yè)3.投影的串接定律

這里，E是關(guān)系代數(shù)表達(dá)式，Ai（i=1，2，…，n），Bj（j=1，2，…，m）是屬性名且{A1，A2，…An}是{B1，B2，…，Bm}的子集。等價(jià)變換規(guī)則第12頁(yè)/共46頁(yè)4.選擇的串接定律等價(jià)變換規(guī)則求IS系年齡大于１９歲的學(xué)生：第13頁(yè)/共46頁(yè)4.選擇的串接定律

E是關(guān)系代數(shù)表達(dá)式，F(xiàn)1和F2是選擇條件。選擇的串接定律說(shuō)明選擇條件可以合并，這樣一次就可以檢查全部的條件。等價(jià)變換規(guī)則第14頁(yè)/共46頁(yè)等價(jià)變換規(guī)則第15頁(yè)/共46頁(yè)5.選擇與投影的交換律

此時(shí)，條件F只涉及屬性組A。若條件中有不屬于A的屬性組B，那么有更一般的規(guī)則：等價(jià)變換規(guī)則第16頁(yè)/共46頁(yè)6.選擇與笛卡爾積的交換（1）F只涉及E1的屬性。（2）F=F1∧F2，且F1只涉及E1的屬性，F(xiàn)2只涉及E2的屬性。（3）F=F1∧F2，且F1只涉及E1的屬性，而F2涉及E1和E2的屬性。第17頁(yè)/共46頁(yè)(1)實(shí)例：選修1號(hào)課程的學(xué)生信息等價(jià)變換規(guī)則(2)實(shí)例：信息系選修1號(hào)課程的學(xué)生信息第18頁(yè)/共46頁(yè)7.選擇與并的分配率設(shè)E=E1∪E2，E1和E2有相同的屬性名，則：注：先做選擇可以減少讀取寫(xiě)入的數(shù)據(jù)，因此減少磁盤(pán)IO量，從而提高了效率。等價(jià)變換規(guī)則第19頁(yè)/共46頁(yè)設(shè)S1是計(jì)科041的學(xué)生關(guān)系表，S2是計(jì)科042的學(xué)生關(guān)系表：等價(jià)變換規(guī)則第20頁(yè)/共46頁(yè)8.選擇與差運(yùn)算的分配率設(shè)E1和E2有相同的屬性名，則：注：先做選擇可以減少讀取寫(xiě)入的數(shù)據(jù)，因此減少磁盤(pán)IO量，從而提高了效率。等價(jià)變換規(guī)則第21頁(yè)/共46頁(yè)設(shè)S1是計(jì)科041的學(xué)生關(guān)系表，S3是計(jì)科專(zhuān)業(yè)的學(xué)生關(guān)系表：等價(jià)變換規(guī)則第22頁(yè)/共46頁(yè)9.選擇對(duì)自然連接的分配率F只涉及E1和E2的公共屬性。注：先做選擇可以減少做笛卡兒積的數(shù)據(jù)，結(jié)果關(guān)系的數(shù)據(jù)量也同步減少，因此減少磁盤(pán)IO量，提高了效率。等價(jià)變換規(guī)則第23頁(yè)/共46頁(yè)等價(jià)變換規(guī)則第24頁(yè)/共46頁(yè)10.投影與笛卡爾積的分配律

設(shè)E1和E2是兩個(gè)關(guān)系表達(dá)式，A是E1的屬性組，B是E2的屬性組。則：注：先做投影可以減少讀取寫(xiě)入的數(shù)據(jù)，因此減少磁盤(pán)IO量，從而提高了效率。等價(jià)變換規(guī)則第25頁(yè)/共46頁(yè)查找所有學(xué)生可能的選課對(duì)：等價(jià)變換規(guī)則第26頁(yè)/共46頁(yè)11.投影與并的分配律設(shè)E1和E2有相同的屬性名，則：注：先做投影可以減少讀取寫(xiě)入的數(shù)據(jù)，因此減少磁盤(pán)IO量，從而提高了效率。等價(jià)變換規(guī)則第27頁(yè)/共46頁(yè)設(shè)S1是計(jì)科041的學(xué)生關(guān)系表，S2是計(jì)科042的學(xué)生關(guān)系表：查找計(jì)科041、042的學(xué)生姓名：等價(jià)變換規(guī)則第28頁(yè)/共46頁(yè)優(yōu)化規(guī)則：選擇運(yùn)算盡可能先做。投影運(yùn)算和選擇運(yùn)算同時(shí)進(jìn)行。把投影運(yùn)算同其前后的雙目運(yùn)算結(jié)合執(zhí)行。選擇運(yùn)算和笛卡兒積運(yùn)算結(jié)合成連接運(yùn)算。找出公共子表達(dá)式，避免重復(fù)運(yùn)算。第29頁(yè)/共46頁(yè)4.2.2查詢樹(shù)的優(yōu)化4.2代數(shù)優(yōu)化1.查詢樹(shù)××SCSC第30頁(yè)/共46頁(yè)4.2.2優(yōu)化算法1.利用規(guī)則4分解選擇運(yùn)算。2.利用規(guī)則4~9把選擇運(yùn)算盡量移到葉端。3.利用規(guī)則3，5，10，11把投影運(yùn)算盡量移到葉端。4.利用規(guī)則3~5把選擇和投影的串接合并成單個(gè)選擇、單個(gè)投影或一個(gè)選擇后跟一個(gè)投影的形式。使盡可能多的選擇和投影同時(shí)執(zhí)行。5.分組。雙目運(yùn)算和他的直系祖先為一組；雙目運(yùn)算后代直道葉子全是單目運(yùn)算時(shí)并入改組。笛卡兒積的后面若不是與之可以合并的自然連接的等值選擇時(shí)，其后代單獨(dú)分為一組。第31頁(yè)/共46頁(yè)優(yōu)化實(shí)例例：查詢至少選修了一門(mén)先行課號(hào)為5號(hào)課程的學(xué)生姓名。其中，C是課程表，S是學(xué)生表，SC是學(xué)生選課表。在優(yōu)化規(guī)則中沒(méi)有對(duì)自然連接的直接優(yōu)化，我們把自然連接分解為笛卡兒積和選擇。第32頁(yè)/共46頁(yè)分解后的關(guān)系代數(shù)表達(dá)式××SCSC第33頁(yè)/共46頁(yè)第一步：利用規(guī)則4分解選擇運(yùn)算××SCSC第34頁(yè)/共46頁(yè)第二步：盡量下放選擇運(yùn)算××SCSC第35頁(yè)/共46頁(yè)××SCSC第二步（2）：下放完成后：第36頁(yè)/共46頁(yè)第三步：盡量下放投影運(yùn)算××SCSCE第37頁(yè)/共46頁(yè)第三步：盡量下放投影運(yùn)算××SCSC第38頁(yè)/共46頁(yè)第三步（2）：第一次下放后：××SCSC第39頁(yè)/共46頁(yè)