Re: SQL, related records (quotes)

From: mAsterdam <mAsterdam_at_vrijdag.org>
Date: Mon, 27 Jun 2005 01:02:41 +0200
Message-ID: <42bf3410$0$50339$e4fe514c_at_news.xs4all.nl>


Dan Guntermann wrote:
> mAsterdam wrote:
>>Dan Guntermann wrote:
<snip>
>>>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.

If and when it's time for that.

I think we have a nice example of a trap here: genericity of solutions at the cost of ditching the original problem.

For the original problem there was a solution where three contstraints did the trick for the whole problem, including its hierarchy:
A key, a fk and a check <.

The < constraint seemed overly specific and coincidental (no dispute here).
So we zoomed in on the hierarchy-issue with a more generic approach.

Let's say for the hierarchy itself we decide on a solution without FK.

After that we should go back to the original problem and see how this fits in.
There are nodes which are not part of the hierarchy. We might call them non-hierarchy hierarchies or create a base table for all nodes (this _would_ of course require FK's) - whatever, we have to do _something_ more to apply our findings from the generic solution.

To avoid the trap, next we should look at the alternative solutions as a whole and compare them.
Our final choice may have FK's. Or not. For now I don't care. It may have a generic approach to hierarchy. Or not.

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

In this approach, I see no need for a foreign key.

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

Ok.

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

It would be a *good* thing if the neccesary constraints would be easily expressed and explained.

> BTW, an 
> irreflexive property is intended to do exactly the opposite of you 
> interpretation.  

Which of my interpretations are you referring to? Seriously: I did a lot of guesswork in this thread (example: from the column names of the OP I guessed he wouldn't like the loops^H^H^H^H^H cycles in the values, below is another example).

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

Confusing indeed - or confused? How can this, "The root is a vertex that has no parent by definition", be and also "a certain case ... a child can be the parent of the root." ?

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

Yes. In the specific solution the 'check <' catered for the irreflexiveness, using the order of the original population. ACYCLIC is ok with me. Would it do the trick? - ah you (or I) snipped that bit ;-)

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

There can be, sure.
Consider these pairs:

structure - substance
form      - meaning
syntax    - semantics

and these triplets:

structure - substance - body
form      - meaning   - usage
syntax    - semantics - pragmatics

> What is an ER diagram then?

A graph, depicting central concepts and the associations between them.

But the question should actually be for the OP. For him it is not hard at all.
What does one tuple mean?

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

Ok. Please rephrase tables and constraints to your current insights somewhat clearly and I'll try to test it. (Some patience please, I have a rather busy next week)

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

I might. Worse: I was guessing.

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

Now I don't know. At that time I guessed "A root node is a node which has itself as parent" because with that I could make the most sense of the surrounding statements. What was it?

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

O, but I _do_ mind. You might have noticed. Received on Mon Jun 27 2005 - 01:02:41 CEST

Original text of this message