（计算机软件与理论专业论文）xml索引技术的研究.pdf

摘要 近年来随着互联网的高速发展，人们进入海量的信息时代，x m l 以其强大的 数据表达能力以及简单、开放性、可扩展等优点而逐渐成为互联网上信息发布和 数据交换的标准。但随着x m l 的广泛应用，x m l 数据急剧增多给x m l 文档的维护工 作带来了很大的挑战，为了更好地对x m l 文档进行维护，使得其他应用程序更容 易对x m l 文档进行操作，人们从存储到索引、再到查询做了积极深入地研究。这 些研究促进了x m l 的发展，解决了现实中的诸多问题，许多优秀的研究成果已经 有了一定规模的应用如l o r e l 1 。但是由于x m l 数据的多样性以及用户日益增长的 查询需求，人们很难找到一种能同时适应不同的数据来源( x m l 纯文本，关系型数 据库以及其他各种应用数据等) 并能够有效的处理各种查询请求的通用索引结 构。因此，针对不同的x m l 应用，人们提出了不同的索引结构，来满足不同环境 下的需求。目前对x m l 索引研究集中在基于节点记录类和结构摘要类两类索引方 法，但它们普遍存在索引对内存要求较高、索引更新效率低等问题，特别是对非 常常见的t w i g 结构查询处理时，都需要进行大量的联接而影响到查询的性能。 本文基于上述的缺点提出两种索引技术m t b - i n d e x 和m i f i n d e x ，这两个索引 的创新之处体现在以下几方面： 1 m t b - i n d e x 索引支持索引的动态更新 2 m t b - i n d e x 索引采用线性模型，它把查询路径匹配转换为区间的匹配 3 m t b - i n d e x 索引能够有效处理带有“结构的查询 4 m i f - i n d e x 索引占用空间小，可以直接放在内存从而提高查询时间 5 m i f - i n d e x 索引处理t w i g 结构无需进行连接，避免了以往索引处理t w i g 结构都要进行连接的弊病 关键词：x m l ；t w i g ；索引 a b s tr a c t w i t ht h er a p i dd e v e l o p m e n to fi n t e r n e t ，x m lh a sg r a d u a l l yb e c o m ean e w s 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 nt h ei n t e m e t k n o w nf o ri 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 m e r o u so t h e r b e n e f i t s s om a n yk i n d so fx m l t e c h n o l o g yb e c o m eah e a rr e s e a r c hf o c u s b u tw i t l l t h ee x t e n s i v ea p p l i c a t i o no fx m l ，t h ex m ld a t at ot h ed r a m a t i ci n c r e a s ei nt h ex m l f i l em a i n t e n a n c ei sab i gc h a l l e n g e t ob e t t e rx m ld o c u m e n tf o re a s ym a i n t e n a n c e a n dm o r eo nx m ld o c u m e n tf o ro p e r a t i o n p e o p l ef r o mt h es t o r a g eo ft h ei n d e x ，a n d t h e nt o i n q u i r i e sm a d eap o s i t i v e a n dt h o r o u g hs t u d y t h e s es t u d i e sf o rt h e d e v e l o p m e n to fx m l a d d r e s st h er e a l i t yo fm a n yp r o b l e m s m a n yo u t s t a n d i n g r e s e a r c hr e s u l t sh a v eac e r t a i ns c a l ea p p l i c a t i o ns u c ha sl o r e l h o w e v e r , d u et ot h e d i v e r s i t yo fx m ld a t aa n dt h eg r o w i n gu s e rd e m a n di n q u i r y , i ti sd i f f i c u l tt of i n da s i m u l t a n e o u s l ya p p l i e dt od i f f e r e n td a t as o u r c e s ( s u c ha sn a t i v ex m l d a t a b a s ea n d r e l a t e dd a t a b a s e ) a n dh a n d l ei n q u i r i e sc o m m o ni n d e xs t r u c t u r e p e o p l eu s ed i f f e r e n t i n d e x i n gs t r u c t u r et om e e tu n d e rd i f f e r e n tc i r c u m s t a n c e sd e m a n d p r e s e n t ，r e s e a r c ho n x m li n d e xm a i n l yc o n c e n t r a t e di nt h en o d et y p ea n ds t r u c t u r eo fr e c o r d sa b s t r a c t c a t e g o r yt w oi n d e x i n gm e t h o d ，b u tt h e yh a v ee f f i c i e n c yo fi n d e xu p g r a d i n gl o w a n d p r o b l e m so fd e a l i n g 、析t l lt w i gs t r u c t u r ew h i c hw i l lp r o d u c eal a r g en u m b e ro f u s e l e s s m i d d l er e s u l t s t h ea b o v e m e n t i o n e df a c t o r sr e d u c i n gt h ep e r f o r m a n c eo fx m l m q u m n g i nt h i sd i s s e r t a t i o n ，t h ea b o v es e v e r a li s s u e sa 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 m m a r i z e da sf o l l o w s ： 1 m t b - i n d e xs u p p o r t sd y n a m i cu p d a t i n go ft h ei n d e x 2 m t b i n d e xi tu s e sl i n e a rm o d e la n dp a t hm a t c h i n gt h ei n q u i r i e si n t ot h e m a t c hi n t e r v a l 3 m t b i n d e xc a ns o l v ee f f i c i e n t l yt h eq u e r y 、析t l lr e l a t i o n 4 m i f i n d e xo c c u p i e das m a l ls p a c e ，i tc a ni m p r o v eo nt h ep e r f o r m a n c eo f m e m o 巧 5 m i f i n d e xs t r u c t u r et od e a lw i t ht w i gn ol i n k ，i ta v o i d st h es h o r t c o m i n g so f d e a l i n gt w i gs t r u c t u r ew h i c h m u s tj o i n k e yw o r d s ：x m l ；t w i g ；i n d e x 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的研究 成果。本人在论文写作中参考的其他个人或集体的研究成果， 均在文中以明确方式标明。本人依法享有和承担由此论文产 生的权利和责任。 声明人( 签名) 夕掺；西 杪i 每其均目 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。 厦门大学有权保留并向国家主管部门或其指定机构送交论文 的纸质版和电子版，有权将学位论文用于非赢利目的的少量 复制并允许论文进入学校图书馆被查阅，有权将学位论文的 内容编入有关数据库进行检索，有权将学位论文的标题和摘 要汇编出版。保密的学位论文在解密后适用本规定。 本学位论文属于 1 保密( ) ，在年解密后适用本授权书。 2 不保密( ( 请在以上相应括号内打“4 ”) 作者签每髟苦一；务 导师签 日期俨_ 7 年厂月加 日氍狎年，月必日 第一章绪论 第一章绪论 本章阐述了论文的研究背景，目前的研究状况和本课题的研究价值。 1 1 研究背景 随着i n t e r n e t 的迅速发展，互联网成为全球信息传递和共享最重要的资源， 它极大地影响了人类的生活方式、商业模式，并且贯穿于电子商务、电子图书、 远程教育等全新领域，使w e b 数据变的更加复杂和多样化，从而使得作为w e b 使用 最广的h t m l 语言的局限性越发明显，可扩展标记语言x m l ( e x t e n s i b l em a r k u p l a n g u a g e ) 便应运而生。x m l 被认为是互联网上数据表示和数据交换的新标准，越 来越多的网上资源将以x m l 的格式表示。x m l 与h t m l 相比具有许多优点： ( 1 ) x m l 简单，自我描述且易于解析。使得x m l 具有机器可读性，一个应用可 以按照各种方式解析、过滤、重构x m l 文档。 ( 2 ) h t m l 中的标记是固定的，不能扩展，而x m l 的标记由用户定义，可以任意 地扩展。x m l 的嵌套结构可以表示现实世界中各种复杂的对象，各种格式的数据 都可以比较容易地转化为x m l 数据，这使得) ( m l 非常适于w e b 信息的发布和集成。 ( 3 ) h t m l 中的标记表示的是数据的显示格式，没有任何语义，而x m l 的标记则 明确指出了数据的含义，使得细粒度的x m l 数据处理成为可能。 ( 4 ) x m l 实现了内容、结构和表现二者的分离。文档类型定义( d t d ) 描述了文 档中元素和子元素间的嵌套结构，不同的用户可以通过x s l 按不同的显示方式显 示全部或部分的文档内容。 由于x m l 同h t m l 兼容，且与平台无关，同时又是一种真正的扩展语言。目前 几乎所有软件厂商都争相采用x m l 技术。比如m i c r o s o f to f f i c ex p 自身可支持在 e x c e l 和a c c e s s 中使用x m l 文件格式，已发布的数据库服务器d b 2 ，s q l s e r v e r 2 0 0 0 、消息服务器e x c h a n g e2 0 0 0 等也很好地支持了x m l ，在网络传输协方 面，由w 3 c 、微软、i b m 和s a p 共同制定的s o a p 协议( 简单对象访问协议) 同样也是 以x m l 为核心。 随着x m l 的广泛应用，x m l 数据急剧增多给x m l 文档的维护工作带来了很大的 挑战，为了更好地对x m l 文档进行维护，使得其他应用程序更容易对x m l 文档进行 第l 页 x m l 索引技术的研究 操作，人们从存储到索引、再到查询做了积极深入地研究。这些研究促进了x m l 的发展，解决了现实中的诸多问题，许多优秀的研究成果已经有了一定的规模的 应用如l o r e l n 】。但是由于x m l 数据的多样性以及用户日益增长的查询需求，人们 很难找到一种能同时适应不同的数据来源( x m l 纯文本，关系型数据库以及其他各 种应用数据等) 并能够有效的处理各种查询请求的通用索引结构。因此，针对不 同的x m l 应用，人们提出了不同的索引结构，而满足不同环境下的需求。 1 2 研究现状 数据库是从6 0 年代初发展起来的计算机技术。经过- _ - - 十年的发展，数据库 技术己经趋于成熟。从应用领域、采用的数据模型及相关技术的三维空间可以看 到数据库形成的门类：数据库与相关技术相结合形成的分布式数据库、并行数据 库、知识数据库、演绎数据库等：数据库在具体应用需求的基础上形成了工程数 据库的研究领域、地理分析系统数据库、数据分析决策等一系列分支；同时，数 据大量积累形成了一个新的应用需求，它带来了数据仓库、联机分析处理等技术。 以数据库观点，x m l 文档可看作数据库，它的d t d 看作是数据库的模式。但数据库 与x m l 文档是有区别的，数据库的数据结构性很强，而x m l 更适合描述半结构化数 据。x m l 数据库是可以对x m l 文档进行存取管理和数据查询的数据库。 目前，x m l 数据库主要有两种类型：纯x m l 数据库和基于现有成熟数据库系统 ( 关系数据库或面向对象数据库) 的使能数据库。纯数据库充分考虑到) ( m l 数据的 特点能够从各方面很好地支持x m l 的查询和存储，但是纯x m l 的数据库还未成熟， 而使能数据库充分利用已有的关系数据库技术来存储和查询x m l 数据，但处理x m l 数据要经过多级复杂的转换而降低效率。 目前已发布多种的纯x m l 数据库，其功能各具特色。在支持对x m l 文档管理的 同时，不同程度的增加了一些附加功能。比较著名的产品有t a m i n o 口1 ，d b x m l 哺1 ， t i m b e r 阳1 等，而t a m i n o 是第一个商用n a t i v e - x m l 数据库，其最新版为2 3 1 。该 系统提供与其它数据源的调用接口，可以对关系型收据进行存储管理。其管理界 面是基于w e b 的，与主流的关系数据库管理系统相似，其查询语言是基于x p a t h ， 有直接x m l 检索和特殊检索的能力，可实现对任意数据元的检索，其功能在某些 方面甚至超过传统s q l ( 根据g a r t n e rg r o u p 的研究报告) 。 第2 页 第一章绪论 而现在国内外关于半结构数据的研究主要集中在新的数据模型、查询模式、 存储技术以及优化技术等方面。基于x m l 的半结构数据索引的研究主要集中于文 档数据的表示( 节点的数据结构) 、索引的结构和检索的算法，在算法中会考虑索 引的存储空间和索引的更新。另外，文档数据的表示和索引的结构不同，对检索 的算法影响也较大。索引的结构主要有倒排文件( i n v e r tf i l e ) 、文档条目矩 阵( d o c u m e n tt e r mm a t r i x ) ，t r i e ( 带标记的树状索引) 、p a t r i c i at r i e ( 带字符 串压缩的t r i e ) 、后缀树( s u f f i xt r e e ) 。而索算法主要有从根到叶、从叶到根、 从根和叶分别开始在中间相遇和从任意一个节点开始到另一个节点终止四种。在 不同的索引中，会根据其索引结构选择相应的检索算法。 1 3 本文的研究价值 由于x m l 数据的广泛应用以及x m l 数据的迅速膨胀，这对x m l 文档查询的要求 也就越来越高。如果不对x m l 文档建立索引结构，那么针对x m l 数据的任何查询都 很可能导致对整个文档树的遍历，随着x m l 数据集的增大，这种遍历所花费的开 销是不可忍受的，x m l 索引结构的提出正是为了提高查询的效率，在速度与准确 性两方面为查询提供更大的灵活性，通过减少访问那些与查询不相关的数据集来 实现快速查询。 t w i g 查询作为一种非常常见的查询，依靠现有的索引技术和连接算法则需耗 费较长时间而无法满足用户的要求，另外由于x m l 数据的经常更新，使得x m l 索引 维护代价很高，故对有效支持t w i g 结构查询和支持动态更新技术有深远的意义。 1 4 本文的组织结构 本文的组织如下：第1 章介绍论文的研究背景、现状和意义，第2 章介绍x m l 索引及其查询语言，编程接口的一些相关概念，第3 章论述m b t - i n d e x 的原理和具 体实现以及实验并进行性能分析，第4 章论述m i f - i n d e x 的原理和具体实现以及实 验并进行性能分析，第5 章总结与展望。 第3 页 x m l 索引技术的研究 第二章x m l 索引 本章先介绍x m l 基础知识，然后上述现有的索引技术，最后阐述现有索引技 术存在的问题和不足。 2 1x m l 基础知识 2 1 1x m 儿文档 个x m l 文档一般对应于一棵x m l 文档树，如图2 1 是一) ( m l 文档而图2 2 是相 应的x m l 文档树。对于一颗x m l 文档树，它通常将标记单元的顺序隐含在其中，称 为x m l j i i 页序( x m lo r d e r i n g ) ，这一概念在x m l 查询处理时是必需的，因为查询结果 中的标记单元应当具有类似的顺序特征。 x m 【l c h i n a j o h n c h i n a d o e x m l 文档实例 第4 页 第二章x m l 索弓 夕u 7 | 7 竹n 7 m 7 竹m m e 图2 2x m l 文档树 x m l 文档通常由5 部分组成：声明、元素、注释、字符引用和处理指令。它以 声明开始，x m l 声明其实是一个处理指令，它指定合适的工具来处理x m l 文档。x m 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 d t 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 。这几种类型被用来表 示元素之间的引用关系。 2 1 2d t d 简介 d t d ( d o c u m e n tt y p ed e f i n e ) 不仅仅用于x m l ，还可以用它为任何类型的s g m l 文档创建模式。d t d 作为w e b 的一个标准，任何能处理x m l 文档的浏览器都能对照 第5 页 x m l 索引技术的研究 d t d 模式来检查文档。x m l 允许文档的编写者制定基于信息描述、体现数据之间逻 辑关系的自定义标记，确保文档具有较强的易读性、易检索性和清晰的语义。因 此，一个完全意义上的x m l 文档不仅仅是“格式良好的 ( 文档必须包含一个或多 个元素，必须包含且仅包含一个根元素) ，而且还应该是使用了一些自定义标记 的“有效的x m l 文档，也就是说，它必须遵守文档类型定义d t d 中已声明的规定。 d t d 规定文档的逻辑结构，它可以定义文档的语法，而文档的语法反过来能够让 x m l 语法分析程序确认某页面标记使用的合法性。d t d 定义页面的元素、元素的属 性以及元素和属性之间的关系。例如d t d 能够规定某个表项只能在某个列表中使 用。 理想的定义应面向描述与应用程序有关的数据结构而不是如何显示数据。换 句话说，应把一个元素定义为一个标题行，然后让样式表和脚本定义如何显示标 题行。 d t d 描述了一个置标语言的语法和词汇表，定义了文档的整体结构以及文档 的语法。即d t d 规定了语法分析器以解释一个“有效的”x m l 文档需要知道的所有 规则的细节主要包括以下几方面： ( 1 ) d t d 文档的引用。 一个d t d 可以是内部的，包含在x m l 文档的前导说明部分：也可以是外部的， 作为一个外部文档被引用。一个包含内部d t d 的x m l 文档的结构为： 文档体 外部d t d 的好处是：它可以方便、高效地被多个x m l 文档所共享。只要写一个 d t d 文档，就可以被多个x m l 文档所引用。使用外部d t d 的x m l 文档的结构为： 文档体 s y s t e m 不是引用外部d t d 的唯一方法，这个关键字主要用于引用一个作者或 组织所编写的众多x m l 文档中通用的d t d 。还存在另一种外部d t d ，即由权威机构 制订的、提供给特定行业或公众使用的d t d ，引用这种外部d t d 的方法是使用关键 第6 页 第二章y d v l l 索引 字p u b l i c ，在d o c t y p e 中说明的形式为： 构建一个基本的x m l 文档往往要注意以下三点： 所有元素必须有结束标签： 所有元素必须正确地嵌套( 不允许交迭元素) ： 所有特征值必须加引号。 ( 2 ) d t d 元素类型的声明。 d t d 中使用元素类型声明e t d ( e l e m e n tt y p ed e c l a r a t i o n ) 来声明有效的文档 元素。表达式为： x m l 标准将元素按内容划分为以下几类： 空元素类型，它定义方式为： 这类元素在 x m l 文档中使用空元素标记，元素中没有内容。 a n y 元素类型，它定义方式为： 这类元素在x m l 文档中可以包含任何内容，一般只把文档的根元素规定为a n y 类型。 # p c d a t a 类型，它定义方式为： p c d a t a 可以包含除标记以外的一切字符，包括数字、字母和符号等，但被定义 为包含p c d a t a 的元素不能包含任何其他的子元素。 子元素类型，它定义方式为： 子元素内容模型用于指定某个元 素可以包含哪些子元素，子元素内容模型有序列和选择两种结构。 混合元素类型，它的定义方式为： 这类元素中可以包含文本，同时文本之间可以有 选择地插人子元素，但子元素出现的顺序和次数不受限制。 ( 3 ) d t d 中属性类型的声明。 使用下面的格式来给一个元素定义一组合适的属性，同时指定这些属性的类 型和缺省值： 可以分为下面几种 情况： 必须赋值的属性，x m l 文档中必须为这个属性给出一个属性值，具体表 达式为： 。 第7 页 x m l 索引技术的研究 属性值可有可无的属性，不要求在x m l 文档中给该属性赋值，而且也无 需在d t d 中为该属性提供缺省值。具体表达式为： 。 固定取值的属性，需要为一个特定的属性提供一个缺省值，并且不希 望x m l 文档中另外给出的元素值替代缺省值。具体表达式为t 。 先定义了缺省值的属性，需要在d t d 中提供一个缺省值，在x m l 文档中 可以为该属性给出新的属性值，也可以不给出属性值，而采用d t d 中给 出的缺省值，具体表达式为： ，其中属性类型用来指定该属性属于哪种有效属性类型。 ( 4 ) 参数实体声明。 参数实体专门用于d t d ，它可以方便元素和属性的声明。在下面这个例子中， 参数实体简化了本科生信息和研究生信息中相同部分的录人工作： 虽然从理论上讲参数实体的内容可以为任何文本，但由于它专门用于d t d 中， 出现在元素定义的正则表达式里，所以对它有一些特殊的规定。参数实体的替换 文本中括号必须成对出现，并且，它不能以连接符“i ”或“，结尾。 若满足以上规则是有效的x m l 文档，这时d t d 反映了x m l 文档的简单模式，它 是传统的半结构化数据所不具备的特性。 但是，d t d 也存在以下缺陷t d t d 本身并不是x m l ，它有着自己的特殊语法。而d t d 的构建和访问并没 有标准的编程接口，无法使用标准的编程方式进行d t d 维护。 d t d 扩展性差，d t d 是内容“封闭”的模型。 d t d 不支持命名空间( n a m e s p a c e ) 的机制。 d t d 缺乏对x m l 文档内容及其语义的约束机制 d t d 只提供有限的几种数据类型。d t d 不支持数据类型定义，d t d 中规定 的文档内容都是字符数据，缺乏最常用的整型、布尔型等这些简单的 第8 页 第二章x m l 索引 数据类型，且仅在属性定义方面提供了少量数据类型。 每个x m l 文档只有单个的d t d 来限制。 2 1 3s c h e m a 简介 ( 1 ) x m ls c h e m a 的特点。 由于x m ld t d 并不能完全满足x m l 自动化处理的要求，所以w 3 c 于2 0 0 1 年5 月正式推荐x m ls c h e m a 为x m l 的标准模式。它与d t d 最大的区别是它采用了x m l 的形式来定义描述x m l 文档的结构，因此它可以很方便地利用x m l 的解析器与相关 工具进行处理。它与d t d 相比优势有以下几方面： 一致性，s c h e m a 使得对x m l 的定义不必再利用一种特定的形式化的语言， 而是直接借助x m l 自身的特性，利用x m l 的基本语法规则来定义x m l 文档的结构， 使得x m l 达到了从内到外的完美统一，也为x m l 的进一步发展奠定了坚实的基础。 扩展性，x m ls c h e m a 对d t d 进行扩充，可自定义数据类型，并引入命名空 间的机制，使其具备更强的可扩展性。 易用性，由于s c h e m a 是x m l 文件，因此两种主要的x m la p i ( 应用编程接口) “d o m ”和“s a x 对s c h e m a 文件都能起作用，而对d t d 文件则无能为力。 互换性，x m ls c h e m a 可验证x m l 文件的合法性，并通过特定的映射机制， 将不同的x m ls c h e m a 进行转换，实现高层次的数据交换。 规范性，同d t d 一样，s c h e m a 也提供了一套完整的机制以约束x m l 文档中 置标的使用，但相比之下，后者基于x m l ，更具有规范性。s c h e m a 利用元素的内容 和属性来定义x m l 文档的整体结构，如哪些元素可以出现在文档中、元素间的关 系是什么、每个元素有哪些内容和属性以及元素出现的顺序和次数等等，都可一 目了然。 ( 2 ) x m ls c h e m a 的语法与结构。 x m ls c h e m a 也是x m l 文件，所以s c h e m a 文件和x m l 文件会被同样的工具处理。 下面介绍一下它的结构和语法。 一个s c h e m a 文件和x m l 文件一样，都是由声明和内容组成的。不同的是 s c h e m a 文件必须将“s c h e m a 元素作为s c h e m a 文档的根元素。其它各类元素( 比 如e l e m e n t ，a t t r i b u t e ，c o m p l e xt y p e 等) 都应包含在该元素中。s c h e m a 具有两 第9 页 x m l 索引技术的研究 个属性：n a m e 指定该s c h e m a 的名称，而x m l n s 贝u 指定该s c h e m a 包含的命名空间。 元素和属性的声明和定义在s c h e m a 文档中，有三个重要的元素e l e m e n t t y p e ，e l e m e n t ，g r o u p 。e l e m e n tt y p e 元素在s c h e m a 文档中使用e l e m e n tt y p e 来声明x m l 文件中会出现的元素，通过c o n t e n t 属性可声明元素是否为空、是否包 含文本、是否包含子元素或既包含文本又包含子元素。通过d a t et y p e 指定该元 素的数据类型。对于e l e m e n t 元素，e l e m e n tt y p e 只是起到声明元素的作用，至 于元素的内容究竟是什么，则要靠它的子元素e l e m e n t 来说明。e l e m e n t 实际上是 对该s c h e m a 中e l e m e n tt y p e 声明的引用，通过t y p e 属性指定元素的类型，且同 e l e m e n tt y p e 中的n a m e 属性严格一致。对于g r o u p 元素，该元素用于将x m l 文件中 的元素分组。通过o r d e r 属性可设置分组或子分组中的元素顺序。通过m i n o c c u r s 和m a x o c c u r s 属性分别指定了该组在其父元素中出现的最小次数和最大次数。在 s c h e m a 文档中，有两个定义属性的元素：a t t r i b u t et y p e ，a t t r i b u t et y p e 元素 也是s c h e m a 中的重要元素之一，用于定义该s c h e m a 文档中出现的属性类型。通过 d a t e t y p e 指定所声明属性的数据类型。 数据类型。x m ls c h e m a 提供了s t r i n g ，i n t 等几十种内置的基本数据类型， 还有一些扩展的数据类型，但是，x m ls c h e m a 数据类型的真正灵活性来自于其对 用户自定义类型的支持。x m ls c h e m a 提供两种方式来实现数据类型的定义。 简单类型定义( s i m p l et y p e ) 。即在x m ls c h e m a 内置的数据类型基础上或其 它由x m ls c h e m a 内置的数据类型继承或定义所得到的简单的数据类型( s i m p l e t y p e ) 基础上，通过r e s t r i c t i o n ，l i s t ，e n u m e r a t i o n ，u n i o n 方式定义新的数 据类型。 复合类型定义( c o m p l e xt y p e ) 。一个复杂元素是一种包含其它元素及( 或) 属性的x m l 元素。有四类复杂元素：空元素，只包含子元素的元素，只包含文本的 元素，包含子元素和文本的混合元素。 一致性约束。一致性约束可以唯一识别文档中的节点，并确保它们之间 引用的完整性。一致性约束可分为三类：唯一性约束( u n i q u e ) 、关键字约束( k e y ) 、 关键字引用( k e y r e f ) 。它们的定义包括三部分：范围( s c o p e ) ，选择器 ( s e l e c t o r ) 、限制域( f i e l d ) 。范围指出一个在其声明中包含约束的元素：选择器 可选择所应用该约束的所有节点：一个或多个字段( f i e l d ) 是元素和属性的值，他 第l o 页 第二章x i v i l 索引 们的组合在所选节点中必须是唯一的。k e y r e f 弓l 用的k e y 必须在同一元素声明中 定义，或者在它的一个子元素的声明中定义。唯一性约束和关键字约束的主要区 别在于唯一性约束的字段可以为空，而关键字约束限定的字段却不可以为空。它 们分别类似于关系数据库中的唯一性索引和主键。而关键字应用则类似于外键。 2 1 4 帆编程接口技术 应用程序要理解x m l 文档，从中提取需要的数据，必须由x m l 分析器对x m l 文 档进行分析：x m l 分析器另一个功能就是在检查文档是否是“格式良好的”基础上， 进一步结合d t d 或x m ls c h e m a 检查x m l 文档是否是“有效的 。基于以上功能，x m l 分析器提供了应用程序编程接口，应用程序通过接口实现对x m l 文档的间接访问。 目前，应用较广泛的有以下几个： ( 1 ) d o m ( d o c u m e n to b j e c tm o d e l ) 。 d o m 文档对象模型) 是一个基于树型的解析技术，它在内存中构建起一棵完整 的解析树它可以实现对整个x m l 文档的全面、动态访问。利用d o m ，可以方便地 创建文档，遍历文档结构，添加、修改、删除文档内容，改变文档的显示方式等 等作为w w w 的标准接口规范，d o m 与语言无关、与平台无关，所以可以用不同语 言来实现d o m 接口。d o m 解析器将x m l 文档一次性解析，生成一个位于内存中的对 象模型的集合( 通常称d o m 树) 用以描述该文档。应用程序正是通过对这个对象模 型的操作，来实现对x m l 文档数据的操作。通过d o m 接口，应用程序可以在任何时 候访问x m l 文档中的任何一部分数据，因此，这种利用d o m 接口的机制也被称作随 机访问机制。d o m 易于使用，丰富的a p i 可用于轻松地导航，整棵树加载到内存， 允许对x m l 文档进行随机访问。但是d o m 也存在一些缺陷：整个x m l 文档必须一次解 析完，将整棵树加载到内存，因此内存消耗比较大。 ( 2 ) s a x ( s i m p l ea p if o r ) ( m l ) s a x ( x m l 简单应用程序接口) 是一种基于事件驱动的模型。当使用s a x 分析器 对x m l 文档进行分析时，会触发一系列事件，并激活相应的事件处理函数，应用 程序通过这些事件处理函数实现对x m l 文档的访问，因而s a x 接口也被称作事件驱 动接口。当分析器对x m l 文档进行分析时，就会触发在d o c u m e n th 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 0 1 v e r 接口中定义的回调方法。由于应用程 第1 l 页 x m l 索引技术的研究 序无需将整个文档加载到内存，只是在读取数据时检查数据，因此内存消耗比较 少，实现效率也比较高，但是它也存在一些缺陷：没有内置的文档导航支持，不 能够随机访问x m l 文档，更改数据比较复杂等。 2 1 5x m l 查询语言 随着利用x m l 存储、交换和表示的信息日益增多，在各种各样的x m l 数据源中 查询x m l 数据的要求也日益迫切。可以灵活的表示多种不同数据源的不同信息， 是x m l 最强大的功能之一，为了使这种灵活性得到最大程度的发挥，人们设计了 许多x m l 查询语言用来从这些数据源查询数据。目前已经提出很多种x m l 查询语 言，比如x m l q l 朝，x m l g l ，q u ilt 射，x p a t h 6 1 和x q u e r y 7 3 等，不同的x m l 查询语 言间的一个重要区别是数据模型的不同。查询x m l 文档的关键是如何从输入中选 择出所需的数据。大多数x m l 查询语言都使用了正规路径表达式( r p e ) 来描述从文 档的“根结点到数据值所走过的路径。由于x m l 可能含有递归嵌套的元素或不 规则的结构，因而可使用正规表达式运算符，如通配符、k l e e n e 运算符和选择运 算符等。 对于树结构的查询语言来说，存在一条从根结点到给定结点的唯一路径，但 是，如果数据模型是图结构的，则可能存在着多条从根结点到给定结点的路径。 在这种情况下，语言的语义通常限定了路径表达式中的结点仅能出现一次。即使 是在图结构数据模型中，也存在着对文档中的子元素进行遍历、或者是将i d r e f 作为属性而不是直接进行查询的情况。x m l - q l 对这些并不做区分：l o r e l 查询语言 则为用户提供了一种图结构与树结构模式的转换机制以支持上述的查询情况。不 同的查询语言所使用的路径表达式有很大的不同，但其功能确实类似，即供沿路 径导航式的查询方式。 ( 1 ) 路径表达式 在现有针对x m l 半结构化数据的查询语言中，其共同特征是路径表达式，他 们所定义的路径表达式能够让用户制定相关结构中符合一定条件的任意路经，这 也是其与关系数据库的一个重要差异。路经表达式是由节点与节点间的关系约束 一次间隔构成的有限长度的列表。表达式的表达能力是衡量和划分表达式的重要 指标。对表达式表达能力的鉴定可以从以下若干方面进行： 第1 2 页 第二章x m l 索引 节点名是否由确定的字符组成；是否允许通配符匹配；是否允许用户使用 正则操作“+ ”、“木”、“? ”和“l ”来表达更为复杂的概念。 节点构造是否允许嵌套递归，即允许节点由其他的一条子路经或节点构造 组成：节点是否允许正则操作；节点是否允许为其附加相应的谓词约束。 节点间的关系约束是固定的直接连接，还是允许用户指定其在数据中的具 体表现形式，如后继和祖先关系等等。根据各项指标的复合程度，我们可将路经 表达式按照表达能力化分为以下两类：简单路径表达式( s i m p l ep a t he x p r e s s i o n ) 和一般路径表达式( g e n e r a lp a t he x p r e s s i o n ) 。下面分别加以讨论： 简单路径表达式。它的主要思想是规定在x m l 文档结构中的路径是基于 节点名的序列路径。例如简单路径表达式p u b l i c a t i o n b o o k a u t h o r 。 在x m l 文档的查询中引入简单路径表达式，可以使用户写查询方便。 一般路径表达式。对于x m l 数据而言，它的模式不是事先知道的，而且 模式不是固定的，故引入一般路径表达式是必要的。一般路径表达式( 扩 展了简单路径表达式，对于查询数据和模式提供了强有力的机制。例如 p u b l i c a t i o n 序a u t h o r ，其中“木通配符指以元素实例集合p u b l i c a t i o n 为初始集合，经过任意路径( 零条或多条) 到达节点名为a u t h o r 的元素， 找出所有该元素的子元素。 ( 2 ) x q u e r y 语言和x p a t h 语言 x p a t h 的最主要的目的是用来对x m l 文档进行定位，它使用了简洁的j f - - x m l 语 法实现查询要求。它是定义在x m l 文档的抽象的逻辑结构上，而不仅是停留在其 表层的语法，这一逻辑结构称作x p a t h 数据模型。x p a t h 使用u r l 中路径的表示方 法来对x m l 文档的层次结构中搜索和定位。x p a t h 的主要用途是嵌入到其他宿主语 言如x s l t 或x q u e r y 中，x p a t h 可以用来进行匹配以确定某一x m l 结点是否符合一个 模式。 x q u e r y 是设计用来实现w 3 c 的x m l 查询工作组( w 3 cx m lq u e r yw o r k i n gg r o u p ) 标准的“x m l 查询要求 ( x m lq u e r y1 0r e q u i r e m e n t s ) ，它是一种小的、易于 实现的查询语言，用它表示的查询简练并且易于理解。x q u e r y 十分灵活，可以在 包括数据库和文档的多种x m l 数据源之上进行查询。x q u e r y 拥有两种语法，一种 使用简单的非x m l 语法，适用于人的阅读和使用；另一种使用严谨的x m l 语法，可 第1 3 页 x m l 索引技术的研究 以由计算机方便地处理和使用。x q u e r y 是一种名为q u i l t 的x m l 查询语言发展而 来，而q u i l t 在其他几种查询语言如x p a t h ，x q l ，x m l q l ，s q l ，o q l 等查询语言之 中借鉴了许多特性。 x q u e r y 的1 0 版本包含了x p a t h 的2 o 版本作为它的一个子集。所有在 x q u e r y l 0 和x p a t h 2 0 中语法上均有效而且均可成功执行的表达式，在这两种语 言中得到相同的结果。由于这两种语言有着如此紧密的联系，它们在语法和语言 的