Spatial Database Systems: An Overview

undefined
 
Introduction to Spatial Database
System
 
Presented by Xiaozhi Yu
 
 
 
Outline
 
What is spatial database system?
What need to be presented?
Organizing the underlying space.
Spatial data types.
Spatial relationships.
Integrating geometry into DBMS data model.
Spatial indexing.
Spatial join.
System architecture.
 
 
 
What is spatial database system?
 
Spatial database is a database system
It offers spatial data types in its data model and
query language
It supports spatial data types in its implementation ,
providing at least spatial indexing and efficient
algorithms for spatial join
 
Modeling: What need to be presented?
 
Single object
         Points, Lines and Regions
 
 
Modeling: What need to be presented?
 
Spatially related collections of objects
         Partitions-----a set of regions
         Networks-----points and lines
 
Modeling: Organizing the Underlying Space-
Discrete Geometric Bases
 
Simplex and simplicial complex:
Simplex :For each dimension d, a d-simplex is a minimal
object in that dimension. Any d-simplex is composed of
(d+1) simplicies of dimension d-1.
Simplicial complex: A finite set of simplices such that the
intersection of any two simplices in the set is a 
face 
(simplex
of d-1 dimension)
 
Modeling: Organizing the Underlying Space-
Discrete Geometric Bases
 
Realm: Conceptually represents the complete
underlying geometry of one particular application
space. A realm is a finite set of points and lines over
discrete grid.
 
Modeling: Spatial data types
 
Example : Rose algebra
Three data types
Points ---a set of R-points
lines ----a set of disjointed R-blocks
regions ---- a set of edge disjoint R-faces
    
Values are realm based, composed from elements from realm.
Kind : type sets
EXT = {lines, regions}
GEO= {points, line, regions}
                        =A kind for all partitions
 
 
 
Four classes of operations in ROSE
 
 
Four classes of operations in ROSE
 
 
Spatial Relationships
 
Several classes of relationships:
Topological relationships
Adjacent, Disjoint, Inside, etc.
Direction relationships
Above, below, north-of, southwest-of, etc.
Metric relationships
Distance < 100 , etc.
 
Relationships of simple regions
 
 
Integrating geometry into DBMS data
model
 
DBMS data model is extended by SDTs at the level of
atomic data types.
The central idea for integrating geometric modeling
into DBMS data model is to present “spatial objects ”
by objects with at least one attribute of spatial data
type.
 
Querying---fundamental operators
 
Spatial selection
Exp : cities select[center inside Bavaris]
Spatial join
Exp : cities rivers join[dist (center, route) < 50]
Spatial function application
Exp :
 
 
Other set operators
Overlay , fusion, Voronoi
 
Spatial indexing
 
Two ways:
Dedicated external spatial data structures are added to the
system, offering for spatial attributes. Like B-tree does for
standard attributes.
Spatial objects are mapped into a one-dimensional space so
that they can be stored within a standard one-dimensional
index such as a B-tree.
 
Spatial indexing : approximations
 
Spatial keys are much simpler geometric objects than
the SDT value itself.
 
Spatial indexing : grid approximation
 
An example : grid approximation. Space is
divided into cells by grid and SDT value  is
represented by a set of cells that it intersect.
 
Spatial indexing : grid approximation
 
Any shape(a set of cells) can be represented by a
set of bit strings called z-elements.
For a spatial object, use its corresponding set of
z-elements as a set of spatial keys.
 
 
 
Spatial index structures for points
 
Grid file : partition data space by irregular grid into
cells.
Scales : split line position, one scale per dimension.
Directory: entries are pointers to buckets.
 
Spatial index structures for rectangles
 
There are three approaches:
Approach 1 Transformation : a rectangle represented by
four points can be regarded as one point in four dimensions.
 
Spatial index structures for rectangles
 
There are three approaches:
Approach 2 Overlapping regions:
 
Spatial index structures for rectangles
 
There are three approaches:
Approach 3 Clipping:
 
Supporting spatial join
 
Central ideas for computing spatial join are the
filter and refine strategy and use of spatial index
structures.
Strategies classification criteria:
Grid approximation/bounding box
None/one/both operands are represented in a spatial index
structure.
 
Supporting spatial join : Grid
approximation/bounding box
 
Grid approximation:
A parallel scan of the two sets of z-elements corresponding
to the two sets of spatial objects is performed, similar to a
merge join for a “<=” predicate.
When using the bounding box :
For each object , the bounding box of its SDT attribute is
used as a search argument. The problem is to determine for
two sets of rectangles R,S, all pairs (r, s) , r intersects s.
 
Supporting spatial join
 
None indexes
Algorithms such as bb_join, an external divided-and conquer
algorithm, similar to external merge join.
Use seeded tree to build an index for one operand on the
fly.
One index
Index join or repeated search join can be used.
     Inner operand is represented in an index. Scan the outer
operand set and for each object, the bounding box of its
SDT attribute is used as a search argument on the index.
 
Supporting spatial join
 
Both operand have indexes
Perform synchronized traversal of the two index structure so
that pairs of cells of their respective partitions covering the
same part of space are encountered together.
 
System architecture
 
Layered architecture: spatial functionality is built
on top of a given DBMS.
 
System architecture
 
Dual architecture:
 
Integrated spatial DBMS architecture- using
an extensible DBMS
 
 
 
 
 
                           
Thank  You
Slide Note
Embed
Share

