數(shù)據(jù)庫系統(tǒng)原理-第五章 代數(shù)和邏輯查詢語言

1、第第5章章 代數(shù)和邏輯查詢語言代數(shù)和邏輯查詢語言 5.1 關系代數(shù)操作5.2 包上的關系操作5.3 關系代數(shù)的擴展操作符5.4 關系邏輯5.5 關系代數(shù)與DatalogPage 15.1 關系代數(shù)操作關系代數(shù)操作(1) 關系代數(shù)的傳統(tǒng)定義關系代數(shù)的傳統(tǒng)定義 一個元組集合一個元組集合(即關系即關系)，能用來進行典型的基于關系的，能用來進行典型的基于關系的查詢查詢 集合上的五個操作：并、差、笛卡爾積、選擇、投集合上的五個操作：并、差、笛卡爾積、選擇、投影影 在基本操作上定義的附加操作：各種連接在基本操作上定義的附加操作：各種連接 關系代數(shù)的操作規(guī)則對于集合和包是不一樣的關系代數(shù)的操作規(guī)則對于集合和

2、包是不一樣的 簡單的說，包是以空間代價換取時間效率簡單的說，包是以空間代價換取時間效率所以對一般小例子來說，包的綜合效率更高所以對一般小例子來說，包的綜合效率更高但對實際應用中的數(shù)據(jù)庫來說，用集合更加合理但對實際應用中的數(shù)據(jù)庫來說，用集合更加合理Page 25.1 關系代數(shù)操作關系代數(shù)操作(2) 關系中的集合操作關系中的集合操作 基本集合操作：并、交、差基本集合操作：并、交、差 應用到關系操作時，需要附加約束應用到關系操作時，需要附加約束 屬性列表和屬性類型必須一致屬性列表和屬性類型必須一致 屬性的排列順序也要一致屬性的排列順序也要一致 原則上屬性名也要對應一致，如果不一致，需要原則上屬性名也

3、要對應一致，如果不一致，需要利用重命名操作處理利用重命名操作處理Page 35.1 關系代數(shù)操作關系代數(shù)操作(3) 投影投影A1,A2,An(R) 只保留指定部分列只保留指定部分列 由于屬性減少，元組可能會重值，進而合并，因由于屬性減少，元組可能會重值，進而合并，因此數(shù)目可能減少此數(shù)目可能減少 選擇選擇C(R) 該操作產生的新關系的元組必須滿足條件該操作產生的新關系的元組必須滿足條件C 結果關系和原關系的模式相同結果關系和原關系的模式相同Page 45.1 關系代數(shù)操作關系代數(shù)操作(4) 笛卡爾積笛卡爾積 RS 一個有序對的集合，有序對的第一個元素來自一個有序對的集合，有序對的第一個元素來自R

4、，第二個，第二個元素來自元素來自S 一般地，笛卡爾積對應一個關系，其元組維度更大，一般地，笛卡爾積對應一個關系，其元組維度更大，個數(shù)更多個數(shù)更多 如果如果R和和S有重名屬性，則在結果中加前綴區(qū)分有重名屬性，則在結果中加前綴區(qū)分 連接操作連接操作 參與連接操作的一般是兩個關系，且連接時相應的元組參與連接操作的一般是兩個關系，且連接時相應的元組在某些方面具有一致性，連接分為三類在某些方面具有一致性，連接分為三類 全連接即笛卡爾積全連接即笛卡爾積 自然連接自然連接 連接連接Page 55.2 包上的關系操作包上的關系操作(1) 一組元素的一種聚集形式，允許重復元素出現(xiàn)，一組元素的一種聚集形式，允許重

5、復元素出現(xiàn)，而集合而集合setset中不允許元素重復出現(xiàn)。中不允許元素重復出現(xiàn)。 對一個包去掉其中重復元素，就可得到一個集合對一個包去掉其中重復元素，就可得到一個集合。 一個集合可認為是一個特殊的包，其中沒有重復一個集合可認為是一個特殊的包，其中沒有重復元組。元組。什么是包什么是包bagbagPage 6 關系看作為集合，則不允許有重復元組，如果看作為包，則允許有重復元組。AB12341212AB1234包包集合集合5.2 包上的關系操作包上的關系操作(1)Page 7為何需要包為何需要包 關系中的元組應該不重復，但經運算得到的新關關系中的元組應該不重復，但經運算得到的新關系中的元組可以重復；

