Is it possible to create a unique constraint that includes the entire path of an ltree field?

Question

I'm using the ltree extension in Postgres to manage paths for a tree. I want to ensure that the name field is unique for any given path on the tree. Can I accomplish this using a constraint or do I have to build this into the query?

  demo table
------------------------------
| name (text) | path (ltree) |
------------------------------
| a           | 1            |
------------------------------
| b           | 1.2          |
------------------------------
| b           | 1.3          |
------------------------------
| b           | 1.2.4        | <-- this should fail on insert
------------------------------

If I have to build it into the query, does this potentially have a race condition if I use READ COMMITTED?

CREATE TABLE demo (
    name text NOT null,
    path ltree NOT null
);
CREATE INDEX path_gist_idx ON demo USING GIST (path);
INSERT INTO demo (name, path)
SELECT 'a', '1'
WHERE NOT EXISTS (
    SELECT * FROM demo WHERE name = 'a' AND (path <@ '1' OR path @> '1')
);
INSERT INTO demo (name, path)
SELECT 'b', '1.2'
WHERE NOT EXISTS (
    SELECT * FROM demo WHERE name = 'b' AND (path <@ '1.2' OR path @> '1.2')
);
INSERT INTO demo (name, path)
SELECT 'b', '1.3'
WHERE NOT EXISTS (
    SELECT * FROM demo WHERE name = 'b' AND (path <@ '1.3' OR path @> '1.3')
);
INSERT INTO demo (name, path)
SELECT 'b', '1.2.4'
WHERE NOT EXISTS (
    SELECT * FROM demo WHERE name = 'b' AND (path <@ '1.2.4' OR path @> '1.2.4')
);
SELECT * FROM demo;

Please explain the logic behind path 1.2.4 failing. It seems to satisfy your requirement that for a given path the field name is unique. Do you actually mean name is unique for any prior sub-tree. — Belayer, Feb 20 '20 at 01:07
It should fail because the name already exists for 1.2, which is an ancestor of 1.2.4. — Travis, Feb 20 '20 at 01:36
But the existence of the ancestors is the basic nature of a tree structure. So are you looking at a tree with only 2 levels or any number of levels provided ancestors do not exist except perhaps for the the root level. If I added (name, path) of (c,2) then tried (c,2.1) should that fail, But (d,3.1) is valid providing there is no (d,3)? — Belayer, Feb 20 '20 at 15:11

Edouard · Answer 1 · 2021-12-08T09:24:32.383

An other solution could be to test the new path in a trigger function or in a rule (better performance) :

Trigger function :

CREATE OR REPLACE FUNCTION path_test ()
RETURNS trigger LANGUAGE plpgsql AS
$$
BEGIN
IF EXISTS (SELECT *
             FROM demo
            WHERE name = NEW.name
              AND (path <@ NEW.pah OR path @> NEW.path))
THEN RETURN NULL ;
ELSE RETURN NEW ;
END ;
$$

CREATE OR REPLACE TRIGGER before_insert_update_demo BEFORE INSERT OR UPDATE OF name, path ON demo
FOR EACH ROW EXECUTE FUNCTION path_test () ;

Rule

CREATE OR REPLACE RULE path_test_insert AS ON INSERT TO demo
WHERE EXISTS (SELECT *
                 FROM demo
                WHERE name = NEW.name
                  AND (path <@ NEW.pah OR path @> NEW.path))
DO NOTHING ;

CREATE OR REPLACE RULE path_test_update AS ON UPDATE TO demo
WHERE EXISTS (SELECT *
                 FROM demo
                WHERE name = NEW.name
                  AND (path <@ NEW.pah OR path @> NEW.path))
DO NOTHING ;

I don't know about rules, but I don't think triggers are thread safe? unless you run the entire insert in a serial transaction, which is something I'd like to avoid — Pinna_be, Dec 09 '21 at 08:59

score 2 · Answer 2 · edited Dec 10 '21 at 10:08

You could create a separate table with stores the name and a path

-- this table is equivalent to the demo table
CREATE TABLE record_table (
    title text NOT null
);
-- this table holds the titles
CREATE TABLE title_table (
    name text NOT null,
    path ltree NOT null,
);

and create a parallel safe function which you can call while inserting into the original table

CREATE OR REPLACE FUNCTION verify_unique_title(title text, tree_path ltree) 
RETURNS TEXT AS '
  DECLARE
      duplicate_path ltree;
  BEGIN
      SELECT path 
       FROM title_table 
       INTO duplicate_path 
       WHERE name=title AND path <@> tree_path;
      IF duplicate_path IS NOT NULL 
       THEN raise exception ''title was not unique''; 
       END IF;
      INSERT INTO title_table (name, path) VALUES (title, tree_path);
      RETURN title;
  END;
' LANGUAGE plpgsql PARALLEl UNSAFE;

-- these inserts should work
INSERT INTO record_table (title) VALUES (verify_unique_title('a', '1'::ltree));
INSERT INTO record_table (title) VALUES (verify_unique_title('b', '1.2'::ltree));
INSERT INTO record_table (title) VALUES (verify_unique_title('b', '1.3'::ltree));

-- the following should fail
INSERT INTO record_table (title) VALUES (verify_unique_title('b', '1.2.3'::ltree));

You'd have to implement similar triggers for updating and deleting items if you want to maintain the separate index.

score 1 · Answer 3 · answered Feb 20 '20 at 02:51

1

There is a race condition if you use read committed.

You could in principle use an EXCLUDE constraint, except that there is no single self-commutative operator you can use. That means you would have to invent a new operator, maybe called <@>, and add it to ltree. I think that this would be possible, but not something you would probably look forward to doing.

Could you just use serializable?

answered Feb 20 '20 at 02:51

jjanes

37,812
5
27
34

I have tried inventing this new operator, but It is quite hard to add it to the gist_ltree_ops family! any tips for doing that? – Pinna_be Dec 03 '21 at 12:19

Is it possible to create a unique constraint that includes the entire path of an ltree field?

3 Answers3