查詢樹的優(yōu)化

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

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

（SC

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

o=‘2’

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

Student））第4頁/共46頁4.1關系數據庫系統(tǒng)的查詢處理Πsname(student.sno=sc.snoΛ

o=‘2’

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

（SC

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

Student）

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

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

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

E是關系代數表達式，F1和F2是選擇條件。選擇的串接定律說明選擇條件可以合并，這樣一次就可以檢查全部的條件。等價變換規(guī)則第14頁/共46頁等價變換規(guī)則第15頁/共46頁5.選擇與投影的交換律

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

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