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

开发者_StackOverflow中文版

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

---

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

---

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.

---

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.

---

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.

---

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.)