[101] 데이터베이스시스템(DBMS)

1. 데이터베이스의 이해 

1.2 데이터베이스 시스템의 개요

https://encrypted-tbn0.gstatic.com/images?q=tbn:ANd9GcSIzYRCA2EaOX1i8vZMu9okSQm5uyOJ3Gz6fr3qjrSapA&s

https://dataonair.or.kr/publishing/img/dbguide/edu/db0602_0101.gif

데이터베이스관리시스템(DBMS)

데이터베이스관리시스템(DBMS)이 사용자에게 서비스 형태로 제공되는 앱 = 데이터베이스시스템(Database System)

1.3. 데이터 베이스 관리 시스템의 목적 (a.k.a 파일 처리 시스템과의 비교)

1960년대 유일한 운영체제 지원 데이터관리 수단 = 파일(file)

이러한 방식을 '파일 처리 시스템(File Processing System)'이라고 한다.

DBMS 이전 대다수의 시스템이 이러한 파일 처리 시스템 사용.

파일 처리 시스템의 문제점: 1) 데이터의 종속 2) 중복 3) 무결성 훼손 및 4) 동시 접근 

1) 데이터의 종속: 해당 프로그램에 종속되는 파일이 생긴다. 데이터 구조의 변경이 프로그램의 변경으로 이어지며 유지보수 비용 증가. 타 프로그램과 공유 불가.

2) 데이터의 중복: 데이터 중복은 다음 세 가지 관점에서 문제가 생긴다. (1) 일관성 문제 (2) 보안성 문제 (3) 경제성 문제

3) 데이터의 무결성 훼손

4) 동시 접근 이상

 

1.4. 데이터베이스 관리 시스템의 특징

1) 프로그램 및 데이터의 추상화: 데이터가 어떻게 물리적으로 저장장치에서 관리되는지 상세한 정보보다는 사용자가 데이터의 의미만으로 접근할 수 있도록 데이터에 대한 개념적인 표현을 제공.

2) 자기 기술성(메타 데이터): DBMS가 데이터베이스 자체 뿐만 아니라 데이터에 대한 정의나 설명에 대한 것까지 포함하고 있는 특성

3) 데이터 공유와 일관성: 여러 사용자의 요청 작업을 최대한 동시에 처리함으로써 전체적인 처리성능을 향상시킴. 또한 이러한 동시 작업 시 발생 가능한 데이터 일관성 문제를 해결하기 위해, 단일 논리 작업을 수행하는 트랜잭션과 동시성 제어기법이라는 명령어 집합 포함.

4) 다중 뷰: 사용자들은 필요에 따라 서로 다른 관점으로 데이터를 바라볼 필요가 있으며, 이를 위해 사용자의 역할과 권한에 맞는 데이터에 접근 가능하도록 데이터베이스에 대해 필요한 부분만 추출해서 제공.

1.5 데이터베이스 관리 시스템의 구조

 

 

1) 데이터 추상화, 데이터 독립성 충족 필요
2) 3단계 구조: 내부 - 개념 - 외부

• 내부 단계: 가장 낮은 추상화 단계. 내부 스키마에 의해 기술됨. 레코드 유형 정의 등 구체적인 사항에 대해 정의.
• 개념 단계: 데이터 베이스의 전체 구조를 추상화 하는 단계. 
• 외부 단계: 추상화의 최상위 단계. 외부 스키마(=뷰)에 의해 기술됨.

3) 단계간 사상(mapping)

• 외부-개념 사상: 외부 스키마(뷰) 와 개념 스키마 간의 대응 관계. 논리적 데이터 독립성 확보 기능.
• 개념-내부 사상: 개념 단계의 데이터 스키마가 디스크 내의 내무 필드와 어떻게 대응하는가를 정의. 즉, 물리적 데이터 독립성 확보.

 

 

1.6. 데이터베이스 언어

1) 데이터 정의 언어(DDL): 데이터 베이스의 물리적 저장 구조와 데이터의 원시수준의 특징을 규정하는 언어. 

2) 데이터 조작 언어(DML): 데이터 베이스에 의해 구조화된 데이터에 사용자가 접근 및 사용할 수 있도록 지원하는 언어

1.7. 데이터베이스 관리 시스템 아키텍쳐

1) 중앙집중식

2) 클라-서버(2티어)

3) 클라-웹서버-서버(3티어): 2티어 구조에 비즈니스 규칙을 저장하는 중간 계층인 WAS를 추가한 형태.

1.8. 데이터베이스 사용자 및 관리

 

2. 데이터베이스 모델링

2.1. 데이터베이스 모델링의 이해

모델링 단계

제안요청서(RFP) -> 사용자 요구 사항 분석 -> 개념적 데이터 모델링 -> 논리적 데이터 모델링 -> 물리적 데이터 모델링 -> 내부 스키마 저장

• 요구 사항 분석: 도출, 분석, 기록으로 단계 세분화됨. 
  • 도출 --(요구사항 명세서, requirement specification)--> 분석 --(요구사항 정의서, requirement definition)--> 기록 단계
