（计算机软件与理论专业论文）xml数据管理技术研究.pdf

南京航空航天人学硕十学位论文 摘要 x m l 文档是一种公认的有语法而无语义信息的半结构化数据，但语义对保护数 据的完整性、数据存储和查询优化都有着十分重要的作用。本文在讨论现有x m l 数 据管理方法的基础上，对x m l 数据管理的相关技术做了深入研究。首先探讨了x m l 数据的完整性约束及相关问题，在此基础上提出了一个支持完整性约束的x m l 数据 模型c x m ；然后对目前流行的查询语言x m l q l 做了相应的改进和规范化，使其更 适合于x m l 数据的查询。最后，实现了一个能够支持完整性约束的x m l 数据管理 系统原型c x d m s 。实验表明，该系统能够有效存储和管理x m l 数据。此外，设计 与实现了人工神经网络汇率预测器，并取得到了较好的试验效果。 关键字：x m l 、完整性约束、数据模型、x m l - q l 、人工神经网络、外汇预测 x m l 数据管理技术研究 a b s t r a c t x m ld a t ai sa na c k n o w l e d g e dt y p i c a ls e m i s t r u c t u r e dd a t aw i t hg r a m m a ra n dw i t h o u t s e m a n t i ci n f o r m a t i o n h o w e v e rs e m a t i ci n f o r m a t i o ni sv e r yi m p o r t a n tt op r e s e r v ed a t a i n t e g r i t y ，d a t as t o r a g e a n d q u e r yo p t i m i z a t i o n b a s e d o nt h e e x i s t i n g x m ld a t a m a n a g e m e n tm o t h e d s ，t h i sp a p e r s t u d i e ss o m e k e y i s s u e sr e l a t e dt ox m ld a t a m a n a g e m e n tt e c h n i q u e s i no r d e r t om a x i m i z es e m a n t i cp o w e ro fx i v i ls p e c i f i c a t i o n s ，t h e m a i ni d e a so ni n t e g r i t yc o n s t r a i n t sf o rx m ld o c u m e n t sa n dt h ep r o b l e m sr e l a t e dt ot h e m a r ed e s c r i b e da n dd i s c u s s e d t h e nw e p r o p o s e lac o n t r a l m e dx m l d a t am o d e l ( c x m ) ， a n dm a k es o m ee x t e n s i o n sa n ds t a n d a r d i z a t i o n so nx m l - q l f i n a l l y ，a nx m ld a t a m a n a g e m e n ts y s t e m ( c x d m s ) i si m p l e m e n t e d e x p e r i m e n t a lr e s u l ts h o w st h a tt h e m e t h o d s p u t f o r w a r di n t h i s p a p e r c a l l e f f i c i e n t l y s t o r ea n d m a n a g ex m ld a t a a d d i t i o n a l l y ，w ed e s i g na n di m p l e m e n tad a t a - m i n i n gt o o lb a s e do na r t i f i c i a ln e u r a l n e t w o r k s 协e x c h a n g e r a t ef o r e c a s t i n ga n d a c q u i r e b e t t e r e x p e r i m e n t a le f f e c t k e yw o r d s ：x m l , i n t e g r i t yc o n s t r a i n t s , d a t am o d e l ，x m l q l , n e u r a ln e t w o r k , f o r e c a s t i n go fe x c h a n g e r a t e 2 南京航空航大大学硕十学位论文 第一章绪论 本章首先阐述了x m l 数据管理的研究背景。然后探讨了半结构化数据和x m l 数据各自的特点以及它们之间的异同。最后给出国内外相关的研究状况及本文的主要 研究内容。 1 1 研究背景 数据库系统的研究与开发在其三十年的历史中取得了巨大的成功，到目前为止， 数据库技术和系统的应用已遍及各个领域。数据库技术自6 0 年代诞生以来经历了网 状型、关系型、面向对象型以及对象关系型的发展过程l l j 。 互联网( i n t e m e t ) 自8 0 年代开始，经过十几年的发展，已经成为新经济时代的 标志，它遍及到人们的生活、工作和学习当中，甚至引起了人们思维观念的转变。作 为互联网最主要应用的w e b 正成为整个世界的窗口，它实现了全球用户和机构信息 的共享。此时，i t 人员的眼光都不由自主地投射到了w e b 上，而传统的关系数据库 和数据管理技术的研究，也在w e b 上找到了新的支点w e b 数据库的研究。 同时，与上述革命性的变化息息相关的超文本标记语言h t m l ( h y p e rt e x t m a r k u pl a n g u a g e ) 也急剧膨胀。i n t e m e t 上信息的数量级从9 0 年代初的m b ( 1 0 6 ) 过渡 到g b ( 1 0 9 ) ，甚至更多。如何有效组织、管理和利用这庞大的数据开始成为人们关注 的问题。尽管h t m l 从发明以来，已成功地成为w e b 上的通用语言，但是它仅注重 信息的表现形式，且数据本身和格式描述是混在一起的，不能很好地表达数据的语义。 如果要对h t m l 作排版和显示之外的处理就会由于没有统一的标准无法实现。为了 解决这一问题，i b m 公司的研究人员总结出三条规刚；第一，文档处理程序必须支 持同一种公共文档表现形式；第二，对于不同的应用，这些公共格式必须能提供不同 的标记以方便处理；第三，对文档进行一定的合法性检查r 3 1 。 1 9 7 4 年。g o l d f a r d 证明了“进行合法性检查的语法分析器”概念的可行性。从 此，国际标准化组织i s o 正式设立一个小组根据这些规则来制定标准通用标记语言 s g m l 作为复杂文档的交换标准。 随着网络应用的日益广泛，h t m l 的局限性也逐渐明显，越来越不适应作为 i n t e m e t 上信息交换和表示的工具。此时，作为s g m l 子集且兼具有h t m l 简单性的 可扩展标记语言x m l ( e x t e n s i b l e m a r k u pl a n g u a g e ) 应运而生。1 9 9 8 年2 月，全球 互联网联盟w 3 c ( w o r l dw i d ew e bc o n s o r t i u m ) 推出了x m l l 0 的正式版本，并正 式推荐x m l 作为下一代互联网数据的表示规范。 x m l 虽然是作为数据表示的规范提出的，但是由于其强大而灵活的表达能力， 1 州l 数据管理技术研究 且x m l 数据交换与平台无关，同时又具有很强的互操作能力再加上有和w e b 相关 的其他舰范的支持( 如x s l 等) ，以x m l 为主导的一系列规范已成为新一代的w e b 标准。世界各大厂商也纷纷推出围绕x m l 发展的产品与解决方案。总之，对x m l 的深入研究将有力促进企业的信息化和电子商务，具有巨大应用前景和经济效益。 从另一个角度看，w e b 虽实现了全球用户共享与交流信息，但是它在信息管理 方面存在缺陷。x m l 的出现使得w e b 变成了数据库【4 j ，这样不仅可以用数据库技术 来有效地解决大量信息的处理问题，而且给w e b 数据库发展带来了契机。 1 2 半结构化数据和x m l 本节研究半结构化数据和x m l 数据的特性以及它们之间的异同。 1 2 1 半结构化数据 w e b 这个庞大的数据集中绝大部分为复杂的、不规则的半结构化数据。这些数 据不仅爆炸式地不断增长，而且以各种形式存在，如从文件系统的无结构数据到关系 型数据库中的高度结构化的数据。这些半结构化数据既不象原始数据那样无结构，又 不象关系型或面向对象型数据库中的数据那样有严格的结构定义。它们有着如下几个 特点 5 , 6 1 ： 1 结构的不规则性 在许多应用中，系统中的大量数据常常含有异构元素。如一些元素是不完全的， 另一些元素则可能含有额外信息。且有时信息可能会采用不同的数据类型来表示。例 如，p r i c e 在一个数据源中是d o l l a r 而在另一个中是f r a n c s 。 2 结构的隐含性 半结构化数据具有一定的结构，但其结构与数据混在一起，没有显示的模式定义， 如h t m l 文件。 3 没有严格的类型约束 由于半结构化数据没有一个预先定义好的模式，且数据的结构也不规则，所以缺 乏对数据的严格类型约束。 目前，关于半结构化数据的研究主要集中在新的数据模型、查询模式、存储技术 以及优化技术等方面1 5 i 。在众多的研究课题中，对半结构化数据结构的研究是一个 非常重要的方向。半结构化数据的模式与传统的关系及面向对象数据的模式不同。传 统的数据库系统是基于一个固定模式的假设，这个模式是任何数据的规范，因此是先 于数据而存在的。对于半结构化数据，它们的结构信息往往要迟于数据而产生。经分 析，半结构化数据模式不同于传统的关系及面向对象数据的模式的地方有： 2 南京航空航天人学硕十学位论文 ( 1 ) 半结构化数掘的模式本身十分庞大，有时可能比数据还大，丽且会随着数据 f 】不断更新而处于动念的变化过程之中； ( 2 ) 半结构化数掘的模式是用于描述数据的结构信息，而不是对数据结构进行强 制性的约束： ( 3 1 半结构化数据的模式与数据间的差别模糊，它可能只描述数据的一部分结构， 也可能根据数据处理阶段的不同而使用不同的模式。 1 2 2 半结构化数据和x m l 数据 x m l 数据和半结构化数据从本质上来看是相似的，可以认为l 数据是一类 新型的半结构化数据，但同时x m l 数据具有一些传统半结构化数据所没有的特点。 下面是x l m 。数据与传统意义上的半结构化数据的异同。 x m l 数据和半结构化数据都可以用图模式来表示，且都是自描述的。但是，x m l 数掘的内容和元素标注是可以混合的，而半结构化数据不是；而且x m l 数据还可以 包含其他的内容( 如处理指令和注释等) 。 对x m l 数据和半结构化数据查询所用的查询语言是很相近的。它们都有路径表 达式、重构算子、递归结构等特性。目前还没有公认的m 。查询语言规范。 半结构化数据没有固定的模式，需要抽取( e x t r a c t i n g ) 和推导( i n f e r r i n g ) 模式： 而x m l 支持文档类型描述( d t d ) ，d t d 一方面可以认为是数据的近似模式，但纯 粹把d t d 作为模式还存在许多不足。 1 2 3x m l 的特点 x m l 之所以能在i n t e m e t 上迅速发展，其原因在于x m l 技术具有下列特性 7 , 8 , 9 1 ： 1 x m l 为文档作者提供了一个友好的环境。x m l 的严格定义和规则集使入和机 器都能容易地阅读x m l 文档。x m l 文档语法包含一个非常小的规则集，使开发者 很容易上手。其中的基本结构可以被用来表示复杂的信息集合。 2 x m l 在两个意义上是可扩展的。首先，它允许开发者创建它们自己的文档描 述方式( d t d 、) q “l s c h e m a 、r e l a x 等) 和可用于多种应用的“可扩展的”标记 集。其次，有许多附加的标准对x m l 的功能进行扩展，它们可以向x m l 的核心功 能集中增加样式、链接和引用能力。 3 x m l 是与平台无关的。它可以在多种平台上使用，而且可以用不同的工具进 行解释。由于文档的结构是相容的，所以解释它们的语法分析器就比较容易创建。 x m l 支持用于字符编码的许多标准，允许它在全世界不同的计算机环境中使用。 4 x m l 标准在w e b 上是完全开放的，可以免费下载。x m l 文档本身也是开放 3 x m l 数据管理技术研究 的，任何人都可以对一个x m l 文档进行语法分析并检查其有效性。不同的用户可以 根据自己的需要创建其特有的x m l 文档，这也是x m l 的开放性的表现之一。 1 3 研究现状 本节主要探讨了x m l 与数据库的关系，并对与x m l 数据管理相关的国内外研 究现状做了阐述。 1 3 1 数据库与x m l 的关系 在i n t e m e t 发展的今天，数据库技术酋先要解决的问题是：在数据库与i n t e m e t 之上所架构的信息系统之间寻找可结合的共同点。原有数据库技术面对的是若干个数 据库在一定的网络空间上连接起来的系统，在这个系统上用户有效地管理各自的数据 库，并完成一定的任务。在w e b 中这一情形发生了根本的变化，w e b 上存储的是一 些无结构、无法组织管理的数据。因此，对这些数据的管理和对传统结构化数据的管 理有着根本的差别。这是因为： 1 x m l 数据和数据库数据本质不同 尽管x m l 可以有文档类型描述，但它是和数据混合在一起的。因此本质上说， x m l 数据还是一种半结构化数据。它是自描述的、无模式( 或者说是弱模式) 的； x m l 数据的结构随时都可以发生变化，且是异构的、深层嵌套的和不规则的。 2 x m l 数据和数据库数据来源不同 x m l 数据往往是由文档的设计者提供的，而数据库数据一般由专家设计。 3 x m l 的w e b 数据管理系统和传统的数据库管理系统不同 x m l 数据和关系型数据有许多相似之处，由于前者是一种典型的半结构化数据， 因此二者又有着不同点1 0 3 1 l ：( 1 ) x m l 数据模型表达能力要比传统的关系模型和对象 模型更强；( 2 ) x m l 数据有自己的特点，简单地应用传统的数据库技术不能使其得到 完全的体现；( 3 ) x m l 主要应用于i n t e m e t 上的信息表示和信息交换，而传统的数据 库技术并不擅长于这些应用。 1 3 2x m l 数据管理的研究现状 早在9 0 年代就有组织和研究机构开始研究半结构化数据管理和x m l 数据管理 的相关问题了，影响较大的如s t a n f o r d 大学的l o r e 项目和& t 实验室的s t r u d e l 项目等。每年召开的国际顶级的数据库界会议都把半结构化数据和x m l 的相关研 究方向作为热点来讨论，丽研究热点从某种意义上恰好说明了问题尚未妥善解决。正 4 南京航空航天人学硕十学位论文 【烈为这样，和x m l 相关的各种技术都有待发展，目前还没有一个完整的x m l 管理 系统。x m l 是一种独特的半结构化数据类型，因此半结构化数据和x m l 之间具有 显著的相似性，半结构化数据已有的理论和原型系统可以作为研究x m l 相关问题的 基础。同时，x m l 所具有的独特特性又为我们带来了新的研究课题。下面是几个主 要的研究方向： 1 数据模型 数据模型是数据管理的基础，在对x m l 数据进行管理时也是如此。x m l 数据 模型是设计丌发专用x m l 数据管理系统的前提。由于x m l 数据的结构和半结构化 数据一样，类似于图或树，所以早期提出的一种简单的、基于图的数据模型目前仍然 是半结构化数据和x m l 数据建模的基准。很多x m l 数据模型都是在此基础上作了 一些改进得到的，如s t a n d f o r d 大学的o e m 模型1 1 4 , 1 5 1 是最具有代表性的。还有一些针 对x m l 语言本身提出的数据模型i l i a 9 0 0 1 ，如t a x 等。 2 完整性约束 x m l 作为w e b 应用中信息交换的标准，它提供了一个便捷的语法来表达来自异 质源的数据，但x m l 所能提供的语义信息却并不多。因此，为说明x m l 数据的语 义，研究人员提出了类型系统、描述逻辑、源数据描述【3 1 j 5 】等方法。这些方法中，大 多都指出了完整性约束对x m l 数据的语义说明十分重要。在传统的关系数据库中通 过键和外键这种基本的完整性约束机制来实现模式引用，x m l 文档也不例外但是 它的完整性约束比关系模型要复杂的多，具有很重要的研究意义。 3 查询语言 由于半结构化数据和x m l 的结构独特，传统数据库查询语言不能直接搬来用。 目前已经开发出了几种半结构化数据的查询语言，如l o r e l 1 4 1 、w e b s q l t 2 ”、 w e b o q l e 2 2 1 及s t r u q l 2 3 蝽。他们的共同特点是，通过使用正规路径表达式，可以 遍历数据中任意长度的路径。x m l 数据查询语言的发展在很大程度上受到了半结构 化查询语言的影响，有的就是由半结构化查询语言改进而得。目前主流的x m l 查询 语言有l o r e l i l 4 1 、x m l q l t 4 0 1 、x m l g l 2 5 1 、x s l t x 4 1 和x q l 4 1 1 等【2 4 】。 4 数据的存储 所有传统的d b m s 都是以数据的有效存储为宗旨，并将数据持久地存储于磁盘 上。但是对于x m l 这种图或树状的数据结构，用聚类( c l u s t e r ) 存储方式来支持它 的有效存取并非易事。目前，x m l 数据存储的方式有很多种【2 】主要有文件存储方 式、专用存储方式【陀l ( 即专门针对x m l 数据设计存储方式) 和通用存储方式【2 7 , 2 8 】 ( 利用现有的存储管理等技术有效地管理x m l 数据) 。 5 专用于v i l 数据管理的d b m s d b m s 是由若干组件构成的复杂的软件系统，其中每个组件都负责特定的数据管 理任务。由于与x m l 相关的各种技术都还没有统一标准出现，因而也没有成熟的专 门用于x m l 数据管理的d b m s 诞生，设计和开发这样的d b m s 是一个研究热点。 5 x m l 数据管理技术研究 6 其他的研究方向 对x m l 数据其他方面的研究主要有：x m l 数据索引技术 17 , 1 8 1 、x m l 查询优化 ! j7 , 1 s 4 3 1 、x m l 查询代数川t j 9 , 2 0 、x m l 视图f 1 7 , 1 8 j 等方面。 在我国，对x m l 也丌展了初步的研究及应用，于2 0 0 0 年1 2 月2 7 2 8 日由国 家高技术发展计划智能计算机主题专家组主持，在北京召开了“中国x m l 技术2 0 0 0 研讨会”，研讨会较为全面地反映了目前我国x m l 的研究水平。总体来说，国内 x m l 研发的力量还比较弱小，真正有深度的研究还很少。 1 4 本文的结构组织 本文主要由七部分组成： 第一章主要介绍了半结构化数据与x m l 的发展及其特点，x m l 数据管理的国内 外研究现状。 第二章主要研究了x m l 数据的完整性约束及与之密切相关的一致性和蕴含性问 题。 第三章主要研究了x m l 数据管理系统建立的基础：数据模型，提出一个具有约 束表达能力的x m l 数据模型_ 叫c 。 第四章在对现有的x m l 查询语言做比较的基础上，详细研究了本文所选择的查 询语言x m l q l ，并根据实际应用的需求对其作了相应的改进。 第五章提出了提出可以保留键约束的x m l 数据的关系存储的算法：分析了查询 实现的具体方法：为了建立数据字典，还提出了x m l 模式x g r m m ：n a r 和模式的提取 算法。 第六章设计并实现了人工神经网络汇率预测器。 第七章是对本文的工作的总结。 6 南京航空航天人学硕十学位论文 第二章x m l 的完整性约束 数据的完整眭约束是用来保证授权用户对数据库进行修改时不会破坏数据的一 致性，以防止对数据的意外破坏和非法存取的，从而保证数据的正确性和相容性。本 章主要研究x m l 数掘的完整性约束及相关问题。 2 1 传统数据模型与x m l 的完整性约束 比。 本节探讨x m l 完整性约束的概念并将其与传统数据模型的完整性约束进行了对 2 1 1 传统数据模型的完整性约束 完整性约束在传统数据库中一直是数据模型的一部分，它在数据的语义说明、更 新一致性控制和查询优化等方面有着重要的意义。关系数据模型中完整性约束可以分 为静态约束和动态约束，而静态约束又可以分为三种，其一为固有约束，既满足第一 范式的约束，如关系的属性应该是原子类型的：第二种为隐含约束，是指隐含于数据 模型中的约束，一般用d d l 语句来说聪，如域约束，实体完整性约束和引用完整性 约束；还有一种就是用户自己定义的约束，这种约束依赖于数据的语义和应用。动态 约束不是对数据库状态的约束，而是数据库从一种状态转变为另一个状态时应该遵守 的约束，例如在更新雇员表时，工资、年龄等属性的值只能增加，不能减少等。这种 约束通过提供灵活的方法来决定哪些操作将被执行以维护数据的一致性。目前的关系 数据库系统，如d b 2 ，以表约束和断言支持这种约束。表约束定义于某一单个表内 部的约束，当表被修改时，进行检测；而断言定义多个表间的约束关系，当其中任何 一个表被修改时，都要检测相应的约束 3 2 1 。 面向对象数据库系统中的完整性约束，除了前面介绍的关键字约束和引用约束外 还有逆关联约束、存在约束、不相交约束和包含约束等多种约束【3 们。 例2 1 我们采用o d l 语法定义了两个类e m p l o y e e 和d e p t 。 c l a s se m p l o y e ec l a s sd e p t a t t r i b u t es t r i n gn a m e ； a r a i b u t es t r i n gd n a m e ； a t t r i b u t es t r i n ga d d r e s s ；a t t r i b u t ee m p l o e e m a n a g e r ； r e l a t i o n s h i ps e t i n _ d e p tr e l a t i o n s h i ps e t h a s _ s t a f f i n v e r s ed e t p ：h a s _ s t a f f ；i n v e r s e e m p l o c c ：i n)_dept； 7 x m l 数据管理技术研究 我们看到属性e m p l o e e ，i nd e p t 与d e p t ，h a s _ t a f t 之间具有逆关联约束，它表示属性 e m p l o e e i n d e p t 的值对应于类d e p t 中的一个实例集合，而属性d e p t h a s s t a f f 的值对 应于类e m p l o e e 的一个实例集合。这类似于关系数掘模型中的引用约束，但与关系数 据数据库不同，这里的属性值可以为集合类型。 2 1 2x m l 的完整性约束 1 x m l 数据说明 一个x m l 文档的数据说明一般由两部分组成：一是类型定义( 如d t d ) ，二是 完整性约束条件集( 如键和外键等) ，这两者在x m l 文档中以非平凡方式相互作用。 下例给出一个具体的x m l 数据说明s i ，sm = ( d 1 ，1 ) ，其中d l 为一个简单的d t d ， 用来说明文档的结构：1 为一个完整性约束条件集，用来说明文档的基本语义信息。 d t d d i ： c o n s t r a i m s i ： c o u n t r y n a m ec o u n t r y p r o v i n c e n a m e p r o v i n c e c a p i t a l n p r o v i n c e c a p i t a l c a p i t a l i n p m v i n c e p r o v i n c e n a m e 这个x m l 数据说明的语义为：每个c o u n t r y 元素都有一个c a p i t a l 子元素、p r o v i n c e 元素集( 次序可变) 和一个i d 属性。每个p r o v i n c e 也都有个c a p i t a l 子元素、c i t y 元 素集( 次序可变) 和一个i d 属性。每个c a p i t a l 元素有i n p r o v i n c e 属性作为i d ，且每 个c i t y 元素有n a m e 属性。下图2 1 就是遵循上述x m l 数据说明的x m l 树。 2 。x m l 数据的完整性约束 完整性约束在传统数据库中非常重要。它不仅可以标识、引用元组，而且在对数 据库进行搜索、查询和更新时也起着很重要的作用。同样，完整性约束在x m l 数据 管理中也是十分重要的。 8 南京航空航犬人学硕十学位论文 “胁1 9 l u m 人 liw”bur”，cajpitalliwburg ” “m “a n d 7 i t a 1 n a m e i i n p r o v i n e“h a s s e h ” i t t p r o v m e “m i a s t r i c h ” l i w b u r g “l i w b u r g 圈21 一棵菠循s l 说明的v l 树 x m l 作为w e b 中信息交换的标准，虽提供了一个便捷的语法来表示各种w e b 数据， 但是它所能提供的语义信息却并不多。完整性约束对于说明语义是非常重要的，且对 于查询优化、防止修改异常和在信息集成中保存特定信息都十分重要。例如，许多因 某种特定目的把数据存储为层次格式的科学数据库，很容易转化为x m l 格式且有一 个组织良好的层次键结构。在传统关系数据库中通过键和外键这种完整性约束机制来 实现模式引用，x m l 文档也不例外，但是它的完整性约束机制比关系模型要复杂的 多，且有着重要的研究意义 3 1 , 3 5 , 3 6 1 。 x m ls t a n d a r d j ，x m ld a t a p j ，x m ls c h e m a 博都定义了各种形式的x m l 键约束。 在标准的x m l 模式语言d t d ( 在x m ls t a n d a r d 中定义的) 中，用i d 属性来唯一地 标识x m l 文档中的一个元素，而i d r e f 属性用来实现引用机制。但是被引用元素的 类型却无法说明。i d 属性的主要缺点是它只能在整个文档中唯一标识一个元素而不 能在一个元素集中唯一标识元素。因此，它被用来作为内部指针雨不是键。 在x m l d a t a 中也精确地定义了键。并规定在元素集中不能同时定义多个键，但 对于不同的元素类型键约束是唯一的。例如，在一个图书馆中，书和期刊不能用同一 个键约束。 x m l s c h e m a 对键的定义更加精确，它用x p a t h l 3 3 】表达式定义键来扩展x m l d a t a 中键的定义。但是由于x p a t h 语言本身比较复杂，存在一些技术上的问题尚未解决， 如x p a t h 表达式的“相等”和“包含”问题，故无法有效地判断两个键是否等价。同 时x m l s c h e m a 把“等值”仅限于文本上，这显得过于严格。 此外，x m l 文档中元素的子元素需要用层次键来标识，而现有的x m l 键都不 能表达键的层次结构。 9 厂 一 、 一 黔一 懑钆 x m l 数据管理技术研究 2 2x m l 完整性约束的类型 从一t 节的比较可以看出，我们需要一个表达能力更强的x m l 文档的键约束。本 节通过例子柬对x m i 完整性约束作系统的分类说明。我们给出三类约束：包含约束、 逆关联约束和键约束。 例2 2 下面是用o d l 定义的例子 c l a s ss t u d e n t ( s e t e n ts t u d e n t sk e ys s n ) c l a s s c o u r s e ( s e t e n d g o l l r s ek e y c n o ) a t t r i b u t es t r i n gs s n ； a t t r i b u t es 伍n gc n o ； a t t r i b u t es t r i n gn a m e ；a t t r i b u t es t r i n gt i t l e ； r e l a t i o n s h i ps e t t a k i n gr e l a t i o n s h i ps e t t a k e n _ b y i n v e r s ec o u r s e ：t a k e n b y ； i n v e r s es t u d e n t ：t a k i n g ； 1 包含约束 定义2 1 包含约束的一般形式为：r x g r 【y 】，其中r ，r 是元素类型；x ，y 是 属性集。 上例中包含约束有：s t u d e n t t a k i n g c o u c n o 和c o u r s e t a k e n _ b y s t u d e n t s s n 。表达的语义为t a k i n g 属性的可能值集是c n o 属性可能值集的子集： t a k i n g _ b y 和s s n 亦然。 半结构化数据和x m l 数据的完整性约束通常用路径表达式来定义，因而比关系 数据库中相应的部分要复杂的多。路径表达式中常用的路径包含约束p i n e 在半结构化 数据中已研究的比较成熟。其一般形式为：a _ b ，其中a ，b 是路径表达式。如果我 们用带根边有标记有向图来表示半结构化数据。这种包含关系衷达的意思是：任何拾 a 从根出发的可达结点，也可以沿b 从根出旋可达。 但上面定义的包含约束只在全局范围内有意义，不能表达局部的包含关系。为 此，我们引入另一类路径约束相对路径约束p 盘。其形式为：a ，b g c ，其中，a ， b ，c 足正规表达式。a b g c 表达的语义是：对于任一结点x ，y ，如果x 从根出发沿 a 可达。且y 从x 出发沿b 可达，则y 一定也可从x 出发沿c 到达。 2 逆关联约束 定义2 2 逆关联约束是另一种完整性约束，其一般形式为：r x 】4 - - r 【y 】，其中r ， r 是元素类型，x ，y 是属性集。 上例中的逆关联约束有：s t u d e n t s t a k i n g , h c o u r s e t a k i n g _ b y ，语义为任意的s t u d e n t 1 0 南京航空航天人学硕士学位论文 年u 任意的c o u r s e 如果菜s t u d e n t 选了某c o u r s e ，则这一c o u r s e 一定被该s t u d e n t 选了。 反之亦然。 当我们连续两次应用逆关联约束时，就会得到初始集的一个子集。因而连续两次 应用上述逆关联可以推出这样的包含关系：s t u d e n t t a k i n g t a k e n b y c s t u d e n t 。 3 键约束 定义2 3 键约束的基本形式为：r x 】寸r ，其中r 是元素类型，x 是属性集。即r 的x 属性的值能唯一地标识所有r 元素集。例如：c o l l r s e ，c n o _ c o 埘s e ， s t u d e n t s s n - * s t u d e n t 。即两个不同的c o u r s e ( 或s t u d e n t ) 应有不同的c n o ( 或s s n ) 值。 除了这种标识元素的键约束外，雏键也是键约束的一种。其形式为r l 【) q r 2 【y 】， r 2 y 1 - - r 2 ，其中r l ，r 2 是元素类型，x ，y 是属性集。外键表达的语义是：r l 的x 属性的值集是r 2 的y 属性值集的一个子集，且y 属性的值唯一地标识所有r 2 元素。 例如：p r o v i n c e n a m e - p r o v i n c e ，c a p i t a l i n p r o v i n c e 】c _ p r o v i n c e n a m e 】 这两个表达式的意思是：两个不同p r o v i n c e 的n a m e 不同，且i n p r o v i n c e 属性的 值集是n a l r l e 属性值集的子集。 用路径表达式表示的半结构化数据的键和外键形式分别为：r 1 1 _ r l 和r 1 1 r 2 1 ， r 2 1 一r 2 ，其中r l ，r 2 是正规路径表达式，l 。1 是边标记。 定义2 4 相对键约束表达的是局部的键约束。其形式如下：r ( r 1 1 - - r 1 ) ，其中r ， r l 是正规路径表达式，1 ，l 是边标记。语义为相对于r 元素类型的每个结点x ，l 是 x 后继结点r l 的键。如：u n i v e r s i t y ( c o m e c n o 寸c o u r s e ) 。 相应的外键为：r ( r 1 1 c _ r 2 1 ) ，r ( r 2 1 斗r 2 ) ，其中r ，r l ，r 2 是正规表达式，l ，1 ， 是边标记。对于图中所有的r 元素集合中的每个x ，l 是类型r l 的x 结点的后继结点 的外键，并且参照x 的后继r 的键l 。具体例子如下： u n i v e r s i t y ( c o u r s e c n o - + c 0 1 n s e ) u n i v e r s i t y ( s t u d e n t t a k i n g c c o u r s e c n o ) 在一个u n i v e r s i t y 中，c n o 的值唯一地标识c 0 1 n s e 元素，且t a k i n g 属性的可能值 集是c n o 属性的可能值集的子集。 相对键具有下述两个特性： ( 1 ) 可传递性 键是用来唯一标识文档中的特定成员。如- f 侈i i ：( ，( b i b l e h o o k ， n a m e d ) ( b i b l e b o o k c h a p t e r , ( v e r s e ， n u m b e r ) ) 中的节v e r s e 在整个b o o k 中却不唯一。因为没有定义b o o k 中用来标识c h a p t e r 的键， 所以遗漏了约束( b i b l e b o o k ，( c h a p t e r ， n u m b e r ) ) 条件。 x m l 数据管理技术研究 定义2 5 是一个相对键的集合，它是可传递的，当且仅当对于任一楣对键 r ( r 1 1 _ r 1 ) ，有一个键( r 2 1 - r 2 ) ，是r ( r 1 i r 1 ) 的前序。 ( 2 ) 可更新性 我们先来看这样一个例子： u n i v e r s i t y n q l e u n i v e r s i t y u n i v e r s i t y ( d e p t e m p l o y e e e m p i d d e p t e m p l o y e e ) 我们用大学名和这个大学里雇员的雇员号来标识一个雇员，如果现在需要往数掘 库中增加新的雇员，我们需要说明往哪个部门( 系) 里加这个雇员，但上例无法标识 部门这个级别的单位，因此我们可以往任意部门添加此雇员。如果我们用键来保证这 种更新，每次规定好具体往哪旱插入。上例中加入t m i v e r s i t y ( d e p t d e p t - i d - - d e p t ) 就会 成为可更新的了。下面我们来e 式定义可更新性： 定义2 , 6 是一个相对键的集合，如果它是可传递的，且当r l ( r 2 n 1 寸r 2 曲， 有键r l ( r 2 1 _ r 2 ) ，其q 6 i r 2 o ，r 1 r 2 - - r l r 2 ，则这个相对键的集合是可更新的。 2 3 一种完备的x m l 完整性约束 文献 3 4 】独立于d t d 和x m ls c h e m a ，利用绪点等值概念和路径表达式对x m l 定义了层次键。本节在此基础上对x m l 数据的完整性约束做进一步研究。 2 3 1 路径表达式语言 在关系数据库中判断值是否相等，只需要比较原子值( 如整型) ，而x m l 文档 的结构是层次型的，因此比较两个结点的值是否相等与关系数据库不同。路径表达式 的等价和包含关系的确定性对于键的推理是十分必要的。下面是其相关的定义。 定义2 7 两个结点b 1 ，1 1 2 值相等，记为n l = ，n 2 ，当且仅当r l l ，1 1 2 符合下面三点： ( i ) n l ，n 2 的标记相同； ( i i ) 如果n l ，n 2 是属性或者文本结点，则它们的值要相等； ( i i i ) 如果n l ，1 1 2 是元素结点，那么( 1 ) 对任何n l 的属性a i ，n 2 也要存在相同的属 性a 2 且a l = 。a 2 ，反之亦然；( 2 ) 对n l 的子元素v l ，v 2 ，v n ，n 2 也要存在相应的子 元素w l ，w 2 ，w n ，并且v i = ，w i ，i e 1 ，a 】，反之亦然。 两个结点值相等是指这个两个结点及其结点下面的子树都完全相同。这个值相等 的概念把“等值”的对象扩充到任意结点而不是仅限于文本。 这里用的路径表达式是正则表达式的子集，因而有足够的表达能力，并且，可以 基于它来解决路径的“相等”和“包含”问题。 定义2 8 路经表达式语言p l 满足下列五点： 1 2 南京航空航天人学硕士学位论文 ( 1 1 窄路径e ； ( m 结点的名称( 标记或者属性名) ； f i i i ) “”代表任意单个结点名； ( i v ) “”代表任意路径； ( v ) 路径的连接p o ，p 和q 是路径表达式。 此路径表达式的定义中，路径只能沿着x m l 树往下移动，即从结点n l 开始，经 过路径p 所到达的结点，记为n i p 】，如果n 2n l 【p 】，那么n 2 就是i l l 的子树结点。在 这一点上与x p a t h 有所不同。此外，简单路径不包含“”或“。 2 3 2 键约束 根据上一小节的定义，现在给出x m l 键完备的形式化定义。 定义2 9x m l 键约束中是形如( q ， p l ，p 。 ) 的表达式。其中o 是路径表达 式， p ，p 。) 是个简单路径表达式集合。如果一个结点n 满足个键说明( q ， p p n ) ) 当且仅当对任意n l ，n 2 n 【q 】，如果对所有i ，l i s n ，存在z i n l p i 】，z 2 e n 2 p i 】 使得z l - 。z 2 ，则有n 1 = n 2 。如：( p e r s o n s t u d e n t ， s s n ) 。 当一个文档的根结点满足键说明，则这个文档满足了这个键说明。反之亦然。注 意到：对于任意的n l 。n 2 e 【q 】，如果p i 在n t 或者n 2 缺省，根据定义n i 【p j 】与n 2 p j 的交集为空。这恰好对应于x m ls c h e m a 中的唯一约束。但此处的键定义支持能到 达多个结点的键路径上结点的比较。即对于任意n l ，n 2 e n 【q 】，如果n l f p i 】包含多个 结点，且n 2 【p d 中有结点与其中之一相同，则n 1 = n 2 。因此，有文档不满足上述的键约 束。如： 1 吲b 1 吲l b 2 叫a 我们约定键( a ， b ) ) 表达这一文档的根。a 元素由b 子元素的值唯一地标识。 因为第一个a 元素的b 子元素与第二个a 元素的第一个b 子元素有相同的值，而按 照键的定义，两个a 元素应该是同一个元素，所以该文档不满足上述键约束。 上述定义保持了x m l 数据的半结构化特性，对路径的存在性和唯一性没有特别 要求