XML查询优化研究

I S 1 0— 8 5 CODE RUXUEW S N 0 0 9 2, N

Jun lf ot r, o.7 No1, tb r 0 6 P .0 9 2 8 o ra Sf eV 1, . Ocoe 0, P2 6— 0 6 o wa 1 0 2 DO: 016/ s7 09 I 1.30j 12 6 o@ 2 0 yJ un lfSf aeAlihs eev d 0 6 o ra ot r. lr t rsre . b o w g

E mal O@i a.c n— i jS s s . : c ac ht:ww js r. t/ w. . gc p/ oo nTe/ x: 8 . 0. 2 6 5 3 l Fa+ 6 1 6 5 2 6

XML查询优化研究孟峰H宇，王锋小，王 小(中国人民大学信息学院，北京 1 0 7 ) 0 8 2

(北大学计算中心，定河保

0 10) 70 2

R sa c nXMLQu r t z t n e e rho eyOp i a i mi oME NG a— n H Xi o Fe g,

WANG 2 Yu,

WANG a . e g Xio F n

( fr t nSh o, n nUnvri f hn, e ig10 7, h ) I omai co lRemi iesyo ia B in 0 8 2 C ma n o t C j (o ue e trHee Unvri, o ig0 10, hn) C mp tr ne, b i ies Badn 7 0 2 C ia C y t +C r sodn u o: h: 8—06 59 5,— i xme g u . uc, t:ww rc d . or pn igat rP n+ 61—2 14 3 Emal f n@rce . ht/ w. . uc e h: d n p/ ue n

Me g XF n ,Wa g Y, n .R sa c n XML q ey o t zt n o r a f S fw r,2 0,71 ) n Wa gXF ee rh o u r p i ai .J u n lo ot ae 0 61 (0: mi o2 6— 0 6 ht:www. s r ./0 09 2/72 6 .t 09 28. t/ p/ j . gc 10 - 8 51/0 9hm oo nAb t a t XM L h sb c me t e d -a t t n a d f rd t e r s n a i n a d e c a g n t e W o l。 i e W e sr c: a e o h e f c o sa d r o a a r p e e t to x h n n e o h

rd W d b. Du o t e n t r f i f r t n o h e nd t e i h r n e i ii f XM L ti x e t d t a u h o e e t h a u e o o ma i n t e W b a n e e tf x b l y o n o h l t,i s e p c e h t m c ft h d t n o e n XM L wi e s misr cur d Daa o h n e n ti n r a i g y p e e t d i aae c d d i l b e -tu t e . t n t e i t r e s i c e sn l r s n e n XM L f r a i h l o m t wh c e a l sr s a c e n va i u i d f n b e e e h s o r o s k n so r XM L so a e mo e . e wh l, tr g d 1M a n i XM L q r p i z to a e o o e ue y o t mi a i n h s b c mea h t r s a c o i n d t b s e d Th s p p rg v s a v r iw ft e c re tsa s o e h o o y f r XM L q e e e r h t p c i a a a e f l . i a e i e n o e v e o u r n tt ft c n l g i h u o u r y o t ia i n p i z t .Th e t r s o m o e f a e f XM L q e p i ia i n a d k y pr b e s o e e c e a s s us e e pl . u u r o t z to n e o lm f r s a h a lo dic s d d e y y m r r M a n a p cs o u e t wo k o i s e t f c r n r n XM L q r o t z t n n l d ue y p i a i i c u e XM L a g b a o t m o e,c mp e a h mi o l e r,c s dl o lx p t s l c i t si to,sa itc n o ma i n a d S n. n l, i p p rp o p cs f t r e e c ie to s a d ee t y e t vi ma i n t t i s i f r t, s o n O o Fi a l t s a e r s e t u e r s a h d r c in y h u r n p e e t o iwp n

so r s n ss me v e oit f XM L q e p i ia in. u r o t z t y m o Ke r s XM L: u r p i ia i n y wo d: q e o t z to y m

摘

要： XML已经成为网络上信息描述和信息交换的标准 .由于网络上信息的本质特性和 XML数据内在的

灵活性，多用 X很 ML编码的数据都是半结构化的.随着 X ML应用得越来越广泛，提出了多种 X人们 ML数据的存储模型与此同时， XML的查询优化也是数据库领域研究的一个重要课题 .综合论述了 XML数据查询优化技术的现状。出了 X指 ML查询优化的特点和研究的关键性问题.述了查询优化技术各个方面的重要研究成果以描及存在的问题。步展望了未来的研究方向。进一并在此基础上提出了对 XML查询优化方法的一些观点 . 关键词： X; ML查询优化中图法分类号： P l T3 l文献标识码： A

S p o e yteNminl trl cec on aino hn n e rn s 0 7 04 6 2 3 1国家自然科学基金) te u p a db h o a Naua S i eF u dt fC iau drG at n o No. 0 3 1, 07 0 8( 6;h

N t n l adF n a na Reerh9 3Porm o hn n e rn No2 0 C 3 7 0国家重点基础研究发展规划 (7 ); e ai a n u dme t sac 7 rga fC iau drG at . 3 B 10 0( o Gr l 0 9 3)t h

K yPoeto hn s nsy o d ct nu drG at .3 4国家教育部科学技术重点项目) teP orm o e etr e rjc fC ieeMiir f uai n e r 0 0 4( t E o n No;h rga frN w C nuyE cln a nsnUnvri (家教育部新世纪优秀人才支持计划 ) xel t l ti ies国 e Te y tRe ev d2 0一 1 1; c pe 0— 4 1 c ie 0 6 O— 9 Ac e td2 060— 7

2 7 00

J u a o f ae软件学报 V 17 N ., c br20 or lfS t r n ow o 1, o 0 O t e 06 . 1 o

XML已经成为网络上信息描述和信息交换的标准.早期

的 X ML数据以文档方式存储，以关键字查询等信息检索手段查询，、易用.简单由于缺乏系统的存储和查询机制的支持，查询能力低，造成不能满足复杂条件的查询，不上查询优化 .更谈一些现有的商业数据库系统扩充了处理 XML数据的功能，利用现有数据库成熟的技术， 把X ML查询要求转变为数据库查询表达，由查询优化器优化查询表达并执行，再将查询的结果转变为 X ML数据.方法在一定程度上解决了查询复杂性的要求，多级转换带来的问题是效率的降低和查询语义的混淆.这种但 与传统的数据库数据相比， XML数据具有如下特点： 数据是自描述的，与结构混杂在一起；内容

数据具有完整的嵌套层次； 数据是有序的.

XML数据的不规则性是对传统统计信息方法的重要挑战，据分布情况使得一些传统的分布假设难以其数成立.为了达到所需的代价估计精度，要更多的统计信息.需而结构的复杂性又为获得相对精确的统计信息带来存储和计算上的困难. XML的有序性制约了转换规则的灵活性. XML数据的上述问题无论是对关系数据库或是对面向对象数据库的现有查询优化技术都是严峻的挑战 . 与传统的查询需求相比， ML查询具有如下特点： X 以长路径表达式为查询的核心语句，径复杂，分支路径；路包含 嵌套的查询表达，查询表达式中加入编程语言的嵌套和条件判断思想； 路径中包含不确定因素这在之前的查询需求中未出现过；

查询对象和返回结果类型不确定. 面向对象数据库已有一些处理复杂长路径表达式的经验，法处理 XML查询中的路径表达式中的不确但无定情况；关系数据库中已有很多处理嵌套查询的方法，对掺杂编程语言风格的 XML查询语言却难以适应 .但 综上所述，自数据结构和查询需求两方面的问题导致基于关系和面向对象数据库的查询处理和查询优来化技术均不能适应 X ML查询的需要.目前， XML查询优化的研究正成为热点 .的内容就是对 X对本文 ML查询优化技术现状的综合论述，出了XML查询优化的特点和研究的关键性问题，指描述了查询优化技术各个方面的

重要研究成果和有待进一步解决的问题.

1 X ML查询优化研究问题查询优化是

数据库技术中重要的研究问题，实现高效查询的关键性因素 .是对传统数据库查询优化的研究

已经形成相对成熟的技术和方法，中基于代价的优化是主流.其查询语言首先被转换成为一种内部表达形式 (通常是某种代数，关系代数等)据变换规则得到等价表达式，算不同形式的表达式的执行代价，后选择一如，根计然个最小的执行方案 .当把这种方法用于 XML查询优化时，究者遇到如下问题：研 f)完善的查询代数标准 1

众所周知，系数据库统治数据管理领域长盛不衰的法宝就是描述性查询语言 S L及其运行基础关系代关 Q数.关系代数的目的之一是给出明确的查询语义，之二是用于支持查询优化 .系代数的优势来自于简单、明确关的数据模型——关系。具有完善的数学基础和系统的转换规则 .的数据模型都以关系代数为蓝本，后来定义了不同的运算，面向对象数据模型等，如但效果并不尽如人意 . XML数据模型本身具有的半结构化特点是定义完善的代数运算的最大障碍. XML查询语言中的不确定性和一些编程思想的引入是另一个难以克服的困难 .而f)精确的代价估计 2

关系模型中，中的记录是无序的、大小相等的，计算时依据的一些分布假设是稳定的.且，表代价而由于其记录大小相等，时间的估计可以转换为对 I次数的估计，转换为对中间结果大小的估计 .对/ O进而而在 XML模型中，数据是有序的，聚集的方式不定，数据的大小相差悬殊，数据每个中间结果大小与 I/ O次数之间的对应关系没有明显的规律.简单地沿用传统的代价计算方法必然导致误差的产生，从而影响精确的代价估计.f)足够的统计信息 3

孟小峰等：ML查询优化研究 X

2 7 01

足够精确的统计信息是保证查询优化有效性的基础；乏足够的统计信息，缺是造成估计与实际情况产生误差的重要因素.的统计信息多是对值的统计，平均值、传统如对最值、记录个数等的统计 .些对 XML查询是不这

够的.ML数据本身缺乏模式的支持，数据结构信息的统计显得更加重要 .ML数据中的数值分布在类似树 X对 X状结构的树叶上，即使相同类型的数据，由于半结构化特点，其分布情况也可能完全不同.,因此需

要把对结构的统计信息和对值的统计信息结合到一起，能得到足够精确的统计信息.才

2 XML查询处理结构 与传统的关系数据库系统的查询处理结构类似，我们可以将 XML查询处理分为 4大的阶段.图 1示个如所

中间方框表示查询处理步骤；方框为使用的相关技术或方法；左侧右侧方框为查询优化和执行时需要的信息.

Fg 1 Q eypo es g i. u r rcsi n

图 1查询处理过程

第 1阶段查询解析，将查询转换为某种内部表达方式，以便于机器处理，并为下一步的优化过程铺平道路 .这种内部表达方式通常以一种抽象语法树或者查询树的形式出现 .统数据库为基础的查询引擎的做法是转以传换成关系代数，然后由关系数据库优化器完成剩下的优化工作. Naie的数据库系统则采用不同的XML代数而 t v系统.我们在第 3节中将会介绍目前流行的几种 XML代数. 第 2阶段逻辑优化，利用模式信息，规范和简化内部表达式 .一阶段中，在这系统不考虑实际数据的值和数据的存储情况.同一查询请求，以转换成不同的等价表达方式，中有一些比原有查询更高效.了进行这种转可其为换，化器需要一些转换规则，将在第 4节中讨论这些转换规则 .优我们 第 3阶段物理优化，利用代价模型和统计信息计算不同表达式、不同算法的执行代价，选择最低代价的查询计划 .一阶段中，在这需要解决两个问题：确定表达式执行顺序和决定每步操作的具体算法 .于 XML查询树对

