소소한 지식 저장소

1. Serializability (직렬 가능성)기본 가정: 각 트랜잭션은 데이터베이스의 일관성(consistency)을 보존함따라서, 트랜잭션 집합을 직렬적으로(순차적으로) 실행하면 데이터베이스 일관성이 보존됨직렬 가능 스케줄(Serializable Schedule): (동시 실행될 수 있는) 어떤 스케줄이 직렬 스케줄(serial schedule)과 동일한 결과를 가질 때스케줄 동등성(equivalence)의 형태에 따라 다음 개념들이 발생함:충돌 직렬 가능성 (Conflict Serializability)뷰 직렬 가능성 (View Serializability)2. Conflicting Instructions (충돌 명령어) 트랜잭션 T_i의 명령어 I_i와 T_j의 명령어 I_j가 충돌하는 경우는 ..

조인 연산 예시비용 추정 예시를 위한 student 및 takes 테이블의 카탈로그 정보:n_{student} (student 튜플 수): 5,000f_{student} (student 블로킹 팩터): 50 (블록 당 50개 튜플)b_{student} (student 블록 수): 100 (5000 / 50)n_{takes} (takes 튜플 수): 10,000f_{takes} (takes 블로킹 팩터): 25b_{takes} (takes 블록 수): 400 (10000 / 25)V(ID, student) (student의 ID(PK) 고유값 수): 5,000V(ID, takes) (takes의 ID(FK) 고유값 수): 2,500takes의 ID는 student를 참조하는 외래 키(Foreign Key)..

비용 추정을 위한 통계 정보- 데이터베이스 시스템 카탈로그는 비용 추정을 위해 다음 통계 정보를 유지함n_r: 릴레이션 r의 튜플 수l_r: 릴레이션 r의 튜플 크기b_r: 릴레이션 r의 튜플을 포함하는 블록 수f_r: 릴레이션 r의 블로킹 팩터 (하나의 디스크 블록에 저장할 수 있는 최대 튜플 수)V(A, r): 릴레이션 r의 속성 A에 나타나는 고유 값(distinct values)의 수이는 Pi_A(r)의 크기와 동일함만약 A가 키(key)라면, 튜플 수(n_r)와 동일함릴레이션 r의 튜플이 물리적으로 파일에 함께 저장되는 경우, 블록 수 b_r는 [n_r / f_r]로 계산됨비용 추정을 위한 근사치 접근 (페이지 28)통계 정보는 매번 계산하기에 비용이 크므로 근사치를 이용해 계산정확한 통계를 유..

