Re: SQL, related records (quotes)

From: mAsterdam <mAsterdam_at_vrijdag.org>
Date: Sun, 26 Jun 2005 10:57:27 +0200
Message-ID: <42be6df6$0$17620$e4fe514c@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

    (and get rid of the NULLs).

    (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.

NOT EXISTS ( SELECT 'x'

   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 - 03:57:27 CDT