數(shù)據(jù)庫系統(tǒng)原理與應(yīng)用教程(第三版)ch08-Datalog語言課件

第8章Datalog語言本章概述本章的學(xué)習(xí)目標(biāo)主要內(nèi)容1第8章Datalog語言本章概述1本章概述關(guān)系代數(shù)是關(guān)系型數(shù)據(jù)庫的理論基礎(chǔ)，是數(shù)據(jù)庫產(chǎn)品應(yīng)用和發(fā)展的堅實基礎(chǔ)。隨著數(shù)據(jù)技術(shù)的不斷提高，關(guān)系代數(shù)也暴露出了一些局限性，例如，無法有效地表示遞歸運算、邏輯表達(dá)能力弱等。在這種情況下，Datalog語言應(yīng)運而生。Datalog語言是一種基于邏輯編程語言Prolog的一種非過程化的語言。同使用關(guān)系演算類似，用戶只需要給出所描述的信息，不需要給出獲取信息的具體過程。Datalog語言使用聲明的方式定義，簡化了簡單查詢的書寫，使查詢優(yōu)化更容易進(jìn)行。本章將要全面介紹Datalog語言的基本結(jié)構(gòu)、規(guī)則、遞歸編程以及從關(guān)系代數(shù)到Datalog語言的轉(zhuǎn)換等內(nèi)容。2本章概述關(guān)系代數(shù)是關(guān)系型數(shù)據(jù)庫的理論基礎(chǔ)，是數(shù)據(jù)庫產(chǎn)品應(yīng)用和本章的學(xué)習(xí)目標(biāo)了解Datalog語言的基本概念；掌握Datalog語言的基本結(jié)構(gòu)；掌握Datalog語言的基本規(guī)則；掌握從關(guān)系代數(shù)到Datalog語言的轉(zhuǎn)換過程；認(rèn)識和掌握Datalog語言的遞歸編程原理；理解包的概念和其在關(guān)系代數(shù)和Datalog語言中的作用。3本章的學(xué)習(xí)目標(biāo)了解Datalog語言的基本概念；3主要內(nèi)容8.1基本概念8.2關(guān)系代數(shù)向Datalog規(guī)則的轉(zhuǎn)換8.3遞歸原理8.4包的運算8.5本章小結(jié)4主要內(nèi)容8.1基本概念48.1基本概念邏輯也是一種表示關(guān)系查詢的方法，例如Datalog語言就可以表示相同類型的查詢。Datalog語言不是使用過程語言來表示查詢，而是使用一種規(guī)則來表示出這種想法，即可以通過已知的關(guān)系中的某些元組的組合推測某個其他元組是否在某個其他關(guān)系中。58.1基本概念邏輯也是一種表示關(guān)系查詢的方法，例如Dat基本結(jié)構(gòu)Datalog語言包括了兩種基本的原子，即關(guān)系原子和算術(shù)原子。Datalog語言是由這些原子按照一定的規(guī)則組成的。在Datalog語言中，關(guān)系通過稱為謂詞的符號來表示，每一個謂詞都有固定數(shù)量的參數(shù)。關(guān)系原子是由符號謂詞和其后的參數(shù)組成，關(guān)系原子也經(jīng)常簡稱原子。例如，如果謂詞是R，其參數(shù)分別是t1，t2，…，tn，那么R(t1，t2，…，tn)就是一個關(guān)系原子。算術(shù)原子是兩個算術(shù)表達(dá)式的比較。算術(shù)原子的值也是布爾值。6基本結(jié)構(gòu)Datalog語言包括了兩種基本的原子，即關(guān)系原子一般規(guī)則在前面講述的關(guān)系代數(shù)中，介紹了許多關(guān)系代數(shù)運算，例如集合、笛卡爾乘積和自然連接等。這些運算形式在Datalog語言中可以使用規(guī)則來描述。規(guī)則就是Datalog語言中描述各種原子元素關(guān)聯(lián)的規(guī)范，包括下列三個組成部分：1.一個稱為頭部的關(guān)系原子，其后是2.左向箭頭符號←，讀作if，其后是3.多個子目標(biāo)組成的規(guī)則體。這些子目標(biāo)既可以是關(guān)系原子，也可以是算術(shù)原子。各個子目標(biāo)之間用邏輯運算符AND連接，且各個子目標(biāo)前面可以有選擇地增加取反邏輯運算符NOT。7一般規(guī)則在前面講述的關(guān)系代數(shù)中，介紹了許多關(guān)系代數(shù)運算，例安全規(guī)則前面講過，Datalog語言是一種由許多原子構(gòu)成的規(guī)則，規(guī)則包含了許多變量。規(guī)則的目標(biāo)是使規(guī)則的頭部關(guān)系原子為真。由于關(guān)系實例總是有限，所以還需要由規(guī)則保證得到的頭部關(guān)系也都是有限的。如果得到的頭部關(guān)系是無限的，那么這種規(guī)則是無意義的。下面分析如何保證得到的查詢結(jié)果是有意義的。在子目標(biāo)中，包括了關(guān)系子目標(biāo)、求反關(guān)系子目標(biāo)、算術(shù)子目標(biāo)和求反算術(shù)子目標(biāo)。8安全規(guī)則前面講過，Datalog語言是一種由許多原子構(gòu)成的外延謂詞和內(nèi)涵謂詞外延謂詞和內(nèi)涵謂詞是兩個經(jīng)常提到的概念。當(dāng)謂詞所指的關(guān)系存儲在數(shù)據(jù)庫中時，稱該謂詞為外延謂詞。當(dāng)謂詞所指的關(guān)系是通過一個或多個Datalog規(guī)則計算得到的，稱該謂詞是內(nèi)涵謂詞。外延謂詞和內(nèi)涵謂詞之間的差別類似關(guān)系代數(shù)表達(dá)式的運算項和使用關(guān)系代數(shù)表達(dá)式計算的關(guān)系之間的差別。在Datalog規(guī)則中，如果謂詞分別是內(nèi)涵的或外延的，可以引用與內(nèi)涵的或外延的謂詞相對應(yīng)的關(guān)系。有時，使用IDB(InternalDatabase，內(nèi)涵數(shù)據(jù)庫)來引用內(nèi)涵謂詞或相應(yīng)的關(guān)系，使用EDB(ExternalDatabase，外延數(shù)據(jù)庫)來引用外延謂詞或相應(yīng)的關(guān)系。9外延謂詞和內(nèi)涵謂詞外延謂詞和內(nèi)涵謂詞是兩個經(jīng)常提到的概念。主要內(nèi)容8.1基本概念8.2關(guān)系代數(shù)向Datalog規(guī)則的轉(zhuǎn)換8.3遞歸原理8.4包的運算8.5本章小結(jié)10主要內(nèi)容8.1基本概念108.2關(guān)系代數(shù)向Datalog規(guī)則的轉(zhuǎn)換上一章介紹了關(guān)系代數(shù)的各種運算形式，本節(jié)將介紹各種Datalog規(guī)則形式。一般地，可以使用一個或多個Datalog規(guī)則來模擬關(guān)系代數(shù)的運算形式，并且可以模擬非常復(fù)雜的運算形式。本節(jié)主要研究如何從關(guān)系代數(shù)的基本運算形式以及連接運算形式轉(zhuǎn)換到Datalog規(guī)則。118.2關(guān)系代數(shù)向Datalog規(guī)則的轉(zhuǎn)換上一章介紹了關(guān)系從集合運算到Datalog規(guī)則集合運算是關(guān)系代數(shù)的最基本的運算形式，包括了交集、并集和差集三種運算形式。下面介紹如何使用Datalog規(guī)則模擬這三種集合運算形式。交集運算可以使用一個Datalog規(guī)則來表示。由于交集運算涉及了兩個關(guān)系，那么在Datalog規(guī)則中，具有與兩個關(guān)系對應(yīng)的子目標(biāo)。在規(guī)則中，相應(yīng)的參數(shù)使用相同的變量。并集運算可以使用兩個規(guī)則來表示。在Datalog規(guī)則中，每個規(guī)則都對應(yīng)著一個并集運算中的關(guān)系，且兩個規(guī)則的頭部都有相同的IDB謂詞。頭部的參數(shù)與各個子目標(biāo)中的參數(shù)完全相同。差集運算可以使用具有求反子目標(biāo)的一個規(guī)則來計算。即如果計算兩個關(guān)系U和V的差集，可以這樣來計算，非求反子目標(biāo)是謂詞U，求反子目標(biāo)是謂詞V。在該規(guī)則中，子目標(biāo)和頭部對于相應(yīng)的參數(shù)都有相同的變量。12從集合運算到Datalog規(guī)則集合運算是關(guān)系代數(shù)的最基本的從投影運算到Datalog規(guī)則把關(guān)系代數(shù)中的投影運算形式轉(zhuǎn)換成Datalog規(guī)則，可以使用一個具有單一子目標(biāo)的規(guī)則。該子目標(biāo)的參數(shù)是數(shù)量不同于關(guān)系的屬性數(shù)量的變量，每個變量都對應(yīng)著關(guān)系的一個屬性。頭部是帶有參數(shù)的原子，這些參數(shù)是按照要求的順序與投影的屬性表對應(yīng)的變量。頭部原子的這些變量只是子目標(biāo)投影過來的變量，因此兩者的數(shù)量不同。13從投影運算到Datalog規(guī)則把關(guān)系代數(shù)中的投影運算形式轉(zhuǎn)從笛卡爾乘積到Datalog規(guī)則兩個關(guān)系U和V的笛卡爾乘積U×V可以使用單一的Datalog規(guī)則來表示。在這個Datalog規(guī)則中，有兩個子目標(biāo)。一個子目標(biāo)對應(yīng)關(guān)系U，另一個子目標(biāo)對應(yīng)關(guān)系V。每個子目標(biāo)都有不同的變量，每個變量對應(yīng)著關(guān)系U或V中的一個屬性。頭部的關(guān)系原子把出現(xiàn)的兩個子目標(biāo)中的所有變量作為參數(shù)，且嚴(yán)格按照出現(xiàn)的先后順序，即出現(xiàn)在關(guān)系U子目標(biāo)中的變量排列在關(guān)系V子目標(biāo)的變量之前。14從笛卡爾乘積到Datalog規(guī)則兩個關(guān)系U和V的笛卡爾乘積從選擇運算到Datalog規(guī)則把關(guān)系運算中的選擇轉(zhuǎn)換成Datalog規(guī)則比較復(fù)雜。下面首先研究一種簡單的情況，然后再研究如何把具有復(fù)雜條件的選擇運算轉(zhuǎn)變成Datalog規(guī)則。如果選擇條件是一個算術(shù)比較表達(dá)式或多個比較表達(dá)式的AND運算，可以建立一個具有下列子目標(biāo)的Datalog規(guī)則：一個關(guān)系子目標(biāo)對應(yīng)于將其進(jìn)行選擇的關(guān)系。該關(guān)系子目標(biāo)的每個分量都有不同的變量，且每個分量都對應(yīng)關(guān)系的一個屬性；多個算術(shù)子目標(biāo)，每個算術(shù)子目標(biāo)都對應(yīng)著選擇條件的一個比較運算。雖然在選擇條件中使用屬性名，但是在算術(shù)子目標(biāo)中卻使用相應(yīng)的變量，并且與關(guān)系子目標(biāo)中建立的變量保持一致。15從選擇運算到Datalog規(guī)則把關(guān)系運算中的選擇轉(zhuǎn)換成Da從連接運算到Datalog規(guī)則連接包括了自然連接、θ連接和外部連接。這里主要介紹如何把自然連接和θ連接轉(zhuǎn)變成Datalog規(guī)則。連接運算非常類似于笛卡爾乘積的運算，因此可以使用像乘積的規(guī)則來表示兩個關(guān)系的自然連接，區(qū)別是如果希望表示關(guān)系U和V的自然連接UV，并且這兩個關(guān)系中有相同名稱的屬性，那么必須使用相同的變量，否則必須使用不同的變量。規(guī)則頭部是每一個變量都出現(xiàn)一次的IDB謂詞。16從連接運算到Datalog規(guī)則連接包括了自然連接、θ連接和從多重運算到Datalog規(guī)則關(guān)系代數(shù)中的單一運算形式可以使用Datalog規(guī)則表示，而且多重運算也可以使用Datalog規(guī)則模擬。模擬多重運算的步驟如下：第一步，繪制關(guān)系代數(shù)的表達(dá)樹。其中，表達(dá)樹就是使用樹狀結(jié)構(gòu)表示關(guān)系代數(shù)表達(dá)式的計算程序。第二步，為表達(dá)樹的每一個內(nèi)部節(jié)點建立一個IDB謂詞。17從多重運算到Datalog規(guī)則關(guān)系代數(shù)中的單一運算形式可以主要內(nèi)容8.1基本概念8.2關(guān)系代數(shù)向Datalog規(guī)則的轉(zhuǎn)換

