Double-grid-based Spatial Database System Sadbs Ii Design And Implementation

The first generation spatial analysis database system,SADBS,uses "Realms" as expression base of spatial data. It adopts discrete integer coordinate system to solve topological error in spatial database. It also uses multi-index data organization and plane-sweep algorithm,which improve the performance of spatial analysis operations. However,complex spatial redrawing process becomes the fatal demerit of SADBS.Dual grid is another spatial expression approach based on discrete geometry. Different from Realms,dual grid adopts finite precision rational coordinate system,which can express intersection points exactly. Therefore,the complexity of spatial redrawing can be avoided,and spatial management subsystem can be implemented easily.Based on the above technology,and combined with the powerful extensibility of PostgreSQL,we design and implement a complete spatial database prototype system,called SADBS II. SADBS II can manage spatial and non-spatial data efficiently,has powerful spatial analysis capability,and can keep the whole system self-contained and consistent.In addition,we summarize some spatial join algorithms based on R-tree index and their cost estimation models. We also give out a query optimization algorithm framework based on dynamic programming algorithm,and integrated basic R-tree index method and query optimization mechanism into SADBS II.At last,for some flaws of SADBS II,we give out some new directions and approaches for further research.