[정처기] 데이터 베이스

■ 데이터 베이스 (DBMS, DataBase Management System)

- 특정 조직 내 필요하 데이터들의 모임, 공용으로 소유/유지/이동하는 공용 데이터

 

■ 스키마(Schema)

• 외부 스키마(서브 스키마)
  • 사용자 관점의 스키마 → 하나의 DB에 여러 개의 외부 스키마 존재
  • 사용자, 프로그램마다 다양한 형태의 논리적 구조로 존재
• 개념 스키마
  • 사용자와 DB 관리자 관점의 스키마 / DB의 전체적인 논리적 구조
  • 일반적으로 하나의 DB에는 하나의 개념 스키마가 존재 → 데이터 개체/관계/제약조건/접근권한/무결성 규칙 명세
• 내부 스키마
  • DB 설계자/개발자 관점의 스키마
  • 개념 스키마를 물리적 저장장치에 구현하는 방법을 정의 → 물리적 구조 / 내부 레코드의 물리적 순서 

 

■ 데이터 독립성

- 논리적 독립성: 응용 프로그램 영향없이 데이터베이스 논리 구조 변경
- 물리적 독립성: 응용 프로그램 및 논리 구조 영향없이 데이터의 물리적 구조 변경

 

■ 데이터 언어

• DDL(Data Definition Language): 데이터베이스 구조/제약 조건 정의
• DML(Data Manipulation ~): 데이터 처리/조작에 사용되는 언어
• DCL(Data Control ~): 데이터의 보안, 권한, 무결성, 권한 검사, 병행 제어를 위한 언어

 

■ 데이터 베이스 설계 순서  ← ★ 순서 외우기(요개논물구)

1. 요구조건 분석: 데이터 베이스의 사용 용도 / 요구사항 / 요구 조건 명세서 작성
2. 개념적 모델
   • 현실 세계의 인식을 추상적 개념 세계로 표현
   • 독립적인 개념 스키마 모델링 / 트랜잭션 모델링 / E-R 모델
3. 논리적 모델
   • 개념적 모델을 컴퓨터가 처리할 수 있는 구조로 표현(관계 모델)
   • 종속적인 논리 스키마 설계 / 트랜잭션 인터페이스 설계 / 정규화
   • 논리적 데이터 베이스 구조로 Mapping / 스키마의 평가 및 정제
4. 물리적 모델
   • 데이터의 실제 저장 방법 및 접근 경로 표현(레코드 형식/순서)
   • 목표 DBMS 종속적인 물리적 구조 데이터로 변환 / 반정규화
   • 오브젝트, 접근방법, 인덱스, 뷰 용량 설계 / 트랜잭션 작성 → 저장 레코드의 형식/순서/접근 경로 설계
5. 구현: DBMS에서 SQL로 작성한 명령문 실행 후 데이터베이스 실제 생성

※ 데이터 모델링: 현실 내 복잡한 데이터 구조를 단순/추상화하여 체계적으로 표현

 

■ 데이터 모델 구성 요소

- 구조 (Structure): 논리적 개체 간 관계, 데이터 구조, 정적 성질 표현
- 연산(Operation): 실제 데이터를 처리하는 작업 명세로 데이터베이스 조작 도구
- 제약 조건(Constraint): DB에 저장될 수 있는 실제 데이터의 논리적 제약 조건

 

■ 개체 - 관계 모델 (E-R Model / Entity-Realation Model)

• 개체(Entity): 독립적이고 구별 가능한 모든 것
  • 개체 타입: 개체를 구성하는 속성들의 집합
  • 개체 인스턴그: 실제 값을 가지면서 실체화된 개체
  • 개체 세트: 개체 인스턴스들의 집합
• 속성(Attribute): 개체가 가진 고유의 특성 / 가장 작은 논리적 단위(원)
• 관계(Relationship): 두 개체 간의 의미 있는 연관성 및 연결 구조(마름모) → 일대일(1:1) / 일대다(1:N) / 다대다 (N:N)

 

■ E-R 다이어그램 표기법

※ 점선: '관계-속성 연결'

 

■ 관계형 데이터베이스 용어

• 릴레이션(Relation)이라는 표(Table)로 표현
• 속성(Attribute) = 열 = 피드 / 튜플(Tuple) = 행 = 레코드
  차수(Degree): 속성의 개수 / 기수(Cardinality): 튜플의 개수
