（计算机软件与理论专业论文）基于物化视图的xml存储和查询.pdf

基于物化视图的x m l 存储和查询 ，、。正以其自描述性、可扩展性以及计算机易处理性迅速取得了学术界和企 业齐的广泛认同，成为i n t e r n e t 上数据表示和交换的标准。随着描述领域交换信息 d t d 的不断制订，遵循d t d 的x m l 应用也不断增加：许多应用对查询的实时响 应也提出了更高的要求。探索此类x m l 文档的有效存储和查询方法已成为数据库 领域研究的热点，并具有广泛的实用价值。 目前对该问题比较有效的解决途径是基于结构的映射，但大多对任何d t d 都 采用相同的、系统预定义的映射方法，无法根据具体应用作适应性调整；同时x m l 应用的灵活性和查询的有效性。该模型提供了根据具体应用的数据分布和查询模式 特征调整从x m l 到关系模式映射的能力，从而提高系统的存储和查询效率。其灵 活性主要体现在以下方面：视图中包含的元素集可以根据常用查询模式的查询元 素组合作调整。视图中存储的结构信息可根据应用作定制。作为特例之一，可以 定义功能等价于x m l 与半结构数据的存储及查询研究中“路径索引”的视图。 可就是否将具有多个父元素的子元素信息映射到父元素所在视图作出选择。可就 是否保存某一元素的顺序语义按照应用需求作出取舍。由于映射模式的生成着眼于 提高常用查询的效率，因而从统计的观点来看，本文提出的存储和查询系统将具有 较短的系统平均查询响应时间。 f f 查询执行模块的目标是充分利用视图中存储的数据和结构信息，产生符合x m l 查询语义并具有较优代价的查询执行方案。但灵活的映射模型极大地增加了查询系 统既面临的复杂性，重写查询中视图集的选择涵盖了包含路径索引的查询优化问 题玉本文定义了用于表示x m l 查询语义和操作的x m l 查询代数图x q a o 。算法通 过对该代数图的各种变换产生不同的查询执行方案，计算并选择具有最小估计执行 代价的方案。针对x q a g 中对关系库操作的部分，本文设计了以加权估计执行代 价为标准的g r e e d 算法来解决转化s q l 查询中视图集和连接表达式的选取问题。 实验证明本文提出的映射模型和查询执行算法有效地提高了系统的查询效率。 关键字 x m ld t d 关系模式 、_ 查询优化 基于物化视图的x m l 存储和查询 a b s t r a c t x m li s e m e r g i n ga st h es t a n d a r dd a t ae x c h a n g ef o r m a tf o ? i n t e r n e t b a s e db u s i n e s s a p p l i c a t i o n s w i t hm a n yi n d u s t r y d o m a i n s e s t a b l i s h i n g & t e a s p e c i f i cd t d , a p p l i c a t i o n s w h o s ex m ld o c u m e n t sc o n f o r mt od t d “e i l l c r e a s i n gs h a r p l y a tt h es a m et i m e ，m o r e a n dm o r e a p p l i c a t i o n s c a l lf o rr e a l d m eq u e r y r e s p o n s e i th a s c r e a t e dt h en e e dt oe x p l o r ea n e f f e c t i v es t o r a g ea n d q u e r y m e t h o df o rt h i sk i n do fx m ld o c u m e n t s w h i l es t r u c t u r e - b a s em a p p k a gm e t h o di sav i a b l ea l t e r n a t i v et os o l v ea b o v e m e n t i o n e d p r o b l e m ，d l e y u s ef i x e da n dh a r d c o d e m a p p i n g , w h i c h i sp r e d e f i n e db y a l g o r i t h m ，f o re v e r y a p p l i c a t i o n s ot h em e t h o dc o u l dn o ta d j u s tt os p e c i f i ca p p l i c a t i o n a n dt h e ”f r a g m e n t ” p r o b l e m ，w h i c h i si n d u c e d b y t h em i s m a t c ho fx l v l ld o c u m e n tm o d a la n dr e h f i o n a lm o d a l , h a si m p a c t e dt h ee f f i d e n c yo fq u e r y g r e a t l y t h e r e f o r e ，t h i sp a p e rp r o p o s e s am a t e r i a l i z e d - v i e wb a s ex m l s t o r a g e a n dq u e r y m o d a l a p p l i c a t i o n - o r i e n t e df l e x i b i l i t ya n dq u e r ye f f i c i e n c ya c et w o r e m a r k a b l ec h a r a c t e r so f i t t h em o d a lo f f e r st h ec a p a b i l i t yt o a d j u s tt h em 8 p p i l l g ，f r o mx m l t or e h t i o n a ls c h e m a ， a c c o r d i n gt ot h e d a t ad i s t r i b u t i o na n d q u e r yp a t t e r n so fa p p l i c a t i o n a sar e s u l t , i td e c r e a s e s a v e r a g eq u e r yt i m eal o t i t sf l e x i b i l i t i e sa r ee x p r e s s e db yt h ef o l l o w i n g s t h ef i r s t , e l e m e n t s s e ts t o r e di ne a c hv i e wc a nb et u n e d t h e s e c o n d s t r u c t t t t ei n f o r m a t i o no fx m l d o c u m e n t sc a nb em o d u l a t e d a sas p e c i a l u s a g ew a y , v i e w s ，w h i c hf u n c d o n a s ”p a t hi n d e x ” i nt h er e s e a r c ho fx m la n ds e m i - s t r u c t u r e dd a t a s t o r a g ea n dq u e r y , c a nb ed e f m e d t h el a s t , i tc a nb ec h o s e nw h e t h e rt os t o r eo r d e rs e m a n t i c so fe l e m e n t s b e c a u s e 山ec r e a d o no f m a p p i n g m o d a lf o c u s e so ns p e e d i n g “pf r e q u e n tq u e r i e s ，f r o mt h ep o i n tv i e wo fs t a t i s t i c s ， t h e s y s t e m o f f e r e di nt h i sp a p e rc a na c h i e v ee x c e l l e n ts y s t e m q u e r ye f f i c i e n c y t h ea i mo fq u e r ye x e c u t i o nm o d u l ei st o f u l l yu t i l i z ed a t aa n ds t r u c t u r a li n f o r m a t i o n s t o r e di nv i e w st oc r e a t ee x e c u t i o np l a n ，w h i c hn o to n l ys a t i s f i e s o r i g i n a lq u e r ys e m a n t i c s b u ta l s oh a sm i n i m a le x e c u t i o nc o s t b u tf l e x i b l em a p p i n gm o d a li n c r e a s e s q u e r y r e w r i t i n g c o m p l e x i t yg r e a d y i nt h i sp a p e r ，w ed e f i n ex q a g t oe x p r e s sx m l q u e r ys e m a n t i c sa n d o p e r a t i o n s ，d e s i g nm a n y t r a n s f o r m so ni tt og e tv a r i o u s q u e r ye x e c u t i o np l a n s ，c o m p u t ea n d s e l e c tt h ep l a nt h a th a sm i n i m a le s t i m a t ec o s t t h i sp a p e ra l s op r o p o s e sg r e e d a l g o r i t h mt o c o n v e r tr e l a t i o n a lo p e r a t i o n si nx q a gt os q l i t a d o p t sw e i g h t e de s t i m a t ee x e c u d o nc o s t a st h es t a n d a r df o rt h es e l e c t i o no fv i e ws e ta n d i o i n - e x p r e s s i o nu s e d i nr e w r i t i n g q u e r y e x p e r i m e n t sh a v ep r o v e dt h a tt h em a p p i n g m o d a la n d q u e r ye x e c u t i o na l g o r i t h mh a v e i m p r o v e ds y s t e mq u e r ye f f i c i e n c yr e m a r k a b l y x m ld t d r e l a t i o n a ls c h e m a q u e r yo p t i m i z a t i o n 基于物化视图的x m l 存储和查询 第二节、示例描述 3 2 第三节、x m l 查询代数图( x q a g ) 3 4 第四节、查询方案生成( e x e e u d o n p l a n g e n e r a t i o n ) 3 7 a消除关联连接( d e c o r r e l a t e ) 3 7 b x m l g r a p h 的合并 3 9 c标签与计算操作分离 4 2 d 算法总结 4 5 第五节、g r e e d 算法 4 5 a 数据库统计信息和代价估计公式 4 6 1 单个视图访问的代价估计 4 6 2 视图连接的代价估计 4 6 bg r e e d 算法 4 7 1 查询重写中部分查询方案p s 的选择标准( 讳，e c ) 4 8 2 算法执行过程 4 9 3 g r e e d 算法的复杂度 5 0 第六节、相关研究比较 5 0 第五章、试验结果及分析 5 2 第一节、试验配置 5 2 第二节、试验结果及分析 5 2 a试验x m l 文档库及其映射定义5 2 b 存储及查询性能分析 5 4 1 存储性能分析 5 4 2 查询性能分析 5 5 3 g r e e d 算法性能 5 6 第六章、总结 致谢 参考文献 图表 图表1 ： 图表2 ： 图表3 ： 图表4 ： 图表5 ： 图表6 ： 图表7 ： 图表8 ： 图表9 ： 图表1 0 幽表1 1 图表1 2 幽表1 3 描述出版信息的x m l 文档 2 描述出版信启、的d t d ( p u b l i c a t i o n ) 3 l o r e l 的查询表达 4 x o u e r y 的查询表达 4 x m l 存储和查询系统体系结构图 1 1 s a l e s 对应的缺省d t d 1 3 一个针对x m l 文档和关系库的查询 1 4 示例d 1 3 3 圈 1 8 实例x m l 文档树 2 0 映射定义文什的d t d 2 1 一个映射定义文件的例子 2 1 路径索引视图映射 2 4 非内嵌的映射定义 2 5 娼 基于物化视图的x m l 存储和查询 图表1 4 图表1 5 图表1 6 图表1 7 图表1 8 图表1 9 图表2 0 图表2 1 图表2 2 图表2 3 图表2 4 图表2 5 图表2 6 ： 定义 查询执行模块体系结构 3 1 表示电影信息的d t d ( m o v i e ) 3 3 示例查询 3 3 示例查询对应的初始x q a g 3 6 示例查询的一种d e c o r r e l a t e 方式 3 8 、 图表1 7 中x q a g 的一种变形 4 0 图表1 9 变形后的x q a g 对应的d e c o r r e l a t e 4 1 将图表1 8 中部分x q a g 的标签与计算操作分离的两种方法 4 3 试验x m l 文档集的d t d ( m o v i e 和i n d e x )5 3 m o v i e 和i n d c x 文档库中各种映射占据的磁盘空间 5 4 m o v i e 和i n d e x 文档库不同映射定义的查询性能5 5 引入a c t o r _ d i r e c t o r 视图的查询性能 5 6 不同查询重写算法的性能 5 7 定义1 ：d t d 类型结构1 7 定义2 ：d t d 图1 8 定义3 ：x m l 文档图 1 9 定义4 ：逻辑路径表达式( l o g i c a lp a t he x p r e s s i o n ) 2 6 定义5 ：逻辑路径表达式前缀( l o g i c a lp a t hp r e f i x ) 2 7 基于物化视图的x m l 存储和查询 第一章、背景及相关研究 第一章、背景及相关研究 经过近十年的发展，互联网已经成为新经济时代的标志。随着国家信息高速公 路及各地信息港计划的实施，i n t e m e t 在地域、用户、功能和应用等方面不断得到 拓展，企业网络化、商务电子化、信息自动化无不以i n t e r n e t 为基础平台。同时， 当今的i n t e r n e t 又面临信息格式松散、缺乏必要标准和元数据的问题，各内容提供 者和服务提供者大多以自治的方式存在。 w 3 c 在1 9 9 8 年制定了x m l 的标准，启动了整个i n t e m e t 信息标准化的进程。 x m l 以其自描述性、可扩展性以及计算机易处理性迅速取得了学术界和企业界的 广泛认同，它日益超出其作为标注语言的初衷而成为i n t e r n e t 上数据表示和交换的 标准。四年来，成千上万的x m la p p l i c a d o n 被定制，许多专业领域都有了满足各 自不同需求的x l v i l 描述标准，数字图书馆元数据描述标准d u b l i n gc o r e 就是其中 之一。 因此，x m l 数据的有效存储和查询给数据库研究和商用系统开发提出了令人 兴奋的机遇和挑战。随着x m l 应用中信息的数量级不断加大，同时众多商用领域 对系统稳定性要求的不断提高，对x m l 的存储系统提出了更高的要求。与此同时， 不同于h t m l 的关键字检索，x m l 文档的一个重要特征是具有结构，并且能对其 进行基于内容的结构化检索。随着x m l 应用服务用户的不断增加，查询的实时响 应对许多应用来说也成为系统成功的必要条件之一。注意到很多实际应用具有其相 对固定的应用特征( 包括x m l 文档的数据分布和查询模式等) ，数字图书馆元数据 镪存储稚查询就是央邙之一。翻伺才能充分翻用x m l 的文档结构以及应用的数据 分布和查询模式特征设计番效的x j 文档存储模跫以提高存储和查询的效率不 同的存储模型隐含了不同的查询执行算法，同时只有当查询执行算法较好地利用了 存储模型的特征时才能体现该模型在查询效率上的优越性。奶匆才铹瑟劳存裁的查 询执行算法通过对x m l 文档存储模挚中毡含的数据和结构信息的充分翻甬得飘 舆存最辔实厮残存旅擘矽香绚巍行艿亲p 以上这些就构成了本文的主要研究课题。 下面首先简要介绍x m l 标准，然后对当前x m l 文档存储和查询相关领域的研 究作概括和总结。 基于物化视图的x m l 存储和查询 第一章、背景及相关研究 第一节、x m l 及d t d 筒分 a x 匝 x m l ( e x t e n s i b l e m a r k u pl a n g u a g e ) b p s 9 8 1 是在i n t e r n e t 上表示和交换信息的层 次文档模型。一个x m l 文档包含了从根元素开始的嵌套元素结构。每个元素有一 个标签( t a g ) 与之相对应，除了字符串数据，它还可以包含属性值对和嵌套子元 素。同时包含字符串数据和嵌套子元素的元素被称为具有混合内容( m i x e d c o n t e n t ) 。x m l 中的元素标签必须良好嵌套，这样的x m l 文档是良构的 ( w e l l f o r m e d ) 。图表1 给出了一个描述出版信息的x m l 文档。其中根元素a r t i c l e 包含m d e 、d a t e 、a u t h o r 等一系列子元素，并且 a u t h o r 元素还包括自己的子元素 集。值得注意的是，一个 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 元素( 子元素) 之间是一对多的关系。每个 a u t h o r 元素有 一个名为。i d f 类型为i d 的特殊属性，它可以在文档范围内唯一标识该元素。与之相 对应的是类型为i d r e f 的属性，它在逻辑上指向具有相同i d 属性值的元素。在本 例中，c o n t a c t a u t h o r 元素的c i d 属性指向了论文的第一作者( 属性i d f 值为a 0 1 的 a u t h o r 元素) 。另一个值得关注的现象是描述论文引用信息的c i t e 元素递归嵌套了 另一个a r t i c l e 元素( a r t i c l e 一 c i t e a r t i d e ) 。 图表1 ：描述出版信息的x m l 文档 s t o r i n g s e m i s t r u c t u r e dd a t aw i t hs t o r e d t u n e1 9 9 9 a t i n d e u t s c h a d e u t s c h g r a d i e n t c i s u p e n n e d u m a r yf e m a n d e z m f f r e s e a r c h a t t c o m a n s w e r q u e r i e su s m gv i e w s 该类型信息可从文档所遵从的d t d 定义中得到。 e f i t 基于物化视图的x m l 存储和查询 第一章、背景及相关研究 b d t d d t d ( d o c u m e n t t y p ed e s c 邱d o n ) 田p s 9 8 1 规定了x m l 文档的结构，可以视为 x m l 文档的模式。d t d 通过描述子元素和属性的名字及类型来定义x m l 元素的 结构。嵌套子元素的出现次数用类似正则表达式的如下符号规定：+ ( 包含零或多 个元素的集合) ，+ ( 至少包含一个元素的集合) ， ( 包含零或一个元素) 和没有修 饰( 包含且仅包含一个元素) 。同时d t d 也严格规定了x m l 文档中元素的子元素 的出现顺序，即按照元素定义的正则表达式顺次展开。正如前- d , 节所述，元素允 许包含至多一个类型为i d 的属性，由该属性在文档域内唯一标识该元素，同时其 他元素也可以通过类型为i d r e f 的属性对其加以引用。i d r e f 属性并没有指明该 属性所指向的元素类型，在这一意义上说，i d r e f 属性是没有类型的。属性定义中 可以用# r e q u i e d 和# i m p l i e d 等修饰符类似描述其在出现次数上的约束，同时 属性的取值范围也可在d t d 中定义。一个良构且符合d t d 的定义的x m l 文档被 称为是有效的( v a l i d ) 。 图表2 ：描述出版信息的d t d ( p u b l i c a t i o n ) l e l e m e n t ! e l e m e n t fe l e m e n t ! e 】点m e n t ! e l e m e n t ( 1 a r i s t l e l e m e n t j e l e m e n t l e l e m e n t l t n i s t t i t l e拌p c d a t d a t ep c d a t a a u t h o r fn a n l e 。e m a l l 为 a u t h 0 1i di d j r e o u i r e d n a m e群p c d 钔队 e m a r lp c d a t a c o n t a c t a u t h o re m p r y c o n m c 乞a u t h o tc i d i d r e f # r e q u i r e d c i r ea r t i c l e * c k e f o t r e a t ( a c mli e e e j i m p u e d 图表2 给出了描述出版信息的d t d 。根据定义，a r t i c l e 元素必须包含一个一t i f f e 。 元素，而。d a t e 元素则是可选的( 这在符合该定义的x m l 文档( 图表1 ) 中已有所 表现) 。同时，每个a r t i c l e 元素所包含的子元素必须按照t i d e 。、d a t e ( 如果存在) 、 基于物化视图的x m l 存储和查询 第一章、背景及相关研究 一个或多个a u d l o r i 等的顺序出现。由定义可见， a u t h o r 元素可以同时成为b o o k 和a r t i c l e t 元素的子元素，且在这两种情况下，父元素都必须为至少包含一个 a u t h o r 元素( 可以有多个) 。每个一a u t h o r 元素g g 须包含一个类型为i d 的属性，而每个 - c o n t a c t a u 山o f 元素的类型为i d r e f 的属性。d d 也是强制出现的( # r e q u i r e d ) a 元素c i t e 的属性f o r m a t 只能取值为 a c m 或i e e e 。 第二节、x h 也查询语言 当前已经有很多有关x m l 查询语言的提议【a q m + 9 7 c r f 0 0 1 e - l s 9 s lp f f + 9 8 c f l + 0 1 ，也有对查询语言总体要求的描述d 田和对现有方案的比较【b c 0 0 1 。所有 的这些查询语言都包含能在x m l 文档的嵌套结构中导航的路径表达式语言构造。 另外，其中的一些具有创建嵌套的x m l 形式结果集的构造功能。由于本论文的研 究方向不在于x m l 的查询语言，这一部分仅选择介绍对理解本文的皿。存储和查 询系统相关的语言l o r d a q m + 9 7 和x q u e r y c f m + 0 1 1 ，并且下面关于查询语言的 描述只向用户提供一个高层的概况，具体细节请参考相关文档( 【a q m + 9 7 】 【c f m + 0 1 】) 。 图表3 ：l o r e l 的查询表达 假设针对前一小节的d t d ，有“找出所有作者名为ns u c i u 的论文的题目” 的查询。图表3 给出了使用l o r d 语言对这一查询的表示。l o r e l 的查询类似s 0 l ， 也包括s e l e c t 、f r o m 和w h e r e 子旬。f r o m 子句将变量a r t i 绑定为所有 a r t i c l e 元素； 对于每一个a r t i 的绑定，w h e r e 子句使用在n a m e 元素上的谓词对其作过滤，只有作 者之一为ns u c i u 。的绑定有效；s e l e c t 子句对有效变量绑定( 即符合条件的a r t i c l e 元素) 根据选择元素的路径表达式。t i d e 产生查询结果。在l o r e l 的路径表达式中有 隐含的存在语义。例如在本例中，如果a r t i c l e 元素的任意一个a u t h o r n a m e 子孙元 素等于1 3 s u c i u 则谓词为真。 图表4 ：x q u e r y 的查询表达 基于物化视图的x m l 存储和查询 第一章、背景及相关研究 x q 。卯是当前w 3 c 组织提出的查询语言的工作草稿，将来可能成为x m l 查 询语言的标准。图表4 显示了使用x q u e r y 表示的查询，其中的f l w r 表达式 ( f o r l e t w h e r e r e t u r n 的缩写) 被用于查找和构造一个p u b l i c a t i o n 元素( 查询结果 集x m l 形式的打包) 。首先，每个a r t i c l e 元素被依次绑定到变量s a r t i ；然后，对每 一个变量绑定，使用) a 山 c d 9 9 1 规定的语义沿路经表达式导航到元素n a m e ( $ a r d a u 1 0 r n a m e ) ，通过检查对该s a r t i 绑定( 一个 a r t i c l e 元素) 的n a m e 子元 素集中是否存在一个元素取值为d s u c i u 来对此a r t i c l e 元素作筛选。如果满足条件， 则取得相应b o o k t i t l e 子元素的字符串值，并按照结果集构造要求的x m l 形式返回 ( 构造p u b l i c a t i o n 结果元素) 。 随着x m l 作为数据表示和交换标准被产业界的不断接受，数据库领域对如何 有效的存储和查询x m l 文档的研究也不断走向深入。不仅有文章对x m l 文档存储 系统的要求作出概括 s t 0 1 1 ，还有研究对各种不同的存储方法作比较性能分析 旷o j + o o 】 f k 9 9 ，为公正、客观地评价和比较各种系统的效率，一系列b e n c h m a r k 也相继提出0 3 r o l 】i y s 0 0 li s w k 0 1 】。下面首先对目前提出的各种x m l 存储方法从较 高的层次上进行分类，然后针对使用关系数据库系统作为x m l 存储底层系统的各 种方法作比较细致的介绍和优缺点概括。 a 存储方法分类 以x m l 文档存储系统底层所使用的数据库系统作为分类标准，存储方法大致 分为四类。半结构存储系统，典型代表有l o r e l m a g + 9 7 和商用系统e x c e l o n 、 t a m i n o s w 0 0 等。它们大多是基于早期对半结构数据存储和查询的研究，并针对 x m l 文档的特性作相应的调整。系统主要针对的应用是为缺乏规整的文档结构定 义( 没有d t d ) 的半结构或无结构的x m l 文档提供存储和查询功能。由于这种方 法没有利用d t d 提供的模式信息，因而对存在d t d 而且所有文档都遵从d t d 定 义的应用而言查询效率较低。面向对象数据库系统( o o d b m s ) ，一个版本的l o r e l 探讨了使用0 ：( 一个o o d b m s ) 作为其底层系统的可行性。 因为对象关系模型 的嵌套结构与x m l 的嵌套文档模型匹配程度较好，对象关系数据库系统 ( o b j e c t r e l a t i o n a ld b m s ) 也是一种选择 s y u 9 9 1 k m 0 0 1 。然而，以上两种方法都 有如下的共同的缺点：相应的数据库系统既不被广泛使用也缺乏有效处理大规模数 据的能力，系统稳定性和效率不能得到保证：同时该存储方法缺乏与大量现有数据 基于物化视图的x m l 存储和查询 第一章、背景及相关研究 ( 存储在商用关系数据库中) 的有效集成。脚关系数据库管理系统( r d b m s ) 也许 是更有希望的一种方法。相对于其他几种方案，它具备以下优点：关系库系统和 技术经过数十年的发展和完善，沉淀了存储和查询技术的精华，为应用提供了较高 的效率、系统稳定性、可移植性和可扩展性。鉴于w e b 上的数据现在、并且将来 也将存储在关系库的情况，使用r d b m s 有利于x m l 文档和原有数据的无缝集成。 可以使用相同的底层系统满足同时针对x m l 文档和关系数据的集成查询，这也正 是部分实际应用的需求。当然，由于x m l 文档模型与关系数据库模型的较大差异 也使得如何有效地将x m l 数据存储在关系库中成为研究的一个热点，本文所作的 研究也正是在此方向上。 b x m l 文档到关系库的映射方法 l 。扶x m l 文档勤关系库和半结构存储 s t o r e d i f d f s 9 9 研究了如何在没有d t d 的情况下将x m l 数据存储到关系库 的问题。它通过对x m l 文档数据分布和查询模式的数据挖掘算法抽取出关系库模 式和许多属于半结构存储的“溢出图”定义。虽然在该数据挖掘算法中考虑了一部 分查询模式信息，但从总体来看，它还是着重强调存储的有效性。讧l 文档的内 容被分割到关系表和众多“溢出图”中，因而为满足一个x m l 查询需要大量关系 表和“溢出图”的连接，极大地降低了查询效率。 2 基于模型的映射( m o d a l - m a p p i n g ) 顾名思义，基于模型的映射就是从x m l 文档模型出发定义从x m l 到关系库的 映射，它们使用固定的关系库模式来存储x m l 文档的结构和内容，在映射的过程 中不考虑或较少考虑具体的d t d 定义( y a o q s k w 0 0 k m 9 9 】 g e w 0 0 【h h w 0 1 】) 。其中e d g e k m 9 9 和x p a t e n t 【h h w 0 1 是其中比较典型的分别以边和节点 为中心的两种方法。每个x m l 文档可被建模为一个有向图。假设e 0 e 一一e 。为一条 数据路径，；厶。为该数据路径的标签路径，其中e 。为虚拟的根节点，e ，是元素 的唯一标识i d 。 e d g e 方法中关系模式只包含一张表e d g e ( s o u r c e ，t a r g e t , l a b e l , o r d i n a l ，f l a g ， v a l u e ) ，由此表保存皿，数据图的所有边信息。其中每条边由节点标识符对( s o u r c e t a r g e t ) 表示，l a b e l 字段记录边的标签，o r d i n a l 表示这条边在兄弟中的顺序，f l a g 指示t a r g e t 字段为内部元素对象引用还是指向字符值。这种以边为中心的方法只维 护边的信息，因而用户查询中路径表达式的计算需要相应边的连接，而连接是关系 基于物化视图的x m l 存储和查询 第一章、背景及相关研究 库基本操作中代价较高的一个，因而查询效率不高。作为这种方法的一个变种， m o n e t s k w o o 】映射将具有不同标签的边映射到不同的关系表中，其字段只包括父、 子元素，标签路径由一系列表的名字决定。同时建立一个用于存储文本和属性值的 表。但如此一来，数据库中的表数目急剧增加( 等于d t d 中元素的数目+ 1 ) ，难以 处理正则表达式查询，对x m l 文档结构可能发生的变化的情况也难于处理。 x p a r e n t 可视为以节点为中心的映射方法，它包括四个表：l a b e l p a t h ( i d , l e n , p a 出) ，d a t a p a t h ( p i d ，g i g ) ，e l e m e n t ( p a t h i d , d i d ，o r d i n a l ) ，d a t a ( p a t h i d , d i d ，o r d i n a l ， y a l u e ) 。它通过两个不同的表l a b e l p a t h 和d a t a p a 出显式地支持标签路径和数据路径。 相对以上两种方法，它能比较好地支持正则表达式查询。 对一个形如d b g r o u p m e m b e r a g e 2 0 l n a m e 的简单查询，f d g e 需要3 次连 接、m o n e t 需要4 次连接、x p a t e n t 需要5 次连接，它们所需查询响应时间很长。由 此可见，基于模型的方法的最大优点在于其d t d 无关性，比较适合没有d t d 或 x m l 文档结构可能动态改变的应用，但其查询的低效率对具有d t d 的应用来说是 无谓的损失。 3 基于结构的映射( s t r u c t u r e m a p p i n g ) 与基于模型的映射方法相对比，基于结构的映射方法根据对定义x k m l 文档结 构的d t d 的理解产生到关系库模式的映射i s t g + 9 9 】 g e w 0 0 m f 0 1 ，其中最具影 响的研究是 s t g + 9 9 】。在 s t g + 9 9 提出了三种从d t d 到关系模式的映射方法： b a s i c l n l i n i n g 、s h “e d i l l l i n i n g 和h y b f i d l n l i n i n g ，作者同时指出b a s i c i n l i n g 方法性能明 显没有后两种方法好。 在d t d 元素类型定义中，用+ 和+ 修饰的子元素可以在同一父元素中包含多个， 即父元素和该子元素是1 ：0 - * 或1 ：1 - * 的关系。在关系数据库理论中，为减少数 据冗余和可能的更新异常，这样的一对多关系用父、子表和外键来建模。 s h a r e d l n l i n i n g 和h y b f i d l n l i n i n g 正是基于这样的思想。d t d 中元素的类型定义可以 用d t d 图来表示，其中结点表示元素，有向边从父元素结点指向子元素结点，边 上标记的”表示父子元素的一对多关系。为减少计算路径表达式所需的表连接次数， 算法尽量将非对多关系的子元素映射到父元素所在的同一个关系表中( i n l i n i n g ) 。 但为了正确处理元素结构定义中可能出现的递归( 如前面例子中的a r t i c l e 一 c i t e 一 a r t i c l e ) ，如果在i n l i n i n g 过程中出现环，则不再将后续元素映射到同一表中，并使 用字段p a f e n f 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 m i n g 的区别。前者将公共子元素映射到单独的表 基于物化视图的x m l 存储和查询 第一章、背景及相关研究 中，后者则将其与父元素存储在同一个关系表中。s h a r e d l n l i n g 方法用于前例图表2 表示的d t d 将产生如下的关系模式( 主要部分) ：b o o k ( b o o k i d ，b o o k t i f l e ) ， a r f i d e ( a r t i c l e i d ，p a r e n t i d ，p a r e n t c o d e ，t i t l e ，d a t e ，d d , f o r m a t ) 和a u t h o r ( a u t h o r l d ， p a r e n t l d ，p a r e n t c o d e ，n a m e , e m a i l , i d 0 对于一个给定的x m l 查询，该映射方法比基于模型的方法需要更少的表连接， 因而具有更高的查询效率。但映射方法的前提是应用存在一个相对比较固定的 d t d ，其适用环境比基于模型的殃射方法窄。同时，正如作者自己所指出的，尽管 这两种映射方法在转化的关系库查询中所需的表连接次数已相对减少，但由于x m l 文档结构模型和关系模型的失配，还是造成了“分片( f r a g m e n t ) ”问题。d t d 被 映射到了很多关系表，为满足一个用路径表达式表示的简单x m l 查询也需要大量 表的连接和关系库查询，查询效率对一些实时的应用来说还有待提高。 第二章、映射模型及系统概述l 对本文所提出的基于物化视图的x m l 存储 和查询系统作概括性的介绍，其中分析了映射模型的合理型、描述了系统的体系结 构、同时简要叙述了在该映射模型下x m l 数据存储和关系库原有数据的集成。 k 第三章、数据模型及关系模式生成目首先定义了系统中使用的x m l 文档和 d t d 的数据模型，该模型是x m l 数据的关系库存储和相应查询执行的基础。然后 详细介绍了从x m l 到关系库的映射定义，分析了该映射定义为充分利用应用的具 体特征所提供的灵活性。同时，根据映射定义产生具体的关系库物理模式也在该部 分中介绍。 由于本文所提出的映射模型的灵活性，引入了一些在固定的映射方法中不存在 的问题和困难，k 第四章、查询重写及结果组装日对查询执行算法作了详细的描述。 算法借鉴关系库查询引擎中使用查询代数图表示查询语义和操作的方法，定义了表 示x m l 查询语义的x m l 查询代数图x 0 a g 。算法的执行过程通过对x q a g 进行 变形，并估计相应的操作代价来选择具有较优实际执行效率的重写查询。考虑到该 映射模型的特殊性，本文提出了以加权估计执行代价为标准的g r e e d 算法解决重写 s