ITPE Momentum

1. 관계 대수(relational algebra)

  - 절차 언어 : how, what 대상

[정의] 관계형 데이터베이스에서 원하는 정보와 그 정보를 어떻게 유도하는가를 기술하는 절차적 언어

[일반집합연산] 합집합, 교집합, 차집합(-), 카티션 프로덕트(X)
[순수관계연산] Select, Project, Join, Division, Rename

2. 관계 해석(relational calculus)

 - 비 절차 언어 : what

[정의] “어떻게 검색할 것인가” 보다 “무엇을 검색할 것인가” 만을 기술하는 선언적 표현법을 사용하는 비절차적 질의어

[구분] 투플 관계 해석(tuple relational calculus)와 도메인 관계 해석(domain relational calculus)으로 구분.

[관계 대수와의 차이점]
– 관계 해석은 하나의 선언적(declarative) 해석식으로 검색질의를 명시하며, 비절차적인 언어임
– 관계 대수에서는 연산들을 순차적으로 사용하므로 절차적인 성질을 가짐
– 두 언어의 표현력(expressive power)은 동등함

[정의] 물리적으로 다른 데이터베이스에 데이터를 수평 분할 방식으로 분산 저장하고 조회하는 방법

[특징] 성능개선(큰 데이터를 압축, 개별 테이블은 각 샤드에서 더 빠른 작업을 지원),
신뢰성 개선(한 샤드가 실패하더라도 다른 샤드는 데이터 서비스를 제공), 위치 추상화

[개념도]

- 샤드 키로 설정된 칼럼의 기반으로 각각의 값에 맞는 Shard 에 저장
- 사용하는 Application 단에서는 MongoS 라는 라우팅 프로세스만 연결하므로
 Shard 구조에 대해서 알 필요가 없음.

[분할방법]
1) Vertical Partitioning : 테이블 별로 서버를 분할하는 방식
2) Range based Partitioning : 하나의 feature 나 table 이 점점 거대해지는 경우 서버를 분리하는 방식.
3) Key or Hash Based Partitioning : 엔티티를 해쉬함수에 넣어서 나오는 값을 이용해서 서버를 정하는 방식.
4) Directory Based Partitioning : 파티셔닝 메커니즘을 제공하는 추상화된 서비스를 만듦.

[고려사항] 데이터 재분배, 조인불가, 파티션 등

[정의] DataBase 의 Semantic의 변화없이 Schema의 변경을 통해 관리 편의성이나 속도, 정합성 개선을 확보하는 일련의 작업

[목적] 구조 최적화, 품질 향상, Agile 개발 지원

[DB Smell]

1. 다목적 컬럼 : 단일컬럼이 다양한목적으로 사용

2. 다목적 테이블 : 단일 테이블이 다양목적 사용

3. 중복데이터 : 많은 행과 열을 보유한 테이블

4. 스마트 컬럼 : 하나의 컬럼이 다기능적 목적 수행가능한 컬럼

5. 변화의 두려움

6. 비정상적 참조경로

7. 테이블 관계의 부적절함

8. 조회성능 및 삽입성능의 저하

[유형]

구조 리팩토링(스키마의 구조적 변경)

데이터 품질(테이블 데이터값의 일관성 및 사용성 개선)

참조무결성(제약조건 추가)

아키텍처(외부 프로그램과 상호 작용방법 개선)

기능 변환(저장 프로시저의 품질, 트리거 개선 등)

[고려사항]
1) 기존 의미에 대한 변경을 가하지 않았는지, 정보에 대한 손실은 없는지 반드시 DB Regression Test 를 수행함
2) 복원 가능한 시나리오 및 검증체계 구축

[정의] 프로세스와 엔티티 타입에 대한 상관관계를 분석하여 데이터 모델의 정확성을 검증하기 위한 모델링 기법

[특징] 모델링 작업 검증, 중요 산출물, 테스트에서 사용, 인터페이스 현황 파악

[입력] 업무분해(기능분해도) → 프로세스, 데이터모델링(ERD) → 엔티티 타입

[관계] 데이터와 프로세스는 다:다

[특징] 모델링 검증, 테스트 설계, I/F 파악

[작성규칙] 상관분석표에서 행은 업무프로세스, 열은 엔티티타입

