（管理科学与工程专业论文）xpath查询的模式检验与xml统计信息的收集方法.pdf

摘要 近年来，随着互连网的迅猛发展，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 ) 已经 成为数据交换事实上的标准，这也使得我们对x m l 文档存储有了新的理念 x m l 数据库，并且随着对x m l 查询的要求越来越多，在x m l 数据库上进行查询 成为目前x m l 技术研究领域的重要组成部分。在x m l 模式的研究方面，w 3 c 于 2 0 0 1 年5 月正式推荐x m ls c h e m a 为x m l 模式的标准，并且越来越多的企业和 组织都开始支持该标准，如何利用x m ls c h e m a 的信息正在成为一个新的研究热 点。 由于x m ls c h e m a 用于定义x m l 文档的结构，因此x m ls c h e m a 拥有x m l 文档 结构的大量信息，在对x m ls c h e m a 和x p a t h 的相关文献进行研究之后，本文提出 了使用ls c h e m a 对x p a t h 表达式进行初步检验的方法，该方法的优越性在于仅 使用x m ls c h e m a 而不用存取x m l 文档数据就可实现对x p a t h 表达式的初步检验。 本文提出了实现该方法的基本算法，并对算法进行了实验，实验证明算法的性能 非常好。 利用统计信息优化数据库查询，是提高查询效率的重要方法之一，由于“l 数据自身的特点，传统数据库统计信息的收集和计算方法不适用于x m l 数据库， 所以要根据x m l 数据的结构特点构造适用的统计信息。本文对近期关于x m l 数 据库统计信息研究的相关成果进行了综述，包括统计信息的构造方法和模型等， 并提出了一种统计信息的通用框架，该框架结构主要包括两个部分的统计信息， 一部分是针对祖先，后裔关系，另一部分是针对父子关系，特别是对于父子关系的 统计信息，本文提出一种父点模型方法，如果以该模型结构构造统计信息，运用 该统计信息对父子关系的连接结果集进行估计，其结果比较能反映真实情况。本 文针对父点模型方法，提出了构造该模型统计信息的算法，并对该算法进行了实 验，通过对实验结果进行性能分析，证明该模型方法可以达到要求。 关键字：x m l 、x m ls c h e m a 、x p a t h 、统计信息、x m l 查询优化、模型 独创性声明 本人郑重声明：所呈交的论文是我个人在导师指导下进行的研究 工作及取得的研究成果尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他入已经发表或撰写的研究成果，也不包含 为获得江西财经大学或其他教育机构的学位或证书所使用过的材料 与我一同工作的同志对本研究所做的任何贾献均已在论文中作了明确 的说明并表示了谢意 4i， 签名：l 垄12 苎日期：砭! 竺：z ! ：! 关于论文使用授权的说明 本人完全了解江西财经大学有关保留、使用学位论文的规定，印： 学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以 公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保 存论文。 ( 保密的论文在解密后遵守此规定) 乃李墨 日期：竺f ，9 ，。厶 1 绪论 1绪论 1 1 论文背景 x m l 日益成为重要的数据交换格式，越来越多的x m l 数据存储在x m l 数据 库中，并且随着对x m l 查询的要求越来越多，在x m l 数据库上进行查询成为目 前l 技术研究领域的重要组成部分，每年的世界数据库的相关会议都有相当数 量的研究文献是关于这方面的，并且o r a c l e 、m i c r o s o r 和i b m 等数据库厂商也 在深入的研究该领域的商业应用。 由于x m l 自身的特点一半结构化、自描述、可扩展和灵活性，构造x m l 数 据库与传统的数据库的方法不尽相同，因此对于x m l 数据库的查询方法的实现也 不同，以目前已有的成果来看，x m l 查询的效率要比传统的数据库的查询效率低 许多，如何提高x m l 查询效率已经显得十分重要和迫切了。对数据库信息进行统 计，并利用统计信息来优化查询是传统的查询优化方法之一，但x m l 数据分布的 不规则性使得传统的数据库统计信息方法难以达到所需的估计精度，误差相当大。 在x m l 模式的研究方面，w 3 c 组织于2 0 0 1 年5 月正式推荐x m ls c h e m a 为 x m l 模式的标准，并且越来越多的企业和组织都开始支持该标准，模式的确定对 于理解x m l 数据的结构有重大意义，如何利用x m ls c h e m a 的信息正在成为一个 新的研究热点。 1 2 研究课题的提出及意义 利用x m l 数据的统计信息优化x m l 查询，是提高查询效率的重要方法之一， 随着x m ls c h e m a 的广泛应用，利用x m ls c h e m a 的信息来为查询服务也将受到 更多的重视，本文的研究包括两部分，一部分是用x m ls c h e m a 验证x p a t h 查询 的存在性，另一部分提出一种统计信息通用框架结构，该框架结构可以用于提高 对x m l 查询的估计准确度。我们的研究得到了江西省自然科学基金“基于关系的 x m l 数据库系统的查询优化技术研究”( 0 4 1 1 0 0 9 ) 和江西省教育厅科技项目“基 于关系数据库的x m l 查询研究”( 赣财教【2 0 0 3 7 3 号) 的资助。 1 3 本文的主要工作 本文的主要研究工作是提出了一种基于x m ls c h e m a 的x p a t h 查询路径表达 式分析方法，它可以初步检验x p a t h 路径表达式的存在性，本文还提出一种统计 信息通用框架，并且提出父点模型方法用于存储统计父子关系节点，同时给出了 生成该统计信息的算法。 x p a t h 查询的模式检验与x m l 统计信息的收集方法 本文其它部分的组织结构是这样的，第二章中介绍了一些基本知识包括 x m l 、x m ls c h e m a 和x p a t h 等，第三章阐述了基于x m ls c h e m a 的x p a t h 查询 路径表达式检验方法，提出了实现算法，并给出部分实现的实例，第四章x m l 数 据库统计信息的研究介绍了几篇关于x m l 数据库统计信息的经典文献，比较各自 的特点，在第五章中提出了一种统计信息通用框架，同时提出了一种父点模型结 构用于构造统计信息，并给出了收集该模型统计信息的算法和分析，最后第六章 是总结与展望。 2 预备知识 2 预备知识 2 1x m l 概述 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 ，可扩展标记语言) 眦】是由w 3 c ( 万维网协会) 设计的用来自动描述数据信息的一种新的标记语言，它是对当初复杂的s g m l ( s t a n d 鲫dg e n e r a l i z e dm a r k u pl a n g u a g e ，标准广义标记语言) h 进行简化以后制定的 一种轻量级标记语言规范。初期x m l 的设计是通过提供更具灵活性和适应性的信 息定义标识来提高w e b 站点功能性，x m l 解决了标准的h t m l 规范的许多限制 和不足，使得人们可以开发出格式更加复杂的w 曲页面。随着网络技术及应用的 迅速发展，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 m l 利用基本语法对元素进行描 述，每个元素数据项都具有自己的类型描述和结构描述。由于x m l 是半结构化数 据，x m l 允许定义新的标记，其结构可以随意嵌套，同时还可以使用相同的标记 表示一个数据集，用户还可以随意定义属性，属性和标记的区别在于给定的属性 只能在标记中出现一次，与其他元素无关。此外x m l 采用一些相关规则进行功能 扩充，采用n c l u d e 用于规定文档中包含模式的处理模型与语法规则1 4 】，采用衍 生样式表( c s s ) 规则定义x m l 文档显示的样式1 5 l ，采用可扩展样式语言( x s l ) 定义 格式化的表现形式秘用户文档闻的数据转换，采用x m l s c h e m a 定义x m l 文档 结构和内容m ，9 等等。 2 1 1 舢的特点 x m l 作为一种自描述的语言主要具有以下四个特点：半结构化、自描述、 可扩展和灵活性j 。 ( 1 ) 半结构化 x m l 最大的特点就是半结构化，即x m l 文档可以利用d t d i 伸】或x m l s c h e m a 规范定义 x x p a t h 查询的模式检验与x m l 统计信息的收集方法( 2 ) 自描述x m l 文档通常包含一个文档类型( d t d 或x m l s c h e m a ) 声明，以便于应用程 序理解数据的意义。xml文档中的数据可被能够对xml数据进行解析的应用程 序所提取、分析和处理，并以所需格式显示。( 3 ) 可扩展性 html是一种只有一个固定标记集的特定标记语言，因此html的虽大弱点就是无法随意增加新的标签来表达w e b 上丰富而复杂的内容，而x m l 是一种用 于设计标记语言的原语言，允许用户根据其需要创建自己的标记，这些标记可通 过d t d 或x m ls c h 锄a 加以定义，这是x m l 最大的优势，它解栗耋王垄磊垂提磊 髯鋈妊型鑫；娑彤萄落葶膏希馕埔塌溶矬蛭磊；哩曼。睡冀镊冀辑鋈纛章 l 毛多搴霎薹? 笔主雾辫羹渐嚣囊囊羹鬟孳超i 女【螺历葶； i 的类型 定义 如果元素4 是b 元素， 则现在以元素4 为当| j l 节点，步进链表走到3 c ，重复步骤2 ，在元 素4 的子元素列表中查找元素c ，如果有c 则提取c 的类 型定义，如果没有c 就返 回f a l s e ，并提示c 不存在，该路径不合法；如果存在 c ，则c 为当前节点，步果存在c ，则c 为当前节点，步进链表走到4 一d ，递归步骤3 ，直到路径结束，如图一叁一皆一雷 x x p a t h 查询的模式检验与x m l 统计信息的收集方法 及元髫蠹碴蘑蓊量糕强臻醚，疑琵弼蒜蓍蓍蠢鞋。弼藩露囊雾蔫笛羹巍期昧l ；g 胡? 蠢薹媳螽壁霞j 鐾祷囊藏蕈嚣琵矍蘸薛鞲恻藿裂蹿羹藿烈褥窿毽； 兰；竞霎蠹灌黎雾羹鍪羹美 # i 琵蒌蓉i 蟊羹鐾缉霾窜；耍：磊囊睡黍蓼l 蓉。i 嚣强蠹黢魏鬟鎏；麴壁 摄壁誓冀h u s g 蠢冀鬟囊囊鎏鏊。羹藿塞k ；0 8 e n d ： e n d e l s e l fh e a d st e 口是路径结尾t h e n b e g n q 1 fh e a d s t ep 中元素名和e l e 名字不匹配耵1 e n有效f l a g = t r u e ： e l s eb e g l n 1 fe l e 类型是复杂类型 严算法34 ， 有效f l a g = l a s 7 r _ d e s c e n d a n t 啊a g a r n s t ( s 忙p n e x t ， e i e ) ： e n d ： e n d ： e n d ： l f 有效f l a g _ t r u e ： 终止列表循环； f o r 列表循环e n d 返同( 有效f l a g 根据s t e p 链表信息提示错误信息) ： 算法32 ：以当前节点类型定义对，a 处理，a 在路径结尾。 l a s l h 1 l d _ a g a i n s t ( s t e p l 0 c a t i o ns t e p ， 乩e m e n te l e m e n t ) b e g l n 将上文节点e l 锄e n t 子元素名称装入一个列表e e1 j s t ： 有效f l a g = f a l s e ： i fs t e p 中元素名不是+ t h e n b e g l n 在元素列表e le _ 1 _ s t 中查找与s t 印中元素名相同的元素； i f 存在与s t e p 中元素名相同的元素1 h e n 有效f l a g = t r u e ： e n de l s e b e g l n 有效f l a g - 豫u e ： e n d ： ! 塑塑奎塑塑堡壅笙堕兰! 坠堑塑堡星塑坚塞互鎏 x s ：s c h e m am l n sx s = ”h n p ：，w w ww 3o r 2 0 0 1 m l s c h e 丌1 a ” e l e m e n t f o m d e f a u l t = ”q u a 】j f i e d a t 【r i b u t e f o m d e f a u l f ”u n q u a l l 矗e d c a i a l o bs c h e m af o rb o o k ( ，x s ：d o c u m e n t a t l o n ( ，x s ：a n n o t a t i o n x se l e m e n tn 哪e = ”a u t h o r ”t y p e = ”x s ：s t n g ”m a x o c c u r s = ”u n b o u n d e d ， x s ：e l e m e n tn a m e = ”t i t l e ”t y p e = ”x s ：s t r i n 旦”肛 x se i e m e n tn a m e = ”p u b l i s h n u m ”t y p e = ”p u b l j s h n u m ”， x s ：s i m d l 占n ，p e x s ：r c s t n c t i o nb a s e = ”x s ：吼r i n 一 x s ：e n u m e r a t i o nv a l u e = ”u n k n o w n ”， x s ：曲u m e r a t i o nv a l u e = ”t r a d i t i o n a l ”， x s ：e n u m e r a t i o nv a l u e = ”b i d o n l v ”， ( x s ：e n u m e r a t i o nv a l u e = ”f j x e d p c e ”， ac a t a l o e0 f o n eo rm o r eb o o k s ( ，x s ：d o c u l n e n t a t j o n x s ：r e 吼r l c “0 nb a s e = ”x s ：i n t e 2 e r ” x s ：m i n l n c i u s i v ev a l u e 一1 l o o 分， x s ：m a ) c l n c l u s i v ev a l u e = ”1 0 0 0 0 0 ”， ( ，x s ：r e s 仃j c t i o n ) 可x s ：s j m d l e t y p e x s ：e l e m e 玳n a m e c a t a l o g ”t y p c 2 “c a t a l o g t y p e “ ac o l l e c “o n0 f b 0 0 k s ( ，x s ：d o c u m e n t a t i o n ( ，x s ：a n n o t 砒j o n x s ：e l e m 肌tn 啪e 2 ”b o o k ”t y p e = ”b o o k 时p e ” x s ：d o c u m e n t a t i o n as j n b l eb o o k ( ，x s ：e l e m e n t 叫x s ：s c h e m a 图2 3 c a 【a l o gs c h 锄a 文档 图2 3 示例中包含了标准的x m l 头 ，这表示该模式文 档自己就是一个x m l 文档。而任何x m ls c h e m a 文档的根元素都必须是s c h e m a ， 它有一个或者多个说明自己的属性。在这种情况下，s c h e m a 的n 啪e s p a c e 定义属 8 2 预备知识 性( x m l n s ) 会定义名称空间为x s ，它将用作文档中所有元索的根名称空间。 2 2 2 名称空间 x m l 把名称空间定义为包装x m l 元素供以后重用的方式”。为了使用x m l 文档的名称空间中定义的元素，你必须通过x m l n s 属性声明你希望采用名称空间。 你还必须为该名称空问定义快捷方式的前缀( 例如x s ：) 作为你文档中的根元素，从 而使得名称空间在文档中都可用。前缀是用于文档的任何导入名称空间的元素的 标识符。这一过程就如同在v i s u a lb a s i c 中给库加索引或者导入模块；c + + 、j a v a 或者n e t 下的名称空间也具有同样的含义。因此，s c h e m a 元素必须具有一个x m l 模式名称空间h n p ：u w 3 o 吲2 0 0 1 m l s c h e m a 的声明。 2 2 3a n n o t a t i o n 元素 在c a t a l o gs c h e m a 示例中紧接着出现的元素是a n n o t a t i o n ，它的作用是对其父 元素进行相关说明。任何在s c h e m a 元素的内容之中的元素都可以拥有一个 a n n o t a t i o n ，并且必须是其第一个子元素【1 5 】。a n n o t a t i o n 元素可以有零或多个 d o c u m e m a t i o n 以及a p p i n f o 予元素。d o c 啪e n t a t i o n 元素用于向模式添加用户可读 信息，a p p i n f o 元素添加特定应用程序专用的某种信息。 2 2 4 类型定义 x m ls c h e m a 可以让使用者把x m l 文档中的元素声明为特定的类型，准许解 析器检查文档的内容及其结构。x m ls c h e m a 定义了两种主要的数据类型：简单类 型和复杂类型。这两种数据类型之间的主要区别是复杂类型可以包含其他元素和 数据而简单类型则只能包含数据。 ( 1 ) 简单类型 在图2 _ 3 的c a t a l o gs c h e m a 示例中，有几个元素和属性被声明为简单类型，其 中一些简单类型如s t r i n g 和d e c i m a l 是x m ls c h e m a 中内置的。而其他的一些则是 源于( 或者说是继承) 内置的类型。举例来说，p u b l i s n n u m 元素的类型称为 p u b l i s h _ n u m t y p e ，是源于i n t e g e r 的。内置的简单类型和他们的后继版本都能够被 用在所有的元素和属性声明中，下面的表2 1 列举了部分的在x m ls c h e m a 中内置 的简单类型及其相应的定义【7 】。 x p a t h 查询的模式检验与x m l 统计信息的收集方法 表2 1 简单类型定义说明 简单娄型定义 s t r i n 自 字符串数据。 b o o i e a n 二元类型的m e 或者f a l s e 。 d a t e 历法日期格式是c c y y - m m d d 。 d m e t j m e 历法日期和时间。 t i m e 2 4 小时格式的时间可根据时区调节。 d e c i m a l 任意精度和位数的十进数。 i n t e g e r 整数 f i o a l 标准的3 2 位浮点数。 d o u b l e 双精度6 4 位浮点数， l a n g u a g e x m l10 中定义的合法语言代码 i d x m l1 0 中定义的l d 属性类型。 新的简单类型通过从现有的简单类型( 内置的简单类型以及源于内置简单类型 的简单类型) 引出定义。特别的，可以通过重新约束一个现存的简单类型来引出一 个新的简单类型。换句话说，新类型的合法值范围是现有类型的值范围的子集。 模式使用s i m p l e l 独e 元素来定义和命名新的简单类型，使用r e s t r i c t i o n 元素来指出 现有的基类型，并且用它来标识约束值范围的细节。例如在图2 - 2 示例中， p u b l i s h n u m 元素的类型为p u b l i s h j u m t y p e ，它的值范围为1 0 0 0 到1 0 0 0 0 0 ，为了 定义p u b l i s h _ n u m t y p e 类型，模式使用图2 4 中的代码来约束i n t c g e r 的范围，它是 由一个基本类型定义和两个值域区间方面描述的组合，通过这三个要素来对 p u b l i s hn u m _ 【y p 类型实施了定义。 x ss l m p l e t y p en 帅f ”p u b l i s n n u m t y p e ” x s ：e l e m e n tn a l l l e = 。a u t h o r t y p e = x s ：s t n n g ”m a x o c c u r s 2 ”u n b o u n d e d ”， x s ：e l e m e n tn a m e = ”t l l l e ”t y p e = ”x s ：s t 一“g ”，) x s ：e i e m e n tn a m e = ”g e n r e ”t y p e 2 ”x ss i n n g ”，) x s ：e l e m e n tn a m e = ”p r c e ”t y p e 2 ”x s ：d o u b l e ” x s ：e 】e m e n tn a m e = ”p u b l i s h n u m ”t y p e 2 ”p u b l i s h _ n u m ”，) x s s i m p l e t y p e 4 0 】只确定第一项 b o o k 。x p a t h 表达式可以引用属性及x m l 文档中的元素。当引用属性时，使用“ ” 字符。例如，x p a t 1 表达式c a t a l o g b 0 0 k 【 i d = “b k l 0 2 ” 确定了b 0 0 k 元素第二 项，其i d 属性值“b k l 0 2 ”。x p a t h 也提供函数，下面的x p a t h 表达式确定了b o o k 的d e s c 打p i i o n 元素，其t y p e d e f 属性是“f i x e d p r i c e ”( d e s c r i p t i o n 元素具有值“a n i n - d e p t bl o o ka tc 他a t i n ga p p l i c a t i o n sw i t hx m l ”) ，这个表达式使用了字符串函数 s t a r t s - w i t h ：c a t a l o g ，b o o k 【s t a r t s w i t l l ( t y p e d e f ，”f i x ”) 】d e s c r i p t i o n 2 预备知识 图2 6 一棵节点树 此外，x p a l h 相对于上下文计算表达式，上下文通常用x p a l h 之外的其他技术 如x s l l 、和x p o i n t e r 指定。x p a t h 上下文包括上下文节点以及上下文的大小、位置 和其他相关数据。从上下文的观点来看，其中最重要的是上下文节点。如果上下 文节点是根节点，那么c a 词o g ，b o o k 指的就是c a t a 】o g x m l 中的2 个b o o k 元素。如 果上下文节点是另一个节点，比方说第一个b o o k 元素，那么c a t a l o g ，b o o k 在该x m l 文档中什么也不指。 2 3 2 位置路径 位置路径不是x p a t h 中最完整的语法的构件，但它们确是x p a t h 中最有用也 是应用最广泛的特性。位置路径标识了和上下文有关的一组x p a t h 节点。x p a m 定 义了两种语法：简化语法和非简化语法。 ( 1 ) 非简化语法 下面是使用非简化语法的一些例子； 2 预备知识表2 _ 3 正向轴和反向轴f o r w a r da x i s self：te+： r e v e r 驼a x 6 descendant-onsel p r e c e d i n g - s i b i l n g ： a n c e s t o 卜o 卜s e l t 以f 是各个轴的说明： c h i l d ：轴包含上下文节点的孩子。 d e s c e n d a t l t ：轴包含上下文节点的子孙；子孙是一个孩子或一个孩子的一个孩 子，等妻j 篇悔；型盘臻矬基蓠簿鼓湎篓憾噼历鲁替型参； “”善! 霸剃剽器显虹犁飘争孚。孕矗辅浮猿。 顺i 自i 的l ；衙鬃镬m 惮鏖恨趱坶力舞! 碰蔷矍文档树的所薹岸。囊娄蔷霆篓 薷搓裂鬟燮薯# ；伟摘i 历序粤骟砌桀尊丢竿照4 4 l f a 。 8 ”“1t e c t u “ s e c r e t a r v ( 1 ( )，10 ) ( 1 1 ，l l j d e d a r 【m e 。t c 3 踟 甄幺瑟饕乏。害之繇 麟 麓 ，1 h e d u r e “3 2 ，3 7 、 篓：蕊除心麓am 三惫娄羹j 娄篇豫黹虹n i i 爬2 嬲j 叼翟累? f 3 4 1 f 3 5 1 ( 3 6 1 sd h t a r a 、 0 ；j h r a l9 1 9 1( 2 0 ，2 0 1f 2 1 2 1 1f 2 2 2 2 2 3 2 3 、 图4 2x m i j 义档片断编码图 文献 3 8 】利用这种区问编码的特点构造位置直方图( p o s i t i o nh i s t o 伊a m s ) ，位置 直方图是构建在基本的谓词之上，比如元素名称，属性名称等，基本的位置直方 图 x 轴方向表示b e g i n 的值，y 轴方向表示e n d 的值，由于每个节点的e n d 值是 定不会小于b e g i n 值的，所以图表中，在斜线x = y 之下是没有节点存在的，那么 以图4 2 为例，全部节点的分布图如图4 3 所示。 苦 3 ! ! 苎! 查塑塑堡查堡堕兰! 坠堕：| 堡皇塑! 堑苎互鎏 一 一 n 素4 了元素列表 图34 提取元素c 的类型定义 直口果元素4 不是b 元素，则元素4 为上文节点，递归步骤3 ，将元素8 的 子元素制成列表，如图3 5 所示。 元素8 予元素列表 表目 图 5 提取元素8 的类型定义 如果检验出路径是存在的，那么终止循环，否则元素往下走一个。 ( 4 ) 返回结果。 很明显，这种思路要用到递归的操作，这种操作方法也是遍历树的基本方法， 对于检验路径是非常合适的方法。下面对具体算法进行描述。 3 2 ，2 具体算法描述 通过对正向轴路径表达式的分析，可以得出一个结论；在有上下文的情况i f 有两种主要的情形就可以组合得到各种表达式。 “a ”有两种情况：在结尾、在中间。 “融”有两种情况：在结尾、在中间。 为了清晰描述算法，我们将上述四种情况分为四种函数由算法3 2 、3 3 、3 4 和3 5 来描述，算法3 1 是主调用函数。算法中考虑了包含有通配符的情况的处理。 算法3i ：主调j f i 函数j c 中参数s c h e n m ar i i e 足x m ls c h e m a 文梢，x p a t h 是x p a 山路径表达式。 s n gt e s t x p a i h ( x m l d o cx m ls c h e n m af - 】e ， x p a 【hs t n gx p a t h ) b e g j n 路径表达式以，、，分成步，分解成s 丁e p 链表，每个s t e p 中包肯育轴和素信息( 如，a b ，c ，分解 为a b ，c ) 链表头称为h e a d s t e d 。 将x m ls c h e m a 文档的t o p 崖元紊制成列表： 有效f l a g = f a l s e ： f o r 列表循环b e g j n 田 x p a t h 查询的模式检验与x m l 统计信息的收集方法 f o r 列表循习、e n d ； e n d ： 返回( 有效f l a g ) ： e n d ： 算法35 ：以上文节点类型定义对，a 处理，a 不在路径结尾。 m i d d e s c e n d a n t _ a g a i n s t 【s t e p l o c a t i o ns t e p ， e l e m e n te 】e m e n i ) b e g n q 将上文节点e l e m e n t 子元素名称装入一个列表e l e 】i s t ： 有效f l a g = f a l s e ： f o r 列袁循环b e g i n ： 将列表元素定义为e l e ： 提取元素e i e 类型定义； 1 fe l e 是复杂类型t h e n b e g l n l fe l e 与s t e p 中元素名相同t h e n b e g i n 设当前步进s t e d 位置f l a g - t r u e ： 取s t e p 链表中下一项赋给s t e d n e x t ； i fs t e p n e x t 是以“”开头 t h e n b e g i n i fs c e p d e x t 是s t e p 链表结尾 ，+ 算法32 + l a s t c h i l d a g a l n s t ( s t e p n e x t ，e i e ) ： e l s e p 算法 x x p a t h 查询的模式检验与x m l 统计信息的收集方