Chapter 1: Introduction to Spatial Databases

1.1 Overview
1.2 Application domains
1.3 Compare a SDBMS with a GIS
1.4 Categories of Users
1.5 An example of an SDBMS application
1.6 A Stroll though a spatial database
1.6.1 Data Models, 1.6.2 Query Language, 1.6.3 Query Processing,
1.6.4 File Organization and Indices, 1.6.5 Query Optimization,
1.6.6 Data Mining
Learning Objectives
Learning Objectives (LO)
LO1 : Understand the value of SDBMS
• Application domains
• users
• How is different from a DBMS?
LO2: Understand the concept of spatial databases
LO3: Learn about the Components of SDBMS

Mapping Sections to learning objectives

LO1 - 1.1, 1.2, 1.4
LO2 - 1.3, 1.5
LO3 - 1.6
Value of SDBMS
Traditional (non-spatial) database management systems provide:
Persistence across failures
Allows concurrent access to data
Scalability to search queries on very large datasets which do not fit
inside main memories of computers
Efficient for non-spatial queries, but not for spatial queries
Non-spatial queries:
List the names of all bookstore with more than ten thousand titles.
List the names of ten customers, in terms of sales, in the year 2001
Spatial Queries:
List the names of all bookstores with ten miles of Minneapolis
List all customers who live in Tennessee and its adjoining states
Value of SDBMS – Spatial Data Examples
Examples of non-spatial data
Names, phone numbers, email addresses of people
Examples of Spatial data
Census Data
NASA satellites imagery - terabytes of data per day
Weather and Climate Data
Rivers, Farms, ecological impact
Medical Imaging
Exercise: Identify spatial and non-spatial data items in
A phone book
A cookbook with recipes
Value of SDBMS – Users, Application Domains
Many important application domains have spatial data and
queries. Some Examples follow:
Army Field Commander: Has there been any significant
enemy troop movement since last night?
Insurance Risk Manager: Which homes are most likely to
be affected in the next great flood on the Mississippi?
Medical Doctor: Based on this patient's MRI, have we
treated somebody with a similar condition ?
Molecular Biologist:Is the topology of the amino acid
biosynthesis gene in the genome found in any other sequence
feature map in the database ?
Astronomer:Find all blue galaxies within 2 arcmin of quasars.

Exercise: List two ways you have used spatial data. Which
software did you use to manipulate spatial data?
Learning Objectives
Learning Objectives (LO)
LO1 : Understand the value of SDBMS
LO2: Understand the concept of spatial databases
• What is a SDBMS?
• How is it different from a GIS?
LO3: Learn about the Components of SDBMS
Sections for LO2
Section 1.5 provides an example SDBMS
Section 1.1 and 1.3 compare SDBMS with DBMS and GIS
What is a SDBMS ?
A SDBMS is a software module that
can work with an underlying DBMS
supports spatial data models, spatial abstract data types (ADTs)
and a query language from which these ADTs are callable
supports spatial indexing, efficient algorithms for processing
spatial operations, and domain specific rules for query
optimization
Example: Oracle Spatial data cartridge, ESRI SDE
can work with Oracle 8i DBMS
Has spatial data types (e.g. polygon), operations (e.g. overlap)
callable from SQL3 query language
Has spatial indices, e.g. R-trees
 SDBMS Example
Consider a spatial dataset with:
County boundary (dashed white line)
Census block - name, area, population,
boundary (dark line)
Water bodies (dark polygons)
Satellite Imagery (gray scale pixels)

Storage in a SDBMS table:

create table census_blocks (
name string,
area float,
population number,
boundary polygon );

Fig 1.2
Modeling Spatial Data in Traditional DBMS

•A row in the table census_blocks (Figure 1.3)

• Question: Is Polyline datatype supported in DBMS?

Figure 1.3
Spatial Data Types and Traditional Databases
Traditional relational DBMS
Support simple data types, e.g. number, strings, date
Modeling Spatial data types is tedious
Example: Figure 1.4 shows modeling of polygon using numbers
Three new tables: polygon, edge, points
• Note: Polygon is a polyline where last point and first point are same
A simple unit sqaure represented as 16 rows across 3 tables
Simple spatial operators, e.g. area(), require joining tables
Tedious and computationally inefficient

Question. Name post-relational database management systems

which facilitate modeling of spatial data types, e.g. polygon.
Mapping “census_table” into a Relational Database

Fig 1.4
Evolution of DBMS technology

Fig 1.5
Spatial Data Types and Post-relational Databases
Post-relational DBMS
Support user defined abstract data types
Spatial data types (e.g. polygon) can be added
Choice of post-relational DBMS
Object oriented (OO) DBMS
Object relational (OR) DBMS
A spatial database is a collection of spatial data types, operators,
indices, processing strategies, etc. and can work with many post-
relational DBMS as well as programming languages like Java, Visual
Basic etc.
How is a SDBMS different from a GIS ?
GIS is a software to visualize and analyze spatial data
using spatial analysis functions such as
Search Thematic search, search by region, (re-)classification
Location analysis Buffer, corridor, overlay
Terrain analysis Slope/aspect, catchment, drainage network
Flow analysis Connectivity, shortest path
Distribution Change detection, proximity, nearest neighbor
Spatial analysis/Statistics Pattern, centrality, autocorrelation, indices of
similarity, topology: hole description
Measurements Distance, perimeter, shape, adjacency, direction
GIS uses SDBMS
to store, search, query, share large spatial data sets
How is a SDBMS different from a GIS ?
SDBMS focusses on
Efficient storage, querying, sharing of large spatial datasets
Provides simpler set based query operations
Example operations: search by region, overlay, nearest
neighbor, distance, adjacency, perimeter etc.
Uses spatial indices and query optimization to speedup queries
over large spatial datasets.
SDBMS may be used by applications other than GIS
Astronomy, Genomics, Multimedia information systems, ...
Will one use a GIS or a SDBM to answer the following:
How many neighboring countries does USA have?
Which country has highest number of neighbors?
 Evolution of acronym “GIS”
Geographic Information Systems (1980s)
Geographic Information Science (1990s)
Geographic Information Services (2000s)

Fig 1.1
Three meanings of the acronym GIS
Geographic Information Services
Web-sites and service centers for casual users, e.g. travelers
Example: Service (e.g. AAA, mapquest) for route planning
Geographic Information Systems
Software for professional users, e.g. cartographers
Example: ESRI Arc/View software
Geographic Information Science
Concepts, frameworks, theories to formalize use and
development of geographic information systems and services
Example: design spatial data types and operations for querying
Exercise: Which meaning of the term GIS is closest to the focus of
the book titled “Spatial Databases: A Tour”?
Learning Objectives
Learning Objectives (LO)
LO1 : Understand the value of SDBMS
LO2: Understand the concept of spatial databases
LO3: Learn about the Components of SDBMS
• Architecture choices
• SDBMS components:
– data model, query languages,
– query processing and optimization
– File organization and indices
– Data Mining

