Normalization Algorithm
=======================

The order function expects seven arguments:
-------------------------------------------
 
  T = the base table
  S = the suffix or ""
  O = symbol vector of ops (# = n)
  A = list of op dictionaries (# = n)
  B = initial column state (i.e. of the base table)
  C = available column after each op in O (# = n)
  M = visible column order after each op in O (# = n)
 
my test-bed for the algorithm consists of (T;S;O;A;B;C;M) structures for the 469 queries generated by the
mdb regression test.
 
The normalization algorithm consists of three main steps:
---------------------------------------------------------
 
0. If the query is a singleton, return it.
 
1. The initial step involves computing the variables which are used in the main steps of the algorithm:
 
  c = the available columns preceding each step in the query
  d = the visible columns preceding each step in the query
  e = all the columns involved in the query
  l = the visible columns following the final step in the query
  w = new columns which result from executing each op in the query (willbes and links)
 
  a = columns referenced by each step in the query
 
  f = a boolean marking the sticky ops in the query
  g = a boolean marking the cache-affecting ops in the query
 
2. The second step involves splitting the query into two sublists:
 
  q = the sublist of sticky and cache-affecting ops.
  r = the sublist of everything else.
 
Each sublist is then sorted under constraints, and merged to form a single list.
 
q is sorted based on a five-column matrix:
 
    <+(f;g;k;o;q)
 
  f[i]=1 iff q[i] is a cache-affecting op in q, then f=+\0>':f
  g[i]=1 iff q[i] is a sticky op in q, then g=+\(~=)':g
  k[i]=1 iff q[i] is a fixed op 
  o = dependency order of ops in q (i.e. q[i] depends on q[j] then j<i)
  q = query dictionaries
 
The function of the first two columns of the sort matrix (f and g) is to retain the "large scale" relative 
ordering of the sticky and cache-affecting ops.  Then within that frame we order queries lexicographically 
within dependency order.
 
r is sorted based on a three-column matrix:
 
    <+(k;o;r)
 
  k[i]=1 iff q[i] is a fixed op 
  o = dependency order of ops in r
  r = query dictionaries
 
We allow the non-sticky, non-cache-affecting ops to reorder lexicographically within dependency order.
 
3. In the final step we merge the two sublists and modify the result to guarantee semantic identity with 
the original query. 
 
We say that r[i] is inserted into the latest position in q such that all ops in q which depend on r[i] occur
later than r[i].  This has the effect of "sinking" ops on which nothing depends to the bottom of the q list.
 
Once the subqueries are merged, we inject colord ops into the list in order to preserve the original effect
of ops which rely on implicit column ordering.
 
We do this first by identifying those ops in the list which rely implicitly on the col-state which preceded
them in the original query.  That col-state is then used to construct the injected colord op.
 
We then append to the op list a colord op specifying exactly the final column-state of the original query.
 
Finally, we delete any duplicate colord ops which might have been created.