[점검]
① 모든 엔티티 타입은 CRUD가 한 번 이상 표기
② 모든 엔티티 타입에 'C'가 한 번 이상 표기
③ 모든 엔티티 타입에 'R'이 한 번 이상 표기
④ 모든 단위 프로세스는 하나 이상의 엔티티 타입에 표기
⑤ 두 개 이상의 단위 프로세스가 하나의 엔티티 타입을 생성 불가(잘못된 경우는 아니나 업무 규칙에 비추어 다시 한번 판단해 볼 필요 있음)

[정의] 릴레이션 R에서 특정 속성 X가 특정고유속성 Y를 결정짓는 관계

[표현] 함수 종속도(FDD: Functional Dependency Diagram) - 애트리뷰트들간의 함수 종속관계를 도식으로 표현

[함수종속성에 대한 정규화 규칙] - 두부이결다조
- 완전함수종속성(FD) : XY -> Z 일 때, X -> Z 가 성립하지 않고 Y -> Z 가 성립하지 않는 경우 Z는 XY에 완전함수종속
- 부분함수종속성(2NF) : XY -> Z 일 때, X -> Z 와 Y -> Z 중 하나만 성립하는 경우 부분함수종속. 제 2정규화 필요
- 이행함수종속성(3NF) : 릴레이션 R에서 속성 X -> Y이고, Y -> Z이면 X -> Z임.  제 3정규화 필요
- 결정자함수종속성(BCNF) : 함수적 종속이 되는 결정자가 후보키가 아닌 경우. 즉, X->Y 일때 X 가 후보키가 아님. BCNF 필요
- 다중값 종속성(4NF)
- 조인종속성(5NF)

[암스트롱 공리 규칙] - 재부이분합의

[정의] 현실 세계의 업무 프로세스를 추상화하여 데이터베이스의 데이터로 표현하기 위한 설계 과정

[단계] 요구사항분석 -> 개념적 모델링 -> 논리적 모델링 -> 물리적 모델링
 - 개념적일수록 추상적 --> 물리적일수록 구체적

[개념적 모델링 ERD 작성절차]
1) 주제영역 선정 : 하위주제 영역 또는 데이터 집합들로 구성업무 기능과 대응(상향식, 하향식, Inside-out, 혼합식)
2) 핵심데이터 집합 선정(Entity) : 데이터의 보관 단위로서 주제영역에서 중심이 되는 데이터 집합을 정의(독립중심, 의존중심, 의존특성, 의존연관데이터)
3) 관계설정(Cardinality) : 업무적 연관성에 따라 개체간 갖는 relationship 설정(1:1, 1:N, M:N, 순환관계)
4) 핵심속성 정의(Attribute) : 데이터 집합의 특성을 나타내는 항목 ==> (핵심속성 : 원자단위검증, 유일값 유무판단, 관리수준 상세화 결정)
5) 식별자 정의 (Identifier) : 데이터 집합을 유일하게 식별해주는 속성(PK 로 구현), PK, CK, AK, FK 로 구분.

[논리적 모델링 주요 Task]
1) 엔티티타입 도출 - 기본, 중심, 행위 엔티티타입 도출
2) 관계 도출 - 엔티티 타입간의 관계 도출
3) 식별자 도출 - PK, FK, UK, AK 등에 대한 정의
4) 속성 도출 - 기본, 설계, 파생속성을 정의함
5) 세부사항 도출 - 용어사전, 도메인정의, 속성의 규칙(기본값, 체크값)등 정의
6) 정규화 - 1 차,2 차, 3 차, BCNF, 4 차, 5 차 정규화 적용
7) 통합/분할 - 엔티티타입의 성격에 따라 통합,분할 수행- 수퍼/서브 타입 모델링 수행
8) 완료기준 task: 데이터 모델 검증 - 엔티티타입, 속성, 관계 등에 대한 적합성 검증

[물리적 모델링 주요 변환단계]
(1)일괄전환 : 1) Entity 를 Table 로 전환 : Sub Type 설계 방안 -> 2) 식별자의 PK 정의 : Artificial Key 검토, PK 컬럼 순서 검토 -> 3) 속성을 컬럼으로 전환 : 영문 컬럼명 매핑, 데이터 타입/길이 결정, Domain 정의, 컬럼 순서 결정
4) 관계를 컬럼으로 전환 : 참조무결성 규칙 및 구현방향 결정
(2)구조조정 : 슈퍼타입/서브타입 모델 전환 : 트랜잭션의 성격에 따라 전체 통합, 부분 통합, 개별 유저에 대한 의사 결정을 통해 데이터 모델 조정
(3)성능향상 : 성능을 고려한 반정규화 : SQL 활용 능력의 미흡으로 인한 빈번한 비정규화는 배제하도록 신중하게 검토

