Chapter 2

Advanced Databases
A spatial database is a database designed to store, query, and manage data that
represents objects in space — such as locations, shapes, and spatial
relationships. It can handle both geometric data (points, lines, polygons) and
geographic data (lat/long coordinates on Earth).

Why Spatial Databases are Needed

Regular databases can store numbers and text, but they don’t know that:
• (12.9716, 77.5946) is a location on Earth
• A certain point is inside a city boundary
• Two roads intersect
Spatial databases understand these relationships and provide specialized indexing for
fast queries.

What Are Spatial Data Types?

Spatial data types define how spatial objects are stored in a database.
They let the DBMS understand whether something is a point, a line, or an area, and
what operations make sense for it.
They generally fall into two broad categories:
1. Geometric types – Purely mathematical
shapes in a flat (planar) coordinate system.
2. Geographic types – Shapes defined on
Earth’s surface using latitude & longitude.

Geographic Types
Some DBMSs (like PostGIS) distinguish geometry
from geography:
• Geometry assumes a flat Cartesian plane
(good for small areas).
• Geography accounts for Earth's curvature
(better for long distances).
Example:
• Geometry distance between Delhi & Mumbai:
straight-line in meters.
• Geography distance: great-circle distance over Earth's surface.

Dr. D. Vivekanandan | Dept of Information Technology | MIT Campus | AU

 Core Spatial Data Types (Geometry)
Data Type Description Example WKT Example
Use

POINT A single Store POINT(77.5946 12.9716)

location in location of a
space store, bus
stop, ATM

LINESTRING Straight or Road, river, LINESTRING(77.59 12.97, 78.00 13.00)

curved path flight path
made from 2+
points

POLYGON Enclosed area City limits, POLYGON((77.58 12.96, 77.60 12.96,

with a closed lake 77.60 12.98, 77.58 12.98, 77.58 12.96))

boundary

MULTIPOINT Multiple points Branch MULTIPOINT(77.59 12.97, 78.00 13.00)

in one object locations of
a bank

MULTILINESTRING Multiple Road MULTILINESTRING((77.59 12.97, 78.00

13.00),(77.61 12.98, 78.02 13.02))
separate lines network
segments

MULTIPOLYGON Multiple Group of MULTIPOLYGON(((...),(...)), ((...),(...)))

polygons islands

GEOMETRYCOLLECTION Mix of different Lake + small GEOMETRYCOLLECTION(POINT(...),

LINESTRING(...), POLYGON(...))
geometry islands + a
types dock

Some spatial query examples (CRUD Operations)

Example: Create a table for storing landmarks as points.

Example: Store parks with both boundary (polygon) and entry points (multi-point).

Dr. D. Vivekanandan | Dept of Information Technology | MIT Campus | AU

Example: Add a spatial column for storing walking trails in a park.

DROP a Spatial Column

Create (Insert)

Read (Query)

Dr. D. Vivekanandan | Dept of Information Technology | MIT Campus | AU

UPDATE and Delete Operation (Just like SQL Query)

2.3 Spatial Relationships

Spatial relationships describe how spatial objects (points, lines, polygons, etc.) are related to
each other in space. These relationships are fundamental in spatial databases, GIS, computer
graphics, and spatial analysis.

They help answer queries like:

• “Which cities are inside Tamil Nadu?”

• “Does this road intersect with the river?”

• “Find the nearest hospital to my location.”

2.3.1 Types Spatial Relationships

Spatial relationships can be categorized into 4 classes

• “Topological Relationships”

• “Directional Relationships”

• Distance Relationships

• Network Relationships

Topological Relationships
Topological relationships in a spatial database describe how spatial objects (like points, lines,
or polygons) relate to each other geometrically, focusing on properties that remain invariant
under continuous transformations like stretching or bending.

Standard relationships (often based on the OpenGIS Simple Features Specification) include:
1. Equals: Two geometries are identical in shape and location (e.g., two polygons cover the
same area).
2. Disjoint: Two geometries have no points in common (e.g., two non-overlapping
polygons).
3. Intersects: Two geometries share at least one point (opposite of disjoint).

Dr. D. Vivekanandan | Dept of Information Technology | MIT Campus | AU

 4. Touches: Two geometries share at least one boundary point but not interior points (e.g.,
two polygons sharing an edge).
5. Crosses: Two geometries intersect such that one passes through the other (e.g., a line
crossing a polygon).
6. Within: One geometry is completely contained within another (e.g., a point inside a
polygon).
7. Contains: The reverse of within (e.g., a polygon contains a point).
8. Overlaps: Two geometries share some but not all points, with partial overlap in their
interiors (e.g., two intersecting polygons).

