（计算机软件与理论专业论文）支持动态更新的xml数据编码方法研究.pdf

山东大学硕士学位论文 摘要 随着计算机技术和网络技术的迅猛发展，i n t e r n e t 成为全球信息传递和共 享的最重要资源，如何利用i n t e r n e t 上的大量信息成为亟待解决的问题。当前， 企业和个人通过网络进行数据交换变得越来越频繁，但是由于不同用户采用的数 据表示方式不同，因此传统的数据模式不再适合用来表示这些数据，需要一个为 大家普遍接受的数据表示方式来对网络数据的交互格式进行统一。此时，x 她的 出现引起了人们极大的关注，随着网络应用的快速发展，它正在成为i n t e r n e t 上数据表示和交换的事实标准。因此，如何有效地存储和查询x m l 数据，特别是 其中的基于特定编码方法的存储和查询，由于其具有广泛的应用，已经成为x m l 数据领域中的研究热点问题之一。 当前针对x m l 文档树的编码方法，大致可以分为两大类：基于区间的编码和 基于路径的编码。基于区间的编码方法利用x m l 文档的有序特点，根据每一个元 素结点在原x m l 文档中字典顺序的位置给每一个元素结点赋予一个编码；而基于 路径的编码方法则是利用瑚l 文档的嵌套特点，根据x m l 文档的嵌套结构，给从 文档跟结点开始所能达到的每个路径和元素结点赋予一个编码。目前提出的x m l 数据编码方法对x m l 文档树的动态更新都不能提供很好的支持，本文就此进行了 相关方面的研究。 本文在分析比较了现有的x m l 数据编码方法后，提出了一种新的支持动态更 新的x 皿数据编码方法。该编码方法能够快速准确的判断x m l 文档结构树中任意 两个结点之间的父子、祖先后裔以及兄弟关系，并采用可变扩展序号支持x m l 文档的动态更新，可有效降低x m l 文档的二次编码率。 本文的主要工作如下： ( 1 ) 对现有的区间编码、前缀编码、位向量编码和二叉树编码进行了深入的 比较分析，指出了现有编码方法不能很好地支持x 札文档树动态更新的 不足； ( 2 ) 提出了一种支持更新的x m l 文档编码方法，该方法在兄弟结点之间采用 了扩展序号：层次较高的兄弟结点之间预留了较多的扩展序号；为每个 结点保存了序号的增量，从而更好地支持了) 眦文档的更新。随着) 眦 山东大学硕士学位论文 文档更新次数的增加，二次编码率将得到明显的降低： ( 3 ) 详细介绍了编码过程并给出了该编码方法的实现算法；对编码的特性进 行了详细介绍，给出了编码更新算法，并结合实例分类讨论了插入结点 后编码的更新情况： ( 4 ) 通过实验，将本文编码方法与已有编码方法进行了时间性能、空间性能、 二次编码率及查询性能等方面的比较分析。 关键词：x m l 索引；编码索引；动态更新；可变扩展序号 i i 山东大学硕士学位论文 a b s t r a c t a c c 0 础n g 、) l ，i t i l 缸1 e 触d e 、，e l o p m e n to fc o m p u t e r 肌dn e t 、0 r kt e c b 血q u e s ， h l t e m e th 弱b e c 锄e l ei m p o r t a n ts o u r c eo f 酉o b a li l l f 0 加撕o n 仃觚s i i l i s s i o n 锄d c o m m i i i l i o n ，f o rt h a tr e 嬲0 nm a th o w t 0u s et h el a 玛ei n 0 眦to f i n 王0 姗撕0 ni s0 n e0 f m eu 玛e n tp r o b l e m st 1 1 a tw en e e dt 0r e s 0 1 v ei m m e d i a t e l yt o d a y a d i l l i t t e d l y ， c o 叩o r 撕o n s 锄di l l d i 、，i d u a l se ) 【c h 锄g et l l e i ri n f o n n a t i o n 锄dd a t ab yh i t e m e tm o r e 锄dm o r ef r e q u e l l n y ，h o w e v e r ，d u et 0m e i rd i a e r e n tr e n d e rp a t t 咖o ft h e i rd a t a ，t 量l e 仃a d i t i o r l a ld a t ap 舭e mi sn o tf i tf o rc o n s 啪e r s r e q m r e m 印t st or 印r e s e n tm e i rd a t 乳 t h e nt h e r en e e da 试f i e dd a t ap a ：t t e mt or e n d e rc o n s 啪e r s i n f o n 】 1 a ：t i o n ，w m c hc o l l l d 、i d e l ya c c 印t e db yi n t 哪e tu s e r s a tt h es 锄et i r ，t 1 1 ea p p e a r 锄c eo fx 二g a i n sa p e r v 嬲i v e 甜朗1 t i o n ，觚df a s td e v e l o p s 谢t hm en e t v v o r k 印p l i c 撕o n ，血e nf i l l a l b e c o m e sc r i t e r i o n so fd a 诅玎印r e s t 趾de x c h 锄g e 1 1 1 u s ，d u et 0t t l ep e 硒i v eu s eo f x ，锄e 舭嘶v ew 研o f 哟咖g 趾di n 舢r i l l gx 加。d a t a ，e s p e c i a l l yi l lt l l ep a n i c u l a r c 0 d es c h e m 钆b e c o m e so n eo fm er e s e a r c hf o c u s e so fx m lf i e l d t h e r ea r e 铆oi i 擒i i lw a y s 幻r e p r e 重l tx l v 几d o c 啪e n t 仃e ec u r r 锄n y ：c o d i i l g b 嬲e do ni n t e r z o n e 觚d 即c o d i n gb 嬲e d0 np a m t h ef i r s tm e t h o d - e n c o d i n gb 嬲e d0 n i l n e r z o n e ，i n i l i z e st 量l ec h a r a c t 嘶s t i co fo r d e ro f 沮。d o c 啪e n t s ，c o d e dm en o d eb y i t sa l p h a b e t i cp o s i 矗o ni i lm eo n g i i l a lx m ld o c 啪e n t w l l i l e 血es e c o n dw 锣- 锄c o d i n gb 嬲e d0 np 础，u s e sm en e s t e dt i 面t o ro fx 池d o c l l i l 懈1 t s ，g a v eac o d eo f e a c hn o d e 砌c hc o u l da 玎i v e df r o mt 量1 er o o tn o d ei i le v e r ) ，p a t h 1 1 0 w e v e r ，训ln o w t 量l ep r o p o s e d 锄c o d i n gm 咖o d so fx m ld a t aa r ea l ln o tw e l ls 叩p o n i n g 也ed y n 痂c u p d a t eo f x m ld a 饥锄dt l l i sp a p e rd 0 郫d 0 也es t u 由i n “s 御e c t b a s e do nt h e 锄a l y s i so ft 量l ec o m p a r i s o no ft l l ee x i s t i n g 沮。缸ae l l c o d i i l g m e m o d ，an e wm e t 量1 0 d 、7 1 7 h j c hs u p p o r t sd y n 砌c a lu p d a t ei sp r o p o s e dh e r e t h e c o d i n g m e c h o dc 肌 f a p 硼y 趾d a c c a t e l yj u d g e t t l e p 砌t - c h i l d 觚c e 哟r ( 1 e s c e n d a m 锄ds i b l i n gr e l 撕o n s h j p sb e t w e 锄yt w on o d 髂o ft l l ex m l d o c u m e n tt r ；a n dw ea d o p t 也ev 撕a b l ee 冲觚d e do r d e rt os u p p o r tu p d a t eo f l d a t a 锄ds oe 髓c t i v e l yr e d u c em es e c o n d 哪咀，e n c o d i n gr a t e i i i 山东大学硕士学位论文 t h em a j nw o r ko f t h i sp 印e ri sa sf o l l o w s ： ( 1 ) a f t e ra 1 1 a l y s i sa i l dc o m l ) a r i s o n ，s 删n gu pt 1 1 ei n a d e q u a c yo f 喇s t i n gc o d i n g m e t l l o d s ( r e g i o ne n c o d i n g ，p r e f i xe n c o d i n g ，b i t v e c t o re n c o d i n g 肌dp b i t r e e c o d i n 曲：n o tw e l ls u p p o n i n gt h ed y n 锄i cu p d a t eo fx m i ，d 0 c u m 既t 仃e e ( 2 ) an e wm e t h o dw h i c hs u p p o r t sd y n 撕c a lu p d a t ei sp r o p o s e d u s ee 斌锄d e d o r d e rb e t 、v e e nb r o m e rn o d e s 】o r ee x c e n d e ds e r i a ln l l i 】出e rb e l 、) i ，e e n l eb r o m e r n o d e si ss e t 掘d ei nt 量l eh i 曲e rl e v e l e a c hn o d es a v e st l l ei i l c r e m 肌t a lv a l u eo f o r d e r w i t h 也e 沮。d o c u m e n tu p d a t e si n c r e a s e ，也es e c o n d a 巧忸。e n c o d i n g r a t ei s 玎e d u c e d ( 3 ) t h i sp a p e rd e s c 曲e sm ep r o c e s so fe n c o d i n ga n d c o d i n ga l g o r i n l mi sa l s o g i v e n ；觚dt h ee n c o d i n gc h a r a c t e r i s t i c sa n dc o d eu p d a c ea 1 9 0 r i t l l 】 ni sd e s c 曲e d i nd e t a i l ，t o o t h eu p d a t eo fn o d e s 世e ri n s e r t 妯gn e wn o d e si sa l s od i s c u s s e d 谢le x a i i l p l e si nd i 艉r e n tc a t e g o 哆 ( 4 ) t h r o u 曲t 量l ee x p e r i m e n t ，w ed 0s o m ec o m p a r 撕v em a l y s i so nh m e p e r f i o r r 】1 a n c e ，s p a c ep e r f - 0 n 】昀n c e ，a 1 1 dt 1 1 es e c o n d 朗c o d i i l gr a t ep e r f o 加= l a n c e b e t w e e nm en e w e n c o d i n gm e t h o da i l d 廿l ee ) 【i s n ge n c o d i n gm e m o d k e yw o r d s ：x m li n d e x ；e n c o d i n gi n d e x ；d y n a m i cu p d a t e ；v a n a b l e e x p a n d e do r d e r 原创性声明和关于学位论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：查盘垄皇 日 油以i 坼兰 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：垒垄趣导师签名： 山东大学硕士学位论文 1 1 研究背景 第一章绪论 i n t e r n e t 的迅速发展，使其成为全球信息传递和共享的最重要资源，如何 利用i n t e r n e t 上的大量信息成为亟待解决的问题。由于i n t e r n e t 上的数据多以 半结构或无结构的形式出现，因此传统的数据模式不再适合用来表示这些数据。 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 ，可扩展标记语言) 【1 】的出现引起了人们极大 的关注，其目标是能够定义计算机和人都能方便识别的数据类型。随着网络应用 的快速发展，它正在成为i n t e r n e t 上数据表示和交换的事实标准。在i d w g 规范 中也推荐使用x 肌来实现i d s 之间的数据交换。与h t m l 相比，x 儿具有很大的 灵活性，不但可以表示无结构的文本信息，也可以表示高度结构化的数据( 如数 据库中的数据) ，它极大地推动了互联网技术在电子商务、电子数据交换和电子 图书馆等多方面的应用。而如何有效地存储和查询这些) 眦数据成为学术界研究 的个热点。 x l 也是w 3 c 在1 9 9 8 年制定的一项标准，是s g m l 【2 1 ( s t a n d a r dg e n e r a l i z e d m a r k u pl a n “a g e ，即标准通用标记语言) 的一个子集，是一种自描述的元语言， 用户可以任意定义自己的标记，其目标是允许普通的s g m l 在w e b 上以目前h t m l 的方式被服务、接收和处理。x 地被设计成易于实现，且可在s g 帆和h t 札之间 互相操作。同h t 魁相比，x m l 具有如下一些特点【3 4 】： ( 1 ) 更多的结构和语义舰侧重与对文档内容的描述，而不是文档的显示。 用户自定义的标记描述了数据的语义，便于对数据的理解和机器的自动处理。 ( 2 ) 可扩展性x m l 允许用户自己定义标记和属性，可以有各种定制的数据 格式。 ( 3 ) 简单易用x m l 严格的定义和规则集使得任何机器都能够更容易地阅读 x m l 文档。与通用标记语言s g m l 相比，x m l 简单易用，便于掌握，这是它得以推 广的重要原因。 ( 4 ) 自描述性涮l 将对数据的语义描述和数据内容本身都包含在x 札文档 中，使数据具有很大的灵活性。 山东大学硕士学位论文 ( 5 ) 数据与显示的分离) ( m l 所关心的是数据本身的语义，而不是数据的显 示方式，所以可以在同样的) ( m l 数据上定义多种显示形式，非常灵活。 ( 6 ) 开放的国际化标准瑚l 是w 3 c 正式批准的，它完全可用于w e b 和工具的 开发。x m l 具有标准的名域说明方法，支持文档对象模型标准、可扩展类型语言 标准、可扩展链接语言标准和) ( 5 l l 指针语言标准。使用) 。可以在不同的计算机 系统间交换信息，而且还可以跨越国界和超越不同文化疆界交换信息。 】( m l 的这些特点使得它不但迅速成为了网络数据交换的事实标准，而且正在 逐渐成为数据表示的标准。一系列相关的标准( 如) ( m ld a t a m o d e l 、x m ls c h e m a 、 x q u e r y 等) 也随之不断出现，形成了围绕x m l 的标准集合，反映了工业界对x m l 的巨大支持。越来越多的w e b 应用，如电子商务，信息服务等采用x m l 作为数据 表现形式，很多的网站也采用l 作为信息发布形式，可以预见将有越来越多的 瑚l 数据出现在i n t e r n e t 上。 由于x m l 具有很多不同于传统数据形式的特点，使得传统的数据处理技术 不能直接应用在x m l 数据上，许多问题都需要重新考虑。针对舭数据处理技术， 工业界和学术界都表现出巨大的热情。工业界在商用系统的扩展、针对) ( m l 数据 处理的产品开发和新的技术标准的制定等方面都做出了巨大的努力，也取得了很 大的进展。而学术界则针对一些基本的问题，如x m l 数据模型【3 5 ，3 6 1 、新的查询处 理技术阢3 8 1 、数据的高效存储口9 4 0 1 和索引机制h 1 ，4 2 1 等进行了深入的研究。 1 2 国内外研究现状 近年来，随着) ( m l 逐渐成为被广泛接受的数据表现形式，对于x m l 数据处理 的研究也逐渐成为了研究的热点，受到广泛的关注。国外许多著名的大学和研究 机构都在从事该领域的研究工作，如s t a n f o r d 大学、w i s c o n s i n 大学、b e l l 实 验室、法国的i n r i a 研究所等。国内的中国人民大学、东北大学、复旦大学等也 在该领域进行了大量的工作。在各种大型的国际学术会议( 如i c d e 、v l d b 、s i g m o d 等) 上，该领域相关的论文占了相当比重，有关的学术交流也非常活跃。此外， 许多面向该领域的国际会议也逐渐发展，如w e b d b 、w i s e 、w a i m 等。 在) ( m l 数据管理的研究领域中，有许多问题受到人们关注，如) ( m l 数据的高 效存储、索引机制、查询处理和优化等。目前有大量的研究工作集中在x m l 数据 2 山东大学硕士学位论文 的关系存储口1 以及由此产生的关系数据的x m l 发布【4 j ，l 视图机制5 1 等方面。此 外，数据压缩【6 】、) ( m l 数据过滤和发布阴等方面也都有学者在从事研究。 在) ( m l 数据处理的众多问题中，实现对x m l 数据的有效存储和查询是非常关 键的一个。针对x m l 这种树型结构数据的查询，学者们己经提出了多种x m l 查询 语言，如x q u e r y l 8 】等。这些查询语言尽管各有特点，但它们的一个共同特点是都 将路径表达式作为其核心内容，用户可以用路径表达式来描述在x m l 数据层次中 的定位。 x m l 查询中的路径表达式可以表示为小枝( t w i g ) 的查询，既能独立地描述查 询要求，又可以在查询语言中描述变量绑定。计算路径查询最直接的方法就是将 x 地文档描述为树型结构，按照树的遍历顺序进行匹配，即从根结点出发，沿着 树中的边搜索，寻找与路径表达式的结点相匹配的部分。这种“一次一元组 的方法是非常低效的。为了提高路径查询匹配的执行效率，人们提出了多种导航 的遍历方式。文献 9 】对路径查询匹配的优化进行了研究，提出了借助文档的模 式信息以及在文档结构树中引入索引的优化方法。虽然这些方法可以在一定情况 下改进路径匹配的效率，但由于导航方式的本质缺陷，查询效率不能得到根本保 障。 由于导航查询方式的低效，人们开始从另一思路寻求路径查询的高效计算， 其主要思想是将一个复杂的查询模式分解成为若干个简单的小的查询模式。首先 计算简单查询片段，然后将基本的匹配结果组合起来生成最后的查询结果。这种 处理策略适用于不同的x m l 数据存储，包括t i v e 系统和关系数据库系统。这 种“一次一集合”的策略适合处理大规模的数据。基于这种处理策略，需要研究 的问题很多，包括查询片段的有效计算，中间结果的高效组合操作，路径查询的 分解策略等。解决这些关键技术问题，实现路径查询的高效处理，是实现大规模 ) 眦数据查询的关键。目前，随着研究的不断深入，对于x m l 路径查询处理已经 取得了许多的研究成果。 在x m l 数据编码方面，由于对x m l 数据进行有效的编码可以迅速确定舭文 档树中任意结点间的结构关系，而不用遍历x m l 文档树。这正是蹦l 路径查询分 解计算的基本要求，为此目前已经提出了许多对删l 文档的编码方法。这些方法 都是使用特定的编码方式对x m l 文档树中的元素、属性和其他语义实体进行编 3 山东大学硕士学位论文 码，使用编码唯一标识实体，从而判断文档树中结点间的基本结构关系。目前已 经提出的编码方法主要可以分为两类：区间编码【1 7 2 2 1 和前缀编码【2 ”引。 区间编码是目前应用最普遍的一类，树丁中的每一个结点被赋予一个区间编 码 s t a r t ，e n d ，并且满足：一个结点的区间编码包含它的后裔结点的区间编码。 也就是说，树，中的结点，是结点矿的祖先，当且仅当s t a r t ( 国 s t a r t ( d 八 e n d ( 功 e n d ( 谚。这类方法的好处是编码直接对应于结点在文档中的偏移位置， 可以方便地得到结点内容，有着较高的查询效率。 前缀编码直接将一个结点的双亲结点的编码作为该结点编码的前缀，要判断 一个结点y 是否是另一个结点口的后裔，只需判断字符串c ( 国是否是字符串c ( 访 的前缀。这类编码方法最大的优点是当文档发生更新时不需要对文档重新进行编 码 另外，还有一种编码方式是素数编码方式【4 3 】，利用素数的唯一性为结点编码。 通过某种特定的遍历方式为文档中所有结点分配一个未被分配的素数作为结点 自身的编码，称为“s e l f l a b e l ，结点的编码为结点自身编码与其父结点编码 的积，父结点编码则称为“p a r e n t l a b e l 。这种编码方式能根据结点编码间的 整除关系快速地确定结点的关系，在有新的结点或子树插入时可能很容易的为新 插入结点分配一个未使用的素数作为新结点的自身编码，可以有效地支持文档的 动态更新和有序的文档结构查询。 目前，已经提出的各种) ( m l 数据编码方法都有各自的特点和优点，但它们也 都同时面临着同一个问题：如何有效地支持) ( m l 文档的动态更新。在基于区间的 编码方式中，由于通过结点所覆盖区域的包含关系来判断结点间的祖先后代关 系，使其对文档更新非常敏感，一旦有新的结点插入就不得不对整个文档重新进 行编码。完全树编码虽然包含了丰富的结构信息，但其由于采用增加虚拟结点的 方法将文档嵌入到完全树中，不仅造成了大量编码空间的浪费而且不易对文档更 新，因此实际中不易采用。而前缀编码方法虽然更新时不需要对文档重新进行编 码，但随着文档中结点的增加，需要将标识符或分隔符与结点编码同时存储，不 仅造成存储空间的浪费，而且严重影响了查询效率，得不偿失。 因此，x m l 数据编码是需要进一步研究的课题，涉及如何解决x m l 文档的更 新问题及提高查询效率等等。 4 山东大学硕士学位论文 1 3 本文的工作 本文详细介绍了) ( m l 数据索引技术，针对以往研究中存在的主要问题，对 ) ( m l 数据编码进行了深入的研究，在分析比较现有的编码方法的基础上提出了一 种新的支持) ( m l 文档更新的编码方法，该编码方法可以快速准确的判断结点间的 父子、祖先后裔关系，满足保序查询要求，并针对整个x m l 文档树经频繁更新 后需要重新编码的情况，采用了扩展序号，文档更新后只需调整部分结点编码， 有效地降低了二次编码率。本文的主要研究内容如下： ( 1 ) 对现有的区间编码、前缀编码、位向量编码和二叉树编码进行了深入的 比较分析，指出了现有编码方法不能很好地支持) 叩。文档树动态更新的 不足； ( 2 ) 提出了一种支持更新的瑚l 文档编码方法，为了支持) 眦文档的更新， 本文的编码方法采用了如下策略：兄弟结点之间采用了扩展序号；由于 较高层次的结点编码更新将会引发较多的结点编码更新，因此层次较高 的兄弟结点之间预留了较多的扩展序号；每个结点编码保存了一个e x 值，该值标识了如果该结点作为第一个需编码更新的结点，其o r d e r 值 的增量。随着x m l 文档更新次数的增加，二次编码率将得到明显的降低； ( 3 ) 详细介绍了编码过程并给出了该编码方法的实现算法；对编码的特性进 行了详细介绍，给出了编码更新算法，并结合实例分类讨论了插入结点 后编码的更新情况； ( 4 ) 通过实验，将本文编码方法与已有编码方法进行了时间性能、空间性能、 二次编码率及查询性能等方面的比较分析。 1 4 本文的组织结构 本文的组织结构如下： 第一章绪论，主要介绍了本文研究背景、国内外研究现状及存在的主要问题 并简单说明本文的工作。 第二章讨论了x m l 数据索引技术的研究现状，为后续研究打下基础。 第三章对编码方法进行了研究，详细介绍了各种编码方法，对现有的编码方 山东大学硕士学位论文 法进行了分类，重点讨论了区间编码方法和前缀编码方法。 第四章提出一种新的支持更新的x m l 数据编码方法，详细介绍编码规则及编 码特性，并通过实验对编码方法的相关性能进行测试和分析。 第五章对全文进行了总结，分析了本文研究成果的意义，并指出了今后需要 进一步做的工作。 6 山东大学硕士学位论文 第二章x m l 数据索引综述 目前，人们对x i l 的研究主要分为两个方面。一个是对x m l 这种半结构化数 据的存储、查询和管理的的原生数据库，其中的数据和元数据完全采用x 地结构 表示，与其底层的数据存储格式( 如对象模型、关系模型等) 无关。另一个是它与 关系数据库之间的相互转换，利用关系数据库的成熟技术对舭数据进行处理。 由于后一个方向比较有现实意义，因此成了l 研究中的重点。 而除了存储方法之外，索引技术也是决定一个数据库系统最重要的因素之 一。如果对x m l 文档不构建索引结构，那么针对x 儿数据的任何查询都很可能导 致对整个文档树的遍历，随着l 数据集的增大，这种开销是不可忍受的。故此， 对x m l 索引技术的研究具有较高的理论和实用价值。 虽然传统的索引技术经过长期的积累已经相对成熟，但是，这类索引技术针 对的主要是根据值( 而不是具有某种关系的模式) 定位数据记录的功能，不太关注 数据记录间的逻辑关系；而x m l 数据查询的基本特征就是根据模式特征( 正则路 径表达式形式描述的结构关系) 的输入提取符合该模式的数据，所以，x m l 索引 的主要内容就是设计适用于模式匹配的技术。 2 1 索引策略 目前，对x m l 文档建立索引的策略主要有三种：无索引、完全索引、部分索 引。 索引并不总是适当的，意识到这一点相当重要。对数据库中的二元关系建立 完全索引，将会对某些隋况有所帮助：而对另一些情况，应该使用部分索引 策略。 ( 1 ) 无索引。以下的几种情况，不应该建索引：数据频繁改变时，查询 只访问很少的结点时。当数据源经常改变时，更新索引的开销可能大于查询 性能的提高。实际上，建索引所消耗的时间应该小于查询所花的时间：否则， 不应该建立索引。当数据库的规模一般只访问元素的父结点和子结点，在一 个大型数据库中建立跨所有祖先和后代的索引，相当浪费。如果不对单一节 点进行直接的物理访问，建立索引也是不合适的，例如，整个文档存储于一 7 山东大学硕士学位论文 个文件。 ( 2 ) 完全索引。对一个相对较小的很少变化的数据库进行频繁的访问， 最适合于使用完全索引。利用索引结构，每个可能的查询( 在一定间隔内) 都可以获得更高的效率。链接和文档中子元素关系上的完全索引，可能会增 加性能。在一个合适的粒度级别上执行查询时，存储文档间的关系也会对性 能提供帮助。 ( 3 ) 部分索引。只在部分元素上进行索引( 例如那些带有某些类型名的 元素) 将减少所需的索引数。通过支持只在某些可能的查询上进行索引，也 能够减少索引的数量。部分索引减少了完全索引中创建的索引结构的数量。 索引也可以支持某些查询，而不支持其他的查询。请求最频繁的大量消耗时 间的查询应该被索引结构所支持；而那些最少执行的、快速应答的查询则不 必建立索引。选择最好的查询策略依赖于了解哪种查询最可能发生。 减少索引所需空间的方法是，清除某些用在完全索引中的索引结构。索引和 搜索相结合可以快速地响应最经常提交的查询，并对很少执行的查询也提供合理 的响应速度。 2 2x m l 数据索引分类 跚l 规范规定了捌l 数据必须满足的条件，基本的形式是x m l 文档。从逻 辑上讲，一个x m l 文档通常由5 部分组成：声明、元素、注释、字符引用和处理 指令，为叙述方便，统称为瑚l 数据单元。x m l 数据内容的限制通常由x m l 模 式( 包括d t d 和) ( m l s c h e m a ) 来描述。图2 1 为b o o k l i s t x m l 文档的示意。图 中b o o k l i s t 为b o o k l i s t x m l 的根，它具有3 个标签为b o o k 的区段，而每一 个b o o k 区段都嵌套一个以t i t l e 标签为标志的区段。当给定) ( m l 文档时，该文 档也就隐含地确定了其中所含的标记单元的顺序，称为) ( m l 顺序( x m l o r d e r i n g ) ，这一概念在x 皿查询处理时是需要考虑的，即查询结果中的标记单 元应当具有类似的顺序特征。 8 山东大学硕士学位论文 p r o f e s s i o n a la j a x n i c h o l a sc z a k a s ，j e r e m ym c p e a k ，j 0 ef 明c e t t p r o f e s s i o n a lj a v a s c r i p tf o rw e bd e v e l o p e r s n i c h o l a sc z a k a s p r o f e s s i o n a lc # si m o nr o b i n s o n ， e ta l 图2 1b o o k l i s t x m l 为了从x 虬以及半结构化数据中获取所需要的信息，研究人员开发了许多 查询语言，包括l o r e l ，x m l - q l ，删l - g l ，q u i l t ，x p a t h ，x q u e r y 。它们共同的 特征为：采用了正则路径表达式式，其本质是捕捉x m l 数据单元间的结构关系 和内容。) ( p a t h 是实现潮l 数据周游的基本语言，是x s l t ，x q u e r y 的基础。 它首先定义了x m l 数据的树形模型。图2 2 即为图2 1 对应的x m l 文档树。由 ) 【p a t h 的定义可以构建很复杂的查询语句，主要分为3 个层次：线性路径表达 式、分支路径表达式和路径树。其中，路径树的定义包含了研究文章中常见的小 枝概念：t w i g 。 9 山东大学硕士学位论文 图2 2b o o k l i s t x m l 对应的x m l 文档树 当在x m l 文档类数据之上处理x p a t h 查询时，借助于w 3 c 定义的x m l 数 据处理的两种接口规范，d o m ( d o c 岫e n to b j e c tm o d e l ) 和s a x ( s i m p l ea p if o r x m l ) ，处理方式可概括为：顺序读取) ( m l 文档中的结点：如果该结点的路径满 足x p a t h 中定义的条件( 包括结构关系、测试条件和谓词关系) ，那么该结点即 为x p a t h 查询语句的一个输出。这种基本的线性表达式查询语句的处理方式存 在如下两个缺陷： ( 1 ) 只能采取周游的方式在) ( m l 文档中寻找满足查询语句结构关系的数据 单元，即为了获取满足查询路径的结果，必须周游所有可能的数据单元的标签路 径，效率不高。以图2 2 为例，要想得到t i t l e 为p r d f e s s i o i i a lc 存的结点，那么 必须从根结点开始沿着b o o k l i s t b o o k t i t l e 的路径到达。如果采取某种索引 结构，可以直接定位到目标结点，将会大大提高查询的效率。 ( 2 ) 对l 中标签路径相瓦的结点，仍然需要重新遍历它们的路径，这个问 题直接来自于( 1 ) 。 同样以图2 2 为例，如果目标结点是t i t l e ，文档中存在3 条相同标签路 径的结点路径，而根据上述基本处理方式，为了搜索所有的t i t l e 结点，必须对 同样的路径都要遍历。那么，将同样路径的结点汇集到同一结点中，就可以提高 搜索的效率。 由此在实际研究中引申出两类) ( m l 索引形式：结点记录类索引和结构摘要 类索引。 1 0 山东大学硕士学位论文 2 2 1 结点记录类索引 本质上讲，第l 类缺陷是由于查询处理必须通过标签路径查找结点这一限 制造成的，即要想最终得到满足查询路径的结点，必须顺序地依次访问标签路径 对应的结点路径才行。那么，如果能够改变x m l 数据管理的方式，使得可以避 免必须通过路径找结点的限制，进而变为在某种辅助信息的帮助下，直接针对结 点集合的划分得到最后结果的方式，这就形成了结点记录类x m l 索引的基本思 想。 类似于树结构的保存，基于实际的处理要求，将x m l 数据单元( 标签名称、 属性名称、属性的值、文本，甚至是文本中的字符串等) 作为记录保存；同时在 数据单元的记录中保存有助于确定结点间结构关系的位置信息，模式为( 数据单 元标识，数据单元在x m l 中的位置信息。位置信息通常分为两类，一类是结点在 某种遍历方法所得字符序列中的序号，另一类是结点在x m l 文档中的路径信息。 实际索引数据的保存可以采用不同的形式【1 0 1 1 】，如保存为文本( n a t i v e s t o r a g e ) 、关系数据形式。其中最常见的就是将索引记录保存为关系的方式，本 文主要针对这种方式展开叙述。 2 2 2 结构摘要类索引 结构摘要是针对舭查询处理基本方式中的第2 个缺陷而来的：既然是相 同路径重复遍历的问题，那么，将l 数据按照路径进行约简，要求这种约简 中只保存x m l 数据中不同的路径，将具有相同路径的结点集合作为约简中该路 径的末端结点的内容，那么，在x 儿数据上的路径查询处理，也就能够在约简 结构中得到相同的结果结点集合。 2 3 结点记录类x m l 数据索引 结点记录类索引本质上即是将x m l 数据分解为数据单元的记录集合，同时 在记录中保存该单元在瑚l 数据中的位置信息。主要有两种获取位置信息的方 法，一种是结点序号方法( n o d en 岫b e r i n gm e t h o d ，有时也称为结点标签方法， n o d el a b e l i n gm e t h o d ) ，另一种是结点路径方法( n o d ep a t hm e t h o d ) 。对它们 山东大学硕士学位论文 的研究占了) ( m l 数据处理研究文献中相当大的部分。根据路径信息表现形式的 不同，结点记录类索引分为2 大类：基于结点序号的索引和基于结点路径信息 的索引。 2 3 1 结点序号类索引 这类索引中的位置信息是结点在某种遍历序列中的序号。对于一个x m l 文 档，设计遍历) ( m l 文档的策略，遍历的最终结果表现为一个由结点组成的序列； 相应地，结点的标签在序列中就有一个序号，该序号表明了结点间的次序关系， 也能够反映结点间的结构关系，进而，就可以基于该序号信息捕获结点间的结构 关系。 结点序号类) ( m l 索引的基本思想是：基于x m l 文档设计某种遍历策略，得到 由元素组成的序列，结点的标签在序列中就具有唯一的次序，将序列与某指标集 ( 最常用的就是自然数) 建立一一映射的关系，对应序列中某个标签就有唯一的序 号；对任意两个具有结点序号信息的结点，可以构建某种运算，该运算的结果可 以表征结点间的结构关系，即 ( 独立单元属性，位置信息) ) ( 结构关系) 映射。 根据标签序列生成方式的不同，目前研究文献中序号类索引可分为两种：基 于标签有向树的遍历( 如先序遍历和后序遍历) 和基于字符流模型的顺序处理根 据映射指标集的不同，可分为赋以自然数、赋以局部编码和赋以素数的方式。在 序列生成和结点序号赋值的基础上，可以构建不同形式的位置信息，进而形成不 同的结点记录索引形式。 根据对位置信息的编码方式不同，基于结点序号类的索引一般可以分为一下 几类： ( 1 ) 基于前缀的索引 基于前缀的索引主要是根据d e w e y 编码生成的索引，o r d p a t h 编码采用的也 是类似的方法，并给出了压缩o r d p a t h 的方法，该方法已应用于s q ls e r v e r2 0 0 5 的索引组织中。 前缀编码的基本思想是直接将一个结点的双亲结点的编码作为该结点编码 的前缀，对于前缀编码，要判断一个结点y 是否另一个结点u 的后裔，只要判断 u 的编码是否y 的编码的前缀。前缀编码索引的一个重要性质是它们的字典有 山东大学硕士学位论文 序：以结点，为根的子树中的任意一个结点口，它的前缀编码c ( 西大于( 小于) 它的左兄弟子树( 右兄弟子树) 中所有结点的前缀编码。因此，基于前缀的索引不 仅能够有效地支持包含关系的运算，而且能够有效地支持文档位置关系的计算。 ( 2 ) 基于区间编码的索引 对于区间编码索引，树t 中的每一个结点被赋予一个区间编码 b e g i n ，e n d ， 满足：一个结点的区间编码包含它的后裔结点的区间编码。也就是说，树，中的 结点口是结点y 的祖先，当且仅当s t a r t ( 动 e n d ( 动。两个结点的区间编码之间 的关系为：它们要么完全不相交，要么完全包含。 第一个区间编码方法是d i e t z 编码，树，中的每一个结点被赋予一个具有先 序遍历序号和后序遍历序号的二元组。由于树，中的一个祖先结点，在先序遍历 ( 后序遍历) 中必然出现在它的后裔结点y 之前( 之后) ，因此，结点口和矿是祖先 后裔关系，当且仅当p r e ( 谚 p r e ( 力且p o s t ( 力 p o s t ( j ) 。因此，树丁中的任意 两个结点之间的祖先后裔关系的检测( 即包含检测) 能够在常数时间内被计算 ( 即两次比较运算) 。对于该编码方法，p r e 或p o s t 均可以作为结点的唯一标 识。 另一个区间编码索引的典型例子是x i s s 索引，它为每个结点赋予一个数字 对，其中o r d e r 为扩展的前序编码，s i z e 为结点的子孙的范围。对一棵文档树 中的任意结点j 和只当且仅当o r d e r ( 亩 o r d e r ( 力o r d e r ( d + s i z e ( 曲， 则j 是j ，的一个祖先。 x i s s 索引通过将原始查询语句分解为子表达式。然后分别针对这些子表达 式实现查询，最后对这些中间结果进行联结获得查询结果集。从而能较好地支持 含通配符的查询语句。不过，它是对每一个中间结果进行联结后得到最终查询结 果。虽然这样一种方法的确能够解决所有的通配符问题，可是，这种中间结果的 联结很有可能是非常耗时的，特别是对于长路径的简单表达式。 2 3 2 结点路径类索引 结点的路径信息同样蕴含结点在x m l 数据中结构的信息：如果给定两结点的 路径信息，同时预知两结点存在结构关系的情况下，就必然可以获知它们之间的 结构关系。即结点彳的标签路径包含结点锣的标签路径，那么，在删l 树中彳和 山东大学硕士学位论文 曰之间一定具有祖先一子孙的结构关系，且占是彳的祖先。所以，基于路径信息 来获取结点的结构关系就成为另一组l 数据处理技术的思路来源，并演化出基 于结点路径的) ( m l 索引【1 2 - 1 4 】。这类索引的核心技术是字符串的模式匹配。因而， 这类索引记录数据的管理方法，有许多是来自于信息获取领域的。例如，t r i e ， p a t r i c i at r i e 以及s u f f i xt r e e ，甚至s u f f i xa r r a y 等结构。索引记录的基 本模式为( 数据单元标识，路径信息) 。已经提出的这类索