ѧ
JOURNAL OF SOFTWARE
2000Vol.11No.2P.222-228



칹ԴϵͳѯֽŻʵ
ܱ
ժҪͨ칹ԴϵͳҪɰWWWڵĸԴ,ЩԴ޹ģʽṹǿĲѯ,ȫֲѯķֽŻһ.칹ԴϵͳVersatileһþֲֵ̬ģ켯ϵͳȫֵֶ̬,ΪѯֽŻ.һûڻԴĲѯֽŻ,ԱԴĲѯ,򻯰װ,ȡýϸߵĲѯЧ.
ؼʣ칹Դ,ݼ,ֵ̬,ѯֽ,ѯŻ,ѯ,.
ţTP311
Query Decomposition and Optimization in Heterogeneous Data Integration System
WANG Ning
(Power System Control Corporation Nanjing Automation Research Institute,Nanjing,210003)
WANG Neng-bin
(Department of Computer Science and Engineering Southeast University,Nanjing,210096)
AbstractA heterogeneous data integration system can integrate a broad range of data sources including WWW.Decomposition and optimization for query are very difficult because some data sources have neither regular schemata nor strong query capabilities.To help query decomposition and optimization,a dynamic dictionary is proposed as unified schemata for various heterogeneous data sources,and the way for the construction of a global dynamic dictionary by operating on dynamic dictionaries of local data sources is given.Furthermore,to simplify the design of wrappers for data sources with limited capabilities and reduce responding time for query,an approach,which can take advantage of all powers of various data sources and results of prior queries,is proposed for query decomposition and optimization.
Key wordsHeterogeneous data source,data integration,dynamic dictionary,query decomposition,query optimization,query capability,cache.
żռWWWĳ,ǵעɶ⼯ɣ1,2תԴ.칹Դϵͳ˼ɾйṹ(well structured)֮,輯WWWԴİṹ(semistructured)ݣ3.ЩԴģͲͬ,Ҳѯ,ѯķֽŻµ.,ṹ봫ͳݿݵ,ǲѭĳ̶ģʽ4.ݿϵͳ,ģʽһڶݿĽṹ,ûĲѯ,һҲǲѯвѯŻ .ȱģʽ,Щʮ.,칹Դϵͳͬڶϵͳ,ڼɷΧӴ,ԴĲѯǧ5.칹ԴϵͳҪðװ5θԴĲ.װƷ֣һðװʵԴδṩĲѯ.һǽԴǾɵĲѯ(ף6гΪleast common denominator),ѯȫֲѯ.ַ·ǳӵİװ,ȫֲѯ.ٴ,ڶϵͳ,ȫֽ㲢洢,ȫģʽĲѯֽӲѯ,͵ӦľֲԴȥִ.ַԶϵͳõ,칹ԴϵͳҪͼȶýϢWWWϵHTMLļ,Щݵļٶ,ÿζӾֲԴЧ̫.,ʵͼ7,8ݵķݼ,ַ߲ѯٶ,ʵͼάĴ̫.
Versatileһͨ칹Դϵͳԭͣ9.ģͶֵ̬ĸͳһ칹Դģʽ,ͨɨݿ,þֲֵ̬ģ켯ϵͳȫֵֶ̬,ΪѯķֽŻ춨˻.ڲѯĹ,VersatileûûȫͼĲѯ,ԪݲֿⱣDBA(database administrator)ṩĲѯϵ͸ԴĲѯ.ѯϵѯ֮ͬϵϢ,ѯݴжϲѯǷڻ,޷ɻȡýĲѯ,Դ,ѯֽ⵽Դִ.VersatileûڻԴĲѯֽŻ,ԴĲѯ,˰װ,ȡ˽ϸߵĲѯЧ.
ĵ1ڼ򵥽VersatileϵͳĶ󼯳ģͺʹ.2ڸȫֵֶ̬Ĺ췽.3ڽܻڻԴĲѯֽŻ.ǽ.
1 Versatile
VersatileһCORBA10ݵĿչ칹Դϵͳԭ.IONA˾OrbixƷ,VersatileĿǰ΢˾SQL ServerݿϵͳVersantļϵͳı(WWWе)аװͼ.ڲþнǿOIM(object integration model)ģΪϵͳĹģ,ϵͳܼԴ,ܼʱԴе.
1.1OIMģ
OIMģͣ11VersatileϵͳĹģ.һOIMOһͨͼ,ʾO(r,V,E).ͼеÿʾ,߱ʾԱ֮Ĺϵ.rһۼ,͵,VǸþۼгԱļ,EǶԱ֮ϵļ.OIMģͽԪݸ,ڼԸ칹Դ칹,ر.
1:һӳоͽʦOIMO1ͼ1ʾ.

