During the hackfest in Mumbaï, 5 of us had a brainstorming about database changes to try to improve it. Would it be feasible for the database not to track a linear version number of the update status, but a list of tickets, one for every DB update? Given these tickets are unique (centrally managed or random, i.e., a hash of the DB statements) you would have no troubles whatsoever applying patches in any order. You would even (with a corresponding un-apply DB statements file) be able to roll back individual patches. Of course, this means the update has to walk through the ticket numbers instead of checking a single version number. In case that's too expensive for the general case of a non-patched system, the update script could be taught a list of tickets of the updates that each released version contains. But I guess looking up a ticket number in a list maintained by the DB is exactly what a DB is good at.