（计算机系统结构专业论文）信息网格中关系模式变更管理.pdf

摘要 本文研究的问题是信息网格中关系模式变更问题：信息网格中大量的应用需要集成 分布自主的具有主、外键约束的基于关系模型的物理数据库信息资源，当这些物理信息 资源的关系模式自主变更时，在不修改应用的前提下，当前用户将得不到f 确的信息， 而修改应用费时费力。 针对此问题，本文提出了一个e v p 信息网格地址空间模型。根据此模型，应用属 性直接引用虚拟信息资源属性，而虚拟信息属性直接引用物理信息资源属性。于是当物 理信息资源模式变更时，我们只需调整物理信息资源到虚拟信息资源之间的映射关系， 而不需修改应用程序，用户就可以得到正确的信息。于是关系模式变更问题转化为物理 信息资源模式变更时物理信息资源模式和虚拟信息资源模式之间映射关系调整问题。 针对映射关系调整问题，本文提出了模式分解模型。此模型将复杂的嵌套关系模式 分解为由主键或主键和一个非主属性构成的原子模式集合。根据此模型，我们可以建立 属性级的映射，这使得映射的调整粒度为属性，有利于物理信息资源模式变更对映射的 调整。 根据上述模式分解模型，本文提出了映射发布规则和基于此规则的映射发布算法。 同时本文详细地分析了各种基本关系模式变更，并提出了相应的映射调整算法。当物理 信息资源模式变更时，映射调整算法自动调整映射并且调整的映射数是最少的。本文证 明映射发布算法和映射调整算法的正确性。与其他方法相比，本文的映射发布方法和映 射调整方法在功能上都具有一定的优越性。 本文形式化地证明了以上方法解决了信息网格中基于关系模型的数据库物理信息 资源模式变更问题。同时我们在织女星铁路信息网格系统中实现和验证了以上方法，结 果表明以上方法能有效地解决铁路中模式变更问题。利用以上方法，铁路物理信息资源 模式变更时，系统调整时间的数量级由天变为毫秒级，于是减轻了映射调整时的人工劳 动。我们同时测试了映射调整算法的性能，测试结果表明映射调整不会造成系统性能瓶 颈。 最后本文提出了适应于基于关系模型的模式变更发布的映射调整方法。此方法减轻 了模式变更发布的人工劳动。 关键词：属性；e v p 信息网格地址空间模型；模式分解模型；映射发布算法：映射调整 算法 r e l a t i o n a ls c h e m ae v o l u t i o nm a n a g e m e n ti ni n f o r m a t i o ng r i d y o u o a n m e i ( c o m p u t e ra r c h i t e c t u r e ) d i r e c t e db yx uz h i w e i t h i sp a p e rs t u d i e st h er e l a t i o n a ls c h e m ae v o l u t i o np r o b l e mi ni n f o r m a t i o ng r i d m a n y a p p l i c a t i o n s i ni n f o r m a t i o ng r i di n t e g r a t ed i s t r i b u t e d ，a u t o n o m o u sr e l a t i o n a ld a t a b a s e sw i t h k e ya n df o r e i g nk e yc o n s t r a i n t s m 1 e nt h ed a t a b a s es c h e m ae v o l v e sa u t o n o m o u s l y , u s e r sc a n n o t g e tc o r r e c ti n f o r m a t i o nw i t h o u tm o d i f y i n g t h ea p p l i c a t i o n s w ep r e s e n ta ne v pa d d r e s ss p a c em o d e lf o rt h ei n f o r m a t i o n g r i d t h ea p p l i c a t i o n a t t r i b u t er e f e r st ot h ev i r t u a li n f o r m a t i o ns o u r c ea t t r i b u t e ，w h i c hi nt u r nr e f e r st ot h ep h y s i c a l i n f o r m a t i o ns o u r c ea t t r i b u t e w h e nt h es c h e m ao ft h ep h y s i c a li n f o r m a t i o ns o u r c ee v o l v e s ，w e j u s t n e e dt o a d j u s t t h e m a p p i n gf r o mp h y s i c a l i n f o r m a t i o ns o u r c ea t t r i b u t e st ov i r t u a l i n f o r m a t i o ns o u r c ea t t r i b u t e s ，w i t h o u tm o d i f y i n gt h ea p p l i c a t i o n s t h e r e f o r e ，t h er e l a t i o n a l s c h e m ae v o l u t i o np r o b l e mi st r a n s f o r m e dt ot h em a p p i n g a d a p t a t i o np r o b l e m t os o l v et h em a p p i n g a d a p t a t i o np r o b l e m ，w ep r o p o s eas c h e m ad e c o m p o s i t i o nm o d e l t h i sm o d e l d e c o m p o s e s an e s t e dr e l a t i o n a ls c h e m ai n t oas e to fa t o m i cs c h e m a s ，e a c ho ft h e m c o n s t i t u t e so f a p r i m a r yk e y o rap r i m a r y k e yp l u san o n p r i m a r ya t t r i b u t e t h e nw e c a ns e tu p t h em a p p i n gb e t w e e na t t r i b u t e ss u i t a b l ef o rm a p p i n g a d a p t a t i o n w e d e v e l o pam a p p i n gp u b l i s h i n gr u l ea n d a m a p p i n gp u b l i s h i n ga l g o r i t h mb a s e d o nt h e r u l ea n dt h e nw e a n a l y s i s v a r i o u sb a s i cr e l a t i o n a ls c h e m a c h a n g e s a n d g i v e t h e c o r r e s p o n d i n gm a p p i n ga d a p t a t i o na l g o r i t h m s w h e nap h y s i c a li n f o r m a t i o ns o u r c es c h e m a c h a n g e s ，t h ea l g o r i t h m sa d j u s tm a p p i n g sa u t o m a t i c a l l ya n da f f e c t t h ef e w e s tn u m b e ro f m a p p i n g s ，w ep r o v et h ec o r r e c t n e s so ft h em a p p i n gp u b l i s h i n ga l g o r i t h ma n dt h em a p p i n g a d a p t a t i o na l g o r i t h m s w es h o w t h a tt h ea l g o r i t h m sc o m p a r e f a v o r a b l yw i t h r e l a t e dw o r k w ef o r m a l l yp r o v et h a tt h ea b o v ea p p r o a c hs o l v e st h er e l a t i o n a ls c h e m ae v o l u t i o n p r o b l e m i ni n f o r m a t i o ng r i d a l s ow e i m p l e m e n ta n dv a l i d a t et h ea p p r o a c hi nv e g ar a i l w a y i n f o r m a t i o ng r i ds y s t e m w i t ht h ea p p r o a c h ，t h et i m et oa d j u s ts y s t e mi sr e d u c e df r o md a y s t om i l l i s e c o n d s w e a n a l y z et h ep e r f o r m a n c eo fm a p p i n ga d a p t a t i o na l g o r i t h m s i nt h e s y s t e m t h e r e s u l ts h o w st h a tt h e m a p p i n ga d a p t a t i o n i sn o tt h e s y s t e mp e r f o r m a n c e b o t t l e n e c k a tl a s t ，w e p r e s e n tam a p p i n ga d a p t a t i o na p p r o a c ha d a p t i v e f o r p u b l i s h i n g s c h e m a c h a n g e st h ea p p r o a c h s a v e sh u m a nl a b o rw h e ns c h e m a c h a n g e s a r ep u b l i s h e d k e y w o r d s ：a t t r i b u t e ，a n e v pa d d r e s s s p a c e m o d e lf o rt h ei n f o r m a t i o n g r i d ，s c h e m a d e c o m p o s i t i o nm o d e l ，m a p p i n gp u b l i s h i n ga l g o r i t h m ，m a p p i n ga d a p t a t i o na l g o r i t h m s i i 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作 及取得的研究成果。就我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工 作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意。 作者签名：篇籁拍 日期：埘f ，孑 关于论文使用授权的说明 中国科学院计算技术研究所有权处理、保留送交论文的复印件， 允许论文被查阅和借阅；并可以公布论文的全部或部分内容，可以采 用影印、缩印或其它复制手段保存该论文。 储繇猁新繇铴移嘲彬腭 1 j 课题背景及意义 第一章引言 铁路综合统计信息系统需要集成分布、自主的关系数据库物理信息资源，然后对集 成的数据进行各种统计，为铁路部门提供综合统计信息。铁路综合统计信息系统面i 临的 一个主要问题是数据库模式的自主变更。数据库模式变更主要包括字段、表的增删和主、 外键的增删等数据结构变更以及属性改名铁o a 。 而现有的铁路综合统计信息系统采用一个数据文件统一存储一类物理信息资源数 据，例如货运信息和客运信息分别存储在货运数据文件和客运数据文件中，然后将所有 数据文件的内容统一存储在一个中央数据库中最后各应用统计程序调用中央数据库的 数据。现有系统的好处是对中央数据库范围内的用户请求响应快，实时性高。但当物理 信息资源模式变更时，需要在停止系统运行的前提下进行二次开发，包括修改数据文件、 中央数据库和应用程序 铁0 2 j 。以上情况不但导致维护成本高，而且可能导致用户得不 到实时的信息。我们将基于关系模型的物理信息资源模式变更产生的问题称为物理信息 资源关系模式变更问题。 铁路综合统计信息系统中物理信息资源关系模式变更问题是信息网格的一个典型 问题。 在网格环境下，大量数据存储在各自主的基于关系模型的数据库物理信息资源中。 这些物理信息资源是自主的一自主管理、自主变化。网格中没有一个全局管理员，各物 理信息资源管理员只能管理本物理信息资源。在电子商务、电子政务等领域中，许多应 用需要同时使用多个自主的关系数据库物理信息资源。一个关系数据库物理信息资源被 多个应用领域使用，一个应用领域要用到多个关系数据库物理信息资源。信息网格的目 的就是实现网格环境下的信息共享。应用领域模式是各应用领域根据行业标准制定的虚 拟数据库模式。虚拟数据库是没有数据的，它的数据都是根据用户需求从各物理信息资 源中获得的。 网格环境下的物理信息资源关系模式是自主变化的。当关系模式自主变化时，为了 保证用户仍能访问各物理信息资源数据，使用了变化的模式的应用就需要被修改，否则 最终用户将得不到正确的数据。但修改应用程序是非常费时费力的，并且应用的数量非 常多，修改的难度是很大的。同时完全手工修改是不可行的，因为这些变化是难以预 9 1 | 5 的( 因为自主性) ，同时模式的可能的变化和应用的数量都会非常多。于是我们需要研 究信息网格中关系模式变更，使得在不修改应用程序的前提下系统就可以自适应模式变 更。 信息网格中关系模式变更管理主要有以下两个领域的需求。 中国科学院博卜学位论文信息悯格中关系模式变更管理 电子商务领域的需要。在电子商务领域中，中间商需要集成各自主企业的商品信息， 统一地提供给用户。一定量商品信息存储在关系数据库中。但由于各企业业务的变化， 如：范围的扩大、业务量的增加、业务变更，使得关系数据库不断变化。在己有的系统 中，不修改应用程序会使得用户得不到或得到错误的信息。解决的一种途径是修改相应 的应用程序。但如果任意一个企业信息变化都要修改应用程序成本会很大。于是如何 实现有效而低廉的模式变更管理成为电子商务领域中一个重要的问题。 电子政务的需要。一个国家中不同地域的相同行业或同一领域的不同行业都有自己 的信息系统。定量的信息系统是基于关系模型的数据库。一个国家经常需要集成这些 信息系统中的信息，形成全国范围内的某个指标的统计。由于这些数据库的模式是自主 变化的，于是需要实现模式变更管理，使得统计系统具有动态适应性，不会因为一个局 部的变化导致整个系统不可用。 本文主要研究具有主、外键的基于关系模型的物理信息资源数据库的模式变更管 理。 1 2 问题的定义 ， 信息网格是研究信息的表示、组织、共享和管理问题。信息网格的一个重要特征是 信息的动态变更性。信息的变更不仅有数据的变更，也有元数据( 本文称为属性) 的变 更。本文研究的是属性的变更。本文不研究属性的语义变化问题。 信息网格中基于关系模型的信息资源模式变更问题：信息网格中物理信息资源关系 模式的动态变更造成应用对物理信息资源引用关系不一致，在不改应用程序的条件下， 用户不能正确访问物理信息资源。此问题可分解为以下问题： 1 ) 用不上问题：当应用所用的物理信息资源属性增加时，用户得不到新增物理信息资 源数据。 2 ) 取不下问题：物理信息资源属性被删除或退出应用或退出信息网格后，用户会进行 无效访问或得不到应用结果。 3 ) 跟不上问题：物理信息资源属性被修改( 包括属性之间的关系) ，例如增加函数依 赖关系或删除函数依赖关系，用户或者进彳亍无效访问或者得不到物理信息资源数据 或者得到错误的物理信息资源数据。 本文只研究信息网格中关系模式变更问题，而不研究事务处理、工作流和计算问题。 本文只研究对各物理信息资源的读操作，而没有写操作。 本文在第七章对信息网格中的关系物理信息资源模式变更问题进行了形式化定义， 并对本文提出的解决方法进行了形式化描述，证明了解决方法的正确性。 1 3 模式变更管理研究 模式变更管理在单个关系数据库数据库、多个关系数据库、单个面向对象数据库领 第一章q l 言 域中已经有广泛的研究，其中多个关系数据库的研究包括数据集成、模式集成、数据交 换、物理数据设计和数据仓库。 从九十年代起，研究者们对单个关系数据库中模式变更问题进行了广泛而深入的研 究。到目前为止，单个关系数据库中的模式变更管理已经比较成熟。研究者们关心的模 式变更问题主要包括模式变更的表示、模式变化操作、模式变更操作的一致性、数据完 整性和数据库的可用性。 对于单个关系数据数据库，研究者们主要从时间角度研究了模式变更，包括时间戳、 事务时间、有效时间。这方面的研究主要有 c c 8 7 1 【d t 8 7 】 m s 9 0 1 【a r i 9 1 1 r o d 9 1 】 r o d 9 2 s c c 9 3 等。而 s t 8 2 、【8 w 8 5 和 m m 8 7 分别从体系结构角度、异常事实处理 角度、实体一关系角度研究了关系模式变更问题。 与单个关系数据库相比，多个关系数据库的模式变更问题研究较少。对多数据库模 式变更问题进行研究的领域主要有数据集成、模式集成、数据交换、物理数据设计和数 据仓库，其中数据仓库领域的研究相对多一些。数据仓库领域中模式变更研究主要是模 式变更时如何调整映射【m p 0 2 m p 0 3 ，包括视图调整【g m r 9 5 i m d 9 6 】和视图同步 f l n r 0 2 。数据集成和模式集成中模式变更研究主要是用户需求变化对映射的影响。数 据交换中模式变更研究主要是修改物理信息资源模式或目标模式 c c g 0 2 a 。物理数据设 计中模式变更研究主要是物理存储向导的设计 t s l 9 6 b f h 0 2 】。而 v m p 0 3 a 提出了一个 通用的映射调整算法来管理模式变更，此方法可以应用于以上各领域。 此外，在单个面向对象数据库领域中，人们对模式变更也进行一定的研究。 由于面向对象模型的复杂性和面向对象数据库的广泛应用，人们从多个不同方面研 究了殛向对象模式变更管理。面向对象模式的变更包括特定对象的变化、类的变化、类 型的变化和方法的变化。 r r 9 7 等研究提出解决对象变化的方法，【l z h 9 7 】等研究提出 了解决方法变化的方法，【p 0 9 7 】【b k k 8 7 1 研究了类的变化， i _ 七r 0 0 】等研究提出解决类 型变化方法。 以上各研究的具体内容见第二章一相关研究。 信息网格领域目前研究主要是基于开发式网格服务体系结构的数据访问和集成服 务( o g s a d a is e r v i c e ) 。它由o g s a - - d a i 服务群注册( d a i s g r ) 、o g s a - - d a i 网 格数据服务工厂( g d s f ) 和o g s a - - d a i 网格数据服务( g d s ) 三部分组成，实现了 物理信息资源的内容以统一的形式发布到网格中和应用以统一访问方式访问物理信息 资源 a j 0 4 1 。但此领域还没有考虑模式变更问题。 1 4 本文的贡献及内容组织 1 4 1 本文的主要工作和贡献 本文研究的问题是信息网格中关系模式变更问题一信息网格中物理信息资源关系 模式的动态变更造成应用对物理信息资源属性引用关系不一致，在不改应用程序的条件 3 中国科学院博十学位论文信息剐格中关系模式变更管理 下，用户不能正确访问物理信息资源。本文的研究目标是在不影响物理信息资源自主性， 不修改应用程序、信息网格系统仍然运行的条件下，系统自动调整应用和物理信息资源 属性之间的关系，使得用户能得到正确的信息。本文的主要贡献包括： 1 e v p 信息网格地址空问模型。此模型由物理信息资源层、虚拟信息资源层、有 效信息资源层三层资源和物理信息资源属性到虚拟信息资源属性的映射关系、 虚拟信息资源属性到有效信息资源属性的映射关系两种映射关系构成。利用虚 拟信息资源层，应用可以透明访问物理信息资源。第七章从理论上证明了并且 第八章也从铁路信息网格项目的实践中表明了：基于此模型，当物理信息资源 模式自主变更时，不需修改有效信息资源层的应用程序，只调整物理信息资源 属性到虚拟资源层属性之间的映射关系，用户就能得到正确的信息。 2 模式分解模型。此模型将具有主键的符合嵌套关系模型的模式分解为由主键或 主键和一个非主属性组成的原子模式集合。本文证明了此分解具有无损连接性。 根据此模型，本文提出了虚拟信息资源层原子模式和物理信息资源模式之间的 映射规则( 映射发布规则) ，此映射是属性级的映射关系。本文证明了基于此映 射规则建立的映射是正确的，即根据映射得到的数据既满足物理信息资源模式 主、外键依赖约束也满足虚拟信息资源模式的主键依赖约束和外键空值依赖约 束。 3 基于模式分解模型的映射发布算法。此算法是根据基于模式分解模型的映射发 布规则生成的。本文证明了根据此算法建立的映射是正确。此算法在人工辅助 下自动生成正确的映射。铁路信息网格项目中已经实现了此算法。 4 映射调整算法。当物理信息资源模式或虚拟资源层模式变更时，映射调整算法 自动调整映射，以保证映射的正确性。本文证明了此算法的正确性。同时本文 也证明了：在保证映射正确性的前提下，此算法调整的映射是最少的。铁路信 息网格项目中已经实现了此映射调整算法。 5 解决了铁路应用中模式变更问题。我们在织女星铁路信息网格系统中实现了基 于模式分解模型的映射发布算法和映射调整算法，解决了铁路应用中模式变更 问题。 6 适用于关系模式变更发布的映射调整方法。为了减少手工发布映射，我们提出 了一个适应于关系模式变更发布的映射调整方法。此方法自动得到一个与模式 变更在一定条件下的等价模式变更集，根据此变更集，系统自动调整物理信息 资源模式和虚拟资源层模式之间的映射。根据调整后的映射，发布者只需发布 少量映射，系统就可以得到正确的映射。在一定的人工辅助下，此方法可以实 现模式变更的自动发布和映射的自动调整。本文证明了此方法的正确性。 1 4 2 本文的内容组织 本文在第一章首先提出了信息网格中应用对物理信息资源弓l 用不一致问题及其意 4 第一章引言 义，并概括性地介绍了模式动态变更管理的相关研究。 第二章分别从单个关系数据库、多个关系数据库和单个面向对象数据库三个方面介 绍并分析了模式变更管理的相关研究。 根据现实问题和现有模式变更管理方法的局限性我们提出了信息网格中关系模式 变更管理方法。 第三章阐述了e v p 信息网格地址空间模型。此模型在应用和物理信息资源之间增 加了虚拟信息资源。基于此模型，应用对物理信息资源引用不一致问题转化为物理信息 资源模式和虚拟信息资源模式之间的映射一致性问题。 第四章定义了映射的相关概念，并提出了基于模式分解的映射发布规则。 第五章将第三章得到的物理信息资源模式和虚拟信息资源模式之间的映射一致性 问题进行了分解，将此问题分解为由于属性的增加、减少、移动、拷贝、模式的外键依 赖约束的增加和减少、映射的增加和减少等变化可能导致映射不正确问题，并根据第四 章基于模式分解的映射发布规则提出了映射发布算法和映射调整算法。根据此调整算 法，当发生以上变化时，算法可以自动调整映射。同时本章还将这两个算法与其他方法 进行了比较。最后第五章介绍了与映射紧密联系的查询分解方法和数据集成方法。 第六章分别对映射表达式和复合变更进行了优化，并对与映射相关的查询进行了优 化。 第七章证明了我们的在第三、四、五章提出的方法解决了第一章提出的问题，并对 基于模式分解模型的映射调整算法进行了性能分析。 第八章介绍了我们的方法在织女星铁路信息网格系统中的应用。 第九章提出了适用于关系模式发布的映射调整方法。此方法可以减少手工发布劳 动。我们证明了此方法的正确性。 最后第十章对整个论文进行了总结，并绘出了将来的研究方向。 2 1 单个关系数据库 第二章相关研究 数据库的变化时会导致模式重构、数据库转换和应用程序转换，于是 s t 8 2 1 提出了 一个模式变更时自动转换关系数据库的体系结构，描述了模式转换时关系数据库系统的 模式转换、存储数据库转换和应用程序的转换。文章试图开发个自动数据库系统工具， 用于转换用关系代数作为数据操作语言的关系模型数据库。在文中，个数据库系统由 一个模式、一个被存储的数据库和一组程序构成。当数据库系统转换后，若对新的数据 库执行新的应用程序时得到的输出和转换前是相等的，则转换保证了输入输出等价性。 文中根据转换的三个特征将关系数据库的变更进行了分类。这三个特征是：信息保留性、 数据依赖独立性和程序依赖独立性。信息保留的转换后没有信息丢失，于是转换是可 逆的。转换的数据依赖性指被存储的数据必须被检查以确定转换是否与目标系统的逻辑 格式致。转换的程序依赖性指应用程序必须被检查以确定转换是否被允许。其中程序 程序依赖性和更新程序依赖性是两种重要的程序依赖性。根据这三个特征，文中将十五 种转换进行了分类，其中在满足信息保留性的转换中，改名、增加属性和增加新关系满 足程序独立性和数据独立性。属性变成主键和主键变成属性满足程序独立性和数据依赖 性，分解信息和删除多值依赖满足查询程序独立性、更新程序依赖性和数据独立性，划 分信息、导出偏序依赖和抽取传递依赖满足查询程序独立性、更新程序依赖性和数据依 赖性：在不满足信息保留性的转换中，组合输入依赖转换满足查询程序独立性、更新程 序依赖性和数据依赖性，删除属性转换和分离满足程序依赖性和数据独立性，合并转换 满足程序依赖性和数据依赖性。根据转换的特征，作者设计出一个自动转换数据库系统。 此系统分为三个阶段处理转换。首先转换处理器读转换声明、检查语法、将变量名与信 息资源模式的变量名进行匹配，若有问题则打印出错误的信息，于是系统可以生成目标 模式：然后系统处理数据依赖转换，数据依赖转换需要检查被存储的信息资源数据库以 保证转换的约束都被满足，当转换约束都被满足时，系统可以生成目标数据库；最后系 统处理程序依赖转换，这种转换需要集成信息资源应用程序以确定转换是否被允许，此 时当输入输出数等价转换不可能时，数据库管理员必须决定采取的措旌，然后系统可l 三i 生成目标应用程序。当目标模式、目标数据库和目标应用程序后，系统必须测试目标系 统功能的正确性。文中定义了并分析了十五种具有约束的关系转换。为了保证输入输出 的等价性，信息资源数据库系统必须满足这些关系转换。利用这些转换，数据库管理员 可以逐步实现模式的变更。 b w 8 5 提出根据异常来修改模式。由于现实世界是不断变化的，因此已经设计好的 稳定的模式可能不能反映真实的现实，于是需要修改模式。文中认为异常信息是不符合 模式约束，但反映现实世界正确状态的信息。根据异常信息，在没有修改整个数据库的 6 中国科学院博l 。学位论文信息恻格中关系模式变更管理 情况下用户就可以得到更多的正确的信息。虽然文章研究的是根据异常修改语义数据 模型的模式，但其中对异常的处理也适用于关系模型。文中分析了数据库的异常并提出 了处理异常的方法。这个方法是：当出现不符合数据库约束的异常时，数据库中的对象 标识异常信息，于是异常信息可以被维护；用户用专门的命令来操作异常信息；当用户 使用异常信息时，异常处理机制会警告用户；同时管理员可以根据异常现实来修改数据 库模式约束。文中提出了一个基于机器学习方法的归纳算法，此算法根据对异常的分析 得出体现现实的异常，并向管理员提出修改模式的建议。此算法的输入是一组对象描述， 输出是以这组对象作为实例的类的描述，共且这个类是任何以这组对象作为实例类的子 类。这个算法的基本思想是：对象可以被一一描述，类可以根据对象被修改以描述当前 的对象：一组被初始化的异常描述作为第一个异常实例，下一个异常实例与这个异常实 例比较；当类的部分描述的约束太严格时，算法通过扩展值域、归纳类和删除属性描述 的方法来使这部分类通用化。根据归纳算法的输出的类，归纳程序可以提出调整模式的 建议，其中对模式的修改包括修改值域、修改完整性约束和定义新的类，最后由管理员 决定对模式的修改。 m m 8 7 提出一个基于实体一关系模型的模式变更方法。数据模型通过数据库的重 组反映了信息系统的变更。数据库重组是有着状态映射的模式重构，其中状态是指关系 的值域。由于关系数据库重组注重关系代数而忽略了信息结构，同时面向设计的关系一 实体能更好地反映信息结构的变更，m m 8 7 采用了实体一关系来研究关系模式变更。 若一个关系模式可以被转换成实体一关系图，则此模式被称为实体一关系一致的。文章 研究了实体一关系一致的关系模式，并给出了这种关系模式和实体一关系图之间的相互 转化方法。模式重构是数据库重组的一部分。文章首先讨论了数据库状态为空时模式重 构。关系模式基本重构操作为关系模式的增加和删除，以及关系内和关系之间的依赖性 的调整。文中定义了增量的、可逆的模式重构，其中增量性表示单步模式修改，可逆性 表示可以取消单步模式修改。文章然后讨论了数据库状态不为空时数据库重组。由可兼 容的增量重构操作对和与实体绑定的状态映射构成了数据库重组操作，由实体关系算子 表示了实体一致性数据库中的状态映射。最后文章用重组操作表示了基于代数的实体一 关系操作。 c c 8 7 n 然没有明确讨论模式变更问题，但讨论了关系模型的生命周期，这表明此 文中的可以用来解决模式变更问题。文中提出了基于生命周期的历史关系数据模型 ( h i s t o r i c a lr e l a t i o n a ld a t a m o i l e l ，h r d m ) 和此模型的历史关系代数。h r d m 模型是 扩展的传统关系数据模型，即在关系数据模型的本体中增加了一个新的对象类型一时刻 集合，并且属性值域被扩展为时刻到简单值域的映射，于是历史关系数据库空间由时间、 属性和属性值三维构成。在h r d m 模型中，元组生命周期表示数据库中的数据会随时间 变化而变化，而属性生命周期表示数据库的模式会随时间变化而交化。h r d m 模型中的 每个属性值都有与一个生命周期参数相联。此生命周期参数定义了属性值的存在周期。 这样的一组属性构成了一个关系。一组这样的关系模式构成了一个数据库模式。模型根 7 第二二章相关研究 据每个属性值的生命周期确定属性存在于模式中的时间周期。关系数据模型中的一元关 系算子提供了属性和属性值的运算，历史关系模型中的历史算予是扩展的关系算子并且 增加了作用于时间维的时间片操作。文中定义了基于时问的扩展的投影算子，选择算子、 连接算子，并增加了时间片算子和时刻算子。用户通过这些算子对历史关系数据库进行 访问。模式变更可以被看作数据库在不同时刻有着不同的模式，并且变更前和变更后的 模式共存于数据库中，于是 c c 8 7 1 中方法同样适用于解决模式变更问题。 f d t 8 7 采用时间数据库研究了模式变更。文中提出了具有时问管理的非第一范式 ( n o n f i r s t n o r m a l f o r m ，n f 2 ) 关系模型。基于此模型的关系数据库可以存储非第一 范式关系。n f 2 数据库存储了不同版本的数据库模式，每种版本对应一个时刻的模式。 文中讨论了九种模式变更并提出了用存储结构来实现每种变更的方法。 r m s 9 0 通过扩展了关系代数和形式化地定义了用于查询和更新数据库的代数语言 来支持数据库模式变更。模式变更是某个时刻数据库模式的变化。传统数据库只允许某 个时刻产生的一个数据库模式存在，当模式变更时，管理员就要重构数据库模式。随着 时间数据库的出现，不同时刻生成的数据库模式可以在一个数据库中并存，于是用户可 以访问过去的数据库 c c 8 7 。【m s 9 0 定义了用于数据库查询和更新的代数语言，这个语 言包括关系代数和历史代数，通过支持事务时间来支持模式变更。现在有三个层次的关 系数据库语言：用户接口级使用的基于演算的语言，例如s q l ：代数级的关系代数语言 和物理级的查询和更新操作语言。m s 9 0 提出的方法是代数级语言。为了扩展关系代数， 数据模型增加了有效时间、事务时间和用户定义时间。有效时间是事件发生时现实中的 时间；一个事件的事务时间是数据库中存储此事件的事务号，用户定义时间是用来支持 输入和输出的，由用户或程序定义的。为了支持有效时间和事务时间，语言中定义了四 种关系的类：快照关系类、回滚关系类、历史关系类和时间关系类。快照关系类由属性 和属性元组组成，反映了一个时刻的数据库状态；回滚关系类是根据事务时间索引的快 照状态序列；历史关系类由属性、属性元组和有效时间构成；时间关系类是根据事务时 间索引的历史状态序列。回滚关系类和时间关系类支持事务时间，而快照关系类和历史 关系类不支持事务时闽。模式变更只与事务时闻有关，此时关系模式是由关系类和映射 ( 签名) 构成的二元组，签名将属性映射到相应的值域上。数据库模式和内容构成了数 据库的状态。以事务时间作为索引的关系类序列、签名序列和状态序列构成了数据库的 关系。数据库由数据库状态和事务时间构成。文中定义了数据库的四个命令：定义关系、 修改关系、删除关系和关系改名。数据库模式可以利用这四个命令修改关系。作者用事 务封装了以上命令。将事务作为一个原子更新操作著支持多命令事务。在多命令事务中， 模式的多个关系都可能会变化。当模式变更时，为了保证代数表达式的语义正确性以及 数据和模式之间的一致性，作者提出了一个语义类型系统来进行类型检查a 此语义类型 检查系统确定不正确的表达式并保证关系类之间一致性约束。文中定义了包含以上内容 的代数语言。文章首先定义了此语言的语法，然后用符号语义定义了语言的语义域和表 达式的语义类型系统，最后定义了将语言构造映射到符号上的语义映射。通过这个代数 禽 中国科学院博士学位论文信息网格中关系模式变更管理 语占，用户可以查询和更新时间数据库。 a r i a v 用面向时间的数据模型( t e m p o r a l l y o r i e n t e d d a t a m o d e l ，t o d m ) 研究模式 变更问题 a r i 9 1 。此研究的一个重要贡献是研究了模式变更时应用程序的管理。模式变 更被分成时问性浅层变化和时间性深层变化两类变更。时间性浅层变化是包含比较少的 操作的变更。这些操作具有最小的j _ | 三确步骤。这些步骤用于将修改后的模式回溯地应用 到现存的数据上。时间性深层变化是需要大量计算的变更，这些计算将己被修改的模式 的应用程序回溯地应用到现存数据上。此研究明确阐述了数据定义和模式变更时使用 t o d m 的要求。但此研究没有说明实现模式变更的具体细节。 【r o d 9 l 】提出了一个关系数据库属性具有时间的模型。此研究表明基于属性的系统 目录必须有有效时间和事务时间支持。文中同时讨论了空值语义、空值对完整性的影响 和空值对查询语言的影响。空值可能有三种语义：属性存在但属性值不存在、属性不存 在和不能确定属性和属性值是否存在。模式变更时空值可能会导致严重的问题，例如当 增加新关系时此关系的所有属性的值可能都空，这将破坏实体完整性约束和引用约束。 这些已在支持模式变更的s q l s e 查询语言中实现 r o d 9 2 1 。 r o d 9 2 提出了一个支持模式变更的关系数据库查询语言s q l s e 。s q l s e 是扩展 的s q l 语言，用于时间关系数据库。时间关系数据库记录了模式变更并保留了当前数 据库模式定义。时间关系数据库是在关系数据库中增加了时间管理以便于模式变更管 理，于是相应的需要扩展关系数据库查询语言以支持模式变更。文中分别从完整关系、 空值、有效时间和事务时间、查询输出角度扩展了s q l 语言。完整关系是包含所有被 定义了的属性的关系，扩展后的s q l 语言- - s q l s e 语言支持查询完整关系。空值可能 有三种语义：属性存在但属性值不存在、属性不存在和不能确定属性和属性值是否存在。 s q l s e 语言的查询语句可以区别返回的空值属于哪种语义。若数据库支持有效时间， 用户可以查询过去和将来的模式；若数据库支持事务时间，数据库可以记录模式变化。 s q l s e 语占支持有效时间和事务时间。当查询出现错误时，为了使用户得到确切的错 误信息，s q l s e 语言将输出这些错误信息。s q l s e 语言允许用户查询指定时间的模式。 s c a l a s 等人讨论了另一个时间关系数据库中的模式变更 s c c 9 3 。变更可以分为两 类：重定义和修改。重定义时，变化后的模式完全独立于变化前模式。最近模式的变化 被称为修改。文中关系模型的变化可分为两类：属性级变化和关系变化。属性级变化包 括增加属性、删除属性、属性改名和重定义属性域。关系变化包括增加关系和删除关系。 文中详细讨论了重定义和修改变化的实现。 采用关系模型的模式变更调整方法包括对数据库的时间支持( 包括对属性的时间 支持) 、视图机制和异常处理。大量的使用关系模型的模式变更研究通过扩展和修改关 系代数来提供支持模式变更的语言。数据库的时间支持( 事务和有效时间) 是支持模式 版本的有效方法。具有时间支持的扩展的s o l 语言是管理时间数据库中数据和模式的基 础。关系模型中的视图机制主要用来支持版本化。根据异常来修改模式，使得模式符台 现实。 9 第二章相关研究 2 2 多个关系数据库 在多数据库中，关系模式变更管理在数据集成、模式集成、数据交换、物理数据设 计和数据仓库等领域都有一定的研究。 联邦数据库系统 b k l 9 9 r 扣，各物理信息资源数据库是相对独立的并且是结构化的， 都可以用查询语言来访问。联邦数据库模式要满足完整性、正确性、最小性和可理解性。 在自底向上采用模式集成技术构建联邦数据库时，构建过程必须保证联邦数据库模式满 足以上性质。同时构成系统的物理信息资源不能随意变更。若物理信息资源发生变更， 系统需要自底向上修改系统，以保证联邦数据库模式满足以上要求。所以联邦数据库系 统是只适合集成静态物理信息资源数据库，而不适合集成自主的经常变更的物理信息资 源。 在数据集成系统中，用户通过一个统一的、虚拟的视图来查询异构数据源 l e n 0 2 。 生成视图的过程被称为模式集成或视图集成 b l n 8 6 1 。大量的算法和工具被提出用来自 动集成模式或半自动集成模式。视图集成过程包括预集成、模式比较和调整模式。 r b l n 8 6 提出了模式集成问题的概念基础，并从使用、完整性和详细说明分析了已有的 解决方法。f s p 9 4 用户使用正式声明的方法定义被集成的模式和视图之间的对应关系， 然后根据用户的输入，系统通过集成算法生成所有可能的方案，于是自动生成了被集成 的模式和视图之间的结构和操作映射。r s p 9 4 3 采用将映射方法使得管理员不需修改被集 成的模式若适应于关系模型等模型。f g l s 9 5 采用表格数据库模型来表示数据，并用表 代数语言查询和重构表的数据和集成模式。然而这些方法都不支持集成模式的任意变 更，例如一个基于用户定义的集成表的水平分解都要求设计者手工修改映射，同时也不 支持信息资源模式的修改：这些变更要求模式集成算法重新运行以生成映射 r r 9 9 1 。 在数据集成中一个重要的方法是用集成的视图表示异构信息资源模式 l r 0 9 6 1 k l s 9 5 】局部作为视图( 1 0 c a l a s - v i e w ，l a v ) 方法。a t t 公司开发的i n f o r m a t i o n m a n i f o l d 项目采用l a v 方式发布各信息资源，先根据应用定义全局的属性，即世界视 图( w o r l dv i e w ) ，根据全局的属性发布信息资源的局部属性。这种方式的好处是信息资 源动态增删时不影响系统的运行，为应用程序提供了极大的灵活性和数据独立性。但根 据应用定义一个全局的属性是一个复杂的事情，并且将对应全局属性的查询语句分解成 对应局部属性查询语句是很难的。同时当某个全局属性发生变化时，在同一表中的所有 信息源属性都不能被访问，于是对全局属性的变更适应性差。并且目前还没有工具能在 模式变更时自动更新这些基于l a v 方法建立的映射。 全局模式作为视图 g l o b a l a s v i e w ，g a v ) 与l a v 相对的是经典数据集成方法， 这种方法用信息资源模式表示集成模式 m p q 9 7 1 。g a v 方法要求集成模式中同一个表的 映射在一起。所有的局部属性组成全局属性。这种方式的好处是全局属性定义简单，对 应全局属性的查询语句直接与局部属性对应，分解简单。当某个信息源属性发生变化时， 在同一表中的所有全局属性都不能被访问，于是对信息源属性的变更适应性差。同样根 1 0 中国科学院博卜学位论文信息恻格中关系模式