（农业机械化工程专业论文）xml查询处理结构中的一种逻辑优化算法.pdf

摘要 x m l 查询处理结构中的 一种逻辑优化算法 农业机械化工程专业硕士研究生冯林 指导教师熊海灵副教授 摘要 随着x m l 在信息管理、电子商务、个性化出版、移动通信、网络教育、电子文档交换 等诸多领域中的广泛的应用，它已经开始成为数据描述和交换的事实上的标准，越来越多的 数据开始采用x 】l 进行描述、存储、交换和表示。然而由于x m l 数据的半结构化特性以及 x m l 数据所特有的路径表达的查询方式不同于现有的关系数据库查询，使得利用关系数据库 系统对x m l 数据的管理功能受到极大限制。现在互联网上已经存在大量以文件形式存放的 x m l 数据，这种方法虽然简单、实用，但是查询能力低，不能满足复杂条件的查询，更谈不 上查询优化。因此，如何高效准确地完成对x m l 数据的查询还存在着许多尚未解决的问题。 查询优化是数据库技术中重要的研究问题，是实现高效查询的关键性因素。查询语言首 先被转换成为一种内部表达形式( 通常是某种代数，如关系代数、x l l 代数等) 。根据变换 规则得到等价表达式，计算不同形式的表达式的执行代价，然后选择一个代价最小的执行方 案，这就是查询处理过程。对查询处理过程的研究是实现查询优化的关键，而查询处理过程 中最重要的是逻辑优化阶段。因此，本文针对咀。查询处理结构的逻辑优化阶段，研究了 这一阶段相应的策略与算法。 本文介绍了l 查询的查询处理结构，分析了逻辑优化的常规策略，重点研究了如何 针对路径表达式进行优化。路径表达式是x m l 数据查询语言的核心部分，但是目前针对路 径表达式本身进行优化的研究却相对较少。本文通过对相关定理的推理，得出了一种逻辑优 化的新策略，即路径缩短优化策略，给出了算法的实现。同时用一般的外延连接算法和这种 路径缩短算法进行比较，最后用相应的评测基准测试了该算法。 本文研究的重点主要包括以下几个方面： ( 1 ) 研究了l 的查询处理结构，特别是逻辑优化阶段路径表达式的查询与分解的方 法。 ( 2 ) 相关定理的推理和一种新的逻辑优化算法的提出。 ( 3 ) 对评测标准的介绍，并且用这些标准来测试路径缩短算法，最后对测试结果进行了 评价。 两南大学硕士学位论文 实验的结果表明，路径缩短算法相对外延连接算法不仅提高了x m l 的查询效率而且具 有更好的可扩展性，适用于大规模数据集的连接运算。 关键词：) ( m l 查询处理逻辑优化路径表达式外延连接 玎 a b 咖c l a b s t r a c t w i me x t e r i s i v e a p p l i 锄c eo fx m lt om a n yf i e i d ss u c h 舔h l f o 肺a t i m 纽a g e m 韶t ， e - b u s i i l e s s ，p e r s l d n a l i z ep u b l i c a t i o n ，m o b i l ec o m m u n i c a t i o n ，o i l l i n ee d u c a t i o na n de 1 e c 仃o n i cd a t a i i l t e r c h 锄g e ，x m lh a sb e c o m et l l ed e f - a c t 0s t a n d a r df o rd a t ad e s c r i p t i o n 锄de x c h 孤g e ，m o r ea n d m o r ei i l f o n l l l a t i o ni 啦b e e nd e s c r i b e d ，s t o r e d ，e x c h a n g e da n dp r e n t e db yx m l h o w e v e r t 量l e q u e 巧o fs 咖s 劬c t u r e - b 舔e dx m ld a t a i sd i 成r e n t舶mm er e l a t i o n a ld a t a b a s eq u e 哆 a c c o r d i n g 】xt 1 1 ee 硒c i e n c yo fq u e 拶i sa 彘c t e dal o t c u r 陀n t l y l o t so fx m l d a t ai ss t o r e di i lt 1 1 c f i l ef o 册o nt h ei n t 锄e t a l t i l o u g l lm i sm e t 1 0 di sv e 叫s i m p l e ，t l l eq u e d ri si n e m c i e n t ，a n dc a nn o t s a t i s f yt h eq u e 叫o f c o m p i i c a t e ds n l l c t i l r e s o ，t l l e 他a 陀s om 锄yp r o b i e m si nq u e r y i i l go f x m l d a t a e 伍c i e n t l y 觚da c c u r a t e l y q u e r y0 p t i l l l i z a t i o ni s 觚i m i 炳t a n ti s 她ei l ld a t ：a b 觞e ，i ti st l l ek e ym e m o do fq u e r y i i l g e f i i c i e i l t ly f i r s t l y q u e 巧l 卸g u a g ei sc h 卸g e d 访t o 柚i i l i l e re x p r e s s i o n ( u s u a l l yi sq u e d ，a l g e b m s u c h 弱r e l a t i o n a la l g e b r ao rx m l a l g e b r a ) ，g e tm ee q u i v a l e n te x p r e s s i o n sb yr u l e ，t h e nc 伽叩u t e t h ec o s to fd i g e r e n te x p f e s s i o m 勰dc h 0 0 s et 1 1 el o w e s to n e t h i si sq u e 珂p r o c e s s i n gt h ef e s e a f c h 0 n q u e r yp r o c e s s ：i 1 1 9i sm ek e yt oq u e r y 叩t i i i l i z a t i o n ，觚do n eo f t l l em o s ti m p o n a n tt l l i n g si i lq u 吖 p r o c e s s i n gi s1 0 每c a l 叩t i i 】 1 i z a t i o n s o ，i i lt l i sp a p e r w er e s e a r c h o nl o g i c a lo p t i m j z a t i o n i i lt h i s p a p 屺r w em k es o m er e s e a r c h e s o n 廿1 ex m l q u e 叮s n u c t u r e 狮da i l a l ) r z e 吐l e o p t i m i z a t i o np o l i c yi i i1 0 舀c a lo p t i m i z a t i o n h o wt 0o p t i m i z et 圮p 砒e x p r e 豁i o ni s d i s c u s s e d p 五i 拢l r i l y i l lm i sp a p e r i a t l le x p r e s s i o ni so n eo ft 1 1 ec o r ec o m p o n e n t so fm o s tx m lq u e 哆 l a n g u a g e s h o w e v e r t l l e 他a r cf e wr e a r c h e so n 吐l ei s s u eo fp a me x p r e s s i o n 叩t i i i l i z a t i o n 1 1 1t l l i s p a p e r ，ak i l l do fp a me x p t i e s s i o no p t 砌z i n gp 血c i p l ei sp r o p o s e db yi l l a t i o n ，n a m e dp a d ls h o r l e i l i n g m i ：n 1 0 d w bc o 玎叩a 他t 1 1 ep a ms h o r t e i l i i l g 锄de x t e n dj o 证，a i l dt l l t e s tm e mw i mt i 坞s t 觚d a f do f e v a l u a t 醯g t h er e a r c hi nm i sp a p c ri s 笛f o l l o w s ： ( 1 ) w ea m l y z et l 圮x m lq u e 叮p r o c e 豁i i i g 柚d 他s e a r c h t l l e 叩t i i l l i z a t i o n 叫i c yi nl o g i c a l o p t i m i z a t i o n ( 2 ) an e wl o 昏c a lo p t i i i l i z a t i 锄p 血c i p l ei sp p o 辩db yi l l a t i 1 1 i i sn e wl o g i c a lo p t i i l l i z a t i 蚴 呻l c i p l ei sp a t hs h o n e n m g ( 3 ) 1 1 1 臼吣d u c em es t a l l d 乏们o fe v a l u a t ：i i l g t c s t 锄de v a l u a t ep a t hs h o r 沧i i i n g 锄a l y z et h e e x p 甜m e n t a lr e s u l t w ec o l l 】p a r ep a ms h 嘣e i l i n gw i me x 劬tj o i i l ，t l l ee 平施姗t a lr e s u l ts h o wt 1 1 a tm ex m l q u e 叮e m c i e n c yi sh n p r o v e db yp a t hs h o r t e n 访g 觚dp a t l ls h o n e n i n gi s n m c hb e n e ri i l 两南大学硕士学位论文 e x t e n d i b i l i t yt h a ne x t e n tj o i n s o ，w ec a ns a yt l l a tp a ms h o n e n i n gc a nb eu s e dt oj o i no p e r a t i o no f l 锄苫ed a t as e t k e y w o r d s ：x m lq u e r yp r o c e s s i n g p a t he x p r e s s i o n i v l 0 酉c a l0 p t 确i z a t i o n e x t c l l tj o i n 独创性声明 学位论文题目：型垦查询处堡缱掏史鲍二盘堡塑盆丝篡洼 本人提交的学位论文是在导师指导下进行的研究工作及取得的 研究成果。论文中引用他人已经发表或出版过的研究成果，文中已加 了标注。 学位论文作者：7 豸旆k签字日期：多娟年占月8 日 学位论文版权使用授权书 本学位论文作者完全了解西南大学有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅。本人授权西南大学研究生部可以将学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书，本论文：口不保密， 口保密期限至年月止) 学位论文作者签名：冯林 导师始荔炙 签字日期：矽。8 年占月 8 日 签字日期：时年厂月驴日 绪论 第1 章绪论 1 1 研究目的和意义 随着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 查询优化问题具有十分重要的意义。 而对x m l 查询处理过程的研究是x m l 查询优化的最重要的内容。与关系数据库的查询处 理结构类似，x m l 查询处理结构可以分为4 个阶段，其中最为重要的阶段是逻辑优化阶段，即： 规范和约简内部表达式。因此，x m l 查询处理的逻辑优化阶段的方法和策略研究十分重要， 是实现x m l 查询优化的关键。 在接下来的研究过程中，我们将针对订l 查询处理的逻辑优化阶段，主要研究逻辑优化 阶段的策略和算法，我们期望达到以下目的： ( 1 ) 对路径表达式进行快速的分解。 ( 2 ) 找到一种效率较高的路径表达式转换方法。 ( 3 ) 提出一种针对路径表达式本身的优化算法一路径缩短优化算法。 总之，研究的主要目的就是力图用简洁的查询语句高效准确的进行x m l 数据的查询。 1 2 研究的主要内容 如何进行高效准确的l 查询是x m l 数据管理的一项极为重要的内容，是数据库技术的 重要问题。虽然路径表达式是x m l 数据查询语言的核心部分，但是目前针对路径表达式本身 进行优化的研究却相对较少，因此本文正是基于这样的背景下，对逻辑优化阶段的路径表达 式进行研究，提出了一种针对路径表达式的优化策略。本文研究的主要内容如下： ( 1 ) 研究了x m l 查询处理结构，重点研究了逻辑优化阶段的一些常规策略和算法。 ( 2 ) 研究了一种常规的逻辑优化算法，即普通的外延连接算法。分析了外延连接算法如 何将查询分解为若干个路径步以及路径查询转换的基本步骤。 ( 3 ) 通过逻辑推理，得到了路径表达式查询的路径缩短策略和算法。 ( 4 ) 研究了常用的x m l 查询的性能测试标准，用这些性能测试标准测评了新提出的逻辑 优化算法。 1 3 研究的技术路线 就整个研究过程，首先要确定研究的目的，接着分析了舭查询处理结构，并且探讨了 西南大学硕士学位论文 逻辑优化阶段的一些方法和策略；然后研究了一种常规的逻辑优化算法即外延连接算法，着 重研究了路径表达式的分解与转换；下一步，通过逻辑推理得到了路径缩短优化策略，提出 了路径缩短优化原理和算法；然后，对路径缩短优化算法在自然数据集和人工生成的数据集 上进行了测试，并且通过和外延连接算法进行比较来分析这种新的逻辑优化算法：最后得出 结论，并且总结了研究中的问题和不足，为下一步的研究提供参考。 整个研究过程用图1 1 来表示： 确定研究动机与目的 上 i 逻辑优化阶段相关技术探讨与研究 上 i 研究外延连接算法和路径表达式的分解与转换 上 对相关定理逻辑推理 上 提出路径缩短优化策略和算法实现 上 对新算法进行测评 上 评价结果分析 上 总结与展望 1 4 论文的组织结构 图1 1 论文研究过程图 本文共分6 章，各章的主要内容如下： 第l 章说明了本文的研究目的和意义，接着介绍了本文研究的主要内容和研究相关的技术 路线。 第2 章是文献综述部分，介绍了x m l 查询处理结构，重点研究了查询处理结构的逻辑优化 阶段相应的策略与算法，为后面的研究奠定理论基础。 第3 章介2 “了一种常规的逻辑优化算法，即普通的外延连接算法，并且分析了路径表达式 的分解与转换。 2 绪论 第4 章提出了一种新的逻辑优化策略和它的算法实现，即路径缩短优化算法。 第5 章研究了x m l 查询性能评价标准，把路径缩短优化算法与一般的外延连接算法进行比 较，并且对路径缩短优化算法进行评价分析。 第6 章对全文的工作做了回顾与总结，并对下一步工作进行了展望。 3 西南大学硕士学位论文 第2 章x m l 查询处理结构及常规逻辑优化算法 x m l ( e x 吣i b l e1 1 1 a 出u pl 锄g t l a g e ) 【l 】称为可扩展标记语言，是一种可以用来创建自己标 记的标记语言。x m l 数据作为一种数据表现和交换的格式，正在赢得巨大的成功，特别是在 w w w 上被广泛接受和采用。随着x m l 的不断普及，x m l 数据的管理和查询问题也越来越 引起人们的重视【2 3 】。尽管l 数据表现形式灵活，可以描述：l 常复杂的结构，但其本质仍 然是树状的模型。树中的每个节点对应于一个元素，树中的边描述了元素之间的父子关系。 针对这种树状数据的查询，学者们已经提出了多种x m l 查询语言，例如x p a m 【4 】， x q u e 习等。这些查询语言尽管各有特点，但它们都将路径表达式作为重要的组成部分。为 了高效地计算路径表达式，人们提出了一种查询处理策略。其主要思想是将一个复杂的查询 模式分解成为若干个二元基本结构关系的集合，首先计算二元基本结构关系，然后将基本的 匹配结果组合起来。在这种处理策略下，基本结构关系( 包括父子关系和祖先后代关系) 的 计算成为查询处理的关键操作，这种操作被称为结构连接( 或包含连接) 。 x m l 的诞生是由于人们发现h t m l 已经不够用了，相对于h t m l 来说x 】l 有着许多 显著的优点，目前x m l 已经成为网络上信息描述和信息交换的标准。早期的x m l 数据以文 档方式存储，以关键字查询等信息检索手段查询，简单、易用。由于缺乏系统的存储和查询 机制的支持，造成查询能力低，不能满足复杂条件的查询，更谈不上查询优化。一些现有的 商业数据库系统扩充了处理x m l 数据的功能，利用现有数据库成熟的技术，把x m l 查询要 求转变为数据库查询表达，由查询优化器优化查询表达并执行，再将查询的结果转变为x m l 数据。这种方法在一定程度上解决了查询复杂性韵要求，但多级转换带来的问题是效率的降 低和查询语义的混淆。因此对x 】l 的查询处理研究正逐渐成为热点。 2 1x m l 查询处理的原理 本节探讨了x m l 数据的查询特点和x m l 查询处理结构两方面的问题。 2 1 1x m l 查询的特点 与传统的查询需求相比，l 查询具有如下特点： ( 1 ) 以长路径表达式为查询的核心语句，路径复杂，包含分支路径； ( 2 ) 嵌套的查淘表达，查询表达式中加入编程语言的嵌套和条件判断思想： ( 3 ) 路径中包含不确定因素； ( 4 ) 查询对象羊i l 返回结果类型不确定。 面向对象数据席已有一些处理复杂长路径表达式的经验，但无法处理l 查询中的路径 表达式中的不确定情况；关系数据库中已有很多处理嵌套查询的方法，但对掺杂编程语言风 格的x m l 查询语言却难以适应。因此，基于关系和面向对象数据库的查询处理和查询优化技 4 x m l 查询处理结构及常规逻辑优化算法 术均不能适应x m l 查询的需要。 2 1 2x m l 查询处理结构 与传统的关系数据库系统的查询处理结构类似，我们可以将x m l 查询处理分为4 个大的阶 段，如图2 1 所示。左侧方框为使用的相关技术或方法：右侧方框表示查询处理步骤。 查询代数 l 查询解析 上 转换规则逻辑优化 上 i 代价模型和启发式规则 物理优化 上 执行算法 查询执行 图2 1 查询处理过程 第1 阶段查询解析，将查询转换为某种内部表达方式，以便于机器处理，并为下一步的优 化过程铺平道路。这种内部表达方式通常以一种抽象语法树或者查询树的形式出现。以传统 数据库为基础的查询引擎的做法是转换成关系代数，然后由关系数据库优化器完成剩下的优 化工作。而n a t i v e 的数据库系统则采用不同的x m l 代数系统。 第2 阶段逻辑优化，利用模式信息，规范和简化内部表达式。在这一阶段中，系统不考虑 实际数据的值和数据的存储情况。同一查询请求，可以转换成不同的等价表达方式，其中有 一些比原有查询更高效。为了进行这种转换，优化器需要一些转换规则。 第3 阶段物理优化，利用代价模型和统计信息计算不同表达式、不同算法的执行代价，选 择最低代价的查询计划。在这一阶段中，需要解决两个问题：确定表达式执行顺序和决定每 步操作的具体算法。对于x m l 查询树而言，首先需要将查询表达式分解为可执行的片断，然 后选择合适的执行顺序和执行算法并执行中间结果集的大小是决定执行策略是否高效的关 键因素，与实际的数据分布密切相关。综合考虑数据的存储、索引和数据值的分布情况，准 确地估计复杂路径选择性是其中的难点。对于一个给定的执行策略，通常会有多个可能的执 行算法，产生所有的执行算法的组合造成选择本身的代价过大。因此，会有一些启发式规则 用来控制其空间规模，并采用一些空间搜索技术加速选择的过程。 第4 阶段查询执行，根据物理优化确定的执行策略和算法，访问数据并得到查询结果。由 于x m l 数据复杂和变化的结构，需要高效的数据访问算法。 5 两南大学硕士学位论文 2 2x m l 查询处理中逻辑优化的常规策略分析 在传统数据库技术中，逻辑优化是指通过一系列转换规则，将原始的查询表达式转换为 等价且更高效的形式，x m l 代数的核心是由路径表达式转换的查询树，查询效率依赖于查询 树的规模。因此，路径表达式和查询树的最小化是x m l 逻辑优化研究的重点，但是目前对路 径表达式的研究相对较少。我们首先介绍路径表达式的分解和最小化问题，接着介绍查询树 的最小化策略以及路径表达式的选择性分析，最后引入x m l 外延和x m l 限定外延的概念，为 后面的研究提供理论基础。 2 2 1 路径表达式查询与分解 x m l 文档可以被抽象成若干路径实例的集合，每一个数据节点都相应地对应于一个路径 实例。路径表达式查询用来匹配x m l 文档的路径实例，从而得到符合条件的元素实例。路径 查询可以由一个五元组q = ( g 。，t d ，s e ，p e 尽s ) 来表示，其中g 。和t d 是查询文档模式及文档数据， p e 是查询路径表达式，s e 是查询的初始元素集，r s 则是查询结果集。由于s e 是p e 的起始点， 因此p e 肯定是一个相对路径，则出现在p e 中的所有路径连接符都只表示元素之间的联系。用 户的原始查询形式可以由s e + p e 得到。 路径表达式分解是根据一定的转换规则，把用查询语句表达的、复杂的、不确定的路径 表达式转换为简单的、明确的、系统可识别的方式，如x m l 代数。路径表达式分解是查询转 换的难点，也是查询优化的重要一步，是代价估计的前提条件。根据不同的规则，路径表达 式可能分解为不同的等价形式，其中有的代价高，有的代价低，形成代价空间路径分解的 原则是能够产生有限的代价空间，有利于利用分解的结果搜索代价最小的执行方案。 在路径分解时，有两种不同的思路：一种思路是把路径细分为两两的祖先后代或父子对， 如i o r e ，x i s s 【6 j 等。这种分解算法简单，可利用数据物理存储信息，分解的结果容易转换为结 构连接运算或者运用系统提供的各种索引。如果查询语句中出现通配符( 如，? ，) ，可以 利用索引直接定位数据，也可以借助模式信息确定通配符所代表的各种可能情况扩展路径。 经过分解，路径表达式转换为连接、投影、选择、导航等不同的代数运算：另一种思路1 7 】是将 复杂路径表达式用树的方式表示：从根开始，在树中搜索最长的确定路径( 不含或) 称为 次分解，其路径构成树的一个子串。以这个点为起点，用上述原则再分解路径，得到确定 路径( 子串) 的集合，称为一个最小分解。在x m l 文档的查询中，确定路径的查询是相对容 易的，而不确定路径的查询是比较困难的，尤其是在没有模式或索引的情况下，可能要将中 间结果合并才能得到全部的结果。将复杂的、不确定的路径分解为确定的、简单的路径处理。 这种分解方法在没有模式信息的情况下处理不确定路径具有一定的优势。 2 2 2 查询树的最小化 从层次上看，查询树的最小化可分为两个层次：语法层次和语义层次。语法层次的优化 6 x m l 查询处理结构及常规逻辑优化算法 是指不依靠任何其他信息，独立地分析查询表达式中分支或结点间的逻辑包含关系，删除冗 余部分；语义层次的优化是指通过数据库提供的模式信息，如d t d ，x m ls c h e m a 等，或者语 义包含、结构包含等完整性约束，查找查询表达式中的冗余分支或结点。下面的例子进一步 说明二者之间的区别。若有如下的x q u e 拶查询表达式： f o r $ ai nr e f e r e n c e b 0 0 k ， f o r $ bi i l $ 以u t l l o r $ ci i l $ a a u t l l o r n 锄e ，$ di i i $ “孤n l 饼屉m a i l w h e 咒$ ba n d 钲柚d $ d r e t l l m $ a 其p a t t e n l1 r e e ( 以下简称p t q ) 如图2 2 ( a ) 所示，其中，实心圆为查询返回结点。若数据 满足$ c ，同时必然满足$ b ，$ b 分支对查询返回结果没有任何影响，是冗余结点。我们称这种 冗余结点为语法冗余结点。经语法优化后的p 1 q 如图2 2 ( b ) 所示。若从模式可知任一个a u m o r 均有n 锄e ，则v 6 为冗余结点。我们称这种冗余结点为语义冗余结点。经语义优化后的p t q 如 图2 2 ( c ) 所示 图2 2 语法优化和语义优化 您 h h 下面我们首先介绍语法优化的研究现状。 对p t q 语法优化问题基于对路径等价性问题1j 的研究。最早提出x p a m 最小化的w 的d f l 刁 指出：一个x p 撕可以表示为合取范式，对x p a t l l 等价性检查的复杂度等价于对合取范式的等价 性检查。而这已经证明是一个n p 完全问题。如果对x p a t h 路径表达式的复杂程度加以一定的限 制，x p a t h 最小化问题的复杂度可以达到多项式级。目前已经提出了对不同类型的p t q 的最小 化方法。 ( 1 ) 简单p 1 r q ，【】，) 文献【1 2 】中提出了对只包含 ，【】，) 的简单路径的最小化方法。其思想为：设原始p 1 q 为p ， 在所有与之等价的p t q 中找到q ，使得q 中的结点个数i n q l 最小，则q 为p 的最小化p 1 q 。 这种方法的关键是通过对包含映射( c o n t a i 姗e n tm a p p i n g ) 的判断完成p t q 的等价性判断。 不存在祖先后代关系( ) 的简单p t q 的最小化p t q 为其子树。查找等价p 1 q 的范围限制在其 7 咐曩 ， 谴 融 一 q，上，；6，16 西南大学硕士学位论义 子树的范围内，是保证最小化算法的复杂度为多项式级的关键因素。文献【1 3 】中给出了复杂性 证明。 ( 2 ) p t q 【 ) 文献【1 4 】提出了p t q 的c i m ( c o f l s 舰妇i n d e p e n d e n tr n i n i i n i z a t i o n ) 算法。与文献【1 3 1 相同， 其算法的基础也是包含映射。路径中缺少“p 的p t q 的最小化问题，仍旧可以在其子树范围 内解决。c i m 算法的思想为：从叶结点开始，判断结点在p t q 中是否冗余；若某结点是冗余结 点，则删除这个结点，继续处理其他叶结点直到所有叶结点判断完毕；若p t q 中结点个数为n ， 则c i m 算法的最大复杂度为o ( n 4 ) 。 文献【1 5 】提出了一种最大复杂度为o ( 1 1 2 ) 的改进算法，通过结点间的二元关系s i m u l a t i o n 判 断冗余性。改进的c i m 算法与c i m 算法最大的不同点在于：前者只关心后代结点之间是否相同； 而后者还要关心祖先结点之间是否相同。改进的c i m 算法通过正向遍历查找冗余结点，如果某 结点的一个儿子结点与另外儿子结点之间有s i l i l u l a t i o n 关系，则这个儿子结点为冗余结点。这 样，在一次遍历可以对多个结点的冗余性进行判断，从而提高了p t q 最小化的效率。 ( 3 ) p t q ，【】，) 与限制条件下p t q 所不同的是，普遍意义下的p t q 在语法优化时遇到的一个关键问题是： 最小化p t q 并非原始p t q 的子树，而是由以原始p t q 的根为根，连接多个p t q 子树构成的p t q 。 其中每个子树均为原始子树的最小化部分。这个问题也是导致其复杂度上升的关键。 文献【1 6 】给出普遍意义下的p t q 最小化算法。其算法思想是：递归地在原始p t q 的子树中 查找最小予树并连接它们，在这个过程中冗余的分支被删除了。文献【1 7 证明其算法的复杂度 为n p 完全，并指出：在对p t q 的分支个数加以一定限制的情况下，改进的算法复杂度可以达 到多项式级。但我们有理由相信，这样的改进意义并不大，因为这要求用户在写查询语句时 必须注意查询的分支情况，否则将导致某些查询无法优化。 目前，语法优化都以判断结点之间的包含映射关系为基础，分析路径等价性。在查询树 中不断地修剪冗余的分支或结点，达到减少查询树规模的目的。普遍意义的p t q 语法优化是一 个n p 完全问题，研究者通过对p t q 复杂度加以一定限制，提出了多种高效的算法。语法优化 不涉及x m l 模式信息，可以利用模式信息进一步简化p 1 q ，这种优化称为语义优化。 接着介绍语义优化的研究现状。 晟早提出语义优化的是关系数据库系统，利用表格属性值之间的约束关系把查询表达式 转换为等价但更高效的形式。c h a s e 方法【1 8 1 是其中的代表。其思想为：把完整性约束作为冗余 条件插入到查询表达式中，与已存在的冗余操作合并，使得组合后的条件符合某些事先定义 女r 的等价转换规则，利用这些等价转换规则重写查询表达式以达到优化的目的。这是一个巧 妙的先膨胀再收缩的方法。 但是，应用c h a s e 方法于x m l 查询的语义优化时面临下述严重的挑战： ( 1 ) 数据结构的变化。与平面表结构不同，x m l 数据具有嵌套性。原有的主键、外键等 8 x m l 查询处理结构及常规逻辑优化算法 完整性约束不能表达结构上的嵌套关系，缺乏匹配的转换规则。 ( 2 ) 数据类型的变化。关系模型中，数据有严格的类型；而在x m l 半结构化模型中，数 据没有严格的类型约束，同名的结点可以出现在不同的位置，可以有不同的子结点。传统的 转换规则的应用方法不适应这种情况，引发的问题就是产生递归的转换，导致路径的无限增 长。 ( 3 ) 查询语句的复杂性。s q l 语句清晰、明确，关系代数操作均为输入参数明确的一元 或二元运算。而x m l 查询语句中包含，等不确定因素，并以包含多个分支长路径为特点， 原有的转换规则不适应于x m l 语义优化。 基于上述挑战，一些研究者提出改进的c h 弱e 方法，而另一些研究者则从对图分析处理的 角度出发，研究x m l 查询的语义优化问题。 w 6 0 d 等人【1 0 】最早将c h a 方法引入简单x p a m 语义优化。文献【l o 】在d t d 上定义了3 种结构 约束关系，分别为儿子约束、父亲约束和兄弟约束。若某个查询树中结点n 为上述约束关系中 的主体，且其约束的结点不在查询树中，则在查询树中相应位置加入客体结点。当所有约束 关系应用完毕，再用语法优化的方法对查询树进行修剪，得到最小化查询树。为了讨论简单 起见，文献【1 9 】中方法只适用于不包含“”和“”的简单路径，其复杂度为多项式级。 文献 2 0 】则认为，x m l 数据中的结构完整性约束可用儿子约束、后代约束和类型约束概括。 为了得到正确的优化结果，他们对c l m e 方法做了3 个方面的改进：首先。假设约束集合是闭包 的；其次，为了保证优化能够完成，约束条件只应用于p t q 中原有结点，如果某结点是由于应 用某约束条件加入p t q 的，则不对其应用任何约束条件；最后，由于应用约束条件加入的结点 是冗余的，因此，需要在算法结束时删除这些临时结点。a c i m 算法分为3 个步骤：首先，应 用约束集合中的约束条件放大p 1 q ；然后，应用c i m 算法语法删除冗余结点，在删除时保证不 检查被加入临时结点的冗余性；最后，删除所有在第一步中加入的临时结点。若p t q 中结点个 数为n ，则a c i m 算法的最坏计算复杂度为o ( n 6 ) 。一些冗余结点是容易识别的，如果提前删除 这些容易识别的冗余结点然后再应用a c i m 算法，可以有效地提高优化的效率。算法c d m 在 p t q 中遍历地查找并删除这样的冗余结点，其计算复杂度为o ( 1 1 2 ) 。实验证明，在使用a c i m 之 前使用c d m ，比直接应用a c l m 可更为有效地节省时间。 文献【2 1 】在文献【2 0 】的基础上扩充了子类约束，并利用语法优化中的t p q s i 删l a t i o n 和 t p q m i n i i n i z a t i o n 改进了a c i m 算法，使计算复杂度达到o ( n 4 ) 。 文献【2 2 】提出了一种基丁模式的x p a m 路径表达式的语义优化方法。其思想是：把订l 文 档模式( d t d ) 划分为若干个路径等价类，每个类中的路径等价；将x p a t h 转换为由简单路径 构成的合取范式形式，利用路径等价类中的最短路径代替表达式中的路径。通过这种方法， 可以实现3 个方面的优化：首先，删除冗余的谓词条件；其次简化路径；最后，判断表达式的 条件是否满足。如果某个分支的条件不满足模式中的约束关系，则整个表达式的查询结果为 空。整个优化过程分为4 部分：分解、扩展、优化和重构。在分解过程中，x p a m 表达式被转 9 两南大学硕士学位论文 换为合取树( x c t ) ：重构x p a t h 表达式则将优化的x c t 转换为，a t h 路径表达式。 改进的c h a s e 方法具有以下的优点：语法优化与语义优化相结合，优化过程无须对p t q 进 行转换。问题是难以保证彻底的优化。基于d t d 的优化方法的优点是：不但能够删除冗余分 支，还能够缩短路径长度和直接判断路径是否满足。问题主要是：首先，需要对p t q 进行转换， 占用大量优化时间；其次，需要不确定路径的确定化。 2 2 3 路径表达式选择性分析 复杂路径表达式选择性分析就是用来估计结果集规模的。其主导思想是：统计x m l 数据 的分布情况，基于一定假设估计路径目标结点中间结果集的大小。这种方法般忽略执行算 法的不同和数据的物理存储。本节主要介绍了路径表达式选择性代价估计的方法和策略。 x m l 路径表达式可视为一棵树。其中的一个主支为从起点到目标点的主路径，其余分支 为约束主支的谓词条件( 如图2 3 所示) ，表示为p = t l 【p l 】t 2 【p 2 】i n 【p 。】。其中：t i 为结点名； p j 为谓词，默认存在量词布尔表达式。路径表达式的选择性估计是对满足分支条件的主支数 据个数的估计。对) ( m l 路径表达式的估计需要数据结构的统计信息与分布在结构内部的值 的统计信息的结合，以计算路径的选择性。 图2 3 a b 【c d e 】 g e f 】杉宰e f 1 数值统计 c h e n 等人把数值结点作为普通结点看待，这样，估计a - 3 与a 3 是等价的，简化统计 结构，适用于数值量较少的情况。如果数值量庞大，统计每一个数值的个数会占据大量的空 间，导致统计信息过多，影响查询代价估计的效率。这种方法对等值的定点查询可以使用， 却很难估计范围查询的代价。如估计a 3 的代价，需要遍历统计信息中所有同类数值结点， 判断其值是否满足条件。 f r e i r e 等人【2 4 1 用直方图等方法分别统计不同类型的数值信息，如最大值、最小值、平均 值、个数等信息。既适用于范围查询，也适用于点查询。其缺点是：数据类型过多会导致统 计信息的膨胀；并且，x 数据的特点是白描述性，其值和结构有密切的语义关系，分开统 计必然导致分别估计，造成估计误差，在文献【2 4 】中有关于这方面的详细论述。 1 0 x m l 查询处理结构及常规逻辑优化算法 2 数据结构抽取 l 数据为有序有向图。对图的结构抽取有两种极端的方法： 标记分裂图( 1 a b e l s p l i tg r a p h ) 方法粗略地统计模式信息，其思想是合并所有的标记名 相同的结点为一个结点，记录合并结点的个数作为标记的统计信息。这种方法占用空间相对 较小，但不能精确地反映数据分布的真实情况，尤其是同名结点出现在不同位置上时，可能 包含错误的路径或者圈信息； b f 类似图( b f - b i s i m 时脚h ) 中，只有所有入边和出边集合相同时才合并同名的结点。 保证准确地统计路径表达式所有的分支情况。这种方法的缺点是占用空间大。 查询优化的统计信息控制在一定的范围内，现有系统的抽取方法都是介于两个极端的情 况之间。 l 0 他的d a t ag u i d e 嗍抽取模式的方法是保证每条路径只出现一次，其最小模式是标记分 裂图的一个例子。文献 2 6 】指出：这种方法统计路径信息能够精确判断路径是否存在，但并 不能更精确地统计不同结点的值在不同路径中的分布情况。如图2 4 所示：图2 4 ( c ) 为图2 4 ( a ) 的虽小d a t ag u i d e 。如果对结点1 9 的统计信息为t ，根据图2 4 ( c ) 无法判断是路径a c 或者 b c 的结点个数；图2 4 ( b ) 为图2 4 ( a ) 的强壮d a t ag u i d e 。如果对结点1 2 和1 3 的统计信息为 t 1 2 和t 1 3 根据图2 4 ( b ) 判断路径a c 的个数为t 1 2 b c 的个数为t 1 3 。 ( i ) 图2 4x 札数据和d a t a g uld e s s t a t i x 【2 7 1 根据x l ls c h e m a 统计结构信息，它是一种折衷的方法。出边不同但同类型的 结点合并为一个，系统对不同类型的结点标记以不同区域的值，按照区域分别统计不同路径 的结点个数，保留了分支结点的路径分布信息。儿子结点的分布情况保留在父亲结点的统计 信息中。每个结点的统计信息不再是单个的值，而是一个复杂的结构。导致的问题一是代价 信息的增长，二是代价估计算法的复杂性。 x s k e t c h 【2 8 】也是一种折衷的方法。但只统计结构中每个结点对应数据中结点的个数信息。 其特别之处在于对结点入边和出边的信息的统计。如果对任意结点v v ，存在u u ，在数 据集中都有边( u ，v ) ，则v 对u 向后固定。如果对任意结点u u ，存在v v ，在数据集中都 有边( u ，v ) ，则u 对v 向前固定。这种统计信息用于在合并不同分支与主支之间选择性代价估 计的计算。 上述方法统计的只是路径中父子之间的关系，而没有统计同父的兄弟之间的相关性。为 了便于计算相对路径的代价和统计路径之间的相关性，c h e n 等人【2 9 1 吸收了信息检索中在文档 中检索子串的采用后缀树的方法【3 0 】统计路径信息，称为相关子路径树( c o r r e l a t e ds u bp a m 缸e e ) 。从x m l 数据中抽取所有到叶子的可能路径，形成路径集合，其中间结点的结点名为 不可分割子串；叶结点为数值或者字符串值，为可分割子串。每个结点存储子路径在数据中 出现的次数和路径特征矢量。我们将在后面的选择性计算部分介绍后缀树方法的代价计算方 法。 x s k e t c h e s 【3 1 3 2 1 在文献【3 0 】的基础上增加了对边的信息和值的信息的统计，从而在一定范 围内( t s n ) 能够处理结构和值或值和值的相关性问题。但增加信息的同时，也使得构造 x s k e t c h e s 结构代价加大。在x s e e d 例中提到：为l o o m 的a r k 【1 文档构造一个x s k e t c h 骼 结构需要超过一天的时间，这在实际中变得不可接受。 针对x s k e t c h e s 的缺点，x s e e d 提出了一种新的处理思路，即抽取晟粗略的信息，称为 x s e e d 内核，一般只占文档大小的2 左右；然后，再利用查询反馈的信息把误差最大的那 部分路径选择率的精确值存储起来，而这部分存储的信息的多少是根据内存大小来确定的。 但是，这种方法只能处理x p a t l l 。 如果把x m l 数据看作树，对树中的结点按照( s t a n e n d ) 嗍编码，以s t a 为横坐标，e n d 为纵坐标，则树中所有结点可看作是平面空间上的点，路径上的祖先和后代关系满足：x 。一妒 x 如鞯c i d a 呲 y d c 。i l d a 。y