title: How to maintain a recursive invariant in a MySQL database?
body: <p>I have a tree encoded in a MySQL database as edges:</p>
  
  <pre><code>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)
      )
  </code></pre>
  
  <p>For each leaf in the tree, <code>items.tot</code> is set by someone. For interior nodes, <code>items.tot</code> needs to be the sum of it's children. Running the following query repeatedly would generate the desired result.</p>
  
  <pre><code>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)
  </code></pre>
  
  <p>(note this actually doesn't work but that's beside the point)</p>
  
  <p>Assume that the database exists and the invariant are already satisfied. </p>
  
  <p>The question is:</p>
  
  <blockquote>
    <p><strong>What is the most practical way to update the DB while maintaining this requirement? Updates may move nodes around or alter the value of <code>tot</code> on leaf nodes. It can be assumed that leaf nodes will stay as leaf nodes, interior nodes will stay as interior nodes and the whole thing will remain as a proper tree.</strong></p>
  </blockquote>
  
  <p>Some thoughts I have had:</p>
  
  <ul>
  <li>Full Invalidation, after any update, recompute everything (Um... No)</li>
  <li>Set a trigger on the items table to update the parent of any row that is updated
  
  <ul>
  <li>This would be recursive (updates trigger updates, trigger updates, ...)</li>
  <li>Doesn't work, MySQL can't update the table that kicked off the trigger</li>
  </ul></li>
  <li>Set a trigger to schedule an update of the parent of any row that is updated
  
  <ul>
  <li>This would be iterative (get an item from the schedule, processing it schedules more items)</li>
  <li>What kicks this off? Trust client code to get it right?</li>
  <li>An advantage is that if the updates are ordered correctly fewer sums need to be computer. But that ordering is a complication in and of it's own.</li>
  </ul></li>
  </ul>
  
  <p>An ideal solution would generalize to other "aggregating invariants"</p>
  
  <p>FWIW I know this is "a bit overboard", but I'm doing this for fun (Fun: verb, Finding the impossible by doing it. :-)</p>