This presentation by Xiaozhi Yu introduces the fundamentals of spatial database systems, covering topics such as spatial data types, relationships, system architecture, modeling, and organizing underlying spaces. It delves into the importance of integrating geometry into DBMS data models, spatial indexing, and efficient algorithms for spatial joins, providing a comprehensive insight into the world of spatial databases.

  • Spatial Database Systems
  • Spatial Data Types
  • Spatial Relationships
  • System Architecture
  • Database Modeling

Uploaded on Jul 05, 2024 | 2 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. Introduction to Spatial Database System Presented by Xiaozhi Yu

  2. Outline What is spatial database system? What need to be presented? Organizing the underlying space. Spatial data types. Spatial relationships. Integrating geometry into DBMS data model. Spatial indexing. Spatial join. System architecture.

  3. What is spatial database system? Spatial database is a database system It offers spatial data types in its data model and query language It supports spatial data types in its implementation , providing at least spatial indexing and efficient algorithms for spatial join

  4. Modeling: What need to be presented? Single object Points, Lines and Regions

  5. Modeling: What need to be presented? Spatially related collections of objects Partitions-----a set of regions Networks-----points and lines

  6. Modeling: Organizing the Underlying Space- Discrete Geometric Bases Simplex and simplicial complex: Simplex :For each dimension d, a d-simplex is a minimal object in that dimension. Any d-simplex is composed of (d+1) simplicies of dimension d-1. Simplicial complex: A finite set of simplices such that the intersection of any two simplices in the set is a face (simplex of d-1 dimension)

  7. Modeling: Organizing the Underlying Space- Discrete Geometric Bases Realm: Conceptually represents the complete underlying geometry of one particular application space. A realm is a finite set of points and lines over discrete grid.

  8. Modeling: Spatial data types Example : Rose algebra Three data types Points ---a set of R-points lines ----a set of disjointed R-blocks regions ---- a set of edge disjoint R-faces Values are realm based, composed from elements from realm. Kind : type sets EXT = {lines, regions} GEO= {points, line, regions} =A kind for all partitions

  9. Four classes of operations in ROSE

  10. Four classes of operations in ROSE

  11. Spatial Relationships Several classes of relationships: Topological relationships Adjacent, Disjoint, Inside, etc. Direction relationships Above, below, north-of, southwest-of, etc. Metric relationships Distance < 100 , etc.

  12. Relationships of simple regions

  13. Integrating geometry into DBMS data model DBMS data model is extended by SDTs at the level of atomic data types. The central idea for integrating geometric modeling into DBMS data model is to present spatial objects by objects with at least one attribute of spatial data type.

  14. Querying---fundamental operators Spatial selection Exp : cities select[center inside Bavaris] Spatial join Exp : cities rivers join[dist (center, route) < 50] Spatial function application Exp : Other set operators Overlay , fusion, Voronoi

  15. Spatial indexing Two ways: Dedicated external spatial data structures are added to the system, offering for spatial attributes. Like B-tree does for standard attributes. Spatial objects are mapped into a one-dimensional space so that they can be stored within a standard one-dimensional index such as a B-tree.

  16. Spatial indexing : approximations Spatial keys are much simpler geometric objects than the SDT value itself.

  17. Spatial indexing : grid approximation An example : grid approximation. Space is divided into cells by grid and SDT value is represented by a set of cells that it intersect.

  18. Spatial indexing : grid approximation Any shape(a set of cells) can be represented by a set of bit strings called z-elements. For a spatial object, use its corresponding set of z-elements as a set of spatial keys.

  19. Spatial index structures for points Grid file : partition data space by irregular grid into cells. Scales : split line position, one scale per dimension. Directory: entries are pointers to buckets.

  20. Spatial index structures for rectangles There are three approaches: Approach 1 Transformation : a rectangle represented by four points can be regarded as one point in four dimensions.

  21. Spatial index structures for rectangles There are three approaches: Approach 2 Overlapping regions:

  22. Spatial index structures for rectangles There are three approaches: Approach 3 Clipping:

  23. Supporting spatial join Central ideas for computing spatial join are the filter and refine strategy and use of spatial index structures. Strategies classification criteria: Grid approximation/bounding box None/one/both operands are represented in a spatial index structure.

  24. Supporting spatial join : Grid approximation/bounding box Grid approximation: A parallel scan of the two sets of z-elements corresponding to the two sets of spatial objects is performed, similar to a merge join for a <= predicate. When using the bounding box : For each object , the bounding box of its SDT attribute is used as a search argument. The problem is to determine for two sets of rectangles R,S, all pairs (r, s) , r intersects s.

  25. Supporting spatial join None indexes Algorithms such as bb_join, an external divided-and conquer algorithm, similar to external merge join. Use seeded tree to build an index for one operand on the fly. One index Index join or repeated search join can be used. Inner operand is represented in an index. Scan the outer operand set and for each object, the bounding box of its SDT attribute is used as a search argument on the index.

  26. Supporting spatial join Both operand have indexes Perform synchronized traversal of the two index structure so that pairs of cells of their respective partitions covering the same part of space are encountered together.

  27. System architecture Layered architecture: spatial functionality is built on top of a given DBMS.

  28. System architecture Dual architecture:

  29. Integrated spatial DBMS architecture- using an extensible DBMS

  30. Thank You

More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#