A relational approach to the design of deterministic programs

Deterministic programs are rules for functions; their specifications are relations. Designing a program to meet a specification (relation) R amounts to determining a function that meets some consistency requirement with R. This problem becomes more complex when relation R is complex, hence the potential need to decompose relation R. Complex relations can be built from simpler relations by relative product, union or transitive closure; hence complex relations (specifications) can be decomposed into simpler ones by writing them as a relative product, a union or a transitive closure of simpler ones. These decomposition strategies correspond to the traditional programming language constructs of sequence (;), alternative (if-then-else) and iteration (while-do). This paper presents relational decomposition rules and discusses their validity and significance.