（计算机软件与理论专业论文）保持语义的xml数据存储和更新.pdf

摘要 摘要 随着i n t e m e t 和w e b 应用的迅速发展，x m l 正取代h t m l 成为w e b 数据发 布、集成、仓储和交换的标准，x m l 的出现和广泛应用带来了w e b 技术的革命， 也为电子商务的新型解决方案提供了重要基础，同时x m l 在电子信息发布、数 字图书馆、w e b 信息搜索和集成等领域都有广阔的应用前景。数据形式的多样化 使得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 数据本身 的语义约束，基于关系数据库技术，研究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 文档保持键约束地映射到关系数据库 中的方法。实现了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 文档在关系数据库中的规范化存储，研究了x m l 文档保持 键约束的更新策略。通过把x m l 键约束映射为关系数据库中的函数依赖，在更 新x m l 文档时，不但保持了x m l 文档本身的键约束，还使关系数据库和x m l 文档保持了一致。利用上述标注技术，快速定位更新位置，从而有效地实现了 x m l 文档保持键约束的更新。更新的实现使得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 所满足的d t d 进行无损分解，利用x m l 转换 技术t r e x 进行被更新文档的规范化，以及更新后x m l 文档用户视图的转换。 关键词：x m l ，x m l 键，标注，规范化存储，x m l 范式，x m l 文档更新 a b s t r a c t a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n t e r n e t w e b ，x m lh a sb e e nb e c o m i n gt h ed ef a c t o s t a n d a r df o ri n f o r m a t i o np u b l i c a t i o n ，i n t e g r a t i o n ，s t o r a g ea n de x c h a n g eo nt h ew e b ， s u b s t i t u t i n gf o rh t m l t h ea p p e a r a n c ea n dw i d ea p p l i c a t i o n so fx m l h a sa r o u s e da r e v o l u t i o no nt h ew e b a n d p r o v i d e s t h en o v e ls o l u t i o n so fe - b u s i n e s sw i t ht 1 1 ec r i t i c a l b a s i s m e a n w h i l e ，x m li sa n t i c i p a t e dt ob et h r i v i n go ns u c ha r e a sa se l e c t r o n i c i n f o r m a t i o nr e l e a s e ，d i g i t a ll i b r a r y ，w e bi n f o r m a t i o nr e t r i e v a la n di n t e g r a t i o n ，a n ds o o n ，x m li s a p p l i e d i n t or e a l a p p l i c a t i o n si nt h er o l eo fs e m i s t r u c t u r e dd a t af o r v a r i o u sd a t af o r m a t s d i f f e r e n tk i n d so fx m l q u e r yl a n g u a g e s ，s t o r a g em a n a g e m e n t t e c h n o l o g i e sa n dx m l s e m a n t i cc o n s t r a i n t sa r ep r o p o s e di no r d e rt oo r g a n i z ea n d m a n a g ex m l d a t ae f f i c i e n t l y w h i l e ，x m ld o x u m e n tm a n a g e m e n t u s i n gr e l a t i o n a l d a t a b a s e s ，x m lu p d a t ep r e s e r v i n gs e m a n t i cc o n s t r a i n t sa r et h ei m p o r t a n tp a r t so f e x t e n d i n gx m lp r o c e s s i n gc a p a b i l i t i e s ，s ot h a t i ti s i n d i s p e n s a b l et o d e f i n ex m l s t o r a g er u l e s ，u p d a t eo p e r a t i o n sa n d e v a l u a t et h e m c o r r e s p o n d i n g l y w i t ht h e s eb a c k g r o u n d s ，i nt h i sd i s s e r t a t i o n ，w et a k ex m l k e y si n t oa c c o u n ta n d s t u d yt h ei s s u e s o nx m l s t o r a g ei nr d b ，x m lu p d a t e sb a s e do nt h en o r m a l i z e d r e l a t i o n a ls t o r a g ea n dt h ex m ln o r m a lf o r m p r e s e r v i n gt h ei n h e r e n tk e yc o n s t r a i n t s i n p a r t i c u l a r , w ef o c u s o nt h ep r o b l e m so ft h en o r m a l i z e dr e l a t i o n a l s t o r a g e ，t h e s e m a n t i ca n n o t a t i o no fx m l ，a n dt h ex m l u p d a t e sp r e s e r v i n gk e yc o n s t r a i n t s t h e e f f e c t i v e s o l u t i o n s ，c o r r e s p o n d i n ga l g o r i t h m s a n d t e c h n i q u e s a r e p r o p o s e d p r e l i m i n a r ye x p e r i m e n t sa r ec o n d u c t e d ，a n dt h er e s u l t ss h o wt h ee f f e c t i v e n e s so f t h o s ea p p r o a c h e s t h em a i nc o n t r i b u t i o n so ft h i sd i s s e r t a t i o no a nb es u m m a r i z e da s f o l l o w s p r o p o s e an o v e ls t o r i n gm e t h o do f m a p p i n gx m ld a t ai n t or d b p r e s e r v i n gk e y c o n s t r a i n t s ，a n di m p l e m e n tt h en o r m a l i z e dr e l a t i o n a ls t o r a g eo fx m l b ye l i m i n a t i n g t h en e e d l e s sr e d u n d a n c ya n do p e r a t i o na n o r m a l i e s ，t h i sm e t h o di st h eb a s i sf o rk e y c o n s t r a i n t p r e s e r v i n gx m lu p d a t i n g p r o p o s ean o v e la n n o t a t i o no fx m l b a s e do nx m l k e y sa n dt h e r e l a t i o n a l s t o r a g ew i t hr e s p e c tt ot h eg r a n u l a r i t yo fk e yn o d ea n dx m lf r a g m e n tr e s p e c t i v e l y t h ea n n o t a t i o ne s t a b l i s h e st h em a p p i n gb e t w e e nr e l a t i o n a ld a t aa n dx m ln o d e so n e t oo n e t h u s ，t h ep o s i t i o no f u p d a t e sc a nb el o c a t e de f f i c i e n t l yo nt h ea n n o t a t e dx m l v i e w a c c o r d i n g t ot h er e t r i e v a lc o n d i t i o n s s t u d yt h es t r a t e g yo fu p d a t i n gx m lp r e s e r v i n gk e yc o n s t r a i n sb a s e do nt h e a b s t r a c t n o r m a l i z e dr e l a t i o n a l s t o r a g eo fx m ld o c u m e n t s b yp r o p a g a t i n gx m lk e y st o r e l m i o n sa sf u n c t i o n a l d e p e n d e n c i e s ，x m ld a t a a n dt h e c o r r e s p o n d i n gr e l a t i o n a l s t o r a g ec a nb eu p d a t e da tt h es a m et i m e ，i nw h i c ht h ec o i n c i d e n c eb e t w e e nt h e mi s p r e s e r v e d u s i n gt h ea n n o t a t i o na b o v e ，t h eu p d a t cp o s i t i o nc a nb el o c a t e da n dt h e x m ld o c u r a e n ti su p d a t e d t h i st e c h n i q u ef u l l ye v o l v e sx m li n t oau n i v e r s a ld a t a r e p r e s e n t a t i o na n ds h a r i n gf o r m a tb yb r i n g i n ga b o u tx m lu p d a t eo p e r a t i o n sa n dt h e e v a l u a t i o ns t r a t e g i e s e u r t h e rs t u d yt h eu p d a t es t r a t e g yp e r f o r m e dd i r e c t l yo nt h en o r m a l i z e dx m l d o c u m e n t s ，s a t i s 母i n gt h e s e m a n t i cc o n s t r a i n t so fx m lk e y sa n dt h es t r u c t u r e c o n s t r a i n t so fd t d i nt h i sm e t h o d ，x m l k e y sf i r em a p p e di n t ot h ee q u i v a l e n tx m l f u n c t i o n a ld e p e n d e n c i e s ，a n dd t di sd e c o m p o s e dl o s s l e s s l y u s i n gt h ee f f i c i e n tx m l t r a n s f o r m a t i o nt e c h n i q u eo ft r e x ，x m li sn o r m a l i z e d ，u p d a t e da n dt h er e s u l tx m l d o c u m e n ti sg e n e r a t e dc o n f o r m i n gt ot h ed t do f u s e r p r o f i l e s k e y w o r d s ：x m l ，x m lk e y ，a n n o t a t i o n ，n o r m a l i z e ds t o r a g e ，x m ln o r m a lf o r m ， x m l u p d a t e 2 第章前言 1 1x m l 简介 第一章前言 继h t m l ( h y p e r t e x tm a r k u p l a n g u a g e ) 语言之后，x m l ( e x t e n s i b l em a r k u p l a n g u a g e ) 【b p s + 9 8 语言业已逐渐成为互联网信息的主要表示和交换工具。早在 1 9 9 6 年w 3 c ( w o r l dw i d ew e bc o n s o r t i u m ) 就开始设计一种可扩展的标注语言， 当时的工作重点是期望将s g m lf i s 0 8 6 的灵活性和强大功能与已经被广泛采用 的h t m l 结合起来。这种后来成为x m l 的语言继承了s g m l 规范的很多特性， 而且x m l 实际上就是s g m l 的一个子集。从s g m l 入手使得该设计小组能够 将精力集中在简化已有的成果上。s g m l 已经提供了一种可以无限扩展的语言， 它允许任何人们能够根据自己的需要加以扩充。x m l 之所以要较s g m l 更为简 化。很大程度上出于易用性的考虑：人们对标签的读写过程应该是使用现有的简 便而通用的工具，同时也应当简化计算机对文档和数据交换的处理；另外，这样 的文档应该被人方便地理解。由于太多的强大功能，s g m l 变得过于繁复，以至 于很难编写出针对这种语言的通用解释处理器，而x m l 的解释处理器则能够比 较方便地实现，这正是得益于x m l 语言的简单性。此外，x m l 使得现有的i n t e m e t 协议和软件的协作性更好，从而简化了数据的处理和传输。作为一个s g m l 语 言的子集，x m l 还保持了对现有的面向s g m l 系统的向下兼容性，这样，用 x m l 标注的数据仍然可以在这些系统中使用，为基于s g m l 的行业节省了大量 的改造费用，同时与w e b 的结合也使得它们更便于被访问。 与h t m l 相比，x m l 具有许多优点： x m l 简单，自我描述且易于解析。使得x m l 具有机器可读性，任何应 用均可按照各种方式解析、过滤、重构x m l 文档。 h t m l 中的标记是固定的，不能扩展，而x m l 的标记由用户定义，可 以任意地加以扩展。x m l 的嵌套结构可以表示现实世界中各种复杂的对象实体、 以及它们之间的关系，应用中各种格式的数据都可以比较容易地转化为x m l 数 据，这使得x m l 非常适于w e b 信息的发布、转换和集成。 h t m l 中的标记表示的是数据的显示格式，而不包括任何语义，而x m l 的标记则明确指出了数据的含义，描述的是数据本身，使 ；导细粒度的x m l 数据 处理、基于内容的x m l 检索成为可能。 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 ) 描述了文档中元素和子元素间的嵌套结构，不同的用 户可以通过x s l 按不同的显示方式显示全部或部分的x m l 文档内容。 在工业界，x m l 自发布以来受到了各界的广泛关注，各计算机厂商们竞相 第章前言 推出了支持x m l 的产品( 如：o r a c l e9 i 中的x m l s q l u t i l i t y ，i b m d b 2 中 的x m le x t e n d e r ，m i c r o s o f ts q ls e r v e r2 0 0 0 中的x m la n di n t e r n e t s u p p o r t 等) ；学术界和研究机构纷纷采用x m l 来表示各种科学数据，并展开了 对x m l 的深入研究。联合国正逐步加大制订全球性x m l 标准的力度，它的 u n e d i f a c t 与o a s i s 组织共同发展了e b x m l 。各个行业如金融机构、海关、 媒体产业正制订各自行业的x m l d t d ，以利于数据以公认的格式交换和集成。 w 3 c 在1 9 9 8 年制定了x m l 的标准，启动了整个i n t e m e t 环境下的信息标准化 进程，基于x m l x s l ( e x t e n s i b l es t y l el a n g u a g e ) 的嘲页、网站和应用开发t 具的 大量涌现，预示着互联网上的海量信息将会以x m l 文档的形式存在，同时，x m l 相关技术标准的制定大大促进了i n t e m e t w e b 的发展。当前，w e b 服务( w e b s e r v i c e s ) f y w z 0 4 迅速发展，成为了w e b 信息集成、企业应用集成、b 2 b 等电 子商务应用的新型解决方案和运作模式；x m l 解决了i n t e r n e t 上多个系统异构、 而又必须进行系统集成的矛盾，w e b 服务以x m l 为基石：在w e b 服务系统中， x m l 是w e b 服务的建模、描述、发现、发布、查找等基本操作的载体，也是相 关标准协议所采用的语言( 例如w s d l 、s o a p 等) 。w e b 服务的广泛应用必将 使x m l 的应用范围更加广泛和深入。 1 2x m l 与数据库技术 传统关系数据库存储的数据是高度结构化的数据，而现实世界中，一些数据 是完全没有结构的，如图像、视频数据流；而另外很多数据并非完全没有结构、 但是它们不具有固定的结构，如h t m l 构成的w e b 页、电子邮件、生物数据库 等。我们把这类数据称为半结构化数据( s e m i s t r u c t u r e dd a t e ) 【b u n 9 7 ，s u c 9 8 ， v i a 0 1 1 。与传统的结构化数据( 如关系数据库、对象数据库中的数据) 相比，其 主要特点是自描述性、结构的不固定性、内容和结构相分离。由于w e b 数据的 表示、集成和交换都需要利用半结构化数据，因此从数据库角度研究半结构化数 据的数据模型、模式、查询处理及优化、视图、完整性约束等成为近年来的数据 库界研究的热点问题，并且取得了很多可喜的成果。x m l 文档代表了一类重要 并且在4 i 断增长的半结构化数据源，它同半结构化数据 s u e 9 8 的性质有很多共 同之处，因此半结构化数据已有的理论( 如数据模型和查询) 、以及已有的半结 构化数据处理原型系统都可以作为x m l 研究的基础。但是x m l 与经典的半结 构化数据之间也有区别：x m l 的元素可以含有属性、x m l 文档的数据元素 ( e l e m e n t ) 具有顺序、元素之间通过i d 和i d r e f 属性进行引用、文档具有可 选的d t d 等。这些特性使x m l 区别于经典的半结构化数据，成为一种独特的 半结构化数据类型，大量x m l 文档的高效组织管理、x m l 数据的高效查询和 第一章前言 检索、分布式计算、w e b 信息集成等问题为我们带来了新的研究方向和课题，研 究适合w e b 数据管理和w e b 应用集成的中间件、w e b 信息发布中x m l 和其它 数据源之间的有效转换及数据发布技术，具有极其重要的理论价值和现实意义。 利用数据库系统，特别是关系数据库系统来处理x m l 数据的方式具有如 下的优点：一方面，当前的关系数据库技术已_ 卜分成熟，商用的关系数据库系统 都具有高性能的查询引擎、良好的可扩展性、安全性和健壮性：当前的关系数据 库管理系统能够对“对象”数据( 例如图像、文本) 进行存储和管理，此外，为 满足应用中数据的一致性及处理的高效性要求，关系数据库管理系统提供了事 务、存储过程、触发器等良好的机制。因此，利用关系数据库系统管理x - m l 数 据可以重用数据库的查询优化器和事务处理机制，能够保证x m l 数据的一致性 和完整性；另一方面，目前大量的w e b 数据主要存放在关系数据库中，x m l 一关 系系统便于在原有关系数据库上建立适于二者的应用，使关系数据库进入w e b 领域成为可能、使基于关系的系统能够与基于w e b 的系统进行无缝耦合。此外， x m l 文档可以具有文档类型定义d t d ，它是x m l 文档的词汇表和结构的定义， 各个组织或个人可以定义自己的d t d ，d t d 可以看作是用x m l 表示的w e b 数据 的模式，这有利于数据库技术应用于w c b 信息的检索和管理中。 1 3 研究现状 在x m l 引起的w e b 变革中数据库技术扮演着关键的角色。从数据处理的 角度来说，传统的w e b 信息处理主要采用的是信息检索技术，其主要方式是关 键字搜索，关键字搜索准确性不高，检索的结果将返回包含关键字的整个文档， 网络传输量大。如果在信息检索中使用x m l 作为信息存储的载体，那么我们便 可以采用现有的数据库技术来存储、检索、分析、加工和处理w e b 信息，即： 可以使用类似于数据库查询语言的方式来检索x m l 文档，搜索引擎的功 能将变得更加强大而准确。此外，查询结果将只返回与查询相匹配的部分而非整 个文档，大大降低了网络传输量，也提高了检索结果的准确性。 x m l 文档以数据为中心，可以方便地在其上进行基于内容的检索，关键 词的匹配比传统的方式更为简便、准确。 传统的w e b 信息管理处理的主要是静态的w e b 页面，利用现有数据库中 成熟的技术和各种辅助机制，可以保证w c b 页面动态更新时数据的一致性。 以x m l 作为w e b 信息的载体、利用数据库技术可以及时、有效地分析和 加工在线的x m l 数据，从中发现有用的知识，辅助企业决策。 随着i n t e m e t 和w e b 的迅速发展，转换和发布也成为了w e b 数据处理中的重 要组成部分这也是w e b 信息集成的主要内容之一。采用w e b 作为信息发布平 第一章前言 台的各个行业之间、或者行业内部需要通过w e b 交换数据，而各个不同的数据 源由于领域的不相同而具有不同的数据库模式，作为w e b 数据表示的标准，x m l 是各行业间数据交换的中间格式，因此将传统数据库中的数据发布为x m l 格式 是整个数据交换中的重要步骤。同理，x m l 到x m l 的转换是另一种重要的w e b 数据转换模式。 x m l 以数据为中心的特点使其很自然地成为一种数据的永久性存储格式， 类似于关系数据库，从数据库的角度看x m l ，x m l 文档中可存储高度结构化、 半结构化的数据。采用x m l 数据库，可以直接进行w e b 信息发布、标准化地完 成w e b 数据交换、高效地进行w e b 数据内容的检索。 x m l 与传统数据库中的结构化数据刁i 同，x m l 数据是自我描述的，没有预 先固定的模式。x m l 与数据库界近年来研究的半结构化数据极为相似。人们可 以将x m l 看作是半结构化数据的标准。并借鉴半结构化数据的研究成果来管理 x m l 数据。但是，目前半结构化数据的研究尚不成熟，并且x m l 与半结构化 数据相比又存在一些差别，这主要表现在：从数据特点上看，x m l 文档中的元 素有次序，x m l 文档可带有描述其结构的d t d ；从应用领域来说，x m l 不但 被用于表示w e b 数据，也面向电子数据交换，因此，需要对x m l 数据作进一步 深入的研究。在学术界，自x m l 标准发布以来，x m l 已经引起了数据库研究 者们极大的兴趣，成为近年来的s i g m o d 、v l d b 、i c d e 和p o d s 等国际数据 库项级会议的研究热点。 数据库界研究半结构化数据的目的在于扩展传统的数据库技术，以处理没有 预先固定的模式或模式经常变动的非结构化的数据；从x m l 数据处理的“内涵” 的角度，类似现有的数据库管理功能，研究x m l 数据上的查询、更新、索引技 术，研究x m l 数据本身的语义约束、数据约束与关联的推理系统，研究用成熟 数据库技术管理x m l 数据的新方法等：从“外延”的角度，研究基于x m l 的 应用中的数据发布、转换策略，研究以x m l 为信息载体、基于内容的检索策略， 研究基于w e b 服务的电子商务解决方案、系统集成技术等。 目前，数据库界在半结构化数据的研究方面已取得了一定的进展，包括数据 模型 p g w 9 5 ，查询语言 b f s 0 0 ，g w 9 7 ，半结构化数据模式 o w 9 7 ，查询和查 询优化技术 f l m + 9 9 ，h g i + 9 5 ，m w 9 9 a ，b d h + 9 6 ，索引技术 i v l w a + 9 8 ，m s 9 9 a ， 半结构化路径约束 b f w 9 8 ，a v 9 7 ，f a n 9 9 ，b d f + 0 1 】，半结构化中间件和视图机制 l y v + 9 8 ，m p q + 9 7 ，p v 9 9 】，半结构化模式抽取 a a c + 9 9 ，n a m 9 8 ，m s 9 9 b 】，半结 构化数据管理系统 q w g + 9 6 ，h g i + 9 5 ，m a g + 9 7 ，w e b 站点管理【f l s + 9 9 ， f y v + 0 0 ，f f k + 9 8 等。关于半结构化数据研究的综述参见 b u n 9 7 ，a b i 9 7 ，v i a 0 1 】。 国际上很多大学、研究机构和各种基金都已经或正在开展x m l 数据处理技 6 第一章前言 术的研究，其中，主要研究项目见下表。另外，i b m ，m i c r o s o r ，o r a c l e 等各大数 据库厂商的研究机构也都有对x m l 技术的专项研究( 未在下表中列出) 。 项目名称研究机构或院校研究重点 n i a g a r aw i s c o n s i nm a d i s o n 大学 x m l 的查询和搜索引擎 | m 1 x 加州大学s a nd i e g o 分校x m l 数据中间件 ( u c s d l x m ld a t am a n a g e m e n tw i s c o n s i nm a d i s o n 大学存储，管理x m l 数据 t u k w i l a w a s h i n g t o n 大学 基于x m l 的数据集成 x m l q l a t & t 实验室，i n r i a n 和x m l 查询语言 w a s h i n g t o n 大学 s i l k r o u t e p e n n s y l v a n i a 大学a t & t 实 x m l 信息发布 验室 x m i l l p e n n s y l v a n i a 大学a t & t x m l 数据压缩 实验室 x p e r a n t 0 w a s h i n g t o n 大学i b m 公司 x m l 信息发布 s e m i s t r u c t u r e dd a t a p e n n s y l v a n i a 大学 x m l 的查询语言，结构描述，约 x m l束机制和类型系统 c a r a v e l法国烈r i ax m l 数据的查询和存储技术 l o r es t a n f o r d 大学x m l 数据库管理系统 t j m m q p ：r a i n b o w w o r c e s t e r 理工大学x m l 和关系数据库 x m l - b a s e d德国国家信息技术研究中x m l 标准和x m l 结构，x m l i n f o r m a t i o ns y s t e m s ，5 , ( o m d ) 文档存储和查询，x m l 在电子 商务和数字图书馆中的应用 v e r s o法国i n i u ax m l 查询，x m l 主动视图 ( a c t i v ev i e w ) 及其在电子商务 中的应用 目前，在x m l 数据管理方面需要解决的前沿问题主要有： x m l 的查询语言和代数。目前提出的x m l 查询语言有l o r e a q m + 9 7 、 x m l q l f d f + 9 9 、x q l r l s 9 8 、x q u e r y b c f + 0 2 a 等。关于这些语言的比较 分析见 b c 0 0 。x m l 的形式化描述较为困难，目前仅有 f s w 0 0 对x m l 的查询 代数作了初步的探索。 x m l 数据的存储机制。x m l 的数据存储是处理x m l 数据的首要问题。 x m l 的主要存储方式为文件系统 t d c + 0 2 1 ，关系数据库 s k w + 0 0 ，z n d + 0 1 ， f k 9 9 ，s t z + 9 9 ，m f o + 0 0 ，面向对象数据库 k m 0 0 ，a c c + 9 7 和半结构化数据仓库 【g m w 9 9 等。 x m l 数据的查询和查询优化技术 f d f + 9 9 ，m w 9 9 b 】。x m l 数据查询优 化的研究包括：x m l 索引技术 m s 9 9 a 、优化正则路径表达式、基于约束的x m l 查询优化和在w e b 环境下的分布式查询优化等。 第一章前言 x m l 视图。在w e b 环境下，x m l 视图显得比传统数据库中的视图更加 重要 a b i 9 9 。多版本x m l 文档的管理，需要建立带有语义标注的x m l 视图 b k t + 0 2 。面向电子商务的应用，需要建立x m l 的主动视图 a a c + 9 9 。 x m l 数据交换和翻译 a c m 9 7 。在电子信息发布领域，需要将传统数据 或h t m l 文档转化为x m l 格式发布 s a 9 9 1 。w e b 数据交换需要将传统关系数据 中的数据符合目标d t d 地发布为x m l 文档 b c f + 0 2 b 。电子数据交换需要能够 自动地将符合一个d t d 规范的文档转化为符合另一个d t d 定义的x m l 文档的 t 具 m s v 0 0 ，z w g + 0 3 。 大规模x m l 文档的检索。在w e b 环境下，搜索大规模的x m l 文档需 要结合数据库和信息检索两方面的技术。大规模x m l 文档的检索技术将构成未 来x m l 搜索引擎的基础。w i s c o n s i nm a d i s o n 的研究者已开始了这方面的初步探 索 c d t + 0 0 ，i n r i a 的x y l e m e x y l 0 1 i 程也致力于同样的目标。基于x m l 文 档的信息检索也有一些研究成果 g s b + 0 3 。 基于x m l 的数据集成。x m l 使得通过统一的数据格式访问各种格式的 w e b 信息成为可能。在x m l 数据集成方面已有深入的研究 b g l + 9 9 ，f y v + 0 0 ， z l z + 0 1 1 ，在p 2 p 环境中处理x m l 数据方面也有一些研究成果 a b m + 0 2 】。 x m l 数据压缩。有效的x m l 数据压缩工具将有效地降低x m l 数据的 网络的传输量。在这方面，a t & t 和p e n n s y l v a n i a 大学已开发出了一个有效的 x m l 压缩工具x m i l l 【l s 0 0 1 。 x m l 的语义约束和规范化。一方面，有效的约束关系将更好地优化对 x m l 的各种处理。樊文飞博士开创并建立了x m l 完整性约束理论，在国际上 第一次提出了x m l 完整性约束理论及x m l 约束的推理体系，包括x m l 键和 外键 b d f + 0 1 ，提出了x m l 键的描述语言及其推理系统 d f h + 0 3 ，有效地将 关系数据库的规范化理论和不规则的x m l 数据和谐地结合在一起，为x m l 数 据的语义描述、存储、索引及更新奠定了基础，并提出了将x m l 键约束映射到 关系数据库上的相应算法。另一方面，规范化的x m l 文档将使x m l 表示的半 结构化数据较少冗余、在处理过程中避免异常，从而提高x m l 半结构化数据库 的数据管理能力和健壮性，这方面也已经取得了一些研究成果 a l 0 2 。 1 4 本文的研究目标和内容 根据以上的论述，本文的研究目标是；基于关系数据库和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 的) w e b 数据的原型系统，吸收有指导意义和有价值的研究成 果并使之与自身的独立研究和创新精神相结合。坚持“研究与实现并重”的原 则把我们的研究成果体现于原型系统的设计和实现中；同时，根据实现中遇到 的问题来指导我们的研究工作，使我们研究和开发出真正具有实用价值的技术。 具体而言，本文的贡献如下： 基于x m l 键约束的概念，提出了一种将x i v l 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 片段 为1 i 同的粒度，提出了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 文档 时，不但保持了x m l 文档本身的键约束，还使关系数据库和x m l 文档保持了 一致。利用如前所述的标注技术，快速定位更新位置，从而有效地实现了x m l 文档保持键约束的更新，该方法也可以作为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 文档所满足的d t d 进行无损分解， 利用x m l 转换技术t r e x 对待更新文档进行规范化，以及更新后x m l 文档用 户视图的转换。 1 5 论文结构 本文共分六章，第一章总体介绍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 r e x ，基于x m l 键语义约束、d t d 结 构约束和x m l 范式，讨论了直接在x m l 文档上进行x m l 数据保持约束的更 新策略。第六章为结束语，总结本文的工作，得出结论，并展望未来的研究方向。 9 第二章x m l 文档的规范化存储 第二章x m l 文档的规范化存储 2 1 引言 在p e t e rb u n e m a n 等提出x m l 键 b d f + o i 的概念之前，因为缺乏对x m l 文档约束关系的描述，大多数存储方法都只保存了x m l 文档的结构和内容而忽 略了其语义约束的保持，都没有实现x m l 文档的规范化关系存储。在x m l 键 出现之前，存储x m l 数据的方法可以分为两类：基于结构的映射和基于模式的 映射 y a s + 0 1 。前一种方法是从x m l 结构中导出关系模式，例如d e u t s c h 等提 出的用数据挖掘的方法从x m l 文档中抽取出关系模式f d f s 9 9 ： s h a n m u g a s u n d a r a m 等提出的将x m l 文档的d t d 映射为关系模式的结构映射方 法 s t z + 9 9 ；后一种是用固定的关系模式存储所有的x m l 文档，如f l o r e s c u 等 提出的简单映射方法，即根据x m l 文档的d o m ( d o c u m e n to b j e c tm o d e l ) 模 型，将d o m 模型中节点与边的关系映射为关系模式 f k 9 9 。 l e e 等提出的c p i 算法虽然考虑了d t d 中的语义约束，实现了x m l 文档保 持d t d 语义约束的关系存储 l c 0 1 1 ，但d t d 主要表示了x m l 文档结构上的约 束，而对语义约束的表示却很有限。键约束是数据库设计的重要方面，它能够无 歧义地标识数据块，并且基于键约束可以导出数据间的依赖关系，以表示并检测 数据的完整性和一致性，从而为避免数据存储的冗余和操作的异常提供了理论依 据。类似于关系数据的键约束，对于x m l ，x m l 键是x m l 文档上一类很重要 的语义约束。 基于x m l 的层次结构及半结构化特征，b u n e m a n 等提出了x m l 键的概念 b d f