Chapter Sections
1.5 second half
1.6 – entire section
Components of a SDBMS
Recall: a SDBMS is a software module that
can work with an underlying DBMS
supports spatial data models, spatial ADTs and a query
language from which these ADTs are callable
supports spatial indexing, algorithms for processing spatial
operations, and domain specific rules for query optimization
Components include
spatial data model, query language, query processing, file
organization and indices, query optimization, etc.
Figure 1.6 shows these components
We discuss each component briefly in chapter 1.6 and in more
detail in later chapters.
Three Layer Architecture Fig 1.6
1.6.1 Spatial Taxonomy, Data Models
Spatial Taxonomy:
multitude of descriptions available to organize space.
Topology models homeomorphic relationships, e.g. overlap
Euclidean space models distance and direction in a plane
Graphs models connectivity, Shortest-Path
Spatial data models
rules to identify identifiable objects and properties of space
Object model help manage identifiable things, e.g. mountains,
cities, land-parcels etc.
Field model help manage continuous and amorphous
phenomenon, e.g. wetlands, satellite imagery, snowfall etc.
More details in chapter 2.
1.6.2 Spatial Query Language
• Spatial query language
• Spatial data types, e.g. point, linestring, polygon, …
• Spatial operations, e.g. overlap, distance, nearest neighbor, …
• Callable from a query language (e.g. SQL3) of underlying DBMS
SELECT S.name
FROM Senator S
WHERE S.district.Area() > 300

• Standards
• SQL3 (a.k.a. SQL 1999) is a standard for query languages
• OGIS is a standard for spatial data types and operators
• Both standards enjoy wide support in industry
• More details in chapters 2 and 3
 Multi-scan Query Example
• Spatial join example
SELECT S.name FROM Senator S, Business B
WHERE S.district.Area() > 300 AND Within(B.location, S.district)
• Non-Spatial Join example
SELECT S.name FROM Senator S, Business B
WHERE S.soc-sec = B.soc-sec AND S.gender = ‘Female’

Fig 1.7
 1.6.3 Query Processing
• Efficient algorithms to answer spatial queries
• Common Strategy - filter and refine
• Filter Step:Query Region overlaps with MBRs of B,C and D
• Refine Step: Query Region overlaps with B and C

Fig 1.8
 Query Processing of Join Queries
•Example - Determining pairs of intersecting rectangles
• (a):Two sets R and S of rectangles, (b): A rectangle with 2 opposite corners
marked, (c ): Rectangles sorted by smallest X coordinate value
• Plane sweep filter identifies 5 pairs out of 12 for refinement step
•Details of plane sweep algorithm on page 15

Fig 1.9
 1.6.4 File Organization and Indices
• A difference between GIS and SDBMS assumptions
•GIS algorithms: dataset is loaded in main memory (Fig. 1.10(a))
•SDBMS: dataset is on secondary storage e.g disk (Fig. 1.10(b))
•SDBMS uses space filling curves and spatial indices
•to efficiently search disk resident large spatial datasets

