（计算机软件与理论专业论文）xml数据的查询、转换和集成.pdf

摘要 x m l 是i n t e r n e t 上最优秀的数据交换格式之一。近年来，学术界和工业界 对x m l 数据处理投入了很大的热情。为了有效地组织和管理x m l 数据，研究 人员提出了不同的解决办法。其中，人们较多地采用关系数据库或者文件系统来 管理x m l 数据。随着w e b 服务的发展，越来越多的远端w e b 服务也开始提供 x m l 数据。所以，在应用中存在着多种x m l 数据源。 虽然学术界已经在x m l 数据的查询处理和转换方面取得了不少研究成果 但是仍然存在着许多有待研究与解决的问题。本文探讨不同x m l 数据源的查 询、转换和集成的问题，包括关系数据库中的x m l 查询处理，特别是通过创建 路径索引来优化查询执行；结果类型保证的x m l 文档的查询和转换；无需中间 结果缓存的x m l 数据转换；集成多个w e b 服务返回的x m l 数据等。本文的主 要贡献如下： 研究了关系数据库中的x m l 数据的查询优化技术。提出了一个代价模型， 该模型考虑到了源x m l 数据的统计信息和具体应用的特点，可以较好地 估计索引的空间占用量和它们对查询性能的改善程度；采用贪心算法来选 择性地创建一部分较好的映射索引；实验表明，相对于没有创建索引的情 况，选择创建的索引仅仅额外占用了有限的的磁盘空间，但是它们对查询 性能的改善是非常明显的。 研究了文件系统中的x m l 文件的查询处理技术。利用x m l 查询扩充属性 文法，构造出一种新的x m l 查询语言x t g 。采用x t g 语言，能够从一定 程度上保证结果文档的正确性，即，它们必定符合预先规定的d t d 结构。 提出了x t g 查询的概念执行计划，并且讨论了几种优化策略，比如图授约 技术等。实验结果表明这些优化策略是有效的。 提出了x m l 转换语言g 2 s t ，它可以将g m l 文档转换得到s v g 文 档。g 2 s t 也是属性文法的扩展，其中的语义计算规则是x s l t 模板。采用 g 2 s t 语言不仅可以减轻用户创建有效转换时的负担，而且保证转换结果 是有效的s v g 文档。实验证实g 2 s t 是一种转换g m l 数据的有效方法。 摘要 v 提出了一个新颖的流处理模型来计算x s l t 转换。该流处理模型支持在 x m l 文档，特别是大的x m l 文档上的x s l t 计算。采用这个模型，x s l t 处理引擎能够将源x m l 文档( 或者流) 转换成结果文档( 或者流) ，期间 不需要利用任何额外的缓存。实验数据表明流处理途径要比现有的x s l t 引擎快上2 到1 0 倍。 提出一种统一的语言集成来自于不同服务提供者的w e b 服务。将x q u e r y 语言扩充成w s q u e r y ，使其可以包含w e b 服务调用。采用w s q u e r y 集成 w e b 服务，既能够表达业务逻辑，又能直接处理w e b 服务返回的x m l 消 息。在给出w s q u e r y 的概念执行策略之后，为了缩短w s q u e r y 程序的总 执行时间，对w e b 服务调用进行调度，以充分利用它们之间的并行度。在 进行调度前，采用依赖分析技术来决定不同的w e b 服务调用之间的依赖关 系。 关键词：x m l 查询处理，x m l 查询语言，x m l 转换，w e b 服务集成 分类号：t p 3 1 1 a b s t r a c t x m li st h ep r e e m i n e n td a t ae x c h a n g ef o r m a to nt h ei n t e r n e t p r o c e s s i n g x m ld a t ah a sr e c e n t l yb e c o m eaw i d e l yr e c o g n i z e da r e ao fi n t e r e s tb o t hi nr e s e a r c ha n di ni n d u s t r y t oo r g a n i z ea n t im a a a g ex m ld a t ae f f i c i e n t l y ，d i f f e r e n t s t o r a g ea p p r o a c h e sh a v eb e e np r o p o s e d a m o n gt h e m ，r e l a t i o n a ld a t a b a n t sa n d f i l es y s t e m sa r et h em o s tp o p u l a ro n e s w i t ht h ed e v e l o p m e n to fw e bs e r v i c e s ， x m li sa l s oi n c r e a s i n g l ys e r v e db yr e m o t ew e bs e r v i c ep r o v i d e r s t h e r e f o r e ，t h e r e e x i s td i f i e r e n tk i n d so fx m ld a t as o u r c e s d e s p i t ec u r r e n tr e s e a r c ha c h i e v e m e n t so nx m lq u e r yp r o c e s s i n ga n dt r a n s f o r m a t i o n ，t h e r ea r es t i l lm a n yo p e ni s s u e st ob ee x p l o r e d t h i sw o r ki n v e s t i g a t e s s o n l ei s s u e sr e l a t e dt oq u e r yp r o c e s s i n g ，d a t at r a n s f o r m a t i o na n di n t e g r a t i o no f d i f f e r e n tk i n d so fx m ld a t as o u r c e s w h i c hi n c l u d e ：x m lq u e r yp r o c e s s i n gi nr e - l a t i o n a ld a t a b a s e s ，e s p e c i a l l y ，b u i l d i n gp a t hi n d e x e st os p e e du pq u e r ye v a l u a t i o n ； x m ld o c u m e n tq u e r y i n ga n dt r a n s f o r m a t i o nw h i l eg u a r a n t e e i n gt h ec o r r e c t n e s s o ft h e i rr e s u l tt y p e s ；x m ld a t at r a n s f o r m a t i o nw i t h o u te x t r am e m o r yb u f f e r s r e q u i r e d ；i n t e g r a t i n gx m ld a t ar e t u r n e db yd i f f e r e n tw e bs e r v i c ep r o v i d e r s ，e t c t h em a i nc o n t r i b u t i o no ft h i sw o r kc a nb es u m m a r i z e da sf o l l o w i n g ： i no r d e rt os p e e du pq u e r ye v a l u a t i o nf o rx m ld a t ai nr e l a t i o n a ld a t a b a s e s b u i l dp a r to fp a t hi n d e x e sw h i c hc a nb r i n gm u c hb e n e f i tt oq u e r ye v a l u a - t i o n m a k i n gu s eo ft h es t a t i s t i c so fx m ld a t aa n dt h ec h a r a c t e r i s t i c so ft h e t a r g e ta p p l i c a t i o n ，ac o s tm o d e li sp r e s e n t e df o re s t i m a t i n gt h es p a c ec o n s u m p t i o no fi n d e x e sa n dt h e i rb e n e f i tt ox m lq u e r i e s g r e e d ya l g o r i t h m s a r ea d o p t e dt os e l e c ts o m em a pi n d e x e st ob eb u i l t t h ee x p e r i m e n t a ls t u d y d e m o n s t r a t e st h a tq u e r yp e r f o r m a n c eg e t ss i g n i f i c a n ti m p r o v e m e n to v e rt h e c a s ew i t h o u ti n d e x e sw h i l eo n l yc o n s u m i n gd i s ks p a c eo fm o d e s ts i z e f o rq u e r y i n gx m lt e x tf i l e s a t t r i b u t eg r a n l m a ri se x t e n d e dw i t hx m l q u e r i e st oo b t a i nan e wx m lq u e r yl a n g u a g e ( x t g ) t os o m ed e g r e e ，x t g g u a r a n t e e st h a tt h er e s u l td o c u m e n tw i l lb ec o r r e c t t h a ti s ，t h er e s u l t v l a b s t r a c t d o c u m e n tw i l lc o n f o r n lt oap r e - s p e c i f i e dd t d w ed i s c u s st h ec o n c e p t u a l e v a l u a t i o np l a no fx t g s ，a n dp r o p o s es e v e r a lo p t i m i z a t i o nt e c h n i q u e s ，s u c h a sg r a p hr e d u c t i o n ，e t c t h ep e r f o r m a n c ea n a l y s i sd e m o n s t r a t e st h e i re f l e c t i v e n e s s f o rt r a n s f o r m i n gg m ld a t a w ep r o p o s ean e wt r a n s f o r m a t i o nl a n g u a g e ( g 2 s t ) t oo b t a i ns v gd o c u m e n t sf r o mg m ld o c u m e n t s g 2 s ti sa l s oa n a t t r i b u t eg r a m m a re x t e n d e dw i t hx s l tt e m p l a t e sa ss e m a n t i cc o m p u t a t i o n r u l e s u s i n gg 2 s tn o to n l yr e d u c e st h ed i f f i c u l t i e sf o ru s e r st oc r e a t ear i g h t t r a n s f o r m a t i o n ，b u ta l s og u a r a n t e e st h a tt h er e s u l ti sav a l i ds v g d o c u m e n t ， e x p e r i m e n t ss h o wt h a tg 2 s ti sa ne f f e c t i v ea p p r o a c hf o rt r a n s | b r m i n gg m l d a t a an o v e ln o t i o no fs t r e a m i n gp r o c e s s i n gm o d e li sp r o p o s e d i tc a nb eu s e dt o e v a l u a t ex s l tp r o g r a m so nx m ld o c u m e n t s ，e s p e c i a l l yl a r g eo n e s w i t h t h i sm o d e l ，a nx s l tp r o c e s s o rc a nt r a n s f o r ma nx m ls o u r c ed o c u m e n t ( o r x m ld a t as t r e a m ) t oo t h e rf o r m a t sw i t h o u te x t r am e m o r yb u f f e r sr e q u i r e d e x p e r i m e n t a lr e s u l t sc l e a r l yc o l l f i r l nt h a tt h i sm e t h o di m p r o v e sx s l te v a l u a t i o nt y p i c a l l y2t o1 0t i m e sb e t t e rt h a ne x i s t i n ga p p r o a c h e s au n i f o r mm e t h o df o ri n t e g r a t i n gw e bs e r v i c e si s p r e s e n t e d a ne x t e n s i o n o fx q u e r y , r e f e r r e dt oa sw s q u e r y , i sp r o p o s e d w s q u e r yp r o g r a m sc a n c o n t a i nw e bs e r v i c ec a l l s t h ec o n c e p t u a le v a l u a t i o ns t r a t e g yo fw s q u e r y p r o g r a m sh a sb e e nd i s c u s s e d f o rs p e e d i n gu pt h ee v a l u a t i o n ，w ep r o p o s e t os c h e d u l ew e bs e r v i c ec a l l st oe x p l o i tp a r a l l e l i s m b e f o r es c h e d u l i n g ，d e p e n d e n c ya n a l y s i si sc a r r i e do u tt od e t e r m i n ed e p e n d e n c yr e l a t i o n sa m o n g d i 丘j r e n t 、 0 bs e r v i c ec a l l s k e y w o r d s ：x m lq u e r yp r o c e s s i n g ，x m lq u e r yl a n g u a g e s ，x m lt r a n s f o r m a t i o n w e bs e r v i c e si n t e g r a t i o n c a t e g o r y ：t p 3 1 1 第一章前言 本文的工作是关于x m l 数据的查询、转换和集成。在这项工作中，将对如 下问题进行深入研究：在将x m l 数据利用关系数据库存储之后，采用索引技术 加快x m l 路径表达式查询的执行；结合属性文法和x m l 查询语言或者x m l 转换语言，并且以属性文法作为针对x m l 文档的查询语言，对磁盘文件型x m l 数据尤其是g m l 地理数据进行查询和转换，并且探讨若干优化技术；如何尽 可能地减少x m l 数据转换过程中的内存占用量；利用x m l 查询语言集成不同 的w e b 服务返回的x m l 数据。 1 1研究背景 x m l 1 j 已经成为w 曲上数据表示和交换的事实标准。对x m l 数据的查询 处理、转换和集成是非常重要的研究问题。过去几年中，人们提出了不同的途径 来研究这个问题。事实上，对x m l 数据的处理在很大程度上取决于底层x m l 数据的存储机制，即不同的x m l 数据源种类： 如果采用成熟的关系数据库技术来管理x m l 数据，那么系统为了能够处 理x m l 查询，必须将x ml 查询翻译成为底层关系数据库系统可以处理的 s q l 查询。因而，第一个难点是查询翻译的工作，其中涉及到怎么使得翻 译所得到的s q l 查询比较简单等问题。第二个难点是怎么来高效地执行查 询翻译所得到的s q l 查询。这种s q l 语句可能比较复杂，而且可能包含 很多连接操作，连接操作在关系数据库中是非常耗费资源的。所以，有必 要考虑怎么来减少连接操作的次数和代价。 如果x m l 数据是以普通文本文件的形式存放于文件系统中，为了查询 文件系统中的x m l 数据，必须考虑两个问题，一是提供给用户的应当是 一种什么样的查询或转换语言，另外一个是如何执行这种查询并且进行 相应的优化。根据实际应用的不同，可能还需要设计不同的查询语言变 体。x q u e r y 和x s l t 这两种语言过于复杂，普通用户不容易完全掌握。最 好能够设计种x m l 查询语言，它既能对结果x m l 文档的正确性做出一 1 第一章前言 2 定程度上的保证，又能比较方便地为用户所掌握和使用，同时还必须具备 很强的表达查询的能力。 在很多应用中，x m l 数据是以x m l 数据流的方式出现的，例如：从网络 上实时接收到的x m l 数据；由其它应用程序动态产生的x m l 数据；非常 大的x m l 文档，要求只能对其从文件头到文件尾扫描一次；系统要求在 接收到前面一部分源数据时，就能够产生部分输出；等等。如果需要查询 x m l 数据流，就必须采取和以上两种方式都不同的途径。x m l 数据流处 理有它特殊之处：不允许预先建立索引结构；不能无限制地缓存源数据或 者中间结果。 随着w 曲服务的兴起，现在有些系统的数据源通过w e b 服务调用返回 x m l 结果给用户。首先需要一种类似查询的语言来无缝地集成对这些异 质数据源的访问，其次需要研究怎么来加快这类查询的执行。这是一种类 似于分布式查询处理的查询范型。为了查询这一类由分布在不同地理位置 的数据源动态产生的x m l 数据，可以考虑充分利用不同的w e b 服务提供 者之间的并行执行能力，加快服务集成类查询的执行。 1 1 1关系数据库与x m l 数据 目前x m l 数据的两种最流行的存储方式是关系数据库存储和文件形式存 储。由于关系数据库的技术已经十分成熟，现在的关系数据库系统都具有高性能 的关系查询引擎、良好的可扩展性、安全性和健壮性等优点，所以，人们想到了 采用关系数据库来管理x m l 数据。利用关系数据库系统管理x m l 数据可以保 证x m l 数据的一致性和完整性。与此同时，关系数据库产品在市场上占的比重 较大，包括w e b 上的后台服务器所用的数据库一般也是关系数据库，那么如果 用关系数据库存储x m l 数据的话，就能够比较方便地在两者之间进行数据格式 的转换。所以，用关系数据库来存储和查询x m l 数据是一种方便可行的方法， 而且比较容易实现企业应用的迁移。 用关系数据库管理x m l 数据并非一帆风顺，最主要的原因在于x m l 数据 和关系数据在数据模型上存在较大差异。从数据模型上来看，二者具有不同的数 据模型：x m l 数据是有序的、嵌套的层次结构，而关系数据是无序的二维表平 面结构；x m l 数据是一种半结构化数据，x m l 可以没有预先定义的模式( d t d 或x m ls c h e m a ) ，而关系数据是结构化数据，一定具有预先定义好的模式；第 三，从查询语言上来说，x m l 数据的查询语言包括数据绑定和结构重构两个部 分，查询语言的基本成分是正则路径表达式，而关系数据的查询语言是s q l ，没 第一章裁言 3 有路径表达式的概念，只能表达非常简单的重构。所以，利用关系数据库处理 x m l 数据仍然面i 临许多新的问题和挑战。 存储在关系数据库中的x m l 数据，需要考虑的关键问题是如何设计存储模 式和如何有效地查询数据。研究人员已经提出了各种存储x m l 数据的方法，包 括如何将x m l 映射为关系数据的映射方法2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 ，1 0 ，1 1 】。这些映 射方法可以分为独立于文档的存储方法和依赖于文档的存储方法。用关系数据 库来存储，还有一个重要因素就是如何才能加快查询的执行。 传统的关系数据和x m l 数据存在很大差别，使得在关系数据库系统中高效 地查询x m l 数据成为一个挑战，尤其是路径表达式的计算。x m l 查询语言的 一个重要特征是路径表达式，例如x p a t h 1 2 使用路径表达式来浏览x m l 文档 的嵌套层次结构。在w 3 c 联盟提出的x m l 查询语言x q u e r y 1 3 1 中，路径表达 式不仅是结构化文档上的一个基本操作，而且成为几乎所有复杂操作的组成部 分所以处理路径表达式是x m l 查询计算的一个重要部分。直接处理路径表达 式的简单方法是浏览x m l 文档中所有可能的路径来找出匹配路径表达式的全 部节点元素，这种简单计算方法需要遍历整个x m l 文档，效率低下。尤其在关 系数据库中，路径浏览需要通过连接所有相关的关系表来实现。众所周知，关系 数据库中的连接操作是高代价的，它从一定程度上抵消了使用成熟的s q l 引擎 来处理x m l 数据所带来的优势。 可以通过建立索引来提高查询效率，学术界对于用关系数据库存储x m l 数据后如何提高查询效率而建立相应索引的研究是相当活跃的。索引技术在各 种数据库应用领域被广泛研究。使用索引是一种有效处理路径表达式查询的方 法，它可以减少查询处理时连接操作的次数，连接索引最初在关系数据库中被提 出1 4 。在面向对象数据库领域也提出了很多其它的索引结构以处理路径查询， 例如访问支持关系表f 1 5 1 和连接索引层次 1 6 1 等。 1 1 2 属性文法与x m l 文档的查询和转换语言 随着x m l 在更大范围内被业界采纳作为信息表示和交换的标准数据格式， 越来越多的软件应用平台开始提供支持x m l 数据处理的工具包。在这类工具 中，有很多都支持w 3 c 联盟制定的标准之一x s l t 1 7 1 。x s l t 作为一种x m l 转换语言，已经在实际应用中获得了非常多开发人员的青睐。x q u e r y 是w 3 c 联盟制定的x m l 的查询语言标准1 3 1 。虽然当初设计x s l t 的目的并不是要将 其发展称为全功能的x m l 查询语言，但是实际上x s l t 和x q u e r y 语言都使用 x p a t h 1 2 来进行路径计算，而且x s l t 也可以完成很多类似于查询的操作功能。 在很多情况下，x s l t 和x q u e r y 都被认为是x m l 数据的查询语言。x s l t 的版 本2 0 几乎可以完成和x q u e r y 样多的查询任务，两者的区别在于x s l t 是从 第一章前言 4 文档处理的角度出发，主要基于模式匹配，较容易被文档处理领域的入所接受； 而x q u e r y 采用的是类似于s q l 语言的句法和语义，所以更容易为数据库领域 内的人所接受。x s l t 和x q u e r y 语言都是t u r i n g 完全的语言如果采用它们来 完成查询任务，很难对查询结果的性质，包括查询结果的类型正确性进行分析。 有一类相对简单的x m l 查询以一个x m l 文档作为输入，然后输出另外 一个x m l 文档，但是要求该结果x m l 文档必须符合某预先定义的数据模 式( 可以通过d t d 或者x m ls c h e m a 描述) 。根据具体应用的不同，这类x m l 查询有时候也被称为x m l 数据之间的转换。那么怎么来保证一个x m l 查询产 生的结果文档肯定是符合某个预先定义的文档结构呢? 本质上，这是一个类型推 导的问题，因为d t d 可以被认为是x m l 数据的类型定义。现在有许多研究人 员在研究x m l 数据的类型检查问题 1 8 ，1 9 ，这似乎为结果类型保证的x m l 查 询或转换提供了一种途径。也就是说，在重构数据格式之后再进行类型正确性验 证，比如x m l 查询语言x q u e r y 的r e t u r n 语句可以使查询结果按r e t u r n 子旬规 定的那样组织成特定的x m l 格式。这样就可以通过查询语言提取必要的数据并 重构成x m l 格式，然后再用x m l 的类型检查机制判断重构后的x m l 文档是 否符合某个x m l 结构约束。但是，这种方法的计算代价相当高，而且更糟糕的 是，采用这种方法不能为应该怎样创建合适的x m l 查询提供指导，用户需要不 停地尝试，然后修改错误，直至最后某次侥幸成功。 由k n u t h 提出的属性文法是一个非常出色的表达推导树上计算的形式化工 具 2 0 k 在属性文法中，可以对树结构中的节点标注“属性”，然后通过相关的语 义计算规则来计算这些属性的值。计算过程可能是自上而下的，这些属性称为继 承属性；也可能是自底向上的，这些属性称为合成属性。属性文法已经成功地被 应用在计算机科学的很多领域，比如编译器构造、编程语言语义分析、软件工程 等领域。x m l 数据是层次型的树状结构，其结构约束可以通过一个扩展的上下 文无关语言来表示。d t d 就属于扩展的上下文无关文法，所以，为了保证一个 x m l 查询结果的类型正确性，可以将属性文法扩充成为一种查询范型2 1 。如果 用属性文法来构造查询语言，就可以从一定程度上保证查询结果的正确性。 1 1 3 x m l 数据流的过滤与查询 因为x m l 是i n t e r n e t 上最优秀的数据交换格式之一，近年来，越来越多的 企业和组织开始将x m l 应用在他们的数据管理和数据交换策略中。但是，在 这些应用中除了一些传统的数据管理问题之外，还出现了一些新的阀题：一方 面，x m l 数据要求高效的存储、索引、检索和查询；另一方面，需要提出一些好 的方法和工具来有效地支持来自于不同数据源的x m l 数据集成和企业之间的 数据交换。 第一章前言 5 很多科研、政府和商业领域的应用需要以x m l 格式交换数据。在数据交换 类应用中，以流的方式处理数据是很自然的一个选择。所以，在x m l 数据流上 进行查询处理正变得日益重要。和一般的x m l 查询引擎类似，目前针对x m l 数据流的查询引擎主要是基于内存的。基于内存的处理引擎一个最大的问题是 会导致非常大的内存消耗，即使对一个比较小的x m l 文档，也需要几倍于原文 档大小的内存。这使锝查询引擎不具备较好的可扩展性。一些研究人员已经开始 试图解决这个问题2 2 ，2 3 ，2 4 ，2 5 1 。在实际应用当中，非常大的x m l 文档和无限 长的x m l 数据流变得越来越常见。所以，如何降低查询处理时的内存消耗是一 个非常重要的研究问题。在查询处理的过程中，内存资源过量消耗的部分原因在 于x m l 数据模型引入的额外开销，但是更重要的原因在于查询引擎需要将整个 文档或者整个x m l 数据流从头到尾都读入内存中，并且内存中的结构比原文档 要大好几倍。 近年来，针对x p a t h 的x m l 数据流过滤已经有了很多工作2 6 ，2 7 ，2 8 ，2 9 ， 3 0 ，3 1 ，3 2 b 其中大部分工作都是基于自动机技术的。x q u e r y 作为x m l 的一种 查询语言，几年前由w 3 c 联盟提出，目前已经相当完善，即将成为标准，并且 在工业界和学术界已经有了一些初步的实现。文献2 3 1 的作者提出了一种新颖的 x q u e r y 查询的处理模型( x m l 流处理机) ，其目的是为了有效处理只能顺序读 取的x m l 数据。他们提出一种办法将x q u e r y 转化成为一个x m l 流处理机， 并且进行优化，然后编译成c 语言程序。然而，基于自动机技术所开展的工作虽 然很漂亮却很难和其他的解决途径结合以产生一个更有效的解决方法。此外， 也很难将这些工作推广，以覆盖实际使用的x m l 查询语言全集。 文献f 2 4 1 的工作是基于一个x q u e r y 的参考实现。为了减少查询引擎的内存 消耗，他们首先分析给定查询，然后将源数据中对查询执行没有影响的一部分 数据过滤掉，这样可以减少不必要的内存消耗。然而，从他们的实验结果中可以 看出，很多查询仍然会导致相当数量的内存开销。文献 2 2 3 提出扩展x q u e r y ，他 们引入一个流处理构造子，其目的是为了支持基于事件的查询处理和内存的谨 慎使用。文献 2 2 1 也提出了将x q u e r y 转化成为基于事件的查询的算法，然后可 以在x m l 数据流上很直接地完成完全基于事件的查询执行。在查询优化的过程 中，他们仅仅考虑了结构约束，而没有考虑语义约束。此外，他们的方法能处理 的x q u e r y 语言的子集也非常有限。 在关系数据库领域，完整性约束在数据库设计和查询优化的过程中起到了 非常重要的作用。为了优化x m l 查询处理，x m l 数据集的结构约束和语义约 束同样非常重要。但是到目前为止，还没有哪项关于x m l 查询优化的工作将语 义约束考虑进去了。 第一章前言 6 1 1 4w e b 服务 x m l 已经成为i n t e r n e t 上交换数据的理想格式，而w e b 服务正在成为 | n t e r n e t 上分布式计算的标准组件模块之- - 3 3 ，3 4 ，3 5 1 。x m l 和w e b 服务结合 在一起，共同提供了一个分布式信息管理的框架3 6 1 。随着w e b 服务技术的发 展，很多公司开始将他们的业务功能包装成为w e b 服务，并允许合作伙伴或者 客户访问这些w e b 服务接口。 很多人都认为w e b 服务将带来w e b 的下一次革命，它不仅允许文档和数据 是分布的，而且允许创建分布式的企业应用系统。x m l 是w e b 服务架构的核心 成分，它不仅是w e b 服务或者应用程序之间交换的数据，而且被用来描述一个 w e b 服务3 7 1 。由于x m l 数据本身的灵活性，它能够极大地促进w e b 服务的开 发、部署、访闯和集成等。 在b 2 b 环境中的很多应用系统经常需要无缝地访问来自于不同站点的异质 数据和服务。因为有很多企业或组织都开始把一些业务功能暴露为w e b 服务， 以便合作伙伴或者第三方的应用可以直接访问这些功能，所以一个应用系统常 常需要访问不同服务提供者提供的w e b 服务，它需要无缝地集成这些不同的 w e b 服务。因此，w e b 服务集成在b 2 b 应用中是非常关键的一个问题。从另一 个角度来说，w e b 服务集成也就是针对不同的w e b 服务返回的x m l 数据的集 成。目前，进行服务集成通常是使用c 脊，j a v a ，c + + 等这类通用的编程语言来 完成，这种方法有两个问题：第一，w e b 服务返回结果是x m l 模式定义的类型， 这和面向对象编程语言的类型系统不一样；第二，使用过程语言开发效率低，调 试复杂。所以，需要一种和x m l 模式的类型系统能够很好地匹配的统一语言来 查询和集成分布在不同地理位置的w e b 服务。 1 2 本文的研究内容 本文研究的是x m l 数据的查询、转换和集成的问题。尽管国际数据库学界 对x m l 数据管理的研究已经有八年多的时间了，但是x m l 查询处理和转换仍 然有很多工作要做。不论是底层的存储库，还是x m l 的查询语言，亦或x m l 查 询语言的扩展，都是还需要深入探索的领域。和当初关系数据库管理系统的发展 有些不一样，e f c o d d 的关系理论 3 8 1 使得关系数据管理有了坚实的理论基础， 而x m l 数据的理论基础远远不够完整，目前还没有一个广为接受的数据模型和 查询代数，也缺少一套系统的规范化理论。目前x m l 数据管理的进展情况和关 系数据库刚刚出现时的情形又有几分相似。最初的关系数据库系统因运行效率 问题广受指摘，当前x m l 数据处理的效率较低。所以本文试图在x m l 查询处 理、数据转换和集成方面做一些工作。 第一章前言7 1 2 1 通过索引优化关系数据库中的x m l 查询处理 在将x m l 数据利用关系数据库存储之后，研究如何采用索引技术加快关系 数据库中x m l 路径表达式查询的执行。在研究x m l 查询中的路径索引技术的 基础上，针对x m l 文档及其关系存储，我们提出了一种新型的索引结构，称之 为映射索引，通过预先建立节点之间的映射，可以显著减少s q l 语句中连接操 作的数目。映射索引由两部分组成，一个向导和一个映射集合，而对于映射，我 们设计了有计算简单路径表达式的单步映射，也有用于计算复杂路径表达式的 多步映射。映射索引可以在现有关系数据库系统上有效地处理路径表达式查询。 通过创建映射，可以显著减少连接操作的代价，提高查询效率。但是，若将所有 候选映射都建立起来，需要消耗大量磁盘空间。若仅仅创建一部分映射，则部分 x m l 查询的效率可能得不到改善。所以我们提出了基于代价的路径索引创建。 我们将x m l 数据的统计信息和特定应用的查询负载模式，以及可获得的磁盘空 间综合考虑，提出了基于查询负载来创建路径索引的方法。我们的方法可自动为 特定应用找到近似最优索引模式。因为每建立一个映射，它会给查询执行带来收 益，同时消耗掉部分磁盘空间。索引模式指被选择的映射的集合，它是所有候选 映射组成的集合的一个子集。通过对磁盘开销和查询收益建立代价模型，利用贪 心算法，最终得到近似最优的索引创建方案，即索引模式。实验结果表明，在利 用我们的方法创建了近似最优的索引模式后，查询性能得到了显著的提高。同 时，它们消耗的磁盘空间不会超过预先规定的限制。 1 2 2 以属性文法查询或转换x m l 文档 很多应用都要求x m l 查询所得到的结果符合某预先规定的文档结构，比 如医院b 要从医院a 查询x m l 数据，它要求从a 返回的x m l 文档能够直接 被b 的应用系统处理，所以医院b 希望该返回结果符合它的系统能够处理的文 档结构。x m l 文档的结构可以认为是其类型，通过d t d 或者x m ls c h e m a 来 表示，而具体的文档数据是其数据实例，所以在上述的应用场景下，用户的要求 是x m l 查询结果的类型必须符合预先指定的类型。我们称以上问题为类型保证 的x m l 查询处理。类型保证在一定程度上保证了查询结果的正确性。由于针对 x m l 数据的事后类型检查算法是指数时间复杂度的，不能实用，我们需要探讨 其它途径。 在本文中，我们用d t d 来表示x m l 查询结果所要求的数据类型。d t d 是 一种扩展的上下文无关语言，我们对其中的元素类型标注必要的属性，补充适当 的语义规则，这些语义规则同时也是这些属性的计算规则。这样，我们就可以得 到一个属性文法。属性文法是一个非常强大的形式化工具。通过补充不同类型的 第一章前言 8 语义规则，可以构造出针对不同应用需求的查询语言。如果将s q l 语句作为语 义规则，那么它可以从关系数据库中查询数据，最后返回x m l 文档 2 1 1 。因为本 文考虑的是x m l 数据的查询处理，所以我们考虑将x q u e r y 或者x s l t 语言的 子集作为语义计算规则，这样就可以对x m l 数据源进行查询，而且能够保证返 回的结果一定是类型正确的。 那么，引入属性文法作为一种新的x m l 查询语言，会不会增加用户额外的 学习负担呢? x q u e r y 和x s l t 都是非常复杂的x m l 查询语言，用户要想掌握 它们是需要付出较长的学习时间的。但是，一个属性文法由多条产生式构成，它 将创建一个较复杂查询的任务分解成了创建若干个较简单查询的任务。所以，这 种分治的策略肯定会减轻用户创建查询时的难度。由于属性文法自身内在的特 点，比较容易以图形化的方式来设计一个合法的、而且逻辑正确的属性文法。通 过采用属性文法，减轻了用户的负担，但是却给查询处理器带来了更多的挑战， 所以我们必须研究优化这类查询的方法。我们将在第三章讨论缓存、图规约和路 径扩展等优化技术。 我们将属性文法作为新的x m l 查询范型，兼具理论价值和实际应用价值。 类似技术将可以应用于电子商务、电子银行、数字图书馆、企业信息交换和集 成、健康医疗和保险等领域。 我们首先采用x q u e r y 语言作为属性文法的语义计算规则，并且记所得到的 查询语言为x t g 。x t g 扩充了查询结果的d t d ，我们将给出x t g 的定义，并 详细讨论其查询计划，最后讨论优化策略，包括中间结果缓存、图规约，还有路 径扩展等优化方法。我们还通过实验比较了不同查询优化方法的效果。 其次，我们采用x s l t 语言作为语义计算规则，记所得到的转换语言为 g 2 s t 。我们提出g 2 s t 的目的是为了转换地理信息数据g m l 3 9 1 ，对g m l 数 据的转换和对一般x m l 数据的查询有些不同。人们希望从g m l 数据得到s v g 数据4 0 ，并将其在浏览器中展现出来。这种转换的目的主要是为了展现数据， 相对于查询语言x q u e r y ，x s l t 更适合于这个功能，所以此时我们采用了x s l t 语言作为语义规则。我们的初步实验结果说明了g 2 s t 途径的有效性。 1 2 3可扩展的x m l 数据转换 如何对x m l 数据流进行查询处理已经成为一个很重要的研究问题。x m l 数据流处理技术有两个最重要的应用场合。第一，网络上的x m l 数据通常是以 流的形式传送；第二，在处理文件系统中的大规模x m l 数据时，如果要求只扫 描一次数据文件，那么也可以将它们理解成x m l 流。我们将研究在给定源数据 模式的情况下，怎么来高效地处理x m l 数据流。 第一章前言 9 在进行x m l 查询处理时，如果数据集的大小和内存大小可以相比拟，或者 甚至于比内存还要大的话，那么就会导致虚拟内存的大量使用，进而导致系统出 现颠簸，性能急剧降低。为了部分地解决这个问题，我们提出一个全新的概念， 流处理模型( 野w ) 。该流处理模型支持在x m l 文档上，尤其是非常大的x m l 文档上执行x s l t 计算。采用流处理模型，在给定源文档的d t d 结构口的情况 下，x s l t 程序c 将被转化成为很多事件处理器。在最开始的时候，结果文档为 空。随着扫描过程的进行或者源x m l 数据流的不断流入，事件处理器的输出片 断将被逐渐添加到已有部分结果文档的后面。在整个查询执行过程中，采用流处 理模型的x s l t 计算引擎不需要利用额外的数据缓存。这个方法既能接受很大 的文档作为输入，也能产生很大的输出结果。我们对流处理模型进行了实验分 析与对比，实验结果显示了流处理模型的巨大优势。相对于现有的x s l t 处理引 擎，采用流处理模型能够将执行效率提高2 到1 0 倍。同时，实验数据还表明我 们提出的流处理模型具有很高的可扩展性。 我们的这项研究成果可以被应用在很多场景下。我们的流处理模型既能处 理文件系统中很大的x m l 文件。也能处理从网络上接收到的或者是动态产生的 x m l 数据流。在w e b 服务的环境中，不同的应用系统之间通过交换s o a p 消息 来完成数据交换任务。s o a p 消息是瞬时数据，不适合建立索引。我们提出的方 法可以很好地用来处理s o a p 消息。在对等计算环境中，每一个节点可能同时 承担数据提供者和数据消费者的角色。部分节点还需要承担路由数据的任务。如 果数据是x m l 格式的，节点可以通过x m l 查询来请求数据。在中间路径上的 节点知道其他节点的请求，因此它可以从一个节点接收x m l 数据流，进行一些 较简单的处理，比如过滤、转换、压缩或者解压缩等，然后再转发给其他节点。 1 2 4 集成w e b 服务 在b 2 b 应用中，w e b 服务集成是一个