（计算机软件与理论专业论文）基于结构化联接的xml查询模式匹配关键技术研究.pdf

摘要 这篇论文主要讨论了基于结构化联接的x m l 查询模式匹配的相关关键技 术。提n5 了包含段划分的概念，并据此提出基于包含段划分的结构化联接新方法。 件也含段概念的基础上，研究了联接次序选择的问题，对隐检整枝联接方法进行 7 扩艘。对运崩基于包含段的隐检整技联接算法查询x m l 流数捌也提出厂个 蝌扶框架。最后，划影响查询系统性能较大的x m l 模式树的最小化问题也进行 j 7 探讨。 这篇论文首先从整树匹配和基于索引结点的模式匹配两个方旺n 对x m l 奄询 匹配的相关研究进行了综述为该方向的研究现状勾勒出一个较为清晰的轮廓， 也为确立本文研究的意义和必要性奠定了基础。 该篇论文的主要贡献有以下几个方面： 针列。结构化联接所基于的三元组索引结构进行了研究，提出列索引窄i r ：i j 结构 进行包含段划分的思想，并据此对结构化联接算法进行了改进。 转于结构化联接操作的隐检整枝联接算法也是以三元组索引为基础的。我们 同样将包含段划分的概念引入到这一领域中来。首先研究基于包含段划分的 隐愉孵枝联接方法。叉运用包含段划分的概念对隐榆祭枝匹配力“法t i ，联接；4 i j 弘选择的问题进行了研宄。从上述两个方面对隐检整枝联接算法进行n 发 进； 隐检祭杖耿接方法有个一r 分优良的特性，就是它只需要列躲个x m l - lp m i 。1 ) 。 人们引入查询同态( q u e r yh o m o m o r p h i s m ) 的概念来解决上述问题。 1 2 5 1 1 2 6 2 9 3 0 3 1 对j ：树模式p 和q 而言，如果存在一个从q 到p 的查询同态( 又称包含映射 c o n t a i n m e n tm a p p i n g ) 则p c _ q 。一个同念h , - q p 是一个从q 的结点到p 的结点的一个映射，它满足如下条件： 1 ) 保持结点类型( t y p e ) 不变：v u q ，u 与h ( u ) 同类型( 也就是u 与h ( u ) 的类型均为中的同一标号) ； 2 ) 保持边的关系不变：如果q 中有u v ( 或u v ) ，则p 中必有h ( u ) 一h ( v ) ( h ( u ) jh ( v ) ) ，一与等分别表示父子和祖先一后代关系。 设p 与p 为树模式，且p 。包含p 的结点集的子集，则h ：p p 。称为p 的一个 注( 1 ) 无秩( u n r a n k e d ) ：事先并未限制一个树结点的子树个数。 自同态( e n d o m o r p h i s m ) 。 命题1 1 ：3 0 1u n o d e s ( p ) ，当且仅当p 存在一个自同态h 使得h ( u ) u 则u 为冗余结点。口 3 0 d ：，也证明了如下定理： 定理1 1 ：给定一个树模式p ，存在它的一个唯一的最小树模式p 1 。p 可以通 过不断删除p 中的冗余叶子结点直到不再存在冗余的叶子结点为止而得到( 内 部j l ：余结点也会在动态的连续删除过程的某一时刻变为叶子结点) 。 口 至此，问题归结到较为具有可操作性了。于是【3 0 】中给出了不考虑x m l 完整 性约束i c s ( i n t e g r i t yc o n s t r a i n t s ) 前提下的树模式最小化算法c i m ，其复杂度 为o ( n 4 ) 。 接着，f 3 0 研究了查询模式p 在给定完整性约束i c s 集合c 下的最小化问题。 文中基于c h a s e 技术 5 5 1 提出了复杂度为o ( n 6 ) 的算法a c l m 。其主要的思想就 是采用c h a s e 技术，将c 中的t c s 逐条加入到p 中，生成一个c h a s e c ( p ) ，再 用算法c i m 消去冗余。c 中主 要考虑三种完整性约束：约束儿子结点( r e q u i r e dc h i l d ) ，约束后代结点( r e q u i r e d d e s c e n d a n t ) 和多类型约束( s u b t y p ec o - o c c u r r e n c e ) 。 2 6 采用图模拟( g r a p hs i m u l a t i o n ) 的方法对【3 0 】的相关算法进行了改进。 给定个有向图g = ( v ，e ) ，v u v ，均有一个类型t ( u ) 与之相联系。 p o s t ( u ) 表示从u 出发经一条边所能到达的结点集。模拟( s i m u l a t i o n ) 就是一 个v 上的二：元关系- ，使得下面的定义成立：如果u - k v ，则t ( u ) - t ( v ) ， 并日v u e p o s t ( u ) ，3 v p o s t ( v ) ，有u _ v 成立。s i m ( u ) 表示所有与 u 相模拟的结点集。 在不考虑完整性约束的前提下， 2 6 得至r j0 ( n 2 ) 的树模式最小化算法 t p q s i m u l a t i o n 和t p q m i n i m i z a t i o n 。算法的主要依据是如下引理： 引理1 1 ：设u 为树模式p 中的一个非冗余结点，则： 1 ) u 的一个儿子结点( c h i l d ) v 是冗余结点当且仅当u 存在另个儿子结点 s i m ( v ) ； 2 ) u 的个子孙结点( d e s c e n d a n t ) v 是冗余结点当且仅当u 存在另一个子孙 结点s i m ( v ) 。 口 算法t p q s i m u l a t i o n 先自底向上( b o s o m u p ) 计算p 中每一个结点的u 的 s i r e ( u ) 值，再用算法t p q m i n i m i z a t i o n 自上而下( t o p d o w n ) 删除多余的结点。 【2 6 中的算法之所以快于【3 0 】，是因为其利用图模拟信息可以一次自卜而下 删除一棵冗余的子树，而【3 0 】中每一次只能自底向上删除一个冗余的叶子结点。 2 6 也考虑了存在完整性约束i c s 情况下，结合图模拟和c h a s e 技术的树模 式最小化算法，得到了复杂度为o ( 1 3 4 ) 的算法c h a s e s i m u l a t i o n 和 c h a s e m i n i m i z a t i o n 。 在x m l 查询模式最小化研究中，还有另外一种提法，那就是x p a t h 表达式 的最小化。现有文献【2 9 1 f 3 1 j 【3 4 】【3 5 1 3 6 1 中所研究的x p a t h 表达式片段( f r a g m e m t ) 般可归结为下式： e x p e x p e x p i e x p e x p i e x p e x p 】i 6 i 其中6 ，一表示“当前结点”。 【3 1 】中已经明确指出，包含，【】的x p a t h 表达式( 表示为x p “ “， i ) ) ，可以转化成势瞳( a r i t y ) 为1 的等价的查询树模式：反之，一个势为1 的查询树模式也可以转换成一个x p p ，“，口， 中的表达式。 如果我们将包含，【】的树模式也描述为p p ”1 ) ，则x p ，”，n ”与p “+ “- ) 是等价的。这样，x p a t h 表达式最小化与树模式最小化其实是一个 问题。而前文也指出，寻找最小化表达式或树模式，其实就是寻找包含其自身的 一个更小的等价形式。于是最小化问题就是x p a t h 表达式或树模式之间的相互 包含问题。 【2 9 3 1 儿3 4 】【3 5 】【3 6 】等文献做了大量的工作，证明了部分x p a t h 表达式的包 含问题的复杂度。 x p a t h 表达式复杂度 x p 以, d 1 c o - n p c o m p l e t e x p t , ，。p x p p - 口1 p x p t , ”，i j p 图1 2 部分x p a t h 表达式的包含问题的复杂度 注( 2 ) 势( a r i t y ) = 前文中结果元组中的k 值。 1 2 图12 中列出了现有文献中已经证明的部分x p a t h 表达式的包含问题的复 杂度。所没有列出的是【3 1 】中证明的：v p e x p , , t 和v q e x p ”- n 。，判定p 呈q 是p t i m e 问题( 多项式时间) 。 d t d ( d o c u m e n t t y p ed e f i n i t i o n ) 的存在，不但规范着x m l 文档的结构， 还对x m l 文档存在一些潜在的约束( c o n s t r a i n t s ) 。 也有些文献，如【3 4 】【3 5 】 3 6 】【5 3 】等，研究这种d t d 约束下的x m l 查询模 式树( x p a t h 表达式) 的最小化问题。 r t w o o d 在 3 5 1 【5 3 】中研究了父- 子约束( p a r e n t c h i l dc o n s t r a i n t s ) ，在 3 6 】 中，他又将父一子约束扩展为兄弟约束s c ( s i b l i n gc o n s t r a i n t s ) 。 没t t 为一棵( 文档) 树，a ，c 为元素名( e l e m e n tn a m e s ) ，b 为 一元素名的集合。我们说t 满足兄弟约束( s c ) a ：b u c ，如果无论何时，t 中标记 为a 的结点拥有标记为b 的子结点( b b ) ，则它必然拥有标记为c 的子结点。 当8 = 西时，s c 就转化为孩子约束c c ( c h i l dc o n s t r a i n t ) 。设s 为定义于上的 所有s c 的集合，则s a t ( s ) 表示t ：中满足s 中s c 约束的树t 的集合。 对于一般意义上的d t d 约束而言设d 为任一d t d 我们用s a t ( d ) 表 示满足d 的t 中树t 的集合。给定树模式p 和q ，如果v t e s a t ( 0 ) ，有q ( t ) p ( t ) ，我们浇pd c o n t a i n sq ，记为q s a t ( d ) p 。如果q 互s a t ( d ) p 且p _ c s a t ( d ) q ， 则p 和q 是d e q u i v a l e n t 的，记为p - - = s a t ( d ) q 。 显而易见，所谓d t d 约束下的x m l 查询模式树( x p a t h 表达式) 的最小化， 实质就是在满足某一d t d 的文档集上判断树模式的冗余度。原来在广义的t t 中查询时并不冗余的 x p a t h 表达式的某一局部，可能会在t ：的某一子集s a t ( d ) 上显得“多余”。 在最近的文献 3 4 】中，作者将x p ，, 口_ 扩大到包括析取( d i s j u n c t i o n ) ，变 量( v a r i a b l e s ) ，且在d t d 约束下。 【3 4 的主要结论可概括为下面的图1 3 中： 。o t d，| 玎 l复杂度 p c o n p c o r f i p l e r e c o n p h a r d + e x p t i m e - c o m p l e t e + e x p t i m e c o m p l e l e e x p t i m e - c o m p l e t e + u n d e c i d a b l ew i t hm o d e s tc o m p a r i s o n s ( a ) d t d 约束下的复杂度 ，| | 口 j v a r s 士 复杂度 + c o n p c o m p l e t e c o n p c o m p l e t e n ；一c o m p l e t e 兀：一c o m p l e t e n ；一c o m p l e t e + u n d e c i d a b l e ( b ) 包禽变鲒的复朵度 图1 3 d t d 约束下包含析取、变量的树模式最小化复杂度 1 1 3 基于结构化联接的匹配方法 本文首先将涉及基于结构化联接的x m l 查询模式匹配的参考文献绘成图 1 4 。 pfd i e t z 在其早期文献【3 9 】中提出用一种编号模式( n u m b e r i n gs c h e m e ) 来标记树中的结点。任一结点的编号模式由其前序遍历值和后序遍历值组成。 f 2 e l 证明了由任意两个树结点的编号模式值可以很方便地确定其是否构成前后 代关系。f 3 8 。p 将这一想法引申成“扩展自h j # ”( e x t e n d e dp r e o r d e r ) 米索引x m l 文档，以实现文中x l s s ( x m li n d e x i n ga n ds t o r a g es y s t e m ) 系统中的e e - j o i n 和e a - j o i n 算法。f 3 7 q ，为了实现在关系库中存储的x m l 文档的快速查找，提出 一种三元组x m l 文档索引结构，它可以快速确定任两个文档结点的祖先一后代 ( 父一子) 关系。【3 7 】还提出了基于x m l 元素三元组索引的多谓词归并联接算法 m p m g j n ( m u l t i p r e d i c a t em e r g ej o i n ) 。 基于上述工作，f 4 3 首次提出了x m l 查询模式匹配的结构化联接( s t r u c t u r a l i o i n s ) 算法。有的文献也将结构化联接称为包含联接( c o n t a i n m e n tj o i n s ) 。 我们用例1 ，1 来说明结构化联接的主要思想。例1 1 中的x q u e r y 语句要查 找的b o o k 元素满足如下条件：1 ) b o o k 元素有一个儿子元素t i t t l e ，它的内容为 串值x m l ：2 ) b o o k 元素同时有一个后代元素y e a r ，其内容为串值2 0 0 0 。因 此，该查询语句被分解为组父子关系和祖先一后代关系结点对。即祖先一后代关 系( b o o k ，y e a r ) 和父一子关系( b o o k ，t i t t l e ) ( t i t t l e ，x m l ) ( y e a r ，2 0 0 0 ) 。于 是，该查询可以这样来完成：在三元组索引的x m l 数据库中匹配上述分解的 二元结构关系；将查找到的二元结构匹配结果集组装( s t i t c h i n g ) 成最终的符 合查询表达式的完整树结构。 3 9 】( 提出编号模式以方便前后代芙系判定) 、 4 0 l ( 引入i r 中倒捧文件索引方法) f 3 8 】【3 7 】( 提出三元组索引和m p m g j n 算法) - t r e e 索引和p b i t r e e 编码) 结构一次成形) 况) 索引将x m l 夯询转化 最优的结构化联接次序) 【5 5 】 为序列匹配) ( 将【4 6 】应用丁x m l 数据流的鹰找) 图1 4 基于结构化联接的x m l 查询模式匹配研究进展示意图 显然，问题的关键在于第一步，它是x m l 查询处理的核心操作。而完成 这一步的方法是将匹配每一个二元组关系的x m l 树中的两结点，根据其三元组 索引结构进行结构化联接，得到所需要的二元组匹配结果。 我们对x m l 文档树中的结点进行三元组索引标记，形式为( d o c l d s t a r t p o s ：e n d p o s 。l e v e i n u m ) ，其中，d o c l d 为x m l 文档的标识符，对于同一 文档中的结点，d o c l d 是一样的；s t a r l p o s ，e n d p o s 分别为文档结点的开始和 结束位置，可以通过计数文档元素的开始和结束位置而得到：l e v e l n u m 是文档 结点的嵌套深度，即层号。需要指出的是，上述三元组标记，可以在顺序读取一 个文档的同时产生，且只需扫描整个文档一遍。 这种三元组索引的优良性质是易于判定两结点之间的结构化关系 ( s t r u c t u r a lr e l a t i o n s h i p ) 祖先一后代( a n c e s t o r - d e s c e n d a n t ) 关系：v n l ，n 2 为x m l 文档树中 的结点，其三元组索引分别为i n d e x l - ( d 1 ，s 1 ：e 1 ，l 1 ) ，i n d e x 2 = ( d 2 ，s 2 ：e 2 ，l 2 ) ，我们说n 2 是n 1 的一个后代结点，当且仅当d 1 = d 2 ， s 1 s 2 ，e 2 e f ； 父一子( p a r e n t c h i l d ) 关系：v n l ，n 2 为x m l 文档树中的结点，其三 元组索引分别为i n d e x 1 = ( d 1 ，s 1 ：e 1 ，l 1 ) ，i n d e x 2 = ( d 2 ，s 2 ：e 2 ， l 2 ) ，我们说n 2 是n ，的一个儿子结点，当且仅当d 1 - d 2 ，s 1 s 2 ，e 2 e 1 ，l 1 + 1 = l 2 。 设查询模式树( 查询语句表达式) 中分解出的一个二元关系为( a ，d ) ( 父 一子或祖先一后代关系) ，与a ，d 分别匹配的结点集为a l i s t = a 1 , a 2 ，a 。) 和 d l i s t = d l ，d 2 ，d 。) ，其中的结点a i ( i = 1 ，n ) 和d j ( j - 1 ，m ) 均有前 述的三元组索引标记，且a l i s t 与d l i s t 均按( o o c l d ，s t a r t p o s ) 从小到大排列。 4 3 1 中的结构化联接算法s t a c k t r e e 逐一考察a j e a l i s t 与d i d l i s t 的关系 是否符合( a ，d ) 所定义的结构关系，使用一个栈将符合条件的( a i ，d i ) 输出 到结果集。 4 4 认为 4 3 1 5 b 对任意两个结点均判定其结构关系是低效的，于是提出算法 a n c d e s b + 采用b + 树来索引三元组标记的结点，从而可以在结构化联接操作中 忽略掉某些不必参加联接操作的结点。 【4 4 采用b 十树索引并4 i 能有效地忽略祖先结点，并不完善。因此，【4 1 1 提出 了适合于结构化联接的x r - t r e e 索引用以改进这种情况。而【4 2 】进一步提出一种 新的编码模式( c o d i n gs c h e m e ) p b i t r e e 编码以取代三元组标记，并以此为框 架重新设计了新的结构化联接算法。但笔者认为【4 1 】【4 2 】的索引结构的局限性在 于缺乏现有数据库技术的支持。 f 如前面的例子中指出的那样基于结构化联接的查询模式匹配方法要走两 步，结构化联接只是其中的第一步。f 4 6 认为分两步走会产生大量无用的中间结 果，作者据此提出了隐检整枝联接( h o l i s t i c t w i gj o i n s ) 算法t w i g s t a c k 。 t w i g s t a c k 采用相互连接的多个栈，每个栈对应一个与查询模式结点相联系的输 入序列i n p u t l i s t 。i n p u t l i s t 的结构与参加结构化联接的序列a l i s t ( 或d l i s t ) 的结构完全相同，也是由匹配该模式结点的x m l 文档结点序列组成。t w i g s t a c k 采用自项向下( t o p - d o w n ) 逐层递归的方式次生成一个查询结果的完整树结 构，从而避免了多余的中间结果存储。 【4 6 】中提出的隐检整枝联接( h o t i s t i ct w i gj o i n s ) 算法t w i g s t a c k 可以通过 图1 5 直观的地予以表现出来。 1 6 例1 2 仍旧考虑例1 1 中的x q u e r y 表达式：b o o k 【t i t t l e = x m l 】i 【y e a r = 2 0 0 0 】，其模式树如图1 1 所示算法t w i g s t a c k 在执行期间的状态如“f 图所示：( q 1 ，q 2 ，q 3 ，q 4 ，q 5 分别代表b o o k ，t i t t l e ，y e a r ，x m l ，2 0 0 0 ) 帕m 。， 匦副f l 货匦 崾一 叵硒刊i 阳匦圄囫 s q 4s q 5 图1 5 算法t w i g s t a c k 示意图 在图1 5 中，算法t w i g s t a c k 从模式树的根结点开始，采用自顶向下 ( t o p d o w n ) 逐层递归的方式渐次匹配各结点，当且仅当一个完整的结果生成 于栈中才将其输出，否则将部分结果退栈后进入下一层循环直至某一匹配序列为 空。栈s q i 对应着第i 个待匹配的模式树结点q ，以及一个与q i 相匹配的输入序 列。 4 9 】受到【4 4 】引进b + 树索引机制改进【4 3 】中结构化联接算法的启发，也引进 【4 1 r t 的x r t r e e 索引对【4 6 】的隐检整枝联接算法t w i g s t a c k 进行了优化，这就 是算法t s g e n e r i c + 。【4 8 】也在【4 3 】和【4 6 】的基础上结合自己课题组的先前研究成 果进一步讨论了多版本x m l 文档的模式查询操作。 f 4 5 采用摘要( s u m m a r y ) 数据结构进行查询模式树匹配结果数目的估计， 认为这一点将成为基于代价估计的反馈式x m l 查询优化的主要问题。【4 3 】的作 者为了完成基于结构化联接的查询模式匹配，也开展了【5 2 】中的工作，结合 5 0 】 的成果他们最终完成了【4 7 。 1 4 7 的工作主要认为，对一个待匹配的查询模式树进行结构化联接操作的代 价是与联接次序的选择相关的。f 4 7 】提出的带修剪的动态规划优化算法d p p ( d y n a m i cp r o g r a m m i n go p t i m i z a t i o nw i t hp r u n i n g ) 可以以较低的代价完成一 个查询模式树匹配的结构化联接操作。 1 7 当然，【4 5 1 的工作本身也是一个独立的工作因此，在2 0 0 4 年的i c d e 会 议上，【6 2 1 采用概率抽样的方法对其进行了改进。 5 5 1 年n 5 6 1 是较近的两篇有关基于结构化联接的查询模式匹配研究的文献。 【5 5 1 自j t 究的是将 4 6 1 中的t w i g s t a c k 算法应用于x m l 数据流查找的相关问题。它 主要讨论了两种情况下隐检整枝联接算法的性能：1 ) 允许x m l 流数据脱机排 序( o f f l i n es o r t i n g ) ；2 ) 允许算法多遍扫描数据流。【5 6 针对 4 3 1 1 4 6 等文献中的 联接算法开销较大的问题，提出了一种动态索引( d y n a m i ci n d e x ) 方法v f s 丁 ( v i r t u a ls u f f i x t r e e 虚拟后缀树) ，将经过v i s t 索引的x m l 文档“展平” ( u n f o l d i n g ) 成字符串序剐，从而将查询模式树与x m l 文档树之浏的匹配转化 成字符串序列与其非连续的子串序列之间的匹配问题。这样就避免了联接运算的 ”销，一次生成查找结果。 1 1 4 结论与展望 本章在相关文献的基础上，对基于多种查询语言的x m l 精确查询的研究进 展情况进行了综述。重点阐述了整树匹配中的模式树最小化问题和基于结构化联 接的索引文档匹配方法。 需要指出的是，本章主要就2 0 0 1 年以后直到2 0 0 4 年初的文献做了总结。 【6 6 也是一篇本领域的综述性文章，但由于期刊的审稿和发表周期较长，它的讨 沦主要限于2 0 0 1 年及以前的文献。与本章的综述基本上是衔接的关系。【6 6 基 本没有涉及本文所综述的内容，而且作者认为，以【3 5 】【3 0 】f 4 3 1 【4 6 】等为代表的 2 0 0 1 年以后的成果才使得本领域的研究真正活跃起来。 本文的作者对所综述领域的未来研究有三点看法 f 女n 3 4 1 5 h 所指出的那样，x p a t h 表达式( 模式树) 最小化下一步的研究显 然是考虑更大范围的表达式的最小化。而且目前考虑的d d 约束过于简单 化，尚未考虑到x m ls c h e m a 引申出的约束等。不过，由于本领域的研究 常涉及树自动机理论、高阶谓词逻辑、规范树模型( c a n o n i c a lt r e em o d e l ) 理论等较艰深理论，难免有些“曲高和寡”，不过并不妨碍它成为p o d s 、 i c d t ( 被称为欧洲的p o d s ) 等会议的热门话题。 x p a t h 表达式( 模式树) 的最小化理论本身处在不断完善中，笔者认为它的 1 8 应用似乎更富前景。首先，前面提到的x m l 数据库研究中的查询代数系统 【1 8 1 【2 3 】【2 2 】设计不能尽如人意的原因之就是过多地模仿了关系库系统理论而 忽略了x m l 数据本身的树型特点，如果在代数优化部分引入模式树最小化 _ 方法可能会成为一条新路。其次，因为基于结构化联接的查询模式匹配方法 的效率也依赖于模式树的规模，故模式树最小化理论也会给结构化联接带来 好处，而这一方面的研究目阿尚未开始。 就糕j 二结构化联接的查询模式匹配方法本身而言，f 5 5 是一个方向，如何斗巷 【4 3 1 4 6 的算法很好地运用到x m l 数掘流的查找中，尚有许多问题值得探讨。 而 5 6 】也是一个具有前景的发展方向，将树匹配转化成索引串序列匹配是一 条很好的思路。本文的第一、第二作者曾与1 5 6 1 的第一作者就【5 6 】进行过讨 论，很受启发，【5 6 】的作者也认为这条思路值得走下去。据悉 5 6 1 的作者的 后续研究可能会出现在2 0 0 4 年的会议上。笔者所在的小组也打算在这方面 丌展工：作。 1 2 本文主要贡献 本文的主要贡献有以下几点 基r 三元组索引的结构化联接操作是x m l 查询模式匹配的关键技术之一。 本文对参与结构化联接操作的三元组索引的结点序列进行了分析，从空i b j 分 布的角度迸一步认清了索引结点序歹f j 的特点，提出了包含段分割的概念。并 以此为基础，完成了基于包含段划分的结构化联接新方法。该方法的显著特 点是：不必在三元组索引之上再建新的索引；以包含段为单位，在联接 操作时可以从两个方向上大量跳过不必参加联接操作的结点序列；只需扫 描整个文档一遍。理论分丰厅和实验结果均表明该方法优于现有工作。 x m l 查询模式匹配的隐检整枝联接方法是对以结构化联接为基础的查询匹 配方法的改进。其主要优点是产生的无用中间结果较少，从而进一步提高了 系统效率。而事实上，隐检整技联接方法的每一步递归过程均是以结构化联 接为基础。因此，本文采用索引空阳j 的包含段划分技术，对隐检整枝联接方 法进行了改进，提出基于包含段划分的隐检整枝联接新方法。理论分析和实 验结果也表明，我们提出的方法也优于现有的相关工作。 ， 在研究基于包含段划分的隐检整枝联接方法的过程中，我们进步发现，现 有隐检整枝联接方法的联接路径是自上而下的( t o p - d o w n ) ，由根结点递归 向下直到叶子结点。我们经过研究，认为这样的一条固定的联接路径仍旧会 1 9 产生一定量的无用的中问结果( “残枝”) 。在有些数据集( 比如d b l p 的x m l 文档) 上的实验表明，这些无用的中问结果集有时还会相当大。于是，我们 仍旧利用包含段分割的相关信息来“规避”这些无用的中间结果。我们提出 基于( 联接) 次序选择的隐检整枝联接新方法。这一方法将所有参与连接运 算的索引结点序列的空问分布情况以包含段为工具进行分析，把相邻结点序 列的包含段分割信息投影到一个数轴上，从它们空间分布的交叉情况束确定 最终的联接次序。从而以较优的隐检整枝联接次序完成查询模式匹配。理论 分析和实验结果进一步印证了我们的想法的正确性和可行性。 基于包含段划分的隐检整枝联接方法的突出优点之一就是只需对整个文档 扫描1 + 遍。这就使得我们很自然地想到将该方法运用到x m l 数据流的查询 操作中去。本文在分析了x m l 数据流的查询操作特点之后，对将基于包含 段划分的隐检整枝联接方法运用到x m l 数据流查询中初步的探讨，并提出 了一个初步的模型。 x m l 查询模式匹配的基础是x m l 查询模式树的生成。由于x m l 查询模式 树的大小直接关系到参加匹配联接的结点序列多少，因此，带冗余结点的模 式树最小化问题显得十分有意义。在本文中重点研究了d t d 约束下的x m l 查询模式树的最小化。主要拓展了p t w o o d 的兄弟约束s c ( s i b l i n g c o n s t r a i n t s ) ，使其扩展为f _ , 8 c ( e x t e n d e ds i b l i n gc o n s t r a i n t s ) ，并进一步 探讨了e s c 下的模式树最小化。通过采用c h a s e 技术和图模拟( gr a p h s i m u l a t i o n ) 方法，提出一种受限模式树的最小化算法，它的时间复杂度为 多项式时间。我们也进行了理论分析和相关实验，以证明其可行性。 第二章结构化联接相关概念 x m l 文档采用了树型的数据模型。x m l 查询通常指明一些基于多个元素的 选择谓词组成的模式树，这些元素之问的结构化关系为父一子关系或祖先一后代关 系。针对两个元素的候选输入集，利用索引的包含关系和栈结构，找出满足结构 化关系的元素对，这就是x m l 结构化联接的一般方法，也是x m l 查询处理的 核心操作。在这篇文章中，作者提出一种新的结构化联接方法先对候选输入序 列进行预处理，找出其结构上的特点，从而在基于栈的结构化联接过程中得以忽 略若干时空耗费，提高处理效率。理论分析和实验结果表明，这种方法优于现有 的相关工作结果。 2 1 引言 x m l 1 1 数据采用了一种树型的数据结构【8 】【1 2 kx m l 查询语言 1 2 1 3 1 4 】 通常均指定一些基于多个元素的选择谓词( s e l e c t i o np r e d i c a t e s ) 组成的模式树 来表达查询。 例如一个x q u e r y 中的表达式： b o o k f t i t t l e = x m l 】a u t h o r 【f n = j a n e a n d i n = d o e 】 它要查询的a u t h o r 元素满足如下条件： 1 ) a u t h o r 元素有一个儿子元素f n ，它的内容为串值j a n e ； 2 ) 2 ) a u t h o r 元素同时另有一个儿子元素| n ，它的内容为串值 d o e ； 3 ) 3 ) a u t h o r 元素为b o o k 元素的后代结点，b o o k 元素另有一 个儿子结点t i t t l e ，其内容为串值x m l 。 这样一个复杂的运算通常是被分解成组父一子或祖先一后代关系结点对，即： 祖先一后代关系( b o o k ，a u t h o r ) 和父一子关系( b o o k t i t t l e ) ，( t i t t l e ，x m l ) ， ( a u t h o r ，f n ) ，( f n ，f a n e ) ，( a u t h o r ，i n ) ，( i n ，d o e ) 。 于是，该查询模式可以这样来完成： 1 ) 在x m l 数据库中匹配上述分解的二元结构关系； 2 2 ) 将查找到的二元结构匹配结果组装( s t i t c h i n g ) 成最终的符合上述查询 表达式的完整树结构。 显然，问题的关键在于第一步，它是x m l 查询处理的核心操作。而完成这 一步的方法是将匹配每一个二元组中两元素的x m l 树中的结点，根据其索引结 构进行结构化联接( s t r u c t u r a lj o i n s ) ，得到所需要的二元组匹配结果。 x m l 的查询模式匹配问题在【2 9 】【2 8 】中已有论述但并未涉及结构化联接。 文献 2 7 】中基于表示元素位置关系的三元组( 第2 2 节中会详细讨论) 索引，提 出。种多诮词归并联接算法m p m g j n ( m u l t i p r e d i c a t em e r g ej o i n ) ，实现了关 系库中存储的x m l 数据的包含查询( c o n t a i n m e n tq u e r i e s ) 。文献【3 3 】在此基础 上，正式将结构化联接的概念引入x m l 数据库的查询操作中，实现了基于栈的 结构化联接算法。【3 4 针对【3 3 】中的算法提出，可以将匹配祖先结点的a l i s t 队列 加入b + 树索引，从而能够依据索引结构特点忽略掉该队列中的若干元素，使其 不参加联接过程，以此提高联接操作的效率。 然而，正如文献 3 1 】中所指出的那样。【3 4 并未实现对匹配后代结点的d l i s t 队列的优化，不能够将d l i s t 队列中的不必参加联接的元素结点忽略掉，因此并 未实现完整的优化联接。 其实，通过对【3 1 】【3 2 】【6 7 】【7 1 】【7 2 】【7 3 】等文献的研究可以发现，所谓优化措施。 均源于对a l i s t 和d 1 i s t 队列的索引结构特点的认识。认识上的每次进步，都 会带来联接优化效率的进一步提高。 本文f 是基于这一点认识，通过对两个参与结构化联接的队列索引结构的认 真分析，认清其实际的索引结构特点。事实上是分析研究两个输入队列的索引包 含特点，得出其包含结构一包含段，然后以此为基础提出了更为优化的同时忽略 两个队列中不必联接的元素结点的结构化联接方法。 2 2 数据模型及索引结构 2 2 1x m l 文档树数据模型 x m l 数据库是一个出有根、有序、带标已的树组成的森林【1 5 】【1 6 ”7 】【1 8 1 其中的每一个x m l 文档都是个符合如下定义的树模型： 定义2 1 一个树型结构的x m l 文档树模型是一个4 元组：t x = ( v ，e ，r o ) ，其中： 一v 是个x m l 文档树中元索结点的集合，v = f v viv 包含x m l 义 档中所有结点) ； 一 e 是x m l 文档树中边的集合，即e = e eie = ( v 1 ，v 2 ) ，v l ，v 2 v v 1i sp a r e n t o f ”2 ； 一 r 是一个单元素集，它只包含x m l 文档中的根结点，即r ： r c r i vv v ，v i sad e s c e n d a n to fr ) ； o 表示从同一父结点引出的同类型边的序，e , f r 对应相应d t d 中的 同一结点。即o = ( e e ，s u c c e e ) lp a r e n t ( e ) = p a r e n t ( s u c c ) ) ，s u c c 表示序中边e 的后继。- f 【 i 举一个例子。本文的例子直接来源于【3 6 】，适当参考了，f 7 6 】和【7 7 】。 例2 。1 ：图2 1 是一个符合定义21 的x m l 文档树模型( 为了节省篇幅和直 观起见，直接给出了文档树的图示) 。 ( 1 3 3 ) 卜卜 i ( 1 , 6 5 ：6 7 ，3 ) i f 阿l nf ni n f ni nx m l 。l 。! ，。! 。! 。，。! 。l 1 ，6 6 4 1 ( 1 ，8 5 ) ( 1 ，1 1 5 )( 1 ，2 6 ，5 ) ( 1 ，4 3 5 ) ( 1 ，4 6 ，5 ) 图2 1 带索引的x m l 文档树模型示意图 2 2 2 索引结构及其特点 h e a d 6 9 ：7 1 ，4 ) i o r i g i n s ( 1 ，7 0 ，5 ) 如图2 1 所示，文档树中任一结点n x 的存储方式e m x 可以有如下定义j 定义2 2 ：v n x t x ，其存储方式可表示为一个二元组，即e m x 。( i n d e x v a l u e ) ，其中： e 龇圳l 42 i n d e x ：( d o c l d ，s t a r t p o s ：e n d p o s ，l e v e l n u m )当s t a r t p o s ：- e n d p o s 时 ( d o c l d ，s t a r t p o s ，l e v e l n u m )当s t a r l p o s = e n d p o s 时 v a l u e ：t a g当s t a r t p o s ：= e n d p o s 时 s t r i n gv a l u e ( p c d a t a )当s t a r t p o s = e n d p o s 时 d o c l d ：x m l 文档标识符，对于同。文档中的结点n x 而言，d o c l d 是一 样的； s t ar t p o s ，e n d p o s ：文档结点的丌始和结束位置，可以通过计数文档元素 ( 或属性) 的开始和结束位置而得到： l e v e l n u m ：文档结点的嵌套深度( 层号) ； t a g 文档中的标号，文档树中的多个元素结点可以对应同一t a g ； s t r i n gv a l u e ( p c d a t a ) ：文档元素的内容，即文档树中的叶子结点的值。 + ， 图21l 】每个结点边上的加括号数据就是i n d e x 的内容，它可以在顺序读取 一个文档的同时产生，且只须扫描一遍。 有的文献中不采用本文的索引标注法【2 8 】【2 9 】【8 0 】【8 1 】，而是将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 ( 后序遍历号) ”一样具有 下面讨论的索引结构特点，生成它一样也只需扫描一遍文档( 只不过要外加一个 栈，用以产生后序遍历值) 。但需要指出的是，采用前后序号标注索引法并不适 用于本文提出的结构化联接方法，这一点下文中还会提到。 定义2 1 中定义的文档树中的结点若采用定义2 2 中的索引法予以标注，则 会具有下面的优良性质：易于判定两结点之间的结构化关系( s t r u c t u r a l r e l a t i o n s h i p ) 。 祖先一后代( a n c e s t o r - d e s c e n d a n t ) 关系：v n x l ，n x 2 t x ；i n d e x l - ( d 1 ，s 1 ：e r ，l 1 ) ，i n d e x 2 = ( d 2 ，s 2 = e 2 ，l 2 ) ，我们说n x 2 是n x i 的一个后代结点，当且仅当d 1 = d 2 ，s 1 s 2 ，e 2 e 1 ； 父一子( p a r e n t - c h i l d ) 关系：v n x r ，n x 2 t x ；i n d e x r = ( d r ，s 1 ：e 1 ， l 1 ) ，i n d e x 2 = ( d 2 ，s 2 ：e 2 ，l 2 ) ，我们说n x 2 是n x r 的一个儿子结点， 当且仅当dr = d 2 ，s r s 2 ，e 2 e r ，l r + l = l 2 。 这个优良特性使得我们判定同一棵树中的任两个结点之间的结构化关系象 判断父子关系那样简单，而完全不必关心那些存在于两者之间路径上的中间结 点。这就使得我们下文论述的结构化联接算法成为可能。 2 3 模式匹配相关概念 2 3 1 模式匹配的定义 下面给出模式匹配的形式化定义。 定义2 3 ：给定一个查询模式q x ，和一个x m l 数据库d x 。 d x = f r x d xit x 是x m l 文档，d x 是由t x 组成的森林) q x = v q x ，e o x ，其中的v q x 为查询模式树q x 中的结点集合e q x 为 其边的集合。 设d x m = f d x l ，d x 2 ，d x m ) 为q x 在d x 中的查询匹配结果集( a n s w e rs e t ) ，其 c v d x 。为q x