1、2.1 關系數(shù)據(jù)庫的基本概念,2.2 關系模型及其描述,2.3 關系代數(shù),2.4 關系演算,第二章 關系數(shù)據(jù)庫,1,2.5 關系數(shù)據(jù)庫查詢優(yōu)化,上一章回顧,什么是數(shù)據(jù)庫？ 按一定結構組織，并長期存儲在計算機內(nèi)、可共享的大量數(shù)據(jù)的有機集合 常用的數(shù)據(jù)庫管理系統(tǒng)有哪些？ Oracle、SQL Server、MySQL等 導師與研究生是什么對應關系？ 1：n,2,上一章回顧,E-R模型的四個組成部分？,3,實體名,屬性名,矩形框表示實體型,橢圓形表示屬性,菱形表示聯(lián)系,連接實體型與聯(lián)系類型，也可用于表示實體與屬性的聯(lián)系 并注明種類；對構成碼的屬性，在屬性名下畫一橫線表示。,上一章回顧,三種基本數(shù)據(jù)模

2、型是？ 層次模型、網(wǎng)狀模型、關系模型 關系模型采用什么結構表示實體及實體間聯(lián)系？ 表結構 DBMS的三級模式與兩級映象？ 外模式、模式、內(nèi)模式 外模式/模式映象、模式/內(nèi)模式映象,4,5,上一章回顧,模式、外模式、內(nèi)模式分別是什么的描述？ 模式：數(shù)據(jù)庫中全體數(shù)據(jù)的邏輯結構和特征的描述 外模式：數(shù)據(jù)庫用戶使用的局部數(shù)據(jù)的邏輯結構和特征的描述 內(nèi)模式：數(shù)據(jù)物理結構和存儲方式的描述 DBMS系統(tǒng)怎樣確保了數(shù)據(jù)獨立性？ 外模式/模式映象：實現(xiàn)數(shù)據(jù)邏輯獨立性 模式/內(nèi)模式映象：實現(xiàn)數(shù)據(jù)物理獨立性,6,2.1基本概念,關系數(shù)據(jù)庫之父 E.F.Codd（埃德加.科德）英國人，1923 在牛津的?？巳貙W院研

3、習數(shù)學與化學 作為英國皇家空軍的飛行員參加了二戰(zhàn) 1948年加入了IBM公司，成為數(shù)學程序員 1953年，出于對參議員約瑟夫麥卡錫的不滿, 他遷往加拿大渥太華居住了十年 之后回到密歇根大學并取得了計算機科學博士學位 1981年, 科德因在關系型數(shù)據(jù)庫方面的貢獻獲得了圖靈獎 2003年4月18日, 科德因心臟病在佛羅里達威廉姆斯島的家中去世, 享年79歲,7,1、關系及其性質(zhì) （1）域 定義2.1: 域是一組具有相同數(shù)據(jù)類型的值的集合。,在關系中用域來表示屬性的取值范圍 域中所包含的值的個數(shù)稱域的基數(shù)(用m表示),例：D1=A , 2 , 3 , , Q , K M1= 13 D2=數(shù)據(jù)庫原理，

4、面向對象數(shù)據(jù)庫技術 M2= 2,2.1 關系數(shù)據(jù)庫的基本概念,8,（2）笛卡爾積 定義2.2: 給定一組域 D1，Dn (可有相同的域)。 其笛卡爾積為： D1D2Dn=(d1，d2，dn) | diDi，i=1,2,n,n元組,di為分量,笛卡兒積也是一個集合,其中每一個元素(d1，d2，dn)叫作一個n元組(n-Tuple), 或簡稱為元組。元素中的每一個值di叫作一個分量（Component）。,若Di（i1，2，n）為有限集，其基數(shù)（Cardinal number）為mi（i1，2，n），則D1D2Dn的基數(shù)為：,2.1 關系數(shù)據(jù)庫的基本概念,9,定義2.3 D1D2Dn的有意義的子集

5、稱為在域D1，D2,Dn上的關系， 記為 R(D1,D2,Dn) 。,其中：R為關系的名；n為關系的度（目）；rR 表示 r 是 R 中的元組。,子集元素是關系中的元組； 關系中的元組個數(shù)是關系的基數(shù); 同樣可以把關系看作是一個二維表：,每一行對應一個元組； 表的每一列對應一個域，每個域起一個名字稱為屬性;,（3）關系,2.1 關系數(shù)據(jù)庫的基本概念,10,例,例：設 D1=男人集合(MAN) = 王強、李東、張兵 D2 =女人集合(WOMAN) = 趙紅、吳芳 D3=兒童集合(CHILD) = 王一、李一、李二 （1）求上面三個集合的笛卡兒積 （2）構造一個家庭關系，可表示為： FAMILY（

