idiot terms for databases

conservative 2PL

prevents deadlocks by acquiring all locks at T start

strict 2PL

prevents cascading aborts by releasing all locks at T end

constructing a waits-for graph

nodes are Ts, edge from T1 —> T2 if T1 waits for lock held by T2

wound-wait protocol

only lower priority waits for a higher priority

wait-die protocol

only higher priority waits for a lower one

phantom

T1 reads data, T2 inserts data, T1 reads again

how does crabbing work when traversing a tree?

lock enxt node, then unlock the parent, then repeat until you reach the leaf

how does the locking procedure work assuming updates?

initiate write locks up to a safe node (less than half-full or more than half-full)

what is an intention lock?

have locks indicating that you want a contained object

based on the validation phase, T1 cannot have conflicted with T2 if:

T1 finishes before T2, or T1 completes before T2 starts writing

how does timestamp-based concurrency control work?

associate Ts with timestamps TS(T)
store last read/write of objects RTS(A) and WTS(A)

when do you abort/restart under timestamp CC?

if T wants to read A: abort if TS(T) < WTS(A) - bc every operation should happen right when T starts

if T wants to write A: abort if TS(T) < RTS(A) - a future transact should have read T’s value

Thomas-Write Rule

ignore outdated writes: if T wants to write A and TS(T) < WTS(A), just act as if T’s write never happened because a younger T’ already wrote

how does multi-version CC work?

keep multiple versions of DB objects
each write creates a new version of an object
map each read to the last version of an object before the TS of T

how does the write check under multi-vers CC work?

can T with timestamp TP write object A?
assume T’ with timestamp greater than TP

if T’ has already read A, we must abort

how does snapshot isolation work?

each T operates on a DB snapshot taken when T starts, using the last committed value for each object (different from MVCC b/c no uncommitted values)

what are the two components of write-ahead logging?

1. write all log entries relating to a T before committing it (can use for a redo)

2. write all log entries of a SINGLE buffer page before persisting to disk (use for undo)

what are the three phases of ARIES?

1. analysis: determine Ts to undo/redo after a log

2. redo: get back to state before crash

3. undo aborted Ts active during crash

What are the main data structures used by ARIES?

1. log tail: most recent entries not used yet in disk

2. flushed LSN: # of most recent entry on disk

3. T table: stores T, status, and last LSN produced by that T

4. dirty page table: currently changed but unpersisted pages and the first LSN that made them dirty