23第章基于邏輯的數(shù)據(jù)庫

1、第23章 基于邏輯的數(shù)據(jù)庫23.1引言在20世紀(jì)80年代中期，在數(shù)據(jù)庫研究領(lǐng)域出現(xiàn)了一個(gè)重要的研究方向，這就是基于邏輯的數(shù)據(jù)庫系統(tǒng)。這時(shí)有關(guān)邏輯數(shù)據(jù)庫、推理 DBMS、DBMS、演繹DBMS、知識(shí)庫、知識(shí)庫管理系統(tǒng)（ KBMS）、數(shù)據(jù)模型邏輯和遞歸處理等的相繼。然而，很難把這些術(shù)語和思想同熟悉的數(shù)據(jù)庫術(shù)語和概念起來；而且也很難從傳統(tǒng)數(shù)據(jù)庫的角度理解其潛在的研究。所以，從傳統(tǒng)的數(shù)據(jù)庫思想和原理去解釋所有這些問題就變得迫切。這一章試圖解決這一問題。我們的目標(biāo)是從傳統(tǒng)數(shù)據(jù)庫的角度去解釋什么是基于邏輯的系統(tǒng)，而并不是就邏輯談邏 輯。所以，當(dāng)我們介紹有關(guān)邏輯的新思想時(shí)，會(huì)用傳統(tǒng)的數(shù)據(jù)庫術(shù)語去解釋它，這樣

2、是可能 的，也是合適的（當(dāng)然，本書中已經(jīng)討論了一些有關(guān)邏輯的概念，特別是在第 7章介紹關(guān)系演算時(shí)。關(guān)系演算是直接基于邏輯的。但基于邏輯的系統(tǒng)中用到的邏輯概念要遠(yuǎn)不止這些）。本章的內(nèi)容如下： 23.2節(jié)將簡單地概述，并介紹一些歷史； 23.3節(jié)和23.4節(jié)分別簡單地介紹命題演算和謂詞演算； 23.5節(jié)介紹所謂的數(shù)據(jù)庫證明理論(proof-theoretic)；23.6節(jié)介紹演繹DBMS；23.7節(jié)介紹遞歸過程的一些方法；最后， 23.8節(jié)對(duì)本章作了小結(jié)。23.2綜述數(shù)據(jù)庫理論和邏輯之間的關(guān)系的研究至少追溯到 20世紀(jì)70年代后期，這一時(shí)期的可參看23.5、23.7和23.13。然而，近來在這一有

3、的領(lǐng)域的發(fā)展中，最基本的應(yīng)該是1984年Reiter的一篇具有里程碑意義的（參看 23.15）。在這篇里， Reiter認(rèn)為傳統(tǒng)的數(shù)據(jù)庫是模型理論。不嚴(yán)格地講，他認(rèn)為：a. 在任何時(shí)候，數(shù)據(jù)庫組；看作一系列明確的關(guān)系，每一個(gè)關(guān)系都包括一系列明確的元b. 執(zhí)行一個(gè)就是對(duì)這些確定的元組和關(guān)系執(zhí)行一些指定的（即表(truth-valued expression)）。在23.5節(jié)更加精確地解釋“模型理論”這一術(shù)語。注意：Reiter還認(rèn)為，一個(gè)可替換的證明理論的觀點(diǎn)在某些方面是可能的，并且是很好的。不嚴(yán) 格地講，它是指：a. 在任何時(shí)候，數(shù)據(jù)庫看作一系列公理（相應(yīng)于基本關(guān)系中的域和元組及某些所謂的“演

4、繹”公理來說，就是“基(ground axiom)）；是這些公理的邏輯結(jié)果，或者說，證明它是一b. 執(zhí)行一個(gè)些定理。就是證明一些確定的注意：我們也將在23.5節(jié)更加精確地解釋“證明理論”這一術(shù)語，我們會(huì)看到它和第 1章1.3節(jié)（參看“數(shù)據(jù)和數(shù)據(jù)模型”這一小節(jié)）介紹的數(shù)據(jù)庫的特征非常相似，是真命題的一個(gè)集合568第五部分 高 級(jí) 專 題（參看1.2）。下面是一個(gè)很適合的例子，它是基于供應(yīng)商-零件數(shù)據(jù)庫的關(guān)系演算SPX WHERE SPX.QTY > 250 ：（當(dāng)然，這里的SPX是定義在供貨表上的范圍變量）用傳統(tǒng)的即模型理論的解釋，供貨表中的元組一個(gè)接一個(gè)地依次執(zhí)行而且對(duì)于每個(gè)元組，此“

5、QTY>250”；結(jié)果僅僅包括一些供貨表的一些元組，取。相比之下，用證明理論解釋，我們就把供貨表的一些元組（還有其它的項(xiàng)）看作一定的“邏輯理論”的公理；在這一理論里，我們用明技術(shù)結(jié)果即去決定范圍變量SPX取哪些可能的值時(shí)，其邏輯結(jié)果為“ SPX.QTY>250”。此由SPX的這些特殊值。當(dāng)然，這個(gè)例子是非常簡單的，以至于很難辨別這兩種解釋之間的差別。但是，證明（即證明理論的解釋）的推理機(jī)制顯然比這個(gè)簡單的例子所表達(dá)的要復(fù)雜得多。會(huì)看到，它能解決那些經(jīng)典征（參看23.15）。所不能解決的問題，而且這一證明理論還有另外的很吸引人的特 描述統(tǒng)一性：用它定義的數(shù)據(jù)庫語言中，基本關(guān)系中的元組

6、和域值、“演繹公理”、和完整性約束基本上用統(tǒng)一的方法描述。 操作統(tǒng)一性：它為各種各樣明顯不同的問題的統(tǒng)一操作提供了一個(gè)基礎(chǔ)，這包括優(yōu)化（尤其是語義優(yōu)化）、完整性約束的實(shí)施、數(shù)據(jù)庫設(shè)計(jì)（依賴?yán)碚摚?、程序正確性證明 和其它的問題。 語義建模： 它為各種基本模型語義的擴(kuò)充提供了堅(jiān)實(shí)的基礎(chǔ)。 擴(kuò)充應(yīng)用：最后，它為處理用那些經(jīng)典的方法很難處理的問題提供了基礎(chǔ)，例如，對(duì)于 析取信息處理（如，供應(yīng)商 S5或者供應(yīng)了零件P1或者供應(yīng)了零件P2，但不知道它供應(yīng)了哪一個(gè)）。演繹公理下面將簡單扼要地解釋演繹公理這一概念（或者叫推理規(guī)則）?；菊f來，一個(gè)演繹公理 就是一個(gè)規(guī)則，它可從給定的事實(shí)推斷別的事實(shí)。例如，給定

