Recoverability and cascadeless schedules in DBMS Theory - Time & Space Complexity

Time Complexity: Recoverability and cascadeless schedules

O(n x m)

Understanding Time Complexity

We want to understand how the time to check or enforce recoverability and cascadeless properties grows as the number of transactions increases.

How does the cost change when more transactions and operations are involved?

Scenario Under Consideration

Analyze the time complexity of checking if a schedule is recoverable and cascadeless.

-- Assume schedule S with n transactions and m operations
FOR each transaction T in S LOOP
  FOR each operation O in T LOOP
    IF O reads data written by another transaction U THEN
      CHECK if U commits before T commits
      IF not, mark schedule as not recoverable
      CHECK if O reads only committed data
      IF not, mark schedule as not cascadeless
    END IF
  END LOOP
END LOOP
    

This code checks dependencies between transactions to ensure recoverability and cascadelessness.

Identify Repeating Operations

Look for loops and repeated checks.

• Primary operation: Nested loops over transactions and their operations.
• How many times: For each of the n transactions, it checks m operations, and for each operation, it may check dependencies with other transactions.

How Execution Grows With Input

As the number of transactions (n) and operations (m) grow, the checks increase roughly by the product of these.

Input Size (n transactions)	Approx. Operations (checks)
10	About 10 x m checks
100	About 100 x m checks
1000	About 1000 x m checks

Pattern observation: The number of checks grows linearly with the number of transactions and operations.

Final Time Complexity

Time Complexity: O(n x m)

This means the time to verify recoverability and cascadelessness grows proportionally with the number of transactions and their operations.

Common Mistake

[X] Wrong: "Checking one transaction is enough to know if the whole schedule is recoverable or cascadeless."

[OK] Correct: Each transaction can depend on others, so all must be checked to ensure no hidden conflicts or uncommitted reads.

Interview Connect

Understanding how the cost grows when checking transaction schedules helps you reason about database reliability and concurrency control in real systems.

Self-Check

"What if we only checked transactions that read from others, skipping those that write only? How would the time complexity change?"