Sunday, February 26, 2006

Hierarchical data structures in relational databases

It's all relative, as are the many possibly ways to express hierarchical structures in relational databases. I spend a few hours this weekend reading about the theory behind this subject and I found many interesting articles but they all seemed to boil down to the following:

Adjacency list
Nested sets (Nested Intervals)
Materialized path

The three above mentioned methods may not be the only ones, but I think most others are derived from one of the above.
Anyways - I was looking for a method for blazingly fast reads and somewhat fast inserts. Especially fast inserts seems to rule out nested sets and fast reads on more than one level seems to rule out adjacency lists, but does it really.. I've come up with an approach albeit it might need some more space (hence data) its basically still an adjacency list but with link data.
For each node I insert the path to the root in a link table (called hierarchy in the below example). I simply go from the node to the root and for each node along the way, I insert a link into the link table. Then I am able to query all nodes for the whole tree or just a sub-tree if I want. I still have a "parent_id" on each node, so a "gimme all nodes directly below this node" is still possibly as with any adjacency list design.. I just have a tad more book-keeping.. But querying is fast and simply and so is inserts and deletes (since its quite fast to find ALL descendants of any given node).. Moves are a hazzle, but who does this a lot?? I surely don't..

There might be an "offical word" for this approach but I call it "Linked adjacency list".


Node (id, name, parent_id)
"2";"Node 1";"1"
"3";"Node 2";"1"
"4";"Node 3";"1"
"5";"Node 1.1";"2"
"6";"Node 2.1";"3"
"7";"Node 3.1";"4"
"8";"Node 1.1.1";"5"
"9";"Node 1.1.2";"5"
"11";"Node 3.1.1";"7"

Hierarchy (node_id, ancestor_id)

This is a simple query of all data below node with id 1 (which is the root node, hence all data) wich select the name of the node and nodes depth in the tree:

select, count(h2.node_id) as depth
from node n, hierarchy h, hierarchy h2
where h.ancestor_id = 1
and h2.node_id = h.node_id
and = h.node_id
group by

Which gives the following result:

Node 3;1
Node 1.1.2;3
Node 2;1
Node 3.1.1;3
Node 2.1;2
Node 3.1;2
Node 1.1;2
Node 1.1.1;3
Node 1;1

Quite messy, huh?

Sunday, February 12, 2006

Gimme my mail, James!

I am working on a project for which we needed a mail server of some sort. We had some pretty peculiar demands for the mail server and by looking at various servers, we decided to go with James. James is a mail and news server from Apache. I had to change ONE internal bit of James to make it accepts mails (as for local server) for all sub domains of a single top-level domain, so we could add multiple sub domains WITHOUT changing the config.xml file and restarting the server. The rest was simply a matter of creating a few Matchers and some Mailets... Great.. I really enjoyed working with James - its easy and logically as you would except and seems to be performant, as I can easily handle more mails than I expect will go thru the system.

Saturday, February 11, 2006

ME, myself and I

It's been awhile - things have been crazy here i Denmark (if you don't know WHY it has been crazy for the state of Denmark, I'm NOT gonna tell ya' - better to stay in oblivia)..

Well - I finally got around to write some more J2ME code... Working on a rather interesting MIDlet... Anyways - I am stunned how easy it is to write simple apps in the MIDP environment.. Yes, you are somewhat limited and its not the BEST looking GUI you can produce just by using the standard Items, but still - its fairly easy to create a mockup/prototype, even with GPRS communication.. I wonder why you don't see more wireless apps?