7、事實(shí)“ Anne是Betty的母親”和“Betty是Celia的母親”，這里存在一個(gè)明顯的演繹公理，從而使我們推斷 Anne是Celia的祖母。因此，用前面所講的理論，就可以把這個(gè)演繹 DBMS中的兩個(gè)給定的事實(shí)描述為關(guān)系中的元組，即是：這兩個(gè)事實(shí)提供了此系統(tǒng)的基理：。我們?cè)偌僭O(shè)系統(tǒng)中以如下的形式給出這一演繹公（假設(shè)并簡化的語法）?，F(xiàn)在，用23.4節(jié)介紹的方法，系統(tǒng)把演繹公理所表達(dá)的規(guī)則應(yīng)用于上述基中的數(shù)據(jù)，從而推導(dǎo)出 GRANDMOTHER_OF(Anne,Celia)的結(jié)果。這樣用戶就可如下問題：誰是Celia的祖母？或誰是Anne的孫女？（或者，更精確地講， Anne是誰的祖母？）。第2

8、3章 基于邏輯的數(shù)據(jù)庫569現(xiàn)在把前面的思想與傳統(tǒng)的數(shù)據(jù)庫的概念為是一種視圖定義，例如：起來。從傳統(tǒng)的術(shù)語講，演繹公理可以認(rèn)（這里我們有意使用關(guān)系演算的形式； MX和MY分別是定義在MOTHER_OF上的范圍變量）。上面所述現(xiàn)在可基于視圖概念重寫如下 :（GX是定義在GRANDMOTHER_OF上的范圍變量）。到目前為止，我們所講的都只不過是對(duì)一些熟悉的例子給出不同語法和解釋。但是，在傳統(tǒng)的 DBMS之間的一些重要的區(qū)別是不能看到，實(shí)際上在基于邏輯的系統(tǒng)和用這些簡單的例子解釋清楚的。23.3命題演算在這一節(jié)和，我們對(duì)一些基本的邏輯思想作一些非常簡單的介紹。本節(jié)講命題演講謂詞演算。這里應(yīng)當(dāng)指出

9、,命題演算本身并不是最重要的；本節(jié)真正的目的僅僅算，是為的理解鋪平道路。這兩節(jié)合起來是章后面幾節(jié)提供基礎(chǔ)。的需要，下面列出了一些將用到的這里，大家需要熟悉代數(shù)的法則： 分配律：代數(shù)的概念。為了律：這里，f、g和h都是任意的表（結(jié)果為）。下面，談?wù)勥壿嫳旧?。邏輯可被定義為規(guī)范的推理方法。因?yàn)樗且?guī)范的，所以，它能 用作執(zhí)行規(guī)范的任務(wù)。如，只要檢查作為每一步結(jié)果的變?cè)Y(jié)構(gòu)，就能測試這個(gè)變?cè)恼_性（即，不必注意這些步驟本身）。特別因?yàn)樗且?guī)范化的，故它有按部就班的過程 即，它可以設(shè)計(jì)成程序，由所應(yīng)用。一般地講，命題演算和謂詞演算是兩個(gè)特殊的邏輯形式（實(shí)際上，前者是后者的子集）。相對(duì)于任何符號(hào)計(jì)算的

10、系統(tǒng)而言，“演算”僅是一般的術(shù)語；目前情況下，所涉及的各種計(jì)算是一定或表1. 項(xiàng)的（假）計(jì)算。假設(shè)有一些對(duì)象的集合，稱為。對(duì)這些，我們可作多種說明。在數(shù)據(jù)庫用語里，是域中的值，語句是諸如“ 3>2”的。把項(xiàng)定義成包含的語句，并且：a. 它不包含任何邏輯連接詞（下面將看到）或者括號(hào)；b. 可以明確地計(jì)算其結(jié)果為假。例如，“供應(yīng)商S1在”、“供應(yīng)商S2在”和“供應(yīng)商S1供應(yīng)零件P1”是項(xiàng)（用通常的樣本值計(jì)算，其值分別為真、假和真）。相比之下，“供應(yīng)商S1供應(yīng)零件p(p是一變量)”和“供應(yīng)570第五部分 高 級(jí) 專 題商S5在未來某一時(shí)刻供應(yīng)P1”就不是項(xiàng)，因?yàn)樗鼈儾荒苊鞔_地計(jì)算出取還是取假值

11、。2.下面，我們定義的概念。命題演算（更一般地講，謂詞演算）是以表的形式出現(xiàn)在數(shù)據(jù)庫中的。的計(jì)算是基于項(xiàng)的以及連接謂詞表。注意：1) 一個(gè)原子2) 符號(hào)“是一個(gè)表，其中沒有連接詞，也不包含括號(hào)?！北硎具壿嬏N(yùn)含連接。表fg 在邏輯上等價(jià)于表NOT f OR g。注意在第7章或其它章節(jié)里，我們使用“ IF.THEN.”表示這個(gè)連接。3) 為了表達(dá)一個(gè)請(qǐng)求的計(jì)算順序，通常對(duì)這些連接詞采取優(yōu)先次序（即NOT、AND、OR、，由高到低的次序）來減少要使用括號(hào)的數(shù)量。4) 一個(gè)命題，就是上面定義的一個(gè)（為了與保持一致性，這里使用了術(shù)語“”）。3. 推理規(guī)則下面討論命題演算的推理規(guī)則。這樣的規(guī)則有很多。其中

12、每一條規(guī)則式的語句：表述為下述形（這里符號(hào) 讀作“總是有”；為了能產(chǎn)生某些語句 即語句的語句，的確需要這樣的符號(hào)）。下面是此推理規(guī)則的一些例子：注意：這一推理規(guī)則特別重要。這叫假言推理規(guī)則。非正式地講，其含義是如果 f為真， 且f蘊(yùn)含g，則g一定為真。例如，下面的a 和b 都為真，a. 我沒有錢；b. 如果我沒有錢，不得不刷碟子； 則我們就一定能推斷c 也為真：c. 我不得不刷碟子。下面仍是這一推理規(guī)則的一些例子：注意：這是另一個(gè)特別重要的規(guī)則，叫作歸結(jié)規(guī)則。在下面要講的“證明”一節(jié)和第23.4節(jié)將詳細(xì)討論。第23章 基于邏輯的數(shù)據(jù)庫5714. 證明方法過程現(xiàn)在，我們討論形式證明的方法問題（在

13、命題演算的范疇）。這就是決定是否一給定的公式g (結(jié)論)是另一些給定的f1、f2、., fn（前提）的邏輯結(jié)果，用符號(hào)表示就是：（讀作“從f1、f2、., fn推導(dǎo)出g”；注意這里使用的另一個(gè)元語言符號(hào)“ ”）。這種基本方法叫做前向推理(forward chaining)。前向推理就是對(duì)這些前提、由這些前提導(dǎo)出的、由這些導(dǎo)出的，等等重復(fù)運(yùn)用推理規(guī)則，直到推導(dǎo)出所需要的結(jié)論；或者說這一過程就是從前提到結(jié)論的“正”。然而，對(duì)這一基本的論題，下面還有幾個(gè)變種：1) 附加一個(gè)前提： 如果g是p提及p推導(dǎo)出來。2) 反向推理： 不直接去證明p3) 反證法：不是直接去證明pq的形式，采用p作為附加的前提，

