演繹數(shù)據(jù)庫(kù)理論(數(shù)據(jù)庫(kù))

時(shí)間：2022-12-03 14:30:01 | 來(lái)源：信息時(shí)代

時(shí)間：2022-12-03 14:30:01 來(lái)源：信息時(shí)代

    演繹數(shù)據(jù)庫(kù)理論 : 采用謂詞邏輯實(shí)現(xiàn)演繹數(shù)據(jù)庫(kù)的一套理論與原理。通常,演繹數(shù)據(jù)庫(kù)采用的數(shù)學(xué)工具以邏輯(主要包括一階謂詞邏輯演算)為主,邏輯程序是一組基于Horn子句的規(guī)則,它們采用邏輯證明論、邏輯模型論和函數(shù)模型論來(lái)描述和解釋。實(shí)現(xiàn)演繹數(shù)據(jù)庫(kù)的理論和原理是建立數(shù)學(xué)模型系統(tǒng),其核心是邏輯程序的模型語(yǔ)義(包括Herbrand基、邏輯滿(mǎn)足、最小模型的唯一性、模型相交定理和最小模型的極小不動(dòng)點(diǎn)等),并在證明論與模型論等理論的基礎(chǔ)上建立相應(yīng)的算法來(lái)實(shí)現(xiàn)。
1.基于一階邏輯的證明論理論
邏輯證明論(logic proving theory)是數(shù)據(jù)邏輯中的一個(gè)傳統(tǒng)分支,作為演繹數(shù)據(jù)庫(kù)的一種模型理論,它采用公理系統(tǒng)來(lái)求解問(wèn)題。由給定公理,通過(guò)證明過(guò)程而得定理,這就是證明論求解問(wèn)題的方法。按邏輯證明論觀點(diǎn),每個(gè)關(guān)系數(shù)據(jù)庫(kù)本身被視為常量原子公式,即每個(gè)關(guān)系元組本身即為一閉合原子。這樣,關(guān)系數(shù)據(jù)庫(kù)與邏輯程序只是同一事物的兩種不同的表示形式,從而有可能將其與規(guī)則一起共同構(gòu)成一個(gè)前提公式集,并推演出新目標(biāo)或演繹數(shù)據(jù),而使檢索處理轉(zhuǎn)化成推理過(guò)程。
證明系統(tǒng)(proving system)又稱(chēng)為推理系統(tǒng)(inference system)或一階謂詞演算的公理系統(tǒng)。在證明系統(tǒng)中,包括公理(集)、定理和證明。公理是廣義于所有數(shù)據(jù)的,在一階謂詞演算公理系統(tǒng)中,公理均為一階謂詞演算公式。通常,它由唯一命名公理(UNA)、域閉包公理(DCA)、閉包世界公理(CWA)等組成公理集。證明系統(tǒng)中的定理,也是一階謂詞演算公式,它是由公理通過(guò)證明而得到的,而證明則是指由公理通過(guò)推理而得到定理的過(guò)程。從證明論的角度看,演繹數(shù)據(jù)庫(kù)即可視為一個(gè)一階謂詞演算的公理系統(tǒng)。表1給出邏輯證明論中的(公理)證明系統(tǒng)與演繹數(shù)據(jù)庫(kù)的關(guān)系對(duì)照。
邏輯證明論實(shí)現(xiàn)演繹數(shù)據(jù)庫(kù)的原理實(shí)際上是將演繹數(shù)據(jù)庫(kù)視為一個(gè)定理證明系統(tǒng),通過(guò)構(gòu)造一個(gè)關(guān)系系統(tǒng)(理論)T,使演繹數(shù)據(jù)庫(kù)成為唯一模型。在該理論下,查詢(xún)求值和完整性約束被視為待證明的定理。設(shè)L為一階謂詞邏輯語(yǔ)言,則對(duì)L中任何合式公式W, T⊦W當(dāng)且僅當(dāng)W可從理論T及公式集中導(dǎo)出。邏輯證明論使一階邏輯和關(guān)系數(shù)據(jù)庫(kù)形成自然聯(lián)系,用一階邏輯公理定義數(shù)據(jù)庫(kù)成為可能。在邏輯證明論中,為確保理論上的嚴(yán)格性,有必要引入若干公理,包括唯一命名公理(UNA)、域閉包公理(DCA)、閉合世界公理(CWA),及它們組成的公理集。

