Other people's work
I went to three talks about query rewriting. the first one was about the properties of the relations between queries, modified queries to be executed on a view of this database, and results. The second one presented a technique to modify queries to handle properly inconsistent data. It works by adding constraint to the query to drop the inconsistent data (useful when the constraints are not part of the DB schema). The third one was officially about 'Rewriting queries using views with access patterns under integrity constraints', but I'm afraid I didn't understand anything.
I also read Jacques Garrigue's paper 'Code reuse through polymorphic variants' (after fighting an hour with the stupid printer to print it). It claims to define a simple solution to the expression problem using O'Caml's polymorphic variants. I believe the solution is fundamentally the same as the solution I had outlined for SLinks (that requires recursive types which are not part of the language right now) in an earlier post.
He does however provide a solution for a problem I did not solve. If you consider this example: 'defrec ^eval2 = fun ^exp -> case exp of <#p={#l=^l,#r=^r}> in (eval2(l))+(eval2(r)) | ^e in eval(e);', the recursion is always done on eval2. That means that if an eval3 function to support extended data is defined, if will not be possible simply to delegate the evaluation of the known cases to eval2 (as eval2 does with eval), because the recursion in eval2 is on the wrong function. To do this, Guarrigue uses open recursion which solves the problem quite nicely (and could, I believe, also be used in SLinks with recursive types).
However, his solution also has the same kind of problems as mine: new functions extending the supported data must have new names (one cannot simply redefine the old function). This means that code using the first version of the function will not support the extended data for free.