《基于结构化联接的xml查询模式匹配关键技术研究》由会员分享，可在线阅读，更多相关《基于结构化联接的xml查询模式匹配关键技术研究（99页珍藏版）》请在金锄头文库上搜索。
1、复旦大学 博士学位论文 基于结构化联接的XML查询模式匹配关键技术研究 姓名：庞引明 申请学位级别：博士 专业：计算机软件与理论 指导教师：施伯乐;汪卫 20040504 摘要 这篇论文主要讨论了基于结构化联接的X M L 查询模式匹配的相关关键技 术。提n5 了包含段划分的概念，并据此提出基于包含段划分的结构化联接新方法。 件也含段概念的基础上，研究了联接次序选择的问题，对隐检整枝联接方法进行 7 扩艘。对运崩基于包含段的隐检整技联接算法查询X M L 流数捌也提出厂个 蝌扶框架。最后，划影响查询系统性能较大的X M L 模式树的最小化问题也进行 J 7 探讨。 这篇论文首先从整树匹配和基于
2、索引结点的模式匹配两个方旺n 对X M L 奄询 匹配的相关研究进行了综述为该方向的研究现状勾勒出一个较为清晰的轮廓， 也为确立本文研究的意义和必要性奠定了基础。 该篇论文的主要贡献有以下几个方面： 针列。结构化联接所基于的三元组索引结构进行了研究，提出列索引窄I r ：i j 结构 进行包含段划分的思想，并据此对结构化联接算法进行了改进。 转于结构化联接操作的隐检整枝联接算法也是以三元组索引为基础的。我们 同样将包含段划分的概念引入到这一领域中来。首先研究基于包含段划分的 隐愉孵枝联接方法。叉运用包含段划分的概念对隐榆祭枝匹配力“法t I ，联接；4 i j 弘选择的问题进行了研宄。从上述两
3、个方面对隐检整枝联接算法进行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
4、 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
5、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
6、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 ) 和
7、多类型约束( 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 上的二：元关系- y R X R 丫RX R ( Y R XXXX S e g m e n t s YYYY 八R 0 0 A 篪 T r e
8、 e 矧厶心 图4 4 隐检整枝联接算法中两联接结点之间的可能位置情况 引理4 3 ：设V q x Q X ，我们有g e t N e x t ( q x ) = q x N ，则下面的性质成立： q x N 存在一个最小后代扩展； V q x s u b t r e e N o d e s ( q x N ) ，I n p u t L i s t q ) c 的第一个结点为h a r ： 无论( a ) q x = q x N 或者( b ) p a r e n t ( q x N ) 均不含有一个由q X N 产生的最小后 代扩展。换句话说，以p = p a r e n t ( q x N
9、 ) 为根的采用h p 的解答，不使用h q 。， 而使用S t a r t P o s 值大于h 。的那些结点来扩展解答。口 使用上面的引理，我们可以证明【4 9 】，当g e t N e x t 函数返回q X N 结点时，h q x N 保证会产生一个后代扩展在s u b t r e e N o d e s ( q x N ) 中。我们还可以证明【4 6 】，使用 h q 。N 来扩展解答的q x N 的祖先结点一定在h q x N 之前被g e t N e x t 函数返回。 于是，我们u J 以为查询模式Q X 小的每一一个查询结点q x 保持。- 生元素绵点， 这些结点组成解答的一
10、部分，并且还包含s u b t r e e N o d e s ( q x ) 5 b 的其它结点。这 样，每当q X N = g e t N e x t ( q x ) 为- - 个叶子结点时，我们就可以输出一个使用h q x N 扩展出的解答。 上面的引理构成算法T w i g S t a c k C S 正确性的基础。 我们考虑与【4 9 】中同样的例子，便于进行比较。因为【4 6 】并不考虑隐检聱技 联接算法中的多余结点的跳转I 司题，我们仅仅考虑将我们的算法与【4 9 】( 采用 X R - t r e e 索引跳过无用结点) 中的相关算法进行比较。 例4 2 ： 设查询模式树为a
11、b C ，其索引结构如下图所示 a 7 b 4b 5 c 8c t l c 7 c 90 1 0o t 2 图4 5 查询模式A b C 和索引结点序列 图4 5 中的元素结点集来自1 4 9 】中的f i g u r e l 所示的X M L 文档举例。我们从 图45 中可以清楚地看出，索引结点序列在空间结构上具有我们上文中所证明过 的特点。 我们分别对上述例子使用算法T S G e n e r i c ( f 4 9 】) 和算法T w i g S t a c k C S ，得 到访问过的元素结点序Y U ( 直到第一个成功的匹配被发现) 如下表所示： 算法访问过的元素结点序列 T S G
12、 e n e r i c ( 8 1 由1 ，0 1 ) ( 8 1 t b l ，0 2 ) ( a 1 ，b 1 ，c 3 ) ( a 1 b 1 ，c 4 ) 。( a 1 鱼1 。c 至) ( a 5 ，b 2 c _ 6 ) ( a 5 ，垒3 鳋) ( a 5 垒幽) ( 旦z 乜l 曼9 ) ( 划线的部分表示是s o l u t i o ne x t e n s i o n s 的一部分) T w i g S t a c k ( a 1 b 1 ，c 1 ) ( a 1 b l ，c 2 ) ( a 1 ，p 1 ，c 4 ) ( a l ，b 4 ，c 8 ) ( a l ，
13、b 4 ，c 9 ) ( 自z ，如，鲰) l 4 2 1 4 算法T w i g S t a c k C S 适用性 从本质上来讲，算法T w i g S t a c k - C S 就是利用包含段划分阶段所获得的信息 来忽略掉I n p u t L i s t 中不参加隐检整枝联接算法的元素结点，从而达到提供系统 效率的目的的。 这样说来，算法T w i g S t a c k - C S 最适宜的应用范围是： 1 )I n p u t L i s t 中只有比例较少的结点参加实际的隐检整枝联接过程，换旬 兰砘 兰 L 专乱 吣丢兰如 丁 话说，I n p u t L i s t 中的“有
14、效”成分所占比例较少 2 )含I n p u t L i s t 中有较多的分支子序列( b r a n c h i n gs u b s e q u e n c e s ) ( 尤 其是原始分支数p r i m i t i v eb r a n c h e s ) ； 3 ) 上述结论与C S 的长度关系不大。 而事实上，上面提到的算法适用范围也是其它以跳转为基础的 ( j u m p i n g b a s e d ) 算法，1 ；1 ，女1 4 6 4 9 1 等的共同限制。 我们给出一个极端的例子来看一看算法( T w i g S t a c k ，T S G e n e r i c
15、a n d T w i g S t a c k C S ) 在这种情况下的运行状况。 例4 3 ： A ， B ， A 2 B ， A 1 甲B 1 甲q 甲 A 婶B z 90 2 0 , A ：。68 。0 。c ：。d ( b ) I n p u t L i s tA 1 1 ，1 3 一C n 图4 6 一个棱端的例子 Ao l I Bo I I C O ( C ) 查询模式 在图4 6 所示的这种情况下，当我们试图去匹配( c ) 中的查询模式时，我们将 会发现模式匹配栈中的S 舳S B i S c k 将异常繁忙。我们将会联接运算C 1 和B 1 。 A 1 ；C 2 和B 1 ，
16、A 1 ，还有B 2 A 2 ；。如此一来，I n p u t L i s t 将会蜕变为完全 由长度为一的包含段组成的结点序列。我们将这种现象称为“颠簸”( d i t h e r i n g ) 。 oloIol9f o I 段片档文 LMX 忸 olololo 晚 卧 & 在这种极端的例子中，算法T S G e n e r i c 和T w i g S t a c k - C S 中的略过多余结点的 跳转动作将根本不会发生! 不过，由于没有定义过多的跳转动作，算法T w i g S t a c k 却在此种环境下没有过多的效率损失。 4 2 1 5 算法T w i g S t a c k - C S 的正确性及复杂度 定理4 2 正确性) ：假设给定一个结点输入序列i n p u t L i s t ，按照它的S t a r t