• 개념적 데이터 모델링: 추상화 기법 사용. 이를 위해 다양한 개념적 데이터 모델들이 제안 및 사용되었고, 대표적인 것이 E-R 모델.
• 논리적 데이터 모델링: DBMS에 맞는 구현 데이터 모델인 스키마로 변환하는 작업. 일반적으로는 관계형 모델 사용.
• 물리적 데이터 모델링: 논리적 데이터 모델링 후 생긴 논리 스키마는 데이터들의 논리적 구성만을 명시하는데, 이를 데이터베이스 파일의 물리적 저장 방식을 결정하는 과정.

2.2 사용자 요구사항 분석 과정

2.3. ER 모델(Entity-Relationship Model)

• 정의 및 관련 용어:
  • 개체(entity): ER모델의 가장 기본 요소. 실세계에 존재하는 유,무형 대상. - ex) 학생, 교수, 과목, 계좌
  • 개체 집합(entity set): 실세계에 존재하는 유,무형 대상들의 모임.
  • 속성(attribute): 그 개체를 특정 지을 수 있는 다수의 속성들. 일부 속성은 개체를 유일하게 구별하는 역할. - ex) 학생번호, 학생 이름, 성별, 나이
  • 값(value): 구체적 속성 값 - ex) 학생번호(속성)-201934(값)
• 하나의 DB는 다수의 개체 집합으로 이루어진다. 
• 이러한 ER모델을 표기하는 방법은 시간을 거치며 발전해왔는데, 최근에는 UML(Unified Modeling Language)라고 불리는 표기법을 사용한다.
  • 키(key): 모든 개체를 고유하게 구분하는 존재
  • 도메인(domain): 속성이 가질 수 있는 모든 가능한 값들의 범위

• 관계 집합: 
  • 정의: 
• 속성:
  • 단순 속성 / 복합 속성: 들여쓰기. 여러 값을 가질 수 있는 속성이어야 한다. ex) 나이, 
  • 단일값 속성 / 다중값 속성: { }
  • 유도 속성 / 저장 속성: () 다른 속성값으롭퉈 유도되어 결정되는 속성값과 실제 값을 저장해야만 의미가 유지되는 속성값.
• 제약 조건
  • 사상수
  • 참가 제약조건: 관계에 참여하는 개체 집합의 범위
    
    • 하나의 실선(일부 참가)
    • 이중 실선(전체 참가)
  • 키 속성
    • 밑줄 표시

속성. 3) 나이는 생년월일에 따라 유추(유도)될 수 있다.

참가 제약조건 예시. 강의 우측의 이중 실선(=)은 과목 집합 전체가 교수 집합에 참가한다는 의미이다. 즉, 모든 '과목'에 '교수'가 필요하다. 모든 과목 개체 집합은 특정 '교수'와 관계를 맺어야 하는 전체 참가인 셈이다.

2.4. ER모델 기호

ERD -> 그림 예시로 주어지면 읽을 줄 알아야 함.

약한 집합 관계: 기본 식별 개체가 삭제되면 함께 삭제되는 개체. 키 속성이 일반 밑줄이 아닌 점선 밑줄 처리된다.

•  

3. 관계형 모델

논리적 데이터 모델링 단계를 다룬다. 논리적 데이터 모델링 단계는 개념 모델링 다음 단계로, 데이터베이스에 저장될 데이터의 논리적 구조인 스키마(schema)를 산출하는 단계였다. 

대표적 구현 모델인 관계형 모델의 기본적 이론과 용어에 대해 학습한다.

구체적으로는 릴레이션을 조적하기 위한 관계 대수 연산자, 관계 ㅇ대수 연산식, ERD를 관계형 모델로 변환하는 방법.

 

 

 

#4. MySQL을 이용한 데이터베이스 모델링

#5. SQL

6. 정규화

6.1. 좋은 릴레이션과 나쁜 릴레이션

나쁜 데이터베이스 모델링

1) 데이터의 중복

2) 갱신 이상: 삽입 이상, 삭제 이상, 수정(또는 갱신) 이상

좋은 릴레이션의 고려사항

1) 한 릴레이션 내의 컬럼 간의 관계 분석

2) 원하지 않는 데이터의 종속과 중복 제거

3) 새로운 컬럼들이 데이터베이스에 추가될 때, 기존 컬럼과 관계 수정 최소화

 

6.2. 함수적 종속성

6.2.1. 함수적 종속성의 정의

어떤 릴레이션을 여러 개의 릴레이션으로 분할함으로써 데이터의 중복을 최소화 시키는 방법 = 정규화

-> 그럼 어떤 컬럼을 떼네고 어떻게 릴레이션을 분할해야 하지? -> 함수적 종속성 고려

 

1) 릴레이션 인스턴스(스키마 자체 X 인스턴스 O)를 분석하여 속성들(컬럼들) 간의 연관관계를 표현한 것

2) 릴레이션 효율성을 향상시켜 좋은 릴레이션으로 변환하는데 이용되는 중요한 개념

