Database Systems
Efficient I/O-Transfer of Spatial Objects
Typically the objects of a spatial database system are stored in pages on secondary storage. Access to secondary memory is very slow compared to accessing main memory. Therefore, the organization of the memory access to the exact geometry of objects is very important for an efficient processing of spatial queries. Typical range queries, for example, require an access of many data pages, which is much more expensive for arbitrarily distributed pages than for physically contiguous pages because the search time of a page is much higher than the transfer time and because physically contiguous pages can be transferred by one set-oriented disk access into main memory.
To support a set-oriented disk access, we need additional concepts. The runtime of a set-oriented access depends on how close to each other the required pages are located on disk and on the order in which the required pages are read. If the data pages storing spatially adjacent objects are distributed arbitrarily over secondary storage, the goal is to find an optimal order for reading the necessary pages and to estimate the resulting costs.
To avoid this, the concept called scene organization was suggested. The basic idea is to associate the geometry of spatially adjacent objects to sets of physically contiguous pages and to use a set-oriented I/O-manager in the underlying system. Based on this idea, we developed a spatial access method for scenes which allows dynamic changes of the database.
Important publications in this area are [SLM 93] and [BK 94a].
HOME Pages:
DBS
Institute
LMU
Contact Institute: info@informatik.uni-muenchen.de
Contact WWW: wwwmaster@informatik.uni-muenchen.de