Spatial joins and allocation

Matching the rows of one domain unit to the rows of another — which customer buys at which shop, which dwelling stands near which wind turbine, which land unit gets which land use — is what a JOIN does in SQL. The GeoDMS spreads that job over a family of functions, because in spatial work the matching condition is more often computed from geometry than read from a key, and because the match itself is often the outcome of a model rather than a recorded fact. This page connects those functions, from the join on a given key to the allocation under competing claims, and says where the analogy with a database stops holding.

For the relational model itself and how its tables map onto domain units, see Relational model versus Semantic arrays.

two result shapes

An INNER JOIN yields one row per matching pair and nothing for the rows without a match. A LEFT JOIN keeps every row of the left table, with nulls where nothing matched, and a LEFT JOIN … GROUP BY the left key reduces the matches of each left row to one aggregate. In the GeoDMS a table is a domain unit and a foreign key is a relation: an attribute whose values unit is the other domain unit. That gives the two shapes every function on this page produces:

• a pair domain, the inner join: a new domain unit with one row per matching pair and two relations, one towards each argument, plus whatever measures the pair — a distance, an intersection geometry, a route impedance. The number of matches is not known beforehand, so the result has to be a new domain, and its size is data: it can reach the product of the two argument sizes.
• a relation of the left domain, the aggregated left join: an attribute of the existing left domain unit, null where nothing matched. The function has already chosen one match per row — the nearest, the containing polygon, the reachable destination — so no pair is ever materialised.

The first converts into the second with aggregation functions over one of the pair relations: min of the distance per left row, pcount for the number of matches, min_index for the pair that holds the nearest match, and a lookup through that pair for the right row itself; a left row without any pair gets null, as a left join should. The second cannot be converted back: a relation is a pair domain collapsed to at most one row per left entry, and the other candidates are gone. That is why the pair-producing functions exist beside their nearest-only siblings, and why the nearest-only siblings are cheaper.

joins on a given key

When the two sides share a key, the GeoDMS functions correspond to SQL one to one:

SQL	GeoDMS	result
A INNER JOIN B ON A.x = B.x	join_equal_values(A/x, B/x)	pair domain with first_rel, second_rel and the common value X_rel
A LEFT JOIN B ON A.key = B.key, B.key unique	rlookup(A/key, B/key)	relation A → B, null where B has no such key
SELECT B.v FROM A LEFT JOIN B …	rjoin(A/key, B/key, B/v), which is rlookup followed by lookup	attribute of A
… GROUP BY A.id with SUM, COUNT, MIN	sum, pcount, min over the relation	attribute of A, or of B over the other relation
A CROSS JOIN B WHERE cond	combine and a selection on the product	pair domain, after materialising all of A × B

The last row is the general fallback and the one to avoid for anything but small sets: the Spatial join example sums population within 120 km that way, and its intermediate domain has #origins × #destinations rows. Everything below exists so that this product is never formed.

inner joins with a spatial pre-selection

Here the join condition is geometric — within a distance, inside, overlapping, reachable within a travel time — and each function evaluates it with a spatial index, so only the candidate pairs that can satisfy it are visited. All of them produce a pair domain with two relations and a measure of the pair. What each needs is a cutoff, and the cutoff is not a filter applied afterwards but what bounds the work and the result size: without one, "all pairs" is the Cartesian product again.

between	function	pair measure	cutoff
points and points	join_near_values(A/geometry, B/geometry, maxDist)	none; compute dist through first_rel and second_rel	maxDist, a distance
points and arcs or polygons	connect_matrix and dist_matrix, since GeoDMS 20.19.2	dist, and for connect_matrix the CutPoint on the feature	a squared distance per point and one per feature, both required; optionally the number of nearest points kept per feature
points inside polygons	point_in_all_polygons(points, polygons)	none; containment is the condition	none needed, containment bounds itself
polygons and polygons	geos_overlay_polygon(A/geometry, B/geometry)	the intersection geometry, hence its area	none; only overlapping pairs are found
origins and destinations over a network	impedance_matrix with od:impedance,OrgZone_rel,DstZone_rel	the impedance of the shortest route, optionally an alternative impedance and the link sequence	cut(OrgZone_max_imp) on the impedance, limit(OrgZone_max_mass,DstZone_mass) on the destination mass reached, euclid(maxSqrDist) on the straight-line distance; see Impedance options