6、數(shù)據(jù)庫系統(tǒng)支持系中的元組可以重復；數(shù)據(jù)庫系統(tǒng)支持 提高投影計算效率提高投影計算效率 對聚合運算有用對聚合運算有用( (匯總值、平均值、計數(shù)等匯總值、平均值、計數(shù)等) )Page 8例子 商業(yè)DBMS實現(xiàn)的都是包，為什么呢？包的實現(xiàn)效率較高。 包的并操作和投影操作實現(xiàn)簡單例如：對下面關系在A、B屬性上的投影A BC125346127128AB12341212AB1234包包集合集合Page 9例子 例如：對下面關系R，要求A屬性的平均值，則先對A屬性投影，如果允許結果為包，則均值為1.5，否則為2(錯)。A BC125346127128A1311A13包包集合集合Page 105.2 包上的關系

7、操作包上的關系操作(2) 包上的運算：并包上的運算：并( (交、差交、差) )、投影、選擇、乘積和、投影、選擇、乘積和連接等都允許運算之前和之后元組重復連接等都允許運算之前和之后元組重復 對兩個關系求并，集合方式要先合并再去重，而包方對兩個關系求并，集合方式要先合并再去重，而包方式只合并不去重，所以效率更高式只合并不去重，所以效率更高 投影操作后不去重投影操作后不去重 對后面要出現(xiàn)的聚集操作來說，只能用包方式，用集對后面要出現(xiàn)的聚集操作來說，只能用包方式，用集合方式的話會出現(xiàn)邏輯錯誤。合方式的話會出現(xiàn)邏輯錯誤。Page 11 包的并、交、差包的并、交、差 設設R和和S是包，若元組是包，若元組t

8、在在R和和S中分別出現(xiàn)中分別出現(xiàn)n次和次和m次次（這里的（這里的m和和n可以是可以是0），則：），則： R S的包并操作結果中：元組的包并操作結果中：元組t出現(xiàn)出現(xiàn)m+n次；次； R S的包交操作結果中：元組的包交操作結果中：元組t出現(xiàn)出現(xiàn) min (m, n)次；次； R-S的包差操作結果中：元組的包差操作結果中：元組t出現(xiàn)出現(xiàn) max(0, n-m)次；次； /減后為負數(shù)則取減后為負數(shù)則取0Page 12 包的并、交、差舉例：設關系包的并、交、差舉例：設關系R、S如下：如下：AB13112422AB13352446nRS：AB1311133524222446nRS：AB1324nR- -S

9、：AB1122R =S =Page 135.2 包上的關系操作包上的關系操作(2) 集合上的包操作（文本框內容釋義）集合上的包操作（文本框內容釋義） 如果對兩個集合如果對兩個集合R、S進行基于包的交和差操作，其結進行基于包的交和差操作，其結果與集合方式運算一樣果與集合方式運算一樣 因為作為被處理對象的兩個關系本身沒有重復的元因為作為被處理對象的兩個關系本身沒有重復的元組，所以交或差之后結果中仍然沒有重值元組組，所以交或差之后結果中仍然沒有重值元組 但對兩個集合但對兩個集合R和和S，進行基于包的并操作，其操作結，進行基于包的并操作，其操作結果可能不再是集合果可能不再是集合 結論：必須看清（答題）

10、結論：必須看清（答題）/聲明（出題）是包方式還是聲明（出題）是包方式還是集合方式集合方式Page 14如果在投影操作過程中，產生了多個同樣的元組，那些重復的元組將不會被從包投影結果中除去。如對enroll表的cid投影包包關系關系5.2 包上的關系操作包上的關系操作(3)Page 15舉例RAB 125612 A (R) =A151Page 16如果在進行選擇操作時，要獨立地對每個元組應用選擇條件。在結果中不去除重復元組RC6(R)ABC125346127127ABC3461271275.2 包上的關系操作包上的關系操作(4)Page 17舉例RAB 125612 A+B 5 (R) = AB