임의의 릴레이션 스키마 R의 인스턴스 r에 포함되는 서로 다른 두 레코드 r1, r2와 컬럼 집합 X와 Y에 대해, r1[X] = r2[X] 일 때, r1[y] = r2[y] 이면 함수적 종속성 X -> Y가 성립한다. 

그림1. 함수적 종속성 판별 예시

ex) 위 그림1을 보면 등급이 할인율을 결정한다. 예를 들어 GOLD(등급) 면 무조건 5%(할인율). 즉, 등급은 할인율에 종속된다. 등급은 "결정자", 할인율은 "종속자"가 된다. 

 

함수적 종속성의 확장

하나의 릴레이션에는 수 개~수십 개의 함수적 종속성이 존재할 수 있다. 우리가 눈으로 찾아낸 게 실제로 존재하는 모든 종속성을 찾았다고 효율성 여부를 판단하기 어렵다. 

1) 함수적 종속성은 릴레이션의 효율성 여부에 중요한 판단 기준.

2) 그러나 릴레이션의 인스턴스만으로 내재된 모든 함수정 종속성을 찾아내기 어렵다. 

3) 판별되지 않은 모든 함수적 종속성을 찾기 위해 추론 규칙을 사용하여 함수적 종속성을 확장.

4) 클로저(closure): 판별된 함수적 종속성 집합으로부터 유추할 수 있는 모든 함수적 종속성 집합.

* F: 눈으로 찾아낸 모든 종속성 집합

** F+ : 추론 규칙을 사용해(=함수적 종속성을 확장해) 찾아낸 최종 모든 종속성 집합.

 

함수적 종속성의 추론 규칙 based on 암스트롱 공리

그림2. 암스트롱 공리를 바탕으로한 추론 규칙 6가지. 4~6번은 암스트롱 공리를 확장한 규칙이다.

 

카노니컬 커버

1. 함수적 종속성 추론 규칙으로 확장된 클로저에는 "자명한 종속성"과 "중복된 종속성"을 포함한다.

• 자명한 종속성: A-> A / 의미가 당연
• 중복된 종속성: X -> AB, X->B / 의미가 여러번 존재. -> 문제

2. 불필요한 함수적 종속성(중복된 종속성)을 제거한 표준형으로 변환 후 정규화를 수행해 효율성을 높이자! -> 카노니컬 커버!

3. 표준형 조건

• F의 모든 함수적 종속성의 오른편 속성(=종속자)은 반드시 1개
  • {x,y} -> {z} (o)
  • {x} -> {a,b} (x, 가능은 하지만 표준형은 아님)
• F에서 X -> A를 X의 진 부분집합 Y에 대하여 Y->A 로 교체했을 때, 그 집합이 F와 동등한 집합이 불가능.
• F에서 어떤 함수적 종속성을 제거했을 때, 그 집합이 F와 동등한 집합이 불가능.

6.3. 정규화

정규형의 개념

1. 정의: 이상 현상을 최소화하도록 특정 조건을 갖춘 릴레이션의 형식

2. 분류: 제1정규형~제5정규형까지 존재한다. 보통 현업에서는 2~BC정규형이 많이 쓰인다.

정규형의 분류. 1->5로 갈 수록 정규형 조건이 더 까다로워진다.

3. 기능: 릴레이션을 효과적으로 표현, 검색 알고리즘을 효과적으로 작성할 수 있도록 지원, 바람직하지 않은 삽입, 수정, 삭제 등 이상 발생 방지, 새 데이터 삽입 시 릴레이션 재구성의 필요성 축소

 

제1정규형

• 가장 조건이 단순한 정규형
• 릴레이션 스키마에서 정의된 모든 속성의 도메인이 원자값을 갖는 상태
• 관계형 모델 조건에 따라 자동 적용되는 정규형

제2정규형

• 제1정규형 + 기본키가 아닌 속성들이 기본키에 대해 완전 종속인 상태

제3정규형

• 제2정규형 + 기본키가 아닌 속성들이 어떤 키에도 이행적으로 종속하지 않는 상태.

BC정규형

• 어떤 릴레이션 스키마 R에서 성립하는 X -> A 형태의 모든 함수적 종속성에 대해 X가 R의 수퍼키인 상태.

 

 

7. 데이터 저장과 파일

7.1. 물리적 저장 장치(메모리)

	휘발성	비휘발성
장치	캐시, 메인 메모리	플래쉬 메모리, 자기 디스크, 광학 디스크, 테이프 장치

* 휘발성(volatile): 전원 공급이 중단되면 데이터가 소멸되는 특징.

7.2. 논리적 저장 장치(파일)

 

7.2.1. 파일의 구성

