（计算机软件与理论专业论文）关系数据的xml发布及其优化技术.pdf

摘要 当今数据在存储格式以及传输格式中出现了矛盾，一方面数据在本地以关系 数据的格式存储在数据库中，另一方面数据咀x m l 格式在网络中传输。为了解 决数据交换与数据共享中的这个难题，需要进行数据格式的转换；本文主要关注 关系数据转换为x m l 数据，称之为“发布问题”。目前关于发布问题已经有了 很多研究成果，这些研究成果已经基本能够满足用户的发布请求，但是关注的是 一次的用户发布请求的解决。当今越来越多的用户发布应用需求，迫切的需要有 效率的解决大量的用户发布请求的问题。为此我们将缓存技术引入发布问题，优 化关系数据的x m l 发布，即尽量使用已经获得的计算结果避免冗余的计算转换。 本文基于已有的p r a t a 发布系统提出了系统框架，以及获得和使用缓存的相应 算法；由于缓存的内容会随着用户的发布请求而变化，所以本文提出增量维护算 法更新缓存的内容。具体说，本文的主要贡献如下： 1 详细分析将关系数据发布x m l 文档的研究成果，从中发现不足之处为： 现有发布问题的解决方案中针对独立用户的发布请求，发布代价很高。为 降低发布代价，我们将缓存引入关系数据的x m l 发布问题中。 2 提出了利用缓存优化关系数据的x m l 发布的系统框架，定义了四个新的 概念并且应用于本文提出的算法：挖掘稳定用户发布模式集的算法f p t 和有效利用缓存的匹配算法t r e e m a t c h i n g 。 3 提出了解决频繁发布模式集增量维护的方法。用户发布模式集只能在某个 时刻是稳定的，如果每次都是重新挖掘频繁模式集就丧失了优化的目的。 增量维护的算法f p t - u p d a t e 能够以较小的代价更新频繁发布模式集。 通过实验，我们得到以下结论：首先采用缓存技术优化关系数据的x m l 发 布是行之有效的方法；第二本文提出的挖掘稳定用户发布模式集的算法f p t 以 及做增量维护的算法f p t - u p d a t e 能够有效的实现缓存的初始获得以及动态更 新。 关键字x m lx m l 文档发布频繁发布根子树增量维护 中图分类号t p 3 1 l 4 a b s t r a c t a b s t r a c t n o w a d a y st h e r ea p p e a r sac o n f l i c tb e t w e e nt h ef o r m a to fd a t as t o r e da n dt h a to f d a t at r a n s f e r r e d o nt h eo n eh a n d ，d a t ai ss t o r e di nr e l a t i o n a ld a t a b a s ei nl o c a lh o s t ；o n t h eo t h e rh a n dd a t ai st r a n s f e f r e di nx m lo nt h ew e b i no r d e rt os o l v et h i sc o n f l i c t p r o b l e mi nd a t ae x c h a n g ea n dd a t as h a r e ，i ti si n e v i t a b l et od of o r m a tt r a n s f o r m a t i o n m a i n l yw ef o c u so nt r a n s f o r m a t i o nf r o mr e l a t i o n a ld a t at ox m l ，w h i c hi sc a l l e da s p u b l i s h i n g t h e r eh a v eb e e nm a n ya c h i e v e m e n t si np u b l i s h i n g ，w h i c hc a ns a t i s f y c u s t o m e r s p u b l i s h i n gr e q u e s t s ，b u tt h e yf o c u so no n ep u b l i s h i n gr e q u e s t i ti sm o r e a n dm o r ec u s t o m e r s p u b l i s h i n gr e q u e s t st h a td e m a n de f f i c i e n ts o l u t i o no fal a r g e q u a n t i t yo fp u b l i s h i n gr e q u e s t s h e n c ew ei m p o r tc a c h i n gi n t op u b l i s h i n gt oo p t i m i z e p u b l i s h i n gp r o c e s st h r o u g hr e d u c i n gr e p e t i t i v ec o m p u t a t i o nw i t he x i s t i n gc o m p u t i n g r e s u l t s b a s i n go np r a t a w ef i g u r eo u tt h ef r a m e w o r ko fo p t i m i z e dp u b l i s h i n g ，a n d w eb r i n gf o r w a r dr e l a t e da l g o r i t h m s ，w h i c ha r eu s e dt og e tc a c h ea n du t i l i z ei t s i n c e c a h c ec o n t e n ti st ou p d a t ea c c o r d i n gt oc u s t o m e r s p u b l i s h i n gr e q u e s t s ，w ea d v a n c e i n c r e m e n t a lm a i n t a l n e n c ea l g o r i t h mt ou p d a t ec a c h e t o t a l l y , t h ec o n t r i b u t i o n so ft h i s d i s s e r t a t i o nc a l lb es u m m a r i z e da sf o l l o w i n g ： 1 s t u d ya n da n a l y z et h ea c h i e v e m e n to fp u b l i s h i n ga n dt h e nf i n dd i s a d v a n t a g eo f t h e m ，w h i c hi st h a tp u b l i s h i n gi sd o n ef o ri n d i v i d u a lc u s t o m e ra n dt h e nh i 曲 p u b l i s h i n gc o s ti sl e d w ei m p o r tc a c h i n gi n t op u b l i s h i n gt or e d u c ep u b l i s h i n g c o s ta n da c h i e v em o r ee f f e c t i v ep u b i s h i n g 2 b r i n gf o r w a r do p t i m i z e dp u b l i s h i n gs y s t e mf r a m e w o r ka n dd e f i n es e v e r a lw o r d s a p p l i e di n t oo u ra l g o r i t h m s s o l v i n gs t a t i cu s e r s p u b l i s h i n gr e q u e s t s ，a l g o r i t h m f p ti su s e dt og e tc a c h ea n da l g o r i t h mt r e e m a t c h i n gi st ou s ec a c h e 3 a d v a n c ea l g o r i t h m st ou p d a t eu s e r s p u b l i s h i n gr e q u e s t s t h es e to fu s e r s r e q u e s t sa r eo n l ys t a t i c a tc e r t a i nm o m e n ta n dw es h o u l du p d a t ei to f t e n i fw e c a l c u l a t ef r e q u e n ts e tf r o mt h ev e r yb e g i n n i n ge v e r yt i m et h ec o s ti sh i g h a l g o r i t h mf p t - u p d a t e i su s e dt ou p d a t ep u b l i s h i n gs e tw i t hl o w e rc o s t e x p e r i m e n t si l l u s t r a t et 1 1 ef o l l o w i n gr e s n l t s o nt h eo n eh a n di ti se f f e c t i v et o i m p o r tc a c h i n gi n t op u b l i s h i n g o nt h eo t h e rh a n dt h ea l g o r i t h m sw ea d v a n c e d ，f p t a n df p t - u p d a t e ，a r ea b l et og e ti n i t i a lc a c h ea n di n c r e m e n t a lc a c h ee f f e c t i v e l y k e y w o r d ：x m lx m l p u b l i s h i n g f p r s tx m l u p d a t i n g c h i n e s el i b r a r yc l a s s i f i c a t i o n ：t p 311 5 第一章绪论 1 1 研究背景 第一章绪论 数据库技术诞生于上个世纪6 0 年代，在经历了层次数据库、网状数据库、 关系数据库的发展、面向对象数据库的发展之后，技术e t 益成熟并且得到了广泛 的应用，目前已经成为计算机系统中的重要支柱。对数据库技术的研究在查询优 化、数据仓库与数据挖掘、移动数据库方面发展同臻完善，并取得了丰硕的研究 成果，工业界业已将研究成果成功的转化为了产品。但是近年来随着网络的出现 与发展，人们越来越多的需要使用全球最大的网络i n t c m e t 来获得数据信息， 共享数据信息，以及交换数据信息。这为传统的数据库研究带来了新的挑战与机 遇。 i n t e m e t 中w e b 充当了重要的角色，w e b 中包含了海量的数据，绝大部分的 情况下还是使用静态h t m l ( h y p e r - t e x tm a r k u pl 锄g u a g e ，超文本标记语言) 页面提供数据和信息。i n t e m e t 的飞速发展使得信息量迅速以指数级增长膨胀， 信息的数量级从9 0 年代初的m b 过渡到g b 、现在已上升到t b ，同时每天以1 0 0 万的速度增加【c h a 9 9 】。面对庞大的信息海洋，人们却遇到了w e b 上的两大问 题：一是i n t e m e t 速度极慢：二是信息泛滥，即需要精确的找到所需要的信息很 困难。分析这种情况产生的原因，是由于h t m l 的过于简单的性质缺陷引起的。 h t 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 pl a n g u a g e ) 【u r l d 的一个具体应 用实例，h t m l 是面向表示的，只能反映显示出来的一小部分结构信息：h t m l 的标签是有限的，只是s g m l 的很小的一个子集，并且标签都是固定的不能扩 展；h t m l 不能提供关于整个文档内容、结构的信息，也就是说如果要进行查询， 需要扫描整个文档才能获得，并且结果信息的精确度不高。为此w 3 c 组织( 全 球互联网联盟) 在1 9 9 8 年提出了可扩展标记语言x m l b p s + 9 8 ( e x t e n s i b l e m a r k u pl a n g u a g e ，简称x m l ) ，给出了其正式的x m l l 0 版本，并且正式推荐 x m l 成为下一代互联网标准；x m l 的出现提供了直接处理w e b 数据的有效方 式。x m l 与s g m l 相比：x m l 是s g m l 的最小完备子集，继承了s g m l 的强 大功能并摒除了繁琐的的定义；s g m l 过于庞大复杂，在w e b 中很难于实现， x m l 的实现相对简单些。x m l 与h t m l 相比，优点如下： 1 x m l 具有自我描述性从而易于解析，不仅使得机器可读。而且对人而言， 也可读。较之h t m l 只表示数据显示格式，仅对人可读的情况，x m l 更 加易于机器处理；一个应用可以按照多种方式解析、过滤和重构x m l 文 档。 b 第一章绪论 2 x m l 具有可扩展性。x m l 是可扩展标记语言，其标记可以由用户自由定 义，任意扩展；并且x m l 支持嵌套结构，可以有效的表示现实世界中的 复杂对象，比如商品有商品名和商品价格，而价格又有基本价格和商品税 收和运输价格之分。所以x m l 更加适用于现今的w e b 信息发布与集成。 3 x m l 标记具有语义。x m l 的标记可以由用户按照需求自由定义，人和机 均可读，即x m l 的标记是有语义的；而h t m l 的标记只表示数据的显示。 因此x m l 更适合细粒度的数据处理。 4 x m l 把结构、内容和表现分离开来。文档类型定义d t d b p s + 9 8 】( 或 x m l s c h e m a s c h 0 1 ) 描述了x m l 的层次结构，描述了文档中元素与子 元素之间的嵌套结构：实际文档存储x m l 的内容信息；样式表 x s l a b c + 0 1 c l a 9 9 1 按不同的方式显示全部或者部分的x m l 文档，不同 的用户可以通过采用不同的x s l 实现不同的x m l 文档显示。 x m l 自发布以来受到了各界的广泛关注。各计算机厂商们竞相推出了支持 x m l 的产品( 如：o r a c l e9 i 中的x m ls q lu t i l i t y ，i b md b 2 中的x m l e 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 ts 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 lf u r l f 。各个行业如金融机构、海关、媒体 产业正制订各自行业的x m ld t d 【b p s + 9 8 】( d o c u m e n tt y p ed e f i n i t i o n ，文档类 型定义) ，以利于数据以公认的格式交换和集成。比如金融服务行业建立了多种 标准x m l 格式以满足自身专门需要：金融产品标记语言是一种基于x m l 的交换格 式，用于金融衍生市场事务，通常用于错综复杂的协商。在学术界，相应类似的 x m l 应用也十分广泛：在生物和医学领域，基因蛋白质数据g e n eb a n k 和s w i s s p o r t 、生物医学数据g e n e x 等等都是以x m l 的形式存放：在化学领域，化学标 记语言c m l u r l g 可以描述分子与晶体结构、化合物的光谱结构；在数学领域， 数学标记语言m a t hm l i m 9 9 可以帮助数学家们将数学公式精确地显示在浏览 器上。 目前，i n t e m e t 上已经涌现了大量的l 页面、站点和应用开发工具。可以 预见，x m l 将成为w e b 信息发布和交换的事实上的标准。国外己形成了x m l 的一系列标准，如c x m l 【u r l e ，u r l g 】、x c b l 、b i z t a l k 、e b x m l 【u r l f 】。 在我国，中国科学院电子商务研究中心也正联合国内软件厂商制定c n x m l 标准。 总之，对x m l 的深入研究将有力促进企业的信息化和电子商务，具有巨大的应 用前景和经济效益。 x m l 的出现引起了w e b 的巨大变革，其中数据库技术将是关键中的关键。 第一章绪论 从数据处理的角度来说，传统的w e b 信息处理主要采用的是信息检索技术，搜 索引擎的主要方式是关键字搜索。关键字搜索有很大的局限性，搜索的结果将返 回包含关键字的整个文档，网络传输量大。x m l 使得我们可以采用数据库技术 来存储、搜索查询、更新、并优化处理w e b 信息。首先，可以使用类似于数据 库的查询语言的方式来检索x m l 文档，搜索引擎的功能将变的更加强大而准确， 查询结果将只返回与查询匹配的部分而非整个文档，大大降低了网络传输量。其 次，传统的w e b 信息管理主要处理的是静态的w e b 页面，而利用保持数据一致 性的x m l 文档更新技术可以保证动态更新的w e b 页面。最后，由于x m l 文档 的大量使用并且成为标准，原有的存储在关系数据库中的数据需要发布成x m l 文档，这是实现从传统的关系数据库过渡到更加高效的x m l 的一个关键步骤。 近几年，关于x m l 的研究已经成为s i g m o d p o d s 、v l d b 、i c d e 等国内外数 据库界顶级会议的研究热点之一，几乎每个会议都有大量关于x m l 的论文报告 会和专题讨论。 1 2 研究现状 由于x m l 与半结构化数据的相似性，人们可以将x m l 看作是半结构化数 据的标准，并借鉴半结构化数据的研究成果来管理x v l l 数据。目前，数据库界 在半结构化数据的研究方面已取得了一定的进展。这包括数据模型 p g w 9 5 1 ，查 询语言 b f s 0 0 ，g w 9 7 1 ，半结构化的模式 0 w 9 7 】，查询和查询优化技术e f m l 9 9 ， h g i + 9 5 ，m w 9 9 ，b d h + 9 6 ，索引技术 m w a + 9 8 ，m s 9 9 a ，半结构化路径约束 【b f w 9 8 ，a v 9 7 ，f a n 9 9 ，半结构化中间件和视图机带i j l y v + 9 8 ，m p q + 9 7 ，p v 9 9 1 ， 半结构化模式抽取 a a c + 9 9 ，n a m 9 8 ，m s 9 9 1 ，半结构化数据管理系统 q w g + 9 6 ， h g i + 9 5 ，m a g + 9 7 ，w e b 站点管理f f y l + 9 9 ，f y v + 0 0 ，f f k + 9 8 等。关于半结构 化数据研究的综述见 b u n 9 7 ，a b i 9 7 1 。 但是，目前的半结构化数据的研究尚不成熟，并且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 数据管理的主要研究项目如图1 1 所 示。另外，i b m ，m i c r o s o f t ，o r a c l e 等各大数据库厂商的研究机构也都有对x m l 技术的专项研究( 未在图1 1 中列出) 第一章绪论 项目名称研究机构或院校 研究熏点 n i a g a r a w i s c o n s i nm a d i s o n 大学 x m l 的查询和搜索引擎 m i x 加州大学s a nd i e g o 分梭 x m l 数据中间件 ( u c s d ) x m l d a t a m a n a g e m e n t w 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 的数据集成 a t & t 实验室，i n r i a n 和 x m l - q l x m l 查询语言 w a s h i n g t o n 大学 p e n n s y l v a n i a 人学a t & t s i l k r o u t ex m l 信息发布 实验室 p e n n s y l v a n i a 大学a t & t x m i l l x m l 数据压缩 实验室 x p e r a n t o w a s h i n g t o n 大学i b m 公 x m l 信息发布 司 s e m i s t m c t u r e dd a t a x m l 的查询语言结构描述，约束机制 x m l p e n n s y l v a n i a 大学 和类型系统 c a l r a v e i 法国1 n r i ax m l 数据的查询和存储技术 l o l g s t a n f o r d 大学x m l 数据库管理系统 x m l b a s e di n f o 帅a t i o n德国国家信息技术研究中 x m l 标准和x m l 结构，x m l 文档存储 和查询，x m l 带电子商务和数字图书馆 s y s t e m s，i 二, ( g m d ) 中的应用 x m l 查l 嘟，x m l 主动视图( a c t i v e v i e w ) v e r s o法国i n r j a 及其在电了商务中的应用 复旦大学w e b d b p 2 p 实验 p r a mx n i l 信息发布 室，贝尔实验室 韩国k a i s t 电子工程与计 x p r e s sx m l 数据压缩 算机系 x g r l n d印度科学研究院x m l 数据压缩 图1 1x m l 数据管理的研究项目 一方面x m l 已经逐渐成为网络中数据传输的标准格式；另一方面由于关系 数据的稳定性及良好性能，大部分的数据都存储在关系数据库中。为了解决数据 存储格式以及传输格式的矛盾，必需研究关系数据转换为x m l 格式的问题。在 a b s 9 9 】中研究了从关系数据到半结构化数据以及x m l 数据的转换，很多相关 工作也都讨论到了这个研究背景：从图1 1 可以看出对x m l 格式转换方面的研 究即是发布问题的研究还是比较受关注的：p r a t af b c f + 0 2 b 】，s i l k r o u t e 【f m s + 0 1 ，f t s 0 0 】，x p e r a n t o 【c f i + 0 0 a ，c f i + 0 0 b 】。此外在网络中传输大规 模的x m l 文档会对带宽的压力，为此将x m l 压缩成为x m l 流的方式在网络 中传输，可以更有效的使用网络带宽，例如图1 1 中的x m i l lf l s o o ，x p r e s s m p c 0 3 】，x g r i n d t h 0 2 】：在 g m o + 0 3 】中分析研究了流上的查询计算。 9 第一章绪论 1 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 发布问题。 1 3 1将关系数据发布为x m l 文档 将关系数据发布为x m l 文档的基本步骤包含两个主要部分：第一个步骤是 根据用户的发布请求获得s q l 语句，查询本地数据库获得关系数据结果；第二 个步骤是将结果按照一定的规则结构化并加标签转换为x m l 文档。早在2 0 0 0 年 s s b + 0 0 】就提出了将关系数据发布为x m l 的几种解决方案。在第一个步骤 中的s q l 查询可以是一个或多个；第二个步骤中结构化和加标签可以同时执行， 也可以分先后执行：操作可以在关系机内部执行，也可以在关系机外部执行。根 据以上几种情况得出结论，对于发布问题可以有多种可以选择的解决方案：或者 先加标记，先结构化：后加标记，后结构化；后加标记，先结构化。并且执行的 操作数量在关系机内部执行又是可变的。 学术界对发布问题的研究较为关注，目前已经开发出了较为成熟的系统满足 用户的发布请求。a t & t 曾经丌发过一个系统s i l k r o u t ef f m s + 0 1 ，f t s 0 0 用于 关系数据的x m l 发布，在该系统中使用一种视图定义语言r x l ( r e l a t i o n a lt o x m l t r a n s f o r m a t i o nl a n g u a g e ) 来描述x m l 视图。r x l 是一种功能强大的声明 性语言，用于从关系数据到x m l 数据的发布。i b m 也曾开发了一个用于x m l 发布的系统x p e r a n t o 【c f i + 0 0 a ，c f i + 0 0 b 】。比起s i l k r o u t e 来说，x p e r a n t o 强调完全的x m l 哲学，即只要求用户熟悉x m l 和x m l 查询语言就行，而不 需要知道s q l 或者是学习r x l 。而且x p e r a n t o 不仅可以把关系数据发布成 x m l 数据，而且还可以发布“对象一关系”数据。除了上面介绍的两个系统外， 其实还有许多商用数据库产品都提供了从数据库到x m l 数据发布的功能 r y s 0 1 ，u r l b ，u r l c ，比如i b md b 2x m le x t e n d e r 、o r a c l e9 if u r l c 和 m i c r o s o f ts q ls e r v e r2 0 0 0 r y s 0 1 1 。以m i c r o s o f ts q ls e r v e r2 0 0 0 为例，它里面就 第一章绪论 提供三种发布x m l 数据的模式，分别为：原始模式( r a w m o d e ) 、自动模式( a u t o m o d e ) 和显式模式( e x p l i c i tm o d e ) 。 由复旦大学w e b d b & p 2 p 实验室和贝尔实验室联合丌发的p r a t a f b c f + 0 2 b 系统中，为了高效地执行a i g 以便快速地把关系数据发布成x m l 数据，也提 出了两种主要的优化办法。这两种方法与上面所讲的优化方案都不相同，分别为 分区( p a r t i t i o n i n g ) 和物化( m a t e r i a l i z a t i o n ) 。a t g 为“属性转换文法”，是一种 有效的将关系数据映射为x m l 的文法。用户只要熟悉a t g 的简单语法就可以 将关系数据发布为x m l 文档。 1 3 2利用缓存优化发布问题 目前的发布系统虽然已经能够基本较好的满足用户的发却请求，但是经过仔 细研究发现：现有的发布系统，无论是s i l k _ r o u t e f m s + 0 1 ，f t s 0 0 、x p e r a n t o f c f i + 0 0 a ，c f i + 0 0 b ，还是本文研究的基础系统p r a t a b c f + 0 2 b ，都是针对满 足一次的用户发布请求实现，并且只关注如何满足用户的发布请求。在越来越频 繁的信息共享以及信息集成的今天，信息发布的需求呈指数增长，如果j 是考虑 如何满足单个用户的请求实现发布过程，就会难以应付日益增长的发布请求。只 考虑一次发布请求实现的发布代价很高，响应时间长：从用户的满意程度来看， 对响应时间有较高的要求，因此发布代价也是荚系数据发布系统中的一个重要因 素。面对纷繁复杂的发布淆求，如何优化发布系统成为发布问题研究的一个不容 忽视的实际问题。 分析发布步骤；在发布过程的第一部分是获得关系数据，检索* 系数据库执 行s q l 语蟊j 申最为耗费时闻l 操作就是表的连接掇作。在以 ：芏的研究和应耀巾， 缓存技术被广泛地应用于融往的数据库访问过程中，能显著提高数据获取的速 度。 为此我们提出利用缓存技术优化发布过程：即降低表连接操作的次数，从而 加遮发布过程、优化现有的发布系统。利其j 缓存优化发布| j j ：j 题，需要解决的问题 包括缓存哪些内容、如何确定缓存内容、如何利用缓存内容、采用的方法是否有 效等等。针对需要解决的问题，我们提出了基于缓存的发布系统框架，并且给出 了挖掘算法获得需要缓存的内容，匹配算法确定如何利用缓存内窖加速教布过 程。通过实验证明，来用缓存优化关系数据的x m l 发靠是较为有效率的，我们 提出的挖掘算法也是有效聚的。 1 3 。3发存翘题翡增量维护 我们利用缓存优化发布问题，荧键在于利用了缓存的数据降低了执行新的用 户发毒请求黠获得绣集酌时溺。我 】提出弱方法可以寿效浆从一个稳定的发布模 第一章绪论 式库中获得频繁集进而加速发布请求的响应。但是发布请求的变化是时刻都在发 生的，一段时间之后原来对加速发布请求有用的频繁结果也可能成为不频繁的并 且对优化发布问题不再有帮助。随着新的发布请求的不断出现，可能会出现新的 频繁发布模式，进而需要缓存新的频繁结果以加速发布过程。因此我们所缓存的 内容就需要随之做相应的调整：原来频繁的结果在更新后可能频繁也可能不频 繁，一些原来不频繁的内容也可能变为频繁。我们称这类频繁结果集要随着发布 模式集的变化而做相应变化的问题为“增量维护”。 基于所提出的利用缓存优化发布问题的系统框架以及方法，我们提出了如何 对频繁集合做增量维护。增量维护所需要解决的问题是，采用何种方法对频繁集 进行增量维护，采用的方法是否有效率等等。针对这些问题，我们提出了增量维 护的算法，并且通过实验证明采用的增量维护的算法是行之有效的。 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 发布问题。 第三章详细阐述将关系数据发布为x m l 文档的研究成果。 1 ) 首先是给出“发布”问题的应用背景：由于数据存储格式与传输格式的 矛盾，格式间的转换势在必行。一方面由于x m l 已经越来越成为网络 中数据传输的标准格式；另一方面由于关系数据库的良好处理性能以及 稳定性，大部分的数据都是以关系数据的格式存储在数据库中。所以在 进行信息交换与信息集成过程中，数据提供方需要将关系数据转换为数 据请求方要求的x m l 文档，而数据请求方又需要将接收到的x m l 文档 转换为关系数据并且存储在本地数据库中。但是由于接收到的x m l 数 据可能不需要存储到本地数据库中，所以对前者即将关系数据转换为 x m l 数据的研究比较关注。 2 ) 然后介绍了将关系数据转换为x m l 文档的一般方法的研究成果。将关 系数据发布为x m l 文档包括两个部分的内容：数据获得以及格式转换。 即首先要检索查询关系数据获得结果，然后按照一定的转换规则为结果 第一章绪论 增加标签转换为x m l 格式。具体的步骤包括获褥结果、结构化以及加 标记三个部分。仔细分析比较三种可行的发布方法，得出结论：相对于 在关系机外，在关系机内建立x m l 文档更加有效搴；当主存足够即查 询处理等操作可以在主存中完成时，采用“无序外连接”效率更高：否 则当主存不足，采用“有序外连接”更有效率。 3 ) 本章的第三部分介绍了三个成熟的x m l 发布系统：a t & t 实验室开发的 数据发布的系统s i l k r o u t e 、由i b ma l m a d e n 研究中心开发的用于关系数 据到x m l 格式的发布系统x p e r a n t o 、以及由复旦大学w e b d b & p 2 p 实验室与贝尔实验室联会开发的p r a t a 系统，并且详细阐述了系统的结 构以及特点。本节还介绍了在p r a t a 系统x m l 视图的增量计算问题。 第四章分毒斤现有的关于发布问题的解决方案的不足之处，考虑优化发布问 题。本章共有三个方面的贡献： 1 ) 经过分析我们得出在发布问题中耗费时间较多的主要是在获得关系操作 时执行的表连接的s q l 操作，所以提出利用缓存技术优化发布问题的方 法，基于p r a t a 系统的结构提出了利用缓存优化之后的系统框架。即挖 掘用户的发布请求模式集获得频繁的发布请求，缓存发布用到的关系数据 结果从而减少执行新的用户发布请求时表连接的时间，达到提高执行发前i 请求的效率。 2 ) 本文提出了四个新的概念并且应用于本章提出的两个主要算法。我们将用 户发布请求a t g 分为两个部分考虑，一是发布模式树，一是发布模式树 对应s q l 语句。我们提出了挖掘频繁发布请求的算法f p t ，用来挖掘用 户发布模式树的集合；根据获得的频繁发布模式获得对应s q l 语句，检 索数据库并执行获得关系数据作为频繁结果集存储在本地以减少表连接 的次数。 我们提出了匹配算法t r e e m a t c h i n g 用来有效的获得相关的发布 模式及其对应的关系数据。 3 ) 通过实验证明：采用缓存优化关系数据的x m l 发布闻题是切实有效的： 我们提出的挖掘算法相对于一般的挖掘算法效果明显，尤其是当关系数据 库的x m l 视图的扇出比较大以及发布模式集规模大的时候更为明显。 第五章在第四章的基础上进一步考虑增量维护的问题。 1 ) 由予在第四章中我们提出的方法针对一稀稳定的情况，即挖掘一个稳定的 发布请求集合获得频繁发布模式集以及频繁结果集；但是由于发布请求时 刻都在更新，所以需要对频繁模式集以及频繁结果集傲增量的维护。为此 我们提出了增量维护的挖掘算法f p t - u p d a t e 用来更新频繁发布模式集 及频繁结果集。 第一章绪论 2 ) 经过实验证明：采用f p t - u p d a t e 增量维护频繁发布模式集相对于直接 使用f p t 算法挖掘定期挖掘用户发布模式集的效果好，尤其是当关系数 据库的x m l 视图的扇出比较大以及发布模式集规模大的时候更为明显。 第六章对所做的工作提出了总结，并且结合目前的工作展望未来的工作。 1 4 第二章x m l 基础知识殷相关技术 第二章x m l 基础知识及相关技术 在本章我们将介绍关于x m l 的基础概念，是后面几章的理论基础。 2 1x m l 基础概念 由于h t m l 的缺点，人们开始研究能改进或替代h t m l 的w e b 语言，在 1 9 9 8 年2 月，万维网相关技术的主要设计组织w 3 c ( 全球互联网联盟) 正式推 出了可扩展标记语言x m l ( e x t e n s i b l em a r k u pl a n g u a g e ) 1 0 b p s + 9 8 版本。 2 1 1x m l 文档 一个x m l 文档由嵌套的元素层次结构构成。每个文档有一个唯一的根节 点。一个元素有一个标记( t a g ) 。描述该元素的含义。一个元素由从起始标记到 终止标记的区域构成。该区域可以是嵌套的子元素，也可以是属性或文本串值。 图2 1 是一个常见的x m l 文档示例： 图2 1x m l 文档示例 第二章x m l 基础知识及相关技术 上图中的x m l 文档是独立文档，“s t a n d a l o n e = y e s ”就说明了文档自我包容 不需要其他的数据。只有一个根元素为p r o j e c t 元素，整个根元素包含三个子元 素：p r o n a m e 以及两个异构m e m b e r 子元素。一个元素可以有多个标记相同的子 元素，且标记相同的子元素可能具有不同的结构。上图中两个m e m b e r 子元素中 又包含子元素：例如第一个m e m b e r 包含n a l t l e 、e m a i l 和p u b l i c a t i o n 三个子元素， 第二个m e m b e r 包含n a m e 、p r o j e c t 和p u b l i c a t i o n 三个子元素。一个元素也可以 是原予元素，如p r o n a m e 子元素下面就是文本信息了。元素之间的包含关系就构 成了x m l 的层次结构。 格式正规的x m l 又称为“良构的) a l ”。所有符合基本x m l1 0 语法规范的数据对象( 文 档) 都叫格式正规的x m l 数据。一个格式正规的x m l 文档包含了恰当地互相 嵌套的一个或多个元素( 由开始和结束标记确定) 。文档元素包含了文档中的所 有其他任何元素，由于这种包含关系确定了嵌套的关系，因此所有的元素组成了 一棵层次树，这棵层次树只有一个根节点。元素之间唯一的直接关系是父子关系， 兄弟关系可以由x m l 应用程序的内部数据结构推理得到。格式正规的x m l 数 据符合x m l 语法规范，但是它不包含对外部资源的引用，一个良构x m l 文档 可以没有d t d 定义。总结格式正规的x m l 应该满足以下四个要求 b 0 2 1 ； 1 ) 结束标记匹配相应的起始标记 2 ) 语法符合x m l 规范 3 ) 元素构成一个层次树，只有一个根节点 4 ) 没有对外部实体的引用 有效的x m l 任何x m l 数据对象，如果它是格式正规的，符合一定的进一步有效性约束， 并且与描述文档内容的文档数据类型( d t d ) 的语法匹配，那么它就可以被视为 “有效的x m l 文档”。使用d t d 进行有效性验证可以确保：服从元素的父子关 系，属性具有有效值，所有引用的实体都被有效性约束。d t d 可以是预先定义 的，在创建和操纵整个有效型x m l 文档过程中都必须符合该d t d 。这样做的好 处在于，文档d t d 可以按照不同领域来划分和制定，各个领域有自身的一组标 准的d t d 来规范其领域内所有的x m l 文档。 x m l 解析器 除了指定x m l 的语法，w 3 c 还描述了x m l 客户端体系结构中低层次的一 些行为。定义了两种行为级别的解析器：“非验证的”和“验证的”。其中“非验 证的”确保数据是格式正规的x m l ，但不需要解析任何外部资源；“验证的”确 1 6 第二章x m l 基础知识及相关技术 保数据的格式正规和使用d t d 的有效性验证，并且必需解析外部资源。一些解 析器同时支持两种方式。 解析器有两种不同的实现方法：“事件驱动的解析器”和“基于树的解析器”。 “事件驱动的解析器”顺序的处理x m l 数据，每次处理一个部分，x m l 解析 器为x m l 数据的每个部分执行回调，x m l 解析器在解析之后并不维护元素的 树形结构；所有主要的事件驱动解析器都支持标准的a p i ，称为s a x ( s i m p l e a p i f o rx m l ) 。所有格式正规的x m l 都能定义一棵树，使用这种方法的解析器都遵 守文档对象模型d o m ( d o c u m e n to b j e c tm o d e l ) 【a p p + 9 8 ，w 0 0 9 8 】；d o m 独 立于平台、语言的接口，允许对树结构的文档进行操作。 2 1 2x m l 文档类型定义d t