Shortest string within same path (branch)

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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.