Обсуждение: A few questions about ltree

Yesterday ltree was mentioned to be a good system for tree structured
table data. I and a colleague of mine have been playing around with the
examples and the (rather sparse) documentation, but we're stuck on a few
questions...

How does one guarantee referential integrity using ltrees? It doesn't
seem to do so by itself, but can it refer a parent node directly?

We assume you can do this:

CREATE TABLE my_tree (
    path ltree PRIMARY KEY,
    parent ltree REFERENCES my_tree(path)
);

In this case a tree would look something like:
parent | path
--------------------------
(NULL) | A
A | A.B
A.B | A.B.D
A | A.C

That's the "classical" way, which is also used in our current
implementation with integers instead of ltrees, but it's not very easy
to query efficiently (at least ordering seems to remain a problem).

Maybe something along the lines of the following is possible?:

CREATE TABLE my_tree (
    path ltree PRIMARY KEY REFERENCES my_tree(path)
);

Data would look like:
path
-----------------------
A
A.B
A.B.D
A.C

With A.B and A.C referencing A in their parent record and A.B.D
referencing A.B

What I like about this solution is that only one ltree path per node is
required, and that the root node doesn't need a parent reference. The
question is whether this is/can-be-made possible...

Do ltrees know that a node with path 'A.B.D' references it's parent
'A.B'? I mean, can ltree 'A.B' equal ltree 'A.B.D' somehow while the
strings are unequal?
Can it be made to know that somehow (functional foreign keys or
something - maybe using "ltree_isparent(ltree, ltree)")?

I can determine things like this with a few experiments, but I want to
know "the right way" to work with ltrees and referential integrity. How
do people use this?

--
Alban Hertroys
alban@magproductions.nl

magproductions b.v.

T: ++31(0)534346874
F: ++31(0)534346876
M:
I: www.magproductions.nl
A: Postbus 416
    7500 AK Enschede

// Integrate Your World //

> That's the "classical" way, which is also used in our current
> implementation with integers instead of ltrees, but it's not very easy
> to query efficiently (at least ordering seems to remain a problem).

That (with integer ids) is classic way to support graph structure, ltree was
develop specially for trees.


> Maybe something along the lines of the following is possible?:
Exact, it's for what ltree was developed.

> Do ltrees know that a node with path 'A.B.D' references it's parent
> 'A.B'? I mean, can ltree 'A.B' equal ltree 'A.B.D' somehow while the
> strings are unequal?
> Can it be made to know that somehow (functional foreign keys or
> something - maybe using "ltree_isparent(ltree, ltree)")?

Yes, use ltree_isparent or

contrib_regression=# select 'a.b.c' <@ 'a.b'::ltree;
  ?column?
----------
  t
(1 row)

contrib_regression=# select 'a.b.c.d' <@ 'a.b'::ltree;
  ?column?
----------
  t
(1 row)
contrib_regression=# select 'a.b.c.d'::ltree ~ 'a.b.*{1}';
  ?column?
----------
  f
(1 row)

contrib_regression=# select 'a.b.c'::ltree ~ 'a.b.*{1}';
  ?column?
----------
  t
(1 row)


>
> I can determine things like this with a few experiments, but I want to
> know "the right way" to work with ltrees and referential integrity. How
> do people use this?

That's right way.

--
Teodor Sigaev                                   E-mail: teodor@sigaev.ru
                                                    WWW: http://www.sigaev.ru/

Teodor Sigaev wrote:
>> Maybe something along the lines of the following is possible?:
>
> Exact, it's for what ltree was developed.

Cool, looks like it is what I need then.

> contrib_regression=# select 'a.b.c' <@ 'a.b'::ltree;
>  ?column?
> ----------
>  t
> (1 row)

How would you use this to constrain a foreign key?

We've been experimenting with a table containing a branch 'a', 'a.b' and
'a.b.c', but deleting 'a.b' didn't cause a constraint violation.