14、并表明 q可從給定的前q，而是去證明其逆否命題，即NOT qNOT P。q，而是先假設(shè)p和NOT q為真，再推導(dǎo)出相互的結(jié)果。4) 歸結(jié)：這種方法要使用歸結(jié)推理規(guī)則（如上述的第條推理）?，F(xiàn)在我們來具體地討論歸結(jié)規(guī)則。它有著廣泛的應(yīng)用（特別地，它可以推廣到謂詞演算 的情況。這在23.4節(jié)將會(huì)看到）。首先要注意，歸結(jié)規(guī)則是很有效的。運(yùn)用它，可以消除一些子。如，給出兩個(gè)：f OR ga n dNOT g OR h我們可以刪去g和NOT g，得到如下簡化的f OR h特別地，若有f OR g 和 NOT g（即h取：），則可以導(dǎo)出f。因此，一般情況下，這些規(guī)則運(yùn)用在兩個(gè)與（ AND）上，并且每一個(gè)是兩

15、個(gè)公式的或（ OR）。下面，我們運(yùn)用這一歸結(jié)規(guī)則（為了使討論更加具體化，用一特殊的例子來解釋這一過程）。假設(shè)希望知道下面的假設(shè)證明是否有效：（這里A、B、C和D都是寫在不同的行，如下所示：）。現(xiàn)在，我們采用附加的前提，即這個(gè)結(jié)論，并把每個(gè)前提這四行隱含著與（ AND）連接?，F(xiàn)在，我們把每一行轉(zhuǎn)化為合取范式，即一個(gè)或一個(gè)以上的、由 AND連接起來的，每一個(gè)的可能包含 NOT和OR，但不包含AND（參看第17章）。當(dāng)然，第二行和第三行已符合要求。為了轉(zhuǎn)化其它兩行，首先我們根據(jù) NOT和OR連接的定義，刪除掉所有的符號(hào)“”；接著，必要的時(shí)候運(yùn)用分配律和律；同時(shí)刪除掉冗余的括號(hào)和鄰近的 NOT，這樣得

16、到:接著，對(duì)于任何包括 ANDs的行，把它轉(zhuǎn)化為一系列的行，每一行是一個(gè)由 AND連接的（即在這一過程中刪掉AND）。此例中，這一步僅用在第四行?，F(xiàn)在，前提看起來如下所572第五部分 高 級(jí) 專 題示：下面，我們開始運(yùn)用歸結(jié)規(guī)則。先選擇能被歸結(jié)的兩行，即分別包含某個(gè)特殊的形式。我們選擇頭兩行，它們分別包含 NOT A 和A，歸結(jié)它們，得到：及其（注意：在一般情況下，我們需要保留原始的兩行，但在這個(gè)特殊的例子里，我們不再需要它們了）。再一次選擇頭兩行，運(yùn)用這一規(guī)則（歸結(jié) NOT B 和B），得：還是選擇頭兩行（ NOT D和D），得：再處理頭兩行（ NOT C和C）；最后的結(jié)果是命題的空集（通常

17、表示為 ），這是一個(gè)這樣，通過反證法，所要求的結(jié)果就被證明了。23.4謂詞演算現(xiàn)在，我們來討論謂詞演算。命題演算和謂詞演算之間最大的區(qū)別在于后者中有變量和量詞，這使得它的功能更為強(qiáng)大，應(yīng)用更。例如，語句“供應(yīng)商 S1供應(yīng)零件p”和“某位供應(yīng)商s供應(yīng)零件p”在命題演算中不合法，但在謂詞演算中它們是合法的。因此，謂詞演算給我們表達(dá)如下的提供了基礎(chǔ)：“S1供應(yīng)了哪些零件？”或“供應(yīng)某一零件的供應(yīng)商”，甚至“1. 謂詞根本不供應(yīng)任何零件的供應(yīng)商”。正如第3章解釋的那樣，一個(gè)謂詞就是一函數(shù)，即給出合適的自變量參數(shù)，其返回結(jié)果為函數(shù)。例如，“>x,y” 更一般地寫作“x>y” 是一個(gè)有著兩個(gè)參

18、數(shù)的謂詞，即x和y；如果相應(yīng)于 x的變?cè)笥谙鄳?yīng)于 y的變?cè)瑒t它返回；否則，返回假值。一個(gè)用了n個(gè)變?cè)闹^詞（即，這個(gè)謂詞由 n個(gè)參數(shù)所定義）叫做 n元謂詞。一個(gè)命題（ 23.3節(jié)所講的）可以認(rèn)為是零元謂詞，沒有參數(shù)，并且其結(jié)果明確地為假。假設(shè)相應(yīng)于“ =”、“>”、“”等的謂詞是固有的（即它們是定義的規(guī)范系統(tǒng)的一部分），并且用一種習(xí)慣的方式將使用它們的表寫出來。當(dāng)然，用戶也應(yīng)能定義他們的謂詞。整個(gè)問題的關(guān)鍵就是：實(shí)際上用數(shù)據(jù)庫的術(shù)語講，一個(gè)用戶定義的謂詞相應(yīng)于一個(gè)用戶定義的關(guān)系變量（從前面幾章我們也可以了解這一點(diǎn)）。例如，供應(yīng)商的關(guān)系變量 S，可以看作有著四個(gè)參數(shù)的謂詞，即S#、SN

19、AME、STATUS和CITY。而且，表S（S1,Smith,20,London）和S(S6,White,45,Rome)分別表示該謂詞結(jié)果為“實(shí)例”，或者“實(shí)例化” , 或者“調(diào)用”。非正式地講，正像前面幾章所講的那樣（特別是第 8章），我們可以把這些謂詞 , 與可能這里的變量是邏輯變量 ,并不是程序語言中的變量。就討論的目的而言，可以把它當(dāng)作第 7章中的所講的范圍變量。第23章 基于邏輯的數(shù)據(jù)庫573的完整性約束(同時(shí)也是謂詞）一起作為數(shù)據(jù)庫內(nèi)容的定義。2. 合式是擴(kuò)展“”的定義。為了避免與前面幾節(jié)講的（實(shí)際上，那是特殊的情形）的語法：，現(xiàn)在我們轉(zhuǎn)到第 7章所講的合式這一術(shù)語（ WFF）。

20、下面是一簡單的合式幾點(diǎn)說明：1) 簡單地講，一個(gè)項(xiàng)（< term>）可能不是“謂詞實(shí)例”（如果把謂詞看作函數(shù)，那么一個(gè)謂詞實(shí)例就是那個(gè)函數(shù)的調(diào)用）。每一個(gè)變?cè)?<argument>）必須是一個(gè)、一個(gè)變量名或一個(gè)函數(shù)調(diào)用，而函數(shù)調(diào)用的每一個(gè)變必須是這樣。在零元謂詞里可以刪去變?cè)斜恚?<argument commalist>）(可選的)及相應(yīng)的括號(hào)。注意：為了WFF能使用包括諸如“ + (x,y) ”（更一般地寫作“ x+y”）的計(jì)算表謂詞的函數(shù)上的函數(shù)。，可以使用建立在作為2) 正如23.3節(jié)講的那樣，為了減少因表達(dá)計(jì)算順序而引入的括號(hào)數(shù)目，我們對(duì)連接詞使

