¿Cómo mantener un invariante recursivo en una base de datos MySQL?

Question

Tengo un árbol codificado en una base de datos MySQL como bordes:

CREATE TABLE items (
    num INT,
    tot INT,
    PRIMARY KEY (num)
    );
CREATE TABLE tree (
    orig INT,
    term INT
    FOREIGN KEY (orig,term) REFERENCES items (num,num)
    )

Por cada hoja del árbol, items.tot lo establece alguien.Para nodos interiores, items.tot debe ser la suma de sus hijos.Ejecutar la siguiente consulta repetidamente generaría el resultado deseado.

UPDATE items SET tot = (
    SELECT SUM(b.tot) FROM
        tree JOIN items AS b
        ON tree.term = b.num 
        WHERE tree.orig=items.num)
    WHERE EXISTS 
        (SELECT * FROM tree WHERE orig=items.num)

(tenga en cuenta que esto en realidad no funciona, pero eso no viene al caso)

Supongamos que la base de datos existe y que los invariantes ya están satisfechos.

La pregunta es:

¿Cuál es la forma más práctica de actualizar la base de datos manteniendo este requisito?Las actualizaciones pueden mover los nodos o alterar el valor de tot en los nudos de las hojas.Se puede suponer que los nodos de hoja permanecerán como nodos de hoja, los nodos interiores permanecerán como nodos interiores y todo permanecerá como un árbol adecuado.

Algunos pensamientos que he tenido:

• Invalidación completa, después de cualquier actualización, vuelve a calcular todo (Um...No)
• Establezca un activador en la tabla de elementos para actualizar el padre de cualquier fila que se actualice
  • Esto sería recursivo (las actualizaciones activan actualizaciones, activan actualizaciones, ...)
  • No funciona, MySQL no puede actualizar la tabla que inició el disparador
• Establecer un activador para programar una actualización del padre de cualquier fila que se actualice
  • Esto sería iterativo (obtener un elemento del cronograma, procesarlo programa más elementos)
  • ¿Qué desencadena esto?¿Confiar en el código del cliente para hacerlo bien?
  • Una ventaja es que si las actualizaciones se ordenan correctamente, es necesario procesar menos sumas.Pero ese ordenamiento es una complicación en sí misma.

Una solución ideal se generalizaría a otras "invariantes agregadas"

FWIW Sé que esto es "un poco exagerado", pero lo hago por diversión (Diversión:verbo, Encontrar lo imposible haciéndolo.:-)

Answer 1

El problema que tienes es claro, la recursividad en SQL.Necesitas conseguir al padre del padre...de la hoja y actualiza su total (ya sea restando lo antiguo y sumando lo nuevo, o recalculando).Necesita algún tipo de identificador para ver la estructura del árbol y capturar todos los nodos secundarios y una lista de los padres/ruta a una hoja para actualizar.

Este método agrega espacio constante (2 columnas a su tabla, pero solo necesita una tabla; de lo contrario, puede unirse más tarde).Hace un tiempo jugué con una estructura que usaba un formato jerárquico usando columnas 'izquierda' y 'derecha' (obviamente no esos nombres), calculadas mediante un recorrido de preorden y un recorrido de postorden, respectivamente. No te preocupes. No es necesario volver a calcularlos cada vez.

Te dejaré echar un vistazo a una página. usando este método en mysql en lugar de continuar esta discusión en caso de que no le guste este método como respuesta.Pero si te gusta, publícalo/edítalo y me tomaré un tiempo para aclararlo.

Answer 2

No estoy seguro de haber entendido correctamente tu pregunta, pero esto podría funcionar. Mi opinión sobre los árboles en SQL.

La publicación vinculada describe el método para almacenar el árbol en la base de datos (PostgreSQL en ese caso), pero el método es lo suficientemente claro, por lo que puede adoptarse fácilmente para cualquier base de datos.

Con este método puede actualizar fácilmente todos los nodos dependiendo del nodo modificado k con aproximadamente norte consultas SELECT simples donde norte es la distancia de k desde el nodo raíz.

Espero que tu árbol no sea muy profundo :).

¡Buena suerte!