[정의] REDO중 역사 반복(Repeating history) 붕괴가 발생했을 때의 데이터베이스 상태를 복구하기 위해, 붕괴 발생이전에 수행했던 모든 연산을 다시 한번 수행하는 알고리즘

[특징]
- UNDO : 붕괴가 발생했을 때 완료되지 않은 상태였던 진행 트랜잭션은 UNDO 됨
- UNDO 중 로깅하여 도중 실패 시 반복 하지 않음: UNDO를 할 때에도 로깅을 함으로써
회복을 수행하는 도중에 실패하여 회복을 다시 시작할 때에 이미 완료된 UNDO 연산은 반복하지 않음

- WAL(Write-Ahead Logging)방식을 이용 : 데이터베이스 시스템에서 ACID의 특성 가운데 원자성과 내구성을 제공하는 기술의 한 계열이다. WAL을 사용하는 시스템에서 모든 수정은 적용 이전에 로그에 기록된다.

[회복 알고리즘의 3단계]
1단계) 분석단계 : 붕괴가 발생한 시점에 버퍼에 있는 수정된 페이지와 진행 트랜잭션을 파악,
REDO가 시작되어야 하는 로그의 위치를 결정
2단계) REDO단계 : 분석 단계에서 결정한 REDO 시작 위치의 로그로부터 로그가 끝날 때 까지 REDO를 수행,
REDO 된 로그 레코드의 리스틀 관리하여 불 필요한 REDO 연산이 수행되지 않도록 함
3단계) UNDO단계 : 로그를 역순으로 읽으면서 진행 트랜잭션의 연산을 역순으로 UNDO 함

[필요정보]
- 로그(LOG) : 페이지에 대한 갱신(write), 트랜잭션 완료(commit), 트랜잭션 철회(abort), 갱신에 대한 UNDO, 트랜잭션 종료(end) 시 기록, 각 로그 레코드마다 로그 순차번호LSN 할당. (LSN: 디스크에 저장된 로그 레코드의 주소로서 단조 증가 –Log Sequence Number)
- 트랜잭션 테이블 : 진행 트랜잭션에 대한 정보(트랜잭션 식별자, 트랜잭션 상태, 해당 트랜잭션의 가장 최근 로그레코드의 LSN 관리)
- 오손 페이지 테이블(dirty page table) : 버퍼에 있는 오손 페이지에 대한 정보(페이지 식별자, 해당 페이지에 대한 가장 최근 로그 레코드 LSN 관리)

[ARIES에서의 검사점 기록]

1.로그에 begin_checkpoint 레코드를 기록하기

2.로그에 end_checkpoint 레코드를 기록하기

   트랜잭션 테이블과 오손 페이지 테이블의 내용도 함께 저장한다.

3.특수 화일에 begin_checkpoint 레코드의 LSN을 기록하기

[ARIES에서 회복의 예]

[정의] 트랜잭션이 한 데이터 아이템을 접근하려 할 때, 그 트랜잭션의 타임스탬프와 접근하려는 데이터 아이템의 여러 버전의 타임스탬프를 비교하여, 현재 실행하고 있는 스케줄의 직렬가능성이 보장되는 적절한 버전을 선택하여 접근하도록 하는 기법

[특징]  판독 요청을 거절하지도, 대기하지도 않음.  트랜잭션간의 충돌문제는 대기가 아니라 복귀처리 함으로 연쇄 복귀초래 발생 가능성

[동작설명]
1) 데이터를 변경할 때마다 그 변경사항을 Undo 영역에 저장해 둔다
2) 트랜잭션 시작 시점 이후에 변경된(진행 중이거나 이미 커밋된) 값을 발견하면,
    Undo 영역에 저장된 정보를 이용, CR Copy 를 생성하여 그것을 읽는다. (SCN 이용)
3) 쿼리 도중에 배타적 Lock 이 걸린, 즉 변경이 진행 중인 레코드를 만나도 진행가능
※ SCN(System Change Number) : commit 발생시, 트랜잭션에 연속증가, 고유번호

※ CR Block : 읽기 일관성(Consistent Read) Block 아래 그림에서는 Data Block을 의미

