（计算机软件与理论专业论文）一种基于位立方体的xml索引方式.pdf

山东大学硕士学位论文 摘要 随着计算机技术和网络技术的迅猛发展，企业和个人通过网络进行数据交换 变得越来越频繁。但是由于不同用户的数据采用了不同的数据表示方式，这就给 数据的交换带了很大的不便，需要一个为大家普遍接受的数据表示方式来对网络 数据的交互格式进行统一。自1 9 9 8 年w 3 c 推出x 札1 o 规范以来，x 虬技术有了 很大发展，成为网络环境下结构化信息描述和管理的有效工具。x 虬作为一种数 据的表示形式，正在数据库及网络中的数据传输领域被广泛使用，并成为事实上 的数据表示标准。 目前，有关x 札数据存储和索引的研究都是数据库研究领域的重要热点。有 鉴于索引技术在数据管理中的突出地位，众多的x 札文献也将研究集中到了) ， 索引的技术。如何捕获x m l 数据中的结构特征，并高效地支持路径( 结构) 查询的 处理，是其中的核心。对当前分布于众多研究文献中的x 札索引进行汇总，可以根 据对) 。查询基本方式中的两个缺陷的不同处理，将x 札索引技术分为两大类： 结构摘要类索引和节点记录类索引。 本文提出了一种有效地在大规模x 札文档数据库上建立索引的技术。本文的 x 虬数据库索引技术，改进了原位立方体索引的构建过程，并在改进后的位立方 体基础上，增加了带有序路径名称链表的文档树和关键字索引表两种索引数据结 构，将三者有机的结合在一起。形成了一种即适合关键字查询又适用于路径查询 ( 包括对模糊路径的查询) 的高效的x 甩索引技术。在该索引机制下，可以方便 快速的完成对拥有大量) 0 儿文档的数据库在关键字、全路径、模糊路径及文档等 方面的检索。 本文所做的主要工作在于： 提出了一种新的) 。索引方式，详细描述了该索引方式的数据结构，并 提出了该索引方式的构建算法。 讨论了文中提出的) a 几索引方法的维护问题。并提出了在增加文档和删 除文档时文中索引的维护算法。 给出了对采用文中索引结构的) 孤。数据库进行各种查询操作的步骤。包 括基于关键字的查询、基于全路径的查询、基于模糊路径的查询和基于 山东大学硕士学位论文 文档的查询。 通过数据分析和实例比较证明了文中索引方法无论从索引的构建时间， 还是在其上对x 札数据库进行各种查询操作，均具有较高的效率。 将本文提出的索引方式应用到) a 儿数据库中，能满足用户的多种查询要求， 减少用户查询所需时间。文中的索引结构尤其适用于对拥有大量文档的稳定儿 数据库频繁查询的情况，文档间元素路径的相似程度越大，效果越好。 关键字：) 咖。索引；位立方体；结构摘要树；模糊路径 i i 山东大学硕士学位论文 a b s t r a c t a st h ed e v e l o p m e n to fc o m p u t e rt e c h n 0 1 0 9 y 眦dn e t w o r kt e c h n o l o g y ， t h ee n t e r p r i s e sa i l di n d i v i d i l a l st r a n s f e r r e dm o r ea n dm o r ed 8 t ab yi n t e m e t a tt h es 锄et i m e 。 t h ei d a t ao fd i f f e r e n tu s e r sa r es t o r e di nd i f f e r e n t f o 埘a t s ， t h e r ea r ea1 0 to fi n c o n v e n i e n c e si nt r a n s f e r e n c eb yi n t e r i l e t ， a i l da i la c c e p t e dd a t af o r m a ti sn e e d e dt ou n i f ya 1 1t h ed a t at r 明s f e r r e d b yi n t e m e t s i n c ex 札1 os t a n d a r d 观si n t r o d u c e db y 霄3 ci n1 9 9 8 ， t h e r e l l a sb e e ng r e a td e v e l o p m e n ti n ) 叫。t e c h n 0 1 0 9 y a i l d ) e c 咖e sa r ie f f e c t i v e t o o lt od e s c r i b e8 n dm a n a g es t r u c t u r ei n f o m a t i o nu n d e rt h en e t w d r k e n v i r o 皿e n t 弛也， a sad a t af o r m a t ，i sw i d e l yu s e di nt h ef i e l d so f d a t a b a s ea n di n t e m e tt r a n s f e r e n c e ，w h i c hi sb e c o m i n gt h es t a n d a r do fd a t a f o r m a ti nf a c t a tp r e s e n t ，t h er e s e a r c h e so f 捌ld a t as t o r a g e 锄di n d e x i n ga r eh o t s p o t si nt h ef i e l do fd a t a b a s es t u d y c m s i d e r i n gt h ep r o m i n e n tp o s i t i o n o fi n d e x i n gt e c l l l l o l o g yi nd a t am a n a g e m e n t ，眦c hx m ld o c 珊e n t sr e s e a r c h a l s of o c u so nt h ex 札i n d e x i n gt e c h n 0 1 0 9 i e s h o wt oc a p t u r et h ex 虬d a t a s t r u c t u r ec h a r a c t e r i s t i ca n ds u p p o r tt h ep a t hi n q u i r yp r o c e s s i n gi st h e c o r eo f ) ( m li n d e x i n gt e c h n o l o g y c o n s i d e r i n gt h ed i f f e r e n c ei nd e a l i n g t h et w 0f l a w so f mb a s i ci n q u i r i n gw a y ，煳li n d e x i n gt e c l l i l 0 1 0 9 yc a i lb e d i v i d e di n t ot w ob a s i cc a t e g o r i e s ： s t r u c t u r e s u 珈n a r y i n d e x锄d n o d e r e c o r di n d e x t h i sp a p e ra f f o r d sa ne f f e c t i v ew a yf o rb u i l d i n gi n d e x e so na l a r g e s c a l ex m ld a t a b a s e i tm e n d st h ec o n s t r u c t i n gp r o c e s so ft h e p r i m i t i 审eb i t c u b ei n d e x i n g ，b e s i d e si ta d d st h ed o c 岫e n tt r e eh a v i n ga n o r d e r l yp a t h _ n 锄et a b l ea n dk e y w o r d si n d e x i n gt a b l eo nt h ei n d e x s oi t s a ne f f i c i e n t 瑚ld a t a b a s ei n d e x i n gt e c h n i q u ef o rb o t hk e y 肿r d sq u e r ya n d p a t hq u e r y ( i n c l u d i n gi n c 伽p l e t ep a t hq u e r y ) a d o p tt h i si n d e x i n ga p p r o a c h ， i i i 山东大学硕士学位论文 u s e r s c a nd oq u e r y i n go p e r a t i o n sb a s e do nk e y w o r d 、c o m p l e t ep a t h 、 i n c o m p l e t ep a t ha n dd o c 吼e n tt oax m ld a t a b a s er a p i d ly t h em a i nw o r k sa n da c h i e v e m e n t so ft h i sa r t i c l ea r e ： a f f o r dak i n do fn e wx m li n d e x i n ga p p r o a c h d e s c r i b et h ed a t a s t r u c t u r eo ft h ei n d e x i n ga p p r o a c h ，a n da f f o r dac o n s t r u c t i n g a r i t h e t i cf o rt h i si n d e x i n ga p p r o a c h d i s c u s st h em a i n t e n a n c ep r o b l e mo ft h ea f f o r d i n gi n d e x i n g a n d a f f o r dt h em a i n t e n a n c ea r i t h m e t i c 训h i l ea d d i n gad o c u m e n to r d e l e t i n gad o c 衄e n t a f f o r dt h es t e p so fq u e r y i n ga ) ( m ld a t a b a s e ，吡i c ha d o p t i n gt h e a f f o r d i n gi n d e x e si nt h i sp a p e r t h eq u e r y i n go p e r a t i o n si n c l u d e s k e y r dq u e r y 、c o m p l e t ep a t hq u e r y 、i n c o m p l e t ep a t hq u e r ya n d d o c e n tq u e r y i m p r o v et h a tt h ea f f o r d i n gi n d e xh a sh i g he f f i c i e n c y ， n o tm a t t e r c o n s i d e r i n gt h ec o n s t r u c t i n gt i m eb u ta l s ot h eq u e r yo p e r a t i o n s a p p l y i n gt h ea d o p t i n gi n d e xo nx 札d a t a b a s ew i l ls a t i s f ym a n yk i n d s o fq u e r yn e e d sa n dr e d u c et h eq u e r y i n gt i m e t h ea f f o r d i n gi n d e x e si n t h i sp a p e ra r ee s p e c i a l l yu s e f u lf o rt h ef r e q u e n tq u e r yo p e r a t i o n so nt h e s t e a d yx m ld a t a b a s e s ，礼i c hh a v i n g 慨s s i v ed o c 岫e n t s t h es i m i l a rd e g r e e b e t w e e nt h ep a t h so fd o c u m e n t si sb e t t e r ，t h ee f f e c ti sb e t t e r k e y w o r d s ：) 。i n d e x ：b i t c u b e ；s t r i l c t u r e s 珊m a r yt r e e ；i n c 伽p l e t ep a t h 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：邀茎 日 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：盈盟导师签名拒! 兰塾日 期： 1 2 ：竺： 山东大学硕士学位论文 1 1 龇简介 第一章绪论 随着计算机网络技术的快速发展，通过网络进行数据交换变得越来越频繁。 但是由于不同用户的数据往往采用了不同的数据表示方式，这就给数据的交换带 了很大的不便。为了支持采用不同数据表示方式的用户之间方便的进行数据交 换，迫切需要一种为各方用户所接受的数据表示标准，使数据交换的各方使用统 一的数据表示方式。这时，) 口诅。( e 鲫s i b l e 丛a r k l l p l 舯g i l a g e ，可扩展标记语言) 应运而生，并在行业中迅速普及，成为事实上的数据表示标准。 本节将对咀的一些基本概念作简单介绍；第二节对目前有关沮。索引 的研究现状作了简单说明；第三节简单描述了本文所做的工作和组织结构。 1 1 1 什么是订l 说到x i l ，一定要先了解一下s g 札( s t a n d a r dg e n e r 8 1 i z e dl i a r k u p l a n g i l a g e ) 。s g m l 最初是由i 叫开发的一种用于排版的符号化语言，称为g 札。 经过若干年的发展，1 9 8 4 年国际标准化协会( i s 0 ) 开始对此提案进行讨论，于 1 9 8 6 年正式承认s g m l 为国际标准规范( i s 0 8 8 7 9 ) 。s g m l 实际上是一种通用的 文档结构描述符号化语言，主要用来定义文献模型的逻辑和物理类结构。一个 s g 儿语言文件由三部分组成，即语法定义、文件类型定义d t d ( d e f i n i t i o nt y p e d 0 c 岫e n t ) 和文件实例。语法定义部分定义了文件类型定义和文件实例的语法结 构；文件类型定义部分定义了文件实例的结构和组成结构的元素类型；文件实例 是s g 虬语言程序的主体部分。在s g 儿的实际使用中，每一个特定的d t d 都定义 了一类文件。因此，人们习惯上把具有某一特定d t d 的s g 札语言，称为某某符 号化语言。这样s g 札就成为那些派生语言的元语言【m 】。 x m l 是s g 虬的一个简化子集，它将s g 儿的丰富功能与耵札的易用性结 合到w e b 的应用中，以一种开放的、自我描述方式定义了数据结构。在描述数 据内容的同时能突出对结构的描述，从而体现出数据之间的关系。这样所组织的 数据对于应用程序和用户都是友好的、可操作的。x 儿具有可扩展性、简单性、 山东大学硕士学位论文 开放性、互操作性及支持多国语言等特性，避免了h t m l 的局限性，成为网络环 境下结构化信息描述和管理的有效工具。 咀。( e 型e n 如l e 丛a r k l 巾坳g u a g e ，可扩展标记语言) 是由w j d d 、) l ，i d ew 曲 c o n m 啪( w 3 c ) 的咀，工作组定义的。这个工作组是这样描述该语言的： “儿是s 皿( 墅a n d a r d 鱼瞰e r a l i z e d 丛a r k u pl a l l g u a g e ，标准通用标记语言) 的子集，其目标是允许普通的s g m l 在w 曲上以目前h n 也( 墅瞪e r ! 嘲丛a r k u p 里，锄g u a g e ) 的方式被服务、接收和处理。儿被设计成易于实现，且可在s g m l 和h n 之间相互操作。”川 儿是一套定义语义标记的规则，这些标记可将文档分成许多部件并对这 些部件加以标记。它不像h n 成格式化程序。这些语言定义了一套固定的标记， 用来描述一定数目的元素。儿是一种元标记语言，用户可以定义自己需要的 标记。这些标记必须根据某些通用的原理来创建，皿标记描述的是文档内容 的结构和含义，而不是描述页面元素的格式化。文档本身只说明文档包含什么标 记，而不是说明文档看起来是什么样的。争刀 下面给出一个简单的v 几文档的例子，见例1 1 。 0 b j e c t 哳i e n t e da n a l y s i s a i l d d e s i g i l w i t h a p p l i c a t i o n s g r a d yb o o c h a d d i s o n - w e s l e yp r o f e s s i o n a l 6 1 7 8 4 8 6 0 0 0 7 5a r l i n g t o 咀s t r e e t ，s u i t e3 0 0b o s t o n ，u s a j u n e4 ，2 0 0 4 2 山东大学硕士学位论文 t h eu n i f i e dm o d e l i n gl a n “a g er e f e r e n c em a n u 8 l j 硼e sr u m b a u g h i v a rj a c o b s o n g r a d yb 0 0 c h a d d i s o n - w e s l e yp r o f e s s i o n a l 6 1 7 8 4 8 6 0 0 0 ( a d d r e s s 7 5a r l i n g t o ns t r e e t ，s u i t e3 0 0b o s t o n ，u s a j u l y1 9 ，2 0 0 4 例卜1一个简单的l 文档b o o ks x m l 从逻辑上讲一个) m 几文档通常由以下5 部分组成刚： ) 心几声明 如在例1 - l 中的第一行 就是 一个v 儿声明。这是沮，规范中必有的，并且要放在第一行，并且其中的字 母是区分大小写的，表示程序依此句为开头。叽声明主要包括两个部分：一 是咀。的版本号，如例1 1 中的v e r s i o n - 1 o ，；二是文字编码声明，如例1 1 中的e n c o d i n 萨1 s o 一8 8 5 9 l ”，要放在版本声明之后。 元素 通常，元素组成了咀，文档中的大部分内容。元素由一对标记( 开始标记 和结束标记) 和字符数据组成，开始标记的形式为 ，结束标记的形式 为 ，字符数据位于开始标记和结束标记之间。如果元素没有字符数据， 则成为空元素，空元素可以用一种速记法来表示，即 表示一个用户，也可以用 表示一个用户。a g e 表示年龄， 。至于年龄的属性的值，可以 用”e i g h t ”也可以用数字”8 ”，总之格式正确就行。而“验证性”的解析器 除了验证结构外，还检查元素的命名。假设定义文档( d t d 文档) 中定义了元素 为 ，那你只能用这个u s e r 作为元素，甚至定义文档中规定了a g e 属性只 能填数字，而如果你的x 札文档中的a g e 为英文字母的话，验证性解析器将认为 你的) 叫。文档是无效的。 对于非验证性解析器而言，d t d 文档没有任何意义。而验证性解释器在解析 某个x 札文档时，一旦发现此) 眦文档指定了d t d 文件，便会按照d t d 中的定义对x m l 文档进行验证，一旦x 札的内容不符合d t d 中的规定。就算此文档符合x 札1 o 规 范，解析器也认为此文档无效。在n e t 中，验证失败会抛出异彬“l 。 大部分时候，我们所说的x 虬文档，指的是能通过“非验证性”解析器验证 的格式正确的x 肌文档。 山东大学硕士学位论文 1 2 ) 叽索引研究现状 对x m l 数据管理的研究，是当前诸多领域的热点。有鉴于索引技术在数据管理 中的突出地位，众多的) 眦文献也将研究集中到了x 札索引的技术。如何捕获) 叫。 数据中的结构特征，并高效地支持路径( 结构) 查询的处理，是其中的核心。对当前 分布于众多研究文献中的) 眦索引进行汇总，可以将x m l 索引技术分为两大类：结 构摘要类索引和节点记录类索引【1 2 l 。 将) 凸也索引技术分为两大类是针对咀。查询处理基本方式中的两个缺陷来 分的。结构摘要类索引和节点记录类索引分别针对其中的一个缺陷来设计。 甜l 这种基本的线性表达式查询语句的处理方式存在如下两个缺陷：( 1 ) 只能采取周 游的方式在皿。文档中寻找满足查询语句结构关系的数据单元，即为了获取满 足查询路径的结果，必须周游所有可能的数据单元的标签路径，效率不高。 以图卜2 为例，要想得到文本包含“w 4 ”的“c ”节点，那么必须从根节点 开始沿着r o o t a b c 的路径到达。如果采取某种索引结构，可以直接定位到 目标节点，将会大大提高查询的效率。 b c 土 同 1 _ j a 图1 - 2 几文档树 ( 2 ) 对x 札中标签路径相同的节点，仍然需要重新遍历它们的路径。这个 问题直接来自于( 1 ) 。同样以图卜2 为例，如果目标节点是c ，文档中存在3 条 相同标签路径的节点路径，而根据上述基本处理方式，为了搜索所有的c 节点， 必须对同样的路径都要遍历。那么，将同样路径的节点汇集到同一节点中，就可 9 b 一一 l k 与。l ii_i厶 b c 1 j l k 由 山东大学硕士学位论文 以提高搜索的效率。 由此在实际研究中引申出两类x n 索引形式：节点记录类索引和结构摘要类 索引。 1 2 1 节点记录类索弓 本质上讲，第1 类缺陷是由于查询处理必须通过标签路径查找节点这一限 制造成的，即要想最终得到满足查询路径的节点，必须顺序地依次访问标签路径 对应的节点路径才行。那么，如果能够改变x 札数据管理的方式，使得可以避免 必须通过路径找节点的限制，进而变为在某种辅助信息的帮助下，直接针对节点 集合的划分得到最后结果的方式，这就形成了节点记录类) 锄。索引的基本思想 3 垌。 节点记录类索引本质上是将沮。数据单元( 标签名称、属性名称、属性的值、 文本，甚至是文本中的字符串等) 作为记录保存( 类似一个关系表的模式) ；同时在 数据单元的记录中保存有助于确定节点间结构关系的位置信息，模式为( 数据单 元标识，数据单元在) 口帆中的位置信息) 。位置信息通常分为两类：一类是节点在 某种遍历方法所得字符序列中的序号，称为节点序号方法( n o d en u m b e r i n g m e t h o d ) ；另一类是节点在儿文档中的路径信息，称为节点路径方法( n o d ep a t h m e t h o d ) 。对它们的研究占了x m l 数据处理研究文献中相当大的部分。根据路径信 息表现形式的不同，节点记录类索引分为3 大类：基于节点序号的索引、基于节 点路径信息的索引和二者相结合的混合索引1 圳。 1 2 2 结构摘要类索弓 1 2 2 1 基本思想 结构摘要类索引是针对x 肌查询处理基本方式中的第2 类缺陷( 对) 眦中标签 路径相同的节点，仍然需要重帮遍历它们的路径) 而来的：既然是相同路径重复 遍历的问题，那么，将x 虬数据按照路径进行约简，要求这种约简中只保存) 哑。 数据中不同的路径，将具有相同路径的节点集合作为约简中该路径的末端节点的 内容，那么，在) ( i l l 数据上的路径查询处理，也就能够在约简结构中得到相同的 结果节点集合瞄氆l 。 1 0 山东大学硕士学位论文 1 2 2 2 相关定义 定义卜1 ：结构摘要埘。 给定标签有向图g - ( v qe g ，r o o t ( g ) ，g ) ，g 的结构摘要是基于定义在 v g 上的一个等价关系上的标签有向图i g ：( v i ( g ) ，e i ( g ) ，r o o ti ( g ) ，g ) 。其中 v i ( g ) 的节点n 称作索引节点，对应于v g 中满足等价关系的节点集合，即 n e x t e n t ；并且，e i ( g ) 中存在一条边( u i ，v i ) ，当且仅当对应于e g 中存在一条 边( u d ，v d ) ，并且u d u i e x t e n t ，v d v i e x t e n t 。 例如，对图卜1 中所示的) a 凡文档树对应有如图卜3 所示的结构摘要图。 图卜3图卜1 中的文档树对应的结构摘要图 定义1 - 2 ：双拟关系( b i s i 眦1 a t i o n ) 【3 们。 给定一棵有向树g ，g = ( v e ) ，其中v 是g 中节点的集合，e 是g 中边的集合 对g 进行转换，可以得到另外一种表达形式g7 ( v7 ，e ) ，它与原来的g 应具有 如下的关系：g 的点元素集合v7 与g 中的v 是一样的，同时g 元素间的关系 e 与g 中的e 是一致的，但是二者的表现形式是不同的；否则，g 基于g 和g7 可以定义一个二元关系r ，它是g 中节点v 和g 的节点v 的笛卡尔积： r - ( ( p ，q ) i p v ，并且q v7 。如果r 满足如下两个条件，则称r 是g 和g 的一 个双拟关系： 1 如果在g 中存在一个节点p ，它与p 具有关系p - 与p 。即，在g 中有 山东大学硕士学位论文 边a 将p 和p 连结，那么，在g 中必也存在一个元素q ，它与g 的元素q 存 在关系。 2 类似地可以定义g 中元素关系到g 中节点间关系的映射： 如果在g 中存在一个节点q ，使得从q 到q 经过元素间关系n ，那么，在 g 中必然也有一个节点p7 ，使得从某一节点p 到p7 也有a 关系，即p p 。 。t 定义卜3 ：双似关系( b i s i i l a r i t y ) 3 0 1 。 如果g 和g 的两个节点p q 间存在双拟关系，那么称p 和q 是双似的 ( b i s i m i l a r ) ，记作p m q 。由前面双拟的定义可知，两个元素双似是等价的关系。 显然，两个节点满足双拟的关系，那么它们必然具有相同的标签路径。 在这类结构摘要索引中，为了达到简化) 0 也树的目的，最初多采用自动机理 论中的n f a 到d f a 转化的思路例。在引文【3 0 】中引入了双拟和双似的概念以后，由 于双似概念能够准确地表述结构摘要问题，所以，后续的这类索引多基于这个概 徭p 1 。3 9 】。 1 3 本文的组织结构 本论文共分六章，其中第一章为绪论，主要针对课题的研究对象一x m ，的有 关概念，包括x 札文档的基本构成、x 扎文档树、) 叫，查询技术x p a t h 与x q u e r y 、 x 扎解析器进行了简单的介绍。第二章到第五章为正文部分。第二章介绍了本 文所提出的也索引的主要数据结构，包括带有序路径名称链表的结构摘要树、 位立方体以及关键字索引表。第三章详细介绍了本文所提出的也索引的构造过 程。此外，还提出了在采用文中所提索引的x 札数据库中增加文档或者删除文档 时，对索引的维护算法。第四章给出对采用了本文提出的x j 也索引方案的l 数据库进行查询操作的步骤，包括基于关键字的查询、基于全路径的查询、基于 模糊路径的查询和基于文档的查询等。第五章通过实验和实例数据分析证明了本 文提出的这种索引方法的高效性。第六章对全文内容进行了总结。 山东大学硕士学位论文 第二章索引的数据结构 2 1 龇索引应考虑的因素 不拘x 札索引是何种形式，其实际设计与实现都必须考虑l 查询的基本特征 结构关系的保存以及基于结构信息快速计算节点间结构关系这两个因素。这 实际上就是要求相关的技术能够满足高效处理x 札查询的请求。实际研究中，) n 几 查询是一个范围很大的方面，内容很多。本文仅就) 咖。索引为满足查询而应当具 备的两个基本方面展开讨论，这就是) 叽文档中结构关系的获取和保序。 2 1 1 结构关系的获取 虽然传统的索引技术经过长期的积累已经相对成熟，但是，这类索引技术针 对的主要是根据值( 而不是具有某种关系的模式) 定位数据记录的功能，不太关注 数据记录间的逻辑关系；而x 札数据查询的基本特征就是根据模式特征( 正则路径 表达式形式描述的结构关系) 的输入提取符合该模式的数据，所以，l 索引的主 要内容就是设计适用于模式匹配的技术。自然，针对正则路径表达式的相关设计 也就成为考虑的重点。 x m l 查询中模式匹配的问题。如前面所述。主要就是对x m l 数据中结构关系的 表达，以及如何利用已有的索引技术为高效获取符合结构关系的数据集提供支持 的问题。 2 1 2 保序 根据前面的叙述可知，元素在具体的x 皿文档中是有一定的次序限制的，该 次序称为x 虬文档的次序。各元素在次序中出现的顺序取决于对x 虬树的先序遍 历。当查询关系存储的x 虬分解数据时，由于关系模式不存在次序的概念，为此， 就必须在分解x 虬的过程中考虑如何确保查询的结果仍然符合结果元素集在原 x 扎数据中的次序关系，与这些元素在原x m l 文档先序遍历次序间有一一对应的关 系，而且元素间的结构关系也必须一致。 山东大学硕士学位论文 2 2 相关定义 如果说x 虬数据可以看作由结构部分( 即元素标识结构关系的集合) 和内容 部分( 包括元素属性的值和元素中所含文本的集合) 组成，那么，当前有关x m l 数 据处理的研究基本上属于这样一种模式：给定表征结构关系的查询路径，搜索x 札 数据空间寻找匹配结构模式的内容集合。也就是说，指到目前为止，经典的x 札 查询都是基于用户已经了解l 数据的组织结构为前提的。显然，这一要求大大 提高了对普通用户搜索x m l 信息的要求，更不用说要求用户掌握查询语言的语法 规则。为此，本文提出的这种索引结构，不仅能够满足传统的结构路径查询，而 且可以对模糊路径进行查询，同时除了可以进行路径查询外，还可以满足普通用 户针对文档中的关键字信息提出的查询。 本文提出的x 札索引方式采用的主要数据结构有三种：带有序路径名称链 表的文档树、位立方体和关键字索引表。在介绍这三种数据结构之前，本文首 先介绍几个在文中用到的定义： 定义2 一l ：元素内容：) 咖。文档中的元素内容主要有以下四类【柏】： 简单内容元素里边的内容为文本内容：元素内容元素包含子元素； 空内容元素为空元素；链接内容元素里边的内容为超级链接。 例如，考虑例2 1 中所示的x 虬文档。在该文档中，第( 9 ) 行的 元 素中的内容为简单内容；第( 1 ) 行的 元素中的内容为元素内容，因为它 包含第( 2 ) 行的 和第( 9 ) 行的 两个子元素；第( 7 ) 行的元素包含了 空内容；第( 5 ) 行的元素包含了一个链接内容。当然，一个元素标识里面的内容 可能不止一种类型，如第( 2 ) 行的龟e c t i 伽 元素，它里面既包含了一个位于第( 2 ) 行的简单内容，又包含了第( 3 ) 行至第( 8 ) 行的元素内容。 ( 1 ) ( 2 ) x 儿i so r i g i n a t e df r 诹 ( 3 ) i ti san e ws t a n d a r d ( 4 ) a na p p l i c a t i o nt om u l t i m e d i ad a t ai ss v ga ss h o 髓i n ( 5 ) 丛主卫；z ! 塑：b ：! z 匹! ! ：理! ( 6 ) x 壮s y n t a x 1 4 山东大学硕士学位论文 ( 7 ) ( 8 ) (