• 도메인(Domain): 하나의 속성에서 취할 수 있는 원자 값들의 집합(ex. 성별: 남/여)
• 릴레이션 인스턴스: 릴레이션에 실제로 저장된 데이터 집합

※ 릴레이션 특징
- 튜플과 속성은 유일하며 순서는 무의미함
- 튜플은 삽입/삭제 등에 의해 계속 변함 / 튜플은 서로 상이한 값을 ㄹ가짐
- 속성의 값은 분해 불가 (원자성) / 동일할 수 있음
- 튜플을 식별하기 위해 속성(필드)의 일부를 Key로 설정
- 속성은 Null 값을 가질 수 있으나, 기본키에 해당되는 속성은 Null 값을 가질 수 없음

 

■ 키(Key)

• 후보키(Candidate Key)
  • 기본키로 사용 가능한 속성 / 모든 릴레이션에는 후보키 존재
  • 모든 튜플에 대해 유일성 O, 최소성 O
    ※ 유일성: 하나의 키 값으로 하나의 튜플 유일하게 식별
    ※ 최소성: 모든 레코드 식별하는데 최소한의 속성으로만 구성
• 기본키(Primary Key)
  • 후보키 중에서 선택되어, 중복된 값•NULL 값 X
  • 유일성/최소성 만좃, 튜플 식별하기 위해 반드시 필요한 키
• 대체키(Alternate Key)
  • 후보키가 둘 이상일 때 기본키를 제외한 나머지 후보키
• 슈퍼키(Super Key)
  • 한 릴레이션 내 속성들의 집합으로 구성된 키
  • 모든 튜플에 대해 유일성 O, 최소성 X
• 외래키(Foreign Key)
  • 다른 릴레이션의 기본키를 참조하는 속성 or 속성들의 집합
  • 참조되는 릴레이션 기본키와 대응되어 릴레이션 간 참조 관계

 

■ 무결성(Integrity)

• 개체 무결성
  • 기본키를 구성하는 어떤 속성도 중복/NULL X
  • 기본키의 속성 값이 NULL값이 아닌 원자 값을 갖는 성질
• 도메인/속성 무결성
  • 릴레이션 내 튜플들이 각 속성의 도메인에 지정된 값만 가짐
• 참조 무결성
  • 외래키는 NULL 또는 참조 릴레이션의 기본키 값과 동일
  • 릴레이션은 참조할 수 없는 외래키 값을 가질 수 없음
• 사용자 정의 무결성
  • 속성 값들의 사용자가 정의한 제약 조건에 만족
• 데이터 무결성 강화
  • 데이터 특성에 맞는 적절한 무결성을 정의하고 강화
  • 강화 방법: 제약조건, 어플리케이션, 데이터베이스 트리거

 

■ 접근 통제 기술 (AC, Access Control)

• DAC (임의 접근 통제)
  • 사용자의 신원/신분에 따라 접근 권한 부여
  • 데이터 소유자가  접근 통제 권한 지정/제어
  • 객체 생성자가 모든 권한 갖고, 다른 사용자에게 허가
  • SQL 명령어: GRANT / REVOKE
• MAC (강제 접근 통제)
  • 주체와 객체의 등급을 비교 후 시스템이 접근 권한 부여
  • DB 객체별로 보안 등급 부여 및 사용자별로 인가 등급 부여
  • 자신보다 보안 높은 객체에 읽기/수정/등록 불가하나 등급 같은 객체에는 모두 가능, 자신보다 낮은 객체에는 읽기 가능
• RBAC (역할 기반 접근 통제)
  • 사용자의 역할에 따라 접근 권한 부여 (중앙관리자가 지정)
  • 다중 프로그래밍에 최적화

 

■ 뷰 (View)

- 기본 테이블에 기반을 둔 이름을 가지는 가상 테이블 (기본 테이블과 동일 형태)
- 저장장치 내 가상으로, 논리저으로 존재 (실존하는 물리적 존재X)
- 기본 테이블 및 뷰 삭제 시 해당 테이블/뷰를 기초로 정의된 다른 뷰도 자동 삭제
▷ 장점: 논리적 데이터 독립성 제공 / 데이터 자동 보안 제공 / 데이터 관리 용이
▷ 단점: 독집적 인덱스 보유 불가 / ALTER 변경 불가 / 삽입, 삭제, 갱신, 연산 제약

 