11、1212Page 18一個關系中的每個元組與另一個關系中的每個元組配對，而不問這個元組是否重復出現(xiàn)RRSAB1212A R.B S.B C122312451245122312451245BC234545S5.2 包上的關系操作包上的關系操作(5)Page 19舉例RAB SBC 1234567812R S =AR.BS.BC123412785634567812341278Page 20包的連接操作也跟預想的一樣，首先對比兩個關系中的元組，看是否能組成一對，如果能，則配對起來的元組就是結果關系中的一員。RR SAB1212BC234545SABC1231235.2 包上的關系操作包上的關系操作(

12、6)Page 21連接如下：RR R.BS.B SAB1212A R.B S.B C1245124512451245BC234545S5.2 包上的關系操作包上的關系操作(6)Page 22舉例RAB SBC 1234567812R R.B=2(cname,avg(grade)avggrade,count(sno)snum(course sc)Page 32是的特殊情況如果R(A1，A2，An)是關系，則A1，A2，An(R)與(R)等價。Page 33舉例參演關系如下：starsin(title, year, starname) 找出至少出演了三部電影的影星，以及他們在電影中出現(xiàn)的最早年份s

13、tarname,minyear(cttitle=3(starname,MIN(year)minyear,count(title)cttitle(starsin)Page 34 擴展的投影操作符擴展的投影操作符 L(R) L(R)，其中L是R的一些屬性序列。L的組成可以做如下擴展：R的屬性；形如：xy，x是R的屬性，y為結果模式中的新屬性名；Ez，E是表達式，z是表達式E計算結果的屬性的新名字。如：a+bx，表示a和b屬性的和并生命名為xPage 35舉例令R關系如下：ABC125346127127那么那么A,B+CX(R)為為：AX173101919Page 36舉例令R關系如下：ABC125

14、346127127那么那么B-AX,C-BY(R)為為：XY13121515Page 37舉例令R關系如下：ABC125346127127那么那么A,B+CX(R)為為：AX173101919Page 38舉例令R關系如下：ABC125346127127那么那么B-AX,C-BY(R)為為：XY13121515Page 39排序操作符有時人們希望對關系中的元組按照一個或多個屬性值排序。L(R)，L是R中某些屬性的列表，對R中的元組按照L列出的屬性排序，作為結果返回。如果L是A1,A2,An，那么R的元組就先按屬性A1的值排序，對于A1屬性相等的元組就按A2的值排序，依此類推。Page 40舉例

15、令R關系如下：ABC125346227127那么那么B,C,A(R)為為：ABC125127227346Page 41外連接外連接 連接操作的缺陷連接操作的缺陷 連接操作的一個性質是可能產生連接操作的一個性質是可能產生懸掛元組。懸掛元組。而而這些元組不能跟另外關系的任何一個元組匹配，這些元組不能跟另外關系的任何一個元組匹配，所以這種連接操作并不能完全反映原始關系的全所以這種連接操作并不能完全反映原始關系的全部信息。部信息。 什么是外連接什么是外連接 先計算兩個關系先計算兩個關系R和和S的自然連接，然后再把來的自然連接，然后再把來自自R或或S的懸浮元組加入其中，用的懸浮元組加入其中，用null符

16、號符號 補齊結補齊結果元組中那些不具有值的屬性。我們稱之為果元組中那些不具有值的屬性。我們稱之為外連外連接，接，用符號用符號 表示。表示。Page 42設有關系設有關系ABC123456789BCD231023116712UVABCD12310123114567896712U VPage 43外連接的不同變體外連接的不同變體 只是將左變量只是將左變量R R的懸浮元組補齊的懸浮元組補齊 加入到結果中，加入到結果中，稱之左外連接，用符號稱之左外連接，用符號R R L LS S表示。表示。 只是將右變量只是將右變量S S的懸浮元組補齊的懸浮元組補齊 加入到結果中，加入到結果中，稱之左外連接，用符號稱

17、之左外連接，用符號R R R RS S表示。表示。 外連接的操作是，先進行外連接的操作是，先進行連接，然后將那些不連接，然后將那些不能匹配其他關系的元組，也用能匹配其他關系的元組，也用 補齊，用補齊，用U U C CV V表表示一個帶條件示一個帶條件C C的的外連接。同樣，可用外連接。同樣，可用L L或或R R來修來修飾這個算符，使其表示飾這個算符，使其表示的左外連接或右外連接。的左外連接或右外連接。Page 44如果只將左邊關系中的懸浮元組加入到結果關系中，就是左外連接oL BCD2342356787810ABCD123412356781097810SR oL S456A B C123456

18、678978R外連接的不同變體外連接的不同變體Page 45如果只將右邊關系中的懸浮元組加入到結果關系中，就是右外連接oR A B C123456678978ABCD123412356781097810RR oR S678BCD2342356787810S外連接的不同變體外連接的不同變體Page 46類似于自然連接，連接也有對應的外連接。A B C123678978BCD231235789AR.B R.C S.B S.CD123235123789678789RSR AD S外連接的不同變體外連接的不同變體Page 47舉例A B C123678978BCD231235789AR.B R.C S

19、.B S.CD123235123789678789RSR OAD S978231Page 48舉例A B C123678978BCD231235789AR.B R.C S.B S.CD123235123789678789RSR LAD S978Page 49舉例A B C123678978BCD231235789AR.B R.C S.B S.CD123235123789678789RSR RAD S231Page 50練習練習 P130 習題習題5.2.1 a, c, e, f, g, k, n已知關系已知關系R(A,B):(0, 1),(2, 3),(0, 1),(2, 4),(3, 4)S

20、(B,C):(0, 1),(2, 4),(2, 5),(3, 4),(0, 2),(3, 4)計算下面的表達式：計算下面的表達式：a)Page 5122,( )A B ABR練習練習 P130 習題習題5.2.1 a, c, e, f, g, k, n已知關系已知關系R(A,B):(0, 1),(2, 3),(0, 1),(2, 4),(3, 4)S(B,C):(0, 1),(2, 4),(2, 5),(3, 4),(0, 2),(3, 4)計算下面的表達式：計算下面的表達式：c)Page 52,( )B AR練習練習 P130 習題習題5.2.1 a, c, e, g, k, n已知關系已知

21、關系R(A,B):(0, 1),(2, 3),(0, 1),(2, 4),(3, 4)S(B,C):(0, 1),(2, 4),(2, 5),(3, 4),(0, 2),(3, 4)計算下面的表達式：計算下面的表達式：e)Page 53( )R練習練習 P130 習題習題5.2.1 a, c, e, g, k, n已知關系已知關系R(A,B):(0, 1),(2, 3),(0, 1),(2, 4),(3, 4)S(B,C):(0, 1),(2, 4),(2, 5),(3, 4),(0, 2),(3, 4)計算下面的表達式：計算下面的表達式：g)Page 54,()( )A SUM BR練習練習

