Re: SQL, related records (quotes)

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

Relevant Pages

  • Re: [RFC][PATCH 1/2] memcg: res_counter hierarchy
    ... While several policy of hierarchy can be considered, ... create a child. ... prepare enough room in parent. ... One way to manage hierarchies other than via limits is to use shares (please see ...
    (Linux-Kernel)
  • Re: Re: [RFC][PATCH 1/2] memcg: res_counter hierarchy
    ... While several policy of hierarchy can be considered, ... there are no shared resource ... create a child. ... prepare enough room in parent. ...
    (Linux-Kernel)
  • [RFC][PATCH 1/2] memcg: res_counter hierarchy
    ... This patch tries to implements _simple_ 'hierarchy policy' in res_counter. ... dynamic hierarchy resource usage management in the kernel is not necessary ... create a child. ... prepare enough room in parent. ...
    (Linux-Kernel)
  • Re: multi-level hierarchical structure
    ... existing ones later) but they do need to represent the hierarchy. ... You will probably want a query that gives these and Ranks them. ... no parent. ... It needs a root. ...
    (microsoft.public.access.tablesdbdesign)
  • object hierarchy, parent-child links, etc
    ... I am trying to construct an object hierarchy for some relatively simple ... objects I am trying to expose to COM / Automation for use in scripting. ... in which the parent has one statically-created child member. ...
    (microsoft.public.vc.atl)