8.3遞歸原理

8.4包的運算8.5本章小結(jié)18主要內(nèi)容8.1基本概念188.3遞歸原理遞歸是一種常見的算法，即如果一個過程直接或間接地調(diào)用它自身，稱該過程為遞歸過程。本節(jié)將要研究為什么使用和如何使用Datalog語言描述遞歸過程。198.3遞歸原理遞歸是一種常見的算法，即如果一個過程直接或關(guān)系代數(shù)存在的問題在數(shù)據(jù)的查詢過程中，經(jīng)常會遇到遞歸現(xiàn)象。例如，在出版社的人事管理中，經(jīng)理和雇員的問題就是一個遞歸問題。一個人可以是某些雇員的經(jīng)理，但是他又可能是另外一個經(jīng)理的雇員，經(jīng)理又可能是更高層經(jīng)理的雇員等多種情況。20關(guān)系代數(shù)存在的問題在數(shù)據(jù)的查詢過程中，經(jīng)常會遇到遞歸現(xiàn)象。計算最小固定點現(xiàn)在研究如何在關(guān)系代數(shù)中解決這種問題。假設(shè)關(guān)系Leader(a，b)表示了這種直接和間接經(jīng)理和雇員的聯(lián)系?？梢詫懗鱿旅娴姆匠?，這是一個包含了關(guān)系Leader和Human的方程式，Leader的值是滿足該方程式的最小關(guān)系，最小關(guān)系也稱為最小固定點。21計算最小固定點現(xiàn)在研究如何在關(guān)系代數(shù)中解決這種問題。21使用Datalog規(guī)則表示固定點公式通過上面的分析可以看到，使用關(guān)系代數(shù)表示固定點公式往往會非常復(fù)雜，使用Datalog規(guī)則表示則比較容易。下面研究如何使用Datalog規(guī)則表示固定點公式。使用Datalog規(guī)則表示固定點公式的思路是：假定一個或多個EDB關(guān)系已知，其他IDB關(guān)系則通過出現(xiàn)在規(guī)則的頭部來定義，規(guī)則體可能包含的謂詞是EDB或IDB的關(guān)系以及代數(shù)原子子目標(biāo)。22使用Datalog規(guī)則表示固定點公式通過上面的分析可以看到主要內(nèi)容8.1基本概念8.2關(guān)系代數(shù)向Datalog規(guī)則的轉(zhuǎn)換

