Using MongoDB as our master database, should I use a separate graph database to implement relationships between entities?
Mike,
you should be able to store your relationship data in the graph database. Its high performance on traversing big graphs comes from locality, i.e. you don't run queries globally but rather start a a set of nodes (which equal documents in your case, which are looked up by an index. you might even store start-node-ids for quick access in your mongo documents). From there you can traverse arbitrarily large paths in constant time (wrt data set size).
What are your other requirements (i.e. data set size, # of concurrent accesses etc, relationship/graph complexity).
Your queries are a really good fit for the graph database and easily expressable in its terms.
I'd suggest that you just grab a graphdb like neo4j and do a quick spike with your domain to verify the general feasibility and also find out additional questions you would like to have answered before investing in the second technology.
P.S. If you hadn't started yet, you could also have gone with a pure graphdb approach as graph databases are a superset of document databases. And you'd rather talk domain in your case anyway than just generic documents. (E.g. structr is a CMS built on top of Neo4j).
The documents in MongoDB very much resemble nodes in Neo4j, minus the relationships. They both hold key-value properties. If you've already made the choice to go with MongoDB, then you can use Neo4j to store the relationships and then bridge the stores in your application. If you're choosing new technology, you can go with Neo4j for everything, as the nodes can hold property data just as well as documents can.
As for the relationship part, Neo4j is a great fit. You have a graph, not unrelated documents. Using a graph database makes perfect sense here, and the sample queries have graph written all over them.
Honestly though, the best way to find out what works for you is to do a PoC - low cost, high value.
Disclaimer: I work for Neo Technology.