数据库与知识库原理 dbkb3.ppt

第三章 逻辑作为数据模型 3.1 逻辑规则含义 3.2 Datalog数据模型 3.3 非递归规则求解 3.4 递归规则求解 3.5 最小不动点的增量求解 3.6 带否定的规则体 3.7 关系代数与逻辑 3.8 域关系演算 3.9 元组关系演算 3.10 封闭世界假设 第三章 逻辑作为数据模型 3.1 逻辑规则含义 3.2 Datalog数据模型 3.3 非递归规则求解 3.4 递归规则求解 3.5 最小不动点的增量求解 3.6 带否定的规则体 3.7 关系代数与逻辑 3.8 域关系演算 3.9 元组关系演算 3.10 封闭世界假设 逻辑规则含义 (1) boss(E,M) :- manages(E,M). (2) boss(E,M) :- boss(E,N) manages(N,M). 事实上，有三种不同的方法来解释规则的含义 规则的证明论解释 规则的模型论解释 规则含义的计算性定义 规则的证明论解释 将规则作为证明中使用的公理，从数据库中的事实出发，通过各种可能的方式使用规则来推出事实 (1) boss(E,M) :- manages(E,M). (2) boss(E,M) :- boss(E,N) manages(N,M). q :- p. 给定事实:?q 规则证明论解释的含义规定：从给定的或数据库中存在的事实出发，仅以从右（前提）至左（结论）的方式使用规则所能推出的事实集合 规则的模型论解释 规则作为所定义的领域或模型 对一组谓词的解释是对它们每个可能的实例赋以真值或假值 谓词的自变元是从某些常数组成的无限域中取值的 一种常用的解释：规则真实例的集合 能够在所有规则中的变量从其取值域中被赋予任意值的情况下，都使这些规则为真 例 下述规则中变量X的取值域为整数集(1) p(X) :- q(X).(2) q(X) :- r(X). M1={r(1)，q(1)，p(1)，q(2)，p(2)，p(3)} 无论用哪个整数替换X，上述规则均满足，因此，M1是一个模型 M2={r(1)} (1) p(X) :- q(X). (2) q(X) :- r(X). 利用规则来定义数据库上的操作 当且仅当在关系中存在对应元组的情况下，相应的数据库谓词的实例才为真 把数据库扩展为在所有谓词上的一个模型，并且将这样的模型看成是由规则定义的一个可能的领域 r作为一个数据库谓词，p和q通过r来定义 在r(1)为真，且X?1，r(x)为假的情况下 M1={r(1)，q(1)，p(1)，q(2)，p(2)，p(3)} M3={r(1)，q(1)，p(1)} 有无穷多个模型与仅有r(1)为真的数据库相容 规则含义的计算性定义 提供一个“执行”规则的算法，以区分一个潜在事实（以常数作为自变元的谓词）的真假值 Prolog：所采用的算法还包括有有哪些信誉好的足球投注网站潜在事实的证明的功能 为了找到证明而采用的事实集不一定与证明所存在的所有事实的集合相同 Prolog所找到的真事实集也不一定是一个模型 在常见的情况下，如果把一个规则集作为Prolog程序来运行的话，Prolog将成功地为它产生一个极小模型 将规则转换成关系代数中的操作序列 不带否定的Datalog规则：会计算出惟一极小模型，因而也是能从数据库中证明的事实集 允许否定的情况下：对于分层否定情况，将会得到一个极小模型，尽管这个极小模型可能并不是惟一的 含义比较 如果想实现一个知识库系统，高效的计算能力是一个非常重要的因素 只有在存在高效的计算逻辑规则含义的算法的前提下，规则才可能被当作程序 对规则含义的纯操作定义也是无法接受的 将使人们对规则含义的理解变得非常困难 只要对于基于逻辑语言的用户来说，规则含义足够清楚就可以了 第三章 逻辑作为数据模型 3.1 逻辑规则含义 3.2 Datalog数据模型 3.3 非递归规则求解 3.4 递归规则求解 3.5 最小不动点的增量求解 3.6 带否定的规则体 3.7 关系代数与逻辑 3.8 域关系演算 3.9 元组关系演算 3.10 封闭世界假设 Datalog与Prolog的区别 Datalog不允许在谓词的自变元中出现函数符号，只允许变量和常数作为谓词变元 Datalog程序的含义遵循模型论观点，在等价的情况下也遵循证明论观点。Prolog所具有的计算性含义在某些情况下却既不符合模型论，又不符合证明论 Datalog支持描述性的查询语言。虽然Datalog在语法上类似于Prolog，但不象Prolog那样有更多的过程化语义 Datalog与关系模型 Datalog中的谓词符号可以表示关系 p(X，Y，Z) 在Dat