21、用優(yōu)先規(guī)則(即 NOT、AND、OR、按優(yōu)先級(jí)排列)。3) 假設(shè)大家熟悉量詞EXISTS和FORALL。注意：這里講的僅是一階謂詞演算，其基本意思是：(a)它沒有“謂詞變量”（即約束。具體請(qǐng)看第7章練習(xí)7.9。值是謂詞的變量），因此(b)謂詞本身并沒有受到4)律可以推廣應(yīng)用到合式，如下：這一點(diǎn)也將在第7章討論。5) 現(xiàn)在重復(fù)一下第7章另一個(gè)要點(diǎn)：在一個(gè)給定的WFF里，每一個(gè)變量的要么是自由的，要么是約束的。一個(gè)是約束的，是指 (a)它緊跟一個(gè)量詞（即它表示約束的變量）；或者(b)位于量詞的范圍內(nèi)并參照可適用的的約束變量。一個(gè)變量當(dāng)且僅當(dāng)它不是約束的。是自由的，6) 一個(gè)封閉的合式不包含自由變量

22、（實(shí)際上，它是一個(gè)命題）。一個(gè)開放的合式就是一個(gè)不封閉的合式模型。3.合式是什么意思呢？為了形式化地回答這個(gè)問題，我們引入了釋義（interpretation）這一概念。一系列合式的義如下： 首先，我們指定要解釋這些合式所需要的論域（universe of discourse ）?；蛘哒f，在 (a)規(guī)范系統(tǒng)所（用數(shù)據(jù)庫的術(shù)語講，就是域值）和 (b)真實(shí)世界的對(duì)象之的間指定一映象。每一個(gè)單個(gè)的明確地對(duì)應(yīng)于論域中的一個(gè)對(duì)象。 第二，根據(jù)論域中的對(duì)象，為每個(gè)謂詞指定一個(gè)含義。 最后，根據(jù)論域中的對(duì)象，為每個(gè)函數(shù)指定一個(gè)含義。574第五部分 高 級(jí) 專 題這樣，這一所作的定義。包括論域、論域中的對(duì)象與

23、之間的映象、根據(jù)論域?qū)χ^詞和函數(shù)下面舉例說明。設(shè)論域是整數(shù)集 0,1,2,3,4,5，2以明顯的方式對(duì)應(yīng)于此論域中的某對(duì)象，設(shè)謂詞“ x>y”定義成通常的含義（若需要的話，也可定義諸如“ +”、“-”等函數(shù)）?，F(xiàn)在，我們給下面的合式賦，如下所示：但是，注意，存在其它的釋義是可能的。例如，我們可以給論域取一系列安全分類級(jí)別，如下：這里謂詞“ >”就表示“更安全的（即更高的安全級(jí)別）”。現(xiàn)在，大家可能覺得上面的兩個(gè)可能的釋義在形式上是一樣的，即在它們之間建立一一對(duì)應(yīng)關(guān)系是可能的，且從更深一層次講，這兩個(gè)釋義其實(shí)就是一個(gè)。但是必須知道，釋義可以存在真正的不同。例如，我們把論域定義為 05

24、的整數(shù)，但是定義謂詞“ >”為相等（當(dāng)然，這樣做會(huì)引起是取真。，但至少這是合法的）?，F(xiàn)在上面的第一個(gè)合式就取假而不另一點(diǎn)必須明確的是，從前述的意義講，這兩個(gè)釋義可能是真正的不同，但是對(duì)某些給定合式集，它們都取同樣的。在我們的例子里，如果刪除合式“ 2 > 1”，則對(duì)于“>”的兩個(gè)不同的定義，就會(huì)出現(xiàn)這種情況。還需要注意的是，迄今為止，這一小節(jié)所討論的合式都是封閉式合式。這是因?yàn)閷?duì)每一個(gè)給定的封閉的合式，總能明確地給它賦一個(gè)。但是，開放的合式的依賴于賦給自由變量的值。例如，開放的合式：很明顯，只要 x 比3 大，其值為真，否則其值為假（無論“大于”和“ 3 ”在這里表示 什么）

25、?，F(xiàn)在，我們來解釋被釋義的一組合式（必須是封閉的）的模型，對(duì)于這個(gè)釋義，所有其中的合式為真。對(duì)于整數(shù) 05，考慮下面四個(gè)合式：上面給出的兩個(gè)釋義并不是這些合式的模型。因?yàn)樵谀欠N釋義下，其中某些合式結(jié)的模果為假。相比之下，上面的第一個(gè)釋義（即“ >”定義為“大于”）應(yīng)該是下面合式型：最后還要注意，因?yàn)閷?duì)于給定的一組合式能接受幾種釋義，且其中的合式為真，因此它就有幾個(gè)模型（一般地講）。所以，用模型理論的觀點(diǎn)來講，一個(gè)數(shù)據(jù)庫僅僅是一組合第23章 基于邏輯的數(shù)據(jù)庫575式。具體見23.5節(jié)。4. 子句式就像任何一個(gè)命題演算轉(zhuǎn)化為合取范式一樣，任何一個(gè)謂詞演算合式轉(zhuǎn)化為子句式，它被認(rèn)為是合取范式的

26、擴(kuò)展形式。進(jìn)行這種轉(zhuǎn)化的結(jié)規(guī)則運(yùn)用于構(gòu)建和驗(yàn)證證明。在于，我們可以把歸這一轉(zhuǎn)化過程如下（這里是概括性的，詳細(xì)請(qǐng)看 23.10）。通過下述例子來解釋這些步驟。這里p和q是謂詞， x、y和z是變量。1) 刪除符號(hào)“”。此例中，這個(gè)轉(zhuǎn)化沒有影響。2) 使用般的合式定律，刪去兩個(gè)鄰近的 NOT。刪去NOT，以便使它僅適合于項(xiàng)，而不適合一。該轉(zhuǎn)化仍對(duì)此例沒有影響。3) 把所有的量詞都移到前面，從而將這些重命名變量：轉(zhuǎn)化為前束范式。如果有必要，可系統(tǒng)地4) 注意一個(gè)有存在量詞的量化的合式：等價(jià)于合式：其中a對(duì)于合式。最初的合式中存在 a這樣的未知，我們不知道其值。同樣，：等價(jià)于合式：其中，全稱量詞u的函數(shù)

27、f是未知的。這里a和函數(shù)f分別命名為（Skloem）（Skloem）函數(shù)，這一命名來自于邏輯學(xué)家T.A.Skloem（注意：一個(gè)Skloem和僅是一個(gè)沒有變?cè)腟kloem函數(shù)）。因此，就是通過取代相應(yīng)的約束變量而刪除存在量詞。其中，這些變量由下式的量詞前面的全稱量詞的Skloem函數(shù)（任意的）所限制：5) 現(xiàn)在，所有的變量都被全稱量詞約束。因此，我們可以習(xí)慣上將所有的變量都隱含為全稱量詞約束，刪除所有的顯式量詞：6) 將合式轉(zhuǎn)化為合取范式，即由AND連接的子句，每一子句只可能有NOT或OR，而沒有 AND。此例中，此合式7) 刪去AND，把每個(gè)子句寫在已是這種形式。的行上，如下：這一子句等價(jià)

