(论文)XML模式中隐式冗余不存在的充要条件

计算机研究与发展 I S S N1 0 0 0 一1 2 3 9 C N1 1 1 7 7 7 T P J o l 】丌l a lo fC o m p u t e rR 黯e a r c ha n dD e v e I o p m e n t 4 4 ( 1 2 ) ：2 1 0 6 2 l l1 2 0 0 7 x M L 模式中隐式冗余不存在的充要条件 吴永辉 ( 复旦大学计算机科学与工程系上海2 0 0 4 3 3 ) ( 中国科学院计算机科学重点实验室北京1 0 0 0 8 0 ) ( y h w u f u d a n e d u c n ) T h eS u f f i c i e n ta n dN e c e s s a r yC o n d i t j o nf o rN oI m p l i c i tR e d u n d a n c i e si na nX M L S c h e m a W uY o n g h u i ( 肼加以m 阴f0 ，凸m 加舯搪n 弹4 “b g i n 盯n g ，M i t 盯i 灯，乩4 增 毹2 0 0 4 3 3 ) ( K 目L 口幻m 如哪0 ，G 删却把r 姗瞳，既i ，心血n d 硎，0 ，枷哪，B 嘶i n g1 0 0 0 8 0 ) 、 A b s t r a c tX M Lh a se m e r g e da s as t a n d a r df o rd a t ar e p r e S e n t a t i o na n di n t e r c h a n g e 。nt h eI n t e m e t N o 瑚a l l yt h ef i r s ts t 印f o rb u i l d i n ga nx M La p p I i c a t i o ni sx M Ld a t a b a S es c h e m ad e s i g n N o m a l l z a t i o n d e s i g no fX M Ld a t a b a s es c h e m ai sg e n e r a t i n gas e to fr e l a t e dX M Ls c h e m a so rD T D st h a tc a nr e p r e s e n td a t 8 d e p e n d e n c i e sa n de I i m i n a t er e d u n d a n c i e s ，i no r d e rt om a k ei n f o r m a t i o nr e t r i e v a lb e t t e r T h er e a s o nw h v r e d u n d a n c i e se x i s ti na nX M Ld a t a b a s es c h e m ai st h a tt h e r ee x i s ts o m ed a t ad e D e n d e n c i 髓i ni t S 0 r e l a t i o n s h i pb e t w e e nd a t ad e p e n d e n c i e sa n dr e d u n d a n c i e si na nX M Ld a t a b a s es c h e m ai sak e yp r 。b l e mf o r r e s e a r c h e so ni t sn o r r n a l l z a t i o nd e s i g n B u tt h e r ei sn or e s e a r c ho ni tn o w D a t ad e p e n d e n c i e si na nX M L d a t a b a s es c h e m ac o n s i s to fd a t ad e p e n d e n c i e sa m o r l ga t t “b u t e sa n da m o n ge l e m e n t s D a t ad e p e n d e n c i 髓i n a nX M Ld a t a b a s es c h e m ab ys y n t h e s i z i n gd a t ad e p e n d e n c i e sa m o n ga t t r i b u t e sa n da m o n ge I e m e n t sa r e d e f i n e d ，i m p I i c i tr e d u n d a n c 洒r e l a t i r l gt oi ta r ea n a l y z e d ，a r l ds e m i n o m a lX M Ls c h e m aa n dn o r m a lX M L s c h e m aa r ed e f i n e db a s e do ni t T h e nt h es u f f i c i e n ta n dn e c e s s a r yc o n d l t i o nt h a tn oi m p l i c i tr e d u n d a n c i e s e x i s ti na nX M Ls c h e m ai f ft h eX M Ls c h e m ai sn o r m a l I sD r o v e d T h i sw o r kl a v sat h e o r e t i c a lf o u n d a t i o n f o rt h ef u r t h e rr e s e a r c ho nn o r m a l i z a t i o nd e s i g no fX M Ld a t a b a s es c h e m a K e yw o r d s X M Ld a t a b a s es c h e m a ；X M Ls c h e m at r e e ；d a t ad e p e n d e n c y ；i m p l i c i tr e d u n d a n c y ；i d e n t i f i e r 摘要X M L 敷据库模式规范化设计是产生一组相关联的、能表示数据间依赖关系、而且消除了冗余的 x M L 模式或D T D ，以更好地进行信息检索x M L 数据库模式中某些数据依赖的存在是冗余存在的原 因因此在X M L 数据库模式中数据依赖与冗余的关联是其规范化设计研究的关键问题，但对这一问题 目前还没有专门的研究x M L 敷据库模式的数据依粕包括属性闻数据依赖和元素阉的数据依赖，给出 综合了属性阃和元素间数据依赖的x M L 数据库模式数据依齄的定义，分析与之关联的隐式冗余，并论 证x M L 模式中隐式冗余不存在当且仅当该x M L 模式是规范的，为x M L 教据库模式规范化设计更深 一层的研究奠定理论基础 美键词X M L 数据库模式；X M L 模式树；数据依赖；隐式冗奈；标识符 中围法分类号T P 3 1 1 1 3 l 近年来，随着互联网的发展，网上的信息呈爆炸 增长趋势，产生了结构非常复杂的、海量的数据；同 时x M L 已经成为互联网上数据表示和交换的主要 工具建立一个x M L 应用的第一步通常是设计 收穑日期：2 0 0 6 一0 9 一l l ；修回日期：2 0 0 70 6I l 基金项目：上海市自然科学基金项目( 0 6 z R l 4 0 1 3 ) ；中国科学院计算机科学重点实验室开放课题基金项目( s Y s K F D 6 0 3 ) 万方数据 吴永辉：x M L 模式中隐式冗余不存在的充要条件2 1 0 ， x M L 数据库模式所以，当前面临着如何通过 x M L 来合理地组织在互联网上的海量信息的问题 而x M L 数据库模式规范化设计，就是根据元素和 属性集合及其数据依赖，设计出一组相关联的、能很 好地表示数据问依赖关系、而且消除了各种冗余的 x M L 模式或D T D ，以更好地进行信息检索 目前x M L 数据库模式规范化设计的研究工作 主要是基于P r o v o s t 提出的将关系数据库理论应用 于x M L 数据库模式规范化设计的思想，有代表 性的工作有：A r e n a s 和L i b k i n 给出x M L 函数依赖 的概念，定义x M L 模式的范式x N F ，并提出将一个 任意的D T D 转化为一个符合X N F 的D T D 的算法， 这一算法通过转移属性和建立新的元素类型来实现 D T D 的规范化设计o ；L i n g 和L e e 定义半结构化 模式的范式S 3 一N F ，N F S S 和O R A s S 给出将一个 半结构化模式转化为一个满足某个范式的x M L 模 式的算法，这一算法是通过规范化规则对半结构化 模式进行重新构造，以实现x M L 模式的规范化设 计【4 。1 ；v i n c e n t 基于x M L 中属性间的F D 和M v D ， 定义x F D 和x M v D 以及相关联的范式，并论证范 式中的数据依赖的保持【6 。7J 因为这些研究的指导思想基于关系数据库理 论所以这些研究存在的共同问题足将x M L 模式 中属性间的数据依赖作为x M L 数据库模式的数据 依赖；这些研究没有对x M L 数据库模式的冗余进 行分析，给出的范式的定义也没有体现保持数据依 赖和消除各类冗余的性质而x M L 数据库模式的 数据依赖复杂，包括属性间的数据依赖和元素间的 数据依赖，数据依赖的形式包括单值依赖和多值依 赖，并且X M L 数据库模式中某些数据依赖关系的 存在是冗余存在的内在原因因此这些研究给出的 规范化设计算法也不能很好地实现“保持数据间依 赖关系、消除冗余”的目标 在X M L 数据库模式规范化设计的研究中， x M L 数据库模式的数据依赖与冗余的关联是一个 关键问题，这一问题的解决将为高质量的x M L 数 据库模式规范化设计奠定理论基础 在以往的工作中，以数据依赖及其所关联的冗 余作为切人点，并基于此实现和验证相应的规范化 设计算法_ 8 1 “在上述研究的基础上，将数据依赖 的研究深入到属性的层面，分析与之关联的隐式冗 余论证在x M L 模式中隐式冗余不存在的充要 条件 1 x M L 数据库模式的数据依赖和隐式冗余 1 1x M L 数据库模式的数据依赖 定义1 元素标识符和标识符设元素e 包含 的属性集为 。l ，口， 如果K 4 l ，d 。l ， 并且K ln l “，n 。 是完全函数依赖，则称K 为P 的元素标识符；将K 一 n 1 一，口。 分解为一组原 子函数依赖表达式，在这些原子函数依赖表达式的 左端中选择一组构成K 的划分，这一划分中的块， 即某个原子函数依赖表达式的左端，称为e 的标识 符；而这一划分称为e 的标识符集合如果e 不包 含属性，则e 本身为e 的元素标识符和标识符 定义2 x M L 模式树一个x M L 模式被定义 为一棵带权有根树了1 ( V ，r ；E ；w f ) ；其中顶点集 v 表示x M L 模式x 中的元素集合，v 中每个顶点 对应x 中的一个元素，e v ，一z ( e ) 为元素e 的标 识符组成的集合；，v ，r 为了1 的树根，表示根元 素；E 是由T 的弧集组成，如果( n ，6 ) E ，则元素 n 包含元素6 T 被称为相应于该x M L 模式的 x M L 模式树 定义3 标识符依赖( i d t m e rd e 唧d e n 叮，I D ) 设。是一个标识符集合，x ，y 0 并且z = o X Uy 如果对于在x 中的每个实例z ，根据语义关 系，在y 中一定存在相应的实例y 可以被访问，则 在。上x 和y 之问存在着标识符依赖如果对于 在x 中的每个实例z ，在y 中仅存在一个相应的实 例，被访问，则在。上x 和Y 之间存在着标识符 单值依赖( s i n g l e v a l u e dd e p e n d e n c y ，s D ) ，表示为X l r ；如果对于在x 中的每个实例z ，在l r 中存在一 组相应的实例，可以被访问，并且对于任意的z 7 z ，在x U z7 中相应于工的任意实例z z ，在y 中与 之关联的是相同的组相应的实例，；则在。上X 和y 之间存在着标识符多值依赖( m u l t i v a l u e d d 印e n d e n c y ，M D ) ，表示为x _ 呻y S D ，M D 与关系数据库理论中的F D ，M v D 类 似，因此，可以相似地给出其推导公理，并证明其完 备性和有效性M D 推导公理为M D l ( 自反公理) ， M D 2 ( 增广规则) ，M D 3 ( 传递规则) ，M D 4 ( 补规则) ， M D 5 ( 平凡补规则) S n M D 推导公理如下 S n M D l ：X y 蕴涵X 斗一y S D M D 2 ：X 斗一y ，Z W ，w 量y 且y n z = 囝蕴涵x w 万方数据 2 1 0 8 计算机研究与发展2 0 0 7 ，4 4 ( 1 2 ) 定义4 依赖基设。是一个标识符集合，J 是 O 上的个I D 的集合，x 0 ，x 在。上相应于j 的依赖基D E P ( x ) = Iy l ，y 。I y I ，”，y 。l 是 。一X 的一个划分；x 斗Y ，或者X 一斗Y ：成立；并 且不存在w c y ，使得相应的x 一和X 一一 成立，f 二1 ，” D E P ，( x ) 中的元素称为x 的依 赖元 设丁是一棵X M L 模式树，且P = ( “，“ ) 是T 中的一条弧对T 定义如下标识：F ( 口) = “； A ( 。) = w z ( 口) U m z ( ”1 ) U U z ( ) ，其中 ”l ，口。是v 的所有祖先结点；D ( 。) = w z ( ”) U z ( 口1 ) U U r ( 口。) ，其中口”，口。是口的所 有后继结点；D ( 丁) = z ( _ ) U U z ( 口。) ，其中 ”l ，口。是T 中的所有结点 定义s 半规范的x M L 模式设0 是一个标 识符集合，I 是。上的一个I D 的集合，T 是一棵 x M L 模式树，o ( T ) 0 ，f7 是j 在O ( T ) 上成立的 I D 集合如果对T 的每条弧P = ( “口) ，蕴涵 M D ：A ( “) - D ( ”) ，则T 被称为相应于J 的半规 范的X M L 模式树，T 对应的x M L 模式被称为相应 于f 的半规范的x M L 模式 对于相应于，的半规范的x M L 模式树T ，令 M D ( T ) 表示T 中的所有弧对应的M D 集合S D ( 丁) 表示J 蕴涵的在0 ( T ) 上成立的s D 集合，在O ( T ) 上成立的I D 集合I D ( T ) = 疽D ( 丁) U s D ( T ) 定义6 规范的x M L 模式设。是一个标识 符集台，是O 上的一个I D 的集合，T 是相应于J 的一棵半规范的x M L 模式树，O ( T ) O ，M7 是f 在o ( T ) 上成立的M D 集合如果M 与M D ( 1 1 ) 等 价；并且，如果x A 是，在o ( T ) 上蕴涵的非平凡 的s D ，A 是标识符，。是T 中的顶点，A 御z ( w ) ， 则J 蕴涵x A ( 。) ；那么丁是相应于f 的规范的 x M L 模式树，与T 相应的x M L 模式是相应于，的 规范的X M L 模式 定义7 模式树的有向路x M L 模式树T 的一 个有向路是一个结点序列”l ，”2 ，口。，其中。l 是T 的根r ，口。是1 1 的叶结点，巩是q + I 的父亲结 点，l i m 一1 1 2x M L 模式中的隐式冗余 定义8 合适的X M L 文档如果在X M L 文档 中任何两个不同实例的根元素取值不同，则称该 x M L 文档为合适的x M L 文档 定义9 隐式冗余设0 是一个标识符集合，J 是。上的I D 集合，丁是相应于，的一棵半规范的 x M L 模式树，o ( T ) o ，x Uy 0 ( 了1 ) ，存在标 识符A y ，A 在x ；z = 0 ( T ) 一X Uy 并设r 是 相应于T 的合适的x M L 文档。r 1 和7 2 是该x M L 文档的两个不同实例，l 和2 是分别对r l 和，2 进 行非嵌套化操作产生的两个不同元组集合中的元 组如果x y 被J 蕴涵，l ( x ) = f2 ( x ) ；或者，如 果在O ( T ) 上X 一一y 被j 蕴涵，1 ( x ) = 2 ( x ) ， f l ( y ) = 2 ( y ) ，o l ( z ) 2 ( z ) ；则相应于x 斗y 或x 一一y ，T 对应的x M L 模式存在隐式冗余 2x M L 模式中隐式冗余不存在的充要条件 2 1x M L 模式中隐式冗余不存在的充分条件 引理1 设0 是标识符集，I 是。上的I D 集 合，T 是相应于J 的半规范的x M L 模式树，O ( 1 、) 量o ，x Uy O ( T ) 如果X 斗一y 被M D ( T ) 蕴 涵，并对任意这样的标识符A ，A y 且A 矗x A w z ( “ ) ，其中”是T 中的顶点；那么f ( 口) X Uy 引理2 设0 是标识符集，丁是相应于f 的半 规范的x M L 模式树，o ( T ) o ，x Uy O ( T ) 如果x _ 一y 是M D ( T ) 蕴涵的一个M D ，对任意 这样的标识符A ，A y ，A 告x ，A 倔“口) ，其中 口是T 中的顶点，那么A ( ”) E x Uy ，D ( 口) x U y 引理3 设O 是标识符集，M 和S 分别是O 上 的M D 集合和s D 集合丁是相应于M Us 的半规 范的x M L 模式树，0 ( 丁) O ，M 7 和s 分别是M 和s 在0 ( 丁) 上成立的M D 集合和s D 集合并设 ，7 = ( M U S ) + 那么在o ( T ) 上，“= ， 引理4 O 是标识符集，是0 上的I D 集合 T 是相应于，的半规范的x M L 模式树，O ( T ) o 如果x Uy 0 ( 丁) ，X + 是在O ( T ) 上x 相应 于，的闭包，则f 在o ( T ) 蕴涵x 一一y 当且仅当 在0 ( 丁) 上蕴涵X + 一一y 引理1 至引理4 证明见文献 1 2 引理5 设T 是相应于J 的半规范的x M L 模 式树，r 是T 对应的合适的x M L 文档，A 是一个标 识符，A z ( v ) ，其中”是丁中的顶点，如果J 和f z 是对r 进行非嵌套化操作产生的不同的元组， f l ( A ( 口) ) = 2 ( A ( 口) ) ，那么f l 和2 是在同一实 例中的元组 定理1 设。是标识符集，J 是0 上的I D 集 合，T 是x M L 模式树，O ( 丁) 0 如果T 是相应 万方数据 吴永辉：X M L 模式中隐式冗余不存在的充要条件2 1 0 9 于I 的规范的x M L 模式树，那么T 相应的x M L 模 式没有隐式冗余 证明假设T 相应的x M L 模式存在隐式冗 余，那么引起隐式冗余的I D 或者是s D ，或者是 M D 如果引起冗余的I D 是s Dx A ，则存在相应 于T 的合适的x M L 文档r ，l 和r 2 是r 的两个不 同实例，f l 和2 是分别对r 1 和r 2 进行非嵌套化操 作产生的两个不同元组集合中的元组，( x ) = z 2 ( x ) 在T 中存在顶点o ，A 懈( o ) 因为A 在 x ，x A 是非平凡的，T 是相应于J 的规范的 x M L 模式树，则X A ( 口) ，所以f 】( A ( 口) ) = 2 ( A ( v ) ) 则由引理5 ，f 1 和0 2 是在同一实例中的元组， 导致矛盾 所以，如果T 相应于，存在隐式冗余，那么隐 式冗余不是由s D 引起的 如果引起冗余的I D 是M Dx 一一y ，存在标识 符A y x ，则存在相应于T 的合适的x M L 文 档r ，1 和r 2 是两个不同的实例，f 1 和2 是分别对 r l 和r 2 进行非嵌套化操作产生的两个不同元组集 合中的元组，fJ ( x ) = f 2 ( x ) ，f 】( y ) = 2 ( y ) ，l ( z ) f 2 ( z ) ，并且z 因为y g x ，x 一一y 是非平凡的M D T 是相应于J 的规范的X M L 模式树，J 7 是J 在 O ( T ) 上成立的I D 集合，则J 7 等价于m ( 丁) ，所以 f D ( T ) 蕴涵x _ Y 由M D2 ，m ( T ) 蕴涵0 ( T ) 上的x + 一呻y 由引理3 ，I = J ，因为x U x + o ( T ) 和f l ( x ) = 0 2 ( x ) ，所以l ( x + ) = 2 ( X + ) 如果A x + ，在了中存在顶点”，A 御f ( v ) ，所以t l ( A ( v ) ) = 2 ( A ( 口) ) ，由引理5 ，导致矛 盾，所以A 每x + ；如果z x + ，则1 ( z ) = 2 ( z ) ， 这与l ( z ) f 2 ( z ) 矛盾，所以z 壁x + 设z7 = O ( 丁) 一( x + Uy ) ，因为Z = O ( T ) 一( x Uy ) ，z 垡 x + ，z 固，所以z7 因为A y ，而且A 奇 x + ，所以y 垂x + ；又因z ，并且x + 一一y 是 非平凡的因为x + Uy O ( 了1 ) ，x + 呻一y 是非 平凡的，A y ，A 在x + ，并且在丁中存在顶点。， A 抛z ( “ ) ，则由引理2 ，A ( 。) x + Uy 因为。 ( X + ) = 2 ( X + ) ，f l ( y ) = 2 ( y ) ，所以l ( X + U y ) = 幻( x + Uy ) 又因为A ( 口) x + Uy ，所以 1 ( A ( F ) ) = 2 ( A ( 口) ) ；由引理5 ，1 和0 2 是在同 一实例中的元组，导致矛盾 所以隐式冗余也不可能由M D 引起 所以丁对应的x M L 模式没有隐式冗余 证毕 2 2x M L 模式中隐式冗余不存在的必要条件 引理6 设O 是标识符集，是。上成立的I D 集合，T 是相应于，的半规范的x M L 模式树，O ( T ) O 并设x 斗斗y 是j 在O ( 丁) 上蕴涵的一 个M D 如果M D ( T ) 不蕴涵x 斗一y ，则在了1 中 存在有向路p ，p 包含的标识符组成的集合是P ，( y x ) n P 0 和( 0 ( T ) 一( x U y ) ) n P 成立 证明设Z = 0 ( T ) 一( x Uy ) ，x M L 模式树 T 的有向路为p 1 ，p 2 ，“，这些有向路包含的相 应标识符集合为P l ，P 2 ，P 。，n 1 假设命题不 成立，即对所有的i ( i = 1 ，2 ，n ) ，( y x ) n 只= ，或者( o ( 了1 ) 一( x Uy ) ) n 只= 囝；则P 。 X U z ，或者P ，x U y 如果对所有的f ( i = 1 ，2 ，n ) ，P ，x Uy ， 因为P l U P 2 U U 尸。= o ( T ) ，所以X Uy=o ( T ) ，则x - + y 是平凡的因此M D ( T ) 蕴涵x 一一y 。所以导致矛盾 同理，如果对所有的i ( i = 1 ，2 ，n ) ，P ，量 X U Z ，所以x U z = o ( T ) ，则x 斗斗z 是平凡的 因此朋D ( 丁) 蕴涵x 一一y ，也导致矛盾 所以，如果上述假设成立，那么对于T 的有向 路集合 户l ，p 2 ，丸 ，存在m ，1 m n ；当1 i m 时，P ：x Uy ；当m 十1 i n ，设P ：x U Z 设V = P l U P 2 U U P 。，1 = P 。+ l U U P 。 设有向路p 。的结点“。是在A 中满足( “：) y nw 的所有结点中离根结点距离最远的结点，1 i m 因为“。不是叶结点，所以“：有一个或多个 孩子，设轧是有向路A 上的“。的孩子A ( “：) 一一 D ( 口，) M D ( T ) ，因为A ( “：) y nw ，所以M D ( 丁) 蕴涵y n 一一D ( _ ，) 又因( v n w ) U D ( 口】) U U D ( 口，) = v ，所以M D ( T ) 蕴涵y n w 一V 因为v x Uy ，w x U z ，所以v nw ( x Uy ) n ( x U z ) 又因z = O ( 1 1 ) 一( x Uy ) ，所 以( X Uy ) n ( x U z ) = x ，则v n E x 因为v x Uy ，所以V x ( x Uy ) 一x ， 则v x y x 假设y x 车v x ，则存在标 识符A ，A y x ，A 每v X 设声为在T 中的 有向路，声包含的标识符集是P ，且A P 所以( y x ) n P 因为A y x ，所以A 每X ；又因 A 鹰y x ，所以A 在v 因为A P ，所以P 车v 因为y = P l U P 2 U U P 。，= 尸。+ l U U P 。， 所以声 户。+ l ，声。l ，即P E x U z ，P 壁x Uy ， 万方数据 2 1 1 0计算机研究与发展2 0 0 7 4 4 ( 1 2 ) 所以( o ( 丁) 一x Uy ) n P 0 由于( o ( T ) 一x U y ) n P 和( y x ) n P a 同时成立，与开 始给出的假设矛盾，所以y x v x 因为v X y X ，所以V X = y X 因为M D ( T ) 蕴涵v n 一一v ，并且v nw X ，所以x 一一V 则X 斗斗V x 又因为V X = y x ，所以x 一呻y X ，则M D ( T ) 蕴涵 x 一一y ，导致矛盾 因此，命题成立证毕 引理7 设。是标识符集，f 是。上的I D 集 合，T 是相应于J 的半规范的x M L 模式树，o ( T ) 0 ，f 是j 在O ( T ) 上成立的I D 集合如果存在 标识符A 和B 以及标识符集X 和z ，A o ( T ) ，B 0 ( T ) ，x O ( T ) ，Z o ( 丁) ，并且在丁中存在 顶点口，A 抛z ( 口) ，B A ( u ) ! A 苦z ，A 每x ，B z ，Z D E P ，一( x ) ，X 斗Z 在o ( T ) 上不成立，那么 相应于f ，丁相应的x M L 模式存在隐式冗余 证明对丁对应的x M L 文档进行非嵌套化操 作因为x z 在o ( T ) 上不成立，所以在产生元组 集合中存在这样的两个元组l 和2 ，t ( x ) = 2 ( x ) ，l ( Z ) 2 ( z ) 构造l 和2 如下：l 是所有 数据项都为口的元组2 ( 0 ( T ) 一z ) = f l ( 0 ( T ) 一z ) = n ，2 ( z ) 的数据项都为6 这样的x M L 文 档是合适的，并且z D E P f 一( x ) 成立，x 斗z 不 成立 因为B z ，则l ( B ) 2 ( B ) 因为A 苦z 并 且A 在x ，所以A 0 ( 丁) 一X U z ，则f l ( A ) = 0 2 ( A ) = n 因为A 抛z ( o ) ，B A ( ”) ，所以由定义 8 ，f l 和2 是在x M L 文档的不同实例“I 和“2 中 设y = D ( 丁) 一( x U z ) ，z D E P f 一( x ) ，所以 f 在O ( 丁) 上蕴涵x 一y 因为A O ( T ) 一( x U z ) 并且Y = O ( T ) 一( x UZ ) ，所以A Y 并且 A 奇x 因为z D P ，一( x ) ，并且x ，Z 不成立则 z n x = o 又因2 ( O ( 了1 ) 一z ) = l ( o ( T ) 一z ) = n ，y = 0 ( 丁) 一( x U z ) ，所以2 ( y ) = 1 ( y ) = 口 又因为I ( z ) 2 ( Z ) ，由定义9 ，x 斗斗y 导致隐 式冗余所以，相应于J ，丁对应的x M L 模式存在 隐式冗余证毕 引理8 设。是标识符集，J 是在0 上的I D 集 合，1 、是相应于J 的半规范的x M L 模式树，O ( T ) o 并设J7 是，在o ( 了 ) 上成立的I D 集合，M 7 是 I 在O ( 丁) 上成立的M D 集合如果M 与! D ( T ) 不等价，那么相应于J ，丁对应的x M L 模式存在隐 式冗余 证明因为T 是相应于J 的半规范的x M L 模 式树，并且M 7 与1 D ( T ) 不等价，所以M 蕴涵M D ( T ) ，并且在M 中至少存在一个M D 无法由M D ( 丁) 导出设在M 中x 一y 无法由M D ( T ) 导 出，并设x + 为x 在O ( T ) 上相应于J 7 的闭包则 由引理4 ，X + O ( 丁) ，M D ( 丁) 不蕴涵X + 斗斗y 由引理6 ，在T 中存在的一条有向路p ，其标识符集 合为P ，( y x + ) n P g ，( o ( T ) 一( x + Uy ) ) n P 又因为x x + ，所以M 蕴涵x + 一一 y 则存在z l 和z 2 ，z l D E 尸，一( x + ) ，z 2 D E P ， ( x + ) ，z ，量( y x + ) 并且zn P 是P 的非空真 子集，z 2 0 ( T ) 一( x + Uy ) 并且z 2 n P 是P 的 非空真子集设A I Z I n P ，A 2 z 2 n P ，则在丁 中存在顶点w l 和。2 ，A I z ( 口1 ) ，A 2 们z ( 口2 ) 因为A 。P ，A ：P ，所以。l 和”2 在有向路p 中 所以，“口1 ) A ( 口2 ) 或者m z ( 2 ) A ( 口1 ) 如 果抛z ( 口1 ) A ( ”2 ) ，设z 为z l ，B 为A l 且A 为 A 2 ；如果伽z ( 。2 ) E A ( _ 1 ) ，则设z 为z 2 ，B 为A 2 且A 为A 1 并设口 为T 中包含A 的结点，则A W ( ” ) ，B A ( “ A ) ，A 奇Z ，A 苦x + ，B z ，z D E P J 一( x + ) ；如果X + 一Z 因为 B 匕z ，则x + B ，那么z 不是x + 的依赖元，导致矛盾，所以X + 一 z 不成立则由引理7 ，相应于f ，T 对应的x M L 模 式存在隐式冗余证毕 引理9 设。是标识符集。f 是O 上的I D 集 合了1 是相应于J 的半规范的X M L 模式树，O ( T ) 0 ，f7 是J 在o ( T ) 上成立的I D 集合如果f 蕴 涵非平凡的s D X A ，x O ( T ) ，A O ( 丁) ，且 在T 中有顶点。，A 加z ( ”) ，x 斗 ( “ ) 不成立，则 丁对应的x M L 模式相应于J 存在隐式冗余， 证明因为x A 是非平凡的，所以A 每X 因为X A ( “ ) 不成立，所以存在一个标识符B A ( 口) 使得x 日不成立因为x B 不成立，则B 在x ，并且存在z D E P J ，( x ) 使得x z 不成立， B z 因为x 斗A ，所以A 在Z 由于A 抛f ( 口) ，B A ( 口) ，A 告Z ，A 在X ，B Z ，Z D E P ， ( x ) 使得x z 不成立，由引理7 ，所以T 对应的 x M L 模式相应于f 存在隐式冗余证毕 定理2 设。是标识符集，f 是在O 上成立的 I D 集合，T 是相应于f 的半规范的x M L 模式树，O ( T ) O 如果相应于J ，T 对应的x M L 模式没有 隐式冗余；则T 是相应于f 的规范的x M L 模式树 证明由引理8 和引理9 ，如果了、不是相应于j 的规范的x M L 模式树，则T 对应的x M L 模式存 在隐式冗余因此，如果相应于，。丁对应的x M L 模式没有隐式冗余；则T 是相应于J 的规范的 x M L 模式树 证毕 万方数据 吴永辉：x M L 模式中隐式冗余不存在的充要条件2 1 1 1 2 3x M L 模式中隐式冗余不存在的充要条件 定理3 设0 是标识符集，是在。上成立的 I D 集合，T 是相应于f 的半规范的x M L 模式树，0 ( T ) o 则相应于f ，T 没有隐式冗余当且仅当T 是规范的x M L 模式树 证明由定理1 和定理2 。命题成立证毕 3 结束语 论证了一个x M L 模式没有隐式冗余当且仅当 该x M L 模式是规范的，为x M L 数据库模式规范化 设计的更深一层研究奠定理论基础今后，将继续 以x M L 数据库模式数据依赖及其关联的冗余作为 x M L 数据库模式规范化设计研究的切入点，具体的 技术路线是：进一步分析x M L 数据库模式的数据 依赖集合不同覆盖的性质以及对规范化设计算法结 果的影响；定义规范覆盖，要求相应于规范覆盖，规 范化设计算法产生的x M L 数据库模式是不可分解 的和不可分裂的，并给出和验证获取规范覆盖的算 法；并在上述研究的基础上，实现和验证x M L 数据 库模式规范化设计算法 【2 3 4 参考文献 w i l lP r o 啪t N 。m l E i I l gx M L o L 】 h t t p ：一x I n I n p u “2 0 0 2 1 l 1 3 1 1 0 r n 】a l i z I n g h | m l ，2 0 0 2 一n 一1 3 M & 北d oA 雎皿s L e i dL I b k l n A 肿r m a lk nf o rX M L d 删毗s 【JJ A C MT f a 锄踊忸b a 靶S ”t e r 岫2 0 0 4 2 9 ( 1 ) ：1 9 5 0 3 2 M 出e kA 比n 曲L e o n i dL i b k m A nm f D r T r n 。nt h e o r e t 记 n p p r c ht 0n o n r l a lf o r m 3f o rr e b u o n da n dx M Ld a 协 J 】 J o u n o fd l e A c M ，2 0 0 5 ，5 2 ( 2 ) ：2 4 6 2 8 3 M o n L lL 鼬，T o kW a 哩L i l l g Am e t 1 0 d o l o g yf 。rn 八l c t 刊 n n j c t蛳h t ni nt l l eI n t 始t i 咖o fe n t l t y - 托I 舭I o n 小1 p s c h e n l a s J K I 】o w k d g ea n dI n 椭岫曲m e 胁，2 0 0 3 ，5 ( 2 ) ：2 2 5 - 2 4 7 5 】J l a h 肌gL u ，1 诜w a l l gL i n g c I 衅Y o 呜c l a n ，以“F n 蝇1 0 n e n c o d i r t oe x t e n d e dd e ”吖：o ne “i c i e n tp r o c 郫s i g0 f x M L 【c T h e3 l mI n t 1c o n o nV e 珂L 8 r g e 璐协B 螂 T r o n d h e i m 2 0 0 5 6 Mwv i 耻e n t Ju u ，cL n I s t 删礓f u n c t m dd e 畔n d 蚰c i 酋 姐dt h e i ra p 州c 舭l 叩t on o n m lf o r n 口i nx M L J 】A c MT f a 啮 锄D a 协h 靶S ”证r 璐2 0 0 4 ，2 9 ( 3 ) ：4 4 5 4 6 2 7 JL L u ，Mwv 眦蛐t ，cu u d “c h e c k L 艇m u l t l v a l u e d d e p e n d e n c l 曙i nx M L G I n ：P 删o fd 】e7 t hA s l a P i 6 c W e bc o n k 舢e L N C S3 3 9 9B e r “：S p 一雌e r 2 0 0 5 3 2 0 3 3 2 8 w u Y o r I g h u i H 埘a r c h I 踊ls c h e r n 辟d “g n 如r x M Ls c h e n 讲觚d D T 隗舯皿dL ；n l 饥d e s i g f I J 】J 。u m do fS 。f t w a r e ，加0 4 1 5 7 ) ：1 0 9 9 1 1 0 6 ( i nC h ) ( 吴永辉用于x M L 模式和m 规范化设计的层次模式设 计 J 软件学报2 0 0 4 ，1 5 ( 7 ) ：1 0 9 9 1 1 0 6 ) 9 w uY o n g h u i N o 皿d 啪t I o nd e “g no fx M Ld a t a h a 辩即h e r m e l i m i 删I g 科n I c t u r d 捌u n d a n d 临 J ，J o u r l l a lo f ( 旆p u t 盯 R e s e 眦ha dD e 她b p m 即t 2 0 0 4 。4 l ( 1 0 ) ：1 鲫9 一1 8 1 4 ( i “ C h l n e 咒) ( 吴永辉消除结构冗余的x M L 赦据库模式的规范化设计 J 计算机研究与发展2 0 0 4 4 “1 0 ) ：1 8 0 9 一1 8 1 4 ) 1 0 】w u Y o E l g h u I N o 舳I l 枷i 册d e s l g T lo f x M Ld a 汕a s e 妯e 曲f o r e I j 嘣t i ”gm r u c t u 州r e d u n d a n a e s I n t d l l g e ml n f 叫饵t i 叽 M 蛐雌e r 耻n ts y n e T I l sa n d T e c h 肿l 。g l 鹪，2 0 0 5 1 ( 3 ) ：3 9 0 一3 9 9 n 1 w u Y o 呕h u iN o 邢越啪t i 叽d 倒g no I x M Ld 毗a b 攒5 c h 廿T I a f o r d i 删I 碍t I n gr d u n d 蚰t 鸵h d n 丛a n d 盟t i s f yL n gl o s d e 舒j d n c I n ：P r o co fI E E E 九l c ，A C MI n t lC f w e bI n t d 蚰c e ( w I2 0 0 4 ) L 埔A l 吼i t ：I E E Ec o m p u t e rS o c m yP r e 路， 2 0 0 4 6 6 0 6 6 3 1 2 L 1 | I gB o w uY 饥g h u i N 种e 鼬r yc o n d m t l l a th l c “ 刚帅d a 眦i 曲d o