SQL> CREATE TABLE ltree_test (path ltree PRIMARY KEY REFERENCES
ltree_test(path));
NOTICE:  CREATE TABLE / PRIMARY KEY will create implicit index
"ltree_test_pkey" for table "ltree_test"
CREATE TABLE
SQL> INSERT INTO ltree_test VALUES ('a'::ltree);
INSERT 84117368 1
SQL> INSERT INTO ltree_test VALUES ('a.b'::ltree);
INSERT 84117369 1
SQL> INSERT INTO ltree_test VALUES ('a.b.c'::ltree);
INSERT 84117370 1
SQL> DELETE FROM ltree_test WHERE path = 'a.b'::ltree;
DELETE 1
SQL> select * from ltree_test;
  path
-------
  a
  a.b.c
(2 rows)

Is there some obvious/easy way to prevent this?

Regards,
--
Alban Hertroys
alban@magproductions.nl

magproductions b.v.

T: ++31(0)534346874
F: ++31(0)534346876
M:
I: www.magproductions.nl
A: Postbus 416
    7500 AK Enschede

// Integrate Your World //

> We've been experimenting with a table containing a branch 'a', 'a.b' and
> 'a.b.c', but deleting 'a.b' didn't cause a constraint violation.
>
> SQL> CREATE TABLE ltree_test (path ltree PRIMARY KEY REFERENCES
> ltree_test(path));
> NOTICE:  CREATE TABLE / PRIMARY KEY will create implicit index
> "ltree_test_pkey" for table "ltree_test"
> CREATE TABLE
> SQL> INSERT INTO ltree_test VALUES ('a'::ltree);
> INSERT 84117368 1
> SQL> INSERT INTO ltree_test VALUES ('a.b'::ltree);
> INSERT 84117369 1
> SQL> INSERT INTO ltree_test VALUES ('a.b.c'::ltree);
> INSERT 84117370 1
> SQL> DELETE FROM ltree_test WHERE path = 'a.b'::ltree;
> DELETE 1
> SQL> select * from ltree_test;
>  path
> -------
>  a
>  a.b.c
> (2 rows)
>
> Is there some obvious/easy way to prevent this?

Sorry, only by using triggers on insert/delete/update.

If it was a possible to use function in foreign key then it might looks as
create table foo (
     path ltree not null
);

insert into foo values (''); -- root of tree, but it unremovable...

create unique index path_foo_idx on foo ( path ); -- BTree index for constraint

alter table foo add foreign key subpath( path, 0, -1) references foo( path )
     deferrable initially deferred,;

But it's impossible...


--
Teodor Sigaev                                   E-mail: teodor@sigaev.ru
                                                    WWW: http://www.sigaev.ru/

Teodor Sigaev wrote:
>
>> We've been experimenting with a table containing a branch 'a', 'a.b'
>> and 'a.b.c', but deleting 'a.b' didn't cause a constraint violation.
>>
>> SQL> CREATE TABLE ltree_test (path ltree PRIMARY KEY REFERENCES
>> ltree_test(path));

> Sorry, only by using triggers on insert/delete/update.

Aw, that's a shame... Well, I do have quite a bit of experience writing
triggers (been working on an avalanche of cascading triggers - works
wonderfully), so that's not really a problem.

It does make me wonder though, the foreign key reference was created ok,
but does it do anything this way? I suspect it does, this isn't MySQL
after all :P

> If it was a possible to use function in foreign key then it might looks as
> create table foo (
>     path ltree not null
> );
>
> insert into foo values (''); -- root of tree, but it unremovable...

Is it really necessary to insert an 'empty' record for the root node?
The 'a' record from my experiments seems to be quite suited for the
task, unless I'm missing something.

> alter table foo add foreign key subpath( path, 0, -1) references foo(
> path )
>     deferrable initially deferred,;

IIRC, you can define equality for custom types depending on the
direction of the comparison. Isn't something like that possible for
foreign keys? You'd be able to check whether the left hand of the
comparison is a parent of the right hand and vice versa. That'd be just
what we need...

