（计算数学专业论文）xml数据管理中的关键问题研究.pdf

摘要 摘要 x m l 的出现给数据库领域带来了很多新的问题，其中最关键的问题是如何准确有效 的存储x m l 数据及如何将有用的信息以x m l 文档形式发布到i n t e r n e t 上。本文在对国 内外研究现状进行综合分析的基础上，从一个全新的角度对x m l 数据的存储与发布问 题进行了研究，以得了以下成果： 1 提出了一种d t d 到e r 模型的转换方法，即d t d ，e r 方法，然后从数据库设计 的角度出发，提出了基于d t d e r 方法的x m l 数据存储技术来完成用关系数据库存储 x m l 数据。该技术弥补了当前研究中只考虑如何存储而不考虑后期的数据处理的不足， 从而为基于x m l 的研究打下了基础。 2 提出了一种e - r 模型到d t d 的转换方法，即e r d t d 方法，然后从数据库设计 的角度出发，提出了基于e r d t d 方法的x m l 数据发布技术，使得x m l 数据发布与 数据库设计同步完成。从而避免了当前方法中为了数据发布对数据库进行的二次开发。 3 本文从图论的角度出发，给出了两类关系数据库的x m l 视图的生成技术，一类 是在数据库设计的同时完成x m l 视图的创建，另一类是为已经存在的关系数据库创建 x m l 视图。同叫本文对应于这两类技术给出了具体的实现算法，并给出了算法分析。从 而为基于x m l 数据的发布与集成奠定了基础。 4 本文对基于双视图的发布集成系统模型进行了研究，给出了模型的体系结构， 并分析了各个模块的具体功能，从而为以后的工作打下了基础。 关键词x m l ；d t d ；数据存储：数据发布；视图：数据集成；有向图 a b s t r a c t w i t hx m l e m e r g i n g ，m a n yn e wi s s u e s a r eb r o u g h tt ot h ed a t a b a s ea r e a ，a n dh o wx m l d a t ai ss t o r e de f f e c t i v e l ya n dp r e c i s e l ya n dh o wt op u b l i s ht h ei n f o r m a t i o nt oi n t e r n e ta s x m ld o c u m e n t sa r ev e r yi m p o r t a n t i nt h i sp a p e r ，b a s e do na n a l y z i n ga n di n t e g r a t i n gt h e a c t u a l i t y o ft h e t e c h n o l o g ya n dt h et r e n di n i n t e r n a la n de x t e r n a l ，p r o b l e m so fs t o r i n ga n d p u b l i s h i n gx m l d a t aa r es t u d i e df r o man e w p o i n to fv i e w , a n dt h et o l l o w i n gt i n d i n g sa r e 博士亓研究1 ：作报告 o b t a i n e d 1am e t h o dt h a tc o n v e r t i n gd t d i n t oe rm o d e l ，i e t h ed t d e rm e t h o di sp r o p o s e d ， t h e nf r o mt h ed a t a b a s e d e s i g np o i n to fv i e w , t h et e c h n o l o g yo fs t o r i n gx m l d a t ab a s e do n t h ed t d e rm e t h o dt oc o m p l e t et os t o r i n gx m l d a t ai nr e l a t i o n a ld a t a b a s ei s p r o p o s e d t h et e c h n o l o g ym a d eu pt h ed e f i c i e n c yt h a tt h ee x i s t i n gm e t h o d so n l yc o n s i d e r e dt h es t o r a g e ， n o tt h ed a t ap r o c e s s i n gs oi tf o u n dt h eb a s ef o rt h er e s e a r c hb a s e d o nx m l 2am e t h o dt h a tc o n v e r t i n ge - rm o d e li n t od t d ，i e t h ee r d t dm e t h o di sp r o p o s e d ， t h e nf r o mt h ed a t a b a s e d e s i g np o i n to fv i e w , t h et e c h n o l o g y o fp u b l i s h i n gx m ld a t ai s p r o p o s e d s ow ec a nc o m p l e t et od e s i g nt h ed a t a b a s ea n d t op u b l i s hx m ld a t ai nt h es k r n e t i m e ，a n da v o i dt h es e c o n d a r yw o r k f o rt h ed a t a b a s et op u b l i s ht h ed a t a 3 f r o mt h eg r a p ht h e o r yp o i n to fv i e w s ，t w ok i n d so ft e c h n o l o g yo fc r e a t i n gx m l v i e w s a r ep r o p o s e do n ei sc r e a t i n gt h ex m l v i e w sw h i l et h ed a t a b a s ei sd e s i g n e d ；t h eo t h e ri s c r e a t i n gt h ex m l v i e w so ft h ee x i s t i n gr e l a t i o n a ld a t a b a s e t h ea l g o r i t h m sc o r r e s p o n d i n g t o t w ok i n d so ft e c h n o l o g ya r ep r o p o s e da n da n a l y z e d s ot h e s et e c h n o l o g i e sf o u n dt h eb a s ef o r t h ed a t ai n t e g r a t i o na n dp u b l i s h i n g 4t h em o d e lo fi n t e g r a t i n g p u b l i s h i n gs y s t e mb a s e do nt h ed o u b l ev i e w si ss t u d i e d ，t h e a r c h i t e c t u r eo ft h em o d e li sp r o v i d e d ，a n dt h ef u n c t i o n so fe v e r ym o d u l ea r ea n a l y z e d i ti s t h ef o u n d a t i o no ft h ef u t u r ew o r k k e yw o r d sx m l ；d t d ；s t o r i n gd a t a ；p u b l i s h i n gd a t a ；v i e w s ；d a t ai n t e g r a t i o n ；d i r e c t e d g r a p h i i 第1 章绪论 1 1 研究背景 第1 章绪论 经过十几年的发展，互联网( i n t e r n e t ) 已经成为新经济时代的标志，它极大地影响了 人类的生活方式、商业模式，并将在新世纪继续对人类社会的进步起着巨大的推动作用。 据美国在线计算机图书中，i i , ( o c l c ) 的2 0 0 0 年度研究报告，全球的w e b 站点已有7 百万 个。根据c y b e rd i a l o g u e 、b e r r i e r a s s o c i a t e s 等机构的统计，美国积极参与互联网的用户 为7 6 0 0 力，加上通过共享设施访问互联网的人数共有1 3 亿，占总人口的一半。就我国 而言，据中国互联网络信息中一l , ( c n n i c ) 酏j2 0 0 0 年统计数据表明：到2 0 0 0 年1 2 月3 1 n 为l ，我国的站点数目为2 6 万个，上网计算机数目为9 0 0 万台，上网用户总人数已达 2 2 5 0 万，这些数据都比1 9 9 9 年翻了一番多。与1 9 9 7 年相比，三年间翻了4 0 倍。作为互 联网最主要应用的w e b 正成为整个世界的窗口，它实现了全球用户和机构信息的共享。 i 】以预计，w e b 将作为人类社会的主要信息源、媒体和商务的门户，而互联网将作为信 息传播的介质和商务运作的基础平台。 同时，随着i n t c r n e t 的迅速发展，网站和静态h t m l ( 超文本标记语言) 页面也急剧膨 胀，到】9 9 9 年底，i n t e r n e t 上的静态页面有3 5 0 百万，同时每天以1 百万的速度增加， 信息的数量级从9 0 年代初的m b ( 1 0 6 ) 过渡到g b ( 1 0 9 ) 、现在已上升到t b ( 1 0 1 2 ) 。面对庞 大的信息海洋，人们却遇到了w e b 上存在的大问题：一是i n t e r n e t 速度极慢，有时犹如 爬行的蜗牛。二是虽然可以在线获得各种信息，但是找到所需要的信息常常极为困难。 其中虽然有硬件方面的原因，但是主要是由目前w e b 语言一h t m l 的性质引起的。尽 管i t m l 从发明以来，已成为最成功的电子发布语言，但是它仅注重信息的表现形式， 它的标已仪仅反映了信息应该如何在页面上表现，并没有对信息本身进行描述，并且它 的标已集合是固定的，不能够根据需要进行扩展。随着w e b 应用的同益广泛，它的局限 博士后研究： 作报告 性越来越明显，不适应作为i n t e r n e t 上信息交换和表示的工具。 1 9 9 6 年，万维网协会( 或者叫w 3 c ，h t t p ：w w w w 3 c o r g ) 开始设计一种可扩展的 标记语舌，使其能够：恪s g m l 的灵活性和强大功能与已经被广泛采用的h t m l 结合起 来。这种后来变成x m l 的语言继承了s g m l 的规范，而且实际上就是后者的一个子集。 从s g m l 入手使得该设计小组能够将精力集中在简化已有的结果上。s g m l 已经提供了 一种可以无限扩展的语言，它允许任何人能够根据自己的需要加以扩充。但是由于s g m l 有太多的可选功能，s g m l 变得过于复杂，以至于很难编写出针对这种语言的普通解释 器。在这种情况下，1 9 9 8 年2 月，万维网协会推出了x m l ( 可扩展的标记语言) ，将它 作为种互联网进行数据表示和交换的标准【1 1 。x m l 是一种既简单、灵活，又功能强大 的标记语言。它是s g m l ( 标准通用的标记语言) 的一个子集，它不仅继承了s g m l 的可 扩展性，同时保持了对现有的面向s g m l 的系统的向下兼容性，而且延续了h t m l 的 易用性。另外，用x m l 标记过的数据仍然可以在基于h t m l 的系统中使用。 x m l 从提出到现在只不过几年的时间，但它作为一种跨产品、跨界面、跨平台的互 联网的标准语言，己经显现出其强大的应用前景，并受到了政府、企业和各大软件厂商 的广泛关注。各个行业如金融机构、海关、媒体产业正制定各自行业的x m ld t d ( d o c u m e n tt y p ed e f i n i t i o n ，文档类型定义) f 2 1 , 以利于数据以公认的格式进行交换与 集成。随着x m ls c h e m a 的逐步成熟，人们开始设计各自的x m ls c h e m a ，同样也是为 了更好的进行数据的交换与集成。微软、s u n 、i b m 、网景、甲骨文等大厂商都推出了基 于x m l 的产品和解决方案，例如：微软推出了n e t 技术，声称到2 0 0 5 年全面支持x m l 。 在国外已经形成了x m l 的一系列标准的基础上，国内也开始给予x m l 极大的关注，例 如：中国科学院电子商务研究中心和联合国的大软件厂商制定了c n x m l 标准。总之， 对于x m l 的深入研究将有力的促进企业的信息化、电子商务以及电子政务的发展，因 此具有巨大的应用前景和经济效益。 2 第】章绪论 = = ；一一一 1 1 1x m l 简介 x m l 是一种界定文本数据的简便而标准的方法。它曾经被人们称作“w e b 上的a s c i i 码”。就好像程序员可以用自己喜欢的编程语言来创建任何一种数据结构，然后同其他人 在其他计算平台上使用的其他语言来共享一样。x m l 的标记用来说明所描述的概念，丽 属性则用柬控制它们的结构，因此人们可以定义自己所设汁出的语法与他人共享。x m l 数掘拙述机制意味着它将成为一种在i n t e r n e t 上共享信息的强大途径，主要有以下三条 原因： _ 它是开放的，x m 。能够在不同的用户和程序之间交换数据，而不考虑其平台如 何。 - 它白描述的特性使其对于b 2 b 和企业内部网解决方案来说是种有效地选择。 _ 无需事先协、调就可以在程序之间共享数据。 x m l 其有以下一些特性：x m l 具有自描述性( 元素的标记描述了信息) ；可扩展性： 首先，x m l 允许用户创建自己的d t d ( d o e u m e n tt y p ed e f i n i t i o n ，文档类型定义) ，从而 可以产生适合多种应用的“可扩展的”标记集。其次，使用几个附加的标准，用户还可 以对x m l 自身进行扩展，向核心的x m l 功能集增加样式、链接及参照能力，基于此特 点，x m l 可作为一个核心标准，可能为别的标准的产生提供坚实的基础：可分析性： h t m l 主要描述页面的显示形式，因此不能从h t m l 文档中理解所显示内容的实际含义。 而x m l 则提供了功能强大、灵活高效地表达数据内容的方法，而其数据内容与具体的 应用无关，使得用它表达的数据有很好的使用效率和可重用性；通过结合d t d 的分析， 人们可以理解x m l 文档中各个元素的含义，即x m l 文档具有自解释性。这些特点方便 了对网络数据的统计分析，也改变了我们搜索和组织信息的方式( 指需要通过分析标签就 可以找到真f 相关的信息) ；简单性：x m l 文档语法包括一个非常小的规则集，使得开 发者可以根掘它立刻开始工作。同时根据这种文档的结构，可以创建自己的d t d 以满 足自己的需要；x m l 的严格定义和规则集使人和机器都能很容易的阅读文档，根据它创 博士后研究工作报告 建x m l 的语法分析器电比较容易：开放性：x m l 标准自身在w e b 上是完全开放的；人 们可以对任伺一个文档进行语法分析，如果得到了相应的d t d ，还可以校验它。当然丌 发者可以以自己的方式进行加密，x m l 并不禁止创建自己私有的格式，但是它的开放性 是它最大的优点，所以加密者电将失去使用x m l 的不少好处。 1 1 2x m l 与h t m l 的比较 为了进一步的既明对x m l 进行研究的重要性，本文对h t m l 和x m l 进行了深入 的比较。h t m l 是符合s g m l 语法的一种固定格式的超文本标记语言，它是最早的应用 于网络信息、传输的置标语言，也是近几年网上最普及的一种网页制作通用语言，因其格 式固定，故难以扩展，它主要用于显示信息的内容，侧重于主页表现形式的描述，大大 丰富了主页的视觉和听觉效果，为推动w w w 的蓬勃发展、推动信息和知识的网上交流 发挥了不可取代的作用，但是它并没有反映出信息的结构，它自身的特点使它蕴藏了许 多危机，随着它不断发展，这些危机不但没有减弱，反而越来越突出，甚至已然成为h t m l 继续发展应用的障碍。h t m l 的主要局限性在于：h t m l 不允许对页面上的个别元素进 行语义性的标注，电无法重制资料结构的规格，例如，某种对资料库或物件层次的重要 资料；h t m l 只描述文件外貌，但无法涵盖任何实质内容，因此不适合用于明确的查询 方式；h t m l 无法延伸，因此无法根据特殊规格来定义自己的标签，也无法在文件内部 使用资料格式。它的标记集合电完全可以用x m l 来定义。x m l 与h t m l 都是用一对互 相匹配的标签来标i 己信息，但h t m l 描述的是数据的显示方式，现在网上通用的文档语 言是h t m l ，尽管这也是一个存储、显示数据的可行的办法，但是它的效率和能力却非 常有限，它至少存在以下三个严重的问题，首先，它的显示方式内嵌于数据之中，当数 据是用列表的形式来表示时，如果某个时候需要改用表格来表示这些数据，那么将不得 不重新编码所有的h 1 1 m l 文件：其次，在数据中寻找信息非常困难，需要编写一个脚本 程序：最后，数掘自身的逻辑不得不让位于h t m l 的语毒规范的逻辑。而x m l 则侧重 于描述数掘本身，它遵循严格的语法要求，并且便于不同系统间的信息传输，具有良好 4 第1 章绪论 的保值性，最重要的是，x m l 的标签集合不是固定的，x m l 不仅允许自定义一套标记， 而且这些标记不必仅限于对显示格式的描述。x m l 允许根据各种不同的规则来制定标 记，用户可以根据自己的需要定义任何一种标签来描述自己文档中的数据元素，将来的 发展趋势是x m i 。作为w e b 上的信启、表达和交换，而h t m l 作为在浏览器端显示的工具， 从x m l 到h t m l 的转换工具是x s l 。总之，x m l 的出现并不是为了取代h t m l ，而 是为了更好的在i n t e r n e t 上进行数据传输与交换。 1 2 国内外研究现状 自从1 9 9 8 年2 月万维j 捌协会推出了x m l1 0 标准后，基于x m l 以及相关领域的理 论研究受到了人们的极大关注。在这其中，x m l 数据的存储与发布技术是两个重点研究 问题。x m l 数据的存储问题可以被认为是整个基于x m l 研究的基础，因为只有合理有 效的存储x m l 数据，才能真正的发挥x m l 的巨大优势。x m l 提出的目的就是为了给 i n t e r n e t 上的数据交换提供一种标准，所以如何以x m l 数据形式发布现有的数据成为了 人们研究的重点i q 题。下面就x m l 数据存储与发布技术分别进行阐述。 1 2 1x m l 数据存储技术研究现状 x m l 有如此多优势和潜能，但它的发展需要一个长期的进化过程，所以为了充分发 挥x m l 的优势和潜能并加速它的发展，需要个可靠的技术来持续的存储管理x m l 数 掘。 在文献f 3 1 中，x m l 存储管理被定义为： _ 它是一个x m l 文档及其部分的集合，它被一个能够管理和控制这些文档集合信 息系统维持。 它不是一个单独的存储结构化和半结构化数据的仓库。它应当具有各种管理 x m l 数据的能力，像关系数据库一样。例如：数据的独立性、完整性、入口权限、冗余， 等等。 5 博士后研究工作报告 下面从不同的角度对x m l 数据的存储技术进行了分类阐述 第一类：x m ld b ：i n i t i a t i v e ( h t t p ：w w w x m l d b o r g ) 将基于x m l 的数据库分为三类 1 ) n a t i v ex m ld a t a b a s e 它专门为存储管理x m l 文档而设计。它存储了x m l 模 型的所有信息。数据以x m l 文档形式存进数据库，当用户需要数据时，n a t i v ex m l d a t a b a s e 仍然以文档形式输出。但它其本身不可能是一个单独的数据库形式存在。文献 4 x , j - 它作了具体的介绍。 2 1x m l e n a b l e dd a t a b a s e 它被设计是为了存储和取回以数据为中心的数据，同时 提供了其它数掘形式的接口，并包含了x m l 文档与其本身的数据传输。文献 5 简述了 它与n a t i v ex m ld a t a b a s e 的区别。 3 ) h y b r i dd a t a b a s e 从某种意义上讲它是n a t i v ex m ld a t a b a s e 和x m l e n a b l e d d a t a b a s e 的一种混合+ 它可以粗略看成是x m l 和其它数据的接口。 文献 5 ，6 ，7 根据这种分类方法介绍了当前存在的系统原形和商业产品。 第二类：基于现有数据库的存储技术的分类 1 1 基r 文件系统的存储管理技术。这种技术是将x m l 数据存储到文件系统中。 h t m l 的存储管理都是基于这种平面的文件系统。但x m l 和h t m l 有着很大的区别 x m l 是层次结构的，而h t m l 不是。一种方法是将x m l 数据以b l o b ( 二进制大对象) 的形式进行存储，然后在每一次使用时将它进行解析。由于反复的解析，破坏了x m l 的结构，所以这种方法存在着很大缺陷。 2 1 基于层次数据库的存储管理技术。由于x m l 本身是层次结构的，所以可以将 x m l 数掘存储在层次数据库中。在层次数据库中，可以利用一种p s e u d oq u e r y 的语法来 编写查询语句对数据进行查询【8 1 。但层次数据库技术非常的不成熟，而且操作非常复杂。 因此这不是一种很有效的方法。 3 1 基于关系数据库的存储管理技术。关系数据库是目前最成熟的数掘库技术，我们 可以将x m l 的模式映射到关系数据库中，例如：将d t d ( 文本类型定义) 映射到关系 6 第1 章绪论 数掘库中 9 1o 文献 8 ，1 0 ，1 l ，1 2 ，1 3 部采用了这种映射技术。一种高效的基于关系的 存储取回技术将x m l 文档分成一。些语义相同、灵活的小单元进行处理并提出了一种查 询算法o “ 。文献15 开发了一个可视化基于关系的x m l 存储系统。总之，这种基于关 系数据库的存储管理技术被应用的非常广泛。 4 ) 基于面向对象数据库的存储管理技术。面向对象数据库用自身的方法、关系和语 义束管理分层x m l 树，同时提供了强大的导航和链接的功能。文献 2 ，1 6 采用了这种 技术存储x m l 数据。虽然面向对象数据库的体系结构非常适合存储x m l 数据，但它本 身技术还不成熟，从而限制了它的应用。 第三类：本文总结的分类方法 1 ) 基于模式映射的存储管理技术的实现方法。 卣接的方法。当x m l 文档中存在一种模式，比如：一个d t d 或一个x m ls c h e m a 。 我们可以利用这个模式中包含的信息，将文档直接的映射到一个数据库模式，比如：一 个关系模式( 也就是表) 。文献【9 ，1 1 ，1 3 ，2 2 详细的描述了这种方法。 间接的方法。并不是所有的x m l 文档都包含模式信息，在没有模式信息的情况下 我们可以利用数据挖掘的技术对文档进行模式抽取 2 3 1 ，当模式被抽耿之后，利用这个被 抽以的模式运用直接的方法将x m l 文档进行存储。例如：v x m l r t l 5 1 就是利用这种方法 丌发的一个x m l 存储管理系统。 2 ) 基于文档映射的x m l 存储管理技术 基于索引的方法。x m l 文档可以表示为一个图，在这个图中，用带标记的关系将数 据元素连接起来，并用这种自描述的关系结构代替了传统的结构化数据库中的模式。基 于索引的方法在x m l 文档中以字符串的形式把路径进行编码，并把这些字符串插入到 索引中，从而列查洵进行优化。然后，将索引块和x m l 数据存储到一个常用的关系数 据库中。这种方法有以下好处：c l ，这咀不需要任何文档的模式信息，因为路径能够从 文档本身抽取出来：c 2 ，无论文档的结构怎样的多样和不规则，这种方法部有很强的适 7 博士后研究： 作报告 应能力； e 1 + e 1 7 7 e 1 7 3 ) 聚集转换( g r o u p i n gt r a ns f o r m a t i o n ) 。它聚集同名的子元素。例如把两 个形如a + 的子元素聚集为一个子a + 元素。具体变换规则如下： t a + ，a + ，一a 4 ，a + ，a ? ，a + ，a ? ，a + ，j a + ，a 9 ，a ? ， 一 a + ，a ，a ， a + 此外，为了表示的统一，所有的“+ ”操作符均替换为“一操作符，因为 “的语义包含了“+ ”的语义。 例22 把例i 中的元素a 经过上述的d t d 简化转换后，它的形式如下所 刁i ： 。 以上d t d 简化变换仅保留了零个或多个，还有空或非空两种语义，而丢 失了d t d 中的一些语义。因此在d t d 不是非常复杂的时候，应当尽量的避免 使用这种简化转换方法，从而保留d t d 中的语义信息。 2 2d t d e r 方法 2 2 1 方法简介 本文将d t d 到e r 模型的转换方法命名为d t d e r 方法。由于d t d 图和 e r 图分别是d t d 到e r 模型的图形化表示，所以本方法基于d t d 图和e r 图的进行转换。 1 7 博七后研究：r 作报告 2 2 2d t d e r 方法的转换规则 规则1 ：将d t d 图中的每个元素结点转换为e r 图中的一个实体。如果 某个元素结点的子元素没有子元素且没有属性，则在e r 图中将这个元素结点 转换为与其父元素相对应实体的一个属性。 规则2 ：将d t d 图中的每个元素结点的属性结点转换为e r 图中这个元素 结点所对应的实体的属性。有以下五种情况 】) 对于简单属性且它是撑r e q u i r e d ，则将它直接连接到对应的实体上 2 1 如果是i d 属性且是# r e q u i r e d ，则将其转换为e r 图中的键属性，然 后连接剑对应的实体上； 3 ) 对于所有被# i m p l i e d 标注的属性( 除了i d r e f 和i d r e f s ) ，则将它作 为虚属性连接到对应的实体上 4 ) 对于含有i d r e f 属性的元素结