(论文)XML的函数依赖

第2 9 卷第1 期 2 0 0 8 年1 月 东北大学学报(自然科学版) J o u r n a lo fN o r t h e a s t e r nU n i v e r s i t y ( N a t u r a lS c i e n c e ) V 0 1 2 9 ，N o 1 J a n 2008 X M L 的函数依赖 赵相国，王国仁，韩东红，丁大斌 ( 东北大学信息科学与工程学院，辽宁沈阳1 1 0 0 0 4 ) 摘要：为了表达引起数据冗余的X M L 函数依赖，研究了X M L 中存在的复杂的多种形式的函数依赖 约束，提出了一种D T D 的路径语言，对于导航和定位X M L 文档的内容具有较强的表达能力提出了一套 X M L 模式及文档的形式化描述方法，进而提出了一种X M L 函数依赖( X F D ) 的定义与以前的X M L 函数依 赖的定义进行比较，展示了X F D 可以表达更多的X M L 上存在的函数依赖，可以概括以前的基于路径表达式 定义的X M L 函数依赖的约束能力 关键词：Y d V L ；函数依赖；规范化；路径语言；数据约束 中图分类号：T P3 1 1 1 3文献标识码：A文章编号：1 0 0 5 3 0 2 6 ( 2 0 0 8 ) 0 1 0 0 5 7 0 4 F u n c t i o nD e p e n d e n c i e si nX M L Z H A OX i a n g - g u o ，W A N GG u o t e n ，H A ND o n g - h o n g ，D I N GD a b i n ( S c h o o lo fI n f o r m a t i o nS c i e n c e & E n g i n e e r i n g ，N o r t h e a s t e r nU n i v e r s i t y ，S h e n y a n g 11 0 0 0 4 ，C h i n a C o r r e s p o n d e n t ：Z H A OX i a n g - g u o ，E m a i l ：z h a o x i a n g g u o m a i l n e u e d u c n ) A b s t r a c t ：F u n c t i o n a ld e p e n d e n c yi Sa ni n t e g r a lp a r ti nt h en o r m a l i z a t i o nr e s e a r c ho nX M Ld a t a b a s e T oe x p r e s st h eX M Lf u n c t i o n a ld e p e n d e n c yw h i c hg i v er i s et od a t ar e d u n d a n c y v a r i o u s c o m p l i c a t e dc o n s t r a i n t so nf u n c t i o n a ld e p e n d e n c ya r ea n a l y z e dw i t hap a t hl a n g u a g ep r o p o s e do n D T Db a s i st og i v es t r o n g e re x p r e s s i o nt ot h en a v i g a t i o na n d1 0 c a t i o nf o r 、a nX M Ld o c u m e n t W i t h as e to fX M Ls c h e m e sa n dr e p r e s e n t a t i o nt of o r m a l i z ed o c u m e n t sp r e s e n t e d ak i n do fd e f i n i t i o no f X M Lf u n c t i o n a ld e p e n d e n c y ( X F D ) i sg i v e n C o m p a r i n gw i t ht h eX F Dd e f i n e dp r e v i o u s l y ，t h i s d e f i n i t i o no fX F Dc a ne x p r e s sm o r ef u n c t i o n a ld e p e n d e n c i e se x i s t i n gi nX M La n di sa v a i l a b l et o g e n e r a l i z ea b o u tt h ec o n s t r a i n a b i l i t i e so nt h ef u n c t i o n a ld e p e n d e n c i e sd e f i n e db e f o r eb yt h e e x p r e s s i o no fp a t h K e yw o r d s ：X M L ：f u n c t i o n a ld e p e n d e n c y ；n o r m a l i z a t i o n ；p a t h1 a n g u a g e ；d a t ac o n s t r a i n t X M L 的函数依赖在关系数据库中扮演着重 要的角色同样，这种数据约束机制将在X M L 数 据管理中发挥重要作用同关系数据库有关系模 式一样，X M L 也有自己的模式，如已发布的X M L D a t a ，X M LS c h e m a 与X M LD T D ，这些规范可描 述的语义信息不足以表示函数依赖 为把函数依赖扩展到X M L 上来，有一些研 究者在做这方面的工作文献 1 基于树元组的概 念提出了X M L 函数依赖( X F D ) ，即把D T D 当作 一个关系模式，D T D 上的所有路径当作模式的属 性；文献 2 基于最近节点( c l o s e s tn o d e ) 的概念提 出X F D ，类似于文献 3 中定义键的方法，最近节 点是指X F D 的左端和右端在X M L 文档树上映 射所得的节点，其路径实例具有最大的公共前缀； 文献 4 指出文献 1 和文献 2 两种定义在不考 虑空值时是等价的；文献 5 定义了局部( 1 0 c a l ) X F D ，类似于文献 3 中定义相对键的方法，描述 X M L 文档片段上的数据约束；文献 6 考虑了 X M L 数据库的层次性特征，提出了一种函数依赖 的定义；3 c 献 7 研究了X M L 键的逻辑蕴含与推 理规则；文献 8 综述了以前的X F D 的概念，提出 了一种通用的、D ( ( F D S ) 以上研究还有不足 之处，为说明问题，举例如下 例1如下是关于某学校的教务信息的 X M L 文档的D ，m ，学校包含多个公共课程和系， 每个系包含有系名、一组课程、一些教室和一些办 收稿日期：2 0 0 6 1 2 2 7 基金项目：国家自然科学基金资助项目( 6 0 5 7 3 0 8 9 ) ；高等学校科技创新工程重大项目( 7 0 6 0 1 6 ) 作者简介：赵相国( 1 9 7 3 一) ，男，吉林通化人，东j t 大学博士研究生；王国仁( 1 9 6 6 一) ，男，湖北崇阳人，东北大学教授，博士生导师 万方数据 5 8东北大学学报( 自然科学版)第2 9 卷 公室，教室包括教室号和所在楼号，办公室包括办 公室号、名称和所在楼号，课程有课程号和选此课 的学生列表，学生列表包括一组学生，每个学生信 息有学号、姓名希望在此D T D 上描述下列约束 信息 在整个文档上，学号确定学生名字； 课程名确定选修该课的学生； 在整个学校内课程名确定课程且课程不 重复； 在某个系内办公室名可以确定房间号，但 在整个文档上这是不成立的； 系名确定办公室与教室的楼牌地址( 假定 每个系都在指定的楼中) ( ! E L E M E N Ts c h o o l ( c o u r s e * ，d e p a r t m e n t * ) ) ( ! E L E M E N Tc o u r s e ( s l i s t * ) ) ( ! A T T L I S TC O U r S ec 1 2 a m eC D A T A # R E Q U I R E D ) ( ! E L E M E N Td e p a r t m e n t ( c o u r s e * ，o f f i c e * ，c l a s s r o o m * ) ) ( ! A T T L I S Td e p a r t m e n td n a m eC D A T A # R E Q U I R E D ) ( ! E L E M E N To f f i c e ( o n a m e ，a d d r ) ) ( ! A T T L I S To f f i c er O O l T l n oC D A T A # R E q U I R E D ) ( ! E L E M E N Tc l a s s r o o m ( a d d r ) ) ( ! A 删L I S Tc l a s s r o o mr o o m n oC D A T A # R E Q U I R E D ) ( ! E L E M E N Ts l i s t ( s t u d e n t * ) ) ( ! E L E M E N Ts t u d e n t ( s h a m e ) ) ( ! A T T L I S Ts t u d e n ts n oC D A T A # R E Q U I R E D ) 例1 展示了X M L 上存在的更多类型的函数 依赖，以上文献的X F D 不能完全描述这些约束 1 符号定义 1 1D T D 及X M L 文档树 结合文献 1 ，3 4 ，8 9 的定义，给出D T D 和X M L 文档树的形式化定义 定义1D T D 定义为6 元组： D = ( E ，E 。，A ，F ，R ，r ) ， 其中，E ，是复杂元素名的有限集；E 。是简单元素 名的有限集；A 是属性名的有限集；VeEE 。， F ( e ) 是一个正则表达式F ( e ) = Ie 7 F ( e ) 1 F ( e ) F ( P ) ，F ( P ) 1F ( e ) “其中s 表示空串， e 7 EE 。UE 。，并且“l ”，“，”，“* ”分别表示并、连 接和K l e e n e 闭包；R 表示从E 。到属性集的映射， 对于e E ，任何F ( g ) 不是e ，或R ( P ) 不是9 ； ，E ，是根元素名 定义2X M L 文档树被定义为7 元组： T = ( V ，l a b ，e t e ，a t t ，v a l ，r e x ，r o o t ) ， 其中，V 是X M L 文档树上节点的集合；l a b 是从 V 到E 。U E 。U A 的映射，得到V 中节点的类型； e l e 和a t t 是定义在复杂元素集上的函数：每个掣 V ，如果l a b ( u ) E 。那么e l e ( 剐) 表示元素节 点序列，a t t ( 印) 表示属性节点集合；v a l 表示得出 节点号码的函数；t e x 表示给每个属性或元素赋予 字符串值的函数，若l a b ( 刁) E ，则r e x ( 口) 为空， 若l a b ( 划) E 。UA ，则r e x ( 口) 为其所包含的文 本；r o o t 表示惟一的根节点 称X M L 文档树了符合D ，条件是： l a b ( r o o t ) = r ；对于每一个复杂元素节点训 V ，如果e l e ( 可) = 口1 ，训 ，另5 么序歹0l a b ( 剐1 ) ， ，l a b ( 仉) 须在语言F ( 1 a b ( 训) ) 中定义；若a t t ( 口) = 口7 1 ，口7 。： ，男| j 么 l a b ( 可7 1 ) ，l a b ( 口7 。) R ( 1 a b ( 础) ) 1 2 路径语言 定义3 简单路径对于给定的一个D T D ， D = ( E 。，E 。，A ，F ，R ，r ) ，简单路径形如z 1 z 。其中，l i E 。，l m E 。UE 。UA ( i m ) ，称为 个路径步并且，当i 2 ，m 一1 ，z i 在F ( z H ) 的字母表中，z ，。在F ( k 一1 ) 的字母表中或 在R ( z 。一1 ) 中 定义4复杂路径一个复杂路径形如z ， z 。形式的表达式，其中，z i E 。U ， ，i 1 ，咒一1 ，z 。E 。UE 。UA ，并且至少存在一个 z i 使z i ， ；符号f 弋表通配符，表示路径向 下一步，可以匹配任何标记；符号表示通配符的 闭包 定义5 匹配路径若z 】z 。C p a t h s ( D ) ，其中z i 为，z7 i E 。UE 。UA ，z 1 z i 一1 z7 i z i + 1 z 。是D 上的简单路径，则z 1 1 i l 。l7 i 。l i + 1 t 。匹配1 1 。；若Z 1 1 。 C p a t h s ( D ) ，其中z i 为，P 为D 上简单路径， z 1 z i 一1 P z i + 1 1 。是D 上的简单路径， 则z 1 z i 1 P z i + 1 1 。匹配z 1 1 。与复 杂路径q 匹配的简单路径称为q 的匹配路径 所有与复杂路径q 匹配的简单路径称为q 的 匹配集，表示为 口 定义6路径实例丁是一个符合D 的 X M L 文档树，口。是T 的一个节点，D 中的路径 P 为z 1 2 。，如果丁中的节点序列铆o 铆1 刁。，i E 1 ，规 满足下列条件之一 1 ) 若z i E 。UE 。UAU ，那么奶就是 巩一l 的孩子并且匹配标记z i ，注意任意节点都 匹配通配符标记； 2 ) 若z i 是，O J 表示口。确定子树上的任意 路径实例，若存在路径实例秒1 一铆i 一1 q + 1 、 、勘。，其中铆1 勘i l 匹配z 1 z i + 一1 ，口j + 1 万方数据 第1 期 赵相国等：X M L 的函数依赖5 9 训。匹配z ：+ 1 z 。，那么称剐1 V 。是P 相 对V 。的路径实例 定义7目标集合用秽。( P ) 表示集合 秽l 移 = l a s t ( P 相对于V 。的路径实例) ，得到相对于节 点口。路径P 对应的节点集合 2X M L 函数依赖定义 定义8给定D 和D 上的相对函数依赖妒 形为0 ，( P ，( Q 1 ，Q 2 ，Q 。，Q 。+ l ( S 1 ， S 。) ) ) ，其中， 1 ) 0 是D 上的路径，并且0 ，P 也是D 上的 路径0 称为上下文路径，指出X F D 成立的范 围，o 为路径并且l a s t ( O ) E ， 2 ) P ，Q ：( i 1 ，Y + 1 ) ，S i ( J 1 ，7 1 ) 是 D 上路径，且P Q i ，Q 。+ 1 S ，P Q 。+ l 也是D 上 路径； 3 ) P 为根路径并且P p a t h s ( D ) 称为函数 依赖的目标路径，并且P e ，l a s t ( P ) E ，指出 函数依赖成立的目标节点集合； 4 ) Q l ，Q 2 ，Q 。称作9 的左部路径，并且 Q i ( i 1 ，咒 ) 是D 上的简单路径，l a s t ( Q i ) E 。 U E 。UA ，且Q 1 ，Q 2 ，Q 。至少有一个不为 表示函数依赖的决定因素； 5 ) Q 。+ l 称作妒的右目标路径，并且Q ：+ 1 E p a t h s ( D ) ，l a s t ( Q i ) E E 。U E 。U A ； 6 ) S 1 ，S 。称作右部路径如果S 1 ， S 。都是空路径e ，则l a s t ( Q 。+ 1 ) 作为被决定因素 如果Q 。+ 1 和s 1 ，S 。都是空路径E ，那么 l a s t ( P ) 作为被决定因素 语义：对符合D 的X M L 文档树T ，称T 满 足X F D 9 ：O ，( P ，( Q l ，Q 2 ，Q 。一Q 。+ 1 ( S 1 ， ，S 。) ) ) 若O 为空，则对于 P Q 。+ 1 任意两 个节点铆l 和V 2 ，分别是以 P 中的铆7 l 和钞7 2 为 根的子树内的节点，若口7 1 Q 1 ，可7 1 Q 2 ， 秽7 1 Q 。 与钞7 2 Q 1 ，口7 2 Q 2 ，可7 2 Q 。 对应 相等，那么口1 S 1 ，l S 2 ，可1 S 。 与V 2 S 1 ，u 2 S 2 ，V 2 S 。 对应相等( 或值相等) ； 若0 不为空，则 O 中的口所确定的子树范围 内，函数依赖P ，( Q 1 ，Q 2 ，Q 。一Q 。+ l ( S 1 ，一， S 。) ) 成立 用“一”表示值相等约束，用“一。”表示相等约 束应用X F D 的定义，则例l 中的5 种数据约束 可以表示为如下形式的函数依赖 s t u d e n t ，( s n 旷s n a m e ) ； c o u r s e ，( c n o - * s l i s t s t u d e n t ) ； C O u r S e ，( c n o 一、，) ； s c h 0 0 1 d e p a r t m e n t ，( o f f i c e ，( o n a m e - - “ r o o m n o ) ) ； s c h 0 0 1 d e p a r t m e n t ，( d n o 一( a d d r ) ) 3X F D 对比分析 本文提出的X F D 可以描述文献 1 2 ，5 6 1 中的X F D 所能表示的X M L 函数依赖，用X F D 表示文献i 的X F D 下面用本文的X F D 描述以上 文献中的约束 在文献 1 中，有两个例子使用X F D 的基 于树元组的定义来描述约束 其中的一个例子是一个大学数据库，这个 D T D 满足3 个约束：c n o 是c o u r s e 的关键字；同一 个c o u r s e 的两个不同的s t u d e n t 的s n o 不能相同； 相同s n o 的两个s t u d e n t 节点的n a m e 必须相同 使用X F D 分别表示如下： C O U l e e S c o u r s e c n o - * c o u r s e s c o u r s e ； c 0 1 u - s e s c o u r s e ，c o u r s e s c o u r s e t a k e n b y s t u d e n t s n o - - - c o u r s e s c o u r s e t a k e nb y s t u d e n t ； c o u r s e s c o u r s e t a k e n b y s t u d e n t s n o - - c o u r s e s c o u r s e t a k e nb y s t u d e n t n a m e S 可以用本文的X F D 表达这3 个约束如下： c o u r s e s c o u r s e ，( c n o _ 。) ； c o u r s e s c o u r s e ，( t a k e n b y s t u d e n t ，( s n o 。e ) ) ； c o u r S e S c o u r s e t a k e n b y s t u d e n t ， s n o 。( n a m e ) 另外一个例子是D B L P 数据库，其D T D 满足 4 个约束：两个不同的会议有不同的标题；同一期 的两篇文章的年份属性有相同的值；给定的某一 期会议，不同的文章必须有不同的标题；文章的键 属性标识数据库中的文章这些约束用X F D 1 分 别表示如下： d b c o n f t i t l e p d b ，c o n f ； d b c o n f i s s u e + d b c o n f i s s u e i n p r o c e e d i n g s y e a r ； d b c o n f i s s u e ，d b c o n f i s s u e i n p r o c e e d i n g s t i t l e S + d b c o n f i s s u e i n p r o c e e d i n g s ； d b c o n f i s s u e i n p r o c e e d i n g s k e y d b c o n f i s s u e i n p r o c e e d i n g s 可以用本文的X F D 表达这4 个约束如下： d b c o n f ，( t i t l e 一。) ； d b c o n f ，( i s s u Pi s s u e i n p r o c e e d i n g s ( y e a r ) ) ； d b c o r f f i s s u e ，( i n p r o c e e d i n g s ，t i t l e + 。 i n p r o c e e d i n g s ) ； d b c o n f i s s u e i n p r o c e e d i n g s ，( y e a r 一，) 限于X F D 】 的路径语言的描述能力以及它 没有包含节点值相等的概念，它完全不能描述本 文例1 的5 种约束如约束若用X F D ， 的概念 来描述为式( 1 ) 和式( 2 ) ，则它们只能分别在文档 的两个部分上有约束能力，不能保证整个文档上 的约束，X F D 1 也不能描述例1 的其他约束 万方数据 东北大学学报( 自然科学版) 第2 9 卷 s c h 0 0 1 d e p a r t m e n t c o u r s e s l i s t s t u d e n t ( 少 s n o + s c h 0 0 1 d e p a r t m e n t c o u r s e s l i s t s t u d e n t s n a m e S ( 1 ) s c h 0 0 1 c o u r s e s l i s t s t u d e n t s n o + s c h 0 0 1 c o u r s e s l i s t s t u d e n t s n a m e S( 2 ) 文献 2 所能描述的函数依赖在不考虑空值 时与文献 1 是等价的文献 5 考虑在局部文档 上，也就是特定的上下文中的数据约束定义了局 部的X M L 函数依赖，可以用本文的函数依赖很 好地表达它 。 文献 6 的X F D 是针对数据库的层次性而设 计的，可以用本文的X F D 完全地描述这些约束， 其项目一供货商一零件数据库的模式文件上的约 束为：一个供货商提供的同一个零件的价格对于 不同的项目都是相同的；零件的数量由项目、供应 商和相关的零件决定这两食约束用X F D 6 表达 为 P S J P 蚵e c t S u p p l i e r ，P a r t f P r i c e ； P S J ， P r o j e c t ，S u p p l i e r ，P a r t - - Q u a n t i t y 用本文的X F D 表达这两个约束如下： P S J P r o j e c t S u p p l i e r ，( P a r t P a r t N o P a r t P r i c e ) ； P S J P r o j e c t ，( S u p p l i e r S N a m e ，S u p p l i e r P a r t P a r t N o - “ S u p p l i e r P a r t Q u a n t i t y ) 同样，例1 的5 种约束X F D 6 无法表达 文献 8 的G X F D s 具有较强的函数依赖表达 能力，但是它的路径语言以及相等的概念复杂， 其蕴含与推理问题是难以确定的并且对于函数 依赖应用于X M L 完整性约束与规范化理论中 时，只需要选择对这些应用有意义的X M L 函数 依赖 文献 8 以学校数据库的模式文件作为示例 进行讨论，其中的约束为：在整个树中，学号决定 学生姓名；学号决定学生的地址集；学号决定学生 的( 排序的) 地址列；每个学生的地址惟一( 如任何 两个值相等的地址) ，地址由学号决定；课程总是 用相同的文本；每个学生的任何单个电话号码都 决定该学生的地址集( 假定没有学生共用一个电 话号码) ；i g 些约束用X F D 8 1 分别表示如下： 一* s t u d e n t ： s n o s n a m e ； 一* s t u d e n t ： s n o - a d d r e s s ； 一* s t u d e n t ： s n o - I a d d r e s s ( L ) ； 一* s t u d e n t a d d r e s s ：f s n o - e ( S ) ； C o u r s e s t u d e n t s s t u d e n t $ t e x t ：仆3 + ( s ) ； 一* s t u d e n t ：$ t e l ( I ) - - * a d d r e s s 本文不考虑文档的顺序及集合相交不为空的 相等，认为这对X M L 规范化理论不重要，由约束 引起的冗余可以用约束代替描述，类似于约 束集合相交不空引起的冗余可以用集合相等代 替，也可以将有序列表的相等和集合相交不为空 的相等概念扩展到X F D 中可以用本文的X F D 描述约束，如下： s t u d e n t ，( s n 旷 s h a m e ) ； s t u d e n t ，( s n o a d d r e s s ) ； s t u d e n t ，( s n 旷a d d r e s s ) ； s c h 0 0 1 c o u r s e ，( c n o - - - s t u d e n t s s t u d e n t ( t e x t ) ) 限于其右部是一个长度为1 或0 的简单路 径，X F D 8 不能表达例l 中的约束 4 结论 本文研究了X M L 上的函数依赖问题，为表 达引起冗余的X M L 上的函数依赖数据约束提出 了一种新的的表示方法总结了以前的 X M L 函数依赖的研究工作，分析它们的表达形 式，并与其进行了比较，显示出本文的X F D 具有 较强的表达X M L 数据间函数依赖的能力 参考文献： 1 A r e n a s M ，L i b k i n LA n o r m a l f o r m f o r X M Ld o c u m e n t s J A C MT r a n s a c t i o n sO nD a t a b a s eS y s t e m s ，2 0 0 4 ，2 9 ：1 9 5 2 3 2 2 V i n c e n tM ，L i uJ ，L i uC S t r o n gf u n c t i o n a ld e p e n d e n c i e sa n d t h e ka p p l i c a t i o nt on o r n l a lf o r m si nX M L J A C M T r a n s a c t i o n sO nD a t a b a s eS u s a n s ，2 0 0 4 ，2 9 ( 3 ) ：4