28、于最初的合式。注意：可以從上述的過程得出，用子句形式的一個(gè)合式且每一個(gè)占一行，形式如下：的一般形式就是一組子句，576第五部分 高 級(jí) 專 題這里A和B都是正項(xiàng)。我們可以轉(zhuǎn)化這個(gè)子句，如下所示：如果最多有一個(gè) B（n=0或1），則這個(gè)子句叫做 Horn子句，它是以邏輯學(xué)家Alfred Horn命名的。5. 使用歸結(jié)規(guī)則下面討論基于邏輯的數(shù)據(jù)庫系統(tǒng)對(duì)的處理過程。我們沿用 23.2節(jié)結(jié)束時(shí)的那個(gè)例子。首先，有謂詞 MOTHER_OF，它包括兩個(gè)參數(shù)，分別表示母親與女兒，再給出下面兩個(gè)項(xiàng)（謂詞實(shí)例）：給出下面的合式（演繹公理）：（注意這是一個(gè) Horn子句）。為了簡化歸結(jié)規(guī)則的運(yùn)用，我們刪去上式中的

29、符號(hào)“ Þ”，如下：現(xiàn)在證明Anne是Celia的祖母 即如何回答這個(gè)已經(jīng)證明了的結(jié)論，而把它作為前提：“ Anne是Celia的祖母嗎？”，現(xiàn)在我們?yōu)榱藨?yīng)用歸結(jié)規(guī)則，必找到兩個(gè)子句，分別包含一個(gè)合式及它的，并系統(tǒng)地給變量賦值。這樣的賦值是合法的，因?yàn)檫@些變量都已隱含為全稱量詞約束，所以對(duì)于每一種變量的值的組合，單個(gè)的合式兩個(gè)子句可歸結(jié)的值的過程叫做合一。（非的）必須為真。注意：尋找一系列使這下面用例子表明上述過程如何進(jìn)行，注意到 4和5分別包含項(xiàng)GRANDMOTHER_OF(x,z)和NOT GRANDMOTHER_OF(Anne,Celia)。因此，我們用Anne取代x，用Cel

30、ia取代y并歸結(jié)，得：第二條包括MOTHER_OF(Betty,Celia)。我們用Betty取代上面6中的y并歸結(jié)，得：歸結(jié)上面的 7 和1，我們得空子句集，從而Anne是Ceila的祖母”。對(duì)于“ Anne的孫女是誰？”又怎么樣呢？首先注意到，系統(tǒng)不知道孫女，它只知道祖母。我們可增加另一演繹公理，用于說明 z是x的孫女，當(dāng)且僅當(dāng)x是z的祖母（此數(shù)據(jù)庫中不有）。當(dāng)然，也可以把這個(gè)問題敘述為“ Anne是誰的祖母？”。我們來討論后面一個(gè)。前提是（和以前一樣）：。所以，起初的應(yīng)是“是的，第23章 基于邏輯的數(shù)據(jù)庫577我們引入第四個(gè)前提，如下：這個(gè)新前提直觀地表明要么Anne不是任何人的祖母，要

31、么有某個(gè)人 r屬于這一結(jié)果（因?yàn)樗莚的祖母）。我們希望發(fā)現(xiàn)r的。可如下進(jìn)行：首先，用Anne取代x，r取代z，并歸結(jié)上面的3和4，得：接著，用Betty取代y，并歸結(jié)上面的5和1，得：現(xiàn)在，Celia取代z，并歸結(jié)上面的6和2，得：因此，Anne是Celia的祖母。注意：如果給出一個(gè)附加項(xiàng)，如下：這樣我們就能在最后一步用Delia（不是Celia）取代z，得：當(dāng)然，在結(jié)果中，用戶期望看到兩個(gè)名字。這樣，系統(tǒng)就需要運(yùn)用合一和歸結(jié)過程去生成所有可能的結(jié)果。進(jìn)一步的細(xì)節(jié)已超出本討論的范圍。23.5數(shù)據(jù)庫的證明理論觀點(diǎn)正像23.4節(jié)解釋的那樣，一個(gè)子句就是下述形式的一個(gè)表：這里A和B都是下述形式的項(xiàng)

32、：(其中r是謂詞， x1、x2、., xt是它的變?cè)?。參看23.12，考慮該一般結(jié)構(gòu)中兩個(gè)重要的特殊的情況： 情況1：m=0, n=1這種情況下，這個(gè)子句可簡單地寫為：B 1或者寫為（刪去蘊(yùn)含符號(hào)）：其中r為謂詞，x1、x2、., xt為變?cè)?。如果x都是（ground，則此子句表示一個(gè)基axiom） 即其結(jié)果明確地為真。在數(shù)據(jù)庫項(xiàng)里，這樣的語句相對(duì)應(yīng)于關(guān)系變量R的一個(gè)元組。謂詞r相對(duì)應(yīng)于關(guān)系變量R的“含義”，本書的其它一些地方解釋過這一點(diǎn)。例如，在供應(yīng)商和零件數(shù)據(jù)，有一個(gè)關(guān)系變量叫SP，它的意思是某一個(gè)供應(yīng)商（S#）以某一數(shù)量(QTY)供應(yīng)某一零件(P#)。這個(gè)含義相對(duì)應(yīng)于一個(gè)開放式合式，因

33、為它包含自由變或者對(duì)應(yīng)中的一個(gè)值。578第五部分 高 級(jí) 專 題量（S#，P#，QTY）的。相比之下，元組（ S1，P1，300） 其變是是一個(gè)基或封閉式合式，它明確地表示供應(yīng)商S1供應(yīng)了300個(gè)零件P1。 情況2：m>0, n=1在這種情況下，子句采用下述形式：這叫做演繹公理；它根據(jù)蘊(yùn)含符號(hào)左邊的謂詞給右邊的謂詞定義（此定義可能（參看前面例子中的GRANDMOTHER_OF謂詞的定義）。全）或者，這樣的子句可被定義為完整性約束（使用第8章的術(shù)語，即一個(gè)關(guān)系變量約束）。 例如，供應(yīng)商變量S有兩個(gè)屬性S#和CITY，則子句：表達(dá)了這樣的約束： CITY函數(shù)依賴于S#。注意這里固有謂詞“ =

