Exclude data that does not have parent in hierarchical schema

Question

I work on a project where we have several tables storing information telling if an entity can have some permissions. Some of these permissions have hierarchical relations (I cannot write in a file if I cannot read in this file, the permission "write_file" would be a child of "read_file" for example). This is how it works, and how it worked for years, I cannot touch that.

We probably still have ooold mysql versions, like mysql 4 :(

We have a table "aggregating" permissions, from different other tables, and after this aggregation, I have to filter out permissions not having their parents permissions, in a request that can potentially affect quite a lot of users.

I don't know how to filter out these permissions, it all :'(

CREATE TABLE permissions {
 id int not null,
 parentId int not null, -- can be 0, meaning this feature does not have parents
 name varchar
 -- etc
};

UPDATE aggregat_table at
  JOIN toto, titi, tutu -- some joins on other table
  INNER JOIN permissions p on p.id = toto.id OR p.id = titi.id OR p.id = tutu.id
  -- JOIN on permissions, but I can't figure out how, to filter out parentless permissions
  SET -- etc etc

Hierarchie is not deep, most of the time there is 3 level, maybe 4 sometime.

id;  parent_id;   name

1;   0;           "can_drink"
2;   0;           "can_walk"
3;   2;           "can_run"
5;   4;           "can_moonwalk"       # is child permission of 4, will be removed
8;   7;           "can_write_document" # is child permission of 7; which is child of 6, will be removed
7;   6;           "can_read_document"  # is child permission of 6, will be removed

If permissions p results in previous step, I would like to keep "can_drink", because it is a root permission, "can_walk", same reason, "can_run", because these is his parent in this set, I would like to get rid of "can_moonwalk", because there is not his parent in the set, and "can_write_document" and "can_read_document" have to disappear, too, because they depend on permission 6 (can_read_document has 6 as parent id, can_write_document has can_read_document as parent, so has 6 as grand parent)

The result would be :

id;  parent_id;   name

1;   0;           "can_drink" # is "root" permission, stayed
2;   0;           "can_walk"  # is "root" permission, stayed
3;   2;           "can_run"   # is child permission, parent is in the set, stayed

Speed matter, a lot.

Thanks for your help

user_1766831 · Answer

(please don't use the old 'comma-join', use JOIN..ON)

(INNER JOIN == JOIN; I am too lazy to type INNER)

LEFT JOIN permissions AS p2 ON ... ... WHERE p2 = 0

UPDATE aggregat_table at
    JOIN toto
    JOIN titi ON ...
    JOIN titu ON ...
    # some joins on other table
    JOIN permissions p
        ON  p.id = toto.id
         OR p.id = titi.id
         OR p.id = tutu.id
    WHERE ... [ see below ]
    SET ...

To skip update the row(s) without a parent:

    WHERE p.parentid != 0

To act on only the parentless row(s):

    WHERE p.parentid = 0

To skip update the row(s) without a GRANDparent:

    WHERE NOT EXISTS( SELECT 1 FROM permissions AS p2
                           WHERE p2.id = p.parentid
                             AND p2.parentid = 0 )

And be sure to have PRIMARY KEY(id) on permissions, if appropriate. And if may be desirable to have INDEX(parentid).

user_87015 · Answer

I am going to assume that the maximum depth of the tree is four.

If the hierarchy is maximum n level deep, you can use n - 1 left outer joins to find the ultimate parent of a node.
An orphan node, in your example, would be the one whose ultimate parent does not have parent_id = 0.

So you can simply do this:

select n0.*
from t      as n0
left join t as p1 on n0.parent_id = p1.id
left join t as p2 on p1.parent_id = p2.id
left join t as p3 on p2.parent_id = p3.id
where coalesce(p3.parent_id, p2.parent_id, p1.parent_id, n0.parent_id) = 0
-- note about coalesce:
-- the ultimate parent needs to be checked from right to left

Demo on DB<>Fiddle

Exclude data that does not have parent in hierarchical schema

2 Answers