Time Complexity: Timestamp-based protocols
O(n * m)
0
0
Timestamp-based protocols in DBMS Theory - Time & Space Complexity
Understanding Time Complexity
We want to understand how the time needed for timestamp-based protocols changes as the number of transactions grows.
Specifically, how does the system handle more transactions and what costs increase?
Scenario Under Consideration
Analyze the time complexity of the following timestamp-based concurrency control steps.
// For each transaction T with timestamp TS(T):
// For each data item X accessed by T:
// If TS(T) < read_TS(X), abort T
// Else if TS(T) < write_TS(X), abort T
// Else allow read or write and update TS(X)
This code checks timestamps to decide if a transaction can read or write a data item safely.
Identify Repeating Operations
Look at what repeats as input grows.
- Primary operation: Checking timestamps for each data item accessed by each transaction.
- How many times: For each transaction, the protocol checks every data item it uses.
How Execution Grows With Input
As the number of transactions and data items accessed grows, the checks increase proportionally.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 transactions | About 10 x data items per transaction checks |
| 100 transactions | About 100 x data items per transaction checks |
| 1000 transactions | About 1000 x data items per transaction checks |
Pattern observation: The total checks grow roughly in direct proportion to the number of transactions and their data accesses.
Final Time Complexity
Time Complexity: O(n * m)
This means the time to process transactions grows linearly with the number of transactions and the number of data items accessed per transaction.
Common Mistake
[X] Wrong: "Timestamp checks happen only once per transaction regardless of data items."
[OK] Correct: Each data item accessed requires a timestamp check, so the total work depends on all data accesses, not just the number of transactions.
Interview Connect
Understanding how timestamp-based protocols scale helps you explain concurrency control in databases clearly and confidently.
Self-Check
What if we changed the protocol to check timestamps only at the start and end of transactions? How would the time complexity change?