You may find the ARRAY column type and associated operators help out here: you can efficiently index and query on array content, including contains and contained by operations.
PostgreSQL also features Common Table Expressions, which are an efficient and reasonably portable way to express a recursive query in a single SQL statement.
Finally, PostgreSQL has a native UUID data type that is efficient to store, index, and operate on.
Given your specified query, you should have something as simple as:
select uuid from node where ANY(children) = X OR ANY(parents) = X
There are other ways to write that - array concatenation, or array containment operations, but that is probably the simples. CTEs will allow you to extend that recursively if your tree structure query, as I anticipate, ends up needing to collect multiple levels in one operation.
In my testing both features performed well for search across a 15GB data set without substantial tuning, on an 8GB Mac laptop with slow spinning disk storage. Given your statements, I would strongly advise PostgreSQL as the conservative choice.
Again, in our testing, Riak performs well and has solid tools, but you need a three physical machine cluster to really start to see basic performance. Since you need much more persistence robustness than scalability, I think that will much less well fit your needs right now.