![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Semirandom Musing on Databases
Feb. 3rd, 2008 11:29 pmAnyone 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...]
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...]
