# How to evaluate relations in a DAG?

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:

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.

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?

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?

## 1 Answer

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.

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