计算机研究与发展
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999　Vol.36　No.7　P.859-864



基于属性等价的多数据源互操作模式合并
许学标　刘宏亮　王轶彤　顾宁　施伯乐
摘　要：在涉及多个异构数据源的互操作处理中，跨数据源模式合并是提供形式一致、概念统一的数据查询/操纵界面和应用程序接口的主要途径.长期以来，对此很少有完善的指导性理论.文中从模式构成的最小单位——属性特性着手，在对象模型的基础上，先自底向上地定义不同种类的属性等价和类等价的概念，然后自顶向下地给出了利用等价类、等价属性进行合并的基本方法，从而为创建跨数据源的一致化对象视图模式探索了新途径.
关键词：现实世界状态，多数据源互操作，属性/类等价，模式合并
分类号：TP311.13
SCHEMA MERGING FOR MULTIPLE DATA SOURCES
INTEROPERATION BASED ON ATTRIBUTE-EQUIVALENCE
XU Xue-Biao
(Department of Computer Science, Fudan University, Shanghai 200433)
LIU Hong-Liang
(Department of Computer Science, Fudan University, Shanghai 200433)
WANG Yi-Tong
(Department of Computer Science, Fudan University, Shanghai 200433)
GU Ning, and SHI Bo-Le
(Department of Computer Science, Fudan University, Shanghai 200433)
Abstract：In the interoperation processing concerning multiple heterogeneous data sources, schema merging spanning them is one effective aspect in providing both the data querying/manipulation and the application program interfaces in a consistent, unified style. Until now there has been no perfect directive theory relevant yet. In this paper, on the foundation of object data model, the authors tackle the problem by setting forth from the features of attribute, the minimal unit in schema construction. The different attribute/type equivalencies are defined first in a bottom-up way, and then the basic schema merging methodologies based on them are presented in a top-down way, which explores a new approach to creating a consistent object view schema over multiple data sources.
Key words：real world state, interoperation of multiple data sources, attribute/type equivalence, schema merging▲
1　引言
　　计算机、网络和多媒体技术的发展，特别是Internet/Intranet的日新月异和数据库的广泛应用，使基于多种异构数据源如文件系统、遗产数据库、RDB/OODB/ORDB、空间和历史等多媒体数据库上的互操作需求越来越多.其基本目标之一是为用户提供形式一致、概念统一的集成数据查询/操纵界面及应用程序接口(API)，这就要求支撑的互操作平台能提供跨数据源的模式合并，从而对不同数据源中含相同内容的异构实体进行合并.过去，模式合并属数据库设计问题，常根据设计者经验确定，很少有成熟的理论指导，这为模式合并的实现及其特性的进一步研究带来困难.而在实际应用中，遗产数据源的模式合并和数据库设计情形仍有相当差距，如模式合并时出现的命名、单位、结构和抽象层次等多种冲突，就无法全盘照搬模式设计的经验.研究表明，在众多互操作系统中，模式合并的基本构架如属性等价、关联等价和类等价等可最终归于属性等价［1～3］.本文根据多数据源模式合并的这一特点，基于公共对象模型，从定义对象属性的等价着手，研究了不同数据源成员对象虚模式特性间的相互关系，并给出了相应的合并方式.
2　公共对象模型简介
　　跨数据源模式合并要求下层的多个异构数据源经转换后能共同遵循某一公共的数据模型.考虑到对象模型具有语义丰富、方法功能强大、映射方便及无缝集成性好等优点，这里采用与ODMG2.0［5］和OMG CORBA互操作对象模型［4］相兼容的公共对象模型(common object model，COM)［4］.在此仅对与模式合并相关的基本概念加以说明.
　　COM最基本的原语是对象和文字，每个对象有唯一的对象标识oid，并通过特性和行为表示其状态和操作.文字与对象相并列，它只有值，没有oid.
　　对象状态通过它所携带的一组特性值来定义.这些特性可以是对象自身属性，也可以是不同对象间的关联.对象取值可随着时间而变化.对象行为通过可在对象上执行或由对象执行的一组操作(方法)来定义.对象和文字按照类型方式进行组织.类型分为文字类型和对象类型.文字类型实例是蕴涵存在的，而不是由应用程序显式生成的；对象类型是通过用户定义的，其实例是应用程序生成的现实世界的特定实体.类型成员在状态范围上有相同的属性、关联和方法.COM中的对象类是指具有相同属性和关联的实体集，对象类型通过定义可用层次表示的超子类进行继承和共享.如果对象类型A是对象类型B的子类，则A类型除继承B类型的所有特性和方法外，还可有区别于B的属性、关联和方法.本文主要对类型及其上的属性、关联等的等价进行定义，以便能根据不同的分类准则采用不同的模式合并算法.
3　多数据源上的对象属性、关联、类型间的等价
　　属性是构造模式的最小单元.为了实现多数据源转换后的对象类型模式向统一对象模式的合并，本文从对象属性的基本特征描述着手，定义强/弱属性等价和类型等价的概念.这里，对象类指的是各数据源经转换处理后合法的“虚”对象类，而属性、关联和方法指的则是“虚”对象类上的属性、关联和方法.
3.1　属性特征、值集和基本等价特性
　　下面给出为属性等价而定义的属性特征描述和属性值集概念.
　　定义1. 属性特征描述：对于对象类C，它的某一属性a的特征描述有7部分构成，分别为：
　　(1) 属性类型域：对象类C的各实例中属性a允许取值的集合，记为DOM(a)；
　　(2) 允许的操作集: 在属性a的类型域中允许操作的方法集合,记为OP(a)；
　　(3) 语义说明: 属性a取值的语义解释和含义.对于数值属性，则是指测量所用的单位，记为SCALE(a)；
　　(4) 语义完整性约束：指的是属性a涉及的与其它属性间的静态约束以及属性变化时所必须遵循的动态完整性约束表达式的集合，记为SIC(a)；
　　(5) 安全性约束：指的是对属性值使用存取权限的约束说明，记为SEC(a);
　　(6) 取值个数范围限制：是指允许在对象类实例中表示的属性a值的最多和最少个数，我们用一对整数(UB(a), LB(a))表示.
　　(7) 唯一标志：是指能唯一标定对象类实例的属性的集合,记为KEY(a).
　　这里的属性类型域DOM可以是整数、字符串、日期等文字类型，也可以是库中定义的抽象对象类型ADT以及由set，bag，list，array等汇集构造子生成的新类型；允许的操作集OP除包含在类型定义中涉及的特定属性的方法外，还包括允许在该属性上使用的公共聚类函数如sum，average，count，max，min等.语义说明SCALE指的是属性值所使用的度量衡含义，例如身高属性可以用米来度量，也可以用厘米来度量，二者虽然值不同，但它们之间存在着可逆的对应关系，这在属性等价时可使用映射函数表达；但有些属性的度量不存在可逆的对应关系，如学生成绩有些科目是用百分制表示的，而有些是用等级(如优、良、中和及格等)来表示的，从前者到后者的函数映射是有意义的，而从后者到前者则是不可逆的，因此无法定义一一关系.
　　语义完整性约束(SIC)包括属性间的函数依赖、存在依赖以及唯一性、非空等与其它类型或属性间的静态关系，以及对象状态改变时在属性上的约束，如雇员对象不能加在已删除的部门中等动态依赖关系集合.安全性约束(SEC)是为自治和安全考虑而给出的控制约束(如不可见、可查询和可更新等)，例如一般用户只能查看学生成绩，而不能修改它.因此，可把SEC(a)看作是涉及到属性a的安全约束表达式的集合.属性的取值个数范围通过上下限表示.取值0表示属性a可为空值，而大于1的上限表示属性a可取值的个数.唯一标志(KEY(a))相当于公共对象模型中的类型特性KEY，它通过oid及一或多个属性描述.用作KEY的属性将用于类等价的判定.
　　定义2. 属性值集.在t时刻对象类C中属性a的值集VALUE(a,t)，指的是在t时刻C上所有实例中属性a的取值集合；全部数据库时刻点上VALUE(a,t)的并集称为类C的数据库状态下的属性a的值集，记为VALUES(a)，即
　　定义3. 基本等价特性.令ai为对象类A的属性, bi为对象类B的属性，设Di为DOM(ai)的最大非空子集，Ri为DOM(bi)的最大非空子集，可定义一个函数fi: Di→Ri及其逆函数f-1i:Ri→Di，称下面5点为需满足的基本等价特性：
　　(1) fi是同构和可逆的，即在Ri和Di间存在一一对应关系；
　　(2) 对每一OP(ai)中的允许操作g，在OP(bi)中必须有一个对应的允许操作g′，使得fi.g=g′.fi，即应用g在DOM(ai)的某一值x后再应用操作fi所得的结果等于先在x上应用fi，然后在fi(x)上应用g′所得结果；
　　(3) 在fi和f－1i映射下保持所有相关的语义完整性.令f1,…,fn是与属性a1,…,an相关联的映射函数.则在SIC(ai)中涉及的属性为a1,…,an的约束必须可以通过把ai用fi(ai)替换后所得到的SIC(bi)中的约束蕴涵，反之亦然；
　　(4) 所有的安全约束在fi和f-1i映射下互为保持，即SEC(ai)SEC(bi)；
　　(5) fi映射函数保持唯一标识.
3.2　各类属性等价的概念
　　下面根据等价合并后的新属性是否允许更新区分定义属性强等价和属性弱等价.
　　定义4. 属性强等价.设在数据库的所有状态下, 有对象类A的属性a和对象类B的属性b遵循定义3中的基本等价特性, 存在一映射f: D→R, 满足：
　　(1) 如果D=VALUES(a), R=VALUES(b), 则称属性a和b是Ⅰ型强等价;
　　(2) 如果D=VALUES(a), RVALUES(b), 或R=VALUES(b), DVALUES(a), 则称属性a和b为Ⅱ型强等价(包含强等价)；
　　(3) 如果RVALUES(b), DVALUES(a),则称属性a和b为Ⅲ型强等价(重叠强等价).
在上述3种情形下，属性a和b均是属性强等价，记为 .
　　定理. 在定义4中给出的3种强等价中，属性a和b合并后是可更新的.
　　证明. 根据定义3和定义4，映射函数f定义了D和R值之间可逆的一一对应关系.这样，在整个数据库的每一时刻的状态下，映射函数f可以把在D中的任何值转换成R中的对应值，反之亦然.如果合并属性是用D中的值表示，则可以将D中的值转换成R中的值，反之亦然.如果合并属性是用其它集合的值来表示，则定义保证该集合一定和R，D之间分别存在一一对应约束，从而使更新能够找到映射的值.
　　当插入包含属性a的一个对象A时，则可以从a属性值域D中指定值；如果属性a在数据库中是直接用D中值表示，就可以把这些值直接存储到数据库中.如果属性a在数据库中是使用R中的值表示，则可以把a的值转换成R中等价的值，存储到数据库中.同样可对二者合并后的属性进行删除和修改操作.
　　从而，属性强等价允许用户对D和R中的值进行更新.
证毕.
　　定义5. 属性弱等价. 令a为对象类A的属性, b为类B的属性；若令D为DOM(a)的最大非空子集，R为DOM(b)的最大非空子集，D和R使得存在一个函数f: D→R,(f可用作表示定义a和b的基本等价特性的条件).如果f满足如下特性：
　　(1) f在R和D间存在着映射对应关系,但不要求f可逆；
　　(2) 对每一个在OP(a)中的允许操作g，在OP(b)中必须有一个对应的允许操作g′，使得f.g=g′.f，即应用g在DOM(a)的某一值x后再应用操作f所得的结果等于先在x上应用f，然后在f(x)上应用g′所得结果；
　　(3) 令f1,…,fn为和属性a1,…,an相连的映射函数，在SIC(a)中涉及的属性为a1,…,an的约束可以在a用fi(ai)(i=1,…,n)替换后所得到的SIC(b)中的约束后保持;
　　(4) 所有安全约束在f映射下单向保持；
　　(5) f映射函数能够保持唯一标识.
　　这时称属性a和b是弱等价的，记为 a≡wab.
　　两个属性a和b，无论是属性强等价还是属性弱等价，都可以合并形成新属性c，差别在于：如果a和b是强等价的，则c的值是可以更新的；如果a和b只是弱等价而非强等价，则c值不能更新.此外，当映射函数的两个域为空时，虽然两个属性值之间无法定义映射函数，但若它们所承担的角色相同，则仍可以进行合并，这是区别于强弱等价的属性不相交等价.具体地：
　　定义6. 属性不相交等价. 令a为对象类A的一属性, b为对象类B的一属性；令D为DOM(a)的最大非空子集，R为DOM(b)的最大非空子集，如果：
　　(1) D和R是不相交的，即D∩R=φ，因此不存在属性强、弱等价关系；
　　(2) a和b承担角色相同，即它们满足定义1中的(1)、(2)、(3)、(6)、(7)特性.则称属性a和b是不相交等价的，记为a≡dab.
　　定义7. 属性等价. 给定两个属性a，b，不管它们是强等价、弱等价，还是不相交等价，我们统称属性a，b是等价的，记为a≡ab.
3.3　现实世界状态和对象类的等价
　　在属性等价基础上，可定义对象关联的强弱等价等概念［3］.下面讨论用对象类的标识属性等价特性来定义对象类等价的方法.由于在多数据源对应的成员对象库的外延已经无法表示在不同数据源上相同的概念，在此引入现实世界状态的概念如下：
　　定义8. 现实世界状态RWS. RWS是一个和数据库外延相似的概念，它的含义是指在多个数据源之上能唯一确定现实世界中对象和类的状态标识集.
　　记两个对象类A和B的RWS分别为RWS(A)和RWS(B).即如果在现实世界中，A和B代表的是给定时刻相同现实世界的实例集合时，虽然在不同数据源中两个类的外延及其表示可能不相等，但仍会有RWS(A) = RWS(B).
　　根据RWS定义对象类的不同等价概念，接近于实际集成时的互操作需求.在现实世界中的对象类，即使在异构数据源模式转换时属于不同成员对象类，甚至描述不同，但如果它们被确认是类型等价的，则可以通过等价桥梁使合并模式划归到同一个类型，或使它们保持一种继承关系.对象类强等价的具体定义为：
　　定义9. 对象类强等价.令对象类A的键为k1，属性/关联为a1,…,am，对象类B的键为k2，属性及关联为b1,…,bn，RWS(A)和RWS(B)分别是在给定时刻A和B的现实世界实例集，T(k1)和T(k2)为A和B在某一时刻全部实例的集合.若令DOM(k1)和DOM(k2)分别为类A和类B在所有时刻对象实例的并.在DOM(k1)和DOM(k2)的每一时间点定义一个映射函数f：D→R，D为在T(k1)中包含的最大非空子集，R为在T(k2)中包含的最大非空子集，则使用f定义对象类A和B之间的类等价如下：
　　(1) 如果k1和k2中的所有属性都是对应强等价，则称RWS(A)和RWS(B)是Ⅰ型强等价；
　　(2) 如果k1集合中的所有属性和k2中的对应属性强等价，或强包含k2中的对应属性，则称RWS(A)和RWS(B)为Ⅱ型强等价；
　　(3) 如果k1和k2中的属性至少有一对是不相交等价，且都不是强重叠等价的，则称RWS(A)和RWS(B)是Ⅲ型强等价；
　　(4) 如果k1和k2中的属性有一对是重叠强等价的，则称RWS(A)和RWS(B)是Ⅳ型强等价.
　　总之，(1)～(4)是对象类强等价的4种类型，可以统一记为A≡scB.
　　类似地，可定义对象类弱等价、对象类不相交等价和对象类等价等概念［3］.
3.4　属性等价定义的应用
　　利用上述的属性等价，通过建立映射函数，可方便地处理如下多数据源互操作模式集成出现的异构问题：
　　(1) 命名冲突. 对于相应属性具有不同名字或不对应属性具有相同名字的问题，可通过使用属性强/弱、不相关等价的定义，来进行标识和合并，使名字相同的非对应属性通过映射识别并对其中的一或多个属性重命名来解决；
　　(2) 语义上的差异. 长度、重量、货币等具有不同的度量衡，它们之间存在着倍数关系，其转换即为强等价的特例.例如若属性a用长度单位“米”表示，其等价属性b用“公里”表示，则有函数f：b=f(a)=a×0.001和逆函数f-1: a=f-1(b) =b×1000.这样，通过使用定义的映射函数表达式可消除等价属性在语义上的差异；
　　(3) 属性抽象标准上的差异. 抽象标准上的差异出现在等价属性间存在包含关系的情形，例如有两个属性，含义分别表示电话号码和家庭电话号码.它们在语义关系上就存在着一种包含关系.通过包含属性等价，可以将其进行等价合并；
　　(4) 对象标识上的差异. 现实世界中的同一实体在不同数据源中会有不同的表示.虽然单一对象库中的同一对象实体可通过语义约束来保持其唯一性，但若处于不同数据库中，则由于表示和实现上的差异，将会出现很多既非对象、又非关系的实体.其标识的建立也大多是根据映射函数来确定的.这样,多种类型对象标识很难将标识的唯一性和对象oid相统一.即使不同数据源上的两个对象在现实世界中表示同一实体，且它们在公共属性上取值相同，若不在对应标识值间建立映射关系，也很难将其合并.建立属性等价和对象等价准则，可较好地解决这类表达上的差异；
　　(5)类型表示上的差异. 由于从需求、设计、实现到数据库的转换等环节可能出现差异，同一实体在不同数据库中可能使用完全不同的类型表示.只有通过对象类等价，才能抹平这些差异，使多数据源间的模式合并顺利进行.
4　对象类/属性合并的方法
4.1　等价对象类的合并
　　按照前面4种对象类等价的定义，可分别给出对应的对象类的集成方法.由于属性不相交等价主要通过设计人员指定对应关系，这里暂不考虑这种情形.其它等价属性的合并处理具体如下(参见图1).


