Previous Entry Share Next Entry
Tree Hierarchy
digimind
thwack
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
That's the basic problem. Trees, by accepted definition in Computer Science circles have only one parent. What you have is a Graph, not a tree. (All trees are graphs, but not all graphs are trees.)

Yeah, I keep seeing that term graph, but I have yet to grasp the concept of it because to me a graph is a 2-dimensional representation of key-value pairs and I have yet to see a description of the visualization of this new (to me) type of "graph".

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.

B---R---S

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:

B-->R<--S

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.

I think you should use XML with Flash on a website instead.


HAHA! *pisses in cheerios* :-P

No! See, Flash can be ON a website, no problems there. You can only piss in my cheerios by saying Flash IS a website. Get it right! :-P

For the record, XML with Flash sounds very cool. Unfortunately I barely know either one, let alone how to combine them.

That's actually what that picture viewer thing does. You should play with that sometime.

  • 1
?

Log in

No account? Create an account