8.3遞歸原理8.4包的運算8.5本章小結(jié)23主要內(nèi)容8.1基本概念238.4包的運算前面已經(jīng)講過，關(guān)系中的元組是集合，是一種自然的斷言。但實際上，在許多數(shù)據(jù)庫產(chǎn)品中，允許相同的元組在關(guān)系中重復(fù)出現(xiàn)。這時，關(guān)系中的元組不是集合，而是包。因此，我們不但需要理解集合的各種運算，還需要了解包是如何運算的。248.4包的運算前面已經(jīng)講過，關(guān)系中的元組是集合，是一種自包的意義集合中不允許元組重復(fù)出現(xiàn)，元組的順序不重要。列表不但不允許元組重復(fù)出現(xiàn)，而且元組的出現(xiàn)順序也是列表的重要特性。相對而言，包的要求比較寬松，既允許元組重復(fù)出現(xiàn)，又不重視元組的出現(xiàn)順序。圖8-9就是一個包的示例。在該示例中，清華大學(xué)出版社元組出現(xiàn)了5次，高等教育出版社元組出現(xiàn)了4次，機(jī)械工業(yè)出版社元組出現(xiàn)了3次。25包的意義集合中不允許元組重復(fù)出現(xiàn)，元組的順序不重要。列表不包的關(guān)系運算關(guān)系的基本運算包括并集、交集、差集、投影、笛卡爾乘積和選擇等形式下面研究如何對包進(jìn)行這些運算。26包的關(guān)系運算關(guān)系的基本運算包括并集、交集、差集、投影、笛卡包的并集運算如果關(guān)系U是一個包，其中元組tupleA出現(xiàn)了n次，關(guān)系V也是一個包，其中元組tupleA出現(xiàn)了m次。那么，在包U∪V的結(jié)果中，元組tupleA出現(xiàn)的次數(shù)是n+m。例如，如果關(guān)系U的一個實例如圖8-12所示，其中高等教育出版社出現(xiàn)了3次，其他元組出現(xiàn)了一次。關(guān)系V的一個實例如圖8-13所示，其中清華大學(xué)出版社元組出現(xiàn)了4次，其他元組均出現(xiàn)了一次。27包的并集運算如果關(guān)系U是一個包，其中元組tupleA出現(xiàn)了包的交集運算下面開始研究包的交集運算。如果關(guān)系U是一個包，其中元組tupleA出現(xiàn)了n次，關(guān)系V也是一個包，其中元組tupleA出現(xiàn)了m次。那么，在包U∩V的結(jié)果中，元組tupleA出現(xiàn)的次數(shù)是min(n，m)。例如，如果關(guān)系U和V的實例分別如圖8-12和8-13所示，那么U∩V的結(jié)果如圖8-15所示，即每個出版社都只出現(xiàn)了一次。28包的交集運算下面開始研究包的交集運算。如果關(guān)系U是一個包，包的差集運算包的差集運算也是一種集合運算。如果關(guān)系U是一個包，其中元組tupleA出現(xiàn)了n次，關(guān)系V也是一個包，其中元組tupleA出現(xiàn)了m次。那么，在包U―V的結(jié)果中，元組tupleA出現(xiàn)的次數(shù)是max(0，n―m)。29包的差集運算包的差集運算也是一種集合運算。如果關(guān)系U是一個包的投影運算圖8-9所示的關(guān)系實例就是圖8-10所示的關(guān)系實例投影的結(jié)果。需要注意的是，如果在投影過程中因為消除一個或多個屬性使得從幾個元組中產(chǎn)生出相同的元組，那么這些重復(fù)的元組不從包的投影結(jié)果中刪除。30包的投影運算圖8-9所示的關(guān)系實例就是圖8-10所示的關(guān)系包的笛卡爾乘積運算在包的笛卡爾乘積中，只需要將一個關(guān)系的每個元組和另外一個關(guān)系的每個元組匹配成對，不考慮這些元組是否重復(fù)。如果關(guān)系U是一個包，其中元組數(shù)量是n個，關(guān)系V也是一個包，其中元組數(shù)量是m個。那么，在包U×V的結(jié)果中，元組的數(shù)量n×m。例如，已知關(guān)系U和V的實例，那么包U×V的運算結(jié)果如圖8-17所示。包的乘積中屬性命名的方式與集合乘積運算中相同。31包的笛卡爾乘積運算在包的笛卡爾乘積中，只需要將一個關(guān)系的每包的選擇運算包的選擇運算與集合的選擇運算非常類似。在包的選擇運算中，把選擇條件應(yīng)用于每個元組，而不論這些元組是否重復(fù)。例如，如果關(guān)系U如圖8-12所示，那么包的選擇σname='高等教育出版社'(U)的結(jié)果如圖8-18所示?？梢娺x擇運算的結(jié)果依然是包。32包的選擇運算包的選擇運算與集合的選擇運算非常類似。在包的選包的邏輯運算包的運算不僅可以用于關(guān)系代數(shù)，而且也可以用于Datalog規(guī)則。即如果沒有求反的關(guān)系子目標(biāo)，那么包的投影、選擇、乘積和連接等運算形式可以同樣應(yīng)用于Datalog規(guī)則。當(dāng)把包的運算應(yīng)用于Datalog規(guī)則時，其運算步驟如下：第一步，對不同子目標(biāo)對應(yīng)的關(guān)系進(jìn)行包連接運算；第二步，按照算術(shù)子目標(biāo)包含的內(nèi)容，對連接運算的結(jié)果進(jìn)行包選擇運算；第三步，把選擇結(jié)果按照規(guī)則頭部的關(guān)系進(jìn)行包投影運算。33包的邏輯運算包的運算不僅可以用于關(guān)系代數(shù)，而且也可以用于D主要內(nèi)容8.1基本概念8.2關(guān)系代數(shù)向Datalog規(guī)則的轉(zhuǎn)換

