Graph of different objects (implementing a similar interface) in a relational database

Question

So I was pondering about certain problem involving serialization of objects to relational databases.

Let's say you have N different objects, all implementing a certain interface (a directed graph interface for that matter. they provide methods such as getIncomingNodes() , getOutgoingNodes()).

If each such object has a corresponding table in a relational database, What's the best practice of serializing such a directed graph to a relational database?

Assuming N is small, (in my case, N=3) I decomposed all possible links to be contained in a separate table. For example, A table of links directed from object x to y will be similar to:

tbl_links_X_Y {
int X_id
int Y_id
}

Problem is , you get N^2 such tables - not very efficient, and could prove difficult to extend in the future to N+1 objects.

Is there any pattern that solves that issue? (even if it does not involve relational databases, I would be happy to hear...)

Thanks!o

Answer 1

You can easily store the class of the objects (table names) in the connection table as well.

tbl_links_X_Y {
int X_id
int Y_id
enum {user, customer, product} X_type
enum {user, customer, product} Y_type
}

They you would just include this in the where or join clause.

I guess this would not be a strictly relational database, since you can't (?) use/enforce foreign key constraints.

Answer 2

You could also "force" your graph to follow the relational model : ie

Table Graph { integer vertexid, varchar edgelist }

edgelist could be made a delimiter based string: For instance {2,10},{3,12},{4,13} etc where entries are {incident vertex,weight}
That way, the number of rows in your table will be O(n) instead of O(n^2)

Then when your application reads the graph and perform some operation, you would have to build the graph in memory,and do the same.

Answer 3

So recently I ran into a NoSQL framework calls OrientDB
That DB engine handles this issue exactly. It is a graph database that has the ability to perform SQL queries and lazy-load object (such as neighboring vertices) that are pointed by another object.

One thing that remains is to compare the performance of this framework to that of a traditional SQL database. (Of course, I'll have to take into account the time it would take for constructing the objects from the raw responses to the query in a traditional SQL database.. )