（计算机应用技术专业论文）基于rcm的异构数据源集成统一数据模型.pdf

太原理工大学硕士研究生学位论文 新内涵信息库并返回两个操作信息集合，即映射集合和视图集 合。其中映射集合记录了构建统一表达过程中对目标数据源所 做的转换操作，视图集合用于获得统一表达概念的实例，二者 极大地提高了对异构数据源信息访问的透明性。最后，文章就 本方法的误差稳定性、正确性和完备性的平衡及时间空间复杂 度作了分析。 关键词：异构数据源，数据集成，x ml ，r c m ，c d m i i 太原理工大学硕士研究生学位论文 ad a l am o d e l0 fh e t e r o g e n e o u s d a ：i a i n t e g r a r l 0 nb a s e do nr c m a b s t r a c t w i t ht h e d e v e l o p m e n t o f c o m p u t e r n e m o r kt e c h n o l o g y ， e n t e r p r i s e s s t a r tt o d e v e l o pm a n ya p p l i c a t i o ns y s t e m sb a s e d o n v a r i o u ss o f t 、a r ea n dh a r d w a r e p l a t f o r m ，c o n s e q u e n t l ym a n y a b u n d a n td a t as o u r c ea r ea c c u m u l a t e d ，i n c l u d i n gs t r u c t u r e dd a i ai n d a t a b a s e ，n o n s t r u c t u r e dd a i ai n f i l es y s t e m ，a n ds e m i s t r u c t u r e d d a t ai nw e bs e r v i c e i nt h es a k eo fa v o i d i n gr e c o n s t r u c t i n ga n d w a s t i n go fd a t as o u r c e ，e n t e r p r i s e s a r ee a g e rt oi n t e g r a f et h e s e h e t e r o g e n e o u sd a t as o u r c e ，w h i c h a r es e p a r a t e di nt h el o c a t i o n s a n ds e l f m a n a g e m e n ta n dh e t e r o g e n e o u si nd a t am o d u l e t h i s p a p e r d i s c u s s e st h e p r o b l e m s i n h e t e r o g e n e o u s d a t a i n t e g r a t i o na n d a na p p r o a c hi s p r o p o s e df o rd e r i v i n gag l o b a l r e p r e s e n a t i o n o fd a t a s o u r c e s h a v i n g d i f ! | e r e n ff o r m a t sa n d s t r u c t u r e s t h ep r o p o s e da p p r o a c hi sb a s e do nt h ee x p l o i t a c i o no fa i i i p a r t i c u l a rc o n c e p t u a lm o d e lf o rb o t hu n i f o r m l yr e p r e s e n t i n gs u c h ( 1 a t as o u r c e sa n dr e c o n s t m c t i n gb o t ht h e i ri n c r a s o u r c ea n dt h e i r i n t e r s o u r c es e m a n t i c s a l o n g 、i e i lt i l e 9 1 u b a ll p r 。6 。n t a t i o l ，。“ a p p r o a c hr e t u r n st w os u p p o r ts t r u c t u r e sw h i c hi m p r o v et h ea c c e s s t r a n s p a r e n c yt os t o r e di n f o r m a t i o n ，i e as e to fm a p p i n g s ，e n c o d i n g t h et r a n s f b 蛐a t i o n sc a r r i e do u t d u r i n g t h ec o n s t m c t i o no ft h e g l o b a l r e p r e s e n t a t i o n ，a n das e to fv i e w s ，o b t a i n i n gi n s t a n c e so ft h e c o n c e p t s o ft h e g l o b a lr e p r e s e n t a t i o nf r o m i n s i a n c e so ft h e c o n c e p t so ft h ei n p u td a i as o u r c e s k e y w o r d s ：h e t e r o g e n e o u sd a t es o u r c e ， d a t ai n t e g r a t i o n ， x m l ，r c m ，c d m i v 太原理工大学硕士研究生学位论文 第一章前言 随着计算机网络的普及，数据资源的共享己经成为一个热门话题。传 统的数据库集成方法现在己经远远不能适应人们获取数据的需求，因此迫 切需要一种新的数据集成系统。这种系统不仅能集成传统的数据库中的结 构化数据，而且还可以集成在w e b 上应用日益广泛的半结构化数据和非结 构化数据。在这种背景下，异构数据集成系统受到越来越多人的重视，这 方面的研究包成为当前数据集成研究的一个热点。 1 1 研究背景 本文研究用于决策支持d s s ( d e c i s i o ns u p p o r ts y s t e m ) 的异构数据集 成技术。该题目的应用背景是由省军区国防动员办和省计委国民经济动员 办委托开发的“山西省医疗卫生动员决策支持系统”。医疗卫生动员是国 防动员的重要组成部分之一，研究旨在确定在大型、分布式复杂系统当中， 中间件子系统划分的层次、位置、功能和它们的胶水作用，分别丌发和集 成用于决策支持的中间件子系统。中间件子系统包括五个部分：1 ) 统一数 据存取中间件：2 ) 特定领域d s s 业务逻辑中间件；3 ) 应用通信中间件： j ) 数据库，方法库，模型库维护中间件。 现有d s s 系统结构可以有以下三个层次模式来描述： 1 )“用户服务级”提供用户和系统进行交互的能力，完成用户与系 统的各种交互操作，并创建问题决策任务。 2 )“业务服务级”则是系统设计和实现的核心工作，它由各四个库 予系统组成，作为系统的中间件。当业务服务级接收到用户级的 任务后，对这个任务进行划分，创建不同库体进程，通过这些划 】 太原理工大学硕士研究生学位论文 分利用数据服务级提供的数据支持完成分布式计算。 3 )“数据服务级”完成对决策支持数据的存贮管理，为系统提供数 据支持。 本文阐述的技术就是定位在“数据服务级”的统一数据存取中间件的 内部实现机制：d s s 及g i s 应通过统一数据存取中间件访问或集成这些 地理上分布、管理上自治、模式上异构的异构数据源，建立在数据源逻辑 层上统一的访问界面，实现异构数据的分布式共享。 1 2 异构多数据源系统的研究现状 异构数据源集成系统除了集成具有规则结构( w j l l s t m c t u r e d ) 的数据 之外，还需集成来自w w w 等数据源的半结构化( s e m i s t r u c t u r e d ) 数据， 包括声音、图形多媒体信息、w w w 上的h t m l 文件等其它格式的文件。 这些数据源模型不同，给系统集成带来了许多问题。 目前，解决异构数据源互连接的方法一般有3 种： 1 ) 分布式数据库，其基本思想是抛弃原有的数据库系统，在网络环境下 建立分布的数据库系统，在体系结构，事务处理模型等方面重新设计， 从而解决信息共享与互操作问题。 2j 联邦式数据库，它是由一组能协调工作，又可独立自治的部件数据库 组成。它可以是原先不分布的，又可以是分布的。它具有分布性、异 构性、自治性3 大特征。 3 ) 在原数据库上进行扩充，具体地又可分为如下两种： a ) 数据库网关( d a t a b a s eg a t e w a y ) ，数据库网关是一种中继器，它能 提供应用级的数据库互连的手段。网关的主要作用是转换和通信。 转换包括模式转换、操作变换等。数据库网关可建立稳定和透明 的连接。但该方法存在有如下局限：仅仅能完成特定的数据库 2 太原理t 大学硕十研究生学位论文 查询语言到另夕 一种特定的数据库查询语言的同等转换，并不涉 及如何屏蔽数据库之间的异构性；不支持事务处理，没有提供 并发控制和事务处理能力：用户受制于特定的数据库。 b ) 中间件技术( m i d d l e w a r e ) ：即几个后台数据源和前台应用之间建 立一个抽象层。使系统对每个不同数据源的操作变为对单一的中 间件的操作，而后再由中问件进行异构处理。 对于一个理想的、通用的异构数据源连接模型，结构应该是基于中间 件技术，因为中间件不仅能使前端用户访问后台的异构数据源实现透明 化，并保证了访问接口的开放性。这样可以使以后的系统功能扩展很方便。 采用这种结构可以避免为每一种数据源连接到w e b 开发接口。 因此本文采用中间件技术以图解决异构数据源集成访问问题。 1 2 1 主要研究问题 在多数据源系统中，如何有效解决数据分布的异构性，实现客户访问 的透明性，同时还要保持局部系统的自治性，是本系统考虑的主要问题。 1 ) 异构性：多数据源系统面临的最大挑战是如何解决局部数据源系统的 异构性。目前，各企业信息典型地分布于多个异构数据库管理信息系 统中，因此需要在这些系统之上共享和访问数据，异构性基本分为如 下三级： a ) 平台异构性：各数据管理系统驻留在不同的硬件平台之上， 使用不同的操作系统，用不同的通汛协议进行通讯。 b ) 数据库管理系统异构性：成员数据库具有不同的d b m s ，如文 件系统、关系以及面向对象数据库管理系统等。它们可能使 用不同的数据模型，提供不同的数据元语，例如：相同的信 息在关系模型中用关系表达，在网状模型中用记录类型表达， 3 太原理工大学硕士研究生学位论文 不同的数据模型可能支持不同的限制和不同的数据语言。 c ) 语义异构性：不同的成员系统中相同或相关数据在含义、解 释和用途方百下蔑；由于不同的局势数据库是独立设计和开 发的，在参加集成的局部数据库之间可能会产生各种语义冲 突，包括模式冲突和数据冲突。 2 ) 透明性：透明性与系统解决异构性的程度相关，决定系统的功能和使 用的方便性。包括平台透明性、系统透明性、数据源透明性和语义透 明性。 a ) 平台透明性：隐藏了硬件平台、操作系统和通讯协议等各种 数据源所基于的平台间的差异。对于用户来讲，每个敛据源 像是在同一个硬件软件平台上。 b ) 系统透明性：当数据源的数据管理系统、数据模型和语言问 的差异被隐藏时，对用户来讲，每个数据源像是用同一个数 据模型来描述的、由同一个数据管理系统和数据语言来管理 和维护的。 c ) 数据源透明性：隐藏了数据源的描述信息，由系统解决诸如： 豢据的存储置，数据如片议查询。用户所见到的只是一个 逻辑数据源。 3 ) 自治性：指每个局部数据库管理系统具有对局部数据库和局部处理的 完全控制能力。成员系统能够决定其是否提供和提供多少它的功能和 资源与其它成员系统共享。这包括成员系统有权决定何时加入或退出 整体而不受全局系统的任何约束和限制。与分布式数据库系统相反， 自治性是多数据库系统所要求的一个重要特征，是多数据库系统的主 要动机。它保证了局部数据库系统以最小的局部影响来加入和退出多 数据库系统。 4 太原理t 大学硕士研究生学位论文 1 2 2 研究现状 信息集成平台的实现主要采用多数裾库集成技术。多数据库集成系统 支持用户使用单一数据定义和操作语言，同时访问蓑鼻私琚时腆温罐? 研 唯超幡洲降埋馐琵k 囊点黪稚强磐象髫： ； 萋2 ；i 璐g 妻醵崩餐鲣移 曼i 辜t ；g 目；i i 噔湃凋塌m 磷孺巍0 描也班驰够舀萋菇 0 薹2 i 精蓦羹菱冀量毒 嘎捌悌型馐群 k u b a 大学的h i r o n o r im i z u g u c h i 等人 提出的公共数据模型w 曲n r s d 。它是基于嵌套的关系数据模型，提供嵌 套的关系代数操作。w 曲n r ，s d 的一个特点就是提供了一个名为 s d ( s tr l l c t u r e dd o c u m e n it y p e ) 类型的抽象数据类型，用来存储和管理半 结构化文档，如x m l ，s g m l 和h t m l “。基于这种数据模型的系统比 较容易实现，但由于它是基于嵌套的关系数据模型，主要缺点仍是不能保 证客观世界中实体的确定性，实体的引用只能通过码和数据冗余来达到 ：“ o 由于o d m g ( o b j e c td a c a b a s em an a g e m e n tg m “p ) 对象数据模型具有 很强的数据表示和描述能力，s t a n f o r d 大学的t i r t h a n k a rk h i r i 等人使用 o e m ( o b i e c e x c h a n g em o d e l) 模型扩展了o d m g 对象数据模型和它的查 询语言o o l ( o b j e c lq u e r yl a n g u ag e ) ，使之能够表示数据中的半结构化部 分，以便允许结构化和半结构化数据可以在同一个物理库中自由地混合 ”。，扩展的o q l 查询语言可以处理这种混合数据( h y b r i dd a c a ) 。这科t 方 法集成了0 d m g 和o e m “”两种数据模型的优点，可以很好地解决结构 化和半结构化数据的集成问题，但是对非结构化的数据描述仍然存在一定 的问题。 东南大学的王宁等人在“一个基于c o rb a 的异构数据源集成系统的 太原理工大学硕士研究生学位论文 构数据集成的公共模型。在这种对象模型中，每个对象由四元组 表示，其中0 i d 表示对象标识符，d 表示对象名，t 表示对象类型， v 表示对象值。t 除了可表示基本数据类型如i n c e g e r ，c h a r ，f l o o e ，5 t r ：n 叠 等外，还可以表示集台数据类型如s e t ，l i s t ，b a g 等、可变长数据类型t e x t b l o b 和引用类型r e 。该模型通过对象集成查询语言o i q l ( o b i e d i n t e g r a t i o nq u e r y 匕n g u a g e ，s q l 语言的扩充) 来实现各科：操怍。o i m 数据模型具有自描述的特性，它的每个对象都含有描述符，因此特别适合 于描述那些没有显式模式或者模式无法预知的数据对象：该数据模型支持 对象标识和对象之间的引用关系，却不强调分类，这一特点使得集成系统 能够方便的处理来自各数据源的异构数据【1 3 i ，i ；统的数据模型支持的分 类在o l m 数据模型中通过对象之间的引用关系也可以实现：该数据模型 是异构数据壤成系统的公共数据模型，它仅在逻辑上统一救表示来自各数 据源的异构数据，至于对象在各数据源上如何存储，与o i m 数据模型无 关。 1 ，4 公共数据模型的选取 公共数掘模型应满足四方面的要求：一是能比较真实的模拟现实世 界；二足数据集成自动化程度高：三足容易为人们所理解；四是便于在计 算机上实现。我们通过分析数据描述能力、操作语言等方面的能力，对上 述几种异构数据的公共数据模型作了分析比较提出了一个基于带根连通 有向图的异构数据集成方法r c m ( r i c hc o n c e p tm o d e l ) 网络概念模型并 认为它更适合作为异构数掘集成的公共数据模型( c o r 玎m o nd a t am o d e l ) 。 8 太原理工大学硕士研究生学位论文 第二章r c m 网络概念模型 要实现一个可扩展的异构数据源集成系统，除为各数据源定义标准界 面外，尚需寻找一种通用的、便于异构数据源集成的统一数据模型。这种 数据模型既要能够自然地描述各种数据源的数据，又耍能够方便地表示来 自各种异构数据源的异构数据，因而必须具有很强的描述能力。从这种意 义上说，多库系统中常用的标准模型，如关系模型、e 瓜模型乃至传统的 面向对象模型都显得不合适。因为在这些模型中，元数据和数据是分开存 放的，不仅难于表示那些没有预知模式的数据源中的数据，在表示从各个 异构数据源集成的数据时，也显得不够方便。 本文提出一种便于异构数据源集成的统一数据模型r c m 网络模型。 在此，引入带根连通有向图“3 瑚3 的概念基础上建立r c m 模型，进而讨论 r c m 网络概念模型。 2 1r c m 网络概述 r c m 网络是一种描述数据源的概念模型，可以对现存大部分数据表达 格式进行统一建模，得出并表示数据源内部和数据源之间的语义关系。 我们用一个带根的标签图( 即r c m 网络) n e t ( d s ) 表示一个数据源d s ( d a t as o u r c e ) ： n e t ( d s ) = ( n s ( d s ) ，a s ( d s ) = n s ( d s ) 是一个节点集合，每一个节点表示数据源d s 中的一个概念并通过它 所表示的概念名称标识。n s ( d s l 中的节点被划分成两个子集，即，原子节 点集n s a ( d s ) 和复合节点集n s c ( d s ) 。如果一个节点的出度为0 那么它就是 原予节点，否则为复合节点。既然一个r c m 网络节点表示一个概念，从现 9 太原理工大学硕士研究生学位论文 在起我们将术语r c m 网络节点和概念互换地使用。 a s ( d s ) 表示个弧集，一个弧表示两个概念之间的关系。个从节 点s 到节点t 的弧a 标识为 ，表明概念s 关联于概念t 。节点s 被 称为弧a 的源节点，而节点t 是弧a 的目标节点。 标签b t 是一个二元组 d s t ，r s t ，d s 卉口r s t 的取值在实数区间 o ，1 。其 中，d s t 称为语义距离系数；它用来指示目标节点t 表示的概念与源节点s 的 概念在语义上相近程度，换句话说，它表达了目标节点t 相关的概念刻化源 节点s 所表示的概念的程度。例如，在e ，r 模式里，一个属性a 比起另一个实 体e l 在语义上更近似于相应的实体e ( 实体e 和实体e l 之间有关系r ) ，类似 地，在x m l 文档里，元素e 的子元素e 1 比起另一个元素e 2 语义上更近似于 e ( e 通过i d r e f 属性引用e 2 ) 。这就是说e ，r 模式中的属性用来描述实体的性 质，关系描述相同模式中实体间的交互( x m l 中，子元素用来描述元素的性 质，i d r e f 属性描述x m l 文档中元素间的交互) 。r s t 称为语义相关系数，表 示源节点s 概念实例数的一个分数，它的完整定义要求至少存在一个目标节 点t 概念的实例。 图2 一l 所示为关于一个描述大学数据源的r c m 网络例子。为了简化布 局，图中灰色节点表示进入灰色节点的孤山进入有相同名称的白色节点。 r c m 网络节点如p r o f e s s o r ，c o u r s e 和s t u d e n t 表示相关的概念，弧 表明教授和电话问存在关系。该弧的语义距离系数幽 是o 3 8 ，说明p h o n e 与p r o f e s s o r 的依存度为3 8 ：语义相关系数r 。，是l ，说明 1 0 0 的教授都有电话。图中，每一个节点的系数表示节点所代表概念实例 的个数；每一条目& 圆括号中的系数是所谓弧的相关实例数；这表示源节点 实例的个数。图中弧线下面括号内的数字仅仅为了表示清楚起见，并不是 模型的一部分，它可以山相关源节点的实例数乘以语义相关系数得出。 1 0 太原理工大学硕士研究生学位论文 ：“鼍i ：薯警浮j i 譬7 f 漤一去一。 “”留 t 潞。口、 。屯笱o 甄。”剖 “简守港! 7 14 蹙氛，躲 n 娶喘。e t 惴”吃、：茹l 二爹逸鞫? 等 m ”：。谕 蔹 。帛 “警每誊” 太原理工大学硕士研究生学位论文 c d s h o r t e s t j a t h ( c o n d i l i o n a ld l s h o n e s t - p a t h ) 为连接n 和n 并包括 弧a 的最小路径语义距离。如果有两冬以上的最小路径语义距离， 那么选择它们问路径语义相关值最大的那条路径。 定义2 5 给楚一个数据源d s 和相应的r c m 网络n e t ( d s ) ，节点x n e t ( d s ) 的第i 个邻居为： n b h ( x ，i ) = a 1 a a s ( d s ) ，a = ，x ，y ja i sad - p a t h 。， x ? y ) i 兰o 如果存在一条包含弧a = 由x 到y 的c d s h o r t e s t | p a t h 并且此路径 为d p a l h 。，那么弧a = 属于n b h ( x ，i _ ) ；注意，a 圣n b h ( x ，j ) ， j ， ， ， ， t ( p r o j e c t ，s t a n i n g d a t e ，【o ，0 5 1 ， ， 1 2 太原理工大学硕士研究生学位论z t ， 例如，a 一 属于n b h ( p r o f e s s o r ，1 ) 因为p r o f e s s o r ，s t a r t i n g d a t e ja 是一个d p a t h l 如并且p r o 是s s o r ? s t a r t i n g - d a t e 。同 样地，可以推导出相关u xr c m 所有其它邻居。 基本上任何数据源都可以被表示成概念集合和这些概念之间的关系。 然而，目前可以得到的数据源大多从语法到语义以及表达格式上都是异构 的：甚至还有一些是多媒体形式的数据。r c m 网络模型能够处理较多的异 构数据但它目前还不能管理多媒体信息。我们可利用模型抽象数据源问的 属性，支持语法和语义异构的管理。 至于数据表达格式的异构问题，我们看到目前一些数据源数是完全结 构化的如关系数据库，而另一些是半结构化的如0 e m 图和x m l 文档，还有 一些是非结构化的，如记录文档。r c m 网络模型通过语义距离和语义相关 系数的办法能够处理不同结构程度的数据。大多数现有的数据表示格式如 关系数据库，记录档案和h t m l 文件能被转换成职模式或x m l 文档，最后 都可以被转换成r c m 网络模型表达的数据。 2 2 从x m l 文档构建r c m 网络 2 2 1 定义r c m 网络节点 数据源的r c m 网络n e t ( d s ) 的节点集n s ( d s ) 是两个集合复合节点集 n s c ( d s ) 和原子节点集n s a ( d s ) 的并集，d 为一个x m l 文档数据源。 为了获得n s ( d ) ，我们检查相关d 的d t d ( d 。c u m e n it y p ed e f j n j t i o n ) 文 件。n s c ( d ) 中的每一个节点由d t d 的非终结元素获得：”m “。反之，n s a ( d ) 从d t d 中的属性或者终结元素得到，不包括下面这些情况： 1 ： 太原理工大学硕士研究生学位论文 1 ) 由于i d r e f 和i d r e f s 属性指示元素间的连接它们没有相应节点， 用n e t ( d ) 中的弧表露。 2 ) 如果不同元素的两个或以上的属性有相同的名称，它们在n e l ( d ) 中用 唯一的n s a ( d ) 节点表示。 3 ) 如果属性的名称与终结或非终结元素相同，它在n e t ( d ) 中用相应元素 的节点表示。 最后，r c m 网络中每个节点的实例数根据) ( m l 文档中相应概念的实例数 得出。 2 2 2 定义r c m 网络弧 奉肯我们阐述怎样从d 中得出n e t ( d ) 弧集a s ( d ) 。下面我们用相同的符 号标识d 中的元素( 或属性) 和n e t ( d ) 中相应的节点。 a s ( d ) 是集合a s n ( d ) 集合a s r ( d ) 的并集。属于a s n ( d ) 的弧称为嵌套弧， 从嵌套关系中得出。如果( i ) t 是元素s 的予元素；或者( i i ) t 是相关元素s 的属性，它的类型不是i d r e f 和i d r e f s 类型，那么就添加弧 到 s 、r d ) 中： 属于a s r ( d ) 中的弧称为引用弧，从元素s 中的i d r e f 和i d r e f s 属性导 出。特别当给定元素s 的i d r e f 和i d r e f s 属性( 引用一个或更多元素t 的实 例) 时，在r c m 网络上用引用弧连接节点s 到节点t 。由于i d r e f 和i d r e f s 属性没有被标出来，仅有a s r ( d ) 中弧的源节点从d t d 被导出；为了确定目 标节点，我们需要分析x m l 文档。 2 2 3 定义关联r c m 网络弧的标签 下面我们使用术语“概念”指示定义在d t d 文件中的元素和属性，称 1 4 太原理工大学硕士研究生学位论文 q c o m p ( o ，) ，q ? p ，p 和q 是终结元素并且不存在r 使得 r n s t ，r c o m p ( o ) ，r 是非终结元素或者是被o 的 i d r = f 或嵩l d i t e f s 属陛弓i 鬲j j 对象 ? x m l ( o i ，t ) = 1如果| p 使得p n s t ，p c o m p ( o ，) ，并且p 是非终结元 素或者是被o 的i d r e f 或者i d r e f s 属性引用的对象 d s 定义是基于如下考虑：属性直接定义了元素的性质，所以它本身就 是元素的一部分，二者的语义距离为0 。一个终结予元素可以直接定义相关 的概念反之一个非终结子元素则借助它的子元素集合定义相关的概念。 这样，给定一个属于r n s st 的对象o ，属于n s t 和c o m p ( o ) 的终结子元素o + 相比属于n s t 和c o m p ( o ) 的非终结子元素o ”从语义上来说更近似于对象o 。 如果有两个或者多个同样名字的终结子元鬃是同样元索o 的构件，单其中之 一不足以完全确定一个给定o 的性质，而只有它们全体才能确定元素o 的性 质。般地，i d r e f 和i d r e f s 属性表示元素间的引用关系：有i d r e f 和 i d r e f s 属性的元素o 和被引用的元素间的语义距离可以被认为与非终结元 豢m j 毫义的语义距离相同。 语义相关系数r s t 定义如下： l 嬲s r m 卜两 ( 2 2 ) 即，概念s 的定义中概念t 的参与 在某些情况下，r s t 能够通过利用下面的性质被立即获得。 性质2 ，2 3 1 当t 是# r e q u i r e d 属性，或者t 是一个有默认值的属性，或 者是一个d t d 中运算符+ 关联的子元素时，语义相关系数r s t 等于l 。 从x m l 文档构建r c m 网络的时间复杂度是实例数的二次方，执行相同 1 6 太原理工大学硕士研究生学位论文 _ _ _ 一一一 一 任务的空涮复杂度是个常量。 从x m 墓熊缆灌爆善雾筑蔓砖野射斟耵斟”吩j 转瓠蜓囊m 燃骢茁昌i 妻荔 瞬需娶篓翠薹迁萋n 删嚣郅誊君雾甄莲潞翳錾零绑戳篓二瑟薹露呵撂颂錾er ) 由两个节点集合的并集构成： n s ( e r ) = n s c( e r ) u n s a ( e r ) 其中n s 。正砷足复合董集，n ：。( e 内是愿j 节点集：为e r 中0 ：每一个 帽同名称m 的属性集合刨建一个n s 。( e r ) 节点m ，为e r 中的实体或者 每个多对多关系创建一个n s c ( e r ) 节点。 必须经过考察有关数据库中相关概念的实例得出每个节点的实例数。 为了获简化r c m 网络结构推导过程，属性没有包含在e r 图中的一对一 和一对多和多对多关系并没有在n e c ( e r 、中的节点表达出来。 2 3 2 定义r c m 网络孤和标签 设e r 为e r 模式并且n e t ( e 鼬为相应的r c m 网络；通过考察( i ) e ，r 模式表示一个结构化的信息源，为了简化a s ( e r ) 的标签计算所有的实体 实例何棚同的结构；( ii ) 一对一，一对多和多对多关系用r c m 网络的弧 表示，我们得出n e t( e r ) 的r c m 网络弧集合a s ( e r ) 和标签的规则。 通过运用下列规则，可以构造n e l ( e r ) 的弧和相应标签： 1 ) 从实体到它的每个属性有一条弧：因为实体的每一个实例确实关联一 个属性的实例，设置这 x 太原理工大学硕士研究生学位论文 0 s sr e a s o n i n g ( t i c l e t a i y u a n t a i y u a n 大学w e b 站点的x m l 文档的d t d u x 如下： 太原理工大学硕士研究生学位论文 ( ! d o c l 吖p e u n i v e t s i t y ( ! e l e m e n t e m a i l ( 舞p c d a t a ) ( ! e l e m e n ta r g u m e n t ( 撑p c d a t a ) ! a t t l i s ts 【l l d e n t l di d 挣r e q u i r e d n a m ec da = i t a 毒r e o u i r e d b i n h d a 【ec d a t a 舟i m p l i e d b i r 【h p l a c ec d a t a 舟i m p u e d e n r o l l m e n t y e a rc d a t a 群f m p l i e d e x a m si d r e f s 箨i m p l i e d a t t e n ( i e dc o u r s e si d r e f s 群i m p l i e d 2 0 太原理工大学硕士研究生学位论文 此外，当引用到从e 瓜模式转化后的r c m 网络时，将使用实体、关系和 属性指代相应实潍的r c m 网络节点、关系和慝性。 二j 1 定义r c m 网络节点 由e 瓜模式获得r c m 网络n e t ( e r ) 节点集合n s ( e r ) 的规则类似于虫 x m l 文档d 得出r c m 网络n e t ( d ) 和n e t ( g ) 的节点集合n s ( d ) 和n s ( g ) 的规则。集合n s ( e r ) 由两个节点集合的并集构成： n s ( e r ) = n s c ( e r ) un s a ( e r ) 其中n s 。正砷足复合董集，n ：。( e 内是愿j 节点集：为e r 中0 ：每一个 帽同名称m 的属性集合刨建一个n s 。( e r ) 节点m ，为e r 中的实体或者 每个多对多关系创建一个n s c ( e r ) 节点。 必须经过考察有关数据库中相关概念的实例得出每个节点的实例数。 为了获简化r c m 网络结构推导过程，属性没有包含在e r 图中的一对一 和一对多和多对多关系并没有在n e c ( e r 、中的节点表达出来。 2 3 2 定义r c m 网络孤和标签 设e r 为e r 模式并且n e t ( e 鼬为相应的r c m 网络；通过考察( i ) e ，r 模式表示一个结构化的信息源，为了简化a s ( e r ) 的标签计算所有的实体 实例何棚同的结构；( ii ) 一对一，一对多和多对多关系用r c m 网络的弧 表示，我们得出n e t ( e r ) 的r c m 网络弧集合a s ( e r ) 和标签的规则。 通过运用下列规则，可以构造n e l ( e r ) 的弧和相应标签： 1 ) 从实体到它的每个属性有一条弧：因为实体的每一个实例确实关联一 个属性的实例，设置这个弧的语义距离系数为0 ，语义相关距离系数 为l 。 太原理工大学硕士研究生学位论文 2 ) 如果r 是从e j 到e j 没有属性的关系，用从e 到e j 的弧a q 和从e j 到e 的弧a j 表示。a u 和a j ，的语义距离系数为1 而a “a j ，) 的语义相关系数等于e j ( e ，) 实例的分数，其中弧a 至少连接一个e 实例。 3 ) 如果r 是一对一或者一对多关系( 包含属性) ，它能被转换为前一个情形。 4 ) 如果r 是多对多关系( 包含属性) ，用r c m 网络复合节点来表示。在n e t ( e r ) 中有从e j 到r 的弧a ”从r 到e j 的弧a 6 ，从e j 到r 的弧a j ，和从r 到e 的 弧a 小所有这些弧的语义距离系数为1 ；由于r 的每一个实例连接到一 个e j 或者e 。实例，所以a d 或者a 的语义相关系数为l 。a i ，或者a j ，的语义 相关系数等于e 或者e i 的实例分数。 最后，设e ，和e i 为e r 中的两个实体使得从e 到e i 存在一个i s a 关系。这 个特殊关系在n e t ( e r ) 中转化为一对弧：由于e i 的知识对于刻画e 是必要的 如e ，的属性被e j 继承，第一条弧从e j 到e ，的语义距离系数等于0 ；因为已的每 一个实例要求一个e 。的实例，所以语义相关系数等于l 。由于e 的知识对于 刻画e 【是不必要的，第二条弧从e 。到e ，语义距离系数为1 ，语义相关系数等 于e 的实例数于e 的实例数之比。 从x m l 文档构建r c m 网络的时间复杂度是实例数的线性关系，空间复 杂度是一个常量。 从e r 图构建r c m 网络仅仅依赖图的结构特征；它可以自动地用解析器 执行，不需要人工干预。 例如，图2 2 描绘的是e r 图u e ，r ，表示一个关于大学数据库概念图 s c h e m e 。- 目应地r c m 网络u er c m 如图4 一l 。 2 3 太原理工大学硕十研究生学位论文 s t u d e n t 一、u m b e r v e r d 蚪一i r k 幽2 - 2 大学数据日r 幽，f r f 嘻2 - 2 n e 矾曲g r a m u nr e l a t i v e i oau n i v e 础y 2 4 太原理工大学硕士研究生学位论文 第三章数据源间性质的推导 构建异构数据源的全局表达必须进行数据源语义上的定义，而数据源 间性质一术语上，结构上和语义性质的知识是定义数据源间语义的重要基 础。1 “”。本文所采用方法基于r c m 模型的三个数据源问性质定义如下： 同义词两个分属不同数据源且具有相同的含义的概念； 多义词两个分属不同数据源且具有相同的名称但含义不同的概念； 子网相似如果两个分属不同数据源的两个局部网络所表示的含义相 同，可以说这两个子网表达的概念相同或简称子网相似。 3 1 同义词和多义词 提取概念问同义词和同形词可能涉及两个不同数据表达格式数据源d s l 、d s 2 和一些存储在同义词词法属性字典( l s p d ，1 e x i c a ls y n o n y m yp r o p e n vd i c l i o n a r v ) 里的词法属性。同义词词法可表示为三元组形式 ， 这儿a 和b 是概念名称，f 0 ，1 同义词的可信度系数。同义词词法可以由 标准辞典自动地得出，比如w o r d n e t 1 ，也可以通过特殊工具得出，如m i n d n e l l 。但是为了获得更为准确的结果，需要领域专家的人工介入。词法 同义词的可信度系数设置如下：如果没有相似性的值供置信度选择，将可 信度系数设为1 ：否则，可信度系数设为相似性的值。在设置过程始终都要 求人丁领域专家对可信度系数进行确认，甚至对其修改。 假设r c m 网络n e l ( d s i ) 和n e l ( d s ! ) 已经被构建，每一个r c m 网络节点 关联一个相应信息源概念。我们讨论的概念间同义词和多义词的提取也就 是r c m 网络= 亿点问同义词和多义词的提取。一般地，概念和相应的r c m 网 络有同样的名字，我们可以互换地使用这个名字指代二者。 2 5 太原理工大学硕士研究生学位论文 提取同义词和多义词技术由两阶段构成。首先，对每一对节点n l n e t ( d s 】) n 。n e t r d s 二) 计算节点n l 和n 。之间所谓基本相似性。酣翥龋雏骱 越靼塑! 麓尝霜娟雠踣掣鬈型i 总划融罂盟馊愿鸭璎翌；警遵嗡眨揖湖礁 m 哺g 嚣j j 委。；疆7 j 溯謦 寰型。蹩黼强旨蝉甭裂掣= 荔剖彰搿；两湄芬 画馐灞嗽书遘；霪jj ii 龈辅来，使得最远 邻居分配最轻的权重。 求精n l 和n 。间相似系数的过程由下列步骤构成： 第i 步； 对于每一对节点n i n e t ( d s l ) 和n 。n e t ( d s 2 ) ，访问n b h ( n l ，i ) 和 n b h (n m ，i ) 。 在构成n b h ( n l ，i ) 和n b h ( n m ，i ) 弧目标节点的双向加权图上，计钳 n b h (n 】，i ) 和n b h ( n m ，j ) 间相似度。 n l 和n m 相似度算法为n l 和n m 不同邻居相似程度的加权平均值。相似度 的权值设为序列 p ( i ) ) 中的元素值。 3 2 子网相似 考查一个数据源d s 和其相应r c m 嘲络n e ( d s ) ，n e t ( d s ) 中能确定的可 能r h 数目是n e t ( d s ) 节点数的幂。为了避免分析这样数量庞大的子h ，定 义种方法挑选相似度最大的子网”，输入为两个数据源d s l 和d s 二分别 表示为rc m 网络n e t ( d s l ) 和n e t ( d s 2 ) 。 按照以下规则可以得到最为相似的子网对： 考查这些子网对 s n ，s n 使得s n i n e t ( d s l ) 的根为n i 的带根子网， s n j ne t ( d s 2 ) 是根为n j 的带根子网，n 哥nn j 是同义词。 同义词节点m 和n 分别为两个子网的根，在构成n b h ( n l ，i ) 和n b h ( n m ， i ) 弧目 2 8 x 奎堕望兰查兰堕主婴塑生兰为绐蚕 章孽霉； h h ；誊v 要垂篓l j j ；i j 毡荔i 荔鉴l 世毒童 ，羊意泵点计算- 出对最为相似的子网娃黎器甜斡髂，热测鹱期黪渝札笛 e 鞫掣斟型垂骢“鼢乳拦罂。醛囊二弩要若型f 至袅薯；= 褰。i ：i 耋鬻毳霎瑟 艇峪毪捌t 磐口j 韪嚣篓霜叁舅蓖嚣跳掣磁璀曩嘤瞪! i ；趔；曩，薪裂托 昌萎黑酞。葛弹瞄铡潮瓠中弧的蓉壹覃患碉。 毳g n b h ( n j ，k ) 中弧的目标节点构成的恰当双向 图上，弧a 。k 的目标节点t i k 和弧a k 的目标节点t j k 间的边出现在最大权 值匹配中，其中l 介于整数区间 0 ，k ：( i i ) h 和t i k 的相似程度大于一 个给定的闽值，那么弧对 a j k a k 被认