ѧ
JOURNAL OF SOFTWARE
1999 10 8 Vol.10 No.8 1999



ṹݲѯĴŻ
 ޡܱ
ժҪṹݵصݵĽṹ,ģͶڴͼ,,ѯ̱Ƕͼ.,ͨ·ʹѯӸӻ.ϸ칹ԴϵͳVersatileвȡİṹOIM(model for object integration)ĲѯŻ,ѯƻɡ·չ·ͻԴ֪ʶ3ֲѯŻ.½ܵķͬİṹģ.
ؼʡṹ,ѯ,Ż.
ͼšTP311
Querying and Optimizing Semistructured Data
CHEN Ying WANG Neng-bin
(Department of Computer Science and Engineering Southeast University Nanjing 210096)
Abstract Semistructured data has irregular or incomplete structure. In recent research on semistructured data sources and integration for heterogeneous data sources, models for semistructured data are based on direct graph with root vertex, so querying semistructured data is equivalent with searching in graph. In addition, path with wildcard characters brings more complexity in query processing. In this paper, the authors present the strategies deployed in querying and optimizing OIM (model for object integrating) data in Versatilea system for integrating heterogeneous data sources. Algorithms for generating query plan and extending path are discussed in detail and three optimization methods, path index (Pindex), level index(Lvindex) and knowledge of data source are introduced. Also the approach can be applicable to other graph-based semistructured data easily.
Key wordsSemistructured data, query processing, optimization.
ṹ(semistructured data)صݵĽṹ(irregular)(incomplete)1,Ϊݲѭ̶ģʽṹģʽϢģʽ仯졢ģʽͳһ洢ص.ṹһԴ. ֱ԰ṹԴ,Webݡ͵ĵ(ӱ,TEX,WORD)ʼ,ЩԴǵ͵İṹݣ Ϊ칹ԴϵͳĹģ,Versatile2,TSIMMIS3ݺLORE4,֮ԲðṹΪģΪṹģͼṹ,ͬʱҲṹ.WWW(World Wide Web)ռͶ칹ԴϵͳмɵҪ,ṹݵоܵ.Ƕ԰ṹݵģͣ25ݡѯԣ25,7ݡѯ1,4,6,7Լݴ洢ͱʾ8ݶһо.ṹɴиڵͼʾ,ף2ݲOIM(model for object integration),ף3,4ݲOEM(object exchange model),ף5ݲͼݿ(graph database).нڵʾӶ,߱ʾľۺϹϵ,ڵϵıǱʾ.ṹĲѯԲOQL(object query language),ף2ݲOIQL(object integration query language),ף4ݲLOREL,ΪӦṹģʽӴûȫ˽ģʽص,ѯ֧ͨ·Ĳѯ,ף5֧·ʽ.,ṹݵĲѯǶͼ,ص㣺ݺģʽϢͳһ(),,ѽϵݿѯƵĴŻݽṹ,֧ݵͨԶתͼпܴȦ,ڴͨ·ʱ,Ӧѯѭ.һ,԰ṹݵͼѯֻܻ,ڱͼĹѰҷ·,Ȼ,ַͼܴʱЧʺܵ.Ϊ˿˷ȱ,ף4ݲݵ(DataGuide),ף9ݲͼģʽ(graph schemas)ķ,ǶǴͼгȡṹݵģʽϢָѯŻ.,ף4ݻģʽһά㷨,߲ѯٶ.,ģʽ仯Դ,ĳЩWeb,ģʽϢЧʽϵ(ף4вOEMתΪDataGuide㷨൱ڽȷԶNFAתΪȼ۵ȷԶDFA,,临Ӷȿָ).
ϸ칹ԴϵͳVersatileвȡİṹݵĲѯŻ.Versatile6,7ǶϴѧƵһCORBA8ݵ칹Դϵͳԭ,ּԡ弴áʽԲͬԴ,ϵͳܵȻѧ.Versatileвö󼯳ģOIM10ΪԴģʽģ,ѯOIQL.ѯQI(query integrator)OIQLѯֽԴ.Versatile,ЩԴ,RDBMSOODBMS,ڱݹ,Ӧİװ(wrapper)OIQLΪزѯ(SQL,OQL),ٽṹתΪOIM󣻶ĳЩԴ,ļϵͳWeb,ûݲѯ,VersatileаװݰװΪOIM,ȻʵʩOIMĲѯ11.ĽڸԴνвѯ,˲漰Դ*1.вѯŻԲ·Դ֪ʶ,ЩŻʩں̶ܴϼͼΧ.ĵȻǻOIM,ͬʱҲĻͼİṹģ.
1OIMģ
1.1OIM
 OIMģVersatile еİṹģ.OIMģ,һԪ顴OID,n,t,cʾ,OIDǶʶ,nʾ,tʾ,cʾֵ,ԪΪ.t˿Աʾ(integer,char,float,string),ɱʾ(set,list,bag)ɱ䳤ͣCLOB,BLOB(ref).һ,ʾöۼ,ΪöӶ,ֵӶʶļ.OIMģ,صһۼһ,һOIM.,ϵݿһűļϵͳһļ,WWWĳͨêӵHTMLļļϾɿOIM.һOIMOôͨͼʾOr,V,E,нڵ㼯Vʾ,߼Eʾ֮ùϵ.ڵrһۼ,͵.OID,OIM·ʾ󼯺ϻôνʵ·ʾ,·ͨ,潫ͨ˵.
OIQLOIMĲѯ,DML(data manipulation language)DDL(data definition language).вѯselect...from...where...ʽ(sfw).
1.2OIM
1ͼ1ǴһWebҳõOIM**.Ǽϵʦѧ.

ͼ1OIMʾ
ͼ1еOID,&r,&1,&2ϵͳ,֤ΨһҶû͸.ʾΪ(&r,CS,REF,{&1,&2,&3,&4}),ͼе·CS,&1,&2,&3,&4&rӶ.ڵԱʾΪ(&15,Name,STRING,Wang),ԭӶ,Ӧһ·CS:TEACHER:Professor:Name.OIMͼڿܶӦ·,ͬʱ,һ·ܱʾ.,·CS:TEACHER:Professorʾеġڡ󼯺.·CS:*:Nameʾ˵,з*ƥ.
OIMͼڿܺȦ,·*:PublicationչOIMڿԶӦ·,,CS:Publication,CS:STUDENT:Doctor Student:Publications:Publication,CS:Publication:Author:Doctor Student:Publication,ԭǴ߹ɵĻ&8&18&4&10&8.,ڲѯʱӦܹЧͳ·չ.
OIQLĲѯ.
Q1:ѯڵϢ.
Select o from CS:Teacher:Professor o where o.Name=Li
Q2:ѯϢ.
Select o from CS:Publication:Author o
Q3:ѯ,ʿ.
Select o from CS:Publication o where o.Author:*:Doctor Student:Name=Wang
Q4һйϢOIMP(ļϵͳWebҳ)ڴйԱϸϢ.Ҫѯ24ĲʿϸϢ.*2
Select o1,o2 from CS:*:Doctor Student o1, P:Person o2 where o1.Name=o2.Name and o2.age24
ע,ѯṹOIM,Q4Ľo1o2ġOIM󲢡.
2OIMѯ
2.1йطźͶ
Ϊ˵,һЩźͶ.oʾOIM,Name(o),TYPE(o)VAL(o)ֱʾơͺֵ,ӦֵNAME,TYPEVALʾ.Orָ.OIMo·po=o.n1:n2:...:nk,k1,n1NAMEȣ*,?},1ik,nkNAME,ʾӽڵoξn1:n2:...:nkĽڵ㣻*Ϊͨ,ƥκζ,*ƥⳤȵĶ.ͨ·ǰṹݲѯҪص,󷽱ûԽṹϤݽвѯ.·pĳȣp=k.ر,o=Orʱ,pOrǾ·.Orеľ·ϼΪP.
1(·չ). ·չX:po{o1,o2,...,om},Xɺ·չ㷨(㷨2)õ.oչ.o=or,ƾ·pOrǶoi(i=1,2,...,m)Orеһ·.oiо·ΪP(oi).
X(po)дӽڵo·poܵĽڵļ,ΪorеĽڵ޵,,X(po)޼.üǰṹݲѯҪ,൱ڶԹϵݿĻɨ.
2(·). OIMooĻ·Ko:o2p,Ko(o)={pX(po)}.
Ko(o)дӽڵo䵽o·.ͼдȦ,,PK(o).˵OIMж·ʾĶ,ûдѯ,Ҳ˲ѯŻѶ.ʵ,ǸȤKo(o)һЩȼ·ļ,ǿڲѯд,·չʱٹ.
2.2 ѯ
OIMĲѯǣOIQL﷨,ѯд,ɲѯƻ,Ż,ִ,ؽҲOIM.
ѯдOIQLдΪĲѯʽ,whereӾеĲʽв·,,Q1дΪQ1: Select o from CS:Teacher:Professor o, o.Name o1 where o1 =Li.Ҫµı.ƪ,Ĳ۲ѯд.
ѯƻʾTQ=(V,E)ʽ,ÿڵvVʾһֲ,Ϊڵ,OP(v){,,,,},ֱʾڵչӡѡͶӰ͹Ȳ.
3Ͳ. eԪ(vi,vj,Output(vi,vj))ʾ,Output(vi,vj)ǲڵvivjOutput(v)=vvĸڵOutput(v,v);ڵvInput(v)=vvӽڵOutput(v).ر,ҶڵϺ͸ڵΪ.ڲڵvвıΪGen(v).
ڲѯTQ,ڵ䴫ݵԪ鼯,ʵԪĹ.ڵvInput(v),Output(v)Gen(v)Output(v)Input(v)Gen(v).
ڵбʾΪߵĸ,ΪǿڵʵʴݵԪ鼯,ͼ( )ʾ,{ }ͬʱ,Ϊʾ,ñʾ//*3.ѯQ1Ĳѯͼ2(a)ʾ.̴Ҷڵ㵽ڵ㷽ɵϽ,ڵ˵.

Q1(a)ѯƻQ2(b)ѯƻ
ͼ2
ڵ(1): (Ҷڵ)·չO1=X(TEACHER:PROFESSOROcs,ΪCSOIMĸ,չ·չڵOCS,չ·TEACHER:PROFESSORչ(ڵ㼯)ڱO1Уڵ(5)ĽϣO1ʾ,Ԫ(o1)ļ,o1ͨչڵOCSչõӦQ1,õ{&5,&6};
ڵ(2): (O1),еo1O1,O2=X(NAMEO1),O1O2뵽Уڵ(4)Ľ(O1,O2)ʾ,Ԫ(o1,o2)ļ,o2ͨڵo1չõӦQ1,õ{(&5,&13),(&6,&15)}
ڵ(3): ѡ,µıӦQ1,õ{(&5,&13)}
ڵ(4): ͶӰ,µıӦQ1,õ{(&5)}ע,ͶӰظԪ飻
ڵ(5): н,뼯ϹµOIMORESULT.
֪,ϵ/ʵʴ˶Ԫļ.ѡԭӶ,˲ѯӦ·չ.Q1whereӾԭӲʽo.name=Li,·չoʱ,ֱжo.name,Ϊڽڵoչ·name󼯺,չڵ(4),ҲҪвѯдҪԭ.Q3еo.ɴ˿ɼ,·չOIMѯȼߵĲ,ڽвѯŻ.
ѯQ4漰OIMĲ,ѯƻͼ2(b)ʾ.нڵ(6)Ӳ,Խڵ(3)ͽڵ(5)ļ.Ӳµı.
2.3 ѯƻ
ѯƻɹ̸ݲѯ,ڵ//.OIMѯƻ㷨.,ٶwhereӾиԭӲʽͨAND,ÿԭӲʽ漰.ɹиÿɵĲڵα,i=1,2,...,ӦĽڵviʾ.
㷨1. ѯƻ
룺ƥġOIQLѯQ;
QĲѯƻTQ;
裺
(1) ΪfromӾÿ·pOչڵXO,£
(1.1) pǾ·,ԸΪչڵչҶڵ,{O},{O}
(1.2) pһO·,OΪչڵչڵXO,i,vjXO,j=Newest(O,i),Newest(O,i)=max{jjiOOutput(Vj)};{O}Output(Xj){O};
(2) ΪwhereӾÿԭӲʽBѡӲڵBOBO1,O2,£
(2.1) B漰һO,ѡڵBO,ivjBO,j=Newest(O,i);ǫ;Output(vj);
(2.2) B漰O1,O2,Ӳڵ㦣BO1,O2,ivjBO1,O2vkBO1,O2,j=Newest(O1,i),j=Newest(O2,i);;Output(vj)Output(vk);
(3) ȻӲڵ㦣vj,vk,£
(3.1) NoParent={v|v,vv},vj,vkNoParent,Output(vj)Output(vk),ȻӲڵ,vj,vk,vjvkԪ鼯Output(vj)Output(vk)ȣvjvj,vkvkvj,vk;Output(vj)Output(vk);
(3.2) ظ(3.1)ֱȻӵĽڵ;
(4) ͶӰڵ㦰,£
(4.1) SʾselectӾбļ,vNoParentOutput(v)S,ͶӰڵ㦰Output(v)SvOutput(v)S;Output(v)S;
(4.2) ظ(4.1)ֱͶӰĽڵ;
(5) ڵ㦲,v,vNoParentORESULT.
3OIMѯŻ
OIMвѯŻ̬Ż·չŻʽ.̬ŻǶԲѯƻʵʩȼ۱任,ҪУ(1) ѹѡͶӰڵ,,ͼ2(b)еѡڵ(7)ѹ(2) ·,OIMѯһҪص,ν·ָ,·չӼչ.,ѯĿ¼Database鼮.
Q5: select o from Store:Book o where o.*:subtitle=Database
ڶoչ·*:titleõļϿܴܺ,ֻҪһoo=Database,չ.
ɲѯƻ֪,·չOIMѯĻ,㷨2ù(breadth first search,BFS)·չ.
㷨2. ·չ㷨*4
룺OIMo·po=o.n1:n2:...:nk
oʼ·poܵĽڵ㼯X(po)
裺
(1)o.level0;Queue{o};oc=Queue.Get;  ȡȥQueueĵ1Ԫ
(2)for i=1 to k do
(2.1) while (oclevel=i-1) do
(2.1.1) if niNAME then for oc ÿӶ oc do
(2.1.1.1) if NAME (oc)=ni and oc.statechecked then Queue.Add(oc); oc.level oc.level+1; oc.state=checked
(2.1.2) if ni=? then for ocÿӶoc do
(2.1.2.1) if oc.statechecked then Queue.Add(oc); oc.level oc.level+1; oc.state=checked
(2.1.3) if ni=* then ocΪչڵ,BFSչⳤֱҵнڵoc, oc.statecheckedName(oc)=n(i+1), Queue.Add(oc)oc.level oc.level+2; oc.state=checked
(2.1.4) oc=Queue.Get
(3)return Queue.
ͼȦĴںͳ·,·չܴܺҽϷʱ,رǲ(2.1.3),Ҫ*BFSչ.Ȼ,·Ժչ,ӶⲻҪĽһչ.,LORE4еֵVindexͱ(Lindex)ҲOIMѯŻ.֮,ĽܼչĲѯŻ.
3.1 ·
·Pindex·pӳ䵽X(p),Hashʵ,,չʱֱͨõ,Դӿ·չٶ.ѯɲѯƻʱ·ӦĲڵ(XڵPindexڵ).·ִʽ˹ϵͳԶ.ԴԱͨOIQLDDLϵͳԶϵͳͳƵóķƵʴ·,·Ƶʵĳһ̶ֵfHʱ,ѯԶΪ·Pindex.
·ڱʾͨ·,ʺϾ·,Ժܿڲѯĳʼ׶չֲĽڵ㼯.
3.2 
4(). oĲlevel(o)=min({k|k=|p|,pP(o)pͨ}).
LvindexκͶĶԪӳ䵽oid,ʵֶĿٶλ.LvindexرʺڲͬĶûظ,,Versatileдӹϵݿ(RDBWrapper)ļϵͳ(FSWrapper)еİṹ.·ֻչ·ͨĲ,ͨع·.,ʼOIMEmail,չ·Email:Address:To:Country,Lvindex(3,Country)Եõڵ㼯.
3.3Դ֪ʶ
ڽռ,ض֪ʶԼΧһձ׼.ͬ,ڰṹԴĲѯ,ȻݵĽṹͰ,ĳԴ,ṹٵشһЩṹϵԼ,ǳƴΪԴ֪ʶ.Դ֪ʶڲѯر·չЧ.Ϊ,Ƕһּ򵥵(knowledge definition language,KDL)Դ֪ʶ.KDLһЩ,ÿһʵԼ·.ͼ1еһǣProject:Member,˵Member·нProject֮(ȥͨ*?)TEACHER:Professorǹ.KDL·չǰȥҪռͷִ·.,KDLĳ̶ֳϿڹ·ͼ,ͨڹӡ,ƭѯΪĳ·Ƿܾѯ,ʱõͨ.
,˵HTML﷨WebԴͨKDL.,WebԴİṹģǴӱͼõ,֮,ͼǴHTMLǵһͨõWebԴİṹģ.
(1) HEAD:TITLE
(2) TABLE:TR
(3) ...
Ȼ,KDLõĽṹԼȫԴӰװOIMʱ̬,ҪԴOIMġ걸Ĺ򼯺,Ӵ,Ԫݴ洢ܴ.
4
ṹݵĲѯؼ칹ԴɺԴһоص.ϸVersatileж԰ṹݵĲѯŻ,˲ѯƻĹ㷨3Լ·չ۵Ż.OIMôͨͼʽ,,ĵļͬͬƽṹİṹԴģ,OEM.ǽһоǻڰṹԴͼչKDLԼKDLԶά.
עоõȻѧ.
*1һּ׵ĽѯԶԴOIMķǽOIMͬһص㣬ʵʩѯ
**WebҳͨWeb WrapperȡװOIMʵʵWebҳϸӣǼ򻯵ӣ
*2ǼٶûͬԱҺԿе칹⣮
*3ϸؽʾOIDڵ䴫ݵݣͬһʶΪ˱ǵĶӦϵ
*4㷨δǴ·ʵʼʱԴ·践ؿռ
ͨѶϵ:ܱ,Ͼ210096,ϴѧѧ빤ϵ
߼飺,1973,ʿ,ҪоΪݿ,.
ܱ,1929,,ʿʦ,ҪоΪݿ,Ϣϵͳ.
ߵλϴѧѧ빤ϵϾ210096
ο
1Serge Abiteboul. Querying semi-structured data. In: Foto Afrati, Phokion Kolaities ed. Lecture Notes in Computer Science 1186, Database TheoryICDT'97. New York: Springer-Verlag, 1997. 118
2Wang Ning, Chen Ying, Yu Ben-quan et al. Versatile: an extensible integration system for heterogeneous data based on CORBA. In: Zhou Li-zhu ed. Proceedings of the 1997 IEEE International Conference on Intelligent Processing Systems(ICIPS'97). Beijing: International Academic Publishers, 1997. 15891593
3Chawathe S, Garcia-Molina H, Hammer J et al. The TSIMMIS project: integration of heterogeneous information sources. In: Proceedings of the 10th Anniversary Meeting of the Information Processing Society of Japan. 1994. 718
4McHugh J, Abiteboul S, Goldman R et al. Lore: a database management system for semistructured data. ACM SIGMOD, 1997,26(3):5466
5Buneman P, Davidson S, Fernandez M et al. Adding structure to unstructured data. In: Afrati Foto, Kolaities Phokion ed. Lecture Notes in Computer Science 1186, Database TheoryICDT'97. New York: Springer-Verlag, 1997. 336350
6Goldman Roy, Widom Jennifer. DataGuides: enabling query formulation and optimization in semistructured databases. In: Jarke Matthias, Carey Michael, Dittrich Klaus R eds. Proceedings of the 23rd Very Large Database Conference. San Francisco: Morgan Kanfmann Publishers, Inc., 1997. 436445
7Buneman P, Davidson S, Hillebrand G et al. A query language and optimization techniques for unstructured data. In: Jagadish H V, Inderpal Singh Mumick eds. Proceedings of the ACM SIGMOD Conference'96. New York: Association for Computing Machinery, Inc., 1996. 505516
8,,᱾Ȩ.칹ԴϵͳаṹݵĴȡʾ.ѧ,1998,25():205207
(Chen Ying, Wang Ning, Yu Ben-quan et al. Access and representation service for semistructured data in heterogeneous data sources system. Computer Science, 1998,25(supplement):205207)
9Fernandez M, Suciu D. Optimizing regular path expressions using graph schemas. In: Urban S D, Bertino Elisa ed. Proceedings of the 14th International Conference on Data Engineering. Los Alamitos: The Printing House, 1996. 1423
10,,ܱ.ڴͨͼĶ󼯳ģͼ.ѧ,1998,9(12):894898
(Wang 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)
11,,᱾Ȩ.칹Դϵͳаװоʵ.:.7ȫ߻飨NCYCS'98.Ϻ:Ϻѧ׳,1998.352359
(Chen Ying, Wang Ning, Yu Ben-quan et al. Wrapper for heterogeneous data sources systemresearch and implementation. In: Fu Yu-xi ed. Proceedings of the 7th National Conference of Youth Computer Scientist. Shanghai: Shanghai Scientific and Technological Literature Publishing House, 1998. 352359)
1998-06-02յԭ,1998-09-01յ޸ĸ
