The battle plan for implementing relations in drupal in no particular order.
hooks - possibly yes, it is a matter of splitting the functionality. I can see the biggest split in execute a relation query and give back the result in a consistent form and get some data to build queries from. Both should be available. The first for speed, the second for extensibility.
trees - vauxia's code will help. I've actually used it, with some extensions, mainly for INSERTs, so we can postpone reindexing.
term - well, it is a good example for a complex relation in Drupal - it is more node->terms->node. What I meant is find related nodes by taking into account which terms they are tagged with.
* relations hooks
* trees: can vauxia help here?
* Term: do we need to bether about taxonomy yet? Should we not ignore that for the time being?