8.3遞歸原理8.4包的運算8.5本章小結(jié)34主要內(nèi)容8.1基本概念34第8章Datalog語言本章概述本章的學(xué)習(xí)目標(biāo)主要內(nèi)容35第8章Datalog語言本章概述1本章概述關(guān)系代數(shù)是關(guān)系型數(shù)據(jù)庫的理論基礎(chǔ)，是數(shù)據(jù)庫產(chǎn)品應(yīng)用和發(fā)展的堅實基礎(chǔ)。隨著數(shù)據(jù)技術(shù)的不斷提高，關(guān)系代數(shù)也暴露出了一些局限性，例如，無法有效地表示遞歸運算、邏輯表達(dá)能力弱等。在這種情況下，Datalog語言應(yīng)運而生。Datalog語言是一種基于邏輯編程語言Prolog的一種非過程化的語言。同使用關(guān)系演算類似，用戶只需要給出所描述的信息，不需要給出獲取信息的具體過程。Datalog語言使用聲明的方式定義，簡化了簡單查詢的書寫，使查詢優(yōu)化更容易進(jìn)行。本章將要全面介紹Datalog語言的基本結(jié)構(gòu)、規(guī)則、遞歸編程以及從關(guān)系代數(shù)到Datalog語言的轉(zhuǎn)換等內(nèi)容。36本章概述關(guān)系代數(shù)是關(guān)系型數(shù)據(jù)庫的理論基礎(chǔ)，是數(shù)據(jù)庫產(chǎn)品應(yīng)用和本章的學(xué)習(xí)目標(biāo)了解Datalog語言的基本概念；掌握Datalog語言的基本結(jié)構(gòu)；掌握Datalog語言的基本規(guī)則；掌握從關(guān)系代數(shù)到Datalog語言的轉(zhuǎn)換過程；認(rèn)識和掌握Datalog語言的遞歸編程原理；理解包的概念和其在關(guān)系代數(shù)和Datalog語言中的作用。37本章的學(xué)習(xí)目標(biāo)了解Datalog語言的基本概念；3主要內(nèi)容8.1基本概念8.2關(guān)系代數(shù)向Datalog規(guī)則的轉(zhuǎn)換8.3遞歸原理8.4包的運算8.5本章小結(jié)38主要內(nèi)容8.1基本概念48.1基本概念邏輯也是一種表示關(guān)系查詢的方法，例如Datalog語言就可以表示相同類型的查詢。Datalog語言不是使用過程語言來表示查詢，而是使用一種規(guī)則來表示出這種想法，即可以通過已知的關(guān)系中的某些元組的組合推測某個其他元組是否在某個其他關(guān)系中。398.1基本概念邏輯也是一種表示關(guān)系查詢的方法，例如Dat基本結(jié)構(gòu)Datalog語言包括了兩種基本的原子，即關(guān)系原子和算術(shù)原子。Datalog語言是由這些原子按照一定的規(guī)則組成的。在Datalog語言中，關(guān)系通過稱為謂詞的符號來表示，每一個謂詞都有固定數(shù)量的參數(shù)。關(guān)系原子是由符號謂詞和其后的參數(shù)組成，關(guān)系原子也經(jīng)常簡稱原子。例如，如果謂詞是R，其參數(shù)分別是t1，t2，…，tn，那么R(t1，t2，…，tn)就是一個關(guān)系原子。算術(shù)原子是兩個算術(shù)表達(dá)式的比較。算術(shù)原子的值也是布爾值。40基本結(jié)構(gòu)Datalog語言包括了兩種基本的原子，即關(guān)系原子一般規(guī)則在前面講述的關(guān)系代數(shù)中，介紹了許多關(guān)系代數(shù)運算，例如集合、笛卡爾乘積和自然連接等。這些運算形式在Datalog語言中可以使用規(guī)則來描述。規(guī)則就是Datalog語言中描述各種原子元素關(guān)聯(lián)的規(guī)范，包括下列三個組成部分：1.一個稱為頭部的關(guān)系原子，其后是2.左向箭頭符號←，讀作if，其后是3.多個子目標(biāo)組成的規(guī)則體。這些子目標(biāo)既可以是關(guān)系原子，也可以是算術(shù)原子。各個子目標(biāo)之間用邏輯運算符AND連接，且各個子目標(biāo)前面可以有選擇地增加取反邏輯運算符NOT。41一般規(guī)則在前面講述的關(guān)系代數(shù)中，介紹了許多關(guān)系代數(shù)運算，例安全規(guī)則前面講過，Datalog語言是一種由許多原子構(gòu)成的規(guī)則，規(guī)則包含了許多變量。規(guī)則的目標(biāo)是使規(guī)則的頭部關(guān)系原子為真。由于關(guān)系實例總是有限，所以還需要由規(guī)則保證得到的頭部關(guān)系也都是有限的。如果得到的頭部關(guān)系是無限的，那么這種規(guī)則是無意義的。下面分析如何保證得到的查詢結(jié)果是有意義的。在子目標(biāo)中，包括了關(guān)系子目標(biāo)、求反關(guān)系子目標(biāo)、算術(shù)子目標(biāo)和求反算術(shù)子目標(biāo)。42安全規(guī)則前面講過，Datalog語言是一種由許多原子構(gòu)成的外延謂詞和內(nèi)涵謂詞外延謂詞和內(nèi)涵謂詞是兩個經(jīng)常提到的概念。當(dāng)謂詞所指的關(guān)系存儲在數(shù)據(jù)庫中時，稱該謂詞為外延謂詞。當(dāng)謂詞所指的關(guān)系是通過一個或多個Datalog規(guī)則計算得到的，稱該謂詞是內(nèi)涵謂詞。外延謂詞和內(nèi)涵謂詞之間的差別類似關(guān)系代數(shù)表達(dá)式的運算項和使用關(guān)系代數(shù)表達(dá)式計算的關(guān)系之間的差別。在Datalog規(guī)則中，如果謂詞分別是內(nèi)涵的或外延的，可以引用與內(nèi)涵的或外延的謂詞相對應(yīng)的關(guān)系。有時，使用IDB(InternalDatabase，內(nèi)涵數(shù)據(jù)庫)來引用內(nèi)涵謂詞或相應(yīng)的關(guān)系，使用EDB(ExternalDatabase，外延數(shù)據(jù)庫)來引用外延謂詞或相應(yīng)的關(guān)系。43外延謂詞和內(nèi)涵謂詞外延謂詞和內(nèi)涵謂詞是兩個經(jīng)常提到的概念。主要內(nèi)容8.1基本概念8.2關(guān)系代數(shù)向Datalog規(guī)則的轉(zhuǎn)換8.3遞歸原理8.4包的運算8.5本章小結(jié)44主要內(nèi)容8.1基本概念108.2關(guān)系代數(shù)向Datalog規(guī)則的轉(zhuǎn)換上一章介紹了關(guān)系代數(shù)的各種運算形式，本節(jié)將介紹各種Datalog規(guī)則形式。一般地，可以使用一個或多個Datalog規(guī)則來模擬關(guān)系代數(shù)的運算形式，并且可以模擬非常復(fù)雜的運算形式。本節(jié)主要研究如何從關(guān)系代數(shù)的基本運算形式以及連接運算形式轉(zhuǎn)換到Datalog規(guī)則。458.2關(guān)系代數(shù)向Datalog規(guī)則的轉(zhuǎn)換上一章介紹了關(guān)系從集合運算到Datalog規(guī)則集合運算是關(guān)系代數(shù)的最基本的運算形式，包括了交集、并集和差集三種運算形式。下面介紹如何使用Datalog規(guī)則模擬這三種集合運算形式。交集運算可以使用一個Datalog規(guī)則來表示。由于交集運算涉及了兩個關(guān)系，那么在Datalog規(guī)則中，具有與兩個關(guān)系對應(yīng)的子目標(biāo)。在規(guī)則中，相應(yīng)的參數(shù)使用相同的變量。并集運算可以使用兩個規(guī)則來表示。在Datalog規(guī)則中，每個規(guī)則都對應(yīng)著一個并集運算中的關(guān)系，且兩個規(guī)則的頭部都有相同的IDB謂詞。頭部的參數(shù)與各個子目標(biāo)中的參數(shù)完全相同。差集運算可以使用具有求反子目標(biāo)的一個規(guī)則來計算。即如果計算兩個關(guān)系U和V的差集，可以這樣來計算，非求反子目標(biāo)是謂詞U，求反子目標(biāo)是謂詞V。在該規(guī)則中，子目標(biāo)和頭部對于相應(yīng)的參數(shù)都有相同的變量。46從集合運算到Datalog規(guī)則集合運算是關(guān)系代數(shù)的最基本的從投影運算到Datalog規(guī)則把關(guān)系代數(shù)中的投影運算形式轉(zhuǎn)換成Datalog規(guī)則，可以使用一個具有單一子目標(biāo)的規(guī)則。該子目標(biāo)的參數(shù)是數(shù)量不同于關(guān)系的屬性數(shù)量的變量，每個變量都對應(yīng)著關(guān)系的一個屬性。頭部是帶有參數(shù)的原子，這些參數(shù)是按照要求的順序與投影的屬性表對應(yīng)的變量。頭部原子的這些變量只是子目標(biāo)投影過來的變量，因此兩者的數(shù)量不同。47從投影運算到Datalog規(guī)則把關(guān)系代數(shù)中的投影運算形式轉(zhuǎn)從笛卡爾乘積到Datalog規(guī)則兩個關(guān)系U和V的笛卡爾乘積U×V可以使用單一的Datalog規(guī)則來表示。在這個Datalog規(guī)則中，有兩個子目標(biāo)。一個子目標(biāo)對應(yīng)關(guān)系U，另一個子目標(biāo)對應(yīng)關(guān)系V。每個子目標(biāo)都有不同的變量，每個變量對應(yīng)著關(guān)系U或V中的一個屬性。頭部的關(guān)系原子把出現(xiàn)的兩個子目標(biāo)中的所有變量作為參數(shù)，且嚴(yán)格按照出現(xiàn)的先后順序，即出現(xiàn)在關(guān)系U子目標(biāo)中的變量排列在關(guān)系V子目標(biāo)的變量之前。48從笛卡爾乘積到Datalog規(guī)則兩個關(guān)系U和V的笛卡爾乘積從選擇運算到Datalog規(guī)則把關(guān)系運算中的選擇轉(zhuǎn)換成Datalog規(guī)則比較復(fù)雜。下面首先研究一種簡單的情況，然后再研究如何把具有復(fù)雜條件的選擇運算轉(zhuǎn)變成Datalog規(guī)則。如果選擇條件是一個算術(shù)比較表達(dá)式或多個比較表達(dá)式的AND運算，可以建立一個具有下列子目標(biāo)的Datalog規(guī)則：一個關(guān)系子目標(biāo)對應(yīng)于將其進(jìn)行選擇的關(guān)系。該關(guān)系子目標(biāo)的每個分量都有不同的變量，且每個分量都對應(yīng)關(guān)系的一個屬性；多個算術(shù)子目標(biāo)，每個算術(shù)子目標(biāo)都對應(yīng)著選擇條件的一個比較運算。雖然在選擇條件中使用屬性名，但是在算術(shù)子目標(biāo)中卻使用相應(yīng)的變量，并且與關(guān)系子目標(biāo)中建立的變量保持一致。49從選擇運算到Datalog規(guī)則把關(guān)系運算中的選擇轉(zhuǎn)換成Da從連接運算到Datalog規(guī)則連接包括了自然連接、θ連接和外部連接。這里主要介紹如何把自然連接和θ連接轉(zhuǎn)變成Datalog規(guī)則。連接運算非常類似于笛卡爾乘積的運算，因此可以使用像乘積的規(guī)則來表示兩個關(guān)系的自然連接，區(qū)別是如果希望表示關(guān)系U和V的自然連接UV，并且這兩個關(guān)系中有相同名稱的屬性，那么必須使用相同的變量，否則必須使用不同的變量。規(guī)則頭部是每一個變量都出現(xiàn)一次的IDB謂詞。50從連接運算到Datalog規(guī)則連接包括了自然連接、θ連接和從多重運算到Datalog規(guī)則關(guān)系代數(shù)中的單一運算形式可以使用Datalog規(guī)則表示，而且多重運算也可以使用Datalog規(guī)則模擬。模擬多重運算的步驟如下：第一步，繪制關(guān)系代數(shù)的表達(dá)樹。其中，表達(dá)樹就是使用樹狀結(jié)構(gòu)表示關(guān)系代數(shù)表達(dá)式的計算程序。第二步，為表達(dá)樹的每一個內(nèi)部節(jié)點建立一個IDB謂詞。51從多重運算到Datalog規(guī)則關(guān)系代數(shù)中的單一運算形式可以主要內(nèi)容8.1基本概念8.2關(guān)系代數(shù)向Datalog規(guī)則的轉(zhuǎn)換

