Обсуждение: uniquely indexing Celko's nested set model

Is it possible to constraint both the LEFT and RIGHT fields of a record to use the same index?  I am looking for a way
toensure for all LEFTs and RIGHTs in a table, that is it is impossible for any LEFT or RIGHT to have to same value. 

On 10/19/07, Richard Broersma Jr <rabroersma@yahoo.com> wrote:
> Is it possible to constraint both the LEFT and RIGHT fields of a record to use the same index?  I am looking for a
wayto ensure for all LEFTs and RIGHTs in a table, that is it is impossible for any LEFT or RIGHT to have to same value. 

a check constraint ought to do it

check (field1<>field2)

On Oct 19, 2007, at 7:37 PM, Scott Marlowe wrote:

> On 10/19/07, Richard Broersma Jr <rabroersma@yahoo.com> wrote:
>> Is it possible to constraint both the LEFT and RIGHT fields of a
>> record to use the same index?  I am looking for a way to ensure
>> for all LEFTs and RIGHTs in a table, that is it is impossible for
>> any LEFT or RIGHT to have to same value.
>
> a check constraint ought to do it
>
> check (field1<>field2)

That won't catch {1,2} {3,1}.

I don't think there's any way to have an index cover two fields in
that way. The only way I can see to do it with an index would be to
have each row of the OPs mental model to map onto two rows of the
table, along with a boolean saying whether the value was for a "left"
or a "right".

There's probably a much, much more elegant way to do it, but this
might work in an existence proof sort of way:

create table moststuff {
   id integer primary key,
   whatever text
};

create table leftright {
   a integer primary key,
   b integer references moststuff(id),
   lr text unique,
   constraint foo check (b = abs(a))
};

Cheers,
   Steve

--- On Fri, 10/19/07, Scott Marlowe <scott.marlowe@gmail.com> wrote:
> > Is it possible to constraint both the LEFT and RIGHT
> > fields of a record to use the same index?  I am looking for
> > a way to ensure for all LEFTs and RIGHTs in a table, that is
> > it is impossible for any LEFT or RIGHT to have to same
> > value.

> a check constraint ought to do it

True, but how do I insure that one record's left does not equal another record's right?

Regards,
Richard Broersma Jr.

On Oct 19, 2007, at 16:42 , Richard Broersma Jr wrote:

> Is it possible to constraint both the LEFT and RIGHT fields of a
> record to use the same index?  I am looking for a way to ensure for
> all LEFTs and RIGHTs in a table, that is it is impossible for any
> LEFT or RIGHT to have to same value.

You can define a check constraint to handle this:

CREATE OR REPLACE FUNCTION strict_nested_set_node_check(INTEGER,
INTEGER)
RETURNS BOOLEAN
STRICT IMMUTABLE SECURITY DEFINER
LANGUAGE SQL AS $_$
SELECT ((abs($1) < abs($2))
        AND ($2 - $1 - 1) % 2 = 0)
$_$;
COMMENT ON FUNCTION strict_nested_set_node_check(INTEGER, INTEGER) IS
'Convenience function to encapsulate the check conditions for the
lower and '
' upper bounds (often called ''left'' and ''right'') for strict
nested set '
'implementations.';

CREATE TABLE nodes
(
     node_id SERIAL PRIMARY KEY
     , node_lower INTEGER NOT NULL
     , node_upper INTEGER NOT NULL
     , UNIQUE (query_plan_id, node_lower)
     , UNIQUE (query_plan_id, node_upper)
     , CHECK (strict_nested_set_node_check(node_lower, node_upper))
);

To actually guarantee that each lower and upper value is only used
once, I think you'd need to write a trigger that checks that each
value is only used once. I haven't used such trigger when I've used
nested sets, however. If you handle your table modifications through
functions and test your functions thoroughly, you can be pretty sure
that your table updates aren't going to cause any duplication of this
time. Then again, maybe I should add the trigger to be on the safe
side :)

Michael Glaesemann
grzm seespotcode net

On 10/19/07, Richard Broersma Jr <rabroersma@yahoo.com> wrote:
> Is it possible to constraint both the LEFT and RIGHT fields of a record to use the same index?  I am looking for a
wayto ensure for all LEFTs and RIGHTs in a table, that is it is impossible for any LEFT or RIGHT to have to same value. 

I found the celko's approach to be not very scalable...if you do any
inserts at all into the tree the table will thrash terribly.  Have you
eliminated other approaches, such as arrays, ltree, etc?

merlin

On Oct 20, 2007, at 7:33 , Merlin Moncure wrote:

> On 10/19/07, Richard Broersma Jr <rabroersma@yahoo.com> wrote:
>> Is it possible to constraint both the LEFT and RIGHT fields of a
>> record to use the same index?  I am looking for a way to ensure
>> for all LEFTs and RIGHTs in a table, that is it is impossible for
>> any LEFT or RIGHT to have to same value.
>
> I found the celko's approach to be not very scalable...if you do any
> inserts at all into the tree the table will thrash terribly.  Have you
> eliminated other approaches, such as arrays, ltree, etc?

I believe it's a trade off: if you're doing a lot of aggregate work
and not very many updates, nested sets works very well: adjacency
lists aren't as good for this because of the necessity of following
the hierarchy from parent to child. If your hierarchy is updated
frequently, yes, you'll have a lot of thrashing as everything above
and to the left of the update must be updated as well. AFAIK, there
isn't currently a single best solution for representing trees in SQL.

Michael Glaesemann
grzm seespotcode net

--- On Sat, 10/20/07, Merlin Moncure <mmoncure@gmail.com> wrote:
> Have you eliminated other approaches, such as arrays, ltree, etc?

Actually I haven't considered using arrays to store hierarchal information. I've seen ltree mentioned from time to
time.Is it true that it works with adjacency list model? 

If the nested set model is chosen, would having a table and index fill factor of 50% be a good idea in this case if
periodicupdates were expected? 

Regards,
Richard Broersma Jr.

On Oct 20, 2007, at 21:24 , Richard Broersma Jr wrote:

> I've seen ltree mentioned from time to time. Is it true that it
> works with adjacency list model?

I don't believe so. I think it's path-based, but you can check it out
for yourself in contrib/


> If the nested set model is chosen, would having a table and index
> fill factor of 50% be a good idea in this case if periodic updates
> were expected?

"fill factor" wrt nested set means not using consecutive numbering of
the bounds, leaving space for inserted nodes. Table rewrites might be
necessary from time to time as inserts fill in the gaps. You could
also do nested sets using numeric rather than integer, which gives
you a lot more flexibility.

Michael Glaesemann
grzm seespotcode net