全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

空间数据库中连接运算的处理与优化

DOI: 10.11834/jig.200307264

Keywords: 数据库(520?4050),空间数据库,空间连接运算,R树索引,动态编程,查询优化

Full-Text   Cite this paper   Add to My Lib

Abstract:

空间数据库的性能问题严重制约了它的应用与发展.由于空间连接运算是空间数据库中最复杂、最耗时的基本操作,因此其处理效率在很大程度上决定了空间数据库的整体性能.尽管目前已经有许多空间连接算法,但空间连接运算的代价估计和查询优化仍然有待进一步研究.众所周知,大部分空间连接算法都是基于R树索引实现的,如果参与空间连接运算的关系上没有索引或只有部分索引,那么就需要使用特殊的算法来处理.另外,各种算法的代价评估模型需要一个相对统一的计算方法,实践证明,根据空间数据库的实际情况,使用I/O代价来估计算法的复杂性较为合理.在此基础上,针对复杂的空间查询中可能出现多个关系参与空间连接运算的情况,故还需要合理地应用动态编程算法来找出代价最优的连接顺序,以便最终形成一个通用的算法框架.通过对该算法框架的复杂性分析可以看出,在此基础上实现的空间数据库查询优化系统将具有较高的时空效率,并且能够处理非常复杂的空间查询

References

[1]  [1]Brinkhoff T, Kriegel H P, Seeger B. Efficient processing of spatial joins using R-trees [A]. In: Proceedings of the 1993 Association for Computing Machinery Special Interest Group International Conference on Management of Data [C].Washington,D. C. USA,1993: 237~246.
[2]  [2]Huang Y W, ling N, Rundensteiner E A. A cost model for estimating the performance of spatial joins using R-trees [A].In: Proceedings of Ninth International Conference on Scientific and Statistical Database Management [C]. Olympia, Washington USA,1997: 30~38.
[3]  [5]Lo M L, Ravishankar C V. The design and implementation of seeded trees: an efficent method for spatial joins [J]. IEEE Transactions on Knowledge and Data Engineering, 1998,10 (1):136~152.
[4]  [6]Lo M L, Ravishankar C V. Spatial hash-joins [A]. In:Proceedings of the 1996 Assciation for Computing Machinery Special Interest Group International Conference on Management of Data[C]. Montreal,Cananda, 1996: 247~258.
[5]  [8]Koudas N, Sevcik K C. Size separation spatial join[A]. In:Proceedings of the 1997 Assciation for Computing Machinery Special Interest Group International Conference on Management of Data[C]. Tucson, Arizona USA, 1997: 324~335.
[6]  [10]Giüting R H, Schneider M. Realms: A foundation for spatial data types in database systems[A]. In: Proceedings of the 3rd International Symposium on Large Spatial Databases [C].Singapore, 1993: 14~35.
[7]  [3]Mamoulis N, Papadias D. Integration of spatial join algorithms for processing multiple inputs[A]. In: Proceedings of the 1999 Association for Computing Machinery Special Interest Group International Conference on Management of Data [C].Philadelphia,Pennsylvania USA, 1999: 1 ~ 12.
[8]  [4]Huang Y W, Jing N, Rundensteiner E A. Spatial joins using Rtrees: Breadth first traversal with global optimizations [A]. In:Proceedings of 23rd International Conference on Very Large Data Bases [C]. Athens ,Greece, 1997: 396~405.
[9]  [7]Patel J M, DeWitt D J. Partition based spatial merge join[A].In: Proceedings of the 1996 Association for Computing Machinery Special Interest Group International Conference on Management of Data[C]. Montreal,Cananda, 1996: 259~270.
[10]  [9]Garcia-Molina H, Ullman J D, Widom J. Database system implementation [M]. Upper Saddle River, New Jersey USA:Prentice Hall, 2000: Chapter 7, Section 6.

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133