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

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

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

3、要對(duì)應(yīng)一致，如果不一致，需要利用重命名操作處理利用重命名操作處理Page 35.1 關(guān)系代數(shù)操作關(guān)系代數(shù)操作(3) 投影投影A1,A2,An(R) 只保留指定部分列只保留指定部分列 由于屬性減少，元組可能會(huì)重值，進(jìn)而合并，因由于屬性減少，元組可能會(huì)重值，進(jìn)而合并，因此數(shù)目可能減少此數(shù)目可能減少 選擇選擇C(R) 該操作產(chǎn)生的新關(guān)系的元組必須滿(mǎn)足條件該操作產(chǎn)生的新關(guān)系的元組必須滿(mǎn)足條件C 結(jié)果關(guān)系和原關(guān)系的模式相同結(jié)果關(guān)系和原關(guān)系的模式相同Page 45.1 關(guān)系代數(shù)操作關(guān)系代數(shù)操作(4) 笛卡爾積笛卡爾積 RS 一個(gè)有序?qū)Φ募希行驅(qū)Φ牡谝粋€(gè)元素來(lái)自一個(gè)有序?qū)Φ募?，有序?qū)Φ牡谝粋€(gè)元素來(lái)自R

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

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

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

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

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

9、：AB1122R =S =Page 135.2 包上的關(guān)系操作包上的關(guān)系操作(2) 集合上的包操作（文本框內(nèi)容釋義）集合上的包操作（文本框內(nèi)容釋義） 如果對(duì)兩個(gè)集合如果對(duì)兩個(gè)集合R、S進(jìn)行基于包的交和差操作，其結(jié)進(jìn)行基于包的交和差操作，其結(jié)果與集合方式運(yùn)算一樣果與集合方式運(yùn)算一樣 因?yàn)樽鳛楸惶幚韺?duì)象的兩個(gè)關(guān)系本身沒(méi)有重復(fù)的元因?yàn)樽鳛楸惶幚韺?duì)象的兩個(gè)關(guān)系本身沒(méi)有重復(fù)的元組，所以交或差之后結(jié)果中仍然沒(méi)有重值元組組，所以交或差之后結(jié)果中仍然沒(méi)有重值元組 但對(duì)兩個(gè)集合但對(duì)兩個(gè)集合R和和S，進(jìn)行基于包的并操作，其操作結(jié)，進(jìn)行基于包的并操作，其操作結(jié)果可能不再是集合果可能不再是集合 結(jié)論：必須看清（答題）

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

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

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

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

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

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

16、null符號(hào)符號(hào) 補(bǔ)齊結(jié)補(bǔ)齊結(jié)果元組中那些不具有值的屬性。我們稱(chēng)之為果元組中那些不具有值的屬性。我們稱(chēng)之為外連外連接，接，用符號(hào)用符號(hào) 表示。表示。Page 42設(shè)有關(guān)系設(shè)有關(guān)系A(chǔ)BC123456789BCD231023116712UVABCD12310123114567896712U VPage 43外連接的不同變體外連接的不同變體 只是將左變量只是將左變量R R的懸浮元組補(bǔ)齊的懸浮元組補(bǔ)齊 加入到結(jié)果中，加入到結(jié)果中，稱(chēng)之左外連接，用符號(hào)稱(chēng)之左外連接，用符號(hào)R R L LS S表示。表示。 只是將右變量只是將右變量S S的懸浮元組補(bǔ)齊的懸浮元組補(bǔ)齊 加入到結(jié)果中，加入到結(jié)果中，稱(chēng)之左外連接