• 파일: 데이터 영구 저장 위해 사용되는 가장 기본이 되는 논리적 구조
• 블럭: 파일을 고정 길이로 분할하여 생긴 균등한 크기의 데이터 묶음. 일반적으로 메모리와 디스크 간 데이터 전송 단위로 사용.
• 레코드: 블럭을 구성하는 요소. 더 이상 분리될 수 없는 최소 데이터 저장 단위.
  • 고정 길이 레코드: 고정적인 바이트 수를 갖는 레코드를 저장하는 방법 - ex) 이름(보통 3글자)
    1.  데이터 접근. 모든 레코드는 k바이트로 구성. -> i번째 레코드 접근 (i-1)*k+1 바이트부터 k개의 바이트를 읽어 접근.
       • 문제: 길이가 고정되어 있기 때문에 잔여 공간 발생
       • 해결책: 
         1. 남겨둔다(잔여 고정 길이 레코드 할당) -> 메모리 낭비 발생.
         2. 한 레코드를 두 블럭으로 나누어 저장한다. -> 효율적 저장 가능 but 레코드 접근 시 두 블럭을 접근해야 함(연산 2배)
       • 문제: 레코드 삭제시 해당 레코드가 저장된 위치에 빈 공간 생성되고, 이렇게 노는 공간, 즉 메모리 낭비가 발생하게 된다.
       • 해결책:
         • 마지막 레코드로 공백 대체 -> 공간의 낭비는 막지만 레코드 순서가 달라져 검색 시 시간이 더 낭비될 수 있다.
         • 삭제 레코드 이후의 레코드를 모두 앞으로 당김. -> 낭비도 막고 순서도 지키지만(검색 효율도 그대로), 모든 레코드 이동 시 시간이 많이 걸린다.
         • 가용 리스트 관리.
           • 동작 원리: 파일 헤더에 공백 레코드 포인터를 담고, 삭제 시 해당 공백을 가리키는 포인터를 추가한다. 새 레코드 추가 시 포인터를 따라가면 됨. -> 이점 많음. 가장 많이 사용되는 방법.
  • 가변 길이 레코드: 블럭에 저장되는 레코드의 길이가 서로 다를 떄 레코드에 가변적인 길이를 할당하는 방법.
    • 필요 상황 ⭐️
      • 한 블럭 내에 저장되는 레코드 유형이 둘 이상
      • 길이가 고정되지 않은 컬럼의 개수가 하나 이상
      • 레코드가 멀티셋을 허용한 컬럼을 가질 때 
        • 멀티셋: 레코드의 컬럼값이 여러 개인 컬럼. -> 관계형 모델에는 없지만, 몇 다른 모델에서는 이러한 멀티셋을 지원하는 경우 있음.
    • 동작 원리:
      • 첫 번째 들어오는 가변 길이 컬럼/행 있다? (포인터 저장)
      • 해당 포인터 따라가면 값 + 해당 값 앞에 특정 길이만큼 Null(가용 공간) 저장
        
        • 슬롯 페이지 구조 ⭐️: 가변 길이 레코드를 저장, 관리하기 위해 사용되는 대표적인 구조. 
          
          • 블럭 초반부는 블럭 헤더로 구성. 블럭에 대한 요약 정보를 담고 있어 레코드 빠른 검색 가능케 함.
          • 신규 레코드는 중간에 있는 가용 공간의 뒤쪽에서부터 쌓이게 됨.

슬롯 페이지 구조

 

7.2.2. 파일 처리 시스템 

 

 

• 파일 구조화
  • 정의: 파일 수준에서 레코드 관리하는 기법
  • 종류: 힙 파일 구조, 순차 파일 구조, 해시 파일 구조
    • 힙 파일 구조: 저장 순서 고려 없이 파일 내 임의의 위치에 배치
      • 저장은 빠르나, 추후 검색 시 많은 시간 소요도
    • 순차 파일 구조: 레코드들이 탐색키 기준으로 정렬되어 저장
      • 삽입/삭제에 많은 비용
      • 오버플로우 블럭: 순차파일구조에서 레코드의 정렬된 상태 유지를 위해 삽입된 신규 블럭
    • 해시 파일 구조: 해시 함수 사용하여 블럭 주소 계산

7.3. 저장장치 관리

7.3.1. 데이터 관리의 필요

저장 장치 접근(= 블록 전송)

• 파일(논리적 관점의 저장 객체)
• 블록(물리적 단위의 저장 객체)

• 버퍼 관리자: DBMS상의 소프트웨어는 필요 블록 있을 시 버퍼 관리자에게 해당 블록 요청.
  • 요청된 블럭이 버퍼에 있으면 버퍼 관리자는 블럭이 위치한 메모리 주소를 프로그램에 전달
  • 없으면, 버퍼 관리자는 버퍼 내의 새로운 공간 할당 후 해당 블럭 적재
  • 더 적재할 공간 없으면 버퍼에 있는 기존 블럭을 선택해 해지하고 해당 블럭 적재
    • 버퍼 교체 전략: 운영체제 메모리 부분 참조
      • LRU(Least Recently Used): 가장 적게 참조된 블럭을 교체
      • MFU(Most Frequently Used): 특정 기간 동안 가장 여러번 사용된 블럭을 선택해 교체
  • 고정 블록 설정 및 블럭 강제 출력 등

8. 인덱싱과 해싱

8.1. 인덱스의 이해

정의:

인덱스란, DBMS에서 요청된 레코드에 빠르게 접근할 수 있도록 지원하는 데이터와 관련된 부가적 구조