The relations carry different names — first_rel and second_rel, arc_rel and point_rel, OrgZone_rel and DstZone_rel — but they are the same thing: a relation from the pair domain towards one argument. Which argument's rows get counted, summed or minimised over is decided by which relation the aggregation is given.

Two cutoff conventions coexist: join_near_values takes a distance, the connect family the square of one. Note also which side a cutoff belongs to. connect_matrix takes one per point and one per feature and a pair must satisfy both, which is what a norm distance that depends on the turbine (its tip height) combined with a limit that depends on the dwelling needs; impedance_matrix bounds the search per origin.

An example: the turbines within reach of each dwelling, then reduced to what a dwelling wants to know.

unit<uint32> dwelling2turbine := connect_matrix(
      turbine/geometry,  sqr(turbine/norm_distance)
    , dwelling/geometry, sqr(dwelling/max_distance)
    , 25)
{
    attribute<dwelling> arc_rel;
    attribute<turbine>  point_rel;
}

attribute<uint32>  nr_turbines     (dwelling) := pcount(dwelling2turbine/arc_rel);
attribute<float64> nearest_dist    (dwelling) := min(dwelling2turbine/dist, dwelling2turbine/arc_rel);
attribute<turbine> nearest_turbine (dwelling) := dwelling2turbine/point_rel[min_index(dwelling2turbine/dist, dwelling2turbine/arc_rel)];

The pair domain is the inner join; the three attributes are the left join grouped by dwelling. A dwelling with no turbine within reach has no pair, so it gets 0, null and null.

left joins, already aggregated

When only the nearest match per row is wanted, a function that decides it internally is cheaper than a pair domain followed by an aggregation, and is the only option where the pairs would not fit. Each of these results in one value per row of the left domain:

question	function	result
the nearest point of B for each point of A	connect(B/geometry, A/geometry), its first variant	relation A → B
the nearest other point in the same set	connect_neighbour	relation A → A
the nearest arc or polygon outline for each point, and where on it	connect_info, or dist_info for the distance alone	container, resp. attribute, of the points: arc_rel, dist, CutPoint
the nearest point for each arc	connect_info(points, arcs), the reversed order, since GeoDMS 20.19.2	container of the arcs: point_rel, dist
the polygon each point lies in	point_in_polygon, or point_in_ranked_polygon where polygons overlap	relation points → polygons, null outside all of them
the impedance to the nearest destination, over a network	[[impedance_table	impedance_table(...)]] with the destinations as start points
the nearest destination whose capacity admits the origin's weight	capacitated_connect	relation origins → destinations; the capacity is a condition per pair, like the key of connect_eq, not a budget the earlier origins use up
one land use type per land unit, under regional claims	[[discrete_alloc	Function-discrete-alloc]]

impedance_matrix belongs here too when its interaction(…) section is used without any od: product: the per-origin and per-destination sums $D_i$, $M_{ix}$, $C_j$, $M_{xj}$ and the link flows are then accumulated while each origin's tree is grown and no pair is stored, which is the GROUP BY without the join table. Impedance options describes the products; Impedance interaction potential how to get the pair-level $t_{ij}$ and $M_{ij}$ back when they are wanted.

the direction of a nearest join

A key join is symmetric in its pairs: A LEFT JOIN B and B LEFT JOIN A differ only in which unmatched rows are kept. A nearest join is not. The point nearest to an arc need not have that arc as its own nearest arc, so connect_info(arcs, points) and connect_info(points, arcs) produce different pair sets, and neither is the transpose of the other. In the connect family the first geometry argument is the choice set and the second is the table that keeps all its rows: connect(B, A) is a left join of A on B.

