时空分析DBMS-STADBS的数据模型与存储机制的研究
|
摘要
时空数据模型是时空数据库(也称移动对象数据库)的核心，是时空查询等其它数据库组成部分的基础。类型系统是一种有效的数据建模方法，它将数据库看作对象的集合，每一类对象及其行为用一种抽象数据类型(ADT)来描述，对象可以具有时空数据类型的属性。本文详细论述了基于这种方法的时空数据的建模过程：以空间模型为基础，分抽象模型和离散模型，定义了两个抽象层次的时空代数系统。抽象模型为时空数据库管理系统——STADBS提供了一个语义精确、概念清晰的基础，离散模型则是一种实现设计，把基于无限描述的抽象模型映射为可在计算机中处理的数据类型。STADBS中采用了文件－内存映射的主存数据库技术，来实现结构复杂的时空数据的存储管理。最后本文讨论了STADBS中存在的问题和进一步的研究方向。
Spatio-temporal data model is the kernel of spatio-temporal database, namely moving object database, and it's the basis of the other components such as spatio-temporal query. Type system is an efficient approach for data modeling, where a database is viewed as a collection of object classes; these classes and their behavior are captured by ADTs; objects may or may not have aspects of spatio-ternporal data types. In this paper, we describe in detail the procedure of modeling with this approach: based on spatial data model, both abstract model and discrete model needed, defining spatio-temporal algebras in two abstract levels. The abstract model provides the Spatio-Teniporal Analysis Database System (STADBS) with a basis having exact semanteme and distinct concept, while the discrete model is a kind of implementation design, which maps the abstract model into those computable data types in terms of finite sets. STADBS employs the technique of main memory database based on file-memory mapping to implement the management of complex-structured spatio-temporal data. At the end, the unresolved problems and future works are discussed.
Spatio-temporal data model is the kernel of spatio-temporal database, namely moving object database, and it's the basis of the other components such as spatio-temporal query. Type system is an efficient approach for data modeling, where a database is viewed as a collection of object classes; these classes and their behavior are captured by ADTs; objects may or may not have aspects of spatio-ternporal data types. In this paper, we describe in detail the procedure of modeling with this approach: based on spatial data model, both abstract model and discrete model needed, defining spatio-temporal algebras in two abstract levels. The abstract model provides the Spatio-Teniporal Analysis Database System (STADBS) with a basis having exact semanteme and distinct concept, while the discrete model is a kind of implementation design, which maps the abstract model into those computable data types in terms of finite sets. STADBS employs the technique of main memory database based on file-memory mapping to implement the management of complex-structured spatio-temporal data. At the end, the unresolved problems and future works are discussed.
引文
[1] Bolen, M.H., Jensen, C. S., Skjellaug, B., Spatio-Temporal Database Support for Legacy, 1998 ACM Symposium on Applied Computing, Atlanta, Georgia, 1998．
[2] Tryfona, N., Modeling Phenomena in Spatiotemporal Applications: Desiderata and Solu-tions, 9th Int. Conf. on Database and Expert Systems Applications, LNCS, 1998．
[3] Tryfona, N., Hadzilacos, Th., Logical Data Modeling of SpatioTemporal Applications: Definitions and a Model, Int. Database Engineering and Applications Symp.m 1997．
[4] Tryfona, N., Jensen, C. S., Conceptual Data Modeling for Spatiotemporal Applications, CHOROCHRONOS Tech. Report CH-98-08．
[5] Theodoridis, Y., Vazirgiannis, M., Sellis, T., Spatio-Temporal Indexing for Large Multi-media Applications, 3rd IEEE Conf. on Multimedia Computing and Systems, ICMCS'96, Hiroshima, Japan, 1996．
[6] Tzouramanis, T., Vassilakopoulos, M., Manolopoulos, Y., Overlapping Linear Quadtrees: a Spatiotemporal Access Method, 6th ACM Int. Workshop on Geographical Information Systems, 1998．
[7] Theodoridis, Y, Sellis, T., Papadopoulos, A., Manolopoulos, Y, Specifications for Efficient Indexing in Spatiotemporal Databases, 10th Int. Conf. on Scientific and Statistical Database Management, Capri, Italy, 1998．
[8] Papadopoulos, A., Rigaux, P., Scholl, M., A Performance Evaluation of Spatial Join Processing Strategies. 6th Intern. Symp. on Spatial Databases (SSD'99) , Hong Kong, 1999．
[9] Gunther, O., Oria, V., Picouet, P., Saglio, J.M., Scholl, M., Benchmarking Spatial Joins A La Carte, 10th Int. Conf. on Scientific and Statistical Database Management, Capri, Italy, 1998．
[10] Theodoridis, Y, Silva, J.R.O., Nascimento, M.A., On the Generation of Spatiotemporal Datasets. 6th Intern. Symp. on Spatial Databases (SSD'99) , Hong Kong, 1999．
[11] Theodoridis, Y, Papadias, D., Stefanakis, E., Sellis, T, Direction Relations and Two-Dimensional Range Queries: Optimisation Techniques, Data and Knowledge Engineering, 1998．
[12] Pfoser, D., Jensen, C.S., Incremental Join of Time-Oriented Data, TimeCenter Tech. Report, Aalborg University, 1998．
[13] Vazirgiannis, M., Theodoridis, Y, Sellis, T., Spatio-Temporal Composition and Indexing for Large Multimedia Applications, ACM Multimedia Systems, 6(5) , 1998．
[14] Guting R.H., An Introduction to Spatial Database Systems, VLDB Journal, Vol. 3, 1994．
[15] Shashi Shekhar, Spatial Databases-Accomplishments and Research Needs, IEEE Transactions on Knowledge and Engineering, Vol. 11, No. 1, 1999．
[16] Smith T.R., Requirements and Principles for the Implementation and Construction of Large-Scale Geographic Information Systems, Intl. Journal of Geographical Information Systems, Vol. 1, 1987．
[17] Frank A., Properties of Geographic Data: Requirements for Spatial Access Methods, Proc. 2nd, Intl. Symposium on Large Spatial Databases, 1991．
[18] Egenhofer, M., A, A Topological Data Model for Spatial Databases, Proc. 1st, Intl. Symposium on Large Spatial Databases, 1989．
[19]Güting R.H., Realms: A Foundation for Spatial Data Types in Database Systems, Proc. 3rd, Intl. Symposium on Large Spatial Databases, 1993.
[20]周毅，空间分析数据库管理系统SADBS——存储管理、可视化编辑器和空间分析算法，硕士学位论文，南京航空航天大学，2001．
[21]Joseph, T., PICQUERY: A High Level Query Language for Pictorial Database Management, IEEE Trans. on Software Engineering, Vol.14, 1998.
[22]Güting R.H., Geo-Relational Algebra: A Model and Query Language for Geometric Database Systems, Proc. EDBT, 1988.
[23]Svensson, P., Geo-SAL: A Query Language for Spatial Data Analysis, Proc. 2nd, Intl. Symposium on Large Spatial Databases, 1991.
[24]Scholl M., Thematic Map Modeling, Proc. 1st, Intl. Symp. on Large Spatial Databases, 1989.
[25]Güting, R.H., Realm-Based Spatial Data Types: The ROSE Algebra, Fernuniversit Hagen, Report 141, 1993.
[26]Egenhofer M., A Formal Definition of Binary Topological Relationships, Proc. 3rd, Intl. Conf. on Foundations of Data Organization and Algorithms, 1989.
[27]Clementini E., A Small Set of Formal Topological Relationships Suitable for End-User Interaction, Proc. 3rd, Intl. Symposium on Large Spatial Databases, 1993.
[28]Lipeck U., Modeling and Manipulating Objects in Geoscientific Databases, Proc. 5th, Intl. Conf. on the Entity-Relationship Approach, 1987.
[29]Clifford J. A Model for Historical Databases. Proceedings of Workshop on Logical Bases for Database, Toulouse, France, December 1982
[30]Tansel A., Chlifford J., Gadia S., et al. Temporal Databases--Theory, Design and Implementation, The Benjamin/Cummings Publishing Company, 1993.
[31]Ben Z.J., The Time Relational Model, Ph. D. Thesis, Computer Science Dept., UCLA, 1982.
[32]Gadia, S.K., A Homogeneous Relational Model and Query Languages for Temporal Databases, ACM Transactions on Database Systems 13, 1988.
[33]J. Loechx, H. D. Ehrich, M. Wolf. Specification of Abstract Data types. John Wiley & Sons, Inc. and B.G. Teubner Publishers. 1996.
[34]Güting R.H., Secnod-Order Signature: A Toll for Specifying Data Models, Query Processing and Optimization, Proceedings of the ACM SIGMOD international Conference on Management of Data, Washington, 1993.
[35]S. Gaal, Point Set Topology, Academic Press, 1964.
[36]邹永娟，时空分析数据库STADBS的分析操作算法及查询语言，硕士学位论文，南京航空航天大学，2002．
[37]J.A. Cotelo Lema, L. Forlizzi, Güting R.H., E. Nardelli, M. Schneider, Algorithms for Moving Objects Databases. FernUniversit Hagen, Informatik-Report 289, October 2001.
[38]Güting R.H., M.H. Bohlen, M. Erwig, C.S. Jensen, N.A. Lorentzos, M. Schneider, M. Vazirgiannis, A Foundation for Representing and Querying Moving Objects. FernUniversit Hagen, Informatik-Report 238, September 1998.
[39]Güting R.H., M. Schneider, Realm-Based Spatial Data Types: The ROSE Algebra, VLDB Journal 4, 1995.
[40]阳国贵，王升，张火炬，吴泉源，主存数据库系统与技术，《软件学报》，Vol．5，No．3，1994．
[41]阳国贵，实时内存数据库的装入，《软件学报》，Vol．11，No．6，829-835，2000．
[42]Le Gruenwald, M.H. Eich, MMDB Reloading Algorithms, Proc. ACM SIGMOD International Conf. Management of Data,397-405, 1991.
[43]阳国贵，王升，吴泉源，主存数据库管理系统GKD—MMDB的研究与实现，《计算机研究与发展》，Vol．32 No．10，1995．
[44]Le Gruenwald, M.H. Eich, Choosing the best Storage Techniques for a Main Memory Database System, 5th Jerusalem Conference on Information Technology, 1990.
[45]Yu Chin Cheng, Le Gruenwald, Greg Ingels, M.T. Thakkar, Evaluating Partitioning Techniques for Main Memory Database: Horizontal and Single Vertical, IEEE Transactions on Knowledge and Data Engineering, 1993.
[46]H. V. Jagadish, D. Lieuwen, R. Rastogi, A. Silberschatz, Dali: A High Performance Main Memory Storage Manage, Proc. of the 20th VLDB Conf., 1994.
[47]http://standards.ieee.org/reading/ieee/std/posix/
[2] Tryfona, N., Modeling Phenomena in Spatiotemporal Applications: Desiderata and Solu-tions, 9th Int. Conf. on Database and Expert Systems Applications, LNCS, 1998．
[3] Tryfona, N., Hadzilacos, Th., Logical Data Modeling of SpatioTemporal Applications: Definitions and a Model, Int. Database Engineering and Applications Symp.m 1997．
[4] Tryfona, N., Jensen, C. S., Conceptual Data Modeling for Spatiotemporal Applications, CHOROCHRONOS Tech. Report CH-98-08．
[5] Theodoridis, Y., Vazirgiannis, M., Sellis, T., Spatio-Temporal Indexing for Large Multi-media Applications, 3rd IEEE Conf. on Multimedia Computing and Systems, ICMCS'96, Hiroshima, Japan, 1996．
[6] Tzouramanis, T., Vassilakopoulos, M., Manolopoulos, Y., Overlapping Linear Quadtrees: a Spatiotemporal Access Method, 6th ACM Int. Workshop on Geographical Information Systems, 1998．
[7] Theodoridis, Y, Sellis, T., Papadopoulos, A., Manolopoulos, Y, Specifications for Efficient Indexing in Spatiotemporal Databases, 10th Int. Conf. on Scientific and Statistical Database Management, Capri, Italy, 1998．
[8] Papadopoulos, A., Rigaux, P., Scholl, M., A Performance Evaluation of Spatial Join Processing Strategies. 6th Intern. Symp. on Spatial Databases (SSD'99) , Hong Kong, 1999．
[9] Gunther, O., Oria, V., Picouet, P., Saglio, J.M., Scholl, M., Benchmarking Spatial Joins A La Carte, 10th Int. Conf. on Scientific and Statistical Database Management, Capri, Italy, 1998．
[10] Theodoridis, Y, Silva, J.R.O., Nascimento, M.A., On the Generation of Spatiotemporal Datasets. 6th Intern. Symp. on Spatial Databases (SSD'99) , Hong Kong, 1999．
[11] Theodoridis, Y, Papadias, D., Stefanakis, E., Sellis, T, Direction Relations and Two-Dimensional Range Queries: Optimisation Techniques, Data and Knowledge Engineering, 1998．
[12] Pfoser, D., Jensen, C.S., Incremental Join of Time-Oriented Data, TimeCenter Tech. Report, Aalborg University, 1998．
[13] Vazirgiannis, M., Theodoridis, Y, Sellis, T., Spatio-Temporal Composition and Indexing for Large Multimedia Applications, ACM Multimedia Systems, 6(5) , 1998．
[14] Guting R.H., An Introduction to Spatial Database Systems, VLDB Journal, Vol. 3, 1994．
[15] Shashi Shekhar, Spatial Databases-Accomplishments and Research Needs, IEEE Transactions on Knowledge and Engineering, Vol. 11, No. 1, 1999．
[16] Smith T.R., Requirements and Principles for the Implementation and Construction of Large-Scale Geographic Information Systems, Intl. Journal of Geographical Information Systems, Vol. 1, 1987．
[17] Frank A., Properties of Geographic Data: Requirements for Spatial Access Methods, Proc. 2nd, Intl. Symposium on Large Spatial Databases, 1991．
[18] Egenhofer, M., A, A Topological Data Model for Spatial Databases, Proc. 1st, Intl. Symposium on Large Spatial Databases, 1989．
[19]Güting R.H., Realms: A Foundation for Spatial Data Types in Database Systems, Proc. 3rd, Intl. Symposium on Large Spatial Databases, 1993.
[20]周毅，空间分析数据库管理系统SADBS——存储管理、可视化编辑器和空间分析算法，硕士学位论文，南京航空航天大学，2001．
[21]Joseph, T., PICQUERY: A High Level Query Language for Pictorial Database Management, IEEE Trans. on Software Engineering, Vol.14, 1998.
[22]Güting R.H., Geo-Relational Algebra: A Model and Query Language for Geometric Database Systems, Proc. EDBT, 1988.
[23]Svensson, P., Geo-SAL: A Query Language for Spatial Data Analysis, Proc. 2nd, Intl. Symposium on Large Spatial Databases, 1991.
[24]Scholl M., Thematic Map Modeling, Proc. 1st, Intl. Symp. on Large Spatial Databases, 1989.
[25]Güting, R.H., Realm-Based Spatial Data Types: The ROSE Algebra, Fernuniversit Hagen, Report 141, 1993.
[26]Egenhofer M., A Formal Definition of Binary Topological Relationships, Proc. 3rd, Intl. Conf. on Foundations of Data Organization and Algorithms, 1989.
[27]Clementini E., A Small Set of Formal Topological Relationships Suitable for End-User Interaction, Proc. 3rd, Intl. Symposium on Large Spatial Databases, 1993.
[28]Lipeck U., Modeling and Manipulating Objects in Geoscientific Databases, Proc. 5th, Intl. Conf. on the Entity-Relationship Approach, 1987.
[29]Clifford J. A Model for Historical Databases. Proceedings of Workshop on Logical Bases for Database, Toulouse, France, December 1982
[30]Tansel A., Chlifford J., Gadia S., et al. Temporal Databases--Theory, Design and Implementation, The Benjamin/Cummings Publishing Company, 1993.
[31]Ben Z.J., The Time Relational Model, Ph. D. Thesis, Computer Science Dept., UCLA, 1982.
[32]Gadia, S.K., A Homogeneous Relational Model and Query Languages for Temporal Databases, ACM Transactions on Database Systems 13, 1988.
[33]J. Loechx, H. D. Ehrich, M. Wolf. Specification of Abstract Data types. John Wiley & Sons, Inc. and B.G. Teubner Publishers. 1996.
[34]Güting R.H., Secnod-Order Signature: A Toll for Specifying Data Models, Query Processing and Optimization, Proceedings of the ACM SIGMOD international Conference on Management of Data, Washington, 1993.
[35]S. Gaal, Point Set Topology, Academic Press, 1964.
[36]邹永娟，时空分析数据库STADBS的分析操作算法及查询语言，硕士学位论文，南京航空航天大学，2002．
[37]J.A. Cotelo Lema, L. Forlizzi, Güting R.H., E. Nardelli, M. Schneider, Algorithms for Moving Objects Databases. FernUniversit Hagen, Informatik-Report 289, October 2001.
[38]Güting R.H., M.H. Bohlen, M. Erwig, C.S. Jensen, N.A. Lorentzos, M. Schneider, M. Vazirgiannis, A Foundation for Representing and Querying Moving Objects. FernUniversit Hagen, Informatik-Report 238, September 1998.
[39]Güting R.H., M. Schneider, Realm-Based Spatial Data Types: The ROSE Algebra, VLDB Journal 4, 1995.
[40]阳国贵，王升，张火炬，吴泉源，主存数据库系统与技术，《软件学报》，Vol．5，No．3，1994．
[41]阳国贵，实时内存数据库的装入，《软件学报》，Vol．11，No．6，829-835，2000．
[42]Le Gruenwald, M.H. Eich, MMDB Reloading Algorithms, Proc. ACM SIGMOD International Conf. Management of Data,397-405, 1991.
[43]阳国贵，王升，吴泉源，主存数据库管理系统GKD—MMDB的研究与实现，《计算机研究与发展》，Vol．32 No．10，1995．
[44]Le Gruenwald, M.H. Eich, Choosing the best Storage Techniques for a Main Memory Database System, 5th Jerusalem Conference on Information Technology, 1990.
[45]Yu Chin Cheng, Le Gruenwald, Greg Ingels, M.T. Thakkar, Evaluating Partitioning Techniques for Main Memory Database: Horizontal and Single Vertical, IEEE Transactions on Knowledge and Data Engineering, 1993.
[46]H. V. Jagadish, D. Lieuwen, R. Rastogi, A. Silberschatz, Dali: A High Performance Main Memory Storage Manage, Proc. of the 20th VLDB Conf., 1994.
[47]http://standards.ieee.org/reading/ieee/std/posix/