Re: SQL, related records (quotes)

From: Dan Guntermann <guntermann_at_verizon.net>
Date: Sun, 26 Jun 2005 20:31:11 GMT
Message-ID: <jgEve.6139$B82.69@trnddc04>

"mAsterdam" <mAsterdam_at_vrijdag.org> wrote in message news:42beffe2$0$32835$e4fe514c_at_news.xs4all.nl...
> Dan Guntermann wrote:

>> <snip>
>>
<snip>

>>>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?
>>
>> No nulls in my model.
>

> Ok with me. As a consequence we need a model change,
> maybe more tables. Anyway we are changing the model.
> (In the OP's question there where quotes _without_
> previous quotes)

> So which FK are we talking about now?

>
>> I don't believe an FK is necessary,
>

> Maybe, maybe not. It depends on the - yet to be defined - new model.

I'll leave it to you to demonstrate why it is necessary.

>
>> and with some implementations could not be achievable.  I could be 
>> convinced otherwise, but consider the following:
>>
>> child    parent
>>   B         A
>>
>> how would one insert this tuple with the FK established?  What would B 
>> reference?
>>
>> Moreover, the model I was conceptualizing would allow for multiple 
>> hierarchies.
>

> Does that matter?

Well, yes. Look at the example again and tell me what parent you intend child B to reference for referential integrity and what meaning the reference would have. This FK is not universal across the relation and therefore would enforce conditions that are not desireable nor within the definition of a hierarchy.

> Multiple trees are easily mapped to branches of one root
> node, so whichever is easiest (one or more trees) is easily used
> for the other - or are you talking about multiple hierarchies over
> the same nodes? I don't think so.

Yes, I am not talking about sharing vertices among hierarchies in this case. Hierarchies are self-contained and mutually exclusive here.

>
>>>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?
>>
>> I think Mr. Rybacki begs to differ, but I had the following rationale:
>>
>> Starting with an empty relation with just a key constraint on 'child', 
>> the following would be allowable, but undersireable:
>>
>> child     parent
>>   A          A
>>
>> Thus, to guarantee the nonreflexive property of a hierarchy, the 
>> constraint is need to guarantee all cases.  Note that this is only 
>> possible with a vertex involving itself as a root node of a hierarchy. 
>> It is not possible for child vertexes by virtue of the key constraint 
>> since they already exist in conjunction with a single parent vertex.
>

> It never stops bugging me how many arbitrary choices one has to make to
> put trees - or even just order - into tables). It seems you define a root
> as a node which has itself as a parent, right? That is one, not uncommon,
> way of dealing with this, but not the only way.

I don't know why it bothers you. A hierarchy is a special case of a graph with special rules that can be logically expressed. It's not a *bad* thing, it's just a matter of expressing and enforcing the constraints. BTW, an irreflexive property is intended to do exactly the opposite of you interpretation. For all vertices in the hierarchy, there does not exist a vertex that is related to itself (including root vertices), but you are right in that it is possible as an approach and it is not the only possible approach.

>
>> To address the issue of antisymmetry, I should identify the conditions 
>> where I think it such a constraint would be pertinent.  Direct cycles are 
>> not an issue anywhere but for a certain case, and that is in the case 
>> where a root can be associated with a child and a child can be the parent 
>> of the root.
>

> Is this just a way of restating the root definition?

No. The root is a vertex that has no parent by definition and a hierarchy is asymmetric by definition. I mentioned the case where a single candidate key on child would be insufficient as a counter-example, but this seems to have been confusing.

<snip>

>>
>>
>> ???  I'm not sure what NOLOOP would do.
>

> Something like this:
> It would not allow loops. A loop being a set of vertices, where there
> exists a vertex A being both child and ancestor of a vertex B (which may,
> of course be A).

>
> It does not play well with having root as parent of itself, though.

Perhaps ACYCLIC is a good term? Give the hierarchies relation H, an acyclic constraint would allow for the transitive closure of H, H', such that H' is also irreflexive, no?

>
>> Properties of relations such as symmetry, reflexivity, and transitivity 
>> are states of relations that are very well defined.
>>
>>
>>>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'?
>>
>>
>> Well, in my little encapsulated world, it can represent several types of 
>> conceptual objects, or specific aspects of hierarchy, really.
>> Possibility:
>> Child Vertex: X of type *vertex* has one and only one Parent Vertex: Y of 
>> type *vertex*
>>   AND (informally) Child Vertex: X belongs to only one edge as the child 
>> and therefore has only one parent
>>   AND (informally) if the Child Vertex = X, then Parent Vertex <> X
>>   AND (informally) there should never be the case where EXISTS 
>> (child_vertex: X, parent_vertex Y) AND (child_vertex: Y, parent_vertex: 
>> X)
>>              AND (child vertex: X <> parent_vertex: Y).
>

> This is structure, not meaning.

I am not aware of a concrete distinction. Is there no meaning in describing structure, relationships, and constraints? What is an ER diagram then?

>
>> The table constraints are really meta constraints across multiple tuples 
>> to enforce structure over the hierarchy.
>

> Yep.

>
>>
>> The formatting was tough, I know.  I'll rewrite the constraint in its 
>> entirety here:
>>
>> 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) );
>>
>> Basically, the intent is to only allow a tuple to be inserted into the 
>> hierarchies relation if the proposed parent vertex value does not already 
>> exist as a child and its value has been previously inserted as a value in 
>> the roots relation.
>

> The intent is clear and common - I think.
> That makes it more annoying that it is so
> difficult to come up with a good set of constraints.
> I'm puzzled wether the above does what it is supposed to do.
> Did you test it?

No I didn't, but you are welcome to. I certainly don't mind the scrutiny.

>
>>>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
>>> ???.
>>
>> It will be rejected by the candidate key for almost all cases except for 
>> the possibility of such a case happening between a root and one of its 
>> children.
>

> This complication sounds like a consequence
> of the (arbitrarily chosen) root definition.

You might have misunderstood. Moreover, I don't think the definition was arbitrarily chosen. Out of curiousity, what do you think my definition was?

<snip>

>
>>>The non-hierarchy hierarchy.
>>>Do I care wether it is in or out?
>>>Let's take the easy road. Out.
>>
>> Makes sense.  However, one might be neglecting some useful applications 
>> (e.g. modeling a B*Tree or something similar).
>

> Ever heard of YAGNI? KISS, so neglect it unless you specifically aim for
> "modeling a B*Tree or something similar" - are you?

*sigh*.... Never mind.

Received on Sun Jun 26 2005 - 15:31:11 CDT