Introduction to Spatial Database SystemsOutlineIntroductionIntroduction …DefinitionModelingModeling …Slide 8Slide 9Slide 10Slide 11Slide 12QueryingQuerying …Slide 15Slide 16Slide 17Data Structures & AlgorithmsData Structures …Slide 20Slide 21Spatial IndexingSlide 23Spatial Indexing …Slide 25Slide 26Spatial JoinSpatial Join …System ArchitectureSystem Architecture …Slide 31Databases for GISSlide 33GIS DefinitionGIS ApplicationsGIS Data ModelsGIS Architecture1C. ShahabiCSCI599-Fall2000CSCI599-Fall2000Introduction to Spatial Database Systemsby Cyrus Shahabifrom Ralf Hart Hartmut Guting’s VLDB Journal v3, n4, October 19942C. ShahabiCSCI599-Fall2000CSCI599-Fall2000OutlineIntroduction & definitionModelingQueryingData structures and algorithmsSystem architectureConclusion and summary3C. ShahabiCSCI599-Fall2000CSCI599-Fall2000IntroductionVarious fields/applications require management of geometric, geographic or spatial data:A geographic space: surface of the earthMan-made space: layout of VLSI designModel of rat brain4C. ShahabiCSCI599-Fall2000CSCI599-Fall2000Introduction …Common challenge: dealing with large collections of relatively simple geometric objectsDifferent from image and pictorial database systems: Containing sets of objects in space rather than images or pictures of a space5C. ShahabiCSCI599-Fall2000CSCI599-Fall2000DefinitionA spatial database system:Is a database system •A DBMS with additional capabilities for handling spatial dataOffers spatial data types (SDTs) in its data model and query language•Structure in space: e.g., POINT, LINE, REGION •Relationships among them: (l intersects r)Supports SDT in its implementation•Providing at least spatial indexing (retrieving objects in particular area without scanning the whole space) •Efficient algorithm for spatial joins (not simply filtering the cartesian product)6C. ShahabiCSCI599-Fall2000CSCI599-Fall2000ModelingWLOG assume 2-D and GIS application, two basic things need to be represented: Objects in space: cities, forests, or riversmodeling single objectsSpace: say something about every point in space (e.g., partition of a country into districts)modeling spatially related collections of objects7C. ShahabiCSCI599-Fall2000CSCI599-Fall2000Modeling …Fundamental abstractions for modeling single objects:Point: object represented only by its location in space, e.g., center of a state Line (actually a curve or ployline): representation of moving through or connections in space, e.g., road, riverRegion: representation of an extent in 2d-space, e.g., lake, city8C. ShahabiCSCI599-Fall2000CSCI599-Fall2000Modeling …Instances of spatially related collections of objects:Partition: set of region objects that are required to be disjoint (adjacency or region objects with common boundaries), e.g., thematic mapsNetworks: embedded graph in plane consisting of set of points (vertices) and lines (edges) objects, e.g. highways, power supply lines, rivers9C. ShahabiCSCI599-Fall2000CSCI599-Fall2000Modeling …A sample (ROSE) spatial type system EXT={lines, regions}, GEO={points, lines, regions}Spatial predicates for topological relationships:inside: geo x regions boolintersect, meets: ext1 x ext2 booladjacent, encloses: regions x regions boolOperations returning atomic spatial data types:intersection: lines x lines pointsintersection: regions x regions regionsplus, minus: geo x geo geocontour: regions lines10C. ShahabiCSCI599-Fall2000CSCI599-Fall2000Modeling …Spatial operators returning numbersdist: geo1 x geo2 realperimeter, area: regions realSpatial operations on set of objectssum: set(obj) x (objgeo) geoA spatial aggregate function, geometric union of all attribute values, e.g., union of set of provinces determine the area of the country closest: set(obj) x (objgeo1) x geo2 set(obj)Determines within a set of objects those whose spatial attribute value has minimal distance from geometric query object11C. ShahabiCSCI599-Fall2000CSCI599-Fall2000Modeling …Spatial relationships: Topological relationships: e.g., adjacent, inside, disjoint. Are invariant under topological transformations like translation, scaling, rotationDirection relationships: e.g., above, below, or north_of, sothwest_of, …Metric relationships: e.g., distanceEnumeration of all possible topological relationships between two simple regions (no holes, connected): Based on comparing two objects boundaries (A) and interiors (Ao), there are 4 sets each of which be empty or not = 24=16. 8 of these are not valid and 2 symmetric so:6 valid topological relationships: disjoint, in, touch, equal, cover, overlap12C. ShahabiCSCI599-Fall2000CSCI599-Fall2000Modeling …DBMS data model must be extended by SDTs at the level of atomic data types (such as integer, string), or better be open for user-defined types (OR-DBMS approach):relation states (sname: STRING; area: REGION; spop: INTEGER)relation cities (cname: STRING; center: POINT; ext: REGION; cpop: INTEGER);relation rivers (rname: STRING; route: LINE)13C. ShahabiCSCI599-Fall2000CSCI599-Fall2000QueryingTwo main issues:1. Connecting the operations of a spatial algebra (including predicates to express spatial relationships) to the facilities of a DBMS query language.2. Providing graphical presentation of spatial data (i.e., results of queries), and graphical input of SDT values used in queries.14C. ShahabiCSCI599-Fall2000CSCI599-Fall2000Querying …Fundamental spatial algebra operations:Spatial selection: returning those objects satisfying a spatial predicate with the query object“All cities in Bavaria” SELECT sname FROM cities c WHERE c.center inside Bavaria.area“All rivers intersecting a query window” SELECT * FROM rivers r WHERE r.route intersects Window“All big cities no more than 100 Kms from Hagen” SELECT cname FROM cities c WHERE dist(c.center, Hagen.center) < 100 and c.pop > 500k (conjunction with other predicates and query optimization)15C. ShahabiCSCI599-Fall2000CSCI599-Fall2000Querying …Spatial join: A join which compares any two joined objects based on a predicate on their spatial attribute values.“For each river pass through Bavaria, find all cities within less than 50 Kms.”SELECT r.rname, c.cname,
View Full Document