22、 P130 習題習題5.2.1 a, c, e, g, k, n已知關系已知關系R(A,B):(0, 1),(2, 3),(0, 1),(2, 4),(3, 4)S(B,C):(0, 1),(2, 4),(2, 5),(3, 4),(0, 2),(3, 4)計算下面的表達式：計算下面的表達式：k)Page 55oLRS 練習練習 P130 習題習題5.2.1 a, c, e, g, k, n已知關系已知關系R(A,B):(0, 1),(2, 3),(0, 1),(2, 4),(3, 4)S(B,C):(0, 1),(2, 4),(2, 5),(3, 4),(0, 2),(3, 4)計算下面的表

23、達式：計算下面的表達式：n)Page 56.oR B S BRS 隨著數(shù)據(jù)技術的不斷提高，關系代數(shù)也暴露出了一些局限隨著數(shù)據(jù)技術的不斷提高，關系代數(shù)也暴露出了一些局限性，例如，無法有效地表示遞歸運算、邏輯表達能力弱等性，例如，無法有效地表示遞歸運算、邏輯表達能力弱等。 在這種情況下，在這種情況下，Datalog語言應運而生。語言應運而生。Datalog語言是一種語言是一種基于邏輯編程語言基于邏輯編程語言Prolog的一種非過程化的語言。同關系的一種非過程化的語言。同關系演算類似，用戶只需要給出所描述的信息，不需要給出獲演算類似，用戶只需要給出所描述的信息，不需要給出獲取信息的具體過程。取信息的

