2

Is there a recommended pattern for modeling a graph in a relational database?

My presumption is that you'd have the following three tables:

Graphs
------
GraphID, PK
GraphName

Each record in the Graphs table represents a single graph you are modeling.

Nodes
-----
NodeID, PK
GraphID, FK
NodeName, string
...

Each record in the Nodes table represents a node in GraphID, specifying attributes specific to that node.

Edges
-----
EdgeID, PK
GraphID, FK
FromNodeID, FK
ToNodeID, FK
EdgeName, string
...

Each record in the Edges table represents an edge in GraphID, specifying the Nodes it connects and the attributes of an edge (name, distance, etc.).

What I'm having a hard time wrapping my head around is what if there are different types of nodes, where each type of a node has some attributes in common (say 5 or so), but has many unique attributes (say 10-30)?

For simplicity's sake, imagine there are two types of nodes to capture: A and B. How do I model this? I've seen one option being to have a "general" Nodes table:

Nodes
-----
NodeID, PK
GraphID, FK
NodeName, string
AnotherSharedAttribute, string
...

And then a detailed table for node type A and node type B:

NodesA
------
NodeID, PK
UniqueToA1, string
UniqueToA2, string
...


NodesB
------
NodeID, PK
UniqueToB1, string
UniqueToB2, string
...

Am I understanding this approach correctly? Because what flummoxes me is how do I query this efficiently? It seems to me that to determine the attributes for a particular node, I have to check all possible node type tables (NodesA and NodesB in this case) for a matching NodeID. This might not be a big deal with just two different types of nodes, but in my project there are ~30 different types of nodes and 5 different types of edges.

Thanks

  • 2
    Have you considered Microsoft's built-in Graph features in SQL Server 2017? – Max Vernon Jul 31 '19 at 16:18
  • @MaxVernon - I have not considered the Graph features in SQL Server 2017, thanks for pointing those out. They look interesting, I'll have to explore those more. My initial concern would be tooling support and mapping these to our object layer - we use Entity Framework for data access. My light Googling shows that EF does not have native support for the Graph features. Also would need to investigate how well these SQL Server features map to an object layer. – Scott Mitchell Jul 31 '19 at 16:38
  • 1
    But you can at least get answers to your questions from the implementation of Graph in SQL Server 2017. Each "node type" and "edge type" maps to a separate table. – David Browne - Microsoft Jul 31 '19 at 18:42
  • @DavidBrowne-Microsoft - I think I'm missing something fundamental here as I'm not seeing how one would have each "node type" as a separate table yet still be able to construct the graph without individually querying each table. I posted a new question that asks this more directly within the purview of SQL Graph - dba.stackexchange.com/questions/244260/… - if you have a moment I'd appreciate your input. Thanks – Scott Mitchell Jul 31 '19 at 18:59
0

There is no great way for modeling a graph in a relational database. They are two different data models. One says data "is really" sets of tuples. The other says it "is really" nodes connected by edges. These are different. Although any real-world scenario can be represented in either model the affordances of each are different. If the use-case is to perform an operation on multiple items that conform to a predicate (e.g. update .. where..) the relational model will, generally speaking, be more convenient. For use-cases involving following connections between items ("people who bought .. also bought ..", "you and Andi have 17 friends in common") the graph model is likely to work better. A relational DBMS makes implementing the former easy and the latter more difficult, and vice versa for a graph DBMS.

There are a few well-trodden relational implementations for the specific sub-set of graphs that are trees.

When implementing a solution in a RDBMS we only have tables to work with. So one has to decide which tables are needed to implement a generalized graph. Are the items of interest in the problem domain simply "things" which can be modeled as a single Node table and all the values of interest in a NodeAttribute table? This is analogous to an EAV, but in a graphy kind of way. Generally this is not useful unless we are concerned purely with the connectivity of nodes.

Usually we want to group things into classes and apply different constraints to each class. We could add a Class attribute to the Node table. This still leaves all the hard work of filtering rows of specific Class, and navigating between classes, to user code.

Relational databases are designed to have one table per class. If we have multiple classes of nodes then each should have its own table. If, as in your question, there are sub-classes of nodes then the problem can be restated as "how to model sub-classes in a relational way?" This is now a problem of table inheritance, about which quite a lot has been written. Some DBMS implement this natively; SQL Server does not.

how do I query this efficiently?

The same way you query any other relational database. Good indexes that support the queries. Understanding the implementation and referencing only those objects required to satisfy the query's needs. If you have 30 types of nodes and 5 types of edges it is unlikely that all will be required in every query.

The discussion above for node tables applies equally for edge tables.

There are hybrid DBMS which allow the representation of data in both graph and relational ways. Starting with 2017 SQL Server introduced graph extensions. Sadly the MATCH clause was little more than syntactic sugar on SQL-89 joins redux. No graph-like affordances were "supported in the first release", though the language was encouraging.

With SQL Server 2019 transitive closure is now supported. One can only hope polymorphism is not far behind.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.