6.2.2. A mechanism for inverting a query
Queries are stored in a model file in the form of a description (See module Perspectives.Query.QueryTypes). Such a description holds the domain and range of the query function, and a description of the actual computation. It turns out that we can turn this description inside out, as it were, ending up with a description of an inverted query.
Consider the straightforward case of a query that is just a composition of simple steps – a path. The inverse query is just the inversion of each individual step, run in inverse order (starting with the last step first). But can we invert each simple step? Yes we can (Except for roles computed by external functions that have no inversion). Remember that with a query we traverse the network that consists of contexts and roles, connected through fills relations. The simple steps are:
-
Move from a role to its context;
-
Move from a context to some role;
-
Move from a role to its filler;
-
Move from a role to its filled role.
Each role has a single context and a single filler (this is not so in the generalised version of Perspectives where a role can have multiple fillers). However, contexts can have many roles and roles can be fill many other roles. So the inverse function of role-instance-to-context-instance must be a function that is informed with the type of the role instance. The same holds for the inverse function of role-instance-to-filler.
But this information is available in the query function description, so we can draw up a description of the inversion of each simple step.
A word on cardinality. If the original query moves from a context to the instances of a particular role, the path ‘fans out’ over multiple instances. However, the inverse path will come from a single instance. In contrast, if the original query moves from a role instance to a context, the inverse query will fan out. This is not a problem, because queries have sequences of values as result. So queries are particular functions, with multiple results.
Besides simple composition of steps, we have (very few) functions that combine simple paths through the context-role network, filter being the most prominent example. In a filter operation, the results of one path are filtered by the outcome of the result of another path.