6、MAN，WOMAN，CHILD）,2.1 關系數(shù)據(jù)庫的基本概念,11,（4）關系中常用術語 候選碼 主碼 外碼 全碼,2.1 關系數(shù)據(jù)庫的基本概念,12,S(Sno, Cardno, Dno, Sname, Sage, ) D(Dno, Dname, Location),主碼,主碼,外碼,PUR(Cno，Pno，Sno),全碼,參照關系,被參照關系,2.1 關系數(shù)據(jù)庫的基本概念,13,（5）關系的性質(zhì) 每列的值為同一類型。 每列具有不同的屬性名(可同域) 任意兩元組不能完全相同。 行的次序可以互換。 列的次序可以互換。 分量值是原子的。,+5,學號 姓名 年齡,、網(wǎng)蟲,不允許,元組,分量值,屬

7、性名,關系的類型 ： 基本關系（基表） 查詢表 視圖表,2.1 關系數(shù)據(jù)庫的基本概念,14,2、關系模式與關系數(shù)據(jù)庫 定義2.4： 關系的描述稱關系模式，其表示為：R(U，D，Dom，F(xiàn)),關系模式可簡記為關系的屬性名表。 R(U)=R(A1 ，A2，A3，.An) 例：學生（學號，姓名，總成績）,域名集,屬性名集,屬性間的依賴關系集,屬性向域的映像集,關系模式就是關系的框架（表框架） 它是對關系結構的描述,2.1 關系數(shù)據(jù)庫的基本概念,15,在關系模型中，實體以及實體間的聯(lián)系都是用關系來表示。在一個給定的現(xiàn)實世界領域中，相應于所有實體及實體之間的聯(lián)系的關系的集合構成一個關系數(shù)據(jù)庫。 關系數(shù)據(jù)

8、庫也有型和值之分。關系數(shù)據(jù)庫的型也稱為關系數(shù)據(jù)庫模式，是對關系數(shù)據(jù)庫的描述，是關系模式的集合。關系數(shù)據(jù)庫的值也稱為關系數(shù)據(jù)庫，是關系的集合。關系數(shù)據(jù)庫模式與關系數(shù)據(jù)庫通常統(tǒng)稱為關系數(shù)據(jù)庫。,關系數(shù)據(jù)庫,2.1 關系數(shù)據(jù)庫的基本概念,16,術語間的聯(lián)系,一個關系只能對應一個關系模式 一個關系模式可對應多個關系 關系模式是關系的型，按其型裝入數(shù)據(jù)值后即形成關系 關系模式是相對靜態(tài)的、穩(wěn)定的，而關系是動態(tài)的、隨時間變化的 一個具體的關系數(shù)據(jù)庫是若干相關關系的集合,17,1.關系模型的特點及組成 關系模型的特點： 結構簡單，表達力強 語言的一體化 非過程化的操作 堅實的數(shù)學基礎 操作效率較低 關系模型

9、的組成： 關系數(shù)據(jù)結構 關系數(shù)據(jù)操作 關系完整性約束,2. 關系模型的數(shù)據(jù)操作 (1)數(shù)據(jù)查詢 (2)數(shù)據(jù)插入 (3)數(shù)據(jù)刪除 (4)數(shù)據(jù)修改,2.2 關系模型及其描述,18,3. 關系的完整性 三類完整性約束： 實體完整性 參照完整性 用戶定義的完整性,說明： 實體完整性規(guī)則是對基本關系的約束和限定。 實體具有唯一性標識主碼。 主碼屬性不能取空值。,(1) 實體完整性 規(guī)則2.1 實體完整性規(guī)則 : 若屬性A是基本關系R的主碼屬性，則屬性A不能取空值。,不變性 由關系系統(tǒng)自動支持,2.2 關系模型及其描述,是應用領域需要遵循的約束條件,19,(2) 參照完整性 引用關系： 關系中的某屬性的值

10、需要參照另一關系的屬性來取值。 例1：學生(學號，姓名，性別，專業(yè)號，年齡) 專業(yè)(專業(yè)號，專業(yè)名),例2: 學生(學號，姓名，性別，專業(yè)號，年齡，班長),引用,引用,2.2 關系模型及其描述,20,定義2.5 ： 設：基本關系R、S(可為同一關系)。 若F是R的一個(組)屬性，但不是R的碼。 如果F與S的主碼 K相對應，則稱F是R的外碼。 并稱R為參照關系，S為被參照關系（目標關系）。 說明：S的主碼K和R的外碼F必須定義在同一個(或一組)域上。,例1：學生(學號，姓名，性別，專業(yè)號，年齡) 專業(yè)(專業(yè)號，專業(yè)名),被參照關系,參照關系,外碼,參照完整性規(guī)則定義了外碼與主碼之間的引用規(guī)則。,