인덱스 탐색키 이용해 해당 레코드가 저장된 블럭을 디스크 저장장치 또는 메모리에서 파악해 해당 블럭 빠르게 적재

 

종류: 순서 인덱스, 해시 인덱스

• 순서 인덱스: 특정 값에 대해 정렬된 순서 구조
• 해시 인덱스: 버킷의 범위 안에서 값의 균일한 분포에 기초한 구조로 해시 함수가 어떤 값이 어느 버킷에 할당할지 결정

평가 기준⭐️: 접근 비용, 유지 비용, 공간 비용 -> 삭제 비용 X

8.2. 순서 인덱스

특징: 탐색키 활용한 빠른 접근. 

 

종류: 밀집 인덱스, 희소 인덱스, 다단계 인덱스

밀집 인덱스와 레코드

희소 인덱스와 레코드

 

• 밀집 인덱스
  • 모든 레코드에 대해 인덱스 엔트리 쌍 가짐
  • -> 검색 속도 빠름(적은 양의 디스크-메모리 입출력으로  but 모든 레코드에 대해 포인터(인덱스) 가지기 때문에 메모리 많이 차지. 
• 희소 인덱스
  • 일부의 레코드에 대한 탐색키 값만을 인덱스 엔트리 쌍 가짐.
  • -> 인덱스가 차지하는 메모리 더 적지만 검색 속도는 더 느림.

다단계 인덱스

• 다단계 인덱스 ⭐️
  • 밀집 인덱스와 희소 인덱스의 장점만 결합. 
  • 밀집 인덱스처럼 인덱스 용량이 커, 인덱스의 크키 > 메모리 크기인 경우, 인덱스 블ㄹ럭을 읽어 들이는 입출력(I/O)비용이 증가해 탐색 시간이 증가.
  • 인덱스에 대한 인덱스를 구성하자!
    • 내부 인덱스: 레코드를 직접 가리키는 인덱스. 밀집 인덱스로 구성. 
    • 외부 인덱스: 레코드를 직접 가리키는 인덱스(내부 인덱스)를 가리키는 인덱스. 희소 인덱스로 구성.

8.3. B+- 트리 인덱스 ⭐️

8.3.1. 정의

• 다단계 인덱스의 일종
• 순서 인덱스 문제: 파일이 커질수록 데이터를 탐색하여 접근하는 비용이 커진다는 단점.
• 해결책: B+- 트리 인덱스. 경로 길이가 같은 높이 균형 트리 형태로 구성된 인덱스로, 검색의 속도를 일정하게 향상시켜 안정적 데이터 검색이 이루어질 수 있도록 함. 현대 상용 DBMS에서 가장 널리 사용되는 순서 인덱스의 일종.

 

8.3.2. B+- 트리의 구조

B+- 트리 구조

단말 노드의 구성 - 좌) 실제 레코드 포인터 / 우) 다음 단말 노드 포인터

• 인덱스 세트: 루트 노드와 중간 노드로 구성. 단말 노드의 탐색키 값을 찾아가는 경로를 제공. [n/2]~n사이의 개수를 자식으로 소유. *n:차수
• 순차 세트:  단말 노드로 구성. 모든 노드가 순차적으로 서로 연결되어 있다. 탐색키에 대한 실제 레코드를 지칭하는 포인터를 제공. [(n-1)/2]개의 탐색키를 포함. 

8.3.3. 검색, 삽입, 삭제 연산

 

8.4. 해싱

8.4.1. 해싱과 버킷

• 해시(hash): 함수를 사용해 데이터 배분 및 접근하는 기법
• 버킷(bucket): 한 개 이상의 레코드를 저장할 수 있는 저장공간의 단위. 크기는 디스크 블록의 크기와 일치?

 

 

8.4.2. 정적 해싱

특징: 1) 버킷의 갯수가 고정된 해싱 기법 2) 키 값이 K인 레코드 삽입 3) 키 값이 K인 레코드 검색

단점: 1) 데베 크기 커질 수록 성능 감소 2) 초기 비용 큼 3) 재구성시 대량의 비용 발생 => 동적 해싱 기법 제안됨

 

문제1) 충돌과 동거자

• 충돌: 서로 다른 두 레코드가 동일한 버킷에 대응. 
• 동거자 ⭐️: 동일한 버킷에 있는 레코드들.

 

 

 

 

 

 

 

 

문제2) 오버플로 ⭐️

버킷에 레코드를 저장할 여유 공간이 없는 상황

추가적인 버킷을 할당하여 처리

오버 플로우가 발생할 수록 접근 시간이 길어지고 해시 성능 저하

 

=> 해시 인덱스

 

 

 

 

8.4.3. 동적 해싱

정의: 버킷의 개수 가변적. 데베 증대 혹은 축소에 따른 인덱스 구조를 조절 및 해시 함수를 동적 변경

• 확장성 해싱 ⭐️: 동적 해싱의 일종으로 디렉터리(버킷 주소 테이블)와 버킷의 2단계 구조.
  
  • 모조키(pseudo key): 확장성 해싱 함수는 먼저 레코드의 키값을 일정 길이의 비트 스트링으로 만드는 데 이 때 사용되는 키. 모조키의 처음 d비트가 디렉터리에 접근하는 데 사용된다.
  • 버킷 헤더: 모조키의 첫 번째 숫자부터 숫자 i까지 일치함을 표시.