8.3遞歸原理

8.4包的運算8.5本章小結(jié)52主要內(nèi)容8.1基本概念188.3遞歸原理遞歸是一種常見的算法，即如果一個過程直接或間接地調(diào)用它自身，稱該過程為遞歸過程。本節(jié)將要研究為什么使用和如何使用Datalog語言描述遞歸過程。538.3遞歸原理遞歸是一種常見的算法，即如果一個過程直接或關(guān)系代數(shù)存在的問題在數(shù)據(jù)的查詢過程中，經(jīng)常會遇到遞歸現(xiàn)象。例如，在出版社的人事管理中，經(jīng)理和雇員的問題就是一個遞歸問題。一個人可以是某些雇員的經(jīng)理，但是他又可能是另外一個經(jīng)理的雇員，經(jīng)理又可能是更高層經(jīng)理的雇員等多種情況。54關(guān)系代數(shù)存在的問題在數(shù)據(jù)的查詢過程中，經(jīng)常會遇到遞歸現(xiàn)象。計算最小固定點現(xiàn)在研究如何在關(guān)系代數(shù)中解決這種問題。假設(shè)關(guān)系Leader(a，b)表示了這種直接和間接經(jīng)理和雇員的聯(lián)系?？梢詫懗鱿旅娴姆匠?，這是一個包含了關(guān)系Leader和Human的方程式，Leader的值是滿足該方程式的最小關(guān)系，最小關(guān)系也稱為最小固定點。55計算最小固定點現(xiàn)在研究如何在關(guān)系代數(shù)中解決這種問題。21使用Datalog規(guī)則表示固定點公式通過上面的分析可以看到，使用關(guān)系代數(shù)表示固定點公式往往會非常復(fù)雜，使用Datalog規(guī)則表示則比較容易。下面研究如何使用Datalog規(guī)則表示固定點公式。使用Datalog規(guī)則表示固定點公式的思路是：假定一個或多個EDB關(guān)系已知，其他IDB關(guān)系則通過出現(xiàn)在規(guī)則的頭部來定義，規(guī)則體可能包含的謂詞是EDB或IDB的關(guān)系以及代數(shù)原子子目標(biāo)。56使用Datalog規(guī)則表示固定點公式通過上面的分析可以看到主要內(nèi)容8.1基本概念8.2關(guān)系代數(shù)向Datalog規(guī)則的轉(zhuǎn)換

