Study On The Theories And Technologies Of Embedded Spatial Database Management System

As an important theory and technology, embedded spatial database will play an important role in the future in all kinds of spatial information application field (including military), but it has not been fully researched although the developed western countries have started to pay attention to. This paper makes a comprehensive and in-depth study on the embedded spatial database, the main contents of which as follows.(1)The paper summarizes systematically the related concepts and the research status quo and the existing problems in the embedded spatial database field, and clarifies the conceptions relevant to EDBMS often be confused or misused, and also details the main characteristics and special demands of embedded spatial database.(2)Based on the analysis of the advantages and disadvantages of each kind of architecture of the traditional spatial database system, and on the analysis of the architecture of two typical EDBMS, the paper proposes three schemes for implementing the embedded spatial database: based on file, based on relational EDBMS and based on the non-relational EDBMS. And designs an uniform spatial extending architecture which can provide both relational interface and the common call interface. And summarizes the commonness and difference of the architecture between the embedded spatial database system and the traditional spatial database system.(3)According to the comparison and analysis on advantages and disadvantages between the five kinds of logical model of DBMS, the paper concludes that the REDBMS is most suitable for implementing ESDBMS. According to the characteristics of the ESDBMS it proposes the principles extending its logical data model should follow: simplicity, integrity and standardization, and designs and implements the spatial data types and spatial operators of ESDBMS based on that principles.(4)It details the mapping relationship of data storage and index between the logic and the physical layers of ESDBMS, which depicts the transforming process from disk storage to the logic view of ESDBMS, and reveals the essence of data storage and index. The paper designs a dynamic extendable storage structure supporting automatically the change of application data type, which make ESDBMS show some intelligent. According to the application characteristics of embedded spatial database, the 3 level spatial index strategy in ESDBMS is put forward and implemented, of which the first level index based on the extended layered R tree is created for scale set and map set, and the second level index based on the grid and the improved quad-tree is created for point and line, surface feature respectively, and the third level based on the incremental joint index is created for the level of detail of the map.(5)The characteristics of spatial query and processing in ESDBMS are analyzed in detail, based on which the paper brings forward the restricting factors of spatial query cost in ESDBMS, namely accessing costs, storage costs and computational costs. Then the author presents the three-step treatment strategies. In the first step, spatial join is executed on the MBRs of objects, getting a candidate set including all the final results and parts of extra pairs of objects dissatisfying the join predicate. In the second step the more accurate approximations (progressive and conservative) are used to identify some answers as well as filter out false hits from the set of candidates, which will reduce the amounts of exact geometrical information of objects need transferred into the main memory in the refining stage and the amounts of accurate calculation, and thus reduce the cost of I/O and CPU simultaneously. In the third step, the spatial query condition is tested on the new candidate set by the exact geometric information of objects. Due to its important role in the operations of ESDBMS, the paper focuses on the effective algorithms for processing spatial join and puts forward a filtering strategy for spatial join based on triple approximations. Firstly, spatial join is executed on MBRs of spatial objects and get a superset of the results, namely, a candidate set. Secondly, the false hits (namely, the MBRs of object pairs intersect but themselves did not) are filtered out from the candidate set through the conservative approximations of objects. At last, some pairs of objects meeting the join predicate necessarily are identified by progressive approximations of objects. The experiment demonstrates that the conservative and progressive approximations of spatial objects should be stored together with MBRs in spatial index. And the influence of approximations on the performance of spatial join is analyzed.(6)According to the characteristics of restricted resource and high cost of the refining step of spatial join in the embedded application environments, the author puts forward a new algorithm for finding an optimal data page access sequence during the spatial join process, which searches the best N-release-K sequence that can minimize the cost of disk I/O theoretically, and describes the main idea and implementing process in detail.(7)The experiments on part of the main contents and algorithms proposed in the paper are carried out including the prototype system, the extending of spatial data types and spatial operators in EDBMS, the performance test of three-level spatial index in ESDBMS, and the performance test of the new OPAS algorithm. The results show the correctness and feasibility of the discussion of the paper.