우선순위 그래프

우선순위 그래프는 충돌 그래프^[1] 및 직렬화 그래프라고도 하며 데이터베이스의 ^[2]동시성 제어 컨텍스트에서 사용됩니다.

일정 S의 우선순위 그래프에는 다음이 포함됩니다.

• S에서 커밋된 각 트랜잭션의 노드
• T의_i 액션이 T의 액션 중 하나와_j 경합하는 경우 T에서_i T로_j 호.즉, 액션은 다른 트랜잭션에 속하며, 액션 중 적어도1개는 쓰기 조작이며, 액션은 같은 오브젝트(읽기 또는 쓰기)에 액세스 합니다.

우선순위 그래프 예시

예 1

${\displaystyle S=begin{bmatrix}T1&T2\R(A)&R(A)\\A=A*5&R(B)\W(A)&B=B+A\R(B)&W(B)\\B=B*10&\W(B)&\end{bmatrix}}$

예 2

${\displaystyle D=R1(A)}$ ${\displaystyle R2(B)}$ ${\displaystyle W2(A)}$ $(\displaystyle Com).2}$ ${\displaystyle W1(A)}$ $(\displaystyle Com).1}$ ${\displaystyle W3(A)}$ $(\displaystyle Com).3}$

3개의 트랜잭션이 있는 스케줄 D의 우선순위 그래프.커밋된 트랜잭션 T1과 T2를 통과하는 주기(길이 2의 엣지 포함)가 있으므로 이 일정(이력)은 Conflict serializable이 아닙니다.Transaction 2의 커밋은 precedence 그래프 작성과 관련하여 아무런 의미가 없습니다.

precedence 그래프를 사용한 시리얼화 테스트

스케줄 S의 Conflict Serializability를 샘플 스케줄과 함께 테스트하는 알고리즘.

$\displaystyle S=begin{bmatrix}T1&T2&T3&\R(A)&\&W(A)&\&Com&\W(A)&\Com.&\&W(A)\&Com.\\\end {bmatrix}}$

또는

${\displaystyle S=R1(A)}$ ${\displaystyle W2(A)}$ $(\displaystyle Com).2}$ ${\displaystyle W1(A)}$ $(\displaystyle Com).1}$ ${\displaystyle W3(A)}$ $(\displaystyle Com).3}$

1. 스케줄 S에 참여하는 트랜잭션_x T마다 우선순위 그래프에 T라는 이름의_i 노드를 만듭니다.따라서 우선 순위 그래프에는₁ T₂, T₃, T가 포함됩니다.
2. T가 write_item(X)을 실행한 후_i T가 read_item(X)을 실행하는 S의_j 각 경우에 대해 우선 순위 그래프에 에지(T_i → T_j)를 생성한다.위의 예에서는 쓰기 후 읽기가 없기 때문에 이 문제가 발생하지 않습니다.
3. T가 read_item(X)을 실행한 후_i T가 write_item(X)을 실행하는 S의_j 각 경우에 대해 우선 순위 그래프에 에지(T_i → T_j)를 생성한다.그 결과 T에서₁ T로₂ 유도된 가장자리가 생성됩니다(T가 R(A)을 가지기 전에₂ T가 W(A)를 가지기 때문입니다₁).
4. T가 write_item(X)을 실행한 후_i T가 write_item(X)을 실행하는 S의_j 각 경우에 대해 우선 순위 그래프에 에지(T_i → T_j)를 생성한다.결과적으로 T에서 T로₂₁, T에서₂ T로₃, T에서₁ T로, T에서 T로₃ 유도된 가장자리가 됩니다.
5. 스케줄 S는 우선순위 그래프에 사이클이 없는 경우에만 시리얼화할 수 있습니다.T와₂ T는 사이클을 구성하기 때문에₁ 위의 예에서는 (컨플릭트)시리얼라이즈 할 수 없습니다.

레퍼런스

외부 링크

• 데이터베이스 시스템의 기초, 제5판에서는 충돌 일련성 테스트와 관련된 우선순위 그래프의 사용에 대해 17장에서 논의한다.
• 에이브러햄 실버샤츠, 헨리 코스와 S.수다르샨2005. 데이터베이스 시스템 개념(5개판), 페이지 628~630.맥그로힐 주식회사, 뉴욕, 뉴욕