演绎数据库.ppt
演绎数据库演绎数据库报告人：马莎北京市高可靠嵌入式系统工程中心北京市高可靠嵌入式系统工程中心Beijing Engineering Research Center Of High Reliable Embedded SystemBeijing Engineering Research Center Of High Reliable Embedded System目录演绎数据库基本概念谓词逻辑datalog演绎数据库出现的必要性演绎数据库的实现方法演绎数据库实例与其他数据库的关系演绎数据库的应用演绎数据库演绎数据库基本概念演绎数据库（Deductive DataBase,简称DDB）：是数据库技术与逻辑理论相结合的产物，它是一种支持演绎推理功能的数据库。支持支持DatalogDatalog规则规则的的DBMSDBMS常被称为演绎数据库常被称为演绎数据库也就是说演绎数据库用关系模型（表达事实）和datalog模型（表达规则）来表达世界演绎功能+关系数据库=演绎数据库 演绎推理：假言推理（形式逻辑）P，PQ Q P、Q为事实 PQ 为规则演绎数据库通常包括外延数据库（EDB）和内涵数据库（IDB）。EDB是实关系，IDB是虚关系。从其功能不难发现，演绎数据库不仅包含实数据，还包括由逻辑关系组成的规则集及由规则形成的新数据虚数据。演绎演绎数据库数据库由三部分组成：由三部分组成：（1）传统数据库管理，由于演绎数据库建立在传统数据库之上，因此传统数据库是演绎数据库的基础。（2）具有对一阶谓词逻辑进行推理的演绎结构，这是演绎数据库全部功能特色所在，推理功能由此结构完成。（3）数据库与推理机构的接口，由于演绎结构是逻辑的，而数据库是非逻辑的，因此必须有一个接口实现物理上的连接。谓词逻辑谓词逻辑的合法表达式称为合式公式，它由原子公式、连接词和量词组成。原子公式：由谓词、括号和括号中的项组成办公地点关系办公地点关系刘凌401陈东华402张明亮318办公地点（刘凌、401）办公地点（陈东华、402）办公地点（张明亮、318）连接词：用来组合原子公式以形成较复杂的合式公式 合取：P Q，当P、Q皆为真时，才为真，否则为假；类似“AND”析取：P Q，当P、Q中皆为假时，则为假，否则为真；类似“OR”蕴涵：P=Q,只有P为真，Q为假时，蕴涵式为假，否则为真；类似“if P then Q”否定。例子：“张某送给屋里的每个人一件礼物”（y）IN(y,ROOM)HUMAN(y)=(x)GIVE(ZHANG,x,y)PRESENT(x)演绎数据库实例表表1 1 父子关系数据库父子关系数据库F F（f f，s 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)(body)、左边部分称为规则头规则头(head)(head)。What does:-mean?Assume we have a rule:Q:-PThen :-means,if P is true then Q is true实例：表示事实：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一致。查询归纳为两种情况：a.在关系数据库本身得到完整回答的查询b.由递归规则定义的查询（区别于一般关系数据库的关键功能）递归规则在数据库中的表示形式规则的外部形式是面向对象的，其着重强调规则的可理解性、方便性和表达能力，而规则的内部表示则是面向存储和推理的。演绎数据库的实现方法目前演绎数据库的实现方法有两种：一种是PROLOG语言实现；另一种是用现有的DBMS+RULE来实现。a.用PROLOG语言实现。由于PROLOG语言是一种基于证明论的语言，因此用它来实现从理论上是完全可行的。但由于PROLOG语言本身是一个逻辑程序设计语言，因此用它来有效地完整地表示一个演绎数据库还需进一步改造。b.用现有DBMS+RULE处理。DBMS部分往往选用目前已有的数据库管理系统，其中RULE部分需要完成推理与接口两部分功能。当用户查询演绎数据库时，如果涉及到的是实关系，则如同通常的数据库查询一样处理；如果涉及到虚关系，则由规则处理部分的演绎结构将其转换成对实关系的查询，最后通过MS的查询结构完成，将最终结果提交给用户。查询归纳为两种情况：a.在关系数据库本身得到完整回答的查询b.由递归规则定义的查询（区别于一般关系数据库的关键功能）以上两种查询由查询语言分析器进行判断，前者直接送SQL Server，后者将递归查询对应的规则模块号和查询目标及初始查询值推送推理及处理。查询过程图演绎数据库查询的特点a.支持复杂对象b.支持对存在变元和非确定性查询的处理在DDS系统中，采用了不同于其他系统的方法处理存在变元和非确定性查询c.长连接优化技术的支持演绎数据库实例“一个一个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 *FROM Components C2 WHERE C2.part=trike 演绎数据库、智能数据库和知识库的关系演绎数据库、智能数据库和知识库的关系 演绎数据库演绎数据库演绎推理加入数据库系统的功能中演绎推理加入数据库系统的功能中。智能数据库智能数据库在数据库系统中加入归纳推理，类比推理等或然性推在数据库系统中加入归纳推理，类比推理等或然性推理，或加入自然语言理解，语音识别等人工智能中更理，或加入自然语言理解，语音识别等人工智能中更多的多的技术技术。知识库知识库对知识的存储和管理，不同于数据库。对知识的存储和管理，不同于数据库。关系：这三者既有联系又有差别。共同点：三者都是人工智能与数据库的结合，都是以数据库为基础，吸取了人工智能的成功技术的成果。不同点：数据库与知识库是不同的概念，前者管理数据，后者管理知识。知识包含的内容远比数据丰富得多。知识至少包括了规则与数据两大部分。智能数据库不仅应用人工智能中的逻辑推理思想，而且还应用人工智能中自然语言理解、语言识别，图象、文字处理等多种方法与技术于数据库，以求得更多的功能、性能的改善与提高。因此，从某种意义讲，演绎数据库是智能数据库的一部分。演绎数据库的应用查询效率低下一直阻碍着演绎数据库的发展，至今尚未商品化的产品问世。生物信息(bioinformation)学中的演绎数据库（Deductive Database）或知识库(Knowledgebase)是指能对已有的生物大分子基本信息进行数据挖掘的数据库，它建立在基本数据库的数据基础之上。比较著名的演绎数据库（系统）有：KEGG（京都基因与基因组百科全书），里面包括代谢途径、生物系统功能等级、生物大分子互作等等信息，它可以从基因组及相关分子的信息预测细胞代谢过程与生物行为。Swiss-Prot，它是一个蛋白质序列数据库，在整合其他数据库信息的基础上以较低的冗余度实现对蛋白质的评注功能，如功能描述、结构域、翻译后修饰、变体等谢谢29