24、具體過程。 本節(jié)介紹本節(jié)介紹Datalog語言的基本結構、規(guī)則以及從關系代數(shù)到語言的基本結構、規(guī)則以及從關系代數(shù)到Datalog語言的轉換等內容。語言的轉換等內容。 5.4 關系邏輯關系邏輯(1)Page 57基本概念基本概念 邏輯也是一種表示關系查詢的方法，例如邏輯也是一種表示關系查詢的方法，例如Datalog語語言就可以表示相同類型的查詢。言就可以表示相同類型的查詢。 Datalog語言不是使用過程語言來表示查詢，而是使語言不是使用過程語言來表示查詢，而是使用一種規(guī)則來表示出這種想法，即可以通過已知的關用一種規(guī)則來表示出這種想法，即可以通過已知的關系中的某些元組的組合來推測元組是否在關系中

25、。系中的某些元組的組合來推測元組是否在關系中。Page 58基本結構基本結構 Datalog語言包括兩種基本的原子，即關系原子和算術原子語言包括兩種基本的原子，即關系原子和算術原子,由原子按照一定的規(guī)則組成由原子按照一定的規(guī)則組成Datalog查詢語句。查詢語句。 在在Datalog語言中，關系通過語言中，關系通過 “謂詞謂詞”來表示，每一個謂詞都來表示，每一個謂詞都有固定數(shù)量的參數(shù)。有固定數(shù)量的參數(shù)。 關系原子是由符號謂詞和其后的參數(shù)組成，常簡稱原子。關系原子是由符號謂詞和其后的參數(shù)組成，常簡稱原子。 例如，如果謂詞是例如，如果謂詞是R，其參數(shù)分別是，其參數(shù)分別是t1，t2，tn，那么那么R

26、(t1，t2，tn)就是一個關系原子。就是一個關系原子。 算術原子是兩個算術表達式的比較，算術原子的值是布爾算術原子是兩個算術表達式的比較，算術原子的值是布爾值。值。 Page 59例子例子 Page 60一般規(guī)則一般規(guī)則 規(guī)則是規(guī)則是Datalog語言中描述原子之間關聯(lián)的規(guī)范，包括下列語言中描述原子之間關聯(lián)的規(guī)范，包括下列三個組成部分：三個組成部分：1. 一個稱為頭部的關系原子，其后是一個稱為頭部的關系原子，其后是2. 左向箭頭符號左向箭頭符號，讀作，讀作if，其后是，其后是3. 主體部分，由一個或多個稱為子目標的原子組成。主體部分，由一個或多個稱為子目標的原子組成。 子目標既可以是關系原子

27、，也可以是算術原子。各個子子目標既可以是關系原子，也可以是算術原子。各個子目標之間用邏輯運算符目標之間用邏輯運算符AND連接，且各個子目標前面可連接，且各個子目標前面可以有選擇地增加取反邏輯運算符以有選擇地增加取反邏輯運算符NOT。 規(guī)則的目標是使規(guī)則的頭部關系原子為真。規(guī)則的目標是使規(guī)則的頭部關系原子為真。例如：例如：LongMovie(t,y)Movies(t,y,l,g,s,p) AND l100等價于等價于LongMovie:=title,year(length) 100(Movies)Page 61例子例子 Page 62例子例子 Page 63例子例子 Page 64例子例子 Pa

28、ge 65Page 66安全規(guī)則安全規(guī)則 安全規(guī)則：安全規(guī)則： 由于關系實例總是有限，所以還需要由規(guī)則保證得到的由于關系實例總是有限，所以還需要由規(guī)則保證得到的頭部關系也都是有限的。頭部關系也都是有限的。 每個在規(guī)則中任意位置出現(xiàn)的變量都必須出現(xiàn)在主體的每個在規(guī)則中任意位置出現(xiàn)的變量都必須出現(xiàn)在主體的某些非否定的關系子目標中。某些非否定的關系子目標中。 尤其是，任何在規(guī)則頭部、否定關系子目標或任意算術尤其是，任何在規(guī)則頭部、否定關系子目標或任意算術子目標中出現(xiàn)的變量，也必須出現(xiàn)在主體的非否定的關子目標中出現(xiàn)的變量，也必須出現(xiàn)在主體的非否定的關系子目標中。系子目標中。Page 67 例例5.19