■ 정규화

- 이상(Anomaly) 현상이 발생하지 않도록 중복성/종속성을 최소화하기 위한 작업
- 논리적 설계 단계에서 수행하며, 속성 수가 적은 테이블로 분할되어 관리가 용이해짐
- 데이터 구조 안정성 최대화 / 데이터 삽입 시 릴레이션 재구성 필요 최소화

※ 이상현상 종류
1. 삽입 이상: 데이터 삽입 시 불필요한 데이터가 함께 삽입
2. 삭제 이상: 튜플 삭제 시 필요한 데이터도 함께 삭제
3. 갱신 이상: 일부만 수정되어 데이터 불일치 → 정보 모순 발생

1) 정규화 과정

제 1 정규형	모든 도메인(Domain)이 원자 값만으로 되어 있음
제 2 정규형	기본키가 아닌 속성이 기본키에 대한 완전 함수적 종속 만족 부분적 함수 종속을 제거한 정규형
제 3 정규형	기본키가 아닌 모든 속성이 기본키에 대해 이행적 함수 종속 관계(X→Y, Y→Z이면 X→Z)를 만족
BCNF	릴레이션 R에서 모든 결정자가 후보키
제 4 정규형	릴레이션 R에 다치 종속이 성립하는 경우 R의 모든 속성이 A에 함수적 종속 관계를 만족하는 정규형
제 5 정규형	릴레이션 R의 모든 조인 종속이 R의 후보키를 통해서만 성립

※ 반정규화: 정규화 과정 진행 후, 시스템 성능 향상 및 운영 편의성을 위해 의도적으로 데이터 중복/통합/분리를 허용해 정규화 원칙을 위반

※ 함수적 종속
- 완전 함수적 종속(Full Functional Dependency): 종속자가 기본키에만 종속
- 부분 함수적 종속(Partial ~): 기본키가 여러 속성으로 구성되어 있을 때 기본키를 구성하는 속성 중 일부만 종속
- 이행적 함수 종속(Transitive ~): X→Y, Y→Z이면 X→Z

제 1 정규형: 원자값 아닌 도메인 분해

 

제 2 정규형: 부분 함수 종속 제거

 

제 3 정규형: 이행 함수 종속 제거

 

BCNF: 모든 결정자가 후보키

 

■ 관계 대수 - 원하는 정보의 검색 과정을 정의하는 절차적 언어

① 순수 관계 연산자

σ	Select(선택)	조건을 만족하는 튜플들의 부분 집합(수평 연산)
ㅠ	Project(추출)	속성들의 부분 집합, 중복 제거(수직 연산)
⋈	Join(조인)	두 개의 릴레이셔능ㄹ 하나로 합쳐 새로운 릴레이션 형성
÷	Division(나누기)	A의 속성이 B의 속성 값을 모두 가진 튜플에서 (A⊃B) B가 가진 속성을 제외한 나머지 속성들만 추출

- 세타 조인: 두 릴레이션 속성 값을 비교 후 조건을 만족하는 튜플만 반환
- 동등 조인: 조건이 정확하게 '=' 등호로 일치하는 결과를 반환
- 자연 조인: 동등 조인의 결과에서 중복된 속성을 제거한 결과를 반환

② 일반 집합 연산자

∪	Union (합집합)	두 릴레이션의 합 추출 / 중복은 제거
∩	Intersection (교집합)	두 릴레이션의 종복되는 값만 추출
−	Difference (차집합)	A 릴레이션에서 B 릴레이션 간 중복되지 않는 값을 추출
×	Cartesian Product (교차곱)	두 릴레이션의 가능한 모든 튜플의 집합 → 속성/칼럼끼리 더하기 / 튜플끼리는 곱하기

 

■ 관계 해석 - 원하는 정보가 무엇이라는 것만 정의하는 비절차적 언어

논리 연산자	⋁	OR	원자식 간 "또는" 관계로 연결
	⋀	AND	원자식 간 "그리고" 관계로 연결
	¬	NOT	원자식에 대한 부정
정량자	∀	전칭 정량자	모든 가능한 튜플 "For All"
	∃	존재 정량자	어떤 튜플 하나라도 존재 'There Exists"

 

■ 트랜잭션 (Transaction)

- 데이터베이스 상태를 변환시키는 하나의 논리적 기능을 수행하기 위한 작업 단위

