分布式知识库系统课件

10.2分布式知识库系统10.2分布式知识库系统110.2.1知识库1.知识库基本概念简单定义：知识库是存储常用知识(命令和规则等)的内涵数据库和存储事实(基本数据)的外延数据库的联合体。知识库系统的接口：用户查询通过外延数据库隐含地使用存储在内涵数据库中的知识。困难和问题：知识的表示，知识的一致性，和知识库的查询处理。10.2.1知识库1.知识库基本概念22.知识表示

在人工智能中有四类知识表达方法：产生式规则、框架、语义网络和数学逻辑。数学逻辑是用来表示人类思维和推理的最理想方法，也为知识库提供了最好的基础。

一般认为知识库是基于知识逻辑的数据库，或称为逻辑数据库和演绎数据库并假定它们都是基于关系数据库之上的。称为Horn子句的一种特殊公式是逻辑数据库的基础。分布式知识库系统课件3一个Horn子句的形式为：设A和B1,B2，…，Bn是肯定的原子公式，及形式为P(t1,t2,…,tn)谓词，采用逻辑隐含符号“→”，那么一个Horn子句一般写成B1∩B2∩…∩Bn

→A一个Horn子句对应于一个规则。A称为规则的头，Bi的积称为规则的体。不为空的规则称为基本子句。一个空句是具有空体的规则，一个事实是没有变量的基本子句。因而，一个逻辑数据库可以定义成规则的一个集合，规则的谓词名字对应关系名或函数名，变量名对应于属性名，常数对应于属性值。一个逻辑数据库可以被解释为元组集合所能满足的全部谓词。此时，关系和谓词可以认为是对等的。一个Horn子句的形式为：设A和B1,B2，…，4

在逻辑数据库的规则中，一个重要类型的规则被称为递归规则，其头部和体部具有相同的谓词（递归谓词）。一个规则被称为线性递归，要求递归谓词在其体中出现一次。

在逻辑数据库的规则中，一个重要类型的规则5例10.5这是一个逻辑数据库的典型例子,它基于父辈和祖辈谓词。

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)

逻辑数据库包含五个事实，定义了parent关系（或parent谓词），还有两个规则定义了ancestor关系（或ancestor）。parent关系联系着一个孩子（第一属性）与他的父亲（第二属性）指定了外延数据库。模式的ancestor关例10.5这是一个逻辑数据库的典型例子,它基于父辈和祖6系（descendant,ascendant）是导出关系，并且指定了内涵数据库。例如，线形递归规则：ancestor(D,A)

parent(D,P),ancestor(P,A)翻译成:如果有三个概念D,P和A,这样parent(D,P)为真,那么ancestor(D,P)也为真。这两个规则定义了ancestor关系把parent关系作为输入来导出ancestor关系。现举例查询:?parent(cathy,P)return(cathy,john)?parent(cathy,bill)returnfalse

系（descendant,ascendant）是导出7例10.6考虑关系:

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

p2单独重量之和.逻辑数据库的另一个例子是（空值用null表示）：

例10.6考虑关系: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）外延数据库由part关系组成（4个事实），内涵数据库由同样模式的导出关系组成，它给出了每一零件的总重量。sum(W,W1,W2)是一个谓词，当W是W1和W2之和为真时，递归规则使得可以从一个零件导出被其传递支持的所有零件，例如，有

?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基于一阶谓词的逻辑程序语言,但不是纯粹的逻辑语言,而且不能用作逻辑数据库。DATALOG纯粹的基于HornClause的语言。用于非程序定义规则的语言。缺点是不带函数，建模能力差。停留在理论研究层次上和实验中。3.知识库语言1010.2.2逻辑查询处理讨论用DATALOG语言表达的逻辑查询处理.因为DATALOG是关系演算的超集.问题：递归查询技术：自底向上的估算技术.内涵数据库被看成是参数查询的一个集合,每一个参数查询被出现在规则头上的谓词所定义.在逻辑数据库中的查询是一个带有实际参数值的谓词,谓词中的变量与常数捆绑(用常数替换).10.2.2逻辑查询处理讨论用DATALOG语言表达的逻11主要步骤:第一步：如果查询规则的头或体引用了查询谓词,就将查询和相关规则合并.相关规则的快速存取可以通过某种形式的索引机制达到,如谓词连接图.查询中的这种捆绑可以在规则体中传播.这一步产生了已捆绑的规则程序.第二步：将规则程序翻译成一个以逻辑数据库的内部语言表示的优化程序.为了使用关系查询优化技术,内部语言可以选择含有控制语句,如“whileto”和“ifthen”的关系代数.主要步骤:12例10.7考虑工程数据库中的查询要求:“寻找在CAD/CAM项目上工作的雇员”,这可以用如下的SQL语句表达:SELECTENAME,JNAMEFROME,G,JWHEREE.ENO=G.ENOANDG.PNO=J.JNOANDJNAME=“CAD/CAM”抽象这个查询需要一个规则(其中‘_’表示忽略):R(ENAME,JNAME)