29、 安全規(guī)則安全規(guī)則 LongMovie(t,y)Movies(t,y,l,g,s,p) AND l100 例例5.20 非安全規(guī)則，不允許出現(xiàn)在非安全規(guī)則，不允許出現(xiàn)在Datalog中中 P(x,y)Q(x,z) AND NOT R(w,x,z) AND xyPage 68擴展謂詞和內涵謂詞擴展謂詞和內涵謂詞 若謂詞所指的關系存儲在數(shù)據(jù)庫中，稱該謂詞為擴展謂詞若謂詞所指的關系存儲在數(shù)據(jù)庫中，稱該謂詞為擴展謂詞。 當謂詞所指的關系是通過一個或多個當謂詞所指的關系是通過一個或多個Datalog規(guī)則計算得到規(guī)則計算得到的，稱該謂詞是內涵謂詞。的，稱該謂詞是內涵謂詞。 擴展謂詞和內涵謂詞分別對應關系代

30、數(shù)表達式中的操作數(shù)擴展謂詞和內涵謂詞分別對應關系代數(shù)表達式中的操作數(shù)和使用關系代數(shù)表達式計算得到的關系。和使用關系代數(shù)表達式計算得到的關系。 在在Datalog規(guī)則中，可以使用規(guī)則中，可以使用EDB(External Database，擴，擴展數(shù)據(jù)庫展數(shù)據(jù)庫)表示擴展謂詞或相應的關系，使用表示擴展謂詞或相應的關系，使用IDB(Internal Database，內涵數(shù)據(jù)庫，內涵數(shù)據(jù)庫)表示內涵謂詞或相應的關系表示內涵謂詞或相應的關系 。 例如，例如，Movies是一個是一個EDB關系，而關系，而LongMovie是一個是一個IDB關系。關系。Page 69練習練習 P136 習題習題5.3.1

31、 b, c, db)Page 70ker100(Pr()mahdoductLaptop 練習練習 P136 習題習題5.3.1 b, c, dc)Page 71 mod,kermod,kermod,ker1:(Pr)2:(Pr)3:(PrPrint)4:123el pricemaBel pricemaBel pricemaBRoductPCRoductLaptopRoducterRRRR 練習練習 P136 習題習題5.3.1 b, c, dd)Page 72mod(Print)elcolor true And type laserer5.5 關系代數(shù)與關系代數(shù)與Datalog 一般地，可以使

32、用一個或多個一般地，可以使用一個或多個Datalog規(guī)則來模擬關系代數(shù)規(guī)則來模擬關系代數(shù)的運算形式，并且可以模擬非常復雜的運算形式。的運算形式，并且可以模擬非常復雜的運算形式。 本節(jié)主要研究如何從關系代數(shù)的基本運算形式以及連接運本節(jié)主要研究如何從關系代數(shù)的基本運算形式以及連接運算形式轉換到算形式轉換到Datalog規(guī)則。規(guī)則。Page 73從集合運算到從集合運算到Datalog規(guī)則規(guī)則 交集運算可以使用一個交集運算可以使用一個Datalog規(guī)則來表示。由于交集運算規(guī)則來表示。由于交集運算涉及了兩個關系，那么在涉及了兩個關系，那么在Datalog規(guī)則中，具有與兩個關系規(guī)則中，具有與兩個關系對應的