디렉터리에 숫자 3(버킷 헤더)은 모조키 첫 3글자를 넣겠다는 의미이다. 각 버킷의 3,3,2,1은 각 모조키의 첫 n숫자를 보겠다는 의미이다. 디렉토리에 담겨진 모조키 시작 3자리 숫자들은 각 조건(000, 001, 01, 1로 시작하는 값)에 맞는 버킷에 담긴다.

 

 

 

 

 

 

8.5. 비트맵 인덱스 ⭐️⭐️

비트맵 인덱스

개념: 탐색키의 중복 비율이 높은 컬럼을 대상으로 하는 질의를 효율척으로 처리하기 위해 고안된 특수 형태의 인덱스. 예를 들어, 탐색키가 성별인 경우. 50%는 여자, 50%는 남자가 된다.

 

비트맵: 간단한 비트의 배열. 0과 1의 나열.

• i번째 비트가 0이다. = 조건과 일치 하지 않는다.
• i번째 비트가 1이다. = 조건과 일치한다.

비트맵 생성 원리

예제에서 볼 수 있듯이, 컬럼에 대해 값이 비교적 작은 규모의 집합으로 만들 수 있다.

 

예제)

step 1.

step 2. 논리곱 수행

 

 

step.3. 생성된 비트맵을 바탕으로 추출 / 100100 뜻 = 1과 4번째 레코드가 '참' -> 이것만 뽑아냄.

 

 

특징:

1) 컬럼에 대한 값의 범위가 유한하고 비교적 개수가 적은 규모일 때 용이

2) 실제 릴레이션 크기에 비해 비트맵 인덱스의 크기는 매우 작은 것이 장점.

 

 

10. 트랜잭션과 동시성 제어

10.1. 트랜잭션 이해

데이터 동시 접근의 문제

 

트랜잭션: 데이터베이스를 조작하기 위한 하나의 논리적 단위를 이루는 일련의 연산의 집합. 데이터베이스를 사용하여 처리하는 작업을 하

 

나의 묶음으로 인식해 묶음 단위로 실행되도록 정의한 개념.

ex) 예금 인출

작업 단위: 예금 1000원 인출

일련의 연산: Read(A), A=A-1000, Write(A)

• Read(A): 잔액 읽기
• A=A-1000: 연산 수행
• Write(A): 연산 수행 후 결과로 잔액 재설정

이러한 연산 작업을 하나의 묶음으로 데이터를 처리!

 

10.2. 트랜잭션 특징

ACID 특성⭐️

• 원자성(Atomicity): 하나의 트랜잭션에 포함된 모든 연산은 완전히 수행되거나 전혀 수행되지 않음
• 일관성(Consistency): 특정 트랜잭션이 수행되기 전과 후에 데이터 베이스가 일관된 상태를 유지
• 고립성(Isolation): 특정 트랜잭션이 데이터베이스를 갱신하는 동안 다른 트랜잭션에 의해 방해받지 않음
• 지속성(Durability): 완료된 트랜잭션의 결과는 어떠한 시스템의 장애에도 데이터베이스에 반영되어야 함
  • 트랜잭션 실행하다 시스템 오류 이후 실행결과가 데베에 반영되어 있는지 먼저 확인 후, 반영되지 않은 경우에만 트랜잭션 재실행.

10.3. 트랜잭션의 동작 방식

트랜잭션의 연산

• Read(X): DB에서 X라는 데이터를 읽은 후, 트랜잭션이 실행되는 메모리의 변수 X에 값을 저장하는 연산.
• Write(X): 트랜잭션이 실행되는 메모리의 변수 X에 값을 DB에 저장하는 연산.

트랜잭션 실행의 연산

• Commit
• Rollback

 

10.4. 트랜잭션의 동시성

동시성 고려

• 장)
  • 처리율, 자원 이용률 향상
  • 대기시간 감소로 인한 사용자 신뢰도 및 만족도 향상
  • 데이터의 가용성 향상
• 단)
  • 동시 실행으로 데이터 갱신 시 일관성 훼손 문제 발생(일관성, 무결성 훼손)
• 해결: 동시성 제어(cocurrencty control)
  • 다수의 트랜잭션이 성공적으로 동시에 실행되어도 일관성을 유지할 수 있도록 지원하는 기법.
  • 뒤에서 더 자세히

스케쥴(schedule)

• 트랜잭션에 포함된 연산의 실제 실행순서를 나타낸 것
  • 직렬 스케줄: 순차적으로 실행되는 스케쥴
  • 병렬 스케줄: 동시다발적으로 실행되는 스케쥴

직렬 가능 스케쥴

다수의 트랜잭션이 동시에 수행된 결과가 직렬 스케쥴의 결과와 동일한 스케쥴. 일관성 유지 가능한 스케쥴.

