Algebraic Operations on Whole Maps

on Whole Maps PathMap supports efficient operations to modify maps or construct new maps, using existing maps as operands. From these primitive operations, it is possible to construct and evaluate complex queries over data represented in a PathMap. For a real-world example, see the [Aunt Knowledge Graph]((GOAT, fix this link)) example section.

These operations, along with the rules and theorems that apply to them, are referred to as the "path algebra".

Join (Union)

join creates the union of multiple tries, so a path present in any operand will be present in the result.

Example

operand_0:

books:don_quixote
books:great_gatsby,the
movies:casablanca

operand_1:

books:moby_dick
movies:star_wars
music:take_the_a_train

result:

books:don_quixote
books:great_gatsby,the
books:moby_dick
movies:casablanca
movies:star_wars
music:take_the_a_train

Meet (Intersection)

meet intersects multiple tries, so a path present in all operands will be present in the result

Example

operand_0:

books:great_gatsby,the
books:moby_dick
movies:casablanca
music:take_the_a_train

operand_1:

books:don_quixote
books:great_gatsby,the
movies:casablanca
movies:star_wars

result:

books:great_gatsby,the
movies:casablanca

Subtract

subtract removes all paths in one trie from another, so a path present in the lvalue trie that is not present in the rvalue trie will be present in the result. Conceptually, subtract acts like a meet between the lvalue and the inverse of the rvalue - although currently there is no inverse operation for PathMap.

Example

lvalue:

books:don_quixote
books:great_gatsby,the
books:moby_dick
movies:casablanca
movies:star_wars
music:take_the_a_train

rvalue:

books:don_quixote
books:moby_dick
movies:star_wars

result:

books:great_gatsby,the
movies:casablanca
music:take_the_a_train

Restrict

restrict removes paths from one trie that do not have a corresponding prefix in another trie. You can conceptualize restrict as a generalization of meet, where every path in the rvalue ends in a "wildcard".

Example

lvalue:

books:fiction:don_quixote
books:fiction:great_gatsby,the
books:fiction:moby_dick
books:non-fiction:brief_history_of_time
movies:classic:casablanca
movies:sci-fi:star_wars
music:take_the_a_train

rvalue:

books:fiction:
movies:sci-fi:

result:

books:fiction:don_quixote
books:fiction:great_gatsby,the
books:fiction:moby_dick
movies:sci-fi:star_wars

Join K Path, aka Drop Head

join_k_path_into collapses n bytes from all paths, joining together the sub-tries as it proceeds.

Example

lvalue:

books:don_quixote
books:great_gatsby,the
books:moby_dick

result of join_k_path(6) (dropping the first 6 chars: books:):

don_quixote
great_gatsby,the
moby_dick