I must be missing something, you've obviously put a lot of thought in
ltree. Maybe it'll be possible with a future version of PostgreSQL :)

Regards,
--
Alban Hertroys
alban@magproductions.nl

magproductions b.v.

T: ++31(0)534346874
F: ++31(0)534346876
M:
I: www.magproductions.nl
A: Postbus 416
    7500 AK Enschede

// Integrate Your World //

On Fri, 21 Apr 2006, Alban Hertroys wrote:

> Teodor Sigaev wrote:
> >> Maybe something along the lines of the following is possible?:
> >
> > Exact, it's for what ltree was developed.
>
> Cool, looks like it is what I need then.
>
> > contrib_regression=# select 'a.b.c' <@ 'a.b'::ltree;
> >  ?column?
> > ----------
> >  t
> > (1 row)
>
> How would you use this to constrain a foreign key?
>
> We've been experimenting with a table containing a branch 'a', 'a.b' and
> 'a.b.c', but deleting 'a.b' didn't cause a constraint violation.
>
> SQL> CREATE TABLE ltree_test (path ltree PRIMARY KEY REFERENCES
> ltree_test(path));
> NOTICE:  CREATE TABLE / PRIMARY KEY will create implicit index
> "ltree_test_pkey" for table "ltree_test"
> CREATE TABLE
> SQL> INSERT INTO ltree_test VALUES ('a'::ltree);
> INSERT 84117368 1
> SQL> INSERT INTO ltree_test VALUES ('a.b'::ltree);
> INSERT 84117369 1
> SQL> INSERT INTO ltree_test VALUES ('a.b.c'::ltree);
> INSERT 84117370 1
> SQL> DELETE FROM ltree_test WHERE path = 'a.b'::ltree;
> DELETE 1

I'm not sure why you expect this to error. Any row that would reference
a.b would be removed by the delete AFAICS.

Stephan Szabo wrote:
>>SQL> CREATE TABLE ltree_test (path ltree PRIMARY KEY REFERENCES
>>ltree_test(path));
>>NOTICE:  CREATE TABLE / PRIMARY KEY will create implicit index
>>"ltree_test_pkey" for table "ltree_test"
>>CREATE TABLE
>>SQL> INSERT INTO ltree_test VALUES ('a'::ltree);
>>INSERT 84117368 1
>>SQL> INSERT INTO ltree_test VALUES ('a.b'::ltree);
>>INSERT 84117369 1
>>SQL> INSERT INTO ltree_test VALUES ('a.b.c'::ltree);
>>INSERT 84117370 1
>>SQL> DELETE FROM ltree_test WHERE path = 'a.b'::ltree;
>>DELETE 1
>
> I'm not sure why you expect this to error. Any row that would reference
> a.b would be removed by the delete AFAICS.

Nope, there's no ON DELETE CASCADE on the FK, and RESTRICT is the
default (thankfully).

But the FK constraint apparently doesn't get triggered by the delete, so
neither case matters much here.

--
Alban Hertroys
alban@magproductions.nl

magproductions b.v.

T: ++31(0)534346874
F: ++31(0)534346876
M:
I: www.magproductions.nl
A: Postbus 416
    7500 AK Enschede

// Integrate Your World //

> Is it really necessary to insert an 'empty' record for the root node?
> The 'a' record from my experiments seems to be quite suited for the
> task, unless I'm missing something.

The root should be and it will be unremovable, because of foreign keys. But it
can be, of course, not empty.


>
>> alter table foo add foreign key subpath( path, 0, -1) references foo(
>> path )
>>     deferrable initially deferred,;
>
> IIRC, you can define equality for custom types depending on the
> direction of the comparison. Isn't something like that possible for
> foreign keys? You'd be able to check whether the left hand of the
> comparison is a parent of the right hand and vice versa. That'd be just
> what we need...

Sorry, I don't know. I don't think that pgsql allows to use particular operator
for foreign key...


