# Re: SQL, related records (quotes)

Date: Sun, 26 Jun 2005 05:20:26 GMT

Message-ID: <uWqve.4681$B82.3905_at_trnddc04>

"mAsterdam" <mAsterdam_at_vrijdag.org> wrote in message
news:42bc8c8b$0$42378$e4fe514c_at_news.xs4all.nl...

> Stefan Rybacki wrote:

>> mAsterdam wrote: >>> mAsterdam wrote: >>>> Stefan Rybacki wrote: >>>>> mAsterdam wrote: >>>>>> Jan Hidders wrote: >>>>>>> Stefan Rybacki wrote: >>>>>>>> timpea_at_gmail.com 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 >>>>>>

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

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' FROM hierarchies WHEREcurrent.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) );

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