而言，需要将查询表达式分解为可执行的片断，首先然后选择合适的执行顺序和执行算法并执行 .中间结果集的大小是决定执行策略是否高效的关键因素，实际的数据分布密切相关.合考虑数据的存储、索引和数据值与综的分布情况，准确地估计复杂路径选择性是其中的难点.于一个给定的执行策略，对通常会有多个可能的执行算

法，生所有的执行算法的组合造成选择本身的代价过大 .产因此，会有一些启发式规则用来控制其空间规模，并采用一些空间搜索技术加速选择的过程 .我们将在第 5节中详细加以讨论 . 第4阶段查询执行，据物理优化确定的执行策略和算法，问数据并得到查询结果.根访由于 XML数据复杂

和变化的结构，需要高效的数据访问算法 .

3 X ML代数XML代数是对遵循一定数据模型的 X ML文档集合的操作集 .ML代数提供根据请求在文档集合中选择 X

27 02

J unlfS tae软件学报 V 17 N ., c br20 ora o ow r f o., o1 O t e 06 1 0 o

一

个或多个文档或者文档片段的能力. XML代数应支持对查询结果的重构.

目前对 XML代数的研究主要集中在对查询代数的定义和从查询语言到查询代数的转换方面 .查询代数定义查询对象的类型，以执行的操作和不同操作之间的转换规则 .语言经分解转换为由查询代数的操作表可查询

达构成的操作树或者操作序列.同的代数表达可以有相同的语义和执行结果，不构成代价空间.31 . XML代数定义

目前产生很多种 X ML代数，风格各异，主要思想来源于关系代数、面向对象代数、半结构化代数和功能其化编程语言等.由于篇幅有限，能在这里一一介绍，不我们介绍其中具有代表性和影响力的几种. l出了不同表列代数之间特点的比较.Ta l Co b e1 mp rs n mo gXM L u r l e r a i o sa n q ey a g b a

表 1 XML查询代数比较

OrceI和 MS联合提出的一个 XML代数标准是文献【】该标准把 XML文档看作有向标记图(果忽 al, BM l.如略引用，以看作有向标记树 )五元组 G VEA,,表示.中：示结点，两种类型： e n和 v le表可 .用 (,, R0)其 V表有 e me t l au. E示 ee n到 e met表示 e met v le即属性表示引用 . lmet l n e l n到 au, e上述 3种为边的类型. 0表示次序.这个模型在上，规定了导航、选择、连接、构造等操作，其导航操作提供在有向标记图中的遍历操作，包括正向遍历和反向遍历；连接操作语义类似关系代数中的连接操作，其根据相同的值连接不同的文档 .该代数采用类似关系代数的表达形式.

B lL b. A&TL b . May等人提出的 XML查询代数【, el a s 和 T a s的 r 2基于简化的 XS T数据模型增加了引用】 L,结点，并了属性和元素结点，除了注释结点.主要思想

来源于曾用于半结构化和面向对象数据库的代数合删其一一

嵌套关系代数，并增加了对正则表达式的操作 .嵌套关系中，在数据由多个元组和多个链表组成，并可多级

嵌套，其采用 l t o rh n in方法表达导航、笛卡尔积、嵌套和连接操作 .i o rh n in根据一系列过 i mpe e s sc o Ls cmpe e s t o滤和 g n rtr作，到满足条件的结果链表 .e eao操作与导航操作相对应.数还支持结构递归等程序 e eao操得 G n rtr该代语言特点， Hak l程序语言作为表达形式.用 sel 上述两种代数还仅停留在逻辑层次，没有考虑与之相对应的物理代数和查询优化策略，优势是具有较高其的描述性和丰富的语义，与查询语言有密切的转换关系；操作中对路径的处理并不完善，但其形成过多的递归结构【或者遍历操作【,一步的优化带来困难，其处理 XML查询的方法和思路被后来的 XML代数规则大 3】 2给下】但量采用 .