원자성(Atomicity)	트랜잭션 연산이 정상적으로 수행되거나 (Commit), 아니면 어떠한 연산도 수행되지 않아야 함 (Rollback)
일관성(Consistency)	시스템의 고정 요소는 트랜잭션 수행 전/후로 동일해야 함
독립성(Isolation)	개별 트랜잭션은 다른 트랜잭션의 간섭 및 영향 받지 않아야 함
영속성(Durability)	완료된 트랜잭션 결과는 영구적으로 기록되어야 함

- COMMIT: 트랜잭션 정상 종료 후 변경된 내용을 DB에 반영하는 명령어
- ROLLBACK: 트랜잭션 비정상 종료 후 모든 변경 작업을 취소하고 이전 상태로 원복
- REDO: 데이터베이스 비정상 종료 시 트랜잭션 시작(Start)와 완료(Commit)에 대한 기록이 있는 트랜잭션들의 작업을 재작업(이전 값을 이후 값으로 변경)
- UNDO: 데이터베이스 비정상 종료 시 시작은 있지만 완료 기록이 없는 트랜잭션들이 작업한 내용을 모두 취소 (이후 값을 이전 값으로 변경)

 

■ 데이터 회복 기법

• 즉시 갱신 기법(Immediate Update)
  • 트랜잭션 실행 상태에서 변경되는 내용을 바로 데베에 적용
    → 변경되는 모든 내용을 로그(Log)에 기록하여 장애 시 해당 로그 토대로 복원
    → Redo / Undo 모두 수행
• 지연 갱신 기법(Deferred Update)
  • 트랜잭션 수행 후 부분 완료될 때까지는 데베에 바로 적용하지 않고, 지연시킨 후 부분 완료 시 로그(Log)의 내용을 토대로 저장
    → 트랜잭션이 실패할 경우 Undo 없이 Redo만 수행
• 검사 시점 기법(Check point)
  • 트랜잭션 수행 중간에 검사시점(Checkpoint) 지정하여 검사 시점까지 부분 수행 후 완료된 내용을 중간중간 데베에 저장
• 그림자 페이징 기법(Shadow paging)
  • 로그 미사용 / 데베를 동일 크기의 페이지로 분할 후 각 페이지마다 복사하여 그림자 페이지 보관
    → 변경 내용은 원본 페이지에만 적용하여 장애 발생 시 해당 페이지 사용/회복

 

■ 로킹 단위 (Locking): 로킹의 대상이 되는 객체의 크기

- 로킹: 데베 병행 제어 위해 트랜잭션이 접근하고자 하는 데이터를 잠가(lock) 다른 트랜잭션이 접근하지 못하도록 하는 병행 제어 기법
- 대상: 데베 / 파일 / 레코드
- 로킹 단위▼ → 로크의 수▲ → 로킹 오버헤드▲ → 병행성(공유도)▲
- 로킹 단위▲ → 로크의 수▼ → 로킹 오버헤드▼ → 병행성(공유도)▼

※ 병행제어 기법 종류
- 로킹 기법: 일관성과 무결성을 유지하기 위한 트랜잭션의 순차적 진행을 보장 (병행 수행 트랜잭션들 간 동일 데이터 접근 차단)
- 낙관적 검증: 일단 트랜잭션 수행하고, 트랜잭션 종료 시 검증을 수행
- 타임 스탬프 기법: 타임 스탬프를 부여해 부여된 시간에 따라 트랜잭션 수행
- 다중버전 동시성 제어(MVCC): 타임스탬프를 비교해 직렬가능성이 보장되는 적절한 버전을 선택해 접근하도록 함

 

■ 분산 데이터베이스

- 논리적으로는 하나의 시스템에 존재하나, 물리적으로는 연결된 다수의 컴퓨터에 분산되어 있는 데이터 베이스
- 구성요소: 분산 처리기(분산된 지역 컴퓨터) / 분산 데이터 베이스 / 통신 네트워크
- 목표: 위치 투명성(Location) / 중복 투명성(Replication) / 병행 투명성(Concurrency) / 분할 투명성(Division) / 장애 투명성(Failure)
→ 사용자 입장에서 데베의 위치/중복/병행/분할/장애 여부 인식할 필요X

 

■ 데이터베이스 관련 용어

