app/willard/README

   1 This program implements the query decomposition algorithm
   2 of Bob Paige and Deepak Goyal for a linear time fragment for Willard's
   3 relational calculus.
   4
   5 The algorithm is described in ``The Formal Reconstruction and Speedup
   6 of the Linear Time Fragment of Willard's Relational Calculus Subset'',
   7 Deepak Goyal and Bob Paige.  In IFIP TC2 Working Conf. Algorithmic Languages
   8 and Calculi, Feb 1997.
   9
  10 The program is called 'willard.'  It is quite primitive at this point:
  11 it simply takes a query from the standard input and splits out the immediate
  12 decompositions.  The files data* contain sample inputs.
  13
  14 The system is composed of the following files:
  15
  16 FILE               DESCRIPTION
  17 ---------------    -----------
  18 willard-ast.ph     The abstract syntax tree definition
  19 willard-ast.pcc    Pretty printer for the AST
  20 parser.pcc         The parser for the query language
  21 paige.ph           The base class of the query decomposer
  22 paige.pcc          The main algorithm used in the query decomposer
  23 paige-aux.pcc      Auxiliary routines
  24 rename.pcc         Transformation to rename duplicate variable names
  25 phase1.pcc         Transformation to simplify query and construct DNF
  26 phase2.pcc         Transformation to eliminate quantifiers
  27 phase3.pcc         Transformation to eliminate disjunctions
  28 phase4.pcc         Transformation to eliminate conjunctions
  29 phase5.pcc         Transformation to process simple find/count queries
  30 proj.pcc           Transformation to rewrite projections into existentials
  31 willard.pcc        Main program