.jpg&blockId=1b87074d-017e-8069-9667-d5678d39e51d)
Seiral Schedule
•
한 번에 하나의 transaction만 실행시키는 것
Serializable schedule
•
Seriali schedule과 같은 효과를 내는 Schedule
Conflict & Conflic-serializable schedule
Conflict: 서로 간의 바뀌면 안 되는 행동들
•
Ri(X), Wj(X)
•
Wi(X), Wj(X)
Not conflicts: 서로 간의 바뀌어도 되는 행동들
•
Ri(X); Rj(X)
•
Ri(X); Wj(Y)
•
Wi(X); Wj(Y)
Conflict-serializable schedule
•
Serial schedule과 conflict-equivalent한 친구들
•
conflict serializable하면 항상 serializable하다.
•
serializable하다고 conflict serializable하지는 않다.
Precedence graph
•
A에 대해서 보면 두 가지 트랜잭션에서 접근한다. 이 때 T2가 일어나고 T3가 일어나야함. 왜냐하면 순서가 그러니까?
•
그래서 이런 식으로 트랜잭션 사이의 우선순위를 다 정할 수 있다.
Locking
•
Two-phase Locking
◦
모든 트랜잭션에 대해서, 락의 획득은 항상 release 전에 일어나야한다.
◦
2PL을 하다가 보면 deadlock이 생길 수도 있다.
•
several mode
◦
한 타입의 lock만 쓰는건 reading과 writing을 할 때 전혀 효율적이지 않다.
◦
대신 reading을 위한 shared lock과 writing을 할 때 exclusive lock을 사용하자
•
update lock
◦
락을 업데이트할 수가 있다. shared lock에서 exclusive lock으로
◦
이런 식으로 update하다가보면 deadlock이 생길 수 있다.
◦
새로운 타입인 update lock을 도입한다.
◦
update lock만 나중에 x-lock이 될 수 있다.
•
increment lock
◦
increment하거나 decrement할 일이 많은데, 이 상황을 위해서 만든 lock이 있다
•
locking schedule
◦
lock table
▪
데이터베이스 내용물과 lock 정보를 담아놓은 테이블
▪
구현은 hash table로 할 수 있다.
▪
테이블 안에 없다면 lock이 없는 것이다.
▪
group모드를 잘 봐야한다. 새로운 락을 요청하는 트랜잭션이 봐야하는 가장 중요한 것
▪
위에처럼 linked list 형식으로 가야하고, 기다려야하는지 아닌지를 나타낸다.
◦
warning lock
▪
락을 거는 위치에 대해서 Relation,, Pages, data block으로 나뉠텐데 이 세 가지에 대해서 warning을 거는 것이다.
▪
말 그대로 warning이기 때문에, 트리 구조처럼 상위 개념에 대해서 warning을 걸어놓는 것.
▪
block 전체에 대해서 락을 걸수도 있으니, 이런 경우는 X락을 거는 것이 될테고 이 때 IX가 걸려있다면 막는다.
▪
Warning끼리는 언제든지 서로 요청할 수 있음.
▪
Insert & Delete
•
Delete의 경우에는 해당 element에 대해서 미리 lock을 걸고 시자갛면 된다.
•
insert에 대해서는 미래 element에 대해 락을 걸 수 없으니, 상위 개념인 aprent에다가 X lock을 걸어야한다.
◦
Tree based locking & Tree protocol
▪
motivation
•
Tree-based 구조에 대해서 기존의 방식을 사용하면 오직 하나의 트랜잭션만 해당 구조를 변경하거나 insert할 수 있다. 예를 들어 B-tree index 같은 경우에 무조건 루트 노드를 지나가기 때문에 이것부터 락을 걸고 시작을 할 테고, 그럼 아무것도 못한다.
•
따라서 tree를 accessing하기 위한 다른 프로토콜이 필요함.
▪
Tree protocol
•
Node에 대해서 꼭 root만이 시작점이 아니어도 된다. 어디서든 할 수 있음.
•
해당 트랜잭션에 subsequent한 락은 그 자식들만이 가질 수 있다.
•
Node에 대해서는 언제든지 unlock을 할 수 있음
•
한 번 unlock된 친구들은 다시 lock을 걸 수 없다.
▪
Tree protocol은 serial order를 보장함.
◦
Optimistic locking
▪
unserializable behavior가 없다고 가정하고 violation이 생기면 transaction abort를 하는 방식
▪
세 phase가 존재
•
Read : Read set에서 읽고 내부적으로 쓸 준비를 마침
•
Validate: RS(T)와 WS(T)를 다른 트랜잭션과 비교
•
Write: 문제가 없다면 쓰기
▪
세 가지 상태가 존재함
•
START: 트랜잭션 시작, 아직 validated 안 됨
•
VAL: validated가 완료되었지만, 아직 write phase를 끝내지 않은 상태
•
FIN: write phase를 끝낸 상태
•
U가 끝나는 시점이 T가 시작하는 시점보다 뒤라면, U에서 쓰는 값과 T에서 읽는 값은 서로 겹치면 안 된다. → 쓰고 읽고가 되야지, 읽고 쓰고가 되면 안 된다.
•
U가 끝나는 시점이 T가 validate되는 시점보다 된 시점보다 뒤에 있다면, U가 쓰는 것과 T가 쓰는 것이 공집합이어야한다. → 동시에 쓰고 있으면 안 된다.
▪
Validation 이 useful한 경우
•
conflict이 잘 안 날 때
•
system resource가 충분할 때
•
application이 real-time constraint가 있을 때