cadena más corta dentro de la misma ruta (rama)

Question

Tengo una representación en árbol en la tabla mysql basada en id, depth, parent_id y path. Cada registro raíz dentro de esta tabla tiene una profundidad de 0, parent_id != null y path representación basada en el valor hexadecimal de la ID rellenada a la izquierda con 0.

Cada elemento del árbol se construye mediante la especificación de depth = parent.depth + 1, path = parent.path + hex(id), parent_id = parent.id (pseudo código), por ejemplo:

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 

y así sucesivamente ... El problema es cómo conseguir los registros de usuario específico Identificación limitada a la ruta más corta en la misma rama. Por ejemplo, para 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 

En lugar de:

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

¿Has probado algo como esto?

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 

(No estoy seguro de que va a funcionar exactamente como el anterior, pero básicamente: a la izquierda se unen en el camino con el fin de extraer la lista completa de los padres y, a continuación, agregar de tal manera que sólo se mantiene el . nodos sin ningún tipo de los padres cuando se agrupan por assigned_user_id)

Answer 3

me gustaría probar algo como esto:

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

Básicamente la idea es seleccionar los mejores nodos padre para el usuario dado.

Answer 4

Si entiendo bien, puede ser suficiente excluir filas cuyo parent_id se encuentra entre los identificadores seleccionados. Esto se debe a que si se seleccionan el padre y el hijo, deben estar en la misma rama. La ruta del padre será más corta, por lo tanto, está bien excluir al niño.

Algo así como:

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

Si desea tener un árbol como este (números son su id de usuario asignados):

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

B2, C2, G2 y M2 serían seleccionados. Sin embargo, todavía no estoy seguro de si esta era tu intención.

Answer 5

Idea detrás de esto: B es más corto que A si A comienza con B. Quizás haya algo mejor que LIKE para hacer esto "comienza con".

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, '%')) 

Ambos? se asignan a la identificación de usuario deseada.

EDITAR

olvidó incluir la assigned_user_id. Cambió el código.

segundo EDITAR

código modificado para evitar el caso de b = a.