Hmmmm, well, it doesn't sound particularly easy. You basically take whatever effort would be involved with compiling down from a string-based form (say, what Hibernate QL does) and then add on top of that magic to get your relational algebra representation to play nicely with the Ocaml type system. (Basically you're creating an embedded DSL). Are you considering targetting SQL or MAL? In a sense MAL seems ideal since the BAT operators implement a relational algebra already, so it would be a fairly direct mapping. Well, except then you're inventing the concept of tables from scratch. In any case, I suspect the main difficulty here will be in the frontend... BTW, Scala has a SQL DSL as well you might want to check out for further inspiration (it's taking heavy advantage of implicits, which are sort of like type classes - Ocaml doesn't have these of course, but maybe still interesting).