演繹數(shù)據(jù)庫系統(tǒng)(數(shù)據(jù)庫)

時間：2022-12-03 20:30:02 | 來源：信息時代

時間：2022-12-03 20:30:02 來源：信息時代

    演繹數(shù)據(jù)庫系統(tǒng) : 一種具有邏輯運算和演繹推理能力的數(shù)據(jù)庫系統(tǒng)。按照J(rèn).D.Ullman的觀點,一個演繹數(shù)據(jù)庫應(yīng)是這樣的程序系統(tǒng): ①有一種說明式語言,即多種可能形式之一的邏輯,用作宿主語言和查詢語言; ②具有DBMS的主要功能,能有效存取大量數(shù)據(jù)、實現(xiàn)數(shù)據(jù)共享和對數(shù)據(jù)的并行存取與故障恢復(fù)等功能。多年來,演繹數(shù)據(jù)庫一直沿著這個研究方向在努力,并相繼產(chǎn)生了一些試驗性的系統(tǒng)。
1. NAIL! 系統(tǒng)
NAIL!是斯坦福大學(xué)的J.D.Ullman及其學(xué)生開發(fā)的一個試驗性演繹數(shù)據(jù)庫系統(tǒng)。該項目的主要目標(biāo)是研究邏輯查詢優(yōu)化。圖1為NAIL! 系統(tǒng)的結(jié)構(gòu)。NAIL!的源代碼采用類似Prolog符號書寫,規(guī)則必須是安全的,并采用分層否定。源程序經(jīng)預(yù)處理后被編譯成內(nèi)部表,并將謂詞劃分成強連通成分(SCC)。一個SCC可以是單個非遞歸謂詞(IDB或EDB),或者是相互遞歸的謂詞的最小集。
一旦規(guī)則被編譯,系統(tǒng)將接受查詢。查詢是一個謂詞,其中變元可以是常量或變量。SCC將決定如何處理一組邏輯規(guī)則。對于被修飾的目標(biāo)Pa,NAIL!系統(tǒng)將為計算p關(guān)系的相關(guān)部分選擇一個策略。給定被修飾的目標(biāo)Pa,策略選擇算法開始為p的SCC構(gòu)造一個規(guī)則/目標(biāo)圖,所有不在p的SCC中的謂詞都作為EDB子目標(biāo)處理。如果成功地構(gòu)造了一個規(guī)則/目標(biāo)圖,就考察所有外部的被修飾目標(biāo)——其謂詞在p的SCC之外的那些目標(biāo)。再通過策略選擇算法,為每一個外部目標(biāo)選擇一種策略。由于外部目標(biāo)處在低于p的層次,因此必將最終到達(dá)某一點,在那里只有被修飾的EDB目標(biāo)和內(nèi)部算術(shù)目標(biāo)要處理。這些目標(biāo)是平凡的,或者成功,或者失敗。失敗時需回溯,并導(dǎo)致重新構(gòu)造規(guī)則/目標(biāo)圖。

圖1 NAIL!的結(jié)構(gòu)