33、子目標。在規(guī)則中，相應的參數(shù)使用相同的變量。對應的子目標。在規(guī)則中，相應的參數(shù)使用相同的變量。 假設假設R和和S的關系模式是的關系模式是R(A,B,C)和和S(A,B,C)，則則RS可以使用規(guī)則可以使用規(guī)則: I(a, b, c) R(a, b, c) AND S(a, b, c)Page 74 并集運算使用兩個規(guī)則來表示，每個規(guī)則對應著一個并集并集運算使用兩個規(guī)則來表示，每個規(guī)則對應著一個并集運算中的關系，且兩個規(guī)則的頭部都有相同的運算中的關系，且兩個規(guī)則的頭部都有相同的IDB謂詞。謂詞。頭部的參數(shù)與各個子目標中的參數(shù)完全相同。頭部的參數(shù)與各個子目標中的參數(shù)完全相同。 假設假設R和和S的關系

34、模式是的關系模式是R(A,B,C)和和S(A,B,C)，則則R S可以使用規(guī)則可以使用規(guī)則: U(x, y, z) R(x, y, z) U(x, y, z) S(x, y, z) 或或U(a, b, c) S(a, b, c) 注意：變量名對于規(guī)則是局部的，即每條規(guī)則是獨立計算的注意：變量名對于規(guī)則是局部的，即每條規(guī)則是獨立計算的，并且向其頭部關系提供元組，與其他規(guī)則無關，因此變，并且向其頭部關系提供元組，與其他規(guī)則無關，因此變量名是獨立于規(guī)則的。量名是獨立于規(guī)則的。Page 75 差集運算可以使用具有求反子目標的一個規(guī)則來計算。即差集運算可以使用具有求反子目標的一個規(guī)則來計算。即如果計算兩

35、個關系如果計算兩個關系U和和V的差集，非求反子目標是謂詞的差集，非求反子目標是謂詞U，求反子目標是謂詞求反子目標是謂詞V。 在該規(guī)則中，子目標和頭部對于相應的參數(shù)都有相同的變在該規(guī)則中，子目標和頭部對于相應的參數(shù)都有相同的變量。量。 假設假設R和和S的關系模式是的關系模式是R(A,B,C)和和S(A,B,C)，則則R-S可以使用規(guī)則可以使用規(guī)則: D(a, b, c) R(x, y, z) AND NOT S(x, y, z)Page 76從投影運算到從投影運算到Datalog規(guī)則規(guī)則 將關系代數(shù)中的投影運算轉換成將關系代數(shù)中的投影運算轉換成Datalog規(guī)則，可以使用規(guī)則，可以使用一個具有單

