（计算机应用技术专业论文）xml路径查询处理关键技术研究.pdf

摘要 随着i n t e m e t 时代的到来，网络在人们的生活中发挥着越来越重要的作用，在众多 的领域中有着广阔的应用前景。作为w e b 所带来的新技术发展中的代表，x m l 成为了 学术界和工业界所关注的焦点。由于x m l 数据具有不同于传统数据形式的特点，以及 基于w e b 的应用环境特点，使得传统的数据库技术不能或不能有效地发挥作用，因此 需要针对其特点研究新的处理方法。 查询是数据处理中最重要的问题之一，对x m l 数据也是如此。为了解决x m l 路 径查询处理中的关键技术问题，为大规模的x m l 查询应用提出切实可行的解决方案， 本文结合o r i e n t x 系统提出了路径查询的处理框架，对三个方面的关键技术进行了研 究，提出了自己的方法， 本文针对结构连接操作的高效实现问题，提出了基于划分的结构连接算法。作为 x m l 查询处理的核心操作，结构连接操作的高效实现是提高查询处理效率的关键。在 x m l 数据区域编码的基础上，我们提出了一种基于划分的结构连接算法。与目前已有 的算法不同，该算法不要求数据有序或索引的存在等前提条件。它基于任务分解的思想， 根据编码的覆盖区间对元索节点进行划分，在划分所得到的对应子集合之间分别进行结 构连接。我们提出了划分子集合的原则，给出了具体的结构连接算法，并在各种数据集 上进行了广泛的实验。实验结果显示该算法具有良好的j 硅能，而且在各种数据分布情况 下具有稳定的表现，以及良好的可扩展性。 在路径索引方面，本文提出了提出了一种基于模式的路径索引s u p e x s c h e m a g u i d e dp a t h i n d e x f o r x m l 。该索引利用了在实际应用中经常存在的x m l 数据的模式信 息d t d ，从d t d 出发构建索引结构，总结了符合d t d 的x m l 数据可能出现的路 径结构。我们对该索引的整体结构，索引的构建过程，以及索引支持的查询方式进行了 详细阐述。通过结合x m l 数据的编码，该索引可以支持多种查询方式，包括绝对路径 查询，父子关系和祖先后代关系的基本结构关系，福对路径查询等，从而能够有效地 支持路径表达式的计算。x m l 数据编码的引入使得查询结果可以进一步用于路径表达 式的计算。 在路径查询的计算方面本文提出了以目标节点为导向的路径查询分解计算框架。 基于基本操作和索引的支持，我们定义了对路径查询树的最小简单路径分解。从查询分 解状态向查询计划转化的过程遵循以目标节点为导向的原则，尽量保证每个连接的绌 果是在下一步将要使用的，避免中间结果的传递。针对这个查询分解计算框架，我们提 出了一些扩展的操作符，包括选择性结构连接操作和扩展的索弓l 查询操作，并给出了具 体的实现方法。结合实际的查询计算需求，这些扩展的操作符可以直接在查询中应用。 本文的工作是在n a t i v ex m l 数据管理原型系统o r i e n t x 的基础上进行的，所提出 摘要 的许多技术在系统中得到了应用。大量的实验都在原型系统的基础上进行。 关键词：x m l ，路径表达式，编码方法，结构连接，路径索g i i a b s t r a e t r e s e a r c ho ak e y t e c h n i q u e s o fp a t h e x p r e s s i o nq u e r yp r o c e s s i n gf o rx m l w a n gj i n g ( c o m p u t e ra p p l i c a t i o nt e c h n o l o g y ) d i r e c t e db y w a n g s h a h w i t ht h ea d v e n to f i n t e r n e t ，n e t w o r kp l a y sa ni m p o r t a n tr o l ei np e o p l e sl i v e s ，a n dw i l lb e a p p l i e di nm o r ea n dm o r ea r e a s x m lh a sb e c o m et h ef o c u so fr e s e a r c ha n di n d u s t r i a l c o m m u n i t i e sa st h e r e p r e s e n t a t i v e o fn e wt e c h n o l o g i e so nt h ew e b t r a d i t i o n a id a t a b a s e t e c h n o l o g i e s c a l l tw o r ke f f i c i e n t l y o w i n gt o t h et r e e l i k en a t u r eo fx m ld a t aa n dn e w a p p l i c a t i o ne n v i r o n m e n t n e wt e c h n o l o g i e ss p e c i a l l yd e s i g n e df o rx m l d a t aa r en e e d e dt o p r o c e s sx m l d a t a e f f i c i e n t l y q u e r y i so n eo ft h em o s ti m p o r t a n ti s s u e si nd a t a p r o c e s s i n g i nt h i sp a p e r , w ef o c u so n t h e p a t he x p r e s s i o n p r o c e s s i n g s u c ht h a tt h e k e yi s s u e s i nt h e l a r g e s c a l e x m l q u e r y a p p l i c a t i o n c a nb es e t t l e db yf e a s i b l ea p p r o a c h e s w e p r o p o s e ap r o c e s s i n gf r a m e w o r ko f p a t h e x p r e s s i o n si n t h en a t i v ex m ld a t am a n a g e m e n ts y s t e mo r i e n t x ，f o c u s i n go nt h r e ek e y t o p i c s ：s t r u c t u r a lj o i na l g o r i t h m ，p a t hi n d e x ，a n dp a t hq u e r yd e c o m p o s i t i o n w e p r o p o s ear a n g ep a r t i t i o nb a s e da l g o r i t h mt oi m p l e m e n ts t r u c t u r a lj o i n a st h ec o r e o p e r a t i o no fx m lq u e r yp r o c e s s i n g ，t h ee f f i c i e n ti m p l e m e n t a t i o no f s t r u c t u r a lj o i ni st h ek e y t oi m p r o v ex m l q u e r yp r o c e s s i n g b a s e do n t h er e g i o nn u m b e r i n gs c h e m eo fx m l d a t a ，t h e m a i ni d e ao fo u ra l g o r i t h mi s p a r t i t i o n i td i v i d e st h ei n p u te l e m e n ts e t si n t os e v e r a ls u b s e t s a c c o r d i n gt ot h ec o d i n gr e g i o n ，a n dp e r f o r m sj o i no p r a t i o n sb e t w e e nc o r r e s p o n d i n gs u b s e t s d i f f e r e n tf r o mp r e v i o u sa l g o r i t h m s ，t h i sa l g o r i t h md o n tr e q u i r et h ea s s u m p t i o nt h a tb o t ht h e i n p u te l e m e n ts e t sa r es o r t e do rh a v ei n d e x e s w ep r o p o s et h ep a r t i t i o nr u l e ，a n dd e s c r i b et h e c o n c r e t ea l g o r i t b a n s t h er e s u l t so fo u rc o m p r e h e n s i v ee x p e r i m e n t ss h o wt h a to u ra l g o r i t h m p e r f o r m sw e l lo n b o t hs y n t h e t i ca n dr e a l w o r l dd a t a s e t s ，a n dh a sg o o d s c a l a b i l i t y w e p r o p o s ea n e ws c h e m ab a s e dp a t hi n d e x s c h e m ag u i d e dp a t hi n d e xf o rx m l d a t a ( s u p e x ) a l t h o u g hs c h e m ai sn o tm a n d a t o r yi nx m ls t a n d a r d ，d t d so f t e ne x i s ti n p r a c t i c a la p p l i c a t i o n s s u p e xd e r i v e si n d e xs t r u c t u r ef r o ms c h e m ai n f o r m a t i o no fd t d ，a n d s u m m a r i z e sa l l p a t h st h a tw i l lp o s s i b l ya p p e a ri nx m l d a t ac o n f o r m i n gt ot h i sd t dw e d e s c r i b et h ea r c h i t e c t u r eo fs u p e xi nd e t a i l ，a n dg i v et h ep r o c e d u r eo fc o n t r u c t i n gi n d e x s t r u c t u r e s u p e xc a r l s u p p o r ts e v e r a lw a y so fq u e r yi n c l u d i n ga b s o l u t ep a t he x p r e s s i o n ， r e l a t i v ep a t he x p r e s s i o n ，a n db a s i cs t r u c t u r a lr e l a t i o n s h i p s t h er e s u l t so fi n d e xq u e r yc a nb e u t i l i z e di nf u t u r eq u e r y p r o c e s s i n gd u e t ot h ec o d i n gi n f o r m a t i o ni ni n d e xr e c o r d s w e p r o p o s eae v a l u a t i n gf r a m e w o r ko fp a t he x p r e s s i o n sw h i c hi sg u i d e db yt h et a r g e t n o d ei nq u e r yp a t t e m w ed e f i n et h em i n i m a ls i m p l ep a t hd e c o m p o s i t i o no fq u e r yp a t t e r n b a s e do nb a s i c o p e r a t i o n s a n di n d e x q u e r y t h ep r o c e d u r e o f t r a n s f o r m i n gq u e r y d e c o m p o s i t i o ns t a t et oq u e r yp l a nt r i e st oe n s u r e t h a tt h er e s u l t so fa no p e r a t i o nc a nb eu s e di n i n a b s t r a c t t h en e x ts t e ps ot h a tt h et r a n s m i s s i o no fi n t e r m e d i a t er e s u l t sc a l lb ea v o i d e d i na d d i t i o n w e d e f i n es o m ee x t e n d e d o p e r a t i o n si n c l u d i n gs e l e c t i v es t r u c t u r a lj o i na n di n d e xq u e r y ，a n d d e s c r i b et h ec o n c r e t ea l g o r i t h m s t h e s eo p e r a t i o n sc a nb eu s e di n q u e r yp l a na c c o r d i n gt o a c t u a lr e q u i r e m e n t o u rw o r ki nt h i s p a p e ri s b a s e do nt h en a t i v ex m ld a t a m a n a g e m e n ts y s t e m o r i e n t - x ，a n dm a n ya p p r o a c h e sd e s c r i b e da r eu t i l i z e di nt h i ss y s t e m a l lt e s t i n gs y s t e m sa r e b u i l to n t o po f o u rp r o t o t y p es y s t e m k e y w o r d s ：x m l ，p a t he x p r e s s i o n ，n u m b e r i n gs c h e m e ，s t r u c m r a lj o i n ，p a t hi n d e x 独创性声明 本人声明我所呈交的论文是我个人在导师指导下进行的研究工作及 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外论 中不包含其他人已经发表或撰写过的研究成果。与我一同工作的刚志对 文所做的任何贡献均已在论文中作了明确的说明并表示，谢意。 作者签名：王静日期：_ 2 。；r ” 关于论文使用授权的说明 中圈科学院计算技术研究所自权保留送交论文的复印件，允许论文 查阅和借阅；并可以公布论文的全部或部分内容，可以采用影印、缩印i 其言复制手段保存该论文。 作者签名：王静导师签名：砂朝时 日期：型。3 譬垃 第一章引言 第一章引言 近年来，网络技术的迅速发展远远超出了人们的想象，i n t e m e t 已经成为了人类生 活的重要部分，成为了重要的信息来源和交换媒介。x m l 作为新一代的网络数据形式， 受到了人们的普遍关注。如何实现对大规模x m l 数据的有效管理和利用，有效支持不 断涌现的各种新型w e b 应用，成为了备受关注的研究热点。本文针对x m l 数据的路径 查询处理问题进行了深入的研究，为有效解决大量x m l 数据的查询问题提供了有效的 解决途径。 1 1 x m l 数据的产生和发展 i n t e m e t 的迅速发展，使其成为了信息传递与共享的最重要和最具潜力的媒介。在 i n t e m e t 上存在着大量内容丰富的的数据，这些数据的内容包罗万象，包括数字图_ f 馆， 电子商务数据新闻，生活资讯等等，覆盖了人类知识的各个方面，而且形式各异，具 有不同的表现形式，如文本文件，多媒体文件，h t m l 文档，各种数据库等。它们与传 统的数据形式存在着明显的不同，具有面向显示，结构灵活，形式多样，动态变化，以 及数据海量等特点。除了数据的新特点以外，应用需求也有许多新的特点。不断涌现的 叛型w e b 应用，如网上购物，网络银行，数字图书馆，电子商务，远程教育等。提出 了许多新的数据处理要求，原有的最普遍的信息浏览功能不再能满足人们的需求。如何 管理w e b 上的大量信息，以满足用户对信息的需求，成为了一个非常迫切的研究课题， 为传统的计算机科学技术提出了新的方向。 w e b 数据管理的研究吸引了来自许多研究领域的研究人员，其中来自数据库领域的 研究人员近年来试图从数据库的角度，运用数据库中的许多概念来解决w e b 数据管理 中的问题。数据库技术经过经过二三十年的发展，己经较为成熟，但它所研究的对象是 规则的，具有良好结构的数据，而w e b 上数据的高度不规则性，灵活多变的特点使得 数据库技术的运用非常困难。w e b 数据的灵活多变与商效的管理和查询之间似乎存在着 不可逾越的鸿沟，x m l 的出现为问题的解决带来了新的契机。 x m l ( e x t e n d e d m a r k u pl a n g u a g e ) 旧p s m 0 0 是w 3 c 在1 9 9 8 年制定的一项标准， 用于网上数据交换。它是通用标记语言s g m l i s o8 8 7 9 的一个子集，是一种元语言， 用户可以定义自己的标记，用来描述文档的结构。与w e b 上已有的最普遍的数据表现 形式h t m l 相比，x m l 具有如下的些特点： ( 1 ) 更多的结构和语义。x m l 侧重于对文档内容的描述，而不是文档的显示。用户 自定义的标记描述了数据的语义，便于对数据的理解和机器的自动处理。 ( 2 ) 可扩展性。x m l 允许用户自己定义标记和属性，可以有各种定制的数据格式。 中国科学院博士学位论文m l 路径查询处理关键技术研究 ( 3 ) 简单易用。与通用标记语言s g m l 相比，x m l 简单易用，便于掌握，这是它得 以推广的重要原因。 ( 4 ) 自描述性。x m l 将对数据的语义描述和数据内容本身都包含在x m l 文档中，使 数据具有很大的灵活性。 ( 5 ) 数据与显示分离。x m l 所关心的是数据本身的语义，而不是数据的显示方式， 所以可以在同样的x m l 数据上定义多种显示形式，非常灵活。 x m l 的这些特点使得它不但迅速成为了网络数据交换的事实标准，而且正在逐渐成为 数据表示的标准。随着它的流行，一系列相关的标准( 如x m ls c h e m a ，x q u e r y ，x m l d a t am o d e l 等) 也不断出现，形成了围绕x m l 的标准集合，这反映了工业界对x m l 的巨大支持。越来越多的w e b 应用，如电子商务，数字图书馆，信息服务等采用x m l 作为数据表现形式，也有很多的网站采用x m l 作为信息发布的形式，可以预见到将有 越来越多的x m l 数据出现在h l t e m e t 上。 由于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 数据模式的研究，x m l 查询语言，x m l 查询处理和优化，及x m l 数据 的高效存储和索引等等。 在x m l 数据处理的众多问题中，数据的查询是非常关键的一个。针对x m l 这种 树状数据的查询，学者们已经提出了多种x m l 查询语言，如x m l q l d f f + 9 8 1 ， x q l r l s 9 8 ，q u i t r c f 0 0 ，及x q u e r y c f r + 0 1 等。x q u e r y 是w 3 c 所推荐的x m l 查询语言标准，它能够表达对各种x m l 数据源的查询。这些查询语言尽管各有特点， 但它们的一个共同特点是都将路径表达式作为其核心内容，用户可以用路径表达式来描 述在x m l 数据层次中的定位。x m l 查询中的路径表达式可以表现为树状的查询，既能 2 第一章引言 独立地描述查询要求，又可以在查询语言中描述变量绑定。例如，“b o o k t i t l e = “b l u e m o u n a i n ” a u t h o r ”要找到t i t l e 为“b l u em o u n t a i n ”的b o o k 的a u t h o r 。这样的路径查询 的处理x m l 查询处理中最关键的问题之一。 计算路径查询最直接的方法就是对x m l 文档树进行遍历，即从根节点出发，沿着 树中的边搜索，寻找匹配路径表达式的节点。这种“一次一元组”的方法是非常低效的， 当存在不确定路径时经常会对整个树进行遍历。为了提高路径查询匹配的执行效率，人 们提出了多种导航的遍历方式 g m w 9 9 ，包括自顶向下，自底向上，以及两者结合的方 式， g w 9 7 ，m w 9 9 对路径查询匹配的优化进行了研究，提出了借助模式信息和索引的 优化方法。虽然这些方法可以在一定情况下改进路径匹配的效率，但由于导航方式的本 质缺陷，查询效率不能得到根本保障。 因为导航方式的低效，人们开始从另一思路寻求路径查询的高效计算，其主要思想 是将一个复杂的查询模式分解成为若干个简单的查询片段，首先计算简单查询片段，然 后将基本的匹配结果组合起来生成最后的查询结果。这种处理策略适用于不同的x m l 数据存储，包括n a t i v e 的系统和关系系统。这种“一次集合”的策略适合大规模数据 的处理。基于这种处理策略，需要研究的问题很多，包括查询片段的有效计算，中间结 果的高效组合操作，路径查询的分解策略等。与实际系统需求相结合，解决这些关键技 术问题，实现路径查询的高效处理，是实现大规模x m l 数据查询的关键。 本文结合n a t i v ex m l 数据管理系统，对x m l 路径查询处理中的关键技术进行了 研究，提出了路径查询处理的框架。对这些问题的研究在理论和实践上具有重要的意义： ( 1 ) 对应用需求的回应。 大量x m l 数据的出现，应用数目的增多对x m l 数据的查询提出了新的要求，需 要高效的查询处理技术。作为x m l 查询的核心内容，路径查询是查询效率的决定因素。 研究高效的路径查询处理技术可以对大规模x m l 数据的查询需求提供有力的支持。 ( 2 ) 具有较高的学术价值。 由于x m l 数据与传统的数据形式存在许多差异，传统的数据处理技术不能有效地 支持该种形式的数据，数据处理的各种关键技术需要在新的环境下根据数据的新特点重 新考虑。结合x m l 数据特点和应用需求。路径查询处理中的许多关键技术有待进一步 的研究，对其他相关领域也有巨大的影响。 ( 3 ) 目前该领域的研究仍处于起步阶段。 尽管近年来学者们在x m l 路径查询处理方面进行了研究工作，取得了一些研究成 果，但总体上来说，这个领域的研究工作仍然处于起步阶段，在该领域仍有较大的研究 空间。 1 3 国内外研究现状 国际上对w e b 数据管理的研究始于九十年代中后期，是随着i n t e r n e t 的发展而逐 中国科学院博士学位论文- - x m l 路径查询处理关键技术研究 步发展起来的。近年来，随着x m l 逐渐成为被广泛接受的数据表现形式，关于x m l 数据 处理的研究也逐渐成为了研究的热点，吸引了众多的学者，受到广泛的关注。国外许多 著名的大学和研究机构都在从事该领域的研究工作，如s t a n f o r d 大学，w i s c o n s i n 大学， b e l l 实验室，法国的i n r i a 研究所等。国内的中国人民大学、东北大学、复旦大学等也 在该领域进行了大量的工作。在各种大型的国际学术会议( 如i c d e 、v l d b 、s i g m o d 等) 上，该领域相关的论文占了相当比重，有关的学术交流也非常活跃，此外许多面向 该领域的国际会议也逐渐发展，如w e b d b ，w i s e ，w a i m 等。 在x m l 数据处理的研究领域中，有许多问题受到人们的关注，如x m l 数据的高效 存储，索引机制，查询处理和优化等。目前有大量的研究工作集中在瑚l 数据的关系 存储，以及由此产生的关系数据的x m l 发布，x m l 视图机制等方面。此外，x m l 数据 更新，数据压缩，x m l 数据过滤和发布等方面也都有学者在从事研究。 路径表达式作为x m l 查询语言的核心内容，其高效处理是倍受关注的研究热点。 对路径查询处理问题的研究在半结构化数据的领域中就已经开始，g m w 9 9 针对路径 表达式的导航式匹配，提出了多种导航遍历方式，g w 9 7 ，m w 9 9 1 对路径查询匹配的 优化进行了研究，提出了借助模式信息和索引的优化方法。随着x m l 数据的出现， 路径查询处理的研究更为活跃，取得了许多的研究成果，主要包括如下的方面： x m l 数据编码 如果对x m l 文档树中的节点进行了有效的编码，节点之间的结构关系就可以根据 它们的编码进行快速判断。目前已经提出的编码方法可以分为三类：区域编码 z n d + o l ， a j k + 0 2 ，d i e t z 8 2 ，l m o l l ，完全树编码 l y y 9 8 ，w j l y 0 3 】，和路径前缀编码 l y y 9 8 。 区域编码是目前应用最普遍的一类，它根据元素节点在树中的位置来给节点编码，主要 的方法有( s t a r t ，e n d ) z n d + 0 1 ，a j k + 0 2 】，( p r e o r d e r , p o s t o r d e r ) d i e t z 8 2 ，以及( o r d e r , s i z e ) l m 0 1 1 。节点编码是采用“一次一集合”处理策略的基础。 结构连接算法 结构连接操作作为x m l 路径查询处理中的核心操作，其效率对查询的效率有决定 性的影响。针对结构连接操作的高效实现，近年来多种结构连接算法被提出。目前已经 提出的算法大致可以分为两类：排序合并 z n d + 0 1 ，l m 0 1 ，a j k + 0 2 ，a j k m + 0 2 。 j l w c 0 3 1 ，和划分方法 w j l y 0 3 】。排序合并类的算法依赖于一定的前提条件：数据集合 是有序的，或者集合上存在索引。这些算法在数据有序和存在索引的情况下有着很好的 性能，但当条件不成立时需要临时对数据排序或建立索引，从而算法的效率大大降低。 f a j k + 0 2 r 扫提出的s t a c k t r e e 类的算法是排序合并类算法的典型代表， a j k m + 0 2 并n j l w c 0 3 针对该算法的缺点分别提出了特定索引结构来改进算法的效率。划分类的方法 目前只有 w j l y 0 3 1 ，它所提出的算法只适用于其所提出的p b i l r e e 编码，而不能应用于 被广泛采用的区域编码方法，应用范围非常有限。 路径索引 路径索引作为支持路径表达式查询的重要手段，在面向对象数据库和半结构化数据 4 第一章引言 领域中已经被提出，半结构化数据研究领域中的代表性研究工作有d a t a g u i d e g w 9 7 1 ， t - l n d e x m s 8 0 等。结合x m l 数据的特点，路径索引的研究工作进一步得到了发展。基 于树状的数据模型，伯克利大学的x s e t z j 9 9 提出了内存中的层次索引结构，f c s f + 0 1 1 提出了对x m l 文档树中从根到叶的路径进行编码形成字符串，用索引结构i n d e x f a b r i c 来对字符串进行索引的方法。在考虑元素间参照关系的前提下，a ( k ) 一i n d e x k s b g 0 2 强 调了路径的局部相似性，而 c m s 0 2 研究了如何动态地结合查询负载来构建和更新路径 索引，提出了一种适应性的路径索引a p e x 。k b n k 0 2 针对分支路径查询问题，提出 了一些规则来限制索引所支持的分支路径表达式的范围，从而减小索引的规模，取得更 好的实际性能。目前已有的这些方法着重强调对数据中路径分布的描述，而没有将路径 索引看作路径查询处理的有机组成部分，为路径查询的计算提供支持。 其他 针对路径表达式分解的问题，f l m 0 1 】中提出了对正则表达式的一套分解规则， f c f g r 0 2 从信息过滤的角度研究了如何对路径查询进行分解，建立对路径查询的索引。 【w p j 0 3 针对结构连接的顺序选择问题提出了多种优化算法。此外， b k s 0 2 和 l w y + 0 2 分别从整体树状连接和自动机理论的角度研究了路径查询的匹配问题。 尽管针对路径查询研究的各个方面都已经取得了很多成果，但仍存在许多问题需要 迸一步研究，特别是如何将各个关键技术结合起来形成完整的处理机制。 在研究工作开展的同时，各种原型系统的开发也在进行，w i s c o n s i n 大学的x m l 数 据搜索引擎n i a g a r a ，法国i n r i a 研究所的x m l 数据仓库x y l e m e ，及m i c h i g a n 大学的 n a t i v ex m l 数据管理系统t i m b e r 等都是具有代表性的项目。除了研究领域的活跃工作 以外，工业界也进行了大量的工作。目前主流的数据库厂商如o r a c l e ，d b 2 ，m i c r o s o f t 和s y b a s e 都在其原来的数据库系统的基础上进行功能扩充，开发出了支持x m l 的数据 库产品，如o r a c l e9 i ，d b 2 ，s q l s e r v e r2 0 0 0 等。此外还有许多厂商从事专门针对x m l 的数据管理系统的开发，其中典型的代表是t a m i n o 。 1 4 论文主要工作和创新 本人在攻读博士学位期间主要从事x m l 数据处理技术的研究工作，参加了n a t i v e x m l 数据管理原型系统o r i e n t - x 的设计和开发工作。 由于x m l 路径查询处理是x m l 数据处理中的重要问题，它一直是学术界和工业 界关注的热点之一。本人选择“x m l 路径查询处理关键技术研究”作为博士论文题目 的目的是为了研究x m l 路径查询处理中的关键技术问题，为大规模的x m l 查询应用 提出切实可行的解决方案。 本文结合n a t i v ex m l 数据管理系统o r i e n t x 中的路径查询处理框架，研究了主要 中国科学院博士学位论文- - x m l 路径查询处理荧键技术研究 的关键技术问题，主要工作和创新点如下： 1 结构连接操作是x m l 查询处理中的核心操作，它的高效实现是提高查询处理效 率的关键。目前已经提出的结构连接算法主要是基于排序合并的算法，它们依赖 ，于输入集合有序或存在索引这样的前提条件，适用范围有限。当前提条件不成立 时，算法的效率就会大大下降。针对这个问题，本文研究了不要求前提条件，适 应各种输入数据情况的结构连接操作实现方法，主要内容包括： i 基于x m l 数据的区域编码，提出了根据元素节点编码对节点进行划分的两 种策略。这两种策略分别对输入数据集合进行相互覆盖和不覆盖的划分，实 现对结构连接任务韵分解。 i i 基于改进的节点编码划分原则，提出了一种基于划分的结构连接算法。该算 法不要求数据有序或索引的存在等前提条件，可以应用于各种输入数据情 况。算法的设计针对可用内存大小和磁盘i o 进行了优化具有较好的i o 性能。 缸 针对可以装入内存的子集合结构连接问题，提出了多种连接算法，对其执行 效率进行了分析。 ；v 通过在各种数据集上的广泛实验和与代表性算法的比较，说明了基于区域划 分结构连接算法的有效性，良好的适应性和可扩展性。 2 路径索引为路径查询计算提供了不可缺少的查询支持，在整个的计算框架中起 着关键性的作用。目前已有的路径索引的研究工作倾向于描述数据中的路径分布 情况，支持不同类型的路径表达式查询。结合o r i e n t x 系统中的路径查询计算 框架，本文以为x m l 路径查询计算提供有效支持为目的，对路径索引进行了研 究，提出了一种基于模式信息的路径索引s u p e x s c h e m ag u i d e dp a t hi n d e x f o r x m l ，主要内容包括： i 针对查询需求，设计了完整的索引结构，包括p a t hd i r e c o r y ，e l e m e n tm a p ， 以及具体的索引记录结构。 i i 给出了从模式信息出发的索引构建方法。利用在实际应用中经常存在的 x m l 数据的模式信息d t d ，根据相应的转换规则，可以生成s u p e x 的整体结构，描述所有可能出现的路径结构。在实际数据装入时，索引结构 随数据情况进行调整。 越在x m l 数据编码的基础上，设计了支持多种索引查询方式，包括绝对路径 查询，父子关系和祖先后代关系的基本结构关系，相对路径等，可以有效 地支持路径表达式的计算，其结果可以进一步用于路径表达式的计算。 i v 通过大量的实验说明了索引方法的有效性。 3 目前的路径查询处理研究工作主要关注单个技术问题，没有对整体的计算框架给 与更多的考虑。在对结构连接操作和路径索引研究的基础上，本文研究了以目标 节点为导向的路径查询分解计算框架，对查询片段的选择，路径的分解，查询计 6 第一章引言 划的选择等问题进行了探讨，给出了解决方案，主要内容包括： i ， 给出了若干简单路径划分的规则，通过对最小简单路径分解的定义，实现对 路径查询树的分解。 i i 基于以目标节点为导向的原则，提出了一组扩展的基本操作符，并给出了路 径查询计划的选择策略。 i i i 针对扩展的基本操作符( 包括选择性结构连接操作和扩展的索引查询操作) ， 给出了具体的实现算法。 1 5 论文组织安排 本文对x m l 路径查询处理中的关键技术进行了深入的研究和阐述，全文的组织结 构如下： 第一章是引言，介绍了x m l 数据产生和发展的背景，x m l 路径查询处理的研究背 景和意义，国内外的研究状况，以及本文的主要研究工作和组织安排。 第二章对x m l 数据处理领域的目前的研究工作现状进行了综述，着重介绍了x m l 数据的路径查询处理技术，分析了目前提出的方法以及存在的问题。 第三章对x m l 索引技术给出了一个综述，给出了基本的概念，介绍了目前的研究 工作，并分析了存在的问题。 第四章首先介绍了x m l 数据的数据模型，路径查询模型，以及一些相关概念，然 后在简要介绍n a t i v ex m l 数据管理系统o r i e n t x 的基础上，提出了o r i e n t x 系统路径 查询处理的整体结构，指出了其中的关键技术问题。 第五章首先介绍了x m l 数据编码和结构连接的基本概念和相关研究成果，然后基 于被广泛采用的区域编码，提出了一种新的基于划分的结构连接算法。该章针对区域编 码的特点，提出了对输入集合的划分原则和改进的划分原则，以及相应的具体算法。该 算法不要求数据有序或索引的存在等前提条件，能够适用于各种数据分布的情况。此外 还通过实验说明了该方法的高效性和可扩展性。 第六章针对x m l 查询中路径表达式的计算，提出了一种基于模式的路径索引 s u p e x 。该章描述了路径索引的整体结构，索引的构建过程，以及索引支持的查询方式。 索引的结构包括p a t hd i r e c t o r y ，e l e m e n tm a p ，以及具体的索引记录，具体阐述了索引 包括的具体内容。此外，索引的构建过程该索引利用了在实际应用中经常存在的x m l 数据的模式信息d t 【) ，从d t d 出发构建索引结构，总结了符合d t d 的x m l 数据 可能出现的路径结构。通过结合x m l 数据的编码，可以支持多种查询方式，包括绝对 路径查询，父子关系和祖先一后代关系的基本结构关系等，从而有效地支持路径表达式 的计算。 第七章研究了路径查询的计算框架问题。该章结合结构连接和路径索引的支持，提 中国科学院博士学位论文- - x m l 路径查询处理关键技术研究 出了路径表达式分解计算的框架，具体阐述了查询树的分解过程和执行计划的选择。此 外，对扩展的基本操作符进行了详细描述。 第八章对本文工作进行了总结，说明了本文的主要贡献和创新，以及进一步的研究 工作。 第二章x m l 数据处理技米的相关研究 第二章n m l 数据处理技术的相关研究 随着x m l 标准被越来越多的应用领域所采纳，i n t e m e t 上的x m l 数据规模正在飞 速增长。由于x m l 数据模型不同于传统的关系或对象模型，其灵活性和复杂性导致了 许多新问题的出现，x m l 数据处理技术成为了数据库，信息检索，及许多其它相关领 域研究的热点。作为一个具有挑战性的新兴研究领域，许多新的研究方向不断涌现，包 括x m l 数据的存储和索引，查询处理和优化，统计信息维护，数据发布，及x m l 数 据压缩等。本章介绍了目前相关领域的研究现状，以及已经取得的主要研究成果，重点 阐述了路径查询相关的技术。 2 1x l v l l 领域的研究工作 由于x m l 数据的灵活和复杂，许多不同于传统的研究领域的问题不断出现。x m l 数据管理涉及的问题非常多，j e n n i f e r w i d o m 在 w i d o m 9 9 】中指出了一些研究方向，包括 x m l 的数据模型和理论研究，x m l 数据模式的研究，x m l 查询语言，x m l 查询处理 和优化，及) a l 数据的高效存储和索引等问题。本节概要介绍x m l 领域的一些研究 工作。 2 1 1 l l 相关的标准集合 x m l 的发展与以前的新兴技术的发展不同，它不是由研究领域提出并推广的，而 是从工业界发展起来的。随着它的流行，一系列相关的标准( 如x m ls c h e m a ，x q u e r y ， x m l d a t a m o d e l 等) 也不断出现，围绕x m l 的一系列标准集合形成了x m l 数据表示 和处理的基础，人们也在致力于将研究成果用于改进目前的标准或提出新的标准以更好 地支持应用。目前的标准主要包括如下几个方面： ( 1 ) x m l 数据模型 x m l 数据与半结构化数据非常类似，所以x m l 数据可以被看成是半结构化数据的 特例。但由于x m l 是一种文档标记语言，它具有自身的一些特点，如x m l 元素的有 序性，文本与元素的混合等，使得半结构化数据模型不能很好地描述x m l 的特征。为 了描述x m l 数据，需要提出新的数据模型。目前还没有公认的x m l 数据模型，w 3 c 已经提出的有：x m li n f o r m a t i o ns e t c t 0 1 ，x p a t h l 0 d a t a m o d e l c d 9 9 ，d o m m o d e l h h w + 0 0 和x m lq u e r yd a t am o d e l f m 0