Directional Relationships
Directional relationships in a spatial database describe the relative orientation or position of
spatial objects (e.g., points, lines, polygons) with respect to each other, typically using cardinal
(e.g., north, south, east, west) or relative directions (e.g., above, below, left, right). Unlike
topological relationships, which focus on invariant properties like containment or adjacency,
directional relationships emphasize the spatial arrangement based on orientation or angular
positioning.

Types of Directional Relationships can be categorized based on the reference system or model
used:

1. Cardinal Directions:

• Based on standard geographic directions: North, South, East, West, Northeast,

etc.

• Example: "City A is north of City B."

• Often used in GIS for straightforward spatial queries.

2. Cone-Based Model:

• Divides space into directional cones (e.g., 8 cones for cardinal and intercardinal
directions).

• Example: A point is in the "northeast" cone relative to another point.

3. Projection-Based Model:

• Projects one object's geometry onto a reference plane to determine directional

relationships.

• Example: Determining if a polygon is "left" of a line based on its centroid.

4. Relative Directions:

• Uses terms like above, below, left, right, in front, behind, based on a reference
object's orientation or an observer's perspective.

• Example: "The park is to the right of the river" (relative to a viewer facing north).

5. Angular Relationships:

• Measures the angle between objects to determine direction (e.g., a point is at a

45° angle from another).

• Used in precise applications like navigation or robotics.

Dr. D. Vivekanandan | Dept of Information Technology | MIT Campus | AU

Usage of Directional Relationships in Real Time querying.

• Geographic Information Systems (GIS): Querying spatial data, e.g., "Find all schools
north of the river."

• Navigation Systems: Determining if a turn is "left" or "right" based on a vehicle’s

heading.

• Urban Planning: Analyzing building layouts, e.g., "Is the park east of the city center?"

• Robotics and AI: Path planning, where a robot needs to know if an obstacle is "in front"
or "to the left."

• Cartography: Labeling maps based on directional relationships for clarity (e.g., placing
labels "above" features).

Comparison with Topological Relationships

• Topological: Focus on connectivity, adjacency, or containment (e.g., "inside," "touches"),

invariant to scale or rotation.

• Directional: Focus on relative orientation (e.g., "north," "left"), sensitive to coordinate

systems or object orientation.

• Example: A topological query might check if a point is "within" a polygon, while a

directional query might check if it’s "north" of the polygon’s centroid.

Distance Relationships
Distance relationships in a spatial database describe the spatial separation between geometric
objects (e.g., points, lines, polygons) in terms of their proximity, measured as a numerical
distance in a given coordinate system. These relationships are critical for spatial analysis,
enabling queries about how far apart objects are, whether they are within a certain radius, or
identifying the nearest neighbors.

Types of Distance Relationships

1. Euclidean Distance:

• Straight-line distance between two points in a planar coordinate system,

calculated as

• Common in local-scale GIS applications.

• Example: Distance between two points (1,1) and (4,5) is 5 units.

2. Geodesic Distance:

• Shortest path on the Earth’s surface (e.g., great-circle distance) for geographic
coordinates (latitude/longitude).

• Used in global-scale applications, accounting for Earth’s curvature.

• Example: Distance between two cities on a globe.

Dr. D. Vivekanandan | Dept of Information Technology | MIT Campus | AU

 3. Manhattan Distance:

• Distance measured along axes (e.g., along grid-like paths), calculated as

|x_2 - x_1| + |y_2 - y_1|

Used in urban planning or grid-based systems.

4. Minimum Distance:

• Shortest distance between two complex geometries (e.g., between a point and a
polygon’s boundary or between two polygons).

• Often computed using closest points on the geometries.

5. Buffer-Based Relationships:

• Determines if objects are within a specified distance (buffer zone) of each other.

• Example: "Find all schools within 1 km of a park."

6. Nearest Neighbor:

• Identifies the closest object(s) to a given reference object.

• Example: "Find the nearest hospital to a given location."

Usage in Real time Querying:

• Geographic Information Systems (GIS): Finding nearby features, e.g., "List all
restaurants within 500 meters of a hotel."

• Urban Planning: Analyzing accessibility, e.g., "Are all residents within 1 km of a public
park?"

• Navigation: Calculating the shortest path or travel distance between locations.

• Environmental Analysis: Measuring distances between ecological features, e.g., "How

far is a water source from a forest?"

• Emergency Services: Identifying the nearest fire station to an incident location.

Comparison with Other Spatial Relationships

• Topological: Focus on connectivity or containment (e.g., "inside," "touches"), not
quantitative distance.

• Directional: Focus on relative orientation (e.g., "north," "left"), not numerical separation.

• Distance: Quantifies "how far" objects are, enabling precise proximity-based queries.

• Example: A topological query checks if a point is "within" a polygon, a directional

query checks if it’s "north" of the polygon’s centroid, and a distance query checks
"how far" it is from the polygon.

