May 4, 2012

Notes on graph data management

This post is part of a series on managing and analyzing graph data. Posts to date include:

Interest in graph data models keeps increasing. But it’s tough to discuss them with any generality, because “graph data model” encompasses so many different things. Indeed, just as all data structures can be mapped to relational ones, it is also the case that all data structures can be mapped to graphs.

Formally, a graph is a collection of (node, edge, node) triples. In the simplest case, the edge has no properties other than existence or maybe direction, and the triple can be reduced to a (node, node) pair, unordered or ordered as the case may be. It is common, however, for edges to encapsulate additional properties, the canonical examples of which are:

Many of the graph examples I can think of fit into four groups:

My main reason for reciting these diverse examples is to illustrate that, for any really interesting technical discussion, it is necessary to focus on a subset of the possible use cases.

Comments

9 Responses to “Notes on graph data management”

  1. Andrey on May 4th, 2012 8:06 am
  2. Marie on May 4th, 2012 3:43 pm

    Nice post. Looking forward to the follow-ups.

    Incidentally, I’m surprised you forgot the classic WWW graph in your examples :)

  3. Scott Meyer on May 4th, 2012 8:04 pm

    I don’t think you need to focus on a particular subset. In a graph database:

    1. All relations are first class (represented equally).
    2. Navigation can be done in constant time
    3. Schema change can be done in constant time

    The examples that you cite all benefit from these qualities in more-or-less obvious ways.

  4. Curt Monash on May 7th, 2012 4:29 am

    Marie,

    Thanks! Post edited in response.

  5. Curt Monash on May 7th, 2012 4:31 am

    Scott,

    Interesting points, but I’m not clear on what you mean by those “constant time” remarks. For example, I would expect simple forms of navigation to be logarithmic or so — I guess that might depend on the physical data model — in the number of edges/node, and linear in path length (or somewhat super-linear depending on what partitioning challenges one encounters).

  6. Scott Meyer on May 7th, 2012 8:23 pm

    Curt,

    The point of defining a graph database in this way is exactly to specify properties of the underlying physical model. If there is a theoretical distinction between a graph data model and a relational model, I suspect that it is very subtle. However, the distinction between constant-time navigation (hash tables, basically) and logarithmic (btrees) is chalk and cheese. LogN navigation means that there is some scale at which it no longer makes economic sense to embed a small graph in a large one.

    Similarly, the practical impact of requiring a constant-time schema change is that physical data must be laid out independent of schema. If not, then changing schema means changing N pieces of data.

  7. Cray | DBMS 2 : DataBase Management System Services on July 2nd, 2012 4:55 am

    [...] Graph-oriented systems such as terrorist networks are also now in the mix, which is how Yarcdata got started. [...]

  8. Introduction to Neo Technology and Neo4j | DBMS 2 : DataBase Management System Services on December 19th, 2013 4:18 pm

    [...] we look at my basic list of graph data model application areas, Neo4j seems to be involved in most of what you would think. Exceptions [...]

  9. 21st Century DBMS success and failure | DBMS 2 : DataBase Management System Services on July 14th, 2014 2:37 am

    [...] NoSQL/non-SQL has penetrated large enterprises mainly for a few specific use cases, for example the lists I posted for MongoDB or graph databases. [...]

Leave a Reply




Feed: DBMS (database management system), DW (data warehousing), BI (business intelligence), and analytics technology Subscribe to the Monash Research feed via RSS or email:

Login

Search our blogs and white papers

Monash Research blogs

User consulting

Building a short list? Refining your strategic plan? We can help.

Vendor advisory

We tell vendors what's happening -- and, more important, what they should do about it.

Monash Research highlights

Learn about white papers, webcasts, and blog highlights, by RSS or email.