Spatial Databases and Information Systems PDF

Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM SPATIAL DATABASES AND INFORMATION SYSTEMS PROF JOSEPH G VELLA ©, UNIVERSITY OF MALTA [email protected] 1 “SPACE BY ITSELF, AND TIME BY ITSELF, ARE DOOMED TO FADE AWAY INTO...

Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM SPATIAL DATABASES AND INFORMATION SYSTEMS PROF JOSEPH G VELLA ©, UNIVERSITY OF MALTA [email protected] 1 “SPACE BY ITSELF, AND TIME BY ITSELF, ARE DOOMED TO FADE AWAY INTO MERE SHADOWS, AND ONLY A KIND UNION OF THE TWO WILL PRESERVE AN INDEPENDENT REALITY.” – ALBERT EINSTEIN, ~1910 SPATIAL DATABASES AND INFORMATION SYSTEMS PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 2 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 1 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM SPATIAL DATA & OPERATIONS PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 4 SPATIAL DATA is data associated to a location in space (including multi dimensional space – vector data) or about space itself (e.g. raster image).  An entity instance can be composed both of non-spatial data (descriptive or categorical properties - what we are accustomed to) and spatial data.  We couch spatial data in terms of:  a spatial reference system - the end user’s perspective (location, speed).  And a co-ordinate system – on which the spatial data is laid.  There are a number of these – Euclidean, polar etc.  Geospatial data is spatial data tied to our globe’s surface.  Therefore geospatial data is spatial data;  But not all spatial data is geospatial data! Also with geospatial data we have a number of traditional co-ordinate systems – most coming from cartography (the making of maps). Furthermore some basic, but hard, decisions have to be made on how to project data and approximate the Earth’s surface. PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 5 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 2 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM EXAMPLES OF SPATIAL DATA Simple self contained spatial objects: Point Line Region extent less! connection in extent is e.g. city, tree space. relevant! e.g. road, e.g. built-up boundary area, forest Spatially related collections of objects: Partition Network each point is connectedness allocated a value (for e.g. bus routes, an attribute) hi voltage elect e.g. pop density, grid land use PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS Digital Terrain Models 6 BOUNDING BOX OF A SPATIAL OBJECT 2D 3D PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 7 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 3 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM OPERATIONS ON SPATIAL DATA Which outgoing path of point 1 is the cheapest? Which point is the closest? What area does this shape has? Where do lines l1 and l2 intersect? Which points on line 4 and 5 are the closest? Some spatial PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS “overlaps”! 8 EXAMPLES OF SPATIAL DATA  Census and surveys data sets  Satellites imagery - terabytes of data per day  Water pathways (rivers), farms, ecological sites of importance  Technical plans of machines, buildings  Weather and Climate Data  Medical imaging  Bodies for animation PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 9 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 4 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM SPATIAL DATA IS MULTIDIMENSIONAL  Multidimensional Data is made up of a number of dimensions as opposed to single dimensional data.  Attributes might be perceived as the dimensions of multidimensional space  Example of multidimensional data: A city which has the name, population, coordinates, coverage, street network, and income as its attributes PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 10 SPATIAL RELATIONSHIPS  A spatial object in space is related to other objects by:  vicinity  Metric: which telephone booth is closest to a specific road segment?  coverage  Topological: equal, intersect, in, cover, touch are examples  directional  NEWS, on top, topmost, lower, lowest  connectedness  Graph model for shortest path  build-up  A spatial object is composed of other spatial objects - But the higher level object is “the” object.  A spatial object is an aggregation of other objects - The higher object is the object but: it could be dismantled into other objects; it could “share” a number of spatial objects PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 11 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 5 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM SIMPLE SPATIAL RELATIONSHIPS BETWEEN OBJECTS (NO HOLES AND CONNECTED 2D OBJECTS) Egenhofer, 1989 & 1994  U is the universe (shaded in green). ‘A’ is the shape (e.g. the ellipse interior shaded in blue). Shape A’s boundary is drawn in yellow.  A is the interior;  A is the boundary; and A− is the exterior in U. U A In terms of boundary and interior! PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 12 SIMPLE SPATIAL RELATIONSHIPS BETWEEN OBJECTS (NO HOLES AND CONNECTED 2D OBJECTS) Egenhofer, 1989 & 1994  U is the universe (shaded in green). ‘A’ is the shape (e.g. the ellipse interior shaded in blue). Shape A’s boundary is drawn in yellow.  A is the interior;  A is the boundary; and A− is the exterior in U. U A In terms of boundary, interior and exterior! PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 13 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 6 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM SPATIAL RELATIONSHIPS BETWEEN OBJECTS  Simpler explanation found in Brisaboa, Luaces & Seco, “An inconsistency measure of spatial data sets with respect to topological constraints”, 2014 PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 14 SPATIAL CONSTRAINTS ✓ We need to inhibit any introduction or manipulation of spatial objects (e.g. translation, rotation, redraw boundaries) that does not make ‘sense’. ✓ We need to be able to model motion and animation that enables automatic semantically consistent modification of encoded data involving interactions with space and itself.  Constraint checking in:  2D - Relatively straight forward, albeit tedious  3D - In general these are heavy to compute PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 15 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 7 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM SPATIAL CONSTRAINTS ENCODING Here the problem of reshaping objects A, B, C, & D but maintain their initial spatial relationships is reduced to converting the original spatial relationships into a graph and consequently checking the graph’s invariance under any object deformation. PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 16 SPATIAL CONSTRAINT’S IN DATA REDUCTION  Convert (reduce) an original object into another mesh that does not degrade the usage and visualisation potential of the original. Normal Mesh Reduced Mesh Vertices: 1443 Vertices: 614 Faces: 2800 Faces: 1102 VRML/x3d VRML/x3d LOC:2471 LOC:1005 PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 17 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 8 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM SPATIAL CONSTRAINTS FOR GENERATING AN ACCEPTABLE TRACK!  Is the generated polygon (dark line) within the acceptable region and with the “right” curvatures? PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 18 SPATIAL CONSTRAINTS, NOT!? “I am Programmer, I have no life”, Facebook group, 9th June, 2023 PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 19 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 9 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM SPATIAL CONSTRAINTS, NOT!? PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 20 SPATIAL CONSTRAINTS FOR GENERATING AN ACCEPTABLE MOVEMENT!  How can we animate the puppet limb with acceptable movements (in terms of space and time)?  This is called spatio-temporal analysis! PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 21 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 10 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM SPATIAL DATA MANIPULATION  Geometric selection:  Point Which objects are at (x, y)? Returns all objects: points, lines, polygons  Windowing Which objects in MBR or polygon? Returns all object that overlap with MBR (i.e. output area could be greater than MBR’s.  Clipping Which objects in MBR or polygon? Returns an object or part-of (delimited by MBR) that overlap and MBR.  Merger of objects  Attribute value based selection (non spatial selection)  Give the cities that do not have a council election this year. PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 22 SPATIAL DATA QUALITY  Data quality is dependent on the area, it is being used  However when referring to spatial data quality one would mostly be referring to 4 main components: 1. Accuracy  The error in accuracy with regards to points - divergence between the actual physical location and the location found in the data set  Metrics for line and region still need to be established 2. Precision  Indicates the level of detail which can be determined from the data set  Every data set has some kind of restriction on their resolution since there is no metric which is “infinitely precise”  Most spatial data sets would be generalised on purpose PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 24 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 11 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM SPATIAL DATA QUALITY (CONTINUED) 3. Consistency  No conflicts or ambiguities in the database  Conformance of the data set with specific “topological rules” which vary with the number of dimensions  Example: all roads must intersect at junctions 4. Completeness  Connection between spatial objects in the database and the actual objects  Might be sub divided into two different sections - data completeness - model completeness PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 25 COMPUTER SYSTEMS WITH A SPATIAL COMPONENT  Geographic or open space  Mostly 2D but some data in 3D  3D – Astronomy  Chip fabrication  2D but multi layered  3D – mechanical and physiological systems (organs, trees, etc)  3d Modellers  Drone assisted flying  3D models of microscopic worlds  DNA  3D models of biological populations PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 26 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 12 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM CAN WE MODEL SPATIAL DATA & RELATIONSHIPS ON TOP OF A RDBMS  Can we use a relational DBMS for handling spatial databases?  Every entity, relationship and constraint has to be encoded;  Lowers logical and physical independence is achieved.  A lot of re-inventing the wheel occurs.  All the spatial functions need to be analysed, written, tested, documented etc.  Experience on how best to “encode” spatial data into relational structures is gained through experience (sometime bitter too).  Few DBMS have multi-dimensional indexes.  Remember Spatial object are multidimensional.  Best option to opt for a spatially *enabled* DBMS. PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 27 SPATIALLY ENABLED DBMS  What, when, and where can spatial DBMS help?  Modelling spatial structures, relationships, and constraints  With implicit support to spatial data types  Offer efficient solutions to spatial data storage, indexing and retrieval  “Joining” data on spatial attributes  Requires handing of models that are not strictly geographical in nature PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 28 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 13 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM EXAMPLES OF SPATIALLY ENABLED DBMS  Oracle DBMS (since 8i)  Microsoft SQL Server  PostgreSQL  Some spatial data types and functions available  PostGIS (An extension for PostgreSQL with Spatial, GIS & Raster data)  More complete version with more adherence to industry standards (e.g. OGC) PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 29 NECESSARY SUPPLEMENTARY TOOLS  QGIS – multiplatform, open-source GIS  E.g., QGIS, JumpGIS  GDAL & OGR (https://www.gdal.org/)  Swiss army knife tools to handle spatial data translation, reading, transforming etc  CuRL and WGET for automating data pulling from web services  JSON & GeoJSON editors, viewers and validators  E.g. http://geojsonlint.com/  Google Map (and other services) API PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 30 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 14 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM OPENGIS DATA TYPES (SIMPLIFIED) PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 31 POSTGIS SPATIAL DATA TYPES Vector Raster PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 32 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 15 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM SPATIALLY ENABLED DATASETS & ACQUISITION  Field surveys:  Traditional, and Global Positioning System enabled  “Implicit” tracking:  Smart phones (ubiquitous and ushered a new realm of services (location based services))  Digitising maps, digitising plans, digitising location (e.g. radar, sonar)  Remote sensing  Data mining  Supplementing data sources (with spatial attributes)  Many, many exists  Combining data sources (not easy) √ In general this is a significant labour and computational effort!  Some efforts are one time (sea bathymetry, google street view).  Data quality issues are also significant; and are further complicated when combining datasets. (sorry for repeating twice In one slide) PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 33 SPATIAL QUERIES IN SQL rem query 1 (no particular syntax) SELECT T.name Query One FROM town T From the towns table return the name of towns whose area overlap that specified by the WHERE overlap( T.area, :querybox() ) user (e.g. some query bounding box). Query Two rem query 2 Which planning applications and towns centres SELECT P.desc, T.name are within 10 kms for applications whose FROM planning P, town T planning gain is greater than 10,000,000 euro? WHERE distwithin( P.area.centre, T.area.centre, 10 ) AND P.plan_gain > 10000000 PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 34 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 16 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM SPATIAL ENABLED DBMS 51 SPATIALLY ENABLED DBMS OVERVIEW  The role of a Spatial DBMS  The Spatial Data Model  Mapping Spatial Models to DBMS  Spatial data definition  Spatial data manipulation  Spatial support  Examples  Using a relational DBMS “empowered” with spatial facilities! PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 52 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 17 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM SPATIAL DBMS  A Spatial DBMS must have the same characteristics and functionalities of other (i.e. non-spatial DBMS). For example:  A data and query model;  Data Definition Language  Data Control Language  Data Manipulation Language  Data import and raw data processing  Query Processing and, if declarative, Query Optimisation;  A transaction model;  To maintain availability and reliability in a “sharing” environment  Control and Management issues pertaining to data  A Spatial DBMS offers, e.g. over and above a non-spatial DBMS, spatial characteristics and management.  Spatial data model and query model  Spatial data storage management  Efficient use of resources – space, performance, sharing etc  Management of spatial specific artefacts – spatially enabled indexes PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 53 ogc_header_top_left THE SPATIAL DATA MODEL  What are the spatial objects we can abstract?  Point, multipoint, line, multi-line, polygon, multi-polygon, and geometry collections. PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 54 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 18 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM WELL-KNOWN TEXT (WKT) REP FOR GEOMETRY ogc_header_top_left := := GEOMETRYCOLLECTION | := EMPTY | ( ) | := | := double precision literal Each Geometry Type has a | := double precision literal WKT that can be used both | := EMPTY | ( {, }* ) | to construct new instances of := EMPTY := the type and to convert POINT | ( existing instances to textual := {, }*) := EMPTY form for alphanumeric display. LINESTRING | ( {, }* ) := := EMPTY | ( POLYGON {, < LineString Text > }* ) := := EMPTY MULTIPOINT | ( < Polygon Text > := {, < Polygon Text > }* ) MULTILINESTRING := EMPTY | ( := {, }* ) MULTIPOLYGON PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 55 WKT EXAMPLES ogc_header_top_left PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 56 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 19 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM WELL-KNOWN BINARY (WKB) REP FOR GEOMETRY ogc_header_top_left  The WKB rep for Geometry provides a portable representation of a geometric object as a contiguous stream of bytes.  The WKB rep for Geometry is obtained by serializing a geometric object as a sequence of numeric types drawn from the set {Unsigned Integer, Double} and then serializing each numeric type as a sequence of bytes.  The specific binary encoding used for a geometry representation is described by a one-byte tag that precedes the serialized bytes. PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 57 SPATIAL OBJECTS EXAMPLES PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 58 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 20 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM ogc_header_top_left BASIC METHODS ON GEOMETRIC OBJECTS (I)  Dimension ( ):Integer  The inherent dimension of this geometric object, which must be less than or equal to the coordinate dimension. This specification is restricted to geometries in 2-dim coordinate space.  GeometryType ( ):String  Returns the name of the instantiable subtype of Geometry of which this geometric object is a instantiable member. The name of the subtype of Geometry is returned as a string.  SRID ( ):Integer  Returns the Spatial Reference System ID for this geometric object.  Envelope( ):Geometry  The minimum bounding box for this Geometry, returned as a Geometry. The polygon is defined by the corner points of the bounding box [(MINX, MINY), (MAXX, MINY), (MAXX, MAXY), (MINX, MAXY), (MINX, MINY)]. PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 59 BASIC METHODS ON GEOMETRIC OBJECTS (II) ogc_header_top_left  AsText( ):String  Exports this geometric object to a specific Well-known Text Representation of Geometry.  AsBinary( ):Binary  Exports this geometric object to a specific Well-known Binary Representation of Geometry.  IsEmpty( ):Integer  Returns 1 (TRUE) if this geometric object is the empty Geometry. If true, then this geometric object represents the empty point set, ∅, for the coordinate space.  IsSimple( ):Integer  Returns 1 (TRUE) if this geometric object has no anomalous geometric points, such as self intersection or self tangency. The description of each instantiable geometric class will include the specific conditions that cause an instance of that class to be classified as not simple.  Boundary( ):Geometry  Returns the closure of the combinatorial boundary of this geometric object. Because the result of this function is a closure, and hence topologically closed, the resulting boundary can be represented using representational Geometry primitives. PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 60 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 21 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM METHODS/PREDICATES FOR TESTING SPATIAL RELATIONS ogc_header_top_left  Equals(anotherGeometry:Geometry):Integer Returns 1 (TRUE) if this geometric object is “spatially equal” to another Geometry.  Disjoint, Intersects,Touches, Crosses, Within, Contains, Overlaps Returns a Boolean according to respective semantics  Relate(otherGeometry:Geometry, interPatternMatrix:String):Integer  Returns 1 (TRUE) if this geometric object is spatially related to another Geometry by testing for intersections between the interior, boundary and exterior of the two geometric objects as specified by the values in the Intersection Pattern Matrix. PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 61 PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 62 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 22 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 63 PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 64 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 23 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 65 PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 66 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 24 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 67 PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 68 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 25 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 69 METHODS THAT SUPPORT SPATIAL ANALYSIS (I) ogc_header_top_left  Distance(anotherGeometry:Geometry):Double  Returns the shortest distance between any two Points in the two geometric objects as calculated in the spatial reference system of this geometric object.  Buffer(distance:Double):Geometry  Returns a geometric object that represents all Points whose distance from this geometric object is less than or equal to distance. Calculations are in the spatial reference system of this geometric object.  ConvexHull( ):Geometry  Returns a geometric object that represents the convex hull of this geometric object. PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 70 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 26 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM METHODS THAT SUPPORT SPATIAL ANALYSIS (II) ogc_header_top_left  Intersection(anotherGeometry:Geometry):Geometry  Returns a geometric object that represents the Point set intersection of this geometric object with another Geometry.  Union(anotherGeometry:Geometry):Geometry  Returns a geometric object that represents the Point set union of this geometric object with another Geometry.  Difference(anotherGeometry:Geometry):Geometry  Returns a geometric object that represents the Point set difference of this geometric object with another Geometry.  SymDifference(anotherGeometry:Geometry):Geometry  Returns a geometric object that represents the Point set symmetric difference of this geometric object with another Geometry. PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 71 PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 72 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 27 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM SPATIALLY ENABLED INTERSECTION AND UNION PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 73 CONVEX HULL Convext Hull (outer) vs Concave Hull (inner) PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 74 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 28 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM GEOMETRY COLLECTION ogc_header_top_left  A Geometry Collection is a geometric object that is a collection of 1 or more geometric objects.  All the elements in a Geometry Collection shall be in the same Spatial Reference. This is also the Spatial Reference for the Geometry Collection.  Methods  NumGeometries( ):Integer  Returns the number of geometries in this Geometry Collection.  GeometryN(N:integer):Geometry  Returns the Nth geometry in this Geometry Collection. PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 75 ogc_header_top_left POINT  A Point is a 0-dimensional geometric object and represents a single location in coordinate space. A Point has:  an x-coordinate value;  a y-coordinate value.  The boundary of a Point is the empty set.  Methods  X( ):Double  The x-coordinate value for this Point.  Y( ):Double  The y-coordinate value for this Point.  Multipoint  A MultiPoint is a 0-dimensional Geometry Collection. The elements of a MultiPoint are restricted to Points.  The Points are not connected or ordered.  A MultiPoint is simple if no two Points in the MultiPoint are equal (have identical coordinate values). PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 76 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 29 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM CURVE ogc_header_top_left  A Curve is a 1-dim geometric object usually stored as a sequence of Points, with the subtype of Curve specifying the form of the interpolation between Points.  One subclass of Curve is LineString, which uses linear interpolation between Points.  A Curve is simple if it does not pass through the same Point twice.  A Curve is closed if its start Point is equal to its end Point.  A Curve that is simple and closed is a Ring.  The boundary of a closed Curve is empty.  The boundary of a non-closed Curve consists of its two end Points.  A Curve is defined as topologically closed.  Methods  Length( ):Double  The length of this Curve in its associated spatial reference.  StartPoint( ):Point  The start Point of this Curve.  EndPoint( ):Point  The end Point of this Curve.  IsClosed( ):Integer  Returns 1 (TRUE) if this Curve is closed [StartPoint ( ) = EndPoint ( )].  IsRing( ):Integer Returns  G VELLA PROF. JOSEPH 1 (TRUE) - SPATIAL if thisAND MODELLING Curve is closed SPATIALLY [StartPoint ENABLED DBMS ( ) = EndPoint ( )] and this Curve is simple (does not pass through the same Point more than once). 77 LINESTRING, LINE, LINEARRING ogc_header_top_left  A LineString is a Curve with linear interpolation between Points. Each consecutive pair of Points defines a Line segment.  A Line is a LineString with exactly 2 Points.  A LinearRing is a LineString that is both closed and simple.  Methods  NumPoints( ):Integer  The number of Points in this LineString.  PointN(N:Integer):Point  Returns the specified Point N in this LineString. ✓ Simple LineString (a), Non-simple LineString (b), Simple, closed LineString (a LinearRing) (c), Non-simple closed LineString (d) PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 78 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 30 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM ogc_header_top_left MULTICURVE & MULTILINESTRING  A MultiCurve is a 1-dimensional Geometry Collection whose elements are Curves.  MultiCurve is a non-instantiable class in this specification; it defines a set of methods for its subclasses and is included for reasons of extensibility.  Methods  IsClosed( ):Integer  Returns 1 (TRUE) if this MultiCurve is closed [StartPoint ( ) = EndPoint ( ) for each Curve in this MultiCurve].  Length( ):Double  The Length of this MultiCurve which is equal to the sum of the lengths of the element Curves.  MultiLineString is a MultiCurve whose elements are LineStrings. ✓ Simple MultiLineString (a), Non-simple MultiLineString with 2 elements (b), Non-simple, closed MultiLineString with 2 elements (c) PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 79 ogc_header_top_left SURFACE  A Surface is a 2-dim geometric object.  A simple Surface consists of a single “patch” that is associated with one “exterior boundary” and 0 or more “interior” boundaries.  Simple Surfaces in 3-dimensional space are isomorphic to planar Surfaces.  Polyhedral Surfaces are formed by “stitching” together simple Surfaces along their boundaries, polyhedral Surfaces in 3- dimensional space may not be planar as a whole.  The boundary of a simple Surface is the set of closed Curves corresponding to its “exterior” and “interior” boundaries.  The only instantiable subclass of Surface defined in this specification, Polygon, is a simple Surface that is planar.  Methods  Area( ):Double  The area of this Surface, as measured in the spatial reference system of this Surface.  Centroid( ):Point  The mathematical centroid for this Surface as a Point. The result is not guaranteed to be on this Surface.  PointOnSurface( ):Point  A Point guaranteed to be on this Surface. PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 80 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 31 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM CENTROID AND POINTONSURFACE EXAMPLES PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 81 POLYGON ogc_header_top_left  A Polygon is a planar Surface defined by 1 exterior boundary and 0 or more interior boundaries. Each interior boundary defines a hole in the Polygon.  Polygons are simple geometric objects. Examples of Polygons with 1 (a), 2 (b) and 3 (c) Rings, respectively  Methods  ExteriorRing( ):LineString  Returns the exteriorRing of this Polygon.  NumInteriorRing( ):Integer  Returns the number of interiorRings in this Polygon.  InteriorRingN(N:Integer):LineString  Returns the Nth interiorRing for this Polygon as a LineString. PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 82 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 32 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM MULTISURFACE ogc_header_top_left  A MultiSurface is a 2-dimensional Geometry Collection whose elements are Surfaces.  The interiors of any two Surfaces in a MultiSurface may not intersect.  The boundaries of any two elements in a MultiSurface may intersect, at most, at a finite number of Points.  MultiSurface is a non-instantiable class in this International Standard. It defines a set of methods for its subclasses and is included for reasons of extensibility.  The instantiable subclass of MultiSurface is MultiPolygon, corresponding to a collection of Polygons.  Methods  Area( ):Double  The area of this MultiSurface, as measured in the spatial reference system of this MultiSurface.  Centroid( ):Point  The mathematical centroid for this MultiSurface. The result is not guaranteed to be on this MultiSurface.  PointOnSurface( ):Point  A Point guaranteed to be on this MultiSurface.  MultiPolygon is a MultiSurface whose elements are Polygons. PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 83 PHYSICAL SPATIAL DATA DESIGN PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 84 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 33 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM SPATIAL INDEXES  A variety of methods exist when assigning “the blocks of a file on disk”:  Allocating blocks sequentially  Linked allocation where every block is linked via a pointer to the next block  Indexing PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 85 BASIC QUERY PROCESSING & OPTIMISATION  B+trees are great for 1 dim indexes. These are fast and well-behaved (in terms of operations required).  Not adequate for multi dim indexing (more than 1 dim!).  Spatial queries require multi dim indexes for many type of spatial queries.  Popular multi dim structure are:  R tree (and its derivatives);  Grid files;  Gist (popular with postGIS implementations).  To build a spatial index on a table with a geometry column, use the "CREATE INDEX" function as follows: CREATE INDEX [ indexname ] ON [tablename ] USING GIST ( [geometrycolumn ] );  Note  GiST indexes are assumed to be lossy. Lossy indexes uses a proxy object (in the spatial case, a bounding box) for building the index.  You have to "gather statistics" on your geometry tables.For PostgreSQL 8.0.x and greater, just run the VACUUM ANALYZE PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS command. 86 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 34 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM WHY ARE INDEXES USEFUL?  Created to be used when dealing with file operations in particular querying of records  Additional auxiliary access structures that are extremely useful when reducing the amount of time taken to retrieve specific records  Sequential Search vs Indexing  Indexes speed up data access they decrease the collection of objects which needs to be considered when dealing with query execution PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 88 INDEXES  Rather than indexing the entire data objects, spatial indexes usually index an approximation of the geometric object (mbb mentioned earlier).  Also indexing aligns with the filter and refinement technique mention in the query processing.  Spatial indexes are made up of a number of entries of the form: [mbb, oid]  The mbb is a reference to the minimum bounding box  The oid is a direct reference to the object’s identifier being stored PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 89 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 35 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM INDEXING ISSUES  The development of indexes, relies on 3 main assumptions : 1. The size of the data set is by far greater than the amount of space available in main memory 2. Accessing data from disks takes much longer than accessing data from memory 3. Data objects are assembled in pages which are used as the basic unit of transfer between main memory and the disk PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 90 PROPERTIES OF SPATIAL INDEXES 1. Time complexity  Point queries and range queries should be executed in sub linear time  Executing queries by means of indexes should take a lesser amount of time when compared to a sequential scan 2. Space complexity  The size of a spatial index must be equivalent to the size of the indexed set 3. Dynamicity PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 91 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 36 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM TYPES OF SPATIAL INDEXES  Many indexing structures have been developed, each of which having particular strong points in certain aspects and weak points in others  No index structure is ideal in every situation  When choosing the best index possible for a given query and data set, one has to keep in mind which particular attributes need to be indexed PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 92 R-TREE INDEX  R-Tree Structure  Proposed by Guttman in 1984  Tree based data structure, however it is physically stored as tables  R-Trees is used for organising and searching for spatial objects  The objects found in the index are referred to as nodes or index entries  Originated from B-trees generated with the main purpose being that of indexing multidimensional information  Minimum bounding boxes PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 93 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 37 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM R-TREE INDEX (CONTINUED) PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 94 R-TREE INDEX (CONTINUED)  Properties of R-Trees  Each node except for the root node should obey the maximum and minimum limits (m and M). It can be calculated as the disk page size per entry size  Provided that the root node is not a leaf, it should have a minimum of two child nodes. Every leaf node should appear at the same level as all of the other leaf nodes  Each record found in leaf nodes is of the form (I, tuple-identifier) PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 95 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 38 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM R-TREE INDEX (CONTINUED)  Every record located in any other node is of the form (I, child-pointer)  An R-tree structure which has a depth d would index a minimum amount of objects equivalent to 𝑚𝑑+1 and a maximum amount of objects equal to𝑀𝑑+1  Leaf nodes are made up of the rectangle which holds the MBR of the actual objects found in it and an entry for each spatial (i.e. its MBR and oid), whilst the internal nodes are made up of a number of entries (Ptr, R) PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 96 R-TREE INDEX (CONTINUED)  Searching in R-Trees  Every internal node which has a MBR, overlapping the object being searched for by the user, is visited throughout the search operation  Provided that a node is a leaf node, then the result would be simply the object found in that node  If the node is a non-leaf node, all of the child nodes are recursively searched in order to identify which child node contains the object being searched for PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 97 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 39 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM R-TREE INDEX (CONTINUED)  The worst case performance of an R- Tree is thus 𝑂(𝑁), as opposed to 𝑂(𝑙𝑜𝑔 𝑁), which is the performance of a B-Tree  the minimum bounding rectangles should have as little overlap as possible, to try to decrease the search time as much as possible PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 98 R-TREE INDEX (CONTINUED)  Deletion in R-Trees  When deleting an object, there might be a node underflow. This situation could require a total reorganisation of the tree  Nodes might than be spread out on multiple sibling nodes PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 99 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 40 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM R-TREE INDEX (CONTINUED)  Updating in R-Trees  Once an update takes place on one of the objects which is being indexed, it might happen that its bounding box would have been altered  The index then needs to be updated by deleting the old object from the tree and re-inserting it according to the new position  R-Trees need 𝑂(𝑁/𝐵) disk blocks and insertion operations are completed in 𝑂 log 𝐵𝑁 Input/Outputs  The height of an R-Tree is equivalent to 𝑂(𝑙𝑜𝑔𝐵𝑁) PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 100 R-TREE INDEX (CONTINUED)  Extensions of the R-tree exist which have not yet gained as much ground as the original R-Tree implementation  Examples include; 1. R*-Tree (inserts may be *re-started* … ie higher construction/update cost – gives slightly better performance) 2. R+ -Tree (Nodes are not guaranteed to be at least half filled,The entries of any internal node do not overlap) 3. Priority R-Tree (favours bulk uploads through an indexing supplementary structure) PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 101 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 41 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM R-TREE INDEX (CONTINUED)  Node Splitting in R-Trees  3 main types of algorithms which can be used in node splitting 1. Exhaustive algorithm – simplest and most optimum but slowest 2. Quadratic cost algorithm 3. Linear-cost algorithm PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 102 IMPLEMENTATION OF R-TREE INDEXES IN POSTGRESQL  R-Tree index operates on top of the GiST structure  QuadTree is implemented in PostgreSQL on top of the SP-GiST structure  Generalized Search Tree (GiST) is a balanced, tree-structured access method which serves as a plug-in on which different indexes might be implemented  Default indexes which are built on top of the GiST indexes structure include the B-tree and R-tree indexes structure PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 103 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 42 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM IMPLEMENTATION OF R-TREE INDEXES IN POSTGRESQL (CONTINUED)  Other indexing schemes might be implemented on top of GiST  SP-GiST is an abbreviation for space-partitioned GiST  SP-GiST supports partitioned search trees, which facilitate development of a wide range of different non-balanced data structures, such as quad-trees, k-d trees, and suffix trees (tries)  The common feature of these structures is that they repeatedly divide the search space into partitions that need not be of equal size. PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 104 PARTIAL INDEXES  Created on a subset of a relation tuples, specified via a conditional expression, referred to as the “predicate”  Comprised solely of tuples which fulfil the predicate condition PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 105 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 43 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM EXPRESSION INDEXES  Expression or functional indexes  The entry which is being indexed is a function or scalar expression calculated from a column in the table PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 106 MULTI-COLUMN INDEX  The creation of a single index on more than one column  Even though, the index would be made up of more than one attribute, queries making use of only a subset of the columns might still make use of the index PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 107 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 44 Prof. Joseph Vella ©, Dept of Computer Information Systems, FICT, UM QUESTIONS? AND THANKS FOR ATTENDING! PROF. JOSEPH G VELLA - SPATIAL MODELLING AND SPATIALLY ENABLED DBMS 108 UM– 2024 – Spatial Data Modelling and Spatially enabled DBMS 45