о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999Vol.36No.7P.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)
AbstractIn 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 wordsreal world state, interoperation of multiple data sources, attribute/type equivalence, schema merging
1
Ͷý弼ķչرInternet/IntranetݿĹ㷺Ӧãʹڶ칹ԴļϵͳŲݿ⡢RDB/OODB/ORDBռʷȶýݿϵĻԽԽ.Ŀ֮һΪûṩʽһ¡ͳһļݲѯ/ݽ漰Ӧóӿ(API)Ҫ֧ŵĻƽ̨ṩԴģʽϲӶԲͬԴкͬݵ칹ʵкϲ.ȥģʽϲݿ⣬߾ȷгָΪģʽϲʵּԵĽһо.ʵӦУŲԴģʽϲݿ൱࣬ģʽϲʱֵλṹͳεȶֳͻ޷ȫհģʽƵľ.оڶ໥ϵͳУģʽϲĻԵȼۡȼۺȼ۵ȿչԵȼۣ13.ĸݶԴģʽϲһص㣬ڹģͣӶԵĵȼ֣о˲ͬԴԱģʽԼ໥ϵӦĺϲʽ.
2ģͼ
ԴģʽϲҪ²Ķ칹Դתܹͬѭĳһģ.ǵģ;ḻǿӳ䷽㼰޷켯Ժõŵ㣬ODMG2.05ݺOMG CORBAģͣ4ݵĹģ(common object modelCOM)4.ڴ˽ģʽϲصĻ˵.
COMԭǶ֣ÿΨһĶʶoidͨԺΪʾ״̬Ͳ.ಢУֵֻûoid.
״̬ͨЯһֵ.ЩԿǶԣҲǲͬĹ.ȡֵʱ仯.Ϊͨڶִлɶִеһ().ְͷʽ֯.ͷΪͺͶ.ʵ̺ڵģӦóʽɵģͨûģʵӦóɵʵضʵ.ͳԱ״̬Χͬԡͷ.COMеĶָͬԺ͹ʵ弯ͨòαʾĳм̳к͹.AǶB࣬Aͳ̳B͵Ժͷ⣬Bԡͷ.Ҫͼϵԡȵĵȼ۽ж壬Աܸݲͬķ׼òͬģʽϲ㷨.
3ԴϵĶԡͼĵȼ
ǹģʽСԪ.ΪʵֶԴתĶģʽͳһģʽĺϲĴӶԵĻ֣ǿ/Եȼۺ͵ȼ۵ĸ.ָǸԴתϷġ顱࣬ԡͷָǡ顱ϵԡͷ.
3.1ֵͻȼ
ΪԵȼ۶ֵ.
1. ڶCĳһa7ֹɣֱΪ
(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ԼsetbaglistarrayȻ㼯ɵͣĲOPͶ漰ضԵķ⣬ڸʹõĹຯsumaveragecountmaxmin.˵SCALEֵָʹõĶ⺬壬ԿҲȻֵ֮ͬſĶӦϵԵȼʱʹӳ亯ЩԵĶڿĶӦϵѧɼЩĿðٷƱʾģЩõȼ(šкͼ)ʾģǰߵߵĺӳģӺߵǰǲģ޷һһϵ.
Լ(SIC)ԼĺԼΨһԡǿյͻԼľ̬ϵԼ״̬ıʱϵԼԱܼɾĲеȶ̬ϵ.ȫԼ(SEC)ΪκͰȫǶĿԼ(粻ɼɲѯͿɸµ)һûֻܲ鿴ѧɼ޸.ˣɰSEC(a)漰aİȫԼʽļ.ԵȡֵΧͨޱʾ.ȡֵ0ʾaΪֵ1ޱʾaȡֵĸ.Ψһ־(KEY(a))൱ڹģеKEYͨoidһ.KEYԽȼ۵ж.
2. ֵ.tʱ̶Caֵ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: DiRi溯f-1i:RiDi5ΪĻȼԣ
(1) fiͬͿģRiDiһһӦϵ
(2) ÿһOP(ai)еgOP(bi)бһӦg䣬ʹfi.g=g.fiӦgDOM(ai)ĳһֵxӦòfiõĽxӦfiȻfi(x)Ӧgý
(3) fif1iӳ±ص.f1,,fna1,,anӳ亯.SIC(ai)漰Ϊa1,,anԼͨaifi(ai)滻õSIC(bi)еԼ̺֮Ȼ
(4) еİȫԼfif-1iӳ»Ϊ֣SEC(ai)SEC(bi)
(5) fiӳ亯Ψһʶ.
3.2Եȼ۵ĸ
ݵȼۺϲǷֶǿȼۺȼ.
4. ǿȼ.ݿ״̬, жAaͶBbѭ3еĻȼ, һӳf: DR, 㣺
(1) D=VALUES(a), R=VALUES(b), abǢǿȼ;
(2) D=VALUES(a), RVALUES(b), R=VALUES(b), DVALUES(a), abΪǿȼ(ǿȼ)
(3) RVALUES(b), DVALUES(a),abΪǿȼ(صǿȼ).
3£abǿȼۣΪ .
. ڶ4и3ǿȼУabϲǿɸµ.
֤. ݶ3Ͷ4ӳ亯fDRֵ֮һһӦϵ.ݿÿһʱ̵״̬£ӳ亯f԰DеκֵתRеĶӦֵ֮Ȼ.ϲDеֵʾԽDеֵתRеֵ֮Ȼ.ϲϵֵʾ屣֤üһRDֱ֮һһӦԼӶʹܹҵӳֵ.
aһAʱԴaֵDֵָaݿֱDֵʾͿ԰ЩֱֵӴ洢ݿ.aݿʹRеֵʾ԰aֵתRеȼ۵ֵ洢ݿ.ͬɶԶߺϲԽɾ޸Ĳ.
ӶǿȼûDRеֵи.
֤.
5. ȼ. aΪA, bΪBԣDΪDOM(a)ǿӼRΪDOM(b)ǿӼDRʹôһf: DR,(fʾabĻȼԵ).fԣ
(1) fRDӳӦϵ,Ҫf棻
(2) ÿһOP(a)еgOP(b)бһӦg䣬ʹf.g=g.fӦgDOM(a)ĳһֵxӦòfõĽxӦfȻf(x)Ӧgý
(3) f1,,fnΪa1,,anӳ亯SIC(a)漰Ϊa1,,anԼafi(ai)(i=1,,n)滻õSIC(b)еԼ󱣳;
(4) аȫԼfӳµ򱣳֣
(5) fӳ亯ܹΨһʶ.
ʱabȼ۵ģΪ awab.
abǿȼۻȼۣԺϲγcڣabǿȼ۵ģcֵǿԸµģabֻȼ۶ǿȼۣcֵܸ.⣬ӳ亯ΪʱȻֵ֮޷ӳ亯еĽɫͬԿԽкϲǿȼ۵Բཻȼ.أ
6. Բཻȼ. aΪAһ, bΪBһԣDΪDOM(a)ǿӼRΪDOM(b)ǿӼ
(1) DRǲཻģDR=գ˲ǿȼ۹ϵ
(2) abеɫͬ㶨1е(1)(2)(3)(6)(7).abǲཻȼ۵ģΪadab.
7. Եȼ. abǿȼۡȼۣǲཻȼۣͳabǵȼ۵ģΪaab.
3.3ʵ״̬Ͷĵȼ
Եȼۻϣɶǿȼ۵ȸ3.öıʶԵȼȼ۵ķ.ڶԴӦĳԱѾ޷ʾڲͬԴͬĸڴʵ״̬ĸ£
8. ʵ״̬RWS. RWSһݿƵĸĺָڶԴ֮Ψһȷʵж״̬ʶ.
ABRWSֱΪRWS(A)RWS(B).ʵУABǸʱͬʵʵʱȻڲͬԴӼʾܲȣԻRWS(A) = RWS(B).
RWSĲͬȼ۸ӽʵʼʱĻ.ʵеĶ࣬ʹ칹ԴģʽתʱڲͬԱ࣬ͬǱȷ͵ȼ۵ģͨȼʹϲģʽ鵽ͬһͣʹǱһּ̳йϵ.ǿȼ۵ľ嶨Ϊ
9. ǿȼ.AļΪk1/Ϊa1,,amBļΪk2ԼΪb1,,bnRWS(A)RWS(B)ֱڸʱABʵʵT(k1)T(k2)ΪABĳһʱȫʵļ.DOM(k1)DOM(k2)ֱΪABʱ̶ʵĲ.DOM(k1)DOM(k2)ÿһʱ㶨һӳ亯fDRDΪT(k1)аǿӼRΪT(k2)аǿӼʹfAB֮ȼ£
(1) k1k2еԶǶӦǿȼۣRWS(A)RWS(B)Ǣǿȼۣ
(2) k1еԺk2еĶӦǿȼۣǿk2еĶӦԣRWS(A)RWS(B)Ϊǿȼۣ
(3) k1k2еһǲཻȼۣҶǿصȼ۵ģRWS(A)RWS(B)Ǣǿȼۣ
(4) k1k2еһصǿȼ۵ģRWS(A)RWS(B)Ǣǿȼ.
֮(1)(4)Ƕǿȼ۵4ͣͳһΪAscB.
Ƶأɶȼۡ಻ཻȼۺͶȼ۵ȸ3.
3.4Եȼ۶Ӧ
Եȼۣͨӳ亯ɷش¶Դģʽɳֵ칹⣺
(1) ͻ. ӦԾвֻͬ򲻶ӦԾֵͬ⣬ͨʹǿ/صȼ۵Ķ壬бʶͺϲʹͬķǶӦͨӳʶ𲢶еһ
(2) ϵĲ. ȡҵȾвͬĶ⣬֮űϵתΪǿȼ۵.aóȵλסʾȼbáʾкfb=f(a)=a0.001溯f-1: a=f-1(b) =b1000.ͨʹöӳ亯ʽȼϵĲ죻
(3) Գ׼ϵĲ. ׼ϵĲڵȼԼڰϵΣԣֱʾ绰ͼͥ绰.ϵϾʹһְϵ.ͨԵȼۣԽеȼۺϲ
(4) ʶϵĲ. ʵеͬһʵڲͬԴлвͬıʾ.ȻһеͬһʵͨԼΨһԣڲͬݿУڱʾʵϵĲ죬ֺܶȷǶַǹϵʵ.ʶĽҲǸӳ亯ȷ.,ͶʶѽʶΨһԺͶoidͳһ.ʹͬԴϵʵбʾͬһʵ壬ڹȡֵͬڶӦʶֵ佨ӳϵҲѽϲ.ԵȼۺͶȼ׼򣬿ɽϺõؽϵĲ죻
(5)ͱʾϵĲ. ڴơʵֵݿתȻڿֲܳ죬ͬһʵڲͬݿпʹȫͬͱʾ.ֻͨȼۣĨƽЩ죬ʹԴģʽϲ˳.
4/Ժϲķ
4.1ȼ۶ĺϲ
ǰ4ֶȼ۵Ķ壬ɷֱӦĶļɷ.ԲཻȼҪͨԱָӦϵݲ.ȼԵĺϲ(μͼ1).


ͼ1ϲʾͼ
(1)RWS(A)=RWS(B), ɽAͶBϲһAB, ABļΪk1k2, 
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)Ϊصȼ.ʱɶӦAB⣬ҪһµAB, ABΪ.ʱҪУ
RWS(A)=RWS(A) RWS(B)=RWS(B); RWS(AB)=RWS(A)RWS(B)
ɽκ㶨ҪȼԺϲ.
4.2ȼԵĺϲ
ȷȼۺҪж/ĺϲ.濼ȼеһԵȼԵĺϲ.ĵȼ۶壬ϲֱΪABabеĳһӦĵȼԣҪݶԵȼ۵Ĳͬȷںϲеλ.
(1) ڢ͵ȼ۵ԣĶǰպֵȼ۷ʽɣʹϲԳΪϵһԣûӳ亯ֵ.
(2) ڢͼȼ۵ԣҪڵǰհʽصʽеȼۺϲֶԴ. ڵĶǰհʽϲRWS(A)RWS(B)²ĶĺϲУɰAӦA䣬BӦB䣬ʹBΪAࣻa԰bԣAָaӳa䣬Bָbӳb䣬b俴Ϊaһͣa䣬bֱûӳ亯ֵȷ ڵĶఴصʽϲ ʱҪָӦABϵab,Ҫ½ABĹABһc, abɿcͣcɿabĹ.
3 ڽصʱĢ͵ȼ۵ԣ(2)abֱָΪӦABһab䣬ĳABc, 京(2).
5
еĿԴģʽϲ漰ƵӦõڶ෽棬һԸӵ13.ڹģͻ,ȺԵϺԶ·˲ͬ/͵ȼ۸Ӧ/ԺϲһоڿԴһ´ȡҪ.һ֪ʶʾƻԵȼ۵ģʽϲߣʵֶԴģʽĸɺ칹λ²ͬԴ䶯/Ķ.
Ŀõҡƻҡ塱ƼغϺпίƼչ.
߼飺ѧ꣬У1969ʿҪоΪOODBKDBԴɺͻ.
У1970ʿҪоΪDOODݲֿ.
ͮŮ1973ʿҪоΪݿͰṹݴ.
У1955ʿڣҪоΪCSCWOODBݿ⡡.
ʩ֣У1935ѧϯڣʿʦҪоΪݡ⡢֪ʶݲֿ.
ߵλѧ(ѧѧϵϺ200433)
(ѧѧϵϺ200433)
ͮ(ѧѧϵϺ200433)
(ѧѧϵϺ200433)
ʩ(ѧѧϵϺ200433)
οף
1Batini C et al. A comparative analysis of methodologies for database schema integration. ACM Computing Surveys, 198618(4)323364
2Larson J et al. A theory of attribute equivalence. In: Databases with Application on Schema Integration. IEEE TOSE, 1989, 15(4): 449463
3ѧ.ֶ֧ԴĹͼо[ʿ]. ѧϺ1998
(Xu Xuebiao. Research on generalized object view for supporting interoperation of multiple data sources (in Chinese). Fudan University, Shanghai, 1998)
4OMG. The common object request broker: Architecture and specification, revision 2.0. Object Management Group. 1995. http://ruby.omg.org/index.html
5Cattell 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