from a database to an allocation model

Take the schema every database course starts from: customers, products, and an order table between them with a customer key, a product key and a quantity. The order table is the join table, and it is recorded: the world decided who bought what, and the database only stores it and gives it back. A query joins customer to product through it, groups, sums, and never decides anything; integrity checks — does every order point at an existing customer? — are the only rule involved.

A spatial model has customers with a location and shops with a location, and no order table. The relation between them is what the model is asked to produce. It gets there in steps, and each step moves a little further from the database case:

1. A recorded relation. The pair table is data. join_equal_values and rlookup reproduce it from its keys, exactly as SQL does. Nothing on this page is needed yet.

2. A derived set of candidates. Which pairs are possible: within 500 m, inside the service area, reachable within 30 minutes. This is what the spatial pre-selection functions compute, and their pair domain is a candidate table: it says what could be, not what is. The cutoff that bounds it is a modelling assumption — the distance beyond which a customer is assumed not to shop — and it is the first thing that has no counterpart in the order table.

3. A chosen relation, by a rule. Each customer goes to the nearest shop; each point lies in one polygon; each origin uses its shortest route. connect, point_in_polygon and impedance_table decide by such a rule and produce a relation, with a null for the rows for which the rule finds nothing. The decision is still row by row: what one customer does has no effect on the others, and that is as far as a left join reaches. Service areas and catchments are these relations, aggregated. Location-allocation analysis — where to site the facilities so that the resulting assignment is best — evaluates candidate sitings by the assignment each of them induces: the assignment is computed by these functions, the search over sitings is a model built on top of them, not a function.

4. A distributed relation. No single shop is chosen; a customer's demand is spread over all shops within reach, more to the attractive ones and less to the far ones. The join table acquires a weight, $M_{ij}$, and a customer's row is split fractionally over many products, which no order table does. This is the spatial interaction model of the interaction(…) section of impedance_matrix, following Alonso's theory of movement, with the distance decay and the elasticity $α$ as its parameters, see Impedance options. The flows summed per destination are what a shop attracts; summed over the links that carry them, they are the traffic.

5. An allocated relation, under competition. Shops have a capacity, regions have claims, and now the choice for one row depends on all other rows: a customer takes the nearest shop only if the customers nearer to it have left room. This is a transportation problem, and discrete_alloc solves it: it finds a shadow price per claim such that allocating each land unit to its highest suitability plus shadow price meets every claim. The join table is now the solution of an optimisation, and it comes with prices — the shadow prices per claim and the bid price per land unit — that say how binding each constraint was. In database terms the order table has become an output; the inputs are preferences and constraints. greedy_alloc and needy_alloc serve the land units in a fixed order without prices, faster and not optimal. The interaction(…) section of impedance_matrix stops short of this step: it constrains the origin side only, so destinations with a hard capacity need a competition-corrected measure or the discrete allocation. And capacitated_connect, despite its name, does not belong here either: its capacity is a threshold each origin is tested against on its own, not a budget that gets used up, so its origins do not compete. See Discrete Allocation for the problem and Discrete Allocation Example for a configuration.

The steps compose. The candidate pairs of step 2 are what keep steps 3 to 5 tractable, since a shop out of reach need not be priced. The row-by-row rules of step 3 are the cheap approximation to use when competition is negligible, and the distributed and allocated relations of steps 4 and 5 are what to reach for when it is not: when the question is not where would each customer go but what happens to all of them at once.

see also

• Relational model versus Semantic arrays and Relational functions
• Network functions, Impedance functions and Allocation functions
• point-polygon operators
• the Accessibility Modelling wiki for the methods behind steps 3 and 4, and the Land Use Modelling wiki for step 5