17、，用符號(hào)稱(chēng)之左外連接，用符號(hào)R R R RS S表示。表示。 外連接的操作是，先進(jìn)行外連接的操作是，先進(jìn)行連接，然后將那些不連接，然后將那些不能匹配其他關(guān)系的元組，也用能匹配其他關(guān)系的元組，也用 補(bǔ)齊，用補(bǔ)齊，用U U C CV V表表示一個(gè)帶條件示一個(gè)帶條件C C的的外連接。同樣，可用外連接。同樣，可用L L或或R R來(lái)修來(lái)修飾這個(gè)算符，使其表示飾這個(gè)算符，使其表示的左外連接或右外連接。的左外連接或右外連接。Page 44如果只將左邊關(guān)系中的懸浮元組加入到結(jié)果關(guān)系中，就是左外連接oL BCD2342356787810ABCD123412356781097810SR oL S456A B C1

18、23456678978R外連接的不同變體外連接的不同變體Page 45如果只將右邊關(guān)系中的懸浮元組加入到結(jié)果關(guān)系中，就是右外連接oR A B C123456678978ABCD123412356781097810RR oR S678BCD2342356787810S外連接的不同變體外連接的不同變體Page 46類(lèi)似于自然連接，連接也有對(duì)應(yīng)的外連接。A B C123678978BCD231235789AR.B R.C S.B S.CD123235123789678789RSR AD S外連接的不同變體外連接的不同變體Page 47舉例A B C123678978BCD231235789AR.B

19、R.C S.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練習(xí)練習(xí) P130 習(xí)題習(xí)題5.2.1 a, c, e, f, g, k, n已知關(guān)系已知關(guān)系R(A,B):(0, 1),(2, 3),(0, 1),(2, 4),(3

20、, 4)S(B,C):(0, 1),(2, 4),(2, 5),(3, 4),(0, 2),(3, 4)計(jì)算下面的表達(dá)式：計(jì)算下面的表達(dá)式：a)Page 5122,( )A B ABR練習(xí)練習(xí) P130 習(xí)題習(xí)題5.2.1 a, c, e, f, g, k, n已知關(guān)系已知關(guā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)計(jì)算下面的表達(dá)式：計(jì)算下面的表達(dá)式：c)Page 52,( )B AR練習(xí)練習(xí) P130 習(xí)題習(xí)題5.2.1 a, c, e, g, k, n已

21、知關(guān)系已知關(guā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)計(jì)算下面的表達(dá)式：計(jì)算下面的表達(dá)式：e)Page 53( )R練習(xí)練習(xí) P130 習(xí)題習(xí)題5.2.1 a, c, e, g, k, n已知關(guān)系已知關(guā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)計(jì)算下面的表達(dá)式：計(jì)算下面的表達(dá)式：g)Page 54,()( )A SUM B

22、R練習(xí)練習(xí) P130 習(xí)題習(xí)題5.2.1 a, c, e, g, k, n已知關(guān)系已知關(guā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)計(jì)算下面的表達(dá)式：計(jì)算下面的表達(dá)式：k)Page 55oLRS 練習(xí)練習(xí) P130 習(xí)題習(xí)題5.2.1 a, c, e, g, k, n已知關(guān)系已知關(guā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)計(jì)

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

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

25、否在關(guān)系中。系中的某些元組的組合來(lái)推測(cè)元組是否在關(guān)系中。Page 58基本結(jié)構(gòu)基本結(jié)構(gòu) Datalog語(yǔ)言包括兩種基本的原子，即關(guān)系原子和算術(shù)原子語(yǔ)言包括兩種基本的原子，即關(guān)系原子和算術(shù)原子,由原子按照一定的規(guī)則組成由原子按照一定的規(guī)則組成Datalog查詢(xún)語(yǔ)句。查詢(xún)語(yǔ)句。 在在Datalog語(yǔ)言中，關(guān)系通過(guò)語(yǔ)言中，關(guān)系通過(guò) “謂詞謂詞”來(lái)表示，每一個(gè)謂詞來(lái)表示，每一個(gè)謂詞都有固定數(shù)量的參數(shù)。都有固定數(shù)量的參數(shù)。 關(guān)系原子是由符號(hào)謂詞和其后的參數(shù)組成，常簡(jiǎn)稱(chēng)原子。關(guān)系原子是由符號(hào)謂詞和其后的參數(shù)組成，常簡(jiǎn)稱(chēng)原子。 例如，如果謂詞是例如，如果謂詞是R，其參數(shù)分別是，其參數(shù)分別是t1，t2，tn，

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

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

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