[정의] 시스템에서 생성하는 고유 번호인 시간 스탬프를 트랜잭션에 부여하는 것으로 트랜잭션간의 순서를 미리 선택하는 방법

[종류] 시스템 시계, 논리적 계수기

[구성]
1) read_TS(X): 항목 X 의 읽기 타임스탬프(read timestamp)로서 항목 X 를 성공적으로 읽은 트랜잭션들의 타임스탬프 중 가장 큰 값. 즉, read_TS(X) = TS(T)이고 여기서 T 는 X 를 성공적으로 읽은 가장 최근의(youngest) 트랜잭션.
2) write_TS(X): 항목 X 의 쓰기 타임스탬프(write timestamp)로서 항목 X 를 성공적으로 기록한 트랜잭션들의 타임스탬프 중 가장 큰 값. 즉, write_TS(X) = TS(T)이고 여기서 T 는 X 를 성공적으로 기록한 가장 최근의 트랜잭션.

[기본적 타임스탬프 순서(Basic Timestamp Ordering)]
- 트랜잭션 T 가 write_item(X) 연산을 수행하려고 할경우:
1) read_TS(X) > TS(T) 또는 write_TS(X) > TS(T)이면 T 를 철회하고 복귀시키고 그 연산을 거부(reject)한다. => 해당 트랜잭션 순서가 이미 지남
2) a 의 조건이 발생하지 않으면 T 는 write_item(X) 연산을 수행하고 write_TS(X)를 TS(T)로 설정한다.
- 트랜잭션 T 가 read_item(X) 연산을 수행하려고 할 경우:
1) write_TS(X) > TS(T)이면 T 를 철회하고 복귀시키고 그 연산을 거부한다. => 해당 트랜잭션 순서가 이미 지나서 다른 값이 있을수도 있음.
2) write_TS(X) ≤ TS(T)이면 T 의 read_item(X) 연산을 수행하고 read_TS(X)를 TS(T)와 현재의 read_TS(X) 중 큰 값으로 설정한다. => read_TS(X)는 가장 큰값.
※ Cascade rollback이 발생할 수 있음. ==> Strict timestamp(해당 순번TS(T)까지 Read_TS, Write_TS가 올때까지 대기하는 방식)

[정의] 트랜잭션 수행중 어떠한 검증도 수행하지 않고, 트랜잭션 종료시 검증을 수행하여 데이터베이스에 반영하는 기법

[기법] 사용자들이 같은 데이터를 동시에 수정하지 않을 것이라고 가정하는 낙관적 동시성 제어 기법에 기반

[처리단계]  판독 → 확인 → 실행(기록/철회)
- 판독(Read phase, R) : 트랜잭션의 모든 갱신은 사본에 대해서만 수행, 실제 DB 수행하지 않음
- 확인(Validation phase, V) : 판독단계에서 사본에 반영된 트랜잭션의 실행결과를 DB반영전 직렬 가능성의 위반여부를 확인
- 기록(Write phase, W) : 확인 통과시 실행결과를 DB에 반영, 실패시 결과 취소후 트랙잭션 복귀

[확인 단계의 확인 검사 조건]
- 타임스탬프 :
  1) Start(Ti) : 판독 시작시간
  2) Validation(Ti) : 판독 끝나고 확인 시작한 시간
  3) Finish(Ti) : 최종 기록 단계를 완료한 시간
- 판독 및 기록 집합 :  확인 작업 위해 트랜잭션의 판독집합 (read set) 과 기록집합(write set)을 유지.
  1) 판독집합(read set): Ti가 판독한 데이터 아이템의 집합
  2) 기록집합(write set): Ti가 기록한 데이터 아이템의 집합

[직렬성 검사 조건]
① Finish(Ti) < Start(Tj)
② Start(Tj) < Finish(Ti) <Validation(Tj) 이고 Write-Set(Ti) ∩ Read-Set(Tj) = F
③ Validation(Ti) < Validation(Tj) 이고 Write-Set(Ti) ∩ Read-Set(Tj) = F 이며 Write-Set(Ti) ∩ Write-Set(Tj) = F
- TS(Ti)<TS(Tj)의 관계에 있는 모든 트랜잭션 Ti 에 대해 위 3가지 조건 중 하나만 만족하면 트랜잭션들 간에 간섭이 없는 것으로 보고 확인을 성공
- 하나라도 만족하지 못하면 트랜잭션 간의 간섭이 일어났을 가능성이 있기 때문에 실패