6.2.4. Implementation complication: two types of trees
Module Perspectives.Query.Inversion holds the code that actually inverts a query function description. This code deals with a complication. In this document, we’ve imagined query execution to trace a path through the graph of instances of contexts and roles, fanning out from a single automatic user context to many source contexts. Why the branching? Because of two reasons:
-
a context may have many instances of a role type;
-
a role may be fill many other roles.
In other words, the path traced by executing a query stands out as a tree selected from the underlying graph of context- and role instances.
However, the way back from a source context (a path endpoint) is always a straight path without branches to the automatic user context (the path starting point).
Confusingly, the description of a query itself can have a tree-shape. This is a tree selected from the graph of types of contexts and roles. Why the branching? Because we have several operators on two arguments, for example:
-
filter
-
join
(Composition is an operator on two arguments, too, but we use it to construct a single path through the graph of types).
Being a tree, its inverse is, again, a collection of paths. This time, however, these are paths through the underlying graph of types of contexts and roles.