查詢時要確定一個被修飾目標(biāo),并由捕獲規(guī)則決定采用什么策略。每個捕獲規(guī)則對應(yīng)于一個計算邏輯規(guī)則的算法,如“左線性遞歸”、“魔集”。捕獲規(guī)則由檢測算法和執(zhí)行算法兩部分代碼組成,最后由執(zhí)行算法產(chǎn)生內(nèi)部中間代碼(ICODE)來計算與該目標(biāo)匹配的元組。查詢中捕獲規(guī)則的測試部分將依次被測試,直到成功。例如,線性遞歸的Datalog類可能依次含有左線性、右線性、左右混合線性、計數(shù)線性和魔集等策略的捕獲規(guī)則。當(dāng)NAIL!為一個給定的被修飾目標(biāo)發(fā)現(xiàn)一個策略時,它將決定放入策略數(shù)據(jù)庫。下次遇到同樣的被修飾目標(biāo),即使約束關(guān)系不同,也不必重新選擇,而是在該數(shù)據(jù)庫中查找適當(dāng)?shù)牟呗?。為了避免重?fù)漫無目標(biāo)的搜索,策略數(shù)據(jù)庫中也存放否定的事實,指出找不到可用于處理某特定被修飾目標(biāo)Pa的捕獲規(guī)則。查詢是否成功的策略通過一個稱作ICODE的語言程序來實現(xiàn)和回答。該語言由一些關(guān)系代數(shù)操作(選擇、投影、積、并、差和各種連接)語句組成。除并和差之外,其余都能以Prolog規(guī)則形式的ICODE語句實現(xiàn)。ICODE還具有控制流的特點。
NAIL!系統(tǒng)以SQL數(shù)據(jù)庫為基礎(chǔ),用于實現(xiàn)傳統(tǒng)的DBMS功能,并將實際數(shù)據(jù)存于SQL數(shù)據(jù)庫中,此外還在NAIL!系統(tǒng)的后端加入了一種過程式語言Glue作為控制結(jié)構(gòu),將其與NAIL!混合使用,以提高系統(tǒng)性能。
2. LDL(logic data language)系統(tǒng)
LDL系統(tǒng)是由美國Texas州奧斯汀的MCC開發(fā),其系統(tǒng)結(jié)構(gòu)和目標(biāo)類似于NAIL!。它不僅是一個邏輯處理系統(tǒng),也是一個完整的DBMS。在LDL中,規(guī)則被譯成一種叫做謂詞連接圖的內(nèi)部形式(規(guī)則中允許函數(shù)符號,而否定必須是分層的),經(jīng)過廣泛的查詢優(yōu)化處理后,規(guī)則被譯成一種稱為FAD的中間代碼。這種語言類似于NAIL! 的ICODE,基本上是關(guān)系代數(shù)的擴充,使之具有處理函數(shù)符號和控制流的能力。
LDL的查詢優(yōu)化程序在響應(yīng)含有被約束變元和自由變元的查詢時,要回答該查詢所需的所有謂詞的約束模式,而不需要重新確定子目標(biāo)的次序。但在執(zhí)行規(guī)則的半樸質(zhì)計算時,LDL也同NAIL! 一樣,需要考慮對應(yīng)于子目標(biāo)的關(guān)系連接次序。LDL確定了約束模式后,將為查詢改寫規(guī)則。這時,可采用魔集、左線性或右線性規(guī)則等變換來實現(xiàn)。實用中可優(yōu)先選擇左線性或右線性變換,且計數(shù)變換優(yōu)先于魔集。同時在變換之后,應(yīng)采用半樸質(zhì)方法自底向上地計算結(jié)果規(guī)則。LDL還提供了一種“推進(jìn)投影變換”規(guī)則改寫技術(shù),能在自底向上的查詢計算中,盡早地去掉最終將被投影掉的謂詞分量。
對于變換后的規(guī)則,LDL采用了魔集規(guī)則化簡的方法對規(guī)則進(jìn)行化簡,結(jié)果導(dǎo)致規(guī)則體增長。由于規(guī)則體的計算涉及子目標(biāo)間關(guān)系的連接,因此重新確定子目標(biāo)的次序?qū)τ谔岣咭?guī)則的求值效率十分重要。為此,LDL采用了一種在無環(huán)超圖上實現(xiàn)的窮舉搜索算法。
3.其他的演繹數(shù)據(jù)庫試驗系統(tǒng)
如下為一些有名的試驗性演繹數(shù)據(jù)庫:
(1) 由Y.Dahl采用Prolog語言實現(xiàn)的一種SOLARS16,系統(tǒng)具有DBMS的諸多功能和提供一種交會式語言,而在演繹推理、智能檢索方面也獨具特色。
(2)俄亥俄州州立大學(xué)開發(fā)的醫(yī)學(xué)演繹數(shù)據(jù)庫系統(tǒng)MEDICAL IDABLE,該系統(tǒng)包括一個解剖學(xué)模型,可回答用戶的各種提問。
(3)美國加州大學(xué)伯克利分校研制的POSTQUEL系統(tǒng):是對Ingres的查詢語言QUEL的擴充,可用關(guān)鍵字retrieve^*標(biāo)明一個檢索的重復(fù)執(zhí)行,并模擬Datalog規(guī)則的遞歸查詢。
(4)問題回答系統(tǒng)(question answering system):系統(tǒng)能用自然語言進(jìn)行問答,具有較高智能。系統(tǒng)中的演繹系統(tǒng),能理解自然語言并將其轉(zhuǎn)換成形式語言(如謂詞演算等),也能將形式語言轉(zhuǎn)換成自然語言。同時系統(tǒng)有完善的信息檢索系統(tǒng),能對存儲在數(shù)據(jù)庫中的各種事實進(jìn)行邏輯演繹推理,以得到所需要的具體答案。
(5) 由馬里蘭大學(xué)J.Minker等采用謂詞演算方法實現(xiàn)的馬里蘭反演證明過程系統(tǒng)(MRPPS)(見圖2)。

圖2 馬里蘭反演證明過程系統(tǒng)(MRPPS)

綜上所述,作為智能數(shù)據(jù)庫初級階段的演繹數(shù)據(jù)庫迄今還一直停留在試驗和原型化階段,還沒有商品化的演繹數(shù)據(jù)庫系統(tǒng)問世。就其原因,主要是基于邏輯數(shù)據(jù)模型的演繹數(shù)據(jù)庫采用的遞歸查詢算法的計算效率很低。因此,提高演繹數(shù)據(jù)庫的查詢效率,實現(xiàn)查詢優(yōu)化與智能檢索和完善演繹數(shù)據(jù)庫的各種算法等,多年來一直是演繹數(shù)據(jù)庫研究領(lǐng)域面臨的主要問題。此外,基于Horn邏輯的語言如何有效實現(xiàn)、演繹數(shù)據(jù)庫的計算傳遞閉包算法能否用更加簡便的遞歸查詢計算來代替等問題,也都需要進(jìn)行更加深入的研究。而且,演繹數(shù)據(jù)庫至今并未能流行起來,還與演繹數(shù)據(jù)庫缺乏應(yīng)用需求的強力推動有著密切的關(guān)系。隨著人工智能、計算智能(神經(jīng)網(wǎng)絡(luò)、遺傳算法、模糊邏輯)、數(shù)據(jù)挖掘與知識發(fā)現(xiàn)、Web數(shù)據(jù)庫和Agent等技術(shù)的飛速發(fā)展,人們期盼演繹數(shù)據(jù)庫、知識庫等智能數(shù)據(jù)庫技術(shù)取得突破性進(jìn)展。