（计算机应用技术专业论文）基于关系模式的带完整性约束的数据集成研究.pdf

摘要 摘要 数据集成的目标是为用户访问多个异构的数据源提供统一的应用界 面，从而使用户将注意力集中在他们想要的特定结果上，而不必关心如何 获得这些结果。本文针对国内外有关数据集成系统的现状进行了综合分析， 分别采用全局视图映射和本地视图映射两种方法，对基于关系模式的数据 集成系统中有关完整性约束以及查询的问题进行了研究。 首先，介绍数据集成系统的相关概念，对数据集成系统中的映射机制 以及数据集成系统中的完整性约束进行了深入的研究，提出一个查询预处 理算法。该算法基于关系模式，采用本地视图映射，对带有完整性约束的 集成系统进行处理，将用户查询投影到新的数据源视图上，从而扩大了查 询范围，获得更多的信息。 然后，根据数据集成系统中完整性约束以及构造标准化数据库的思想， 提出一个判断数据集成系统是否存在“约束循环”的算法。该算法基于关 系模式，采用全局视图映射方法，对带完整性约束的数据集成系统全局模 式上定义的参照完整性约束进行处理。通过该算法，可以判断出数据集成 系统中的参照完整性约束是否存在“约束循环”。当数据集成系统中的参照 完整性约束不存在“约束循环”时，可以构造出有限的标准化数据库，不 仅解决了带完整性约束的数据集成系统上的查询问题，而且提高了用户查 询的效率。 关键词数据集成系统；全局视图映射；本地视图映射；完整性约束：约束 循环 燕山大学工学硕士学位论文 a b s t r a c t 1 1 1 eg o a lo fd a t ai n t e g r a t i o ni st op r o v i d e sam t i f i c a t e da p p l i c a t e ds u r f a c e f o rt h eu s e r st ov i s i tt h ei s o m e r i s md a t as o l i c e s ，t h u st h eu s e r st r u l y c o n c e n t r a t et h ea t t e n t i o no nt h es p e c i f i cr e s u l t sw h i c ht h e yw a n t s ，b u td o e sn o t n e e dt oc a r ea b o u th o wo b t a i n st h e s er e s u l t s t h i sa r t i c l eh a sc a r r i e do nt h e g e n e r a l i z e da n a l y s i si nv i e wo f t h ed o m e s t i ca n df o r e i g nr e l a t e dd a t ai n t e g r a t i - o ns y s t e mr e s e a r c hp r e s e n ts i t u a t i o n ，u s e st h eg l o b a la sv i e wm a p p i n ga n dt h e l o c a la sv i e wm a p p i n gs e p a r a t e l y , t h ei n t e g r i t yc o n s t r a i n t sa n dt h eq u e r yq u e s t i o nh a sc o n d u c t e dt h er e s e a r c ha c c o r d i n gt od a t ai n t e g r a t i o ns y s t e mb a s e do n r e l a t i o n a lm o d e l f i r s t l y , i n t r o d u c e dt h er e l a t e dc o n c e p t sa b o u td a t ai n t e g r a t i o ns y s t e m ，t h e m a i nl o g a r i t h mh a sc o n d u c t e dt h et h o r o u g hr e s e a r c ha c c o r d i n gt ot h em a p p i n g m e c h a n i s ma sw e l la st h ei n t e g r i t yc o n s t r a i n t si nt h ed a t ai n t e g r a t i o ns y s t e m ， a n dt h e np r o p o s e daq u e r yp r e p r o c e s s i n ga l g o r i t h m t h ea l g o r i t h mp r o c e s st h e d a t ai n t e g r a t i o ns y s t e mu n d e ri n t e g r i t yc o n s t r a i n t sb a s e do nt h er e l a t i o n a l m o d e lw h i c hu s e st h el o c a la sv i e wm a p p i n g ，u s e rq u e r ym a p p e do nt h en e w s o u r c ev i e w s ，c o n s e q u e n t l ye x p a n d e dt h es c o p eo fq u e r y , a n dr e c e i v e dm o r e i n f o r m a t i o n s e c o n d l y , a c c o r d i n gt ot h ei d e ao fd a t ai n t e g r a t i o ns y s t e mu n d e ri n t e 鲥t y c o n s t r a i n t sa sw e l la sc o n s t r u c t e dt h ec a n o m c a ld a t a b a s e ，t h i sp a p e rp r o p o s e d a na l g o r i t h mw h e t h e rt h ed a t ai n t e g r a t i o ns y s t e mh a v et h e ”r e s t r a i n tc i r c u l a - t i o n ”t h ea l g o r i t h mp r o c e s st h ef o r e i g nk e yc o n s t r a i n t so nt h eg l o b a ls c h m a lo f t h ed a t ai n t e g r a t i o ns y s t e mb a s e do nt h er e l a t i o n a lm o d e lw h i c hu s et h eg l o b a l a sv i e wm a p p i n g i tc a ns u r m i s ew h e t h e rt h ef o r e i g nk e yc o n s t r a i n t sh a v e ”r e s t r a i n tc i r c u l a t i o n “o nd a t ai n t e g r a t i o ns y s t e m w h e nt h ef o r e i g nk e y c o n s t r a i n t si nt h ed a t ai n t e g r a t i o ns y s t e md o e sn o th a v et h e ”r e s t r a i n tc i r c u l a t 一 a b s t r a c t i o n ”，w ec a l lc o n s t r u c tt h el i m i t e dc a n o n i c a ld a t a b a s e n o to n l ys o l v e dt h e q u e r yq u e s t i o ni nd a t ai n t e g r a t i o ns y s t e mu n d e ri n t e g r i t yc o n s t r a i n t sm o r e o v e r e n h a n c e dt h eu s e rq u e r y e f f i c i e n c y k e y w o r d sd a t ai n t e g r a t i o ns y s t e m ；g l o b a la sv i e w ；l o c a la sv i e w ；i n t e g r i t y c o n s t r m n t ；c o n s t r a i n tc i r c u l a t i o n ； m 燕山大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文基于关系模式的带完整性 约束的数据集成研究，是本人在导师的指导下，在燕山大学攻读硕士学位 期间独立进行研究工作所取得的成果。据本人所知，论文中除已注明部分外 不包含他人已发表或撰写过的研究成果。对本文的研究工作做出重要贡献的 个人和集体，均已在文中以明确方式注明。本声明的法律结果将完全由本人 承担。 作者签字：艟 日期：函刁筚归刁日 燕山大学硕士学位论文使用授权书 基于关系模式的带完整性约束的数据集成研究系本人在燕山大学攻 读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归燕 山大学所有，本人如需发表将署名燕山大学为第一完成单位及相关人员。本 人完全了解燕山大学关于保存、使用学位论文的规定，同意学校保留并向有 关部门送交论文的复印件和电子版本，允许论文被查阅和借阅。本人授权燕 山大学，可以采用影印、缩印或其它复制手段保存论文，可以公布论文的全 部或部分内容。 保密口，在年解密后适用本授权书。 本学位论文属于， 不保密日。 ( 请在以上相应方框内打“4 ”) 作者签名：醚 导师签名：再分：争 日期d 十 珈 日期：问年“月垢 第1 章绪论 1 1 研究背景 第1 章绪论 最近的二十年来，随着计算机的普及与网络的飞速发展，产生了海量 的信息数据，可利用的信息源持续增长，许多应用需要对多个数据库的信 息进行访问和结合，导致用户需要面对大量的异构数据源【1 1 。因此，近年 来许多研究都集中在数据集成方面，数据集成将存在于各个数据源中的数 据结合起来，并为用户提供一个最终的视图。许多公司建立数据仓库，数 据挖掘或者企业资源规划系统来解决异构数据源的数据集成问题。 数据集成技术已经历了2 0 多年的发展过程，研究者己提出了很多数据 集成的体系结构和实现方案，然而这些方法所研究的主要集成对象是传统 的异构数据库系统。随着i n t e r n e t 的飞速发展，网络迅速成为一种重要的 信息传播和交换的手段，尤其是在w e b 上，有着极其丰富的数据来源。如 何获取w e b 上的有用数据并加以综合利用，即构建w e b 信息集成系统， 成为一个引起广泛关注的研究领域。 在应用领域，i n t e r n e t 是目前主要的驱动力，特别是在支持“跨企业” 的应用上。在历史上，应用都是企业内部的，可以在一个行政领域内进行 完善的指定和优化。但是现在大部分企业感兴趣的是如何与供应商和客户 进行更密切的交流，以便提供更好的客户支持。这类应用从根本上说是跨 企业的，需要安全和信息集成的有力工具。由此产生的新问题需要数据库 研究人员去解决。 越来越重要的另一个应用领域是自然科学，特别是物理科学、生物科 学、保健科学以及工程领域，这些领域产生了大量复杂的数据集，需要比 现有的数据库产品更高级的数据库的支持，这些领域同样也需要数据集成 机制的支持。 数据集成是信息系统集成的基础和关键。好的数据集成系统要保证用 燕山大学工学硕士学位论文 户以低代价、高效率使用异构的数据。 1 2 研究现状 数据集成技术经历了2 0 多年的发展过程，目前已广泛应用于电信、保 险、银行、广电等各行各业的日常操作和各种管理决策过程中，但是这些 系统往往只分散在各个职能部门中，相互间的信息交流非常困难。随着 i n t e r n e t 在全球的迅猛发展，各行业的信息系统已经不再是传统的单数据库 应用系统，而希望发展为i n t e m e t 上多数据源集成的信息系统，因此“数 据集成”成为当前信息领域研究和开发的热点【2 】。下面分别从数据集成系 统的体系结构以及数据集成方法两个方面分别对数据集成系统的研究现状 作一简要介绍。 1 2 1 数据集成系统的体系结构 1 9 9 1 年，g i ow i d e r h o l d 提出了数据集成的研究方向以及未来数据集成 系统的体系结构即中间件查询系统 3 1 ( m e d i a t e dq u e r ys y s t e m ，m q s ) 。其目 标是针对应用需求将分布异构的数据源通过集成形成一个整体，使用户可 以以透明的共享方式访问信息，并且通过集成为用户提供新的知识。m q s 系统用于处理结构化、半结构化等各类信息的集成。其目标是针对需求将 分布异构的数据源通过集成形成一个整体，使用户可以以透明的共享方式 访问信息，并且通过集成为用户提供新的知识。 m q s 的思想是将集成的任务和功能进行层次的划分，其结构中包括三 个层次1 4 1 ：f o u n d a t i o n 层，m e d i a t i o n 层和a p p l i c a t i o n 层。 f o u n d a t i o n 层中包括了信息源和w r a p p e r ，w r a p p e r 是一个软件模块， 称作包装器，它用于各类数据源的查询语言、数据模型以及各类概念和 m e d i a t i o n 层全局的查询语言、数据模型与概念的转换。 m e d i a t i o n 层本身也是分层次的。它由若干称作m e d i a t o r 的模块组成， 一个m e d i a t o r 其实就是一个或多个信息源上数据的视图，它从一个或多个 低于它的部件中获得信息，这些部件可能是经过包装的信息源，也可以是 2 第1 章绪论 其它m e d i a t o r 。每个m e d i a t o r 可以向高层部件提供信息，也可以直接向系统 的外部用户提供信息。m q s 系统中m e d i a t i o n 层的主要任务，就是“通过使 用视图定义来转换和提炼信息源提供的数据”。从而达到“简化、抽象、 缩减、合并、解释数据”的目的。数据集成的大量问题，都可以看作如何 使用视图组建用户查询要求的问题，一个m e d i a t o r 其实就是一个或多个信 息源上数据的视图”。然而利用视图组建查询有许多理论上的尚未解决的 问题，在数据集成过程中，迫切需要给出这些问题的解答。因此许多数据 集成系统都围绕视图查询问题进行了研究，并取得了许多新成果。 a p p l i c a t i o n 层可以根据具体应用需求，建立相关的应用，如o i a p 、数 据挖掘和查询的g u i 等等。 1 2 2 数据集成方法 模式集成是人们最早采用的数据集成方法1 5 1 。其基本思想是，在构建 集成系统时将各数据源的数据视图集成为全局模式，使用户能够按照全局 模式透明地访问各数据源的数据。全局模式描述了数据源共享数据的结构、 语义及操作等。用户直接在全局模式的基础上提交请求，由数据集成系统 处理这些请求，转换成各个数据源在本地数据视图基础上能够执行的请求。 模式集成方法的特点是直接为用户提供透明的数据访问方法。由于用户使 用的全局模式是虚拟的数据源视图，一些学者也把模式集成方法称作虚拟 视图集成方法。模式集成要解决两个基本问题【6 】：构建全局模式与数据源 数据视图间的映射关系；处理用户在全局模式基础上的查询请求。 目前比较流行的建立数据集成系统的方法是w r a p p e 删e d i a t o r 方法【7 1 。 该方法并不将各数据源的数据集中存放，而是通过w r a p p e r m e d i a t o r 结构满 足上层集成应用的需求。这种方法的核心是中介模式( m e d i a t e ds c h e m a ) 。 信息集成系统通过中介模式将各数据源的数据集成起来，而数据仍存储在 局部数据源中，通过各数据源的包装器( w r a p p e r ) 对数据进行转换使之符合 中介模式。用户的查询基于中介模式，不必知道每个数据源的特点，中介 器( m e d i a t o r ) 将基于中介模式的查询转换为基于各局部数据源的模式查询， 它的查询执行引擎再通过各数据源的包装器将结果抽取出来，最后由中介 燕山大学工学硕士学位论文 器将结果集成并返回给用户，如图1 1 所示。 图1 - 1 基于中间件的数据集成系统模型 f i g u r e1 - 1m o d e lo f d a t ai n t e g r a t i o nb a s e d0 1 1t h em e d i a t o r i n f o r m a t i o nm a n i f o l d 和t s i m m i s 是两个很有代表性的数据集成系统。 它们分别代表两类视图集成的方、法【8 】：首先定义全局谓词，然后将各个信 息源表示为全局谓词的视图；根据信息源的信息模式，在m e d i a t o r 层定义 统一的视图。这两类方法有各自的利弊，第一种方法的优点是很容易增加 新的信息源，当增加信息源时，只需要为它增加一个w r a p p e r ，并且根据 全局谓词定义视图就可以了。但是缺点也很明显，系统根据信息源的视图 得到的结果很可能是不完整的。第二种方式较为常见，在m e d i a t o r 中定义 统一的视图，能够比较精确地定义信息提供的信息，但缺点是系统不易扩 展，每增加一个信息源，都可能要重新定义m e d i a t o r 中的视图定义。 1 3 研究意义 数据集成的难点 9 a 0 归纳为以下三个主要方面。 ( 1 ) 异构性被集成的数据源通常是独立开发的，数据模型异构，给集 成带来很大困难。这些异构性主要表现在：数据语义、相同语义数据的表 达形式、数据源的使用环境等。 ( 2 ) 分布性数据源是异地分布的，依赖网络传输数据，这就存在网络 传输的性能和安全性等问题。 ( 3 ) 自治性各个数据源有很强的自治性，它们可以在不通知集成系统 的前提下改变自身的结构和数据，给数据集成系统的鲁棒性提出挑战。为 4 第1 章绪论 了解决这些难题，人们尝试了很多方法，但还没有完全解决数据集成中的 一些难题。 w r a p p e r m e d i a t o r 方法解决了数据的更新问题。但是，由于各个数据源 的包装器是要分别建立的，因此w e b 数据源的包装器建立问题又给人们提 出了新的挑战。近年来，如何快速、高效地为w e b 数据源建立包装器成为 人们研究的热剧”1 。 目前，这种框架结构正受到来自三个方面的挑战【m 1 6 】。 第一个挑战是如何支持异构数据源之间的互操作性。数据集成必须在 多至数百万的信息源上穿梭进行，这些数据源的数据模型、模式、数据表 现和查询接口各不相同。数据库界已经对联邦式的数据系统做了多年的研 究，其中最早的报告针对这个问题做了广泛的讨论。然而，语义的相异性 这个问题依然存在。由不同人设计的任何两个模式都不会是相同的。它们 会有不同的单位，不同的语义解释，对于相同的事务还会有不同的名字。 能够在网络标准上进行配置的语义相异性的解决方案依然是难以捉摸的。 需要认真和集中地对待这个问题，否则跨企业的信息综合只会停留在幻想 上。语义w e b 的上下文方面的研究也存在着相同的问题。吸收相关领域的 研究成果对解决这一问题是很重要的。 第二个挑战是如何模型化数据源内容和用户查询。目前广泛采用的技 术有两种。本地视图映射( l o c a la sv i e w , l a y ) 方法利用全局谓词集合描述 多个数据源内容视图和用户查询。当给定某用户查询时，中间件系统通过 综合不同的数据源视图决定如何回答查询。这种方法可看作利用视图回答 查询，目前已有一些研究成果，它亦可应用于数据仓库或查询优化等领域。 全局视图映射( g l o b a la sv i e w , g a y ) 方法假设用户查询直接作用于定义在 数据源数据关系上的全局视图。人们主要关注的是在这种情况下如何提供 高效的查询处理。 第三个挑战是当数据源的查询能力受限时，如何处理查询和进行优化。 很少的组织会允许外部实体来抽取自己运行系统中的所有数据，所以这些 数据必须保留在数据源端，在查询的时候才会被访问。如何模型化和计算 具受限查询能力的数据源，如何生成查询计划和优化查询的研究工作正在 燕山大学工学硕士学位论文 进一步展开。 本文基于关系模式，采用本地视图映射方法对带完整性约束的数据集 成系统进行的研究，模型化和计算具有受限查询能力的数据源，优化了用 户查询；而采用全局视图映射方法对带有完整性约束的数据集成系统进行 的研究，优化了用户查询，提高了用户查询效率。因此，采用本地视图映 射方法的查询预处理算法和采用全局视图映射方法的“约束循环”判断算 法具有十分广泛的应用前景和实际意义。 1 4 研究内容 根据上面所阐述的研究背景和研究现状，本文在对带有完整性约束的 数据集成系统深入研究的基础上，对现有的方法进行了补充。主要分为以 下几个方面。 第一，当集成系统不考虑完整性约束时，会导致查询结果不完整。现 有的基于关系模式，考虑完整性约束的数据集成系统中的查询方法，采用 的是全局视图映射方法。针对此方法，提出一种基于关系模式，采用本地 视图映射，对带有完整性约束的数据集成系统进行查询的方法。这个查询 预处理算法，将会解决基于关系模式，采用本地视图映射，带有完整性约 束的数据集成系统中的查询问题。 第二，由于数据集成系统中全局模式上定义的参照完整性约束可能存 在“约束循环”，导致规范化数据库无穷大。针对此问题，提出一种基于关 系模式，采用全局视图映射，带有完整性约束的数据集成系统判断“约束 循环”的算法。通过此算法，可事先判断出数据集成系统中的完整性约束 是否存在“约束循环”，从而可以有效的优化查询过程，提高查询效率。 1 5 本文的结构 本论文总体上分为4 章，从第2 章开始具体布局如下。 第2 章介绍数据集成系统的基础知识。对数据集成系统的基本概念， 6 第l 章绪论 层次，分类、集成过程，以及数据集成系统研究的关键问题进行了简要的 介绍。 第3 章主要研究带完整性约束的数据集成系统。首先，对基于关系模 式的带有完整性约束的数据集成系统进行简要的分析：其次，详细论述当 采用全局视图映射方法时，带有完整性约束的数据集成系统上查询所产生 的问题，以及采取的解决方法；最后，针对采用本地视图映射方法时，带 有完整性约束的数据集成系统中的查询所出现的问题，提出基于关系模式 的待完整性约束的数据集成系统中的查询预处理算法。 第4 章主要研究基于关系模式，采用全局视图映射，带有完整性约柬 的数据集成系统中的“约束循环”问题。首先，提出“规范化数据库”的 概念，并阐述规范化数据库的构造方法：其次，提出“约束循环”的定义， 并论述在何种情况下，会出现“约束循环”问题；最后，针对由于“约束 循环”的存在，导致数据集成系统无法通过构造标准化数据库来进行查询 的问题，提出基于关系模式，采用本地视图映射，带有完整性约束的数据 集成系统的“约束循环”判断算法。 最后，在结论中对本文的工作进行总结，并对进一步的研究进行分析 和展望。 7 燕山大学工学硕士学位论文 2 1引言 第2 章基础知识概述 上一章主要阐述了本课题的研究背景、研究现状和研究意义。本章将 详细介绍与本课题研究相关的基础知识，包括数据集成系统的三元组表示 形式，映射机制以及数据集成系统的语义表达；然后介绍了数据集成系统 的层次、分类和集成过程；最后介绍了数据集成研究中的关键问题。 2 2 数据集成系统基本概念 为了更好的理解数据集成系统，下面介绍数据集成系统中的基本概念， 包括数据集成系统的三元组表示形式，数据集成系统的映射机制，以及数 据集成系统的语义。 2 2 1数据集成系统的表示形式 数据集成的根本任务l l7 j 是提供用户对多种异构数据源透明、一致和实 时访问。透明性是屏蔽底层数据源的差异，让用户感觉数据来自一个大的 数据源；一致性是消除数据源之间存在的结构异构和语义异构；实时性则 指访问到的数据是最新更新过的。 映射的一个重要性质涉及到与对应视图及其相关数据源投影的精确性 问题【1 8 l 。如果一个数据源仅提供根据全局模式得到的相应视图中可访问数 据的子集，那么就说此映射性质为s o u n d ；如果数据源提供与相应视图确 切完全的数据，就说映射性质为e x a c t 。本文假设映射性质为s o u n d 。 数据集成系统的表示形式由定义2 1 给出。 定义2 1 ：这里给出数据集成系统的三元组表示形式【1 9 l ：卢( g ，s 务， g 表示全局模式，s 表示数据源模式，肘表示全局模式与数据源模式之间 第2 章基础知识概述 的映射。 ( 1 ) 全局模式g 描述为带有实体完整性约束以及参照完整性约束的关 系模式； ( 2 ) 数据源模式s 所有本地数据源集合组成数据源模式； ( 3 ) 映射m 表示全局模式与数据源模式之间的映射关系，目前主要有 两种定义映射的哇：全局视图映射( o a v ) 表示全局模式中的关系描述为 本地数据源集合的视图；本地视图映射( l a v ) 表示本地数据源中的每一个 关系描述为有关全局模式的一个视图。 2 2 2 数据集成系统的映射机制 在设计数据集成系统时，需要考虑全局模式和数据源之间的映射。目 前定义映射的方法有以下几种1 2 0 。 ( 1 ) 全局视图映射全局模式中的关系描述为局部数据源集合上的视 图。由于视图是依据物化的关系( 表) 定义的虚的关系；因此这里，全局关 系是虚的，并且局部数据源为物化的。在g a v 中，映射肋是由以下一组断 言组成的，如式( 2 1 ) ，式( 2 2 ) 所示。 g 三鲰( s d 跚d s o “r c e ) 谊哟_ g 两)( 2 1 ) 萨似例甜j d 伽p ) 噱确号确)( 2 2 ) 对于爿g 中的每一个元素g ，c s 为s 上的查询。给定源数据库c ，满足与 c 的映射m 的gi - 的数据库b ，如果对于每个g e g ，如式( 2 - 3 ) ，式( 2 4 ) 所示。 旷2 4 铲( s o l l l l ds o u r c c ) ( 2 3 ) g z = ( p s 。( e x a c ts o u i c c )( 2 - 4 ) 给定一个数据源数据库，肘提供关于满足全局模式元素的直接信息。 g 中的关系为视图，查询在视图上表达。 ( 2 ) 本地视图映射在l a v 方法下，每一个局部数据源中的每个关系表 依据全局关系描述为一个视图。更精确的说，在一般情况下，存在物化的 数据源s l ，焉和一个相对于从& ，焉中集成数据的全局模式g 。将研焉 中的关系表看作全局模式g 上的视图，由全局模式上的查询表达式定义。 在l a v 中，映射m 由以下一组断言组成，如式( 2 5 ) ，式( 2 6 ) 所示。 9 燕山大学工学硕士学位论文 眶西g “耐j o “阳p ) v 袁j 国一西g 两) ( 2 5 ) s = - o a ( e x a c ts d “比p ) v b 两i 西g 南)( 2 6 ) 对于凡中的每一个数据源元素s ，西g 为g 上的查询。给定数据源数据库 c ，满足与c 映射关系m 的g 上的数据库b ，如果对于每一个s e s ，如式f 2 7 ) ， 式( 2 - 8 ) 所示。 j 。驴，( s o u n as o u r c e )( 2 7 ) s c = q b a s ( e x a c ts o u r c e )( 2 8 ) 映射脐口数据源数据库c 不提供有关满足全局模式数据的直接信息。数 据源是视图，只能在视图中，基于那些可用的数据回答查询。 ( 3 ) 其他映射机制g l a v 映射m 由以下一组断言组成，如式( 2 9 ) ，式 ( 2 - 1o ) 所示。 5 量西g o o 埘dj d 村阳p ) 咄4 霸中g 南)( 2 9 ) 艇西g ( 唧c rs o “，钾) 咄蛾两；西g 南)( 2 1 0 ) ( p s 为s 上的查询，4 g 为g 上的查询。给定数据源数据库c ，满足与c 映 射关系m f 3 j g 上的数据库b ，如果对于映射肘中的每一个断言，如式( 2 1 1 ) ， 式( 2 1 2 ) 所示。 a 铲a 秽( s o u i l ds o u r c e )( 2 - 1 1 ) 4 铲= 毋g 。( e x a c ts o u r c e )( 2 1 2 ) 映射m ；能提供满足全局模式的有关数据的直接信息，为了回答g 上 的查询g ，需要推断如何使用映射肘来访问数据源数据库c 。 p 2 p 数据集成：在p 2 p 中，不存在全局模式。约束( 仍然称作g ) 定义在 彳g i 4 j il j ，u 爿砌上，映射m 由一组断言组成( 中l 成与0 2 s j分别为在4 所和 彳母上的查询) ：中i s t c t 刍2 s j 。 瓜为彳g 中可以区别的谓词子集，叫做“基本谓词”。一个数据源数 据库是这些基本谓词的数据库。给定数据源数据库c ，一个有关c 的满足 ，的数据库矽是一个对于膨中的每一个断言西l 晚，满足西l t 奶矿的s 上的数据库。 目前主要采用的是全局视图映射( g a v ) 和本地视图映射( l a v ) 两种视 图映射方法。如果采用g a v 的映射方式，那么系统中增加和删除数据源会 1 0 第2 章基础知识概述 非常不灵活，它意味着需要修改全局关系上的定义。而采用l a v 方法时， 由于一个新的数据源仅仅是一个视图的定义，因此在集成系统中增加或者 删除数据源的操作更加灵活。对于查询来说，g a v 方法下的查询过程基于 一组较为简便的展开策略，而l a v 方法下的查询过程则需要经过推理得出。 两种方法各有优缺点，全局视图方式有利于查询重写，但是其可扩展性不 强，增加新的数据源非常困难。本地视图方式恰恰相反，可扩展性非常好， 但是其查询重写实现起来却很困难：另一个好处是其指定数据源的约束条 件也很自然，对于存在数据源数据相互重复、冲突等情况，这种性能是非 常关键的【2 1 1 。因此在集成系统的设计过程中，需要根据实际情况采用不同 的映射方式。 2 2 3 数据集成系统的语义 为了定义数据集成系统的语义，从数据源中的数据开始，详述满足全 局模式的具体数据。一个数据集成系统卢 g s 参上的数据源数据库d 由 s 上的每一个数据源，的关系尸组成。一个数据集成系统，上的数据库b 如果满足以下条件，就说该数据库有关数据源数据库d 合法。 条件1 ，b 满足全局模式g 上的完整性约束； 条件2 ，b 满足关于数据源数据库d 之间的映射m ，也就是说，对于 g 上的每一个关系，b 上的元组集，赋值给r 是元组集合肿) d 的子集， 由d 上的查询反r ) 计算得到。 当视图“r ) 为s o u n d 时，说明由数据源提供的数据只是满足全局模式上 关系的数据的子集【2 2 】。当视图为c o m p l e t e 时，也就是说，对于全局模式 g 上的每一个关系，有p ( ，) 气，当视图为e x a c t 时，对于全局模式g 上 的每一个关系r ，有p ( r ) 如矿。本文主要针对s o u n d 视图进行研究，提出方 法，是数据集成系统中最常见的类型。 根据以上观点，给出数据集成系统的语义定义 2 4 1 如下。 定义2 2 ：给定一个数据集成系统卢 g ，s 务，一组符合数据源模式 转( & ，品 的数据源集合d e d l ， d ，) ，有关数据源d 的数据集成系统， 的语义表示为有关d 合法的，上的数据库集合，记做s e m ( 1 , d ) 。这些合法 燕山大学工学硕士学位论文 的数据库不仅满足全局模式g 上的完整性约束，而且满足与数据源d 之间 的映射。 由定义可知，数据集成系统的语义由一组数据库集合阐释，而不是一 个数据库。 以上介绍了数据集成系统中的基本概念，下面将对数据集成系统的架 构，即数据集成系统的层次以及分类进行阐述，并论述了数据集成系统的 集成过程。 2 3 数据集成系统架构 近年来，随着计算机的普及与网络的飞速发展，可利用的信息资源持 续增长。许多应用需要对多个数据库的信息进行访问，导致用户需要面对 大量的异构数据源。因此许多公司建立数据仓库、数据挖掘或者企业资源 规划系统时需要解决异构数据源的数据集成问题【2 5 1 。 2 - 3 1 数据集成的层次 数据集成是一项复杂的活动，它包括在各个层次上的协同。数据集成 可以分为下述三个层次1 2 6 。 ( 1 ) 数据模型集成异构数据源集成的首要任务就是要为集成系统设 计一个公共数据模型，以对来自不。2 据源的各种数据进行表示，从而便 于进行统一处理。 ( 2 ) 数据模式集成在设计好一个公共数据模型后，问题就集中在如何 协调同一实体或属性的不同表示。例如，两个数据源采用不同的名称表示 同一概念( 如“价格”和“费用”) ，或者相同的名称却表达了不同的含义( 如 “工程”既可表示一个雇员正在从事的工程，也可表示一个雇员监督的工 程) ，或者同一信息采用了两种不同的表示方法( 如“年龄”和“出生日期”) 。 另外，数据源也可以采用不同的数据结构表示相同的信息。例如，两个数 据源依照关系模型组织数据，两者均表示实体“雇员”，但一个仅使用一 张表格存储雇员信息，而另一个则将这些信息分割后存放在多张表格中。 第2 章基础知识概述 这就需要一些工具，能够将异构数据之间的不一致进行协调。 ( 3 ) 数据实例集成在实例层，即基本数据层，集成问题包括如何确认 来自不同数据源的不同对象其实是同一实体；在不同数据源发现相互冲突 的信息时，如何选择数据源( 如表示同一个人的不同的出生日期) 等等。前 者的处理方法是隔离和调和。隔离是保证实体的每次出现都指派一个唯一 标识符。调和是确认哪些实体其实是相同的，并且将该实体的各次出现合 并；至于后者，当目标元素有多个来源时，指定某一个系统在冲突中占据 主导地位即可。 2 3 2 数据集成模型的分类 数据集成是把不同来源、格式、特点性质的数据在逻辑上或物理上有 机地集中，从而为企业提供全面的数据共享。在企业数据集成领域，已经 有了很多成熟的框架可以利用。目前通常采用联邦式、基于中间件模型和 数据仓库等方法来构造集成的系统，这些技术在不同的着重点和应用上解 决数据共享和为企业提供决策支持f 2 ”。在这里将对这几种数据集成模型做 一个基本的分析。 联邦数据库系统( f d b s ) 由半自治数据库系统构成，相互之间分享数 据，联盟各数据源之间相互提供访问接口，同时联盟数据库系统可以是集 中数据库系统或分布式数据库系统及其他联邦式系统。在这种模式下又分 为紧耦合和松耦合两种情况，紧耦合提供统一的访问模式，一般是静态的， 在增加数据源上比较困难：而松耦合则不提供统一的接口，但可以通过统 一的语言访问数据源，其中核心的是必须解决所有数据源语义上的问题。 中间件模式通过统一的全局数据模型来访问异构的数据库、遗留系统、 w e b 资源等。中间件位于异构数据源系统( 数据层) 和应用程序( 应用层) 之 间，向下协调各数据源系统，向上为访问集成数据的应用提供统一数据模 式和数据访问的通用接口。各数据源的应用仍然完成它们的任务，中间件 系统则主要集中为异构数据源提供一个高层次检索服务。 数据仓库是在企业管理和决策中面向主题的、集成的、与时间相关的 和不可修改的数据集合。其中，数据被归类为广义的、功能上独立的、没 燕山大学工学硕士学位论文 有重叠的主题。 这几种方法在一定程度上解决了应用之间的数据共享和互通的问题， 但也存在以下的问题：联邦数据库系统主要面向多个数据库系统的集成， 其中数据源有可能要映射到每一个数据模式，当集成的系统很大时，对实 际开发将带来巨大的困难；中间件模式通过在中间层提供一个统一的数据 逻辑视图来隐藏底层的数据细节，使用户可以把数据源看为一个统一的整 体。这种模型下的关键问题是如何构造这个逻辑视图并使得不同数据源之 间能映射到这个中间层；数据仓库技术则在另外一个层面上表达数据之间 的共享，它主要是为了针对企业某个应用领域提出的一种数据集成方法。 2 3 3 数据集成的过程 多源异构数据的集成包括三个步骤【2 8 l ：清洗、匹配和合并。在数据清 洗过程中，须对数据进行解析、校正、标准化、增补等一系列的处理，为 数据的精确匹配做准备。通过在各数据源内部或各数据源之间对数据进行 比较，获取所有相似信息，消除重复数据，最终实现对相匹配的各数据成 份进行合并，如图2 1 所示。 图2 - 1 异构数据集成过程 f i g u r e2 - 1p r o c e s so fi s o m e r i z a t i o nd a t ai n t e g r a t i o n 数据集成的目的是运用一定的技术手段将系统中的数据按一定规则组 1 4 第2 章基础知识概述 织成为一个整体，使得用户能有效地对数据进行操作。处理的主要对象是 系统中各种异构数据源中的数据。它们的不相容性表现在值的不同类型、 代码或值的约定、概念的解释以及不同模式中表示的不同概念集合。集成 异构数据源需要用到多种工具和技术，利用它们可以将异构数据进行统一 的表示、存储和管理【”。 2 4 数据集成研究的关键问题 在数据集成系统中，在创建虚拟的全局模式及其与下层数据源模式之 间的“映射关系”后，用户在全局模式上提出“查询请求”，系统将查询 请求按照映射关系转换为对应下层数据源模式的“子目标”( 称之为“查询 重写”) ，而后进入子目标的“执行”，重写和执行过程中都可能存在“优 化”，子目标并不是直接运行在下层数据源系统内，而是通过一个“封装 器”间接地和下层数据源交流，最后系统将每个子目标执行结果整合为统 一结果，按照用户要求或系统设置格式提供给用户。 数据集成系统遇到的主要问题【3 0 l 集中在建立语义联系，查询重写，查 询优化和查询执行中，核心和基础是建立语义联系。 2 4 1 语义联系 语义联系是多模式应用( 数据集成、语义w e b 、数据移植、实体整合1 中的一个基础性问题，在数据集成系统中，它是用户查询和下层数据源数 据建立联系的唯一桥梁。 使用最多的语义联系方式是采用映射，其终极目的就是获得一个正确 的、满足应用要求的映射，文献 3 1 提出了一种映射框架，对其性质作了 研究。 定义2 3 ：映射乃，乃分别是定义在语言工l ，工2 中的模式，乃，乃之 间的映射坂可能存在一个帮助模式乃定义在语言三3 内) 就是建立在( 乃， 恐) ，( 乃，乃) 或( 乃，乃) 之上的规则的集合。 映射语义就是对两个模式之间的元组所实施的约束，决定了在给定映 燕山大学工学硕士学位论文 射下哪些元组对可以共存。一个映射能否满足特定的主题要求必须具备三 个条件：清晰语义，对不完整信息的适应性和允许模式异构。映射有三个 重要的属性：查询回答能力，映射推理能力和映射整合能力，决定了用映 射表达语义联系的能力，并有下面的结论。 ( 1 ) 查询回答能力确定映射能不能回答查询p 是个n p 完全问题； ( 2 ) 映射推理能力判断某个规则是否符合指定的映射语义是一个n p 完全问题； ( 3 ) 映射整合能力判断两个映射的整合结果是否满足指定的映射语 义是n p 完全问题。 2 4 2 查询重写 查询重写是利用语义联系，将建立在全局模式上的查询用且仅用下层 数据源的资源描述来重新表述。全局模式采用不同的描述方式对应着不同 的查询重写方式，前面提到l a v 方式引入了一个关键难题：利用视图来回 答查询的问题。该问题在不同的应用领域都有不同的侧重点，它有三种输 出结果：最终查询结果、查询计划和查询重写形式。文献【3 2 将其分为两 类：基于代价重写和逻辑重写，前者用于查询优化和保持物理数据独立性； 后者用于数据集成，并可分两类，获取重写的算法和直接获取查询结果的 算法。 数据集成中的查询重写有几个特点需要注意：第一是涉及的视图数量 非常多，其次视图定义中可能包含非常复杂的谓词逻辑，第三数据源的数 据往往是不完整的，即数据源只包含部分满足视图定义的数据。 查询重写算法主要有以下三种。 ( 1 ) b u c k e ta l g o r i t h m 算法主要的想法是先单独考虑每个子目标，确定 哪些视图和子目标相关，从而达到显著减少重写个数的目的。算法分为两 个阶段，第一阶段确定b u c k e t 中的视图；第二阶段根据b u c k e t 中的视图 写出查询重写表达式。 佗) i n v e r s er u l e sa l g o r i t h m 算法思想是构建一个由反转视图定义后形 成特殊规则的集合。反转规则是将l a v 的描述方式变换成g a v 的描述方 1 6 第2 章基础知识概述 式。查询可以按照反转规则直接展开，返回的是最大包含重写。算法最大 的优点是概念非常清楚而且很容易模型化，另外获得最大包含重写的时间 开销是相对于视图和查询大小的多项式。该算法的缺点有两个：反转规则 会包含一些对查询没有意义的视图，需要在算法中利用单独过程来消除无 用视图：没有充分利用已经物化的视图，从而丧失了很多计算上的优势。 ( 3 ) m i n i c o na l g o r i t h m 算法的关键思想是考虑查询中的每个变量如何 与视图中的变量相互作用，因此该算法在第二阶段需要考虑的视图组合显 著减少。m i n i c o n 算法的