Fig.1Structure of OIM object O1 for postgraduate-teacher database
ͼ1о-ʦOIMO1Ľṹ
Ϊ,ͼ1ÿʾһ.Բν;νʾ,,ԲνǸӶ,νԭӶ,ӴֵԲνʾ.Բνʾ.ʵ߱ʾӶԱ֮ùϵ,߱ʾ֮Ĺϵ.
O1о-ʦΪ,4Աоʦ.ְƶǽʦĳԱ.оĳԱաʦ3֮,ۺϲ.,ʾķ,ۺϲʾķԱ׼Ϊ.
1.2OIM
OIMģʹӱ칹Դļɳ,ṩһϵOIMĶ,ǷֱǶ󲢡ѡ񡢶ͶӰճ,ЩܺͳΪOIM.OIMVersatileϵͳȫֲѯOIQL(object integration and query language)ѧ.ΪԺ,򵥽OIMļ,OIMϸ,ף11.
(1) .ӶOIMO1,O2Ӷ󼯵Ĳ,ʾO1O2.
(2) .ӶOIMO1,O2Ӷ󼯵Ĳ,ʾO1O2.
(3) ѡ.һf,ڸOIMO1ѡȡӶ,ʾɦңf(O1).
(4) ͶӰ.ڸOIMO1Ӷ,ָ·p1,...,pkѡȡ·յӶ,ʾɦp1,...,pk(O1).
(5) ճ.涨ճO1Ϊ,һf,ڻĳp1ճO2ĳp2Ӷ,ʾO1p1,p2,fO2.
(6) .ڸOIMO1Ӷ,ָ·p1,...,pkȥ·յӶ,ʾɣp1,...,pk(O1).
2 ֵ̬Ľ
칹Դϵͳ,ͨװΪԴṩ׼,ʵϵͳĿչԣһѳɹʶ.VersatileϵͳҲðװ㽫Դ칹תOIM,ӦҪ.Ϊ˰ûĲѯԼЭѯвѯֽŻ,ֲİװȫֽ㶼ҪԼĿ¼,VersatileϵͳгΪֵ̬.ν̬,һָЩԴûʽģʽ,ֲװģʽϢûԤָ,ͨɨݿõ,Loreеݵ(DataGuide)4ݣһָȫֽģʽϢɾֲӦϢ.
Versatileģ12M(O)ʾOIMOĽṹ,ģ屾ҲOIM,дӸ·ļвͬ·.ģLoreеݵͬ,Ľṹ,Ϊ.һģEM(O)һضģ,ܾȷطӳOIMOĽṹ.ͼ1ʾOIMO1һģͼ2ʾ.Ȼ,ûй̶ģʽṹOIM˵,һģȷ,ȷʱļ̫(һͨɨݿȡ),һģȡ.ģеĶ,ݿвһ.,ģ岻ᡰΡݿеĶ,Ҳ˵,ݿеĶ,ģбͬ·ͬ.,Ȼģݿж׼ȷṹȫһ,ΪԪʹȻǺ.

