... Language¹

This is an incomplete draft reporting work in progress.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... (SQL).²

See, e.g., [12] for an excellent, easily accessible tutorial.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... monoids.³

We call these monoids ``primitive'' following the presentation of Fegaras and Maier [9] as it adheres to a more operational (as opposed to mathematical) approach more suitable to computer-scientists. Mathematically, however, these should be called ``semantic'' monoids since they are interpreted by the computation semantics of their operations.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... algebra.⁴

For a fixed set of base elements and operations (which constitute what is formally called a signature), the syntactic algebra is unique (up to isomorphism). This algebra is also called the free, or the initial, algebra for its signature.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... structures.⁵

Note that this ambiguity never arises for semantic algebras whose operations are interpreted into a unique result.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... commutativity.⁶

Such are important considerations in the field of term rewriting [8], where the problem of finding canonical term representations for equational theories was originally addressed by Donald Knuth and Peter Bendix in a seminal paper proposing a general effective method--the so-called Knuth-Bendix Completion Algorithm [13]. The problem, incidentally, is only semi-decidable. In other words, the Knuth-Bendix algorithm may diverge, although several interesting variations have been proposed for a wide extent of practical uses (see [8] for a good introduction and bibliography).

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... ``curryed.''⁷

Recall that a curryed form of an $n$-ary function $f$ is obtained when $f$ is applied to less arguments than it expects; i.e., $f(t_1,\ldots,t_{k})$, for $1\leq k < n$. In the $\lambda$-calculus, this form is simply interpreted as the abstraction $\lambda x_1.\ldots\lambda x_{n-k}.f(t_1,\ldots,t_{k},x_1,\ldots,x_{n-k})$. In their fully curried form, all $n$-ary functions can be seen as unary functions; indeed, with this interpretation of curried forms, it is clear that $f(t_1,\ldots,t_n) = (\ldots(f\;t_1) \ldots t_{n-1})\;t_n$.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... online⁸

http://www.acm.org/sigs/sigmod/record/issues/9403/Comprehension.ps

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... online⁹

http://www.cs.washington.edu/homes/echris/papers/apl99.ps

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... online¹⁰

ftp://ftp.cs.washington.edu/tr/1998/11/UW-CSE-98-11-01.PS.Z

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... online¹¹

http://www-sal.cs.uiuc.edu/~nachum/papers/taste-fixed.ps.gz

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... online¹²

http://lambda.uta.edu/tods00.ps.gz

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... online¹³

ftp://ftp.informatik.uni-konstanz.de/pub/dbis/Publications/HS:BTW91.ps.gz

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... online¹⁴

http://w3.one.net/~jhoffman/sqltut.htm

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... online¹⁵

http://www.cs.toronto.edu/~libkin/papers/sigmod96a.ps.gz

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... online¹⁶

file:/nfs/opl/matisse/dev/opl_syntax_critic.html

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... online¹⁷

ftp://ftp.cs.wisc.edu/pub/tech-reports/reports/1993/tr1161.ps.Z

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... online¹⁸

ftp://ftp.cis.upenn.edu/pub/ircs/tr/94-09.ps.Z

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.