직렬가능성 (Serializability)

직렬가능성 (Serializability)

여러 트랜잭션의 병행 실행 결과가 어떤 직렬 스케줄(Serial Schedule)의 결과와 동등할 때 해당 스케줄이 직렬가능하다고 하며, 이는 트랜잭션 정확성의 기본 기준

목적: 병행 실행의 정확성 보장, 직렬 실행과 동일한 결과 보증

유형

• •충돌 직렬가능성(Conflict Serializability): 비충돌 연산의 교환으로 직렬 스케줄로 변환 가능 여부, 선행 그래프(Precedence Graph)에 순환 없으면 충돌 직렬가능
• •뷰 직렬가능성(View Serializability): 동일 데이터를 읽는 결과가 같으면 뷰 직렬가능, 충돌 직렬가능 ⊂ 뷰 직렬가능 (더 넓은 범위)

선행 그래프(Precedence Graph): 트랜잭션을 노드, 충돌 연산 순서를 간선으로 표현, 비순환(Acyclic)이면 충돌 직렬가능, 위상 정렬로 동등한 직렬 순서 도출

충돌 연산: 서로 다른 트랜잭션이 같은 데이터 항목에 접근하고 최소 하나가 쓰기(Write)인 경우

직렬 스케줄(Serial Schedule): 트랜잭션이 겹치지 않고 순차적으로 완전히 실행, 항상 정확하나 동시성 없음

비교: 충돌직렬가능(그래프판정/다항시간) vs 뷰직렬가능(범위넓음/NP-Complete판정) vs 직렬(항상정확/동시성없음)

연관: 트랜잭션, 동시성 제어, 격리 수준, 2PL, 타임스탬프 기반 제어