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

8.3遞歸原理

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

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

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

8.3遞歸原理

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

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