Fig.2Exact template of OIM object O1 for postgraduate-teacher database
ͼ2о-ʦOIMO1һģ
VersatileϵͳĶֵ̬ģļ,ȫֵֶ̬;ֲֵ̬֮,ֱӦVersatileȫͼ;ֲͼ.Versatileϵͳ,ֲͼɾֲԴDBA,ϵͳṩɹOIM,ĳԴṩĿɹOIMģ弯ϹɸԴľֲֵ̬.ȫͼɾֲͼͨOIMɵ,ǿɹնûʵĶ,ȫOIMģļϹVersatileȫֵֶ̬.
Versatileһչ칹Դϵͳ,뼯ɵԴǶֶ.еľʽģʽṹ,ݿϵͳ,ģʽṹֱתΪģ壻еûʽģʽṹ,ļϵͳ,Versatileϵͳṩģʽṹ,ģɴģʽļȡãеԴ,WWWϵHTMLļ,ģLoreеݵĻȡ,ͨɨݿȡã4.
칹Դϵͳ,Դģʽ,ȫֽ㼯ݵģʽͬҪ.Versatileϵͳʵͼݼ,LoreͨɨݿķȡȫݵģʽȻǲʵʵ.
Versatileϵͳȫģɾֲģͨģ.OIMO1,O2ģM(O1),M(O2),P1=p1,p2,...,pn,p1,p2,...,pn,p1,p2ǴӸ·.ģ5,Ƿֱǣ(1) M(O1)M(O2)ģ岢,M(O1)mM(O2);(2) M(O1)ͬģ,M(O1);(3) M(O1)P1ϵģͶӰ,mp1,p2,...,pn(M(O1));(4) M(O1)P1ϵģ,mp1,p2,...,pn(M(O1));(5) M(O1)ڱճp1M(O2)ճp2ģճ,M(O1)mp1,p2M(O2).
֤M(O1)mM(O2)O1,O2󲢵ģ.M(O1)O1,O2ģ,ҲO1Ķѡģ.mp1,p2,...,pn(M(O1))O1P1ͬ·TLP(P1,O1)϶ͶӰģ.mp1,p2,...,pn(M(O1))O1P1ͬ·TLP(P1,O1)϶ģ.M(O1)mp1,p2M(O2)O1ڱճTLP(p1,O1)O2ճTLP(p2,O2)϶ճģ.֤ף12.
Ͻ,OIMģӦģ,,þֲģ֮ĲԹȫOIMģ.Versatileϵͳȫֵֶ̬þֲֵ̬ģɵ.
3 ȫֲѯķֽŻ
3.1Դѯ
VersatileĲѯԿͻ˵Ĳѯ,ѯֽӲѯ,װ,װùԱĲѯתӦԴܽܵĲѯ,ٽԴصĽתɹģͱĶ,Ա㼯Ը칹Դ.ȻôͳֲʽݿϵͳϵͳеĲѯֽŻ,ԴİװʵOIMȫ,һЩѯԴ˵,֧OIMҪ൱ӵİװ.
Ϊ˼򻯰װ,VersatileϵͳɸԴѯ.ԴĲѯòѯQCV(query capability vector)ʾ.op1,op2,op3,op4,op5,op6ֱʾOIM6ֲ,QCVά,ʾ(c1,c2,c3,c4,c5,c6),ck=1ck=0,k=1,...,6.ck=1ʾԴװ֧opk;ck=0ʾԴװ֧opk.һԴװ֧QCVĲѯ,֧OIMĶ.
ֲԴVersatileϵͳעʱṩѯQCV,ԴװOIM֧,QCVԪݲֿ,ѯڲѯֽʱǸԴ,Դֵ֧Ĳѯ.
3.2OIM󻺴
VersatileҪɶýϢWWWϵHTMLļ,Щݵļٶ,ÿδӾֲԴЧ̫.ʵͼݼȻ߲ѯٶ,άĴ̫.
Versatileϵͳûȫֲѯٶ.ûȫͼĲѯڻ,LRU㷨̭õOIM.ڻнȫͼĳò,ʵͼ,άĹ.
Versatileϵͳȫͼݼ,ȫͼɾֲͼͨOIMκβ.նûÿβѯĳȫͼ,ʹOIMĵĿ,Ʒʵ,ҲΪʵṩ˷.
ΪжûĲѯǷڻ,ȥĲѯ,滹ҪѯõȫͼѡͶӰ()·,³3Ϊ.ûĲѯ뻺ĳ,ѯɻֱӶȡ,.ĳӦOIMOûѯĽ,OʵĶѡͶӰ()ɵòѯ,Oӻȡ,ѯٶҪȴӸԴȡٻܿö.ʵ,ĳӦOIMOûѯĽ,ҲɽOΪѯĲֽ.ûڲֽ,򽫸òѯֽ͸Դ,Իȡѯ.ֲѯûҪʱ,ĴЧȻϸ.
жѯǷаϵ,жǵѡǷ̺ϵԼͶӰ()·Ƿаϵ,㷨Ƚϸ,ܻӰѯٶ.VersatileϵͳȫDBAṩѯϵQRV(query relation vector),QRVȷָѯ֮ĵͬϵ,ԼжϹ,ϵͳЧ.QRVά(vn,e1,e2,r).vnʾȫͼ.e1,e2vnĲѯʽ,ͶӰ()·PѡfɣʾȫͼvnִѡΪfĶѡԼͶӰ()·ΪPĶͶӰ(),ͶӰ·ã ,·! ,ѡ( ).e1e2,PfͬʱȱʡʾȡȫͼvnеOIMrʾe1,e2֮Ĺϵ,e1,e2֮Сԡֹ͡ϵ.rΪԡʱ,ȫͼvnִe1ʾĽִe2ʾĽǵͬOIM;rΪʱ,ȫͼvnִe1ʾĽִe2ʾĽ.
2:ͼ1ʾо-ʦһȫͼ,ѯ
ѯ1.ȡõʦΪġо.
ѡʦΪġо,ȻͶӰȡ,òѯOIMʾ
[о:,о:( )]([о:ʦ:=ġ] (о-ʦ)).
ѯ2.гʦΪġо.
ѡʦΪġо,Ȼȥ,òѯOIMʾ
о:գ(ңоʦġ(о-ʦ)).
˳ָ,VersatileϵͳΪӦOIM,Ӷԭʼ·ʽʾ.ԭʼ·ʽӸ󵽸ñʽʾ·,һͨ Ӷ.OIMģַ֧,ԭʼ·ʽбʾɡ(1,2,...)ʽ.
Ȼ,ѯ2ĽOIMѯ1ĽOIM.֮ĹϵQRVʾ
(о-ʦ,!оգ(о:ʦ:=ġ),
о:,о:()(о:ʦ:=ġ),).
ȫDBAṩĲѯϵQRVԪݲֿ,ѯʹ.
ʹøϵͳ,Ȼ,еOIMӦľֲͼ仯ʱ,OI MԴ֮ͳ˲һ,ˢ.VersatileϵͳݲͬӦ ȡˢ(periodical refresh)Ͱˢ(by-demand refresh)ַʽ.
(1) Versatileڼ黺OIM漰ľֲͼǷı,ݱ仯޸Ļ е.ЩҪӦûѯ,ԴӻֱӶȡ,Ȼ,ݲ ӳˢֲ֮ͼĸı.
(2) ЩҪ׼ȷӦûѯ,ˢ¾Եò.Versatileϵͳ ȡˢ·ʽ,ȼ黺OIM漰ľֲͼǷı,ûиı,ֱ ӻȡݣиı,򽫲ѯֽ⵽Դ,жȡ,޸Ļ .
3.3ڻԴĲѯֽŻ
Versatileϵͳ,ͻ˷Ĳѯѯķдʷ﷨,õһOIMѯT,OIQLɵOIMѯSQLɵĲѯ,Ҷʾ(OIM),Ҷʾ(OIM).òѯĲȫͼv,ѡΪf,ͶӰ()·ΪP
(1) v,f,P뻺ĳ,ѯɻֱӶȡ.
(2) (1),ڲѯϵ(vn,e1,e2,r),vnv,rԡ,e1(e2)òѯ,ve2(e1)ʾѡͶӰ()·뻺ĳ,ѯɻֱӶȡ.
(3) (1)(2),ڲѯϵ(vn,e1,e2,r),vnv,r,e2òѯ,ve1ʾѡͶӰ()·뻺ĳ,ӦOIMOԭѯ.,ɽѯTĲ(ԭΪv)O滻õһ²ѯT1,T1TִеOIMȻͬ,T1ĲԻ,ִT1ٶȻTҪö.
(4) (1)(2)(3),ڲѯϵ(vn,e1,e2,r),vnv,r,e1òѯ,ve2ʾѡͶӰ()·뻺ĳ,ӦOIMOԭѯ,ԭѯĲֽɻֱӶȡ.,ӻȡO֮󽻸û,ѯûԲ̶ֽ.,ԭѯ,(5)ķѯֽԴִ.
(5) ,ԪݲֿȡȫͼĶ(ҲһOIMѯ,ΪT),TȡԭѯTеҶ(ȫͼ),õһ²ѯT2.T2Ż,ŻòѯֽΪӲѯ.ѯڵķֽʱ,ҪǾֲOIMڵԴ,ҪǸԴĲѯ.Դֵ֧ӲѯӦԴִ,Ӳѯȫֽ.
4 
һͨ칹ԴϵͳҪɸָԴ,ЩԴ,WWW,޹ģʽṹǿĲѯ,ȫֲѯķֽŻһ.VersatileϵͳģͶֵ̬ĸͳһ칹Դģʽ,þֲֵ̬ģ켯ϵͳȫֵֶ̬,ΪȫֲѯķֽŻ춨˻.,VersatileûûȫͼĲѯ,ԪݲֿⱣDBAṩĲѯϵQRV͸ԴĲѯQCV.ڴȫֲѯʱ,QRVжϲѯǷڻ,ڻе,ӻȡ.ڻ,򲿷ֽڻжûⲿֽ,Դ,ѯֽ⵽Դִ.VersatileĲѯܳԴĲѯ,ûȫֲѯٶ.
ĿоõȻѧ.
߼飺,Ů,1967,ʿ,ʦ,ҪоΪݿͷֲ.
ܱ,1929,,ʿʦ,ҪоΪݿ⼰Ϣϵͳ.
ߵλ(ԶоԺоϾ210003)
ܱ(ϴѧѧ빤ϵϾ210096)
οף
1Bright M W et al.A taxonomy and current issues in multidatabase systems.IEEE Computer,1992,25(3):5059
2Sheth Amit P.Federated database systems for managing distributed,heterogeneous,and autonomous databases.ACM Computing Surveys,1990,22(3):182236
3McHugh J,Abiteboul S,Goldman R et al.Lore:a database management system for semistructured data.SIGMOD Record,1997,26(3):3953
4Roy Goldman,Jennifer Widom.DataGuides:enabling query formulation and optimization in semistructured databases.In:Dayal U,Gray P M D,Nishio S eds.Proceedings of the 23rd International Conference on Very Large Data Bases.San Francisco,CA:Morgan Kaufmann Publishers,Inc.,1997.436445
5Mary Tork Roth,Peter Schwarz.Don't scrap it,wrap it! A wrapper architecture for legacy data sources.In:Dayal U,Gray P M D,Nishio S eds.Proceedings of the 23rd International Conference on Very Large Data Bases.San Francisco,CA:Morgan Kaufmann Publishers,Inc.,1997.266275
6Kevin Chen-Chuan Chang,Hector Garcia-Molina.Boolean query mapping across heterogeneous information sources.IEEE Transactions on Knowledge and Data Engineering,1996,8(4):515521
7Gupta A,Mumick I,Subrahmaman V.Maintaining views incrementally.In:Buneman P,Jajodia Sushil eds,Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data.New York:Academic Press,1993.157166
8Zhuge Y et al.View maintenance in a warehousing environment.In:Widom J ed,Proceedings of 1995 ACM SIGMOD Conference.New York:Academic Press,1995.316327
9Wang N,Chen Y,Yu B Q,Wang N B.Versatile:A scaleable CORBA-based system for integrating distributed data.In:Department of Computer Science and Technology of Tsinghua University ed.Proceedings of the 1997 IEEE International Conference on Intelligent Processing Systems.Beijing:International Academic Publishers,1997.15891593
10Randy Otte,Paul Pafrik,Mark Roy.Understanding CORBA.Englewood Cliffs,NJ:Prentice Hall,Inc.,1996
11Wang Ning,Xu Hong-bing,Wang Neng-bin.A data model and algebra for object integration based on a rooted connected directed graph.Journal of Software,1998,9(12):894898
(,,ܱ.ڴͨͼĶ󼯳ģͼ.ѧ,1998,9(12):894898)
12Wang Ning,Xu Hong-bing,Wang Neng-bin.Construction of global dynamic dictionary in heterogeneous data integration system.Chinese Journal of Computers,1999,22(1):103107
(,,ܱ.Դϵͳжֵ̬乹췽о.ѧ,1999,22(1):103107)
13Wang Ning,Xu Hong-bing,Wang neng-bin.Construction of global dynamic dictionary in heterogeneous data integration system.Chinese Journal of Computers,1999,22(1):3138
(,,ܱ.칹ԴϵͳлԴĲѯֽŻ,ѧ,1999,22(1):3138)
ոڣ1998-04-20
޸ڣ1999-01-20
