演繹數(shù)據(jù)庫(kù)語(yǔ)言(數(shù)據(jù)庫(kù))

時(shí)間：2022-12-04 02:30:02 | 來源：信息時(shí)代

時(shí)間：2022-12-04 02:30:02 來源：信息時(shí)代

    演繹數(shù)據(jù)庫(kù)語(yǔ)言 : 演繹數(shù)據(jù)庫(kù)提供給用戶的一種實(shí)現(xiàn)演繹推理和智能查詢的計(jì)算機(jī)語(yǔ)言,該語(yǔ)言一般是基于一階謂詞邏輯的。通常,這樣的語(yǔ)言系統(tǒng)是由一個(gè)合式公式集、一個(gè)演繹推理系統(tǒng)和一個(gè)解釋機(jī)制組成的。
1. 演繹數(shù)據(jù)庫(kù)語(yǔ)言
常用的演繹數(shù)據(jù)庫(kù)語(yǔ)言有:
(1) Prolog語(yǔ)言:是由馬賽大學(xué)的A.Colmereaer和P.Roussel創(chuàng)立的。Prolog語(yǔ)言是一種邏輯程序語(yǔ)言,Prolog中客觀世界的描述可表達(dá)為對(duì)象之間所有可能的關(guān)系,關(guān)系可以復(fù)合。邏輯語(yǔ)言的邏輯基礎(chǔ)是一階謂詞邏輯,其操作語(yǔ)義是歸結(jié)。Prolog程序是由Horn子句形式的規(guī)則和事實(shí)子句的集合。Prolog語(yǔ)言采用的控制策略是自頂向下、從左到右,帶回溯的、深度優(yōu)先搜索,其基本操作是匹配合一,可直接用于推理。
(2) OPS(official production system):是由卡內(nèi)基-梅隆大學(xué)提出的一種基于規(guī)則的產(chǎn)生式知識(shí)處理系統(tǒng)。在演繹推理中,表示“如果A則B”的因果關(guān)系或推理關(guān)系的規(guī)則稱為產(chǎn)生式規(guī)則。OPS邏輯語(yǔ)言家族已有OPS 1,…,OPS5、OPS5+、OPS83等多種版本,這種演繹數(shù)據(jù)庫(kù)語(yǔ)言采用的是自底向上的控制策略。
(3) Datalog:是一種特殊形式的Horn子句所構(gòu)成的演繹數(shù)據(jù)庫(kù)語(yǔ)言,目前它已作為一種較好的邏輯知識(shí)表示語(yǔ)言,在演繹數(shù)據(jù)庫(kù)、知識(shí)庫(kù)和人工智能中廣泛應(yīng)用,并被稱為Horn子句在這些領(lǐng)域中的專門Datalog版本。作為一種數(shù)據(jù)庫(kù)語(yǔ)言,Datalog采用了類似于Prolog的記法,但與Prolog不同的是:①Datalog中的項(xiàng)僅由個(gè)體常量或個(gè)體變量組成而不允許使用函數(shù)作為變?cè)?②Datalog程序的含義遵循模型論的解釋,并且作為數(shù)據(jù)庫(kù)語(yǔ)言或數(shù)據(jù)模型,它們還遵循證明論的解釋;③Datalog是一種非過程語(yǔ)言,其規(guī)則或規(guī)則中子目標(biāo)的書寫次序并不決定它們的處理次序;④Datalog必須滿足安全性規(guī)則。因?yàn)檠堇[數(shù)據(jù)庫(kù)中,數(shù)據(jù)必須是有限的,必須對(duì)變量作量的限制,這就是Datalog安全性規(guī)則。以下重點(diǎn)介紹Datalog語(yǔ)言的特點(diǎn)與Datalog模型。
2. Datalog語(yǔ)言及其特點(diǎn)
Datalog是一個(gè)杜撰的詞,意為“數(shù)據(jù)邏輯”,它既是一種數(shù)據(jù)庫(kù)語(yǔ)言,又是一種邏輯程序設(shè)計(jì)語(yǔ)言。通常,可以將Datalog視為適合數(shù)據(jù)庫(kù)操作的某種邏輯程序設(shè)計(jì)語(yǔ)言(如Prolog)的專門版本。Datalog語(yǔ)言的語(yǔ)法及重要特性如下:
(1) Datalog的基礎(chǔ)數(shù)據(jù)模型是關(guān)系模型。在Datalog中,每個(gè)謂詞都代表一個(gè)關(guān)系。通常謂詞用以小寫英文字母開始的字符串表示,而其對(duì)應(yīng)的關(guān)系用大寫英文字母開始的字符串表示。Datalog不對(duì)變?cè)?謂詞p的第i個(gè)變?cè)獙?duì)應(yīng)于其對(duì)應(yīng)關(guān)系P的第i列。如果一個(gè)謂詞的對(duì)應(yīng)關(guān)系存儲(chǔ)在數(shù)據(jù)庫(kù)中,則將該謂詞稱為外延數(shù)據(jù)庫(kù)(EDB)謂詞,其對(duì)應(yīng)的關(guān)系為EDB關(guān)系。由規(guī)則定義的謂詞稱作內(nèi)涵數(shù)據(jù)庫(kù)(IDB)謂詞,其對(duì)應(yīng)的關(guān)系為IDB關(guān)系。
(2)原子公式是Datalog程序的基本單位。原子公式是一個(gè)帶變?cè)斜淼闹^詞符號(hào),如p(A₁,A₂,…,A_n),其中p是謂詞符號(hào),A₁,A₂,…,A_n是變?cè)?。在Datalog中,變?cè)荒苁亲兞炕虺Ａ俊Ｍǔ?變?cè)统Ａ糠謩e用以大寫或小寫的英文字母開始的字符串表示。每個(gè)原子公式都對(duì)應(yīng)一個(gè)關(guān)系,該關(guān)系是謂詞對(duì)應(yīng)關(guān)系的受限形式: ①如果原子公式中出現(xiàn)常量,則在常量出現(xiàn)的分量上做相等選擇;②如果同一個(gè)變量出現(xiàn)多次,則在具有相同變量的分量上做相等選擇。例如,原子公式emps(‘李明’,Salary,Dept)對(duì)應(yīng)于關(guān)系σ_{＄1=‘李明’}(EMPS),其中,EMPS是謂詞emps的對(duì)應(yīng)關(guān)系。Datalog也使用算術(shù)比較運(yùn)算符構(gòu)造原子公式。算術(shù)比較運(yùn)算符稱作內(nèi)部謂詞(用中綴表示),其他謂詞稱作一般謂詞。
(3) Datalog中的規(guī)則是一種Horn子句,并采用類似Prolog的記法,如,H:-B₁,B₂,…,B_n。其中,H為規(guī)則的頭部,B₁,B₂,…,B_n為規(guī)則體,而B_i(1≤i≤n)為規(guī)則體中的子目標(biāo),它們是原子公式(正的子目標(biāo))或負(fù)的原子公式(負(fù)的子目標(biāo))。如果子目標(biāo)B_i是內(nèi)部謂詞,則稱B_i為內(nèi)部子目標(biāo),否則B_i為一般子目標(biāo)。該規(guī)則表示“如果B₁,B₂,…,B_n均為真,則H為真”。事實(shí)也可以看作規(guī)則,其規(guī)則體為空。
(4) Datalog程序由一組規(guī)則組成。如果Datalog程序定義了遞歸謂詞,則它是遞歸的,否則是非遞歸的。如果p_i是IDB謂詞,定義它的規(guī)則都是調(diào)整后的規(guī)則,則IDB謂詞p_i對(duì)應(yīng)的關(guān)系可以用一個(gè)關(guān)系代數(shù)表達(dá)式E_i表示。其基本方法是: 對(duì)每個(gè)以p_i為頭部謂詞的規(guī)則,將它的規(guī)則體關(guān)系投影到頭部變量上,然后取它們的并。如果一個(gè)非遞歸的Datalog程序定義了m個(gè)IDB謂詞,則可對(duì)這些IDB謂詞確定一個(gè)次序p₁,p₂,…,p_m,使得當(dāng)i<j時(shí),p_i對(duì)應(yīng)的關(guān)系p_i不在p_j的關(guān)系代數(shù)表達(dá)式E_i中出現(xiàn)。這樣,可以依次計(jì)算p₁,p₂,…,p_m對(duì)應(yīng)的關(guān)系p₁,p₂,…,p_m。如果Datalog程序是遞歸的,則IDB謂詞對(duì)應(yīng)的關(guān)系必須通過求不動(dòng)點(diǎn)得到。
(5) Datalog是高度非過程化的語(yǔ)言,其規(guī)則的書寫次序和規(guī)則體中子目標(biāo)的書寫次序都不決定它們的實(shí)際執(zhí)行次序,并且不含諸如cut和fail等與邏輯不協(xié)調(diào)的操作。此外,對(duì)于遞歸查詢,采用自頂向下還是自底向上處理,由系統(tǒng)自動(dòng)進(jìn)行選擇。而其他邏輯語(yǔ)言,只支持自頂向下(如Prolog)或自底向上(如OPS5)的求值。
(6)提高Datalog表達(dá)能力。其能力一是體現(xiàn)在允許在規(guī)則中出現(xiàn)否定子目標(biāo); 二是能處理集合值變量。但是,如果不限制否定詞的使用,會(huì)導(dǎo)致不動(dòng)點(diǎn)不存在。處理否定的方法有:①采用分層否定:一個(gè)邏輯程序是分層的,如果它的所有謂詞都可以賦予一個(gè)非負(fù)整數(shù)秩,使得任何謂詞都不否定地依賴具有相等或較高秩的其他謂詞。對(duì)于分層的邏輯程序,可以逐層處理,得到它的一個(gè)極小不動(dòng)點(diǎn),并用它定義規(guī)則的計(jì)算含義。引入分層否定后,Datalog的表達(dá)能力比關(guān)系代數(shù)強(qiáng)。②用局部分層處理否定: 局部分層把對(duì)謂詞的限制進(jìn)一步擴(kuò)充到函數(shù)詞和常量: ③用膨脹不動(dòng)點(diǎn)處理否定: 在計(jì)算不動(dòng)點(diǎn)時(shí),一個(gè)事實(shí)一旦導(dǎo)出就不再丟棄。膨脹不動(dòng)點(diǎn)比分層否定具有更強(qiáng)的處理否定的能力,但是當(dāng)邏輯程序是分層的時(shí),分層否定是更自然的選擇。通常,提高Datalog表達(dá)能力還可采用限制集合值變量、使用嵌套關(guān)系、允許變?cè)谐霈F(xiàn)函數(shù)詞等措施。
3. Datalog數(shù)據(jù)模型
智能數(shù)據(jù)庫(kù)和管理信息系統(tǒng)用于決策支持的需求,使人們將演繹數(shù)據(jù)庫(kù)、知識(shí)庫(kù)的研究轉(zhuǎn)向了提高數(shù)據(jù)庫(kù)中“邏輯規(guī)則”的表達(dá)能力和查詢優(yōu)化方面。為適應(yīng)在知識(shí)庫(kù)中表示知識(shí),要對(duì)Horn子句作一些必要的限制,在邏輯規(guī)則方面,就出現(xiàn)了基于邏輯的Datalog數(shù)據(jù)模型。這種演繹數(shù)據(jù)模型提供了遞歸定義能力,具有比關(guān)系數(shù)據(jù)模型更強(qiáng)的表達(dá)能力,包括定義復(fù)雜的數(shù)據(jù)模型,更強(qiáng)的數(shù)據(jù)操縱能力,支持更完善的完整性約束條件,并最終提供一個(gè)具有數(shù)據(jù)操縱與宿主語(yǔ)言功能的統(tǒng)一的說明性語(yǔ)言。
Datalog數(shù)據(jù)模型是用一系列關(guān)系代數(shù)操作實(shí)現(xiàn)的。與Prolog不同的是:Datalog程序的含義應(yīng)遵循模型論的觀點(diǎn); 或者,當(dāng)它們等價(jià)時(shí),也遵循證明論的觀點(diǎn)。然而,Prolog所具有的計(jì)算性含義在某些情況下可能既偏離模型論,又偏離了證明論。
本質(zhì)上,Datalog數(shù)據(jù)模型的數(shù)學(xué)基礎(chǔ)與關(guān)系模型是相同的。在Datalog中,謂詞符號(hào)表示關(guān)系。然而,如同關(guān)系代數(shù)的形式定義一樣,通常未用屬性對(duì)這些關(guān)系的列命名。它們是列表集合意義下的關(guān)系,分量以固定的順序出現(xiàn),對(duì)列的訪問僅通過給定謂詞符號(hào)的自變?cè)械奈恢脕磉M(jìn)行。例如,若p是一個(gè)三元謂詞符號(hào),可以用p(X,Y,Z)表示它,而變量X指示謂詞p的對(duì)應(yīng)關(guān)系中的某個(gè)元組的第一分量。
對(duì)Datalog數(shù)據(jù)模型,涉及對(duì)datalog不動(dòng)點(diǎn)的語(yǔ)義、半樸素求解、帶有否定的邏輯、分層規(guī)則和魔集技術(shù)的研究,其中尤以魔集重寫技術(shù)、魔謂詞、魔集變換、魔集規(guī)則約簡(jiǎn)、廣義魔集等研究成果較突出。而在邏輯規(guī)則及知識(shí)表示和查詢優(yōu)化研究方面也取得較大進(jìn)展。如Solomon證明查詢優(yōu)化問題是不可判定的,M.J.Maher和Y.Sagiv在邏輯程序的合取查詢方面,提出了邏輯程序的等價(jià)、判定方法和包含問題; A.Klug給出了內(nèi)部謂詞中有不等式時(shí)的合取查詢包含問題等成果。此外,在線性遞歸優(yōu)化方面,也有右線性遞歸、混合線性遞歸、傳遞閉包和閉半回路中的傳遞閉包,以及將非線性轉(zhuǎn)化為線性遞歸的方法。