@EricGT My leading contender right now is Erlang’s mnesia, partly because it allows multiple indexes (NoSQL typically only allows single indexes and, with some contortions, multiple indexes). But it’s not clear to me how best to do transitive joins (e.g., the “ancestor” predicate), or whether that matters if the query node is colocated with the data node. (I wonder if there’s a Prolog-mnesia connector …)
Another possibility is to implement a distributed set of pengines or similar, using the design paradigm from Bigtable. (The standard paper on that is a bit opaque on the underlying concepts, but it’s fairly straightforward. The downside is that it’s not clear to me how to best implement efficiently inverse (transitive) relationships.)