DOC PREVIEW
USC CSCI 599 - s1and2-v2

This preview shows page 1-2-17-18-19-36-37 out of 37 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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-Fall2000OutlineIntroduction & definitionModelingQueryingData structures and algorithmsSystem architectureConclusion and summary3C. ShahabiCSCI599-Fall2000CSCI599-Fall2000IntroductionVarious fields/applications require management of geometric, geographic or spatial data:A geographic space: surface of the earthMan-made space: layout of VLSI designModel of rat brain4C. ShahabiCSCI599-Fall2000CSCI599-Fall2000Introduction …Common challenge: dealing with large collections of relatively simple geometric objectsDifferent from image and pictorial database systems: Containing sets of objects in space rather than images or pictures of a space5C. ShahabiCSCI599-Fall2000CSCI599-Fall2000DefinitionA spatial database system:Is a database system •A DBMS with additional capabilities for handling spatial dataOffers 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-Fall2000ModelingWLOG assume 2-D and GIS application, two basic things need to be represented: Objects in space: cities, forests, or riversmodeling single objectsSpace: 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, riverRegion: 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 mapsNetworks: 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  boolintersect, meets: ext1 x ext2  booladjacent, encloses: regions x regions  boolOperations returning atomic spatial data types:intersection: lines x lines  pointsintersection: regions x regions  regionsplus, minus: geo x geo  geocontour: regions  lines10C. ShahabiCSCI599-Fall2000CSCI599-Fall2000Modeling …Spatial operators returning numbersdist: geo1 x geo2  realperimeter, area: regions  realSpatial operations on set of objectssum: set(obj) x (objgeo)  geoA 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 (objgeo1) 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, rotationDirection relationships: e.g., above, below, or north_of, sothwest_of, …Metric relationships: e.g., distanceEnumeration 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-Fall2000QueryingTwo 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

USC CSCI 599 - s1and2-v2

Documents in this Course
Week8_1

Week8_1

22 pages

Week2_b

Week2_b

10 pages

LECT6BW

LECT6BW

20 pages

LECT6BW

LECT6BW

20 pages

5

5

44 pages

12

12

15 pages

16

16

20 pages

Nima

Nima

8 pages

Week1

Week1

38 pages

Week11_c

Week11_c

30 pages

afsin

afsin

5 pages

October5b

October5b

43 pages

Week11_2

Week11_2

20 pages

final

final

2 pages

c-4

c-4

12 pages

0420

0420

3 pages

Week9_b

Week9_b

20 pages

S7Kriegel

S7Kriegel

21 pages

Week4_2

Week4_2

16 pages

sandpres

sandpres

21 pages

Week6_1

Week6_1

20 pages

4

4

33 pages

Week10_c

Week10_c

13 pages

fft

fft

18 pages

LECT7BW

LECT7BW

19 pages

24

24

15 pages

14

14

35 pages

Week9_c

Week9_c

24 pages

Week11_67

Week11_67

22 pages

Week1

Week1

37 pages

LECT3BW

LECT3BW

28 pages

Week8_c2

Week8_c2

19 pages

Week5_1

Week5_1

19 pages

LECT5BW

LECT5BW

24 pages

Week10_b

Week10_b

16 pages

Week11_1

Week11_1

43 pages

Week7_2

Week7_2

15 pages

Week5_b

Week5_b

19 pages

Week11_a

Week11_a

29 pages

LECT14BW

LECT14BW

24 pages

T7kriegel

T7kriegel

21 pages

0413

0413

2 pages

3

3

23 pages

C2-TSE

C2-TSE

16 pages

10_19_99

10_19_99

12 pages

Week10_3

Week10_3

23 pages

jalal

jalal

6 pages

1

1

25 pages

T3Querys

T3Querys

47 pages

CS17

CS17

15 pages

porkaew

porkaew

20 pages

LECT4BW

LECT4BW

21 pages

Week10_1

Week10_1

25 pages

wavelet

wavelet

17 pages

October5a

October5a

22 pages

p289-korn

p289-korn

12 pages

2

2

33 pages

rose

rose

36 pages

9_7_99

9_7_99

18 pages

Week10_2

Week10_2

28 pages

Week7_3

Week7_3

37 pages

Load more
Download s1and2-v2
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view s1and2-v2 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view s1and2-v2 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?