29、例5.19 安全規(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擴(kuò)展謂詞和內(nèi)涵謂詞擴(kuò)展謂詞和內(nèi)涵謂詞 若謂詞所指的關(guān)系存儲(chǔ)在數(shù)據(jù)庫(kù)中，稱(chēng)該謂詞為擴(kuò)展謂詞若謂詞所指的關(guān)系存儲(chǔ)在數(shù)據(jù)庫(kù)中，稱(chēng)該謂詞為擴(kuò)展謂詞。 當(dāng)謂詞所指的關(guān)系是通過(guò)一個(gè)或多個(gè)當(dāng)謂詞所指的關(guān)系是通過(guò)一個(gè)或多個(gè)Datalog規(guī)則計(jì)算得到規(guī)則計(jì)算得到的，稱(chēng)該謂詞是內(nèi)涵謂詞。的，稱(chēng)該謂詞是內(nèi)涵謂詞。 擴(kuò)展謂詞和內(nèi)涵謂詞分別

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

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

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

33、關(guān)系對(duì)應(yīng)的子目標(biāo)。在規(guī)則中，相應(yīng)的參數(shù)使用相同的變量。對(duì)應(yīng)的子目標(biāo)。在規(guī)則中，相應(yīng)的參數(shù)使用相同的變量。 假設(shè)假設(shè)R和和S的關(guān)系模式是的關(guān)系模式是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 并集運(yùn)算使用兩個(gè)規(guī)則來(lái)表示，每個(gè)規(guī)則對(duì)應(yīng)著一個(gè)并集并集運(yùn)算使用兩個(gè)規(guī)則來(lái)表示，每個(gè)規(guī)則對(duì)應(yīng)著一個(gè)并集運(yùn)算中的關(guān)系，且兩個(gè)規(guī)則的頭部都有相同的運(yùn)算中的關(guān)系，且兩個(gè)規(guī)則的頭部都有相同的IDB謂詞。謂詞。頭部的參數(shù)與各個(gè)子目標(biāo)中的參數(shù)完全相同。頭部的參數(shù)與各個(gè)子目標(biāo)中的參數(shù)完全相同。 假設(shè)假設(shè)R和

34、和S的關(guān)系模式是的關(guān)系模式是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) 注意：變量名對(duì)于規(guī)則是局部的，即每條規(guī)則是獨(dú)立計(jì)算的注意：變量名對(duì)于規(guī)則是局部的，即每條規(guī)則是獨(dú)立計(jì)算的，并且向其頭部關(guān)系提供元組，與其他規(guī)則無(wú)關(guān)，因此變，并且向其頭部關(guān)系提供元組，與其他規(guī)則無(wú)關(guān)，因此變量名是獨(dú)立于規(guī)則的。量名是獨(dú)立于規(guī)則的。Page 75 差集運(yùn)算可以使用具有求反子目標(biāo)的一個(gè)規(guī)則來(lái)計(jì)算。即差集運(yùn)算可以使用具有求反子目標(biāo)的一個(gè)規(guī)則來(lái)計(jì)算。即

