（计算机软件与理论专业论文）基于结构索引的高效xml查询处理方法.pdf

沦文独创挫声爨 本毒仑文是我个人在导嬖萋据导下妻夔季= ：l 二载磋究互 乍及取褥浆磅究成暴。论文中除 了特别加以标注和致谢的地方外，不包含其他人或其它机构已经发表或撰写过的 研究戒桑。其稳间恚对拳研究的启发和所徽的贡献均已在论文中作了明确的声明 并表示了谢意。 作者签名_ 趑日期： 论文使用授权声明 翟霸。6 本人完全了解复旦大学有关保留、使用学位论文的舰定，即：学校有权保留 送交论文的复露俘，允许论文被查耀程借阙；学校可以公蠢论文戆全邦或部分内 容，可以采用影印、缩印或其它复制手段保存论文。保密的论文在解密后遵守此 怒定。 俸密签名：导雾器签名： ；2 z 基羯： x 砷童# 。丢 基于结椒索0 l 鹑囊效x m l 囊诲她理方法辅簧 摘要 殓沤，跫经戏为瓣终上数鬃表承帮交换静逶用标准。隧蓑跫啦黪应蹋越来越 广泛，对x m l 查询效率的要求也越来越毫。模式捉甄配怒x m l 查诲的核心操 作，在高效处理模式树匹配的各种方法中，缩构化连接算法最为流行。i b k s 0 2 i 巾提凼的结构化连接算法t w i g s t a e k 可阻对模式树迸秤整技连接，避免了二元连 接孛茏用黪串溪结栗。蠢予t w i g s t a c k 算法静高效稳寇易兼容等特点，穰多研究 王作在它的基础上进行了优化。t w i g s t a e k 算法毂i o 秘e p u 牙锬与输入x m l 嚣 索的数量密切相关，所以提高算法效率的一个可行方法是在算法开始之前筛掉尽 麓多韵无用结点。一些工作使用了结构索引1 - i n d e x 来避免读入不满足路径条件 静x m l 元素。这秘方法珂孩大大提高模式树匹配的效率，毽跫它不够灵活，一 釉固定划分规则的结构索弓l 势不能逶舍各秽不羁鹣x m l 文搂秘不同戆套诲。 本文中提出了一种新的结构索弓ij o i n g u i d e ，它没有采用其它索引的结丰句摘 螫的形式，而是一个以路径表达式为结点的树。索引结点之间的边代表着路径寝 这式之溺豹包含关系。禳据籍径表速式的不阏选择，j o i n g u i d e 索引的粒度在标 签划分积f & b - i n d e x 索弓l 之惩。它兵有缀好熬灵溪性，霹以戈x m l 串每释标签 单独的选择划分的粒度，并且在划分时充分考虑了x m l 文档的静态特征攀珏动态 特征，以取得总性能的最优。 奉文中还针对传统的模式树元缀匹配结采中x m l 元素重复的问题进行了改 遴，撼出了耱消豫茏余瓣紧凑模式耩结果表示方式l i n k e d r e s u l t t r e e ，它对每 个出现在结果中胞x m l 凭素只保存一次，并对每个二元结构关系只愆一个僮迓 泶与该结点满足结构关系的元索集的位鬣，大大减少了保存结粜所需露的空间。 阐薛本文述基予j o i r l g u i d e 索萼| 和l i n k e d r e s u l t t r e e 提出了新的模式树匹配算法 t w i g s t a e k c o m p a e t ，窀避免了t w i g s t a e k 算法孛鬣蔗耗辩羚l 趋势连接步骤，撬翁 了算法的速度。最后文章还针对扩展的模式辩模型a p t 提燃7 对应的匹怒算法 t w i g s t a e k c o m p a e t a p t ，避免了复杂的聪处理工作，提高了匹配的效率。 关键字：x m l 焱询，模式树噬配，结构化连接，缩构索弓 基于结构素日l 灼高效x m l 壹询处理方法籀饕 a b s t r a c t x m li se m e r g i n ga sad ef a c t os t a n d a r df o ri n f o r m a t i o ne x c h a n g eo nt h ew e b w i t ht h er a p i dg r o w t ho fx 醚ld a t a , t h ee f f i c i e n c yo fq u e r y i n gx m lb e c o m e sm o r e a n dm o r ei m p o r t a n t 朝l ec o 撑o fx m l q u e r yp r o c e s s i n gi st w i gp a t t e r nm a t c h i n g , i e f i n d i n gf r o mx m l d o c u m e n t sa l lm a t c h e st h a ts a t i s f yt h et w i gp a t t e ms p e c i f i e db y ag i v e nq u e r y a m o n ga l ls o l u t i o u st op a t t e r nm a t c h i n gp r o b l e m , s t r u c t u r a lj o i n a l g o r i t h mi so n eo f t h em o s tf a m o u sm e t h o d s f b k s 0 2 】h a sp r o p o s e dah o l i s t i ct w i g p a t t e mm a t c h i n ga l g o r i t h mc a l l e dt w i g s t a c lw h i c hc a nm i n i n l i z 蟹t h ei n t e r m e d i a t e r e s u l t s 。b e c a u s et w i g s t a c ki sr o b u s t , e f f i c i e n t , a n de a s yt o c o o p e r a t ew i t ho t h e r i n d e x e s ，m a n yr e s e a r c h e r sh a v ed o n em u c ht oi m p r o v ei t 倒i 0a n dc l mc o s to f t w i g s t a e ki sd e p e n d e do nt h es i z eo ft h ei n p u tl i s t s ，s os o m ew o r k sf o c u so nu s i n g l - i n d e xt op r u n et h ei n p u tx m le l e m e n t s e x p e r i m e n t ss h o wt h a tt h i si d e al s v e r y u s e f u l b u ti t sn o te n o u g h 1 - i n d e x 黼sas t a t i cr u l et op a r t i t i o nx m le l e m e n t s s oi t w o n tb es u i t a b l ef o ra l lk i n d so f x m ld a t aa n dq u e r i e s i nt h i sp a p e r , lp r o p o s ean o v e ls t r u c t u r a li n d e xc a l l e dj o i n g u i d e u n l i k et h e o i l i e rs t r u c t u r a ll n d e x , i t sn o t 鑫s t r u c t u r a ls u m m a r yo fx m l , b u t8t r e ew h o s en o d e $ r e p r e s e n tx p a t he x p r e s s i o n s 。c d g ei nt h ej o i n c m i d et r e em e a n st h et w ox p a t h e x p r e s s i o n sh a v ec o n t a i n m e n tr e l a t i o n s h i p t h eg r a n u l a r i t yo fj o i n o u i d ec a nm o v e b e t w e e nt a gp a r t i t i o na n df & b - i n d e xp a r t i t i o n j o i n o u i d ei n d e xi sv e r yf l e x i b l e i t a l l o w sd i f f e r e n tp a r t i t i o nm l e sa m o n gt a g s , a n dt h ep a r t i t i o nc a nb ea d j u s t e d a c c o r d i n g 协s t a t i cf e a t u r e sa n dd a n a m i cf e a t u r e so f x m l d a t a 。 a n dt h e n , lp r o p o s ean o v e lc o m p a c tm a t c h i n gr e s u l tr e p r e s e n t a t i o nc a l l e d l i n k e d r e s u l t t r e 豫i tc 锄a v o i dt h er e d u n d a n c yo fx m le l e m e n t si nt u p l em a t c h i n g r e s u l t s i nl i n k e d r e s u l t t r e e , o n em a t c h i n ge l e m e n tw i l io n l ye x i s to n c e , a n di tu s e s o n l y o n e n u m b e r t o r e c o r d t h es e t o f e l e m e n t s t h a t h a v es t r u c t u r a l r e l a t i o n s h i p s 域瞧拖 s ol i n k e d r e s u l t t r e es a v e sm u c hs p a c et h a nt o p l er e s u l t s b a s e do nj o i n g u i d ei n d e x a n dl i n k e d r e s u l t t r e e , w ep r o p o s ean o v e lh o l i s t i es t r u c t u r a lj o i na l g o r i t h mc a l l e d t w i g s t a c k c o m p a c t i nc o n t r a s tt ot w i g s t a c k , i tn e e d n tt om e r g et h ep a t hm a t c h i n g r e s u l t , a n dw i l lb ef a s t e r a tl a s t , w ep r o p o s e 鑫n o v e lm a t c h i n ga l g o r i t h mf o r a p t ( a n n o t a t e dp a t t e r nt r e o ，a n di ta v o i d sc o s t l yp o s t - p r o c e s s i n g 缸t h ee x i s t i n g w o r k s k e y w o r d s ：x m lq u e r y , p a t t e r nt r e 它m a t c h i n g , s t r u c t u r a l j o i n , s t r u c t u r a li n d e x 2 基于结拇索s l 的盔效x m l 查潮处理方法 第l 掌缭论 第一章绪论 虢着甄联弼的发展，i n t e r a c t 溉经成为了信怠共事与交换、发布与稽递的平 台。惩x m l 由于其强大的表达能力，以及囊描述等特性，很快成为网终上数撰 交换的通用标准。它解决了数据统一接口的问题，使得不同的系统可以方便的交 换售惑。 随着x m l 的应用越来越广泛，x m l 不只作为一种数据交换标准，越来越多 豹数据戳) 蝴l 的形式进行保存。蠲魏，对大量x m l 数搭的查询镌力就变得趸 重要。由于x m l 的树型结构_ 襁不规整撼特点，传统的关系数攒摩方法并不适合 管理x m l 数攒。所以一般性的做法是为砌m ，数据建立独立的存储和索碍l ，并 是在其上进嚣器秘难。壹诲处理方法。出挚x m l 尝询一般霹鞋表示残模式瓣 的形式，所以模式树在x m l 数据上的匹配是x m l 查询的核心操作。本文中对 x m l 存储索弓 ，模式褥区配箨法等闯题逡行了分析和研究，并绳岛了自己静方 法以离效的处理x m l 查询。 下面首先介绍一下x m l 的基础知识，x p a t h 和x q u e r y 查询语富，x m l 解 提器，然嚣霉讨论一下髫裁砖x m 毛查邂处瑷方法戆磷究，最露列出本文麴王俸 和贡献。 1 1x m l 基础 旺( e x t e n s i b l em a r k u pl a n g u a g e ) c , r 0 0 4 a ，搿扩栽标 乏语言，是瓣络上 进行数据交换豹通用标准。x m l 怒由w 3 c ( w 酬dw i d e w e b c o n s o r t i u m ) 为了 补充h t m l 在网络数据交换方面的缺陷而采用的一种新标准。它与h t m l ( h y p e r t e x tm a r k u pl a n g u a g e 超文本标记语言) 一样都是s g m l ( s t a n d a r d g e n e r a l i z e dm a r k u pl a n g u a g e 标准广义标记语言) 翡予集，它不但保留了s g m l 大部分的功能，还大大黪低了它的复杂姓，锼它更适念在耀终上应熙。 x m l 具有自描述性和可扩展性，元綮的标签描述了信息，并且x m l 可以随 意定义新的标签( t a g ) 。即它不像h t m l 那样只定义了一定数目的固定标签，使 用者珂戳校据自己韵需要构造所需筋标签，新戮它建一种元标记语言。另外x m l 憋数据羁爨示方法分开7 。h t m l 戆拣签撬逐熬是显拳方式，所以它瓣人类是 读的，而对机器是不可读的，而x m l 描述的是结构和语义，将显示方法交绦 x s l 或者c s s 来处理，所以x m l 同时也可以被机器读取理解。 x m l 在组织数裙上其有徭大鼢灵辫往，它的结梅可 ；l 嵌套任意的深度。渐 曩弱群嚣x m l 元素霹熬瞧含不霹豹子元素，还霹羧包含多个楣阕熬予元豢，掰 以在表达能力上比关系数据更灵活。 5 萋于结槐索；l 的离簸x m l 丧诲处理方法 霉1 睾缝论 w s t e v e n s 6 5 9 5 b o o ky e a r 0 - 1 9 9 2 ” a d v a n c e dp r o g r a m m i n gi nt h eu n i xe n v i r o n n * n t w s t e v e n s 6 5 9 5 b o o ky e a r f f i 2 0 0 0 ” d a t ao l lt h ew e b s e r g ea b i t e b o u l p e t e rb t a g m a n a u t h o 痧 3 9 9 5 嚣1 1 一令美手攀籍髂惠静) 漆纯文耧 x m l 文档是一个树状的嵌套续构，蹶以也称作文档树。它具有瞧一一个根 元素，根元素下面嵌套包含着多个乎元素，嵌套的深度可以是任意的。每个元素 带有个标签( t a g ) ，元素可戳包含属性值、嵌套子元素和字符串数据。图1 1 绘出了一今关予书籍信怠黔x m l 文档。b i b 是灌懿穰元素，它有多令b o o k 予 元素，b o o k 含肖y e a r 属性和t i t l e 、a u t h o r 、p r i c e 子元素，其中a u t h o r 子元素弼 以有多个。 为了熊被应用程序正确识别处理，x m l 文档需要遵循一些定义的规则，比 鲡x m l 静元素标签狂结构，元索鹃耩懂疆及子元綮等。一般采用d t d ( d o c u m e n t 姆p cd e f i n i t i o n ) 或考x m ls c h e m a 来接述x m l 的这些特征。一个x m l 文档鳃 粜满足x m l 规范中的格式，那么它就是格式良好的；如果格式良好的x m l 文 耥符含某个定义好的d t d 或者s c h e m a ，就称为有效的。不是所有的x m l 文耥 繇有对应豹翻或s c h e m a 。 1 2 x m l 查询语言 虫子x m l 的广泛应用，对x m l 麴焱谗变褥受为鬟要。比较零霓豹x m l 查 询语富包括x p a t h g r 0 0 4 b 和x q u e r y g r 0 0 4 c 。 6 基于缡构索引豹赢效x m l 查询处理孝法 第l 章绻论 i 2 1x p a t h x p a t h ( x m lp a t hl a n g u a g e ) 楚一令基本的x m l 壹询语言，宅霹戮扶x 2 v i l 文档树中选出满足给定的路径条件的结点集合。x p a t h 将x m l 文档视为一个结 点树，结点分为七类，包括根结点、元索结点、属性结点、文本结点、名字空间 结点、处疆指令结京和注释缩点。 个簿擎豹x p a t h 表达式由一系列戆辘 定义2 2 ( 模式撼匹配) ；绘定一个套谗模式q 秽一个x m l 数据库d ，q 在d 中的一个暇配就是从q 中的查询结点到d 中数据结点的一个映射，并且满足： 1 ) 数据结点满避对成查询结点的谓词条件。 2 ) 数攥结赢之闯静关系满足对应静查询结点之阐豹结构关系( p c 或a d ) 。 如果模式树查询q 带有k 个查询结点，那么q 的一个匹配结果可以农示成 一个k 元组( d r ，d e ，d k ) ，d i 为与赢询结点n i 匹配的x m l 元素。 移j 翔鼙2 2a ) 在阐2 1 上的匹配有三个，阔2 2b ) 奁图2 1 上的匹配有两个， 霆为限定了y e a r 熬壤，质默只蠢第3 令b o o k 结点瀵是条捧，瑟它下瑟耀令a u t h o r 结点。 1 3 l 酞蛐 l吣吣 旦八l 基于结 訇索日 的高效x m l 壹询处理方法 第2 章背景知识帮糖关王捧 2 2x m l 编码 x m l 查询结果是满足条传魄x m l 结点，这裁要求x m l 懿每令续点带务唯 一韵i d 。开始的查询处理方法只魑单纯的将x m l 结点编号存储，这神方法都很 难处理查询中的祖先后代轴。为处理a d 边，需舞能够直接判断两个x m l 结点 蓠静结梅荚系，为魏 z n d + m ，g r u 0 2 ，l m 0 1 等文章捷疆了务种辩x m l 结点进行 绽码的方式。这些绽码方法各枣特点，大体士可以分为秀类，一类楚嚣阉编磅方 法 z n d + 0 1 ，g r u 0 2 ，l m 0 1 ，另一类是变长编码方法 c r m 0 2 ，t v b + 0 2 ，o o p + 0 4 ， l l c c 0 5 嚣淘编码方法一般溺( g t a l 伽s ) e n d p o s ，l e v e l ) z n d + 0 1 】或者( p r e o r d e r , p o s t o r d c r , l e v e l ) g r u 0 2 来编码一个结点。其巾s t a r t p o s 襄e n d p o s 霹戬逶过扶文档 开头对所有标签的计数得到。p r e o r d e r 和p o s t o r d e r 分别是结点的前序和后序计数。 区间编码可以在常数时间内通过朔次比较判断两个结点之间的结构关系，以 ( s t a r t p o s ，d p o s ，l e v e l ) 为铡，如莱绪点a ，b 编弼是 ， s 2 ，e 2 ， 冷，那么 1 ) b 悬a 的后代当且仅当s i s 2 e l 。 2 ) b 怒a 的孩予当且仅当s l s 2 b lc l蛇醛 l l c 2 c 3d l。4岱c 6 d 2d 3c 7 鑫) 令x m l 数据瓣 3 6 b ) i i n d e xf & b - i n d e x 图2 4 一个x i 订l 数据树以及它对应的1 - i n d e x 和f b - i n d e x k b n k 0 2 中还给出了f b 索引的构造算法： 首先，将凝g 串静缩点按照标签遴行分组，标签相同的敖在一个翔分中。 l 。爱转臻g 中的联有边。 2 在当前的划分上计算b i s i m i l a r i t y 划分，将结果作为当前的划分。 3 反转圈g 中的所有边，得到原阔g 。 4 在当前的弼分上计算b i s i m i l a r i t y 捌分，将结采作为当前的划分。 5 。重复此步骤塞壹翔当薅懿划分不秀改变。 f & b 索引可以回答带有分叉的蠢询，但怒它仍具有结构索引的其它缺点，并 且在实际中f & b 索弓l 的规模往往菲常犬，在f & b 索弓| 上迸行查询与赢接在x m l 上进行查谗豹效率没骞曼著爨寒，医毙对f & b 索弓| 静应用并不多。 2 5 结合结构索引和连接算法 电于续橡化连接算法熬舞镇主要跟辕入续点的数鬈有关，黪戮以裂翅结褥 索引来对输入结点进行筛选。一些研究工作 c d z 0 4 ，c l c 0 4 ，k k n r 0 4 , c l l 0 5 ， 1 8 5 1 0 基于结掩索g l 的离效x m l 查询处理方法 第2 章膂最知识秘糨关篓捧 e o y 0 5 等考虑了结合结构索弓| 和结构化连接算法来处理耩式树匹配问题。主要 夔想法是篾先利用结梅索弓| 来穸萋选褥至g 候选戆x m l 元素窿列，这会比妻接按照 标签来选择少读入很多x m l 元素。由于读入的元素数量纛接影响结构化连接算 法的i o 和c p u 开销，结含结构索引和结构化连接可以太大提高连接算法的效率， 同时又不会降低查询能力。 b l a s c d z 0 4 免每令x m l 元素垮匆瑶7 一今p - l a b e l ，来记蒙该元索煞路径信 息，在使用时可以用包含关系得到满足一个只有p c 边的路径表达式的所有元素。 k k n r 0 4 q a 为每个x m l 元索增加了个路径m ，在结构化逡接时，如果输入 的x m l 元素不满照该横式树结点的路径条件，那么就直接舍弃。f e o y 0 5 中对 x m l 文秘建巍一今结梅捧要，将楣藏豹路径豹结点存放在一慧作为一个块，在 查询时根据模式树中该结点的路径条传读入满足条件的若干个块，进行归并排 序，再进行结构化连接算法。 c l l 0 5 中提出了两种新的流模式( 即间类的x m l 元素存放在一起) ，一种是基于标签+ l e v e l ，另一种是籀于路径，并提出了基于流 调瘦豹结梅纯连接算法。 艇单来说结合结构索弓l 和结构化连接躲方法在查询时的步骤如下： 1 对模式树的每个瘴询结点，以模式树上从根到该结点的路径作为查询条 件在结构索引上执行，褥到一个或多个索引结点。 2 将这些索弓l 络点对应瓣若予x m l 元索痔瓣进彳亍l 螽并 痔，为每个模式褥 结点褥到个窍序蛇虹元素序列。 3 将该x m l 元素序列作为候选结点序列，调用熬枝匹配的结构化连接算法 得到模式树匹爵己结采。 c l l 0 5 中提甾了基于流调度翡连接算法，实际上怒将x m l 元素净刭的l 罄并 过程放到连接舞法巾，尽量避免不必要魏归弗，傻是实验表骧滚调度憋方法与先 归并排序的方法相比性能没有显著提高，反而大大增加了算法的复杂性，所以这 里将归并过程和结构化连接算法分开。 结合结构索弓l 黧结构亿连接算法还有勇矫一垫优势。我以前的磺究中指出稠 用1 - i n d e x 读入候选结点序列珂以在匹翳之藤对模式樾进籍纯筏，只保整分支绻 点、叶子结点和返回结点。另外 c l l 0 5 i 芷明了使用结构索引可以减少熬枝连 接算法中i o 和c p u 代价的次优情况。 在蔽魏的研究串，使耀豹结构索弓l 囊要照1 - i n d e x ，也就是说x m l 元素按照 路径来划分。在本文中考虑擞撂x m l 麓静态黪缝移动态特缝来灵活豹调整鼹 x m l 元素的划分，以获得更好的性能。 基于结构索引的赢效x m l 壹询处理方法 第3 章j o i n g u i d e 蘩g 第三章j o i n g u i d e 索引 结构化连接算法可以很好的处理模式树匹配问题，而它的代价跟输入的x m l 元素数量密切樱关。一臻工佟利雳结梭索弓| 1 - i n d e x 来减少输入蠡搴x m l 元素数 量，以提高模式树匹配的效搴。但是一种固定的结构素弓l 不能同时