Propagators and relational algebra
Some thoughts on propagators… seemed like an a-ha moment when I wrote it about a month ago, but now that I reread, it seems sort of trivial… oh well, what are blogs for.
The Sussman/Radul propagator framework is described operationally, as a mechanism for manipulating constraint networks and doing constraint propagation, together with dependency-directed backtracking for diagnosing inconsistencies. I want to redescribe it as a mechanism implementing operations that can be described declaratively: to wit, relational algebra.
Relational algebra was invented to provide a clean theory of databases. According to relational algebra, a database is a set of tables, which are physical and mutable. Each table carries, at any given point in time, a relation, which is ideal and mathematical. When a table is updated, it goes from carrying one relation to carrying another (usually very similar) relation.
Relations in the broader mathematical sense are uniform, potentially infinite sets of tuples. (“Uniform” meaning the tuples all have the same arity, making the relation rectangular, i.e. a subset of a cross product.) In a relational DBMS the relations held by tables can be given by enumerating their tuples. But there is nothing in the theory of relational algebra that requires that relations be enumerable. Relational algebra still makes logical sense with infinite relations, e.g. the less-than relation.
Now the deep piece of relational algebra is relational compositions or joins. Join is a binary operation on relations that yields a relation. The key fact about the join operator is that it’s associative. The most interesting and performance-critical part of any DBMS is the implementation of joins – specifically (a) in what order to perform joins when there’s more than one, (b) for each join, the details of performing that particular join (e.g. enumeration over the left table vs. over the right table). The heart of any DBMS is its query planner, which is the often very hairy compiler-like code that makes these strategic decisions.
So you should see the analogy to propagators. At any given time, every propagator network, including individual propagators and cells as special cases, has an associated relation (e.g., the ternary is-the-sum-of relation). (A cell’s associated relation is unary i.e. a set.)
The propagator network as a data structure changes in two ways: the relation that is expressed (i.e. the set of constraints – values in cells and so on) can be updated, and knowledge about the solution of a particular set of constraints (the propagated implications of the expressed constraints) can change.
Connecting propagators to cells is a side-effecty way of constructing new relational join expressions and therefore expressing new relations. The purpose of the propagation loop is to converge toward the relational join expressed by the network.
The readout of the knowledge state of the cells gives an approximation of the true solution to the constraint set. The would be the cross product of all of the sets expressed by each cell’s knowledge state (e.g. an interval), which contains the true solution relation. In the special case of the most successful possible outcome of constraint satisfaction, the knowledge states of the cells give exact single values for each cell, and the cross product approximation is the true relation, which is just a single tuple. This is the sense in which a propagator network can evaluate functions.
If a relation becomes known to be empty, we have a contradiction, and the TMS can help us figure out why.
So how does this comparison help?
- By showing connections to familiar frameworks (relations and relational algebra), a presentation like this might help in communicating the propagator idea to people (like me) who like declarative and mathematical formulations of things, and might convince them to help join the effort to develop the ideas.
- By thinking about the relations involved one might be helped to think about convergence conditions, case analysis, and other hard problems, and transfer mathematical intuitions developed elsewhere (topology, real analysis, compiler construction, database theory…) to the development of better propagator mechanisms.