Pere Urbón Bayes has put together an excellent table comparing features of notable graph databases: post, table (PDF): Neo4j, HyperGraphDB, DEX, InfoGrid, Sones and VertexDB.
One can quibble, as one always can with tables like this, but it is the best comparison of graph databases so far that I’m aware of. Check it out.
Part 7: Sets
Sets are a core concept of most databases. For example, any SQL SELECT statement in a relational database produces a set. Sets apply to Graph Databases just as well and are just as useful:
The most frequently encountered set of nodes in a Graph Database is the result of a traversal. For example, in InfoGrid, all traversal operations result in a set like this:
MeshObject startNode = ...; // some start node MeshObjectSet neighborNodes = startNode.traverseToNeighbors();
We might as well have returned an array, or an Iterator over the members of the set, were it not for the fact that there are well-understood set operations that often make our jobs as developers much simpler: like set unification, intersection and so forth.
For example, in a social bookmarking application we might want to find out which sites both you and I have bookmarked. Code might look like this:
MeshObject me = ...; // node representing me
MeshObject you = ...; // node representing you
TraversalSpecification ME_TO_BOOKMARKS_SPEC = ...;
// how to get from a person to their bookmarks, see post on traversals
MeshObjectSet myBookmarks = me.traverse( ME_TO_BOOKMARKS_SPEC );
MeshObjectSet yourBookmarks = you.traverse( ME_TO_BOOKMARKS_SPEC );
// Bookmarks that you and I share
MeshObjectSet sharedBookmarks = myBookmarks.intersect( yourBookmarks );
Notice how simple this code is to understand? One of the powers of sets. Or, if you know what a “minus” operation is on a set, this is immediately obvious:
// Bookmarks unique to me MeshObjectSet myUniqueBookmarks = myBookmarks.minus( yourBookmarks );
This is clearly much simpler than writing imperative code which would have lots of loops and if/then/else’s and comparisons and perhaps indexes in it. (And seeing this might put some concerns to rest that NoSQL databases are primitive because they don’t have a SQL-like query language. I’d argue it’s less the language but the power of sets, and if you have sets you have a lot of power at your fingertips.)
To check out sets in InfoGrid, try package org.infogrid.mesh.set. Clearly much more can be done than we have so far in InfoGrid, but it’s a very useful start in our experience.
I’m planning to be at Big Data Workshop, the first unconference on NoSQL and Big Data. If past events moderated by Kaliya Hamlin are any guide, it will be a great opportunity for everybody:
Arguably, without Internet Identity Workshop (also moderated by Kaliya) was the enabler for the stunning adoption rate over the past five years of OpenID, OAuth and related technologies (at last count, more than 1 billion enabled accounts). I hope history repeats itself here.
P.S. Feel free to corner me on InfoGrid, graph databases or any other subject. That’s the whole point of an unconference.
Graph theory distinguishes between graphs that are multigraphs and those that are not, i.e. between graphs where there may be more than one edge between any two nodes, and those graphs where there can only be one edge between any two nodes.
On the first glance, InfoGrid does not support multigraphs. On the second glance, InfoGrid is a bit more powerful than it appears; not an unusual occurrence 
Let me explain:
Here is how we create an edge between two nodes in InfoGrid:
MeshObject node1 = ...; MeshObject node2 = ...; node1.relate( node2 );
If we try to do the last statement again, InfoGrid will throw a RelatedAlreadyException. That clearly says that multiple edges between the same two nodes are not allowed.
But.
We do this in InfoGrid because unless there is some associated information with each of these edges, we cannot distinguish them and so there is no point in having two. The way we do that in InfoGrid is to bless the edge with more than one RelationshipType, such as:
node1.blessRelationship( PARENT_TO_SON, node2 ); node1.blessRelationship( CUSTOMER_TO_VENDOR, node2 );
These two relationships express that node1 is a parent of son node2, and that node2 (the son) has sold something to customer node 1 (the parent). Very different semantics associated with the same edge. Just like multiple edges in a multigraph.
So: InfoGrid supports multigraphs just fine, just perhaps not entirely as you would have expected.
Part 6: Traversals
Traversals are the most common operations on a graph database. They are just as important for graph databases as joins are for relational databases. But of course, they are something else as graphs are not tables.
A traversal in a graph database is uniquely described by two data items:
A traversal always leads to a set of nodes. Depending on the structure of the graph being traversed, that set may contain many, one or zero nodes. For example, if we traverse from a node representing a Person to the nodes representing their grandchildren, we may or may not find any, depending on whether they have any.
From a given node, we can traverse in many different ways (i.e. same node, different traversal specifications). Or, given the same traversal specification, we can start with different nodes.
By way of analogy, consider street directions:
The result of this particular traversal is a single-element set containing the neighborhood park. If you had started at the same node (my house), but gone right first, you would not have arrived at the park. If you had started at a different node (somebody else’s house), you may or may not have arrived at the park. You may not have arrived anywhere (perhaps there is no left that one can take from certain houses). Or you might have arrived in multiple places (“go either straight or left” might not take you to the same part regardless which you take, but taken you into different directions.
Graph database products seem to differ on how to deliver to the developer the set of nodes that is the result of a traversal. In InfoGrid, all traversals produce a MeshObjectSet, which, as the name says, is a set of nodes. One can then iterate over that set, for example, subset it, unify it with another or ask how many elements it has. In other products, traversals produce an iterator directly which then can be queried for one member of the result set at a time. Regardless of API details, the result of a traversal is always a set (e.g. it can’t contain duplicates.)
Just like there are many ways of giving directions, traversal specifications can be captured in many different ways. In InfoGrid, we have — you guessed it — an abstract data type called TraversalSpecification and several different classes that implement that type, such as:
The FirstStep example shows some simple traversals.
And just for simplicity, InfoGrid also allows traversals starting from a set of start nodes, not just one. So we can say things like this:
MeshObject me = ...; MeshObjectSet myParents = me.traverse( childToParents ); MeshObjectSet myGrandParents = myParents.traverse( childToParents );
In our experience, working with sets makes complex traversals very easily understandable.
Part 5: Identifiers
Well, “identifiers” aren’t much of an “operation”, but there are some operations related to identifiers, thus the title.
All first-class objects in a graph database typically have a unique identifier. This means nodes have unique identifiers, and for those graph databases that represent edges as distinct objects (see previous discussion on the pros and cons), they have unique identifiers, too.
This means we can ask a node for their identifier, remember the identifier, and later find the node again by looking it up in the graph database. In InfoGrid, this looks as follows:
MeshObject someNode = ...; // some MeshObject aka Node
MeshObjectIdentifier id = someNode.getIdentifier();
and later we can do this:
MeshBase mb = ...; // some MeshBase
MeshObject nodeFoundAgain = mb.findMeshObjectByIdentifier( id );
As you can see, InfoGrid uses an abstract data type called MeshObjectIdentifier, which you can think of as String for a second. (see below.) In InfoGrid, all identifiers are long-lasting. This means, your object will still have the same MeshObjectIdentifier after you rebooted your database. This has some advantages, e.g. you can define well-known objects in your graph database to which you can easily return even weeks later.
Other graph databases may use different data types as identifiers (e.g. int or long), but the use of identifiers is common with the above operations. They may or may not be the same after rebooting of the database.
Why does the type of identifier matter? Well, it depends on the application you have in mind. For InfoGrid applications, we primarily care about web applications, specifically REST-ful web applications. And so InfoGrid web applications generally use MeshObjectIdentifiers that identical to the URLs of the application. Let’s make an example:
Assume you have a URL bookmarking application which runs at http://example.com/. Let’s say a user creates tag “books”, which can be found at URL http://example.com/books/. It would be most straightforward to create a MeshObject with MeshObjectIdentifier http://example.com/books/. Which is exactly what InfoGrid does by default. No impedance mismatch between URLs that the user sees, the objects in the application layer, and the database! This leads to dramatic simplification of development and debugging.