34、”的使用。正如前面討論所解釋的那樣，關(guān)系（“基”）中的元組、導(dǎo)出關(guān)系（“演繹公理”）及完整性約束是一般子句結(jié)構(gòu)的特殊情形?，F(xiàn)在來看一看對(duì)于 23.2節(jié)所講的數(shù)據(jù)庫的“證明理論”的觀點(diǎn)，是如何由這些思想導(dǎo)出的。首先，數(shù)據(jù)庫的傳統(tǒng)觀點(diǎn)被認(rèn)為是模型理論。這里講“傳統(tǒng)觀點(diǎn)”，是指數(shù)據(jù)庫被理解為由顯式命名關(guān)系變量的集合組成，每一個(gè)關(guān)系變量列顯式元組及顯式完整性約束組成。正是基于這種理解，所以這種觀點(diǎn)刻畫為模型理論?？聪旅娴慕忉專?基本（ underlying）的域包括值或，它們被假設(shè)代表“現(xiàn)實(shí)世界”（更精確地講，像23.4節(jié)那樣，是某種釋義）中一定的對(duì)象。這樣它們就對(duì)應(yīng)于論域。 關(guān)系變量（更精確地講，是

35、關(guān)系變量頭部）表示一系列謂詞或者開放式合式，且這在此論域上釋義。例如，關(guān)系變量頭 SP表示謂詞“供應(yīng)商S#以數(shù)量QTY供些合式應(yīng)零件P1”。 給定的關(guān)系變量里的每一個(gè)元組表示一個(gè)相應(yīng)謂詞的實(shí)例；即表示在這個(gè)論域里結(jié)果明確為真題（一個(gè)封閉的合式，它沒有變量）。，并且它們?cè)谕挥蛏厢屃x。所以，這些數(shù)據(jù)并沒有 完整性約束也是封閉式合式（不可能）違背這些約束，這些約束結(jié)果必須為真。 元組和完整性約束在一起就被看作一組公理，它定義某種邏輯理論（不嚴(yán)格地講，一個(gè)“理論”在邏輯上就是一組公理）。由于在這一釋義里，這些為真，所以從 23.4節(jié)所述的意義講，該是邏輯理論的模型。注意到正如前一節(jié)所指出的，這個(gè)模型

36、不是唯一的，即一個(gè)給定的數(shù)據(jù)庫可能有幾個(gè)釋義，從邏輯的角度講，所有這些釋義都是同 樣有效的。因此，在模型理論的觀點(diǎn)里，按“模型”的術(shù)語講，數(shù)據(jù)庫的含義就是模型。并且由于有許多可能的模型，故有許多可能的意義，至少從理論上講是這樣的 。而且，在模型理論觀點(diǎn)下的過程基本上就是計(jì)算某一個(gè)開放的合式的過程。這一過程是為了發(fā)現(xiàn)在這取。一模型里，合式中哪一個(gè)自由變量使得這個(gè)合式信息（即一個(gè)“ NOT S# （S9）”形式題，表示 S9然而，如果我們假設(shè)數(shù)據(jù)庫不顯式地包含任何不是一個(gè)供應(yīng)商號(hào)），則將有一個(gè)最小的或規(guī)范的意義，這就是所有可能模型的交集（參看 23.10）。而且，在這種情況下，這一規(guī)范的意義與在證

37、明理論的觀點(diǎn)下的數(shù)據(jù)庫的意義一樣。這會(huì)在以后的適當(dāng)時(shí) 候解釋。第23章 基于邏輯的數(shù)據(jù)庫579模型理論的觀點(diǎn)內(nèi)容很豐富。然而，為了能運(yùn)用 23.3節(jié)和23.4節(jié)所講的推理規(guī)則，就必須采用一個(gè)不同的視角。在這個(gè)視角中，數(shù)據(jù)庫被明確地看作一定的邏輯理論，即作為一系列公理。這樣，數(shù)據(jù)庫的意義就精確地變成所有真語句的集合，而這些真語句是從一些公理演繹來的，即能由那些公理證明的定理。這就是證明理論的觀點(diǎn)。用這一觀點(diǎn)，工作就變成是一個(gè)證明理論的過程（任何情況下，從概念上講是這樣的；但是，為了有更好的效率，系統(tǒng)可能還要使用的傳統(tǒng)的技術(shù)。 23.7節(jié)再講這一點(diǎn)）。注意：從前面一段可以得出，直觀上模型理論與證明

38、理論的觀點(diǎn)間的區(qū)別是，在模型理 論的觀點(diǎn)中，一個(gè)數(shù)據(jù)庫有許多“意義”，而在證明理論的觀點(diǎn)中，一個(gè)數(shù)據(jù)庫僅有一個(gè)“意義”。但是（ a）正如前面指出的，在模型理論中，數(shù)據(jù)庫的意義是真正的規(guī)范的意義，并在任何情況下，（b）一般地講，如果數(shù)據(jù)庫包含任何一個(gè)數(shù)據(jù)庫只有一個(gè)意義就不再成立參看23.923.10。的公理，則在證明理論情形下，證明理論的觀點(diǎn)中，給定數(shù)據(jù)庫的公理可總結(jié)如下（非正式的）：1) 基相對(duì)于庫關(guān)系變量中域值或元組值。這些公理有時(shí)組成了所謂的外延數(shù)據(jù)庫（相對(duì)于內(nèi)涵數(shù)據(jù)庫，見）。2) 每一個(gè)關(guān)系變量的“完整公理 (completion axiom)”表明，我們所講的關(guān)系變量中有效元組的失效可

39、被解釋為相對(duì)于此元組題是（當(dāng)然，實(shí)際上，這些完整化公理在一起就了封閉世界假說，這在第7章已經(jīng)討論了）。例如，供應(yīng)商變量S不包括元組（S6,White,45,Rome）就是命題“存在供應(yīng)商S6，它的名字是White,它的等級(jí)是45， 它住在羅馬”為假。3) “唯一命名”公理，表明每一個(gè)都不同于其它的任何，即它有唯一名。4) “域閉包”公理，表明不存在數(shù)據(jù)庫域以外的。5) 一組定義固有等價(jià)謂詞的基謂詞。需要這組公理，是因?yàn)樯厦娴?2、3、4利用了等價(jià)現(xiàn)在，我們對(duì)模型理論和證明理論這兩個(gè)概念之間的基本區(qū)別作簡短的小結(jié)。首先，有 人說，僅從實(shí)用的角度講，它們之間根本沒有什么區(qū)別，至少從今天的 DBMS

40、的角度講是這樣的。但是： 對(duì)于證明理論的觀點(diǎn)，上述 25作了一定的明確假設(shè)，而在模型理論的觀點(diǎn)中，這一假設(shè)隱含在釋義的概念中（參看 23.15）。明確地列出這些假設(shè)在一般情況下是一好的思想；而且，為了能應(yīng)用一般的證明理論的技術(shù)（如在 23.3節(jié)和23.4節(jié)講的確指定這些公理是必要的。 注意到上述公理沒有講到完整性約束規(guī)則。這是因?yàn)槿绻由线@些約束（在證明理論的 觀點(diǎn)里），系統(tǒng)就變?yōu)檠堇[DBMS。23.6節(jié)討論這一問題。 證明理論的觀點(diǎn)確實(shí)有一定的優(yōu)雅性，而模型理論的觀點(diǎn)則沒有。因?yàn)樗鼮橐恍┙Y(jié)構(gòu)提 供了統(tǒng)一的理解，而這些結(jié)構(gòu)通常被認(rèn)為有或多或少的不同。這些結(jié)構(gòu)有：基本數(shù)據(jù)、完整性約束（雖然是以前

