PG Checker for parent-child validation

Question

I have a table:

CREATE TABLE MENUPOINT (
  id BIGINT NOT NULL,
  parent BIGINT,
  name VARCHAR(64),
  CONSTRAINT "MENUPOINT_pkey" PRIMARY KEY(id),
  CONSTRAINT fkc75dac36251dd346 FOREIGN KEY (parent)
    REFERENCES MENUPOINT(id)
    ON DELETE NO ACTION
    ON UPDATE NO ACTION
    NOT DEFERRABLE
);

And this content:

 id     parent    name
------------------------
 1      null      root
 2      1         child

All this to create this structure:

root
 +- child

Now I need a checker on the Database to check that this can not be executed:

UPDATE MENUPOINT SET parent = 2 WHERE id = 1;

Because:

I would not be able to find out who is root.
The display of the tree would be endless like this:

 root 
  +- child
      +- root
          +- child
              +- root ....

What I have:

CONSTRAINT "NOT_SELF_REFERENCE" CHECK (id <> parent)

But it does not check the whole tree.

What have to be changed for a non-looping tree?

Revoke update of that table from roles. It should be done exclusively using a certain function. — Clodoaldo Neto, Jan 30 '17 at 12:05
trigger to check `NEW.parent not in (select id from menupoint where parent = NEW.id)`?.. — Vao Tsun, Jan 30 '17 at 12:11
@VaoTsun that only checks for loops of 2 elements. With recursive CTEs any loops could be detected. -- But simple trigger checks might run into race conditions at high concurrency (f.ex. 2 simultaneous updates could create a loop while by themselves they would not). I'm not sure however how a `CONSTRAINT TRIGGER` would act (not found anything related to race conditions about them in the docs). — pozs, Jan 30 '17 at 16:39
Possible duplicate of [What are the options for storing hierarchical data in a relational database?](http://stackoverflow.com/questions/4048151/what-are-the-options-for-storing-hierarchical-data-in-a-relational-database) — Grim, Jan 31 '17 at 10:52

score 2 · Answer 1 · edited Jan 06 '22 at 03:58

If you are storing hierarchical data, then this post is an excellent place to start. You can also Google "Karwin hierarchical tree", because Bill Karwin has thorough investigations of this subject.

For what you want to do, three things immediately come to mind. The first is to write a function to check for cycles and to use this for insert and update triggers. This is not my favorite choice.

Another option is to use a closure table. This lists all links between two nodes in the tree. Then a modified check constraint can be used (basically a new connection is allowed if all new paths are valid, and this can be checked fairly easily).

Perhaps the simplest (from the usage perspective) is the full path. If each node contains the full path from the root, then on insert you can check existing full paths fairly easily for potential cycles.

PG Checker for parent-child validation

1 Answers1