This isn't a fully-thought-out, comprehensive solution, but rather something that occurred to me while reading your examples. So there may be better arguments for or against this approach...

What strikes me most about the predicates you describe is that they seem to lend themselves to a matrix-like structure. Granted, in your examples you are using names/strings rather than numbers, but that is a minor detail, comparitively speaking. If you can handle converting queries to and from matrix indices (or vector extractions, or vector operations, etc.) then you may find that PDL may be a great boon to your efforts. As an added plus, it handles sparse matrices, which I seem to remember being a key implementation component of matrix-based AI.

But it's been 13 years since I took an AI class, or even really read up on the topic. This is just a thought.

--rjray