（计算机软件与理论专业论文）xml数据查询的关键技术研究.pdf

e 原创性声明和关于论文使用授权的说明 原创性声明 i i i i l l t l l l l l l l l l 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 l i i y 17 9 18 2 2 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名： 赵互盈日期：兰! ! ：生势 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名： 丞血袈导师签名日期：迦f 皇：鱼 山东大学硕七学位论文 目录 摘要i a b s t r a c t i i 第一章绪 论1 1 1 预备知识l 1 2 国内外研究现状4 1 3 本文的主要贡献6 1 3 1x p a t h 路径表达式的优化6 1 3 2 基于o r i e n t x a 的x m l 代数优化“6 1 3 3 多x m l 文档片段的相似性度量方法7 1 4 本文的组织结构7 第二章x p a t h 路径表达式的最优化方法9 2 1 背景与相关概念9 2 2m n - p a t h 理论基础1 1 2 3m i n p a t h 结构创建方法1 2 2 3 1 元素关系表的建立1 2 2 3 2x t r e e 的生成1 3 2 3 3x g r a p h 的建立1 4 2 4m i n p a t h 优化处理方法15 2 4 1 路径表达式的分解1 6 2 4 2 路径表达式的重构1 6 2 5 实验结果及分析l8 26 相关研究工作”1 9 本章小结_ ”2 0 第三章x m l 查询代数与查询优化方法2 0 3 1 背景与相关介绍2 1 3 2x l v l 查询代数o r i e n t x a 。2 1 3 2 1o f i e n t x a 的基本特点2 l 3 2 2 关键的代数操作符2 2 【ij 东大学硕士学位论文 3 2 3 查询代数表示方法2 5 3 3x m l 查询优化方法2 6 3 3 1 基于等价变换的查询优化2 6 3 3 2 复杂路径的最小分解算法2 7 3 4 最小分解算法复杂性分析3 0 3 5 相关研究工作3 0 一 本章小结3 0 第四章多x m l 文档片段相似性度量方法3 1 4 1 背景及相关介绍一3l 4 2 文档片段多标签有向树模型3 1 4 3 相似度度量方法3l 4 3 1 结点标记分析31 4 3 2 边标记分析3 2 4 4x m l 匹配算法设计”3 3 4 4 1 粗糙结果集计算“3 3 4 4 2 边优化方法实现3 4 4 5 实验效果分析3 5 。 本章小结3 6 第五章结束语3 7 5 1 总结3 7 5 2 展望3 7 参考文献4 0 致谢4 5 攻读硕士学位期间发表的学术论文目录4 6 i 东大学硕士学位论文 t a b l eo fc o n t e n t s a b s t r a c ti nc h i n e s e i a b s t r a c ti ne n g l i s h c h a p t e rli n t r o d u c t i o n ”1 1 1r e s e a r c hb a c k g r o u n d 2 1 2r e s e a r c ha c t u a l i t y 4 1 3t h em a i nc o n t r i b u t eo ft h et h e s i s 6 1 3 1t h eo p t i m i z a t i o no fx p a t he x p r e s s i o n 6 1 3 21 1 l ea l g e b r ao p t i m i z a t i o nb a s e do no r i e n t x a 6 1 3 3s h e m a m a t c h i n gm e t h o do fs e v e r a lx 几d o c u m e n t 7 1 4t h es t r u c t u r eo f t h et h e s i s ”7 c h a p t e r21 h eo p t i m i z a t i o no f x p a t he x p r e s s i o n s 9 2 1b a c k g r o u n da n dr e l a t e dc o n c e p t s 9 2 2t h e o r yb a s e m e n to f m 皿帅棚”1 1 2 3t h ec r e a t i o no f m d 师炯1 2 2 3 1 ，1 1 l eb u i l d i n go f d e m e n t sr e l a t i o nt a b l e 1 2 2 3 2t h ec r e a t i o no fx t r e e 13 2 3 31 1 1 ec r e a t i o no f x g r a p h - 1 4 2 4t h eo p t i m i z a t i o nm e t h o do f m n p a t h 15 2 4 1d e c o m p o s i t i o no f p a t he x p r e s s i o n 一1 6 2 4 2r e b u i d i n go f p a t he x p r e s s i o n 1 6 2 5e x p e r i m e n ta n da n a l a s i s 18 2 6r e l a t e dw o r k s 1 9 c h a p t e rc o n c l u s i o n 2 0 c h a p t e r3 x m l q u e r ya l g e b r aa n dq u e r yo p t i m i z a t i o n 2 1 3 1b a s i ct h e o r yo f x 儿q u e r y 2 1 3 2x m l q u e r ya l g e b r ai e n t x a 2 2 3 2 1b a s i cc h a r a c t e r i s t i c so f o r i e n t x a ”2 2 3 2 2t h ek e yo p e r a t i o n so fo r i e n t x a 一2 3 山东大学硕士学位论文 3 2 3t h ep r e s e n t a t i o no f q u e r ya l g e b r a 2 6 3 3t h er e s e a r c ho nx m l q u e r yo p t i m i z a t i o nm e t h o d 2 7 3 3 1t r a n s l a t i o nb a s e do ne q u i v a l e n c e 2 7 3 3 2d e c o m p o s i t i o na r i t h m e t i cf o rc o m p l e x p a t h 。“2 8 3 4t h e c o m p l e x i t ya n a l a s i s “3 0 3 5r e l a t e dw o r k s 3 0 c h a p t e rc o n c l u s i o n 3 0 c h a p t e r4m u l t i p l ex m l d o c u m e n ts i m i l a r i t ym e a s u r em e t h o d 。31 4 1r e l a t e dc o n c e p t s 31 4 2t h ec r e a t i o no f m u l t i 1 a b e l e dt r e em o d e l 3l 4 3c a l c u l a t i o no fq u e r ys c h e m a 3 2 4 3 1n o d el a b e l ”3 l 4 3 2e d g el a b e l 3 2 4 4s c h e m am a t c h i n gm e t h o d 3 4 4 4 1t h ec a l c u l a t i n go fi n i t i a lr e s u l t 3 3 4 4 2e d g el a b e lo p t i m i z a t i o np r o c e s s 一3 4 4 5e x p e r i m e n t sa n da n a l a s i s 3 5 c h a p t e rc o n c l u s i o n 3 7 c h a p t e r5c o n c l u s i o na n do u t l o o k 3 8 5 1c o n c l u s i o n 3 8 5 2e x p e c t 撕o n 3 8 r e f e r e n c e s ：4 0 a c k n o w l e d g e 4 6 t h et h e s i sp u b l i s h e df o rt h em a s t e r sd e g r e e 4 7 - 山东大学硕士学位论文 摘要 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 数据的存储管理、查询处理、访问控制、 数据更新等。x m l 查询处理与优化包括x m l 查询代数、查询处理、查询优化等。 x m l 数据查询是x m l 数据管理一个非常重要的组成部分，是当前学术界研究的 一个热点方向。x m l 查询根据其查询模式的不同可以分为两类：x m lq u e r y 查 询方式和x m l 瓜查询方式。而x m li r 方式又可以细分为三类：x m li r j k e y w o r d 方式、x m ll r d q u e r y 方式和x m li p j f r a g m e n t 方式。 本文主要研究x m l 数据集成查询过程中碰到的一些问题，以及所采取的相 应解决方案。其中主要包括三部分的内容：第一，由于x _ p a t h 是当前流行的x m l 数据查询语言x q u e r y 和x s l t 的基础，我们针对x p a t h 语言中的复杂路径表达式， 设计了一种路径表达式的最优化方法，用以提高在对x m l 进行查询时的执行效 率；第二，基于当前比较流行的一种查询代数o r i e n t x ) t ，基于代数表达等价原则， 设计了一系列的等价转化方法，简化了舳查询路径表达式的代数表示，优化 了x m l 数据的查询效率：第三，针对多x m l 数据源的集成查询，由于查询过程 往往涉及到对多个x m l 片段中相似重复信息的处理，而我们有时候需要对多 x m l 片段中的共同信息进行提取，由此，本文提出一种x m l 有向标记树模型， 并在此模型上设计了一种相似匹配算法来对共同信息进行挖掘。实验显示，该算 法具有很高的可行性及使用价值。 一关键词：x m l 查询，查询优化，模式匹配 d e f i c i e n c yi nx m ld a t aq u e r yf i e l d ，t h ee f f i c i e n c ya n ds p e e dn e e dt ob ei m p r o v e d l a r g e l y x m ld a t am a n a g e m e n ts y s t e m m a i n l ys o l v et h ex m l d a t as t o r a g em a n a g e m e n t ， q u e r yp r o c e s s i n g ，a c c e s sc o n t r o l ，d a t au p d a t e s x m ld a t as t o r a g em a n a g e m e n t t e c h n o l o g yi n c l u d ed a t as t o r a g e ，d a t ae n c o d i n g ，i n d e x i n ga n do t h e rm e t h o d s x m l q u e r yp r o c e s s i n ga n do p t i m i z a t i o n ，i n c l u d i n gx m lq u e r ya l g e b r a , q u e r yp r o c e s s i n g ， a n dq u e r yo p t i m i z a t i o n x m ld a t aq u e r yi sa v e r yi m p o r t a n tc o m p o n e n to fx m l d a t am a n a g e m e n ta n di ti sah o tt o p i co ft h ec u r r e n ta c a d e m e a c c o r d i n gt ot h e d i f f e r e n tq u e r yp a t t e r n sx m lq u e r yc a nb ed i v i d e di n t ot w om a i np a r t s ：x m l q u e r yq u e r ym o d ea n dx m li rq u e r i e s x m li rc a na l s ob ed e v i d e di n t ot h r e e p a r t s ：x m li r k e y w o r dm e t h o d ，x m li r q u e r ym e t h o d sa n dx m li r f r a g m e n t m e t h o d t h i sp a p e rs t u d i e ss o m eo ft h ek e yt e c h n o l o g i e so fx m lq u e r i e s ，c o n s i s t i n g m a i n l yt h r e ep a r t s ：f i r s t , i n t r o d u c i n gb r i e f l yt h eb a s i cc o n c e p t so fx m ld a t aq u e r y ， a n dd e s i g n i n gao p t i m i z a t i o nm e h o df o rx p a t he x p r e s s i o n s s e c o n d l y ，w ea n a l y z e d k e y w o r d ：x l l i lq u e r y ，q u e r yo p timiz a tio n 。s c h e m ai l a t c hin g i 一 ， 山东大学硕十学位论文 1 1 预备知识 第一章绪论 x _ m l i , 2 1 ( 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 ( w o r l dw i d ew e bc o n s o r t i u m ) 的团体提出并构想出来的。目前x m l 已经成为 w e b 上数据表示和交换的事实标准。随着互联网的发展，符合x m l 规范的数 据已经大量的存在于当前的信息社会，尤其是数字图书馆、w r e b 服务、电子商 务的飞速发展，使得x m l 数据成为当前的主流数据。如何对x m l 数据进行有 效管理成为当前研究的热点问题【3 】。 在x m l 数据有了形式化的定义后，查询x m l 数据中的有效信息成为 x m l 数据管理的重要主题，而基于x m l 数据的查询成为数据库研究领域的一 个热点问题。x m l 数据有如下几个特点： 1 开放性x m l 技术根据标准规范，允许数据在任何平台上用读取和处 理，通过开放性数据标准进行通信，不必使用专用通信协议。 2 简单性x m l 的严格定义和规则集使人类和机器都能更容易地阅读文 档。x m l 文档语法包含一个非常小的规则集，使开发者能立刻开始工作。x m l 文档建立在基本嵌套结构的一个核心集的基础之上。这些基本结构可以用来代 表复杂的信息集合，而不需要改变结构自身。 3 高效可扩展x m l 在两个意义上是可扩展的。首先，它允许开发者创 建他们自己的d t d ，有效地创建可被用于多种应用的“可扩展的”标志集。其 次，使用几个附加的标准，可以对x m l 进行扩展，这些附加标准可以向核心 的x m l 功能集增加样式、链接和参照的能力。作为一个核心标准，x m l 为可 能产生的其他标准提供了一个坚实的基础。 4 自描述性x m l 数据本身已经包含了数据本身的信息，变现为不同语义 的标记( 例如元素、属性等) 。在所有标记中，元素标记最为重要，一个元素标 记由起止标签组成，起止标签所含的文本就是对应的语义单元。 5 半结构化，即不同于传统的关系数据库，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 数据， 由此解决了查询复杂性的要求。 x m l 查询与传统的查询需求相比具有如下特点： 1 以长路径表达式为查询的核心语句，路径复杂，包含分支路径。 2 嵌套的查询表达，查询表达式中加入编程语言的嵌套和条件判断思想。 3 路径中包含不确定因素，这在之前的查询中从未出现。 4 查询对象和返回结果不确定。 综上所述，来自数据结构和查询需求两方面的问题导致基于关系和面向对 象数据库的查询处理和查询优化技术均不能适应x m l 查询的需求。目前，对 x m l 查询的需求已经成为查询的热点，本文即是对多x m l 数据源集成查询综 合处理过程的探索与研究，以寻求x m l 数据查询的优化处理过程，并分析x m l 查询过程中的特点及查询过程中的关键技术。 x p a t h 【4 】是制定x m l 技术规范标准的w 3 c 推出的x m l 文档寻址语言， x p a t h l 0 在1 9 9 9 年发布，之后就成为w 3 c 的推荐标准，目前已经推出了 x p a t h l 0 的工作草案。x p a t h 的出现使得对x m l 文档的查询有了规范化的标准。 x p a t h 中的基本语法单元是和传统计算机文件系统路径相似的路径位置表达 ( l o c a t i o n p a t he x p r e s s i o n ) 。通过位置路径表达式，我们可以精确的查找到x m l 元素结点的位置。位置路径表达式可以使用绝对路径也可以使用相对路径。 在x p a t h 里有七种不同的节点：元素、属性、文本、名称空间、处理指令、 2 ， 山东大学硕士学位论文 内容、文档( 根) 节点【5 】。x m l 文档是节点树状结构，“树根 称作文档节点( 或 根节点) ，节点之间具有父子、祖孙、兄弟等关系。 节点之间具有的关系是通过轴表示的。轴定义了相对于当前节点的节点集。 x p a t h 中共定义了1 3 种轴。表1 1 中列出了路径表达式中经常使用的轴及其意 义： 表1 1x p a t h 路径表达式中常用轴及意义 表达式注释 l 选取攫节点 | l 选墩支镑中所有符合条侔的节点，不臂该节点位予何处 选取当前节点 选取荜前节点约父节点 选取属性 表1 2 列出了一些常用的路径表达式及其运行的结果： 表2 2x p a t h 路径表达式示例 表达式结果 b o o k s t o r e 选取b o o k s t o r e 元素的所有予节点 i b o o k s t o r e 选敬b o o l 珏t o r 譬元煮的根节点 b o o 缸w r e b o o k 选取b o o k s t o r e 中的所有b o o k 予元素 | b o o k 选墩文辎中的所有b o o k 元素 b 0 0 1 日t o r e i i b o o k选取文挡中所有处于b o o l 暖t o r e 节赢下的b o o k 元素 | | 她曝选取所有肠喀属性 一个路径表达式三个主要组成部分是轴、节点测试和谓词，表示了相关的 上下文节点集。轴表示x _ p a t h 查询进行的顺序；节点测试是选取x p a t h 查询进 行顺序中的一系列节点；谓词是为了对当前节点集进行筛选而定义的条件表达 式，其出现顺序一般是在节点测试后面的方括号里面。谓词可以是x p a t h 表达 式、数字、节点、运算符、逻辑符等的组合。如果一个节点经过谓词运算后结 果为真，则这个节点就被选进定位节点集。在谓词中可以使用多个测试条件， 只要将这些条件根据需要用连接词即a n d 或o r 连接起来即可。 路径表达式在进行节点或结点集选择的时候使用谓词来添加限制条，通过 谓词的使用精确了查询条件。虽然谓词并不是一个x p a t h 表达式必需的内容， 3 山东大学硕士学何论文 但是随着现在x m l 数据规模的不断扩大，用户对查询的精确化要求，所以大 部分x p a t h 表达式中都会包含谓词。表1 3 是典型的x p a t h 表达式中使用谓词 的例子： 表1 3x p a t h 表达式中使用谓词示例 袭达式 结果 选取6 d 出触警节点下的第一个b o o k ，6 口口矗黝甜譬，如戚 1 1 元素 选取b o o k s t o r e 节点下的所有包古 ，如威呦孵，幻荫董脚 3 5 o o 】 p r i c e 元素太子3 5 。的b o o k 元素 选取b o o k x t o r e 笮点下的所有包含 ，幻旃呦憎，6 口嘶娩 3 5 0 0 a t l e 声妇元素大予3 s 。的b o o k 节点下的 触元素 不符合条件的查询结果。正因为谓词操作的重要性决定了其在x m l 查询中的 使用频率，因而对谓词的处理是影响查询时间复杂度的关键一环【6 】。 1 2 国内外研究现状 学术界对x m l 数据查询技术的研究由来己久，有一定的成果，这些成果大大 的提高了对于x m l 数据的查询效率，作为日渐广泛采用的数据形式，从中提取 有用的信息是一个不可回避的研究内容，为了从自描述的、半结构化的x m l 数 据中抽取用户感兴趣的信息，研究人员开发了许多查询描述形式，根据用户定义 的查询模式的不同可以将其概括的分为两大类查询模式：x m lq u e r y 查询模式和 x m l i r ( i n f o r m a t i o nr e t r i e v a l ) 查询模式【7 】。目前存在种类繁多的x m l 代数，其风 格各异，而主要思想皆来自对关系代数的扩展。而对多x m l 数据片段的查询在 现实生活中有很高的实用价值，而如何发掘其中的有效信息进行处理显得 要，而本文中所研究的针对多x m l 文档片段中相似信息的提取就是其中 方面。 x m lq u e r y 查询模式在x m l 数据查询过程中占有极其重要的地位， q u e r y 查询模式首先定义精致的查询模式描述语言，用户借助它来描述自 趣的模式，将用户的模式交由实际的x m l 数据处理系统处理，返回与模 4 山东大学硕士学位论文 配的结果，属于该模式的查询语言包括：x p a t h ，x m l q l t 引，q u i l t t 9 1 ，x q u e r y t l 们。 这些语言有一个共同的特征就是采用了正则路径表达式的形式，其本质是捕捉 x m l 数据单元间的结构关系和内容。 x m l q u e r y 不但要求用户学习相关的语法机制，而且要求用户对x m l 数据内 容及其结构有一定的了解，这就为用户现实生活中的使用增加了难度。x p a t h 查 询语言是x s l t ，x q u e r y l 拘基础，在x p a t h 查询模式中“”表示位于其前、后的 标签对应得节点具有祖孙的关系。而在x m lq u e r y 查询模式规定的f l o w r 中， 新加入了u 玎，f o r ，o r d e rb y ，r e t u r n ，w h e r e 等关键词。由于x m lq u e r y 查询模式是在x p a t h 的基础上发展而来的，所以x m lq u e r y 包含三个方面的主要 内容：线性路径表达式、路径树和分支路径表达式。x m lq u e r y 查询模式的本质 是挖掘x m l 文件中的有效信息( 主要是其结构及内容信息) 。由于对x m l 数据的 查询通常是通过路径表达式来完成的，而查询x m l 数据中的某个元素需要对路 径树进行顺序访问，这就造成了数据查询效率的地下，为了提高数据查询效率， 大量学者做出了很多的研究，提出了一系列的索引方法，主要可分为两类：一， 节点记录类索引方法；二，结构摘要类索引方法。节点记录类索引方法又可分为： 节点序号类索引方法、节点路径类索引方法和混合类索引方法。 为了更好的对x m l 数据进行查询，x m li r 查询模式吸收了传统信心检索 技术的一些优点，对x m lq u e r y 查询模式进行了适当的扩充，最终形成了大约 如下三种方式：x m li r q u e r y ，x m li r k e y w o r d 和x m li r f r a g m e n t 。其中x m l i r q u e r y 对x m lq u e r y 进行了扩充。x m li r k e y w o r d 则将用户的查询请求直 接扩展到相应的x m l 数据片段。x m ll l u f r a g m e n t 则是用户在查询的时候直接 对x m l 片段进行模式描述。 目前存在的主流的关系代数有o r a c l e ，m m 和m s 联合提出的一个x m l 代数标准【1 1 1 ，该标准把x m l 文档看作有向标记图，用五元组g ( v ，e ，a ， r ，o ) 来对x m l 文档进行建模，该代数采用类似关系代数的表达形式。b e l ll a b s 和a r & tl a b s 的m a r y 等人提出的x m l 查询代数 1 2 】，基于简化的x s l t 数据 模型【1 3 】，增加了引用结点，合并了属性和元素结点，其主要思想来源于嵌套 关系代数。这两种关系代数还仅停留在逻辑层次，没有考虑物理代数和查询优 化策略，其长处则在于具有丰富的语义，且与查询语言有密切的转换关系。w 3 c 5 山东大学硕十学何论文 于2 0 0 1 年公布了x m l 查询代数标准x q u e r y l 0f o r m a ls e m a n t i c s ，用于规范查 询语言语义。而o r i e n t x a 是一种优化了的，从关系代数延伸而来的一种新型查 询代数表示，其继承传统的关系代数表示方法，极大地促进了x m l 查询代数 的发展。 1 3 本文的主要贡献 1 3 1x p a t h 路径表达式的优化 x p a t h 表示的是一种路径语言，其目的是对x m l 文档内容进行定位，将 x m l 文档作为一个树来进行处理，是对文档内容的一种抽象。x p a t h 主要定义 了两个部分的内容：一部分是类似于文件系统的目录形式的路径表达式方法， 另一部分是一组名为x p a t h 核心库的基本函数。 x p a t h 路径表达式在许多w 3 c 的标准和建议中都占有至关重要的地位，比 如x s l 转换框架x s l t 以及当前流行的x m l 查询语言x q u e r y 。正因为x p a t h 的基础作用，所以在本节中我们试图探索一种将x m l 查询路径最小化的优化 方法。本章中，我们设计了二种对复杂的、嵌套的x m l 查询表达式进行简化 的方法。本文的方法是将x m l 表示的数据划分为路径等价类的形式，我们首 先将x m l 数据可能出现的路径划分为不同的路径等价类，然后根据元素之间 的关系得到元素关系表并在此基础上形成一种树x t r e e 和图x g r a p h ，并在此基 础上对其进行优化处理，得出优化处理算法。最后，通过实验对我们的方法进 行验证，实验结果显示本章的方法具有一定的可行性。 我们将这种对路径表达式进行最优化的过程称之为路径最优化过程，并将 该方法命名为m i n p a t h 方法。 1 3 2 基于o r l e n t x a 的x 1 v i l 代数优化 随着x m l 数据使用越来越广泛，对x m l 数据的查询提出了越来越高的要求。 前期的研究主要集中在x p a t h 的查询处理上。x p a t h 相对比较简单，表达能力有限， 比如，不能表示连接操作等。由此，人们提出了基于x m l 代数的处理方法，这 种处理方法类似于关系代数的代数体系。每一个代数操作符的输入都是一个或者 6 山东大学硕士学位论文 多个x m l 树集合，输出也是一个x m l 树集合。 本部分的内容是基于当前流行的x m l 查询代数o r i e n t x a ，根据等价变化的原 则对其代数表达方法进行优化处理，有利于对x m l 数据查询的优化。 1 3 3 多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 文档结点属性和有向边属性。结点属性又分为两类：一，名称；二， 数据类型和系数。将有向边属性分为四种类型：一，一般化( g e n e r a l i z a t i o n ) ； 二，特殊化( s p e c i a l i z a t i o n ) ；三，聚集( a g g r e g a t i o n ) ；四，联合( a g g r e g a t i o n ) 。 并综合考虑结点相似度与边相似度，通过结点相似与边相似相结合的思想，整 理出一个简单的算法来实现相似度的计算。 、 1 4 本文的组织结构 本文是按照下面的结构组织的： 第一章绪论部分介绍了本文的一些预备知识，分析了本文研究涉及的相关 领域国内外的研究现状；并介绍了本文所做工作的主要贡献及创新点，最后介 绍了本文的组织结构。 第二章的内容主要是对x p a t h 路径表达式的最优化处理过程。在本节中我们 试图探索一种将x m l 查询路径最优化的方法，以达到简化对x m l 数据的查询， 从而提高查询的速度。 第三章介绍了当前流行的x m l 查询代数o r i e n t x a ，并在此基础上根据等价 变换的方法，研究了对代数表达式的优化处理方法。 第四章是介绍了如何对多x m l 文档片段查询中相似信息进行获取的一种方 法，建立标签有向树模型，利用结点标签与边标签计算不同x m l 文档片段中 元素之间的相似度，从而找到匹配关系。 7 8 山东大学硕十学位论文 第二章x p a t h 路径表达式的最优化方法 x p a t h 表示的是一种路径语言，其目的是对x m l 文档内容进行定位，将 x m l 文档作为一个树来进行处理，是对文档内容的一种抽象。x p a t h 主要定义 了两个部分的内容：一部分是类似于文件系统的目录形式的路径表达式方法， 另部分是一组名为x p a t h 核心库的基本函数。 x p a t h 路径表达式在许多w 3 c 的标准和建议中都占有至关重要的地位，比 如x s l 转换框架x s l t 以及当前流行的x m l 查询语言x q u e r y 。正因为x p a t h 的基础作用，所以在本节中我们试图探索一种将x m l 查询路径最小化的优化 方法。本章中，我们设计了一种对复杂的、嵌套的x m l 查询表达式进行简化 的方法。本文的方法是将x m l 表示的数据划分为路径等价类的形式，我们首 先将x m l 数据可能出现的路径划分为不同的路径等价类，然后根据元素之间 的关系得到元素关系表并在此基础上形成一种树x t r e e 和图x g r a p h ，并在此基 础上对其进行优化处理，得出优化处理算法。最后，通过实验对我们的方法进 行验证，实验结果显示本章的方法具有一定的可行性。 我们将这种对路径表达式进行最优化的过程称之为路径最优化过程，并将 该方法命名为m i n p a t h 方法。 2 1 背景与相关概念 随着x s l t 的发展与x q u e r y 技术的进一步完善，x p a t h 作为两种技术的基 础路径表达方式，正发挥着越来越重要的作用。x m l 数据首先被定义为一种路 径树的结构，然后我们可以在此基础上进行简单并且灵活的查询操作。我们在 进行查询操作的时候，总会想找出一条最优化的查询路径树来对其进行查询。 x m l 数据表示可以是一种非常复杂的结构，包含很多的分支以及嵌套关系。 x m l 查询的优化概括而言可以分为两个方面的内容：逻辑优化和物理优化。 传统意义的逻辑优化是指将原始的查询表达式转化为等价并且高效的形式，而 该部分的主要内容是对关系代数操作顺序进行调整，以提高操作执行的效率。 而x m l 逻辑优化的主要目的是将x m l 所形成的查询树规模进行缩减，以得到 一个最小规模的查询树。物理优化的核心思想是对x m l 查询片段的执行顺序 9 【j j 东大学硕十学位论文 进行选择，以得出一条最优的查询片段执行顺序。 因为x p a t h 路径表达式有如此复杂的结构，所以我们设计了基于路径表达 式的优化方法。由于在x m l 数据的存储以及获取上存在定的局限性，