36、一子目標的規(guī)則。該子目標的參數(shù)是不同的變一個具有單一子目標的規(guī)則。該子目標的參數(shù)是不同的變量，每個變量代表關系的一個屬性。量，每個變量代表關系的一個屬性。 頭部是帶有參數(shù)的原子，其參數(shù)按照期望順序對應于投影頭部是帶有參數(shù)的原子，其參數(shù)按照期望順序對應于投影列表的屬性。列表的屬性。 例例5.25 將關系將關系Movies (title, year, length, genre, studioName, producerC#)投影到前三個屬性：投影到前三個屬性： P(t,y,l) Movies(t,y,l,g,s,p)Page 77從選擇運算到從選擇運算到Datalog規(guī)則規(guī)則 如果選擇條件是一個

37、或多個算術比較表達式的如果選擇條件是一個或多個算術比較表達式的AND運算，運算，可以建立一個具有下列子目標的可以建立一個具有下列子目標的Datalog規(guī)則：規(guī)則： 一個關系子目標對應于將其進行選擇的關系。該關系子一個關系子目標對應于將其進行選擇的關系。該關系子目標的每個分量都有不同的變量，且每個分量都對應關目標的每個分量都有不同的變量，且每個分量都對應關系的一個屬性；系的一個屬性； 多個算術子目標，每個算術子目標對應選擇條件的一個多個算術子目標，每個算術子目標對應選擇條件的一個比較運算。雖然在選擇條件中使用屬性名，但是在算術比較運算。雖然在選擇條件中使用屬性名，但是在算術子目標中卻使用相應的變

38、量，并且與關系子目標中建立子目標中卻使用相應的變量，并且與關系子目標中建立的變量保持一致。的變量保持一致。 復雜條件可以將邏輯表達式轉化成復雜條件可以將邏輯表達式轉化成“析取范式析取范式”，即正負文，即正負文字的合取的析取。字的合取的析取。Page 78例5.26 length100 and studioName=Fox (Movies) S(t,y,l,g,s,p) Movies(t,y,l,g,s,p) AND l 100 and s=Fox例例5.27 length100 or studioName=Fox (Movies) S(t,y,l,g,s,p) Movies(t,y,l,g,s

39、,p) AND l 100 S(t,y,l,g,s,p) Movies(t,y,l,g,s,p) AND s=Fox例例5.28 NOT(length100 or studioName=Fox） (Movies) 根據(jù)狄摩根定律，等價于根據(jù)狄摩根定律，等價于 (NOT(length100) AND (NOT (studioName=Fox)） (Movies) 即即length100 AND studioNameFox (Movies) 再轉化為再轉化為Datalog規(guī)則：規(guī)則：S(t,y,l,g,s,p) Movies(t,y,l,g,s,p) AND l100 and s FoxPage

40、79從笛卡爾乘積到從笛卡爾乘積到Datalog規(guī)則規(guī)則 RS可以使用單一的可以使用單一的Datalog規(guī)則來表示，規(guī)則包含兩個規(guī)則來表示，規(guī)則包含兩個子目標，一個對應子目標，一個對應R一個對應一個對應S，兩個子目標有不同的變，兩個子目標有不同的變量分別對應量分別對應R和和S的屬性。的屬性。 頭部頭部IDB謂詞擁有所有在這兩個子目標中出現(xiàn)的參數(shù)，謂詞擁有所有在這兩個子目標中出現(xiàn)的參數(shù)，R子目標中的變量列在子目標中的變量列在S子目標中變量的前面。子目標中變量的前面。 p(a,b,c,x,y,z) R(a,b,c) AND S(x,y,z)Page 80從連接運算到從連接運算到Datalog規(guī)則規(guī)則

41、 自然連接自然連接R S使用一條近似于笛卡爾積的使用一條近似于笛卡爾積的Datalog規(guī)則來表規(guī)則來表示，區(qū)別在于示，區(qū)別在于R和和S的同名屬性使用相同的變量，否則使用的同名屬性使用相同的變量，否則使用不同的變量。不同的變量。 規(guī)則頭部是一個規(guī)則頭部是一個IDB謂詞，它的每個變量出現(xiàn)一次。謂詞，它的每個變量出現(xiàn)一次。 假設假設R和和S的關系模式是的關系模式是R(A,B)和和S(B,C,D)，則自然連接，則自然連接R S 可以用規(guī)則可以用規(guī)則 J(a,b,c,d) R(a,b) AND S(b,c,d)Page 81 連接連接 先對笛卡爾積進行轉化，再對選擇條件進行轉化。先對笛卡爾積進行轉化，再

42、對選擇條件進行轉化。例例5.32 考慮關系考慮關系U(A,B,C)和和V(B,C,D)，其，其連接連接 對應的對應的Datalog規(guī)則：規(guī)則： J(a,ub,uc,vb,vc,d) U(a,ub,uc) AND V(vb,vc,d) AND ad AND ubvb例例5.33 J(a,ub,uc,vb,vc,d) U(a,ub,uc) AND V(vb,vc,d) AND ad J(a,ub,uc,vb,vc,d) U(a,ub,uc) AND V(vb,vc,d) AND ubvbU AD AND U.BV .BVU AD OR U.BV .BVPage 82從多重運算到從多重運算到Datalog規(guī)則規(guī)則 關系代數(shù)中的單一運算形式可以使用關系代數(shù)中的單一運算形式可以使用Datalog規(guī)則表示，而規(guī)則表示，而且多重運算也可以使用且多重運算也可以使用Datalog規(guī)則模擬。規(guī)則模擬。 模擬多重運算的步驟如下：模擬多重運算的步驟如下： 繪制關系代數(shù)的表達樹。其中，表達樹就是使用樹狀結繪制關系代數(shù)的表達樹。其中，表達樹就是使用樹狀結構表示關系代數(shù)表達式的計算程序。構表示關系代數(shù)表達式的計算程序。 為表達樹的每一