쿼리 최적화 (Query Optimization) 개요- 주어진 쿼리를 처리하는 데 가장 효율적인 **쿼리-평가 계획(query-evaluation plan)**을 선택하는 프로세스목표: 동일한 결과를 생성하는 여러 전략 중 비용(cost)이 가장 적은 계획을 찾는 것중요성: 최적화 여부에 따라 쿼리 수행 시간이 며칠에서 몇 초로 단축될 수 있음두 가지 최적화 측면: 관계 대수 수준: 더 효율적인 동등한(equivalent) 표현식 찾기전략적 수준: 연산(operation) 수행을 위한 구체적인 알고리즘 (예: Hash Join, Merge Join) 및 인덱스(index) 사용 여부 결정비용 기반 최적화 (Cost-Based Optimization) 단계- 옵티마이저는 비용 추정(cost estimat..

정렬 (Sorting)데이터베이스 시스템에서 정렬이 중요한 두 가지 이유:사용자 요구: SQL의 ORDER BY 절을 통해 사용자가 결과의 정렬을 명시적으로 요구.효율적인 연산: 조인과 같은 관계 대수 연산은 입력 데이터가 정렬되어 있을 때 훨씬 효율적으로 수행 가능.정렬 기법:인덱스 활용: - 인덱스를 사용하여 논리적으로 정렬된 순서대로 데이터를 읽는 방법. - 하지만 이 경우 각 튜플에 접근할 때마다 디스크 접근이 발생하여 비용이 매우 높을 수 있음.내부 정렬 (Quicksort): 관계(데이터)가 메모리에 전부 올라갈 정도로 작을 때 사용.외부 정렬 병합 (External Sort-Merge): 관계가 메모리보다 커서 한 번에 처리할 수 없을 때 사용하는 기법1단계: 정렬된 부분 집합 (Run) 생..

1. Secondary Index를 이용한 동등(Equality) 조건 선택 (A4)- Secondary Index는 Primary Index와 달리 데이터가 물리적으로 정렬되어 있지 않은 경우에 사용A4 (Secondary B+-Tree, 동등 조건)후보 키(Candidate Key)에 대한 검색: - 검색하려는 키가 고유한 값(unique)이라면, Primary Index와 유사하게 인덱스 트리의 높이(hi​)만큼 탐색하고, 실제 데이터 블록에 한 번 더 접근후보 키가 아닌 컬럼에 대한 검색: - 검색 결과로 여러 개의 레코드가 반환될 수 있으며, 이 레코드들은 물리적으로 서로 다른 데이터 블록에 흩어져 있을 수 있음- 따라서 인덱스 탐색 후, 조건을 만족하는 n개의 레코드를 가져오기 위해 각각 I/..

쿼리 처리의 3가지 기본 단계- 쿼리 처리는 크게 구문 분석 및 변환, 최적화, 그리고 평가의 세 단계로 이루어짐 구문 분석 및 변환 (Parsing and Translation)사용자가 작성한 SQL 쿼리의 문법이 맞는지 확인하고, 관계들이 유효한지 검증사람이 사용하기 좋은 비절차적 언어인 SQL을 시스템이 이해하기 쉬운 내부 표현(주로 절차적인 확장 관계 대수)으로 변환최적화 (Optimization)변환된 관계 대수 표현은 여러 가지 동등한 표현으로 바뀔 수 있음예를 들어, salary 인 교수의 salary를 찾는 것은 두 가지 동등한 표현이 가능σ_salary Π_salary(σ_salary 쿼리 최적화 프로그램(Optimizer)은 이러한 여러 동등한 실행 계획(Evaluation Plan) ..

1. 복잡한 함수 종속성 다듬기: 정규형 커버 (Canonical Cover)- 주어진 함수 종속성(FD) 집합이 복잡하거나 불필요한 정보를 포함하는 경우에 '정규형 커버(Canonical Cover)' 사용 정규형 커버란?정규형 커버는 주어진 FD 집합 F와 논리적으로 동등하면서, 더 이상 단순화할 수 없는 최소한의 FD 집합- Fc​를 의미- 즉, F로부터 유추할 수 있는 모든 종속 관계를 Fc​로부터도 똑같이 유추 (F+=Fc+​).- 정규형 커버는 다음 세 가지 조건을 만족해야 함불필요한 속성(Extraneous Attribute)이 없음모든 FD의 왼쪽(결정자)은 유일(Unique)함불필요한 FD가 없음정규형 커버 계산 과정정규형 커버는 다음과 같은 단계를 통해 계산결합 (Union Rule)..

데이터베이스를 설계할 때 가장 중요한 목표 중 하나는 '불필요한 데이터 중복을 최소화'하는 것중복된 데이터는 삽입, 삭제, 수정 시 이상 현상(Anomaly)을 일으킬 수 있으며, 데이터의 일관성을 해치는 주범임이러한 문제를 해결하기 위한 체계적인 프로세스가 바로 정규화(Normalization)1. 정규화의 초석: 함수 종속성(Functional Dependency) 파헤치기- 정규화를 이해하기 위해서는 먼저 함수 종속성(Functional Dependency, FD)의 개념을 확실히 알아야 함- 간단히 말해, 어떤 속성(Attribute)의 집합이 다른 속성의 값을 유일하게 결정할 때 "함수 종속성이 있다"고 말함표기: α → β (α가 β를 함수적으로 결정)의미: 릴레이션 내의 두 튜플(행)이 α ..

1. 기본 개념 (Basic Concepts)데이터베이스 설계의 목표목표: 불필요한 중복(redundancy) 없이 필요한 정보를 모두 표현(저장)할 수 있는 Schema핵심 질문: 어떤 attribute들을 갖는 어떤 table을 둘 것인가?스키마 정의R = (A B C D E) ← single relation schema 정의DB1 = {R1, ..., Rn} ← DB schema 정의 (set of relation schemas)설계 문제점동일한 문제에 대해서 여러 가지 디자인이 가능함어떤 것이 더 좋은 디자인인가? 왜 더 좋은 디자인인가?2. 스키마 결합의 문제점예시: instructor와 department 결합 instructor와 department를 inst_dept로 결합할 경우:IDna..