Re: Bill of materials / Groups in Groups

joe_celko_at_my-deja.com wrote in message <86a0gg$67o$1_at_nnrp1.deja.com>...
>
>>> OK, I've refreshed my memory on Domain-Key Normal Form, as presented
>in Atzeni & DeAntonellis ... definition is that you can always
>delete any tuple from the relation without making it inconsistent ... <<
>
>Bingo! Let's do the nested set table out in its full glory:
>
>CREATE TABLE OrgChart
> (emp CHAR(10) PRIMARY KEY,
> lft INTEGER NOT NULL UNIQUE CHECK (lft > 0),
> rgt INTEGER NOT NULL UNIQUE CHECK (rgt > 1),
> CONSTRAINT subset_definition
> CHECK (lft < rgt),
> CONSTRAINT subordination
> CHECK ((rgt-lft +1)/2
> = (SELECT COUNT(*)
> FROM OrgChart AS C1
> WHERE C1.lft BETWEEN OrgChart.lft AND OrgChart.rgt))
> );
>
>We could also add a minimal numbering constraint and enforce it with a
>trigger, but it is not vital:
>
> CONSTRAINT no-gaps
> CHECK (2 * (SELECT COUNT(*) FROM OrgChart)
> = (SELECT MAX(rgt) FROM OrgChart))

DKNF allows you to express constraints in only two ways: 1) Domain constraints -- "the value in attribute A must belong to the domain D"; 2) Key constraints -- "the attributes A1, ..., An form a key for the relation".

Your constraints "subset_definition" and "subordination" are not in either of those two forms, and I can't see how they could be expressed as conjunctions of constraints of those two forms.

It follows that this relation is not in DKNF.

>Now use the old data again:
>
> OrgChart
> emp lft rgt
> ==================
> Albert 1 12
> Bert 2 3
> Chuck 4 11
> Donna 5 6
> Eddie 7 8
> Fred 9 10
>
> which 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)
>
>
>Delete Chuck in the nested set model and Donna, Eddie and Fred are
>still subordinates of Albert. Delete Chuck in the adjacency list model
>and Donna, Eddie and Fred are separate trees in a forest, with no
>relationship to Albert!

Rather: Delete Chuck in the nested set model and the database engine will issue an error and roll back your transaction! After all, deleting the tuple (Chuck, 4, 11) from the data listed above results in a data set that does not satisfy the constraints you listed. According to the definition of DKNF, this qualifies as a "deletion anomaly": you have a consistent data set which becomes inconsistent if you remove a row from it.

The nested set model works ONLY if you write complex stored procedures to do all of your updates, and you allow the procedures to temporarily violate the constraints of the relation. This is fine from a practical standpoint, and can be done effectively with today's DBMSs. However, it does NOT satisfy the definition of DKNF.

Moreover, if you define a normalized database to be one where integrity can be maintained as long as all updates are carried out by a specified set of stored procedures, then I can make virtually ANY database design be "normalized" simply by writing the appropriate stored procs. I won't repeat the example here, but I think I made this point clearly in my post on 1/13/00 when I showed how you could store employees, department ids and department names all in the same relation. I could certainly write stored procedures to maintain integrity in the adjacency model. That would allow me to delete Chuck and maintain Donna, Eddie and Fred's relationships to Albert, never creating a "forest".

I still don't believe that there's any definition of normalization according to which the nested set model is normalized while the adjacency model is not. Received on Fri Jan 21 2000 - 00:00:00 CET