分布式知識庫系統(tǒng)課件

10.2分布式知識庫系統(tǒng)10.2分布式知識庫系統(tǒng)110.2.1知識庫1.知識庫基本概念簡單定義：知識庫是存儲常用知識(命令和規(guī)則等)的內(nèi)涵數(shù)據(jù)庫和存儲事實(基本數(shù)據(jù))的外延數(shù)據(jù)庫的聯(lián)合體。知識庫系統(tǒng)的接口：用戶查詢通過外延數(shù)據(jù)庫隱含地使用存儲在內(nèi)涵數(shù)據(jù)庫中的知識。困難和問題：知識的表示，知識的一致性，和知識庫的查詢處理。10.2.1知識庫1.知識庫基本概念22.知識表示

在人工智能中有四類知識表達方法：產(chǎn)生式規(guī)則、框架、語義網(wǎng)絡(luò)和數(shù)學(xué)邏輯。數(shù)學(xué)邏輯是用來表示人類思維和推理的最理想方法，也為知識庫提供了最好的基礎(chǔ)。

一般認為知識庫是基于知識邏輯的數(shù)據(jù)庫，或稱為邏輯數(shù)據(jù)庫和演繹數(shù)據(jù)庫并假定它們都是基于關(guān)系數(shù)據(jù)庫之上的。稱為Horn子句的一種特殊公式是邏輯數(shù)據(jù)庫的基礎(chǔ)。分布式知識庫系統(tǒng)課件3一個Horn子句的形式為：設(shè)A和B1,B2，…，Bn是肯定的原子公式，及形式為P(t1,t2,…,tn)謂詞，采用邏輯隱含符號“→”，那么一個Horn子句一般寫成B1∩B2∩…∩Bn

→A一個Horn子句對應(yīng)于一個規(guī)則。A稱為規(guī)則的頭，Bi的積稱為規(guī)則的體。不為空的規(guī)則稱為基本子句。一個空句是具有空體的規(guī)則，一個事實是沒有變量的基本子句。因而，一個邏輯數(shù)據(jù)庫可以定義成規(guī)則的一個集合，規(guī)則的謂詞名字對應(yīng)關(guān)系名或函數(shù)名，變量名對應(yīng)于屬性名，常數(shù)對應(yīng)于屬性值。一個邏輯數(shù)據(jù)庫可以被解釋為元組集合所能滿足的全部謂詞。此時，關(guān)系和謂詞可以認為是對等的。一個Horn子句的形式為：設(shè)A和B1,B2，…，4

在邏輯數(shù)據(jù)庫的規(guī)則中，一個重要類型的規(guī)則被稱為遞歸規(guī)則，其頭部和體部具有相同的謂詞（遞歸謂詞）。一個規(guī)則被稱為線性遞歸，要求遞歸謂詞在其體中出現(xiàn)一次。

在邏輯數(shù)據(jù)庫的規(guī)則中，一個重要類型的規(guī)則5例10.5這是一個邏輯數(shù)據(jù)庫的典型例子,它基于父輩和祖輩謂詞。

parent(join,ann)parent(cathy,john)parent(michael,john)parent(sarah,cathy)parent(juliette,cathy)ancestor(D,A)

parent(D,A)ancestor(D,A)

parent(D,P),ancestor(P,A)

邏輯數(shù)據(jù)庫包含五個事實，定義了parent關(guān)系（或parent謂詞），還有兩個規(guī)則定義了ancestor關(guān)系（或ancestor）。parent關(guān)系聯(lián)系著一個孩子（第一屬性）與他的父親（第二屬性）指定了外延數(shù)據(jù)庫。模式的ancestor關(guān)例10.5這是一個邏輯數(shù)據(jù)庫的典型例子,它基于父輩和祖6系（descendant,ascendant）是導(dǎo)出關(guān)系，并且指定了內(nèi)涵數(shù)據(jù)庫。例如，線形遞歸規(guī)則：ancestor(D,A)

parent(D,P),ancestor(P,A)翻譯成:如果有三個概念D,P和A,這樣parent(D,P)為真,那么ancestor(D,P)也為真。這兩個規(guī)則定義了ancestor關(guān)系把parent關(guān)系作為輸入來導(dǎo)出ancestor關(guān)系?，F(xiàn)舉例查詢:?parent(cathy,P)return(cathy,john)?parent(cathy,bill)returnfalse

系（descendant,ascendant）是導(dǎo)出7例10.6考慮關(guān)系:

part（pname，weight，support_pname）其中pname和support_pname具有相同的域,weight是pname的重量.support_pname是組裝到(支持)pname中去的零件名.如果p1零件支持p2,則p1的總重量是p1和

