《用以更新XML文档的注释技术》由会员分享，可在线阅读，更多相关《用以更新XML文档的注释技术（5页珍藏版）》请在金锄头文库上搜索。
1、计算机科学2 0 0 2 V 0 1 2 9 N 9 8用以更新X M L 文档的注释技术A n n o t a t i o nT e c h n o l o g yU s e dt oU p d a t eX M LD o c u m e n t s岳昆胥正川周傲英宫学庆( 复旦大学计算机科学与工程系上海2 0 0 4 3 3 )A b s t r a c tR e a lw o r l da p p l i c a t i o n sh a v es h o w nt h a ts u p p o r t i n gu p d a t eo p e r a t i o ni sv e r
2、yi m p o r t a n tt oX M L I no r d e rt ou p d a t et h em u l t i p l er e l a t e dX M Ld o c u m e n t sw i t hk e yc o n s t r a i n t sa c c o r d i n gt oi t sr e l a t i o n a lv i e w ，w en e e dt ol o c a t et h eu p d a t e dn o d e si nX M Ld o c u m e n tw i t ht h e i rp a t hv a l u e
3、 I nt h i sp a p e r ，w ep r e s e n tan o v e la n n o t a t i o nt e c h n o l o g yw h i c hd e f i n e st h ep a t hv a l u eo fe a c h X M Ln o d et ob ei t sa n n o t a t i o ni n f o r m a t i o n ，m o r e o v e rd e f i n e st h ec o m b i n a t i o no fk e y a t t r i b u t e ( s )v a l u e
4、o fe a c ht u p l ei nt h ec o r r e s p o n d i n gn o m a l i z e dR D Bt ob et u p l e sa n n o t a t i o ni n f o r m a t i o n O nu p d a t i n gt h eR D B ，t h eu p d a t e dn o d e sc a nb el o c a t e de f f i c i e n t l yb ym a t c h i n gt h ep a t h v a l u eo ft h en o d e si nX M Lt r
5、e ew i t ht h a to ft h et u p l e si nR D B ，S Ot h a tu p d a t i n gX M Ld o c u m e n t sc a nb ei m p l e m e n t e d I na d d i t i o n ，w ep r e s e n ta ni m p r o v e da l g o r i t h mt og e tt h ea n n o t a t i o nw i t ht h em e t h o do fac e r t a i nh a s hf u n c t i o n K e y w o r
6、 d sK e yc o n s t r a i n t s ，U p d a t e ，P a t hv a l u e ，A n n o t a t i o n ，X M L引言随着X M L ( e X t e n s i b l eM a r k u pL a n g u a g e ) 在过去几年中的发展，X M L 被作为在线文档的语义保持标记语言，它现在已经成为一种异构系统问数 据交换的格式。一个简单的X M L 文档如图1 。在现实生活中，X M L 被广泛应用于各个方面 1 ，例如软 件组件状态保存方面，若用X M L 来描述对象的状 态，把要保存的对象以X M L 文档的形
7、式写入数据 流中，则对象状态的更新可以归结到X M L 文档的更新。此外。现实应用中多个相关文档的更新必须保持它们之间的一致性。为了适应现实中的多种需要、 真正使X M L 成为一种统一的数据表示和共享格 式，就必须允许用户定义X M L 的更新操作，并且利用相应技术对其进行有效的处理。本文首先回顾了相关的工作，并对文 2 ，3 中 X M L 键约束的定义作了简单的概括，此外为了使 X M L 文档中节点从根开始的路径值能唯一确定一个节点，我们定义了更强的X M L 键约束。然后利用 现有技术将X M L 文档以某种映射规则映射到关系数据库中，并对其进行了规范化。我们接着提出注释 技术，将X
8、 M L 文档中节点的路径值作为节点的注释信息，将相应规范化关系数据库中元组键属性值的组合作为元组的注释信息，当更新关系数据库时， 将X M L 节点的路径值和关系数据库中元组的注释 信息进行匹配，快速定位被更新节点，从而实现X M L 文档的更新。( d b ( b o o ki s b n = 1 2 3 ) ( t i t l e ) X M L ( a u t h o r T i mB r a y ( a u t h o r I n t r o d u c t i o n ( n a m e ) C o n c l u s i o n ( b o o k ( b o o ki s b
9、n = 2 3 4 ( t i t l e X M 乙( n a m e G e t t i n gA c p u a i n t e d ( s e c t i o nn u m b e r = 1 ( n a m e ) A t t r i b u t e s ( n a m e ) ( s e c t i o n ) b o o k ) d b )2 相关工作图1 一个X M L 文档在X M L 文档及其视图的变化检测、保存和注 释等方面，文 4 6 提出了不同的方法。文 4 提出 了d i f f 算法，它在X M L 的新旧版本之间检测未发 生变化的子树，试图通过考查被匹配节点的祖
10、先及 后代节点以匹配尽可能多的节点。针对具有键结构的层次数据，文E s 提出了存档( A r c h i v i n g ) 技术，对 X M L 文档中的节点进行注释，以统一的方式保存 发生变化的多个X M L 文档版本，用一个X M L 文档 来记录重复出现在多个X M L 文档中节点的相关时间戳及版本信息。文 6 提出了用注释技术实现视图4 7 更新的理论依据和一般方法。X M L 文档的更薪是一个新的研究方向，文 7 通过扩展X Q u e r y 查询语言定义了X M L 数据的更 新操作，把X M L 数据映射到关系数据库中作为 X M L 的视图，用S Q L 语句实现这些操作。
11、但是，该文对更新操作的描述与处理中发生的不满足完整性 约束的异常情况、多个相关X M L 文档的一致更新及节点的有效定位等问题未从根本上给予解决。关系数据库是广泛使用的数据库技术【8 ，关于X M L 文档的关系存储问题有很多研究成果 9 ，但这 些方法都不能保证存储X M L 文档的关系模式具有 一致性，不能避免数据的插入、删除异常，原因在于在这样的映射规则下，得到的是非规范化的关系模 式。文 3 已得出结论：若X M L 文档满足其上键的约束，那么由某种映射规则得到的关系模式必定满足该键约束下的函数依赖，且在多项式时间内可解， 这样便可实现X M L 关系存储的规范化。5X M L 键完整
12、性约束5 1X M L 键的定义不同于关系数据库，X M L 数据是层次型的，可以表示为一棵树，树中节点带有标记( 1 a b e l ) ，文E T 对X M L 树模型作了定义。节点按其标记分为三类： 元素节点( E ) 、属性节点( A ) 和文本节点( S ) 。记 X M L 树为T ，根节点为r 。文E 2 对X M L 键作了全面的定义，简单概括如下：定义1 ( 节点等值)设X ，Y 是X M L 树T 中的任意两个节点，X 与Y 等值，记为x 一，Y ，是指：( 1 ) 其节点标记( n a m e 或s t r i n g ) 相等； ( 2 ) 以它们为根的子树也相等：即若
13、为A 或S ，其文本值( s t r i n g ) 相等；若为E ，其子女节点也等值。 定义2 ( 节点可达)若对T 中任意节点n 1 ，存 在节点n 2 ，n 1 可由路径p 到达n z ，则称n 2 由n 1 经过简单路径p 可达，记为T E p ( n l ，n 2 ) 。当且仅当( 1 )n l n 2 ，P 一；( 2 ) P = p z ，P 为简单路径。存在n T ，T = ( n l ，n ) ，n 2 是n 经过路径z 到达的节点。更 一般地，对于T 中任意节点，记n P 为T 中从n 经过P 可达的所有节点，若n r ，记为 P 。 定义5 ( X M L 键) X M
14、L 的键完整性约束是形如( Q ，( Q ，( P 。，P k ) ) 的表达式。其中Q ，Q ，为简单路径，P ；为可带* 的路径。Q 称为上下文路径，Q 称为目标集路径，P 。，P k 称为键路径。当 Q e 时，圣称为绝对键( 可记为( Q ， P 。，P 。 ) ) ，否则西称为相对键，前者是后者的特例。键的集合记为。目标集最终确定了定义键的对象，键路径是从目标集开始的简单路径表达式的集合。 定义4 ( X M L 树满足键约束) X M L 树T 3 满足键约束中，当且仅当对任意n Q ，n 1 ，n z n4 8 Q ， ，若任意i 1 ，k ，存在x n lE P ， ，Y n
15、。 P 。 ，有x 一。y n 1 = n 2 。 5 2 对X M L 键约束的限定和假设 为了能够正确地对X M L 文档中所有节点进行唯一的注释，基于文E s 中的阐述，我们对键约束作如下的限定和假设。 定义5 ( 键节点)若X M L 文档中某个节点有 键约束，则该节点称为键节点。换句话说，如果从根到某一节点的路径等于上下文路径和目标集路径的 连接，那么该节点是键节点。如上例中的b o o k 和c h a p t e r 。假设1对于任意键节点，从根开始到该节点的路径经过的所有节点均是键节点。如上例中，c h a p t e r 的n a m e 节点对应的路径为b o o k c
16、h a p t e r n a m e ，其中b o o k ，c h a p t e r ，f l a m e 均是键节点。 定义6 ( 边界路径、边界节点)给定键的集合，就对应一个从根到键节点的路径的集合。路径集合中的一条路径称为边界路径( f r o n t i e rp a t h ) ，当且 仅当该路径不是其他任何路径的合适前缀。可见，边 界路径与键路径为空的键相对应。一个节点称为边界节点，当且仅当从根开始到该节点的标记序列等于一条边界路径。如上例中的n a m e 。 假设2由以上定义及假设，在有键约束的 X M L 树模型中，任何未出现在边界节点之下的节点都是键节点。即边界节点之下不能再有键节点， 覆盖了树中的边界节点及位于边界节点之上的所有节点。定义7 ( 键值)对于某个键约束
