2. The Query Signature Graph

Figure 12 is a graphical representation of the functions that would be generated for the checklets and transformations in our running example. The nodes depict the signature-bound functions and the edges show transformations from one signature to another. The shaded nodes are those nodes that have associated checklets.

To construct this query signature graph we start with those signatures accepted by checklets--they are trivially acceptable. Then, for all of those signatures, we apply the inverted transformations wherever possible. I.e., at each step of this process we determine those signatures that are one transformation away from the given acceptable signature. By repeatedly applying these inverted transformations, all acceptable query transformations can be discovered and the graph can be constructed.

 

There is, however, one unfortunate complication to this architecture. With a sufficiently rich set of transformations, it is possible to generate an infinite number of signatures:

To avoid this problem, and to bound the number of signatures, we put a limit on the number of transformations that will be applied to any query. This limit is currently set to four. This would seem to limit the usefulness of A$\lambda$goVista, but in practice this is not so. First of all, the exhaustive search algorithm from Section 3 is still available to those users who are willing to trade a somewhat longer response-time for a more complete response. Secondly, very deep chains of transformations will often mutate a query beyond recognition, resulting in spurious query results that have little meaning to the user.

With our current database of 95 checklets, with 28 unique signatures, and 23 transformations, A$\lambda$goVista can accept queries with 9828 different signatures.

The generation of the decision tree and all of the signature-specific functions is done automatically by a small Icon program [12].