In hindsight it occurred to me that the algorithm can be abstractly expressed in terms of relational algebra for which I need an EDSL.

One concrete implementation could then be an interpreter / compiler to SQL, if I choose to use a database backend, and another implementation could be a interpretor to in-memory data structures (maps, whathaveyou), or a debugger to see if I have got the abstract algorithm right.

Perhaps the CoddFish project (what a great name!) may be relevant here: http://wiki.di.uminho.pt/twiki/bin/view/Research/PURe/CoddFish Perhaps it is the first project that systematically exploited the connection between functional dependencies in type classes and functional dependencies among database attributes.