8.3遞歸原理8.4包的運算8.5本章小結(jié)57主要內(nèi)容8.1基本概念238.4包的運算前面已經(jīng)講過，關(guān)系中的元組是集合，是一種自然的斷言。但實際上，在許多數(shù)據(jù)庫產(chǎn)品中，允許相同的元組在關(guān)系中重復(fù)出現(xiàn)。這時，關(guān)系中的元組不是集合，而是包。因此，我們不但需要理解集合的各種運算，還需要了解包是如何運算的。588.4包的運算前面已經(jīng)講過，關(guān)系中的元組是集合，是一種自包的意義集合中不允許元組重復(fù)出現(xiàn)，元組的順序不重要。列表不但不允許元組重復(fù)出現(xiàn)，而且元組的出現(xiàn)順序也是列表的重要特性。相對而言，包的要求比較寬松，既允許元組重復(fù)出現(xiàn)，又不重視元組的出現(xiàn)順序。圖8-9就是一個包的示例。在該示例中，清華大學(xué)出版社元組出現(xiàn)了5次，高等教育出版社元組出現(xiàn)了4次，機(jī)械工業(yè)出版社元組出現(xiàn)了3次。59包的意義集合中不允許元組重復(fù)出現(xiàn)，元組的順序不重要。列表不包的關(guān)系運算關(guān)系的基本運算包括并集、交集、差集、投影、笛卡爾乘積和選擇等形式下面研究如何對包進(jìn)行這些運算。60包的關(guān)系運算關(guān)系的基本運算包括并集、交集、差集、投影、笛卡包的并集運算如果關(guān)系U是一個包，其中元組tupleA出現(xiàn)了n次，關(guān)系V也是一個包，其中元組tupleA出現(xiàn)了m次。那么，在包U∪V的結(jié)果中，元組tupleA出現(xiàn)的次數(shù)是n+m。例如，如果關(guān)系U的一個實例如圖8-12所示，其中高等教育出版社出現(xiàn)了3次，其他元組出現(xiàn)了一次。關(guān)系