E(ENO,ENME,_),G(ENO,JNO,_,_),J(JNO,JNAME,_)这个查询可以表达成?R(ENAME,“CAD/CAM”)

例10.7考虑工程数据库中的查询要求:“寻找在CAD/C13第一步产生:R(ENAME,“CAD/CAM”)

E(ENO,ENME,_),G(ENO,JNO,_,_),J(JNO,“CAD/CAM”,_)第二步,它可以翻译成关系代数表达式:

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

在上面的例子中,把逻辑查询处理降级成关系查询处理.对于递归查询这样就不可以了,它们不能直接影射成系代数,因为关系代数没有递归或者重复操作符.自然估算:采用重复“whiledo”操作符和关系代数来处理递归的简单技术,重复应用规则以导出新元组,直到所有元组都被完全导出.第一步产生:14T是通过递归规则导出的关系,R是存储外延知识的系,f(T)是根据规则体对T进行关系代数运算所产生的新关系的函数.算法10.5NAIVEinput:R:operandrelationoutput:T:outputrelationbeginT

RwhileTisnotemptydoT

Tf(R)end.{NAIVE}T是通过递归规则导出的关系,R是存储外延知识的系,f(15例10.8考虑例10.5的逻辑数据库和查询:?ancestor(D,A)这要求计算所有的(descendant,ascendant)对.这个ancestor关系的自然估算可以表示成:

TparentwhileTisnotemptydo

T

p.child,T.par(parent

par=childT)其中:p.child表示父亲关系的第一个属性,T.par表示T关系的第二个关系.第一次迭代连接父亲关系和它自己,产生:R1=parent{(cathy,ann),(michael,ann),(juliette,john),(sarah,john)}例10.8考虑例10.5的逻辑数据库和查询:16第二次迭代产生:R2=R1

{(juliette,ann),(sarah,ann)}自然估算的主要缺点是产生冗余工作.因为在一次迭代中,函数f(T)计算了前一次迭代推导出的元组,即在每次迭代中重复了元组的推倒过程.在例10.8中四个元组在第一次迭代中产生,在第二次中又产生.半自然估算方法是对自然估算方法的改进,在每个迭代中仅考虑那些新导出的元组,其主要方法是利用增量关系.第二次迭代产生:17算法10.6SEMINAIVEinput:R:operandrelationoutput:T:outputrelationdeclareDR:relationbeginDR

RT

RwhileDRisnotemptydobeginDRdf(R,DR)T

TDRend-whileend.{SEMINAIVE}算法10.6SEMINAIVE18例10.9关系ancestor的半自然估算可表示为

DRparentTparentwhileDRisnotemptydobeginDR

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

T

T

DR

end例10.9关系ancestor的半自然估算可表示为1910.2.3并行递归查询处理通过把知识库和分布式数据库技术的有机结合得到分布式知识库,使知识库管理的性能得以显著改进.例如,考虑在一个完全不共享数据服务器上建立一个逻辑数据库,由于递归查询的复杂性使得并行查询处理变得更加困难.下面集中讨论并行递归查询处理问题.10.2.3并行递归查询处理201.迭代传递闭包算法(ITC)设基本关系R为一个具有属性A和B的二元关系,A和B在同一值域上定义.关系R可以被看成一个有向图边的集合,R的元组(a,b)表示从站点a到站点b的一条边.R的元组个数成为R的深度,标记为depth(R),即图中的最长路径,或边的个数.R的传递闭包,记作R+,等价于相应图的传递闭包.换句话说,元组(x,y)在R+中,当且仅当在图中有一条从x到y且长度大于零的路径.用*表示两个二元关系R(A,B)1.迭代传递闭包算法(ITC)21和P(B,C)的组合,其所有的属性都在一个域上定义,并且把Ri作为关系R的第i次幂,即,R1=RRi=Ri-1*R.这样:R*P={(a,c)|(

b)(a,b)

Rand(b,c)

P}R+=Ui>BRi

R*P可以通过投影操作和连接操作来实现:R*P=

A,C(R

BP)和P(B,C)的组合,其所有的属性都在一个域上定义,并22例10.10图10.8是相应于parent关系的图,和相应于传递闭包parent+关系的图.DAJohnCathyMichaelSarahJulietteAnnJohnJohnCathyCathyDAJohnCathyMichaelSarahJulietteAnnJohnJohnCathyCathyCathyMichealJulietteSarahAnnAnnJohnJohnJuliettesarahAnnAnnAnnJohnMichaelCathySarahJuliette图10.8parent关系的传递闭包例10.10图10.8是相应于parent关系的图,和相23算法10.7ITC(采用增量关系的半自然估算)input:R:operandrelationoutput:T:outputrelationdeclareDR:relationbeginDR

RT

RwhileDRisnotemptydobeginDR

DR*RT

TDRend_whileend.{ITC}

算法10.7ITC(采用增量关系的半自然估算)242.传递封闭关系的传递闭包算法(TCCR)传递封闭关系是这样一种关系,它所对应的传递闭包不会产生新的元组.设关系R可以分割为R1和R2(即R=R1

R2),直接计算R的闭包R+的办法是ITC(R1+

R2+).这将重复计算R1+

和

R2+,存在冗余的工作.算法TCCR计算了两个传递闭包关系的传递闭包,该算法避免了重复计算工作.该算法通过产生一种组合序列来计算R1+

R2+的传递闭包,如(R1

R1)或(R2

R2)这样的序列是不会出现的.因为交替组合的序列不包含冗余部分,所以TCCR算法不会存在重复的工作.2.传递封闭关系的传递闭包算法(TCCR)25算法10.8TCCRinput:R1,R2:操作数关系ouput:T:输出关系declareDR1,DR2:关系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关系来举例说明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:为空最后,第二次迭代没有产生新的元组,算法结束.例10.12以例10.6的parent关系来举例说明TCC273.并行操作的传递闭包算法并行操作的传递闭包算法是ITC算法的并行版本.关系R分簇与n个站上.TCPO算法采用散列连接算法来实现关系组合的连接操作,使用并(union)操作来合并局部执行的局部结果,从而来实现全局并操作,这样使得全局并操作所需的站点间通信最少.但是,其结果可能会在不同的站点包含有重复的元组,因此,需要消除那些有重复的元组,然后求得传递闭包.为了简化TCPO算法的描述，假定关系R和增量关系DR都有属性A和B，在R和DR上执行组合操作定义为3.并行操作的传递闭包算法28RDR=

R.A,RD.B(R

B=ADR)此外,partition(R,A)是指对关系R进行分割,是在属性A上使用hash函数h(A),分簇于n个站点上.TCPO算法可以分为三个相继的阶段:初始阶段、处理阶段和结果阶段.在初始阶段,操作partition(R,B)根据B上的hash函数将关系R分布到n个站点上.关系T(输出关系)和DR也被初始化为R.处理阶段是并行连接操作和局部并操作的循环.由于R由作用于属性B的hash函数h(B)来分割,并行连接操作包括操作partition(DR,A),因此,DR的元组被移到了具有匹配元组的R的站点.DR元组在n个站点上的分布是在每次循环中做的.当DR为空时,循环终止.因为DR在n个站点上分布,因此,终止测试必须RDR=R.A,RD.B(29在一个中央控制点上(是n个站点中的一个)完成,该控制站点来自于每个站点i(i=1,…,n)的布尔值“DR为空?”.当所有的DRi为空时,处理阶段结束.结果关系T分布于n个站点,并且在不同的站点上可能包含有相同的新元组.结果阶段消除这些重复的元组,这可以通过一个并行基于hash算法来实现.T首先根据一个属性(如A)的hash算法在n个站点分片,此操作可能在n个并行的消除操作后完成.此外,操作的结果分布在n个站点上.在一个中央控制点上(是n个站点中的一个)完成,该控制站30例10.13n=4时,TCPO算法的初始和处理阶段.初始分割(R,B)处理第一遍(DR,A)处理第二遍