Databases
StackOverflow2013
Postsdbo
POHow to maintain a recursive invariant in a MySQL database?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POHow to maintain a recursive invariant in a MySQL database?
    primarykey
    data
    text
    <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>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USBCS
    1. USBCS
    plurals
    1. This table or related slice is empty.
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POHow to maintain a recursive invariant in a MySQL database?
      1. This table or related slice is empty.
      1. VTUpMod
    1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload