ѧ
JOURNAL OF SOFTWARE
2000Vol.11No.2P.265-270



ռѯ·ļɴ
⾩
ժҪݿо,·ͿռѯΪص,ȻڴпռԼ·ѯʱ,Ҫݿϵͳṩ·ͿռѯĹ.Ϊ˴·еĿռԼ,ദ:(1) ռǷ·֮ǰԤ;(2) ռǷ·֮ǰԤѡȡ.,ӦеĿռӡR-ռͿռ༼,4ּɵĿռ·ѯ.
ؼʣռѯ,·,ѯŻ,ѯ.
ţTP311
Integrated Processing Strategies for Spatial Query and Path Search
WU JingJING NingCHEN Luo
(School of Electrical Engineering National University of Defense Technology Changsha 410073)
AbstractPath search and spatial query are considered as two independent topics in database research.The processing of path query with spatial constraint needs both path computation and spatial query.To provide path computation with spatial constraint,two processing strategies are considered:(1) whether pre-processing spatial operation before path computation,and (2) whether pre-filtering spatial objects before path computation.Based on these two strategies,four integrated spatial path query processing approaches are proposed in this paper.
Key wordsSpatial query,path search,query optimization,query processing.
·ѯںܶӦжеĹ,Ϣϵͳϵͳй滮.Ȼ·ѯ硰ҳAB·ӦбṩĹ,,ȽӦȴԽԽҪṩпռԼ·ѯ.оԼĿռ·ѯ,ռ·ѯ:
Q1:ҳABĽε1000·;
Q2:ҳABĲˮû·;
Q3:ҳABĲ·.
ѯQ1ǵϵͳĿռѯ,Q2ڽѴпĲѯ,Q3ΪӵṩҪ֧.
һռ·ѯҪ·()Ϳռѯ,νɡָڿռ·ʱ,Ϊȷ·(һ·ָһ·ڽ·ڵĵ·.ͼ,ýڵģ⽻·,ñģ·)ǷռԼ,ռѯ·һ.оڸ,ռѯ·ڿռ·ѯŻ.
Ϊ˴ռ·ѯ,Ҫоܵദ.,ڽ·֮ǰԤռ佻,Ӷཻ·εʵϵ;෴,·ʱٶ̬֤·ཻ,ǳַΪ·Ԥ.ͬ,ҲԤʱ˵Լ,ӶΪĿռѯСռ;෴,ռѯռ,ǳַΪԤ.
Ļڡ·Ԥ͡Ԥϲ,ֿռ·ѯŻ.ۺӦÿռӣ1,R-2ݡռ3ݺ·4ݼ,Чʵֿռ·ѯԵļ.
صо·3,4ݺͿռ䴦1,2,5.ĵĿǼм(ռӡR-ռ)Чؽռ·ѯ.ǵĳ6,ڲѯԵԺʽнϴĸĽ.
ĵ1ڽо.2ڽܿռѯ·.34ֿռ·ѯ.ܽȫ.
1 о

ݿо,·ΪԼĴݱհ(transitive closure)4,ף3ĿռŻȦ(cyclic)ͼ.
ڿռѯ,R-2Ƕάռݴȡ,ף7ŻR-㷨.ף1,5˸ֿռӼ.ĵоص㲻·ռѯ㷨,Ǽеļռ·ѯŻ.
2 ռѯ·
2.1 ռͼݱʾ
Ϊ˴Q1ռ·ѯ,ݿ洢ռ:(1) ȫߵĿռ;(2) ȫĿռ.ʾߺݽṹ.
LINK.LINK洢ͼϵȫ,ÿһLINKԪʾߵ.ái,j,MBR,&OaʾLINKԪ,ijֱǱߵʼڵֹڵ,wǱߵĳ,MBRǸߵСΧ,&OaʾñߵĿռݵ.ڱߵĿռݿܴܺ,Ǳ䳤,,ֱӴLINK.
AREA.AREA洢ͼϵȫ.ÿһAREAԪʾ.áa,h,MBR,&OpʾAREAԪ,aʶ,h߶,MBRǸСΧ,&OpʾĿռݵ.
ARCļ.ARCļ洢бߵĿռ.ÿһͶռʸʾ,ʾռ,ÿʸX-Y-ʾ.
POLYGONļ.POLYGONļ洢ȫĿռ.ռ״ڱߵ״,֮ͬǿռĵ1ռһռͬ.
ͼ1˵LINKARCļԼAREAPOLYGONļ֮Ĺϵ.

Fig.1Map data representation
ͼ1ͼݱʾ
2.2 ·
LINKģͼиϢ˽ṹ,·LINKԪнеݹ鴦,SPijʾӽڵiڵj·.ռ·ѯ·,Ӧúܶе·㷨,Dijkstra㷨.
2.3 ռѯ
3ֿռѯɿռѯ.
ռཻ.ռཻжһǷĳһཻ,һplane-sweep1һ.ǶԪ,ֱLINKԪĿռ&OaAREAԪĿռ&Op.ཻ,TRUE,򷵻FALSE.
ռ.ΪЧĳһཻ,ǲR-2ݼ,R-ĿǰӦ㷺Ŀռ.
ռ.ף1ĿռӼCPUI/OŻ,ѡ÷ʵֿռཻ.
3 ռ·ѯ

ԿʼQ1ĲѯΪۼɵĿռ·ѯ.
3.1 ѯļ
ǿռ·ļ:(1) ǷпռཻѯԤԤȷߺཻϵ;(2) Ƿ˲ռԼ.
1(ռཻԤ).ռ(spatial search,SS)ռ(spatial join,SJ).
ڴѯQ1,ÿΪ·ı߱ڿռԼЧ֤.Ϊ֤һߵЧ,Ҫпռཻѡཻ.ཻȫԼaltitude1000 (ں1000ס),Ч.ֿռཻѯ·ʱÿı߽,ǳַΪռ.
෴,ռཻ·֮ǰеķΪռ.ڿռ,бߺཻϵͨLINKAREAĿռһʵཻϵ.·ʱ,Ҫ֤ıߵЧ,ཻϵнм,Ҫκοռ䴦.
2(˲ռԼ).(filtering,F)(no filtering,NF).
ڼѯQ1ʱҪĳཻ,ȫ򼯺Ͻ,ǳַΪ(no filtering).෴,Ҳȹ˵Լaltitude1000,Լһ.,ռཻͿһСġԼϽ,ַΪ.
,ǵ4ֿռ·ѯ:
.ռͷˡSSNF(spatial search and no filtering);
.ռˡSSF(spatial search and filtering);
.ռӺͷˡSJNF(spatial join and no filtering);
.ռӺˡSJF(spatial join and filtering).
3.2 ռͷˡSSNF
SSNFڴռʱ,ÿıAREAϽпռཻ.SSNFԴѯQ1Ĳͼ2ʾ.

Fig.2Spatial search and no filtering strategy
ͼ2ռͷɲ
Step 1.AREAеռ,R-.,ߺཻR-ѡ,ֱӶ·оÿ߽пռཻ(ߺĿռཻҪȡARCPOLYGONļеĿռʸ,ҪӦplane-sweep1ݼбǵཻ,ռཻI/OCPUϴ).
Step 2.·㾭ߡi,j,w,MBR,&Oaʱ,MBRR-ཻ,ɺѡཻ򼯺.ÿһѡ(a),SSNF¼:AREAмԪ顴a,h,MBRp,&Op;h1000,&Oa&OpĿռཻ;a,h,MBRp,&Opߡi,j,w,MBRa,&Oaཻ,ߡi,j,w,MBRa,&Oa·ı,ֹñߵ·.
SSNFԿԱʾΪ:
{SPAB(i,j,w,MBRa,&OaSPAB)(a,h,MBRp,&OpAREA)
(i,j,w,MBRa,&OaLINKh1000&Oa&Op=True)}.
3.3 ռˡSSF
SSNFԲͬ,SSFԹAREA(ͼ3ʾ),ѯ:
Step 1.AREAѡȡaltitude1000Ԫ鲢ʱAREASP֮,ֹ˲Ϊռѯһ.
Step 2.ΪAREASPR-.
Step 3.·оߡi,j,w,MBRa,&oaʱ,MBRaAREASPR-вཻĺѡ.R-a,h,MBRp,&OpСΧMBRpMBRaཻ,&Oa&OpĿռཻ,,ñЧ.

Fig.3Spatial search and filtering strategy
ͼ3ռɲ
SSFԿԱʾΪ:
AREASP={a,h,MBRp,&Opa,h,MBRp,&OpAREAh1000},
{SPAB(i,j,w,MBRa,&OaSPAB)(a,h,MBRp,&OpAERASP),
(i,j,w,MBRa,&OaLINK&Oa&Op=True)}.
3.4 ռӺͷˡSJNF
SJNF(ͼ4ʾ)ȶLINKAREAпռ,.Ԫ硴i,j,aʾߡi,jaཻ.пռŵ,·ʱؽд۸ߵĿռཻ,ֱֻϲ.ɵĿռ漰ߺཻĿռѯ.SSNFĴ:
Step 1.LINKR-.
Step 2.AREAR-.
Step 3.LINKR-AREAR-Ŀռ,ӱJOIN-INDEX,Ԫ顴i,j,aʾߡi,jaཻ.
Step 4.·ߡi,j,w,MBRa,&Oaʱ,i,jڲѯJOIN-INDEX;JOIN-INDEXдԪ顴i,j,a,aAREAԪ顴a,h,MBRp,&Op;h1000,ߡi,j,w,MBRa,&OaЧ,ñЧ.

Fig.4Spatial join and no filtering
ͼ4ռӺͷ˲
SJNFԿԱΪ:
JOIN-INDEX={i,j,ai,j,w,MBRa,&OaLINK
a,h,MBRp,&OpAREA&Oa&Op=True},
{SPAB(i,j,w,MBRa,&OaSPAB)(i,j,aJOIN-INDEX)
a,h,MBRp,&OpAERAh1000}.
3.5 ռӺˡSJF
SJF(ͼ5ʾ)Ͽռӷ͹˷,䴦:
Step 1.LINKR-.
Step 2.AREAѡaltitude1000Ԫ顴a,h,MBRp,&Op,ȻЩԪ齨R-.
Step 3.Step 1Step 2R-Ŀռ,JOIN-INDEX,Ԫ顴i,j,aʾߡi,jaཻ,aaltitude1000.
Step 4.·ߡi,j,w,MBRa,&Oaʱ,i,jڲѯJOIN-INDEX;Ԫ顴i,j,aJOIN-INDEX,ñЧ,ñЧ.

Fig.5Spatial join and filtering
ͼ5ռӺ˲
SJFԿԱʾΪ:
JOIN-INDEX={i,j,a|i,j,w,MBRa,&OaLINKġa,h,MBRp,&Op
AREAh1000&Oa&Op=True},
{SPAB(i,j,w,MBRa,&OaSPAB)(i,j,aJOIN-INDEX)}.
4  
оԼĿռ·ѯ,ִռ·ѯŻ:(1) ߺĿռԤ;(2) ռԼԤ.Ż,4ֿռ·ѯŻ.ǽеĳʵ6ݱ,ֲڲͬ¸ŵ.ĵо⸴ӿռѯĴ,ݲѯݿռ,ѡ񼯳ɵĲѯŻ.
ĿоõѧѧԤĿͽʦ
߼飺⾩,Ů ,1968,ʦ,ҪоΪϵͳ,Ϣ.
,1963,ʿ,,ʿʦ,ҪоΪϢϵͳ,ݿ⼼.
,1973,ʿ,ҪоΪݿ⼼.
ߵλ⾩(ѧѧӹѧԺɳ410073)
(ѧѧӹѧԺɳ410073)
(ѧѧӹѧԺɳ410073)
οף
1Brinkhoff T,Kriegel H,Seeger B.Efficient processing of spatial joins using R-trees.In:Peter Buneman,Sushil Jajodia eds.Proceedings of the ACM SIGMOD International Conference on Management of Data.New York:ACM Press,1993.237246
2Guttman A.R-tree:a dynamic index structure for spatial searching.In:Beatrice Yormark ed.Proceedings of the ACM SIGMOD International Conference on Management of Data.New York:ACM Press,1984.4557
3Huang Y W,Jing N,Rundensteiner E A.Effective graph clustering for path queries in digital map databases.In:Ken Barker,Tamer Ozsu M eds.Proceedings of the 5th International Conference on Information and Knowledge Managemen.New York:ACM Press,1996.215222
4Agrawal R,Dar S,Jagadish H V.Direct transitive closure algorithms:design and performance evaluation.ACM Transactions on Database Systems,1990,15(3):427458
5Gunther O.Efficient computation of spatial joins.In:Proceedings of the IEEE International Conference on Data Engineering.Los Alamitos:IEEE Computer Society Press,1993.5059
6Huang Y W,Jing N,Rundensteiner E A.Integrated query processing strategies for spatial path queries.In:Proceedings of the IEEE International Conference on Data Engineering.Los Alamitos:IEEE Computer Society Press,1997.477486
7Bechmann N,Kriegel H,Schneider R et al.The R*-tree:an efficient and robust access method for points and rectangles.In:Garcia-Molina Hector,Jagadish H V eds.Proceedings of the ACM SIGMOD International Conference on Management of Data.New York:ACM Press,1990.322332
ոڣ1998-11-30
޸ڣ1999-03-15
