Join_equal_values - ObjectVision/GeoDMS GitHub Wiki

Relational functions join_equal_values

• join_equal_values(AtoX_rel, BtoX_rel)

join_equal_values(AtoX_rel, BtoX_rel) results in a uint32 domain unit that represents each combination of AtoX_rel and BtoX_rel that relate to the same X. The function results in three subitems being attributes of this domain:

• first_rel (FKA nr_1_rel): the index numbers of each row in A that participates in a combination of rows that have the same X-values as rows in B.
• second_rel (FKA nr_2_rel): the index numbers of each row in B that participates in a combination of rows that have the same X-values as rows in A.
• X_rel (FKA nr_X_rel): the equal value in the combination

The result rows are ordered by ascending X value, then by row number in A, then by row number in B.

The explicit join_equal_values_uint64, join_equal_values_uint32, join_equal_values_uint16 and join_equal_values_uint8 functions can be used in the same manner as the join_equal_values function, to create a new domain unit with an explicit value type.

• AtoX_rel: an attribute with an integer value type, usually a relation to a domain unit X
• BtoX_rel: an attribute with the same values unit as AtoX_rel

1. The values unit of the arguments: AtoX_rel and BtoX_rel must match.
2. The domain unit of arguments: AtoX_rel and BtoX_rel must be zero based.
3. Rows with an undefined X, or with an X outside the range of the values unit, do not participate in any combination.

X itself does not have to be a domain unit: a plain uint32 attribute joins just as well as a relation. Since GeoDMS 20.13.0 the values unit of X no longer needs to have a limited range, nor to be ordinal and zero based; see implementation below.

The function counts, per candidate common value, how often it occurs in A and in B; the number of result rows for that value is the product of the two counts. How the candidate values are addressed depends on the values unit X, with n and m the number of rows of the A and B domain:

• when X is ordinal, zero based and its range holds no more values than n + m, one slot per value in the range of X is used, addressed directly;
• otherwise an index of the distinct X values that actually occur in AtoX_rel is built and searched. A value that occurs in B only cannot produce a result row, so this index never holds more than n entries, however large the range of X is.

Both variants produce the same result, in the same row order. Earlier versions always used the first variant, which made a join on an attribute typed by its value type rather than by a domain unit allocate one slot per representable value: joining three rows on three rows over a uint32 values unit reserved tens of gigabytes (GeoDMS issue #1175).

O(n + m + r), respectively O(n log n + m log n + r) for the indexed variant, where n = size of the A domain, m = size of the B domain and r = number of result rows. Memory is proportional to the number of candidate values — the range of X for the direct variant, the number of distinct occurring values for the indexed one — plus the result itself. Note that r is the sum of the per-value products, so it grows quadratically when many A and B rows share the same X value.

• join_equal_values_uint8_16_32_64
• https://en.wikipedia.org/wiki/Pullback_(category_theory)
• https://www.w3schools.com/sql/sql_join_inner.asp

unit<uint32> RegionCity := join_equal_values(region/country_rel, city/country_rel);

domain CityRegionCombinations , nr of rows = 5

domain region, nr of rows = 5

domain city, nr of rows = 3