p2單獨重量之和.邏輯數(shù)據(jù)庫的另一個例子是（空值用null表示）：

例10.6考慮關(guān)系:8part（p1，30，p2）part（p2，20，p3）part（p3，10，null）part（p4，10，null）total_part(p，W，S)

part(p，W，S)total_part(p,W,S)

total_part(p,W1,p1),total_part(p1,W1,S)，sum（W,W1,W2）外延數(shù)據(jù)庫由part關(guān)系組成（4個事實），內(nèi)涵數(shù)據(jù)庫由同樣模式的導(dǎo)出關(guān)系組成，它給出了每一零件的總重量。sum(W,W1,W2)是一個謂詞，當(dāng)W是W1和W2之和為真時，遞歸規(guī)則使得可以從一個零件導(dǎo)出被其傳遞支持的所有零件，例如，有

?part（p2，W，S）return(p2，20，p3)?total_part(p2,W,S)return{(p2,20,p3

),(p2,30,null)}

part（p1，30，p2）93.知識庫語言PROLOG基于一階謂詞的邏輯程序語言,但不是純粹的邏輯語言,而且不能用作邏輯數(shù)據(jù)庫。DATALOG純粹的基于HornClause的語言。用于非程序定義規(guī)則的語言。缺點是不帶函數(shù)，建模能力差。停留在理論研究層次上和實驗中。3.知識庫語言1010.2.2邏輯查詢處理討論用DATALOG語言表達的邏輯查詢處理.因為DATALOG是關(guān)系演算的超集.問題：遞歸查詢技術(shù)：自底向上的估算技術(shù).內(nèi)涵數(shù)據(jù)庫被看成是參數(shù)查詢的一個集合,每一個參數(shù)查詢被出現(xiàn)在規(guī)則頭上的謂詞所定義.在邏輯數(shù)據(jù)庫中的查詢是一個帶有實際參數(shù)值的謂詞,謂詞中的變量與常數(shù)捆綁(用常數(shù)替換).10.2.2邏輯查詢處理討論用DATALOG語言表達的邏11主要步驟:第一步：如果查詢規(guī)則的頭或體引用了查詢謂詞,就將查詢和相關(guān)規(guī)則合并.相關(guān)規(guī)則的快速存取可以通過某種形式的索引機制達到,如謂詞連接圖.查詢中的這種捆綁可以在規(guī)則體中傳播.這一步產(chǎn)生了已捆綁的規(guī)則程序.第二步：將規(guī)則程序翻譯成一個以邏輯數(shù)據(jù)庫的內(nèi)部語言表示的優(yōu)化程序.為了使用關(guān)系查詢優(yōu)化技術(shù),內(nèi)部語言可以選擇含有控制語句,如“whileto”和“ifthen”的關(guān)系代數(shù).主要步驟:12例10.7考慮工程數(shù)據(jù)庫中的查詢要求:“尋找在CAD/CAM項目上工作的雇員”,這可以用如下的SQL語句表達:SELECTENAME,JNAMEFROME,G,JWHEREE.ENO=G.ENOANDG.PNO=J.JNOANDJNAME=“CAD/CAM”抽象這個查詢需要一個規(guī)則(其中‘_’表示忽略):R(ENAME,JNAME)

E(ENO,ENME,_),G(ENO,JNO,_,_),J(JNO,JNAME,_)這個查詢可以表達成?R(ENAME,“CAD/CAM”)

例10.7考慮工程數(shù)據(jù)庫中的查詢要求:“尋找在CAD/C13第一步產(chǎn)生:R(ENAME,“CAD/CAM”)

E(ENO,ENME,_),G(ENO,JNO,_,_),J(JNO,“CAD/CAM”,_)第二步,它可以翻譯成關(guān)系代數(shù)表達式:

ENAME,JNAME(((JNAME=‘CAD/CAM’(J))JNOG)ENOE)

在上面的例子中,把邏輯查詢處理降級成關(guān)系查詢處理.對于遞歸查詢這樣就不可以了,它們不能直接影射成系代數(shù),因為關(guān)系代數(shù)沒有遞歸或者重復(fù)操作符.自然估算:采用重復(fù)“whiledo”操作符和關(guān)系代數(shù)來處理遞歸的簡單技術(shù),重復(fù)應(yīng)用規(guī)則以導(dǎo)出新元組,直到所有元組都被完全導(dǎo)出.第一步產(chǎn)生:14T是通過遞歸規(guī)則導(dǎo)出的關(guān)系,R是存儲外延知識的系,f(T)是根據(jù)規(guī)則體對T進行關(guān)系代數(shù)運算所產(chǎn)生的新關(guān)系的函數(shù).算法10.5NAIVEinput:R:operandrelationoutput:T:outputrelationbeginT

