How to maintain recursive invariant in MySQL database?

Question

I have a tree encoded in the MySQL database as edges:

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

For each sheet in the items.tot tree, items.tot set by someone. For internal items.tot nodes should be the sum of his children. Repeated execution of the following query will create the desired result.

 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) 

(note that this does not actually work, but as for the point)

Suppose a database exists and the invariant is already running.

The question arises:

What is the most practical way to update the database while maintaining this requirement? Updates can move nodes around or change the tot value on leaf nodes. It can be assumed that leaf nodes will remain as leaf nodes, internal nodes will remain internal nodes, and all this will remain as a regular tree.

Some thoughts that I had:

• Complete cancellation, after any update, recount everything (Um ... No)
• Set a trigger in the item table to update the parent of any updated row
  • It will be recursive (updates of update triggers, update trigger ...)
  • Doesn't work, MySQL cannot update the table that started the trigger
• Set a trigger to schedule the update of the parent of any updated row
  • It will be iterative (get an element from the graph, process it with a schedule of more elements).
  • What does it mean? Trust the client code to get it right?
  • The advantage is that with proper ordering of updates, fewer amounts should be a computer. But this ordering is complexity and its own.

An ideal solution would generalize to other "aggregate invariants"

FWIW I know this is “a little overboard”, but I do it for fun (Fun: verb, search for the impossible, doing it. :-)

Answer 1

The problem you are facing is understandable, recursion in SQL. You need to get the parent element of the parent ... of the sheet and update it (either subtract the old one, add a new one, or recompose it). To view the structure of the tree, you need a certain form of identifier and grab all the child nodes and the list of parents / path to the sheet for updating.

This method adds constant space (2 columns to your table - but you only need one table, otherwise you can join later). Some time ago, I was playing with a structure that used a hierarchical format, using the left and right columns (obviously, the wrong names), calculated by going around the order and then going around, respectively - no worries about them need to be recounted every time.

I will let you take a look at the page using this method in mysql instead of continuing this discussion, unless you like this method as an answer. But if you like it, send / edit, and I will take some time and clarify.

Answer 2

I'm not sure I understood your question correctly, but this might work "I take trees in SQL . "

A related post is the described method of storing a tree in a database - PostgreSQL in this case - but the method is clear enough, so it can be easily used for any database.

Using this method, you can easily update all nodes depending on a modified node K with approximately N simple SELECT queries, where N is the distance from K from the root node.

Hope your tree is not very deep :).

Good luck