• 충돌: 서로 다른 트랜잭셔닝 연산을 수행할 때, 최소 하나의 연산이 Write 연산일 경우, 두 트랜재션은 서로 충돌(conflict)한다 라고 한다.
• 충돌 동등: 특정 스케줄 S가 있을 때 충돌이 일어나지 않는 연산의 순서를 바꿔서 충돌이 없는 스케줄 S'로 변환할 수 있는 상태.
• 충돌 직렬성 ⭐️: 순서 교환이 가능한 연산을 교환해, 직렬 스케줄의 연산과 동등하게 변환이 가능한 스케쥴

 

10.5 트랜잭션 회복

회복성

만약 트랜잭션 Ti가 실패하면 실패하기 전까지 실행되었던 모든 연산을 트랜잭션이 시작되기 이전 상태로 회복시켜야 한다.

Commit 된 순간, 취소가 불가하다.

 

회복 가능 스케줄(recoverable scedule)

모든 트랜잭션 순서쌍 Ti와 Tj에 대해, Ti가 기록한 데이터 항목을 Tj가 읽는다면 Ti의 커밋이 Tj 의 커밋보다 먼저⭐️ 나타나는 스케줄 의미.

즉, 스케줄에서 오류가 발생하더라도 Tj는 Ti가 커밋을 완료할 때까지 기다려야 함.

 

회복 불가능 스케쥴 / T6는 T5에 종속적이다. T5에 오류가 발생하여 트랜잭션을 롤백해야 한다면, T6도 취소해야 하기 때문. 하지만 이 때 T6는 커밋된 상황이기 때문에 취소가 불가하다. 따라서 T5가 실패해도 회복할 수 없는 상황이 되었다.

회복 가능 스케쥴 / T7의 롤백으로 인해 연쇄적으로 다른 트랜잭션도 롤백되는 연쇄적 롤백 유발 가능 스케줄이다.

 

비연쇄적 스케줄(cascadeless schedule)

연쇄적 롤백은 많은 연산을 동반하기 떄문에 연쇄적 롤백이 일어나지 않도록 스케쥴이 제한을 둔 스케쥴.

비연쇄적 스케줄

10.6 동시성 제어

앞서 언급된 '직렬화'과 '회복화'이 동시 실행 가능 여부와 회복  가능 여부를 판별하는 기법이었다면,

동시성 제어(concurrency control)은 실제 동시 실행을 가능하게 하는 기법이다.

 

이러한 동시성 제어 기법은 2가지 규약을 따른다.: 1) 락 기반 규약 2) 타임 스탬프 규약

10.6.1. 락 기반 규약

정의

락(lock)을 가지고 있는 트랜잭션만 진행 가능하다는 규약이다.

약간 화장실 키 같은 개념

 

종류

• 공유 락(shared lock): 트랜잭션 T가 데이터 항목 Q에 공유하는 형태의 락을 얻으면(S로 표기), T는 Q를 읽을 수는 있으나 쓸 수는 없다.
• 배타 락(exclusive lock): 트랜잭션 T가 데이터 항목 Q에 공유하는 형태의 락을 얻으면(X로 표기), T는 Q를 읽고 쓸 수 있다.

명령어

• LS(Q):
• LX(Q):
• UN(Q):

적법한 스케줄

• 스케줄 S가 라킹 규약을 준수하는 스케줄이면, S는 주어진 락킹 규약하에서 적법한 스케쥴이라고 한다. 
• 또한 모든 적법한 스케줄에서 각 트랜잭션들에 대해 사이클(cycle)이 포함되지 않으면(-> 들이 서로 환원상태가 된 것) 락킹 규약은 충돌 직렬성을 보장(=순서대로 진행)한다고 할 수 있다.
• 언락(UN, unlock)을 너무 뒤에서 몰아서 하면, 중간에 사이클이 생기는 좋지 않은 상황이 발생할 수 있다.

2단계 락킹 규약

락 기반 규약 중 하나로, 락을 요청'만' 할 수 있는 확장 단계와 반납'만' 할 수 있는 축소 단계로 나뉜다.

직렬성을 보장하나 교착상태를 예방할 수는 없다.

 

엄격한 2단계 락킹 규약

기존의 2단계 락킹 규약과 달리 트랜잭션이 모든 락을 유지하다 커밋되거나 중단될 경우에만 락을 해지한다.

 

10.6.2. 타임스탬프 기반 규약

락킹 규약에서 트랜잭션 간의 직렬성 순서는 락을 획득한 순서에 따라 결정된다.

직렬성 순서를 결정하는 또 다른 방법은 트랜잭션 간의 순서를 미리 선택하는 것이다.

여기에 가장 보편적으로 사용되는 규약이 타임스탬프 순서 규약이다.

 

트랙잭션이 시스템에 들어올 때 타임스탬프를 부여하는 시스템 클럭 방법과,

새로운 타임스템프가 발급될 때마다 증가되는 논리적 계수기 값을 설정하는 논리적 계수기 방법이 있다. 

 

일반적인 타임 스탬프 규칙 vs 토마스 기록 규칙

(작성 예정)

 

10.6.3. 교착상태

