Re: Quote of the Week

--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     }

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

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.

>

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 Fri May 14 2004 - 00:29:32 CEST