演绎数据库.ppt

演绎数据库 报告人 马莎 北京市高可靠嵌入式系统工程中心BeijingEngineeringResearchCenterOfHighReliableEmbeddedSystem 目录 演绎数据库基本概念谓词逻辑datalog演绎数据库出现的必要性演绎数据库的实现方法演绎数据库实例与其他数据库的关系演绎数据库的应用 演绎数据库 演绎数据库基本概念演绎数据库 DeductiveDataBase 简称DDB 是数据库技术与逻辑理论相结合的产物 它是一种支持演绎推理功能的数据库 支持Datalog规则的DBMS常被称为演绎数据库也就是说演绎数据库用关系模型 表达事实 和datalog模型 表达规则 来表达世界 演绎功能 关系数据库 演绎数据库演绎推理 假言推理 形式逻辑 P P Q QP Q为事实P Q为规则演绎数据库通常包括外延数据库 EDB 和内涵数据库 IDB EDB是实关系 IDB是虚关系 从其功能不难发现 演绎数据库不仅包含实数据 还包括由逻辑关系组成的规则集及由规则形成的新数据 虚数据 演绎数据库由三部分组成 1 传统数据库管理 由于演绎数据库建立在传统数据库之上 因此传统数据库是演绎数据库的基础 2 具有对一阶谓词逻辑进行推理的演绎结构 这是演绎数据库全部功能特色所在 推理功能由此结构完成 3 数据库与推理机构的接口 由于演绎结构是逻辑的 而数据库是非逻辑的 因此必须有一个接口实现物理上的连接 谓词逻辑 谓词逻辑的合法表达式称为合式公式 它由原子公式 连接词和量词组成 原子公式 由谓词 括号和括号中的项组成 办公地点 刘凌 401 办公地点 陈东华 402 办公地点 张明亮 318 连接词 用来组合原子公式以形成较复杂的合式公式 合取 P Q 当P Q皆为真时 才为真 否则为假 类似 AND 析取 P Q 当P Q中皆为假时 则为假 否则为真 类似 OR 蕴涵 P Q 只有P为真 Q为假时 蕴涵式为假 否则为真 类似 ifPthenQ 否定 例子 张某送给屋里的每个人一件礼物 y IN y ROOM HUMAN y x GIVE ZHANG x y PRESENT x 演绎数据库实例表1父子关系数据库F f s 两种逻辑规则 祖孙规则 F X Z F Z Y G X Y 祖先规则 1 F X Y A X Y 2 A X Z F Z Y A X Y 建立如下两种逻辑规则 1 祖孙规则F X Z F Z Y G X Y 该规则表示X是Z的父亲 Z是Y的父亲 则X是Y的祖父 用父子关系数据库F通过以上规则就得祖孙关系G 表1的数据库得出的祖孙关系为 李学 李山 李平 李同 刘定 刘思 2 祖先规则 1 F X Y A X Y 2 A X Z F Z Y A X Y 其中 1 表示X是Y的父亲 则X是Y的祖先 2 表示X是Z的祖先 Z是Y的父亲 则X是Y的祖先 父子关系F通过以上规则得到祖先关系A Datalog 本质上 Datalog是FOL中Horn子句表示法的子集 是通过对FOL的Horn子句进一步限定而发展起来的 并主要用于演绎数据库的一种简单知识表达语言 Datalog规则 符号 表示逻辑蕴含 其右边部分称为规则体 body 左边部分称为规则头 head Whatdoes mean Assumewehavearule Q PThen means ifPistruethenQistrue 实例 表示事实 human kate human bill likes kate bill 表示kate和bill是人 human kate喜欢bill 表示规则 friend X Y likes X Y likes Y X 表示对于两个对象XY 如果X喜欢Y 且Y喜欢X 那么他们是朋友 演绎数据库是在关系数据库的基础发展起来的 不仅继承了关系数据库数据高度的独立性 非过程性查询语言和面向集合的存取方式等优点 并且演绎数据库使用逻辑作为数据模型便于理论研究 其特点是处理大量数据 具备逻辑推理能力 比视图表示能力强而且能处理递归定义 逻辑语言具有非过程性的特征 并且是完全计算的 是最理想的查询语言 演绎数据库存在的必要性 演绎数据库的查询 用户输入的查询语言DQL是SQL的补充 格式与SQL一致 查询归纳为两种情况 在关系数据库本身得到完整回答的查询由递归规则定义的查询 区别于一般关系数据库的关键功能 递归规则在数据库中的表示形式规则的外部形式是面向对象的 其着重强调规则的可理解性 方便性和表达能力 而规则的内部表示则是面向存储和推理的 演绎数据库的实现方法 目前演绎数据库的实现方法有两种 一种是PROLOG语言实现 另一种是用现有的DBMS RULE来实现 用PROLOG语言实现 由于PROLOG语言是一种基于证明论的语言 因此用它来实现从理论上是完全可行的 但由于PROLOG语言本身是一个逻辑程序设计语言 因此用它来有效地完整地表示一个演绎数据库还需进一步改造 用现有DBMS RULE处理 DBMS部分往往选用目前已有的数据库管理系统 其中RULE部分需要完成推理与接口两部分功能 当用户查询演绎数据库时 如果涉及到的是实关系 则如同通常的数据库查询一样处理 如果涉及到虚关系 则由规则处理部分的演绎结构将其转换成对实关系的查询 最后通过MS的查询结构完成 将最终结果提交给用户 查询归纳为两种情况 在关系数据库本身得到完整回答的查询由递归规则定义的查询 区别于一般关系数据库的关键功能 以上两种查询由查询语言分析器进行判断 前者直接送SQLServer 后者将递归查询对应的规则模块号和查询目标及初始查询值推送推理及处理 查询过程图 演绎数据库查询的特点支持复杂对象支持对存在变元和非确定性查询的处理在DDS系统中 采用了不同于其他系统的方法处理存在变元和非确定性查询长连接优化技术的支持 演绎数据库实例 一个strike 三轮车 总共有哪些配件 为查询每个配件的构成组件 即子配件 可能会先定义一个名为Components的中间结果关系 并构造如下包含两条Datalog规则的逻辑程序 Components Part SubPart Assembly Part Subpart Qty Components Part SubPart Assembly Part Part2 Qty Components Part2 SubPart r1 r2 有了这个推理结果 仅通过使用一个极简单的SQL语句 就可获得strike的所有配件 SELECT FROMComponentsC2WHEREC2 part trike 演绎数据库 智能数据库和知识库的关系 演绎数据库演绎推理加入数据库系统的功能中 智能数据库在数据库系统中加入归纳推理 类比推理等或然性推理 或加入自然语言理解 语音识别等人工智能中更多的技术 知识库对知识的存储和管理 不同于数据库 关系 这三者既有联系又有差别 共同点 三者都是人工智能与数据库的结合 都是以数据库为基础 吸取了人工智能的成功技术的成果 不同点 数据库与知识库是不同的概念 前者管理数据 后者管理知识 知识包含的内容远比数据丰富得多 知识至少包括了规则与数据两大部分 智能数据库不仅应用人工智能中的逻辑推理思想 而且还应用人工智能中自然语言理解 语言识别 图象 文字处理等多种方法与技术于数据库 以求得更多的功能 性能的改善与提高 因此 从某种意义讲 演绎数据库是智能数据库的一部分 演绎数据库的应用 查询效率低下一直阻碍着演绎数据库的发展 至今尚未商品化的产品问世 生物信息 bioinformation 学中的演绎数据库 DeductiveDatabase 或知识库 Knowledgebase 是指能对已有的生物大分子基本信息进行数据挖掘的数据库 它建立在基本数据库的数据基础之上 比较著名的