트랜잭션 간 상호대기 상태에 놓여 더는 진행이 불가한 경우 이를 교착상태(deadlock)이라고 한다.

 

DBMS에서는 트랜잭션의 교착상태 여부를 파악하고 처리하는 여러 방법을 사용한다.

1. 교착상태 방지(prevention)
   • wait-die 기법
     비선점유 기반. 락이 걸린 데이터 항목 요청 경우, 요청한 트랜잭션이 요청 받은 트랜잭션보다 먼저 시행된 경우(=요청한 쪽의 타임스탬프 값이 더 작은 경우)에만, 락이 반환되길 기다린다. (아니면 뺸 먹고 기다릴 수도 없다.)
   • wound-wait 기법
     선점유 기반. 락이 걸린 데이터 항목 요청 경우, 요청한 트랜잭션이 요청 받은 트랜잭션보다 나중에 시행된 경우(요청한 쪼그이 타임스탬프 값이 더 큰 경우)만, 락이 반환되길 기다린다. (아니면 뺸 먹고 기다릴 수도 없다.)
2. 교착상태 탐지와 복구(detection & recovery)
   • 탐지(detection): 대기 그래프(wait-for graph)라는 방향성 그래프를 이용해 교착상태를 확인 가능하다.
   • 회복(recovery): 희생자(victim, 롤백시킬 트랜잭션)을 선택한 뒤 롤백 시킨다. 간혹 무한정 기다림(starvation)이 발생하기도 한다.

11. 회복 시스템

11.1 회복 시스템 개요

11.1.1 실패의 유형

• 트랜잭션 실패: 논리적 오류 혹은 시스템 오류로 구분. 논리적 오류는 트랜잭션이 잘못된 데이터의 입력 등으로 정상 실행이 안되는 상태이고, 시스템 오류는 dBMS가 교착상태 같은 상황에 도달해 실행 지속이 어려운 상태.
• 시스템 장애: 하드웨어 고장 혹은 소프트웨어 오류로 인한 휘발성 저장장치의 내용 손실 및 트랜잭션 처리 중단 상태
• 디스크 실패: 비휘발성 디스크 저장 장치의 일부 혹은 전체의 손상 및 고장. 데이터의 손상 및 손살 상태.

11.1.2 회복 데이터의 구성

회복의 방법은 바로 복제본을 두는 것이다.

 

복제본 생성의 2가지 방법

• 백업(backup): 디비 일부 또는 전체를 다른 저장장치에 주기적으로 복제하는 방식
• 로그(log): 디비에서 변경 연산이 요청될 때마다 데이터 변경 이전 이후 값을 별도의 파일에 저장하는 방식

11.1.3. 저장장치 구조와 연산

순서: Input(X) > Read(X) > Write(X) > Output(Y)

 

11.2 로그 기반 회복

DB가 수행한 모든 수정 작업을 기록한 여러 종류의 로그를 사용해 회복하는 시스템

 

WAL(Write-ahead Log)

트랙잭션은 DB 수정 전, 로그 레코드를 생성해 기록한다.

 

11.2.1 로그 레코드 종류

Redo(Ti) 

• 트랜잭션 Ti 에 의해 수정된 새로운 값으로 DB의 데이터 값 수정. 
• <Ti start>를 갖고 있고 <Ti commit> 혹은 <Ti abort> 레코드를 포함할 경우, Ti 는 Redo 되어야 한다.

Undo(Ti) 

• 트랜잭션 Ti 에 의해 수정된 모든 데이터 항목을 이전 값으로 복귀 완료 후, <Ti abort>.
• <Ti start>를 갖고 있지만,  <Ti commit> 혹은 <Ti abort> 레코드를 포함하지 않을 경우, Undo 되어야 한다.

11.2.2 데이터베이스 변경과 커밋

11.2.3 회복의 유형

• 지연 갱신 회복(deferred update restore)
  부분 커밋까지는 디스크 반영을 지연시키고 로그에만 기록. 실패 시 별도의 회복 작업 없이 로그만 수정
• 즉시 갱신 회복(immdidate update restore)
  갱신 요청을 바로 디스크에 반영. 실패 시 디스크에 반영된 갱신 내용을 로그를 바탕으로 회복

11.2.4 체크 포인트를 이용한 회복

로그 기반 회복 시스템의 한계

시간이 지남에 따라 로그가 계속 증가해 로그 탐색 비용이 매우 커짐. -> 체크 포인트 기법 제안

 

체크 포인트 기법 발생시⭐️

• 현재 시점에 메인 메모리 버퍼 블록에 존재하는모든 레코드를 안정 저장 장치로 기록.
• 수정된 모든 버퍼 블럭을 디스크에 반영.
• 로그 레코드 <checkpoint ListT>를 안정한 저장장치에 기록.  -> checkpoint 시 실행된 트랜잭션( <start>가 있었던 모든 Ti)은 모두 ListT에 담기게 된다.

 

11.3 회복 알고리즘

11.3.1. 시스템 장애 후 회복 알고리즘

 

11.4. 백업

 

 

---

# Reference

<데이터베이스시스템>, 정재화 지음