（信息与通信工程专业论文）xml数据编码与小枝模式查询的研究.pdf

、：，j 。 r e s e a r c ho nl a b e l i n g a n dt w i gp a t t e r nq u e r yo fx m ld a t a s p e c i a l t y ：i n f o r m a t i o na n dc o m m u n i c a t i o ne n g i n e e r i n g m a s t e r d e g r e ec a n d i d a t e ：i 垒塾g 堕i 旦gh 坠 s u p e r v i s o r ： p r o f j i a n h u al i s c h o o lo fi n f o r m a t i o ns c i e n c ea n d e n g i n e e r i n g c e n t r a ls o u t hu n i v e r s i t y c h a n g s h ah u n a np r c h i n a 4249哪mmi m 7 ，叭il_y 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得中南大学或其他单位的学位或证书而使用过的材料。与我共 同工作的同志对本研究所作的贡献均己在论文中作了明确的说明。 作者签名：嘲坚蛆 日期：墨! 旦年月上日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校有 权保留学位论文并根据国家或湖南省有关部门规定送交学位论文，允 许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 扭嗍迎年月上日 ： 摘要 目前，随着x m l 相关标准和技术的不断推广和应用，各领域出 了大量的x m l 数据，特别是在w e b 上。有大量显而易见的事实表明： x m l 已经成为数据表示和交换的标准。大量x m l 文档的出现促进 了x m l 数据库的研究，包括x m l 数据的存储、索引技术、查询处 理技术和查询优化技术，其中索引技术之编码机制和查询处理技术之 小枝模式查询匹配算法是当前研究的热点。 为了有效支持x m l 数据的结构查询，目前已经提出了多种编码 机制和小枝模式查询匹配算法，以减少对数据库的访问和连接操作， 提高查询效率。本文通过分析x m l 语言、x p a t h 语言、x q u e r y 语言、 x m l 小枝模式查询和x m l 常用评测数据集，重点研究已有的各种 x m l 文档树编码机制和小枝模式查询匹配算法，总结出x m l 文档 树编码机制和小枝模式查询匹配算法存在的问题和待改进的地方。 首先，针对已有x m l 编码机制时空效率不高、对x m l 文档动 态更新支持不够的问题，结合素数和i b s l 两种编码机制的思想，提 出了一种新的x m l 文档树编码机f 1 u - - p b s l ，该编码机制不仅有较好 的查询效率，能完全高效地支持x m l 文档动态更新，而且大大降低 了空间成本。 接着，针对已有小枝模式查询匹配算法或基于归并会有很高的计 算代价或非常复杂的问题，尤其是考虑了大部分查询表达式中只有一 个结点是最终的输出结点的特点，提出了一种新的x m l 小枝模式查 询匹配算法t w i g n m i 。该算法和以往大部分的小枝模式查询算法不 同，不是从根结点开始查询匹配，而是直接以输出结点为导向，自底 向上逆向到根结点匹配，不需要归并，只用了一个栈来实现，且能够 扫描更少的有效数据结点而得到最终满足查询的匹配结果。 本文提出的p b s l 编码机制和小枝模式查询匹配算法t w i g n m i ， 是在x m l 数据库研究方向上进行的有效尝试，为以后的相关研究提 供了新的思路和方法。 关键词x m l 数据库，编码机制，小枝模式查询匹配算法 a bs t r a c t n o w a d a y s ，w i t ht h ec o n s t a n ts p r e a do fx m lr e l a t e ds t a n d a r d sa n d a p p l i c a t i o n s ，t h e r ea r e al a r g en u m b e ro fx m ld a t ai n l o t so ff i e l d s ， p a r t i c u l a r l yi nt h ew e b al a r g en u m b e ro fo b v i o u sf a c t ss h o wx m lh a s b e c o m et h ea c t u a ls t a n d a r do ft h ed 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 t h e e m e r g e n c eo fal a r g en u m b e ro fx m ld o c u m e n t sp r o m o t e st h er e s e a r c h o nx m l d a t a b a s e ，i n c l u d i n gx m l d a t as t o r a g e ，i n d e xt e c h n i q u e ，q u e r y p r o c e s s i n ga n dq u e r yo p t i m i z a t i o nt e c h n i q u e a m o n gt h e s e ，l a b e ls c h e m e i ni n d e x t e c h n i q u e a n dt w i g p a t t e r nm a t c h i n ga l g o r i t h mi nq u e r y p r o c e s s i n ga r e t h ec u r r e n tr e s e a r c hf o c u s k i n d so fl a b e ls c h e m e sa n dt w i gp a t t e mm a t c h i n ga l g o r i t h m sh a v e b e e np r o p o s e dt or e d u c ed a t a b a s ea c c e s s e s ，c o n n e c t i o no p e r a t i o n sa n d i m p r o v eq u e r ye f f i c i e n c y b ya n a l y z i n gt h ex m ll a n g u a g e ，x p a t h l a n g u a g e ，x q u e r yl a n g u a g e ，x m lt w i gp a r t e mq u e r ya n dx m l d a t as e t s ， f o c u s i n go nav a r i e t yo fe x i s t i n gx m l t r e el a b e ls c h e m e sa n d t w i gp a t t e m m a t c h i n ga l g o r i t h m s ，t h i sp a p e rs u m m a r i z e ss o m ep r o b l e m sa b o u t e x i s t i n gx m l t r e el a b e ls c h e m e sa n d t w i gp a t t e r nm a t c h i n ga l g o r i t h m s f i r s t ，t h e r e a r et w om a i n p r o b l e m sa b o u t t h ee x i s t i n gl a b e l i n g s c h e m e s ：t h el o ws p a c e - t i m ee f f i c i e n c ya n di n s u f f i c i e n ts u p p o r t i n gf o r d y n a m i cu p d a t eo fx m ld o c u m e n t c o m b i n i n gw i t ht h ep r i m ea n di b s l l a b e ls c h e m e s ，t h i sp a p e rp r e s e n t san o v e lx m lt r e e l a b e l i n g ，c a l l e d p b s lw h i c hh a sa h i g he f f i c i e n c yi nq u e r y , c a nc o m p l e t e l ya v o i d r e - l a b e l i n ga n ye x i s t i n gn o d e sw h e nt h ex m lu p d a t ei sp e r f o r m e di na n y c a s ea n dg r e a t l yr e d u c et h es t o r a g es p a c e t h e n ，e x i s t i n gq u e r yt w i gp a t t e r nm a t c h i n ga l g o r i t h m sa r eb a s e do n m e r g i n gw i t hh i g hc o m p u t a t i o n a lc o s to rv e r yc o m p l e x c o n s i d e r i n gi t a n dm o s tq u e r i e sw i t ho n l yo n eo u t p u tn o d e ，t h i sp a p e rp r o p o s e san e w t w i gp a t t e r nm a t c h i n ga l g o r i t h mn a m e dt w i g n m i t h i sa l g o r i t h mi s d if f e r e n tf r o mm o s te x i s t i n ga l g o r i t h m sw h i c hm a t c hf r o mr o o tt oj e a f n o d e i tm a t c h e sb o t t o m u pw i t h o u tm e r g i n g ，s e t su po n l yo n es t a c ka n d s c a n sl e s s e rd a t an o d e sg e t t i n gt h ef i n a lq u e r yr e s u l t t h i sp a p e rp r o p o s e san e wx m lt r e el a b e ls c h e m e p b s la n da n e wx m l p a r t e mm a t c h i n ga l g o r i t h m t w i g n m i t h e s ea r ee f f e c t i v e a t t e m p tr e s e a r c ha n dp r o v i d en e wi d e a sa n dm e t h o d sf o rt h ef u r t h e r r e s e a r c ho nx m ed a t a b a s e k e yw o r d sx m ld a t a b a s e ，l a b e ls c h e m e ，t w i gp a t t e r nm a t c h i n g a l g o r i t h m 第一章 1 1 1 2 1 3 1 4 第二章 2 1 2 2 2 3 2 4 2 5 2 6 第三章 3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3 9 第四章 4 1 目录 绪论1 研究背景1 研究现状2 研究内容5 论文结构6 x m l 查询相关技术研究7 x m l 语言与模式7 x p a t l l 语言1o x q u e r y 语言1 2 小枝模式查询1 3 常用评测数据集1 4 本章小结。1 5 p b s l 编码机制1 6 编码机制综述1 6 3 1 1 基于区间的编码机制1 6 3 1 2 基于路径的编码机制1 8 3 1 3 编码机制小结1 9 基本定义2 0 静态p b s l 编码2 2 动态p b s l 编码2 2 扩展动态p b s l 编码2 4 p b s l 编码的关系数据库存储2 4 p b s l 编码性质分析2 5 3 7 1包含关系的快速查询2 5 3 7 2 左右位置关系的判断2 6 3 7 3 编码长度分析2 6 实验及性能分析。2 7 本章小结”2 9 一种新的小枝模式查询匹配算法1 w g n m i 3 0 小枝模式查询综述3 0 4 1 1 小枝模式查询研究现状一3 0 4 1 2 小枝模式查询小结3 2 i v 4 2 基本定义3 2 4 3 小枝模式查询匹配算法t w i g n m i 。3 5 4 4 t w i g n m i 算法分析3 9 4 4 1 算法正确性分析3 9 4 4 2 算法效率比较4 0 4 4 3 算法复杂度分析4 l 4 5 实验及性能分析4 2 4 6 本章小结：4 4 第五章研究总结与展望4 5 5 1 本文总结。4 5 5 2 进一步的工作4 5 参考文献4 7 致谢5 3 攻读学位期间主要的研究成果5 4 v 硕十学位论文第一章绪论 第一章绪论 1 1 研究背景 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 ，最新规范为2 0 0 8 年的x m l i 0 第五版【1 1 ) ， 可扩展的标记语言，是一套定义语义标记的规范，其目标是能够定义计算机和人 都能方便识别的数据类型。作为种半结构化数据模型，x m l 具有自描述性、 平台无关性、可扩展性和简单易用等特点，能以可读的格式表示数据而不受表现 形式的限制。随着i n t e m e t 的快速发展，x m l 已成为w e b 数据表示和交换的新 标准，在电子商务、w e b 服务、网格计算以及各种垂直行业得到广泛应用，越来 越多的信息处理系统采用x m l 文档作为信息存储、交换和发布的载体。x m l 类型的数据已成为当前主流的数据形式【2 棚。 1 数据交换和融合 据估计，在一个i t 方案的预算中大约有4 0 花费在整合上。而基于x m l 的松耦合、灵活性的整合方案，相对于其它紧耦合的方案，显著地节省了成本， 缩短了开发周期。在整合过程中，涌现了大量的x m l 数据，为了满足以后系统 的调整和一致性需求，直接存储和管理这些x m l 数据是非常有必要的。 2 以x m l 为中心应用的发展 在许多领域中，x m l 已经取代了原来私有的电子数据交换技术，成为数据 交换事实上的标准。 3 内容和元数据的管理 早在2 0 0 7 年前，一些高端文档著作系统，包括a d o b e 框架，已经从原来私 有格式或s g m l 过渡到x m l 。 接着，两个最著名、使用最广的套装软件o p e n o f f i c e 和m i c r o s o f to f f i c e 把x m l 做为它们文档的存储格式，其它同类软件也纷 纷效仿。x m l 的灵活性，也使其被广泛应用于内容的元数据管理上。 这些x m l 数据，按照所含信息的类型，可分为2 类： 1 以数据为中心的x m l 文档( d a t a r i c h ) ：以数据为中心的x m l 文档包含 的绝大部分信息为值信息，如数值、字符串、日期、逻辑值等，这类文档通常用 于应用程序间的数据交换。 2 富含文本信息的x m l 文档( t e x t r i c ：富含文本信息的x m l 文档的特征 是结构不太规则或根本不规则、数据粒度大、混合内容多、兄弟元素或p c d a t a 出现的次序一般来说非常重要，其常见于网页、商业文档、数字图书馆等。随着 网络应用的快速发展，富含文本信息的x m l 文档正以几何基数迅猛增长，其总 量远远超过以数据为中心的x m l 文档，己成为网络信息资源的主体。 综上所述，x m l 数据以几何基数迅猛增长，其结构也相当复杂，包含递归、 硕士学位论文第一章绪论 嵌套和其它复杂情况，这些复杂结构很难完全映射成关系模型，传统关系数据库 已不能有效对其进行管理。因此，如何有效地管理x m l 数据，已成为当前数据 库领域急需解决的问题，给x m l 存储、索引、查询处理和查询优化技术提出了 严峻的挑战。 1 2 研究现状 x m l 成为信息表示和交换的事实标准，各领域堆积如山的x m l 数据对数 据库技术带来了极大的挑战，也吸引了一大批数据库研究者先后投身于x m l 数 据库研究领域，他们为之付出艰辛和努力，进行了深入的研究，使得x m l 数据 库技术在不过十年多一点的时间内就取得了丰硕的成果。当前x m l 数据库相关 技术的研究总结如下【2 叫： 1 ) ( 】l 数据的存储 ( 1 ) 基于关系的x m l 数据库存储技术f 7 l 。 a 模型映射 需要将x m l 文档模型( 即文档树结构) 映射为关系模式，用关系模式表示 x m l 文档模型的构造，对于所有的x m l 文档都有固定的关系模式，因此，它 是x m l 模式无关的。典型的模型映射方法有：边模型映射方法【8 】和结点模型映 射方法【9 - 1 。 b 结构映射 需要将x m l 模式映射为关系模式，用关系模式来表示目标x m l 文档的逻 辑结构( 即x m l 模式) ，它是x m l 模式相关的。典型的结构映射方法有：结构映 射方法【1 2 彤1 和约束映射方法0 6 , 1 7 】。 ( 2 ) 原生x m l 数据库存储技术1 1 8 j a 基于文本的原生x m l 存储技术 文件系统中的文件，关系数据库中的b l o b 类型或特定的文件格式。这种 方法的优点是当存储或检索整个文档或连续片段时会很快，并且能够精确地再现 原来的x m l 文档，但当重组整个文档或者提取文档的结构时效率却很低。文献 f 1 9 1 就属于这种类型。 b 基于模型的原生x m l 数据库存储技术 根据文件构造一个内部模型并存储这个模型，至于模型究竟怎样存储取决于 数据库。它的基本原理是把x m l 数据抽象成一个由各种结点组成的树状模型， 树中常见的结点有元素结点、属性结点、文本结点。n a t i x l 2 0 l 、l o r e 2 1 、t 觚l i n o 【2 2 1 和t i m b e f l 2 3 j 数据库中x m l 的存储格式就属于这一类。在物理存储中，存取的最 小单位是记录。决定存储方案时需要考虑三个关键问题：一是记录的粒度，二是 2 硕士学位论文 第一章绪论 记录的顺序，三是记录的内部表示。 x m l 数据的存储技术研究在x m l 数据库技术的早期( 1 9 9 9 2 0 0 2 年) l l 较活 跃，到后期研究相对较少，但这不并意味着x m l 存储技术已经成熟，而是因为 随着研究的深入，需要对x m l 查询处理有更深入的认识。 2 x m l 数据库索引技术1 2 4 】 ( 1 ) 结构概要索引 基本思想是，以x m l 树的结构信息为基础，对x m l 树进行约简，使得约 简之后的树中不再存在路径相同的两个结点。如d a t a g u i d e l 2 5 】、1 - i n d e x l 2 6 1 、 a ( k ) 一i n d e x 阳、a p e x l 2 引、d ( k ) i n d e x t 2 9 1 、m ( k ) - i n d e x l 3 们。 ( 2 ) 结点编码索引 给x m l 树中每个结点赋予一个编码( 在绝大部分编码机制中每一个结点的编 码是唯一的) ，使得结点之间的结构关系可以直接通过它们的编码判断出来，而 无须对源x m l 文档进行遍历。为了能高效地查询求解，已经提出了多种x m l 文 档树编码机制，依据编码原理，可以分为基于区i f i j ( r a n g e - b a s e d ) 的编码机制和基 于路径( p a t h b a s e d ) 的编码机制两大类( 详见本文第三章第- d , 节) 。 ( 3 ) 整体索引 从整体上来建立索引，而不是以结点为单位。查询处理时先要将查询转换为 小枝模式，并映射到另外一种形式，或者说也要给查询建立“索引”。查询匹配是 整体匹配，而不是先分拆后组装。文档索引和查询“索引”之间的匹配一般比较简 单。目前主要有两种整体索引：基于序列的和基于特征值的索引。基于序列的索 引将x m l 文档树映射到一个编码序列，而基于特征值的索引则将x l v l l 文档映 射为若干个特征值。代表性的基于的序列索引有p r i x l 3 、f i x l 3 2 j 等。 各种类型的索引有着各自不同的特点和优势，系统地比较各种索引是一件很 困难的事，很难说哪种索引最好。但是，展望未来，x m l 索引在完善对数据更 新的支持，同时满足x m l 查询和检索的需求等方面有待进一步地研究。 3 l 查询处理技术 ( 1 ) 基于导航的查询执行策略 基于导航的查询执行策略的关键在于如何设计及构造概要结构，一旦概要结 构建立起来，x p a t h 表达式的处理过程就比较直接了。 ( 2 ) 基于连接的查询执行策略 3 3 】 将x p a t h 表达式分为若干个片段，一个片段是一个“最小”查询单位，可以直 接由相应算法求解，求出每个片段的查询结果，然后将这些片段的结果装配起来， 形成最终结果。有两种连接：结构连接和小枝连接。结构连接指的是找出满足一 定结构关系的所有特定结点对或结点的操作：小枝连接是找出满足某些结构关系 硕士学位论文 第一章绪论 的所有特定结点向量或结点的操作。结构连接和小枝连接都是用来计算查询中的 一个片段，虽然，小枝连接在概念上相当于多步结构连接，但是执行一步小枝连 接比执行多步结构连接效率要高，而且事实上一步小枝连接是作为一个整体来执 行地( 详见本文第四章第- d , 节) 。 ( 3 ) 混合的查言询执行策略 基于导航的x m l 查询执行策略和基于连接的x m l 查询执行策略各有优缺 点，一种新的思路就是将两者结合起来，实现优势互补。如文献【3 4 】，就是在这 方面的尝试者。 ( 4 ) 基于整体匹配的查询执行策略 与基于连接的策略将匹配过程按照结构关系分为很多步不同，这种策略试图 通过寻找查询树模式和文档树之间整体的直接匹配。这种执行策略的效果主要取 决于映射方法。 x m l 查询处理技术，目前的研究虽然角度众多，非常活跃，但是远未成熟， 由于x m l 模型固有的复杂性和x m l 查询语义上的复杂性，x m l 查询处理还有 着相当的难度，而目前的研究成果仅仅是为x m l 查询处理技术的深入研究打下 了基础，并提供了一些启示。 4 x m l 查询优化技术 ( 1 ) x m l 查询最小化技术 实质就是等价问题，实质又是查询包含问题，求一个查询的最小化查询就是 找与之等价的一个规模最小的查询。文献 3 5 1 对x m l 查询的最小化做了一个比 较系统而全面的研究。 ( 2 ) 基于代价的x m l 查询优化 在x m l 查询中，一个给定的查询或是逻辑查询计划，在转换为物理查询计 划的时候往往有多种选择，通常要对多个物理查询计划进行评价，选择最好的物 理查询计划，这种评价往往是基于代价的。文献 3 6 佣一种叫b l o o m 直方图的概 要结构来描述x m l 文档中的概要信息，作为查询代价评估的依据。 ( 3 ) x m l 结构连接顺序的选择 在基于连接的x p a t h 查询处理方式中，一个x p a t h 被分解为一系列的连接操 作，而这些连接操作的求解顺序是多种的，不同的求解顺序查询性能可能相差很 远。x m l 查询的结构连接顺序的选择是一个较新的领域，相关研究文献有【3 7 】。 ( 4 ) x m l 视图查询优化技术 x m l 视图之上的x m l 查询可以有多种方案执行，比如将视图物化或者将 视图查询合成等，不同方案查询性能可能相差很远。 x m l 查询优化技术是x m l 数据库技术中重要的研究问题，是实现高效查 4 硕十学位论文第一章绪论 询的关键之一，但是由于x m l 数据库许多技术还处于发展时期及x m l 查询优 化技术有其自身的复杂性，所以，至今x m l 数据查询优化技术还相当稚嫩。 5 x m l 数据库性能评测标准 研究出更有公信力、权威的评测方法和数据集。 最后不得不提到的是现行主流商用数据库在这方面的努力： 1 o r a c l e ：甲骨文公司的o r a c l e 数据库是现在市场占有率第一的商用数据 库管理系统。早在o r a c l e8 i 中，就支持x m l ；到了o r a c l e9 i ，提供了x m ld b 功能，支持x m lt y p e 数据类型；o r a c l e1 0 9 中，功能和性能得到进一步加强； 在o r a c l e1 l g 中，可以使用c l o b 及二进制两种方式保存x m l 信息，还支持针 对x m l 的查询机制。 2 d b 2 ：d b 2 是由i b m 公司推出的，具有深厚的理论和技术底蕴，在数据 库市场上很有竞争力。在2 0 0 6 年发布的d b 2v 9v i p e r 中，提出了p u r e x m l 技 术，这是一个x m l 数据处理技术方面的重大进步，x m l 数据和关系数据一样 成为了数据库中的一等公民。2 0 0 8 年升级版本d b 2v i p e r2 中，对p u r e x m l 技 术进行了改进和完善。 3 s q ls e r v e r ：s q ls e w e r 是由微软公司推出的，在数据库市场上仅次于 o r a c l e 和d b 2 ，近年的发展势头很猛。早在s q ls e r v e r2 0 0 0 中，就支持x m l ， 把x m l 做为b l o b 对象存储，并对s e l e c t 做了一些x m l 方面的扩展；到了s q l s e r v e r2 0 0 5 ，提出了新的、n a t i v ex m l 数据类型，引入了对x m l 索引的支持； s q ls e r v e r2 0 0 8 中，对以前x m l 功能进行了加强和完善，特别是加强了x m l 数据的插入功能。 1 3 研究内容 本文的研究内容和所做的工作主要涉及本章1 2 小节中的l ( 1 ) a 、2 ( 2 ) 和3 ( 2 ) 三个方面，具体如下： 一、x m l 文档树编码机制方面 1 深入研究已有各种x m l 文档树编码机制，特别是素数、p d i v 和i b s l 编码机制： 2 提出一种新的动态x m l 文档树编码机伟i j - - p b s l ，给出p b s l 编码算法， 包括静态和动态编码算法，提出扩展p b s l 编码思想； 3 将x m l 数据采用d o m 4 j 解析，通过j d b c 驱动程序访问关系数据库 o r a c l e1 0 9 ，将x m l 数据存入关系数据库，并给出基于p b s l 编码的x m l 数据 关系数据库存储表结构； 4 对p b s l 编码进行深入研究和分析： 硕士学位论文第一章绪论 ( 1 ) 编码所采用x m l 文档数据模型的研究：p b s l 编码的数据模型为树； ( 2 ) 编码空间成本分析：编码的最大长度和平均长度分析； ( 3 ) 编码对x m l 数据动态更新完全支持的研究； ( 4 ) p b s l 编码对x p a t h 和x q u e r y 的支持； ( 5 ) 编程实现i b s l 、p d i v 和p b s l 三种编码机制，对三种编码性能进行比 较。 二、小枝模式查询匹配算法方面 1 深入研究已有的多种x m l 小枝模式查询匹配算法，特别是最早的经典 算法t w i g s t a c k 、t w i g l i s t 和本人所知的、最新提出的t w i g n m 算法； 2 提出一种新的小枝模式查询匹配算法t w i g n m i ，结出t 而g n m i 算法思 想和伪代码描述； 3 对州斟m i 算法的正确性、效率和复杂度进行分析； 4 编写了c + + 程序，实现t w i g s t a c k ( 采用区间编码机制中的z h a n g 编码) 、 硕士学位论文第二章x m l 查询相关技术研究 第二章x m l 查询相关技术研究 2 1x m l 语言与模式 x m l 是由w 3 c 的x m l 工作组定义的。这个工作组是这样描述该语言的： x m l 是s g m l ( s t a n d a r dg e n e r a l i z e dm a r k u pl a n g u a g e ，标准通用标记语言) 的子 集，其目标是允许普通的s g m l 在w e b 上以目前h t m l ( h y p e r t e x tm a r k u p l a n g u a g e ，超文本标记语言) 的方式被服务、接收和处理。x m l 被设计成易于实 现，且可在s g m l 和h t m l 之间互操作。” x m l 和h t m l 一样，都是s g m l 的一个子集。s g m l 过于复杂，实际上根 本没有流行起来，而h t m l 则过于简单且缺乏灵活性。x m l 是一种介于s g m l 和h t m l 之间的语言，它保持了s g m l 强大的标记功能，同时又没有损失灵活 性和开方性。x m l 是一种元标记语言，用户可以定义自己需要的标记，只要这 些标记是满足某些最低准则。 相对于h t m l 而言，x m l 具有很多优点： 1 x m l 是自描述的。x m l 的最大能量来源于它不仅允许用户定义自己的 一套标记，而且这些标记不必像h t m l 一样局限于对于显格式的描述。 2 x m l 支持对文档内容的验证。x m l 文档的结构和内容必须符合一定的 文档规则，最起码它要遵守基本的x m l 语法，除些之外，还往往受到一定模式 的约束。有了模式，就可以方便地验证文档的有效性。 3 x m l 允许开发各种不同专业的特定领域的标记语言。有了这些语言，这 个领域的专业人士就可以自由地交换短文、数据和信息，而不必担心对方是否能 够解析和理解这些数据。 4 x m l 是非专有并易于阅读和编写的。这使得它成为在不同的应用间交换 数据的理想格式。x m l 是基于w 3 c 定制的开放标准。从而使得基于x m l 的应 用具有广泛性。 5 支持高级搜索。因为可以知晓文档内容的结构和含义，所以很容易在x m l 文档中进行搜索。 x m l 的语法简单易学，简单的说，一个x m l 文档主要由以下几部分组成 ( x m l 文档的准确详细含义请参见w 3 c 发布的x m l 文档规范) ： 1 x m l 声明。x m l 声明必须在文档的第一行，而且其中的字母是区分大 小写的。例如， ，其中， v e r s i o n = ”1 0 ”是x m l 文档的版本号，e n c o d i n g = ”u t f 8 ”是文字编码声明， s t a n d a l o n e = ”n o ”是独立文件声明。 2 元素。通常，元素组成了x m l 文档中的大部分内容。元素由一对标记( 开 7 硕七学位论文第二章x m l 查询相关技术研究 始标记和结束标记) 和字符数据组成，开始标记的形式为 ，结束标记的 形式为叫标记名 ，字符数据位于开始标记和结束标记之间。如果元素没有字符 数据，则成为空元素，空元素可以用一种速记法来表示，即 。 3 属性。元素可以用属性来注释。属性通常用来给元素显示额外的信息。 元素的属性在元素的起始标记中结出，形式为 - 。属性值必须 出现在单引号或双引号中，一个元素可以有任意数目的属性，但是它们的名称必 须不同。 4 处理指令。通常用来为处理x m l 文档的应用程序提供信息，这些信息 包括如何处理文档，如何显示文档等。处理指令由两部分组成：处理指令的目标 或名称、数据或信息，其格式为 。 5 注释。x m l 支持注释。注释分别使用字符序列 ! ? 和“”作为开始和 结束，注释的文本内容在这两个字符序列之间。 6 命名空间。相当于一个词汇表，它限定了与之关联的所有元素的作用范 围。它本身也有名称，叫统一资源标记符( u n i f o r mr e s o u r c ei d e n t i f i e r ，u ) 。命 名空间的名称和元素的本地名称组合在一起形成了一个全局唯一的名字，叫限定 名( q u a l i f i e dn a m e ，q n a m e ) 。 示例x m l 文档b i b x m l t 3 酗如下： t c p i pi l l u s t r a t e d l 舔伊s t e v e 船 l 嬲伊 f i r s 伊w a d d i s o n - w e s l e y 6 5 9 5 a d v a n c e dp r o g r a m m i n gi nt h eu n i xe n v i r o n m e n t s t e v e n s w a d d i s o n - w e s l e y 6 5 9 5 d a t ao nt h ew e b a b i t e b o u l s e r g e 8 硕士学位论文 第二章x m l 查询相关技术研究 b u n e m a n p e t e r s u c i u d a n m o r g a nk a u f m a n np u b l i s h e r s 3 9 9 5 t h ee c o n o m i c s o ft e c h n o l o g ya n dc o n t e n tf o r d i g i t a l t v g e r b a r g d a r c y c i t i k l u w e ra c a d e m i cp u b l i s h e r s 12 9 9 5 x m l 文档本质上是保存信息的结构化载体。为了得到有效的x m l 文件， 还必须要明确文件中的信息必须遵守哪些结构，即需要一种用来描述x m l 文档 中信息结构的机制，这种机制不仅建立了x m l 文档中可以使用的x m l 词汇表， 还定义了x m l 文档中元素的顺序、元素的嵌套和内容模型，并建立了文档数据 的数据类型。解决方案有两个： 1 一个是早期的、简单的d t d ( d o c u m e n tt y p ed e f i n i t i o n ，文档类型定义) ， 它是一种保证x m l 文档格式正确的有效方法，可以通过比较x m l 文档和d t d 文件来看文档是否符合规范，元素和标签使用是否正确。一个d t d 文档包含： 元素的定义规则、元素间关系的定义规则、元素可使用的属性、可使用的实体或 符号规则。 示例x m l 文档的d t d l 3 9 l 如下： ! e l e m e n tb i b ( b o o k 幸) 9 硕士学位论文 第二章x m l 查询相关技术研究 ! e l e m e n tf i r s t ( # p c d a t ap ! e l e m e n ta f f i l i a t i o n ( # p c d a t ap 2 另一个是基于d t d 有较大局限性，后来提出的x m ls c h e m a 。w 3 c 于 2 0 0 1 年5 月把x m ls c h e m a 第二个版本作为官方正式推荐，该版本包括三个部 分4 叫2 1 。x m ls c h e m a 是定义一份x m l 文档的合法组件群，就像d t d 的作用一 样，一份x m ls c h e m a ： ( 1 ) 定义了可以出现在文档里的元素 ( 2 ) 定义了可以出现在文档里的属性 ( 3 ) 定义了哪些元素是子元素 ( 4 ) 定义了子元素的顺序 ( 5 ) 定义了子元素的数量 ( 6 ) 定义了一个元素是否能包含文本，或应该是空的 ( 7 ) 定义了元素和属性的数据类型 ( 8 ) 定义了元素和属性的默认值和固定值 虽然x m ls c h e m a 是后期针对d t d 功能不足而提出的，但是x m ls c h e m a 并不是能够解决所有的问题，特别是它不能替代d t d ，d t d 有其自身的优势， 可以对同一个文档同时使用x m ls c h e m a 和d t d 。 2 2x p a t h 语言 x p a t h 也是由w 3 c 创建的，它的最新推荐标准是2 0 0 7 年的x p a t h2 0 1 4 3 1 。 x p a t h 使用一种紧凑的、非x m l 的语法，主要目的是对一个x m l 文档进行寻 址。这里所说的x m l 文档是一个被抽象的有多个结点的逻辑上的树模型。它有 不同的结点类型，包括根结点、元素结点、内容结点、属性结点、命名空间结点、 处理指令结点和注释结点七种。 x p a t h 的主要构件是路径表达式，其中，最重要的表达式是定位路径( 1 0 c a t i o n p a t h ) 表达式，亦简称为路径表达式，这也是它为什么命名为x p a t h 的原因。定位 路径表达式有两种，分别是相对定位路径和绝对定位路径。每个定位路径表达式 都由一个或多个定位步( 1 0 c a t i o ns t e p ) 组成，每个定位步之间用正斜杠分开。绝 对路径以正斜杠( ) 开始，它是从文档树的根结点( 即文档结点) 开始定位路径；而 相对路径则直接从某个定位步开始定位路径。x p a t h 中用上下文结点集来描述定 位路径的求值过程是如何进行的。上下文结点集定义为：表达式中给定点确定的 当前结点集；而上下文则定义为：正在处理的当前结点。定位按照顺序从左到右 1 0 硕+ 学位论文 第二章x m l 查询相关技术研究 一次一个地求值。 一个定位路径由若干个定位步组成，而一个定位步有三个部分： 1 一个轴，它指定了定位步选择的结点与上下文结点之间树状关系； 2 一个结点测试，它指定定位步选择结点的结点类型以及结点扩展名；