[DB/1-3. How to Test Serializability]

3️⃣ How to Test Serializability

---

Testing for Conflict Serializability

Precedence graph의 Cycle 유무를 검사

• a direct graph where the vertices are the transactions
• We draw an arc from Ti to Tj if the two transactions conflict, and Ti accesses the data item on which the conflict arises earlier
• we may label the arc by the item that is accessed
• Node : 트랜잭션, Edge : 충돌연산 있을 때 데이터를 먼저 읽는 방향으로.

⇒ 만약 사이클 존재? conflict serializable 하지 않음 -(cycle이 없어야 함)

---

Precedence Graph

[Example 1]

사이클 존재 → 충돌 직렬 가능 스케줄이 아님

 

 

 

[Example 2]

사이클 존재하지 않음 → Conflict Serializable Schedule

 

---

Cycle Detection

사이클 검사는 N^2 또는 N+E 의 시간 복잡도로 가능 (N = 정점 수, E = 간선 수)

만약 그래프가 비순환적? → topological sorting(위상정렬)을 통해 serializable하게 만들 수 있음

 

---

Test for View Serializability

NP-complete 문제이므로 precedence 그래프로 판단할 수 없다.