3
$\begingroup$

To begin with: what I know of computer science is what friends have told me and what I've read on Wikipedia. Please correct me if I'm using some term wrongly, or if there is something I can clarify.

Let's say I have a directed graph. I want my computer to look at it, and see whether x > y, y > x, or if the relationship between x and y is unknown.

Linear graph

If the graph looks kind of like this it's an easy task:

A linear graph

Just let a = 4, b = 3, c = 2, and d = 1. I can evaluate if a > c by comparing 4 and 2, and the result will be correct.

Tree graph

Now it gets interesting.

A tree graph

Here we have a tree graph. This kind of hierarchical data is discussed by Bill Karwin in these slides, which outlines four different ways of storing hierarchical data in a relational database. You can see a summary table on slide 69. Of these, the "nested sets" model looks like the one I'd prefer.

Directed acyclic graph (DAG)

Now, what if we have a directed acyclic graph?

enter image description here

All of the models described by Bill Karwin above work only if each node has at most one parent. In this graph, and more complex variants of it, any given node can have any number of parents (and any number of children).

My question is: how can I store a DAG in a normal relational database (such as MySQL) so that I can query the database for the relationship between two given nodes?

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
3
$\begingroup$

Excellent question. This is known as the problem of answering reachability queries in a graph, and in particular, in a directed acyclic graph (dag). Basically, you want to know whether y is reachable from x by following edges in the graph -- that's known as a reachability query. (And symmetrically, you also want to know whether x is reachable from y -- that's a second reachability query.) Answering reachability queries efficiently is challenging: there are good algorithms for trees, but dags are harder.

One approach is to do a depth-first search from x and see if y is reachable. However, in the worst case you might end up traversing the entire graph; the worst-case running time is $O(V+E)$. That's fine if the graph is small, but might take an uncomfortably long time if the graph is large. So there's been a lot of work on determining whether or not you can do some preprocessing or precomputation on the graph to make it easier to later answer reachability queries more efficiently than that. If the graph is static (doesn't change), this is known as the reachability problem in dags; if the graph is also changing, then this is known as the dynamic reachability problem for dags. These problems have been studied in both the CS theory and the databases communities.

Here are some resources to get you started in learning about the state of the art on this problem:

Finally, note that MySQL is a relational database, which is intended for relational data -- i.e., data in a tabular structure. I believe there are also graph-based databases, intended for data with a graph structure. I don't know much about that subject, but it's possible they might have built-in support that eases some kinds of queries and computations on graphs.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I've edited the question regarding the polytree/DAG comment, thank you. I will look at your list! $\endgroup$
    – Jobjörn Folkesson
    Jan 24, 2017 at 20:37
  • $\begingroup$ @jobjorn, ok, thanks! I removed that part of my answer... and added an additional remark at the end about graphs & databases. $\endgroup$
    – D.W. ♦
    Jan 24, 2017 at 21:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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