表1 證明系統(tǒng)與演繹數(shù)據(jù)庫(kù)的關(guān)系對(duì)照

證明系統(tǒng)	演繹數(shù)據(jù)庫(kù)
公理	數(shù)據(jù)、窗口、邏輯規(guī)則
定理	查詢(xún)、快照、數(shù)據(jù)模式、完整性約束
證明	查詢(xún)、快照的實(shí)現(xiàn)、數(shù)據(jù)模式的檢驗(yàn)、完整性約 束的檢驗(yàn)

目前,用邏輯證明論實(shí)現(xiàn)演繹數(shù)據(jù)庫(kù),即建立一階謂詞邏輯演算的公理系統(tǒng),主要是通過(guò)采用基于一階謂詞邏輯語(yǔ)言Prolog和Datalog來(lái)實(shí)現(xiàn)的。由于演繹數(shù)據(jù)庫(kù)采用一階邏輯作為知識(shí)表示工具,一般都是采用基于一階邏輯的證明論理論。其公理系統(tǒng)的實(shí)現(xiàn)步驟如下:
(1)建立一組公理(公式的集合)。公理可認(rèn)為在該系統(tǒng)內(nèi)普遍有效,即公理中的公式永為真。演繹數(shù)據(jù)庫(kù)一般有特殊性公理、事實(shí)性公理和演繹性公理等。其中,事實(shí)性公理數(shù)量較多,因?yàn)槊恳粩?shù)據(jù)事實(shí)都有一條公理。演繹性公理給出了演繹數(shù)據(jù)庫(kù)中的規(guī)則,一般在Datalog中以規(guī)則形式出現(xiàn)。
(2)建立一組推理規(guī)則,即演繹的方法,一般的推理規(guī)則可以是: A,A→B,|-B。
(3) 由公理與推理規(guī)則給出一組證明過(guò)程。一般,一個(gè)證明過(guò)程可定義為一個(gè)公式的序列,其中序列內(nèi)的公式(k),可由(1)-(k-1)及公理通過(guò)推理規(guī)則而得到。
(4)最后,可得到公理系統(tǒng)的定理,一般對(duì)某組公理如有證明過(guò)程P₁,P₂,…,P_n,而P_n即為該公理系統(tǒng)通過(guò)證明過(guò)程而得的定理。在演繹數(shù)據(jù)庫(kù)中,定理相當(dāng)于對(duì)規(guī)則的查詢(xún)(結(jié)果),它有時(shí)也可作為演繹數(shù)據(jù)庫(kù)的完整性、一致性及相容性的校驗(yàn)工具。
在證明論理論中所用的推理規(guī)則及證明過(guò)程是一種演繹性的推理方法,一開(kāi)始無(wú)法在計(jì)算機(jī)上自動(dòng)實(shí)現(xiàn)。1956年,美國(guó)數(shù)理邏輯學(xué)家R·Robinson證明了這個(gè)問(wèn)題在理論上的可行性,并給出了自動(dòng)證明的算法——?dú)w結(jié)原理(resolution principle)。
如上所述,在證明論解釋下,將演繹數(shù)據(jù)庫(kù)中存放的EDB關(guān)系元組看作事實(shí),規(guī)則看作公理。規(guī)則定義的IDB關(guān)系就是利用數(shù)據(jù)庫(kù)中的事實(shí),使用規(guī)則可以證明的事實(shí)(即定理)集合。查詢(xún)處理過(guò)程就是定理證明過(guò)程。在此觀點(diǎn)下,演繹數(shù)據(jù)庫(kù)可視為一個(gè)具有演繹功能的公理系統(tǒng)?；谧C明論的歸結(jié)原理為邏輯規(guī)則的自頂向下處理奠定了基礎(chǔ)。
2.基于一階邏輯的模型論理論
模型論(model theory)是數(shù)據(jù)邏輯中的傳統(tǒng)分支,在演繹數(shù)據(jù)庫(kù)中,一般是采用一階邏輯模型論方式求解問(wèn)題。模型論一般可用如下的一個(gè)三元組組成:(L,∑,M),其中L是書(shū)寫(xiě)的語(yǔ)言,∑是用L書(shū)寫(xiě)的句子集,M是L的一個(gè)解釋,稱(chēng)為結(jié)構(gòu)或L-結(jié)構(gòu)。
基于一階邏輯的模型論理論是以Datalog為書(shū)寫(xiě)語(yǔ)言L,以演繹數(shù)據(jù)庫(kù)中的事實(shí)與規(guī)則為句子集∑,并構(gòu)作模型M(滿(mǎn)足M|=∑,且為最小),其最小模型即為演繹數(shù)據(jù)庫(kù)的演繹結(jié)果,而最小模型可通過(guò)對(duì)∑的關(guān)系代數(shù)方程組的最小不動(dòng)點(diǎn)來(lái)求得。為獲取此項(xiàng)結(jié)果,目前一般采用代數(shù)方法,即將求得最小模型變換成為某代數(shù)方程組的求解,其求解的算法有以“Bottom Up”方法所形成的算法體系,以及將證明論中的“Top Down”算法體系與“Bottom Up”相結(jié)合所形成的魔集(magic set)算法。
邏輯模型論(logic model theory)作為演繹數(shù)據(jù)庫(kù)中一種常用的數(shù)據(jù)模型,它將關(guān)系數(shù)據(jù)庫(kù)視為一階邏輯閉合公式集。在一階邏輯中,使得一組(個(gè))閉合公式為真的解釋,分別稱(chēng)為這組(個(gè))公式的模型。以此為基礎(chǔ),可重構(gòu)關(guān)系數(shù)據(jù)庫(kù)理論,并因此引出數(shù)據(jù)庫(kù)的邏輯模型論。邏輯模型論的原理是: ①數(shù)據(jù)庫(kù)之內(nèi)涵由一組閉合公式描述。這組公式相當(dāng)數(shù)據(jù)庫(kù)的完整性約束,作用于數(shù)據(jù)庫(kù)對(duì)象的全體,亦即這組公式相當(dāng)于約束條件的全稱(chēng)閉包; ②數(shù)據(jù)庫(kù)的外延為用于描述數(shù)據(jù)庫(kù)的一階公式的模型。若令一階公式為G,數(shù)據(jù)庫(kù)為D,則D為G的一個(gè)模型,亦即D為G的一個(gè)解釋,使得G中所有公式為{X|W(X)},其中,X為一變量(如元組),W(X)為一階公式,X為W(X)中的唯一自由變量。檢索表達(dá)式針對(duì)數(shù)據(jù)庫(kù)取其真值,即在數(shù)據(jù)庫(kù)規(guī)則公式的解釋中發(fā)現(xiàn)所有X的實(shí)例對(duì)象,使得W(X)為真?？梢?jiàn),數(shù)據(jù)庫(kù)的邏輯模型論簡(jiǎn)明地建立起數(shù)據(jù)庫(kù)關(guān)系理論與一階謂詞邏輯理論之間的聯(lián)系。該模型將查詢(xún)求值的完整性約束視為在真值語(yǔ)義定義下的解釋環(huán)境中的求值,這是從語(yǔ)義角度看待和實(shí)現(xiàn)演繹數(shù)據(jù)庫(kù)。邏輯模型論使演繹數(shù)據(jù)庫(kù)的研制相對(duì)簡(jiǎn)化,但它在描述視圖重構(gòu)、空值、否定和析取等方面仍存在局限性。
在規(guī)則的模型論理論解釋下,一組規(guī)則被看作定義了一個(gè)可能的模型。謂詞的解釋是使得謂詞為真的所有可能實(shí)例。模型的解釋是使得規(guī)則集中所有規(guī)則都為真的解釋,而演繹數(shù)據(jù)庫(kù)中的數(shù)據(jù)就是最小(極小)模型。規(guī)則的模型論解釋為用最小(極小)不動(dòng)點(diǎn)定義規(guī)則的計(jì)算含義提供了基礎(chǔ)。在此理論下,隨后相繼出現(xiàn)了規(guī)則的自頂向下算法,如樸質(zhì)算法、半樸質(zhì)算法、魔集算法等。
3.基于函數(shù)論的模型理論
函數(shù)論模型(functional theory model)是一種構(gòu)造性求值模型。該模型建立在集合、函數(shù)、算子和變換這四個(gè)層次上。其中,集合是函數(shù)論的基礎(chǔ),由集合構(gòu)造函數(shù),而算子則在建立函數(shù)之上構(gòu)造新的函數(shù),包括反函數(shù)、迭代、復(fù)合、遞歸、插入及刪除等。變換給出了函數(shù)構(gòu)造集合的方法,包括λ-變換和μ-變換,它們分別將顯函數(shù)和隱函數(shù)構(gòu)造成集合。因此,在函數(shù)論模型下,查詢(xún)求值可利用基本函數(shù)通過(guò)算子構(gòu)造出許多新函數(shù),再通過(guò)變換構(gòu)造集合來(lái)實(shí)現(xiàn)。如上所述,演繹數(shù)據(jù)庫(kù)的構(gòu)造性求值模型就是通過(guò)構(gòu)造上述算子及變換來(lái)實(shí)現(xiàn)的。
4.邏輯程序計(jì)算的有效性
演繹數(shù)據(jù)庫(kù)的實(shí)現(xiàn),十分關(guān)注基于規(guī)則的邏輯程序的計(jì)算有效性問(wèn)題。通常,邏輯規(guī)則處理的算法大體分為自頂向下與自底向上兩大類(lèi)。自頂向下是由目標(biāo)進(jìn)行推理,其理論基礎(chǔ)是歸結(jié)原理。大部分自頂向下的方法都可以看作Prolog所用方法的基于關(guān)系的版本和改進(jìn)。與Prolog不同,演繹數(shù)據(jù)庫(kù)采用一次一個(gè)關(guān)系,而不是一次一個(gè)元組的處理方式。自頂向下的方法具有很好的聚焦性(從而具有較高的求值效率),但其實(shí)現(xiàn)較為復(fù)雜,并且收斂性難以保證和判斷。與此相反,基本的自底向上算法是樸質(zhì)算法和半樸質(zhì)算法,其理論基礎(chǔ)是不動(dòng)點(diǎn)原理。它們具有實(shí)現(xiàn)簡(jiǎn)單、收斂性易于判定等優(yōu)點(diǎn)。但是由于缺乏聚焦性,自底向上這種算法很難單獨(dú)使用。
魔集算法的發(fā)現(xiàn)是遞歸查詢(xún)處理研究的重要里程碑。針對(duì)具體查詢(xún),魔集算法首先改寫(xiě)規(guī)則,然后自底向上地計(jì)算新規(guī)則的不動(dòng)點(diǎn),得到查詢(xún)的回答。魔集算法保持了自頂向下和自底向上方法的全部?jī)?yōu)點(diǎn),避免了兩者的缺點(diǎn)。魔集算法的發(fā)現(xiàn)使得規(guī)則的自底向上處理方法開(kāi)始走向?qū)嵱?成為遞歸查詢(xún)處理的主要方法,并推動(dòng)了基于變換的查詢(xún)優(yōu)化技術(shù)的研究。魔集算法有許多拓廣,包括處理帶函數(shù)詞的規(guī)則、帶聚集函數(shù)的規(guī)則和包含否定詞的規(guī)則。魔集變換的思想還被用于處理一些特殊的,在實(shí)踐中經(jīng)常出現(xiàn)的遞歸查詢(xún),如右線(xiàn)性遞歸、左線(xiàn)性遞歸、混合線(xiàn)性遞歸和計(jì)數(shù)線(xiàn)性遞歸。