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.
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.
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?