• 인덱스(Index)
  • 데이터베이스 테이블 검색 속도 향상을 위한 저장 위치 자료
    → 데이터 빠른 조회를 위한 위치 정보(포인터) 포함
• 클러스터(Cluster)
  • 자주 사용하는 테이블 데이터를 동일 위치에 저장하여 데이터 접근 효율 향상
• 데이터베이스 이중화
  • 서비스 장애 대비하여 데베 중복(복제)하여 관리
  • Eager 기법: 모든 이중화 데이터 즉시 업데이트
  • Lazy 기법: 변경 사항을 새로운 트랜잭션으로 각 노드에 전달
• 파티셔닝(Partitioning)
  • 대용량 데베를 여러 섹션으로 분할(조회 속도 향상)
  • 범위 분할: 파티션 키 값을 범위로 분할
  • 해시 분할: 해시 함수 적용 후 반환된 값으로 파티션 분할
  • 합선 분할: 범위 분할 후 해시 함수 적용하여 다시 분할
• 복구 시간 목표(RTO, Recovery Time Objective)
  • 서비스 중단 후 복원까지 최대 시간
    → 서비스를 사용할 수 없는 최대 허용 시간
• 복구 시점 목표(RPO, Recovery Point Objective)
  • 마지막 데이터 복구 후 허용되는 최대 시간
    → 허용 가능한 최대 데이터 손실량 결정

 

■ 알고리즘

- 선형 검색: 하나씩 순서대로 비교하며 원하는 결과값을 찾아내는 검색
- 이진 검색: 검색 수행 전에 데이터 집합이 정렬되어야 함

1) 알고리즘 시간 복잡도

복잡도	알고리즘	설명
O(1)	해시 함수	자료 크기 무관 일정한 속도
O(log₂N)	이진 탐색	로그형 복잡도
O(n)	순차 탐색	선형 복잡도: 입력 자료를 하나씩 처리 (정비례)
O(Nlog₂N)	힙 / 합병(병합) 정렬	선형 로그형 복잡도
O(N²)	선택 / 버블 / 삽입 / 퀵 정렬	대부분의 경우 힙/합병 보다 복잡도가 큼 N² > Nlog₂N (N > 2)

2) 알고리즘 설계 기법
- Divide and Conquer: 문제를 최소 단위로 나누어 풀고, 각각을 다시 병합
- Dynamic Programming: 더 작은 문제의 연장선으로 여기고 과거에 구한 해를 활용
- Greedy: 현 시점에서 가장 최적으로 방법을 선택
- Backtracking: 모든 조하을 시도하여 문제의 답을 선택 (→ 문제의 부모 노드로 되돌아간 후 다른 자손 노드 검색)

3) 정렬 알고리즘
- 삽입: 이미 정렬된 파일에 새로운 레코드를 순서에 맞게 삽입하여 정렬
- 선택: N개의 레코드 중 최소값을 찾아 첫번째에 배치, 나머지 N-1개 레코드 중 최소값 찾아 두번째 배치, 이를 반복하여 정렬
- 버블: 인접한 두 개의 레코드 키 값 비교 후 크기에 따라 레코드 위치 교환
- 퀵: 자료 이동 최소화 후 하나의 파일을 부분적으로 나눠가면서 정렬
- 2-way 합병: 이미 정렬된 2개의 파일을 한 개의 파일로 합병하여 정렬
- 쉘: 입력 파일을 매개변수 값으로 서브파일 구성 후 각 서브파일을 삽입 정렬 방식으로 순서 배열하는 과정 반복
- 힙: 완전 이진 트리를 이용한 정렬

4) 정렬 방법
① 선택 정렬(Selection sort)
- 최소값을 찾아 첫번째 숫자와 위치 교환, 이후 정렬된 값을 제외한 최소 숫자를 정렬되지 않은 숫자 중 첫번째 숫자와 다시 위치 교환, 이를 반복

② 삽입 정렬 (Insert sort)
- 두 번째 숫자와 첫번째 숫자 비교하여 크기 순으로 정렬, 이후 3번째 숫자를 앞서 정렬된 숫자들 사이에 크기 순에 맞게 재정렬, 이를 반복

③ 버블 정렬 (Bubble sort)
- 왼쪽부터 인접한 두 숫자 간 크기 비교하여 위치 교환, → 1 Pass 마다 정렬되고 숫자들 중 가장 큰 숫자를 오른쪽으로 밀어서 배치