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:

  1. a context may have many instances of a role type;

  2. 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:

  1. filter

  2. 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.