41、的觀點(diǎn)）、虛擬數(shù)據(jù)，等等。所以，更統(tǒng)一的接口和更統(tǒng)一的實(shí)現(xiàn)的可能性就提高了。方法），明 證明理論的觀點(diǎn)也為那些取信息（例：供應(yīng)商S6住在在傳統(tǒng)上有處理的問題提供了良好的基礎(chǔ)。如析還是巴黎），信息導(dǎo)出（例：誰不是供應(yīng)商？）、遞歸（講到）等。對(duì)遞歸，盡管幾個(gè)商業(yè)系統(tǒng)已能夠加以處理（參看附錄580第五部分 高 級(jí) 專 題B），但原則上還不知道為什么經(jīng)典在23.6節(jié)和23.7節(jié)詳細(xì)討論這一問題。不能被合適地?cái)U(kuò)展去解決此類。 最后，Reiter的話(參看23.15)，就是證明理論的觀點(diǎn)“為關(guān)系模型（擴(kuò)展的）和現(xiàn)實(shí)世界語義的結(jié)合提供了正確的處理方法”（23.2節(jié)還將講到）。23.6演繹數(shù)據(jù)庫系統(tǒng)一個(gè)演繹D

42、BMS就是支持證明理論觀點(diǎn)的DBMS。特別地，對(duì)給定的外延數(shù)據(jù)庫中的事實(shí)運(yùn)用指定的演繹公理或推理規(guī)則，就可以從這些事實(shí)演繹或推導(dǎo)別的事實(shí)。演繹公理和完整性規(guī)則（下面將討論）合在一起有時(shí)就叫做內(nèi)涵數(shù)據(jù)庫。外延數(shù)據(jù)庫和內(nèi)涵數(shù)據(jù)庫合在一起就了通常講的演繹數(shù)據(jù)庫（這不是一個(gè)很恰當(dāng)?shù)男g(shù)語，因?yàn)樗沁\(yùn)用演繹原理的DBMS，而不是數(shù)據(jù)庫）。正如剛剛所講的，演繹公理了內(nèi)涵數(shù)據(jù)庫的一部分，而另一部分是表示完整性約束的公理（這些規(guī)則的主要目的是約束更新，實(shí)際上它們也可以用在從給定事實(shí)演繹另外的事 實(shí)的推理過程中）?，F(xiàn)在我們來看一看圖3-8所示的供應(yīng)商和零件數(shù)據(jù)庫，其在“演繹 DBMS”中的形式如何。首先，這里有一

43、系列基定義了一些合法的域值。注意：在這里，為了可讀性，我們采用了圖3-8中表示值的同樣的方法，如表示 300在習(xí)慣上就可簡寫為QTY（300）： 等等 等等 等等 等等 等等。對(duì)基本關(guān)系中的元組有如下的基： 等等 等等 等等 注意：我們并沒有嚴(yán)格地表明上面列出的基將明確地產(chǎn)生外延數(shù)據(jù)庫；不過，我數(shù)據(jù)登錄方法?；蛘哒f，演繹 DBMS直接作用在已存在的由傳統(tǒng)們將使用傳統(tǒng)的數(shù)據(jù)方法構(gòu)建的數(shù)據(jù)庫上。然而要注意的是，外延數(shù)據(jù)庫不違背那些已定義的完整性約束！因?yàn)橐粋€(gè)違背任何如此約束的數(shù)據(jù)庫就表示了這一系列公理的不一致性（從邏輯上講），并且由此可知，任何命題證明為“真”（或者說，可導(dǎo)出）。正是這一，要求完整

44、性約束集是一致的就顯得重要。現(xiàn)在來看外延數(shù)據(jù)庫。下面是一些屬性約束：在這種推導(dǎo)里，值得注意的是，在 1974年，Codd就認(rèn)為關(guān)系模型中的目標(biāo)之一是“把事實(shí)檢索和文件管理域合并起來為后來商業(yè)中的推理性服務(wù)作好另外的準(zhǔn)備”（參看11.2,25.8）。第23章 基于邏輯的數(shù)據(jù)庫581 等等 候選碼約束： 等等 外碼約束：等等。注意：為了說明的方便，我們假設(shè)在蘊(yùn)含符號(hào)右邊而不是左邊的變量（即此例中的 sn、st等）被存在量詞所約束（所有其它變量就像 23.4節(jié)講的那樣，被全稱量詞約束）。從技術(shù)上講，我們需要一些林函數(shù)。函數(shù)；例如，實(shí)際上， sn應(yīng)該由SN(s)所替代，這里SN就是一個(gè)還要注意，上面的

45、大部分約束不僅僅是 23.5節(jié)所講的意義上的子句，因?yàn)樯鲜接疫叢粌H僅是簡單項(xiàng)的邏輯和。下面，我們?cè)僭黾右恍┭堇[公理；(比較第9章9.1節(jié)中GOOD_SUPPLIER視圖的定義)等等。為了使這個(gè)例子更具說明性，我們把這個(gè)數(shù)據(jù)庫擴(kuò)展到包括“零件結(jié)構(gòu)”這一關(guān)系變量，它表明零件px由哪些零件py標(biāo)識(shí)存在的零件：它的組件（只涉及第一級(jí)的）。第一個(gè)約束要表明 px和py都必?cái)?shù)據(jù)值包括：等等（實(shí)際上， PART_STRUCTURE也可能有一個(gè)“數(shù)量”變?cè)?，去表明一個(gè) px由多少個(gè)py組成， 但為了簡單起見，我們刪去了這一細(xì)節(jié)）。下面增加兩個(gè)演繹公理來解釋零件 px由零件py（任何一級(jí)的）組成是什么意思；58

46、2第五部分 高 級(jí) 專 題或者說，如果零件py（某一級(jí)的）是px的中間組件或是pz（某一級(jí)的）的中間組件，而 pz又是px的中間組件，則 py就是px的組件。注意到第二個(gè)公理是遞歸的，它又根據(jù)它本身定義了COMPONENT_OF謂詞。相比而言，在的歷史上，是不如此遞歸地定義視圖或完整性約束或） 。演繹DBMS相對(duì)于經(jīng)典（或來說，支持遞歸能力是其最直接的最明顯的區(qū)別之一。盡管，就像 23.5節(jié)和第6章所說的那樣，對(duì)于為什么經(jīng)典的不能擴(kuò)展去支持如此的遞歸，還沒有什么根本的解釋；但某些系統(tǒng)確實(shí)已經(jīng)開始支持這一點(diǎn)。在23.7節(jié)詳細(xì)討論遞歸。Datalog從前面的討論很明確地看到,演繹DBMS的大部分內(nèi)

