Re: SQL, related records (quotes)

From: Dan Guntermann <>
Date: Sun, 26 Jun 2005 05:20:26 GMT
Message-ID: <uWqve.4681$B82.3905_at_trnddc04>

"mAsterdam" <> wrote in message news:42bc8c8b$0$42378$
> Stefan Rybacki wrote:

>> mAsterdam wrote:
>>> mAsterdam wrote:
>>>> Stefan Rybacki wrote:
>>>>> mAsterdam wrote:
>>>>>> Jan Hidders wrote:
>>>>>>> Stefan Rybacki wrote:
>>>>>>>> wrote:
>>>>>>>>> I have a website that users can request quotes, and a user may 
>>>>>>>>> also
>>>>>>>>> make a new quote that links to a previous quote.
>>>>>>>>> QuoteNo    PreviousQuoteNo
>>>>>>>>>      1
>>>>>>>>>      2
>>>>>>>>>      3                     1
>>>>>>>>>      4                     3
>>>>>>>>>      5                     4
>>>>>>>>> If i request quoteNo 3 i want to have a list of all the related 
>>>>>>>>> quotes.
>>>>>>>>> RelQuote
>>>>>>>>>      1
>>>>>>>>>      3
>>>>>>>>>      4
>>>>>>>>>      5
>>>>>>>>> Is this possible with a SQL statement? or would i be best doing a 
>>>>>>>>> loop
>>>>>>>>> in asp and many requests?
>>>>>>>> Try the nested sets model.
>>>>>>> Are you sure the relation describes always a tree?
>>>>>> Values like
>>>>>> QuoteNo    PreviousQuoteNo
>>>>>>       3           6
>>>>>>       6           3
>>>>>> or just
>>>>>> QuoteNo    PreviousQuoteNo
>>>>>>       3           3

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

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. 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'
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'
roots.root_vertex = current.child_vertex),
                   CONSTRAINT EXISTS (SELECT 'x'
roots.root_vertex = current.parent_vertex
                                     FROM roots r2
                                      WHERE r2.child_index = 
current.parent_index) );

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.

  • Dan
Received on Sun Jun 26 2005 - 07:20:26 CEST

Original text of this message