基于文献【,】 W3 23等， C于 2 0年公布了一个 XML查询代数标准 XQ e . F r l e nis J 01 u r 1 oma S ma t【, y 0 c 4用于规范查询语言语义.该标准遵循简化的 XQ ey 1和 Xp t . aaMo e[. u r . 0 a 20D t h dl比照关系代数给出了 XML数据模型的 投影、选择和连接等操作的定义，引入结构递归、条件判断等编程语言的概念 .oma S mat s的一个特点还 F r l e ni c

是代数表达与 X ey查询语言相同，为 XQ ey的核心语法； Qu r成 ur另一个特点是操作有不同的层次，高层次的操作可以转换为低层次的操作.标准中还给出了少量表达式转换规则，有待近一步扩充.目前已经有了应用该标准的xML查询引擎， Gaa t.如 l x Sa dod学开发的 XML数据库 L r系统[针对系统本身提供的访问操作和索引情况，出了一套独特 t fr大 n oe 7】提

的代数操作，括逻辑代数、物理代数和相应的转换规则.oe以该代数系统为基础提出了查询优化方法，包 Lr】但由于代数操作定义过多地依赖于 L r身独特的数据存储和索引技术， oe本该代数很难应用于其他系统.

Tm e数据库[中应用的 T X代数

[,数据模型为无序的树的集合，中的数据是有序的.针对树和 i br 9】 A】其们树直接

孟小峰等：ML查询优化研究 X

2 7 03

树枝规定了一系列操作无须中间结构的转换 . X把 ML数据模式看作树，把查询语句也看作树，二者之间作模式匹配，到满足查询树条件的结果树集合.AX在处理连接操作时对操作的顺序未做明确规定，得 T不适应严格要求文档顺序的情况 . X[】于集合概念构造了逻辑代数操作集， AL“基其操作分为 3种：抽取操作从 XML文档中获得必要的数据， 如选择、影等；投元操作控制表达式求值过程，非针对 X并 ML数据的抽取或者构造操作，是为其他操作符准备而输入或者控制其他操作的操作，映射、迭代等；如构造操作用于构造查询结果. AL为查询优化提供了一组启发 X式转换规则. 其他如 X OM代数【,】是完整的操作集，含 6种对象操作，包但不支持优化； AL代数【】 OP¨基于半结构化数据

模型，操作对象为多个链表，有限状态自动机用于生成执行计划；有 S将还 AL等[-] 1 1根据代数的操作方式， 47可将上述不同的方法分为两种：种是面向集合的代数，一其操作对象是某种类型的集合，如树的集合、值的集合等.这

种方法具有很好的优化基础，可能丢失数据的顺序；但另一种称为导航的代数，其操作对象是单个的数据 .这种方法不利于进一步的优化 .数定义应是逻辑操作与物理操作的有机结合 .目前的 X代但 ML代数研究或是把他们混合在一起，是虽然分开但缺乏相应的转换规则.或 早期对 XML代数的研究工作重点在于规范 XML查询语义，未考虑查询优化因素，并这些代数具有明显的程序化思想艮难进一步优化，能利用遍历方法求解查询，成查询效率的低下，只造不适应大规模 X ML数据的查询需求 .而基于数据库思想提出的一些面向“合”集的代数，具有很好的优化基础 .,因此目前查询优化的研究工作也多以这些代数为背景，也存在一些问题.但 首先是表达式嵌套 I . X ey查询中， '在 Qu r d题由于表达式可以任意嵌套，谓词可以出现在任意地方.谓词是有

作用域的，个谓词在不同的地方会产生不同的查询结果 .于集合

的代数需要将嵌套的查询转换为逻辑树同一基形式，不可避免地面临嵌套结构的非嵌套化问题.虽然在关系数据库中有一些方法可以借鉴，由于 X但 ML数据结构的复杂性，决这个问题变得更加困难.解

其次是 XML数据的有序性问题.除非查询语句特别指定，则应该保持结点在源文档中的结点顺序 .原否而

来一些处理连接的算法，比如排序连接、 ah接等，乱结点顺序，连接完成后， H s连会打在需要对连接结果做一个额外的根据结点顺序的排序操作.如果用 n s 1o et o p连接算法， .则可以省去这趟额外的排序 .进行代价估计的过程在

中，额外的排序操作要被考虑在内，给进行查询优化的过程带来新的考虑因素 .可能的解决方法是这个这就一种在所有操作中，忽略结点的有序性，在最后构造结果的时候再对结点按照文档顺序排序 .竟是使用 n s- o,究 eto p还 l是最后增加额外的排序的方法。这是查询优化的一个研究点. 最后，同的代数标准. XML代数研究中一个值得重视的问题是：不在目前已经出现了一些查询代数标准，这些标准在风格上相去甚远，难有共通性 .对执行方法的研究还远远不够，能形成完整的系统 .很而不而且从逻辑代数到物理代数的转换也将是未来研究的一个重要问题.32复杂路径表达式分解 .

目前的 X ML查询语言有很多， XP t[ XQ ey,如 ah, u r[ XML Q[, L,ul】 .们的一个共同的特 . L XQ[ Q i[等它们” t点就是对复杂路径表达式的支持 .表达式分解是根据一定的转换规则，路径把用查询语句表达的、复杂的、不确定的路径表达式转换为简单的、明确的、系统可识别的方式， XML代数.如路径表达式分解是查询转换的难点，是查询优化的重要一步，代价估计的前提条件 .也是根据不同的规则，路径表达式可能分解为不同的等价形式，中有的代价高，的代价低，成代价空间.其有形路径分解的原则是能够产生有限的代价空间，有利于利用分解的结果搜索代价最小的执行方案 .在路径分解时，两种不同的思路：种思路是把路径细分为两两的祖先后代或父子对， lr, S L等 .有一如 oeXIS2

这样做分

解算法简单，利用数据物理存储信息，可分解的结果容易转换为结构连接运算或者运用系统提供的各种索引.如果查询语句中出现通配符(,,)以利用索引直接定位数据，如？/可/,也可以借助模式信息确定通配符所代表的各种可能情况扩展路径 .过分解，经路径表达式转换为连接、投影、选择、导航等不同的代数运算；另一种思路【】 2是将复杂路径表达式用树的方式表示：开始，树中搜索最长的确定路径 ( 从根在不含/为一次分或/称 )

2 7 04

J unlfS tae软件学报 V 17 N ., c br20 ora o ow r f o 1, o 0 O t e 06 . 1 o

解，其路径构成树的一个子串.以这个点为起点，上述原则再分解路径，到确定路径(串)用得子的集合，为一个最称小分解 . XML文档的查询中，定路径的查询是相对容易的；在确而不确定路径的查询是比较困难的，其是在没尤

有模式或索引的情况下，可能要将中间结果合并才能得到全部的结果 .复杂的、不确定的路径分解为确定的、将 简单的路径处理 .分解方法在没有模式信息的情况下处理不确定路径具有一定的优势.这种

4逻辑优化在传统数据库技术中，逻辑优化是指通过一系列转换规则，原始的查询表达式转换为等价且更高效的形将式 .系代数表达式求解时，关操作顺序是影响效率的关键 .因此，逻辑优化研究的重点并不在于对冗余操作的分析，而是对操作顺序的调整. X而 ML代数的核心是由路径表达式转换的查询树，查询效率依赖于查询树的规模. 因此，查询树的最小化是 XML逻辑优化研究的重点，也是目前研究的热点问题.而对操作顺序的调整因为更多地依赖于物理存储的情况，因此与物理优化相关联. 从层次上看，逻辑优化可分为两个层次：语法层次和语义层次 .层次的优化是指不依靠任何其他信息，语法 独立地分析查询表达式中分支或结点间的逻辑包含关系，除冗余部分；删语义层次的优化是指通过数据库提供的模式信息， DT XML S hma,语义包含、结构包含等完整性约束，如 D, ce等或者查找查询表达式中的冗余分支或结点.的例子进一步说明二者之间的区别.有如下的 XQur下面若 e

y查询表达式：fr￥ i eee c/ o . o口 nr frn ebo k

o 6i aa t o, ci f r￥ n￥/uh r￥ aa to/ a, i a a to/mal n￥/uh r n me￥ n￥/uh re i wh r 6a d￥ n e e￥ n ca d￥

rtr b o )ab o ) e n(o k￥ (o k u

其 P R m T e(下简称 P Q￣图2 a所示，中，圆为查询返回结点. a e re T )I ()]其实心若数据满足￥, c同时必然满足￥, 6

￥分支对查询返回结果没有任何影响，余结点.称这种冗余结点为语法冗余结点.语法优化后的 P Q 6是冗我们经 T如图 2b所示. ()若从模式可知任一 ato uh r均有 n me则 v为冗余结点.称这种冗余结点为语义冗余结点. a, 6我们经语义优化后的 P Q如图 2c所示. T ()Re e e e f f nc

Bo k o

Au h r to

F g 2 S n a d s ma t p i ia i n i . y t x a e n i o t z to n c m

图 2语法优化和语义优化下面我们分别介绍语法优化和语义优化的研究现状 . 41语法优化 .

对 P Q语法优化问题基于对路径等价性问题 T

的研究.早提出 X a最小化的 Wo d旨一个最 Pt h o[出：

xpt可以表示为合取范式， XP t ah对 ah等价性检查的复杂度等价于对合取范式的等价性检查.而这已经证明是一个 NP完全问题.如果对 X a P t径表达式的复杂程度加以一定的限制，P t最小化问题的复杂度可以达到多 h路 x al l项式级.目前已经提出了对不同类型的 P Q的最小化方法. T ()简单 P Q{[ 1 T/】 ),,

文献【】出了对只包含{[ ) 2中提 9/】的简单路径的最小化方法.,, 其思想为：设原始 P Q为 P在所有与之等价 T,

孟小峰等：ML查询优化研究 X

27 05

的 P Q中找到 Q使得 Q中的结点个数I T,Ⅳ最小， Q为 P的最小化 P Q.则 T 这种方法的关键是通过对包含映射 (o timet p ig的判断完成 P Q的等价性判断. cnan n pn ) ma T不存在祖先后代关系()/的简单 P Q的最小化 P Q为其子树./ T T查找等价 P Q的范围限制在其子树的范围内， T是

保证最小化算法的复杂度为多项式级的关键因素.文献[2 q给出了复杂性证明，并未给出算法细节 . 2 1h虽然() P Q{/[ 2 T//],, )

文献[0提出了 P Q的 CI c nt it n e e d n nmiain算法 .献[9相同， 31 T M(o s an d pn et i zt ) r i mi o与文 2】其算法的基础也是包含映射 .径中缺少“的 P Q的最小化问题，旧可以在其子树范围内解决 .I算法的思想为：叶结点开路 T仍 CM从

始，判断结点在 P Q中是否冗余： T若某结点是冗余结点，除这个结点，则删继续处理其他叶结点直到所有叶结点判断完毕； P Q中结点个数为，则 C M算法的最大复杂度为 O( .若 T 2, I n) 文献[1提出了一种最大复杂度为 O(的改进算法，结点间的二元关系 Smu￣in判断冗余性. 3】 n)通过 i lo改进的 C M算法与 CI算法最大的不同点在于： I M前者只关心后代结点之间是否相同；后者还要关心祖先结点之间而是否相同.改进的 C M算法通过正向遍历查找冗余结点，果某结点的一个儿子结点与另外儿子结点之间有 I如

Smuain关系，个儿子结点为冗余结点. i lo t则这这样，在一次遍历可以对多个结点的冗余性进行判断，从而提高了P Q最小化的效率. T () P Q{/[,) 3 T//】 ,, 。

与限制条件下 P Q所不同的是，遍意义下的 P Q在语法优化时遇到的一个关键问题是： T普 T最小化 P Q并 T非原始 P Q的子树，是由以原始 P Q的根为根， T而 T连接多个 P Q子树构成的 P Q.中每个子树均为原始子树 T T其的最小化部分.这个问题也是导致其复杂度上升的关键 . 文献[2给出普遍意义下的 P Q最小化算法.算法思想是：归地在原始 P Q的子树中查找最小子树并 3】 T其递 T连接它们，这个过程中冗余的分支被删除了.[2证明其算法的复杂度为 NP完全，在文献 3】并指出：对 P Q的分在 T支个数加以一定限制的情况下，的算法复杂度可以达到多项式级 .我们有理由相信，改进但这样的改进意义并不大，因为这要求用户在写查询语句时必须注意查询的分支情况，则将导致某些查询无法优化 .否目前，法优

化都以判断结点之间的包含映射关系为基础，析路径等价性.查询树中不断地修剪冗余的语分在

分支或结点，到减少查询树规模的目的.意义的 P Q语法优化是一个 NP完全问题，达普遍 T研究者通过对 P Q复 T

杂度加以一定限制，出了多种高效的算法 .法优化不涉及 X提语 ML模式信息，以利用模式信息进一步简化可P Q, T这种优化称为语义优化.42语义优化 .

最早提出语义优化的是关系数据库系统.利用表格属性值之间的约束关系把查询表达式转换为等价但更高效的形式 . ae方法【其中的代表.思想为： c s h]是其把完整性约束作为冗余条件插入到查询表达式中，已存在与的冗余操作合并，使得组合后的条件符合某些事先定义好的等价转换规则，用这些等价转换规则重写查询表利达式以达到优化的目的.是一个巧妙的先膨胀再收缩的方法.这但是，应用 C ae法于 XML查询的语义优化时面临下述严重的挑战： hs方 数据结构的变化：面表结构不同，ML数据具有嵌套性.与平 X原有的主键、键等完整性约束不能表达结构外上的嵌套关系，缺乏匹配的转换规则.

数据类型的变化：模型中，有严格的类型；关系数据而在 X ML半结构化模型中，没有严格的类型约束， 数据同名的结点可以出现在不同的位置，以有不同的子结点.的转换规则的应用方法不适应这种情况，发的问可传统引题就是产生递归的转换，致路径的无限增长.导 查询语句的复杂性：Q语句清晰、明确， SL关系代数操作均为输入参数明确的一元或二元运算. XML查而询语句中包含//等不确定因素，以包含多个分支长路径为特点，,并原有的转换规则不适应于 X ML语义优化. 基于上述挑战，一些研究者提出改进的 Ch s ae方法，另一些研究者则从对图分析处理的角度出发，究而研XML查询的语义优化问题 .()改进的 Ch s法 1 ae方

27 06

Junl fSf ae软件学报 V 17 N ., c br 06 ora t r o ow o 1, o1 O t e 20 . 0 o

Wo d等人IJ早将 C ae方法引入简单 XP t o z最 9 hs a h语义优化.献[9在 D D上定义了 3种结构约束关系，文 2]

T 分别为儿子约束、父亲约束和兄弟约束.个查询树中结点 n为上述约束关系中的主体，若某且其约束的结点不在查询树中，则在查询树中相应位置加入客体结点.当所有约束关系应用完毕，用语法优化的方法对查询树进再行修剪，到最小化查询树.了讨论简单起见，献[9中方法只适用于不包含“和“/的简单路径，得为文 2]’/”其复杂度为多项式级 .

文献[o￣认为， 31 XML数据中的结构完整性约束可用儿子约束、后代约束和类型约束概括 .了得到正确为的优化结果，对 C ae方法做了 3个方面的改进：先，设约束集合是闭包的；他们 hs首假其次，了保证优化能够完为

成，束条件只应用于 P Q中原有结点，约 T如果某结点是由于应用某约束条件加入 P Q的，不对其应用任何约 T则束条件；后，最由于应用约束条件加入的结点是冗余的，因此，需要在算法结束时删除这些临时结点. I算法 AC M分为 3个步骤：首先，用约束集合中的约束条件放大 P Q;应 T然后，用 C M算法语法删除冗余结点，删除时保应 I在证不检查被加入临时结点的冗余性；后，除所有在第一步中加入的临时结点. P Q中结点个数为，则最删若 T 2, AC M算法的最坏计算复杂度为 O(。.些冗余结点是容易识别的，果提前删除这些容易识别的冗余结点然 I n)一如后再应用 AC M算法，以有效地提高优化的效率.法 C I可算 DM在 P Q中遍历地查找并删除这样的冗余结点， T其

计算复杂度为 O( . n)实验证明，使用 AC M之前使用 C在 I DM,比直接应用 ACI可更为有效地节省时间. M

文献[1文献[0的基础上扩充了子类约束， 3]在 3】并利用语法优化中的 T Q iuao和 T Q n zt n P S li m tn P Mii ao改 mi i进了 AC M算法， I使计算复杂度达到 O( . n) ()基于 DT的路径等价类方法 2 D

文献[4提出了一种基于模式的 XP t 3] ah路径表达式的语义优化方法 .思想是： XML文档模式( D划其把 DT )分为若干个路径等价类，每个类中的路径等价； XP t换为由简单路径构成的合取范式形式，路径等价将 ah转利用类中的最短路径代替表达式中的路径 .这

种方法，以实现 3个方面的优化：通过可首先，删除冗余的谓词条件；其次简化路径；最后，断表达式的条件是否满足 .果某个分支的条件不满足模式中的约束关系，整个表达式判如则的查询结果为空 .整个优化过程分为 4部分：、扩展、优化和重构.分解在分解过程中，P t达式被转换为合 Xa h表取树( CT;构 X a X )重 Pt h表达式则将优化的 XC T转换为 XP t ah路径表达式. 改进的 C ae方法的优点是： hs语法优化与语义优化相结合，优化过程无须对 P Q进行转换. T问题是难以保证彻底的优化：先，T中存在非叶冗余结点，首 PQ而语法优化只能在删除叶结点后，让非叶结点变为叶结点的情况

下才能判断其冗余性 .约束条件后的 P Q语法优化，能在不删除叶结点的情况下，加入 T不判断非叶结点的冗余性；次，其膨胀后的 P Q难以压缩， T采用对转换规则加以一定限制的方法限制膨胀后 P Q规模的方法， T会导致优化的不彻底 .改进的 C ae法都是针对一定复杂程度的 P Q的优化策略，目前 hs方 T普遍意义上的 P Q的语义优化 T

研究还需深入；最后， D D中获得的约束条件并不充分，从 T这也是导致优化不彻底的一个因素.如何抽取更多的语义约束条件，是未来研究的一个重要问题.基于 D D的优化方法的优点是：但能够删除冗余分支， T不还能够缩短路径长度和直接判断路径是否满足 . 问题主要是：先，首需要对 P Q进行转换， T占用大量优化时间；其次，需要不确定路径的确定化，实际上也是一种这

路径膨胀，以保证优化的结果小于优化之前.难 两种方法都需要首先扩大路径规模，成优化的不彻底和效率的丧失，造这是目前语义优化面临的一个重要问题.

5物理优化逻辑优化的结果是一个或多个查询树 .如何确定其中不同查询片断的执行次序， XML物理优化的核心问是

题.确定执行次序的主要因素是中间结果集的大小 .杂路径表达式选择性分析就是用来估计结果集规模的.复其主导思想是：统计 XML数据的分布情况，一定假设估计路径目标结点中间结果集的大小.种方法一般忽基于这略执行算法的不同和数据的物理存储 .节从统计信息抽取、存储、压缩

、维护和统计信息计算等几个方面论本述目前这一技术的发展情况和所面临的问题 .

孟小峰等： XML查询优化研究

2 7 07

51代价估计方法研究 .代价估计是对查询物理运算时间的估计 .目前，代价计算方法主要有 3种：于参数的方法、基于取样的方基

法和基于统计信息计算的方法 .于参数的方法【无须统计数据信息，数据分布情况假定其满足包含某些基】根据参数的分布函数，通过计算函数的值估计查询计划的执行代价 .种方法在处理有规律分布的数据 (这如学生成绩),以大量节省统计信息空间和 I代价，时可/ O但对分布无明显规律的数据会有很大的误差；于取样的方基法【,] 33也无须统计数据信息，法是从数据集中提取具有代表性的样本， 67做比较不同的查询计划的执行情况，获得

代价最小的方案.这种方法的精确性决定于取样的代表性.最简单的方法是随机取样，些优化的方法根据数据一的密度取样 .取样方法的缺点是代价估计本身占用时间可能很大；常用也是研究最多的方法是基于统计信息最

的方法【1要统计估计所用的各种信息， 3,需 8利用统计信息计算不同方案的执行代价 .方法的精确性取决于统这种计信息的正确性 .是，但统计信息过大又会导致统计时间过长 .用有限的时间和空间得到相对小的执行方案，利 是代价统计的基本原则 .同的系统支持的物理运算算法不同，价模型也不同.不代 在关系模型中，行代价估计时有两个通用的前提：进独立性假设和均匀分布假设.者是指各谓词之间没有前相互依赖关系：后者是指如果关系在某个属性上没有直方图，则认为该属性的各值在数据库中均匀出现 . X ML数据的不规则性是对传统统计信息方法的重要挑战 .其数据分布情况使得一些传统分布假设难以成立. X在 ML中，同名字的结点可能在同一个文档的不同部分出现但却具有截然不同的语义 .同为 n me点，相如 a结 在 p ro esn下和在 c y下出现其意义就完全不同，可以称为元素之间的结构依赖性； i t这同时， X在 ML文档中，嵌套在不同祖先下的同类结点的个数差别也很大， b o点下的 a to个数是不确定的，如 o k结 uh r这可以称

为元素之间的结构相关性.了达到所需的代价估计精度，要更多的统计信息.为需而结构的复杂性又为获得相对精确的统计信息带来存储和计算上的困难 .ML的有序性制约了转换规则的灵活性 .这些问题， X所有都使得在 XML中采用传统的代价估计方法不切实际，来很大的误差 .会带针对 X ML数据的特点，我们应该寻求一种新的代价估计方法 .511代价模型 ..

查询计划的执行代价主要来自 3方面的因素：P计算代价、/ CU I O代价和数据传输代价 .P磁盘和网络的 C U,速度差距悬殊 .当不考虑数据的分布性因素时，影响代价的决定性因素是 I代价 .O代价受众多因素制约，/ O I/主

要来自 3个方面：一是数据库系统参数，页面大小、内存使用情况等；数据集本身因素，如二是如数据存储空间大小、索引情况、每个元素占用空间情况和元素的聚集情况等；三是查询请求因素，如查询条件的选择性等 . 目前， X对 ML代价模型的研究并不充分，代价模型相对简单，这也是造成代价估计误差的一个原因.oe的 Lr代价模型没有考虑聚集情况，不能判定不同的数据是否在同一页面上，,设每次 I操作只能获得一个因此其假/ O对象，把对 I/ O时间的估计转换为对中间结果大小的估计 .由于 L r o e中数据本身无聚集，方法可以获得较好这种的效果，对其他 XML数据库系统参考意义并不大 .但文献[9提出了一种新的代价模型，基本思想是利用查询 3]其

反馈信息来调整参数.如图 3所示，用户提交查询之前，在先人：找出影响查询执行时间的特征，[再利用线性回归模型计算出各个特征对查询代价的影响系数，即得到一个形如 c g (.:, 0 ),,….的函数模型， vv v当用户提交查询

时，利用函数和事先统计的特征值进行计算 .但是，中提出的方法只是针对 C U代价估计的，扩展到 I文 P没有/ O代价的估计；且只考虑了一个 X v操作符，而 Na至于如何扩展到其他情况，献[9中并未提及 .工抽取特征具有文 31人主观性，如何让系统自动地抽取特征是下一步研究的重点.

Fi . CO ET o tmi a i n s t m g3 M p i z t yse o

图 3 C ME O T优化

系统

2 7 08

Junl fSf ae软件学报 V 17 N ., c br 06 ora o t r ow o 1, o1 O t e 20 . 0 o

51代价空间搜索技术 .. 2代价空间搜索算法首先通过某种计算方法量化代价空间、构造搜索函数，据函数值的变化判断是否继续根搜索.在众多的空间搜索技术中，简单的是随机搜索方法，机地或者按照某个顺序在搜索空间中计算代价 .最随 但这种方法效率低下，实际的系统中很少被采用.山算法是应用广泛的一种搜索算法，以某步长对函数进在爬在行搜索的过程中按照逐步接近的方式，位局部最优执行计划，索的效率与初始值和步长相关.定搜当搜索函数非单调时，种方法找到的是局部极值，这而非全局最值 .传算法是解决局部最优的一种新颖的空间搜索方法 .遗用杂交的方法搜索不同的最优执行计划，用于有多个极值的搜索函数 .方法在关系数据库查询优化中有一适这种定的应用意义， X在 ML查询优化的代价空间搜索技术中应用遗传算法的难点在于适应度函数的构造.单个查询物理计划形成的代价空间可能非常庞大，尤其是对路径很长的情况，其代价空间呈幂次级增长.为

了减少代价估计时间，需要利用启发性规则约束代价空间.oe的做法是： Lr分别将每一个逻辑操作转换为最优物理子计划，并在转换时应用启发性规则 .:ag te操作只在路径表达式的起始结点是标记名并且只在路径例如 T reS t

结束结点上有变量约束时使用；当查询中有多个路径表达式时，不改变其间的顺序.值得注意的一条规则是，选择操作总在最后做 .规则和关系查询优化的启发性规则正好相反.这条这是由于在 L r选择运算总是基于变 oe中，量绑定运算. 在 X ML代价估计研究中，表达式选择性代价估计是核心问题，路径也是在 XML查询优化研究中份量最重

的一个领域，我们特别关注 .值得在第 52节中我们将做专门的论述 . .52路径表达式选择性代价估计 . X ML路径表达式可视为一棵树，中的一个主支为从起点到目标点的主路径，其其余分支为约束主支的谓词

条件(图 4所示)如，表示为 P tt] 2,/ = .,/[z…. I。tt】

】 .其中：为结点名 f为谓词

,认存在量词布尔表达式 .表默路径

达式的选择性估计是对满足分支条件的主支数据个数的估计. XML路径表达式的估计需要数据结构的统计对信息与分布在结构内部的值的统计信息的结合，以计算路径的选择性 .

Fg4//[ d/]/////l i. abc/[/J/ e / e g e] y

图 4 abc/]//l/// ll[ d/[/y l e/ e g e] f521数值统计 ..

Ce hn等人[】数值结点作为普通结点看待，把。这样，估计 a 3与口3是等价的，= .简化统计结构，适用于数值量较少的情况.如果数值量庞大，计每一个数值的个数会占据大量的空间，统导致统计信息过多，响查询代价估计影

的效率.这种方法对等值的定点查询可以使用，却很难估计范围查询的代价 .估计 a 3如>的代价，遍历统计信需要息中所有同类数值结点，判断其值是否满足条件 .

F e e等人【J ri r 4用直方图等方法分别统计不同类型的数值信息，最大值、最小值、平均值、个数等信息. l如 即适用于范围查询，用于点查询.也适其缺点是：据类型过多会导致统计信息的膨胀；且，数并 XML数据的特点是自描述性，值和结构有密切的语义关系，其分开统计必然导致分别估计，成估计误差，文献[1中有关于这方造在 4】

孟小峰等：ML查询优化研究 X

27 09

面的详细论述. 522数据结构抽取 ..

XML数据为有序有向图.图的结构抽取有两种极端的：【 对疗法 4:标记分裂 I 1 e.pi ga h方法粗略地统计模式信息，￣( b 1 l rp ) a s t其思想是合并所有的标记名相同的结点为一个结点，录合并结点的个数作为标记的统计信息.种方法占用空间相对较小，能精确地反映数据分布的真实记这但不情况。其是同名结点出现在不同位置上时，能包含错误的路径或者圈信息；尤可 BF类似图(/ .imi rp )只有所有入边和出边集合相同时才合并同名的结点，/ B F bs a ga h￣, i r保证准确地统计路径表达式所有的分支情况.这种方法的缺点是占用空间大. 查询优化的统计信息控制在一定的范围内。现有系统的抽取方法都是介于两个极端的情况之间 .

L r的 D t ud[】模式的方法是保证每条路径只出现一次，小模式是标记分裂图的一个例子 . o e a G i 抽取 a e其最文献【3指出：种方法统计路径信息能够精确判断路径是否存在，并不能更精确地统计不同结点的值在不 4】这但同路径中的分布情况 .图 5所示： 5c为图 5a的最小 Da G ie果对结点 1如图 () () t ud . a如 9的统计信息为 r,根据图 5c ()

无法判断是路径 A. C或者 B. C的结点个数； 5b为图 5a的强壮 Daa ud .果对结点 1图 () () tG ie如 2和 1 3的统计信息为 t和 f, l l根据图 5b判断路径 A. 2 3 () C的个数为 f, C的个数为 t . lB. 2 l 3

() a

() b

() c

F g 5 XM L d t n sc re po d n t Gu d s i . a a a d i o r s n i g Da a i e" t

图 5 XML数据和 Daa ud s tG ie

Sai J tt l X[根据 XML S h ma统计结构信息，一种折衷的方法. ce它是出边不同但同类型的结点合并为一个，系统对不同类型的结点标记以不同区域的值，按照区域分别统计不同路径的结点个数，留了分支结点的路径分保布信息.结点的分布情况保留在父亲结点的统计信息中.结点的统计信息不再是单个的值，儿子每个而是一个复杂的结构.导致的问题一是代价信息的增长，二是代价估计算法的复杂性 . , Xsec[ J kth也是一种折衷的方法，只统计结构中每个结点对应数据中结点的个数信息 .别之处在于对 2但其特结点入边和出边的信息的统计.如果对任意结点 v/存在“ 在数据集中都有边(,,∈I,∈“v则对 U向后固定 . )如果对任意结点“,∈U存在 v 在数据集中都有边(,,￡对向前固定.种统计信息用于在合并不同分支与∈“v则， )这主支之间选择性代价估计的计算 . 上述方法统计的只是路径中父子之间的关系，没有统计同父的兄弟之间的相关性 .了便于计算相对路而为径的代价和统计路径之间的相关性，h n等人【 J了信息检索中在文档中检索子串的采用后缀树的方法[】 Ce 吸收 o 4 4统计路径信息，为相关子路径树(o

rltd sb ah t e. XML数据中抽取所有到叶子的可能路径，成路称 c r ae u p t r ) e e从形

径集合，中间结点的结点名为不可分割子串；其叶结点为数值或者字符串值，为可分割子串.结点存储子路每个径在数据中出现的次数和路径特征矢量 .我们将在后面的选择性计算部分介绍后缀树方法的代价计算方法：在信息统计部分介绍后缀树信息的存储和修剪维护方法 .XS ec e[,J文献[2的基础上增加了对边的信息和值的信息的统计， k th s 56 44在 4】从而在一定范围内( N) TS￣够处

理结构和值或值和值的相关性问题.增加信息的同时，但也使得构造 XS ece结构代价加大 . XS E】 kt s h在 E D[中提’

28 00

Junl fSf ae软件学报 V 17 N ., c br20 ora o t r ow o., o 0 O t e 06 1 1 o

到： 10的 X r[】档构造一个 XS e h s结构需要超过一天的时间，在实际中变得不可接受.为 0M Mak 8文 kt e c这针对 XS ec e kth s的缺点， E D[提出了一种新的处理思路， XS E】即抽取最粗略的信息，为 XS E内核，称 E D一般

只占文档大小的 2%左右；后，然再利用查询反馈的信息把误差最大的那部分路径选择率的精确值存储起来，而这部分存储的信息的多少是根据内存大小来确定的.是，方法只能处理 XP t.但这种 ah如果把 XML数据看作树，中的结点按照(tne dI编码， s r为横坐标， d为纵坐标，树中所有对树 s, ) a n】以 tt a e n则

结点可看作是平面空间上的点，径上的祖先和后代关系满足：路

跏

,抽出

,整个空间把

区域分成多个方格，计结点在每个格中的分布个数；等人 1统 Wu。的思想是：不同结点映射为一维坐标上的线把段，线段和后代线段的起点及长度满足某种偏序关系，整个区间分成多个小区间，祖先把分别计算落在不同区间内的线段之间的关系 .这种方法减少了稀疏分布时的误差，不能完全避免.两种统计方法适用于对结构连接但这运算的代价估计.5 -选择性计算 .3 2

当 XML数据结构复杂、每个文档的数据量很大时，确地统计

信息是不可能的.精在计算查询代价时，需要用一

些假设来弥补统计信息的不足.目前的路径选择性计算方法分为 3种： ()基于马尔可夫链的方法 1

L r[】法基于马尔可夫链思想，于计算没有分支条件的简单路径. oe。 的方用系统中只保留短路径的选择性统计信息，于父子结点分布的独立性假设计算长路径选择性 .有长路径 t tt…/,选择性计算公式可以是基如 l23 t其/// .r一，+、”1,+、

( .=兀 Jki J×( ) \1 t} l . )l 厂 i=此时，只需保留长度为 1 2的路径信息.可以是和也￣(t…n= t2 t) l

则需保留长度为” 2和” 1的路径信息 .一一路径信息越长，组合个数越多，占用空间越大，算值越精确 .计实验表明，

当路径信息较短时，加长路径信息导致明显的计算精确性，空间代价增长相对缓慢；且当路径信息较长时，加长

路径信息导致空间代价的爆炸性增长，而精确性提高缓慢 .果在路径的某个结点上有对简单值的选择，据如则根兄弟分布独立性原则，不同选择性再做交集运算 .计算

Ab un g o la a等人【对 L r】 oe的方法进行了改进，出了路径(ah树和 Mak v表来估计简单路径的选择性 .提 pt) ro 用路径树可以表示原文档的结构，中的每一个结点代表了从文档的根结点开始的路径，树并记录了相应结点出 现的次数 .当树变得很大以至于不能放在内存的时候，需要对树进行剪枝，据一定的算法，去那些出现但就根删不频繁的结点，在这个剪枝过的树上进行选择率的估算 . ro然后 Mak v表存储长度为 m (= )> 2的不同路径，如果查询的长度和 m相等，直接就可以从表中读出相应的值，误差为 O当长度大于 m时，公式；用n—m r f . i● i i ●、

厂 t…t= (//I)兀 l I,f2+l,…,f: (///)厂 t…t×=1 j+ 2 2 m l - m+一 f1进行计算 .同样地，当表不能放入内存时，删除那些不频繁路径 . Xsec[加了对边的固定性统计信息，对 L r的方法做了改进，用于更一般的路径表达式代价 k th增并 oe以适估计 .果主路径是向后固定的，

统计信息为精确信息，如则无须进一步计算；n O果主路径中有些点不是向后固定

的，则在这些点上把主路径分为多个子路径，路径独立性假设，根据用类似 L r oe的公式，以子路径统计信息为参数，计算长路径的选择性.果分支路径是向前固定的，如则其选择性为 1无须参与计算；,如果分支路径中有些点不是向前固定的，则在这些点上把分支路径分为多个子路径，计算不同选择性，再做交集运算 .了提高计算的精为确性，其代价路径分解方法为最大交叉方法 . XS ece[,1 k th s 56 44对文献[2的工作进行了扩展，以计算 t g匹配的个数 . k th在原来模型的基础上增 4】可 wi XS e c加了边的分布信息，而能够从细节上把握数据的分布.种方法的特点是：抽取 XML文档的结构建立从这先XS ece, k th s然后利用边的稳定性和边的分布概率来估计 t g的匹配个数， wi如果边的确是分布均匀的话，么这那

孟小峰等：ML查询优化研究 X

28 01

种方法的准确率就比较高 .

XS E方法在 XS E E D[ E D核结构上增加了对递归结点的处理，递归结点是指在 DT中有类似 A A,的 D (+B )定义， A结点是一个递归结点. E D核结构在边上记录了在递归的不同层相应的父亲、孩子的结点个数 .则 XS E因此，方法可以很好地处理带有递归表达式的 X ah查询.这种 Pt 马尔可夫链思想中的一个关键性假设是父子结点分布独立性和兄弟结点分布独立性假设.实际上，多而很

X ML数据的父子结点、兄弟结点之间的相关性非常强，应用上述计算方法会导致误差 .哈希方法统计相同集合分支之间的相关性信息，更准确地计算分支路径的选择性.()集合哈希方法 2

集合哈希方。 的核心思想来自蒙特卡罗技术的 Mi. s n e e d n emuain[这种方法用于估 nWi id p n etpr tt s e o .计两个集合之间的相似性.合的特征通过设置哈希函数的集合获得 .势在于集合的哈希函数值占用存储集其优空间很小.合，对集其特征矢量为s A ( n x ), n i= mi{ l} g mi{ ),.mi{l )) )., n x A}. . (

其中， f

, .}旋 U的排列；是哈希函数的个数 . 1.,; .n,s i gI I

[=mi{ g『…, g『) i】 n s 】 s A[ . i, i】

假设 A为势最大的集合，尹 -- f则=

__,而

I … u I l u

I . ’ u… A l

三：::三,,

.

关于集合哈希函数的构造方法在文献[4中有详细的论述 . 41

利用集合哈希方法计算路径表达式的代价的方法为：用后缀树统计所有可能出现在查询中的子路径的特征矢量；分解查询为多个相关子路径；用公式计算选择性.应文献[0中提供了 3种路径分解的方法，比较了不 4】并同方法之间的优劣 .种代价计算的精度对路径的长度敏感：这随路径长度的增长，计精度下降 .,征矢量统并且特本身是一种信息压缩的方法用来计算相关性时的精确性是值得商榷的.上述两种算法都是根据确定路径上的父子关系统计信息计算路径表达式中后代结点的选择性，没有直接计算后代，没有根据某些后代估计满足条件的祖先结点的选择性 .执行计划中，也在存在大量的向前遍历的算

法.如何估计这些算法的代价。一个需要解决的问题 .是 上面所提到的各种方法的处理能力各有不同，从方法能够支持的各种情况( a, u r,,,au )看，仅 xp t Xq ey/ v le来 h/}可以总结为表 2 .T b e2 Co a i o m o g v i u t o s p o e sn a l mp rs n a n a o sme h d’ r c s i g r

表 2各种方法处理能力比较

()位置直方图方法 3

Wu等人 u用位置直方图的方法统计组先后代的分布信息， J采其代价计算分为基于祖先的代价估计和基于后代的代价估计 .祖先的代价估计根据每一个祖先的格，基于累计其满足条件的后代的格中的结点个数；基于后代的代价估计则与其正好相反.不同区域的祖先后代结点的偏序关系，根据分别计算.图 6所示：如为某祖先格， 则区域中所有的格的所有结点均为 A中所有结点的后代： E区域中所有格的部分结点为 A中部分结点的后 C.

代； D,区域中只有左上半角区域中存在结点且部分结点为 A中部分结点的后代.而如果考虑自身的嵌套， A则

J

unl fS ta ora o f r o w e软件学报 V 17 N ., c br 06 o 1, o 0 O t e 2 0 . 1 o

中部分结点是中部分结点的后代 .据上所述，足条件尸的的满足条件尸的后代个数估计公式为满 1 2r 1.

1

[=[×÷ H t】舶[+ 舶 { i】】L s+咔 A 舶[】舶[+×[】舶[] .】 c+ E÷ ( D+】舶 F) J }

对每个格而言，其后代格限定在较小区域内，免多余的统计和计算 .在计算区域的边缘，避但并非所有结点满足上述关系 .平均分布的假设给计算结果加以某个系数是产生误差的主要因素，差在空间结点分布稀根据误疏时变得很大.一个改进的方法是分别统计不同类型的结点的分布情况，但统计信息占用空间很大.这种方法解

决的问题是已知集合间的祖先后代关系的估价，未涉及路径中单个谓词的选择性计算问题 .

西∑, . . , . .

『 1

wF g6 T i . wo Di n i n h so r m。 me to it g a

以嘞

图 6二维直方图示例

Jn i g等人【】 a 的思想是：不同的结点映射为一维坐标上的线段，把祖先线段和后代线段的起点和长度满足某种偏序关系 .整个编码空间[mi, x分成多个小区间，把 c nc] ma然后在每个小区间内估计覆盖的线段/始点的对起数.图 7示：如所统计信息 r表示每个桶中的线段/ l起始点的对数；s表示桶的起始坐标； s表示桶的终点坐标： ws we,

表示桶中线段的平均长度；匹配的祖先.代个数在图中用表示，方法减少了稀疏分布时的误差，不能完后这种但全避免.

—∈一 l——一

∈口{叫 2

I ) MA

I () MpD

F g 7 PL h so r m n tts is i . it g a a d sa it c

图7 P直方图及统计信息 L

上述方法在计算路径选择性时，考虑有谓词约束的结点，过其他结点，只跃直接估计后代或祖先的代价，简化了计算的复杂度，在对模糊路径的代价估计中有一定的优势.与马尔可夫方法相同的是：当路径中出现多个谓词时，假设不同的谓词条件是独立的，没有计算不同的谓词之间的相关性.合哈希方法计算不同

谓词之间的相集关性，后缀树占用空间过大，是在 X但尤其 ML数据中包含大量数值时 .而查询优化的一个原则就是在有限的时间和空间内精确地估计代价.时，须对统计信息进行压缩，这必以保证优化的效率 .

孟小峰等：ML查询优化研究 X

2 8 03

5统计信息研究 . 3XML数据结构复杂，分布不均匀 .量庞大时，有限的空间内统计足够多的信息是统计信息研究的难数据在

点.当数据更新频繁时，高效的信息维护技术显得更为重要.531统计信息存储 ..

在前文介绍数值统计和数据结构抽取时，已经涉及到统计信息的存储问题，讨论集中在逻辑层，未涉及但并存储的形式. XML数据统计信息的存储结构主要有以下几种： 树或图[ -] 4 4. 0 2用于存储模式信息，在文献[2中模式树中每个结点的个数，如 4】或者文献[0中结点之间的固 4】定关系等 .由于其数据结构与 XML原始数据相同，用对数据本身的存取方法存取统计信息.可如果 X ML数据模式结点个数为 n则树方法存储的代价为 D n;, ()后缀树的存储代价为 D(! ) .马尔可夫表【用于存储路径信息，同的路径对应其在数据中出现的次数.了查找方便，:不为一般在表上再

加以一定的索引.果只统计小于 k长度的路径，如则其存储代价为 O n ) (k. 直方图【 :。关系数据库中普遍应用的一种统计信息方法.将某属性的值域划分为多个连续或不连续的部分， 分别统计不同部分区域内数据的分布情况 .简单数据，用一维直方图方法；对于采若统计相关的不同属性的分布情况。需要二维或者更多维数的直方图.在对 XML数据作统计时，主要采用直方图和树相结合的方法.如果某个结点的值为树值型，则用直方图统计这个结点数值的分布情况.文献[ 1中，于结点之间的父子关系也采用直 4】对方图的方法统计.须首先唯一地标记所有的数据结点，且，同类型结点标记的值域没有交叉 .必并不当路径中的某些点有谓词约束时，过统计信息无法知道那些满足条件的结点的标记，而无法进一步估计其后代的个数 .通从 位置直方图【 :。这是一种二维直方图，其值是离散的，结构嵌套转换为平面位置

关系 .果按类型每维分把如为七则其存储代价为 O n 2.[2等采用一维直方图方法保存结点的位置信息，需要根据结点在连接过格， (k)文献 5】但程中是祖先或后代来保存不同的统计信息，际上冗余很大.实 532统计信息压缩 -.

对直方图压缩方面的研究在关系数据库查询优化中已经有一定的研究基础，遍采用的是小波压缩 l普 j J和 DC (i rt c s e t n fr . T ds ee oi r s m) c n a o两种方法均能把直方图中大量的“”桶压缩为少量的系数，同时丢失很少的信息. 小波压缩方法在代价估计时，重新构造与查询相关的部分直方图.a[ J采用密度函数方法压缩直方图，要 Y h_等人 j 5

用数据密度函数直接模拟实际的数据的分布情况.这种方法适用于离散的或是连续的数值型数据 .树的修剪和马尔可夫表的压缩思想是从统计信息中删除对代价估计结果影响相对较少的结点.点在数结据中出现次数越少，则越缺乏统计价值.文献【1中提供了 4种不同的方法， 5】并通过实验分析了几种方法在不同

的数据分布情况和查询情况时的占用空间和代价估计精度关系，但并未得到相对稳定的方法. 533统计信息维护 ..据我们所知，目前对 XML统计信息维护的研究很少见.【4提出一种马尔可夫表的在线维护方法，思文献 5】其想是：查询开始时没有统计信息，用查询反馈逐步生成和细化统计信息.在利其细化规则有两个：重尾规则 (ev . i￣增量规￣ (et) h ayt l l a)l ld l . J a重尾规则是在计算选择性时，接近查询路径末端的路径的选择性计算加以较高给的权重 .做基于如下考虑：这样接近路径末端的路径选择性对整个路径的选择性影响更大；量规则是一种错误增减少学习方法 .[4的优点在于在线维护统计信息 .[5提出了基于 Sai]文献 5】文献 5】 tt 1 X[框架 I MAX增量维护算法，包括结构信息和值信息的增量维护，但是不易扩展到其他系统上 .

6总结及展望随着 It n t的发展， ne e r XML数据规模与日剧增，准确、高效地查询 XML数据成为目前研究的热点问题 .近年来， XML查询优化研究方兴未艾

,要集中在如下几个方面： XML代数的研究、对根据 XML代数分解查主对询语句的研究、对路径选择性估计的研究、对结构连接代价估计的研究等 .ML查询优化是一门综合性强的 X

研究领域，需要吸收众多其他技术的思想，其中对 X ML查询优化影响深刻的主要有：关系数据库查询优化技术、面向对象数据库查询优化技术、信息检索技术、数据仓库和数据挖掘技术、图像处理和压缩技术、人工智能

28 04

J u a o ow r or lfS tae软件学报 V 17 N ., c br 06 n f o1, o1 O t e 20 . 0 o

技术、概率论和统计技术等 .

从查询优化的过程来讲，ML查询优化和其他数据库查询优化技术并无不同之处. X从优化的不同环节的技术上看， XML查询优化具有其独特之处：要适应更复杂的数据结构和更灵活的变化，要适应更丰富的查询既又语义.目前对 XML查询优化的研究工作还远未成熟，有众多尚待解决的问题或需要完善的技术.仍因此，未来的 XML查询优化研究将以更广泛、更深入的方式展开 .在X ML代数研究中，一个值得重视的问题是逻辑操作与物理操作的分工不明确 .大量的工作在于制定不同

的代数标准，这些标准在风格上相去甚远，有共通性.很难而对真正执行的物理代数的研究还远远不够，而且不能形成完整的系统.另外，从逻辑代数到物理代数的转换也将是未来研究的一个重要的问题.关系数据库中一些约定俗成的启发式转换规则是在大量的实践基础上形成的.目前对 XML数据查询的而

各种不同的执行方法之间的优劣比较的工作还刚刚开始，并未形成共识性的规则 .由于 XML数据本身的灵活性，找到一些普遍适用的规律是很困难的 .今后的一段时间内，在相信会有更多的研究工作在这方面展开.复杂路径表达式选择性代价估计是 XML查询优化研究的核心问题，目前已有大量的成果 .这些研究或对数

据分布进行大量的假设，对查询表达式的复杂性加以一定的约束 .其是在相关路径选择性的研究方面，或尤仍有一

些尚待解决的关键性问题.一

直以来，统计信息维护是代价估计的基础.是，于 X但关 ML数据统计信息的维护问题的研究还处于起步

状态.由于 XML

数据统计信息在数据结构上与传统的统计信息有本质的不同，很难直接利用现有的统计信息维护的技术.由于目前在 X又 ML统计信息研究中采用了大量的压缩技术，为统计信息维护增加了难度.Naie XML Da b s t v t ae的研究是目前在 XML研究领域的一个热点， a已经出现一批相对独立的系统，这些系

统采用的查询和处理方法也将对 XML查询优化技术产生越来越重要的影响.Re e e e s rr n e:

[】 Bec Mah t R sM. r l a d ln le r r ML I: ehD, lor Ry esNoet eW3 1 ehD, lor A, y A f ma dt mo e adag baf a o a o X .n Bec Ma t A, s h a M, d. t t C ohX u r rigG o p 1 9 .— 6 ht:w w bs no de u ifs mia/ r hv/ al 9 m lor l e/ lor.d ML Q ey Wokn r u . 9 9 1 2 . t/ w d . a fr ./ o e n r c ieF l p/ t d n A Y9/ ah t s d s a i mah t p f a

[】 F rad zM, i o, ui Walr . aamo e ada er r MLq e .9 9 ht:wwwc.ela s o/ a l/ 2 en e Sme nJ S c D, de P A dt n u dl l baf n g o X ur 19 .t/ y p/ .s ll . m w de b—b c rt p c/ m1 t# l e r o is x . ml a g b a h

[】 Ka XS asom t n ( L )Ves n1 . CR cmme dt n 19 . t:ww w _ T/s 3 yM. Lt fr ai s XS T, ri, W3 eo r n o o 0 nai, 9 9 ht/ w.30 Rxl o p/ r t[】 F n hu e P F ra dzM, lo a R s Sme nJ Wa l . u r . fr a e nt sW3 rigDrf 2 0 . 4 ak a sr, e n e Mah t n r A, y M, i o, de P XQ e 1 o l ma i . C Wokn a, 0 2 r y 0 m s c tht/ t/ p: www. . r/ R/ u r - e n t s w3 o g T q e s ma i/ y c

[】 F radzM, o i JX e . adX a

h20 aamoe. C Wokn a, 0 2ht:w w. .r/R q e -aa d l 5 e n e R be . Qur 1 P t .dt d 1W3 rigDrf 2 0 .t/ w w3ogT/u r dtmo e n y 0n t p/ y/[】 MayF,66 eS B rnC Amdi M, ag .m l nigx ur .: h aa x ei c.n FetgJ, o kma nP, 6 r F Jrm, yo, e G ri I pe t q e 1 T eglxep r n eI: rya C L ce n C S me n y 0 eAb t b ulS,Ca e i o e r y MJ e i g rPG,He e ,S l e n u r A,e s r c ft e 2 t n’ Co f n Ve r e Da a Ba e .Be l:Mo g d .P o .o h 9 h I tl n .o r La g t s s y ri n ra n Ka f n b ih r, 0 3 0 7 0 0. u ma n Pu ls e s 2 0 .1 7 -l 8

[】 Mc g Abtb u, lma Q as Wio . oe A dtb s nae n ytm fr e s utrddt. I MO 7 Hu hJ i o l God n R, u s, e S D, d m JL r: aaaema g met s mircue aa SG D s e o s t R cr, 9 72() 4 6 . eod 19, 3:— 6 6 5 [】 Mc g, d m J Q e pi zt nfrX .n AtisnMP Or wsaME V lui , d nkS B o i ML, d. 8 Hu hJ Wio . ur ot ai ML I: kno , l k, ad r zP Z oi B, rde y mi o o o e esP o . ft e 2 t n’ Co f o r a geDa aBa e . i b r h: o g n Ka f n u ls e s 1 9 3 5 2 r c o h 5 h I tl n . n Ve L r t s s Ed n u g M r a u ma n P b ih r, 9 9. -3 6. y 1

[】 Jg ds 9 aa i VH, - h la S L kh n ,Ni a P p i sS P tl, r atv h AI ai , asma a L K f n e nA, aa z , a Si s aD,Wu Y m r r o eJ v a Q.Tmb r A aieXML i e: nt v

dtb s. h D ora, 02l() 7- 9 . aaaeT e VL BJunl20,14: 42 1 2 [0 Jg ds, - h laS L kh nnL Si s v T o p o Tx Ate le r r 1】 aa i VH AI ai, a sma a, r at aD, h m snK. a: ea baf h K f v a r g o XML.n G elG G an, d. I: h l, rh eG es iDa a a e P o a t b s r gr mmi g La g a e, t n’ W o k h p DBP 0 1 F a c t: p i g r Ve lg 2 0 . 4 -1 4. n n u g s 8 h I tl rs o, L 2 0 . r s a i S rn e - r, 0 1 1 9 6 a

[l Faic , ue J PuC. L: ler r I】 rsna F Ho bnG, a XA Anag baf r o XMLq e pi zt n I: huXF e. rc o elt s aai ur o t ai .n Z o, d Po. f h 3hAut l a y mi o t r sn Da bs o f( C 20 )Me o re Mo ahUnvri, 02 t aeC n.AD 0 2. l un: n s ies y 2 0 . a b t[2 Z agD, n . dt d l n ler o eWe .n Po . fh 0hItl rso nD tbs 1】 h DogYS A amo e a dag bafrh b I: rc o e1t n’ Wokh po aa ae& E pr S s ms n a t t x et yt eAp l ai n . o e c: EEE Co u e o it . 9 9. l 7l . p i to s Fl r n e I c mp t rS c e y 1 9 7I一 4

[3 Lek Hoiotl u r pi zt no ree e s utrddt.n Cu tS Mi, d. rc o eACM I MO 1】 ifeH. r na qe o t ai nodrdsmit c e aa I: le, l T es Po . ft z y mi o r u o h SG D Wokhpo h badDaaae ( b 9)P i dlha AC Pes 19 . l6 . rso nT eWe tb ss WeDB’ . hl ep i: M rs, 9 9 6一 6 n 9 a [4 Mu h p dy yP P pk nt t o Miigqe igadn

vgt ni X.n Aga l, RihK, uAHH esP o. 1】 k o ah a, a ao s i uY. xn u r n aiai MI I: rwa R Dir Ng n a n y n o n c, d. rco t 8hItl n . nDaaEn ie rn . a o e I fhel t n’ Co fo t gn e ig S J s:EEE Co ue o it. 0 2 2 5 5 . n mp trS ce 2 0 . 4—2 4 y

孟小峰等：ML查询优化研究 X

2 8 05

㈣ 5 6 7 8 9 O

P p r o, . h l a S a a i a ai s S A1 ai ,Jg ds HV, ema Wu Y A h sc l le r o ML e h ia R p r, ies y o z K f h Ni r n A, Q. p y ia ag b a f rX .T cn c l e o Unv ri f t tM ih g n 2 0 c i a, 0 2. Ch it ph d s V,Cl e,M o r o t r so i e u tS e k te G.E l a i g q re t e e a i e a h e r s i n .I J g d s vau t ue i swi g n r l d p t xp e so s n: a a i h HV,M u c S, d . n h z mi k I e s

P o . f h 9 6 ACM I r c o t e1 9 S GM OD n’ n n Ma a me t fDaa M o te l ACM r s,1 9 41 - 2 . I t1 Co e o n ge n o t. nra: P e s 9 6. 3 4 2

B nma . a Sme,We se . o s a t frsmirc rddt adXML AC SGMO R cr, 0 1 01: u e n P F W, i nJ n i ti S C nt i so e s ut e aan n n rn t u . M I D eod 2 0, () 34 - 5 7 4 .

Wo l d b C n ot m. r Wie We o s r u XML p t a g a e( ah Ve s n 1 . C R c mme d t n 9 9 t: w w. 3o gT d i ah ln u g XP t ) r o . W3 e o i 0 n ai,1 9 .ht/ w w ./ o p/ rx a h h ml p t .t

C a e l , akJ F o ec R beJ S m6 n J Sea e c XQu r .: h

mb r n D Cl, lrs uD, o i, i o, tf su M. i r n e 1 AnXML q e a g a e T c i l e o, y 0 u r l u g . eh c p r y n n aR tW o l i eW e n o i m, 3 W o k n a, 0 . rd W d b Co s r u t W C r i g Dr f 2 0 t 1

De tc F r a d z M, l r s u D, v S c u D. q r a g a e f rXM L.2 0 . t/ u s h A, e n n e F o e c Le y A, u i A ue y ln u g o 0 3 ht/ p: www.e e c .t.o -mf/ l s r s a h atc m/ r ff e/ ii 1 m1 f a.t n h

Roi L p Sh c XMLq e g a e X )h p/ w. .r/a d// L 8p/q.ml beJ apJ cahD.,, ur l u g ( QL、 t:ww w3ogT SQLQ 9/px 1 t y a n t/ n hC a el Ro i, lrs uD. i: ML q e a g a efrh trg n o sd t s u c s I: u i, se , d . h mb ri D, b eJ F o ec Qul An X u r l u g eeo e e u a o r e. n S c D Vo sn G e s n t y n o a uT e W o l i e W e d Da a a e . r n’ W o k h p W e DB 2 0 . NCS 1 9, rn e— ra, 0 .—2 . h rd W d b a t b s s 3 d I t1 n rso b 0 0 L 9 7 Sp i g r Ve l g 2 01 1 5

L Mo nB. n e ig a d q e ig X aafrrg l ah e pe so s I: esP i Q. o I d xn u r n ML d t o e ua p t x rs i . n Ap r MG, z n, eiS P rb sh, n y r n Ate i C r, a a o c iS P Ra mo a a a ma h r o K,S o g a s RT d .VL n n d r s,e s DB 0 r c ft e 2 t n’ Co .o r a g t s s 2 01,P o .o h 7 h I t1 nf n Ve y L r e Daa Ba e .Ro ma:M o g n ra Ka f n u l h r, 0 . 61 7 . u m

a n P b i e s 2 01 3 -3 0 s

[4 2】[5 2】

Ch n a C,F l e ,Ga o a a s M,Ra t giR.Efi in i e i g o eb rP r f lki so fc e g fl rn f XM L o u n s wi t d c me t t Xp t x e so s n:Ag a l R, h a e pr s i n .I h r wa

Dirc Ng t ihK, uAHH,e s P o . fh t n’ Co nDaaE gi eig a o e I EE Co ue o it, 0 2 2 5 2 4 t d . r c o te 1 hIt1 neo t n ne r .S nJ s: E mp trS ce 2 0 . 3— 4 . 8 n yW o d P 0n t ee u v ln eo o T. h q i a e c fXM L p Re s I I: o n W Ve 6 i a D, rc M a f e Ku g K, t ca P Lu s M a r . n: n J h L, r n c Ulih F, n n r d K, n— L Caus i , i P, h h , t rJS e s P o . f h s n’ n . n Co Ye os uaS Pe e , d . r c o t e 1 t t1 I Co f o mp tro mp t t n Lo i . u e n Co u a i g c LNAI 1 6,Be l S rn e— ra, o 8 1 ri n: p i g rVe l g 2 0 .1 2 l 6. 0 0 l -l 6 5

y n o f v h r o h[6 Foec L v u i Q e otim n rcnu cieq eiswt eua x rsin .n P p, d Po . fte 2】 lrsuD. eyAY S cuD. u r c na e t ojnt ure i rg l epes s I: o aL e . rc o 1 t 7 ACM I h S GACT. I S GM OD. I S GART S mp o rn i l so Da a a eS s e . a e ACM r s,1 9 . 3 -1 . y . n P i c p e f t b s y t ms Se al: P e s 9 8 1 9 48

la s n ao n eiiM On ted cd bl o u r c nanme ta e o srit.I P p e . o .o i y y n h[7 Cav e eD,Gic moGD,Le z rn . h e ia it fq

e o ti n d rc n tans n: o aL, d Pr c fte 2】1 t 7 h ACM I S GACT— I S GM OD. I S GART ymp o rn i l so Da a a e S t ms e t e ACM r s, 9 8 1 9 5 . S . n P i c p e f t b s yse .S at: l P e s 1 9 . 4 -1 8

de P A f ma sma i f a e L . r u a g a e hv, 9 92 )1 3 2 2 r o c n i r a ( [8 Wa l . r l e n t so p t r s nXS T Mak pL n u g s c ie 1 9, 2:8— 0 . 2】

[9 2】

WodP o T. i i z n i l M n mi i g smp e XPa h e pr s i n .I:Me c t x e so s n c a G,S m6 n J e s r c o h t n’ W o ks o n t e W e d i o , d .P o . ft e 4 h I t 1 r h p o h ba n Da a a e .W e DB 0 1 S t r a a ACM r s . 0 .1—1 . tb ss b 2 0 . a aBa b n r: P e s 2 01 3 8

rYa i .Ch , k h o S La s ma a n LV,S i a t v M i i z t n o e at r ue is I: e G, d P o . ft e S GM OD n rv s a aD. n mi a i ft e p te q re . n Ar fW o r n e . r c o I h[0 Ame— h sS 3】 2 01El cr n c S t r b a ACM r s . 0 4 7 5 8 0 e to i . a aBa a: n r P e s 2 01 9— 0 . .

ma n P. f c e tag rt m n mi i e p t r q e i s I: a l M,M o o r n n n l a k A,e s Pr c o e 2 0 d . o . ft 0 2 h[1 Ra n a Efi in l o ih sf rmi i zng te a e u re . n Fr k i J o n B,Ai ma i 3】 ACM I S GM OD n’ Co n M a a e n f t . a io: I t1 ne o n g me t Da a M d s n ACM e s 0 2 2 9 3 9 o Pr s,2 0 . 9 - 0 .i o lS e r yM, s ir On t n mi

a i f a h q re . n Fr y a C, c e n h on o [2 F e c Fu f r 3】 l s a S, r a o F,Ma c a iE. e m i i z t r Xp t ue is I: e t g J Lo k ma n PC,Ab t b u ,Ca e J

y ri n r a Ka f n n S l g rPG,He rA,e s ei e n ue d .VL 0 3 DB 2 0,Prc fte 2 t n’ Co f o r r g t s s o .o h 9h It1 n n Ve La e Daa Ba e .Be l:M o g u ma nP b ih r,2 0 .1 3 6 . u l e s 0 3 5—1 4 s

[3 3】[4 3】

P p o a L,De tc u s h A,S h g e Ta n n V.A h s o a? I Ch n W D, u h o F a u u t A, n e c a etof r n: e Na g t n J,Be se n PA, d .P o . f t e 2 0 n r t i e s r c o h 0 0

ACM GM OD n’ Co e o a a e e t fDa a Da l s ACM e s 2 0 . 7— 8 . SI It1 n nM n g m n o t. l: a Pr s, 0 0 2 3 2 4Kwo Ge t . c e— s do tmi ai n o ng A, rz M S h ma Ba e p i z t fXPah e p e so s Te h i a p r, i e st fCa io i, 0 . o t x r sin . c nc l Re o Un v r i o t y lf r a 2 01 n

See t y etmain a dq e o t vi y miaini a ed tb s swi hghy s e d dsrb to so ou le . n r h[5 L n hCA. lci t si to n u r pi zto n l g aa a e t i l k we itiuin fc lmnvau s I: 3】 y cBa i o ncl n F,De i ,e s 1 t n’ Co f n Ve r g t s s o g l s h W t DJ d . h I t1 4 n .o r La e Da a Ba e .L s An e e:M o g uf n b i h r,1 8 y r a Ka ma n Pu ls e s . n 982 0 2 . 4 - 51

a, wa P AN. eu nila l gpoe

ue r ur ie smain SG S q et mpi rcd rs e s t t、 I MODReo￣ 19,12: 1 30 as n o f q y zei o cr 9 22 () 4— 5、 3[6 Has JS mi 3】[7 3】Li g Y,S n W . s p lme t o s p i g b s d m e o sf rq e i e e tma in i a a a e s se n u A u p e n a t m l a e t d u r sz s i to n ad t b s y t m. n h o y ACM I S GM OD c r, Re o d

1 9, 14:2 1 . 9 22 ( )1— 5 rl ih a M,De i .Eq iDe t so rm sf re t aig s lcii a tr rmut— i n in lq e is I OD k W t DJ t u— ph hitga si t ee tvt fco sf lidme so a u re.SGM o m n y o[8 M uairs n 3】

R cr, 9 81() 8 3 . eod 18,73: -6 2 n a s J o i s iV,Lo ma o h n GM,Z a g C.S a itc ll a n n e h q e r c si g XM L q e is n: hm h n t tsi a e r i g t c niu s f o t o n u re .I B6 K,[9 Zh g N,Ha s P,J sf v k 3】J ns n CS Ha s LM,Ke se L, r s n PK, i e e, a r tn M La o Oo BC, d . o . tt e 3 s n’ Co e o r a g t s e . o d e m: e s Pr c o’ h tI t1 n n Ve L e Da a Ba s Tr n h i 1 y rACM e s 2 0 . 8 - 0 . Pr s, 0 5 2 9 3 0

2 8 06

J un lo o w r o ra f Sf ae软件学报 V 1 7 t o.,No1, tbr2 0 1 .0 Oc e 0 6 o

[0 C e Y,aa i V, o, ua Muh ki n nS N , r atv C u t gt gmace e.n Yo n C 4】 hnZ Jg ds H K r F Ko ds h u N, tu r h a, gRT Si s a s v a D. o ni th snat eI: u gD n wi i re . r c o e 1 t n’

Co f o t n i e rn . i e b r: EE Co u e o i t . 0 5 5 6 4. d P o . f h I I t1 n . n Da a E g n e i g He d l e g I E mp tr S ce y 2 01 9— 0 t 71.

[1 F e eJHaiaJ, a n t M, o, i o . t i MaigXMLcu tI: rn l , o A l k A.d . rc 4】 ri, rs R maa R yP SmdnJSa X: kn r t R h t o n.n Faki MJ Mo nB, i ma i es Po. n a O te2 0 f 0 2 ACM I h S GM OD n’ Co f o n a e e t fDa a ACM r s . 0 2.1 1 9 . I t1 n . n Ma g m n o t Pes2 0 8 -1 1.

[2 P lzt G rfl iMN. ttt a n pe r rp—t c rd 4】 oyoiN, aoaa s s k Sai i ly o ssf ahsu t e sc s og r u XMLd t ae.n Faki, o, i mai es aa ssI: r l MJ MonB Al k d. b n n a A,P o . ft e2 0 M I r c o h 0 2 AC S GM OD n’ Co f o a a me to Daa. I t1 n . n M n ge n f t ACM r s . 0 2 3 8 3 9 P es 2 0 5— 6 ..

[3 God n, d m _ tG ie: n bigqeyfr lt nadot zt ni e s u t e aa ae.n JreM. ae 4】 lma R Wio JDa ud s E a l u r omuai pi ai smi cu ddtbssI: ak C ry a n o n mi o n r t rM J Di ih KR,L c o s y F, t c r t o h v k H, u o o l sP, e s ed M A e s VL Lo c p u o J u f l d . DB’ 7 Pr c o h 3 d I t1Co f o r r e Da a 9, o . ft e 2 r n’ n . n Ve La g t y,

Ba e . h n: o g uf n n P l h r,1 9 . 3— 4 . s s At e s M r a Ka ma ub i e s 9 7 4 6 4 5 n s

[4 C e Y K m, o ds Muh ki n . e c vt smainfr o la u r sI:

o aL e. rc o te1t M 4】 h nZ, o F K u a N, tu r h a S S l t i et t oe q ei .n Pp . d Po . fh 9hAC s n ei y i o oB n eSI GM OD— I S GACT S GART S mp o rn i lso—I y . n P i c p e fDa a a e S se . l s ACM r s . 0 0 21 - 2 . t b s y t ms Da l: a P e s2 0 6 2 5.

[5 P lz t G rfl i M. t cueadv lesn pe r 4】 o oi N, aoaa s S u tr a y o ssf y s k r n u o XML dt ga h.n B es, h uhiA, e, X a p sI: rsa S C a dr B L eML YuJ, ar nLa r i e s P o . ft e2 t DB n . n n M o g u ma n P bl h r . 0 2 4 6 7 . c ox Z, d . r c o 8 h VL h Co f Ho g Ko g: r a Ka f n u i e s 2 0 . 6—4 7 n s

[6 P lzt Oaoaa iM,on iiY. eet i smainfr 4】 oyoiN, rflks Isnds S l i t et t s c v y i o o XMLt g .n Tt r, d Po . f e2 t t o fo sI: iwot F e . rco t 0hI’C n. n wi s h h n1DaaE gn eig I t n ie rn, CDE 0 4 Bo tn I EE mp trS ce, 0 4 2 4 27 . 2 0 . so: E Co ue o it 2 0 . 6— 5 y

[7 Z agN, s, o laaA, la F XS E A crt dfs adnl smainfrX a ur s I: ig L 4】 h Ozu MT Ab ung I sI. E D: cuaea atcriai et t P t q ei . n Ln . n y n y t i o o h e

A des Ky— J jnZ es Po. f e2n n’C n o aaE gn eig At t:E E C mp trS c t. 0 6 n ra R, uY W,i u, d. rc o 2 dIt1 o f nD t n ier . l a IE o ue oiy 2 0 . n a h t . n n a e61 .

[8 S h d, as, rtnML Foec

Maoec C ryMJB seR T ex e cmakpoetT cncl p r 4】 cmit AR W a Kes , l suD, n lsuI ae, us . h MLb nh r rjc. eh iaReot F e r, .I NS R01 3 CW I 2 0 . 0,, 0 1

[9 Z a gC Nag tnJ, e t D, u, oma M. nsp o igcnan n ur si rl inl aaaemaa e n 4】 h , u ho F D wi J L oQ L h n G O u p rn o timet ei n ea o a dtb s n gmet n t t q e ts se . n: e G, d Pr c o h e 2 t M I y tms I Ar fW e . o . ft 0 h AC S GM OD n’ Co f o a a e n fDa a S t r r: I t1 n . n M n g me to t . a aBa ba a ACM e s 2 01 n Pr s . 0 .4 5 3 2—4 6.

[0 wuY P tl M, aa i 5】 Q, ae J Jgds HV. s man nw rs e frXML q eisI: esnC, efr h E t t g as e i so i i z u r .n Jne S Jf y KG, o on￣, a ei S e e P kr3J Sl ns, t Be i o E,B6 m t rn h K,J r ,e s P o .o t n’ Co f n E t n i g Da b s e h o o y r g e p i g r Ve lg 0 2 a ke M d . r c f 8l I t1 n .o x e d n t a e T c n l g .P a u:S rn e - ra .2 0 1 a5 0 6 8. 9— 0.

[1 JagH, uHJW agW, uJ . nan n i sz si t n Mo es n to s I: aeyAY,vs G, a es 5】 i F L , n Y X Cotimeton ieet i: d la dme d.n H l n j ma o h v Ie Z DonA, d.Pr c o t e2 0 o. f h 0 3 ACM I S GM OD n’ Co f o a a e n fDa a S e o ACM r s . 0 3 45 5 I t1 n . n M n g me to t . a Di g: n P e s 2 0 .1—1 6.

[2 Abung Al lenA N u ho F E

t t gtesl t i f 5】 o laa A, a d e R, a gtnJ. smai e i t o me i n h e c v y xMLp t pes n r ne e saeapiai sI: a e rsi s tr t cl p l t n .n h x o f I u o c oAp r e sPM G,At e Ce iS, a a o c i S Ra mo a a a z ni P, r P r b s h , ma h n r o K,S o g a sRT. ds P o . ft e2 t n’ Co f o r r e n d s r e . r c o 7 It1 n h h . n Ve La g yDaa Ba e . ma M o g uf n n P l h r, 0 . 9— 0 . t s s Ro: r a Ka ma ub i e s 2 01 5 1 6 0 n s

【3 Mai Vt rJ Wa gM . vlt ae io a o eet i sma o .n HasL Twa , d. I 5] t sY, ie C, n Wa e - sdhs g msfrslcvt et t n I: a M, i r A e s SGMO 9, a t eB tr iy i i y D’8P o . f e AC I r c o t M S GM OD n’ Co . o a a e n f t . e tl: h I t1 nf n M n g me to Daa S ate ACM e s 9 8 4 8 5 . Pr s .1 9 . 4—4 9

[4 Lm,Wag M, ama ah nS Vie S P r X ah l re: n o—n efu igMak v hs ga o 5】 i L n P d n b a, t rJ, arR. p t e n r A nl eslt n ro io m frXML pt t a i - n tr a hs lcii si t n I:Brsa , a d r ee t t e t vy mai . n o es S Ch u hiAB,L eM L n e ,YuJ X,Lar i e s Prc ofte2 t n’ Co f o r r e cox Z, d . o . 8hI t1 n n Ve Lag h . yDa a Ba e . n n: r a u ma n P b ih r, 0 2 4 2— 5 . t s s Ho g Ko g Mo g n Ka f n u ls e s 2 0 . 4 4 3

[5 R ma ahM, h n Z Fe eJ Ice n l itn eo h mab e 5】 a n t Z agL, ri

.n rmet nec f ce—a dXMLs tt s I: n l . hfr es Po. f e r a ma s s t i i .n DoadF S ae, d. rc o asc h t

2 E t1 o fo aaE gn eig T J oI E o p tr o i,0 5 2 3 2 4 1tE EI’C n nD t n ier . o y:E EC m ue ce 2 0 . 7— 8 . sI n . n ( S t y

孟小峰 (94一),士，授，士生导 16,博男教博

王小锋 (9 0 ),士生，要研究领域 18-,硕女主为 XML数据库 .

师， F高级会员，要研究领域为 we CC主 b数据集成，ML数据库，动数据管理 . X移

王宇 (9 3,,士，要研究领域为 17一)女博主W e据管理 . b数 XML数据库 .

本文来源：https://www.bwwdw.com/article/6vai.html