invertAll

Relational functions invertAll

The invertAll function creates an inverted relation with linked list navigation for one-to-many relationships.

syntax

invertAll(relation: A->B) -> container with:
    - attribute<A> (B): first element of A that maps to each B
    - attribute<A> Next (A): next element of A with same B value

definition

Creates a linked list structure that enables efficient iteration over all elements in domain A that map to each element in domain B.

For a relation A→B, invertAll produces:

1. Result attribute (B→A): For each B, the first A that maps to it
2. Next attribute (A→A): For each A, the next A with the same B value (or undefined if last)

This is more memory-efficient than invert when many A elements map to the same B, as it avoids creating a separate domain for all (B,A) pairs.

arguments

argument	description	type
relation	The relation to invert	A->B

result

A container with two attributes:

• Main result: B→A (first element)
• Next subitem: A→A (linked list navigation)

To iterate over all A elements for a given B:

1. Start with the result value for B
2. Follow Next links until undefined

performance

Time complexity: O(n) where n = cardinality of A

Space complexity: O(n) for the Next array, plus O(m) for the result where m = cardinality of B

More efficient than invert when the relation has high fan-out (many A per B), as invert would create a large intermediate domain.

conditions

• The values unit of the relation must be a domain unit
• Domain A must be ordinal and zero-based

example

unit<uint32> Person: nrofrows = 5;
unit<uint32> Household: nrofrows = 3;

attribute<Household> household_rel (Person) := union_data(Person, 0, 0, 1, 2, 1);
// Person 0,1 -> Household 0; Person 2,4 -> Household 1; Person 3 -> Household 2

container inv := invertAll(household_rel);
// inv (Household) = {0, 2, 3}  -- first person per household
// inv/Next (Person) = {1, null, 4, null, null}  -- next person in same household

// Iteration: Household 0 -> Person 0 -> Person 1 -> (null)
//            Household 1 -> Person 2 -> Person 4 -> (null)
//            Household 2 -> Person 3 -> (null)

see also

• invert - simple inversion without linked list
• rlookup - reverse lookup
• Relational functions

since version

5.0