Semirandom Musing on Databases

[tcepsa]

Anyone out there know whether there's a reasonably easy way to represent a tree of arbitrary depth in a database? There's nothing special about any given level of the tree, but there has to be a fairly straightforward way of retrieving the parent and (if present) children records of a given node. Siblings would be nice too, but aren't as important for what I'm thinking about (and worst case scenario, if I need them, siblings are all of the current node's parent's children that aren't the current node).

All of the shadows of ideas that I've come up with so far involve either one, two, or X tables (X being the number of levels in the tree, which makes my brain recoil in horror for daring to even think of it), and a bunch of semi--if not fully--recursive programming on the code side... I'm wondering if there's a way to set it up so that the database can handle it instead, but my SQL-fu is not that strong. Am I barking up an impossible tree, or is there a solution to this problem if I just throw my brain at it harder?

(For a concrete example of what this could be used for, think XML document storage. I make no claims as to the usefulness or efficacy of such an implementation; I merely wish to know about the feasibility.)

Required queries (since maybe this'll be a little more straightforward than the phrasing above):
Give me the record of the parent of this node ID.
Give me the records of the children of this node ID, if there are any.

Queries that would be nifty:
Give me the records of all the siblings of this node ID.
Give me the records of all the ancestors of this node ID [even more optional: to N generations away].
Give me the records of all the descendents of this node ID [even more optional: to N generations away].


[EDIT: Okay, I'm pretty sure two tables would work to provide the 'required' queries. One to hold the actual node records, and one to map parents to children. That doesn't address the problem of recursion on the 'queries that would be nifty' side of things, but that part may be intractable...]

Comments

[adularia.livejournal.com]

You don't need N tables, for sure. *cringes*

Um... damn, this is brain candy. I'm at work now, but I'll have to poke it today. Responses will be biased towards MySQL.

[tcepsa.livejournal.com]

~grin~ Looking forward to it!

[shadeofnight.livejournal.com]

Oracle handles it very well, and does recursive queries in very simple syntax. I am not sure any of the other databases do recursive in the database itself with just a single query....

Most people do trees in the same way as a data structure, and just put a parent_id on the node itself, that references the primary key of the node it is in... so the table looks like

ID .... Name of NODE ... Parent ID
1 Hi I am top NULL
2 Hi I am child 1
3 Hi I am another C 1

Not sure if any of that helps, but I do a lot of tree coding in my code these days...

[tcepsa.livejournal.com]

Oracle handles it very well, and does recursive queries in very simple syntax. I am not sure any of the other databases do recursive in the database itself with just a single query....

This may be the first shiny thing I've learned about Oracle... ~wry~ I'm not sure it'd be enough to convince me that I actually want to use it though.

Most people do trees in the same way as a data structure, and just put a parent_id on the node itself, that references the primary key of the node it is in... so the table looks like

~nods~ That seems like it would work, though it also seems like it would be a hassle to write a query to get, for example, the parent record for a given child ID (e.g. 5, so I don't feel obligated to put in the code to create a prepared statement, etc. ~wry grin~). It would have to look something like this:

SELECT * FROM tree_table WHERE id=(SELECT parent_id FROM tree_table WHERE id=5)

Or maybe

SELECT * FROM tree_table a INNER JOIN tree_table b ON a.id=b.parent_id WHERE b.parent_id=5;

(Can a table do inner joins on itself like that?)

[shadeofnight.livejournal.com]

Any table should be able to join to itself in both inner and outer joins, so you should be covered by that.

Since you database is not doing recursion all that well, you will have to build some fancy functions in your code outside the database to handle it.

In oracle I can do stuff like:

select treeid
from tree T
start with 1
connect by T.treeid = prior T.parentid

That will return the entire tree in order from the treeid 1. You can also change the start and connect by info to go up or down the tree...

If I had to do this outside oracle, I would have to do loops of loop...

Select * from tree where parent_id is null

then select * from tree where parent_id = #treeid#

and then do recursion on those logic until the whole tree is printed... maybe make into a function to start at the any point passed into the function... fun stuff heh.

[nminusone.livejournal.com]

My customers almost always require my code to be database vendor-agnostic, so my perspective is pretty much "What can you do with straight-up ANSI SQL?" From that point of view I think the 2-table solution is the best generic one, though if you know more about the shape of the tree you might try to denormalize in various ways to get higher performance.

Stepping back a bit I'd suggest that a strict relational DB is probably not the ideal way to store tree-structured data. The shapes just don't map onto each other well enough. For light duty use I'm sure it's fine but for anything heavy duty I'd look for a storage mechanism that more closely matches the tree structure. At which point, yeah, you're probably looking at various non-standard extensions that Oracle, SQL Server and others have. And as an aside I need to read up on the latest version of ANSI SQL...