图1　对象类合并基本方法示意图
　　对于(1)，如果RWS(A)=RWS(B), 可将对象类A和对象类B合并成一个单独的虚对象类AB′, AB′的键为k1或k2, 并且有
RWS(AB′) = RWS(A)∪RWS(B) = RWS(A) =RWS(B)；
　　对于(2)，即对象类包含等价情形，设RWS(A)RWS(B)，则可将A在合并模式中对应于新虚类A′，把B对应于新虚类B′，并使B′成为A′的子类，且有
RWS(A′)=RWS(A), RWS(B′)=RWS(B);
　　对于(3), RWS(A)和RWS(B)为重叠等价情形.这时，除需生成对应的虚类A′和B′外，还要生成一个新的虚对象类AB′, 把A′和B′作为它的子类型.这时要求有：
RWS(A′)=RWS(A)， RWS(B′)=RWS(B); RWS(AB′)=RWS(A)∪RWS(B)
　　按上述方法，可将任何满足定义要求的两等价类加以合并.
4.2　等价属性的合并
　　在确定对象类等价后，需要进行对象类中属性/关联的合并.下面考虑两等价类中的一对等价属性的合并处理方法.按照上述对象类的等价定义，设欲合并的两对象类分别为A和B，a和b是它们中的某一对应的等价属性，需要根据对象类和属性等价的不同分类确定新属性在合并对象类中的位置.
　　(1) 对于Ⅰ型等价的两属性，不管所属的对象类是按照何种等价方式集成，都需使合并的新属性成为超类上的一个属性，且类型域等于用户定义的映射函数的值域.
　　(2) 对于Ⅱ型即包含等价的两个属性，则要根据它们所在的两个类是按照包含方式还是重叠方式进行等价合并来区分对待.① 如果两属性所在的对象类是按照包含方式合并，设有RWS(A)RWS(B)，而在新产生的对象类的合并中，可把A对应于类A′，把B对应于类B′，并使B′成为A′的子类；设a属性包含b属性，则可在A′上指定a的映象属性a′，在B′上指定b的映象属性b′，并把b′看作为a′的一个子类型，属性a′，b′的域分别可由用户定义的映射函数的值域确定；② 如果两属性所在的对象类按照重叠方式合并， 这时，除要指定对应类A′和B′上的两属性a′和b′外,还要在新建立的A类和B的公共超类AB′上增加一个属性c′, a′和b′可看作是属性c′的子类型，c′可看作是属性a′和b′的公共特性.
　　（3） 对于仅出现在两个类是重叠时的Ⅲ型等价的两属性，处理类似于(2)，即将两属性a和b分别指定为对应类A′和B′的一个属性a′和b′，并在两个类的超类AB′上增加新属性c′, 其含义类似于(2).
5　结语
　　互操作中的跨数据源模式合并涉及从设计到应用的众多方面，是一个相对复杂的问题［1～3］.本文在公共对象模型基础上,先后用自底向上和自顶向下方法给出了不同类的属性/对象类型等价概念和相应的类/属性合并方法，这一研究对于跨数据源互操作的一致存取具有重要意义.进一步工作包括利用知识表示设计基于属性等价的模式合并工具，实现多数据源互操作对象类模式的辅助生成和异构自治环境下不同数据源间动/静依赖的对象类表达等.■
基金项目：本课题得到国家“八六三”计划、国家“九五”科技攻关和上海市科委科技发展基　　　　　　金的资助.
作者简介：许学标，男，1969年生，博士，主要研究方向为OODB、KDB、多数据源集成和互操作.
　　　　　刘宏亮，男，1970年生，博士生，主要研究方向为DOOD和数据仓库.
　　　　　王轶彤，女，1973年生，博士生，主要研究方向为数据库和半结构化数据处理.
　　　　　顾宁，男，1955年生，博士生，副教授，主要研究方向为CSCW、OODB、工程数据库　　　　　　等.
　　　　　施伯乐，男，1935年生，复旦大学首席教授，博士生导师，主要研究方向为数据　　　　　　库、知识库和数据仓库等.
作者单位：许学标(复旦大学计算机科学系　上海　200433)
　　　　　刘宏亮(复旦大学计算机科学系　上海　200433)
　　　　　王轶彤(复旦大学计算机科学系　上海　200433)
　　　　　顾宁(复旦大学计算机科学系　上海　200433)
　　　　　施伯乐(复旦大学计算机科学系　上海　200433)
参考文献：
［1］Batini C et al. A comparative analysis of methodologies for database schema integration. ACM Computing Surveys, 1986，18(4)：323～364
［2］Larson J et al. A theory of attribute equivalence. In: Databases with Application on Schema Integration. IEEE TOSE, 1989, 15(4): 449～463
［3］许学标.支持多数据源互操作的广义对象视图的研究[博士论文]. 复旦大学，上海，1998
　　　(Xu Xuebiao. Research on generalized object view for supporting interoperation of multiple data sources (in Chinese). Fudan University, Shanghai, 1998)
［4］OMG. The common object request broker: Architecture and specification, revision 2.0. Object Management Group. 1995. http://ruby.omg.org/index.html
［5］Cattell R G G. The Object Database Standard: ODMG-93(Release 1.2). San Mateo, California: Morgan Kaufmann Publishers, 1996
收稿日期：1998-08-24
修稿日期：1999-03-08
