[학교 수업]/[학교 수업] Database

Failure Classifier Database system에서 발생할 수 있는 failure case는 다음과 같습니다:Transaction failure:Logical errors: transaction내부의 error condition으로 인해 transaction이 끝나지 않는 것을 말합니다.System errors: deadlock과 같이 error condition으로 인해 database system이 동작중인 transaction을 종료해야만 하는 상황을 말합니다.System crash: power failure나 다른 hardware/software failure로 인해 system이 crash가 발생한 상황을 말합니다.Fail-stop assumption: non-volatile st..

Timestamp-Based Protocols 각각의 Transaction Ti에 대해 unique한 timestamp TS(Ti)를 할당합니다. timestamp는 transaction이 사작될 때 할당되며, timestamp는 logical counter를 기반으로 할당해도 됩니다. *굳이 real-time일 필요는 없습니다. 그냥 Transaction들의 시작 시간을 구분할 수 있기만 하면 됩니다. 그리고 이 timestamp 순서대로 serialize하는 것이 목표입니다. Timstamp-Ordering Protocols TSO(TimeStamp Ordering protocols)는 데이터 항목 Q마다 W-timestamp(Q): 성공적으로 write(Q)를 실행한 가장 큰 timestamp, 즉..

Deadlock Handling system이 deadlocked되었다는 것은 일련의 transaction들이 서로 상대방이 lock을 해제하기를 무한정 기다리는 상황을 의미합니다. 대부분의 locking protocol에서는 deadlock의 발생가능성이 항상 있습니다.2025.06.06 - [[학교 수업]/[학교 수업] Database] - [Database] Concurrency Control [Database] Concurrency ControlConcurrency control Concurrency control의 목표는 DBMS가 Serializable하고 Recoverable하며 가급적이면 Cascadeless인 스케줄을 생성하도록 스케줄링 결정을 내리는 것입니다.2025.05.25 - [[..

Concurrency control Concurrency control의 목표는 DBMS가 Serializable하고 Recoverable하며 가급적이면 Cascadeless인 스케줄을 생성하도록 스케줄링 결정을 내리는 것입니다.2025.05.25 - [[학교 수업]/[학교 수업] Database] - [Database] Transaction [Database] TransactionTransaction Concept Transaction이란 프로그램의 실행 단위입니다. 예를 들어 $50을 A계좌에서 B계좌로 이동하는 Transaction은 다음과 같습니다: 이 과정에서 두 가지 issues가 있을 수 있습니다. (1) 만약 hardwahw-hk.tistory.com DBMS Scheduler는 높은 수준..

Basic Steps in Query Processing 일반적으로 DBMS에서 Query를 처리하는 과정은 다음과 같습니다: (1) Parsing and translation - SQL을 구문 검사한 후 관계 대수식(Relational Algebra)의 형태로 변환하는 과정입니다.(3) Evaluation - 선택된 계획을 query-excution engine이 실제로 실행해 결과를 반환하는 과정입니다. Basic Steps in Query Processing: Optimization relational algebra는 정말 많은 수의 같은 의미를 갖는 표현들을 가질 수 있습니다: 따라서 어떤 순서로 primitive operation들을 실행시킬 것인지를 평가해야하며, 이 과정을 통해 결과적으로 ..

Write Optimized Indices B+-tree의 경우는 write-intensive한 일에 대해서, 즉 쓰기 연산이 많은 작업에서는 비효율적일 수 있습니다. 하나의 leaf노드강 하나의 I/O가 필요한데, 총 100개의 record들에 대해 write operation을 수행하고 싶으면 최악의 경우 100번의 I/O가 필요할 수 있습니다. 따라서 write에 집중된 작업에 특화된 방법이 필요했고 그것이 Log-structured merge tree (LSM tree)입니다. Log Structured Merge (LSM) Tree LSM tree는 매우 빠른 insertion을 제공하며, 그대신 B+-tree에 비해 조금 느린 search performance를 보여줍니다. *search co..

Transaction Concept Transaction이란 프로그램의 실행 단위입니다. 예를 들어 $50을 A계좌에서 B계좌로 이동하는 Transaction은 다음과 같습니다: 이 과정에서 두 가지 issues가 있을 수 있습니다. (1) 만약 hardware failure나 system crashes와 같이 다양한 종류의 failure가 중간에 발생하는 경우 어떻게 대처해야하는지, (2) 그리고 하나의 Transaction만을 수행하면 performance가 좋지 않으니 어떻게하면 여러개의 transaction을 동시에 처리해야하는지... 가 있습니다. * 위 예시 transaction에서 A:= A - 50은 local buffer(memory)에서 이뤄지는 연산이지 실제 DB인 disk에 적용되는..

static hashing 일반적으로 bucket이라고 부르는 storage space는 4KB입니다. *OS의 Page단위와 맞추기 위해서. hash function은 bucket의 위치를 가르키는데 사용됩니다. search key의 값을 hash function h에 넣어 bucket의 address를 가져옵니다. 서로 다른 search key를 h의 입력으로 넣어도 같은 bucket address를 가르킬 수도 있습니다. 따라서 bucket 안에서의 탐색 또한 필요합니다. hash index는 bucket에 records들의 address(pointer)들이 있는 것을 말하며, hash file-organization은 bucket안에 실제 records들이 존재하는 것을 말합니다. *b+-tree..