（计算机软件与理论专业论文）xml函数依赖的推理规则与蕴涵问题研究.pdf

摘要 摘要 x m l 的出现给数据库领域带来了很多新的问题，其中x m l 数据的约 束是当前的研究热点之一。函数依赖是一种重要的x m l 数据约束，它是 x m l 规范化理论的基础。本文在对国内外研究现状进行综合分析的基础 上，从一个全新的角度对x m l 函数依赖的推理规则与蕴涵问题进行了研 究。 首先，对当前广泛使用的两种主要x m l 模式( 文档类型定义d t d 与 x m ls c h e m a ) 进行了比较和分析；对已经提出的x m l 函数依赖定义进行 了分类和比较，并对x m l 函数依赖的几个相关问题进行了讨论。 其次，介绍了现有的x m l 函数依赖推理规则集并分析了它们各自的 优缺点，然后提出了基于树元组的x m l 函数依赖推理规则集并证明了它 的正确性和完备性，给出了求解路径闭包算法和成员籍算法。 然后，基于所提出的x m l 函数依赖推理规则集，定义了x m l 函数依 赖集覆盖、规范覆盖、最小覆盖及最优覆盖的概念，并给出了求解规范覆 盖和最小覆盖的算法。 最后，提出了一种d t d 路径编码方法，并对它的性质进行了分析。 编码后的d t d 消除了部分x m l 平凡函数依赖，并能在线性时间内对 m a r e n a s 等人给出的x n f 算法中的逻辑蕴涵问题进行判定。提出了一个 将x f d 中的编码路径重新映射到d t d 路径的算法，并证明了它的正确性。 关键词x m l ；推理规则：函数依赖；蕴涵与覆盖；规范化 燕山大学工学硕士学位论文 a b s t r a c t w i t hx m l e m e r g i n g ，m a n yn e w i s s u e sa r ep r o p o s e di nd a t a b a s ea r e a , a n d c o n s t r a i n t so f x m ld a t aa r eo n eo f t h e s ei s s u e s f u n c t i o nd e p e n d e n c yi sas o r t o fe s s e n t i a lc o n s t r a f i a to fx m ld a t a ，a n di ti st h ef o u n d a t i o no fx m l n o r m a l i z a t i o nt h e o r y o nt h eb a s i so f a n a l y z i n ga n ds y n t h e s i z i n gt h ea c t u a l i t y i ni n t e r n a la n de 砒e r n a l t h i sp a p e rr e s e a r c h e dt h ep r o b l e m so fi n f e r e n c er u l e s a n di m p l i c a t i o na b o u tx m lf u n c t i o nd e p e n d e n c yf r o man e w p o i n to f v i e w f i r s t l y ，i nt h i sp a p e rt w ok i n d so fx m ls c h e m aw e r ec o m p a r e da n d a n a l y z e d ：d o c u m e n tt y p e d e f i n i t i o na n dx m ls c h e m a , w h i c hw e r eu s e d e x t e n s i v e l y ；d e f i n i t i o n so fx m l f u n c t i o nd e p e n d e n c y , w h i c hh a db e e np u t f o r w a r d , w a sc l a s s i f i e da n dc o m p a r e d ，a n ds e v e r a lp r o b l e m sr e l a t e dw i t hx m l f u n c t i o n a ld e p e n d e n c i e sw e r ed i s c u s s e d s e c o n d l y , t h ee x i s t i n g i n f e r e n c er u l e so fx f da n dt h e i r r e s p e c t i v e a d v a n t a g e sa n dd i s a d v a n t a g e sa r ep r e s e n t e d ，t h e nas e to fi n f e r e n c er u l e sb a s e d o nt r e et u p l ew a s p r e s e n t e da n di t sc o r r e c t n e s sa n dc o m p l e t e n e s sw e r ep r o v e d ， a sw e l la sa p a t hc l o s u r ea l g o r i t h ma n dm e m b e r s h i pa l g o r i t h mw e r ep r e s e n t e d t h i r d l y , b a s e do nt h e i n f e r e n c er u l e so fx f d ，c o n c e p t i o n so fc o v e r s ， c a n o n i c a lc o v e r s ，m i n i m u mc o v e r sa n do p t i m a lc o v e r sf o rt h es e to ff d sw e r e p r e s e n t e da n da l g o r i t h m so f c a n o n i c a lc o v e r sa n dm i n i m u mc o v e r sw e r e g i v e n f i n a l l y , ap a t hc o d i n gm e t h o do fd t d w a sp r e s e n t e d ，a n di t sc h a r a c t e r s w e r ea n a l y z e d i nc o d i n gd t d ，s o m et r i v i a lx f d sw e r er e m o v e d ，a n dl o g i c a l i m p l i c a t i o np r o b l e m o f x n fa r i t h m e t i cp r o p o s e db ym a r e n a se ta 1 c o u l dh e t e s t si nl i n e a rt i m e a na r i t h m e t i co fm a p p i n gc o d i n gp a t h so fx f d si n t o o r i g i n a ld t dp a t h s w a s g i v e n , a n d i t sc o r r e c t n e s s w a s , p r o v e d k e y w o r d sx m l ；i n f e r e n c er u l e s ；f u n c t i o nd e p e n d e n c y ；i m p l i c a t i o na n d c o v e r ；n o r m a l i z a t i o n 第1 章绪论 1 1 研究背景 第1 章绪论 x m l ( e x t e n s i b l em a r k u pl a n g u a g ) 从提出到现在不过只有几年的时间， 但是它作为一种跨产品、跨界面、跨平台的互联网的世界语，具有极大的 应用前景，正引起政府、企业和各大软件厂商的极大兴趣。关于x m l 实 际上有系列标准，x m l l 0 t ”只是其基本的语言规范。其他标准包括 x l i n k ( x m ll i n kl a n g u a g e ，用于描述将超链接加入x m l 文档的方法的 标准1 、x p o i n t e r ( x m l p o i n t e rl a n g u a g e ，关于x m l 文档中特定部分的 定位的标准) 1 2 1 、x s l ( e x t e n s i b l es t y l e s h e e tl a n g u a g e ，有关x m l 文档的显 示样式的标准) 【3 1 、d o m ( d o c u m e n to b j e c tm o d u l e ，供应用程序处理x m l 文档的对象模型及接口标准的定义) 4 l 、x m ln a m e s p a c e s ( 关于如何将x m l 文档中的元素标识、属性与u r l 相关联的标准) 9 】、x m ls c h e m a s1a n d2 ( 供 应用开发者精确地定义基于x m l 的类型) 【6 i 以及x m lq u e r y ( 关于x m l 数 据的查询的标准) 【等等，其中很多标准还正在制定中【g j 。 另外，随着x m l 数据量的增多，以及相关行业标准d t d ( d o c u m e n t t y p ed e f i n i t i o n ) t g l 的制定，人们也开始越来越多地希望以对待数据库的方式 来管理x m l 文档。既然是这样，就必然要求增强x m l 相关标准中对于约 柬的定义能力，因为约束是数据语义的重要组成部分。然而x m l 文档作 为半结构化数据的特例，虽然它很容易表达来自不同源的数据，但是，由 于d t d 与s c h e m a 这些模式定义方法对于完整性约束的定义能力都是有限 的，其所能表示的语义信息也是相对有限的。并且一个设计良好的d t d 可以避免数据冗余的出现，从而避免插入、更新和删除操作异常，减少海 量的数据空间，并使得数据存储和交换更加容易和安全。由于i n t e r n e t 的 开放性，x m l 数据更新异常的危害性要远远大于关系数据更新异常的危害 性，这就对x m l 数据的模式提出了更高的要求。规范化是模式设计的基 础，它是评价一个模式好坏的主要依据，而x m l 函数依赖的推理和蕴涵 燕山大学工学硕士学位论文 是进一步研究x m l 规范化的基础。 本文的研究就是在这一背景下提出的。目前x m l 已经逐渐成为 i n t e r n e t 上的数据表示和数据交换的标准，需要通过i n t e r n e t 交换和处理的 x m l 数据会大大的增加。对于x m l 的深入研究将有力的促进企业的信息 化、电子商务以及电子政务的发展，因此具有巨大的应用前景和经济效益。 1 1 1x m l 简介 x m l 是w 3 c ( w o r l dw i d ew e bc o n s o r t i u m ) 提出的一种用于w 乩网络 上的数据和文档结构的通用标记语言。w 3 c 原意是用来解决h t m l 信息 的不确定性和网站之间的数据交流问题，但随着它的应用深入，特别是与 j a v a 语言配合，在软件开发、网站运营、移动互联等方面逐渐呈现出它的 优秀性能。很多技术专家和商业人士都预言它的出现将引发互联网技术发 展的又一次浪潮。x m l 可以解决网络中跨平台的数据交流问题，使不同的 网络信息可以以精确的、可供人和机器分析再加工的结构化、半结构化数 据的形式向外界提供。 x m l 是标准通用标记语言s g m l ( s t a n d a r dg e n e r a l i z e dm a r k u p l a n g u a g e ) 的一种变体，它采用了优化浏览器显示文档视图的严格的规则集 合。从s g m l 中经过精心修剪而来的x m l 既保持了s g m l 的功能，同时 又减少了s g m l 的复杂性。与h t m l 不同，x m l 允许文档开发人员创建 描述数据的标记，并使开发人员可以创建被称为文档类型定义( d t d ) 的规 则集合。任何标准的x m l 语法分析器都可以读取、解码和检验这种基于 文本的自描述文档，并以独立于平台的方式提取数据元素，因此使应用程 序可以通过另一种名为文档对象模型( d o m ) 的标准访问数据对象。对于电 子商务软件厂商和行业集团来说，x m l 的通用数据交换格式提供了可以与 其它基于标准的协议( 如h t t p 、t c p i p ) 以及i n t e m e t 一起使用的基于标 准的构件。各公司已经开始支持x m l ：数据库厂商o r a c l e 公司和i b m 从 一开始就支持x m l ：m i c r o s o t t 的i e 5 0 以及n e t s c a p ew e b 浏览器支持 x m l ；s u n 公司考虑将此标准作为用于j a v a 的可移植数据语言。此外，像 o b j e c td e s i g n 公司的e x c e l o n 这类应用服务器提供了x m l 来支持应用集 2 第1 章绪论 成、数据交换和电子商务。 一个x m l 文档包含了从根元素开始的嵌套元素结构。每个元素有一 个标签( t a g ) 与之相对应，除了字符串数据，它还可以包含属性值对和嵌套 子元素。同时包含字符串数据和嵌套二子元素的元素被称为具有混合内容 f m i x e dc o m e m ) 。x m l 中的元素标签必须良好嵌套，这样的x m l 文档是 良构的( w e l l f o r m e d ) 。 1 1 2x m l 完整性约束问题 下面来通过几个例子分析一下在x m l 领域中完整性约束的一些相关 问题。 例1 1 ：某个商店原来是采用关系数据库来存储相关数据的，数据库 设计的关系模式如下所示： c u g o m e r ( q q ，n a m e ，a d d r e s s ) i t e m ( i n o ，c o s t ) b u y ( g 盥q ，! 丛q ，c o u n t ) 这个数据库模式很直观，包括顾客信息( 顾客号、姓名和住址) ，商品 信息( 商品号和售价) 和购买信息( 顾客号，商品号和购买数量) 。c n o 、i n o 和( c n o ，r n o ) 分别是相应关系的键( 出于简单考虑，假定同一顾客购买同 一商品都只记录一次) 。另一方面，在关系b u y 中，c n o 和i n o 也是外键， 分别引用c u s t o m e r 和i t e m 关系中的相应元组。 现在假设该商店出于数据交换的需要，要将数据库中的数据以x m l 文档的形式来发布，它们设计的相应d t dd 1 如下： 这里省略了元素类型为字符串( # p c d a t a ) 的定义。从语义的角度来 说，这个d t d 的定义是不究善的，因为它丢失了原有的数据库中键和外 键的定义，这可能会带来不利的影响。直观地来说，在转化的过程中，或 燕山大学工学硕十学位论文 许有某个顾客的信息会被重复，也可能某个购买信息中会出现根本不存在 的顾客号或是商品号。如果没有完整性约束的定义，相应的x m l 文档就 无法避免类似情况的产生。为此，可以为模式定义增加下面形式化的约束 表示。 键： c u s t o m e r c n o 】_ c u s t o m e r i t e m i n o 】 i t e m b u y c n o ，i n 0 斗b u y 外键： b u y c n o 】c u s t o m e r c n o 】 b u y i n o 】i t e m i n o 上面的约束表示的含义是：在相应的x l v i l 文档中，任意两个c u s t o m e r 元素的c n o 值必须不同，任意两个i t e m 元素的i n o 值必须不同；b u y 元 素的c n o 值必须在c u s t o m e r 元素的c n o 值中出现过，而b u y 元素的i n o 值必须在i t e m 元素的i n o 值中出现过。 但是需要注意的是，即使是这样简单的约束也是无法在d t d 中表示 的。因为按照d t d 的规范，键只能够被定义在属性上。此外在上面的定 义中，即使将c n o 和i n o 都改定义为属性，而不是元素，也依然无法表 示元素b u y 上的键。这是因为在d t d 规范中，键只能够被定义在单个属 性上。从这个简单的例子可以看到，d t d 中对于键的定义方法是非常不完 善的。 根据对于前面的数据约束的分析，可以认定该文档不具有一个设计良 好的d t d 。相关的问题就是，如何判定一个d t d 是否是设计良好的；进 一步的，假设某个d t d 不是设计良好的，那么采用什么样的方式可以找 到一个与之表述语义相同而设计良好的d t d 。和关系模式相类似，x m l 中存在数据冗余的原因是由于文档内部数据之间存在着某种依赖关系。首 先需要一种表示这种依赖关系的方法，引入关系模式中的概念，称其为 x m l 上的函数依赖，显然它比平面或是嵌套关系中的函数依赖都复杂的多 1 0 l ，也超出了已有的d t d 和x m l 模式中键可以表达的范畴。这种函数依 4 第1 章绪论 赖的描述需要一种基于路径的方式，并要考虑到x m l 文档中元素可能的 复杂构造所带来的对于“相等”概念的影响。 与函数依赖相关的一个问题是逻辑蕴涵，其在x m l 领域中的含义为： 给定一个函数依赖集和一个函数依赖口，是否可以判定任意使成立的 x m l 文档并，必然也使盯成立。推理规则的引入通常是解决逻辑蕴涵判定 的主要手段，这也是在x m l 的领域中需要讨论的一个问题。考虑到x m l 自身的复杂性，它的推理规则显然也会比关系上的推理规则复杂的多。 在函数依赖和逻辑蕴涵的基础上，就可以形式化地定义x m l 文档中 存在的冗余。而要消除文档中存在的数据冗余，归根结底是需要一个设计 良好的d t d 。那么接下来的问题就是判定怎样才是一个可以消除对应文档 中冗余的d t d ，即规范化的d t d ；并进一步地讨论如何将给定的d t d 转 化为规范化的形式。 1 2 国内外研究现状 函数依赖和规范化的理论源于数据库领域。在关系数据库里，键和外 键是数据库概念设计的基础，它们提供了如何唯一识别元组和如何引用另 一元组的方法。函数依赖理论和蕴涵是关系模式设计的核心部分，是范式 研究的基础。基于范式的关系模式，可以消除修改、删除和插入的异常情 况，提高数据的质量。函数依赖和包含依赖( i n c l u s i o nd e p e n d e n c i e s ) 结合在 一起，往往被用于进行查询优化的工作。在面向对象数据库中，逆向约束 ( i n v e r s ec o n s t r a i n t ) $ 1 键约束是非常常见的。在数据库领域中，对于函数依 赖有深入研究 1 1 , 1 2 的，还包括一些复杂的扩充的模型，如嵌套函数依赖1 3 】 和嵌套关系上的范式 1 4 , 1 5 。文献【1 6 中给出了面向对象数据库中路径依赖、 局部依赖和全局依赖的定义。此外，在受限的面向对象数据模型上也有关 于函数依赖的讨论1 1 7j 。它们的研究限于传统的数据库范畴，x m l 所特有 的树状结构和路径导航的文档模型显然超出了它们的表述能力。而x m l 数据约束对于研究x m l 数据的查询优化1 1 8 】、数据集成1 1 9 1 以及x m l 数据 与其它形式数据库的转换1 2 0 1 都极为重要。 在半结构化数据领域中，研究比较集中在路径约束【2 m 5 1 。这主要是由 燕山大学工学硕士学位论文 于半结构化数据的图状结构，导致很多导航路径相互包含。而x m l 文档 是一棵树，树上的每个节点都有由根到达它的唯一路径。此外，文献 2 1 - 2 5 中所使用的语言也缺乏表述键的能力。一些更广泛的完整性约束研 究包括基于网站的管理所进行的但引，但是显然，这样的研究并不是建立在 一个定义模型上的。 目前已有的关于x m l 上约束的讨论主要是基于d t d 进行的。d t d 的定义规范中包含了一些基本的约束信息。例如，考虑以下的d t d 片断， 一篇文章有唯一标题，个以上的作者，若干参考文献和可选的价格。 在语义上，这里表达了两个关于文档结构的最基本的约束： ( 1 ) 父子关系( 祖先后代关系) 例如元素a r t i c l e 和元素t i t l e 之间就具有 父子关系； ( 2 ) 基数d t d 中支持使用符号+ 、t 和? 来表示基数，其含义分别为 个以上( 含一个) ，任意多个( 可以为零个) 和可选( 零个或一个) 。若不使用， 比如对于元素t i t l e ，就表示有且仅有一个。 虽然类似约束是平凡的，但是在有关x m l 上存在树模式查询口7 1 和结 构化查询 2 8 1 时，它们可以被用于查询优化 2 9 】。 另外，d t d 上还可以定义域约束。如以下的片段中就说明了作者的性 别取值是限于男或女的： 在进行x m l 文档的关系数据库存储时，文献 2 0 考虑到了域约束的保 持问题。 d t d 、x m ls c h e m a 和x m l d a t a 提供了x m l 上基本的约束定义能力。 在d t d 中，通过为属性标注i d 和i d r e f 提供了定义键和外键的方法。但 是这种机制的表述能力相对有限，并存在不少缺陷。首先，被标注了i d 的属性必须在整个文档内唯一，而不是仅仅在某个特定类型的元素内。这 样的要求显然局限性太强。在现实中，很多情况下键值都是采用自然数序 列来生成的。如果是这样，那么文档中就不能存在两个这样的键了。其次， i d 或i d r e f 只能被标注在单个属性上，这样在关系数据库中很常见的复 6 第1 章绪论 合键就没有办法在x m l 中表示了。最后，在d t d 中i d r e f 既没有类型 限制也没有范围限制，在文档中根本没：有任何机制来确保i d r e f 所指向的 具体属性。为了解决这些问题，x m ld a t a 提供了新的定义键和外键的能 力。在x m ls c h e m a 中，则更进一步地支持使用x p a t h 3 0 , 3 1 ( x m lp a t h l a n g u a g e ) 表达式来定义键和外键；但是x m ls c h e m a 中所采取的方式也仍 然存在着些问题。首先，x m ls c h e m a 中的“相等”概念是比较模糊的， 考虑到x m l 文档中可能具有的元素的复杂构造，因此需要一个明确的对 于“相等”概念的定义。其次，作为一种用来表述键的路径表达式语言，x p a t h 显得过于复杂了。在x _ p a t h 表达式中，不但可以在文档树上从根到叶，还 可以逆向地从叶到根，更不用说其中还允许嵌入函数等。个很直接的结 果就是关于x p a t h 表达式的包含和相等目前仍然无法得到有效的判定，这 样在规范化研究中非常重要的推理就无法进行了。最后，在所有这些规范 中，有关函数依赖的概念都完全地没有被涉及到。 文献 3 2 1 在d t d 规范的基础上，扩展了键的定义能力，可以表述相对 键。文献 3 3 】更进一步地通过分析两类特殊的路径表达式，在文档上讨论 了键的逻辑蕴涵问题及其计算复杂度分析。对于“相等”，文献 3 2 ，3 3 1 中采 取了“交不空”的定义方法，而并不是严格意义上的相等。另外它们的讨论 仅限于键，并没有引入函数依赖的概念。一般来说，键只是函数依赖的一 个特例，应该将其归结到函数依赖的体系中去。 文献 3 4 为x m l 引入了逆向约束，并讨论了简单定义下键、外键和逆 向约束在x m l 中的逻辑蕴涵问题。它的主要思路来源于半结构化领域 3 5 1 ， 因而采用了图而不是树来作为x m l 文档的模型。在文献【3 4 】所使用的模型 中，节点是可以共享的，所以无法精确地来表示x m l 数据。具体来说， 不存在从x m l 图到x m l 文档的一一对应，一个x m l 图可以有多个相对 应的x m l 文档。 文献【3 6 给出了形为( p 卵q ：。，q 。一吼+ 。 ) 的函数依赖表达式，其 中，p ，吼( f 【l ，+ l 】) 均为形如r ，的路径表达式，f 为元素类型。当对 x m l 树r 中的任意两棵子树n 、乃，其中，n 、死均为由r 的根节点经 由路径p 到达的子树，如果对每个f 1 ，咒 ，n 、t 2 在q i 上均相等，则它们 燕山大学工学硕士学位论文 在“+ ，上也相等，此时，称丁满足函数依赖约束。该定义需要对函数依赖 加入一些语法限定，且该文并没有讨论x m l 覆盖和规范化问题。 文献 3 7 j 给出了函数依赖的定义，通过将x m l 文档映射到关系，讨论 了x m l 的范式x n f ( x m l n o r m a lf o r m ) ，给出了一个将d t d 转化为符合 x n f 形式的算法。文献【3 8 从信息论的角度进一步说明了x n f 的优越性。 文献f 3 7 的主要问题是，模型中的“相等”有二意性。对于元素，相等是节 点重合，而对于属性，相等则是值相等。文章中所需要的键和相对约柬的 概念实际上是依托于这个二意性来进行定义的。此外文献 3 7 】中并没有给 出一个用于推理的方法，而这实际是不可缺少的。 可满足性是一个理论性很强的问题，其意义为，给定一组约束，是否 存在x m l 文档满足这些约束。在给定d f d 的情况下，问题就变为是否存 在有相应的x m l 文档既符合该d t d ，又满足这些约束。文献 3 9 - - 4 1 1 所考 虑的约束主要被限定为键和外键，给出d t d 和一组包括键和外键的完整 性约束定义，是不能判定是否存在同时符合该d t d 和完整性约束的x m l 文档的。即使进一步将键和外键的定义都限制为简单属性，类似的判定也 是n p 完全的。 另外，文献【4 2 6 】等研究使用关系数据库来存储x m l 文档。它们共 同存在的一个问题是只关注了x m l 文档的结构信息，而没有考虑到文档 所具有的语义信息，比如键，函数依赖等。这样带来的后果是两方面的， 一个是所产生的关系模式往往是零碎和低效率的，并非最佳。另一个是完 全丢失了x m 文档中固有的约束，损失了语义的重要部分。 文献 4 2 1 的方法很有特点，它提出了种使用关系和半结构化模式相 结合来存储x m l 文档的方法。这种方法的基础是寻找从x 】帆文档实例到 关系模式的映射，并通过s t o r e d ( s e m i s t r u c t u r e dt or e l a t i o n a ld a t a ) 语言 来表示。为了保证这个映射是无损的，部分不符合关系模式的数据会被存 储在额外的溢出图( o v e r f l o wg r a p h ) 中。溢出图是一个半结构化存储，文中 忽略了其具体实现细节。由于半结构化存储对于查询效率会有较大的影响， 文章中假定溢出图通常会很小。 文献 4 2 1 中主要讨论的问题包括以下几个： 第1 苹绪论 ( 1 1 s t o r e d 语言用来表示从半结构化数据到关系模式和相应溢出 图的映射； ( 2 ) 模式生成算法从一组半结构化数据实例中，发现其“模式”，并生 成存储的关系表和相应的s t o r e d 映射表示。该算法是基于一个数据挖掘 算法改进后而得到的； ( 3 ) 溢出图生成算法在( 2 ) 的基础上，生成相应的溢出图。文中主要讨 论了在已知半结构化数据模式的情况下，溢出图的生成； ( 4 ) 查询重写在给出关系模式、溢出图、s t o r e d 表示后，将对半结 构化数据的查询重写为对关系表和溢出图的查询。 文献 4 3 1 中的方法是比较具有代表性的一类。在这里，x m l 文档和一 般的半结构化数据一样，被看作是一棵有序的标记树。树上的每个节点是 x m l 文档的一个元素，树根就是文档的根元素，非叶节点以对应的诅l 元素的标识( i d ) 来标记。树上的边表示元素间的父子关系，以所对应的子元 素名来标记。为了保留同一父元素的子元素之间的顺序，系统给同父的边 分配一个序号。树叶代表x m l 元素的值，并以此标记。在这样的假定下， 文献 4 3 1 主要考虑的问题是，如何分别在数据库中存储边( 父子关系) 和树叶 ( 值) ，文中给出了3 种存放边和2 种存放树叶的方法，因而共有相应的6 种变形。不同的实现会带来不同的问题，例如某些情况下需要对边表做大 量的联结操作，某些情况下所生成的关系是非范式化的等。 文献 2 0 ，4 7 1 研究了如何在维持约束的情况下进行x m l 和关系模式的 相互转化，它们的方法是在文献 4 5 1 的基础上修改后得到的。由于它们所 使用的模式是限于d t d 的，而d t d 中可以表示的约束语义相当有限，所 以文中所考虑的仅仅限于维数，域约束，父子关系等。此外，文献 2 0 1 与 文献 4 7 1 中方法的思路是在文献 4 5 】中得到的关系模式结果上再添加完整 性约束，而并不是主动地利用这些约束来组织存储实现；并且它们也没有 考虑到规范化的问题。 文献 4 8 1 讨论了利用x m l 的键信息来组织关系生成的问题，其键定义 方法出自文献 3 2 1 。由于仅仅有键的信息，所以也就没有x m l 上规范化的 概念；由于没有涉及到推理，其所考察的键形式未必会生成尽可能少的关 9 燕山人学工学硕士学位论文 系；由于以上原因，最后所生成的关系也并不满足相应的范式。 文献 4 9 】、文献 5 0 】和文献 5 1 】分别针对基于路径和路径实例的x m l 函数依赖提出了一组推理规则，但函数依赖的表示形式不同。文献 4 9 1 采 用p 】，- ”，阮一g 的形式表示函数依赖，把函数依赖的绝对函数依赖和相对函 数依赖混在一起，其中p l ，“执，q 为任意属于x m l 树的路径。文献 5 0 采 用r ( q ，q 2 ，q 。一p 。，巴，尸j 的形式表示函数依赖，其中 r ，e q l ，螅，g o l , - - , r p k 都是d 上的路径表达式，且矗为根路径表达式。 文献【5 1 采用( r l ，r 2 ，q l ，凸) 一_ p 1 ，一形式表示函数依赖，其中r l 称为范 围路径，它允许为空，月l 为空时表示绝对函数依赖，不为空时表示相对函 数依赖，月2 称为目标路径，9 ，9 称为头部路径，p l ，“，r 称为体部路径。 而且文献【5 0 和文献 s u 在模式上不寻求x m l 向关系模式的映射。但是文 献 3 7 】提出的函数依赖是基于树元组的，它的表示形式为 g 拶i ，- 一批) - + 擘， 其中的g 表示限定函数依赖成立的范围路径，允许它为空，当g 为空时， 表示绝对函数依赖，不为空时表示相对函数依赖，p 】“，m ，q 为d t d 上的 路径。因此，文献 4 9 】、文献 5 0 】和文献 s u 中的函数依赖推理规则集都不 适用于文献【3 7 】中的x m l 规范化方法。有关x m l 函数依赖集的覆盖问题 尚未见到其他研究成果。 1 3 研究的理论和实际意义 当前数据库理论研究与实际应用已经出现了脱节，x m l 的出现给数据 库领域注入了新鲜血液。随着互联网时代的到来，数据越来越多地开始以 网络在线的方式进行着发布、交换和集成。由于x m l 具有跨平台，简单 易用等特性，在很短的时间内就获得了广泛认同，其应用领域不断地得到 拓展，已成为一种被大量使用的通用数据格式。数据库理论的研究人员开 始考虑将原有数据库理论应用到x m l 的研究中，推动理论与实际相结合， 从而产生巨大的社会效益和经济效益。 本文为x m l 领域引入了一个比较完整的正确、完备的函数依赖推理 规则集，并提出了函数依赖集覆盖的概念，以扩充已有的对于约束的定义 能力。x m l 文档作为半结构化数据的特例，虽然它很容易表达来自不同源 1 0 第1 章绪论 的数据，但是其所能表示的语义信息却相对有限。从这一角度看，本文的 工作增强了x m l 数据的语义表现力。 然后，本文又在推理规则集和覆盖的基础上，提出了一种d t d 路径 编码方法。该方法能在线性时间内对m a r e n a s 等人给出的x n f 算法中的 逻辑蕴涵问题进行判定，为进一步研究x m l 规范化奠定了基础。 1 4 本文的主要研究工作及文章结构 以下是本文的结构安排； 第l 章为绪论，主要介绍了论文研究的目的、意义、现状以及所研究 的内容。 第2 章提出了形式化的d t d 、x m l 文档和路径表达式定义，并定义 了x m l 树、树元组等概念，并结合实例对这些概念进行了说明。为后面 的讨论作符号上的准备。 第3 章讨论了基于树元组的x m l 函数依赖推理。本章首先简要介绍 了关系模式上传统的函数依赖的概念，然后通过若干约束的实例详细分析 了x m l 对于函数依赖表达能力所提出的要求。文章接着给出了基于树元 组的形式化的x m l 函数依赖定义，并对该定义中的一些关键问题进行了 说明。在这种x f d 定义的基础上研究了x m l 的推理规则和逻辑蕴涵问题， 提出了一组推理规则集并证明了推理规则的正确性和完备性，给出了求解 路径闭包算法和成员籍算法。 第4 章进一步介绍了x m l 函数依赖的蕴涵问题。首先提出了x m l 函 数依赖集的无冗余覆盖、规范覆盖、最小覆盖和最优覆盖的概念，接着给 出了几个覆盖的求解算法。 第5 章本文的另一个研究重点，为了更有效的解决x m l 函数依赖的 蕴涵问题，提出了种d t d 路径编码方法，并且对它的性质进行了分析。 该方法能在线性时间内对m a r e n a s 等人给出的x n f 算法中的逻辑蕴涵问 题进行判定。提出了一个将x f d 中的编码路径重新映射到d t d 路径的算 法，并证明了它的正确性。 最后总结全文，对未来的研究方向进行了展望。 型当奎兰三兰堡主堂笪笙奎 1 5 本章小结 本章对涉及x m l 函数依赖和蕴涵问题方面的研究工作做了介绍，阐 述了目前在该方面的研究现状、已经取得的成果，同时指出了本文要研究 的内容。可以看出，在该领域已经取得了丰硕的成果。然而仍然需要进一 步的完善和改进，仍需要有大量的工作要做，包括：对正确和完备的x m l 函数依赖推理规则集的进一步研究；x m l 函数依赖蕴涵问题的进一步解 决；x m l 函数依赖集的覆盖；x m l 数据的多值依赖等。 1 2 第2 章x m l 的模式与树元组 2 1引言 第2 章x m l 的模式与树元组 x m l 模式是伴随着x m l l 0 规范的制订而推出的，从x m l 模式的第一 个方案到现在为止，w 3 c 成员共提交了五个x m l 的模式规范，它们分别是 x m l 一- d a t a 、d c d ( d o c u m e n t c o m e m d e s c r i p t i o n f o r x m l ) 、s o x ( s c h e m a f o ro b j e c to r i e n t e dx m l ) 、d d m l ( d o c u m e n td e f i n i t i o n m a r k u pl a n g u a g e ) 和x m ls c h e m a 。直到现在，关于x m l 模式还没有一个正式推荐标准，它 仍处于不断修改完善的过程当中。d t d 良好的一致性、扩展性、易用性、 互换性和规范性作为x m l 模式的应用倍受研究者的青睐。本文的研究是 基于d t d 模式的。 x m l 除了可以创建x m l 文档外，还需要为所建的标记语言提供文档 管理和描述。这些都是d t d 可以处理的事务。d t d 还提供了校验解析器， 可以用来作为检测x m l 文档元素、属性、实体和符号的规则的指令或者 限制列表。如果x m l 文档遵循了d t d 的限制，校验解析器将会发现文档 是良构的，而且能够正确地进行显示。d t d 的语法设计具有足够的灵活性， 可以允许创建规则，并用来管理文档中可能遇到的任何情况或者所需的任 何限制。 本章首先比较和分析目前广泛使用的两种x m l 模式：d t d 和s c h e m a 。 然后给出形式化的d t d 、x m l 文档和路径表达式的定义，在此基础上进 一步定义x m l 树、树元组等概念，为后面章节中的讨论作符号上的准备。 其中，定义2 1 至2 1 0 来自文献 3 7 1 。 2 2x m l 的模式 x m l d t d ( x m l 的文档类型定义) 是近几年来x m l 技术领域所使用的 最广泛的一种模式。但是，由于x m ld t d 并不能完全满足x m l 自动化 处理的要求，例如不能很好实现应用程序不同模块间的相互协调，缺乏对 燕山火学工学硕士学位论文 文档结构、属性、数据类型等约束的足够描述等等，所以w 3 c 于2 0 0 1 年 5 月正式推荐x m ls c h e m a 为x m l 的标准模式。显然，w 3 c 希望以x m l s c h e m a 来作为x m l 模式描述语言的主流，并逐渐代替x m ld t d 。但作 为一种最简单的x m l 模式，x m ld t d 也还将会在一段时间内发挥它应有 的作用。 2 2 1 文档类型定义( d t d ) 与s c h e m a 的比较和分析 下面从不同方面对d t d 和s c h e m a 进行比较分析。 2 2 1 1x m l 格式x m l s c h e m a 的格式与x m l d t d 的格式有着非常明 显的区别，x m ls c h e m a 事实上也是x m l 的一种应用，也就是说x m l s c h e m a 的格式与x m l 的格式是完全相同的，而作为s g m ld t d 的一个 子集，x m l d t d 具有着与x m l 格式完全不同的格式。这种区别会给x m l s c h e m a 的使用带来许多好处： ( 1 ) x m l 用户在使用s c h e m a 的时候，不需要为理解x m ls c h e m a 而重 新学习，节省了时间； ( 2 ) 由于x m ls c h e m a 本身也是一种x m l ，所以许多x m l 编辑工具、 a p i 开发包、x m l 语法分析器可以直接的应用到x m ls c h e m a ，而不需要 修改： ( 3 ) 作为x m l 的一个应用，x m ls c h e m a 理所当然的继承x m l 的自描 述性和可扩展性，这使得x m ls c h e m a 更具有可读性和灵活性； ( 4 ) 由于格式完全与x m l 样，x m ls c h e m a 除可以像x m l 一样处理 外，也可以同它所描述的x m l 文档以同样的方式存储在一起，从而方便 管理； ( 5 ) x m ls c h e m a 与x m l 格式的一致性，使得以x m l 为数据交换的应 用系统之间，也可以方便的进行模式交换； ( 6 ) x m l 有非常高的合法性要求，x m l d t d 对x m l 的描述，往往也 被用作验证x m l 合法性的一个基础，但是x m ld t d 本身的合法性却缺 少较好的验证机制，必需独立处理。x m ls c h e m a 则不同，它与x m l 有 着同样的合法性验证机制。 1 4 第2 章x v l l 的模式与树元组 2 2 1 2 数据类型对于许多开发人员来讲，x m ls c h e m a 与x m ld t d 相比的一个最显著的特征，就是其对数据类型的支持了。这完全是因为 x m ld t d 所提供的数据类型只有c d a t a 、e n u m e r a t e d 、n m t o k e n 、 n m t o k e n s 等十种内置( b u i l t - i n ) 数据类型。这样少的数据类型通常无法满 足文档的可理解性和数据交换的需要。x m ls c h e m a 则不同，它内置了三 十七种数据类型，如l o n g ，i n t ，s h o r t ，d o u b l e 等常用的数据类型，并通过将 数据类型表示为由v a l u es p a c e 、l e x i c a ls p a c e 和f a c e t 三部分组成的三元组 而获得更大的灵活性。但是，x m ls c h e m a 数据类型的真正灵活性来自于 其对用户自定义类型的支持。 2 2 1 3 元素顺序的支持x m ld t d 与x m ls c h e m a 都支持对子元素节 点顺序的描述，但x m ld t d 没有提供对于无序情况的描述，也就是如果 以x m ld t d 来描述元素的无顺序出现情况，它必须采用穷举元素各种可 能出现的排列顺序的方式来实现，这种方法不仅繁琐，有时甚至是不现实 的。而用x m ls c h e m a 来实现子元素的无序描述要简单的多。 2 2 1 4 命名空间在x m l 中引入命名空间的目的是为了能够在一个 x m l 文档中使用其它x m l 文档中的一些具有通用性的定义( 通常是一些 元素或数据类型等的定义) ，并保证不产生语义上的冲突。x m l d t d 并不 能支持这一特性，这进一步限制了x m ld