Fig 1.10
Organizing spatial data with space filling curves
•Issue:
•Sorting is not naturally defined on spatial data
•Many efficient search methods are based on sorting datasets
•Space filling curves
•Impose an ordering on the locations in a multi-dimensional space
•Examples: row-order (Fig. 1.11(a), z-order (Fig 1.11(b))
• Allow use of traditional efficient search methods on spatial data

Fig 1.11
 Spatial Indexing: Search Data-Structures
•Choice for spatial indexing:
•B-tree is a hierarchical collection of ranges of linear keys, e.g. numbers
•B-tree index is used for efficient search of traditional data
•B-tree can be used with space filling curve on spatial data
•R-tree provides better search performance yet!
•R-tree is a hierarchical collection of rectangles
•More details in chapter 4

Fig 1.12: B-tree Fig. 1.13: R- tree

1.6.5 Query Optimization
•Query Optimization
• A spatial operation can be processed using different strategies
• Computation cost of each strategy depends on many parameters
•Query optimization is the process of
•ordering operations in a query and
•selecting efficient strategy for each operation
•based on the details of a given dataset
•Example Query:
SELECT S.name FROM Senator S, Business B
WHERE S.soc-sec = B.soc-sec AND S.gender = ‘Female’
•Optimization decision examples
•Process (S.gender = ‘Female’) before (S.soc-sec = B.soc-sec )
•Do not use index for processing (S.gender = ‘Female’)
1.6.6 Data Mining
• Analysis of spatial data is of many types
• Deductive Querying, e.g. searching, sorting, overlays
• Inductive Mining, e.g. statistics, correlation, clustering,classification, …
• Data mining is a systematic and semi-automated search for
interesting non-trivial patterns in large spatial databases

•Example applications include

•Infer land-use classification from satellite imagery
•Identify cancer clusters and geographic factors with high correlation
•Identify crime hotspots to assign police patrols and social workers
1.7 Summary
SDBMS is valuable to many important applications
SDBMS is a software module
works with an underlying DBMS
provides spatial ADTs callable from a query language
provides methods for efficient processing of spatial queries
Components of SDBMS include
spatial data model, spatial data types and operators,
spatial query language, processing and optimization
spatial data mining
SDBMS is used to store, query and share spatial data
for GIS as well as other applications
Chapter 2: Spatial Concepts and Data Models
2.1 Introduction
2.2 Models of Spatial Information
2.3 Three-Step Database Design
2.4 Extending ER with Spatial Concepts
2.5 Summary
Learning Objectives
Learning Objectives (LO)
LO1: Understand concept of data models
• What is a data model?
• Why use data models?
LO2 : Understand the models of spatial information
LO3: Understand the 3-step design of databases
LO4: Learn about the trends in spatial data models

Mapping Sections to learning objectives

LO2 - 2.1
LO3 - 2.2
LO4 - 2.3, 2.4
What is a Data Model?
•What is a model? (Dictionary meaning)
• A set of plans (blueprint drawing) for a building
•A miniature representation of a system to analyze properties of interest

•What is Data Model?

• Specify structure or schema of a data set
•Document description of data
•Facilitates early analysis of some properties, e.g. querying ability,
redundancy, consistency, storage space requirements, etc.

• Examples:
•GIS organize spatial set as a set of layers
•Databases organize dataset as a collection of tables
Why Data Models?
• Data models facilitate
• Early analysis of properties, e.g. storage cost, querying ability, ...
• Reuse of shared data among multiple applications
• Exchange of data across organization
• Conversion of data to new software / environment
• Example- Y2K crisis for year 2000
Many computer software systems were developed without well-defined data
models in 1960s and 1970s. These systems used a variety of data models for
representing time and date. Some of the representations used two digits to
represent years. In late 1990s, people worried that the 2 digit representation of
year may lead to errorneous behaviour. For example age of a person born in
1960 (represented as 60) in year 2000 (represented as 00) may appear
negative and may be flagged as illegal data item. A large amount of effort and
resources (hundreds of Billions of dollars) was spent in revising the software.
Proper use of data model may have significantly reduced the costs. If time and
date were modeled as abstract data types in a software, only a small portion of
the software implementing the date ADT had to be reviewed and revised.
Types of Data Models
•Two Types of data models
•Generic data models
•Developed for business data processing
•Support simple abstract data types (ADTs), e.g. numbers, strings, date
•Not convenient for spatial ADTs, e.g. polygons
•Recall a polygon becomes dozens of rows in 3 tables (Fig. 1.4, pp. 8)
•Need to extend with spatial concepts, e.g. ADTs
•Application Domain specific, e.g. spatial models
•Set of concepts developed in Geographic Info. Science
•Common spatial ADTs across different GIS applications
•Plan of Study
•First study concepts in spatial models
•Then study generic model
•Finally put the two together
Learning Objectives
Learning Objectives (LO)
LO1: Understand concept of data models
LO2 : Understand the models of spatial information
• Field based model
• Object based model
LO3: Understand the 3-step design of databases
LO4: Learn about the trends in spatial data models

Mapping Sections to learning objectives

LO2 - 2.1
LO3 - 2.2
LO4 - 2.3, 2.4
2.1 Models of Spatial Information
Two common models
Field based
Object based
Example: Forest stands
Fig. 2.1
(a) forest stand map
(b) Object view has 3
polygons
(c ) Field view has a
function
2.1.1 Field based Model
Three main concepts:
Spatial Framework is a partitioning of space
• e.g., Grid imposed by Latitude and Longitude
Field Functions:
f: Spatial Framework → Attribute Domain
Field Operations
• Examples, addition(+) and composition(o).

f + g : x → f ( x) + g ( x)
f  g : x → f ( g ( x))
Types of Field Operations
Local: value of the new field at a given location in the spatial frame-work
depends only on the value of the input field at that location(e.g., Thresholding)
Focal:value of the resulting field at a given location depends on the values
that the input field assumes in a small neighborhood of the location(e.g.,
Gradient)
Zonal:Zonal operations are naturally associated with aggregate operators or
the integration function. An operation that calculates the average height of the
trees for each species is a zonal operation.

Exercise: Classify following operations on elevation field

(I) Identify peaks (points higher than its neighbors)
(II) Identify mountain ranges (elevation over 2000 feet)
(III) Determine average elevation of a set of river basins
2.1.2 Object Model
Object model concepts
Objects: distinct identifiable things relevant to an application
Objects have attributes and operations
Attribute: a simple (e.g. numeric, string) property of an object
Operations: function maps object attributes to other objects
Example from a roadmap
Objects: roads, landmarks, ...
Attributes of road objects:
• spatial: location, e.g. polygon boundary of land-parcel
• non-spatial: name (e.g. Route 66), type (e.g. interstate, residential
street), number of lanes, speed limit, …
Operations on road objects: determine center line, determine
length, determine intersection with other roads, ...
Classifying Spatial objects
• Spatial objets are spatial attributes of general objects
• Spatial objects are of many types
•Simple
•0- dimensional (points), 1 dimensional (curves), 2 dimensional (surfaces)
•Example given at the bottom of this slide
•Collections
•Polygon collection (e.g. boundary of Japan or Hawaii), …
•See more complete list in Figure 2.2

Spatial Object Types Example Object Dimension

Point City 0

Curve River 1
Spatial Object Types in OGIS Data Model
Fig 2.2: Each rectangle shows a distinct spatial object type
 Classifying Operations on spatial objects in Object Model
•Classifying operations (Tables 2.1, 2.2, pp. 29-31)
• Set based: 2-dimensional spatial objects (e.g. polygons) are sets of points
• a set operation (e.g. intersection) of 2 polygons produce another polygon
• Topological operations: Boundary of USA touches boundary of Canada
•Directional: New York city is to east of Chicago
•Metric: Chicago is about 700 miles from New York city.
• Q? Identify classes of spatial operations not listed in this slide.

Set theory based Union, Intersection, Containment,

Toplogical Touches, Disjoint, Overlap, etc.

Topological Relationships
Topological Relationships
invariant under elastic deformation (without tear, merge).
Two countries which touch each other in a planar paper map will
continue to do so in spherical globe maps.
Topology is the study of topological relationships
Example queries with topological operations
What is the topological relationship between two objects A and B ?
Find all objects which have a given topological relationship to
object A ?
Topological Concepts
Interior, boundary, exterior
Let A be an object in a “Universe” U.

Green is A interior ( Ao )
U
Red is boundary of A (A)

Blue –(Green + Red) is

−
A exterior ( A )
A

Question: Define Interior, boundary, exterior on curves and points.

Nine-Intersection Model of Topological Relationships
•Many toplogical Relationship between A and B can be
•specified using 9 intersection model
•Examples on next slide
•Nine intersections
•intersections between interior, boundary, exterior of A, B
•A and B are spatial objects in a two dimensional plane.
•Can be arranged as a 3 by 3 matrix
•Matrix element take a value of 0 (false) or 1 (true).
•Q? Determine the number of many distinct 3 by 3 boolean matrices .
Specifying topological operation in 9-Intersection Model
Fig 2.3: 9 intersection matrices for a few topological operations

Question: Can this model specify topological operation between a polygon

and a curve?
Using Object Model of Spatial Data
Object model of spatial data
OGIS standard set of spatial data types and operations
Similar to the object model in computer software
Easily used with many computer software systems
Programming languages like Java, C++, Visual basic
• Example use in a Java program is in section 2.1.6
Post-relational databases, e.g. OODBMS, ORDBMS
• Example usage in chapter 3 through 6
Learning Objectives
Learning Objectives (LO)
LO1: Understand concept of data models
LO2 : Understand the models of spatial information
LO3: Understand the 3-step design of databases
• Conceptual - ER model
• Logical - Relational model
• Physical
• Translation from Conceptual to Logical
LO4: Learn about the trends in spatial data models

Mapping chapter sections to learning objectives

LO2 - 2.1
LO3 - 2.2
LO4 - 2.3, 2.4
2.2 Three-Step Database Design
Database applications are modeled using a three-step
design process
Conceptual-datatypes,relationships and constraints(ER model)
Logical-mapping to a Relational model and associated query
language(Relational Algebra)
Physical-file structures, indexing,
Scope
We discuss conceptual and logical data models in section 2.3
Physical model is discussed in chapter 4
Example Application Domain
Database design is for a specific application domain
Often a requirements document is available
Designers discuss requirements with end-users as needed
We will use a simple spatial application domain
• to illustrate concepts in conceptual and logical data models
• to illustrate translation of conceptual DM to logical DM
Spatial application domain
A state-park consists of forests.
A forest is a collection of forest-stands of different species
State-Park is accessed by roads and has a manager
State-Park has faciltities
River runs through state-park and supplies water to the facilities
2.2.1 Conceptual DM: The ER Model
3 basic concepts
Entities have an independent conceptual or physical existence.
• Examples: Forest, Road, Manager, ...
Entities are characterized by Attributes
• Example: Forest has attributes of name, elevation, etc.
An Entity interacts with another Entity through relationships.
• Road allow access to Forest interiors.
• This relationship may be name “Accesses”
Comparison with Object model of spatial information
Entities are collections of attributes are like objects
However ER model does not permit general user defined operations
Relationships are not directly supported in Object model
• but may be simulated via operations
Relationship Types
Relationships can be categorized by
cardinality constraints
other properties, e.g. number of participating entities
• Binary relationship: two entities participate
Types of Cardinality constraints for binary relationships
One-One: An instance of an entity relates to a unique instance of other entity.
Many-One: Many instances of an entity relate to an instance of an other.
Many-Many: Many instances of one entity relate to multiple instances of another.

Exercise: Identify type of cardinality constraint for following:

Many facilities belong to a forest. Each facility belong to one forest.
A manager manages 1 forest. Each forest has 1 manager.
A river supplies water to many facilities. A facility gets water from many rivers.
ER Diagrams Graphical Notation
•ER Diagrams are graphic representation of ER models
•Several different graphic notation are used
•We use a simple notation summarized below
•Example ER Diagram for Forest exampl in next slide

•Q? Compare and contrast “Atributes” and “Multi-valued attributes”.

Concept Symbol

Entities

Attributes

Multi-valued Attributes

Relationships
ER Diagram for “State-Park”

Fig 2.4

•Exercise:
•List the entities, attributes, relationships in this ER diagram
•Identify cardinality constraint for each relationship.
•How many roads “Accesses” a “Forest_stand”? (one or many)
2.2.2 Logical Data Model: The Relational Model
Relational model is based on set theory
Main concepts
Domain: a set of values for a simple attribute
Relation: cross-product of a set of domains
• Represents a table, i.e. homogeneous collection of rows (tuples)
• The set of columns (i.e. attributes) are same for each row
Comparison to concepts in conceptual data model
Relations are similar to but not identical to entities
Domains are similar to attributes
Translation rules establishing exact correspondence are discussed in 2.2.3
Relational Schema
Schema of a Relation
Enumerates columns, identifies primary key and foreign keys.
Primary Key :
• one or more attributes uniquely identify each row within a table
Foreign keys
• R’s attributes which form primary key of another relation S
• Value of a foreign key in any tuple of R match values in some row of S
Relational schema of a database
collection of schemas of all relations in the database
Example: Figure 2.5 (next slide)
Ablue print summary drawing of the database table structures
Allows analysis of storage costs, data redundancy, querying capabilities
Some databases were designed as relational schema in 1980s
Nowadays, databases are designed as E R models and relational schema is
generated via CASE tools
 Relational Schema Example

•Exercise:
•Identify relations with
•primary keys
•foreign keys
•other attributes
•Compare with ER diagram
•Figure 2.4, pp. 37

Fig 2.5
Relational Schema for “Point”, “Line”, “Polygon” and “Elevation”

•Relational model restricts attribute domains

•simple atomic values, e.g. a number
•Disallows complex values (e.g. polygons) for columns
•Complex values need to be decomposed into simpler domains
•A polygon may be decomposed into edges and vertices (Fig. 2.5)

Fig 2.5
More on Relational Model
Integrity Constraints
Key: Every relation has a primary key.
Entity Integrity: Value of primary key in a row is never undefined
Referential Integrity: Value of an attribute of a Foreign Key must appear as a value
in the primary key of another relationship or must be null.

Normal Forms (NF) for Relational schema

Reduce data redundancy and facilitate querying
1st NF: Each column in a relation contains an atomic value.
2nd and 3rd NF: Values of non-key attributes are fully determined by the values of
the primary key, only the primary key, and nothing but the primary key.
Other normal forms exists but are seldom used
Translating a well-designed ER model yields a relational schema in 3rd NF
• satisfying definition of 1st, 2nd and 3rd normal forms
2.2.3 Mapping ER to Relational
•Highlights of transaltion rules (section 2.2.3)
•Entity becomes Relation
•Attributes become columns in the relation
•Multi-valued attributes become a new relation
•includes foreign key to link to relation for the entity
•Relationships (1:1, 1:N) become foreign keys
•M:N Relationships become a relation
•containing foreign keys or relations from participating entities
•Example and Exercise
•Compare Fig. 2.4 and Fig. 2.5
•Identify the relational schema components for
•entity Facility, its attributes and its relationships
•Note an empty relation box in Fig. 2.5. Fill in its schema.
Learning Objectives
Learning Objectives (LO)
LO1: Understand concept of data models
LO2 : Understand the models of spatial information
LO3: Understand the 3-step design of databases
LO4: Learn about the trends in spatial data models
• Pictograms in conceptual models
• UML class diagrams

Mapping Sections to learning objectives

LO2 - 2.1
LO3 - 2.2
LO4 - 2.3, 2.4
2.3 Extending ER with Spatial Concepts
•Motivation
•ER Model is based on discrete sets with no implicit relationships
•Spatial data comes from a continuous set with implicit relationships
•Any pair of spatial entities has relationships like distance, direction, …
•Explicitly drawing all spatial relationship
•clutters ER diagram
•generates additional tables in relational schema
•Misses implicit constraints in spatial relationships (e.g. partition)
•Pictograms
•Label spatial entities along with their spatial data types
•Allows inference of spatial relationships and constraints
•Reduces clutter in ER diagram and relational schema
•Example: Fig. 2.7 (next slide) is simpler than Fig. 2.4
ER Diagram with Pictograms: An Example

Fig 2.7
Specifying Pictograms
•Grammar based approach
•Rewrite rule
•like English syntax diagrams
•Classes of pictograms
•Entity pictograms
•basic: point, line, polygon
•collection of basic
•...
•Relationship pictograms
•partition, network
Entity Pictograms: Basic shapes, Collections
Entity Pictograms: Derived and Alternate Shapes
•Derived shape example is city center point from boundary polygon
•Alternate shape example: A road is represented as a polygon for construction
•or as a line for navigation
2.4 Conceptual Data Modeling with UML
•Motivation
•ER Model does not allow user defined operations
•Object oriented software development uses UML
•UML stands for Unified Modeling Language
•It is a standard consisting of several diagrams
•class diagrams are most relevant for data modeling
•UML class diagrams concepts
•Attributes are simple or composite properties
•Methods represent operations, functions and procedures
•Class is a collection of attributes and methods
•Relationship relate classes
•Example UML class diagram: Figure 2.8
UML Class Diagram with Pictograms: Example
•Exercise: Identify classes, attributes, methods, relationships in Fig. 2.8.
•Compare Fig. 2.8 with corresponding ER diagram in Fig. 2.7.

Fig 2.8
Comparing UML Class Diagrams to ER Diagrams
•Concepts in UML class diagram vs. those in ER diagrams
•Class without methods is an Entity
•Attributes are common in both models
•UML does not have key attributes and integrity constraints
• ERD does not have methods
•Relationships properties are richer in ERDs
•Entities in ER diagram relate to datasets, but UML class diagram
•can contain classes which have little to do with data
2.5 Summary
Spatial Information modeling can be classed into Field
based and Object based
Field based for modeling smoothly varying entities, like
rainfall
Object based for modeling discrete entities, like country
Summary
A data model is a high level description of the data
it can help in early analysis of storage cost, data quality
There are two popular models of spatial information
Field based and Object based
Database are designed in 3-steps
Conceptual, Logical and Physical
Pictograms can simplify Conceptual data models
Chapter 3:Spatial Query Languages
3.1 Standard Database Query Languages
3.2 Relational Algebra
3.3 Basic SQL Primer
3.4 Extending SQL for Spatial Data
3.5 Example Queries that emphasize spatial aspects
3.6 Trends: Object-Relational SQL
Learning Objectives
Learning Objectives (LO)
LO1: Understand concept of a query language
• What is a query language?
• Why use query languages?
LO2 : Learn to use standard query language (SQL)
LO3: Learn to use spatial ADTs with SQL
LO4: Learn about the trends in query languages

Mapping Sections to learning objectives

LO2 - 3.2, 3.3
LO3 - 3.4, 3.5
LO4 - 3.6
What is a query?
What is a Query ?
A query is a “question” posed to a database
Queries are expressed in a high-level declarative manner
• Algorithms needed to answer the query are not specified in the query
Examples:
Mouse click on a map symbol (e.g. road) may mean
• What is the name of road pointed to by mouse cursor ?
Typing a keyword in a search engine (e.g. google, yahoo) means
• Which documents on web contain given keywords?
SELECT S.name FROM Senator S WHERE S.gender = ‘F’ means
• Which senators are female?
What is a query language?
What is a query language?
A language to express interesting questions about data
A query language restricts the set of possible queries
Examples:
Natural language, e.g. English, can express almost all queries
Computer programming languages, e.g. Java,
• can express computable queries
• however algorithms to answer the query is needed
Structured Query Language(SQL)
• Can express common data intensive queries
• Not suitable for recursive queries
Graphical interfaces, e.g. web-search, mouse clicks on a map
• can express few different kinds of queries
An Example World Database
Purpose: Use an example database to learn query language SQL
Conceptual Model
3 Entities: Country, City, River
2 Relationships: capital-of, originates-in
Attributes listed in Figure 3.1
An Example Database - Logical Model

• 3 Relations
Country(Name, Cont, Pop, GDP, Life-Exp, Shape)
City(Name, Country, Pop,Capital, Shape)
River(Name, Origin, Length, Shape)
• Keys
•Primary keys are Country.Name, City.Name, River.Name
• Foreign keys are River.Origin, City.Country
•Data for 3 tables
•Shown on next slide
World database data tables
Learning Objectives
Learning Objectives (LO)
LO1: Understand concept of a query language
LO2 : Learn to use standard query language (SQL)
• How to create and populate tables?
• How to query given tables?
LO3: Learn to use spatial ADTs with SQL
LO4: Learn about the trends in query languages

Mapping Sections to learning objectives

LO2 - 3.2, 3.3
LO3 - 3.4, 3.5
LO4 - 3.6
What is SQL?
SQL - General Information
is a standard query language for relational databases
It support logical data model concepts, such as relations, keys, ...
Supported by major brands, e.g. IBM DB2, Oracle, MS SQL Server, Sybase, ...
3 versions: SQL1 (1986), SQL2 (1992), SQL 3 (1999)
Can express common data intensive queries
SQL 1 and SQL 2 are not suitable for recursive queries
SQL and spatial data management
ESRI Arc/Info included a custom relational DBMS named Info
Other GIS software can interact with DBMS using SQL
• using open database connectivity (ODBC) or other protocols
In fact, many software use SQL to manage data in back-end DBMS
And a vast majority of SQL queries are generated by other software
Although we will be writing SQL queries manually!
Three Components of SQL?
Data Definition Language (DDL)
Creation and modification of relational schema
Schema objects include relations, indexes, etc.
Data Manipulation Language (DML)
Insert, delete, update rows in tables
Query data in tables
Data Control Language (DCL)
Concurrency control, transactions
Administrative tasks, e.g. set up database users, security permissions
Focus for now
A little bit of table creation (DDL) and population (DML)
Primarily Querying (DML)
Creating Tables in SQL
• Table definition
• “CREATE TABLE” statement
• Specifies table name, attribute names and data types
• Create a table with no rows.
• See an example at the bottom
• Related statements
• ALTER TABLE statement modifies table schema if needed
• DROP TABLE statement removes an empty table
Populating Tables in SQL
• Adding a row to an existing table
• “INSERT INTO” statement
• Specifies table name, attribute names and values
• Example:
INSERT INTO River(Name, Origin, Length) VALUES(‘Mississippi’, ‘USA’, 6000)

• Related statements
• SELECT statement with INTO clause can insert multiple rows in a table
• Bulk load, import commands also add multiple rows
• DELETE statement removes rows
•UPDATE statement can change values within selected rows
Querying populated Tables in SQL
• SELECT statement
• The commonly used statement to query data in one or more tables
•Returns a relation (table) as result
• Has many clauses
• Can refer to many operators and functions
• Allows nested queries which can be hard to understand
• Scope of our discussion
• Learn enough SQL to appreciate spatial extensions
•Observe example queries
• Read and write simple SELECT statement
• Understand frequently used clauses, e.g. SELECT, FROM, WHERE
• Understand a few operators and function
SELECT Statement- General Information
• Clauses
•SELECT specifies desired columns
•FROM specifies relevant tables
•WHERE specifies qualifying conditions for rows
•ORDER BY specifies sorting columns for results
•GROUP BY, HAVING specifies aggregation and statistics
•Operators and functions
•arithmetic operators, e.g. +, -, …
•comparison operators, e.g. =, <, >, BETWEEN, LIKE…
•logical operators, e.g. AND, OR, NOT, EXISTS,
•set operators, e.g. UNION, IN, ALL, ANY, …
•statistical functions, e.g. SUM, COUNT, ...
• many other operators on strings, date, currency, ...
SELECT Example 1.
• Simplest Query has SELECT and FROM clauses
• Query: List all the cities and the country they belong to.

SELECT Name, Country

FROM CITY

Result →
 SELECT Example 2.
• Commonly 3 clauses (SELECT, FROM, WHERE) are used
•Query: List the names of the capital cities in the CITY table.
SELECT *
FROM CITY
WHERE CAPITAL=‘Y ’

Result →
Query Example…Where clause
Query: List the attributes of countries in the Country relation
where the life-expectancy is less than seventy years.

SELECT Co.Name,Co.Life-Exp
FROM Country Co
WHERE Co.Life-Exp <70

Note: use of alias ‘Co’ for Table ‘Country’

Result →
Multi-table Query Examples
Query: List the capital cities and populations of countries
whose GDP exceeds one trillion dollars.
Note:Tables City and Country are joined by matching “City.Country =
Country.Name”. This simulates relational operator “join” discussed in 3.2

SELECT Ci.Name,Co.Pop
FROM City Ci,Country Co
WHERE Ci.Country =Co.Name
AND Co.GDP >1000.0
AND Ci.Capital=‘Y ’
Multi-table Query Example
Query: What is the name and population of the capital city in the
country where the St. Lawrence River originates?

SELECT Ci.Name, Ci.Pop

FROM City Ci, Country Co, River R
WHERE R.Origin =Co.Name
AND Co.Name =Ci.Country
AND R.Name =‘St.Lawrence ’
AND Ci.Capital=‘Y ’

Note: Three tables are joined together pair at a time. River.Origin is matched
with Country.Name and City.Country is matched with Country.Name. The
order of join is decided by query optimizer and does not affect the result.
Query Examples…Aggregate Staistics
Query: What is the average population of the noncapital cities listed in the
City table?

SELECT AVG(Ci.Pop)
FROM City Ci
WHERE Ci.Capital=‘N ’

Query: For each continent, find the average GDP.

SELECT Co.Cont,Avg(Co.GDP)AS Continent-GDP

FROM Country Co
GROUP BY Co.Cont
Query Example..Having clause, Nested queries
Query: For each country in which at least two rivers originate, find the length
of the smallest river.

SELECT R.Origin, MIN(R.length) AS Min-length

FROM River
GROUP BY R.Origin
HAVING COUNT(*) > 1

Query: List the countries whose GDP is greater than that of Canada.

SELECT Co.Name
FROM Country Co
WHERE Co.GDP >ANY(SELECT Co1.GDP
FROM Country Co1
WHERE Co1.Name =‘Canada ’)
Learning Objectives
Learning Objectives (LO)
LO1: Understand concept of a query language
LO2 : Learn to use standard query language (SQL)
LO3: Learn to use spatial ADTs with SQL
• Learn about OGIS standard spatial data types and operations
• Learn to use OGIS spatial ADTs with SQL
LO4: Learn about the trends in query languages

Mapping Sections to learning objectives

LO2 - 3.2, 3.3
LO3 - 3.4, 3.5
LO4 - 3.6
3.4 Extending SQL for Spatial Data
Motivation
SQL has simple atomic data-types, like integer, dates and string
Not convenient for spatial data and queries
• Spatial data (e.g. polygons) is complex
• Spatial operation: topological, euclidean, directional, metric
SQL 3 allows user defined data types and operations
Spatial data types and operations can be added to SQL3
Open Geodata Interchange Standard (OGIS)
Half a dozen spatial data types
Several spatial operations
Supported by major vendors, e.g. ESRI, Intergraph, Oracle, IBM,...
OGIS Spatial Data Model
Consists of base-class Geometry and four sub-classes:
Point, Curve, Surface and GeometryCollection
Figure 2.2 (pp. 27) lists the spatial data types in OGIS

Operations fall into three categories:

Apply to all geometry types
• SpatialReference, Envelope, Export,IsSimple, Boundary
Predicates for Topological relationships
• Equal, Disjoint, Intersect, Touch, Cross, Within, Contains
Spatial Data Analysis
• Distance,Buffer,Union, Intersection, ConvexHull, SymDiff
Table 3.9 (pp. 66) details spatial operations
Spatial Queries with SQL/OGIS
• SQL/OGIS - General Information
•Both standard are being adopted by many vendors
•The choice of spatial data types and operations is similar
•Syntax differs from vendor to vendor
• Readers may need to alter SQL/OGIS queries given in text to make
them run on specific commercial products
• Using OGIS with SQL
• Spatial data types can be used in DML to type columns
• Spatial operations can be used in DML
• Scope of discussion
• Illustrate use of spatial data types with SQL
• Via a set of examples
List of Spatial Query Examples
• Simple SQL SELECT_FROM_WHERE examples
•Spatial analysis operations
•Unary operator: Area (Q5, pp.68)
•Binary operator: Distance (Q3)
•Boolean Topological spatial operations - WHERE clause
•Touch (Q1, pp. 67)
•Cross (Q2, pp. 68)
•Using spatial analysis and topological operations
•Buffer, overlap (Q4)
•Complex SQL examples
• Aggreagate SQL queries
• Nested queries
Using spatial operation in SELECT clause
Query: List the name, population, and area of each country listed in
the Country table.

SELECT C.Name,C.Pop, Area(C.Shape)AS "Area"

FROM Country C

Note: This query uses spatial operation, Area().Note the use of

spatial
operation in place of a column in SELECT clause.
Using spatial operator Distance
Query: List the GDP and the distance of a country’s capital
city to the equator for all countries.

SELECT Co.GDP, Distance(Point(0,Ci.Shape.y),Ci.Shape) AS "Distance"

FROM Country Co,City Ci
WHERE Co.Name = Ci.Country
AND Ci.Capital =‘Y ’
Using Spatial Operation in WHERE clause
Query: Find the names of all countries which are neighbors of the United
States (USA) in the Country table.

SELECT C1.Name AS "Neighbors of USA"

FROM Country C1,Country C2
WHERE Touch(C1.Shape,C2.Shape)=1
AND C2.Name =‘USA ’

Note: Spatial operator Touch() is used in WHERE clause to join Country table
with itself. This query is an example of spatial self join operation.
Spatial Query with multiple tables
Query: For all the rivers listed in the River table, find the countries through
which they pass.

SELECT R.Name, C.Name

FROM River R, Country C
WHERE Cross(R.Shape,C.Shape)=1

Note: Spatial operation “Cross” is used to join River and Country tables. This
query represents a spatial join operation.

Exercise: Modify above query to report length of river in each country.

Hint: Q6, pp. 69
Example Spatial Query…Buffer and Overlap

Query: The St. Lawrence River can supply water to cities that are
within 300 km. List the cities that can use water from the St.
Lawrence.

SELECT Ci.Name
FROM City Ci, River R
WHERE Overlap(Ci.Shape, Buffer(R.Shape,300))=1
AND R.Name =‘St.Lawrence ’

Note: This query uses spatial operation of Buffer, which is

illustrated in Figure 3.2 (pp. 69).
Recall List of Spatial Query Examples
• Simple SQL SELECT_FROM_WHERE examples
•Spatial analysis operations
•Unary operator: Area
•Binary operator: Distance
•Boolean Topological spatial operations - WHERE clause
•Touch
•Cross
•Using spatial analysis and topological operations
•Buffer, overlap
•Complex SQL examples
• Aggreagate SQL queries (Q9, pp. 70)
• Nested queries (Q3 pp. 68, Q10, pp. 70)
Using spatial operation in an aggregate query
Query: List all countries, ordered by number of neighboring countries.

SELECT Co.Name, Count(Co1.Name)

FROM Country Co, Country Co1
WHERE Touch(Co.Shape,Co1.Shape)
GROUP BY Co.Name
ORDER BY Count(Co1.Name)

Notes: This query can be used to differentiate querying capabilities of simple

GIS software (e.g. Arc/View) and a spatial database. It is quite tedious to carry
out this query in GIS.

Earlier version of OGIS did not provide spatial aggregate operation to support
GIS operations like reclassify.
Using Spatial Operation in Nested Queries
Query: For each river, identify the closest city.

SELECT C1.Name, R1.Name

FROM City C1, River R1
WHERE Distance (C1.Shape,R1.Shape) <= ALL ( SELECT Distance(C2.Shape)
FROM City C2
WHERE C1.Name <> C2.Name
)

Note: Spatial operation Distance used in context of a nested query.

Exercise: It is interesting to note that SQL query expression to find smallest distance
from each river to nearest city is much simpler and does not require nested query.
Audience is encouraged to write a SQL expression for this query.
Nested Spatial Query
Query: List the countries with only one neighboring country. A country is a
neighbor of another country if their land masses share a boundary. According to
this definition, island countries, like Iceland, have no neighbors.
SELECT Co.Name
FROM Country Co
WHERE Co.Name IN (SELECT Co.Name
FROM Country Co,Country Co1
WHERE Touch(Co.Shape,Co1.Shape)
GROUP BY Co.Name
HAVING Count(*)=1)

Note: It shows a complex nested query with aggregate operations. Such queries can be written into
two expression, namely a view definition, and a query on the view. The inner query becomes a view
and outer query is runon the view. This is illustrated in the next slide.
Rewriting nested queries using Views
•Views are like tables
•Represent derived data or result of a query
•Can be used to simplify complex nested queries
•Example follows:
CREATE VIEW Neighbor AS
SELECT Co.Name, Count(Co1.Name)AS num neighbors
FROM Country Co,Country Co1
WHERE Touch(Co.Shape,Co1.Shape)
GROUP BY Co.Name

SELECT Co.Name,num neighbors

FROM Neighbor
WHERE num neighbor = ( SELECT Max(num neighbors)
FROM Neighbor )
Learning Objectives
Learning Objectives (LO)
LO1: Understand concept of a query language
LO2 : Learn to use standard query language (SQL)
LO3: Learn to use spatial ADTs with SQL
LO4: Learn about the trends in query languages
• Facilities for user defined data types in SQL3

Mapping Sections to learning objectives

LO2 - 3.2, 3.3
LO3 - 3.4, 3.5
LO4 - 3.6
Defining Spatial Data Types in SQL3
• SQL3 User defined data type - Overview
• CREATE TYPE statements
• Defines a new data types
• Attributes and methods are defined
• Separate statements for interface and implementation
•Examples of interface in Table 3.12 (pp. 74)

• Additional effort is needed at physical data model level

Defining Spatial Data Types in SQL3
• Libraries, Data cartridge/blades
• Third party libraries implementing OGIS are available
• Almost all user use these libraries
• Few users need to define their own data types

• We will not discuss the detailed syntax of CREATE TYPE

•Interested readers are encouraged to look at section 3.6
Summary
Queries to databases are posed in high level declarative manner
SQL is the “lingua-franca” in the commercial database world
Standard SQL operates on relatively simple data types
SQL3/OGIS supports several spatial data types and operations
Additional spatial data types and operations can be defined
CREATE TYPE statement
Project 2 Presentation

Spatial Databases
GIS Case Studies

Elizabeth Sayed
Elizabeth Stoltzfus
December 4, 2002

UC Berkeley: IEOR 215

Agenda

 Spatial Database Basics

 Geographic Information Systems (GIS) Basics

 Case Studies

UC Berkeley: IEOR 215

1
Spatial Database Basics

 Common applications

UC Berkeley: IEOR 215

2
Spatial Databases Background

 Spatial databases provide structures for storage and analysis of spatial data

 Spatial data is comprised of objects in multi-dimensional space

 Storing spatial data in a standard database would require excessive amounts of space

 Queries to retrieve and analyze spatial data from a standard database would be long and
cumbersome leaving a lot of room for error

 Spatial databases provide much more efficient storage, retrieval, and analysis of spatial data

UC Berkeley: IEOR 215

3
Types of Data Stored in Spatial Databases

 Two-dimensional data examples

– Geographical
– Cartesian coordinates (2-D)
– Networks
– Direction

 Three-dimensional data examples

– Weather
– Cartesian coordinates (3-D)
– Topological
– Satellite images

UC Berkeley: IEOR 215

4
Spatial Databases Uses and Users

 Three types of uses

– Manage spatial data
– Analyze spatial data
– High level utilization

 A few examples of users

– Transportation agency tracking projects
– Insurance risk manager considering location risk profiles
– Doctor comparing Magnetic Resonance Images (MRIs)
– Emergency response determining quickest route to victim
– Mobile phone companies tracking phone usage

UC Berkeley: IEOR 215

5
Spatial Databases Uses and Users

 Three types of uses

– Manage spatial data
– Analyze spatial data
– High level utilization

 A few examples of users

– Transportation agency tracking projects
– Insurance risk manager considering location risk profiles
– Doctor comparing Magnetic Resonance Images (MRIs)
– Emergency response determining quickest route to victim
– Mobile phone user determining current relative location of businesses

UC Berkeley: IEOR 215

6
Spatial Database Management System

 Spatial Database Management System (SDBMS) provides the capabilities of a traditional

database management system (DBMS) while allowing special storage and handling of spatial
data.

 SDBMS:
– Works with an underlying DBMS
– Allows spatial data models and types
– Supports querying language specific to spatial data types
– Provides handling of spatial data and operations

UC Berkeley: IEOR 215

7
SDBMS Three-layer Structure
 SDBMS works with a spatial application at the front Core Spatial

Interface to spatial application

Functionality
end and a DBMS at the back end

Spatial application

Interface to DBMS
Taxonomy
 SDBMS has three layers:
Data types
– Interface to spatial application

DBMS
Operations
– Core spatial functionality
Query language
– Interface to DBMS
Algorithms
Access methods

UC Berkeley: IEOR 215

8
Spatial Query Language

 Number of specialized adaptations of SQL

– Spatial query language
– Temporal query language (TSQL2)
– Object query language (OQL)
– Object oriented structured query language (O2SQL)

 Spatial query language provides tools and structures specifically for working with spatial data

 SQL3 provides 2D geospatial types and functions

UC Berkeley: IEOR 215

9
Spatial Query Language Operations

 Three types of queries:

– Basic operations on all data types (e.g. IsEmpty, Envelope, Boundary)
– Topological/set operators (e.g. Disjoint, Touch, Contains)
– Spatial analysis (e.g. Distance, Intersection, SymmDiff)

UC Berkeley: IEOR 215

10
Spatial Data Entity Creation

 Form an entity to hold county names, states, populations, and geographies

CREATE TABLE County(
Name varchar(30),
State varchar(30),
Pop Integer,
Shape Polygon);

 Form an entity to hold river names, sources, lengths, and geographies

CREATE TABLE River(
Name varchar(30),
Source varchar(30),
Distance Integer,
Shape LineString);

UC Berkeley: IEOR 215

11
Example Spatial Query

 Find all the counties that border on Contra Costa county

SELECT C1.Name
FROM County C1, County C2
WHERE Touch(C1.Shape, C2.Shape) = 1 AND C2.Name = ‘Contra Costa’;

 Find all the counties through which the Merced river runs
SELECT C.Name, R.Name
FROM County C, River R
WHERE Intersect(C.Shape, R.Shape) = 1 AND R.Name = ‘Merced’;

CREATE TABLE County( CREATE TABLE River(

Name varchar(30), Name varchar(30),
State varchar(30), Source varchar(30),
Pop Integer, Distance Integer,
Shape Polygon); Shape LineString);

UC Berkeley: IEOR 215

12
Geographic Information System (GIS) Basics

 Common applications

UC Berkeley: IEOR 215

13
GIS Applications
1. Cartographic
– Irrigation
– Land evaluation
– Crop Analysis
– Air Quality
– Traffic patterns
– Planning and facilities management

2. Digital Terrain Modeling

– Earth science resources
– Civil Engineering & Military Evaluation
– Soil Surveys
– Pollution Studies
– Flood Control

3. Geographic objects

– Car navigation systems
– Utility distribution and consumption
– Consumer product and services

UC Berkeley: IEOR 215

14
GIS Data Format
 Modeling
1. Vector – geometric objects such as points, lines and polygons
2. Raster – array of points

 Analysis
1. Geomorphometric –slope values, gradients, aspects, convexity
2. Aggregation and expansion
3. Querying

 Integration
1. Relationship and conversion among vector and raster data

UC Berkeley: IEOR 215

15
GIS – Data Modeling using Objects & Fields
(0,4)

Pine
(0,2)

Fir Oak

(0,0) (2,0) (4,0)

Object Viewpoint Field Viewpoint

Name Shape Pine: 0<x<4; 2<y<4

Pine [(0,2), (4,2), (4,4), (0,4)]

Fir: 0<x<2; 0<y<2
Fir [(0,0), (2,0), (2,2), (0,2)]

Oak [(2,0), (4,0), (4,2), (2,2)

Oak: 2<x<4; 0<y<2

Source: “Spatial Pictogram Enhanced Data Models pg 79

UC Berkeley: IEOR 215

16
Conceptual Data Modeling
Relational Databases: ER diagram

Limitations for ER with respect to Spatial databases:

– Can not capture semantics
– No notion of key attributes and unique OID’s in a field model
– ER Relationship between entities derived from application under consideration
– Spatial Relationships are inherent between objects

Solution: Pictograms for Spatial Conceptual Data-Modeling

UC Berkeley: IEOR 215

17
Pictograms - Shapes
 Types: Basic Shapes, Multi-Shapes, Derived Shapes, Alternate Shapes, Any possible
Shape, User-Defined Shapes

Basic Shapes Alternate Shapes

Multi-Shapes Any Possible Shape

N 0, N *
Derived Shapes User Defined Shape

UC Berkeley: IEOR 215

18
 Extending the ER Diagram with Spatial
Pictograms: State Park Example
Standard ER Diagram Spatial ER Diagram
RName LineID
RName

Supplies_to River PolygonID Supplies_to River

FoName
FoName
FacName
FacName Touches
Facility Forest
Facility Forest Belongs_to
Belongs_to

PointID Within
Monitors Fire Station Monitors
Fire Station

FiName
FiName
PointID

UC Berkeley: IEOR 215

19
Case Studies

 Specific applications of spatial databases

UC Berkeley: IEOR 215

20
Case Study: Wetlands
 Objective: To predict the spatial distribution of the
location of bird nests in the wetlands
Location of Nests

 Location: Darr and Stubble on the shores of lake

Erie in Ohio
A
 Focus A
Actual Pixel Locations
1. Vegetation Durability A

2. Distance to Open Water

3. Water Depth P
P P A
 Assumptions with Classical Data mining Case 1:
1. Data is independently generated – no A A Possible Prediction
autocorrelation
2. Local vs. global trends

 Spatial accuracy
P A
1. Predictions vs. actual P P
Case 2:
2. Impact A A
Possible Prediction
Source: What’s Spatial About Spatial Data Mining pg 490

UC Berkeley: IEOR 215

21
Case Study: Green House Gas Emission Estimations
 Objective:
– To assess the impact of land-use and land cover changes on ground carbon stock and soil
surface flux of CO2, N2O and CH4 in Jambi Province, Indonesia

 Methodology:
– Initiated by development of land-use/land cover maps and followed by field measurements
– Spatial database construction development based on 1986 and 1992 land-use/land cover
maps that developed from Landsat MSSR and SPOT
– Weight of sample components of the tree and streams, branches, twigs, etc were estimated
from equations and literature
– Emission rates were developed by plotting and analyzing collected air samples
– Field data measurements and GIS spatial data were combined using a Look Up Table of
Arc/Info.

Source: “Spatial Database Development for green house gas emission Estimation using remote sensing and GIS”

UC Berkeley: IEOR 215

22
Case Study: Green House Gas Emission Estimations (cont)
Results:
– Able to quantitatively compare emission changes between 1986 to 1992:
o Determined that there was a loss of 8.3 million tons of Carbon
o Proportion of primary forest decreased from 19.3% to 12.5%
o Showed 24% of primary forest was converted into logged forest, shrub,
cash crops
– Greenhouse gas emission varied depending on the site condition and season.
– Process gave impacts of greenhouse gas on the soil surface

UC Berkeley: IEOR 215

23
Case Study: Pantanal Area, Brazil
 Objective: To assess the drastic land use changes in the Pantanal region since 1985

 Data Source:
– 3 Landsat TM images of the Pantal study area from 1985, 1990, 1996
– A land-use survey from 1997

 Assessment Methodology:
– Normalized Difference Vegetation Index (NDVI) was computed for each year
– NDVI maps of the three years combined and submitted to multi-dimensional image
segmentation
– Classified vegetation
– Produced a color composite by year that identified the density of vegetation

Source: Integrated Spatial Databases pg 116

UC Berkeley: IEOR 215

24
Conclusion
 Many varied applications of spatial databases

 Stores spatial data in various formats specific to use

 Captures spatial data more concisely

 Enables more thorough understanding of data

 Retrieves and manipulates spatial data more efficiently and effectively

UC Berkeley: IEOR 215

25
UC Berkeley: IEOR 215
26
Problem 1 Solution
a) Find all cities that are located within Marin County.
SELECT C2.Name
FROM County C1, City C2
WHERE Within(C1.Shape, C2.Shape) = 1 AND C1.Name = ‘Marin’;
b) Find any rivers that borders on Mendocino County.
SELECT R.Name
FROM County C, River R
WHERE Touch(C.Shape, R.Shape) = 1 AND C.Name = ‘Mendocino’;
c) Find the counties that do not touch on Orange County.
SELECT C1.Name
FROM County C1, County C2
WHERE Disjoint(C1.Shape, C2.Shape) = 1 AND C2.Name = ‘Orange’;

UC Berkeley: IEOR 215

27
Problem 2 Solution
ClosetID

Length

Type
Closet
Hallway

RoomID
HallI Accesses
D
Belongs_T
Room o

Belongs_
To
FurnID
Belongs_To

Furniture

Nam
e

UC Berkeley: IEOR 215

28