關(guān)系系統(tǒng)及其查詢優(yōu)化.ppt

2006年4月12日,1,第四章 關(guān)系系統(tǒng)及其查詢優(yōu)化,2006年4月12日,2,第四章 關(guān)系系統(tǒng)及其查詢優(yōu)化,4.1 關(guān)系系統(tǒng) 4.2 關(guān)系系統(tǒng)的查詢優(yōu)化 4.3 小結(jié),2006年4月12日,3,關(guān)系系統(tǒng),能夠在一定程度上支持關(guān)系模型的數(shù)據(jù)庫(kù)管理系統(tǒng)是關(guān)系系統(tǒng)。 由于關(guān)系模型中并非每一部分都是同等重要的 并不苛求一個(gè)實(shí)際的關(guān)系系統(tǒng)必須完全支持關(guān)系模型。,4,關(guān)系系統(tǒng)與關(guān)系模型,關(guān)系數(shù)據(jù)結(jié)構(gòu) 域及域上定義的關(guān)系 關(guān)系操作 并、交、差、廣義笛卡爾積、選擇、投影、連接、除等 關(guān)系完整性 實(shí)體完整性、參照完整性、用戶自己定義的完整性,2006年4月12日,5,關(guān)系系統(tǒng)的定義,一個(gè)數(shù)據(jù)庫(kù)管理系統(tǒng)可定義為關(guān)系系統(tǒng)，當(dāng)且僅 當(dāng)它至少支持： 1. 關(guān)系數(shù)據(jù)庫(kù)（即關(guān)系數(shù)據(jù)結(jié)構(gòu)） 系統(tǒng)中只有表這種結(jié)構(gòu) 2. 支持選擇、投影和（自然）連接運(yùn)算 對(duì)這些運(yùn)算不要求用戶定義任何物理存取路徑 對(duì)關(guān)系系統(tǒng)的最低要求,2006年4月12日,6,關(guān)系系統(tǒng)的定義,不支持關(guān)系數(shù)據(jù)結(jié)構(gòu)的系統(tǒng)顯然不能稱為關(guān)系系統(tǒng) 僅支持關(guān)系數(shù)據(jù)結(jié)構(gòu)，但沒(méi)有選擇、投影和連接運(yùn)算功能的系統(tǒng)仍不能算作關(guān)系系統(tǒng)。 原因：不能提高用戶的生產(chǎn)率 支持選擇、投影和連接運(yùn)算，但要求定義物理存取路徑，這種系統(tǒng)也不能算作真正的關(guān)系系統(tǒng) 原因：就降低或喪失了數(shù)據(jù)的物理獨(dú)立性 選擇、投影、連接運(yùn)算是最有用的運(yùn)算,2006年4月12日,7,4.1.2 關(guān)系系統(tǒng)的分類,分類依據(jù)：支持關(guān)系模型的程度 分類 表式系統(tǒng)：支持關(guān)系數(shù)據(jù)結(jié)構(gòu)(即表) (最小)關(guān)系系統(tǒng) 支持：關(guān)系數(shù)據(jù)結(jié)構(gòu) 選擇、投影、連接關(guān)系操作, 關(guān)系完備的系統(tǒng) 支持：關(guān)系數(shù)據(jù)結(jié)構(gòu) 所有的關(guān)系代數(shù)操作 全關(guān)系系統(tǒng) 支持：關(guān)系模型的所有特征 特別是:數(shù)據(jù)結(jié)構(gòu)中域的概念,（a）表式系統(tǒng) (b) （最小）關(guān)系的 (c）關(guān)系完備的 (d)全關(guān)系的,2006年4月12日,8,關(guān)系系統(tǒng)的分類 （續(xù)）,2006年4月12日,9,第四章 關(guān)系系統(tǒng)及其查詢優(yōu)化,4.1 關(guān)系系統(tǒng) 4.2 關(guān)系系統(tǒng)的查詢優(yōu)化 4.3 小結(jié),2006年4月12日,10,4.2 關(guān)系系統(tǒng)的查詢優(yōu)化,4.2.1 查詢優(yōu)化概述 4.2.2 查詢優(yōu)化的必要性 4.2.3 查詢優(yōu)化的一般準(zhǔn)則 4.2.4 關(guān)系代數(shù)等價(jià)變換規(guī)則 4.2.5 關(guān)系代數(shù)表達(dá)式的優(yōu)化算法 4.2.6 優(yōu)化的一般步驟,2006年4月12日,11,4.2.1 查詢優(yōu)化概述,查詢優(yōu)化的必要性 查詢優(yōu)化極大地影響RDBMS的性能。 查詢優(yōu)化的可能性 關(guān)系數(shù)據(jù)語(yǔ)言的級(jí)別很高，使DBMS可以從關(guān)系表達(dá)式中分析查詢語(yǔ)義。,2006年4月12日,12,由DBMS進(jìn)行查詢優(yōu)化的好處,用戶不必考慮如何最好地表達(dá)查詢以獲得較好的效率 系統(tǒng)可以比用戶程序的優(yōu)化做得更好 (1) 優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計(jì)信息，而用戶程序則難以獲得這些信息,2006年4月12日,13,由DBMS進(jìn)行查詢優(yōu)化的好處,(2)如果數(shù)據(jù)庫(kù)的物理統(tǒng)計(jì)信息改變了，系統(tǒng)可以自動(dòng)對(duì)查詢重新優(yōu)化以選擇相適應(yīng)的執(zhí)行計(jì)劃。 在非關(guān)系系統(tǒng)中必須重寫程序，而重寫程序在實(shí)際應(yīng)用中往往是不太可能的。 (3)優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計(jì)劃，而程序員一般只能考慮有限的幾種可能性。 (4)優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù),2006年4月12日,14,查詢優(yōu)化目標(biāo),查詢優(yōu)化的總目標(biāo) 選擇有效策略，求得給定關(guān)系表達(dá)式的值 實(shí)際系統(tǒng)的查詢優(yōu)化步驟 1. 將查詢轉(zhuǎn)換成某種內(nèi)部表示，通常是語(yǔ)法樹(shù) 2. 根據(jù)一定的等價(jià)變換規(guī)則把語(yǔ)法樹(shù)轉(zhuǎn)換成標(biāo)準(zhǔn) （優(yōu)化）形式,2006年4月12日,15,實(shí)際系統(tǒng)的查詢優(yōu)化步驟,3. 選擇低層的操作算法 對(duì)于語(yǔ)法樹(shù)中的每一個(gè)操作 計(jì)算各種執(zhí)行算法的執(zhí)行代價(jià) 選擇代價(jià)小的執(zhí)行算法 4. 生成查詢計(jì)劃(查詢執(zhí)行方案) 查詢計(jì)劃是由一系列內(nèi)部操作組成的。,2006年4月12日,16,代價(jià)模型,集中式數(shù)據(jù)庫(kù) 單用戶系統(tǒng) 總代價(jià) = I/O代價(jià) + CPU代價(jià) 多用戶系統(tǒng) 總代價(jià) = I/O代價(jià) + CPU代價(jià) + 內(nèi)存代價(jià) 分布式數(shù)據(jù)庫(kù) 總代價(jià) = I/O代價(jià) + CPU代價(jià)+ 內(nèi)存代價(jià) + 通信代價(jià),2006年4月12日,17,4.2.2 查詢優(yōu)化的必要性,例：求選修了課程2的學(xué)生姓名 SELECT Student.Sname FROM Student, SC WHERE Student.Sno=SC.Sno AND SC.Cno=2;,2006年4月12日,18,查詢優(yōu)化的必要性（續(xù)）,假設(shè)1：外存： Student:1000條,SC:10000條, 選修2號(hào)課程:50條 假設(shè)2：一個(gè)內(nèi)存塊裝元組:10個(gè)Student, 或100個(gè)SC, 內(nèi)存中一次可以存放: 5塊Student元組, 1塊SC元組和若干塊連接結(jié)果元組 假設(shè)3：讀寫速度：20塊/秒 假設(shè)4：連接方法：基于數(shù)據(jù)塊的嵌套循環(huán)法,2006年4月12日,19,執(zhí)行策略1,1 name(Student.Sno=SC.Sno SC.Cno=2 (StudentSC) StudentSC 讀取總塊數(shù)= 讀Student表塊數(shù) + 讀SC表遍數(shù) *每遍塊數(shù) =1000/10+(1000/(105) (10000/100) =100+20100=2100 讀數(shù)據(jù)時(shí)間=2100/20=105秒,2006年4月12日,20,不同的執(zhí)行策略,考慮I/O時(shí)間,中間結(jié)果大小 = 1000*10000 = 107 (1千萬(wàn)條元組) 寫中間結(jié)果時(shí)間 = 10000000/10/20 = 50000秒 讀數(shù)據(jù)時(shí)間 = 50000秒 總時(shí)間 =1055000050000秒 = 100105秒 = 27.8小時(shí),2006年4月12日,21,查詢優(yōu)化的必要性（續(xù)）,2. 2 name(SC.Cno= 2 (Student SC) 讀取總塊數(shù)= 2100塊 讀數(shù)據(jù)時(shí)間=2100/20=105秒 中間結(jié)果大小=10000 （減少1000倍） 寫中間結(jié)果時(shí)間=10000/10/20=50秒 讀數(shù)據(jù)時(shí)間=50秒 總時(shí)間1055050秒205秒=3.4分,2006年4月12日,22,查詢優(yōu)化的必要性（續(xù)）,3. 2 Sname(Student SC.Cno= 2 (SC) 讀SC表總塊數(shù)= 10000/100=100塊 讀數(shù)據(jù)時(shí)間=100/20=5秒 中間結(jié)果大小=50條 不必寫入外存 讀Student表總塊數(shù)= 1000/10=100塊 讀數(shù)據(jù)時(shí)間=100/20=5秒 總時(shí)間55秒10秒,2006年4月12日,23,查詢優(yōu)化的必要性（續(xù)）,4. 2 name(Student SC.Cno=2 (SC) 假設(shè)SC表在Cno上有索引，Student表在Sno上有索引 讀SC表索引= 讀SC表總塊數(shù)= 50/1001塊 讀數(shù)據(jù)時(shí)間 中間結(jié)果大小=50條 不必寫入外存,2006年4月12日,24,查詢優(yōu)化的必要性（續(xù)）, 讀Student表索引= 讀Student表總塊數(shù)= 50/10=5塊 讀數(shù)據(jù)時(shí)間 總時(shí)間10秒,2006年4月12日,25,4.2.3 查詢優(yōu)化的一般準(zhǔn)則,選擇運(yùn)算應(yīng)盡可能先做 目的：減小中間關(guān)系 在執(zhí)行連接操作前對(duì)關(guān)系適當(dāng)進(jìn)行預(yù)處理 按連接屬性排序 在連接屬性上建立索引 投影運(yùn)算和選擇運(yùn)算同時(shí)做 目的：避免重復(fù)掃描關(guān)系 將投影運(yùn)算與其前面或后面的雙目運(yùn)算結(jié)合 目的：減少掃描關(guān)系的遍數(shù),2006年4月12日,26,查詢優(yōu)化的一般準(zhǔn)則 （續(xù)）,某些選擇運(yùn)算在其前面執(zhí)行的笛卡爾積 = 連接運(yùn)算 例：Student.Sno=SC.Sno (StudentSC) Student SC 提取公共子表達(dá)式,2006年4月12日,27,4.2.4 關(guān)系代數(shù)等價(jià)變換規(guī)則,關(guān)系代數(shù)表達(dá)式等價(jià) 指用相同的關(guān)系代替兩個(gè)表達(dá)式中相應(yīng)的關(guān)系所得到的結(jié)果是相同的 上面的優(yōu)化策略大部分都涉及到代數(shù)表達(dá)式的變換,2006年4月12日,28,常用的等價(jià)變換規(guī)則,設(shè)E1、E2等是關(guān)系代數(shù)表達(dá)式，F(xiàn)是條件表達(dá)式 l. 連接、笛卡爾積交換律 E1 E2 E2E1 E1 E2E2 E1 E1 F E2E2 F E1,2006年4月12日,29,關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）,2. 連接、笛卡爾積的結(jié)合律 (E1E2) E3 E1 (E2E3) (E1 E2) E3 E1 (E2 E3) (E1 E2) E3 E1 (E2 E3) F F F F,2006年4月12日,30,關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）,3. 投影的串接定律 A1,A2, ,An( B1,B2, ,Bm(E) A1,A2, ,An (E) 假設(shè)： 1) E是關(guān)系代數(shù)表達(dá)式 2) Ai(i=1，2，n), Bj(j=l，2，m)是屬性名 3)A1, A2, , An構(gòu)成Bl，B2，Bm的子集,2006年4月12日,31,關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）,4. 選擇的串接定律 F1 （ F2（E） F1 F2(E) 選擇的串接律說(shuō)明 選擇條件可以合并 這樣一次就可檢查全部條件。,2006年4月12日,32,關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）,5. 選擇與投影的交換律 (1)假設(shè): 選擇條件F只涉及屬性A1，An F (A1,A2, ,An(E) A1,A2, ,An(F(E) (2)假設(shè): F中有不屬于A1, ,An的屬性B1,Bm A1,A2, ,An ( F (E) A1,A2, ,An(F (A1,A2, ,An,B1,B2, ,Bm(E),2006年4月12日,33,關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）,6. 選擇與笛卡爾積的交換律 (1) 假設(shè)：F中涉及的屬性都是E1中的屬性 F (E1E2)F (E1)E2 (2) 假設(shè)：F=F1F2，并且F1只涉及E1中的屬性， F2只涉及E2中的屬性 則由上面的等價(jià)變換規(guī)則1，4，6可推出： F(E1E2) F1(E1)F2 (E2),2006年4月12日,34,關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）,(3) 假設(shè)： F=F1F2， F1只涉及E1中的屬性， F2涉及E1和E2兩者的屬性 F(E1E2) F2(F1(E1)E2) 它使部分選擇在笛卡爾積前先做,2006年4月12日,35,關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）,7. 選擇與并的交換 假設(shè)：E=E1E2，E1，E2有相同的屬性名 F(E1E2) F(E1) F(E2) 8. 選擇與差運(yùn)算的交換 假設(shè)：E1與E2有相同的屬性名 F(E1-E2) F(E1) - F(E2),2006年4月12日,36,關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）,9. 投影與笛卡爾積的交換 假設(shè)：E1和E2是兩個(gè)關(guān)系表達(dá)式， A1，An是E1的屬性， B1，Bm是E2的屬性 A1,A2, ,An,B1,B2, ,Bm （E1E2) A1,A2, ,An（E1) B1,B2, ,Bm(E2),2006年4月12日,37,關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）,l0. 投影與并的交換 假設(shè)：E1和E2 有相同的屬性名 A1,A2, ,An(E1E2) A1,A2, ,An(E1) A1,A2, ,An(E2),2006年4月12日,38,小結(jié),1-2: 連接、笛卡爾積的交換律、結(jié)合律 3： 合并或分解投影運(yùn)算 4： 合并或分解選擇運(yùn)算 5-8： 選擇運(yùn)算與其他運(yùn)算交換 5，9，10： 投影運(yùn)算與其他運(yùn)算交換,2006年4月12日,39,4.2 關(guān)系系統(tǒng)的查詢優(yōu)化,4.2.1 查詢優(yōu)化概述 4.2.2 查詢優(yōu)化的必要性 4.2.3 查詢優(yōu)化的一般準(zhǔn)則 4.2.4 關(guān)系代數(shù)等價(jià)變換規(guī)則 4.2.5 關(guān)系代數(shù)表達(dá)式的優(yōu)化算法 4.2.6 優(yōu)化的一般步驟,2006年4月12日,40,4.2.5 關(guān)系代數(shù)表達(dá)式的優(yōu)化算法,算法：關(guān)系表達(dá)式的優(yōu)化 輸入：一個(gè)關(guān)系表達(dá)式的語(yǔ)法樹(shù)。 輸出：計(jì)算該表達(dá)式的程序。 方法： （1）分解選擇運(yùn)算 利用規(guī)則4把形如F1 F2 Fn (E)變換為 F1 (F2( (Fn(E) ),2006年4月12日,41,關(guān)系代數(shù)表達(dá)式的優(yōu)化算法 (續(xù)),（2）通過(guò)交換選擇運(yùn)算，將其盡可能移到葉端 對(duì)每一個(gè)選擇，利用規(guī)則48盡可能把它移到樹(shù)的葉端。 （3）通過(guò)交換投影運(yùn)算，將其盡可能移到葉端 對(duì)每一個(gè)投影利用規(guī)則3，9，l0，5中的一般形式盡可能把它移向樹(shù)的葉端。,2006年4月12日,42,關(guān)系代數(shù)表達(dá)式的優(yōu)化算法 (續(xù)),（4）合并串接的選擇和投影，以便能同時(shí)執(zhí)行或在一次掃描中完成 利用規(guī)則35把選擇和投影的串接合并成單個(gè)選擇、單個(gè)投影或一個(gè)選擇后跟一個(gè)投影。 使多個(gè)選擇或投影能同時(shí)執(zhí)行，或在一次掃描中全部完成 盡管這種變換似乎違背“投影盡可能早做”的原則，但這樣做效率更高。,2006年4月12日,43,關(guān)系代數(shù)表達(dá)式的優(yōu)化算法 (續(xù)),（5）對(duì)內(nèi)結(jié)點(diǎn)分組 把上述得到的語(yǔ)法樹(shù)的內(nèi)節(jié)點(diǎn)分組。 每一雙目運(yùn)算(， ，-)和它所有的直接祖先為一組(這些直接祖先是，運(yùn)算)。 如果其后代直到葉子全是單目運(yùn)算，則也將它們并入該組，但當(dāng)雙目運(yùn)算是笛卡爾積()，而且其后的選擇不能與它結(jié)合為等值連接時(shí)除外。把這些單目運(yùn)算單獨(dú)分為一組。,2006年4月12日,44,關(guān)系代數(shù)表達(dá)式的優(yōu)化算法 (續(xù)),（6）生成程序 生成一個(gè)程序，每組結(jié)點(diǎn)的計(jì)算是程序中的一步。 各步的順序是任意的，只要保證任何一組的計(jì)算不會(huì)在它的后代組之前計(jì)算。,2006年4月12日,45,4.2 關(guān)系系統(tǒng)的查詢優(yōu)化,4.2.1 查詢優(yōu)化概述 4.2.2 查詢優(yōu)化的必要性 4.2.3 查詢優(yōu)化的一般準(zhǔn)則 4.2.4 關(guān)系代數(shù)等價(jià)變換規(guī)則 4.2.5 關(guān)系代數(shù)表達(dá)式的優(yōu)化算法 4.2.6 優(yōu)化的一般步驟,2006年4月12日,46,4.2.6 優(yōu)化的一般步驟,1把查詢轉(zhuǎn)換成某種內(nèi)部表示 2代數(shù)優(yōu)化：把語(yǔ)法樹(shù)轉(zhuǎn)換成標(biāo)準(zhǔn)（優(yōu)化） 形式 3物理優(yōu)化：選擇低層的存取路徑 4生成查詢計(jì)劃，選擇代價(jià)最小的,2006年4月12日,47,優(yōu)化的一般步驟 (續(xù)),（1）把查詢轉(zhuǎn)換成某種內(nèi)部表示 例：求選修了課程2的學(xué)生姓名 SELECT Student.Sname FROM Student, SC WHERE Student.Sno=SC.Sno AND SC.Cno=2;,2006年4月12日,48,（1）把查詢轉(zhuǎn)換成某種內(nèi)部表示,語(yǔ)法樹(shù),結(jié)果,project(Sname),select(SC.Cno=2),join(Student.Sno=SC.Sno),Student,SC,2006年4月12日,49,關(guān)系代數(shù)語(yǔ)法樹(shù),2006年4月12日,50,（2）代數(shù)優(yōu)化,利用優(yōu)化算法把語(yǔ)法樹(shù)轉(zhuǎn)換成標(biāo)準(zhǔn)（優(yōu)化）形式,2006年4月12日,51,（3）物理優(yōu)化：選擇低層的存取路徑,- 優(yōu)化器查找數(shù)據(jù)字典獲得當(dāng)前數(shù)據(jù)庫(kù)狀態(tài)信息 選擇字段上是否有索引 連接的兩個(gè)表是否有序 連接字段上是否有索引 然后根據(jù)一定的優(yōu)化規(guī)則選擇存取路徑 如本例中若SC表上建有Cno的索引，則應(yīng)該利用這個(gè)索引，而不必順序掃描SC表。,2006年4月12日,52,（4）生成查詢計(jì)劃，選擇代價(jià)最小的,在作連接運(yùn)算時(shí)，若兩個(gè)表(設(shè)為R1，R2)均無(wú)序，連接屬性上也沒(méi)有索引，則可以有下面幾種查詢計(jì)劃： 對(duì)兩個(gè)表作排序預(yù)處理 對(duì)R1在連接屬性上建索引 對(duì)R2在連接屬性上建索引 在R1，R2的連接屬性上均建索引 對(duì)不同的查詢計(jì)劃計(jì)算代價(jià)，選擇代價(jià)最小的一個(gè)。 在計(jì)算代價(jià)時(shí)主要考慮磁盤讀寫的I/O數(shù)，內(nèi)存CPU處理時(shí)間在粗略計(jì)算時(shí)可不考慮。,2006年4月12日,53,第四章 關(guān)系系統(tǒng)及其查詢優(yōu)化,4.1 關(guān)系系統(tǒng) 4.2 關(guān)系系統(tǒng)的查詢優(yōu)化 4.3 小結(jié),2006年4月12日,54,4.3 小結(jié),關(guān)系系統(tǒng) 關(guān)系系統(tǒng)的定義 一個(gè)數(shù)據(jù)庫(kù)管理系統(tǒng)可定義為關(guān)系系統(tǒng)，當(dāng)且僅當(dāng)它至少支持： 1 關(guān)系數(shù)據(jù)庫(kù)（即關(guān)系數(shù)據(jù)結(jié)構(gòu)） 2 支持選擇、投影和（自然）連接運(yùn)算， 且不要求用戶定義任何物理存取路徑,2006年4月12日,55,小結(jié) 關(guān)系系統(tǒng)的定義： 一個(gè)系統(tǒng)可定義為關(guān)系系統(tǒng)，當(dāng)且僅當(dāng)它支持： 1關(guān)系數(shù)據(jù)庫(kù)。即從用戶觀點(diǎn)看，數(shù)據(jù)庫(kù)是由表構(gòu)成的，并且 只有表這種結(jié)構(gòu)。 2支持選擇、投影和（自然）連接運(yùn)算。對(duì)這些運(yùn)算不必要求 定義任何物理存取路徑。 關(guān)系系統(tǒng)分類 （a）表式系統(tǒng) (b) （最?。╆P(guān)系的 (c）關(guān)系完備的 (d)全關(guān)系的,2006年4月12日,56,小結(jié) （續(xù)）,關(guān)系系統(tǒng)的查詢優(yōu)化 代數(shù)優(yōu)化：關(guān)系代數(shù)表達(dá)式的優(yōu)化 關(guān)系代數(shù)等價(jià)變換規(guī)則 關(guān)系代數(shù)表達(dá)式的優(yōu)化算法 物理優(yōu)化：存取路徑和低層操作算法的選擇,2006年4月12日,57,查詢優(yōu)化的總目標(biāo)是：選擇有效的策略。求得給定的關(guān)系表達(dá)式 的值 優(yōu)化的一般策略： 1選擇運(yùn)算應(yīng)盡可能先做。 2在執(zhí)行連接前對(duì)文件適當(dāng)?shù)仡A(yù)處理，預(yù)處理方法主要又兩種， 對(duì)文件排序和在連接屬性上建立索引。 3把投影運(yùn)算和選擇運(yùn)算同時(shí)進(jìn)行。 4把投影同其前或后的雙目運(yùn)算結(jié)合起來(lái)。 5 把某些選擇同在它前面要執(zhí)行的笛卡兒積結(jié)合起來(lái)成為一個(gè) 連接字段。 6找出公共子表達(dá)式。,2006年4月12日,58,關(guān)系代數(shù)等價(jià)變換規(guī)則： 兩個(gè)關(guān)系表達(dá)式E1和E2是等價(jià)的，可記為E1 E2 1連接、笛卡兒積的交換律 設(shè)E1和 E2是關(guān)系代數(shù)表達(dá)式， F是連接運(yùn)算的條件，則有： E1 E2 E2 E1 E1 E2 E2 E1 E1 E2 E2 E1 F F 2連接、笛卡兒積的結(jié)合律 設(shè)E1，E2，E3是關(guān)系表達(dá)式，F(xiàn)1和F2是連接運(yùn)算的條件，則有： （E1E2）E3 E1（E2E3） （E1 E2） E3 （E1 E2） E3 (E1 E2) E3 E1 (E1 E2) 3投影的串接定律 A1,A2,An ( B1,B2,Bm(E) A1,A2,An (E) 這里，E是關(guān)系代數(shù)表達(dá)式，Ai（ i=1,2, , n ),Bj( j=1,2, , m )是,2006年4月12日,59,屬性名且A1,A2, , An構(gòu)成B1,B2, , Bm 的子集. 4選擇的串接定律 F1（ F2（E） F1F2（E） 這里，E是關(guān)系代數(shù)表達(dá)式，F(xiàn)1，F(xiàn)2是選擇的條件。選擇的串接律 說(shuō)明條件可以合并。這樣一次就可以檢查全部條件。 5選擇和投影的交換律 F(A1,A2,An (E) A1,A2,An(F(E) 這里,選擇條件F只涉及屬性A1,A2, , An。若F中有不屬于屬性 B1,B2, , Bm 則有更一般的規(guī)則 A1,A2,An(F(E) A1,A2,An(F(A1,A2,An , B1,B2, , Bm (E) 6選擇與笛卡兒積的交換律 如果F中涉及的屬性都是E1中的屬性，則 F（E1 E2） F （E1） E2 如果F=F1F2，并且F1只涉及E1中的屬性，F(xiàn)2只涉及E2中的屬性 ，則由上面的1,4,6 可推出： F（E1 E2） F 1（E1） F2 （E2）,2006年4月12日,60,若F1只涉及E1中的屬性， F2涉及E1和E2兩者的屬性，則仍有： F（E1 E2） F 2（F1 （E1） E2） 它使部分選擇在笛卡兒積前先做。