데베응 기말 정리

6. Relational Database Design

 

E-R 다이어그램을 좋은 relational design 만드는법

-data redundancy(데이터 중복성) 제거

-모호함 없이 쉽게 retrieval(검색)할수 있게 정보 제공

-schema를 일반적인 form으로 design하기

 

정보 repetition 방지: 두개의 relation을 하나의 relation으로 나타내는거 고려해보기 혹은 Decomposition하기

ㄴ Lossy Decomposition: 테이블 분해 후 다시 결합했을때 원래 없던 정보가 만들어지거나 왜곡되는 분해문제

 

Lossless Decompostion:R을 R1 R2로 분해해도 정보손실x → 분해된 relation 써야함!

r(R): schema R을 가진 r의 instance

ㄴ r을 R1과 R2로 project하고 natural join 하면 r 나옴

ㄴㄴ 만약에 loss가 있다면 r보다 더 많은 정보가 나옴 (만약 두명 이상 같은 이름가지면 더 많아지고 같은이름 없으면 더 적어짐)

R을 R1, R2로 분해할때 R1∩R2→R1 또는 R1∩R2→R2를 만족하면 무손실 분해. * R1∩R2가 R1또는 R2의 super key면됨!

이때, R1∩R2→R1: R1∩R2가 R1의 super key이자 primary key이고 R2의 foreign key이다.

 

Normalization Theory: R이 good form(반복정보 x)가 아니면 relation들로 분해하기(무손실 분해!)

legal instance: 현실 데이터의 모든 제약조건을 만족하는 relation

Functional dependency(a→b): relational schema R안에 속성 a,b가 있을때 legal 관계 r(R)에 대해 어떤 튜플 t1과 t2가 a를 만족하면 b도 만족한다. * 속성 a값을 알면 b값을 반드시 알 수 있다

 

Closure: A → B이고 B → C이면 자동으로 A → C인것처럼 암시적으로 있는 functional dependency. F의 closure은 F+로 나타냄

Super key: K →R이고 K가 R의 super key라면 K의 값만으로 해당 행을 구분가능 ex) ID

Candidate key: 최소 Super key ex) {name, ID}는 더 줄일수있지만 {name}은 더 못줄이는 candidate key임

Trivial Functional Dependencies: a안에 b가 속하면 a →b는 자명하다(trivial).

 

Armstrong’s Axioms

1. Reflexive rule: Y⊆X이면 X→Y

2. Augmentation rule: X→Y이면 XZ→YZ

3. Transitivity rule: X→Y, Y→Z이면 X→Z

ㄴ Sound: 실제로 참인 FD만 생성, Complete: 참인 FD 모두 생성 가능

ㄴㄴ 단점: n개의 속성에 대해 2^n의 가능한 조합이 있고 왼쪽이랑 오른쪽에 2^n씩 있다고 하면 최악의 경우 2^n*2^n의 조합을 봐야함

 

Rules inferred from Armstrong’s Axioms

1. Union rule: A→B and A→C이면 A→BC

2. Decomposition rule: A→BC이면 A→B, A→C

3. Pseudotransitivity rule: A→B, CB→D이면  AC→D

 

a⁺ 계산 알고리즘

result := a        // 처음 시작한 속성 집합
while (result가 더 이상 변하지 않을 때까지)
   F의 각 FD b → g에 대해
       if b ⊆ result then
           result := result ∪ g

 

Attribute Closure활용

- Testing for superkey: a+가 R의 모든 속성을 포함하면 a는 super key

- Testing functional dependencies: a→b가 성립하는지 확인하려면 b⊆a+ 인지 확인하면됨

- Computing closure of F: 모든 속성 집합의 a⁺ 계산

 

Canonical Cover: functional dependencies F에서 관계 업데이트 할때마다 dependency 위반 안하게 해야하는데, 모두 확인하면 비용이 드니까 동일한 범위의 단순한 버전으로 파악함. F+=Fc+ 둘은 같은 closure을 갖지만 Fc+는 중복을 제외한 최소한의 형태. left가 중복된FD없음 있으면 합침!! (a →b, a →c 이면 a →b, c로) 

 

Extraneous(불필요) Attributes: Canonical Cover를 만들 때 불필요 속성 제거 필수!

left: a→b에서 a의 속성 하나(A)를 없애도 여전히 a→b가 F+에서 추론가능하면 A는 왼쪽에서 불필요(extraneous), FD 강화

right: a→b에서 b의 속성 하나(A)를 없애도 여전히 F+로 A가 추론가능하면 A는 오른쪽에서 불필요, FD 약화

ㄴF’ = (F - {a→b}) ∪ {a→(b-A)}, a⁺ 계산 후 A 포함 여부 확인

ㄴㄴright 예시: F={AB →CD, A →E, E →C}라고 할때, AB →CD에서 C를지우고 (AB)+구하면 {A,B,C,D,E}나옴 따라서 C는 AB →CD에서 extraneous함!

 

