（计算机应用技术专业论文）基于cml关系化存储的化学表达式知识库设计与实现.pdf

摘要 摘要 人类社会发展到现在已经进入到一个知识大爆炸的时代。为了应对知识的 迅速累计，将知识信息化成为了必然的趋势。信息化的一个重要的特征就是强 大的知识检索功能。在各种检索工具出现以后，人们在浩如烟海的知识面前不 再茫然无措。 本文以信息化在化学教育领域应用的案例一化学学习助手为出发点，阐述 了学习助手子系统一化学表达式知识库引擎设计和实现的重点和难点。化学知 识库引擎存储和管理了在化学教育中常见的知识信息，其中核心信息为方程式， 并提供知识检索功能。 x m l 在数据描述方面的诸多优点，知识库引擎选择了x m l 作为化学知识 的描述语言。但由于x m l 在检索方面的不足，已经有较多的研究将x m l 结构 模式( d t d ) 转化为关系模型，利用数据库成熟的技术进行检索。但由于d t d 的复杂性，不利于这种技术的广泛使用。x s d 是一种比d t d 简单的结构模式， 并且可以从x m l 内容逆向推导出x s d 结构。本文提出了一种基于x s d 的将 x m l 数据关系化映射到数据库中存储的方法，使得以x m l 作为数据描述、以 关系化数据库存储检索这种优势互补的模式更加容易的应用到各种系统中。 另一方面，化学中存在一类特殊的分子式结构信息，对这类信息的检索其 实是图的匹配问题。图的匹配本身是一个n p 完全问题，因而分子式的结构匹配 是知识库引擎实现的一个难点。本文提出了一种能够完全描述分子式结构的全 息特征字符串，使用这种特征字符串可以利用数据库的高效的查询技术来尽可 能的提高分子式结构匹配的效率。 关键字i 信息检索，x s d ，x m l 关系化，全息特征字符串，结构匹配 a b s t r a c t t h es o c i e t yh a se n t e r e di n t o a ne r ao fk n o w l e d g ee x p l o s i o n i n f o r m a t i o n t e c h n o l o g yh a sb e c o m e t h eu t i l i t yt od e a lw i t ht h ee x p l o s i o n o n ei m p o r t a n tf e a t u r eo t i i 讧i o m a t i o nt e c h n o l o g yi st h es t r o n gp o w e ro fi n f o r m a t i o nr e t r i e v a l t h i sp a p e rb a s e do nt h ec h e m i c a ls t u d ya s s i s t e r ( c s a ) 一o n ec a s e o ft h e a p p l i c a t i o no fc o m p u t e rt e c h n o l o g yi nc h e m i c a le d u c a t i o n t h ec h e m i c a lk n o w l e d g e b a s ei sas u b s y s t e mo ft h ec s a ，w h i c hs t o r e sa n dm a n a g e st h ec o m m o nc h e m l c a l i n f o 皿a t i o no fc h e m i c a le d u c a t i o na n ds u p p o r t sv a r i o u sk i n d s o fi n f o r m a t i o nr e t r i e v a l t h i sp a p e rd e s c r i b e dt h ei m p o r t a n c ea n dd i f f i c u l t yo ft h ei m p l e m e n t a t i o no ft h e c h e m i c a lk n o w l e d g eb a s e t h ek n o w l e d g eb a s ec h o o s e sx m l t od e s c r i b et h ec h e m i c a li n f o r m a t i o n b u tt h e w e a l ( n e s so fx m l t h ed a t ar e t r i e v a l i sa l s on o t a b l e t h e r eh a v eb e e ns o m e r e s e a r c h e so nc o n v e r t i n gt h ex m l ss t r u c t u r a lp a t t e r ni n t ot h er e l a t i o n a lp a t t e mb y d t d b u tt h i st e c l l n o l o g yc a nn o tb ef u l l ya p p l i e db e c a u s eo ft h ec o m p l e x i t yo f t h e d t d t h i sp a p e rp r o p o s e dam e t h o do fc o n v e r t i n gx m l d a t ai n t or e l a t i o n a ld a t a u s i n gx s d t h i sc a nm a k e t h ep a t t e mo f ”d e s c r i b i n gi nx m l ，s t o r i n ga n dr e t r i e v i n g i nd a t a b a s e ”m o r ee a s i l yt od e p l o y e dt ok i n d so fa p p l i c a t i o ns y s t e m t h es p e c i a lm o l e c u l a rs t r u c t u r a li n f o r m a t i o ne x i s t si nc h e m i s t r y t h er e t r i e v a l o f m e 曲m c t u r a li n f b f m a t i o ni sag r a p hm a t c h i n gp r o b l e mw h i c hi s an p _ c o m p l e t e p r o b l e m s o t h e m a t c h i n g o fm o l e c u l a r s t r u c t u r ei sd i f f i c u l tp o i n t o ft h e i m p l e m e n t a t i o n t h i sp a p e rp r o p o s e dt h eh o l o g r a p h i cf e a t u r eo f t h eg r a p hw h i c hc a n f u l l yd e s c r i b et h es t r u c t u r a li n f o r m a t i o no ft h eg r a p h u s i n gt h eh o l o g r a p h i c f e a t u r e c a nd r a wo nt h em a t u r eq u e r yt e c h n o l o g yo fd a t a b a s et oe f f e c t i v e l yi m p r o v et h e p e r f o r m a n c eo ft h e s t r u c t u r a li n f o r m a t i o nr e t r i e v a l k e yw o r d s ： i n f o r m a t i o nr e t r i e v a l ，r e l a t i o n a lm o d e lc o n v e r s i o n ，h o l o g r a p h i c f e a t u r e ， s t r u c t u r em a t c h i n g 内容目录 图目录 图2 1 化学知识库的六项功能9 图2 2 描述化学方程式的c m l 片段1 0 图2 3 有机分子式结构示例一1 1 图2 4 描述分子式结构的c m l ( 部分) 1 1 图2 5c m l 的x s d 定义1 3 图2 6x s d 所描述的c m l 结构示意图1 4 图2 7 子结构匹配的模式结构1 7 图2 8 子结构匹配的目标结构1 7 图2 9 相邻原子同符号、不对称的结构2 1 图2 1 0 全息特征字符串生成时的队列变化示意图2 3 图2 11 模式结构和目标结构2 5 图2 1 2 模式特征字符串和目标特征字符串2 5 图2 1 3 通过全息特征字符串还原出的结构2 6 图3 1 化学知识库引擎的整体架构2 7 图3 2x s d 规则抽取流程图31 图3 3 由x s d 规则描述创建表的结构流程图3 3 图3 4 根据x s d 结构提取x m l 数据的流程图3 4 图3 5 全息特征字符串生成准备工作流程图一3 8 图3 6 全息特征字符串的生成流程图3 9 图3 7 分子式结构查询流程图4 0 图3 8 子结构匹配流程图一4 1 图3 9 子结构匹配流程图二4 3 图4 1 子结构匹配中的一种特殊情况4 6 图4 2 结构完全匹配评测结果一4 7 v 内容目录 图4 3 较复杂的分子式结构4 8 图4 4 子结构匹配评测官能团集，4 8 v i 内容目录 表目录 表2 1 根据x s d 映射的表的结构1 5 表2 2 特征字符串的生产过程18 表2 3 图2 3 所示分子式所有特征字符串列表1 9 表2 4 含有通配符的特征字符串列表一2 0 表2 5 图2 9 所示分子式的所有特征字符串列表2 1 表3 1 系统模块功能列表2 8 表3 2x s d 关系化的重要的数据结构3 0 表3 3 全息特征字符串生成、匹配所需的关键数据结构3 6 表4 1 知识库中的样本类型和数量4 5 表4 2 两种c m l 存储方式的查询时间比较4 6 表4 3 子结构查询时间统计5 0 i 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：豫v 溯彩 沙7 年z 月；日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签学位论文作者签 名：名： 解密时年月 日 间： 各密级的最长保密年限及书写格式规定如下： 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、己公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均己在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名：话埙彬 沙年月多日 第一章前言 第一章前言 第一节研究背景 从第一台计算机问世以来，计算机硬件技术就按照摩尔定律飞速发展着。 硬件技术发展到了今天，虽然受到经典物理学的限制晶体管的集成度已经接近 极限，但是随着体系结构的改良，并行计算等技术的发展，计算机硬件技术的 发展的脚步依然稳健，摩尔定律并没有退出历史舞台。在人们追求速度与容量 的同时，人们也追求着各种便捷性，如移动技术、各种人机交互技术也成为了 研究的热点。不过与之相应的计算机技术的应用发展之快更是令人咋舌。计算 机应用技术正加速渗透到人们生活的每一个领域，信息化成为了不可阻挡的历 史潮流。计算机应用到教育领域已经有几十年的历史，但新兴的移动计算技术 在教育领域的应用并不多见，而其在化学领域的应用更是处于原始状态。 将移动计算应用于教学中，最显著的特征就是教学方式的改变，能使得老 师和学生不再仅仅局限于传统的计算机教室，而是在更多的场合中收益。移动 计算实现了在任何时候、任何地点都可以利用计算机进行教学。移动教学存在 的瓶颈是在一个移动环境中用户与计算机间的交互效率。在移动的环境下使用 传统的鼠标和键盘相当的不变，笔式交互为移动计算有效的解决了这个问题。 平板电脑是一种结构小巧、高性能的移动式计算机。它填充了个人电脑和笔记 本之间的鸿沟，改变了学生和老师之间的交互方式。这项新的技术使得老师和 学生可以使用数字墨水和画图工具随意地书写、画画、标注，随时共享思想、 相互交流，具有改变教学过程的极大潜力。 在此背景下，为了支持移动计算方面的技术创新和应用创新，促进相关研 究社区的形成，鼓励相互交流和成果分享，微软亚洲研究院于2 0 0 6 年1 1 月推出 “教育中的移动计算 主题研究支持计划。希望通过该计划，推动移动计算在 教育方面的应用，促进教育革新方面的探索，进一步推动教育创新。 本文讨论的化学知识库引擎为南开大学机器智能所“化学学习助手”课题 的一个子系统。化学学习助手( c h e m i c a ls t u d ya s s i s t o r ，c s a ) 成功获得了微软 “教育中的移动计算 项目资助，是移动、人机交互等新技术在化学教育领域 的创新应用。c s a 课题组致力于t a b l e tp c 平台上手写化学公式的识别与应用研 究。对于一个帮助系统而言，该系统必然需要维护某个特定领域的相关知识和 1 第一章前言 信息，并提供添加、删除、修改等操作的支持。化学知识库引擎正是根据这个 需要从系统中独立出来的一个子系统。 化学学习助手有以下几个特点和实现目标： 完全的手写笔操作。使用手写笔可以完成所有的人机交互操作，提供了 一整套完整的预定义的手势，用户通过简单的手势就可以完成各种命令 的输入。如今的教育p p t 已经很大程度上代替了传统的黑板和粉笔。但 使用p p t 教学很多时候却不如传统的方式效果好。c s a 的目标就是结 合传统手写教学和电子化教学的优势，提高老师的教学效率和学生的学 习效果。 相关信息查询。任何一个好的帮助系统都会提供完整的信息关联网络， 一般都是以交叉引用的形式提供的导航。c s a 也提供了这样一个导航网 络。如我们在浏览某个分子式的信息的同时，可以提供这样的导航：所 有含有该分子式的化学方程式，该分子式包含的离子或官能团；浏览某 个方程式信息的时候可以提供的导航有：浏览该方程式的某个分子式的 详细信息。 分子式结构查询。以文本作为查询条件的查询方式在现有的检索系统中 占有绝对的统治地位，但也有极大的局限性。以分子式结构作为查询条 件，可以实现如查询含有某个分子式的文章，所有含有某个子结构( 官 能团) 的分子式等，这些查询使用文本作为关键字都难以描述，而且查 询的结果的相关性也不高。 c s a 的相关研究具有开拓性和创新性，在化学的教学、文献检索、互联网 数据集成等领域有着广泛的应用前景。 第二节相关工作 1 - 2 - 1x m l 与关系型数据库 任何一个应用系统都离不开数据。传统的数据描述与存储形式多种多样。 以w i n d o w s 系统为例，应用程序有三种存储数据的方式，本地文件、注册表、 数据库。随着互联网的发展，在异构的平台间交互数据的需求越来越迫切。而 传统的应用程序的数据存储方式因为其与应用程序和操作系统平台的耦合性都 不利于数据的交互与传输。在这样的背景下，w o r l dw i d ew e bc o n s o r t i u m ( w 3 c ) 2 第一章前言 的x m l 工作组定义在1 9 9 8 年发布了x m l l 0 。x m l 是i n t e r n e t 环境中跨平台 的，依赖于内容的技术，是当前处理结构化文档信息的有力工具。扩展标记语 言x m l 是一种简单的数据存储语言，使用一系列简单的标记描述数据，而这些 标记可以用方便的方式建立，极其简单易于掌握和使用。 x m l 是由s g m l ( t h es t a n d a r dg e n e r a l i z e dm a r k u pl a n g u a g e ) 简化而来的。 s g m l 是1 9 8 6 年出版发布的一个信息管理方面的国际标准( i s o8 8 7 9 ) 。该标准 定义独立于平台和应用的文本文档的格式、索引和链接信息，为用户提供一种 类似于语法的机制，用来定义文档的结构和指示文档结构的标签。但是s g m l 是一种非常严谨的文件描述法，导致过于庞大复杂( 标准手册就有5 0 0 多页) ， 难以理解和学习，进而影响其推广与应用。并且其语法具有随意性，使得程序 员对s g m l 的解析大费脑筋。 x m l 的特点是：语法简单、自描述、可扩展，支持文档内容验证，易于阅 读和编写。由于以上优点，使x m l 很快成为数据交换的唯一公共语言。 虽然x m l 的应用越来越广泛，也成为了数据交换的唯一公共语言，但在数 据的存储与检索领域，关系型数据库的地位仍然不可动摇。关系型数据库经历 了几十年的发展，技术已经相当的成熟，其主要优点是： 成熟、优化的查询检索技术。尽管在查询时有时需要进行表的连接，甚 至有时需要进行笛卡尔积运算，但数据库能够优化查询请求，将最复杂 的操作推迟到最后进行，从而减少数据的操作量，提高查询效率。 使用方便。不管是使用s q l 语句还是通过u i 操作，数据库的操作都是 简单易行的。 数据安全、并发控制。在维护数据的基础之上，还提供了权限管理、并 发控制等机制，使用起来不仅效率高，而且安全。 可移植性高。关系型数据库已经经历了半个世纪的发展，s q l 语句已经 标准化，便于系统的维护和移植。 由于x m l 的简单、通用性与关系型数据库的存储、查询的高效性，如果在 一个应用系统中使用x m l 来描述与交互数据，使用关系型数据库来存储和查询 数据，就能够充分的利用两者的有点，使得应用系统具有良好的通用性、可扩 展性、移植性，并同时拥有高效的存储和查询效率。但这种结合并不是两项功 能简单的叠加，需要将半结构化的x m l 数据转换为结构化的关系型数据，这方 面已经有较多的相关研究工作 1 5 】 16 】【1 7 】 1 8 】 1 9 】。 3 第一章前言 1 2 2 信息检索与x m l 检索 自从人类文明诞生以来，人类的知识和信息就不断的累积。有了知识和信 息，就必然出现了信息检索的问题。因此信息检索已经有了上千年的历史。索 引是最古老的信息检索技术。每本书有目录，有些书籍还在最后附有关键字的 索引；每个图书馆对其收藏的图书也有索引，以便于读者迅速找到需要的图书。 计算机在信息检索领域有着无可比拟的优势：快速而精确。如今，在计算 机的世界中，信息检索无处不在：各种单机应用程序几乎都提供了搜索功能。 在互联网领域搜索更是应用广发，通用的搜索引擎有g o o g l e 、b a i d u ，绝大多数 网站也提供了站内搜索功能。在这众多的搜索领域里面，虽然有的是全文搜索， 有的使用了各种索引技术如倒排索引，但是他们都有一个共同的本质，即基于 文本关键字的搜索，这一类搜索的输入都是文本。还有一些搜索可以有其它的 输入形式，如语音、视屏等，由于其技术实现上复杂性，应用还远远不如传统 的文本搜索广泛。文本搜索虽然简单，但表达形式单一，在一些特殊的领域里 远远不能满足用户的检索需求，因此多种检索形式的研究已成为计算机领域研 究热点之一。 虽然x m l 具有众多的优点，但x m l 的查询检索实现比较复杂繁琐，并且 效率较低，这是所有的x m l 文档的通病。由于x m l 的使用广泛，解决其检索 效率低成为了一个热点问题。欧洲d e l o sn e t w o r ko fe x c e l l e n c ef o rd i g i t a l l i b r a r i e s 与i e e ec o m p u t e rs o c i e t y 于2 0 0 2 年共同启动i n i t i a t i v eo fe v a l u a t i o nf o r x m lr e t r i e v a l 创新活动，旨在评估各种x m l 检索方法，同时为研究者提供一 个展示自己成果的空间。 x m l 文档的查询检索优化主要有两个方面：a ，使用x m l 专用的检索引擎， 研究集中在优化检索引擎和建立索引上 2 】 3 】 4 】【5 】 6 】。b ，前文已经提到过，考虑到 数据库的成熟技术及在查询检索上的优势，将x m l 文档存储到数据库中以进行 检索。 1 _ 2 - 3 分子式结构与图的匹配 化学知识库引擎提供一类特殊的检索一分子式结构检索。分子式结构不同 于一般的化学信息，在有机化学中分子式结构是相当复杂的。分子式结构可以 看做是一个图。图的匹配是一个古老而复杂的话题。说其古老，是因为图是计 算机中一个相当重要的数据结构，关于图和图的匹配的研究很早就有了。说其 复杂，是因为图本身是一个复杂的数据结构，任意两个图的匹配是一个n p 完全 4 第一章前言 问题，无法在最坏情形下找到一个多项式算法。但如果对图的结构或者对匹配 的形式做一些限制，则有可能存在多项式时间算法，如： 文献【2 7 】中讨论了如果图在一定的限制框架以内的四种匹配算法，以此为 基础提出了一种新的匹配算法江+ ，并给出了此算法在已访问节点方 面更优的形式证明。 文献 2 8 】提出一种新的方法来表达和解决子图匹配问题。通过将算法和具 体的图的模型的分离，此算法可以解决多种图的模型的匹配问题。并提 出了一种查询概念作为具体问题的抽象。 文献 2 9 】提出了一种线性时间算法，可以判断某个图是否存在一个最简单 的环一三角形。文中还给出了此类问题若干算法的优化。 文献【3 0 】提出了一种多项式时间o ( 铲5 ) 算法，但此算法适用的范围很小， 仅适用于树的匹配问题。 文献【3 1 】提出了一种线性时间算法，要求子图大小为常数。此算法使用了 一种分割技术，将图划分为若干子图，并在每个子图上使用动态规划。 可见，每种特定的图的匹配算法都有一定的限制框架，如果对两个图不做 任何限制，目前为止还没有找到一个多项式时间的匹配算法。化学中的分子式 可以看作是一类特殊的图，特别是初、高中教育领域内的分子中原子数目不会 太多( 1 0 0 以内) ，并且由于化学键的限制也不会存在两两原子都有化学键连接 这种最坏情形，这为设计一种分子式结构匹配算法提供了可能。 第三节化学表达式知识库引擎简介 作为化学学习助手的子系统，化学表达式知识库引擎存储和管理了所有的 知识信息。为了描述的简便起见，后面将化学表达式知识库简称为化学知识库。 在知识库引擎的设计时考虑了以下一些问题： 选择x m l 作为化学知识的描述语言。系统的可扩展性和可移植性是设 计优劣的指标之一，使用标准化的x m l 能够是系统具有良好的可扩展 性和可移植性。x m l 在其标准化不久就应用到化学领域，产生了一门 特殊的标记语言c h e m i c a lm a r k u pl a n g u a g e ( c m l ) 。在化学相关的应 用系统中使用c m l 已经成为了一种惯例。c m l 是x m l 在化学领域中 的应用，其本质还是x m l 。在后文中，如果讨论的是和知识库引擎相 5 第一章前言 关，使用c m l ，如果讨论的是一些通用算法，则使用x m l 。 选择数据库存储底层数据。因为数据库的开发的便捷性、查询的高效性、 管理的安全性，和绝大多数应用系统一样，我们选择数据库作为底层数 据的存储和管理者。 在数据的描述形式和存储形式确定下来之后还需要考虑一下几个问题，这 几个问题也是知识库引擎实现时的重点和难点问题： 数据库如何存储x m l 。在x m l 刚出现的时候将x m l 数据存入数据库 中只能以字符串的形式存储，即在数据库看来，x m l 数据和一般的文 本信息没有任何的区别。随着x m l 的标准化，各大数据库供应商也很 快的提供了对x m l 数据类型的支持。传统的关系型数据库，如d b 2 ， s q l s e r v e r 等，都在其新版本中加入了x m l 字段。凡是存入这个字段的 数据必须符合x m l 的格式规范。并且在对这个字段进行检索时，需要 使用x q u e r y e 9 】与x p a t h 1 0 】进行查询。虽然这些数据库提供了对x m l 数 据类型的支持，但是由于对x m l 数据类型的解析本身就是一个效率不 高的操作，数据库对传统的s q l 语句的查询效率比x q u e r y 的查询效率 要高得多。已经有相关的研究如何将x m l 数据映射到关系数据库存储 1 5 】 1 6 】【1 7 】【1 8 】【1 9 】。考虑到提高知识库引擎的查询检索效率，在实际实现中 选择则将x m l 数据映射到关系数据库存储。 化学知识的检索。由于使用了关系数据库存储数据，并且在将c m l 数 据存储到数据库之前已经将其关系化，我们检索的对象就是传统的关系 型数据。对于常见的化学信息查询，如含有特定原子的物质，含有特定 物质的方程式，原子的属性，物质的属性，离子列表，官能团列表等， 都只需要简单的s q l 语句就能做到。对于有机物中的分子式，由于存 在原子之间的键的关联，可以将分子式结构描述为一个图的结构。一般 的s q l 语句已经不能支持这类检索，因为s q l 语句无法描述一个分子 式的结构。最直观的解决方案是每次查询时获取到所有的数据库中的分 子式结构，再选用图匹配算法选出所有的结果。显然这是一种效率极低 的解决方案。本文提出了一种图的特征字符串，可以将图的所有的结构 信息以一个字符串的形式描述出来。这种能够描述图的所有的结构信息 的字符串称之为全息特征字符串。将全息特征字符串代替图的结构存储 到数据库中可以方便的进行检索。利用数据库提供的通配符“”，可 6 第一章前言 以从数据库中选出一个和查询子结构匹配的超集，再通过对超集进行一 步简单的验证就可以实现子图匹配的功能。 第四节本文组织结构 本文内容共分为五章，组织结构如下： 第一章为前言，主要讲述化学知识库的应用背景，所需要使用的各种技术， 包括x m l 、关系型数据库、图的匹配( 包括完全匹配和子图匹配) 。以数据库作 为底层数据的存储和管理者，需要解决两个问题：x m l 到关系型数据库的转化 和关系型数据库中图的匹配的解决方案一特征字符串。 第二章讲述知识库的设计。提出了通过x s d 将x m l 文件关系化到数据库 的算法和通过全息特征字符串实现关系型数据库进行图的匹配的算法。 第三章为知识库实现的关键技术。详细描述了x m l 文件关系化和特征字符 串的生成和匹配的流程。 第四章为知识库的评估。主要对x m l 关系化后效率的提升和特征字符串匹 配的精确度和效率进行评估。 第五章为总结与展望，总结了知识库实现中可以进一步优化的改进的地方， 指出了结构查询在化学领域的应用前景，展望了将特征字符串改进后可以作为 一种通用的图的匹配算法的可行性。 7 第二章化学知识库引擎的分析与设计 第二章化学知识库引擎的分析与设计 第一节知识库引擎的整体功能分析 化学知识库引擎的功能从总体上来说就是存储系统所需的所有的化学知 识，并且提供知识的管理与查询。我们将知识库的功能分为三类，即添加、维 护( 删除、修改) 、查询。我们再将化学知识分为两类，即一般的化学信息和分 子式结构信息。分子式的结构信息虽然也是用x m l 描述的，也可以同其他化学 信息一样关系化到数据库中存储，但这样会导致分子式结构查询的难以实现和 低效。因为分子式结构信息的特殊性，知识库的每一类功能都对一般的化学信 息和分子式结构信息分别处理，因此知识库引擎实际提供了6 类功能，如图2 1 所示。下面对这6 类功能做一个简要的分析。 1 一般化学信息的添加。用x m l 描述的一般的化学信息需要映射到关系 化数据库存储。x m l 映射到关系型数据库有两种方案：选择d t d 1 】或 者x s d 1 1 】 1 2 】 13 1 ，因为x s d 比较简单，不需要规则的简化，在实际的实 现中选择了x s d 。将x m l 数据映射到数据库存储可以极大的提高查询 效率，是化学知识库的重要组成部分。 2 分子式结构信息的添加。为了在数据库中实现分子式的结构匹配功能， 需要将分子式的特征字符串代替一般的结构描述存储到数据库中。特征 字符串本质上是一种特殊的广度优先遍历结果，但能够以简单的字符串 形式完整的描述分子式的结构信息，使用特征字符串能够很好的利用数 据库的查询优势，简单而高效的解决了分子式结构查询这个难题。 3 一般化学信息的维护。这里有两种解决方案：常见的做法是对每一类需 要维护的信息设计一个维护接口，这样的做法比比较简单，但是工作量 会随着信息类别数量的增多而增加，不具有通用性。另外一种方案就是 将关系化到数据库中的数据库全部或者部分的还原为x m l 数据，维护 操作的对象为x m l 数据，当操作完成之后再更新到数据库中。这种方 案只需要实现通过d t d 或者x s d 反关系化关系型数据为x m l 数据， 另外再提供一个通用的x m l 编辑器即可。此方案通用性好，并且工作 量不随信息类别数量的变化而变化，可维护性好，但是由于时间的关系， 还未能实现这部分的功能。 8 4 分子式结构信息的维护。这类信息在数据库只涉及一张单独的表，所需 要的特征字符串生成的功能也与分子式结构信息的添加相同。此功能实 现比较简单，不做过多的说明。 5 ：一般化学信息的查询。与大多数数据库应用程序类似，使用s q l 查询语 句即可完成此功能。实现比较简单，不是知识库的重点内容。 6 分子式结构的查询。分子式的结构信息是以特征字符串的形式存储到数 据库中的。分子式的结构查询有两种形式：结构的完全匹配查询。此类 查询不需要最后的验证，实现较简单。子结构匹配查询。在数据库查询 结果的基础上还需要进行结果的验证，即特征字符串的比对。分子式的 特征字符串的生成、查询、验证是知识库的核心组成部分，也是本文创 新点之一。 厂一厂一般化学信息一絮蒜嚣数 f知识添加 i l 分子式结构信息 一分嚣字 ， 一般化学信息+叫 关系型数据还原 f 3 、) 触矧叫觥籼t 一息一燃否 l 分子式结构信息 一 蟹! 苎h ! 廿u r ， 一般化学信息 一一一般咚祭查询 l 知识查询 x s d 比d t d 容易解析。d t d 有着复杂的语法结构，解析d t d 文档本 身就需要相当的工作量。因为x s d 本身就是x m l 文件，对于x m l 文 件的解析有着大量成熟、优化的解析器，因此只需要很简单的编码即可。 x s d 的编写比d t d 简单。不需要掌握d t d 的语法，仅需要掌握x m l 的语法即可编写x s d 。由于x s d 的简单性，从x m l 数据文件逆向推 导出x s d 文件也比较容易，并且已经有工具实现了此功能。在只有x m l 数据文件存在的情况下，将极大的提高开发效率。 由于x s d 有着广泛的应用前景，而将x m l 数据映射到数据库存储的研究 主要集中在d t d 的使用上，因此研究如何利用x s d 关系化数据也是对这个领 域的充实，具有一定的科研意义。 基于以上因素，在知识库的实现中使用x s d 进行关系化的转换。 2 2 - 3x s d 的关系化算法 图2 2 展示了如何使用c m l 描述方程式。因为方程式都遵循一定的基本形 式，因而描述方程式的c m l 也有一定的规律可循，这种规律就是c m l 的结构。 前面提到过结构的定义可以使用d t d 或者x s d ，如图2 5 所示就是描述方程式 的c m l 的x s d 定义。由于篇幅的限制隐藏了部分x s d 定义，在图中以 一表 示隐藏的定义。由于x m l 具有极强的可读性，与方程式的c m l 描述对应起来 看，可以很容易读懂x s d 所表达的意义。如果需要对x s d 作深入的了解可以 参考w 3 c 的标准文献n u 【1 2 】【1 3 】。 1 2 第二章化学知识库引擎的分析与设计 z s ：e l e m e n tn a m e = r c a c t a n t l i s t 翌j | ：1 x s ：e i e m e n tn a 噩e = c o n d i t i o n l i s t 。) 一。i 。 i - l x s ：a tt r i b u ten a , , l t e = r e a c tio n b a la n c e 。t y p e = x s ：u n sig n e d e y te u se = r e q u i r e d m x s ：a t t r i b u t en a m e = 。r e a c t i o n t y p e 2 t 即e = x s ：u n s i g n e d b y t c u s e = r e q u i r e d 尽可能多的将一个元素的子孙( 包括属性、子元素和子元素属性) 转换 到一个单独的表中，这样可以产生尽可能少的表。 当一个元素的某个子元素可能多次出现的时候，则此子元素及其子孙元 第二章化学知识库引擎的分析与设计 素需要单独映射到一个新的表中，这样可以避免产生数据冗余。 0 r e a c t i o n b a l a n c e ：i n o r g a n i c ： r e a c t i o n ( 1 )卜r e a c t i o n t y p e1jr e a c t i o n t y p e2 ： 。1 r e a c t i o n f o r m u l a 7 7。 r e a c t a n t l i s t ( 1 。1 ) | | 叫c o u n tip r o d u c t l i s t ( 1 ，1 ) i 叫c o u n t 、 、 lir e a c t a n t ( 1 ，) |l p r o d u c t ( 1 。】 l l，”、 、 k i 1 m o l e c u l e ( 1 ，1 ) j m o l e c u l e ( 1 ，1 ) ： 、 一t c o e f f i c i e n t ；s t a t e r e f l c o e f f i c i e n tjs t a t e i r e f l 图2 6x s d 所描述的c m l 结构示意图 在x m l 文件中除了根元素以外的所有元素都可以出现任意多次，因此进行 共享转换时其实是一个递归转换的过程。这个递归的过程描述如下： 将当前元素的每个属性作为一个字段加入到当前表的结构中。 对每个子元素做如下操作：如果此子元素可以出现任意多次，则以此元 素为表名新建一个表，并将此表作为当前表进行递归；如果此子元素只 能出现一次，则直接进行递归即可。 可以看出，如果一个元素可以出现任意多次，则此元素就是建立新表的标 志。以图2 6 所示的结构为例。图中的r e a c t i o n 、r e a c t a n t 、p r o d u c t 都可以出现任 意多次，这三个元素将图中的结构划分为4 个部分，每个部分分别映射到一张 表，并通过表之间的外键关系维持原有的结构信息。这种起到划分表的作用的 关键元素称为表的根元素，表的根元素名即为映射的表名。表的外键指示了表 之间的父子关系，如表c a s d o c u m e n t 为表r e a c t i o n 的父表，r e a