Log in

No account? Create an account

Previous Entry Share Next Entry
Tree Hierarchy
How much of a geek to I need to be to chuckle at the idea of looking for help with designing a database to store a tree hierarchy in the comp.databases.theory archive on Google Groups?

(Hint: Google shows each thread as a huge tree structure in the left frame.)

For those who think they're geeky enough to tackle this, the specific problem I'm having is with the case of a node having more than one parent. You give it a row for each parent, right? Ok, so then what if that node has children? To which row does it point to as the parent? Both? That means two rows for each child. This would quickly get out of hand, plus the duplication of data means the database isn't normalized. (Every instance of a parent somewhere should have the same children under it, so shouldn't it only need to be defined once?)

Wrap your head around that one and then get back to me. :)

(Incidentally, the Google Groups thread tree isn't vulnerable to this problem because each message only has one parent, so I'm not chuckling TOO much...)

  • 1
Then just imagine it to be Node-and-Arc. Imagine Rochester being a node. There's an arc that leads to Buffalo and an arc that leads to Syracuse.


That's an undirected graph. (or undie graph as us crazy computer people call it.)

Now, if you have one-way arcs, it's a directed graph. If you could only go from Buffalo to Rochester and only from Syracuse to Rochester, the graph looks something like this:


And here's an intro to graph theory.

Wow... thanks. Ok then, is there any way to store information about a graph in a relational database (if that's what MS Access is) and easily return all first-degree vertices that can be reached from a specific starting vertex using just normal (non-recursive) SQL?

I've found a way to do that with a tree... by using Joe Celko's method of storing lft/rgt values. I'm wondering if there's a similar trick that can be applied to a graph.

  • 1