# Re: SQL, related records (quotes)

Date: Sun, 26 Jun 2005 10:57:27 +0200

Message-ID: <42be6df6$0$17620$e4fe514c_at_news.xs4all.nl>

Dan Guntermann wrote:

> mAsterdam wrote:

*>
*

>>Stefan Rybacki wrote: >> >>>mAsterdam wrote: >>> >>>>mAsterdam wrote: >>>> >>>>>Stefan Rybacki wrote: >>>>> >>>>>>mAsterdam wrote: >>>>>> >>>>>>>Jan Hidders wrote: <snip> >>>>>>>>Are you sure the relation describes always a tree? >>>>>>> >>>>>>>Values like >>>>>>>QuoteNo PreviousQuoteNo >>>>>>> 3 6 >>>>>>> 6 3 >>>>>>> >>>>>>>or just >>>>>>>QuoteNo PreviousQuoteNo >>>>>>> 3 3

> <snip>

>>>>>Consider adding these constraints: QuoteNo as key, >>>>>and PreviousQuoteNo as foreign key to QuoteNo. >>>>> >>>>>Only now we have the intended tree-consistency. >>>>>The circular states mentioned above are inconsistent with the >>>>>constraints, and I can't add these values by hand or by algorithm. >>>> >>>>Oops - still not good enough. >>> >>>It should be good enough for an insert but not for an update, or did I >>>forget something? >> >>Exactly. Now in this specific situation a check constraint, >>PreviousQuoteNo < QuoteNo, would do the trick (I hope am not still >>forgetting something). >> >>Is there a more generic way to get the wanted tree-garantuee? >>Sigh. No escape - I'll just have to buy Celko's book :-)

*>*

*>*

> I'll have to get Celko's book myself, I guess.

*>*

*> Ideally and abstractly, I think something like this would work:*

*>*

*> hierarchies(child_vertex *vertex*, parent_vertex *vertex*,*

*> CONSTRAINT primary_key (child_vertex),*

*> CONSTRAINT CHECK (child_vertex <> parent_vertex),*

*> CONSTRAINT CHECK ****ANTISYMMETRIC******> );*

*>*

A few questions:

1. Did you just forget the foreign key constraint

(child_vertex referencing parent_vertex) or did you leave it out for a purpose?

2. Both the '<>' and the ****ANTISYMMETRIC**** constraint serve to

establish that 'hierarchies' can just contain hierarchies (trees)
indeed.

What is special about the '<>' constraint? Shouldn't it be included
in the (as yet magical) ****ANTISYMMETRIC**** constraint?

3. Would ****NOLOOP*** (some other as yet magical constraint over

child_vertex and parent_vertex) suggest the same mechanics to you as ****ANTISYMMETRIC**** ?

4. (should have been the first Q to the OP - to late for that I guess:)

What does one tuple mean / what is the predicate for 'hierarchies'?

5. (Proposal, not really a question) Let's isolate the roots

(PS: later I saw that you already did just that)

> This ideal but unachievable representation would solve the problem and it

*> enforces:
**> * a single root vertex for any hierarchy.
**> * a single parent for any child vertex and allows for multiple children for
**> any parent.
**> * ensures an nonreflexive property and thus eliminates the self-referential
**> cyclic issue.
**> * eliminates the possibility of a cycle between a root and single child
**> with the antisymmetric constraint.
**> * eliminates the possibility for indirect cycles by virtue of the
**> constraint that any given vertex can only have one parent.
**>
**> But alas, not many implementations allow for assertions of antisymmetry,
**> though it could be done with a trigger.
*

Let's forget implementation for now and focus on minimal needs.

> This approach would enforce the

*> condition that
**> for all (child, parent) relationships that are members of hierarchies, there
**> does not exist a tuple of (parent, child). It also has the limiting factor
**> of disallowing single node hierarchies.
**>
**> Another possibility that is not quite as clean is to model the following. I
**> am using a bastardized notation of course:
**> roots(root_vertex *vertex*,
**> CONSTRAINT KEY root_vertex),
**> CONSTRAINT NOT EXISTS (select 'x'
**> FROM
**> hierarchies
**> WHERE
**> current.root_index = hierarchies.child_index);
**>
**> hierarchies(child_vertex *vertex*, parent_vertex *vertex,
**> CONSTRAINT primary_key (child_vertex),
**> CONSTRAINT CHECK (child_vertex <> parent_vertex),
**> CONSTRAINT NOT EXISTS (SELECT 'x'
**> FROM
**> roots
**> WHERE
**> roots.root_vertex = current.child_vertex),
**> CONSTRAINT EXISTS (SELECT 'x'
**> FROM
**> roots
**> WHERE
**> roots.root_vertex = current.parent_vertex
**>
**> AND NOT EXISTS (SELECT 'x'
**>
**> FROM roots r2
**>
**> WHERE r2.child_index =
**> current.parent_index) );
*

Hmm... the formatting makes this a tough read.

FROM roots WHERE roots.root_vertex = current.child_vertex

)no children are root. Ok.

EXISTS ( SELECT 'x' FROM roots

WHERE roots.root_vertex = current.parent_vertex)

all parents should be root? To restrictive.

To check we should have something like this:
A length 1 loop:

Values:

parent_vertex child_vertex 3 3

can't be in 'hierarchies', it will be rejected by 'CONSTRAINT CHECK (child_vertex <> parent_vertex)'. Good.

A length 2 loop:

Values:

parent_vertex child_vertex 3 6 6 3

can't be in 'hierarchies', it will be rejected by ???.

A length 3 loop:

Values:

parent_vertex child_vertex 3 6 6 7 7 3

can't be in 'hierarchies', it will be rejected by ???.

> The last constraints, which are DB constraints, of the tables would most

*> likely have to be implemented as a database constraint either with trigger
**> logic or by modeling manipulation within the scope of a transaction boundary
**> from the application side. This overcomes the obstacle that a hierarchy
**> could conceivably be composed of a single root node.
*

The non-hierarchy hierarchy.

Do I care wether it is in or out?

Let's take the easy road. Out.
Received on Sun Jun 26 2005 - 10:57:27 CEST