《并行xml文档数据分片技术研究》由会员分享，可在线阅读，更多相关《并行xml文档数据分片技术研究（4页珍藏版）》请在金锄头文库上搜索。
1、计算机科学2 0 0 2 V o i 2 9 N o 8 ( 增刊) 并行X M L 文档数据分片技术研究 R e s e a r c h0 1 2D a t aP a r t i t i o ni nP a r a l l e lX M LD o c u m e n t 吴刚于亚新王国仁于戈 ( 东北大学信息科学与工程学院 沈阳1 1 0 0 0 4 ) A b s t r a c t I no r d e rt Oo b t a i nh i g hp e r f o r m a n c ew h e ns t o r i n g ，i n d e x i n ga n dq u e r
2、y i n gX M Ld o c u m e n t sw i t hh u g es c a l e ，X M Ld o c u m e n t sm u s tb ep r o c e s s e di np a r a l l e l A l t h o u g hd a t ap a r t i t i o n i n gi nc o n v e n t i o n a lD B M Sh a sb e e nw e l ls t u d i e d ，s t r a t e g i e sa i m e da tX M Ld o c u m e n t Sf e a t u r e
3、 h a v en o tb e e ns t u d i e d T h i sp a p e r o c u s e so nt w ok i n d so fX M Ld a t ap a r t i t i o n i n gs t r a t e g i e sw i t h d i f f e r e n tP a r t i t i o nG r a n u l a r i t i e s ：P S P I Ba n dN R Rs t r a t e g i e s P S P I Bd i s t r i b u t e sX M Lp a t hi n s t a n c
4、e sb e l o n g i n gt Ot h es a m ep a t hs c h e m at ot h ep r o c e s s o r sa v e r a g e l y ；N R Rd i s t r i b u t e sX M L d o c u m e n tt Ot h ep r o c e s s o r sa c c o r d i n gt OE L E M E N Td e f i n i t i o n K e y w o r d sX M L ，P a r a l l e ld a t a b a s e ，P a r t i t i o n 1
5、引言 X M L 作为I n t e r n e t 数据表示和交换标准正成 为海量信息资源的新型载体。为存储、索引及查询 M 或G 字节X M L 文档时获得高效率，并行化是有 效方法之一。 X M L 这种半结构化数据与传统关系数据库和 对象数据库完全不同。半结构化数据的特性限制了 直接利用已有并行关系或对象数据库存储、索引和 查询X M L 文档数据的可能性。针对X M L 半结构化 特点设计的并行数据库系统将有助于解决以上问 题。数据分片对于并行数据库查询的性能影响很大， 因此有必要对并行X M L 文档数据库中采用的数据 分片策略进行深入研究。首先给出定义： 定义1 ( 分片粒度P
6、a r t i t i o nG r a n u l a r i t y ) 指并行数据库系统在进行物理存储时，多处理机之 间分布各种数据库对象( 关系、索引等) 的逻辑抽象 程度。 分片策略的制定应考虑分片粒度。决定分片粒 度的主要因素有：数据存储模型和数据查询策略。通 常X M L 文档数据被表现成图或树结构，相应的 X M L 查询语言也是基于路径表达式的。因而把分 片粒度定位在路径模式这种逻辑抽象程度上是一种 显然的想法。以路径模式为分片粒度的分片策略将 有助予基于路径表达式查询的并行化。E l e m e n t 是 X M L 标记的基本组成部分，因而也可以将D T D 中 定义的
7、元素作为分片的粒度，对符合该D T D 的 X M L 文档按照元素类型声明的不同进行分片。分 片粒度定位在元素这种逻辑抽象程度上有助于基于 路径表达式查询的流水线并行化。依以上两种分片 粒度，提出两种分片策略：基于路径模式的路径实例 均衡策略( P S P I B ) 和携带父亲信息的孩子节点轮循 策略( N R R ) 。 2 引例 图1X M L 文档简化D O M 树表示 下面结合一篇简单的X M L 文档解释两种分片 策略的原理。见图1 中简化表示的一篇X M L 文档 b o o k 。x m l ( 文 4 ) 。规定使用元索首字母来代表所 属的元素定义，其后跟整数以区别属于相同
8、元素定 义的不同元素实例。例如：b 车= b o o k ，t e = t i t l e ，a C ：寺a u t h o r 。s = s e c t i o n ，p 肆p a r a g r a p h ，f c ：* f i g u r e ，i t ：V i m a g e ；文本节点用T E X T 表示。并作如下假定：本文 中假定处理X M L 文档中元素不存在I D R E F 或 I D R E F S 属性；采用s h a r e dn o t h i n g 并行系统中处 理器数目为4 ；系统使用D O M 作为文档数据逻辑存 储模型；使用X Q u e r y 作为查
9、询语言。使用如下典型 * ) 教育部高校骨干教师计划、教育部跨世纪优秀人才基金吴刚硬士，研究方向为文档数据库、X M L 3 1 的基于路径的查询X Q u e r y 语句为查询示例：d o c u m e r i t ( ”b o o k x m l ) b o o k s e c t i o n t i t l e 。 5 基于路径模式的路径实例平衡分片策略 P S P I B P S P I B 分片策略是以路径模式为分片粒度的分 片策略。以D O M 为逻辑存储模型时，X M L 文档的 逻辑结构很像一棵树，更像包含多棵树的“森林”或 “丛林”。若把D O M 文档元素( D o c
10、 u m e n tE l e m e n t ) 称为D O M 树根元素；文本( T e x t ) 节点或无孩子元 素( E l e m e n t ) 节点称为叶子元素，则X M L 文档的一 条路径实例定义为： 定义2D O M 树中的每一条从D O M 根元素到 叶子元素的路径称为X M L 文档的一条路径实例， 表示为户一( ，e l ，e 2 ，e 。，) 。 ，L = D O M 树的根元素所对应的t a g n a m e ；t E T ， T 一 D O M 树的叶子元素所对应的t a g n a m e 。e ，E E ，E 一 D O M 树的任意元素所对应的t a
11、g n a m e ) ； e H 与e ，之间满足e H 所对应的D O M 对象是e ，所 对应的D O M 对象的父亲的关系。 定义5 对于任意一条路径实例，s C h ，P S ，z 称为一个路径模式。 h D O M 树根元素所对应t a g n a m e ；t T ，T = D O M 树叶子元素所对应t a g n a m e ) ；P S 一 ( 户，f P E E ，C E E ，户所对应D O M 对象是C 所对应D O M 对象父亲) 。 对X M L 文档的一条路径实例总可以进行抽 象，得到一个路径模式。 定义4 条路径实例对应一个路径模式过程 称为从路径实例抽取路径
12、模式。 可证这种从一条路径实例P 到一个路径模式s 的对应关系是一种映射关系。同理可证从一篇X M L 文档中所有路径实例的集合P H E T 到一 篇X M L 文档中的所有路径模式的集合S H P S T 之间的对应关系也是一种映射关系。 定义5 设X M L 上的路径模式集合上的相等 关系为“一”，如果路径模式s 。一( | 7 t 。，P S 。，t 。) 与路径 模式s 2 = ，( t ，T E X T ，T E X T ； s 2 一( b ， ( b ，a ) ，( a ，T E X T ，T E X T ) ； s 3 = ( b ，( ( b ，s ，( t ，T E X
13、T ，( s ，t ) ，T E X T ； s 4 一 ，C s ，s ，T E X T ； s 5 一( b ，( ( b ，s ，( t ，T E X T ，( S ，s ， ， ，( s ，f ，( f ，t ) ，T E X T ) ； s 7 = ， T E X T ； s 8 一 ，( s ，f ) ， ) ，i ) ； s 9 一( b ，( ( b ，s ，( s ，P ，( p ，T E X T ，T E X T ； s l o = ，( s ，f ) ，( f ，i ) ) ，i ； 根据每一个路径实例所属路径模式，按前述三 个条件分布到各场地上，并在该场地上与其他路径
14、实例合并，从而得到局部的D O M 树。如下面的4 个 图所示： 分片后备场地上路径模式实例数目如下：s ，： 1 ，0 ，0 ，0 ) ；s 2 ： 0 ，1 ，1 ，1 ) ；s 3 ： 1 ，1 ，0 ，0 ；S 4 ： 1 ，1 ， 1 ，1 ) ；s 5 ： 1 ，0 ，1 ，0 ) ；s s ： 0 ，0 ，0 ，1 ；S 7 ： 1 ，1 ，2 ，1 ) ； s 8 ： 0 ，l ，0 ，1 ；s 9 ： 0 ，1 ，1 ，1 ；s l o ： 1 ，0 ，0 ，0 。各场 地上实例总数为： 6 ，6 ，6 ，6 ) ： P S P I B 策略确定路径实例所在场地后，需将路 径
15、复制到相应场地，这将导致某些节点对象在数据 库全局逻辑视图中不唯一，如图2 5 ，s 。被复制到所 有场地。为解决此问题，采取在D O M 的数据库物理 绑定中增加对D O M 对象进行全局逻辑标识的方 法。这样复制到同一场地上的具有同一全局逻辑标 识的数据库物理对象被视为同一D O M 对象。合并 时只复制该场地上不存在的全局逻辑标识的数据库 物理对象。合并局部查询结果时，必须根据全局逻辑 标识消除重复的局部查询结果。 图2 场地1 上局部D O M 树 图3 场地2 上局部D O M 树 图4 场地3 上局部D O M 树 图5 场地4 上局部D O M 树 引例中的查询示例可制定如下并行
16、查询执行计 划：( 1 ) 抽取出对应的模式信息S 。；( 2 ) 根据对应统计 信息：S 。： 1 ，1 ，0 ，0 可知该模式在处理机1 和2 上； ( 3 ) 启动处理机1 和2 上的单处理机查询引擎执行该 X Q u e r y 查询。( 4 ) 将1 、2 场地上的局部查询结果，返 回前端机，根据全局逻辑标识合并成全局的查询结 果。 4 携带父亲信息的孩子节点轮循策略N R R N R R 策略以元素为分片粒度，相对P S P I B 分 片粒度更为细腻。N R R 类似分布式数据库中的垂直 分片。在分布式关系数据库中，利用分片属性分解一 个元组，再利用连接操作合并片断以保持元组完整 性。若把一条路径实例中所有元素根据对应D T D 中所属元素定义不同分布到不同场地，则同样可以 将棵D O M 树按分片目标分解开，而且可以按元 素间的父子关系连接合并
