How to model this problem in a graph database

even that the way to distribute data in graph databases is not that easy as in key-value stores, where the keys are distributed by ranges, there are techniques to distribute a graph.

InfiniteGraph (made by Objectivity) for instance is a highly distributed graph database. It uses a P2P technology to increase read and write performance by growing the hardware. It allows the user to cluster a certain part of the graph or a certain kind of information as its needed and to distribute it over some machines as its needed too.

As I heard this process of clustering/distribution will be eased for the user in release 3.0. A parallel query mechanism is also planned, that allows to run one query concurrently on the machines.

I think you are making a fairly common mistake here by selecting NoSQL technologies in order to be "future-proof" without understandng the tradeoffs. If in doubt start with PostgreSQL and figure you can always set up a graph db or other NoSQL db on the side as you need it. Also you can do graph traversal in PostgreSQL but keep in mind you are working with sets and so that's very, very different from a graph db with different benefits and drawbacks.

Your basic tradeoff is between flexibility of data entry and an ability to flexibly utilize data on output. NoSQL db's (including graph db's) sacrifice the latter for the former and because very often you need an ability to run ad hoc queries on sets of data you probably want an RDBMS somewhere. This means if you have a good data model, you should be able to add adjunct db servers to your environment for special purposes of your RDBMS won't handle it.

Nonetheless, there are a couple specific reasons why if you are thinking at some point of adding various NoSQL solutions why I would recommend starting with PostgreSQL instead of MySQL and these have to do with performance of NoSQL-friendly database structures and the fact that PostgreSQL supports WITH RECURSIVE common table expressions. This approach (WITH RECURSIVE CTE's) allows things like hierarchies and graphs to be traversed using recursive SQL statements which can repeatedly traverse paths. These are also relatively efficient for a set-based approach, and so if you end up with a lot of part/subpart modelling problems you may be able to do that directly in PostgreSQL without too much work. If this doesn't work however, you can also more easily represent the data in a way which is easier to import into your NoSQL db. So it gets you further and it integrates better. You may even be able to set up foreign "tables" against your NoSQL db and run queries against it from inside Pg!

More on the Tradeoff 1

Graph databases arose from a need to do binary traversal quickly over large sets of information. The obvious example might be a social network site like LinkedIn which might want to tell you quickly how far removed you are from another user (in simple terms this means essentially they are designed to play "six degrees of Kevin Bacon"). Typically on a graph database you are essentially traversing nodes using what are often described as "three word sentences" which represent the graphs. In this regard you are looking at essentially something like "John friended Jane" and traversing this way. Typically the API is relatively navigational.

A relational database is really designed to work with sets of information. Typically when giving up on relational databases, one is giving up on set operations too. This can be a big deal. Often it is faster both operationally and in terms of development time to be able to do set operations rather than navigate, aggregate, and report. This is a huge difference and if your use case fits a relational workflow, I have trouble imagining that a graph db will help you.

More on the tradeoff 2: Consistency Models

A second thing to investigate and keep in mind is the question of what consistency model your database uses. Even with "ACID-Compliant" RDBMS's there is a range of consistency models based on different levels of transaction isolation that can be used to prevent problems. If your data is important, the standard RDBMS consistency models are going to fare much better than most of the NoSQL models because they make more guarantees both to the DBA and to the application. Graph databases are a relatively large field, and each vendor may have some differences in their consistency model. This isn't necessarily something that will rule the use out, but it is something to be cautious about when looking at the solutions as a whole.

Note that schema flexibility is both a blessing and a curse in the NoSQL world and this also affects graph databases. It is a blessing because you can get up and running in the initial stages faster, but it is a curse because the set operation strengths of an RDBMS depend on a fixed schema, and those that relax that to some extent (Informix, for example, supports jagged rows in return sets) require programmer knowledge of the places where those requirements have been relaxed.