35、如果計(jì)算兩個(gè)關(guān)系如果計(jì)算兩個(gè)關(guān)系U和和V的差集，非求反子目標(biāo)是謂詞的差集，非求反子目標(biāo)是謂詞U，求反子目標(biāo)是謂詞求反子目標(biāo)是謂詞V。 在該規(guī)則中，子目標(biāo)和頭部對(duì)于相應(yīng)的參數(shù)都有相同的變?cè)谠撘?guī)則中，子目標(biāo)和頭部對(duì)于相應(yīng)的參數(shù)都有相同的變量。量。 假設(shè)假設(shè)R和和S的關(guān)系模式是的關(guān)系模式是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從投影運(yùn)算到從投影運(yùn)算到Datalog規(guī)則規(guī)則 將關(guān)系代數(shù)中的投影運(yùn)算轉(zhuǎn)換成將關(guān)系代數(shù)中的投影運(yùn)算轉(zhuǎn)換成Datalog規(guī)則，可以使用規(guī)則，可以使用

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

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

38、用相應(yīng)的變量，并且與關(guān)系子目標(biāo)中建立子目標(biāo)中卻使用相應(yīng)的變量，并且與關(guān)系子目標(biāo)中建立的變量保持一致。的變量保持一致。 復(fù)雜條件可以將邏輯表達(dá)式轉(zhuǎn)化成復(fù)雜條件可以將邏輯表達(dá)式轉(zhuǎn)化成“析取范式析取范式”，即正負(fù)，即正負(fù)文字的合取的析取。文字的合取的析取。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,

39、l,g,s,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ù)狄摩根定律，等價(jià)于根據(jù)狄摩根定律，等價(jià)于 (NOT(length100) AND (NOT (studioName=Fox)） (Movies) 即即length100 AND studioNameFox (Movies) 再轉(zhuǎn)化為再轉(zhuǎn)化為Datalog規(guī)則：規(guī)則：S(t,y,l,g,s,p) Movies(t,y,l,g,s,p) AND l100 and s Fox

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

41、g規(guī)則規(guī)則 自然連接自然連接R S使用一條近似于笛卡爾積的使用一條近似于笛卡爾積的Datalog規(guī)則來(lái)表規(guī)則來(lái)表示，區(qū)別在于示，區(qū)別在于R和和S的同名屬性使用相同的變量，否則使用的同名屬性使用相同的變量，否則使用不同的變量。不同的變量。 規(guī)則頭部是一個(gè)規(guī)則頭部是一個(gè)IDB謂詞，它的每個(gè)變量出現(xiàn)一次。謂詞，它的每個(gè)變量出現(xiàn)一次。 假設(shè)假設(shè)R和和S的關(guān)系模式是的關(guān)系模式是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 連接連接 先對(duì)笛卡爾積進(jìn)行轉(zhuǎn)化，再對(duì)選擇條件進(jìn)行轉(zhuǎn)化。先對(duì)笛卡爾積進(jìn)

42、行轉(zhuǎn)化，再對(duì)選擇條件進(jìn)行轉(zhuǎn)化。例例5.32 考慮關(guān)系考慮關(guān)系U(A,B,C)和和V(B,C,D)，其，其連接連接 對(duì)應(yīng)的對(duì)應(yīng)的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從多重運(yùn)算到從多重運(yùn)算到Datalog規(guī)則規(guī)則 關(guān)系代數(shù)中的單一運(yùn)算形式可以使用關(guān)系代數(shù)中的單一運(yùn)算形式可以使用Datalog規(guī)則表示，而規(guī)則表示，而且多重運(yùn)算也可以使用且多重運(yùn)算也可以使用Datalog規(guī)則模擬。規(guī)則模擬。 模擬多重運(yùn)算的步驟如下：模擬多重運(yùn)算的步驟如下： 繪制關(guān)系代數(shù)的表達(dá)樹(shù)。其中，表達(dá)樹(shù)就是使用樹(shù)狀結(jié)繪制關(guān)系代數(shù)的表達(dá)樹(shù)。其中，表達(dá)樹(shù)就是使用樹(shù)狀結(jié)構(gòu)表示關(guān)系代數(shù)表達(dá)式的計(jì)算程序。構(gòu)表示關(guān)系代數(shù)表達(dá)式的計(jì)算程序。 為表達(dá)樹(shù)的每一