Oracle FAQ | Your Portal to the Oracle Knowledge Grid |
Home -> Community -> Usenet -> comp.databases.theory -> Re: SQL, related records (quotes)
Dan Guntermann wrote:
> <snip>
>
>>>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**** >>> ); >> >>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?
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.
> 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?
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.
>>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?
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.
> 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?
> All other vertices of the hierarchy will be immune to such a condition
> because each child is defined in terms of its relationship with a parent
> and, by definition, the number of arrows representing a directed
> parent-child relationship and thus pointing into child is limited to one (as
> enforced by the key).
>
> example1: child parent
> B A
> C A
> A B <-- cyclic (symmetric)
> relationship
>
> example2 B A
> C A
> D B
> B D XXXX <-- can't happen,
> because of the key
> constraint.
>
> Nor can a leaf node or an intermediate branch node reference higher level
> vertices as children.
>
> As Mr. Rybacki points out, a relation is antisymmetric <=> for all x, y in
> some domain, if x R y and y R x, then x = y. The antisymmetric constraint
> will disallow the extensional relation given in previous posts:
>
> child parent
> 3 6
> 6 3
>
> Why? Because the DBMS will see that <child: 3, parent 6> exists and that if
> <child: 6, parent: 3> were allowed to be inserted, the assertion of
> antisymmetry would not hold because 6 <> 3, and thus the DBMS would reject
> the insertion on the basis of the ANTISYMMETRIC constraint.
>
>
>>3. Would ****NOLOOP*** (some other as yet magical constraint over >> child_vertex and parent_vertex) suggest the same mechanics >> to you as ****ANTISYMMETRIC**** ?
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.
> 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'?
This is structure, not meaning.
> The table constraints are really meta constraints across multiple tuples to
> enforce structure over the hierarchy.
Yep.
>>5. (Proposal, not really a question) Let's isolate the roots >> (and get rid of the NULLs). >> >> (PS: later I saw that you already did just that) >>
>>>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. >> >>Let's forget implementation for now and focus on minimal needs. >>
>>Hmm... the formatting makes this a tough read. >>
>>NOT EXISTS ( SELECT 'x' >> FROM roots WHERE roots.root_vertex = current.child_vertex ) >>no children are root. Ok. >> >> >>EXISTS ( SELECT 'x' FROM roots >> WHERE roots.root_vertex = current.parent_vertex) >> >>all parents should be root? To restrictive. >>
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?
>>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 >> ???.
This complication sounds like a consequence of the (arbitrarily chosen) root definition.
> In that case, the ANTISYMMETRIC constraint should ensure that that special
> case does no occur.
>
>
>>A length 3 loop: >>Values: >> parent_vertex child_vertex >> 3 6 >> 6 7 >> 7 3 >>can't be in 'hierarchies', it will be rejected by >> ???.
>>>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. >> >>The non-hierarchy hierarchy. >>Do I care wether it is in or out? >>Let's take the easy road. Out.
Ever heard of YAGNI? KISS, so neglect it unless you specifically aim for "modeling a B*Tree or something similar" - are you? Received on Sun Jun 26 2005 - 14:20:02 CDT