Re: Tree structure in Relational DB design

>>It is likely that renumbering might not be a significant issue in
the average
practical case. <<

Based on my email,that seems to be true ... so far <g>

>> However, it is extremely dubious what happens in conditions of
concurrency if several distinct connections attempt an operation that trigger the renumbering. <<

This is why people with a heavy update requirement use large gaps in the numbers; the message board in my second post is such an example.

Simply the fact that a simple update or

>> However, I must take issue with your strange idea of what
"normalized"
means. By your account, any schema whatsoever that has a foreign key is denormalized, because if one updates the primary key or deletes the record altogether, the effects would have to be propagated in all the places. <<

Or the action prevented. That is not what I am trying to say. In Domain-Key Normal Form, the important thing is that after every insert/update/delete, all of the constraints are true and all of the invariant relationships still hold. In the adjacency list model, when I drop the row with 'Chuck', I also destroy the fact that 'Albert' was in the chain of command to all of Chuck's subordinates; this does not happen in a nested set model.

>> Yep, only 38 digits precision. Should be enoiugh though for many
trees <<

LOL! Or a forest.

>> However they are said to be normalized . Could we agree at least
that a table in 5NF is said to be normalized ? <<

I am very happy to get to 5NF, since most of the real world is lucky to be in 3NF.

>> Following your logic no schema ever designed by Celko was
normalized because I'm sure it must have contained at least one foreign key. And if we try to update/delete the master record we run into trouble. <<

The problem here is that the PK-FK is a self-referencing relationship.  If the self-reference is really checked by the database engine, I can only delete leaf nodes from the tree because they will not leave "dangling subordinates" in the table.

"Fire only the peons!" might be a business rule, but I want to be able to fire the managers, too.

>> Well, I was asking precisely for the definiton of a normal form
(1,2,3,4,5 you choose) and how OrgChart breaks it, this you fail to produce. <<

I would say we are in Domain-Key Normal Form problems with this one. The reason is that inheritance of subordination is a global invariant in a heirarchy, which puts it at the table level rather than the row level.

>> For example, how would you model in a relational database the grid
of
an electronic circuit whith the constraint that the grid must be at any given time a planar graph ? <<

I have never found a good way to do graphs in SQL. I keep falling back to an adjacency list model for the general graph. I cannot remember the conditions for a planar graph -- K(5,5) is the simplest non-planar graph? Too many years between math courses ...

>> ... if I insert a node under a "leftish" node in your nested set
model, I'd generate lots of invalid facts (a big part of the tree would need to be renumbered). <<

I have alway said this is the weak spot -- you are actually creating a totally new relationship when you change the structure.

>> The sad truth is that practitioners are unaware of what 5NF is, and
the "apparent" difficulty of the 5NF is use a scarecrow. The reality is that once one reaches the BCNF (most would rweach BCNF instictively because schemas that violate BCNF, usually are easy to tell just by common sense) there is absolutely no reason whatsoever not to have it in 5NF. <<

Agreed.

>> ... It is amusing though how practitioners are scared by 5NF as if
it would be something out of ordinary that would be required of them. <<

something out of ordinary = Thinking? Reading a book? Using a CASE tool? all of the above <g>

>> A describing attribute of an entity may be its relation with
another entity.
For example in a Employey table you might have a DeptNo attribute without any need whatsoever to maintain this relationship in a separate table. <<

Call that realtionship table "JobAssignments", I guess. But even if I don't have "JobAssignments", I would like to know that the department number is valid in its own right, not something like "666 = Enron's Accounting Ethics Department" -- a CHECK() clause would be fine. Then I'd like to be sure that the right person is in the right department.

>> Encoding trees as nested set is a clever mathematical artifice, I
grant you that, but is not the essence of the facts that we need to model. It is merely an encoding, and the update anomalies are a reflection of that. <<

It is the best I can do with the tools I have ... Received on Tue Jun 11 2002 - 20:02:44 CEST