>
> I must be missing something, you've obviously put a lot of thought in
> ltree. Maybe it'll be possible with a future version of PostgreSQL :)
Make a patch to allow function in FK :)

--
Teodor Sigaev                                   E-mail: teodor@sigaev.ru
                                                    WWW: http://www.sigaev.ru/

On Fri, 21 Apr 2006, Alban Hertroys wrote:

> Stephan Szabo wrote:
> >>SQL> CREATE TABLE ltree_test (path ltree PRIMARY KEY REFERENCES
> >>ltree_test(path));
> >>NOTICE:  CREATE TABLE / PRIMARY KEY will create implicit index
> >>"ltree_test_pkey" for table "ltree_test"
> >>CREATE TABLE
> >>SQL> INSERT INTO ltree_test VALUES ('a'::ltree);
> >>INSERT 84117368 1
> >>SQL> INSERT INTO ltree_test VALUES ('a.b'::ltree);
> >>INSERT 84117369 1
> >>SQL> INSERT INTO ltree_test VALUES ('a.b.c'::ltree);
> >>INSERT 84117370 1
> >>SQL> DELETE FROM ltree_test WHERE path = 'a.b'::ltree;
> >>DELETE 1
> >
> > I'm not sure why you expect this to error. Any row that would reference
> > a.b would be removed by the delete AFAICS.
>
> Nope, there's no ON DELETE CASCADE on the FK, and RESTRICT is the
> default (thankfully).

The only row that matches 'a.b' that I see in the above is the second
insert which is also the row that is deleted in the delete. And since the
constraint uses equality, any row that matches path='a.b' is a target of
the delete because it's the same operator.

Stephan Szabo wrote:
> On Fri, 21 Apr 2006, Alban Hertroys wrote:
>>Stephan Szabo wrote:
>>
>>>>SQL> CREATE TABLE ltree_test (path ltree PRIMARY KEY REFERENCES
>>>>ltree_test(path));
>>>>NOTICE:  CREATE TABLE / PRIMARY KEY will create implicit index
>>>>"ltree_test_pkey" for table "ltree_test"
>>>>CREATE TABLE
>>>>SQL> INSERT INTO ltree_test VALUES ('a'::ltree);
>>>>INSERT 84117368 1
>>>>SQL> INSERT INTO ltree_test VALUES ('a.b'::ltree);
>>>>INSERT 84117369 1
>>>>SQL> INSERT INTO ltree_test VALUES ('a.b.c'::ltree);
>>>>INSERT 84117370 1
>>>>SQL> DELETE FROM ltree_test WHERE path = 'a.b'::ltree;
>>>>DELETE 1
>>>
>>>I'm not sure why you expect this to error. Any row that would reference
>>>a.b would be removed by the delete AFAICS.
>>
>>Nope, there's no ON DELETE CASCADE on the FK, and RESTRICT is the
>>default (thankfully).
>
> The only row that matches 'a.b' that I see in the above is the second
> insert which is also the row that is deleted in the delete. And since the
> constraint uses equality, any row that matches path='a.b' is a target of
> the delete because it's the same operator.

Ah, I misinterpreted what you said; I thought you were talking about
records with foreign keys referencing 'a.b' being deleted. That would
have been unexpected unless there'd be an ON DELETE CASCADE on those
records.
What may be confusing here is that the FK reference is in the same table
(in fact, on the same column) as the PK being referenced.

Why I'd expect it to error is because the record with PK value 'a.b'
should have been referenced by the record with PK value 'a.b.c'.

I was hoping that the fact that the fields are of type ltree would hint
the underlying system that these are related records, of which the
parent can't be deleted due to the FK constraint. But alas, this doesn't
seem to be the case - instead we'll need a few triggers. I expected a
little bit more magic than there actually is.

Regards,
--
Alban Hertroys
alban@magproductions.nl

magproductions b.v.

T: ++31(0)534346874
F: ++31(0)534346876
M:
I: www.magproductions.nl
A: Postbus 416
    7500 AK Enschede

// Integrate Your World //