（计算机软件与理论专业论文）xml数据索引和语义约束.pdf

摘要 摘要 随着互联网的飞速发展，x m l 以其强大的数据表达能力以及简单、开放性、 可扩展等优点而逐渐成为互联网上信息发布和数据交换的事实上的标准，因此对 x m l 数据进行有效地管理和查询的要求也越来越迫切。同时，各种各样的x m l 查询语言被提出来了。路径表达式是这些查询语言的重要组成部分，因此高效地 处理路径表达式成为提高x m l 查询效率的关键所在。 对x m l 而言，一个公认的问题是：只有语法意义而缺乏语义信息。为了回 应这神批评，研究者们提出了各j f 中各样的语义约束。虽然x m l 已经作为数据交 换的主要格式和标准而应用于各行各业，但是在实际的应用中，为了有效地利用 关系数据库成熟的数据管理功能来处理x m l 数据，并且能够利用基于关系数据 库的应用系统，通常需要把x m l 存储在本地的关系数据库中。在提出x m l 语 义约束后，当用关系数据库存储x m l 文档时，如何把这些语义约束信息映射到 关系数据库中是一个重要的研究课题，具有较高的理论价值和现实意义。 本文对上述两个方面的问题进行了相关的研究，具体地说，本文的主要贡献 和创新之处在于： 提出了一种新型的x m l 索引结构：u o ( k ，1 ) 一索引，该索引充分利用了 x m l 数据节点之间在向上和向下路径上的局部相似性，因此能够有效 地处理路径表达式的查询，特别是分支路径表达式的查询。 对u d ( k n 一索引在索引大小、生成时间、路径查询性能等方面进行了详 细的实验，并与1 索引和a ( k ) 索引作了对比和分析。实验研究表明， u d ( k ，1 ) 一索引具有较短的生成时间，并能够以相对较小的空间代价获得 较好的查询性能。 研究了两种形式的x m l 语义约束：x m l 键和x m l 函数依赖，并提出 - f n 应的算法用来当存储x m l 文档到关系数据库中时把x m l 上的语 义约束转换成关系数据库上相应的语义约束a 基于上述x m l 键转换算法，开发了用来把x m l 键转换成关系数据库 键约束的k e y g e n 原型系统。 关键字：x m l ，索引，语义约束，x m l 键，x m l 函数依赖，约束映射 a b s t l j c t a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to ft h ei n t e m e t , x m lh a sg r a d u a l l yb e c o m e t h ed e f a c t os t a n d a r df o ri n f o r m a t i o np u b l i c a t i o n ，d a t ae x c h a n g eo n t h ei n t e m e t k n o w nf o r i t s s t r o n gd a t ar e p r e s e n t a t i o nc a p a b i l i t y , o p e n n e s s ，e x t e n s i b i l i t ya n dn u l n g r o u so t h e r b e n e f i t s ，t h u si ti sm o r ea n dm o r ei n d i s p e n s a b l et o m a n a g ea n dq u e r yx m l d a t a e f f i c i e n t l y m e a n w h i l e ，v a r i o u sx m lq u e r yl a n g u a g e sh a v eb e e np r o p o s e d ，i nw h i c h p a t he x p r e s s i o n t a k e sau b i q u i t o u s p a r t t h u s ，e f f i c i e n t x m l p a t he x p r e s s i o n p r o c e s s i n gp l a y sak e y r o l ei nx m l q u e r y e v a l u a t i o n a r e c o g n i z e dp r o b l e m f o rx m li st h a ti to n l y p r e s e n t ss y n t a xa n d d o e sn o tc a r r y t h es e m a n t i c so ft h ed a t a i nr e s p o n s et ot h i sc r i t i c i s m ，s o m es e m a n t i cc o n s t r a i n t so f x m lh a v eb e e np r o p o s e d a l t h o u g hx m lh a sb e e nu s e df a ra n dw i d ea st h em a i n s 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 e ，i np r a c t i c a la p p l i c a t i o n s ，x m ld a t ai s u s u a l l ys t o r e di nr e l a t i o n a ld a t a b a s e s t h e r e f o r e ，t h ee x i s t i n gm a t u r et e c h n i q u e so f r e l a t i o n a ld a t am a n a g e m e n tc a nb e f u l l yu t i l i z e d ，a n d t h el o c a lr d bb a s e d a p p l i c a t i o n s y s t e m sc a n b eu s e da sw e l l a f t e rx m l s e m a n t i cc o n s t r a i n t sh a v eb e e nd e f i n e d ，i ti s i m p o r t a n tt om a pt h e s ex m l s e m a n t i cc o n s t r a i n t si n t or e l a t i o n a lc o n s t r a i n t sw h e n s t o r i n gx m l d a t ai n t or e l a t i o n a l d a t a b a s e s c o n s e q u e n t l y , t h i s r e s e a r c hi s s u ei s v a l u a b l eb o t ho nt h e o r ya s p e c t sa n dr e a l i s t i ca p p l i c a t i o n s i nt h i s d i s s e r t a t i o n ，t h ea b o v et w oi s s u e s a r es t u d i e d t h em a i nn o v e l t ya n d c o n t r i b u t i o n sc a nb es u l t l m a r i z e da sf o l l o w s ： b a s e do nt h ea n a l y s i so fs o m ee x i s t i n gx m li n d e xt e c h n i q u e s ，an o v e li n d e x s t r u c t u r e ，l i d ( k ，1 ) 一i n d e x ，i sp r o p o s e d , w h i c hf u l l ye x p l o i t s t h eu p w a r da n d d o w n w a r ds i m i l a r i t yi nt h es t r u c t u r eo fx m l d a t an o d e s s ot h a ti tc a n e f f i c i e n t l ys u p p o r tp a t he x p r e s s i o ne v a l u a t i o n ，e s p e c i a l l yb r a n c h i n gp a t h e x p r e s s i o n e v a l u a t i o n ， - d e t a i l e de x p e r i m e n t sa r ec o n d u c t e dt oc o m p a r et h ei n d e xs i z e s ，t h ec r e a t i o n t i m e ，t h eq u e r y p r o c e s s i n gp e r f o r m a n c e sf o rb o t hp l a i np a t he x p r e s s i o n sa n d b r a n c h i n gp a t he x p r e s s i o n s o fu d ( k ，1 ) 一i n d e xw i t ht h o s eo f1 - i n d e xa n d a ( k ) 一i n d e x i na d d i t i o n ，t h ea n a l y s i so fe x p e r i m e n t a lr e s u l t si sa l s op r e s e n t e d t h ep r e l i m i n a r ye x p e r i m e n t ss h o wt h a tu d ( k ，1 ) 一i n d e xh a sl e s sc o n s t r u c t i o n t i m e ，a n dc a ne f f i c i e n t l ys u p p o r tp a t hq u e r i e so f b o t hp l a i np a t he x p r e s s i o n s a n d b r a n c h i n gp a t he x p r e s s i o n s w i t h r e l a t i v e l yl o ws p a c e o v e r h e a d _ t w o t y p e so fx m l s e m a n t i cc o n s t r a i n t sa r es t u d i e d ：x m lk e ya n dx m l 2 a b s t r a c t f u n c t i o n a ld e p e n d e n c y a n dt h ec o r r e s p o n d i n ga l g o r i t h m sa r ep r o p o s e dt o m a px m l s e m a n t i cc o n s t r a i n t st or e l a t i o n mc o n s t r a i n t sw h e ns t o r i n gx m l d a t ai n t or e l a t i o n a ld a t a b a s e s _ b a s e do nt h ex m lk e ym a p p i n ga l g o r i t h m ，ap r o t o t y p es y s t e m ，n a m e d k e y g e n ，h a s b e e n d e v e l o p e d t od e r i v er e l a t i o n a lk e y sf r o mx m l k e y s k e y w o r d s ：x m l ，i n d e x ，s e m a n t i c c o n s t r a i n t s ，x m lk e y , x m lf u n c t i o n a l d e p e n d e n c y , c o n s t r a i n tm a p p i n g 3 第一章绪论 第一章绪论 1 1 研究背景 x m l 是( 可扩展标记语言，e x t e n s i b l e m a r k u p l a n g u a g e ) b p s + 9 8 的缩写，是 w 3 c ( 全球互联网联盟) 于1 9 9 8 年2 月正式推出来的。x m l 的出现，改变了 w e b 的基本面貌，它以其独有的特点逐渐脱颖而出，成为w e b 上数据表示和交 换的标准格式。x m l 是一种文档标注( m a r k u p ) 语言，用来描述文档的内容和结 构，它的提出是为了弥补h t m l 在w e b 数据交换上的不足。x m l 是s g m l ( s t a n d a r dg e n e r a lm a r k u pl a n g u a g e ) i s 0 8 6 的一个优化子集，它将s g m l 的丰富 功能与h t m l 的易用性结合到w e b 应用中，和s g m l 比，它更为轻量级，使得 现有的i n t e m e t 协议和软件的协作性更好，从而简化了数据的处理和传输，所以 更适合软件开发和信息分布。与h t m l 相比，x m l 具有许多优点： 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 非常适于 w e b 信息的发布和集成。 h t m l 中的标记表示的是数据的显示格式，没有任何语义，而x m l 的标 记则明确指出了数据的含义，使得细粒度的x m l 数据处理成为可能。 x m l 实现了内容、结构和表现三者的分离。文档类型定义( d t d ) 描述 了文档中元素和子元素间的嵌套结构，不同的用户可以通过x s l 按不同 的显示方式显示全部或部分的文档内容。 x m l 自出现以来，就受到了各界的关注，已经有许多公司全力支持x m l ， 比如a d o b e 公司的f r a m e m a k e r s ，a l t o v a 公司的x m l s p y 可以用来书写x m l 文 档，m i c r o s o f t 公司推出的i e 也支持显示x m l 文档。各大公司推出的其它产品 也支持和使用x m l ，比如a p a c h e ，w e b l o g i c ，j b u i l d e r 等用x m l 表示各种配置信 息，m s nm e s s e n g e r 把x m l 作为一种数据库来保存信息。m i c r o s o f t 新版 o f f i c e 2 0 0 3 通过将文档保存为x m l 文件，可以让企业数据库等后端运算系统重 新得到以及重新使用文档中的数据。人们也逐渐从信息检索( i n f o r m a t i o n r e t r i e v a l ) 的角度看待x m l 过渡到从数据库的角度去认识它。值得提出的是， 数据库技术在x m l 中扮演着十分重要的角色，人们用数据库技术来存储、查询、 分析、加工和集成x m l 文档。各数据库厂商竞相在自己的产品中支持x m l ， 4 第一章绪论 比如o r a c l e9 i 中的x m l s q l u m i t y ，i b m d b 2 中的x m l e x t e n d e r ，以及m i c r o s o f t s q l s e r v e r2 0 0 0 中的x m la n di n t e m e t s u p p o r t 等等。 在工业界，x m l 的应用更是比比皆是：在电子数据交换领域，x m l 丰富的 格式语言可以用来描述不同类型的单据，例如信用证、贷款申请表、保险单、索 赔单以及各种发票等，而且结构化的x m l 文档送至w e b 的数据可以被加密，并 且很容易附加上数字签名。在电子交换的基础上，医院、保险公司、电信等各部 门相继制定了用于行业数据交换的d t d 标准( 如c x m l 、e b x m l 等) ；由m i c r o s o f t 和m a r i m b a 应用x m l 而提出了格式描述语言o s d ( 开放软件描述) ，它通过详 细说明软件的规格、使用说明以及运行平台等信息使得软件可以在网上能时时检 查，时时更新版本，而不用用户自己更新或是由软件提供商提供类似服务：在学 术界，相应类似的x m l 应用也十分广泛：在化学领域，化学标记语言c m l 可 以描述分子与晶体结构、化合物的光谱结构；在数学领域，数学标记语言m a t hm l 可以帮助数学家们将数学公式精确地显示在浏览器上；在生物和医学领域，基因 蛋白质数据g e n eb a n k 和s w i s sp o r t 、生物医学数据g e n e x 等等都是以x m l 的 形式存放。 应用驱动研究，正是由于应用的需要，关于x m l 方面的研究才受到研究人 员的广泛关注。首先，x m l 是一种半结构化数据，它不象传统数据那样是结构 化的，所以研究人员首先是把x m l 看作是半结构化数据来研究。而数据库界在 半结构化数据的数据模型、查询语言、查询优化、路径约束和模式抽取等方面的 研究已取得了一定的进展，因此x m l 可以借鉴这些研究成果。但是，x m l 毕 竟与半结构化数据不同，相比之下它们之间又有一些差别，因此又需要对x m l 专门作进一步深入研究，近几年，关于x m l 的研究已经成为s i g m o d p o d s 、 v l d b 、i c d e 等国际数据库界顶级会议的研究热点之一，几乎每个会议都有大 量关于x m l 的论文报告会和专题讨论。 下面将针对本文所涉及的几个研究方面介绍一下研究现状和本文的研究内 容。 1 2x m l 数据索引 随着讧l 成为互联网上数据表示和数据交换的标准格式，并在各个领域得 到广泛的应用，如何有效查询x m l 数据这个问题也日益变得重要。于是研究者 们提出了各种各样的查询语言，直 i l o r e a q m + 9 7 、x p a t h c d 9 9 、y a t l c j j 9 9 、 x m l q l f d f + 9 9 、x q l r l s + 9 8 、x s l a b c + 0 1 、q u i l t r c f 0 0 和x q u e r y 【b c f + 0 2 等。 传统的数据库得以成功的一个重要因素在于提供了高效的索引机制。为了提 第一蕈绪论 高x m l 数据的查询效率，同样需要借助索引技术。对x m l 数据的的访问既与 传统数据库由相似之处，又有所区别。一方砸，从内容的角度来看，x m l 数据 库是由大量的对象组成，原子类型的属性值以及具有特定属性值的对象是查询的 主要内容，这与传统数据库是相同的。另一方面，x m l 数据的形式又与传统数 据库又有很大的不同，x m l 数据是以文本形式表示的，结构可能是不规则的、 嵌套的。所以，x m l 数据索引可以借鉴传统数据中的方法，但不能原样照搬。 正因为如此，研究者们对x m l 索引技术的研究表示了极大的兴趣，提出了 多种对x n i l 数据进行索引的方法。文 w 0 2 把这些索引划分为：元素索引如 【z n d + 0 1 ，f k m 0 0 ，m w a + 9 8 ，l m o i 积路径索引如 g w 9 7 ，m s 9 9 ，s f + o t ，c m s 0 2 1 等。 上面提到的各种查询语言的一个重要特征是路径表达式的处理能力，例如 x p a t h c d 9 9 使用路径表达式来浏览x m l 文档的嵌套结构。在w 3 c 提出的第一 个查询语苦方案x q u e r y 【b c f + 0 2 之后，路径表达式不仅是一个结构化文档 上的基本的操作，而且成为几乎所有复杂操作的组成部分。处理路径表达式是 x m l 查询计算的一个重要部分。所以路径表达式处理效率的高低对x m _ l 查询 的性能至关重要。一个通用的处理路径表达式的技术是遍历x i v l l 文档中所有的 可能路径来找出匹配路径表达式的元黍。这种路径表达式的简单计算方法需要穷 尽整个x v l l 文档，其效率显然是低下的。通过使用路径索引，能够缩小搜索的 范围，显著地提高路径表达式的处理效率。本文在分析几种现有的路径索引技术 的基础，提出了一种新型的路径索引结构，它能够充分利用x m l 数据节点间在 向上和向下结构上的局部相似性，因此能够有效地处理路径表达式查询，特别是 带分支的路径表达式查询。 1 3 x m l 语义约束 一般来说，一个文档类型定义d t d 和一个x m ls c h e m a 都可以看作是一个 x m l 文档的模式或类型，在这种模式里定义了一些符合它们酌x m l 文档的约 束。就拿d t d 来说，d t d 中对元素属性值范围的规定，被称为域约束；对元素 出现次数的规定，如某元素可出现一次或零次，或必须出现次，或可以出现任 意多次，被称为势约束：包含依赖约束规定某元素属性的值必须出现在其他某元 素属性之中，这属于数据库中参照完整性约束概念的泛化；等值依赖约束规定某 元素最多只能有一个子元素，当它包含两个子元索实例时，两个子元素必相等： 双亲孩子关系约束规定元素间的包含关系。 但这些数据约束都是有限的。遵守d t d 和s c h e m a 中的约束规则，能够保 证x m l 文档在语法上正确，而语法上正确的文档不一定在语义上正确。而在实 第一章绪论 际应用中，我们需要指定这些语义信息，如在一本书中，所有的章节号不能重复； 对任意两个项目，如果零件相同，并且供货商相同，那么零件的价格也应该相同。 指定了这些语义信息，这样产生的文档才有实际意义。所以又有不少研究人员提 出x m l 的语义约束，并成为研究的热点之一。在这些语义约束信息中，b u n e m a n 等人在文 b d f + 0 1 q h 提出的x m l 键是一类十分重要的约束。他们还定义了如何 描述x m l 键，如何判断一个x m l 文档是否符合一些x m l 键，以及如何在x m l 键之间进行推导等等。文 f s w 0 1 进一步研究了包含向上通配符的键的定义及其 性质。在此基础上，又有不少研究人员提出其它的x m l 语义约束，包括t 0 kw a n g l i n g 等人提出的x m l 函数依赖 l l l 0 2 。 虽然x m l 已经成为了互联网上数据交换的主要格式和标准面得到广泛的应 用，但是在实际的应用中，我们通常需要把x m l 存储在本地的关系数据库中， 在网上进行数据交换时才以x m l 的方式进行。也就是说，在网上进行数据交换 之前，以及在网上进行数据交换之后，数据都可以不是以x m l 的形式而是以关 系数据的形式存在的。所以一个机构在进行数据交换之后，要把网上的x m l 文 档下载下来保存到关系数据库中，以备日后的查询和检索。由于x m l 数据是一 种层次结构的数据，而关系数据则是一种二维表的数据，所以要将x m l 文档保 存到关系数据库中并不是一件很容易的事情。过去几年中有很多学者都提出过多 种方法 s k w + 0 0 ，z n d + 0 1 ，f k 9 9 ，s t z + 9 9 ，m f o + 0 0 ，d f s 9 9 ，它们既能保存x m l 文档的内容，又能记录x m l 文档中各节点之间的结构信息。在x m l 语义约束提 出来之后，在用关系数据库保存x m l 文档的时候就要考虑如何保持这些语义信 息。 在本文中我们研究了这几种形式的x m l 语义约束，并研究了在存储x m l 文 档到关系数据库中时，如何映射和保持这些语义约束。 1 4 本文结构安排 本文共分五章。第一章介绍本文的研究背景，指出本文的研究内容。第二章 介绍x m l 相关的一些基础知识。第三章在分析现有的几种索引技术的基础上， 提出一种新的高效的x m l 索引技术。第四章研究了两种形式的x m l 语义约束， 并提出了三个把x m l 语义约束映射到关系数据库的算法。第五章为结束语，总 结了全文的工作，并展望未来的研究方向。 2 1x m l 语言 第二章x m l 基础知识 x m l ( e x t e n s i b l e m a r k u p l a n g u a g e ，可扩展置标语言) 是由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 ) 于1 9 9 8 年2 月发布的一种标准，是s g m l ( s t a n d a r dg e n e r a l i z e d m a r k u p l a n g u a g e ，标准通用置标语言) 的一个简化子集。由于它将s g m l 的丰 富功能与h t m l 的易用性结合到了w e b 的应用中，以一种开放的自我描述方式 定义了数据结构，在描述数据内容的同时能突出对结构的描述，从而体现出数据 之间的关系。这样所组织的数据对于应用程序和用户都是友好的、可操作的。 x m l 白推出以来，迅速得到主要软件开发商的支持和广大程序开发人员的喜爱， 显示出强大的生命力。 2 2x m l 文档 x m l 文档主要包括：x m l 声明、文档类型定义( d o c u m e n t t y p e d e f i n i t i o n ，简 称d t d ) 5 f i 文档实例。其中d t d 可以作为一个匹配x m l 文档的独立文件存在。 所有x m l 文档都必须以x m l 声明开始。x m l 声明其实是一个处理指令， 它指定合适的工具来处理x m l 文档。x m l 声明以“ ? x a n l ”为开始，指出目前 支持的版本、字符集和s t a n d a l o n e 属性值。s t a n d a l o n e 属性值表明该x m l 文件是 否和一个独立的d t d 文件配套使用。 x m l 文档实例主要由标注和文本构成，可被看作是x m l 文档的“正文” 部分。每段x m l 文本都有相应的标注，其中的标注必须符合x m l 规范。x m l 标注规范如下所示：x m l 使用标签( t a g ) 来标注数据。被一对匹配的起始标签 ( s t a r tt a g ) 和终止标签( e n dt a g ) ( 被称为一个标注( m a r k u p ) ) 所包含的数据称为一 个元素( e l e m e n t ) 。开始标签和结束标签的一个例子是 和 。元素 是x m l 文档的基本结构，元素可以包括嵌套的标签。每个元素可以附带属性 ( a t t r i b u t e ) 。属性可以具有有限的几种类型：i d 、i d s 、i d r e f 、i d r e f s 。这几种 类型被用来表示元素之间的引用关系。x m l 通过标注来描述整个文档。这也是 标注语言称谓的由来。一个x m l 文件的例子如下所示： a l a n 苎二兰兰竺! 苎型塑望 4 2 a g b a b c t o m 在x m l 文档中，使用d t d 来描述x m l 文件的语法格式。它可以是x m l 文件本身的一部分，不过通常都是单独成为另一个文件，或者甚至是一系列的文 件。d t d 是一种定义相应x m l 文档实例的机制，具体地说，d t d 定义了文档 实例的标签的语法规范。d t d 并不是x m l 文档的严格模式定义。它仅仅提供了 标注和属性可能出现的形式。同时，类型的说明是灵活且粗略的：用“? ”表示标 注不出现或出现一次，用“+ ，表示出现一次或多次，用“一表示出现任意次数： 标注之间可能以“或”( “ ”) 的关系出现，也可能以串联( “，”) 的形式出现。所以， d t d 只提供了简单的模式信息。另一方面，d t d 一般是文档的作者编写或选择 的，或者是某个领域的标准。于是，d t d 中的标注和属性所使用的词和标注之 间可能出现的嵌套结构可被认为是相应x m l 文档的提纲。即：d t d 反映了对应 x m l 文档的内容和结构信息。d t d 的创建是很灵活的，任何人、组织都可以写 些针对某一领域的d t d 来规范相应的x m l 数据。例如我们可以把h t m l 规 范中所有的标记信息看作一个所有人共用的d t d 。一个x m l 文档最多只有一个 d t d ，但一个d t d 可以是公用的，即定义多个x m l 文档的类型说明。一个d t d 的例子： 根据x m l 文档和d t d 的关系，x m l 文档可被分为两种相关的类型：良构 型( w e l l f o r m e d ) 和有效型( v a l i d ) 。两者都要符合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 基础知识 相关的d t d ：它必须在内部包含d t d ，或者显式地指明它所引用的外部d t d 文件。也就是，有效型x m l 文档中的元素只能按d t d 中指定的方式嵌套和拥 有d t d 规定的属性：而对标识符和引用来说，要求就很低了：i d 类型的属性值 必须唯一以及i d r e f 和i d r e f s 类型的引用必须指向存在的标识符。d t d 不 对被引用元素的类型作任何限制。 具有一定的结构性，但因自述层次的存在，从而是一种非完全结构化的数据， 这被称为半结构化数据。由于x m l 具有半结构化数据的特征：结构不规则、结 构动态可变、结构自描述，所以从某种意义上说，x m l 文档是一种半结构化数 据。但是对于有效型x m l 文档，d t d 反映了x m l 文档的简单模式，这是传统 的半结构化数据所不具备的特性。 2 3x m ls c h e m a d t d 对于x m l 文档的结构起到了很好地描述作用，但它也有一些缺点：它 采用了非x m l 的语法规则，不支持数据类型、扩展性较差，另外x m l 文档处 理的自动化要求有一种更为严格、更为全面的解决方案，x m ls c h e m a t 0 1 正好 解决了这些问题。 从根本上讲，x m ls c h e m a 实际上也是x m l 的一种应用，即将d t d 重新按 照x m l 语占规范来定义，这充分体现了x m l 的自描述性。 s c h e m a 的概念提出已久，但直到2 0 0 1 年5 月才正式成为w 3 c 的推荐标准， 相应的应用支持还有待完善，与d t d 相比，s c h e m a 具有下列优点： 一致性：利用x m l 的基本语法定义x m l 的文件结构，使x m l 达到了 从内到外的完美统一。 扩展性：引入数据类型、命名空间，对d t d 进行了扩展，使s c h e m a 具 备可扩展性。 互换性：读者可以自己设计符合自己应用的s c h e m a ，并与他人交换， 利用s c h e m a 书写x m l 文档，验证文档的合法性。 规范性：s c h e m a 提供了一套完整的机制，以约束x m l 文档中标记的作 用。 易用性：归功于d o m 和s a x ，d o m 和s a x 对x m l 文档实例有效， 但对d t d 文档无效，无法实现对d t d 中元素、属性的访问，但对s c h e m a 则不存在这个问题。 塑三! 型! 兰型竺望 2 4x m l 应用程序接口 要进行x m l 应用，首先就要对x m l 文档进行解析，以获得必要的内容和 结构信息，所以x m l 编程接口必不可少。像本文提出的x m l 近似索引就是建 立在x m l 文档的结构信息之上。x m l 的重要编程接口包括d o m ，s a x j d o m 等。 d o m ( d o c u m e n t o b j e c tm o d e l ，文档对象模型) 是w 3 c 制定的一种独立于 平台和编程语言的应用编程接口规范。d o m 是基于文档的树状结构的，它提供 了用来表示x m l 文档和h t m l 文档的一组标准的对象、组合这些对象的标准模 型、以及存取和操纵它们的一个标准接口，使得程序和脚本能以标准的方式存取 与更新文档的内容、结构和样式。 尽管d o m 是由w 3 c 定义的，w e b 上的讨论组还是提出了一些问题。其 中包括： d o m 在内存中建立x m l 文档树。如果文档非常大，d o m 树可能需 要很大的内存。 - d o m 树包括许多对象表示x l v l l 源文档的内容。如果只需要文档中的 少量信息，创建所有这些对象是一种浪费。 d o m 解析器必须在代码访问之前建立整个d o m 树。如果解析非常大 的x m l 文档，在等待解析器完成之前会有明显的延迟。 为了解决上述问题，x m l d e v 在d a v i dm e g g i n s o n 的领导下定义了 s a x ( s i m p l e a p if o rx m l ，简单的x m l 应用编程接1 3 ) m 9 8 。该标准是集体努 力的结果，事实上被所有的x m l 解析器支持。 s a x 是事件驱动型的一个标准接口。它的工作原理是：解析器顺序扫描文 档，当扫描到文档或元素开始与结束等地方时触发事件处理函数( h a n d l e r ) ，执 行用户在事件处理函数中编制的程序，然后继续扫描，直至文档结束。由于s a x 在原理以及提供的接口等方面均比d o m 简单，因此，在内存资源有限、运行速 度要求高的情况下，s a x 是一个比较好的选择。 针对文档对象模型的复杂性，人们提出了另外一种解决方案，即j d o m 。 它由b r e t tm c l a u g h l i n 和j a s o n 所创建，使用8 0 2 0 法则为最常用的8 0 的 x m l 处理功能提供一种简单的a p i 。j d o m 并没有尝试替代d o m ，目莳还只 能用于j a v a 语言。 第二二章x m l 基础知识 2 5 x m l 查询语言 随着互联网的飞速发展，x m l 以其强大的数据表达能力以及简单、可扩展 和跨平台的优点逐渐成为信息表示和交换的事实上的标准，因此如何有效查询 x m l 数据这个问题也日益变得重要。在这种背景下，研究者们提出了很多种 x m l 查询语言，其中比较著名的有l o r e a q m + 9 7 】、x m l q l f d f + 9 9 、 x q l r l s + 9 8 、x s l a b c + 0 1 、q u i l t r c f 0 0 和x q n e r y b c f + 0 2 等。关于这些 语言的比较分析见 b c 0 0 1 。 x q u e r y 是w 3 c 最新推荐的x m l 查询语言，它具有灵活、简单、易于理解 和实现等特点，同时适用于查询x m l 文档和x m l 数据库。x q u e r y 起源于另一 x m l 查询语言：q u i l t ，同时也借鉴了众多其他查询语言的优点，如类似于x p a t h 和x q l ，x q u e r y 采用了路径表达式，以适应数据和文档的层次化结构；类似于 x m l q l ，x q u e r y 采用了捆绑变量的概念，并以此创建新的结构：和s q l 一样， x q u e r y 采用了基于关键词的分句表达式的模式，为重构数据提供了统一的模板 ( 如s e l e t c t f r o m w h e r e 模式) ；和o q l 一样，作为一种功能性语言，它结合了多 种不同的表达式，并且可以嵌套使用以适合各种场合。另外，x q u e r y 中也包含 了l o r e 和y a t l c j j 9 9 等语言的一些优秀思想。 在x q u e r y 查询中，查询是通过表达式来实现的。x q u e r y 的主要表达式有 以下几种： - 路径表达式( p a t he x p r e s s i o n s ) 元素构造器( e l e m e n tc o n s t r u c t i o n s ) 一f l w r 表达式( f l w re x p r e s s i o n s ) - 关于操作和函数的表达式( e x p r e s s i o n si n v o l v i n go p e r a t o r sa n df u n c t i o n s ) 一条件表达式( c o n d i t i o n a le x p r e s s i o n s ) - 量化表达式( q u a n t i f i e de x p r e s s i o n s ) - 测试或修改数据类型表达式( e x p r e s s i o n s t h a tt e s to rm o d i f y d a t a t y p e s ) 各种表达式可以单独使用，也可以结合，嵌套起来使用。 第三章一种有效的x m l 数据近似索引 本章在分析现有的几种x m l 索引技术的基础上，提出了一种新的x m l 索 引技术：u d ( k ，1 ) 一索引，它能够充分利用x m l 数据节点问在向上和向下结构上 的局部相似性，因此能够有效地处理路径表达式查询，特别是带分支的路径表达 式查询。本章第一节对x m l 数据索引的技术进行了回顾和分类，并提出本章的 研究动机和主要内容，第二节介绍本章中要用到的一些基本概念和模型，第三节 讨论u d ( k ，1 ) 一索引的定义、性质和构造方法，第四节提出在u d ( k ，1 ) 一索引上进行 路径表达式查询的算法，第五节讨论了对u d ( k ，1 ) 一索引进行更新维护的算法，最 后一节对u d ( k ，1 ) 一索引各方面的性能进行了实验分析。 3 1x 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 数据索引可以借鉴传统数据 中的方法，但不能原样照搬。参照文 w 0 2 我们把x m l 索引划分为元素索引和 路径索引。 元素索引：根据文档中节点的标签、内容或父子节点，对文档中的元素节 点进行索引，而忽略x m l 文档的结构信息。它还可迸一步细分为文本索引、值 索引、标签索引、边( 父子关系) 索引等。 文本索引索引出现在元素的文本中的关键词，它把这些关键词映射到出现这 些关键词的元素上。文本索引可能需要限制为“直接包含”，这样就避免了冗余 或判断元素之间的祖先，后代关系。文本索引可以采用倒排表，t r i e 结构，b 树等 结构来实现。如z h a n g 和f l o r e s c u 提出了两种在关系数据库中实现x m l 关键字 检索的倒排索引z n d + 0 1 ，f k m 0 0 。 值索引 m w a + 9 8 是对文本索引的扩充针对具体的数据类型，增加了特 第三章一种有效的x m l 近似索引技术 定的匹配操作符，如对字符串类型增加了“包含”操作符，对整数类型增j n t 大 于或小于操作符。如 5 】返回所有的数字内容小于5 的元素节点， c o n t a i n “x m l ， 将返回在文本索引中使用“x m l ”作为关键字查询的结果，加上使用包含“x m l ” 的关键字查询的结果。 标签索引是对文档中元素的标签进行索引。它也可以采用倒排表、b 树等方 式。如文 j l w 0 3 提出了一种基于b + 树结构的标签索引，并在此基础上进行有效 的连接来