47、容表現(xiàn)為一種語言,在這一語言里,演繹公理(通常叫規(guī)則)可以化。這樣的語言最著名的例子就是 Datalog語言（和Prolog類似）(參看23.9）。這一節(jié)里我們對(duì) Datalog語言作簡單的介紹。注意： Datalog語言的重點(diǎn)是它的描述能力，而不是它的計(jì)算能力（實(shí)際上，它與最初關(guān)系模型那種情況類似，參看 5.1）)。其目標(biāo)就是定義一種語言，使它最終能比傳統(tǒng)的關(guān)系語言有更大的表達(dá)能力（參看 23.9）。所以， Datalog中強(qiáng)調(diào)的（的確，一般地講，這一強(qiáng)調(diào)貫穿于整個(gè)基于邏輯的系統(tǒng)中）是對(duì)查詢的處理，而不是更新，盡管這是可能的，并也要求擴(kuò)展這門語言去支持更新（以后將看到）。Datalog語言用

48、它最簡單的形式，對(duì)于那些像簡單的 Horn子句且沒有函數(shù)的規(guī)則，作了公式化的支持。在23.4節(jié)里，我們把Horn 子句定義為下述形式的合式：（這里的 A 和B是僅包含和變量的謂詞的實(shí)例）。然而，根據(jù) P r o l o g的格式，實(shí)際上，Datalog將這第二種形式變形，即：為了和此領(lǐng)域的其它版本保持一致，下面我們作同樣處理。在這樣一個(gè)子句中， B是規(guī)則頭（或結(jié)論），A是規(guī)則體（或前提或目標(biāo)；每一個(gè)是子目標(biāo)）。為簡潔起見，這里的 AND通常都用逗號(hào)代替。一個(gè)Datalog程序是由某些傳統(tǒng)的方式分割的一系列子句，例如，可由分號(hào)隔開（本書里不使用分號(hào)，而是簡單地將每一個(gè)子句寫在單獨(dú)的一行）。在這樣

49、的，子句的順序是無所謂的。看作 Datalog程序。例如，我們可以把上、完整性約束、演繹公理）用 Datalog的從上述所講的意義看，整個(gè)“演繹數(shù)據(jù)庫”述所有的關(guān)于供應(yīng)商和零件數(shù)據(jù)庫的公理（基，或把它們寫在單獨(dú)的行上，這樣，其結(jié)果就是 Datalog程序。形式寫出來，用分號(hào)把它們?nèi)欢缭缧r(shí)候所說的那樣，數(shù)據(jù)庫的擴(kuò)展部分不能用這種方式詳細(xì)說明，但能用別的更傳統(tǒng)的方法。這樣， Datalog語言的主要目標(biāo)就是明確地支持演繹公理的出過，函數(shù)可以看成傳統(tǒng)的關(guān)系DBMS中視圖定義機(jī)制的擴(kuò)展?；Ｇ懊嬖窪 a t a l o g 語言也可用作語言（這里，也很像P r o l o g ）。例如，假設(shè)

50、我們對(duì)GOOD_SUPPLIER作出Datalog的定義，如下：當(dāng)然，實(shí)際上，我們已經(jīng)定義了一個(gè)傳遞閉包。在任何時(shí)刻，相應(yīng)于 COMPONENT_OF的關(guān)系都是相對(duì)于PART_STRUCTURE的關(guān)系的一個(gè)閉包（參看第6章）。第23章 基于邏輯的數(shù)據(jù)庫583下面是有關(guān)GOOD_SUPPLIER的典型的：1)所有“好”供應(yīng)商：2)在巴黎的“好”供應(yīng)商：3) 供應(yīng)商S1是“好”供應(yīng)商嗎？等等?；蛘哒f， Datalog由一個(gè)以“？”為頭的特殊的規(guī)則組成，其規(guī)則體由一個(gè)唯一的項(xiàng)組成，從此項(xiàng)可得結(jié)果。“？”按其習(xí)慣用法表示“顯示” (display)。應(yīng)當(dāng)指出，盡管最初定義的 Datalog語言支持遞歸

51、，但還有許多傳統(tǒng)的關(guān)系數(shù)據(jù)庫語言的特征它不支持，如：標(biāo)量運(yùn)算（“+”、“*”等）、運(yùn)算（ COUNT、SUM等）、差運(yùn)算（因?yàn)樽泳洳荒鼙唬?、分組運(yùn)算和不分組運(yùn)算 (ungrouping)等。它還不支持屬性命名（謂詞變?cè)蕾囉谒跏嘉恢茫?，不支持全域（即?的用戶自定義類型）。本節(jié)早些時(shí)候說過，它不提供任何更新操作，（由此造成的結(jié)果）也不支持定義過的外碼刪除及更（ON DELETE CASEADE等等）。則的說明為了彌補(bǔ)上述這些不足，已經(jīng)對(duì) Datalog語言提出了各種各樣的的擴(kuò)展，這些擴(kuò)展試圖提供下述特征：的前提 例如： 標(biāo)量操作（固有的或用戶自定義的） 例如：此例中，我們假設(shè)符號(hào)“ *”用傳

52、統(tǒng)的記法寫在中間。此項(xiàng)也可運(yùn)用 AND的更傳統(tǒng)的前綴邏輯表示法為“ =(pg,*(pw,454)”。 分組和操作（與關(guān)系的SUMMARIZE操作相似，參看第6章）：有時(shí)為了敘述總量的問題，這樣的操作是必需的；這些問題的不僅僅是零件px由哪些零件py組成，而且要組成零件px需要多少個(gè)零件py。（這里我們假設(shè)關(guān)系變量PART_STRUCTURE包括QTY屬性）。 更新操作：解決這個(gè)要求的法（不僅僅是這種方法）是基于對(duì)基本的 Datalog語言的觀察，（a）在規(guī)則頭里面的任何謂詞必須是非的，并且（ b）規(guī)則生成的每一個(gè)元組可看作是在結(jié)果中的“”。這樣，一個(gè)可能的擴(kuò)充是在規(guī)則頭里面有否定的謂詞，且認(rèn)為

53、這些謂詞是請(qǐng)求刪除（有 規(guī)則體里的非Horn子句?；蛘哒f在規(guī)則的定義中元組）。有完全通用的合式。Gardarin 和Valduriez在23.10中舉例綜述了以上的擴(kuò)展內(nèi)容，同時(shí)還討論了各種各樣的Datalog語言的實(shí)現(xiàn)技術(shù)。23.7遞歸過程正如前一節(jié)里所述的，演繹數(shù)據(jù)最值得注意的特征是它對(duì)遞歸的支持。這里的遞歸584第五部分 高 級(jí) 專 題包括遞歸規(guī)則的定義及由此決定的遞歸。所以，最近的幾年對(duì)這樣的遞歸的實(shí)現(xiàn)技術(shù)有著大量的研究 的確，大約從1986年以來，每一次數(shù)據(jù)庫會(huì)議都至少提交這樣的一篇(請(qǐng)看本章“參考文獻(xiàn)”部分 )。由于遞歸們只簡單地討論一下。表達(dá)了經(jīng)典 DBMSs中不存在的問題，故本節(jié)我下面我們舉例說明。仍以 2 3 . 6 節(jié)C O M P O N E N T _ O F 的遞歸定義來說，它是由PART_STRUCTURE定義的。為簡單起見，我們