Dr. D. Vivekanandan | Dept of Information Technology | MIT Campus | AU

 Network Relationships
Network relationships in a spatial database describe the connectivity and interactions between
spatial objects (e.g., points, lines, or polygons) within a network structure, such as roads, rivers,
pipelines, or utility grids. These relationships focus on how entities are linked through paths or
edges, enabling analysis of routes, flows, connectivity, and accessibility in a spatial context.

Types of Network Relationships

1. Connectivity:

• Determines if nodes are connected by edges (e.g., "Is there a path between two
cities?").

• Example: Checking if two intersections are reachable via road segments.

2. Adjacency:

• Identifies nodes or edges directly connected (e.g., "Which roads connect to this
intersection?").

• Example: Listing all road segments linked to a specific junction.

3. Shortest Path:

• Finds the path with the minimum total weight (e.g., distance or time) between
two nodes.

• Algorithms: Dijkstra’s, A*, or Bellman-Ford.

• Example: "What’s the shortest route from home to work?"

4. Reachability:

• Determines which nodes or areas can be reached within a certain distance,

time, or cost.

• Example: "Find all locations within a 10-minute drive."

5. Flow Analysis:

• Analyzes movement through the network, such as traffic flow, water flow, or data
transmission.

• Example: Calculating maximum flow in a pipeline network.

6. Service Area Analysis:

• Identifies areas accessible from a node within a specified threshold (e.g.,

distance or time).

• Example: "Map the area reachable from a fire station within 5 minutes."

Applications

• Transportation: Finding optimal routes, calculating travel times, or analyzing traffic

networks (e.g., road, rail, or public transit systems).

• Utility Networks: Managing water, gas, or electrical grids, including flow and
connectivity analysis.

Dr. D. Vivekanandan | Dept of Information Technology | MIT Campus | AU

 • Logistics: Optimizing delivery routes or supply chain networks.

• Urban Planning: Analyzing accessibility to services (e.g., hospitals, schools) within a

city network.

• Environmental Studies: Modeling river networks or wildlife corridors for connectivity

analysis.

• Telecommunications: Designing and analyzing network connectivity for internet or

phone systems.

Comparison with Other Spatial Relationships

• Topological: Focus on adjacency or containment (e.g., "touches," "within"), not path-

based connectivity.

• Directional: Focus on orientation (e.g., "north," "left"), not network traversal.

• Distance: Focus on spatial separation (e.g., "how far"), but network relationships
consider paths along edges, not just straight-line distances.

• Network: Emphasize connectivity and traversal along defined paths (e.g., "shortest
route along roads").

2.4 Spatial Data Structures

Categories of Spatial Data Structures
A. Point-based Structures / Region-based Structures
Spatial data structures are specialized data structures designed to efficiently store, query, and
manipulate data associated with spatial information, such as points, lines, polygons, or other
geometric objects in 2D or 3D space. They are widely used in applications like computer graphics,
geographic information systems (GIS), robotics, game development, and spatial databases.
Below is an overview of commonly used spatial data structures, their properties, and typical use
cases.

1. Grid-Based Structures

• Description: Divide space into a regular grid of cells (e.g., 2D or 3D grid). Each cell
contains a list of objects or points that fall within its boundaries.
• Use Cases: Fast spatial queries (e.g., finding objects in a region), collision detection,
and rendering in games.
• Examples:
o Uniform Grid: Divides space into equal-sized cells. Simple to implement and
efficient for uniformly distributed data.
o Hierarchical Grid: Uses multiple levels of grids with varying cell sizes for
adaptive resolution.
• Advantages: Simple, fast for uniform data, constant-time access to cells.
• Disadvantages: Inefficient for sparse or unevenly distributed data, as many cells may
be empty.

Dr. D. Vivekanandan | Dept of Information Technology | MIT Campus | AU

2. Quadtrees (2D) and Octrees (3D)

• Description:
o Quadtree: Recursively divides a 2D space into four quadrants when a cell
exceeds a certain capacity or depth. Each node represents a rectangular region.
o Octree: Extends the quadtree concept to 3D, dividing space into eight octants.
• Use Cases: Collision detection, image compression, spatial indexing in GIS, and level-
of-detail rendering.
• Advantages: Adapts to varying data density, efficient for sparse data, supports
hierarchical queries.
• Disadvantages: Complex to implement, sensitive to data distribution, and queries can
be slower for deep trees.

To visualize a quadtree, the distribution of points across its quadrants or the structure of the
tree. A visualization for the quadtree example provided (with points at (200, 200), (300, 300), and
(250, 250) in a 1000x1000 world).

Visualization Description

• Points: Three points at (200, 200), (300, 300), and (250, 250).

• Quadtree Boundaries:

o Root: 0 ≤ x ≤ 1000, 0 ≤ y ≤ 1000.

o First split: Divides into four 500x500 quadrants at x=500, y=500.

o Second split (in SW quadrant): Divides SW (0 ≤ x ≤ 500, 0 ≤ y ≤ 500) into four

250x250 sub-quadrants at x=250, y=250.

• Chart: A scatter plot showing the points, with dashed lines indicating quadrant
boundaries.

• In the Point-Region quadtree (hereafter referred to as the PR quadtree) each node either
has exactly four children or is a leaf. That is, the PR quadtree is a full four-way branching
(4-ary) tree in shape.
• The PR quadtree represents a collection of data points in two dimensions by
decomposing the region containing the data points into four equal quadrants,
subquadrants, and so on, until no leaf node contains more than a single point. In other

Dr. D. Vivekanandan | Dept of Information Technology | MIT Campus | AU

 words, if a region contains zero or one data points, then it is represented by a PR quadtree
consisting of a single leaf node.
• If the region contains more than a single data point, then the region is split into four
equal quadrants.
• The corresponding PR quadtree then contains an internal node and four subtrees, each
subtree representing a single quadrant of the region, which might in turn be split into
subquadrants. Each internal node of a PR quadtree represents a single split of the two-
dimensional region.
• The four quadrants of the region (or equivalently, the corresponding subtrees) are
designated (in order) NW, NE, SW, and SE. Each quadrant containing more than a single
point would in turn be recursively divided into subquadrants until each leaf of the
corresponding PR quadtree contains at most one point.

For example, consider the region of Figure (a) and the corresponding PR quadtree (b). The
decomposition process demands a fixed key range. In this example, the region is assumed to be
of size 128×128

Note that the internal nodes of the PR quadtree are used solely to indicate decomposition of the
region; internal nodes do not store data records. Because the decomposition lines are
predetermined (i.e, key-space decomposition is used), the PR quadtree is a trie.

Simulation and Algo can be found at:

[Link]

3. k-d Trees (k-Dimensional Trees)

• Description: A binary tree that partitions k-dimensional space by alternating between

dimensions at each level. Each node splits the space along one axis (e.g., x, y, z in 3D).
• Use Cases: Nearest neighbor search, range queries, point cloud processing, and ray
tracing.
• Advantages: Efficient for low-dimensional data (e.g., 2D or 3D), supports dynamic
updates.
• Disadvantages: Performance degrades in high dimensions, unbalanced trees can lead
to inefficient queries.

Dr. D. Vivekanandan | Dept of Information Technology | MIT Campus | AU

Eg:The kd tree is a modification to the BST that allows for efficient processing of multi-
dimensional search keys. The kd tree differs from the BST in that each level of the kd tree makes
branching decisions based on a particular search key associated with that level, called the
discriminator. In principle, the kd tree could be used to unify key searching across any arbitrary
set of keys such as name and zipcode. But in practice, it is nearly always used to support search
on multi-dimensional coordinates, such as locations in 2D or 3D space.

First level: Compare with X, navigate and then at second level compare with Y.

K-D Tree Simulation and Algorithm can be found at:

[Link]

1. R-Trees and Variants

R-Trees are another important spatial data structure widely used in GIS, databases, and spatial
indexing. Unlike Quadtrees (good for raster/grid), R-Trees are best for vector data (points, lines,
polygons).

What is an R-Tree?

• A height-balanced tree (like B-Trees).

• Each node stores a set of Minimum Bounding Rectangles (MBRs).
• Each MBR encloses a group of spatial objects (points, polygons, etc.).
• Used for efficient range queries, nearest neighbor queries, and spatial joins.

Description: A tree structure that groups nearby objects into minimum bounding rectangles
(MBRs) or bounding boxes. Each node stores a bounding region and pointers to child nodes or
objects.

• Variants:
o R-Tree*: Optimized for better splitting and balancing.
o R+-Tree: Avoids overlapping bounding boxes for better query performance.
• Use Cases: Spatial databases, GIS, indexing complex shapes (e.g., polygons, lines).
• Advantages: Handles arbitrary shapes, efficient for range and overlap queries.

Dr. D. Vivekanandan | Dept of Information Technology | MIT Campus | AU

 • Disadvantages: Overlapping regions can lead to redundant searches, complex to
maintain.

Example: Storing City Parks in an R-Tree

Suppose we want to store 4 city parks in a GIS system, each represented by a polygon
(bounding box):
1. Park A → rectangle (2,2) to (4,4)
2. Park B → rectangle (5,3) to (7,6)
3. Park C → rectangle (8,1) to (9,4)
4. Park D → rectangle (3,6) to (6,8)

Solution:

Step 1: Create Leaf Nodes

Each leaf node stores the MBR of one park.
Leaf 1:
• Park A (2,2 – 4,4)
• Park B (5,3 – 7,6)
Leaf 2:
• Park C (8,1 – 9,4)
• Park D (3,6 – 6,8)

Step 2: Create Parent Nodes

Each parent node stores the MBR that encloses its children.
• Parent 1 (covers A + B): rectangle (2,2) to (7,6)
• Parent 2 (covers C + D): rectangle (3,1) to (9,8)
Step 3: Root Node
• Root node stores the MBRs of Parent 1 and Parent 2.
• Root MBR = (2,1) to (9,8)

5. Bounding Volume Hierarchies (BVH)

• Description: A tree structure where each node represents a bounding volume (e.g.,
spheres, axis-aligned bounding boxes, or oriented bounding boxes) enclosing objects or
child nodes.
• Use Cases: Ray tracing, collision detection in 3D graphics, and physics simulations.
• Advantages: Fast intersection tests, hierarchical culling, works well for dynamic
objects.
• Disadvantages: Construction can be computationally expensive, less efficient for
highly dynamic scenes without updates.

Dr. D. Vivekanandan | Dept of Information Technology | MIT Campus | AU

6. BSP Trees (Binary Space Partitioning)

• Description: Recursively partitions space using planes into two subspaces, forming a
binary tree. Each node represents a splitting plane, and leaves contain objects.
• Use Cases: Rendering in games (e.g., Doom), visibility determination, and collision
detection.
• Advantages: Precise partitioning, efficient for static scenes, supports visibility ordering.
• Disadvantages: Expensive to construct and update, not ideal for dynamic
environments.

7. Spatial Hashing

Spatial hashing is a spatial data structure that maps objects in a multidimensional

space (e.g., 2D or 3D) to a hash table by discretizing the space by dividing it into a grid of
cells. Each object is assigned to one or more cells based on its position or bounding
box, and the cells are stored in a hash table for fast lookups.

It works by dividing space into cells and using a hash function to map objects or points
into these cells, allowing for rapid neighbor lookups and collision detection.

Description: Maps spatial coordinates to a hash table by discretizing space into a grid.
Objects in the same grid cell are hashed to the same bucket.

Use Cases: Particle simulations, real-time collision detection, and large-scale spatial
queries.

Advantages: Fast lookups, scalable for large datasets, simple to implement.

Disadvantages: Hash collisions can degrade performance, requires tuning grid size.

Scenario

Consider a 2D 1000x1000 game world with moving objects (e.g., particles or characters)
represented by points:

• P1: (200, 200) (id=1)

• P2: (300, 300) (id=2)

• P3: (250, 250) (id=3) The spatial hash will:

• Divide the space into a grid (e.g., 100x100 cells).

• Map each point to grid cells using a hash function.

• Support insertion (adding a point to cells) and deletion (removing a point by ID).

Spatial Hash Structure

• Grid: The 2D space is divided into cells of fixed size (e.g., 100x100 pixels).

• Hash Table: Maps cell coordinates (e.g., (i, j)) to a list of objects in that cell.

• Hash Function: Converts cell coordinates to a hash key (e.g., string “i,j” or a
numerical hash).

• Cell Assignment: Points are assigned to the cell(s) they occupy. For objects with
extent (e.g., rectangles), they may occupy multiple cells.

Dr. D. Vivekanandan | Dept of Information Technology | MIT Campus | AU

8. Voronoi Diagrams and Delaunay Triangulations

• Description:
o Voronoi Diagram: Partitions space into regions where each region contains
points closer to a specific seed point than to any other.
o Delaunay Triangulation: The dual of a Voronoi diagram, connecting points to
form triangles (or tetrahedra in 3D) with specific geometric properties.
• Use Cases: Nearest neighbor queries, mesh generation, pathfinding, and terrain
modeling.
• Advantages: Optimal for proximity queries, mathematically elegant.
• Disadvantages: Computationally expensive to construct and update.

Example: Suppose we have 4 points (called sites) on a plane:

• P1=(2,3)
• P2=(6,5)
• P3=(8,2)
• P4=(4,7)
Steps to construct the Voronoi diagram:

1. Plot the points on a 2D plane.

2. For each pair of points, find the perpendicular bisector of the line segment joining
them.

3. The perpendicular bisectors divide the plane into cells (regions). Each cell contains all
points closer to its site than to any other site.

4. The resulting polygons form the Voronoi cells.

Interpretation
• Any point inside the cell for P1is closer to P1 than P2, P3 and P4.
• The edges of the Voronoi cells are points that are equidistant to two sites.
• The vertices of the Voronoi diagram are points equidistant to three or more sites.

Dr. D. Vivekanandan | Dept of Information Technology | MIT Campus | AU

Applications
• Geography: Determining the nearest hospital or school to any location.
• Computer graphics: Texture mapping and mesh generation.
• Robotics: Path planning.
• Urban planning: Market area analysis.
9. Point-Based Structures

• Description: Specialized structures for

managing large sets of points, often used
in point cloud processing.
• Examples:
o Point Quadtrees: A quadtree
variant where nodes store points
rather than regions.
o Cover Trees: Designed for
efficient nearest neighbor
searches in metric spaces.
• Use Cases: Point cloud rendering,
machine learning (e.g., clustering), and
spatial analysis.
• Advantages: Efficient for point data,
supports high-dimensional spaces.
• Disadvantages: Limited to point data,
may require preprocessing.

Comparison of Spatial Data Structures

Data Structure Best For Query Types Complexity Complexity
(Construction) (Query)

Uniform Grid Uniform data Range, O(n) O(1) for cell

collision access

Quadtree/Octree Sparse data Range, O(n log n) O(log n)

nearest

k-d Tree Low Nearest, O(n log n) O(log n)

dimensions range

R-Tree Complex Range, O(n log n) O(log n)

shapes overlap

BVH Dynamic Intersection O(n log n) O(log n)

scenes

BSP Tree Static scenes Visibility O(n log n) O(log n)

Spatial Hashing Large Collision O(n) O(1) with

datasets collisions

Voronoi Diagram Proximity Nearest O(n log n) O(log n)

Dr. D. Vivekanandan | Dept of Information Technology | MIT Campus | AU

Choosing the Right Spatial Data Structure

• Data Distribution: Uniform grids work well for evenly distributed data, while
quadtrees/octrees or R-trees are better for sparse or clustered data.

• Query Type: Nearest neighbor searches favor k-d trees or Voronoi diagrams, while range
queries are efficient with R-trees or grids.

• Dynamic vs. Static: BVHs and spatial hashing are better for dynamic scenes, while BSP
trees excel in static environments.

• Dimensionality: k-d trees are effective in low dimensions, but performance degrades in
high dimensions, where cover trees or spatial hashing may be better.

2.5 Active Databases

2.5.1 Introduction
An active database is a database management system (DBMS) that incorporates event-
driven mechanisms to automatically respond to specific conditions or events within the
database. Unlike traditional passive databases, which rely on external applications to
initiate queries or updates, active databases use predefined rules (often called triggers
or Event-Condition-Action rules) to monitor events, evaluate conditions, and execute
actions autonomously.
Key Components (ECA Model):
• Event: A change in the database state (e.g., insert, update, delete) or an external
event (e.g., time-based or sensor data).
• Condition: A logical test to check if the event meets specific criteria.
• Action: An operation executed when the condition is satisfied (e.g., updating
another table, sending a notification).
Characteristics
• Proactivity: Automatically performs actions without external intervention.
• Rule-Based: Uses stored rules to define behavior.
• Real-Time Response: Executes actions immediately or on a schedule.
• Integration: Combines data management with business logic.
How It Works
1. Event Detection: The DBMS monitors for events like data modifications or
system events (e.g., a timer).
2. Condition Evaluation: Checks if the event satisfies predefined conditions (e.g., "if
stock < 10").
3. Action Execution: Performs tasks like updating records, logging, or invoking
external procedures.

Dr. D. Vivekanandan | Dept of Information Technology | MIT Campus | AU

Implementation
• Triggers: Most relational DBMSs (e.g., PostgreSQL, Oracle, SQL Server) support
triggers to implement active database functionality.
CREATE TRIGGER notify_low_stock
AFTER UPDATE ON inventory
FOR EACH ROW
WHEN ([Link] < 10)
EXECUTE FUNCTION send_alert();
• Stored Procedures: Encapsulate complex actions triggered by events.

2.5.2 Languages for Rule Specifications: ECA

Specifying active rules as triggers in Oracle notation. Below are the examples for statement
level active rules in ORACLE.

(a) Triggers for automatically maintaining the consistency of Total_sal of DEPARTMENT

Dr. D. Vivekanandan | Dept of Information Technology | MIT Campus | AU

(b) Examples of Statement-Level Active Rules in STARBURST

In STARBURST, First the basic events that can be specified for triggering the rules are the
standard SQL update commands: INSERT, DELETE, and UPDATE. These are specified by the
keywords INSERTED, DELETED, and UPDATED in STARBURST notation.

Second, the rule designer needs to have a way to refer to the tuples that have been modified.
The keywords INSERTED, DELETED, NEW-UPDATED, and OLD UPDATED are used in
STARBURST notation to refer to four transition tables

2.5.3 Rule Considerations: ECA

The rule condition evaluation is also known as rule consideration, since the action is to
be executed only after considering whether the condition evaluates to true or false.
There are three main possibilities for rule consideration:
1. Immediate consideration. The condition is evaluated as part of the same
transaction as the triggering event and is evaluated immediately. This case can be
further categorized into three options:
■ Evaluate the condition before executing the triggering event.
■ Evaluate the condition after executing the triggering event.
■ Evaluate the condition instead of executing the triggering event.

Dr. D. Vivekanandan | Dept of Information Technology | MIT Campus | AU

2. Deferred consideration. The condition is evaluated at the end of the transaction that
included the triggering event. In this case, there could be many triggered rules waiting to
have their conditions evaluated.
3. Detached consideration. The condition is evaluated as a separate transaction,
spawned from the triggering transaction.

2.6 Temporal Databases

2.6.1 Introduction
A temporal database is a database management system (DBMS) designed to store and
manage data with a time dimension, tracking changes over time to maintain historical
records alongside current data. Unlike traditional databases that store only the current
state, temporal databases capture the valid time (when data is true in the real world)
and/or transaction time (when data is stored in the database), enabling queries about
past, present, and sometimes future states.
Key Concepts
1. Valid Time: The period when a fact is true (e.g., an employee’s role from 2023-
01-01 to 2024-06-30).
2. Transaction Time: The period when the data is recorded in the database (e.g.,
when a record was inserted or updated).
3. Bitemporal: Combines valid time and transaction time for full historical
accuracy and auditability.
4. Temporal Queries: Retrieve data as it was at a specific time, track changes, or
analyze trends.
5. Temporal Constraints: Ensure data integrity across time (e.g., no overlapping
valid periods for unique attributes).
Types of Temporal Databases
1. Valid-Time Databases: Track when facts are true (e.g., employee salary history).
2. Transaction-Time Databases: Track when data was entered or modified (e.g.,
audit logs).
3. Bitemporal Databases: Combine both, allowing queries like “What did we know
about an employee’s salary on 2024-01-01, and when was it true?”
4. Snapshot Databases: Store only current data but can simulate temporality with
versioning.
Features
• Time-Aware Schema: Tables include time attributes (e.g., valid_start, valid_end,
transaction_start, transaction_end).
• Temporal Operators: SQL extensions like AS OF, FROM-TO, or CONTAINS for
time-based queries.
• Data Versioning: Maintains historical versions of rows rather than overwriting.
• Indexing: Temporal indexes (e.g., time-based B-trees or R-trees) for efficient
time-range queries.

Dr. D. Vivekanandan | Dept of Information Technology | MIT Campus | AU

 2.6.2 Temporal CRUD OPS
SQL:2011
CREATE TABLE employee
(
emp_id INT,
salary INT,
valid_period PERIOD FOR valid_time,
SYSTEM VERSIONING
);

SELECT * FROM employee FOR SYSTEM_TIME AS OF '2025-01-01';

PostgreSQL: No native temporal tables, but can be implemented using range types (tsrange,
tstzrange) and triggers.

CREATE TABLE employee_history

(
emp_id INT,
salary INT,
valid_time tstzrange
);
SELECT * FROM employee_history
WHERE valid_time && tstzrange('2024-01-01', '2025-01-01');

Oracle:
ALTER TABLE employee ADD PERIOD FOR valid_time;
SELECT * FROM employee AS OF PERIOD FOR valid_time DATE '2025-01-01';

2.6.3 Languages for Temporal Rule Specification (ECA Model Integration)

Temporal databases often integrate with the Event-Condition-Action (ECA) model to enforce
temporal constraints or automate actions based on time-based events.

PL/SQL, Oracle:

CREATE OR REPLACE TRIGGER salary_change_alert

BEFORE UPDATE OF salary ON employee
FOR EACH ROW
WHEN (NEW.valid_time <> OLD.valid_time)
BEGIN
INSERT INTO audit_log (emp_id, change_time, old_salary, new_salary)
VALUES (:NEW.emp_id, SYSDATE, :[Link], :[Link]);
END;

TSQL (Temporal SQL):

SELECT emp_id, salary

FROM employee
WHERE VALID TIME OVERLAPS (DATE '2024-01-01', DATE '2025-01-01');

Dr. D. Vivekanandan | Dept of Information Technology | MIT Campus | AU

FLINK SQL: Handle temporal events in real-time, especially for time-series or bitemporal data.
SELECT emp_id, salary
FROM employee_stream
WHERE valid_time < NOW()
AND EVENT_TIME > TIMESTAMP '2025-01-01';

2.6.4 Temporal Data Models and Querying

A temporal data model defines how time-related information is represented, stored, and
queried in a database to support temporal data management.

Types of Temporal Data Models

a. Valid-Time Data Model
• Description: Tracks the period when data is valid in the real world.
• Structure: Adds valid-time attributes (e.g., valid_start, valid_end) to tables.

CREATE TABLE employee_salary (

emp_id INT,
salary INT,
valid_start DATE,
valid_end DATE
);
• Queries: Retrieve data for a specific time or period (e.g., SELECT salary FROM
employee_salary WHERE valid_start <= '2024-06-01' AND (valid_end > '2024-06-01' OR
valid_end IS NULL)).
• Use Cases: Historical tracking (e.g., salary changes, contract durations).
• Challenges: Managing open-ended periods (e.g., NULL for current data); ensuring non-
overlapping periods.

b. Transaction-Time Data Model

• Description: Tracks when data is recorded or modified in the database, supporting audit
trails.
• Structure: Adds transaction-time attributes (e.g., transaction_start, transaction_end) to
tables, often managed automatically by the DBMS.

CREATE TABLE employee_log (

emp_id INT,
salary INT,
transaction_start DATETIME,
transaction_end DATETIME
) WITH SYSTEM VERSIONING;

emp_id salary transaction_start transaction_end

101 50000 2023-01-01 10:00 2023-12-31 12:00
101 55000 2023-12-31 12:01 9999-12-31 23:59
• Queries: Retrieve data as it was known at a specific time (e.g., SELECT * FROM
employee_log FOR SYSTEM_TIME AS OF '2023-06-01').
• Use Cases: Auditing, compliance (e.g., GDPR, financial audits).
• Challenges: Storage growth due to immutable history; limited to database events.

Dr. D. Vivekanandan | Dept of Information Technology | MIT Campus | AU

c. Bitemporal Data Model
• Description: Combines valid time and transaction time for full historical and audit
tracking.
• Structure: Includes both valid-time and transaction-time attributes.

CREATE TABLE employee_bitemporal (

emp_id INT,
salary INT,
valid_start DATE,
valid_end DATE,
transaction_start DATETIME,
transaction_end DATETIME
) WITH SYSTEM VERSIONING;

emp_id salary valid_start valid_end transaction_start transaction_end

101 50000 2023-01-01 2023-12-31 2023-01-02 09:00 2023-12-31 11:00
101 55000 2024-01-01 NULL 2023-12-31 11:01 9999-12-31 23:59

Queries: Complex queries like “What did we know about an employee’s salary on 2023-06-01,
and when was it valid?”
SELECT salary
FROM employee_bitemporal
FOR SYSTEM_TIME AS OF '2023-06-01'
WHERE valid_start <= '2023-06-01' AND (valid_end > '2023-06-01' OR valid_end IS NULL);

d. Snapshot Data Model with Versioning

• Description: Stores only the current state but uses versioning (e.g., appending
timestamps or version numbers) to simulate temporality.
• Structure: Adds a version or timestamp column to track changes.

CREATE TABLE employee_versioned (

emp_id INT,
salary INT,
version_timestamp DATETIME
);

emp_id salary version_timestamp

101 50000 2023-01-01 10:00
101 55000 2024-01-01 09:00

2.7 Temporal Relational Algebra

Temporal Relational Algebra extends traditional relational algebra to handle temporal
data by incorporating time dimensions, such as valid time (when data is true in the real world)
and transaction time (when data is stored in the database). It provides a formal framework for
querying and manipulating temporal databases, enabling operations that account for time
intervals or timestamps. This is particularly useful for applications requiring historical tracking,
auditing, or time-based analysis, such as in finance, HR, or healthcare.

Dr. D. Vivekanandan | Dept of Information Technology | MIT Campus | AU

 2.7.1 Temporal Relational Algebra Operators
Temporal Selection (𝝈𝑻 )
• Description: Filters tuples based on attribute conditions and temporal constraints (e.g.,
valid during a specific period).

Example: Select employees with salary > 50000 valid in 2024.

-- Equivalent SQL

SELECT * FROM Employee

WHERE salary > 50000
AND valid_start <= '2024-12-31' AND valid_end > '2024-01-01';

Temporal Projection (𝛑𝑻 )

• Description: Projects attributes while preserving temporal attributes to maintain time
context.

Example: Project emp_id and salary with valid time.

SELECT emp_id, salary, valid_start, valid_end FROM Employee;

Temporal Join (⋈𝑻 )

• Description: Joins relations based on attribute conditions and temporal overlap (e.g.,
periods where both relations are valid).

Example: Join Employee with Department(emp_id, dept_name, valid_start,

valid_end) where periods overlap.

SELECT e.emp_id, [Link], d.dept_name

FROM Employee e JOIN Department d
ON e.emp_id = d.emp_id
AND e.valid_start < d.valid_end AND e.valid_end > d.valid_start;

Temporal Slice (𝛕)

Description: Extracts tuples valid at a specific time or interval.
SQL Equivalent: SELECT * FROM Employee WHERE valid_start <= '2024-01-01' AND
valid_end > '2024-01-01';

Dr. D. Vivekanandan | Dept of Information Technology | MIT Campus | AU