An introduction to Spatial Database Systems

논문명 : An introduction to Spatial Database Systems

. Spatial DB
  pictorial
  image
  geometric
  geographic
  spatial

. Large collections of relatively simple geometric objects
  
. full fledged DB + spatial data
. intersects, area
. large area에서 odject 찾기
. spatial indexing : full scan없이 찾기 위해 필요

. Basic abstraction
  . Point : location
  . Line : moving, connectivity,
  . Region : area

. Instances
  . Partition : disjoint - land
  . Network : node, edge - traffic
  . nested partition

. basic concept : combinatorial topology
  . simplex
    d-simplex : minimal object in dimension d
    0 simplex : point
    1 simplex : a line segment
    2 simplex : triangle
    3 simplex : tetrahedron
    n simplex : n+1개의 n-1 simplex로 구성
    faces : n simplex를 이루는 n-1 simplex
  . simplicial complex
    simplex들의 set.
    n-simplex의 intersection이 항상 n-1 simplex인 것
. realm
  . line segment of grid point

. Spatial Data Type
  . realm R
  . R-block : a connected set of line segments of R
  . R-face : a polygon with holes that can be defined over reealm segment
  . lines : a set of disjoint R-blocks
  . regions : a set of edge-disjoint R-faces
    . edge-disjoint : two faces have a common vertex, no common edge
  . kinds : type set
  . EXT = {lines, regions}
  . GEO = {points, lines, regions}
  . operation
    . inside
    . intersects
    . meets
    . adjacent, encloses
    . plus, minus - union, difference
    . contour(등고선, 윤곽)
    . dist - distance
    . perimeter, area
    . sum - spatial aggregate function
    . closest - minimal distance object from object
  . extensibility
  . completeness
  . one or more types
  . set operation

. spatial relationship
  . topological relationship
    . adjacent
    . inside
    . disjoint
  . direction relationship
    . above
    . below
    . north_of
    . southwest_of
  . metric relationship
    . distance < 100
  . basic relationship
    . disjoint
    . in
    . touch
    . equal
    . cover
    . overlap
  . operation
    . boundary
    . interior
  . GraphDB
    . simple classes
    . link classes
    . path classes

. transformation
  . translation(병진이동)
  . scaling
  . rotation

. Querying
  . Fundamental Operations
    . spatial selection
    . spatial join
    . spatial function application
    . set operation
      . overlay
      . fusion
      . voronoi - 각 점에 가장 가까운 공간으로 partitioning
        http://mathworld.wolfram.com/VoronoiDiagram.html

  . Graphical I/O
    . spatial data type
    . graphical display of query result
    . graphical combination(overlay) of several query results
    . display of context
    . A facility for checking the content of a display
    . Extended dialog
    . Varying graphical representation
    . A legend
    . lavel placement
    . scale selection
    . subarea for queries

. Spatial DBMS implementation
  . one page - Single contiguous byte block
  . info part - often used summary information
  . geometry part
  . general approximation
    . MBR : minimum bounding rectangle
    . continuous approximation
      . bounding box
      . grid approximation
  . plane sweep sequence
    . sort하지 않아도 되게 하기 위해서
  . stored unary function values
    . cost가 큰 area, perimeter 같은 값을 한 번 계산해서 미리 저장해 둠.

  . query
    . range query
    . nearest neighbor
    . distance sscan
    . intersection query
    . containment query

  . spatial index structure
    . bucket - page 크기와 같음.
    . bucket region - bucket이 가진 모든 공간
    . clustering
    . secondary index
    . kd-tree partioning

  . 1-d embedding of grid approximations
    . bit interleaving
    . z-order
    . z-element
    . quadrant
    . lexicographical order of the bit strings
    . proximity-preserving property

  . spatial index structures for points
    . grid file
    . kd-tree
    . KDB-tree
    . LSD-tree
      Local split decision tree
    . EXCELL
    . buddy hash tree
    . BANG file
    . hB-tree

  . spatial index structure for rectangles
    . transformation approach
      k-dimensional rectangle -> 2k-dimensional points
    . overlapping regions
    . clipping

    . stratege
      . filter and refine stratege

    . conservative approximations
      . bounding ellipses
      . convex hull
      . convex 5-corners
      . false hits
    . prograssive approximations

  . supporing spatial join
    . classic join methods : hash join, sort/merge join
    . Grid approximation/bounding box
      . too fine grid - inefficiency
      . too rough grid - too many false hits
    . None/one/both operands are represented in a spatial index structure
    . bb_join
    . external divide-and conquer algorithm
    . seeded trees
    . index join
    . repeated search join
    . join indices

. system architecture
  . integrated architecture
  . extensible DBMS
  . GIS architectures
    . layered architecture
    . dual architecture
  . Integrated Spatial DBMS Architecture
    . Extensible DBMS
      . POSTGRES
      . GENESIS
      . Gral
      . Starburst
      . DASDBS
      . Probe
      . GEO-Kernel
      . GEO++
      . GeoSabrina
      . Sabrina

GIS : Geographic Information Systems
VLDB Journal : The International Journal on Very Large DB
http://www.informatik.uni-trier.de/~ley/db/journals/vldb/