分布式知识库系统课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,10.2 分布式知识库系统,10.2 分布式知识库系统,1,10.2.1 知识库,1.,知识库基本概念,简单定义,：,知识库是存储常用知识(命令和规则等)的,内涵数据库,和存储事实(基本数据)的,外延数据库,的联合体。,知识库系统的接口,：,用户查询通过外延数据库隐含地使用存储在内涵数据库中的知识。,困难和问题,：,知识的表示，知识的一致性，和知识库的查询处理。,10.2.1 知识库1.知识库基本概念,2,2.,知识表示,在人工智能中有四类知识表达方法：产生式规则、框架、语义网络和数学逻辑。数学逻辑是用来表示人类思维和推理的最理想方法，也为知识库提供了最好的基础。,一般认为知识库是基于知识逻辑的数据库，或称为逻辑数据库和演绎数据库并假定它们都是基于关系数据库之上的。,称为Horn子句的一种特殊公式是逻辑数据库的基础,。,分布式知识库系统课件,3,一个Horn子句的形式为：设A和B,1,B,2，,，B,n,是肯定的原子公式，及形式为P(t,1,t,2,t,n,)谓词，采用逻辑隐含符号“,”，那么一个Horn子句一般写成,B,1,B,2,B,n,A,一个Horn子句对应于一个规则。A称为规则的头，B,i,的积称为规则的体。不为空的规则称为基本子句。一个空句是具有空体的规则，一个事实是没有变量的基本子句。因而，一个逻辑数据库可以定义成规则的一个集合，规则的谓词名字对应关系名或函数名，变量名对应于属性名，常数对应于属性值。一个逻辑数据库可以被解释为元组集合所能满足的全部谓词。此时，关系和谓词可以认为是对等的。,一个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)return false,系（descendant,ascendant）是导出,7,例10.6 考虑关系:,part（pname，weight，support_pname）,其中,pname,和,support_pname,具有相同的域,weight,是,pname,的重量.,support_pname,是组装到(支持),pname,中去的零件名.如果,p,1,零件支持,p,2,则,p,1,的总重量是,p,1,和,p,2,单独重量之和.,逻辑数据库的另一个例子是（空值用null表示）：,例10.6 考虑关系:,8,part（p,1,，30，p,2,）,part（p,2,，20，p,3,）,part（p,3,，10，null）,part（p,4,，10，null）,total_part(p，W，S),part(p，W，S),total_part(p,W,S),total_part(p,W,1,p,1,),total_part(p,1,W,1,S)，sum（W,W,1,W,2,）,外延数据库由part关系组成（4个事实），内涵数据库由同样模式的导出关系组成，它给出了每一零件的总重量。sum(W,W,1,W,2,)是一个谓词，当W是W,1,和W,2,之和为真时，递归规则使得可以从一个零件导出被其传递支持的所有零件，例如，有,?part（p,2,，W，S）return(p,2,，20，p,3,),?total_part(p,2,W,S)return(,p,2,20,p,3,),(p,2,30,null),part（p1，30，p2）,9,3.知识库语言,PROLOG,基于一阶谓词的逻辑程序语言,但不是纯粹的逻辑语言,而且不能用作逻辑数据库。,DATALOG,纯粹的基于,Horn Clause,的语言。用于非程序定义规则的语言。缺点是不带函数，建模能力差。停留在理论研究层次上和实验中。,3.知识库语言,10,10.2.2 逻辑查询处理,讨论用,DATALOG,语言表达的逻辑查询处理.因为,DATALOG,是关系演算的超集.,问题：递归查询,技术：自底向上的估算技术.内涵数据库被看成是参数查询的一个集合,每一个参数查询被出现在规则头上的谓词所定义.在逻辑数据库中的查询是一个带有实际参数值的谓词,谓词中的变量与常数捆绑(用常数替换).,10.2.2 逻辑查询处理讨论用DATALOG语言表达的逻,11,主要步骤:,第一步：如果查询规则的头或体引用了查询谓词,就将查询和相关规则合并.相关规则的快速存取可以通过某种形式的索引机制达到,如谓词连接图.查询中的这种捆绑可以在规则体中传播.这一步产生了已捆绑的规则程序.,第二步：将规则程序翻译成一个以逻辑数据库的内部语言表示的优化程序.为了使用关系查询优化技术,内部语言可以选择含有控制语句,如“,while to,”和“,if then,”的关系代数.,主要步骤:,12,例10.7 考虑工程数据库中的查询要求:“寻找在CAD/CAM项目上工作的雇员”,这可以用如下的SQL语句表达:,SELECT ENAME,JNAME FROM E,G,J,WHERE E.ENO=G.ENO AND G.PNO=J.JNO,AND JNAME=“CAD/CAM”,抽象这个查询需要一个规则(其中_表示忽略):,R(ENAME,JNAME),E(ENO,ENME,_),G(ENO,JNO,_,_),J(JNO,JNAME,_),这个查询可以表达成,?R(ENAME,“CAD/CAM”),例10.7 考虑工程数据库中的查询要求:“寻找在CAD/C,13,第一步产生:,R(ENAME,“CAD/CAM”),E(ENO,ENME,_),G(ENO,JNO,_,_),J(JNO,“CAD/CAM”,_),第二步,它可以翻译成关系代数表达式:,ENAME,JNAME,(,JNAME=CAD/CAM,(J),JNO,G),ENO,E),在上面的例子中,把逻辑查询处理降级成关系查询处理.对于递归查询这样就不可以了,它们不能直接影射成系代数,因为关系代数没有递归或者重复操作符.,自然估算:采用重复“while do”操作符和关系代数来处理递归的简单技术,重复应用规则以导出新元组,直到所有元组都被完全导出.,第一步产生:,14,T是通过递归规则导出的关系,R是存储外延知识的系,f(T)是根据规则体对T进行关系代数运算所产生的新关系的函数.,算法10.5,NAIVE,input:R:operand relation,output:T:output relation,begin,T,R,while T is not empty do,T,T,f(R),end.NAIVE,T是通过递归规则导出的关系,R是存储外延知识的系,f(,15,例10.8,考虑例10.5的逻辑数据库和查询:,?ancestor(D,A),这要求计算所有的(descendant,ascendant)对.,这个ancestor关系的自然估算可以表示成:,T,parent,while T is not empty do,T ,p.child,T.par,(,parent,par=child,T),其中:p.child表示父亲关系的第一个属性,T.par表示T关系,的第二个关系.,第一次迭代连接父亲关系和它自己,产生,:,R,1,=parent(cathy,ann),(michael,ann),(juliette,john),(sarah,john),例10.8 考虑例10.5的逻辑数据库和查询:,16,第二次迭代产生:,R,2,=R,1,(juliette,ann),(sarah,ann),自然估算的主要缺点是产生冗余工作.,因为在一次迭代中,函数f(T)计算了前一次,迭代推导出的元组,即在每次迭代中重复了,元组的推倒过程.在例10.8中四个元组在第,一次迭代中产生,在第二次中又产生.,半自然估算方法是对自然估算方法的,改进,在每个迭代中仅考虑那些新导出的元,组,其主要方法是利用增量关系.,第二次迭代产生:,17,算法10.6,SEMINAIVE,input:R:operand relation,output:T:output relation,declare,DR:relation,begin,DR,R,T,R,while DR is not empty do,begin,DR,df(R,DR),T,T,DR,end-while,end.SEMINAIVE,算法10.6 SEMINAIVE,18,例10.9 关系ancestor的半自然估算可表示为,DR,parent,T parent,while DR is not empty do,begin,DR,p.child,DR.par,(parent,par=child,DR),T,T,DR,end,例10.9 关系ancestor的半自然估算可表示为,19,10.2.3 并行递归查询处理,通过把知识库和分布式数据库技术的有,机结合得到分布式知识库,使知识库管理的,性能得以显著改进.例如,考虑在一个完全不,共享数据服务器上建立一个逻辑数据库,由,于递归查询的复杂性使得并行查询处理变,得更加困难.下面集中讨论并行递归查询处,理问题.,10.2.3 并行递归查询处理,20,1.迭代传递闭包算法(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)的组合,其所有的属性都在一个域上定义,并且把R,i,作为关系R的第i次幂,即,R,1,=RR,i,=R,i-1,*R.这样:,R*P=(a,c)|(,b)(a,b),R and(b,c),P,R,+,=U,iB,R,i,R*P可以通过投影操作和连接操作来实现:,R*P=,A,C,(R,B,P,),和P(B,C)的组合,其所有的属性都在一个域上定义,并,22,例10.10 图10.8是相应于parent关系的图,和相应于传递闭包parent,+,关系的图.,D,A,John,Cathy,Michael,Sarah,Juliette,Ann,John,John,Cathy