Conflict serializability in DBMS Theory - Time & Space Complexity

Time Complexity: Conflict serializability

O(n^2)

Understanding Time Complexity

When checking if a schedule of database transactions is conflict serializable, we want to know how hard it is to analyze the schedule as it grows.

We ask: How does the effort to verify conflict serializability increase as the number of operations grows?

Scenario Under Consideration

Analyze the time complexity of checking conflict serializability for a schedule.

-- Given a schedule with n operations
-- Steps to check conflict serializability:
-- 1. Identify conflicting operation pairs
-- 2. Build a precedence graph
-- 3. Check the graph for cycles

-- Pseudocode outline:
FOR each pair of operations (i, j) in schedule
  IF operations conflict AND i precedes j THEN
    Add edge i -> j in graph
END FOR

Check graph for cycles
    

This code builds a graph from conflicting operations and checks if the graph has cycles to decide conflict serializability.

Identify Repeating Operations

Look for repeated steps that take most time.

• Primary operation: Comparing every pair of operations to find conflicts.
• How many times: For n operations, pairs are about n x n, so roughly n² times.

How Execution Grows With Input

As the number of operations grows, the number of pairs to check grows much faster.

Input Size (n)	Approx. Operations
10	100
100	10,000
1000	1,000,000

Pattern observation: Doubling the number of operations roughly quadruples the work needed.

Final Time Complexity

Time Complexity: O(n2)

This means the checking effort grows roughly with the square of the number of operations in the schedule.

Common Mistake

[X] Wrong: "Checking conflict serializability only needs to look at each operation once."

[OK] Correct: Because conflicts depend on pairs of operations, you must compare many pairs, not just single operations.

Interview Connect

Understanding how conflict serializability checking scales helps you reason about database concurrency and correctness in real systems.

Self-Check

What if we only checked conflicts between operations on the same data item? How would the time complexity change?