Como manter uma invariante recursiva em um banco de dados MySQL?

Question

Eu tenho uma árvore codificada em um banco de dados MySQL como arestas:

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

Para cada folha da árvore, items.tot é definido por alguém.Para nós internos, items.tot precisa ser a soma de seus filhos.Executar a consulta a seguir repetidamente geraria o resultado desejado.

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)

(observe que isso realmente não funciona, mas isso não vem ao caso)

Suponha que o banco de dados exista e os invariantes já estejam satisfeitos.

A questão é:

Qual a maneira mais prática de atualizar o banco de dados mantendo esse requisito?As atualizações podem mover nós ou alterar o valor de tot em nós folha.Pode-se presumir que os nós folha permanecerão como nós folha, os nós internos permanecerão como nós internos e tudo permanecerá como uma árvore adequada.

Alguns pensamentos que tive:

• Invalidação Total, após qualquer atualização, recalcular tudo (Hum...Não)
• Defina um gatilho na tabela de itens para atualizar o pai de qualquer linha atualizada
  • Isso seria recursivo (atualizações acionam atualizações, acionam atualizações, ...)
  • Não funciona, o MySQL não consegue atualizar a tabela que acionou o gatilho
• Defina um gatilho para agendar uma atualização do pai de qualquer linha atualizada
  • Isso seria iterativo (obter um item da programação, processá-lo e agendar mais itens)
  • O que dá início a isso?Confiar no código do cliente para acertar?
  • Uma vantagem é que se as atualizações forem ordenadas corretamente, menos somas precisarão ser computadas.Mas essa ordem é uma complicação por si só.

Uma solução ideal seria generalizar para outros "invariantes agregadores"

FWIW, eu sei que isso é "um pouco exagerado", mas estou fazendo isso por diversão (Diversão:verbo, Encontrar o impossível fazendo isso.:-)

Answer 1

O problema que você está tendo é claro, recursão em SQL.Você precisa pegar o pai do pai ...da folha e atualiza o total (seja subtraindo o antigo e adicionando o novo, ou recalculando).Você precisa de algum tipo de identificador para ver a estrutura da árvore e pegar todos os nós filhos e uma lista dos pais/caminho para uma folha para atualizar.

Este método adiciona espaço constante (2 colunas à sua tabela - mas você só precisa de uma tabela, caso contrário, poderá fazer uma junção mais tarde).Eu brinquei com uma estrutura há algum tempo que usava um formato hierárquico usando colunas 'esquerda' e 'direita' (obviamente não esses nomes), calculada por uma travessia de pré-pedido e uma travessia de pós-ordem, respectivamente - não se preocupe estes não precisam ser recalculados todas as vezes.

Vou deixar você dar uma olhada em uma página usando este método no mysql em vez de continuar esta discussão caso você não goste desse método como resposta.Mas se você gostar, poste/edite e eu vou tirar um tempo para esclarecer.

Answer 2

Não tenho certeza se entendi corretamente sua pergunta, mas isso pode funcionar Minha opinião sobre árvores em SQL.

A postagem vinculada descreveu o método de armazenamento de árvore no banco de dados - PostgreSQL nesse caso - mas o método é claro o suficiente, para que possa ser adotado facilmente para qualquer banco de dados.

Com este método você pode atualizar facilmente todos os nós dependendo do nó modificado K com sobre N consultas SELECTs simples onde N é a distância de K do nó raiz.

Espero que sua árvore não seja muito profunda :).

Boa sorte!