5. Query Transformations

Early on in the design of A$\lambda$goVista we realized that there is often a representational gap between a user's query and the checklet that is designed to match this query. For example, there are any number of reasonable ways for a user to express the topological sorting query in Figure 1(c), including representing the input graph as a list of edges, an adjacency matrix, or a list of neighbors. These queries are shown in Figure 6(b) -. The corresponding topological sorting checklet, on the other hand, might expect the input graph only in a matrix form.

This gap between query and checklet representation is probably the most contentious part of A$\lambda$goVista, and solving this problem is a major key to the success of the search engine. We have considered two ways of attacking the problem:

1.

The first solution is the kitchen-sink approach to query language design that was alluded to in the previous section. The idea is to provide special syntax for every conceivable literal data structure, including graphs, trees, lists, polygons, points, line segments, planes, sets, bags, etc. The advantage of this approach is that the query language syntax will guide both checklets and queries to use the same representation. The disadvantages are (a) that it is difficult to know when the query language is complete, and (b) that the query language becomes large and difficult to learn.

2.

The second approach is to provide a set of query transformations that will automatically mutate queries between common representations. For example, given the topological sorting query in Figure 6(b) , A$\lambda$goVista would automatically produce the queries in Figure 6(b) -, all of which would be matched against the checklets in the checklet coop.

The current implementation of A$\lambda$goVista uses the second approach. Figures 8 and 9 lists the transformations currently in use by the search engine.

  

Figure: Query transformations (A). $\emptyset$ represents Null. Greek letters are type variables. Examples are in the format signature: query.

  

Figure 9: Query transformations (B).

Transformation (Float2IntFloor) in Figure 8 transforms a float to an integer by truncation. Transformation  swaps the elements of a pair. Transformation  converts a vector to a set, provided the elements of the vector are unique. Transformations  through  are concerned with transforming a pair of vectors to various linked structures.

 

Figure 10 gives an elaborate query transformation example. A user query

$\ulcorner\hspace*{-2pt}$ [a->/5b,b->/9c] $\hspace*{-2pt}\urcorner$

is first transformed (using the Vector2VectorPair transformation) to

$\ulcorner\hspace*{-2pt}$ ([a,b,c],[a->/5b,b->/9c]) $\hspace*{-2pt}\urcorner$

by adding the list of nodes left out by the user. Through a series of analyses it is eventually determined that the query represents a linked list

$\ulcorner\hspace*{-2pt}$ List($\emptyset$,Int):([a,b,c],[a->/5b,b->/9c]) $\hspace*{-2pt}\urcorner$,

which could also be represented by the vector

$\ulcorner\hspace*{-2pt}$ Vector(Int):[5,9] $\hspace*{-2pt}\urcorner$.

Since the vector is of size two, it could also represent a pair. The elements of this pair, finally, can be swapped and converted from integers to floats. The A$\lambda$goVista search engine would hand off any or all intermediate results of this string of transformations to checklets that have the appropriate signature.