（计算机软件与理论专业论文）xml数据的可视化查询、查询优化及索引技术.pdf

摘要 摘要 ，7 近年来，随着i n t e r n e t w e b 的迅速发展，w e b 已经成为人类社会的主要信息 源、磲体和商务的门户、信息交换的平台。x m l 的出现引发了w e b 的一场变革， 大量x m l 页面、站点和应用开发工具纷纷涌现。可以预见，x m l 将成为w e b 信息发布和交换事实上的标准。它在电子信息发布、电子商务、数字图书馆、 w e b 信息搜索和集成等领域都具有非常广阔的应用前景。而在x m l 引起的变革 中，为了有效管理x m l 数据，数据库技术毫无疑问将扮演关键的角色。 在这样的背景下斗我们从数据库角度研究和开发了一个基于x m l 的w e b 数 据管理原型系统，并支寸其中的些关键技术，如可视化查询、查询重写和优化、 索引技术等进行了研究。 具体说来，本文的贡献如下： 1 合作设计并实现了基于关系数据库存储和查询x m l 数据的原型系统 v x m l r 。文中给出了它的体系结构，概括了系统特点。 2 提出d v q ( d t d d r i v e nv i s u a lq u e r y ) 可视化查询界面，它是v x m l r 系统的可视化查询界面。有了d v q ，v x m l r 系统的用户可以通过它浏 览x m l 文档的嵌套结构、生成查询、浏览查询结果。 3 ( 对v x m l r 系统的查询处理部分进行了研究。查询处理包括查询重写和 查询优化两方面的工作钵文提出了通过d t d 字典中的结点信息和统计 信息来消除正则符号和通配符，扩展递归路径表达式的技术。并提出路 径目录技术作为关系数据库上的路径索引，优化查询，提高查询效率。 4 同时，我们进一步研究索引技术，提出了结构化映射( s t r u c t u r a lm a p ) 。 f 它可以在任何现有数据库系统上有效处理路径表达式查询。在初步性能 实验中，结构化映射可以提高路径表达式查询性能一个数量级以上。j 关键词：x m l f 可视化查询；查询重写，查询优化；结构化映射， 垒堕型 一 a b s t r a c t w i t ht h er a p i dg r o w i n go fi n t e r n e t j w e bd u r i n gr e c e n ty e a r s ，w e bh a sb e c o m et h e m a i ns o u r c eo fi n f o r m a t i o n ，t h ep o r t a lo fm e d i a sa n db u s i n e s s e s ，a n dt h ep l a t f o r mf o r d a t ae x c h a n g e t h ea p p e a r a n c eo fx m lh a sa r o u s e dar e v o i u t i o ni nt h ew e b d u r i n g t h ep a s ts e v e r a ly e a r s ，l a r g en u m b e r so fx m ld o c u m e n t s ，s i t e sa n da p p l i c a t i o nt o o l s h a v eb e e na p p e a r i n gi nt h ei n t e m e t w ec a na n t i c i p a t et h a tx m li sg o i n gt ob et h e p r a c t i c a ls t a n d a r df o ri n f o r m a t i o np u b l i s h i n ga n de x c h a n g i n go nt h ew e b i ti sm u c h u s e f u la n dp o w e r f i f li nm a n yf i e l d s ，s u c ha se l e c t r o n i cd a t ar e l e a s e ，e c o m m e r c e ， d i g i t a ll i b r a r y , w e bi n f o r m a t i o nr e t r i e v a la n di n t e g r a t i o n a m o n gt h er e v o l u t i o nt h a t x m li sb r i n g i n gt ot h ew e b ，d a t a b a s et e c h n o l o g yw i l lp l a yam a j o rr o l e w i t ht h i sb a c k g r o u n d ，w ed e v e l o p e daw e bd a t am a n a g e m e n ts y s t e mf o rs t o r i n g a n dq u e r y i n gx m ld a t a b a s e do nt h i sp r o t o t y p es y s t e m ，w ec o n d u c t e ds o m er e s e a r c h t o p i c s d a t am o d e l ，v i s u a lq u e r y , q u e r yr e w r i t i n ga n do p t i m i s a t i o n ，i n d e xt e c h n i q u e s t h ec o n t r i b u t i o n s & t h i sp a p e ra r ea sf o l l o w s 1 w ed e v e l o pap r o t o t y p es y s t e mv x m l r ( v i s u a lx m l r e l a t i o n a ld a t a b a s e s y s t e m ) t os t o r ea n dq u e r yx m l d a t ao nt o po fr d b m s w ep r e s e n tt h e a r c h i t e c t u r eo f t h es y s t e ma n di t su n i q u ef e a t u r e s 2 c o m eo u t 谢mav i s u a lq u e r yi n t e r f a c ed v q ( d t d d r i v e nv i s u a lq u e r y ) i m p l e m e n t e di nv x m l r i tp r o v i d e su s e r sw i t hag r a p h i c a li n t e r f a c es ot h a t c o m p l e xq u e r i e sc a l lb ef o r m e db yu s e r s s i m p l eg u i a c t i o n s 3 s t u d yt h eq u e r ye x e c u t i o np e r f o r m a n c eo fv x m l r aq u e r yr e w r i t i n g s y s t e mw b sd e v e l o p e dt ot r a n s f o r map a t he x p r e s s i o nq u e r yi n t oas e to fs q l s t a t e m e n t s i np a r t i c u l a r , w eu s es t a t i s t i c sa n dap a t hd i r e c t o r yt or e d u c et h e n u m b e ro fs q ls t a t e m e n t s ，a n dt h en u m b e ro f j o i n s 、v i 山曲s q ls t a t e m e n t s ， s oa st oi m p r o v et h ep e r f o r m a n c ed r a m a t i c a l l y 4 f u r t h e rs t u d yi n d e xt e c h n i q u e sa n dc o m eo u tw i t han o v e ld a t as t r u c t u r e ， s t r u c t u r a lm a p i tc a nb ei m p l e m e n t e di na n yd a t a b a s es y s t e mt oe f f i c i e n t l y h a n d l ep a t he x p r e s s i o nq u e r i e s i np r i m a r ye x p e r i m e n t s ，s t r u c t u r a lm a pc a n s p e e du pt h eq u e r ye x e c u t i o ns i g n i f i c a n t l y k e y w o r d s ：x m l ，v i s u a lq u e r y , q u e r yr e w r i t i n g ，q u e r yo p t i m i s a t i o n ，s t r u c t u r a lm a p 一一 墨二童! ! i _ - - _ - _ - - - _ _ _ _ 一一 1 1x m l 简介 第一章引言 x m l ( e x t e n s i b l em a r k u pl a n g u a g e ) b p s + g g 是一种元语言，也是一种基 于文本的标记语言。它是s o m l ( 标准通用标记语言) m 0 8 6 的一个子集。x m l 包含一组基本规则，任何人都可以利用这种规则创建针对特定应用领域的标记语 言，这些标记并非描述信息的显示方式，而是信息本身。它允许标记文本( 元素) 、 元素嵌套、以及元素引用。x m l 标准的制定大大促进了i n t e m e t w e b 的发展， 它将成为第二代w e b 的基础。 s g m l 是完备的，但是s g m l 文档过于复杂，它要对每个字节都加以说明， 因此只用于波音公司等大公司和美国国税局等政府机构，而大多数应用和中小机 构并不需要如此精确的说明。过于复杂的文档使w e b 浏览器很难处理，而x m l 作为s g m l 的最小完备予集，继承了s g m l 的强大功能而去除了烦琐的定义。 h t m l ( h y p e r t e x tm a r k u pl a l l g u a g e ) 是符合s g m l 语法的一种固定格式的超文 本标记语言。因其格式固定，故难以扩展，主要用于显示信息的内容，而不能反 映出信息的结构。它的标记集合也完全可以用x m l 来定义。将来的发展趋势是 使用x m l 作为w e b 上的信息表达和交换的标准，而将h t m l 作为在浏览器端 描述显示方法的工具。从x m l 到h t m l 的转换工具是x s l ( e x t e n s i b l es t y l e s h e e t l a n g u a g e ) 【a b c + o i 。 x m l 具有以下一些特性：x m l 具有自描述性( 元素的标记描述了信息) ； x m l 具有可扩展性( 用户可以通过d t d 来定义新的元素) ；x m l 提供了更为灵 活的机制来表达更为复杂的链接关系( 使它更适应于w e b ) ；把信息的结构、内 容和显示分离开来，x m l 主要表示信息的内容和结构，而把显示方法交给x s l 或c s s 处理。以上特性使x m l 适用于w e b 上的信息表示和交换，便于计算机 进行处理，是面向机器的标记语言。而h n 也是面向显示的标记语言，机器处 理很不方便。 需要指出的是，x m l 格式处理的是文本数据。对于非文本数据，如图像、 声音的原始数据，用x m l 格式来编码并不理想。但是l 提供记号、外部实 体和处理指令这三种结构供其它应用程序来处理非x m l 格式数据。 按照x m l1 0 标准的定义，x m l 描述了一类称为x m l 文档的数据对象， 同时也部分描述了处理这些数据对象的计算机程序行为。x m l 文档：如果一个 数据对象满足v i l 规范中的格式良好( w e l l f o r m e d ) 的要求时，它就是一个 x m l 文档：如果它又符合规范中的文档类型定义d t d ( d o c u m e n tt y p e d e f i n i t i o n ) ，那么称它是有效的( v a l i d ) x m l 文档。x m l 数据：以x m l 格式 3 墨二兰! ! 童 一 表示的数据。它可以表示结构化数据，如关系数据，但是更多的是表示无固定结 构的w e b 数据。本文中，对于x m l 文档和x m l 数据这两个概念并不严格区分， 认为它们是同义的。x m l 文档这个提法更多出现在x m l1 0 规范中，而x m l 数据是更为通常的说法。 1 2x m l 和半结构化数据 现实世界中，些数据是完全没有结构的，如图像，音频，视频数据流；而 另外很多数据并非完全没有结构，但也不具有固定的结构。如h t m l 构成的w e b 页、电子邮件、l a t e x 文档、生物数据库( 如a c e d b ) 等等。我们把它们称为 半结构化数据( s e m i s t r u c t u r e dd a t a ) b u r 0 7 ，s u c 9 8 。与传统的结构化数据( 如关 系数据库、对象数据库中的数据) 相比，它的主要特性是自描述性( 即内容与结 构都包含在数据中) ，它的结构是不固定、不规则、隐含的，并且是易变化的。 由于w e b 数据表示、数据集成、数据交换都需要利用半结构化数据，因此从数 据库角度研究半结构化数据的数据模型、模式、查询、查询优化、视图成为近年 来的热点问题，并且取得了很多可喜成果。x m l 文档代表了一个重要的并且在 不断增长的半结构化数据源，它同半结构化数据有许多共同的性质，如自描述性、 结构是不固定的、易变的。半结构化数据中的标注( 或称为属性) 、对象、原子 值( s t r i n g ，i n t ，f l o a t ，v i d e o 等等) 分别对应于x m l 中的标记、元素、p c d a t a 。 因此半结构化数据已有的理论，如数据模型和查询，以及已有的原型系统可以作 为x m l 研究的基础。但是x m l 与经典的半结构化数据之间也有区别。x m l 的 元素可以含有属性。x m l 文档的数据元素( e l e m e n t ) 具有顺序，元素之间通过 i d 和i d r e f 属性进行引用，文档具有可选的d t d ( d o c u n l e i l tt y p ed e f i n i t i o n ， 文档类型描述) 等。x m l 文档的这些特性将其区别于经典的半结构数据，使其 成为一种独特的半结构数据类型。大量x m l 文档的高效组织管理、文档类型推 导、分布式计算等问题为我们带来了新的研究课题。v i l 具有可扩展性、更强 的链接方法等优良特性，使得它可以作为一种半结构化数据的通用逻辑表示，程 序可以很容易地把任何数据源的数据转换成为x m l 格式的数据。因此，x m l 是半结构化数据家族中的代表，对于它的研究具有极其重要的价值。 1 3x m l 与数据库技术 作为h t m l 的替代，x m l 将作为第二代的w e b 数据表示和交换语言。可以 预料，x m l 数据将大量出现在w e b 中。引入) 。以l 的初衷是要极大地促进 i n t e r n e f f w e b 的发展和应用。这给数据库界带来了巨大的机会，使数据库技术运 用于w e b 数据管理和将研究扩展到w e b 数据管理成为可能。其根据有二点：第 4 第一章引言 一，以x m l 表示的w e b 数据，有助于对文档和数据进行结构化处理，是面向机 器的语言( 而h t m l 对于文档的结构化用于显示目的，是面向人的语言) ，从而 使它们能在部门、客户和供应商之间进行交换。与现在的w e b 工具( 浏览器、 搜索引擎) 面向文档的操作不同，x m l 数据也需要数据库的一些操作，比如数 据抽取、数据集成、数据转换和数据存储。其二，x m l 文档可以具有文档类型 定义d t d ( d o c u m e n tt y p ed e f i n i t i o n ) ，它是x m l 文档的词汇表和结构，各个 组织或者个人都可以定义自己的d t d 。d t d 可以看作是x m l 表示的w e b 数据 的模式，这有利于数据库技术应用于w e b 数据管理。 数据库界一直采用三级体系结构来代表数据的三个抽象级别。其中，物理模 式描述了数据是如何存储的，这个层次涉及物理存储和可能的索引机制。物理模 式之上是概念模式，它是一个全局数据视图，不涉及存储结构和访问技术，由此 实现了数据的独立性。最外层是子模式，它提供用户需要的大量视图。目前，对 于w e b 数据而言，概念层和物理层并没有很大区分，这是因为当前w e b 的主要 功能是传输少量的超文本，区分并无多大意义。但是，这种情况会逐渐改变，例 如，对于包含成千上万条目的科学数据库而言，如果每个条目含有几k b ，那么 我们可以认为它是一个大小为1 0 0 g b 的x m l 文件，但是实际的物理存储也许是 个压缩文件，或者是一个关系数据库，或者根本没有存储，而直接链接到相应 的服务器。这时，我们既可以把x m l 看作是一种物理存储一种数据格式， 也可以把它作为一种半结构化数据的逻辑表示。 1 4 数据库领域x m l 技术的研究现状 x m l 自发布以来就受到了各界的广泛关注。各计算机厂商们竞相推出或即 将发布支持x m l 的产品( 如：o r a c l e9 i ，i b m 的d b 2u d b ，m i c r o s o f t 的s q l s e r v e r2 0 0 0 等) ；学术和研究机构纷纷采用x m l 来表示各种科学数据并正在对 x m l 开展深入的研究；工业界和商业界则忙于定制适于各行业应用的d t d 规 范。目前，i n t e r a c t 上已经涌现了大量的x m l 页面、站点和应用开发工具。可以 预见，x i v l l 将成为w e b 信息发布和交换事实上的标准。x m l 在电子信息发布、 电子商务( e d i 交换) 、数字图书馆、w e b 信息搜索和集成等领域具有广阔应用 前景。 在x m l 引起的w e b 变革中，数据库技术将扮演关键角色。从数据处理的角 度来说，传统的w e b 信息处理主要采用的是信息检索( i n f o r m a t i o nr e t r i e v a l ) 技 术。搜索引擎的主要方式是关键字搜索。关键字搜索极不准确，搜索的结果将返 回包含关键字的整个文档，网络传输量大。x m l 使得我们可以采用数据库技术 来存储、搜索、分析、加工和处理w e b 信息。具体地说： 5 第一章引言 1 ) 可以使用类似于数据库的查询语言的方式来检索x m l 文档，搜索引擎的 功能将变的更加强大而准确。如：通过x m l 搜索引擎，我们可以进行诸 如。搜索房价低于4 0 0 元的饭店名称”的搜索。此外，查询结果将只返回 与查询匹配的部分而非整个文档，大大降低网络传输量。 2 ) 传统的w e b 信息、管理主要处理的是静态w e b 页面，而利用数据库中的成 熟技术可以保证动态更新的w e b 页面的数据一致性。 3 ) 利用数据库( 和数据挖掘) 技术可以及时、有效地分析、加工在线的x m l 数据，从中发现有用的知识，辅助企业决策。 然而，x m l 与传统数据库中的结构化数据不同，x m l 数据是自我描述的， 没有预先固定的模式。x m l 与数据库界近年来研究的半结构化数据 ( s e m i s t r u c t u r e dd a t a ) 极为相似。数据库界研究半结构化数据的目的在于扩展 传统的数据库技术以处理没有预先固定的模式或结构经常变动的非结构化的数 据。 目前，数据库界在半结构化数据的研究方面已取得了一定的进展。这包括数 据模型 e g w 9 s ，查询语言 b f s 0 0 ，g w 9 7 ，半结构化的模式 g w 9 7 ，查询和查询优 化技术 f m l 9 9 ，h g i + 9 5 ，m w 9 9 a , b d h + 9 6 ，索引技术 2 v l w a + 9 8 ，m s 9 9 a ，半结构化路 径约束 b f w 9 8 ，a v 9 7 ，f a n 9 9 ，半结构化中间件和视图机* j l je l y v + 9 8 ，m p q + 9 7 ，p v 9 9 ， 半结构化模式抽取 a a c + 9 9 ，n a m 9 8 ，m s 9 9 b 】，半结构化数据管理系统 q w g + 9 6 ， h g i + 9 5 ，m a g + 9 7 ，w e b 站点管理 f y l + 9 9 ，f y v + 0 0 ，f f k + 9 8 等。关于半结构化数据 研究的综述见 b u n 9 7 ，a b i 9 7 。 由于x m l 与半结构化数据的相似性，人们可以将x m l 看作是半结构化数 据的标准。并借鉴半结构化数据的研究成果来管理x m l 数据。但是，目前的半 结构化数据的研究尚不成熟，而x m l 与半结构化数据相比又有一些差g i j t s u c 9 s l ， 这主要表现在：从数据特点上看，x m l 文档中的元素有次序，x m l 可带有描 述文档结构的d t d ：从应用领域来说，x m l 不但被用于表示w e b 数据，也面向 电子数据交换。因此，需要对x m l 数据进一步作深入的研究。自x m l 标准发 布以来，x m l 数据已经引起了数据库研究者们极大的兴趣，成为了近年来的 s i g m o d 、v l d b 、i c d e 和p o d s 等数据库界顶级会议的研究热点。 国外的许多大学和研究机构和各种基金都对x m l 数据处理进行研究。目前 国际上正在开展的x m l 数据管理的主要研究项目见下表。另外，i b m ，m i c r o s o f t ， o r a c l e 等各大数据库厂商的研究机构也都有对x m l 技术的专项研究( 未在下表 中列出) 。 6 第一章引言 项目名称研究机构或院校研究重点 n i a g a r aw i s c o n s i nm a d i s o n 大学x m l 的查询和搜索引擎 m i x 加州大学s a nd i e g o 分校( u c s d )x m l 数据中间件 x ld a t aw i s c o n s i nm a d i s o n 大学存储，管理x m l 数据 m a n a g e m e n t t u k w i l a w a s h i n g t o n 大学 基于x m l 的数据集成 x a m l - q l a t & t 实验室，n r a n 和x m l 查询语言 w a s h i n g t o n 大学 s i l k r o u t e p e n n s y l v a n i a 大学a t & t 实验室 x m l 信息发布 x r a i l l p e n n s y l v a n i a 大学a t & t 实验室 x m l 数据压缩 x p e r a n t o w a s h i n g t o n 大学，i b m 公司 x m l 信息发布 s e m i s t r u c t u rd a t a p a n n s y n a n i a 大学 x m l 的查询语言结构描述， x m l 约束机制和类型系统 c a r a v e l法国i n r j a x m l 数据的查询和存储技术 l o r e s t a n f o r d 大学 x m l 数据库管理系统 t j mm q p ：r a i n b o w w o r c e s t e r 理工大学 x m l 和关系数据库 x n 几b a s e d 德国国家信息技术研究中心 x m l 标准和x m l 结构， i n f o r m a t i o ns y s t e m s ( g m d )x m l 文档存储和查询，x m l 带电子商务和数字图书馆中 的应用 v e r s o 法国i n r i a x m l 查询，x m l 主动视图 ( a c t i v ev i e w ) 及其在电子商 务中的应用 目前，在x m l 数据管理方面需解决的前沿问题主要有： x m l 的查询语言和代数。目前提出的l 的查询语言有l o r e i a q m + 9 7 1 、 x m l q l f d f + 9 9 、x q l r l s 9 8 、x q u e r y b c f + 0 2 等。关于这些语言的 比较分析，见 b c o o i 。x m l 的形式化描述较为困难，目前仅有 f s w o o 对x m l 的查询代数作了初步的探讨。 x m l 数据的存储机制。x m l 的数据存储是处理x m l 数据的首要问题。 x m l 的主要存储方式为文件系统 t d c + 0 2 ，关系数据库 s k w + 0 0 z n d + 0 1 f k 9 9 ，g t z + 9 9 ，m f o + 0 0 ，面向对象数据库 k m 0 0 ，a c c + 9 7 和半结构化数据 仓库 g m w 9 9 等。 x m l 数据的查询和查询优化技术 f d f + 9 9 ，m w 9 9 b 。x m l 数据的查询优 化包括；优化正则路径表达式 m w 9 9 b j ，基于约束的x m l 查询优化和在 w e b 环境下的分布式查询优化等。 x m l 视图。在w e b 环境下，x m l 视图显得比传统数据库中的视图更加 重要f a b i 9 9 。面向电子商务应用，需要建立x m l 的主动视 蛩 a a c + 9 9 1 。 x m l 数据的完整性约束机制。d t d 提供了x m l 数据的语法规范，然而， 7 第一章引言 d t d 缺乏关于x m l 数据的语义描述。因此，需要建立x m l 的约束机 制，包括主键和外键约束 b d f + 0 1 ，反向约束和路径约束等。 大规模x m l 文档的检索。在w e b 环境下，x m l 文档将是海量的。搜索 大规模x m l 文档需要结合数据库和信息检索两方面的技术。大规模 x m l 文档的检索技术将构成将来x m l 搜索引擎的基础。w i s c o n s i n m a d i s o n 的研究者已经开始了这方面的初步探索 c d t + 0 0 。 x m l 数据交换和翻译 a c m 0 0 。在电子信息发布领域，需要将传统数据 或h t m l 文档转化为x m l 格式发布( 一个转换工具见 s a 9 9 1 ) 。而面向 电子数据交换，则需要一种工具，自动将符合一个d t d 规范的文档转 化为符合另一个d t d 定义的文档。在这方面的相关研究有 m s v 0 0 1 。 基于x m l 的数据集成。x m l 使得通过统一的x m l 格式访问各种形式 的w e b 信息成为可能。在x m l 数据集成方面已经有了一些深入的研究 b g l + 9 9 ，f y v + 0 0 ，z l z + 0 1 。 x m l 数据压缩。有效的x m l 数据压缩工具将有效地降低x m l 数据的 网络的传输量。在这方面，a t & t 和p e n n s y l v a n i a 大学的研究者已开发 出了一个有效的x m l 压缩工具x m i l l l s o o 。 尽管上述研究涉及到了x m l 数据管理的诸多方面，但总的来说，上述x i v i l 数据管理的研究尚处于初级阶段，另外，还有一些重要的研究方向尚未被涉及或 未有论文发表。 1 5 本文的研究内容与目标 根据前面几节的分析，我们看到，x m l 将成为下一代互联网的交换和表示 语言，具有广泛的应用前景，对于它的研究和技术开发将会带来巨大的经济效益。 国际上从9 0 年代中期就从数据库角度研究w e b 数据的管理，开发了若干个不同 原型系统，为进一步研究x m l 技术打下了良好基础。国内虽然对x m l 有一定 的研究，但是目前还处于比较落后的阶段，理论研究深度不够。 根据上面的论述，本文的研究目标是：研究和开发一个存储和查询大量x m l 数据的数据库原型系统。以此为基础，对其中些关键技术，如可视化查询、查 询重写与优化、索引技术等问题进行研究。 具体说来，本文的贡献如下： 1 合作设计并实现了基于关系数据库存储和查询x m l 数据的原型系统 v x m l r 。文中给出了它的体系结构，概括了系统特点。 2 提出d v q ( d t d - d r i v e nv i s u a lq u e r y ) 可视化查询界面，它是v x m l r 的可视化查询界面。有了d v q ，v x m l r 系统的用户可以通过它浏览 8 第一章引言 x m l 文档的嵌套结构、生成查询、浏览查询结果。 3 对v x m l r 系统的查询处理部分进行了研究。查询处理包括查询重写和 查询优化两个方面的工作。本文提出了通过d t d 字典中的结点信息和统 计信息来消除正则符号和通配符，扩展递归路径表达式的技术。提出路 径目录技术作为关系数据库上的路径索引，优化查询，提高查询效率。 4 进一步研究索引技术，提出了结构化映射( s t r u c t u r a lm a p ) 。它可以在任 何现有数据库系统上有效处理路径表达式查询。在初步性能实验中，结 构化映射可以提高路径表达式查询性能一个数量级以上。 1 6 论文结构 本文共分六章，第一章总体介绍x m l 的基本概念和国际上目前研究状况。 第二章探讨x m l 查询语言，提出了朝向可视化的x m l 查询技术。第三章重点 讨论了x m l 的查询重写和使用新颖的路径目录来优化x m l 查询的技术。我们 实现了一个存储查询x m l 数据的可视化l 一关系数据库系统v x m l r ，在第 四章中研究该系统的性能。第五章针对优化查询处理的重要方法索引机制进 行探讨，提出了结构化映射技术，并研究了该技术的性能。 9 蔓三兰! 坚! 塑里望些壅塑! 里! 旦! 第二章x m l 的可视化查询( d v q ) 2 1x m l 查询语言背景 “l 是i n t e m e t 上数据表示与交换的标准。在众多的基于i n t e m e t 的应用中， x m l 是一种易于书写，易于解析的语言。目前，多数商业数据使用关系数据库 或者对象关系数据库系统来存储。这种格局还将继续，因为关系数据库技术非常 成熟，能提供优良的可查询性( q u e r i a b i l i t y ) 、可扩展性( s c a l a b i l i t y ) 和可用性 ( a v a i l a b i l i t y ) 。所以，可以充分利用关系数据库的这些优势，使用关系数据库来 存储x m l 文档。 为了查询x m l 数据，研究者们提出了很多查询语言，包括l o r e l a q m + 9 7 、 x m l q l d f f + 9 8 、x p a t h c d 9 9 1 和x q u e r y b c f + 0 2 等等。尽管这些查询语言在表 达查询的能力方面有所不同，但是x m l 查询的一个共有特点是：查询是基于路 径表达式的，这与面向集合的关系查询语言，例如s q l ，是极其不同的。 与关系数据库中使用的s q l 查询语言相比较，查询x m l 数据更为困难。原 因是用户需要知道数据的结构。如果x i v l l 数据被存储在关系数据库中，这一点 更为显著，尤其使用结构映射的方法把x m l 模式映射成为关系模式的时候 ( x m l 数据的原始结构信息并不能完全在关系模式中体现出来) 。x m l 数据的 存储及在特定存储方式之上的查询处理技术已经被研究者广泛关注。但是，如何 向用户提供工具，方便地生成基于路径表达式的x m l 查询，相关工作还很少。 l o r e 系统的d a t a g u i d e g w 9 7 界面能够通过半结构化数据的d a t a g u i d e 来生成简 单的l o r e l 查询语句。但是它只能生成简单路径表达式，而且只能在某一条特定 路径上设置连接条件。m 系统的b b q m p 0 0 查询界面以及e q u i x c k k + 9 9 查询 界面可以显示x m l 数据的d t d 结构，以辅助用户浏览和构造查询。但是它们 不能生成任意正则路径表达式和复杂约束条件。 本章提出d v q ( d t d d r i v e n v i s u a lq u e r y ) 查询界面，它是x m l 一关系数据 库系统v x m l r z l z + 0 1 的可视化查询界面。v x m l r 采用一种基于结构映射的 方式将x m l 数据映射到关系表，而这些关系表由商业关系数据库管理系统管理。 它的查询界面d v q ，显示被存储的x m l 数据关联的d t d 结构。用户通过点击 d t d 结构中的结点，并输入相关的条件，便可以容易地生成路径表达式。然后， d v q 自动地生成基于路径表达式她查询语句。查询结果通过x s l 表现，并通过 d v q 传递给用户。有了d v q ，v x v i l r 系统用户可以通过它浏览x m l 数据的 嵌套结构、生成查询、浏览查询结果。d v q 的独特性包括以下几点： 1 0 兰三兰兰坠箜里望些奎塑! 里旦! 一 它提供给用户一个图形界面，使复杂的查询可以通过用户的简单g u i 动 作来形成。不论x m l 专家还是普通用户，都可以制定查询，而无需x k m l 查询语言的相关知识。 它可以生成包括通配符的正则路径表达式以及包括连接( c o n j u n c t i o n ) 、 析取( d i s j u n c t i o n ) 和否定( n e g a t i o n ) 的任意复杂的查询条件。同时， d v q 的w y s w y g ( w h a ty o us e ei sw h a ty o ug e t ) 特点使得查询的构 造变得相当直观。 除了输入查询，d v q 还给用户提供浏览x m l 结构的机制，以及观察查 询处理主要中间步骤的机制。 它是运行在客户端的独立模块，由原始x m l 数据的d t d 驱动。也就是 说，它是独立于底层x m l 一关系映射模式的。所以，它是一个可以用在 任意x m l 数据库系统上的可移植模块。 本章安排如下。在第二节介绍一些背景信息。第三节描述d v q 的体系结构。 第四节，通过示例，我们描述d v q 如何生成包含集合约束条件的路径表达式。 在第五节给出d v q 用来监视x m l 查询处理并显示查询结果的功能。最后在第 六节给出小结。 2 2 面向可视化的x m l 查询 在这一节中，我们介绍一些关于“l 数据和l 查询的背景知识。 2 2 1 一个d t d 样例 h t m l 文档通常没有可知的结构。不同于h t m l 文档，x m l 文档的文档类 型定义( d t d ) 描述了文档中数据元素的嵌套关系。在图2 1 给出了一个d t d 样例，我们将在后面的讨论中使用它作为运行示例。 蔓三兰兰! 些箜里望些奎塑! 望g ! 一 x m l z h o ua o y i n g a y z h o u e f u d a n e d u c n aa l g o r i t h m j o u r n a io f z e n g p i n gt i a n c l u s t e r i n g a _ l g o r i t h m c l u s t e d n g 图2 2 ：一个x m l 文档和它的数据图 有了这样的结构，我们可以使用从根到元素的路径来表示一个元素。如果我 们采用点符号来标识父子结点关系的话，- - + m e m b p r 的h a m p 可以用路径 p r o j e c t m e m b e r , n a m e 来表示。一股而言，路径表达式会很复杂。如果，r ，和一 是元素或者属性，那么一个路径表达式具有如下的形式： 1 3 一 墨三兰茎坠堕旦望些童塑! 里旦! 一 _ _ _ _ _ _ _ _ 一一一 r = ( r ) + l ( r ) + l ( ，) ? ，f 以e ( r t r 2 ) l # ln a m e 其中，+ 、+ 、? 分别表示元素出现0 或者多、1 或者多、0 或者1 次a7 ，和以 的串连“以用来生成，到n 的路径。“或”符号“1 ”代表析取。通配符“# ”表 示任意正则表达式的任意出现。我们将路径表达式分为两类：简单路径表达式 ( s p e ) 和正则路径表达式( r p e ) 。简单路径表达式是只包含元素或属性名的路 径表达式，例如：t a b f n f o r m a t i o n p r o j e c t , m e m b e r n a m e 。正则路径表达式是包含正 则操作符的路径表达式，例如：# ( p r o j e c t m e m b e r ) i n a m e 是一个r p e 。 2 2 3v x m l r ：可视化x m l 关系数据库系统 我们开发了一个可视化x m l 一关系数据库系统v x m l r ( v i s u a l x m l r e l a t i o n a ld a b b l es y s t e m ) z l z + 0 1 1 。这个系统具有下面的特点： 1 x m l 数据被映射到关系表，使用关系数据库系统来存储数据。 2 具有可视化查询界面，提供简单的方法来查询存储在关系数据库中的 x m l 数据。x m l 数据的结构被显示在界面上，用户可以通过点击界面 上数据条目并输入查询条件来生成查询，而不需要知道路径表达式的复 杂语法。 3 使用一个查询重写系统来转换路径表达式查询到s q l 语句。尤其，我们 使用统计信息和一个新颖的路径目录来减少s q l 语句的数目、s q l 语句 中连接操作的数目，来显著提高系统性能。 图2 3 给出v “l r 系统的体系结构。在v x m l r 中，x m l 文档存储在一 个关系数据库系统中，由关系数据库管理系统维护。个x m l 文档作为输入， 首先被解析成一棵d o m 树。同时，抽取出该文档的d