Dan Ports <d...@csail.mit.edu> wrote: > On Wed, Jun 01, 2011 at 05:09:09PM -0500, Kevin Grittner wrote: >> Published papers have further proven that the transaction which >> appears to have executed last of these three must actually commit >> before either of the others for an anomaly to occur. > > We can actually say something slightly stronger than that last > sentence: Tout has to commit before *any* other transaction in the > cycle. That doesn't help us implement SSI, because we never try to > look at an entire cycle, but it's still true and useful for proofs > like this. I didn't know that, although it doesn't seem too surprising. With that as a given, the proof can be quite short and straightforward. > Now, supposing Tin is read-only... > > Since there's a cycle, there must also be a transaction that > precedes Tin in the serial order. Call it T0. (T0 might be the > same transaction as Tout, but that doesn't matter.) There's an > edge in the graph from T0 to Tin. It can't be a rw-conflict, > because Tin was read-only, so it must be a ww- or wr-dependency. > Either means T0 committed before Tin started. > > Because Tout committed before any other transaction in the cycle, > Tout has to commit before T0 commits -- and thus before Tin > starts. If we're going to put this into the README-SSI as the proof of the validity of this optimization, I'd like to have a footnote pointing to a paper describing the "first commit in the cycle" aspect of a dangerous structure. Got any favorites, or should I fall back on a google search? -Kevin
-- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers