# CMPT 454
[CMPT 454] Week13_2
Assignment 3 practice > T1:R(X), T2:R(X), T1:W(X), T2:W(X) > Serializable: T1T2또는 T2T1에 해당하는지 봐야한다. T1T2가 될 수 없다. 왜냐하면 R2(X)는 initial value를 읽기 때문이다. T1T2에서는 W1(X)를 R2(X)가 읽는다. T2T1 또한 될 수 없다. R1(X)가 initial value를 읽기 때문이다. serialiazalbe doesn't guarantee conflict serializable. > conflict-serializable: R2(X), W1(X)에서 T2 -> T1이 발생한다. W1(X), W2(X)에서 T1 -> T2가 발생한다. 싸이클이 발생했으므로 conflict-serializ
[CMPT 454] Week11_2
What can happen > system crash는 memory는 날라가고 disk는 괜찮은 상황을 말한다. Motivation Crash Recovery: Big Picture ANALYSIS Phase 
[CMPT 454] Week11_1
Day 1 Other Log-Related State > 맨 마지막 TT에 (T2, U, 160)이 들어갈 것이다. 만약 (150, T1, End)가 없다면 (140, T1, Commit)이 있을 것이다. 뒤뒤 transaction commits 참조. Checkpoint: save TT and DPT to disk > Write LSN을
[CMPT 454] Week10_3
Observation 2: Support REDO/UNDO Write-Ahead Logging (WAL) Example: WAL > T1 update A는 메모리에만 일어나고, disk에는 바뀌지 않으므로 dirty page다. T2 update C도 마찬가지다. T1 update A (steal)은 write to the disk이다
[CMPT 454] Week10_2
C.C in B+ Tree > C.C = Concurrency Control > 38\*을 찾는다고하면 처음 A (20)을 lock하고 그다음 B만 필요하다는 것을 안다. 그다음 B를 lock하고 A를 release한다. 그다음 C가 필요하다는 것을 알고 C를 lock 하고 B를 release한다. 그다음 D를 lock하고 C를 release한다.
[CMPT 454] Week10_1
Locking alone is insufficient for serializabilty > W1(A)다음 W2(A)이므로 T1 -> T2 이고 W2(B) 다음 W2(B)여서 T2 -> T1이다. Cycle이 있으므로 not serializable. Two-Phase Locking (2PL) Example: 2PL > 첫번째 막대기 이후는 T1
[CMPT 454] Week9_3
Serializable schedules are not necessarily conflict serializable! Isolation Cascading Aborts Avoid Cascading Aborts 
[CMPT 454] Week9_2
Schedules of T1 and T2 > Transaction 1이랑 Transaction2는 완전히 별개다? R1(B)와 R2(B)에 전혀 영향을 미치지 않는다. R1(B)이후 B-100 해도 W 하지 않으면 R2(B)에 영향 미치지 않는다. 메모리에 separated된 공간에 있다. W1(B)이후 R2(B)하면 영향을 받는다. S1: R1(X),W2(X),W1(Y),R3(X),C1,C2,C3 > S1에서 파란색 부분을 스왑하면 다른 것에 아무 영향을 미치지 않으면서 T1T2T3가 된다. swap이후에도 R3(X)는
[CMPT 454] Week9_1 - ACID
The ACID Properties of Schedules Example: Atomicity Consistency Consistency Violated
[CMPT 454] Week 8_3
Transaction Management and Concurrency Control Goals To enusre correctness for concurrent execution of queries and updates from multiple users. Topics Concurrent vs non-concurrent data access Why Have Concurrent Processes? 
[CMPT 454] Week 8_2
Aggregate Operations (AVG, MIN, etc.) > without grouping: group by가 없다면 avg를 한번만 구하면된다. rating과 age만 있으면 되므로, index-only를 써야한다. with group: Using Index for Sorting > index only, but sorting
[CMPT 454] Week 8_1
Multiple Indexes Most selective access path > Option1 : "retrieved"라고 강조한 이유는 이미 I/O로 읽은 상태에서 걸러내는 것이기 때문에 I/O가 줄어들지는 않는다. > 시험이나 과제에서는 (RF)ReductionFactor가 주어진다 > 여기서는 하나의 쿼리만 이용했다. Second Approach: Intersectio Of Rids 
[CMPT 454] Week 7_3
General Selection Conditions An Example > clustered에서 1000 * 0.1인 이유는 10%가 matching term이기 때문이다. > unclustered에서는 한 rid를 follow해도 1개의 record만 얻을 수 있다. 10\*0.1인 이유는 전체 data entries의 개수가 10개이기 때문이다
[CMPT 454] Week 7_2
Hash-Join > join- phase에서 Ri는 크기가 메모리보다 작지만 si는 메모리보다 크다고 가정한 것이다. 둘다 메모리보다 한참 작으면 둘다 메모리에 올릴 수 있다. Nested loop join때와 비슷한 상황이다. > 만약 둘다 메모리보다 크다면 partition을 또 해야한다. Partition phase (h = join co
[CMPT 454] Week 7_1
Index Nested Loops Join (INL) INL (sid is key in S) > R에 있는 record 마다 probing을 하게된다. \ Hash-index (Alt. 2) on sid of R 
[CMPT 454] Week 5_3
Evaluation of Relational Operations Block Nested Loops Join (BNL) (B>3) B = 4, |R| = 6, |S| = 10 > 메모리에 2-page block for outer이므로 1 block, 즉 여기서는 2 page씩 읽어 들인다. outer 페이지를 읽는데 I/O가 바뀌지는 않지만,
[CMPT 454] Week 5_2 - Join (Simple Nested Loop Join)
Replacement Sort > current set에서 ouput의 max value인 5보다 크면서 가장 작은 값은 8이다. 그래서 8을 붙이고 그다음은 input에서 12가 오지만, 8보다 크면서 가장 작은 값은 10이니 10이 온다. Example > 처음에는 current set에서 1을 output으로 옮긴다. 그리고 input에서 3을 current로 옮긴다. 그리고 curret에서 1을 output으로 옮긴다. input에서 5를 current로 옮긴다. ouput이 1,2로 꽉 차니 밖으로 옮기고
[CMPT 454] Week 5_1
Pass 1, 2 
[CMPT 454] Week 4_3 - External Sorting
Chapter 12: Overview of query evaluation (self-reading: 12.1 - 12.3) Chapter 13: External sorting External Sorting The Problem: sort 100Gb of data with 100Mb of RAM The file is stored on disk and too large for any in-memory sorting methods. Cost model: I/O pages. Why External Sort? A classic problem in computer science! Data requested in sorted order e.g., find students in increasing gpa order First step in bulk loading B+ tree index (i.e., sort data entries and
[CMPT 454] Week 4_2
Index Summary Hash-based indexes: best for equality searchs, cannot support range searches. Static Hashing can lead to overflow chains. Extendible Hashing avoids overflow pages by splitting a full bucket a new data entry is added to it. Directory keeps track of buckets, doubles periodically. Linear Hashing avoids overflow pages by splitting buckets in round-robin, without using a directory. > Linear Hashing은 directory가 왜 필요없는지 이해해야하고, directory에 I/O가 쓰이지 않는다는 것을 알아야한다. -> over