11、2.2 關系模型及其描述,21,規(guī)則2.2 參照完整性規(guī)則 若屬性(組) F是R的外碼且它與S的主碼K相對應，則對于R中每個元組在F上的值必須為： 或者取空值(F的每個屬性值均為空值)； 或者等于S中某個元組的主碼值。 例1：學生(學號，姓名，性別，專業(yè)號，年齡) 關系中每個元組的專業(yè)號取值： 空值(未給該學生分配專業(yè))； 非空值(是專業(yè)關系中某個元組的專業(yè)號值)。,2.2 關系模型及其描述,22,例2：職工EMP(EMP#,ENAME,JOB,DEPT#) 部門DEPT(DEPT#,DNAME,LOC) 則：EMP中的DEPT#為空或為DEPT中的DEPT#的值,(3) 用戶定義的完整性,用

12、戶自定義完整性是針對某一具體數(shù)據(jù)的約束條件，反映某一具體應用所涉及的數(shù)據(jù)必須滿足的語義要求，由應用環(huán)境決定。,例： 屬性的取值范圍 屬性的非空限制,2.2 關系模型及其描述,23,關系數(shù)據(jù)語言的分類 （1）關系代數(shù)語言 用對關系的運算來表達查詢要求方式的語言。 （2）關系演算語言 用謂詞來表達查詢要求方式的語言。 元組關系演算語言 域關系演算語言 （3）結構化查詢語言 （SQL) 具有關系代數(shù)和關系演算雙重特點的語言,2.3 關系代數(shù),24,關系查詢語言,關系代數(shù)語言：查詢操作是以集合操作作為基礎的語言 關系演算語言：查詢操作是以謂詞演算作為基礎的語言,關系查詢語言是一種比Pascal、C等程

13、序設計語言更高級的語言。 Pascal、C、關系代數(shù)語言屬于過程性語言，在編程時必須給出獲得結果的操作步驟。 而關系演算語言屬于非過程性語言，編程時只需要指出需要什么信息，不必給出具體的操作步驟。,干什么？ 怎么干？,干什么？,2.3 關系代數(shù),25,2.3 關系代數(shù),關系代數(shù)、元組關系演算和域關系演算三種語言在表達能力上是完全等價的。 關系代數(shù)、元組關系演算和域關系演算都是抽象的查詢語言，與實際DBMS中實現(xiàn)的語言（SQL）不完全一樣，可以用來評估實際系統(tǒng)中查詢語言的能力 關系數(shù)據(jù)語言表達能力完全相同、非過程化、功能強且可嵌入使用,26,關系代數(shù)語言的組成,關系代數(shù)語言是通過對關系的運算來表

14、達查詢，通過對關系進行“分割”或者“重組”，得到新的關系 關系代數(shù)以元組的集合為運算對象，通過各種運算形成新的元組集合 關系運算分為： 集合運算 關系運算 擴充的關系運算,27,1.集合運算 關系代數(shù)是一種抽象的查詢語言。它以關系為運算對象，通過對關系進行“組合”或“分割”，得到所需的數(shù)據(jù)集合關系。 分類： 集合運算（并、交、差；廣義笛卡爾積） 關系運算 （投影、選擇、連接和除運算）,設：t 為元組變量；R、S為同類關系(同元、相應屬性同域）； 下列運算結果為同類關系： (1)并運算: RUS =t |（tR）（t S） (2)差運算: R-S=t |（tR）（t S） (3)交運算: RS=

15、t |（tR）（t S）,R,S,2.3 關系代數(shù),28,關系的集合運算實例,29,(4)廣義笛卡爾積: R、S可為不同類關系，則結果為不同類關系： RS=tr ts|（trR）（ts S）,連接為 m+n目關系,m目關系,n目關系,2.3 關系代數(shù),30,元組的前n列是關系R的一個元組 后m列是關系S的一個元組,2.3 關系代數(shù),31,記號 設t為R的元組變量，設：R（A1，A2，An) = R(U) tAi (Ai為屬性)： R在屬性Ai上的所有值。 tA (A為屬性集)，R在屬性集A上的所有值。 例：t學號 -R中學號上的值 t 學號，姓名,學號 姓名 年齡,t,2.3 關系代數(shù),32,

16、2.專門的關系運算 （1）選擇 是行上的選擇，產(chǎn)生同類關系。 F(R)=t|(tR)F(t)=true 含義：由R中滿足F條件的元組組成。 其中：F由屬性名（值）、比較符、邏輯運算符組成。 例： A25 A3 “f”(R) 或： 25 3 “f”(R) 選擇運算是從行的角度進行的運算, 25 3 “f”(R),2.3 關系代數(shù),33,（2）投影運算 是列上的選擇，產(chǎn)生不同類關系。 A(R)=tA |(tR) 含義：R中取屬性名表A中指定的列，消除重復元組。 例： A3，A2(R),2.3 關系代數(shù),34,投影操作主要是從列的角度進行運算,用關系代數(shù)表示查詢： 例：查選2號課程的學生記錄。 例:

