Note: these pages are no longer maintained

Never the less, much of the information is still relevant.
Beware, however, that some of the command syntax is from older versions, and thus may no longer work as expected.
Also: external links, from external sources, inside these pages may no longer function.

	Recipe #12 Neighbours
2011 January 28

Previous Slide

Table of Contents

Next Slide

The problem

Obviously each Local Council shares a common boundary with a neighbour:
[not an absolute rule, anyway: e.g. small islands are self-contained].
We'll use Spatial SQL to identify every adjacent couple of Local Councils.
Just to add some further complexity, we'll specifically focus our attention on the Tuscany region boundaries.

Tuscan Local Council	Tuscan County	Neighbour LC	County	Region
ANGHIARI	AREZZO	CITERNA	PERUGIA	UMBRIA
AREZZO	AREZZO	MONTE SANTA MARIA TIBERINA	PERUGIA	UMBRIA
BIBBIENA	AREZZO	BAGNO DI ROMAGNA	FORLI' - CESENA	EMILIA-ROMAGNA
CHIUSI DELLA VERNA	AREZZO	BAGNO DI ROMAGNA	FORLI' - CESENA	EMILIA-ROMAGNA
CHIUSI DELLA VERNA	AREZZO	VERGHERETO	FORLI' - CESENA	EMILIA-ROMAGNA
...	...	...	...	...

SELECT lc1.lc_name AS "Local Council",
lc2.lc_name AS "Neighbour"
FROM local_councils AS lc1,
local_councils AS lc2
WHERE ST_Touches(lc1.geometry, lc2.geometry);

This first query is really simple:

the ST_Touches(geom1, geom2) function is used to evaluates the spatial relationship existing between couples of Local Councils.
the local_council table is scanned twice, so to implement a JOIN;
in other words this simply allows to evaluate each Local Council against any other, in a combinatory/permutative fashion.
obviously this may cause ambiguity.
We have to set an appropriate alias name (AS lc1 / AS lc2) so to uniquely identify each one of the two table instances.

Anyway, a so simplistic approach implies several (strong, severe) issues:

this query surely will return the correct answer: but the process time will be very long.
[actually, so long to be absolutely not usable for any practical purpose].
explaining all this is really easy: evaluating ST_Touches() implies lots of complex calculations, so this one is a really heavy (and lengthy) step.
following a pure combinatorial logic creates many million couples requiring to be evaluated.
conclusion: iterating many million times a lengthy operation is a sure recipe for disaster.

SELECT lc1.lc_name AS "Local Council",
  lc2.lc_name AS "Neighour"
FROM local_councils AS lc1,
  local_councils AS lc2
WHERE lc2.ROWID IN (
  SELECT pkid
    FROM idx_local_councils_geometry
    WHERE pkid MATCH RTreeIntersects(
      MbrMinX(lc1.geometry),
      MbrMinY(lc1.geometry),
      MbrMaxX(lc1.geometry),
      MbrMaxY(lc1.geometry)));

Happily enough, we can perform such Spatial queries in a really fast and efficient way:

we have to use a Spatial Index [aka R*Tree]
this will add some further complexity to the SQL statement, but will achieve a ludicrous speed enhancement.
how it works: the R*Tree is checked first, so to evaluate Minimum Bounding Rectangles [MBRs] of both Geometries.
- This one is a very quick step to be evaluated, and allows discarding lots of couples that surely cannot share a common boundary.
- So the number of times ST_Touches() will then be actually called will be dramatically reduced.
- And all this strongly reduces the overall processing time.
At SQL syntax level using the Spatial Index simply requires to implement a sub-query:
- the R*Tree Spatial Index in SQLite actually is a separate table.
- table names are strictly related: the Spatial Index corresponding to table myTbl and geometry column myGeom always is expected to be named as idx_myTbl_myGeom.
- the MATCH RTreeIntersects() clause is used to quickly retrieve any interesting Geometry simply evaluating its own MBR.
- MbrMinX() and alike are used to identify the extreme points of the filtering MBR.

Just to explain better what's going on, you can imagine that this SQL query is processed using the following steps:

