How to structure a graph database to support 3-way relationships?

Question

I've been trying to figure out a database backend for a personal webapp I've been working on. Due to the flexibility that I require in the data, a relational database isn't feasible and some form of document storage is likely. When I learned about graph databases, I felt that this would be perfect.

However, I've run into someone of an issue: I need to be able to define a 3-way relationship in some way. I haven't decided on a database yet, but I've been tinkering with Neo4j, so I'll use Cypher to describe the problem.

Essentially, I start out with this:

(a:N)-[r:E]->(b:N)

What I need is a way to relate multiple nodes to not only a and b, but also r. These other nodes are going to be storing different pieces of information about all 3. I decided that there are probably only two ways to handle this: store the relationship in its own node or store references to the nodes containing the information and create pseudo-edges. I figure that the former is probably a better idea giving us something more like this:

(a:N)<-[:E]-(r:R)->[:E](b:N)
(s:S)->(a)
(s)->(r)
(s)->(b)

So, now, this leads to an issue with querying the data. The whole point of using a graph database is being able to traverse the graph. If I do something like this, is there a way to recursively traverse between nodes of type N? What is the proper way of handling this? I've thought of several different ways of handling this, but all of them have their faults. Is there a specific graph database that supports this type of functionality natively?

UPDATE

With the original code, I was able to recursively traverse the nodes with this code:

MATCH (a:N)-[:E*]->(b:N)
RETURN a,b

However, once I pull the edge out into a hyperedge, I can't figure out if there is a way to be able to traverse the graph recursively to an undetermined depth because I would be alternating node types. I'm looking for something along the lines of

MATCH chain=((a:N)-[]->(r:R)-[]->(b:N))*
RETURN [nodes of type N along the chain]

If the answer is just to also create an edge between a and b while creating the hyper edge, then my question becomes: is there a good way to ensure that the edge and hyper edge are removed together? Basically, having both feels like a work-around rather than an actual solution.

stephen mallette stephen mallette · Accepted Answer · 2013-12-28T13:17:22

The scenario you describe is handled in property graph model by the hyperedge pattern @Pangea mentioned. You essentially convert the edge (that needs edges in/out of it) to a vertex. With graphs I would think of it less as a denormalization and more of a different modelling abstraction.

As far as native support for edges on edges go, none of the graphs you tagged your question with directly support such a feature. As you did include Titan and OrientDB I assume you are evaluating TinkerPop as a possible part of your solution as well and I can further say that as Blueprints doesn't support edges on edges, none of the Blueprints graphs will either.

As far as traversal goes, I can't say I fully follow what you mean by "recursively traverse". If you could elaborate a bit, I could try to amend my answer. I'll add this simple example of how you would traverse from the "a" vertex to find all other related vertices in Gremlin (sorry, I don't know Cypher):

gremlin> g = new TinkerGraph()
==>tinkergraph[vertices:0 edges:0]
gremlin> va = g.addVertex([type:'N',name:'a'])
==>v[0]
gremlin> er = g.addVertex([type:'R',name:'r'])
==>v[1]
gremlin> vb = g.addVertex([type:'N',name:'b'])
==>v[2]
gremlin> vc = g.addVertex([type:'N',name:'c'])
==>v[5]
gremlin> va.addEdge('e',er)
==>e[3][0-e->1]
gremlin> vb.addEdge('e',er)
==>e[4][2-e->1]
gremlin> vc.addEdge('e',er)                   
==>e[6][5-e->1]
gremlin> va.out.in.except([va]).name
==>c
==>b
gremlin> vd = g.addVertex([type:'N',name:'d'])
==>v[7]
gremlin> es = g.addVertex([type:'R',name:'s'])
==>v[8]
gremlin> vb.addEdge('e',es)
==>e[9][2-e->8]
gremlin> vd.addEdge('e',es)
==>e[10][7-e->8]
gremlin> x=[];va.aggregate(x).out.in.except(x).loop(4){it.loops<2}.name
==>c
==>b
gremlin> x=[];va.aggregate(x).out.in.except(x).loop(4){it.loops<3}.name
==>d

In regards to:

If the answer is just to also create an edge between a and b while creating the hyper edge, then my question becomes: is there a good way to ensure that the edge and hyper edge are removed together?

When you remove the "hyperedge" vertex, you will automatically remove the edges connected to it, so you effectively remove them together.

How to structure a graph database to support 3-way relationships?

3 Answers