Drew McDermott made a build system called (IIRC) "chunks," that did just what you want: it put dependencies on arbitrary data structures and recomputed them on need. One challenge is that his build system is built on top of his "yale-tools" mega-library, which can be difficult for outsiders....
Here's Drew's paper, A Framework for Maintaining the Coherence of a Running Lisp: http://www.cs.yale.edu/homes/dvm/papers/lisp05.pdf
I suggest you read this, and see if you could graft the ideas onto ASDF (with suggestions from asdf-devel).
ASDF mostly uses the filesystem to track dependencies (although it has an internal db, as well), so there would be a little effort to extend to a non-file-centric build.
Drew's key idea is that his system (and ASDF), unlike build systems like make or ant, have as a primary job maintaining the integrity of the running lisp image. [Faré may disagree with this claim: he comes to Lisp usage with a newer perspective than my old-school view.]
Drew's system is less fine-grained than the cells system that Faré suggests. I don't think the cells system ever got mature enough for use.
If you want a dependency-driven, lisp-based constraint system per Faré, I think you'd have better luck with the KR system developed a long time ago at CMU. It is primitive in some ways (hand-built on structures, rather than using CLOS), but was used for years in a very high-stress environment, so is much more likely to work than cells. KR is available as part of the Garnet UI system. Drop me a line if you are interested.
Best, r