17、 成績在90分以上的學生號。,解： Cno=2(SC),解: Sno(Grade90(SC),2.3 關系代數(shù),35,（3）連接運算： 一般連接 它從兩個關系的笛卡爾積中選取屬性間滿足一定條件的元組。 R S=tr ts|(trR)(tsS)trA tsB,比較運算符,含義： 從R X S中選取R關系在A屬性組上的值與S關系在B屬性組上值滿足關系的元組。,2.3 關系代數(shù),36,A B,= R. A S. B(RS),連接舉例,R S,CE,37,X,連接 = 笛卡爾積 + 選擇, 等值連接：為“=”的連接。 為“”的連接運算稱為等值連接 等值連接的含義 從關系R與S的廣義笛卡爾積中選取A、B

18、屬性值相等的那些元組，即等值連接為： R S = | tr Rts StrA = tsB ,2.3 關系代數(shù),38,R S,R.B=S.B,等值連接舉例,39, 自然連接 設R、S有同名屬性集B R S= tr ts|(trR)(tsS)trB = tsB,其中B是R和S的公共屬性（同名屬性組），并且在形成的新關系中要去掉重復的屬性。 特殊的等值連接，要求兩個關系中進行比較的分量必須是同名屬性組,2.3 關系代數(shù),40,R S,自然連接舉例,R S,R.B=S.B,41,等值連接與自然連接的區(qū)別： （1）自然連接一定是等值連接，但等值連接不一定是自然連接。因為自然連接要求相等的分量必須是公共屬

19、性，而等值連接相等的分量不一定是公共屬性。 （2）等值連接不把重復的屬性去掉，而自然連接要把重復屬性去掉。,注意,若R、S無公共屬性，R S=？,2.3 關系代數(shù)連接,42,R S= tr ts|(trR)(tsS)trB = tsB,回憶：關系的“乘”運算 廣義笛卡爾積 R(X)乘以S(Y)：把X屬性組上的每一種取值都與Y屬性組上的每一種取值組合在一起,（4）除運算,2.3 關系代數(shù),43,被除數(shù),商(X),除數(shù)(Y),關系的除運算可以看成是“乘”運算的逆運算,（4）除運算,2.3 關系代數(shù),44,余數(shù)？,象集（Image Set） 關系R(X , Z), X, Z是屬性組，x是X上的取值，

20、定義x在R中的象集為 Zx=tZ|tRtX=x 從R中選出在X上取值為x的元組，去掉X上的分量，只留Z上的分量,X Z,張軍同學所選修的全部課程,x=張軍,Zx,（4）除運算,2.3 關系代數(shù),45,選擇 + 投影,做法：逐個考慮選課關系SC中的元組r，求r在姓名SN上的分量x，再求x在選課關系中的象集課程Cx，若Cx包含了所有的課程C，則x是滿足條件的一個元組, x | x=rSN rSC CxC ,選修全部課 程的學生,全部課程,x同學所選修 的全部課程,除定義: R(X,Y) S(Y) = trX | trRY(S)Yx 其中Yx為x在R中的象集, x=trX,除運算,如何得到選修了全部

21、課程的學生？,2.3 關系代數(shù),46,2.3 關系代數(shù),設關系R(X，Y)和S(Y，Z)，X，Y，Z為屬性組 RS=tX|tR y(S)Yx , X(R) Yx為x在R中的象集: 對于每個值x， xX(R) 求：y (X=x(R) 結果為：象集Yx包含了y(S)的x。,關系代數(shù)定義了除運算。但實際應用中，當關系R真包含了關系S時，RS才有意義。 R能被S除盡的充分必要條件是： R中的屬性包含S中的所有屬性；R中有一些屬性不出現(xiàn)在S中。 設R為r元、S為s元關系(rs0)，當關系R真包含了關系S時，RS可用下式計算： RS =1,2,r-s(R)-1,2,r-s(1,2,r-s(R)S)-R)

22、【例2.8】設R(S#,P#)、W1(P#)、W2(P#)、W3(P#)。 則RW1可表示為： S#(R)-S#(S#(R)W1)-R) 同理可列出另外兩式。,R,S,2.3 關系代數(shù),（4）除運算,例RWi的運算結果可理解為： R中包含Wi屬性值的那些元組在R與Wi的屬性名之差（即S#）上的投影。,2.3 關系代數(shù),示例 求同時選修了001和002號課程的學生號 方案1： S#，C#(SC) C# = 001 C# = 002 (C) 方案2： S#(SC C# = 001 C# = 002 (C) 哪一個正確？,2.3 關系代數(shù),50,S#，C#(SC) C# = 001 C# = 002

23、 (C),2.3 關系代數(shù),51,S#(SC C# = 001 C# = 002 (C),2.3 關系代數(shù),52,X = S#, Grade,=,R,AB (R),S,AB (R) CD (S),AB (R) CD (S)-R,R S=,-,=,2.3 關系代數(shù),53,R(X,Y) S(Y)=X(R) X(X(R) Y (S) - R ),Student,2.3 關系代數(shù)(綜合舉例）,54,Course,2.3 關系代數(shù)(綜合舉例）,55,SC,2.3 關系代數(shù)(綜合舉例）,56,2.2 關系代數(shù),例: 查詢至少選修了一門其直接先行課為005號課程的學生名。,學生-課程數(shù)據(jù)庫表見教材: S(s

24、no，sname，sex，age，dept) C(cno，cname， credit ， pcno) SC(sno，cno，grade),sname(pcno=005 (C SC S),A(F (R),例：查選修002號課程的學生姓名與年齡。 sname,age(S cno=002 (SC),例1：查不選002號課程的學生姓名與年齡。,Cno002 ?,sname,age(S)- sname,age(S cno=002 (SC),2.3 關系代數(shù)(綜合舉例）,sname,age(S cno 002 (SC),58,例2：查詢至少選修了兩門課程的學生學號。,sno(1=425(SCSC),2.3

25、 關系代數(shù)(綜合舉例）,59,例3：查所選課程包含了學生210101所選全部課程的學生號和姓名。,sno,sname(S) (sno，cno(SC) cno (sno=210101 (SC),例4：查詢選修了全部課程的學生學號與姓名。,sno,sname(S) (sno，cno(SC) cno(C),2.3 關系代數(shù)(綜合舉例）,60,例9查詢至少選修了一門其直接先行課為5號課程的課程的學生姓名。 Sname(Cpno=5(Course SC Student) 或 Sname(Cpno=5(Course)SCSno，Sname(Student) 或 Sname(Sno(Cpno=5(Cours

26、e)SC)Sno，Sname (Student),2.3 關系代數(shù)(綜合舉例）,61,2.3 關系代數(shù),關系代數(shù)五種基本運算： 投影,選擇,并,差,笛卡爾積 5種基本運算的作用： 1)關系的屬性指定 A1 , A2 , , An (R) 2)關系的元組選擇 F (R),3)兩個關系的歸并 R1R2 4)關系中元組的插入 R1R2 5)關系中元組的刪除 R1R2,3.擴充的關系運算 （1）廣義投影 F1,Fn(R)，其中，F(xiàn)1,Fn是涉及R中常量和屬性的算術表達式。 例：sno,sname,sex,age=20(sno=200101(Student) （2）賦值 RS: 將關系S賦予R。 例：C

27、ourse Course099，電子商務，2，003（并） Student Student-(sno=200108(Student) （刪除）,2.3 關系代數(shù),63,(3) 外連接 為避免自然連接時因失配而發(fā)生的信息丟失，可以假定往參與連接的一方表中附加一個取值全為空值的行，它和參與連接的另一方表中的任何一個未匹配上的元組都能匹配，稱之為外連接 外連接 = 自然連接 + 失配的元組 外連接的形式：左外連接、右外連接、全外連接 左外連接 = 自然連接 + 左側表中失配的元組 右外連接 = 自然連接 + 右側表中失配的元組 全外連接 = 自然連接 + 兩側表中失配的元組,2.3 關系代數(shù),64,

28、外連接例子,65,（4）半連接 R和S的自然連接只在關系R或關系S的屬性集上的投影， 稱為半連接。 R和S的半連接記為R S。 S和R的半連接記為S R。 （5）聚集 根據(jù)關系中的一組值做統(tǒng)計、計算得到一個值作為結果。 常用聚集函數(shù)：max、min、avg、sum、count。 形式：G 聚集函數(shù)名(屬性)(關系),2.3 關系代數(shù),66,例：求男同學的平均年齡。 G avg(age)(sex=男(Student) 例：計算年齡不小于20歲的同學人數(shù)。 G count(sno)(age20(Student) 例：數(shù)據(jù)庫課程的平均分數(shù)。 G avg(grade)(cno(cname=數(shù)據(jù)庫(Co

29、urse) SC) （6）外部并 由R和S中的所有屬性組成(公共屬性只取一次)，其元組由屬于R或屬于S的元組組成，且元組在新增加的屬性填上空值。,2.3 關系代數(shù),67,外部并例子,68,（7）重命名 x(E)：其含義為給一個關系表達式賦予名字。它返回表達式E的結果，并把名字x賦給E。 x(A1，A2，An)(E):其含義為返回表達式E的結果，并把名字x賦給E，同時將各屬性更名為A1，A2，An。 例：設關系R(姓名，課程，成績)，求數(shù)學成績比王紅同學高的學生。 S.姓名(課程=數(shù)學姓名=王紅(R)(課程=數(shù)學S(R) R.成績S.成績,2.3 關系代數(shù),69,關系演算：以謂詞演算為基礎表示的

30、關系運算。 關系演算分類 元組關系演算 域關系演算 1. 元組關系演算 用 t|(t) 表示關系。,命題公式,元組變量,表示所有使得為真的元組組成的集合。,2.4 關系演算,70,（1）元組關系演算中的原子公式 R(t) t元組變量 R關系名 R(t)表示：t是關系R的一個元組。 關系R可表示為：t|R(t) tiC 或 Cti C常量 表示：元組t的第i個分量與常量C之間滿足關系。 tiuj 其中：t，u元組變量 算術比較符 tit的第i個分量 uju的第j個分量 tiuj表示：元組t的第i個分量與元組u的第j個分量之間滿足關系。,2.4 關系演算-元組演算,71,（2）公式的遞歸定義 每個

31、原子公式是公式。 若1和2是公式，則1、12、12也是公式。 若是公式，則(t)()、(t)()也是公式。 有限次使用上述3條規(guī)則得到的公式都是元組關系演算表達式。 公式中各種運算符的優(yōu)先級： 算術運算符、量詞()、邏輯運算符( ),高,低,括號優(yōu)先,2.4 關系演算-元組演算,72,關系代數(shù)表達式,關系演算表達式, 用關系演算表達式表達五種基本運算：,RS= t | R(t)S(t) ,RS= t | R(t) S(t) ,RS = t(n+m) | ( u(n) ) ( v(m) ) ( R(u) S(v) t1=u1 tn=un tn+1=v1 tn+m=vm ) ,F (R) = t

32、| R (t) F ,i1, i2, , ik (R) = t(k) | ( u) (R(u) t1=ui1 tk=uik ),2.4 關系演算關系代數(shù),73,例1 查詢信息系（IS）全體學生,F (R) = t | R (t) F ,SIS= t | Student(t) t5=IS ,例2 查詢年齡小于20歲的學生,S20= t | Student(t) t420 ,2.4 關系演算關系代數(shù),74,例3 查詢學生的姓名和所在系,S1= t(2) | ( u) （Student(u) t1=u2 t2=u5）,i1, i2, , ik (R) = t(k) | ( u) (R(u) t1=u

33、i1 tk=uik ),2.4 關系演算關系代數(shù),75,例2：設R和S都是二元關系，將1,4(2=3(RS)轉換成元組演算表達式。,t|(u)(v)(R(u)S(v)u2=v1t1=u1t2=v2),2.4 關系演算-元組演算,76,例1：設有關系R和S，請寫出下列元組演算表達式的結果。,R,S,R1=t|S(t)t12 R2=t|R(t) S(t) R3=t|(u)(S(t)R(u)t3u1),2.4 關系演算-元組演算,2.4 關系演算-域演算,78,2.域關系演算 以域變量作為謂詞變元的基本對象。 用t1,t2,tk|(t1,t2,tk)表示關系。 t1,t2,tk是元組變量t的各個域分

34、量。 （1）域演算中的原子公式 R（ t1,t2,tk) 表示：由分量t1,t2,tk組成的元組屬于R。 tiuj 表示：元組變量t的第i個分量與元組u的第j個分量間滿足關系。 tiC 或 Cti 表示：元組變量t的第i個分量與常量C間滿足關系。 （2）公式的遞歸定義 與元組演算定義類似。,例：設有關系R、S、W，試寫出下列域演算表達式的結果。,R,W,S,R1=xyz|R(xyz)x3 R2=xyz|R(xyz)S(xyz)y=8 R3=xyz|(u)(v)(R(zxu)W(yv)uv),2.4 關系演算-域演算,79,2.4 關系演算-域演算,用域演算表達式表示下列查詢： （1）查詢女學生

35、的情況。 R1=t1t2t3t4t5|Student(t1t2t3t4t5)t3=女 （2）查詢學號為220101的學生選修的課程在85分以上的課程號。 R2=t2| (t1) (t3) (SC(t1t2t3) t1=220101 t385 ) （3）查詢選修課程號為003的所有學生的學號和姓名。 R3=t1t2| (t1) (u2) (Student(t1t2t3t4t5) SC(u1u2u3) t1=u1 u2=003 ),安全運算 不產(chǎn)生無限關系和無窮驗證的運算。 安全表達式 安全運算的表達式。 安全限制 安全運算所采取的措施。,關系代數(shù)運算總是安全的。關系演算則可能出現(xiàn)無限關系和無窮驗

36、證問題,3.關系演算的安全性,例：t|R(t),這是一個無限關系。,要使關系演算是安全的，只要定義一個安全約束有限集合，該有限集是表達式中涉及到的關系中的值的集合。經(jīng)過安全限制后的表達式其運算是安全的。,關系代數(shù)和關系演算所依據(jù)的基礎理論是相同的，故可進行相互轉換。已證明，關系代數(shù)、安全的元組演算、安全的域演算在關系的表達能力上是等價的。,2.4 關系演算,81,2.5 查詢優(yōu)化,數(shù)據(jù)查詢是DBS中最基本、最常用和最復雜的數(shù)據(jù)操作，查詢優(yōu)化是影響關系DBMS性能的關鍵因素。 關系數(shù)據(jù)理論基于關系代數(shù)，同一個查詢要求可以對應多個不同形式卻相互等價的表達式。 關系數(shù)據(jù)查詢語言是非過程化的，由DBM

37、S自動生成若干候選的查詢計劃并擇優(yōu)使用。,82,2.5 查詢優(yōu)化,1.關系DB的查詢優(yōu)化及其目標 查詢優(yōu)化：從查詢的多個執(zhí)行策略中進行合理選擇的過程。 目標：選擇有效的策略，求得關系式的值，以提高其查詢效率。 基本途徑可以分為兩種：用戶處理和機器自動處理 查詢優(yōu)化器： 由DBMS自動生成并從中選取較優(yōu)查詢計劃的程序。 查詢的開銷主要包括： 在單機數(shù)據(jù)庫中：總代價 = I/O代價 + CPU代價 在多用戶環(huán)境下：總代價 = I/O代價 + CPU代價 + 內(nèi)存代價 在網(wǎng)絡環(huán)境下： 總代價 = + 網(wǎng)絡代價 查詢的執(zhí)行開銷與多個因素有關： 軟件環(huán)境、硬件環(huán)境、數(shù)據(jù)量、方法。,2.5 查詢優(yōu)化,關系

38、數(shù)據(jù)庫查詢過程：,為什么要查詢優(yōu)化？,例: Student表有l(wèi)03個學生記錄，每人平均選10門課， SC表共有1000*10=l04個選課記錄。要求: 查學生“王林”選課成績在85分以上的課程號。 SELECT cno FROM S，SC WHERE S.sno=SC.sno AND sname=王林 AND grade 85 ；,等價的關系代數(shù)表示： cno( F1 F2 F3 ( SSC ) ) cno( F2 F3 ( S SC ) ) cno(F2 (S) F3 (SC) ),哪種效率高？,連接時間復雜度為： 103104=O(107) 10310=O(104) 110=O(101)

39、,對執(zhí)行基本運算(關系掃描與連接)的次數(shù)進行分析：, cno( F1 F2 F3 ( SSC ) ) cno( F2 F3 ( S SC ) ) cno( F2 (S) F3 (SC) ) 先在兩表上做 ，產(chǎn)生1000*10000=107個連接記錄，再在其上進行先后操作。其基本運算的次數(shù)為：3*107。 先在兩個表上做 ，產(chǎn)生1000*10=104個連接記錄，再在其上進行先后操作。其基本運算的次數(shù)為：107+2*104。 先分別在兩個表上做,再做 ，產(chǎn)生1*10=10個連接記錄，再在其上進行 。其基本運算的次數(shù)為：104+103+2*101。,連接時間復雜度為： O(107) O(104) O

40、(101),2.5 查詢優(yōu)化,查詢處理包括三個基本步驟： 解析和翻譯 優(yōu)化 實現(xiàn)（求值）,解析和翻譯 解析：檢查語法、驗證關系 翻譯：將查詢轉化為內(nèi)部形式，并進一步翻譯為關系代數(shù) 實現(xiàn) 執(zhí)行引擎選取一個查詢計劃并執(zhí)行，而后將結果返回給查詢.,87,2.5 查詢優(yōu)化,查詢優(yōu)化技術的分類： 規(guī)則優(yōu)化：根據(jù)某些啟發(fā)式規(guī)則，如“先選擇，后投影”來完成優(yōu)化。特點是對查詢的關系代數(shù)表達式進行等價變換，以減少執(zhí)行開銷，也稱為代數(shù)優(yōu)化 物理優(yōu)化：根據(jù)數(shù)據(jù)的物理組織和訪問路徑進行優(yōu)化，如用索引進行優(yōu)化，也稱物理優(yōu)化 代價估算優(yōu)化：對于多個候選策略逐個進行執(zhí)行代價估算，從中選擇代價最小的作為執(zhí)行策略，稱為代價估算

41、優(yōu)化,88,2.查詢優(yōu)化的一般策略 當前一般都采用先代數(shù)優(yōu)化、后物理優(yōu)化的方法。 代數(shù)優(yōu)化的基本原理是對關系代數(shù)表達式進行等價變換，選擇其中代價最小的。 基本原則就是盡量減少查詢過程中產(chǎn)生的中間結果，從而換取較小的時空開銷。,89,2.5 查詢優(yōu)化,(1)盡可能先做選擇運算、投影運算 這是優(yōu)化策略中最重要、最基本的一條。 可以有效降低中間結果的數(shù)量，常?？墒箞?zhí)行時間節(jié)約幾個數(shù)量級。,90,2.5 查詢優(yōu)化,(2)合并笛卡爾積與其后的選擇為連接運算 把要執(zhí)行的笛卡爾積與在它后面要執(zhí)行的選擇結合起來成為一個連接運算，連接特別是等值連接要比笛卡爾積節(jié)省很多時間。 R.AS.C(RS)=R S AC,

42、91,2.5 查詢優(yōu)化,(3)把投影運算和選擇運算同時進行 如果有若干投影和選擇運算，且是對同一個關系執(zhí)行，則可以在掃描關系的同時進行投影和選擇運算，避免重復掃描關系 sno(grade=90(SC),92,2.5 查詢優(yōu)化,(4)讓投影運算和其前后的其他運算同時進行 把投影同其前后的雙目運算結合起來，不必為了去掉某些列而專門掃描關系 sno(S1-S2) S1 sno(S2),93,2.5 查詢優(yōu)化,(5)在執(zhí)行連接前對關系適當?shù)念A處理 預處理主要有兩種：索引連接、歸并連接 如：經(jīng)過排序后的R和S進行連接時，時間復雜度大大降低，從O(m*n)到O(m+n) (6)尋找公共子表達式 如果某個子

43、表達式常常出現(xiàn)，并且將其結果放在外存中的代價小于計算它的代價，則將其計算一次，并放入中間文件中。,94,2.5 查詢優(yōu)化,2.5 查詢優(yōu)化,3. 關系代數(shù)表達式的轉換 如果在每個合法的數(shù)據(jù)庫實例上, 兩個關系代數(shù)表達式都生成同樣的元組集合, 則這兩個關系代數(shù)表達式稱為等價的 注意: 元組次序是無關的 等價規(guī)則說明了兩種形式的表達式是等價的 可以用一個表達式替換另一個 12條等價規(guī)則,95,1.連接、笛卡爾積交換律 E1E2 E2E1 E1 E2 E2 E1 E1 E2 E2 E1 F F 2.連接、笛卡爾積的結合律 (E1E2) E3 E1(E2E3) (E1 E2) E3 E1 (E2 E3

44、) (E1 E2) E3 E1 (E2 E3) F1 F2 F1 F2,96,2.5 查詢優(yōu)化,3.投影的串接律 條件：t1是t2、 tn的子集 說明：多個投影中，只有最后一個運算是必須的 4.選擇的串接律 說明：多個連續(xù)的條件可以合并成一個，這樣可以一次檢查所有條件；同樣，合取選擇運算可以分解為多個選擇運算，便于和其他運算重新組合,97,2.5 查詢優(yōu)化,5.選擇與投影的交換律 形式（1） 說明：其中選擇條件F只涉及屬性A1,A2,An 形式（2） 意義：將條件F中涉及的屬性的投影前移，以便投影和其他運算合并 6.選擇與笛卡爾積的交換律 如果F中涉及的屬性都是E1中的屬性：,98,2.5 查

45、詢優(yōu)化,如果F=F1F2，F(xiàn)1只涉及E1中的屬性，F(xiàn)2只涉及E2中的屬性： 如果F1只涉及E1中的屬性，F(xiàn)2涉及E1和E2中的屬性： 該規(guī)則使得選擇盡量能在笛卡爾積之前先做，減小中間結果集。 7.選擇與并的交換律 設E1、E2有相同的屬性名：,99,2.5 查詢優(yōu)化,8.選擇與差的交換律 設E1、E2有相同的屬性名： 9.投影與笛卡爾積的交換 設A1,An是E1的屬性，B1,Bm是E2的屬性： 這個策略使投影在笛卡爾積之前先做 10.投影與并的交換 設E1和E2有相同的屬性名,100,2.5 查詢優(yōu)化,11.選擇對自然連接的分配律 如果F中涉及的都是E1的屬性： （1）F (E1 E2) F (E1 ) E2 如果F=F1F2，F(xiàn)1只涉及E1中的屬性，F(xiàn)2只涉及E2中的屬性： （2）F (E1 E2) F1 (E1 )