Dependency Preservation: R의 분해 Ri의 속성만 가진 Fi가 F+의 dependency라고 할때, (F1 ∪ F2 ∪ ... ∪ Fn)+ = F+을 만족하면 dependency 보존이 성립한다. -> 원래 존재하던 FD가 분해 후에도 유지되어야함 (join없이 검사가능!) 

 

BCNF(Boyce–Codd Normal Form): 모든 함수적 종속성 α → β 에 대해 α → β 가 trivial dependency (β ⊆ α) 이거나 α가 R의 superkey (왼쪽거가 superkey가 아니면 위반) → relation 분해해서 만족하게 만들기.

ㄴ relation R이 있고 F가 있을때, F내부 모든 fd가 superkey인지만 확인하면 됨

ㄴㄴ 분해된 테이블에선 F+까지 봐야함 

result = {R}
while (R 안에 BCNF 위반 FD가 존재) :
    a → b 선택 (a는 슈퍼키 아님, a ∩ b = ∅)
    R을 (R - b) 와 (a, b)로 분해

b를 삭제하여 superkey를 만들고 (a,b)테이블로 분해 ( R → (R − b) + (a, b))

 

3NF(Third Normal Form): 모든 FD a →b 에 대해 아래 조건 중 1개 이상 만족하면 됨

 

• α→β 가 trivial dependency (즉 β⊆α)
• α 가 superkey
• β−α 의 각 attribute가 R의 candidate key에 포함

ㄴ좌변이 superkey가 아녀도 우변이 candidate key의 일부면 ㅇㅋ해줌!!

bcnf는 redundancy 제거에 강하지만 모든 dependency를 보존할수없어 join이 필요해짐, 3nf는 더 널널해서 실용적임

 

1NF(Atomicity): 더이상 못쪼갬

2NF: 1NF 만족하고 모든 non-key attribute는 primary key에 완전 함수 종속해야 함 ex)

2nf 예시

Denormalization: 성능을 위해 normalization을 깨고 중복허용, 조회속도 빠르지만 데이터 중복과 갱신 불일치 위험有

ㄴ 대안: 비정규화 테이블 생성/Materialized view 사용

 

7. Physical Storage Systems

volatile storage(휘발성): RAM

non-volatile storage: HDD, SSD

캐시위에는 cpu, cpu로 갈수록 속도 빠르고 휘발됨

primary(cache, main memory): 휘발성

secondary(flash memory, magnetic disk):비휘발성, on-line storage로도 불림

tertiary(optical disk, magnetic tapes):비휘발성, 속도 느림, off-line storage로도 불림, 아카이브용으로 쓰임

 

Storage Interface

- Disk interface 표준: SATA, SAS, NVMe(셋 중 가장 빠름, PCle 커넥터랑 함께 이용해 지연을 낮추고 전송속도 높임)

- SAN: 많은 양의 디스크가 다수의 서버에 고속의 네트워크로 연결되어있음

- NAS: disk system interface 대신 networked file system protocol로 연결함

Disk 성능 측정 기준

1. Access time: 읽기/쓰기 요청 발생시점부터 데이터 전송이 시작될때까지 걸리는 시간

ㄴ Seek time: arm을 올바른 track(줄)으로 재위치 시키는 시간

ㄴ Rotational latency: sector(줄안에서 칸)가 head 아래에 올때까지 걸리는 시간

2. Data-transfer rate: Disk에서 데이터 검색할 수 있는 속도

 

Disk block: 공간 할당/검색하는 logical unit, 작은블록은 더 transfer하고 큰건 더 많은 공간 낭비됨

Sequential access pattern: 첫번째 블록에서만 disk seek 요구됨

Random access pattern: 어떤 위치에서든 disk seek 요구됨, 찾는데 많은 시간 걸려서 전송률 낮음

IOPS: 디스크가 초당 지원할 수 있는 무작위 블록 읽기 횟수

MTTF: 디스크가 failure없이 계속 run할 것으로 기대되는 평균 시간

 

Flash Storage

NAND flash: NOR보다 저렴, page단위로 읽어야함, 덮어쓰기 하려면 페이지를 지워야함

논리 페이지주소를 물리페이지 주소로 remapping해서 erase 기다리지 않아도됨, 새 물리공간에 즉시 write하고 나중에 remove함

 

SSDs: parallel read 지원

RAID: 여러개의 디스크를 병렬로 사용하여 고용량과 고속 보장, 데이터 중복 저장해서 하나 고장나도 복원가능

ㄴ Redundancy: 디스크 고장났을때 재구축에 사용할 수 있는 추가 정보 저장

Mirroring: 모든 디스크 복제, write할때 두 디스크 둘다 함, 읽기는 어디든지 ok

 

Disk 접근 최적화 방법

1. Buffering: 메모리 버퍼에 disk block 저장

2. Read-ahead: 곧 요구될 것으로 기대 될 트랙에서 추가 블록 읽기

3. Disk-arm-scheduling: disk-arm 움직임 최소화 되게 알고리즘 설정

4. File organization: 파일을 가능한 연속된 곳에 할당, 파일이 조각나있는 경우 조각난거에 순차적으로 접근

5. Non-volatile write buffers

 

8. Data Storage Structures