（计算机应用技术专业论文）基于抽象语法树的xquery查询语言实现技术研究.pdf

东北大学硕士学位论文摘要 基于抽象语法树的x q u e r y 查询语言实现技术研究 摘要 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 ) 的简称，具有有效的 表达各种信息、数据和使各种应用协同工作的能力，它已经成为w e b 上数据发布 和数据交换的事实标准。x m l 是典型的半结构化数据，对x m l 数据的查询要求 不同于传统数据库，在查询时不仅要对数据库中的数值进行查询，而且要对x m l 文档的结构和数据之间的关系进行查询。随着x m l 相关技术的深入研究，x m l 查询已经具备了坚实的技术基础。在此基础上，w 3 c ( w o r l d w i d e w e b c o n s o r t i u m ) 于2 0 0 1 年1 2 月提出了x m l 查询语言规范( 工作草案) x q u e r y 语言。迄今为止， x q u e r y 一直在不断发展中。 由于x q u e r y 语言十分复杂，在对该语言规范体系的分析理解和研究的基础 上，我们着重实现一个核心的功能子集，以其作为我们正在开发的x m l 数据库管 理系统n e x t 的一部分。由于j a v a 的跨平台特性，我们使用j a v a 语言实现该语言 的查询引擎。 我们系统中x q u e r y 处理分为两大部分：x m l 文档载入模块以及x q u e r y 查询 处理模块。在x m l 文档载入模块中，我们采用b e r k e l e yd b 数据库存储x m l 文 档和索引，提供数据库对外操作接口：与关系模型不同，x m l 数据是树状结构， 路径表达式在查询中非常关键。而且f l w o r 表达式是x q u e r y 最为有特色且最为 重要的语法类型之一，所以我们在查询处理模块中，着重处理了路径表达式和 f l w o r 表达式。抽象语法树在查询引擎中是关键部分，针对这一问题，我们细致 地分析了主要表达式的语法树结构，并在此基础上提出了路径表达式和f l o w o r 表达式的实现方法。 关键词：x m l ，x q u e r y ，查询处理引擎，抽象语法树 东北大学硕士学位论文a b s t r a c t s t u d yo ni m p l e m e n t a t i o nt e c h n i q u e so fx q u e r y l a n g u a g eb a s e do n a b s t r a c ts y n t a xt r e e a b s t r a c t x m l ，s h o r tf o re x t e n s i b l em a r k u pl a n g u a g e ，i se m e r g i n ga sad ef a c t os t a n d a r d f o ri n f o r m a t i o nr e p r e s e n t a t i o na n dd a t ae x c h a n g eo nt h e 阢6f o ri t s c a p a b i l i t yo f r e p r e s e n t i n g v a r i o u sk i n d so fd a t aa n d i n t e r o p e r a b i l i t yt h r o u g hh e t e r o g e n o u s a p p l i c a t i o n s x m li s as e m i s t r n c t u r e dl a n g u a g e ，t h eq u e r y i n gr e q u i r e m e n t si nx m l d a t a b a s e sa r et h u se l i f f e r e n tf r o mt h a ti nt r a d i t i o n a ld a t a b k g e s x m ld a t a b a s e sn e e dt o s u p p o r tb o t hq u e r y i n go nv a l u e sa n dq u e r y i n g o ns t r u c t u r a l r e l a t i o n s h i p sa m o n g d o c u m e n tn o d e s w j md e e p l ys t u d y i n go nx m lr e l a t e dt e c h n o l o g y , t h ef i r mr e s e a r c h f o u n d a t i o no f x m l q u e r yl a n g u a g eh a sb e e na c h i e v e d i nt h i sb a c k g r o u n d ，w 3 c ( w o r l d w i d ew e bc o n s o r i u m ) p r o p o s e daw o r k i n gd r a f ts p e c i f i c a t i o no nx m l q u e r yl a n g u a g e ， x q u e r y , i no c t o b e r , 2 0 0 1 a n d i th a sb e e ni nd e v e l o p i n gc o n s t a n t l ya l lt h et i m e b e c a u s eo ft h e c o m p l e x i t yo fx q u e r y , a f t e ri n v e s t i g a t i n gt h es p e c i f i c a t i o n c a r e f u l l y , t h i st h e s i sd e s i g n sa n di m p l e m e n t sac o r es u b s e to fx q u e r ya sp a r to ft h e x m ld a t a b a s em a n a g e m e n ts y s t e mn e x tw h i c hi su n d e rd e v e l o p m e n ta tn e u b e c a u s ej a v ah a sag o o di n t e r o p e r a b i l i t ya c r o s sh e t e r o g e n e o u sp l a t f o r m s i ti sa d o p t e d t or e a l i z et h eq u e r y i n ge n g i n eo f t h ex q u e r yl a n g u a g e i no u rs y s t e m ，t h eq u e r yp r o c e s s i n gp r o c e d u r eo f x q u e r yi sd i v i d e di n t ot w om a j o r p a r t s ，t h ex m l d o c u m e n tl o a d i n gm o d u l ea n dt h ex m l q u e r yp r o c e s s i n gm o d u l e i n t h ef o r m e rm o d u l e ，w ea d o p tb e r k e l e yd bt os t o r ex m ld o c u m e n t sa n di t si n d e x e sa n d p r o v i d ee x t e r n a la c c e s si n t e r f a c et ot h ed a t a b a s e d i f f e r e n tf r o mt h er e l a t i o n a lm o d e l x m ld a t ai st r e e s t r u c t u r e d ，p a t he x p r e s s i o n sa r et h u so fg r e a ti m p o r t a n c ei nx m l q u e r i e s i na d d i t i o n ，f l w o re x p r e s s i o ni sa ni m p o r t a n tq u e r y i n gs t r u c t u r ei nx q u e r y s i n c ei ti su n i q u ea n do n eo fq u i t ee x p e n s i v eo p e r a t i o n s t h e r e f o r e ，w ef o c u so np a t h e x p r e s s i o na n df l w o re x p r e s s i o ni nt h ex m lq u e r yp r o c e s s i n gm o d u l e s i n c e a b s t r a c ts y n t a xt r e ei sc r u t i a li nt h eq u e r y i n ge n g i n e ，w ef i r s ta n a l y z ec a r e f u l l yt h e a b s t r a c ts y n t a xt r e es t r u c t u r eo fs o m ek e ye x p r e s s i o n s t h e nw ep r o p o s et h e i m p l e m e n t a t i o n m e t h o d so fq u e r yp r o c e s s i n go fp a t he x p r e s s i o n sa n df l w o r e x p r e s s i o n sb a s e do na b s t r a c ts y n t a xt r e e k e y w o r d s ：x m l ，x q u e r y , q u e r yp r o c e s s i n ge n g i n e ，a b s t r a c ts y n t a xt r e e i 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取 得的研究成果除加以标注和致谢的地方外，不包含其他人已经发表或 撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确 的说明并表示谢意。 学位论文作者签名：荣蓉宇 日期：加步 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学 位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的 复印件和磁盘，允许论文被查阅和借阅。本人授权东北大学可以将学 位论文的全部或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名；否则视为不同意。) 学位论文作者签名： 签字日期： 导师签名： 签字日期： 东北大学硕士学位沦文第一章引言 第一章引言 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 ) i l l 是一种简单的、自描述的语言，以其数据 和表现相分离的特性和强大的数据表达能力，已经逐渐成为互联网和数据库之间 沟通的桥梁。 x m l 的出现最初是因为h t m l l2 】标记语言的不足。一方面，h t m l 无法满足 各行各业的需求，越来越多的标签使得h t m l 日渐臃肿；另一方面，h t m l 语言 有固定的格式，它注重的是如何显示，不关心实际数据的语义，内部结构缺乏条 理。针对这些缺点，w 3 c 开发的x m l 显示了它独特的优势：( 1 ) 自由优势。有了 x m l ，各行业可以自由地制定自己的置标语言，而不必征求w 3 c 首肯，也不必开 发新的浏览器来支持新的标记。( 2 ) 超越格式。x m l 跟h t m l 不同，它通过样式 表来把显示格式从文档中分离出去，而x m l 文档本身则只包含文档的结构和内容 描述，侧重于数据的语义，这种文档的内容和格式相分离的好处是，一方面如果 需要改动信息的表现方式时，不必改动信息的本身；另一方面在x m l 中数据搜索 可以简单高效地进行。搜索引擎不必再去遍访整个x m l 文件，它只须去查找相关 标记下的内容就够了。( 3 ) x m l 遵循严格的语法要求。严格的语法要求对网页文件 可以提供较好的可读性和可维护性，浏览器开发人员也大大减轻了负担。( 4 ) x m l 便于不同系统之间信息的传输。当今的计算机世界中，不同部门之间存在着许多 不同的系统、不同的数据库，要想在这些不同的平台之间传输信息，不得不使用 一些特殊的软件，非常的不便。而由于x m l 的简单性，它可以很容易的以x m l 为交流的媒介来实现异质系统间的信息互通。( 5 ) 数据保值。一些如w o r d ，p d f 等 二进制格式的这类文件，只要一处损坏，可能整个文件都不可用了，同时由于软 件升级和新软件的不断出现，二进制的文件格式也在不断变化，不利于长久保存 文件，而由于x m l 语言的自描述性，且以文本方式存在，就避免了这种缺点，可 以用它来进行数据的保值。 x m l 也有着自身的一点缺陷：由于x m l 的半结构化特性【3 】，使得传统的数 据管理技术不能完全满足对x m l 数据的存储以及查询管理的需要，针对x m l 数 据的数据库管理技术一直进行着更加深入的研究。 1 东北大学项士学位论文 第一章引言 综上所述，x m l 有着广泛的前景。实际上也是如此，自1 9 9 8 年2 月成为w 3 c 推荐标准以来，它受到了广泛的支持。各大软件厂商如i b m 、m i c r o s o f t 、o r a c l e 、 s u n 等都积极支持并参与了x m l 的研究和产品化工作，w 3 c 也一直致力于完善 x m l 的整个理论体系。 1 1x m l 的逻辑结构 x m l 是一个遵循着严格语法要求的置标语言，一个x m l 文档应该是良构 ( w e l l f o r m e d ) 的x m l ，它的要求是这样的：所有的构造从语法上讲都是正确的。 要求只有一个根元素，所有的起始标记都要有与之相对应的终止标记，或者使用 空元素标记，所有的标记都要正确地嵌套。另外，元素的所有属性都使用不同的 名字。同时，一个元素的所有命名空间声明必须赋予不同的前缀。为了保证x m l 文档标签之间的层次结构，这些要求是必要的。 1 1 1 一个舭实例文档 为了对x m l 的逻辑结构进行说明。我们通过一个例子来进行阐述。表1 1 是 一个x m l 实例文档。行( 1 2 】是处理指令，以“ ”结束，负责 提供x m l 文件的基本信息，供应用程序处理使用：其中的行 1 】是一个x m l 声明， 它给出了x m l 文档所采用的x m l 版本号，数据所采用的编码方式等信息，以及 是否和外部d t d ( 文档类型定义1 配合使用，分别由v e r s i o n 属性，可选的e n c o d i n g 属性及s t a n d a l o n e 属性给出；处理指令行 2 则给出了x m l 文档的样式表的信息， 指出了显示该x m l 文档时所应使用的样式文件s a m p l e x s l 。行 3 】是外部d t d 使 用说明。行 5 是注释，用作解释的字符数据。行 4 】 2 6 是文件中的各个元素，在 本例子中共有2 6 个元素，其中的b i b 元素从头部声明之后开始一直到文件尾，包 含了文件中所有的元素信息，称它为根元素，任何元素都是它的后代。b i b 有三个 b o o k 子元素，每个b o o k 元素又是不同的，都有着自己的属性y e a r 和子元素，b o o k 的子元素中a u t h o r 、e d i t o r 也有自己的l a s t 和f i r s t 子元素，而其他b o o k 子元素t i t l e 、 p u b l i s h e r 、p r i c e 都有一个文本类型的元素作为其子结点以表示其取值，这种以父 子和兄弟为基础的关系构成了整个x m l 的层次关系。 ， 东北大学硕士学位论文第一章引言 表1 1x m l 实例文档 t a b l e1 ，1a ne x a m p l eo f x m ld o c u m e n t 0 1 】 0 9 a d d i s o n - w e s l e y 1 0 】 6 5 9 5 【1 1 1 2 d a t ao nt h ew e b 【1 3 】 a b i t e b o u l s e r g e 【1 4 】 s u c i u d a n 刮f i r s t 【1 5 m o r g a nk a u f m a n np u b t i s h e r s 【1 6 3 9 9 5 【1 7 1 8 t h ee c o n o m i c so ft e c h n o l o g ya n dc o n t e n tf o rd i g i t a l 【1 9 】 t v 2 0 】 2 1 g e r b a r g d a r c y 【2 2 】 c r r i 2 3 】 【2 4 】 k l u w e ra c a d e m i cp u b l i s h e r s 2 5 】 1 2 9 9 5 2 6 1 1 2x m l 结构要素 在上例中已经阐述的位于x m l 文档头部的三个结构要素：x m l 声明、文档 样式表信息、d t d 使用说明，它们对于x m l 文档提供了重要的信息，但是元素 是构成文档内容的最基本要素。x m l 的其他结构要素多与元素相关。除此之外， 3 东北大学硕士学位论文 第一章引言 表l1 x m l 实倒文档 t a b l e l l a ne x a m p l eo f x m l d o c u m e n t 叭】 ? x m lv o r s t o n = ”1 0 ”s t a r t d a l o n e = n 0 ”? ) 【0 2 】( ? x h d s 【y l e s h e e tt y p e - - t e x t x s l h r e f - - ”s a r a p l ex s l ”协 f 0 3 【0 4 f 0 5 c o s l s t e v e n s w 0 9 】 a d d i s o n - w e s l e y 1 0 】 6 59 5 【1 1 】 【1 2 d a t ao n t h ew e b 1 5 】 m o r g a nk a u f m a n np u b l i s h e r s p u b l i s b e r ( 1 6 】p n c e 3 9 9 5 1 7 】d o o o k y e a r = “1 9 9 9 。) f 1 8 】 t h ee c o n o m i c s0 f t e c ? m o l o g ya n dc o n t e n tf o rd i o t a l 【1 9 t v 2 6 】 1 1 2x m l 结构要素 在上例中已经阐述的位于x m l 文档头部的三个结构要素：x m l 声明、文档 样式表信息、d t d 使用说明，它们对于x 3 v i l 文档提供了重要的信息，但是元素 是构成文档内容的最基本要素。x m l 的其他结构要素多与元素相关。除此之外， 是构成文档内容的擐基本要素。x m l 的其他结构要素多与元素相关。除此之外， 3 东北大学硕士学位论文 第一章引言 与本文相关的主要结构要素还有：c d a t a 、标签、属性、注释和文档类型定义 d t d 。下面分别加以详细阐述。 元素是x m l 文件内容的基本单元。由一对标记串行化而成：起始标记、结束 标记以及标记之间的数据内容。元素的内容可以是嵌套的子元素，也可以是文本。 把x m l 中开始和结束标记之间的文字称作“字符数据”，而把标示文字称作“标 签( t a g n a m e ) ”。当在字符数据中需要使用某些特殊符号 时，我们采用它的实体引用来代替。这些特殊的x m l 实 体引用包括表1 2 所示的一些常用的实体引用。在不能使 用或是要频繁使用这些特殊字符的时候，我们可以用 c d a t a 进行块转义文字文本。 c d a t a 是在不能使用实体引用取代禁用字符的时 候，可以用它来“块转义( b l o c ke s c a p e ) ”文字文本。c d a t a 段可以显示在元素内容中，并且允许小于号( ( ) 和符号文 表1 2 实体引用 t a b l e l 2e n t i t yr e f e r e n c e s 字符实体引用 & g t ： i t ： & a m p ： q u o t ： & a p o s ： 字显示。c d a t a 段以字符序列 结束。在这两个字 符序列之间，x m l 处理程序忽略所有的标记符号。 标签是x m l 语言的精髓。因此，标记在x m l 的元素中、乃至整个x m l 文 件中，占了举足轻重的位置。x m l 的标记和h t m l 的标记在模样上大体相同，除 了注释和c d a t a 部分以外，所有符号“ ”之间的内容都称为标记。 标签有如下特性：( 1 ) 标记必不可少；( 2 ) 大小写有所区分；( 3 ) 要有正确的结束标 记；( 4 ) 标记要正确嵌套；( 5 ) 标记命名要合法；( 6 ) 有效使用属性。 属性是对元素加以注释。属性通常用来编码实际数据或者为元素提供元数据， 也就是说，提供关于元素所显示内容的额外信息。给定元素的属性被串行化在元 素的起始标记中。属性表示为用等号( “= ”) 分开的名，值对。属性名与元素名有相 同的构造规则。属性值是自然的文本形式。元素可以有任意数目的属性，但是它 们的名称必须不同。如表1 1 中的， 表示b o o k 元素有一个y e a r 属性，y e a r 的值是一个整数2 0 0 0 。 注释通常是为用户提供有关真实的x m l 内容的信息。注释不能用来编码真实 的数据。注释可以作为元素的后代出现，也可以作为顶层结构( 文档的后代) 出 矗 东北大学硕士学位论文第一章引言 现在文档元素的前砥或者后面。注释使用字符序列 作为结束。 元素有名字，也可能有后代。这些后代可能本身就是元素或者是处理指令、 注释、字符数据( c d a t a ) 段或者字符。元素后代是有序的。 文档类型定义0 ) t d ) 就是一个被用来描述特定类型的x m l 文档的层次结构的 重要要素。通过d t d 可以允许文档的编写者制定基于信息描述、体现数据之间逻 辑关系的自定义标记，确保文档的易读性、清晰的语义和易检索性。在表1 ，l 例中， 文档的第3 行说明了外部d t d 文件名为s a m p l e d t d ，并与x m l 文件处于同一目 录下。通过d t d 文件可以检测x m l 文档的结构是否正确。一个遵守x m l 语法 规则，并遵守相应d t d 文件规范的x m l 文档我们称之为有效的x m l 文档( v a l i d x m l ) ，与“w e l l f o r m e d ”的x m l 相比，它们最大的差别在于一个完全遵守x m l 规范，一个则有自己的“文件类型定义( d t d ) ”。x m l 解析器利用d t d 来验证 x m l 文档的正确性。 d t d 分为外部d t d ( 在x m l 文件中调用另外已经编辑好的d t d ) 和内部 d t d ( 在x m l 文件中直接设定d t d ) 两种，外部d t d 的优点是可以被多个x m l 文档所引用。x m l 本身并没有一个通用的d t d ，想使用x m l 进行数据交换的行 业或组织可以定义它们自己的d t d 。所以d t d 通常是以某种应用领域为定义的范 围，d t d 定义的元素涵盖范围越广泛，那么就越复杂。 1 2s a x 和d o m 无论我们想创建、访问或是操作一个x m l 文件。我们所开发的应用程序 都需要能够读懂x m l 文件，从中提取我们所需要的信息。一个统一的x m l 数据 接口也是必需的。w 3 c 意识到了上述问题的存在，于是制定了一套书写x m l 分 析器的标准接口规范d o m 【“。除此之外，x m l _ d e v 邮件列表中的成员根据应 用的需求也自发地定义了一套对x m l 文档进行操作的接口规范s a x 【5 。这两种 接口规范各有侧重，互有长短，应用都比较广泛。 下面，我们给出d o m 和s a x 在应用程序开发过程中所处地位的示意图。从 图1 1 中可以看出，应用程序不是直接对x m l 文档进行操作的，而是首先由x m l 5 东北大学硕士学位论文第一章引言 分析器对x m l 文档进行分析，然后应用程序通过x m l 分析器所提供的d o m 接 口或s a x 接口对分析结果进行操作，从而间接地实现了对x m l 文档的访问。 圈1 1 d o m 和s a x 接口地位示惹图 f i g u r e1 1t h ep o s i t i o no f d o m a n ds a xi n t e r f a c es k e t c hm a p 在这一节里，我们就来介绍由w 3 c 和x m ld e v 邮件列表成员分别提出的两 个标准应用程序接口：d o m 和s a x 。 1 2 1d o m 标准 d o m 的全称是d o c u m e n t o b j e c t m o d e l ，也即文档对象模型。在应用程序中， 基于d o m 的x m l 分析器将一个幢l 文档转换成一个对象模型的集合，应用程 序正是通过对这个对象模型的操作，来实现对x m l 文档数据的操作。通过d o m 接口，应用程序可以在任何时候访问x m l 文档中的任何一部分数据，因此，这种 利用d o m 接口的机制也被称作随机访问机制。 d o m 接口提供了一种通过分层对象模型来访问x m l 文档信息的方式，这些 分层对象模型依据x m l 的文档结构形成了一棵节点树。由于x m l 本质上就是一 种分层结构，所以这种描述方法是相当有效的。在这棵节点树中，文档中所有的 内容都是用节点来表示的，一个节点又可以包含其他节点，节点本身还可能包含 一些信息，例如节点的名字、节点值、节点类型等。文档有一个根节点一d o c u m e n t 节点，之所以要把它单独列出来，是因为在x m l 文档中，所有其他的节点都是根 节点的后代节点，而且根节点是唯一的，具有其他节点所不具有的某些特征。节 点树生成之后，就可以通过d o m 接口访问、修改、添加、删除、创建树中的节点 和内容。 d o m 标准是为文档操作制订的一组程序a p i 。在d o m 接口规范中，有四个 基本的接口：d o c u m e n t 、n o d e 、n o d e l i s t 以及n a m e d n o d e m a p 。在这四个基本接 6 东北大学硕士学位论文第一章引言 口中，( 1 ) d o c u m e n t 接口代表了整个x m l 文档，因此，它是整棵文档树的根，提 日 供了对文档中的数据进行访问和操作的入口。d o c u e m t 节点是从n o d e 接口继承过 来的。( 2 ) n o d e 接口在整个d o m 树中具有举足轻重的地位，d o m 接口中有很大 一部分接口是从n o d e 接口继承过来的，像d o c u m e t ，e l e m e n t ，a t t r i b u t e ，t e x t ， c o m m e n t 、c d a t a s e c t i o n 等接口都是从n o d e 接口继承过来的。( 3 ) n o d e l i s t 接口 提供了对节点集合的抽象定义，它并不包含如何实现这个节点集的定义。n o d e l i s t 用于表示有顺序关系的一组节点，比如某个节点的子节点序列，n o d e l i s t 中的每 个i t e m 都可以通过一个索引来访问，该索引值从0 开始。( 4 ) n a m e d n o d e m a p 接口 的对象中包含了可以通过名字来访问的一组节点的集合。不过，n a m e d n o d e m a p 并不是从n o d e l i s t 继承过来的，它所包含的节点集中的节点是无序的。尽管这些 节点也可以通过索引来进行访问，但这只是提供了枚举n a m e d n o d e m a p 中所包含 节点的一种简单方法，并不表明在d o m 规范中为n a m e d n o d e m a p 中的节点规定 了一种排列顺序。 1 2 2s a x s a x 的全称是s i m p l e a p i sf o rx m l ，也即x m l 简单应用程序接口。与d o m 不同，s a x 提供的访问模式是一种顺序模式，这是一种快速读写x m l 数据的方 式。当使用s a x 分析器对x m l 文档进行分析时，会触发一系列事件，并激活相 应的事件处理函数，应用程序通过这些事件处理函数实现对x m l 文档的访问，因 而s a x 接口也被称作事件驱动接口。 它的基本原理是由接口的用户提供符合定义的处理器，x m l 分析时遇到特定 的事件，就去调用处理器中特定事件的处理函数。一般s a x 接口都是用j a v a 实 现的。在s a x 接口规范中，有六个基本a p i 接口：s a x p a r s e r f a c t o r y 、p a r s e r 、 d o c u m e n t h a n d l e r 、e r r o r h a n d l e r 、d t d h a n d l e r 、e n t i t y r e s o l v e r 。在这几个基本的 接口中，( 1 ) s a x p a r s e r f a c t o r y 接口的对象用来按照系统属性中的定义创建一个分 析器的实例。( 2 ) p a r s e r 接口定义了类似s e t d o c u m e n t h a n d l e r 的方法来创建事件处 理函数。另外，该接口中还定义了p a r s e r ( u r l ) 方法来对x m l 文档进行实际的分 析工作。( 3 ) d o c u m e n t h a n d l e r 接口。当分析器遇到x m l 文档中的标记时，就会激 7 东北大学硕士学位论文第一章引言 活该接口中的s t a r t d o c u m e n t ，e n d d o c u m e n t ，s t a r t e l e m e n t 以及e n d e l e m e n t 等方法。 0 ( 4 ) e r r o r h a n d l e r 接口。当分析器在分析过程中遇到不同的错误时，e r r o r h a n d l e r 接 口中的e r r o r 、f a t a l e r r o r 或者w a r n i n g 方法就会被激活。( 5 ) d t d h a n d l e r 接口。当处 理d t d 中的定义时，就会调用该接口中的方法。( 6 ) e n t i t y r e s o l v e r 接口。当分 析器要识别由u r i 定义的数据时，就会调用该接口中的r e s o l v e e n t i t y 方法。 d o m 接口和s a x 接口有着各自的优缺点。也正是如此，它们一直长期并存 着，在不同的应用中发挥不同的作用。 d o m 树所提供的随机访问方式给应用程序的开发带来了很大的灵活性，它可 以任意地控制整个x m l 文档中的内容。然而，由于d o m 分析器把整个x m l 文 档转化成d o m 树放在了内存中，因此，当文档比较大或者结构比较复杂时，对内 存的需求就比较高。而且，对于结构复杂的树的遍历也是一项耗时的操作。所以， d o m 分析器对机器性能的要求比较高，实现效率不十分理想。不过，由于d o m 分析器所采用的树结构的思想与x m l 文档的结构相吻合，同时鉴于随机访问所带 来的方便，因此，d o m 分析器还是有很广泛的使用价值的。 s a x 不是通过构造棵节点树，而是通过遍历整个x m l 文档，并且根据遇 到的标记激活事件。s a x 分析器在对x m l 文档进行分析时，触发了一系列的事 件，由于事件触发本身是有时序性的，因此，s a x 提供的是一种顺序访问机制， 对于已经分析过的部分，不能再倒回去重新处理。同d o m 分析器相比，s a x 分 析器缺乏灵活性。然而，由于s a x 分析器实现简单，对内存要求比较低，因此实 现效率比较高，对于那些只需要访问x m l 文档中的数据而不对文档进行更改的应 用程序来说，s a x 分析器更为合适。 综上所述，由于s a x 接口的特点，更适合我们需要，所以我们系统采用的是 s a x 接口实现对x m l 文档的访问。 1 3x m l 数据管理技术介绍 x m l 作为一个数据交换和表示的国际标准，已经贯穿于i n t e m e t 应用的各个 领域规划之中，带来了大量的x m l 格式的数据，从而使得x m l 已经成为一套新 8 东北大学硕士学位论文第一章引言 的数据管理需求。目前x m l 数据的存储管理有四种方式：文本文档、关系数据库、 对象数据库及n a t i v e 数据库。由于出发点不同，造成它们在x m l 数据的存储功能 以及x m l 查询效率上各有所长。具体x m l 数据存储管理方式如图1 2 所示。 图1 , 2x m l 数据存储管理方式 f i g u r e1 2 m o d eo f x m l d a t a m a n a g e m e n ts y s t e m s 由于x m l 数据的一般表现形式是文本文件，因此管理x m l 数据的最简单的 方法就是直接将它们存储于文件系统中，对于x m l 数据的访问入口就是文件系 统提供的句柄。这种存储方式的优点是：存储方便，成熟的信息检索技术可以直 接得到应用，不需要任何额外操作；可以使用基于d o m 或s a x 的工具。缺点有： 没有存储控制，不能为结构化查询提供支持，信息检索方法查询功能简单，d o m 方 式无法支持大文档查询，每查询一次都要重新解析，数据访问速度较慢等等。 对于关系数据库来讲，由于关系数据库技术已经非常成熟，而且目前绝大多 数的数据都是存储在关系数据库中，因此，使用关系数据库系统来存储和查询x m l 数据是另外一个选择。当我们将x m l 数据存入关系数据库中时，包含不同关系 ( r e l a t i o n ) 的模式必须被恰当定义以作为存储x m l 数据的模式。使用关系数据库 管理x m l 数据主要包含以下几个步骤：( 1 ) 为x m l 数据定义合适的表模式，并将 其存储到关系表中。( 2 ) 利用文档d t d 信息和文档本身的信息将x p a t h ( x q u e r y ) 查 询语句转化为s q l 语句。( 3 ) 套询优化，查询执行。( 4 ) 将查询结构以x m l 的格式 提交给用户。使用关系数据库技术来管理x m l 有两个比较明显的缺点：一是x m l 的数据模型与关系模型有显著不同。x m l 数据是半结构化的，而关系表是二维表 9 东北大学硕士学位论文第一章引言 结构。无论存储还是查询都要在两种格式之间相互转化。二是x m l 查询语言支持 许多复杂的语义，比如正则表达式中的闭包操作符，这在s q l 中是找不到与之对 应的部分的。 对于对象数据库来讲，o d m g 6 1 标准为面向对象数据库定义了对象模型( o b j e c t m o d e l ) ，对象定义语言( o d l ) 和对象查询语言( o q l ) 。因为x m l 在描述数据时采 用在不同层次上的嵌套关系，在理论上，将树型结构数据映射为嵌套对象模型比 映射为普通的关系表结构更自然，而且对象数据库中的对象路径表达式查询也比 关系表之间的连接操作与对于x m l 数据的路径遍历操作更相似，因此一些系统 采用了对象技术来管理x m l 数据。文献 7 提出了两种基于对象数据库的x m l 数 据存储映射技术。第一种是用不变的特制o d m go d l 模式存储x m l 数据，模 式类似予x m l 文档对象模型l o o m ) 。第二种方法则为每一种x m l 元素类型映射 一个对象类型，x m l 元素之间的关系使用o d m g 提供的类之间的联系 ( r e l a t i o n s h i p ) 来实现。虽然对象数据模型以其复杂类型支持和丰富的查询语义使锝 它在表示与查询x m l 数据上比关系数据库有着天然的优势，然而商用对象数据 库的技术并没有得到广泛的认可和应用，技术发展得并不是很成熟，特别是对大 规模数据的复杂查询能力上还有欠缺。 作为一种新的数据格式，x m l 数据有着与关系模型数据和对象数据都不完全 相同的性质，因此专门为x m l 数据设计存储模型与索引技术，研究特定的查询处 理技术以及查询优化策略成为目前一个研究热点。这样的x m l 数据管理系统被称 为n a t i v e x m l 数据库( n a t i v e x m l d a t a b a s e ) 。它支持x m l 文档的结构并保留 它们的数据层次结构和意义，同时定义为一个x m l 文档的模型并按照该模型来保 存和检索讧l 文档。斯坦福大学的l o r e 嘲系统是讧l n a t i v e 数据库的代表l 0 r e 【7 】， 其它比较著名的还有t a m i n o1 9 等。这些系统专门为x m l 这一特殊的数据类型设 计存储模型与索引技术。由于x m ln a t i v e 数据库采用了针对x m l 本身特点而设 计的存储方案和查询策略，因此，虽然目前n a t i v ex m l 数据库系统的研究还处于 起步阶段，各种技术还不成熟，但它在处理) ( m l 数据时拥有传统数据库所不能比 拟的天生优势，已促使越来越多的目光聚焦到它上面。随着时间的推移，相信n a t i v e x m l 数据库系统也会得到前进。 1 0 东北大学硕士学位论文 第二章x q u e r y 查询语言 第二章x q u e r y 查询语言 x m l 的查询语言o 】经历了一个比较复杂的发展过程。x m l 可以灵活的表示 多种不同数据源的不同信息，为了使这种灵活性得到最大程度的发挥，人们设计 了多种x m l 查询语言，用它们来从这些多样的数据源中获得查询数据。人们提出 并使用过的查询语言有x s l 1 “、x q l t l ”、x m l - q l t l3 1 、y a t l 1 4 1 、l o r e l 8 1 等。每种 语言都有自己的优点，满足一定的x m l 查询需要，但作为一个通用的查询语言又 有些不足。在这种情况下d o mc h a m b e r l i n 等人提出了q u i l t 1 5 语言，现在已经被 w 3 cx m lq u e r yw o r k i n gg r o u p 采用，作为x q u e r y 语言的基础。x q n e r y 具有上 述很多语言的优点，如x q u e r y 吸收了x q l 语言的路径表达式，x m l q l 语言的 变量绑定机制，o q l 中的函数概念等。 x q u e r y 1 6 1 的基础是表达式。每一个x q u e r y 查询包括一个或多个查询表达式。 常用的x q u e r y 语法有：( 1 ) 路径表达式( p a t he x p r e s s i