a Geometry is picked up from the first local_councils instance: lc1.geometry
then the R*Tree Spatial Index is scanned, so to identify any other Geometry from the second local_councils instance: lc2.geometry
Only Geometries satisfying an intersecting MBR constraint will be fetched via Spatial Index.
and finally ST_Touches() will be evaluated: but this will affect only a very limited few carefully pre-filtered Geometries.

SELECT lc1.lc_name AS "Tuscan Local Council",
  c1.county_name AS "Tuscan County",
  lc2.lc_name AS "Neighbour LC",
  c2.county_name AS County,
  r2.region_name AS Region
FROM local_councils AS lc1,
  local_councils AS lc2,
  counties AS c1,
  counties AS c2,
  regions AS r1,
  regions AS r2
WHERE c1.county_id = lc1.county_id
  AND c2.county_id = lc2.county_id
  AND r1.region_id = c1.region_id
  AND r2.region_id = c2.region_id
  AND r1.region_name LIKE 'toscana'
  AND r1.region_id <> r2.region_id
  AND ST_Touches(lc1.geometry, lc2.geometry)
  AND lc2.ROWID IN (
    SELECT pkid
      FROM idx_local_councils_geometry
      WHERE pkid MATCH RTreeIntersects(
        MbrMinX(lc1.geometry),
        MbrMinY(lc1.geometry),
        MbrMaxX(lc1.geometry),
        MbrMaxY(lc1.geometry)))
ORDER BY c1.county_name, lc1.lc_name;

All right, once we have resolved the Spatial Index stuff writing the whole SQL query isn't so difficult.
Anyway this one is a rather complex query, so some further explanation is surely welcome:

we have to resolve JOIN relations connecting local_councils to counties, and counties to regions
anyway we used two different instances for local_councils, so we need to resolve JOIN relations separately for each one instance.
setting the r1.region_name LIKE 'toscana' clause only Tuscan Local Councils will be evaluated for the homeland side.
and setting the r1.region_id <> r2.region_id clause ensures that only not-Tuscan Local Councils will be evaluated for the foreigner side.
only Tuscan Local Councils sharing a common boundary with not-Tuscan Local Councils will be extracted by this query.

SELECT lc1.lc_name AS "Tuscan Local Council",
  c1.county_name AS "Tuscan County",
  lc2.lc_name AS "Neighbour LC",
  c2.county_name AS County,
  r2.region_name AS Region
FROM local_councils AS lc1,
  local_councils AS lc2
JOIN counties AS c1
  ON (c1.county_id = lc1.county_id)
JOIN counties AS c2
  ON (c2.county_id = lc2.county_id)
JOIN regions AS r1
  ON (r1.region_id = c1.region_id)
JOIN regions AS r2
  ON (r2.region_id = c2.region_id)
WHERE r1.region_name LIKE 'toscana'
  AND r1.region_id <> r2.region_id
  AND ST_Touches(lc1.geometry, lc2.geometry)
  AND lc2.ROWID IN (
    SELECT pkid
      FROM idx_local_councils_geometry
      WHERE pkid MATCH RTreeIntersects(
        MbrMinX(lc1.geometry),
        MbrMinY(lc1.geometry),
        MbrMaxX(lc1.geometry),
        MbrMaxY(lc1.geometry)))
ORDER BY c1.county_name, lc1.lc_name;

Obviously you can this query adopting the alternative syntax for JOINs: the difference simply is syntactic.
And doesn't implies any difference at functional or performance levels.

Performing sophisticated Spatial Analysis not necessarily is an easy and plain task.
Mastering complex SQL queries is a little bit difficult (but not at all impossible).
Optimizing such complex SQL, so to get fast answers surely requires some extra-care and attention.

But Spatial SQL supports you in the most effective (and flexible) way: the results you can get simply are fantastic.
After all the game surely is worth the candle.

Previous Slide

Table of Contents

Next Slide

	Author: Alessandro Furieri a.furieri@lqt.it
	This work is licensed under the Attribution-ShareAlike 3.0 Unported (CC BY-SA 3.0) license.

	Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.3 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.