PadhaikoAll subjects

Spatial Databases and Data Management

Geographical Information Systems (ENCT 468)

Open in the Padhaiko app

5.1 Spatial database management systems and geodatabase concept

Traditional file-based GIS storage (such as folders of Shapefiles) breaks down when multiple analysts edit data simultaneously, datasets reach millions of features, or web APIs require sub-second concurrent spatial queries. A Spatial Database Management System (SDBMS) extends a relational DBMS with native spatial data types, spatial indexing, and geometric query optimization while retaining full ACID (Atomicity, Consistency, Isolation, Durability) guarantees.

Definition

Core Requirements of a Spatial DBMS

An SDBMS must provide:

  1. Spatial Data Types: Native geometric columns (POINT, LINESTRING, POLYGON, RASTER) alongside standard relational columns.
  2. Spatial Operations & Predicates: Built-in functions for measurements (ST_Area, ST_Distance), topological relationships (ST_Intersects, ST_Contains), and geometric construction (ST_Buffer, ST_Union).
  3. Spatial Indexing: Multi-dimensional indexes (R-tree, GiST, quadtree) integrated into the query planner.
  4. CRS Metadata Catalog: Standard coordinate reference registry (e.g., spatial_ref_sys table keyed by SRID/EPSG).
  5. Concurrency, Security, and Recovery: Multi-user row-level locking, MVCC versioning, role-based access control, and crash recovery.

SDBMS Architecture and the Geodatabase Concept


5.2 Spatial data types and operations: OGC Simple Features for SQL and PostGIS

The OGC Simple Features for SQL (SFS) standard defines a portable SQL type hierarchy (Geometry, Point, Curve/LineString, Surface/Polygon, and Multi* collections), text/binary interchange formats (WKT — Well-Known Text; WKB — Well-Known Binary), and standardized ST_* functions.

PostGIS is the industry-standard open-source spatial extension for PostgreSQL implementing OGC SFS:

Essential PostGIS / OGC SFS Functions
CategoryPostGIS / OGC SQL FunctionPurpose
Constructors / I/OST_GeomFromText('POINT(85.32 27.71)', 4326), ST_AsGeoJSON(geom)Parse WKT into geometry or export to GeoJSON/WKT
CRS TransformationST_Transform(geom, 32645), ST_SRID(geom)Reproject coordinates from one SRID (e.g., 4326) to another (UTM 45N)
MeasurementsST_Area(geom), ST_Length(geom), ST_Distance(g1, g2)Compute area, polyline length, and minimum Euclidean/geodetic distance
Topological PredicatesST_Intersects(a, b), ST_Contains(a, b), ST_Within(a, b), ST_Touches(a, b)Evaluate DE-9IM spatial relationships (return boolean)
Constructive OpsST_Buffer(geom, r), ST_Intersection(a, b), ST_Union(a, b)Create buffer zones, clip intersections, or dissolve polygons

5.3 Spatial queries and spatial SQL

Spatial SQL extends standard SELECT ... FROM ... WHERE queries to answer three fundamental classes of spatial questions:

  1. Range (Window) Query: Retrieve all features intersecting a specified bounding box or polygon region.
  2. -Nearest Neighbor (-NN) Query: Find the closest features to a target point or feature, accelerated directly by the R-tree index using PostGIS's <-> bounding-box/centroid distance operator in ORDER BY.
  3. Spatial Join Query: Combine rows from two spatial tables whenever their geometries satisfy a spatial predicate (ST_Contains, ST_Intersects, ST_DWithin) instead of an attribute equality ON a.id = b.id.
PostGIS Spatial SQL: Range, k-NN, and Spatial Join QueriesSQL
-- 1. Range (Window) Query: Roads inside a UTM Zone 45N bounding box
SELECT road_id, name, ST_Length(geom) AS length_m
FROM roads
WHERE geom && ST_MakeEnvelope(330000, 3060000, 340000, 3070000, 32645)
  AND ST_Intersects(geom, ST_MakeEnvelope(330000, 3060000, 340000, 3070000, 32645));

