Re: Quote of the Week

From: Paul <paul_at_test.com>
Date: Thu, 13 May 2004 23:29:32 +0100
Message-ID: <oFSoc.3147$wI4.311658@wards.force9.net>

--CELKO-- wrote:
> The organizational chart would look like this as a directed graph:
>

 >            Albert (1, 12)
 >            /        \
 >          /            \
 >    Bert (2, 3)    Chuck (4, 11)
 >                   /    |   \
 >                 /      |     \
 >               /        |       \
 >             /          |         \
 >        Donna (5, 6) Eddie (7, 8) Fred (9, 10)

It's a very ingenious method, but the thing that worries me a bit is that you're basically creating a list and specifiying an arbitrary order:

1 Albert {
2 Bert {
3 }
4 Chuck {

5      Donna {
6      }
7      Eddie {
8      }
9      Fred {
10     }

11 }
12 }

So everyone supervises the people between the numbers of their opening and closing brackets. (just another way of writing what you're saying really and easier to write than ascii art!). Now how is this different to this?:

1 Albert {
2 Chuck {

3      Eddie {
4      }
5      Fred {
6      }
7      Donna {
8      }

9 }
10 Bert {
11 }
12 }

You have two different relations representing *identical* real-world situations. How would you compare two of these organization structure relations for equality?

Maybe use alphabetical order to assign the numbers, but what if you need a tree structure for a domain that doesn't have an ordering defined on it?

I think with all these discussions about representing trees in the relational model, we always skirt around the basic problem: it can't be done properly with first-order predicate logic.

It seems to me that the adjacency list model is the elegant solution to storing the data because it doesn't require adding extra artificial items of data. The problem (if it is one) is that querying it requires additional relational operators like the "transitive closure" operator to boost the level of logic up towards second-order logic.

I'm not sure off-hand if a transitive closure operator would allow you to answer all possible queries about trees stored in an adjacency list model, but I suspect it would.

> Now do a simple query, given an employee, find all their Supervisors,
> no matter how deep the tree.

>

> SELECT O2.* FROM OrgChart AS O1, OrgChart AS O2 WHERE O1.lft BETWEEN
> O2.lft AND O2.rgt AND O1.emp = :myemployee;
>
> This is a pure set operation: Given all the nodes in the tree, I can
> apply the test (characteristic function) for membership in the result
> in parallel.

 >
> In the adjacency list model, you have to loop or recurse from the
> employee's node up the tree procedurally. You can try to hide the
> cursor in syntax, like the Oracle CONNECT BY .. PRIOR, but the
> natural of the model requires a sequential or recursive solution.

But *any* query requires a procedural solution at the lowest level. The point is that a DBMS can hide the procedural code internally so the user has only to use declarative code. We shouldn't have to worry about assigning arbitrary orders to our data; we want the DBMS to make life easy for us and do all the hard work.

Maybe there would be other advantages in "hiding" procedural code in a transitive closure operator. There might be an algebra of "relational + tclose" that could usefully simplify expressions for optimization.

Paul. Received on Thu May 13 2004 - 17:29:32 CDT