79:T63b,To deeply understand the Thomas Write Rule, we must appreciate the different roles of read and write timestamps and why they're handled differently. **R-TS(X): The Read Timestamp** The read timestamp R-TS(X) records the largest timestamp of any transaction that has read data item X. This is critical because: 1. **Reads establish dependencies**: When a transaction reads X, it makes decisions based on that value. Future transactions' writes cannot change what a past transaction "saw." 2. **Reads cannot be undone**: Once a transaction has read a value and potentially used it in computations or decisions, that read has consequences that persist even if the transaction later aborts. 3. **Read-write conflicts break serializability**: If T₁ (timestamp 10) tries to write X after T₂ (timestamp 20) has read X, we cannot allow it. T₂ has already seen the old value; allowing T₁'s write would mean T₂ should have seen T₁'s value instead. **W-TS(X): The Write Timestamp** The write timestamp W-TS(X) records the largest timestamp of any transaction that has written to data item X. This is simpler because: 1. **Writes are overwritable**: Unlike reads, a write's effect can be "erased" by a subsequent write. 2. **Write-write conflicts can sometimes be resolved**: If T₁ (timestamp 10) tries to write X after T₂ (timestamp 20) has written X, T₁'s value would be immediately superseded. No transaction can observe T₁'s write. 3. **The Thomas Write Rule exploits this**: We can safely ignore T₁'s write, treating it as if it happened but was immediately overwritten.7a:T440,The Thomas Write Rule produces schedules that are **view serializable** but not necessarily **conflict serializable**. Understanding this distinction is crucial for appreciating what the Thomas Write Rule achieves. **Conflict Serializability Review:** A schedule S is conflict serializable if we can transform it into a serial schedule by swapping the order of non-conflicting operations. Two operations conflict if: 1. They belong to different transactions 2. They access the same data item 3. At least one of them is a write **View Serializability Review:** A schedule S is view serializable if: 1. For each data item, the same transaction performs the initial read in S as in some serial schedule S' 2. For each read operation, the same transaction wrote the value being read in S as in S' 3. For each data item, the same transaction performs the final write in S as in S' **The Thomas Write Rule and View Serializability:** When we ignore an obsolete write using the Thomas Write Rule, we may create a schedule that is **not conflict serializable** but **is view serializable**.7b:T435,**When to Use the Thomas Write Rule:** The Thomas Write Rule is most beneficial in systems where: 1. **Write-write conflicts are common**: Applications with many concurrent writes to shared data items benefit most. 2. **Transactions are long-running**: Aborting and restarting long transactions is expensive; ignoring obsolete writes saves significant work. 3. **View serializability is acceptable**: Applications that don't require strict conflict serializability can leverage this optimization. 4. **Read-write conflicts are rare**: The rule doesn't help with read-write conflicts, so systems with many reads may see less benefit. **When NOT to Use the Thomas Write Rule:** 1. **Strict conflict serializability required**: Some applications need the stronger guarantee; auditing systems, for example. 2. **Write operations have side effects**: If writing triggers external actions (logging, notifications), ignoring writes could cause inconsistencies. 3. **Recovery considerations**: Ignoring writes complicates some recovery scenarios (discussed in later sections).71:{"json":{"id":"seed_29931101b971f8b1aded00e2a68710a1","slug":"thomas-write-rule","category":"Database Management Systems","topic":"Thomas Write Rule","title":"Thomas Write Rule","description":"Master the Thomas Write Rule, a fundamental optimization to timestamp-based concurrency control that eliminates unnecessary transaction aborts by intelligently ignoring obsolete write operations. Learn how this rule improves system throughput while maintaining serializability guarantees.","difficulty":"INTERMEDIATE","estimatedMinutes":60,"pages":[{"id":"seed_4a2dd6ec52735102108df7388f7cab57","title":"Thomas Write Rule","order":0,"content":[{"id":"opening-hook","title":"The Unnecessary Abort Problem","content":[{"data":{"content":"In the basic timestamp ordering protocol, a transaction is aborted whenever it attempts to write a value that is \"too late\"—when another transaction with a larger timestamp has already read the data item. This strict approach ensures serializability, but it can lead to **unnecessary transaction aborts** that waste computational resources and reduce system throughput.\n\nConsider this scenario: Transaction T₁ (timestamp 10) wants to write to data item X, but transaction T₂ (timestamp 20) has already written to X. Under basic timestamp ordering, T₁ must be aborted and restarted. But think about this carefully: **if T₂'s write has already overwritten X, does T₁'s write even matter anymore?**\n\nThis is precisely the insight that led to one of the most elegant optimizations in database concurrency control—the **Thomas Write Rule**."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"By the end of this page, you will understand the Thomas Write Rule, its motivation, formal definition, and why it represents a fundamental insight about the nature of write operations in database systems. You'll see how this simple rule can dramatically improve transaction throughput without sacrificing correctness.","variant":"info"},"type":"callout"}]},{"id":"historical-context","title":"Historical Context and Motivation","content":[{"data":{"content":"The Thomas Write Rule was introduced by **Robert H. Thomas** in the late 1970s as part of his work on distributed database systems. Thomas observed that the basic timestamp ordering protocol was overly conservative in its handling of write operations, leading to transaction aborts that were unnecessary from the perspective of data correctness.\n\n**The Problem with Basic Timestamp Ordering:**\n\nIn the basic timestamp ordering protocol, every write operation must adhere to a strict rule: a transaction T can write to data item X only if no transaction with a larger timestamp has already read or written X. The rationale is straightforward—if a later transaction has already accessed X, then allowing T to write would violate the timestamp order, potentially breaking serializability.\n\nHowever, Thomas recognized a subtle but crucial distinction: **reads and writes are fundamentally different operations with different implications for serializability**."},"type":"text"},{"data":{"icon":"Lightbulb","title":"The Key Insight","content":"When a transaction T₁ attempts to write a value that has already been overwritten by a later transaction T₂, T₁'s write is effectively invisible—it would be immediately superseded by T₂'s write. Rather than aborting T₁ and wasting all its work, we can simply **ignore** the obsolete write and let T₁ continue.","variant":"tip"},"type":"callout"},{"data":{"content":"**Why Reads Must Be Protected, But Some Writes Can Be Ignored:**\n\nConsider the difference:\n\n1. **Read-Write Conflict**: If T₂ (timestamp 20) has already read X, and T₁ (timestamp 10) wants to write X, we have a real problem. T₂ has made decisions based on the old value of X. If T₁'s write were allowed, it would change history—T₂ should have seen T₁'s value, not the old one. This violates serializability.\n\n2. **Write-Write Conflict**: If T₂ (timestamp 20) has already written to X, and T₁ (timestamp 10) wants to write X, the situation is different. T₁'s write would simply be overwritten by T₂'s write anyway. In any serial schedule where T₁ comes before T₂, T₁'s write would be superseded. **T₁'s write is obsolete before it even happens.**\n\nThis distinction is the foundation of the Thomas Write Rule."},"type":"text"}],"titleType":"number","titleNumber":1},{"id":"formal-definition","title":"Formal Definition of the Thomas Write Rule","content":[{"data":{"content":"The Thomas Write Rule modifies the write rule of the basic timestamp ordering protocol. Let's first recall the basic protocol, then see how Thomas's modification improves it.\n\n**Basic Timestamp Ordering Protocol (Write Rule):**\n\nWhen transaction T wants to execute write(X):\n\n1. If **TS(T) < R-TS(X)**: A transaction with a larger timestamp has already read the old value of X. T's write would change history. **Abort T and restart with a new timestamp.**\n\n2. If **TS(T) < W-TS(X)**: A transaction with a larger timestamp has already written to X. T's write would be overwritten. **Abort T and restart with a new timestamp.**\n\n3. Otherwise: Execute the write and set **W-TS(X) = TS(T)**."},"type":"text"},{"data":{"icon":"Info","title":"Notation Reminder","content":"**TS(T)** = Timestamp of transaction T\n**R-TS(X)** = Read timestamp of data item X (largest timestamp of any transaction that has read X)\n**W-TS(X)** = Write timestamp of data item X (largest timestamp of any transaction that has written X)","variant":"note"},"type":"callout"},{"data":{"content":"**The Thomas Write Rule Modification:**\n\nThe Thomas Write Rule changes only case 2. Instead of aborting T, we simply **ignore the write operation** and let T continue:\n\nWhen transaction T wants to execute write(X):\n\n1. If **TS(T) < R-TS(X)**: A transaction with a larger timestamp has already read X. **Abort T and restart.**\n\n2. If **TS(T) < W-TS(X)**: A transaction with a larger timestamp has already written to X. T's write is obsolete. **Ignore the write but do NOT abort T. Let T continue with its other operations.**\n\n3. Otherwise: Execute the write and set **W-TS(X) = TS(T)**."},"type":"text"},{"data":{"rows":[["TS(T) < R-TS(X)","Abort T and restart","Abort T and restart (same)"],["TS(T) < W-TS(X)","Abort T and restart","**Ignore write, T continues**"],["TS(T) ≥ R-TS(X) and TS(T) ≥ W-TS(X)","Execute write, update W-TS(X)","Execute write, update W-TS(X) (same)"]],"caption":"Comparison: Basic Timestamp Ordering vs Thomas Write Rule","headers":["Condition","Basic Timestamp Ordering","Thomas Write Rule"]},"type":"table"},{"data":{"content":"**The Elegance of the Rule:**\n\nNotice that the Thomas Write Rule doesn't add complexity—it actually simplifies the protocol's response to one scenario. Instead of the expensive operation of aborting and restarting a transaction, we simply skip the obsolete write and continue. The transaction loses nothing (its write was going to be invisible anyway), and the system gains the benefit of avoiding unnecessary work."},"type":"text"}],"titleType":"number","titleNumber":2},{"id":"illustrative-example","title":"Illustrative Example","content":[{"data":{"content":"Let's walk through a concrete example to see the Thomas Write Rule in action. Consider two transactions, T₁ and T₂, with timestamps 10 and 20 respectively, both operating on data item X.\n\n**Initial State:**\n- X = 100 (initial value)\n- W-TS(X) = 0, R-TS(X) = 0\n\n**Schedule of Operations:**\n1. T₂ writes X = 200\n2. T₁ attempts to write X = 150\n3. T₁ reads Y and performs other operations\n4. T₁ commits\n5. T₂ reads Z and performs other operations\n6. T₂ commits"},"type":"text"},{"data":{"left":[{"data":{"items":["Step 1: T₂ writes X = 200. W-TS(X) = 20.","Step 2: T₁ tries to write X. TS(T₁) = 10 < W-TS(X) = 20.","**T₁ is ABORTED**. All its work is lost.","T₁ must restart with a new timestamp (e.g., 30).","T₁ re-executes all operations from scratch.","Significant overhead and reduced throughput."],"title":{"icon":"XCircle","text":"Without Thomas Write Rule","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"accent"},"type":"list"}],"right":[{"data":{"items":["Step 1: T₂ writes X = 200. W-TS(X) = 20.","Step 2: T₁ tries to write X. TS(T₁) = 10 < W-TS(X) = 20.","**T₁'s write is IGNORED** (not executed).","T₁ continues with its other operations.","T₁ commits successfully without restart.","No wasted work, higher throughput."],"title":{"icon":"CheckCircle","text":"With Thomas Write Rule","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}]},"type":"two-column"},{"data":{"content":"**Analyzing the Outcome:**\n\nIn the Thomas Write Rule scenario, the final value of X is 200 (written by T₂). This is exactly what we want! In any serial schedule where T₁ (timestamp 10) executes before T₂ (timestamp 20), T₁'s write to X would be followed by T₂'s write—meaning T₂'s value would be the final one.\n\nThe Thomas Write Rule produces the same final database state as the serial schedule T₁ → T₂, but without the overhead of aborting and restarting T₁. The ignored write is called an **obsolete write** or a **blind write** that would have been immediately overwritten.\n\n**The Intuition:**\n\nThink of it this way: T₁'s write to X is like writing a message on a whiteboard, only to have T₂ immediately erase it and write a different message. Why bother writing the first message at all? The Thomas Write Rule captures this intuition formally."},"type":"text"}],"titleType":"number","titleNumber":3},{"id":"why-it-works","title":"Why the Thomas Write Rule Works","content":[{"data":{"content":"The Thomas Write Rule's correctness isn't immediately obvious. How can we simply ignore a write operation and still maintain correctness? Let's examine the reasoning carefully.\n\n**The Serialization Order Argument:**\n\nThe timestamp ordering protocol produces schedules that are equivalent to a serial schedule where transactions execute in timestamp order. If T₁ has timestamp 10 and T₂ has timestamp 20, the equivalent serial schedule is T₁ → T₂.\n\nNow consider what happens to data item X in the serial schedule T₁ → T₂:\n\n1. T₁ executes first, writing its value to X\n2. T₂ executes second, overwriting X with its value\n3. Final value of X = T₂'s written value\n\n**T₁'s write exists in the serial schedule, but its effect is invisible in the final state**. Any transaction that reads X after both T₁ and T₂ will see T₂'s value, not T₁'s."},"type":"text"},{"data":{"icon":"Lightbulb","title":"The Invisibility Principle","content":"A write operation whose value will be overwritten before any transaction reads it is **semantically invisible**. Ignoring such a write doesn't change the database state that any transaction can observe. The Thomas Write Rule exploits this principle.","variant":"tip"},"type":"callout"},{"data":{"content":"**Formal Correctness Argument:**\n\nLet T_i be a transaction with timestamp TS(T_i), attempting to write data item X, where W-TS(X) = TS(T_j) and TS(T_i) < TS(T_j).\n\n**Claim**: Ignoring T_i's write preserves serializability.\n\n**Proof Sketch**:\n\n1. The equivalent serial schedule orders transactions by timestamp: T_i before T_j.\n\n2. In this serial schedule:\n - T_i writes to X first\n - T_j writes to X second, overwriting T_i's value\n - Final value of X = T_j's written value\n\n3. By ignoring T_i's write and keeping T_j's write:\n - Final value of X = T_j's written value (same as serial schedule)\n - No transaction can observe T_i's write (it would be overwritten anyway)\n\n4. The resulting schedule is view-equivalent to the serial schedule T_i → T_j.\n\n**Important Caveat**: This argument works only because W-TS(X) = TS(T_j) > TS(T_i). If a third transaction T_k with TS(T_i) < TS(T_k) < TS(T_j) reads X, T_k would see T_j's value in both cases (with or without the Thomas Write Rule), maintaining consistency."},"type":"text"},{"data":{"items":["**TS(T) < W-TS(X)**: The transaction's timestamp is older than the current write timestamp of the data item.","**TS(T) ≥ R-TS(X)**: No transaction with a larger timestamp has read the item (this would still cause an abort).","**Write-only conflict**: The conflict is purely between two write operations, not involving any reads of the old value."],"title":{"icon":"CheckCircle","text":"Conditions for Thomas Write Rule Applicability","type":"icon","color":"primary","variant":"outline-circle"},"variant":"glass"},"type":"list"}],"titleType":"number","titleNumber":4},{"id":"read-write-semantics","title":"Understanding Read vs Write Timestamp Semantics","content":[{"data":{"content":"$79"},"type":"text"},{"data":{"rows":[["Meaning","Largest timestamp that has read X","Largest timestamp that has written X"],["Dependency Type","Creates hard dependencies (decisions made)","Creates soft dependencies (can be overwritten)"],["Conflict Resolution","Must abort if TS(T) < R-TS(X)","Can ignore write if TS(T) < W-TS(X)"],["Why Different","Reads cannot be retroactively changed","Writes can be overwritten before observation"],["Thomas Write Rule Impact","Not affected (still causes abort)","Allows ignoring obsolete writes"]],"caption":"Read Timestamp vs Write Timestamp: Key Differences","headers":["Aspect","R-TS(X) - Read Timestamp","W-TS(X) - Write Timestamp"]},"type":"table"},{"data":{"icon":"AlertCircle","title":"Common Misconception","content":"The Thomas Write Rule does NOT allow ignoring writes when TS(T) < R-TS(X). If a later transaction has read the data item, the obsolete write MUST cause an abort. The rule applies ONLY to write-write conflicts where no read has occurred.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":5},{"id":"view-serializability","title":"Relationship to View Serializability","content":[{"data":{"content":"$7a"},"type":"text"},{"data":{"content":"**Example:**\n\nConsider transactions T₁ (timestamp 10) and T₂ (timestamp 20):\n\n```\nSchedule S:\nT₂: write(X) \nT₁: write(X) [IGNORED by Thomas Write Rule]\nT₂: commit\nT₁: commit\n```\n\n**Conflict Analysis:**\n- T₂'s write(X) and T₁'s write(X) conflict\n- In schedule S, T₂'s write appears before T₁'s write\n- But T₁ has a smaller timestamp, so in the equivalent serial schedule, T₁ should come first\n- The schedule is NOT conflict serializable!\n\n**View Analysis:**\n- The serial schedule T₁ → T₂ would have T₂ as the final writer to X\n- In schedule S (with T₁'s write ignored), T₂ is also the final writer to X\n- No transaction reads X in this schedule\n- The schedule IS view serializable!\n\n**The Key Insight:**\n\nThe Thomas Write Rule sacrifices conflict serializability for better performance, but maintains the stronger guarantee of view serializability. This is acceptable because view serializability is the true correctness criterion—it ensures the schedule produces the same results as some serial schedule."},"type":"text"},{"data":{"icon":"Info","title":"Theoretical Implication","content":"This makes the Thomas Write Rule protocol theoretically interesting: it's a practical, efficient protocol that produces view serializable schedules—something that is NP-complete to verify in general, but is achieved here through timestamp ordering constraints.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":6},{"id":"comparison","title":"Comparison with Other Approaches","content":[{"data":{"content":"The Thomas Write Rule represents one of several strategies for handling write-write conflicts in concurrent database systems. Let's compare it with alternative approaches."},"type":"text"},{"data":{"rows":[["Basic Timestamp Ordering","Abort younger transaction","Simple, conflict serializable","Many unnecessary aborts"],["Thomas Write Rule","Ignore obsolete write","Fewer aborts, higher throughput","Only view serializable"],["Two-Phase Locking (2PL)","Wait for lock release","Conflict serializable, no aborts","Potential deadlocks"],["MVCC (Multi-Version)","Create new version","High concurrency, no blocking","Storage overhead, GC complexity"]],"caption":"Write-Write Conflict Handling Strategies","headers":["Approach","Action on Conflict","Pros","Cons"]},"type":"table"},{"data":{"content":"$7b"},"type":"text"}],"titleType":"number","titleNumber":7},{"id":"summary","title":"Summary: The Thomas Write Rule","content":[{"data":{"content":"We've covered the foundational concepts of the Thomas Write Rule. Let's consolidate the key takeaways:"},"type":"text"},{"data":{"type":"ordered","items":["**The Thomas Write Rule is an optimization** — It modifies the basic timestamp ordering protocol to reduce unnecessary transaction aborts.","**Obsolete writes can be safely ignored** — When TS(T) < W-TS(X), T's write would be immediately overwritten; ignoring it produces the same final state.","**Read conflicts still cause aborts** — The rule only applies to write-write conflicts; TS(T) < R-TS(X) still requires aborting T.","**The result is view serializable** — Schedules produced are view serializable but not necessarily conflict serializable.","**Significant performance benefits** — By avoiding aborts and restarts, system throughput improves substantially.","**Named after Robert H. Thomas** — Introduced in the 1970s as part of distributed database research."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**What's Next:**\n\nIn the following pages, we'll explore the concept of outdated writes in greater depth, understanding exactly when and why writes become obsolete. We'll then examine how the Thomas Write Rule handles these cases and analyze the performance improvements it provides. Finally, we'll rigorously examine the correctness guarantees to ensure you have complete confidence in applying this optimization."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You now understand the Thomas Write Rule—its motivation, formal definition, and why it works. This optimization is a perfect example of how deep understanding of database semantics can lead to significant performance improvements without sacrificing correctness.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":8}],"isLocked":false},{"id":"seed_156d1dc1cbb927079339c61956cbabc4","title":"Outdated Writes","order":1,"content":null,"isLocked":true},{"id":"seed_e294ec5263fe819920c04af09543fabd","title":"Ignoring Obsolete Writes","order":2,"content":null,"isLocked":true},{"id":"seed_f6d19e7aa6e5c302a787fa44d8f21b2e","title":"Performance Improvement","order":3,"content":null,"isLocked":true},{"id":"seed_54281e952075c09aa31c673eb8d08ae8","title":"Correctness","order":4,"content":null,"isLocked":true}]}}