-- 2. k-Nearest Neighbor (k-NN) Query: 3 closest hospitals to an accident site
SELECT name, ST_Distance(geom, ST_SetSRID(ST_MakePoint(334500, 3065200), 32645)) AS dist_m
FROM hospitals
ORDER BY geom <-> ST_SetSRID(ST_MakePoint(334500, 3065200), 32645)
LIMIT 3;

-- 3. Spatial Join Query: Count schools located inside each municipal ward
SELECT w.ward_no, COUNT(s.id) AS school_count
FROM wards AS w
LEFT JOIN schools AS s
  ON ST_Contains(w.geom, s.geom)
GROUP BY w.ward_no
ORDER BY w.ward_no;

5.4 Spatial indexing and hierarchical grids

Conventional B-tree indexes sort 1D keys linearly and cannot efficiently prune 2D/3D spatial objects. Spatial databases use multi-dimensional indexes or space-filling linearizations:

  1. Grid Index: Divides space into a fixed array of rectangular cells; each cell lists pointers to all features whose bounding boxes touch it. Very fast lookup for uniform point data, but degrades when feature density is highly skewed or object sizes vary wildly.
  2. Quadtree: Recursively partitions 2D space into four quadrants (NW, NE, SW, SE) whenever a bucket exceeds its capacity threshold. Adapts naturally to clustered cities vs. sparse rural regions.
  3. R-tree (and R-tree / GiST): A height-balanced tree (analogous to a B-tree for 2D rectangles) where each node stores a Minimum Bounding Rectangle (MBR) enclosing all child MBRs beneath it. Leaf entries hold (MBR, tuple_id). Unlike quadtrees, R-tree MBRs dynamically fit data extents and may overlap slightly; R-tree minimizes both MBR area and overlap during node splits. PostGIS implements R-trees via its GiST (CREATE INDEX idx ON tbl USING GIST(geom);) access method.
  4. Space-Filling Curves (Z-order and Hilbert): Map 2D integer grid coordinates onto a 1D curve so nearby 2D points stay close in 1D B-trees or cloud partitions:
    • Z-order (Morton) Curve: Interleaves the binary bits of and (e.g., , ). Fast bitwise computation, though occasional long diagonal jumps occur.
    • Hilbert Curve: Folds recursively so every step moves only to an edge-adjacent cell ( distance ), preserving 2D spatial locality better than Z-order.
  5. Geohash and Hierarchical Discrete Global Grids:
    • Geohash: Recursively bisects latitude/longitude and interleaves bits (Z-order), encoding the resulting bit string in Base-32 characters (e.g., tuqrw). Longer shared prefixes indicate closer proximity, though edge effects occur across prime-meridian/equator seams.
    • Hierarchical Grids (DGGS, e.g., Uber H3 / Google S2): Partition the globe into uniform nested cells (hexagons in H3, spherical quads in S2) with unique 64-bit integer IDs, ideal for spatial aggregation and distributed cloud joins.
Example 1

1 (5 marks)

On a integer grid with -bit coordinates and , compute the Morton (Z-order) index by interleaving bits in order for cells and .

Convert coordinates of to -bit binary and interleave:

Interleaving :

Convert coordinates of to -bit binary and interleave:

Interleaving :

Answer:

Using bit-interleaving order , cell has Morton Z-order index (1001) and cell has index (1100).


5.5 Spatial query processing: MBR and filter-and-refine strategy

Computing exact geometric intersections between polygons with thousands of vertices is CPU-expensive. Spatial databases avoid running exact math on every row by using Minimum Bounding Rectangles (MBRs) in a two-phase filter-and-refine pipeline:

Definition

Filter-and-Refine Query Processing

  1. Minimum Bounding Rectangle (MBR): The smallest axis-aligned rectangle that completely encloses a geometry (stored in just numbers).
  2. Phase 1 — Filter Step (Coarse Pruning): Tests the query MBR against feature MBRs stored in the R-tree index. Two MBRs and intersect iff:

This eliminates the vast majority of irrelevant features in time, returning a small candidate set (which guarantees zero false negatives, though it may include false positives whose MBRs overlap even when the true polygons do not).

  1. Phase 2 — Refine Step (Exact Geometry Check): Loads the full vertex coordinates only for the candidate set and evaluates the exact computational geometry predicate (e.g., ST_Intersects, ST_Contains), discarding false positives.
Example 2

2 (5 marks)

Consider a triangular park with vertices and a circular query zone centered at with radius .

  1. Find the MBR of and the MBR of .
  2. Trace what happens in the Filter step and the Refine step when testing ST_Intersects(P, Q).

Compute the MBRs of and :

  • .
  • .

Run the Filter step (MBR intersection): Check overlap along and :

  • -intervals: .
  • -intervals: .

Since both intervals overlap, lies inside , so the Filter step passes as a candidate.

Run the Refine step (exact geometry check): The upper-left edge of triangle connects to , which is the line , and triangle occupies the region . Compute the perpendicular distance from circle center to the boundary line :

Since has (outside ) and is units away from the hypotenuse (more than radius ), and are actually disjoint. The Refine step discards as a false positive.

Answer:

and . The Filter step returns because the MBRs overlap, whereas the Refine step computes exact distance to the hypotenuse and correctly rejects (ST_Intersects = false).


5.6 Geospatial data formats and big geospatial data management

Choosing the right storage format directly affects interoperability, storage size, and cloud streaming performance:

Comparison of Modern Geospatial Data Formats
FormatType & EncodingKey Characteristics & AdvantagesLimitations
ShapefileMulti-file vector (.shp, .shx, .dbf, .prj)Legacy universal GIS interchange format file limit, -char DBF column names, no mixed geometries or topology, many sidecar files
GeoJSONUTF-8 JSON text (RFC 7946)Human-readable, native in web browsers & REST APIsVerbose for large files; coordinates fixed to WGS 84 (EPSG:4326)
KML / KMZXML (or zipped XML)Standard for Google Earth 3D visualization & stylingPoor relational attribute support and large file bloat
GeoPackage (.gpkg)Single SQLite database file (OGC)Stores vectors, raster tiles, attributes, spatial index (R-tree), and metadata in one portable file; no limitLess suited to massive concurrent multi-writer enterprise edits than PostGIS
GeoTIFFBinary raster TIFF + geo-tagsStandard lossless/compressed raster storage preserving CRS & affine transformTraditional row-striped TIFF requires downloading entire file before reading a subset
Cloud Optimized GeoTIFF (COG)Tiled GeoTIFF + internal overviewsOrganized for HTTP GET Range requests, letting cloud clients stream only needed tiles/zoom levels directly from S3/GCSSlightly larger file header/pyramid overhead
GeoParquetApache Parquet columnar binary + WKBColumn-oriented compression, spatial bounding-box row-group statistics; built for distributed engines (Spark/Sedona, DuckDB)Not intended for single-feature transactional updates

Overview of Big Geospatial Data Management

Modern Earth observation archives, IoT vehicle telemetry, and global mobile datasets generate terabytes to petabytes daily—exceeding single-node RDBMS capacity:

added

Question 1

Why is a Spatial DBMS (such as PostGIS) preferred over file-based Shapefiles for enterprise GIS applications? Explain the concept of a geodatabase.

Advantages of Spatial DBMS over Shapefiles:

  1. Multi-user concurrency & ACID transactions: Multiple editors can update features concurrently with row locking and crash recovery, avoiding file corruption.
  2. Rich schema & no file limits: Removes Shapefile's limit, -character attribute name truncation, and multi-file fragility.
  3. Spatial indexing & SQL optimizer: Combines attribute and spatial predicates (ST_Intersects, <->) in a single query plan using GiST R-tree indexes.

Geodatabase concept: A geodatabase is an object-relational spatial repository that stores feature classes alongside domain constraints, subtypes, relationship classes, and topological rules so spatial integrity is enforced at the database tier rather than relying on user discipline.

Answer:

An SDBMS provides ACID transactions, multi-user concurrency, unlimited table sizes, and integrated R-tree spatial query optimization—capabilities file-based Shapefiles lack. A geodatabase extends this storage with feature classes, attribute domains, subtypes, relationship classes, and enforced topological rules.

Question 2

Write a PostGIS Spatial SQL query for two tables wards(ward_id, population, geom) and clinics(clinic_id, name, geom) (both in EPSG:32645) to find the total number of clinics inside Ward 5, and explain the difference between PostGIS's geometry and geography types.

Write the PostGIS Spatial Join SQL query:

Clinics Inside Ward 5SQL
SELECT w.ward_id, COUNT(c.clinic_id) AS total_clinics
FROM wards AS w
LEFT JOIN clinics AS c
  ON ST_Contains(w.geom, c.geom)
WHERE w.ward_id = 5
GROUP BY w.ward_id;

Contrast geometry vs. geography:

  • geometry: Performs fast planar Cartesian math in the unit of the assigned projected SRID (e.g., meters in EPSG:32645). Best for regional/local projected datasets.
  • geography: Stores WGS 84 geographic coordinates and computes true ellipsoidal (geodetic) distances and areas in meters across global spans, at higher CPU cost and fewer supported functions.
Answer:

Use JOIN clinics c ON ST_Contains(w.geom, c.geom) WHERE w.ward_id = 5 with COUNT(c.clinic_id). PostGIS geometry computes fast planar math in the CRS's native units, whereas geography computes exact ellipsoidal distances/areas on the curved Earth in meters.

Question 3

Compare Quadtree and R-tree spatial indexes. Using -bit coordinates with Morton (Z-order) interleaving , compute the Z-order indices of and .

Compare Quadtree vs. R-tree:

  • Quadtree: Recursively partitions a fixed rectangular region into equal quadrants until bucket capacity is met; non-overlapping space partitioning, sensitive to grid boundary placement.
  • R-tree: Height-balanced tree grouping actual feature Minimum Bounding Rectangles (MBRs) into hierarchical bounding boxes; adapts directly to object extents, minimizes empty space, and is the standard spatial index in PostGIS (GiST).

Compute Z-order indices for and :

  • For : (), (). Interleaving gives .
  • For : , . Interleaving gives .
Answer:

A Quadtree uses disjoint space-driven 4-way splits, while an R-tree uses data-driven nested MBRs in a balanced tree. With interleaving, (1101) and (1111).

Question 4

Explain the Filter-and-Refine strategy in spatial query processing. Two geometries have and , where is the lower-right triangle with vertices (region ) and is a circle centered at of radius . Show why passes the filter phase yet is rejected in the refine phase.

Filter-and-Refine strategy:

  • Filter step: Tests fast axis-aligned MBR overlaps using an R-tree index to prune non-matching features in time, producing candidate pairs.
  • Refine step: Evaluates exact vertex geometry on the candidates to eliminate false positives.

Evaluate Filter and Refine for and :

  • Filter step: , so passes the filter phase as a candidate.
  • Refine step: Circle center has (outside ). Distance to triangle edge is:

Because , circle does not touch or intersect triangle , so the refine step rejects .

Answer:

Filter-and-refine prunes rapidly by MBR overlap before running exact geometric tests on candidates. Here and overlap on (passing the filter), but the exact distance from to the boundary is , so the refine step rejects the intersection.

Question 5

Contrast Shapefile, GeoJSON, GeoPackage, Cloud Optimized GeoTIFF (COG), and GeoParquet, stating the best use case for each format.

Summarize each format and its ideal role:

  1. Shapefile: Legacy multi-file vector format (.shp/.dbf/.shx/.prj); only for backward compatibility with older desktop tools.
  2. GeoJSON: Lightweight WGS 84 JSON text; ideal for web APIs and browser mapping (Leaflet/MapLibre).
  3. GeoPackage (.gpkg): Single-file OGC SQLite container with R-tree indexing; best modern desktop/mobile exchange format replacing Shapefiles.
  4. Cloud Optimized GeoTIFF (COG): Internally tiled GeoTIFF with overviews arranged for HTTP Range requests; best for streaming subsets of large cloud-hosted satellite rasters.
  5. GeoParquet: Columnar compressed Parquet table with WKB geometry and bbox statistics; best for distributed cloud analytics (Apache Sedona, DuckDB).
Answer:

Use Shapefile only for legacy interoperability, GeoJSON for lightweight web APIs, GeoPackage as the modern single-file desktop/mobile exchange standard, COG for HTTP range-streaming cloud rasters, and GeoParquet for distributed big-data spatial analytics.

← Spatial Data Acquisition and Data QualitySpatial Analysis →