RwhileTisnotemptydoT

Tf(R)end.{NAIVE}T是通過遞歸規(guī)則導(dǎo)出的關(guān)系,R是存儲外延知識的系,f(15例10.8考慮例10.5的邏輯數(shù)據(jù)庫和查詢:?ancestor(D,A)這要求計算所有的(descendant,ascendant)對.這個ancestor關(guān)系的自然估算可以表示成:

TparentwhileTisnotemptydo

T

p.child,T.par(parent

par=childT)其中:p.child表示父親關(guān)系的第一個屬性,T.par表示T關(guān)系的第二個關(guān)系.第一次迭代連接父親關(guān)系和它自己,產(chǎn)生:R1=parent{(cathy,ann),(michael,ann),(juliette,john),(sarah,john)}例10.8考慮例10.5的邏輯數(shù)據(jù)庫和查詢:16第二次迭代產(chǎn)生:R2=R1

{(juliette,ann),(sarah,ann)}自然估算的主要缺點是產(chǎn)生冗余工作.因為在一次迭代中,函數(shù)f(T)計算了前一次迭代推導(dǎo)出的元組,即在每次迭代中重復(fù)了元組的推倒過程.在例10.8中四個元組在第一次迭代中產(chǎn)生,在第二次中又產(chǎn)生.半自然估算方法是對自然估算方法的改進,在每個迭代中僅考慮那些新導(dǎo)出的元組,其主要方法是利用增量關(guān)系.第二次迭代產(chǎn)生:17算法10.6SEMINAIVEinput:R:operandrelationoutput:T:outputrelationdeclareDR:relationbeginDR

RT

RwhileDRisnotemptydobeginDRdf(R,DR)T

TDRend-whileend.{SEMINAIVE}算法10.6SEMINAIVE18例10.9關(guān)系ancestor的半自然估算可表示為

DRparentTparentwhileDRisnotemptydobeginDR

p.child,DR.par(parentpar=childDR)

T

T

DR

end例10.9關(guān)系ancestor的半自然估算可表示為1910.2.3并行遞歸查詢處理通過把知識庫和分布式數(shù)據(jù)庫技術(shù)的有機結(jié)合得到分布式知識庫,使知識庫管理的性能得以顯著改進.例如,考慮在一個完全不共享數(shù)據(jù)服務(wù)器上建立一個邏輯數(shù)據(jù)庫,由于遞歸查詢的復(fù)雜性使得并行查詢處理變得更加困難.下面集中討論并行遞歸查詢處理問題.10.2.3并行遞歸查詢處理201.迭代傳遞閉包算法(ITC)設(shè)基本關(guān)系R為一個具有屬性A和B的二元關(guān)系,A和B在同一值域上定義.關(guān)系R可以被看成一個有向圖邊的集合,R的元組(a,b)表示從站點a到站點b的一條邊.R的元組個數(shù)成為R的深度,標(biāo)記為depth(R),即圖中的最長路徑,或邊的個數(shù).R的傳遞閉包,記作R+,等價于相應(yīng)圖的傳遞閉包.換句話說,元組(x,y)在R+中,當(dāng)且僅當(dāng)在圖中有一條從x到y(tǒng)且長度大于零的路徑.用*表示兩個二元關(guān)系R(A,B)1.迭代傳遞閉包算法(ITC)21和P(B,C)的組合,其所有的屬性都在一個域上定義,并且把Ri作為關(guān)系R的第i次冪,即,R1=RRi=Ri-1*R.這樣:R*P={(a,c)|(

b)(a,b)

Rand(b,c)

P}R+=Ui>BRi

R*P可以通過投影操作和連接操作來實現(xiàn):R*P=

A,C(R

BP)和P(B,C)的組合,其所有的屬性都在一個域上定義,并22例10.10圖10.8是相應(yīng)于parent關(guān)系的圖,和相應(yīng)于傳遞閉包parent+關(guān)系的圖.DAJohnCathyMichaelSarahJulietteAnnJohnJohnCathyCathyDAJohnCathyMichaelSarahJulietteAnnJohnJohnCathyCathyCathyMichealJulietteSarahAnnAnnJohnJohnJuliettesarahAnnAnnAnnJohnMichaelCathySarahJuliette圖10.8parent關(guān)系的傳遞閉包例10.10圖10.8是相應(yīng)于parent關(guān)系的圖,和相23算法10.7ITC(采用增量關(guān)系的半自然估算)input:R:operandrelationoutput:T:outputrelationdeclareDR:relationbeginDR

RT

RwhileDRisnotemptydobeginDR

DR*RT

TDRend_whileend.{ITC}

算法10.7ITC(采用增量關(guān)系的半自然估算)242.傳遞封閉關(guān)系的傳遞閉包算法(TCCR)傳遞封閉關(guān)系是這樣一種關(guān)系,它所對應(yīng)的傳遞閉包不會產(chǎn)生新的元組.設(shè)關(guān)系R可以分割為R1和R2(即R=R1

R2),直接計算R的閉包R+的辦法是ITC(R1+

R2+).這將重復(fù)計算R1+

和

R2+,存在冗余的工作.算法TCCR計算了兩個傳遞閉包關(guān)系的傳遞閉包,該算法避免了重復(fù)計算工作.該算法通過產(chǎn)生一種組合序列來計算R1+

R2+的傳遞閉包,如(R1

R1)或(R2

R2)這樣的序列是不會出現(xiàn)的.因為交替組合的序列不包含冗余部分,所以TCCR算法不會存在重復(fù)的工作.2.傳遞封閉關(guān)系的傳遞閉包算法(TCCR)25算法10.8TCCRinput:R1,R2:操作數(shù)關(guān)系ouput:T:輸出關(guān)系declareDR1,DR2:關(guān)系beginDR1

R1

R2DR2

R2

R1

T

R1

R2

DR1

DR2whileDR1不為空orDR2不為空dobeginDR1(DR1

R1)

(DR1

R2)

DR2

(DR2

R1)

(DR2

R2)end_whileT

T

DR1

DR2end.{TCCR}算法10.8TCCR26例10.12以例10.6的parent關(guān)系來舉例說明TCCR.假定parent可以分割為下面的parent1和parent2:parent1:{(join,ann),(sarah,cathy),(juliette,cathy)}parent2:{(cathy,john),(michael,john)}初始化為:DR1:{(sarah,john),(juliette,john)}DR2:{(cathy,ann),(micheal,ann)}第一次迭代中:DR1:{(sarah,ann),(juliette,ann)}DR2:為空最后,第二次迭代沒有產(chǎn)生新的元組,算法結(jié)束.例10.12以例10.6的parent關(guān)系來舉例說明TCC273.并行操作的傳遞閉包算法并行操作的傳遞閉包算法是ITC算法的并行版本.關(guān)系R分簇與n個站上.TCPO算法采用散列連接算法來實現(xiàn)關(guān)系組合的連接操作,使用并(union)操作來合并局部執(zhí)行的局部結(jié)果,從而來實現(xiàn)全局并操作,這樣使得全局并操作所需的站點間通信最少.但是,其結(jié)果可能會在不同的站點包含有重復(fù)的元組,因此,需要消除那些有重復(fù)的元組,然后求得傳遞閉包.為了簡化TCPO算法的描述，假定關(guān)系R和增量關(guān)系DR都有屬性A和B，在R和DR上執(zhí)行組合操作定義為3.并行操作的傳遞閉包算法28RDR=

R.A,RD.B(R

B=ADR)此外,partition(R,A)是指對關(guān)系R進行分割,是在屬性A上使用hash函數(shù)h(A),分簇于n個站點上.TCPO算法可以分為三個相繼的階段:初始階段、處理階段和結(jié)果階段.在初始階段,操作partition(R,B)根據(jù)B上的hash函數(shù)將關(guān)系R分布到n個站點上.關(guān)系T(輸出關(guān)系)和DR也被初始化為R.處理階段是并行連接操作和局部并操作的循環(huán).由于R由作用于屬性B的hash函數(shù)h(B)來分割,并行連接操作包括操作partition(DR,A),因此,DR的元組被移到了具有匹配元組的R的站點.DR元組在n個站點上的分布是在每次循環(huán)中做的.當(dāng)DR為空時,循環(huán)終止.因為DR在n個站點上分布,因此,終止測試必須RDR=R.A,RD.B(29在一個中央控制點上(是n個站點中的一個)完成,該控制站點來自于每個站點i(i=1,…,n)的布爾值“DR為空?”.當(dāng)所有的DRi為空時,處理階段結(jié)束.結(jié)果關(guān)系T分布于n個站點,并且在不同的站點上可能包含有相同的新元組.結(jié)果階段消除這些重復(fù)的元組,這可以通過一個并行基于hash算法來實現(xiàn).T首先根據(jù)一個屬性(如A)的hash算法在n個站點分片,此操作可能在n個并行的消除操作后完成.此外,操作的結(jié)果分布在n個站點上.在一個中央控制點上(是n個站點中的一個)完成,該控制站30例10.13n=4時,TCPO算法的初始和處理階段.初始分割(R,B)處理第一遍(DR,A)處理第二遍