（计算机软件与理论专业论文）xml数据和关系数据混合查询技术的研究.pdf

复旦大学硕士学位论文x m l 数据利关系数据混合查询技术的研究 摘要 x m l 以其强大的数据表达能力，事实上已经成为i n t e r n e t 上数据表示和交换的 标准。由于x m l 数据中保存了大量有用的信息，我们需要一种高效的x m l 查询技 术，来获得这些信息。 现有的x m l 查询技术主要有两种，一种是基于关系数据库的x m l 查询技术， 另一种是纯x m l 的结构化联接技术。本文考虑了两种技术各自的优缺点，并从x m l 数据和查询集的特点出发，提出一种新的x m l 存储方式混合映射方式，即将 一部分x m l 数据以关系元组的形式存储在关系数据库中，一部分x m l 数据以纯文 本的方式存储，并分别用关系数据库技术和结构化联接技术对这两部分数据进行查 询，使得给定查询集具有最优查询代价。为了根据x m l 数据利给定查询集得到具 有最优查询代价的混合映射模式，本文还提出了一个代价估算模型，以及基于该模 型的混合映射模式牛成算法。 本文还借鉴集合数据查询中的树型索引技术，提出将x m l 数据中枚举类型的 数据以纯文本的方式存储，并将一棵子树下的多个枚举类型元素属性看作一个集 合，利用树型索引技术对它们建立索引。本文还提出了适用于x m l 查洵的基于该 索引的查询算法。 最后，本文还实现了一个基于关系数据库的x m l 查询系统，它是国家8 6 3 项 目“w e b 数据库新技术”中的一部分。 关键词：x m l ，混合映射模式，树型索引结构，代价估算模型 复旦大学硕十学位论文x m l 数据和关系数据混台查询技术的研究 a b s t r a c t i nf a c t ，x m lh a sb e c o m et h es t a n d a r do fd a t ar e p r e s e n t a t i o na n de x c h a n g eo n i n t e r n e tb e c a u s eo fi t sp o w e r f u la b i l i t yo fe x p r e s s i o n w en e e ds o m eh i g hp e r f o r m a n c e t e c h n o l o g i e st oq u e r yx m ld a t af o rt h el a r g eq u a n t i t yo f u s e f o li n f o r m a t i o ns t o r e di ni t t h e r ea r et w op r e v a i l i n gt e c h n o l o g i e sf o rq u e r yx m ld o c u m e n t o n ei ss t o r i n g x m ld o c u m e n ti nr e l a t i o n a ld a t a b a s ea n dq u e r y i n gi tt h r o u g hr e l a t i o n a le n g i n e ，a n dt h e o t h e ri ss t r u c t u r a lj o i n i nt h i sp a p e r , w ec o n s i d e rt h ea d v a n t a g ea n dd i s a d v a n t a g eo fe a c h m e t h o d ，a n dp r o p o s ean e wn o t i o no fx m ls t o r a g e ，w h i c hi sc a l l e dm i x e dm a p p i n g i n t h i sm a p p i n gm e t h o d ，s o m ep a r to f t h ex m ld a t ai ss t o r e di nt h ef o r mo fr e l a t i o n a lt u p l e s ， a n dt h er e s ti nt h ef o r mo fx m lt e x t r e l a t i o n a lt e c h n i q u ea n ds t r u c t u r a lj o i na r eu s e d r e s p e c t i v e l yt oq u e r yt h ed a t at oa c q u i r et h eb e s tq u e r yp e r f o r m a n c e o nac e r t a i nq u e r ys e t t og e n e r a t et h em i x e dm a p p i n go ft h eb e s tp e r f o r m a n c ef o rg i v e nx m ld a t aa n dq u e r y s e t ，w ea l s ob r i n gu pac o s te s t i m a t i o nm o d e l w ea l s ou s et h et r e es t r u c t u r ei n d e xt e c h n o l o g yf o rs e td a t at ob u i l di n d e xf o rx m l e l e m e n t so fe n u m e r a t i o nt y p ev a l u e c o r r e s p o n d i n gq u e r ya l g o r i t h m sf o rx m ld a t a b a s e do nt h i si n d e xi sp r e s e n t e d f i n a l l yw ed e s c r i b eax m lq u e r ys y s t e mb a s e do nr e l a t i o n a ld a t a b a s e ，w h i c hi sp a r t o f n a t i o n a l8 6 3p r o j e c t “n e wd a t a b a s et e c h n o l o g yo nw e b ” k e yw o r d s ：x m l ，m i x e dm a p p i n g ，t r e es t r u c t u r ei n d e x ，c o s te s t i m a t i o nm o d e l 2 复旦人学硕士学位论文x m l 数据和关系数据混合查询技术的研究 第一章绪论 1 1 w e b 数据、x m l 和数据库 互联网的出现带给人们一个问题，那就是如何表示互联网上的数据，即w e b 数 据。w e b 数据和传统的数据中的数据不一样，它们一般不遵循任何广为使用的结构 ( 如关系结构或对象层次) ，所以不能直接使用传统的数据库来保存这些数据。为此， 人们提出了各种方法用来存放和表示w e b 数据。h t m l 就是其中广为流行的一种w e b 数据表示形式。h t m l 是从s g m l ( 标准通用标记语言) 演化而来，它放弃了s g m l 定 义中复杂的数据定义，仅仅保留很小的标签集合用来定义数据的表现形式，由于其 短小精悍，易于掌握，特别是它在w e b 数据呈现方面的优越特性，使得h t m l 流行起 来。但是，随着一些新应用开始在互联网上出现，如电子商务等，各种应用终端和 服务器之间的数据交换变得非常重要。再者，由于h t m l 数据抛弃了数据的结构信息， 也使得大量的h t m l 格式的内容只能通过全文检索的方式进行查询，准确率不高。为 了解决h t m l 信息的结构不确定性和w e b 数据交流问题，w 3 c 万维组织，在1 9 9 8 年提出了x m l x m l 9 8 ( e x t e n s i b l em a r k u pl a n g u a g e 可扩展标记语言) ，用来表 示w e b 数据和文档结构。 和h t m l 一样，x m l 也是从s g m l 中演化而来的，但和h t m l 旨在表现数据不一样 的是，x m l 则旨在描述数据和数据的逻辑结构，它不但保持了s g m l 的功能，还减少 了s g m l 的复杂性。随着x m l 的应用深入，它的优秀性能在很多领域都呈现出来了， 如软件开发、网站运营、移动互联等，它还可以解决网络中跨平台的数据交流问题， 使不同的网络信息可以以精确的、可供人和机器分析并加工的结构化、半结构化数 据的形式向外界提供。事实上，x m l 已经成为w e b 数据表示和交流的国际标准。 为了能被浏览器正确处理，x m l 文档在创立时就应该遵从一些既定的规则，如 x m l 文档的元素名、属性名、元素之间的关系和元素之间的顺序等，这些规则一般 写进一个独立d t d 文档或s c h e m a 文档。任何x m l 文档只有遵循了它的d t d 或s c h e m a 才是正确的。可以说，d t d 或s c h e m a 就是x m l 文档的数据结构描述。d t d 一般呈树 状，也就是说，x m l 也遵循某种数据结构，正是这一点，使得x m l 数据库的建立成 为可能。 为了要利用那些蕴含在x m l 文档中的信息，也由于他们遵循了一定的d t d ( 或 s c h e m a ) ，人们提出使用数据库来保存x m l 文档。使用数据库来保存x m l 文档具有以 复旦大学硕士学位论文 x m l 数据和关系数据混合查询技术的研究 下优点：一，可以长久地保存x m l 数据，便于充分利用已有的x m l 信息；二，可以 借鉴已有的数据操作技术和查询优化技术来优化x m l 查询。三，使得x m l 数据和已 有的大量的传统数据库数据一起使用成为可能。 目前，许多主流的数据库厂商都把x m l 支持结合到其产品中，或者提供可在其 数据库中使用x m l 的工具。i b m 提供的x m le x t e n d e rf o rd b 2 ，允许用户在d b 2 中 存储x m l 文档，并提供一些新功能协助用户处理x m l 文档；m i c r o s o f t 的s q ls e r v e r 6 5 和7 0 也进行了x m l 扩充，能将关系数据库中的数据以x m l 的形式对外发布。 o r a c l e 也拥有功能强大的x m l 索引引擎。 可以说，在未来的信息领域，x m l 数据，和传统数据库一样，是一种非常重要 的信息来源。而且，x m l 数据库也将变得海量，对查询系统的响应时间要求也将越 高。因此，对x m l 查询的分析及其在查询优化方面的应用的研究也就变得重要了。 1 2 相关工作 1 2 1 x m l 数据管理系统的发展过程 随着x m l 的应用越来越广泛，对x m l 数据进行有效管理的重要性日益显现。 为此，一系列的管理系统诞牛了。它们使用不同的方式存储x m l 数据，查询的性 能也随之有所不同。 最早的x m l 数据管理系统是l o r e 系统 a q m 9 7 1 ，它使用半结构化数据库来篱 理x m l 数据。l o r e 系统把数据当作带有标记的有向图，并把每一个元素当作一个 对象进行存储。它使用l o r e l 作为查询语言。为了提高查询效率，系统中建立两种 索引：l i n d e x 和v i n d e x 。l i n d e x 本质上是每一个元素的父元素指针，而v i n d e x 是 对所有原子值建立的索引。通过这两种索引避免对整个数据库的扫描，提高查询效 率。 然而，半结构化数据库技术并不是种成熟的技术，建立在这种技术之上的x m i 查询，其性能势必受到限制。与之相比，关系数据库经过2 0 多年的发展，已经相当 成熟。因此，使用关系数据库来存储和查询x m l 的想法随之成形。在这种方式下， x m l 文档被分解成关系的元组存储在关系数据库中；对x m l 数据的查询，首先经过 查询重写，转换成对关系表的查询( s q l 语句) 并提交给关系数据库的引擎执行， 最后将查询结果转换成x m l 格式。这种建立在关系数据库的基础上的x m l 数据篱弹 系统，被称为x m lo v e rr e l a t i o n a l ( x o r ) 系统，例如 e d 0 0 1 ，s b 0 0 ，s q x 0 4 。系 复旦大学硕士学位论文x m l 数据和关系数据混台查询技术的研究 统结构图如图1 1 所示。x o r 系统的一个大前提，就是x m l 文档遵循特定的d t d ，从 而具有相对的数据规则性。系统根据d t d ，生成关系模式，以将树型结构的x m l 文 档转换成关系元组。 s t g 9 9 中提出了几种根据d t d 生成关系模式的映射算法。x o r 系统的优点是显而易见的，它使用了关系数据库技术，查询效率具有定的保障， 而且系统的开发相对简单，主要就是一个查询重写和查询结果转换的中间件。其缺 点是由于s o l 和x m l 的查询语言( 如x o u e r y x q l 0 3 ) 之间的语义差异，r o x 系统不 能完全实现x m l 查询的功能。 到l s q l d b m s x q u e r ye m b e d d e di n t os q l 图1 1x o r 体系结构图 图1 2c o - p r o c e s s o r 体系结构图 c o p r o c e s s o r 的系统是另一种使用关系数据库存储x m l 数据的系统，如图1 2 所示。在这种系统中 e d 0 0 1 ，m s f 0 0 ，x m l 文档是以文本的方式来存储在关系数据 库中。当用户提交一个x q u e r y 查询时，一个x o u e r y 查询处理器将以用户白定义函 数的形式被调用，被查询的x m l 数据和查询的结果以文本的形式在x q u e r y 查询处理 器和关系库查询引擎之间进行交换。可以看出，关系数据库中起作用的主要是存储 功能。c o p r o c e s s o r 的优点是系统结构简单，模块化。缺点是查询时x m l 数据必须 被全部读入内存，因此查询效率低。 t i m b e r 系统 j a c 0 2 使用n a t i v e 方法存储x m l 数据。系统使用三元组 ( s t a r t p o s ，e n d p o s ，l e v e l ) 表示每一个节点，分别代表节点的其实标签位置，结 束标签位置以及层次号。根据两个节点的三元组表示，很容易判断两个节点之间是 否具有祖先后代关系。这样，一个树型x m l 查询首先通常是被分解成一组父i 予或 祖先，后代关系结点对，然后在x m l 数据库中匹配分解的二元结构关系，最后将查 找到的二元结构匹配结果组装( s t i t c h i n g ) 成最终的符合查询表达式的完整树结构。 为了加快二元结构关系的匹配，产生了一系列的结构化联接算法。 a j k + 0 2 q b 提出 了基于栈的s t a c k t r e e 联接算法。【c v z + 0 2 是对s t a c k t r e e 算法的改进，它使用 复旦大学硕士学位论文x m l 数据和关系数据混合查询技术的研究 b + 树对s t a r t p o s 建立索引，快速跳过部分不必参加联接运算的结点。【b s k 0 2 ! 的 h o l i s t i ct w i gj o i n 算法，是为了避免匹配分解的二元结构关系而产生大量无用的中 间结果而提出的。它的核心算法p a t h s t a c k 算法与t w i g s t a c k 算法采用多个栈一次 生成从根到叶的长枝下的查询结果。它不但可以确保中间结果对最终结果有用，而 且它避免了结构化联接后对多个二元关系的匹配结果的连接。 s q l p 8 r s e r ，r e w r i t e r x q u e r yd b m s s q lr n n t i m e f u n c t i o nl i b r a r y 图1 3 r o x 体系结构图 h j l 0 4 针对目前越来越多的数据以x m l 形式出现，而多数应用程序使用s q l 接口的状况，提出了r e l a t i o n a lo v e r x m l 模型( r o x ) ，如图1 3 所示。这是一个 n a t i v ex m l 管理系统，丰要由x q u e r y 查询引擎和n a t i v e 方式的x m l 存储管理组 成，同时它保留了对关系接口( s q l 语句) 的支持。当用户通过一个s q l 接口防 问x m l 文档时，系统首先通过一个p a r s e - a n d - r e w r i t e 模块，将s q l 语句转换成 x q u e r y 语句，然后提交给x q u e r y 查询引擎执行。系统中还有一个s q l 函数库， 以支持不能被转换成x q u e r y 函数的s q l 函数。文章中还讨论了r o x 模型的性能 以及优化。 i 2 2 物化视图在x o r 系统中的应用 在数据库的查询中，相当一部分查询是复杂的，通常需要涉及大量的数据，而 且一般要对数据进行投影、连接、分组等复杂处理，这是一个非常耗时的过程。然 而数据库应用系统却要求它的查询能够被快速响应。解决这个矛盾可能所采用的方 6 复且大学硕士学位论文 x m l 数据和关系数据混旨查询技术的研究 法是：数据库针对可能的查询对原始数据进行投影、连接、分组等预处理，建立许 多“物化视图( m a t e r i a l i z e dv i e w ) ”。物化视图与数据库的“视图”概念不同之处 在于：它不是虚拟的，而是经过计算，含有大量数据，并存储在数据库的一张实实 在在的表中的。通过这些预计算，数据库的数据操作引擎基本上不再需要对原始数 据进行复杂处理，而只需在物化视图的基础上进行一些简单的计算便可以完成复杂 的查询。 作为一种查询优化技术，物化视图同样适用于x o r 系统。不管x m l 是以怎样的 方式映射到数据库中的，在查询x m l 时，都需要将x m l 各个元素按其语义进行连接， 这种连接可能涉及很多个表( 由x m l 的存储策略决定) ，如果数据量大的话，其时间 消耗是非常大的，所以对于复杂的查询，和传统数据库一样，我们可以将可能查淘 到的数据事先选择、连接，形成x m l 的物化视图，并以此来优化x m l 查询。 在x o r 系统中使用物化视图技术首先要面对的问题是：建立什么样的物化视图。 我们知道由于物化视图中引入冗余信息，从而减少复杂查询的联接代价，然而却由 于数据量的增大，对简单的查询造成负面的影响。又比如，查询的模式多种多样， 因此如何合理的设计物化视图，使得最少的物化视图能匹配更多的查询是一个很重 要的问题。 z m 0 3 通过统计x m l 文档集中各个元素的分布信息，并通过群体遗传算 法在基本视图集的基础上计算具有最大物化收益的物化视图集。 w w s 0 3 ，w z q 0 4 采 用数据挖掘的算法，在大量的查询中挖掘出频繁的查询模式，并建立相应的物化视 图。另一个重要的问题是：在查询时如何选取物化视图。由于物化视图的引入，一 个被查询的元素可能被映射到了多个物化视图中。因此，在查询重写时如何进行选 取，使得查询代价最小是一个难点问题。 z l c 9 8 根据数据库的统计信息，提出了自 己的代价估算模型，并在这个代价估算模型的基础上使用贪心法进行物化视图的选 取。算法不能保证所选取的物化视图是最优的。 1 2 3 集合数据查询的相关研究 在x m l 中存在着大量的集合类型的数据。例如，在x m l 文本中，形如： 的元素定义是非常普遍的，在这个定义中 c h i l d r e n 就是一个集合数据。因此，将集合数据的查询操作方面的研究成果应用于 x m l 中集合数据的查询是一件十分有意思的事情。【h m 9 9 】中讨论了基于传统的 s i g n a t u r e 和i n v e r tf i l e ( 反向文件) 的方法，研究了基于b - 树的i n v e r t l i s t 、 s e q u e n t i a ls i g n a t u r ef i l e 、s i g n a t u r et r e e 和e x t e n d i b l es i g n a t u r eh a s h i n g 四种集 复旦大学硕士学位论文 x m l 数据和关系数据混合查询技术的研究 合索引结构，并对选择操作的实现方法进行了研究和比较。【h p 9 7 1 提出了一种基 于树的集合索引结构r dt r e e ，r dt r e e 以r 一树的思想为基础，将内容相近集合 数据存储在一起。 m + 0 0 和 a + 9 4 1 基于s i g n a t u r e 的方法对集合数据的联接操作进 行了研究，提出了p s j ( p a r t i t i o nb a s e dj o i n ) 算法。 w x t + 0 4 针对集合数据提出了 一种索引结构：s e t _ s t r u c ，这种结构是利用集合数据中的结构信息和集合数据的次 序信息建立的一棵树型结构，同时还借助了反向文件的思想定义了反向链表。文中 还基于s e l s t r u c 提出了集合数据包含联接操作的实现算法，它具有较高的执行效 率。同时避免了基于s i g n a t u r e 方法中计算量较大的验证阶段。 1 3 本文的主要贡献 本文的丰要贡献主要有； 1 本文对x m l o v e r r e l a t i o n a l 体系中的从d t d 到关系数据库的映射方式进行 了新的思考，从x m l 数据利查询集合的角度出发，结合现有的纯x m l 研 究成果结构化联接技术，提出了一种混合映射方式，即将x m l 中的一 部分元素以关系属性的形式存放在关系数据库中，另一部分元素以文本的 形式存储。它有利于充分发挥关系数据库和结构化联接技术的优点，获取 更高的查询性能。本文还提出了关系数据库和结构化联接技术的代价估算 模型，并根据这一模型提出了x m l 数据的混合映射算法。 2 借鉴集合数据查询中的树型索引技术，本文提出以文本形式存储x m l 数据 中枚举类型的元素，把这些元素看作集合并利用这种技术建立索引。它可 以通过数据合并减少数据的体积，并存放在内存中，具有较高的查询效率。 本文还提出了基于这种索引的适用于x m l 查询的查询算法。 3 本文实现了个完全基于关系数据库的x m l 数据查询系统。它是国家8 6 3 项目“w e b 数据库新技术”中的一部分。 1 4 文章结构 在接下来的章节中，文章是这么安排的： 在第二章中，我们将介绍现有的从d t d 到关系数据库的映射方法，以及本 文所提出的混合映射方式。 在第三章中，我们将介绍如何用集合数据上的树型结构索引技术对枚举类 复旦人学硕士学位论文x m l 数据和关系数据混合查询技术的研究 型的元素建立索引，并进行查询。 第四章将介绍我们实现的基于关系数据库的x m l 查询系统。 第五章是总结与展望。 复旦大学硕士学位论文x m l 数据和关系数据混台查询技术的研究 第二章x m l 数据的关系存储 随着x m l 数据的大量涌现，如何合理有效的管理x m l 数据成为人们日益关 注的问题，而关系数据库技术便是最早用于x m l 数据管理的技术之一。这是因为， 一方面关系库系统和技术经过数十年的发展和完善，相关技术已经非常成熟，并有 一整套理论基础，它在大规模数据处理中的高效性、系统稳定性、可移植性和可扩 展性是其他技术所无法比拟的。在现有关系数据库技术的基础上加一层中间件，实 现对x m l 数据的查询和管理，具有开发工作量小，查询性能较好的优点。具有另 一方面，鉴于w e b 上的数据现在、并且将来，也将存储在关系库的情况，使用r d b m s 有利于x m l 文档和原有数据得无缝集成。然而，我们知道，x m l 数据是树型结 构，而关系数据是平坦的= 维结构，这种模型的差异给x m l 数据的关系存储带来 较大的困难。可以说，x m l 数据到关系数据的映射方式，将对系统的查询性能造 成直接的影响。本章首先介绍现有的两种映射技术：基于模型的映射利基于结构的 映射，然后介绍本文所提出的x m l 文本和关系元组的混合映射方式。 2 1 基于模型的映射 顾名思义，摹于模型的映射就是从x m l 文档模型定义出发，从x m l 到关系 库的映射，它们使用固定的关系库模式来存储x m l 文档的结构和内容，在映射的 过程中不考虑或较少考虑具体的d t d 定义 y a t + 0 1 s k w + 0 0 k m 9 9 。其中 e d g e l k m 9 9 和x p a r e n t 是其中比较典型的分别以边和节点为中心的两种方法。每个 x m l 文档可被建模为一个有向图。假设e 0 , e i 八e n 为一条数据路径，2 八l 。为该数 据路径的标签路径，其中e o 为虚拟的根节点，e i 是元素的唯一标识i d 。 e d g e 方法中，关系模式包含一张表e d g e ( s o u r c e ，t a r g e t ，n a m e ，o r d i n a l ，f l a g ， v a l u e ) ，此表保存x m l 数据图的所有边信息。此外还可以包含以节点值的类型分 别存储的v a l u e 表v t y p e ( v i d ，v a l u e ) 。e d g e 表的主键为组合属。 生 s o u r c e ，o r d i n a l ，其 中每条边由结点标识符对( s o u r c e ，t a r g e t ) 表示，n a m e 字段记录边的标签，o r d i n a l 表示这条边在兄弟中的顺序，f l a g 指示t a r g e t 字段为内部元素对象引用还是指向 字符值。v a l u e 表则是为所有结点可能具有的数据类型分别创建表，例如，所有类 型为i n t 的结点存在一张表中，所有类型为s t r i n g 的结点存在另张表中。e d g e 表 中的f l a g 列指出此节点对应的v a l u e 应存在哪个v a l u e 表中。如图2 1 。 o 复旦人学硕士学位论文x m l 数据利关系数据混合查询技术的研究 0 r d i n a l f l a gt a r g e t 11 a g e l i l tv 1 12n e s t r i n g v 2 13a d d r e s s s t r i n g v 3 1 4 c h i l dr e f3 l5c h i l dr e f4 2 v i dv a l u e v 2p e t e r v 3f r u i t d a l e v 5 m a r y v 6f u i t d a l e v 7 p a i n t i n g v 1 5f m i t d a l e 图2 ，1e d g et a b l ew i t hs e p a r a t ev a l u et a b l e s 这种以边为中心的方法主要维护边的信息，因而用户查询中路径表达式的计算 需要相应边的连接，而连接是关系库基本操作中代价较高的一个，因而查询效率不 高。作为这种方法的一个变种，m o n e t s k w + 0 0 映射将具有不同标签的边映射到不 同的关系表中，其字段只包括父、子元素，标签路径由一系列表的名字决定。同时 建立一个用于存储文本和属性值的表。但如此一来数据库中的表数日急剧增加( 等 于d t d 中元素的数目+ 1 ) ，难以处理正则表达式查询，对x m l 文档结构可能发 生的变化的情况也难于处理。在以结点为中心的映射方法同以边为中心的想法相 似，但其保存了x m l 数据中所有结点的信息。 2 2 基于结构的映射 对于一个给定的x m l 查询，该映射方法比基于模型的方法需要更少的表连接， 因而具有更高的查洵效率。其中最具影响的研究 s t g 9 9 提出了三种从d t d 到关 系模式的映射方法：b a s i c l n l i n i n g 、s h a r e d l n l i n i n g 和h y b f i d l n h n i n g 。该映射方法的前 提是应用存在一个相对比较固定的d t d ，因此其适用环境比基于模型的映射方法 窄。同时，尽管这些映射方法在转化的关系库查询中所需的表连接次数己相对减少， 但由于x m l 文档结构模型和关系模型的失配，还是造成了“分片( f r a g m e n t ) ”问 题。d t d 被映射到了很多关系表，为满足一个用路径表达式表示的简单x m l 查询 也需要大量表的连接和关系库查询，查询效率对一些实时的应用来说还有待提高。 复旦大学硕士学位论文x m l 数据和1 关系数据混合查询技术的研究 e l e m e n t b o o k ( b o o k t i t l e ，a u t h o r ) e l e m e n ta r t i e l t i t l e ，a u t h o r ，c o n t a c t a u t h o r ) e l e m e n tc o n t a c t a u t h o re m p t y a t 丁l i s tc o n t a c t a u t h o ra u t b o r i di d r e fi m p l i e d e l e m e n tm o n o g r a p h ( t i t l e ，a u t h o r ，e d i t o r ) e l e m e n t e d i t o r ( m o n o g r a p h 1 b a t t 乙i s te d i t o rr l a l f l ec d a t a # r e q u i r e d e l e m e n t n a m e ( f i r s t n a m e ? ，1 8 s m a m e ) e l e m e n tf i r s t n a m e ( # p c d a t a ) e l e m e n tl a s m a m e ( # p c d a t a l e l e m e n ta d d r e s sa n y 图2 2 个d t d 实例 b 。人融 2 2 1b a s i ci n l i n i n g 方法( 简称b a s i c ) 图2 3 d t d 图 b a s i c s t g 9 9 为d t d 中的每一元素都构造一张表，因为在x m l 文档可以以 d t d 中的任一元素作为根节点。对于为每一个元素所建立的表，将其子孙都内联 入同一表中，但有两种情况例外： a “”节点的直接孩予需被分离出来另建表，即多值属性结点需分离另建新表； b 具有b a c k p o i n t e r 边的节点也需被分离出来另建新表，以处理循环的情况。 对于这两种情况中的子孙节点，需要建立新的表。例如图2 _ 3 的d t d 中的 a r t i c l e a u t h o r 元素，在生成元素a r t i c l e 相应的表时就无法表达其下的a u t h o r s 元素的多 值信息。于是再为a u t h o r 仓j j 建一个表而并使用f o r e i g nk e y 来联接到父表a r t i c l e 表。但 也就是因此而导致表的数目极多。对于递归关系，则因要中止其无休止的迭代在存 储时要强行切断，因此表达递归关系时要使用关系表主键及关系迭代的处理来重获 这种信息。 b a s i c 对某些查询确实不错，如“l i s t a l la u t h o r s o f b o o k s ”，因为此时b o o k 和a u t h o r 的信息存储在同张关系表中。但对于其他某些查询就可能十分低效。比如“l i s t a l l a u t h o r sh a v i n gf i r s tn a m ej a c k ，就需要分别执行5 次查询( 因为有5 个表中都有a u t h o r 元素) ，再将其结果合并。并且，b a s i c 还有另一缺陷就是产牛的关系表数量太多。 接下来的s h a r e di n l i n i n g 方法便解决了这些问题。 复旦大学硕士学位论文x m l 数据和关系数据混合查咖技术的研究 2 2 2s h a r e di n l i n i n g 方法( 简称s h a r e d ) 为了解决b a s i c 的不足，规定每个元素节点只出现在一张表中，也就是只出现 一次，而不像b a s i c 中那样出现多次。方法也就是标识出在b a s i c 中多次出现的那些 元素节点( 象图2 3 中的f i r s t n a m e ，l a s m a m e ，a d d r e s s 这些元素) 并为其创建新表，再以 共享的方式访问它们。 首先需确定要创建哪些表。在s h a r e d 方法【s t g 9 9 中为d t d 图中每一个入度大 于l 的节点创建一个表，很明显，这些节点即在b a s i c 的方法中的多个表中多次出现 了的那些节点。入度为i 的节点则被l _ j ! | 联。另外，显然入度为0 的节点也需创建新表， 因为它们不可能从其他节点起被遍历到，也就是不可能被其他表内联。同样，如同 在b a s i c 中，对多值元素也需分别建新表。最后，入度均为1 的相瓦递归构成循环的 元素( 如图2 3 中的m o n o g r a g h 与e d i t o r ) 也需选取其中一个来建新表。可以通过查 找d t d 图中的强联通图来找到这样的相互递归的元素。 一旦确定了哪些元素需要另建表则构造相应的关系模式就很简单了。对于一个 需建表的元素x ，以其为根向下遍历，所遇到的节点，只要不是符合上述需另建表 的条件的节点都被内联入x 所在的关系表中。 将某一元素x 内联入元素y 所在的表而为以x 为根的查询带来了不便，我们可 以加入一些i s r o o t 域。在查询处理过程中被共享的元素就起到作用了，如一个查询 所有a u t h o r s 的选择查询就只需访问一个表而不像b a s i c 中需访问5 个。s h a r e d 确 实解决了b a s i c 中的一些问题及继承了它的一些优点，但b a s i c 也有其明显的优势， 就是大大减少了对某一特定的节点查询时的联接的数量。这样我们结合b a s i c 的减 少联接数量的优点与s h a r e d 方法的优点来又设计了另一种方法，就是h y b r i d 方法。 2 2 3h y b r i di n l i n g 方法( 简称h y b r i d ) h y b r i d 方法【s t g 9 9 】与s h a r e d 方法大体相同，而不同点就是多内联了些 s h a r e d 中未内联的元素。也就是内联了那些入度大于l 但未构成递归或在“”节点 之下的元素。多值节点和循环的处理方式与在s h a r e d 中一样。 2 2 4 基于结构的映射方法的总结 在此就上述三种映射方法而言做一个比较和总结。 复旦大学硕士学位论文x m l 数据和关系数据混台查询技术的研究 在d t d 元素类型定义中，用+ 和+ 修饰的子元素可以在同一父元素中包含多个， 即父元素和该子元素是1 ：0 - - * 或l ：1 一的关系。在关系数据库理论中，为减少数 据冗余和可能的更新异常，这样的一对多关系用父、子表和外键来建模。 s h a r e d l n l i n i n g 和h y b r i d l n l i n i n g 正是基于这样的思想。d t d 中元素的类型定义可以 用d t d 图来表示，其中结点表示元素，有向边从父元素结点指向子元素结点，边 上标记的w 表示父子元素的一对多关系。为减少计算路径表达式所需的表连接次 数，算法尽量将非一对多关系的子元素映射到父元素所在的同一个关系表中 ( 1 n l i n i n g ) 。但为了正确处理元素结构定义中可能出现的递归，即如果在i n l i n i n g 过程中出现环，则不再将后续元素映射到同一表中，并使用字段p a r e n t l d 和 p a r e n t c o d e 来存储元素的递归嵌套结构。其中p a r e n t l d 是指向父元素所属表的外键， p a r e n t c o d e 指明该父元素的类型。一个元素可能成为多个不同元素的了元素( 如例 予中的a u t h o r ) ，是否将这样的元素映射到父元素所在的关系表成为s h a r e d l n l i n i n g 和h y b r i d l n l i n i n g 的区别。前者将公共子元素映射到单独的表中，后者则将其与父 元素存储在同一个关系表中。 综上所述，三种方法各有利弊，b a s i c 生成的关系表的数目是h y b r i d 与s h a r e d 的若干倍；s h a r e d 查询时所需的联接( j o i n s ) 数目较多；h y b r i d 查询时需牛成的 s q l q u e r i e s 数目较多( 因为有的元素重复出现) 。可以依据具体的d t d 的结构及 p a t h ( 路径) 的长度来决定选用三种方式之一( 因为查询所需联接数目与路径长度 成一线性关系) 。 2 3 混合映射方式 基于结构的映射仅仅从d t d 的结构出发，没有考虑x m l 数据和查询的特点， 因此，这种映射方式难免具有局限性。本节在考虑x m l 数据和查询的前提下，结 合现有的纯x m l 查询技术结构化联接技术，以及对集合数据查询的索引技术， 寻找一种新的映射方式混合映射方式，将一部分元素存储在关系数据库中，另 一部分元素以纯文本的形式存储，并通过相应的技术建立索引，力求取得更好的性 能。 2 3 1 枚举类型数据 x m l 中元素的属性可以是枚举类型。此外，x m l 中某个元素上不同值的数目 复旦大学硕士学位论文x m l 数据和关系数据混合查询技术的研究 可能很小( 例如小于3 2 个) ，这种元素也可以看作是枚举类型。将这类元素属性 映射到关系属性时，在关系属性上将出现大量重复数据，造成空间的浪费。而对集 合数据的树型结构索引技术通过合并公共前缀的，能大大减少数据所占用的空间， 通常可以放在内存中进行处理。因此，如果能把枚举类型的元素属性以纯文本的 方式存储，并用树型结构索引技术进行索引，将能提高查询的性能。树型结构索引 技术将在第三章中介绍。 2 3 2 关系查询和结构化联接方法的比较 目前，纯x m l 查询技术的研究已经具有一定成果，比较具有代表性的有结构 化联接技术。而结构化联接技术中，比较有代表性的算法是h o l i s t i ct w i gj o i n 算 法。与关系数据库相比，h o l i s t i c t w i gj o i n 算法具有什么样的优缺点呢? 假设元素e 具有后代非多值的叶子元素a 、b 、c 、d 。根据基于结构的映射 方法，为元素e 建表r ( a ，b ，c ，d ) 。为了查询元素a 和b ，需要读入所有元 组，并对每个元组的a 和b 属性作投影。这个过程实际上也查啕了c 和d 元素。 结构化联接的方法分别为元素e 、a 、b 、c 、d 建立索引，这个索引是五元组序列 ( d o c i d ，s t a r t p o s ，e n d p o s ，l e v e l ，v a l u e ) ，在查询元素a 和b 时，需要对e 、a 、 b 的五元组序列按照d o c i d ，s t a r t p o s 进行排序，并对这三个序列进行联接。联接 的代价是对元素e 、a 、b 的元组排序序列的一次扫描。可见，关系数据库的存储 方式在一定程度上保留了x m l 数据的结构，从而避免查询过程中的结构联接，但 是有可能查询了额外的元素而花费更多的代价。结构化联接的方法查询的仅仅是相 关的元素，由于在建立索引时，可以使得五元组序列本身就是排序的，因此结构化 联接的方法的代价仅仅是查洵元素的五元组序列的一次扫描。 当查询元素涉及多个关系表中的少部分属性时，同样存在上面的问题，并且由 于联接是关系数据库中代价最高的操作，这种多关系联接的情况下会带来更多额外 的开销。因此，我们有理由相信，在某些情况下，结构化联接的方法比关系数据库 的方法好。 虽然如此，关系数据库上的索引却可能带来比结构化联接更好的性能。例如， 如果查询中对属性b 有选择条件，并且属性b 上有索引，根据索引可能减少访问 的元组的数量，从而获得结构化联接更好的性能。这种性能提高同样可以体现在多 关系的连接中。 可见，关系数据库技术和结构化联接技术各有利弊。因此，我们需要一种x m l 复旦大学硕士学位论文x m l 数据和关系数据混合查询技术的研究 数据和关系存储的混合映射方式，它将一部分x m l 元素按照基于结构的映射规则 转换成关系元组，而将另一部分x m l 元素以纯文本的形式存储在关系数据库中。 对于纯文本形式的属性，按照结构化联接的技术建立索引，并在这种索引的基础上 用h o l i s t i ct w i gj o i n 算法进行查询。 2 3 3 混合映射模