（计算机软件与理论专业论文）关系数据到xml的发布的研究.pdf

复旦人学硕l 学位论文关系数据到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 规模的庞大，定义映射关系的工 作往往很复杂。本文提出一种自动生成映射关系的算法，根据给定的关系库和 d t d ，利用两者之间的语义关系，推导出映射关系。该算法能显著减少定义映射 关系的工作量，并可直接应用到后续的发布工作。 在实际应用的发布中，关系数据随着时间的推移会发生变化，于是发布的 x m l 也应该作相应的更新。当原x m l 文件很大，而变化的部分的数据量很小的 情况下，将x m l 重新发布的策略将导致大量计算都用于生成已有的x m l 文档。 本文提出一种增量更新的算法，算法中只需要保存当前路径和x m l 的d t d 。因 此内存开销和x m l 文档的大小无关，适用于大数据量的x m l 的发布。 最后，本文还实现了一个基于关系数据库的x m l 发布系统，它是国家8 6 3 项目“w e b 数据库新技术”中的一部分。 关键词：x m l ，关系数据库管理系统，映射关系，增量发布，d t d ，视图 复旦大学琐l 学位论文 关系数据到x m l 的发布的研究 a b s t r 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 i nf a c t ，m o s tb u s i n e s s d a t ai ss t i l is t o r e di nr e l a t i o n a id a t a b a s e s ot h er e s e a r c ho fp u b l i s h i n g r e l a t i o n a ld a t at ox m li si m p o r t a n t d e f i n i n gm a p p i n gb e t w e e nr e l a t i o n a ld a t aa n dx m l ，w h i c hi sn e e d e d d u r i n ga p p l i c a t i o n so fp u b l i s h i n g ，i sv e r yc o m p l i c a t e da n dh a r dw h e nd o n eb y h a n d t h i si sb e c a u s eg r e a ts t r u c t u r ed i f f e r e n c eb e t w e e nx m la n dr e l a tj o n a i d a t aa n dp u b l i cx m ls c h e m a ( d t d ) i sl a r g e i nt h i sp a p e rw ep r e s e n ta m e t h o do fg e n e r a t i n gm a p p i n ga u t o m a t i c a l l yw h i c ht a k e ss c h e m a so fb o t h r e l a t i o n a ld a t a b a s ea n dx m la si n p u ta n dt a k e sa d v a n t a g eo ft h e i rs e m a n t i c i n f o r m a t i o nt oc o m p u t et h eb e s tm a p p i n gb e t w e e nt h e m t h em e t h o dc a n o b v i o u s l yr e d u c em a n u a lm a p p i n gd e f i n i n gw o r ka n dc a nb ed i r e c t l yu s e di n p u b l i s h i n ga f t e r w a r d r e l a t i o n a ld a t aw i l lc h a n g ei nr e a lw o r l dp u b l i s hw o r ka n dx m lg e tf r o m t h i sd a t as h o u l db eu p d a t e da c c o r d i n g l y w h e nt h ee x i s t i n gx m lf i l e i sv e r y l a r g ea n dt h ea m o u n to fc h a n g e dd a t ai sc o m p a r a t i v e l ys m a l l ，t h ew a yt o r e c o m p u t ex m l v i e ww i l lc a u s el o t so fr e d u n d a n tw o r kw h i c hu s e dt og e n e r a t e e x i s t i n gx m lp a r t i nt h i sp a p e rw ep r e s e n taw a yt oi n c r e m e n t a lm a i n t e n a n c e x m lv i e ww h i c ho n l yk e e p st h ed t do fx m li nm e m o r ya n dh a sn o t h i n gt od o w i t hh o wl a r g et h ex m lf i l ei s f o rt h i sr e a s o nt h em a t h o df i t s i nt h en e e do f l a r g ex m lp u b l i s h i n g f i n a l l yw ed e s c r i b eax m lp u b l i s hs 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 to fn 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 ，r d b m s ，m a p p i n g ，i n c r e m e n t a lp u b l i s h ，d t d ，v i e w 2 复口火学倾十学位论文 关系数据到x m l 的发布的研究 第一章绪论 1 1 介绍 当今x m l 已经成为网络上交换数据的通用标准。它解决了数据统一接口的 问题，由于x m l 的自定义性和可扩展性，它足以表达各种类型的数据。它可以 应用在需要和不同的数据源进行交互的场合。还有，x m l 的自解释性使得在客 户端收到数据的同时，也理解数据的逻辑结构和含义，从而使广泛，通用的分布 式计算成为可能。因为x m l 是关于如何描述信息的，所以可以将数据存储在x m l 文档中，而不牵涉到数据的显示问题，这样就可以将同一数据以不同的面貌展示 给不同的用户。还有，用户还可以根据需要编辑x m l 文档中的数据，提取自己 需要的部分。也就是说，可以对不同的用户，对数据进行不同的过滤，然后生成 不同的文件给用户。 尽管x m l 有很广泛的用途，但是很多现有的数据还是以非x m l 的格式存 储的。最通常的情况是数据存储在关系数据库中，因为b 2 b 是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 的规模也很大，而变化部分相对较少的情况 复旦人学硕i 学位论文 关系数据到x m l 的发布的研究 下，增量发布工作是必要的。已有的关系数据到x m l 的发布的研究很少考虑到 对于x m l 视图的增量维护。据作者所知，仅有【3 4 】做过这方顽的研究。但是【3 4 】 的方法是基于内存的，在大数据量发布的情况下，f 3 4 的方法并不适合。因此， 本文研究了一种新的增量发布方法，以流处理的方式进行增量发布，该方法不依 赖内存的大小，并且从实验上证明了本文提出的增量发布方法适用于大规模的数 据发布。 1 2 相关工作 1 2 1x 批的发布 前面已经提到很多商用数据仍然存贮在关系数据库中，因为关系数据库管理 系统所提供的稳定性和成熟的技术，这一现状在短期内不会改变。因此，将关系 数据库的数据转换成x m l 的形式正式我们所要研究的。目前，已有不少关于x m l 发布的研究成果。 关系数据的发布过程可以用图1 1 来表示。将关系数据转换成x m l 必须解 决以下两个问题。第一，如何定义这种转换规则。第二，如何有效地实现这种转 换规则，将数据发布成x m l 。 1 2 1 1 ) 【m l 的映射关系 映射关系的定义是x m l 发布过程中首要解决的问题，只有确定哪些数据以 及这些数据以什么规则转换成x m l 之后，才能进行发布工作。对于这个问题， 许多x m l 的发布方法都是定义一种从关系库到x m l 的映射关系语言，通过映 射关系语言中所描述的映射关系，即数据转换规则，进行数据发布。【3 】通过扩 展s q l ，增加了聚合操作以及分阶层操作，用于定义具体的x m l 的嵌套结构。 利用s q l 函数进行x m l 数据的提取。该映射关系语言的实现需要扩展现有的 s q l ，然后整个映射关系可以利用关系引擎实现，充分利用关系库稳定成熟的技 术。【4 】给出了基于特定d t d 的发布框架，设计了自己的映射关系语言a t g 。a t g 为d t d 中每个元素节点绑定了关系表的属性组以及语义规则，根据语义规则可 得到数据从关系库中提取的方式。a t g 需要预先定义，因为该映射关系定义比 较繁琐，所以定义a t g 的工作量较大。【5 】提出了一种通用的发布方法 s l | k r o u t e ，它将映射关系称为视图，并分为物化视图和虚拟视图。【5 l 中定 义视图的语言是r x l ，r x l 是一种说明性的查询语言，比较贴近于s q l ，可以 4 复旦，l = = 学碗i 学位论文 关系数据到x m l 的发布的研究 用来提取关系数据以及构造层次化的x m l 。在虚拟视图中，s i l k r o u t e 支持 x m l _ q l 6 ，并将r x l 和x m l _ q l 拙，g l “1 ：i ，形成一种新的x m l 查询语言。在物 化视图中，s i l k r o u t e 使用r x l 作为系统的物化视图定义语言。 峨日于必杀 跳i 铡) s o l 谯渤 糕台雕h 、箍 图1 1x m l 的发布 除此之外，还有一些商业化的发布系统，0 r a c l e 的x m ls q lu t i l i t y 7 1 ，i b m 的d b 2x m le x t e n d e r 【8 】，以及m i c r o s o f ts q ls e r v e r2 0 0 0 【9 】，他们都有自己 的映射关系语言。o r a c l e 的x s q l 把单独的s q l 查询嵌入到x s l t 1 0 】样式表 中。s q l 的查询结果映射到正规的x m l 格式，然后样式表将x m l 转换到需要 的格式。在所有的系统中，x s q l 是将x m l 视图同相应的s q l 查询结合的最紧 密的。i b m 的d b 2d a t aa c c e s sd e f i n i t i o n ( d a d ) 语言包含了数据提取部分和 x m l 模板。每个x m l 模板可以包含在关系表上任意的s e l e c t 和i o i n 的条件， 它不可以任意嵌套d a d 的说明。s q l s e r v e r 2 0 0 0 支持x m l 视图的工具和以上 两个类似。 在已有的发布系统中，这些映射关系需要数据库管理员来定义，定义转换规 则的工作量是巨大的。这是因为通常映射关系的定义是很复杂的，关系库的数据 是表结构的，标准化的( 例如3 n f ) ，而x m l 的结构是嵌套的，非标准化的。 复旦人学碱i j 学位论文 关系数据到x m l 的发布的研究 所以，从关系型数据到x m l 的映射关系的定义通常需要嵌套的查询语句，多个 关系表的联接以及不相关表之间的整合，将关系表中的表和属性名映射到x m l 的元素和属性，建立x m l 的层次结构。本文提出了一种自动推导的映射关系的 算法，使得只要对少量必要信息进行定义，其余部分的工作都可以由算法完成。 该推导算法得到的映射关系可以方便的转换成【5 】中的r x l 以及s q l 。对于关系 库到x m l 的映射关系的自动生成的方面的研究非常少。【1 1 】提出一种根据d o m 来发布关系数据的方法，形式化描述了发布的过程。【1 1 1 和本文的相同点在于都 是根据用户指定需要发布的数据，自动生成映射关系，同样存在一些无法预测的 情况，在本文第二章中介绍。但不同点是】根据d o m ，程序生成和关系表结 构类似的d t d ，不适用对于给定的d t d 发布关系数据。而且对于关系表的联接 操作，】需要用户给出，而本文可以通过算法推导出这方面的内容。 1 2 1 2x , y l 的发布过程 给定了映射关系的定义，接下来需要提供一种机制来实现映射关系中所描述 的数据转换规则，即将关系数据提取出来，整合加标签成为符合映射关系定义的 x m l 文档。目前已有不少发布系统的研究【3 ，4 ，5 ，12 】，还有发布系统的实现 以及部分商业化的发布系统【7 ，8 ，9 ，1 5 】。f 5 】中提出的发布系统分为虚拟视图 的发布以及物化视图的发布。虚拟视图的发布初始时并不真正的将关系数据导出 成x m l 的格式，而是仅仅定义一个x m l 关于关系库的视图，当应用程序需要 访问x m l 视图中的m l 数据时，发布系统对关于x m l 的查询x m lq l 进行 解析，得到相应的s q l 传送给关系数据库管理系统。经过s q l 查询，得到关系 元组，然后对关系元组进行整合加标签，得到应用程序需要的结果x m l 。这样 的好处是每次的得到的x m l 数据都是最新的。不过，频繁的解析应用程序的x m l 查询，将其转换成s q l 以及最后得到结果集的处理，因为x m l 和关系库结构上 的巨大差异，再加上程序生成的s q l 总是比人为描述的s q l 复杂许多，这些 x m l 专关系查询专关系查询结果- - ) x m l 查询结果的转换开销很大。 另一种重要的发布方法就是物化视图的发布。物化视图的发布初始时将整个 x m l 关于关系库的视图从关系库中导出，之后的x m l 查询不再涉及关系库管理 系统，而直接在发布好的x m l 上进行查询。本文主要研究的就是大数据量的物 化视图的发布。大数据量的发布主要用于数据导出以及数据仓库的应用。本文主 要参考了【1 2 中的物化视图发布方法。【3 1 对各种发布方法的实现机制根据生成 x m l 标签，结构的早晚分成三类。第一类，先加标签，先整合。该方法简单的 通过嵌套查询实现数据提取与整合。x m l 的结构通过相同结构的嵌套查询来实 复旦人学颀：f 一学位硷文 关系数据到x m l 的发布的研究 现。结果x m l 中同类型元素的生成都调用相同的存储过程来实现。加标签的过 程发生在每次查询结果的返回。因此该方法边生成结果x m l 边进行关系库查询a 缺点在于每生成一个嵌套结构的x m l 片断都要调用一次或多次s q l 。多次查询 的提交导致性能的低下。第二类，后加标签，后整合。该方法将发布过程分为明 显的两部分，第一部分提取关系库的数据，第二部分加标签并整合。实现第一部 分的一个简单的方法是联接所有相关关系表。这样做会带来大量的数据冗余( 因 为多值依赖【1 3 1 ) 。另一种方法是将根到每个叶子层的节点的路径中相关关系表 联接，所有联接结果做外部并。这样可以减少多值节点的重复，不过父节点的信 息在每个子节点上还是有重复拷贝。这类发布的添加标签和整合的有效方法通常 是用h a s h 表来实现，但是如果主存的大小相对h a s h 表不足，那么会导致性能 急剧下降。因此对于大数据量的物化视图的发布，第二类发布方法也不合适。第 三类，先整合，后加标签。该方法通过关系库引擎来排序元组，使得最终结果集 的结构和x m l 的结构一致，即先生成结构，该方法翻称之为s o r t e do u t e rj o i n 。 最后加标签的过程只需要通过比较父节点是否相同来判断结束标签的输出。因 此，加标签需要的内存和x m l 文档的深度有关，和x m l 文档的大小无关。本 文采用的发布方法【1 2 1 即为第三类发布方法。综上所述，第三类方法对于大数据 量发布的情况最适合。下面简要介绍本文所用到的发布机制。 整个发布过程分为映射关系解析，中间结构优化，s q l 生成，s q l 提交取 得结果元组，整合加标签这几个步骤。见图1 1 。 映射关系的解析器的输入为关系数据库到x m l 的映射关系的定义。这一部 分先略过，因为本文采用了自动生成映射关系的方法，不需要解析映射关系，而 且输入部分大大简化了映射关系的定义。只需要提供少量必要的映射信息。映射 关系的解析器的输出是发布过程中用到的中间数据结构。这一部的详细描述请见 第二章。 中间结构优化器的输入是上一步生成的中间数据结构。这里采用的是【1 2 1 中 的v i e w t r e e 。v i e w t r e e 是树型结构，v i e w t r e e 对应x m l 的d t d 的结构。每个 节点对应d t d 中的一个元素类型。v i e w t r e e 上的每个节点用d e w e yi d 14 】进行 编号。该模块用于选择一个s q l 提交方案，使得该方案的执行效率接近最优。 对于v i e w t r e e d 的任何一种分割代表一种s q l 提交方案。也就是说，如果v i e w t r e e 中两个节点之间有边相连，那么这两个节点的内容就通过一条s q l 得到。 某一种s q l 提交方案是一次性提交一整句s q l ，该s q l 查询所有x m l 中的节 点( 对应完整的一棵v i e w t r e e ，所有边都不删除) 。另一种极端的s q l 提交方案是 提交多个s q l ，每个s q l 只提取一个元素的内容( 对应v i e wt r e e 的所有边都 被删除，只剩下单个的节点) 。【5 ，1 2 实验表明这两种方案都不是最优的。因此该 复u 大学硕一j ! 学位论文 关系数据到x m l 的发布的研究 优化器通过关系数据库管理系统提供的执行代价估计以及结果元组大小来选择 某种s q l 提交方案( 分割v i e wt r e e ) 。 s q l 生成器使用优化后的中间数据结构作为输入( 分割好的v i e w t r e e ) 。对 于v i e wt r e e 中每个连通部分生成一条s q l ，每个连通部分的s q l 是这样计算 的：对于树中的兄弟节点之间先采用外部并，然后父子节点之间采用左外联接。 结果集按照v i e wt r e e 中的d e w e y 编号进行排序。 下一步，s q l 提交得到结果元组，可以通过o d b c 等中间件来完成，由关 系数据库管理系统来执行s q l 以及返回结果集。 最后一步是整合加标签。前面已经提到过，这里使用的是s o r t e do u t j o i n 策 略，整合在提交s q l 时候已经完成( 参见s q l 生成的方法) 。最后只需要对元组 加标签。x m l 中的标签和h t m l 中的标签形式是一样的。例如， ， 。 标签是成对出现的，这里称后者” ”为关闭标签。根据d t d 我们对产生的关 系数据添加相应的标签。这里的加标签只要存储每个父节点的i d 在哪个元组中 最后出现即可。所以需要存储当前的i d ，然后和下一个元组的该i d 作比较，如 果不相同，就可以输出关闭标签。 上面大概介绍了发布的过程。作为大数据量的物化视图的发布，主要问题在 于数据的更新，因为通常物化视图是一次性从关系库导出大量数据，但是当关系 数据发生变化时，如果不更改发布的x m l ，那么会导致数据不一致的情况。然 而，重新计算物化视图的代价又是非常高的。在现实世界中，随着数据量的增大， 物化视图的更新问题得到越来越多的重视。如何解决数据更新问题，将在下一小 节中讨论。 1 2 zx m l 的增量发布 本文所研究的是大数据量的关系库发布成x m l 的问题。当关系数据库发生 变化时，发布的x m l 文档也应该作相应的变化，否则就会产生数据陈旧的问题。 可行的一个解决方法是重新进行关系数据发布。事实上对于数据仓库等应用，关 系数据发生变化的部分和原来的部分相比，只是一小部分数据。重新计算发布的 方法使得大部分的计算都用于生成原来的x m l 文档，导致大量的重复计算。因 此有必要进行增量发布的研究。 目前，增量计算的研究在许多领域都被证明非常有效【2 2 j 。关系视图f 仃， 1 8 ，1 9 ，2 0 ，2 q ，d a t a l o g 视图【2 3 】以及面向对象的视图 2 4 ，2 5 的增量维护。 不过这些增量维护的研究都不能直接应用在本文所研究的x m l 在关系数据库上 面的物化视图。因为和传统的数据库视图不同，本文的x m l 视图是定义在构造 复旦人学坝l 学位论文 关系数据到x m ! 。的发布的研究 嵌套的x m l 结构的语言( 例如r x l ) 之一卜的。关于半结构化数据的增量维护也有 一些研究3 1 ，2 6 ，2 7 ，2 8 ，2 9 ，3 0 ，3 2 】，这些半结构化视图都是建立在图形 结构的源数据之上，视图定义也是无递归嵌套的。例如【3 1 】是基于o e m ( o b j e c t e x c h a n g em o d e l ) 【3 3 】数据库，使用扩展的l o r e l 查询语言来定义视图，整个算 法根据给定的视图和o e m 数据库上的更新，生成一组增量维护的l o r e l 语句， 提交o e m 数据库得到一组更新，然后在已有的视图上( 已建立索引) 实现更新。 半结构化数据的视图增量维护和本文的情况明显不同，本文得增量部分从关系数 据库获得，增量关系的维护建立在传递关系数据库的增量数据到外部的x m l 文 档之上。因此半结构化视图的增量维护也无法直接应用在关系库的x m l 发布的 情况。 关于关系数据库的x m l 物化视图的增量发布的研究，到目前为止，据本文 了解只有f 3 4 】作了相应的研究。 3 4 】的关系库发布系统使用的视图定义语言是 a t g ( a t t r i b u t et r a n s l a t i o ng r a m m a r ) 【4 】a t g 为d t d 中每个元素节点绑定了 关系表的属性组以及语义规则，根据语义规则可得到数据从关系库中提取的方 式。增量发布的过程分为两部分，第一，增量部分数据的计算，第二，将原x m l 文档建立索引，将增量部分添加到原x m l 文档中去。本文的工作也是基于d t d 的，增量部分的提取也比较接近。不过本文和 3 4 1 的区别在于，我们考虑的是大 数据量得增量发布，相对原x m l 而言，增量部分只占了很小的比例，而【3 4 1 得 增量维护方法需要在内存中对原文档的每个节点建立h a s h 索引。如果内存相对 原x m l 文档不足，那么会严重影响该增量发布方法，甚至变得不可行。本文的 增量发布方法采用一次遍历原x m l 文档的方法，在遍历的过程中根据映射关系 以及关系库的增量作相应的x m l 的增量更新。本文的增量发布方法需要的内存 大小和原文档的大小无关，只和原文档的s c h e m a 大小有关( 这里是指d t d ) ， 因此对于主存大小相对原文档不足的情况( 这在大数据量的关系库发布中很常 见) ，本文的增量发布策略是适合的。 除了增量视图的维护，其他方面有关增量的研究也有不少成果。有不少工作 是关于增量检查更新的x m l 文档的合法性 3 5 ，3 6 ，3 7 1 以及一些x m l 文档加标 签技术对于x m l 更新的支持 3 8 ，3 9 。 1 3 本文主要贡献 本文的主要贡献在前- - + 节中已经陆续阐述，现总结如下： 提出了一种自动推导映射关系的算法。 1 简化映射关系的定义。只需指定x m l 的节点对应关系表中的属性，算法 复旦人学硕，j 学位论史 关系数据到x m l 的发布的研究 可以自动生成映射关系。如果需要对x m l 修改，只要节点对应的关系属 性不变，算法立即可以生成新的映射关系，而不需要额外的人：i ：操作。 对比繁琐的x m l 视图定义语言( r x l 。d a d ，x s q l ) ，算法可以大大简化 映射关系的定义，而不需要掌握具体的x m l 视图定义语言。 2 由于本文的算法所生成的映射关系即为从关系库中得到x m l 节点的路 径，类似于为每个x m l 节点生成一条s q l ，这个可以直接用于后续的 发布处理。因为无沦哪种映射语言，最终都要通过提交s q l 语句，从关 系库中得到数据来实现发布。算法结果可以根据需要用于相应的发布策 略，例如s q l 策略的选择，见【12 】。该方法相对于视图定义的语言，可 省去解析映射关系模块。 提出了一种新的增量发布方法。 1 适用于大数据量的物化视图的发布。对于大数据量的物化视图的发布， 当关系数据库数据发生变化时，重新计算物化视图的代价是巨大的。为 了保持发布的x m l 数据和原关系数据的一致性，本文采用增量发布方 法。该方法通过对原x m l 文档的一次遍历，根据映射关系以及关系库的 增量作相应的x m l 的增量更新。本文的增量发布方法需要的内存大小和 原文档的大小无关，只和d t d 大小有关。 2 通过实验证明，本文的方法可以在原x m l 文档大小超过主存的情况下， 有效地进行增量发布工作。同时证明了已有的增量发布方法在大数据量 的情况下并不适合。 1 4 文章结构 在接下来的章节中，本文作如下安排： 第二章给出一个发布的例子，介绍自动生成映射关系的算法。 第三章对本文增量方法进行阐述，并且进行了实验的比较。 第四章介绍我们实现的一个关系库关于x m l 的发布系统，包括增量发 布。 第五章总结与展望。 复丛大学硕l 学位论文 关系数据到x m l 的发布的列f 究 第二章自动生成关系数据到d t d 的映射关系 将关系数据发布成x m l 之前需要定义关系数据库和x m l 之间的映射关系。 因为通常公共d t d 有很多节点，所以定义映射关系是项繁琐的工作。而且，目 前的发布系统都有各自定义的映射关系语言。因此，关系数据库的微小改变以及 关系库在不同发布系统之间的移植所带来的映射关系重定义的作代价是巨大的。 本文提出了映射关系自动生成的算法，根据需要发布的x m l 的d t d 以及关系 库的表模式，只要用户给出x m l 节点对应的关系，即可自动生成合理的x m l 和关系库之间的映射关系。算法结果还可根据需要直接应用于发布策略的选择。 2 1 映射关系的一个例子 首先来看一个关系数据发布的例子。该例子取自于 1 2 1 。 图2 1 是待发布的数据库的表模式。这里引用的是t p cb e n c h m a r k h 擞据 库。该数据库包含了p a r t 的信息。p a r t 的供应商即s u p p l i e r 的信息，p a r t s u p p 表存储这种供应商s u p p l i e r 提供零件p a r t 的关系。c u s t o m e r 以及c u s t o m e r 关 于某个零件( p a r t ) 的订单即o r d e r s 的信息。其中每张表的主键由“”标出。例如 p a r t 表有6 个属性，其中p a r t k e y 是主键。本例中外键由相同的属性名表示。例 如，s u p p l i e r 中的属性n a t i o n k e y 是外键，指向n a t i o n 中的属性n a t i o n k e y ， n a t i o n k e y 是n a t i o n 的主键。 为了描述简便，下文用表名中的大写字母表示关系表，用“表名属性名”表示 关系属性。例如p s s u p p k e y 表示p a r t s u p p 的属性s u p p k e y 图2 1 待发布的关系表的表模式 d t d 是用来定义x m l 文档的结构的。d t d 通过描述x m l 文档中每个元素 的属性和子元素序列来规定x m l 文档结构。图2 2 为图2 1 中关系表将要发布 墨竺查堂堡望竺堕兰 篓至塑塑型墨坚! 塑垄鱼! ! ! ! 堕 的x m l 的d t d 的片断。该d t d 描述了整个x m l 文档唯一的根节点是s u p p l i e r s ， s u p p l i e r s 有零个或多个子节点s u p p l i e r s u p p l i e r 节点有一个属性节点i d ，类型 “# r e q u i r e d 表示该属性是必须的。还有s u p p l i e r 的名称n a m e 子节点，s u p p l i e r 所在的国家n a t i o n 子节点，s u p p l i e r 所在的地区r e g i o n 子节点以及一些p a r t 子 节点。除此之外，整个d t d 还描述了p a r t ，o r d e r , c u s t o m e r 等节点的结构。 图2 2d t d 片断 将关系数据发布成x m l 文档，仅有d t d 是不够的，因为机器无法知道这 些节点具体表示什么数据，节点之间的关系在关系库中是如何体现的。所以，还 需要定义关系库和x m l 节点映射关系。这里使用的映射关系语言是r x l ，图2 3 是这个发布的r x l 描述。 r x l 中的f r o m 和w h e r e 部分描述了如何从关系库中提取数据，以$ 开头的 为元组变量。c o n s t r u c t 部分用于构造x m l 。例如，对于p a r t 节点，根据f r o m 和w h e r e ( 图2 3 中的”和1 2 行) 我们可以知道，对于某个s u p p l i e r 节点$ s ，$ s 的子节点p a r t $ p ( 根据d t d ，有零个或多个p a r t 子节点) 必须满足，表p a r t s u p p 中存在$ p s ，使得$ s s u p p k e y = s p s s u p p k e y 并且$ p s p a r t k e y = s p p a r t k e y a 这 就意味着供应商s u p p l i e r 下面的子节点p a r t 必须是该供应商提供的零件。根据 这个例子可以看出，仅仅指定x m l 中的节点对应的关系表的属性不足以描述两 者之间的映射关系。假如将图2 3 中的1 1 和1 2 行改为“f r o mp a r t $ p ”，那么修 改后的映射关系变成了对于某个s u p p l i e r 节点$ s ，$ s 下面的子节点p a r t 包含了 关系库p a r t 表中所有的p a r t 。该语义和修改前的完全不同，虽然修改前后x m l 节点对应的关系表的属性都是一样的。 直观的理解，本文的工作就是自动生成图2 2 中的f r o m 和w h e r e 部分。图 复1 3 大学硕士学位论史 关系数据到x m l 的发布的耐f 究 2 2 描述的1 0 个节点中就包含7 条f r o m 语句，6 条w h e r e 语句。f r o m 和w h e r e 部分占据了映射关系的主体。而映射关系又是非常复杂的，这是因为：一，关系 数据的平坦的表结构和x m l 数据的嵌套层次结构的巨大差异，使得定义它们之 间的转换关系的映射语言变得复杂；二，公共d t d 可能有上百个元素节点上千 个属性节点，每个节点都必须在映射关系中有定义，随着d t d 节点数目的增多， 相应的映射关系也变得非常庞大。因此，本文的工作能大大提高工作效率。 1f r o ms u p p l i e rs s 2c o n s t r u c t 3 $ s n a m e 4 f f o r en a t i o n $ n 5w h e r es s n a t i o n k e y = s n n a t i o n k e y 6 c o n s t r u c t 。 7 $ n n a m e 8 r o m r e g i o ns r 9w h e r e s n r e g i o n k e y = $ r r e g i o n k e y 10 c o n s t r u c t $ n n a m e 1 1 f r o mp a r t s u p p $ p s ，p a r t $ p 12 w h e r e $ s s u p p k e y = $ p s s u p p k e y 13 $ p s p a r t k e y = $ p p a r t k e y 14 c o n s t r u c t 15 $ p n a m e 16 (froml i n e l t e m $ l ，o r d e r s $ o 17 w h e r e $ s p a r t k e y = $ i p a r t k e y | 18 $ p s u p p k e y = $ 1 s u p p k e y , 19 $ 1 o r d e r k e y = s o o r d e r k e y 2 0c o n s t r u c t 2 1 2 2 2 3 2 4 2 5 $ o o r d e r k e y ( f r o mc u s t o m e r $ c w h e r e $ o c u s t k e y = $ c c u s t k e y c o n 甜r u c t 2 6 $ c n a m e 27(fromn a t i o n $ n 2 2 8 w h e r e $ c n a t i o n k e y = $ n 2 n a t i o n k e y 2 9 c o n s t r u c t 3 0 $ n 2 n a m e 3 1 ) 3 2 3 3 o r d e r 蚺 3 4 3 5 图2 3 上述发布的映射关系的r x l 描述 复日大学硕士学位沦殳 关系数据到x m l 的发布的研究 2 2 预备知识 本文推导映射关系的依据是：x m l 的模式d t d 本身具有语义信息，关系库 的模式也包含了语义信息。本文根据两者的语义信息，将d t d 映射到关系库的 模式上，使得两者之间语义信息最匹配，即在d t d 上如果两个节点的语义关系 最近，那么映射之后，它们在关系模式上的语义关系也最近。 2 2 1d t d 的语义信息 对于d t d 中的某个节点，它所对应的关系数据由另一些节点决定。例如， 图2 2 中p a r t 的值取决于s u p p l i e r 的值。在s u p p l i e r 对应的$ s 值( s s u p p k e y ) 确定后，根据行1 1 - 1 5 ，查询得至l j $ p ( p p a r t k e y ) 的值，然后p a r t 的信息才确定。 语义理解是p a r t 表示供应商s u p p l i e r 提供的零件。供应商的值确定了零件的值。 本文称s u p p l i e r 是p a r t 的前导节点，记为p r e ( p a r t ) = s u p p l i e r 。前导节点可能有 多个，例如根据行16 2 2 ，p r e ( o r d e r ) = s u p p l i e r , p a r t ，即o r d e r 的值由s u p p l i e r 和p a r t 的值共同决定。语义上o r d e r 表示关于某个供应商的某个零件的订单。本 文把有多个前导节点的节点称为多值节点。因为节点的值由前导节点决定，所以 节点和前导节点语义关系最近。 通过对d t d 展开化简( 在算法介绍时说明如何展开化简) ，可将d t d 用树 结构表示。在d t d 树中，语义关系最紧密的是父子( 祖孙) 节点和兄弟节点， 因此节点的前导节点在父( 祖先) 节点和兄弟节点之中。本文称树中一个内部节 点以及它的所有子节点为一个模块。模块中的所有节点共同表达了一个有主题的 语义信息。因此模块内语义关系最紧密。如图2 2 中，节点s u p p l i e r 以及它的子 节点共同描述了供应商的信息。 2 2 2 关系库的语义信息 本文提出基于关系属性的模型r a m o d e l ( r e l a t i o n s a t t r i b u t em o d e i ) ，用于 表示关系库的模式，见图2 3 。图中的节点为关系属性，节点之间的路径可以描 述图2 2 中的f r o m 和w h e r e 部分，路径的长度定义了节点间的语义距离。因此 d t d 到关系的映射过程如下：根据d t d 上的语义信息，将d t d 的节点映射到 图中的节点，使得图中节点问的语义关系( 根据路径长度计算得到) 和d t d 中 的语义关系一致。所得的路径即为要求的映射关系。 1 4 复旦人学硕士学位论文 关系数据到x m l 的发布的研究 2 2 2 1 关系属性的模型r a m o d e l 图2 4r a m o d c l 注：以k e y 结尾的属性名都缩写成x k 。x 是该属性名的首字母。例如s u p p k e y 记为s k 。 图2 4 是图2 1 所示关系表的r a m o d e l 。每个具有主外键信息的关系表都 对应一个r a m o d e l 。图2 4 中用椭圆表示属性，矩形表示关系表。矩形内部的 虚线圈对应关系表的主键，椭圆对应关系表的属性。关系表的其他属性所对应的 椭圆，排列在矩形的周围。因为空间缘故，图中只保留了和d t d 节点对应的关 系属性，省略了其他的属性。图2 1 所示的8 张关系表在图2 4 中表示为8 个带 标记的矩形，标记为相应的关系表名称。矩形s u p p l i e r 中有一个标记为s k 的椭 圆。表示该关系表的主键是s k 属性，即为属性s u p p k e y 。矩形l i n e l t e m 中有三 复旦人学硕士学位论文 关系数据到x m l 的发布的研究 个椭圆，分别标记s k ，p k ，o k ，表示表l i n e l t e m 的主键由三个属性组成，他们 分别为s u p p k e y , p a r t k e y , o r d e r k e y 。 2 2 2 2i l 4 j e d e l 中的边和路径 r a m o d e l 中当属性集a ，b 满足以下情况之，则a ，b 间存在有向边，汜 为( a ，b ) ： 1 ) a 。b 是外键关系。a 引用b 或b 引用a 2 ) a ，b 属于同一个关系表，a 是主键。 3 ) a ，b 属于同一个关系表，a 非主键，b 是主键。 r a m o d e l 中的路径由多条邻接边组成，映射关系中的关系表查询可以由 r a m o d