CODEWITHSUNDEEP
phpmysqlsql
veritas
veritas

Reputation: 2052

Shortest string within same path (branch)

I have a tree representation in mysql table based on id, depth, parent_id and path. Every root record within this table has a depth of 0, parent_id != null and path representation based on hex value of ID padded left with 0.

Every element of the tree is constructed by specifying depth = parent.depth + 1, path = parent.path + hex(id), parent_id = parent.id (pseudo code) for example:

id    path            depth    parent_id    assigned_user_id
------------------------------------------------------------
1     001             0        NULL         NULL
2     002             0        NULL         1
3     001003          1        1            2
4     002004          1        2            1
5     001003005       2        3            2
6     001003005006    3        5            2
7     002004007       2        4            1
8     002004008       2        4            2
9     002004009       2        4            2
10    00200400800A    3        8            2

and so on... The problem is how to get the records for specific user id limited to the shortest path in the same branch. For example for assigned_user_id = 2 retrive:

id    path            depth    parent_id    assigned_user_id
------------------------------------------------------------
3     001003          1        1            2
8     002004008       2        4            2
9     002004009       2        4            2

Instead of:

id    path            depth    parent_id    assigned_user_id
------------------------------------------------------------
3     001003          1        1            2
5     001003005       2        3            2
6     001003005006    3        5            2
8     002004008       2        4            2
9     002004009       2        4            2
10    00200400800A    3        8            2

Upvotes: 5

Views: 187

Answers (5)

Wolfgang
Wolfgang

Reputation: 2407

Idea behind this: B is shorter than A if A starts with B. Maybe there's something better than LIKE to do this "begins with".

SELECT a.* FROM node AS a
WHERE a.assigned_user_id = ?
AND NOT EXIST
(SELECT * FROM node AS b
    WHERE b.assigned_user_id = ?
    AND LENGTH(a.path) > LENGTH(b.path) 
    AND a.path LIKE CONCAT(b.path, '%') )

Both ? are mapped to the desired user id.

EDIT

Forgot to include the assigned_user_id. Changed the code.

2nd EDIT

Changed code to avoid the case of b=a.

Upvotes: 1

Andriy M
Andriy M

Reputation: 77687

SELECT t1.*
FROM atable t1
  LEFT JOIN atable t2
    ON t2.assigned_user_id = t1.assigned_user_id AND
       t2.path = LEFT(t1.path, CHAR_LENGTH(t2.path)) AND
       t2.id <> t1.id
WHERE t1.assigned_user_id = 2
  AND t2.id IS NULL

Upvotes: 2

Krab
Krab

Reputation: 2148

If I get you right, it might be enough to exclude rows whose parent_id is among the ids selected. This is because if the parent and child is selected, they must be in the same branch. The parent's path will be shorter, therefore it's OK to exclude the child.

Something like:

SELECT * 
  FROM x 
  WHERE assigned_user_id = 2 
        AND parent_id NOT IN (SELECT id FROM x WHERE assigned_user_id = 2)

If you would have a tree like this (numbers are your assigned user ids):

  A1                    G2
 / \                   / \
B2  C2                H2  I2
    | \               |   | \
    D2  E2            L1  J2 K2
                      |
                      M2

B2, C2, G2 and M2 would be selected. I'm still not sure if this was your intention, though.

Upvotes: 2

Andrey Adamovich
Andrey Adamovich

Reputation: 20663

I would try something like this:

SELECT * FROM PATHS WHERE ASSIGNED_USER_ID = 2
AND NOT PARENT_ID IN (SELECT ID FROM PATHS WHERE ASSIGNED_USER_ID = 2)

Basically the idea is to select top parent nodes for the given user.

Upvotes: 1

Denis de Bernardy
Denis de Bernardy

Reputation: 78473

Have you tried something like this?

select child.assigned_user_id, child.id
from node as child
left join node as parent
on child.path like CONCAT(parent.path, '%')
and child.assigned_user_id = parent.assigned_user_id
and child.id <> parent.id
group by child.assigned_user_id, child.id
having max(parent.id is null) = true

(Not sure it'll work exactly as above, but basically: to left join on the path in order to extract the full list of parents, and then to aggregate in such a way that you only keep the nodes without any parents when grouped by assigned_user_id.)

Upvotes: 0

Related Questions