1、10.2 分布式知识库系统10.2.1 知识库知识库1.知识库基本概念知识库基本概念简单定义：知识库是存储常用知识(命令和规则等)的内涵数据库和存储事实(基本数据)的外延数据库的联合体。知识库系统的接口：用户查询通过外延数据库隐含地使用存储在内涵数据库中的知识。困难和问题：知识的表示，知识的一致性，和知识库的查询处理。2.知识表示知识表示 在人工智能中有四类知识表达方法：产生在人工智能中有四类知识表达方法：产生式规则、框架、语义网络和数学逻辑。数学逻式规则、框架、语义网络和数学逻辑。数学逻辑是用来表示人类思维和推理的最理想方法，辑是用来表示人类思维和推理的最理想方法，也为知识库提供了最好的基础
2、。也为知识库提供了最好的基础。一般认为知识库是基于知识逻辑的数据一般认为知识库是基于知识逻辑的数据库，或称为逻辑数据库和演绎数据库并假定它库，或称为逻辑数据库和演绎数据库并假定它们都是基于关系数据库之上的。们都是基于关系数据库之上的。称为称为Horn子句的一种特殊公式是逻辑数子句的一种特殊公式是逻辑数据库的基础据库的基础。一个一个HornHorn子句的形式为：设子句的形式为：设A A和和B B1 1,B,B2 2，B Bn n是肯定的原子公式，是肯定的原子公式，及形及形式为式为P(tP(t1 1,t,t2 2,t,tn n)谓词，谓词，采用逻辑隐含符号采用逻辑隐含符号“”，那么一个，那么一个H
3、ornHorn子句一子句一般写成般写成 B B1 1 B B2 2BBn n A A 一个一个HornHorn子句对应于一个规则。子句对应于一个规则。A A称为规则的称为规则的头，头，B Bi i的积称为规则的体。不为空的规则称为基的积称为规则的体。不为空的规则称为基本子句。一个空句是具有空体的规则，一个事实本子句。一个空句是具有空体的规则，一个事实是没有变量的基本子句。因而，一个逻辑数据库是没有变量的基本子句。因而，一个逻辑数据库可以定义成规则的一个集合，规则的谓词名字对可以定义成规则的一个集合，规则的谓词名字对应关系名或函数名，变量名对应于属性名，常数应关系名或函数名，变量名对应于属性名，
4、常数对应于属性值。一个逻辑数据库可以被解释为元对应于属性值。一个逻辑数据库可以被解释为元组集合所能满足的全部谓词。此时，关系和谓词组集合所能满足的全部谓词。此时，关系和谓词可以认为是对等的。可以认为是对等的。在逻辑数据库的规则中，一个重要在逻辑数据库的规则中，一个重要类型的规则被称为递归规则，其头部和类型的规则被称为递归规则，其头部和体部具有相同的谓词（递归谓词）。一体部具有相同的谓词（递归谓词）。一个规则被称为线性递归，要求递归谓词个规则被称为线性递归，要求递归谓词在其体中出现一次。在其体中出现一次。例10.5 这是一个逻辑数据库的典型例子,它基于父辈和祖辈谓词。parent(join,an
5、n)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关 系（descendant,ascendant）是导出关系，并且指定了内涵数
6、据库。例如，线形递归规则：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 例10.6 考虑关系:part（pname，weight，support_pname）其中pname和support_pname具有相同的域,weight是pn
7、ame的重量.support_pname是组装到(支持)pname中去的零件名.如果p1零件支持p2,则p1的总重量是p1和 p2单独重量之和.逻辑数据库的另一个例子是（空值用null表示）：part（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个事实），内涵数据库由同样模式的导出关系组成，它给出了每一零件
8、的总重量。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)3.知识库语言PROLOG基于一阶谓词的逻辑程序语言,但不是纯粹的逻辑语言,而且不能用作逻辑数据库。DATALOG纯粹的基于Horn Clause的语言。用于非程序定义规则的语言。缺点是不带函数，建模能力差。停留在理论研究层次上和实验中。10.2.2 逻辑查询处理逻辑查询处理讨论用DATALOG语言表达的逻辑
9、查询处理.因为DATALOG是关系演算的超集.问题：递归查询技术：自底向上的估算技术.内涵数据库被看成是参数查询的一个集合,每一个参数查询被出现在规则头上的谓词所定义.在逻辑数据库中的查询是一个带有实际参数值的谓词,谓词中的变量与常数捆绑(用常数替换).主要步骤:第一步：如果查询规则的头或体引用了查询谓词,就将查询和相关规则合并.相关规则的快速存取可以通过某种形式的索引机制达到,如谓词连接图.查询中的这种捆绑可以在规则体中传播.这一步产生了已捆绑的规则程序.第二步：将规则程序翻译成一个以逻辑数据库的内部语言表示的优化程序.为了使用关系查询优化技术,内部语言可以选择含有控制语句,如“while
10、to”和“if then”的关系代数.例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”)第一步产生第一步产生:R(ENAME,“CAD/CAM”)E(ENO,
11、ENME,_),G(ENO,JNO,_,_),J(JNO,“CAD/CAM”,_)第二步第二步,它可以翻译成关系代数表达式它可以翻译成关系代数表达式:ENAME,JNAME(JNAME=CAD/CAM(J)JNOG)ENOE)在上面的例子中,把逻辑查询处理降级成关系查询处理.对于递归查询这样就不可以了,它们不能直接影射成系代数,因为关系代数没有递归或者重复操作符.自然估算:采用重复“while do”操作符和关系代数来处理递归的简单技术,重复应用规则以导出新元组,直到所有元组都被完全导出.T是通过递归规则导出的关系,R是存储外延知识的系,f(T)是根据规则体对T进行关系代数运算所产生的新关系的
12、函数.算法10.5 NAIVEinput:R:operand relationoutput:T:output relationbegin T R while T is not empty do T T f(R)end.NAIVE例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=childT)其中:p.child表示父亲关系的第一个属性,T.pa
13、r表示T关系的第二个关系.第一次迭代连接父亲关系和它自己,产生:R1=parent(cathy,ann),(michael,ann),(juliette,john),(sarah,john)第二次迭代产生:R2=R1(juliette,ann),(sarah,ann)自然估算的主要缺点是产生冗余工作.因为在一次迭代中,函数f(T)计算了前一次迭代推导出的元组,即在每次迭代中重复了元组的推倒过程.在例10.8中四个元组在第一次迭代中产生,在第二次中又产生.半自然估算方法是对自然估算方法的改进,在每个迭代中仅考虑那些新导出的元组,其主要方法是利用增量关系.算法10.6 SEMINAIVEinput
14、:R:operand relationoutput:T:output relationdeclare DR:relationbegin DR R T R while DR is not empty do begin DR df(R,DR)T TDR end-while end.SEMINAIVE例10.9 关系ancestor的半自然估算可表示为 DR parent T parent while DR is not empty do begin DR p.child,DR.par(parent par=childDR)T T DR end10.2.3 并行递归查询处理 通过把知识库和分布式数据
15、库技术的有机结合得到分布式知识库,使知识库管理的性能得以显著改进.例如,考虑在一个完全不共享数据服务器上建立一个逻辑数据库,由于递归查询的复杂性使得并行查询处理变得更加困难.下面集中讨论并行递归查询处理问题.1.迭代传递闭包算法(ITC)设基本关系R为一个具有属性A和B的二元关系,A和B在同一值域上定义.关系R可以被看成一个有向图边的集合,R的元组(a,b)表示从站点a到站点b的一条边.R的元组个数成为R的深度,标记为depth(R),即图中的最长路径,或边的个数.R的传递闭包,记作R+,等价于相应图的传递闭包.换句话说,元组(x,y)在R+中,当且仅当在图中有一条从x到y且长度大于零的路径.
16、用*表示两个二元关系R(A,B)和P(B,C)的组合,其所有的属性都在一个域上定义,并且把Ri作为关系R的第i次幂,即,R1=RRi=Ri-1*R.这样:R*P=(a,c)|(b)(a,b)R and(b,c)P R+=UiB Ri R*P可以通过投影操作和连接操作来实现:R*P=A,C(R BP)例10.10 图10.8是相应于parent关系的图,和相应于传递闭包parent+关系的图.DAJohn CathyMichaelSarahJulietteAnnJohnJohnCathyCathyDAJohn CathyMichaelSarahJulietteAnnJohnJohnCathyCa
17、thyCathyMichealJulietteSarahAnnAnnJohnJohnJuliettesarahAnnAnnAnnJohnMichaelCathySarahJuliette图 10.8 parent关系的传递闭包算法10.7 ITC(采用增量关系的半自然估算)input:R:operand relationoutput:T:output relationdeclare DR:relationbegin DR R T R while DR is not empty do begin DR DR*R T TDR end_whileend.ITC 2.传递封闭关系的传递闭包算法(TCC
18、R)传递封闭关系是这样一种关系,它所对应的传递闭包不会产生新的元组.设关系R可以分割为R1和R2(即R=R1 R2),直接计算R的闭包R+的办法是ITC(R1+R2+).这将重复计算R1+和 R2+,存在冗余的工作.算法TCCR计算了两个传递闭包关系的传递闭包,该算法避免了重复计算工作.该算法通过产生一种组合序列来计算R1+R2+的传递闭包,如(R1R1)或(R2R2)这样的序列是不会出现的.因为交替组合的序列不包含冗余部分,所以TCCR算法不会存在重复的工作.算法10.8 TCCR input:R1,R2:操作数关系ouput:T:输出关系declare DR1,DR2:关系begin DR
19、1 R1 R2 DR2 R2 R1 T R1 R2 DR1 DR2while DR1不为空 or DR2不为空 dobegin DR1 (DR1 R1)(DR1 R2)DR2 (DR2 R1)(DR2 R2)end_while T T DR1 DR2end.TCCR例10.12 以例10.6的parent关系来举例说明TCCR.假定parent可以分割为下面的parent1和parent2:parent1:(join,ann),(sarah,cathy),(juliette,cathy)parent2:(cathy,john),(michael,john)初始化为:DR1:(sarah,joh
20、n),(juliette,john)DR2:(cathy,ann),(micheal,ann)第一次迭代中:DR1:(sarah,ann),(juliette,ann)DR2:为空 最后,第二次迭代没有产生新的元组,算法结束.3.并行操作的传递闭包算法 并行操作的传递闭包算法是ITC算法的并行版本.关系R分簇与n个站上.TCPO算法采用散列连接算法来实现关系组合的连接操作,使用并(union)操作来合并局部执行的局部结果,从而来实现全局并操作,这样使得全局并操作所需的站点间通信最少.但是,其结果可能会在不同的站点包含有重复的元组,因此,需要消除那些有重复的元组,然后求得传递闭包.为了简化TCP
21、O算法的描述，假定关系R和增量关系DR都有属性A和B，在R和DR上执行组合操作定义为 R DR=R.A,RD.B(R B=A DR)此外,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的元
22、组被移到了具有匹配元组的R的站点.DR元组在n个站点上的分布是在每次循环中做的.当DR为空时,循环终止.因为DR在n个站点上分布,因此,终止测试必须 在一个中央控制点上(是n个站点中的一个)完成,该控制站点来自于每个站点i(i=1,n)的布尔值“DR为空?”.当所有的DRi为空时,处理阶段结束.结果关系T分布于n个站点,并且在不同的站点上可能包含有相同的新元组.结果阶段消除这些重复的元组,这可以通过一个并行基于hash算法来实现.T首先根据一个属性(如A)的hash算法在n个站点分片,此操作可能在n个并行的消除操作后完成.此外,操作的结果分布在n个站点上.例10.13 n=4时,TCPO算法的
23、初始和处理阶段.初始分割(R,B)处理第一遍(DR,A)处理第二遍(DR,A)hash R1hash R2hash R3hash R4Hash(R1 DR1)Hash(R2 DR2)Hash(R3DR3)Hash(R4 DR4)Hash(R1 DR1)Hash(R2 DR2)Hash(R3DR3)Hash(R4 DR4)4.并行程序的传递闭包算法 将传递闭包操作分解为一组并行程序,每个程序使用ITC算法或TCCR算法执行.TCCP算法分成两个阶段:初始阶段和处理阶段.在初始阶段,使用ITC算法来产生传递封闭关系;在处理阶段,使用TCCR算法处理这个传递闭包关系.在处理过程中,将n个传递闭包关系
24、看做一棵二叉树,每次迭代做并操作,直到抵达树根.与TCPO算法相比较,TCPP算法不需要达到恒定的平行度.此算法使站点间的通信最少.在初始阶段并行度为n,在每遍处理过程中减半,直到为单个站点时结束操作.例10.14 n=4时两个处理阶段的TCCR算法.箭头表示了结点之间的通信.为了使站点间通信最少,站点的二叉树安排如下,每一遍使用紧前一遍处理使用的某些站点.ITCITCITCITCTCCRTCCRITCR+1R+2R+3R+4TCCR(R1+R2+)TCCR(R3+R4+)初始化处理第1遍处理第2遍5.性能比较 并行传递闭包算法与集中式算法:将所有操作数据移动到一个站点,然后终止.性能比较表明,并行算法比集中式有显著性能改善.当站点数较多(超过16个)和传递闭包将产生大量新元组时改善系数最大.TCPO的响应时间比算法TCPP要好,原因是TCPO的并行度是n,而TCPP每遍减半.相对与集中算法,TCPP改善一个数量级,而TCPO改善两个数量级.综合考虑时间和总成本时,TCPP比TCPO的性能要好.谢 谢！
