베이즈 정리(베이지언 확률) - Bayesian theorem

사건 A1, A2, A3, ..., An이 표본공간 Ω를 이룰 때, 사건 Ai가 서로 배반이고

※ 배반 : 한쪽이 일어날 경우 다른 한쪽이 일어나지 않는 경우를 말한다.

             (A와 B가 일어날수 있을때, 만약 A가 일어나면 B가 일어나지 않는 것)

B를 임의의 사건 사건이라 하면,

이다.  이때 An ∩ B는 서로 배반이다. 따라서 다음이 성립한다.

확률의 곱셈정리에 의하여 [식 2]는 다음과 같이 표현이 가능하다.

또한, 임의의 사건 Ai에 대한 사건 B의 조건부 확률 P(B|Ai)의 정의로 부터

를 얻을 수 있다.

[식3]과 [식4]를 이용해서 베이즈 정리(Bayes theorem)를 만들 수 있다.

예) 다음 그림과 같이 4개의 상자에 각각 빨간 공과 파란 공이 들어있다. 다음과 같은 방식으로 상자들 중에서

하나를 선택하여 임의로 공을 꺼낼 때, 꺼낸 공이 빨간 공일 확률을 구하라.

(a) 각각의 상자를 선택할 기회가 모두 동등한 경우

     각각의 상자를 선택할 확률은 모두 동등하므로 1/4이다. 이때 빨간 공을 꺼낸 사건을 E, 각각의 상자를 선택할

     사건을 A, B, C, D라 하면, 전확률 공식에 의하여 빨간공을 꺼낼 확률은 다음과 같다.

(b) 동전을 세 번 던져서 앞면이 3번 나오면 상자 A, 앞면이 2번 나오면 상자 B, 앞면이 1번 나오면 상자 C를 선택,

     앞면이 나오지 않으면 상자 D를 선택할 경우 

그녀(her)란 영화를 보면 OS1이라는 운영체제가 나온다. 주인공 테오도르가 OS1을 처음 설치한 이후에, OS1은 

100분의 2초만에 '아기 이름 짓는 법'이라는 책에 나오는 18만개의 이름 중 하나를 선택해 자신의 이름으로 삼는다.

이 영화에서는 운영체제는 "또 하나의 의식" 이라고 소개한다.

                      [그림 1] 그녀(her) 영화속의 한 장면

데이터를 어떻게 분류할 것인가를 놓고 많은 기계학습 알고리즘이 등장했다. '의사결정나무' 혹은 베이지언 확률로 

접근하는 '베이지언망', '서포트벡터머신(SVM)', '신경망'이 대표적이다.

신경망이란 기존의 뇌 구조를 컴퓨터로 모방하려는 발상으로, 신경들을 모아 신경망 모델로 확장시키는 개념이다.

초기 신경망은 선형 분류기에 불과하다는 한계로 신경망 연구는 한동안 빛을 보지 못했다. 하지만 최근 퍼셉트론의 

원리를 계승하고, 다층 퍼셉트론이 등장하며 신경망 연구는 새롭게 부활하기 시작했다. 

가장 간단한 퍼셉트론 모델부터 살펴보자.

퍼셉트론

퍼셉트톤(perceptron)의 구조는 [그림 2]와 같다. 여러개의 입력층을 모아 하나의 출력을 낸다.

                          [그림 2] 퍼셉트론 구조 (1)

하나의 출력은 이진 형태의 출력이다. 1과 -1을 출력하는데 [그림 3]의 c형태와 같다.

각 에지는 가중치를 가지며, 여러개의 입력을 받아 [그림3]의 b형식으로 각각의 에지의 가중치와

입력값을 계산해 활성함수에서 1과 -1을 출력한다.

                     [그림 3] 퍼셉트론 구조 (2)

활성함수 τ는 activation function으로 불리며 [그림 3] c와 같은 계단 함수(step function)를 사용한다.

동작 과정의 예는 다음과 같다.

2차원 공간 상에 [그림 4] a와 같은 네 개의 샘플 x1, x2, x3, x4가 존재한다고 할때,

x1는 w2에 속함을 볼 수 있다.([그림 4]c)

샘플과 부류 값으로 표시하면 x1 = (0,0), t1=-1, x2=(1,0), t2=1, x3=(0,1), t3=1, x4=(1,1), t4=1 이다.

이때 ti는 xi가 속하는 부류 정보이다.(w1에 속하면 1이고, w2에 속하면 -1)

                                 [그림 4] 퍼셉트론 동작 예제

OR게이트 동작의 분류 문제로 간주할때, 이 퍼셉트론은 w=(1,1), b=0.5(가중치)를 가진다.

위와 같은 방식으로 x3은 1을 출력함을 볼 수 있다.

퍼셉트론 식을 정리하면 다음과 같다.

이 퍼셉트론 모델은 선형 분류기(linear classifier)에 해당한다. 특징 공간을 둘로 나누는 것이다.

이 경계는 2차원에서는 직선, 3차원에서는 평면, 4차원에서는 초평면(hyperplane)이라고 부른다.

하지만 여기서 문제가 발생한다.

                 [그림 5] 선형분리 가능 모델과 불가능 모델

[그림 5]를 보면 a의 경우 파란선으로 선형분리가 가능하다. 하지만 b를 보면 선형 분리가 불가능함을

볼 수 있다. 이러한 한계로 한동안 빛을 보지 못한 퍼셉트론 모델은 퍼셉트론을 확장한 다층 퍼셉트론이란

아이디어가 나온 이후로 신경망 연구를 살릴 수 있었다. 

다음 포스트에서 다층 퍼셉트론 모델을 살펴본다.

참조 : 네이버케스트(딥러닝 - http://navercast.naver.com/contents.nhn?rid=122&contents_id=64183) 

         컴퓨터비전(오일석)

사람의 능력 중 가장 뛰어난 능력은 학습 이라고 한다. 학습은 무엇일까?

처음 접하는 일은 처음에는 미숙하지만 시간이 지나고 보면 쉬운일이 된 경험이 많을 것이다.

또한 자전거를 처음 탈때 많이 넘어지고 다치며 자전거 균형 잡기 기술을 배우고 나면 

왠만해선 잘 넘어지지 않는다.

공학자에게는 항상 꿈이 있다. 이런 사람의 학습 기술을 기계에게 가르쳐 기계 스스로 학습하며 배워나갈수 

있는 환경을 구축하는 것이다. 

이런 꿈을 갖고 사람의 학습 방법과 기계의 학습 방법에 대해 살펴보자.

지도 학습과 비지도 학습

                           [그림 1] 사람의 학습과 기계의 학습

[그림 1]은 사람의 학습과 기계의 학습 방법을 설명하고 있다. 사람은 외부 환경으로부터 가르침을 받아

그것을 기억하고 다음 동일한 환경에 기억된 행동을 수행한다. 자전거를 탈때 균형 잡는 방법을 기억해 두었다가

추후 자전거를 탈때 균형을 잘 잡고 탄 경험이 있을 것이다.  

기계의 경우 특정 테스트 집합이 입력으로 들어 왔을때 이미 검증된 집합과 테스트 집합의 목록 중 테스트 모델이 

어디에 적합한지 확인하고 분류해 가며 학습함을 볼수 있다.

이렇게 기계 학습은 사람의 학습과 개념적으로는 비슷하지만, 학습 방법의 차이가 존재함을 볼 수 있다.

[그림 2]의 a를 보면 기계가 처음 학습 분류기를 생성하는 과정을 나타낸다. 학습 집합으로부터 특징을

추출한 뒤, 추출한 특징공간을 적절 나눈다. 나눈 특징들을 토대로 경계를 나눈 분류기를 만는다.

추후 테스트 영상이 들어왔때 학습 단계에서 사용한 방법과 동일하게 특징을 추출한 다음 분류기를 만들어

분류하는 과정을 거친다.

                                                             [그림 2] 기계 학습

이와 같은 방법은 지도 학습(supervised learning) 이다. 즉 학습 집합에 있느 샘플은 (x, t)라는 정보를 갖는다.

x는 특징 벡터이고, t는 그것이 속하는 부류다. 하지만 때에 따라선 x만 있고, t의 정보가 없을때도 있다. 분류 정보가

없기 때문에 분류 작업을 수행할 수 없다. 이런 방법을 비지도 학습(unsupervised learning)이라고 부른다. 군집에서

유용한 정보 추출을 한다.(데이터 마이닝, 빅데이터, 정보 검색 등의 많은 응용)

두 가지 학습 방식의 중간에 속하는 경우를 준지도 학습(semi-supervised learning)이라고 한다. 

분류기 성능 평가

기계 학습은 학습 집합을 가지고 수행한다. 학습이 완료되면 테스트 집합으로 성능을 평가 한다.

그런데 데이터 수집에 상당한 비용이 들기 때문에 데이터 양이 충분하지 않은 경우 잘 분류되지 않거나, 잘못된

결과가 나오기도 한다. 이런 상황에서 유용하게 사용할 수 있는 방법을 몇가지 소개한다.

첫번째 방법은 재 샘플링(resampling)이다. 재 샘플링의 기본 아이디어는 같은 샘플을 이용해 여러번 학습 시키는 

것이다. 학습 데이터 량이 충분하지 않을때 유용하다. 

두번째 방법은 교차샘플이다. 교차 샘플은 분류기를 k-1개의 부분 집합으로 학습시키고 나머지 한 개의 부분 집합으로

분류기의 성능을 측정한다.

이 과정을 서로 다른 부분 집합으로 k번 수행하여 얻은 성능의 평균값을 분류기의 성능으로 취한다.

이러한 방법을 k-겹 교차검증(f-fold cross validation)이라고 한다. 

세 번째 방법은 부스트랩(bootstrap)이다. 이 방법은 샘플의 중복 사용을 허용한다. 

N개의 샘플을 가진 집합 X에서 pN개의 샘플을 임의로 뽑는다. 이때 한거번에 하나씩 샘플을 뽑는데 뽑은 것을

다시 집합 X에 넣는다. 따라서 운이 좋은 경우 집합 X에서 여러번 뽑인 샘플도 있고, 한번도 뽑히지 않은 샘플이

존재할 수 있다. 이렇게 얻은 샘플 집합으로 성능을 측정한다. 

이 과정을 독립적으로 T번 수행하고, 그 결과를 평균한 값을 최종 성능으로 취한다.

데이터 모델

1. 구조 : 데이터 정적 성질
2. 연산 : 데이타 동적성질
3. 제약조건 : 데이터의 논리제약
 
개체 : 다른것과 구별되는 객체

개체 타입 : 이름과 속성들로 정의

개체 집합 : 개체 인스턴스 들의 집합(개체 모임)

단순 속성 : 더이상 작은 요소들로 분할할수 없는 속성

복합 속성 : 몇개의 단순속성으로 분해할수 있는 속성

단일값 속성 : 특정 개체에 대해 하나의 값만 지님 예)이름

다중값 속성 : 한 개체에 대해 여러값을 가질수 있음 예)취미

유도 속성 : 다른 속성이나 개체가 가지고있는 값으로 부터 유도되어 결정될 경우

저장 속성 : 유도속성을 생성하는데 사용된 속성

널 속성 : 널 값을 갖는 속성

관계 타입 : 개체 집합들 사이의 대응, 즉 매핑을 의미

[학생] - <등록> - [과목]

전체 참여 : A-B관계에서 개체집합 A와 모든 개체가 A-B관계에 참여 
예) 교수 - 학과 관계

부분 참여 : A-B관계에서 개체집합 A의 일부 개체만 A-B관계에 참여
예) 학생 - 과목 관계

존재 종속 : 어떤 개체 B의 존재가 A의 존재에 종속될때, B는 A에 존재종속
  A : 주개체, B : 종속개체(주개체가 존재함으로 인해 존재)

약한 개체타입 : 자신의 속성만으로는 키를 명세할수 없는 개체 타입
강한 개체타입 : 자신의 속성으로 구성된 키를 가진 개체 타입

*논리적 데이타 모델

<릴레이션 스키마 모델> : 개체와 관계성을 모두 테이블로 정의
<네트워크 데이타 모델> : 스키마 다이어그램
<계층 데이타 모델> : 사이클이 없음(네트워크 데이타 모델과 차이)

1. 삭제 이상 : 투플을 삭제함으로써 유지되어야할 정보까지도 삭제되는 연쇄삭제 현상이 일어나 정보손실이 발생하는것

2. 삽입 이상 : 어떤 데이타를 삽입해야 할때 불필요한 데이터를 삽입해야 하는것

3. 갱신 이상 : 중복된 투플 중에서 속성 값 만을 갱신시킴으로써 정보의 모순성이 생기는 현상

속성들 간의 종속성을 분석해서 하나의 릴레이션에 기본적으로 하나의 종속성이 되도록 분해하는 과정을 정규화라고 함

1. 정보 표현의 무손실 : 하나의 스키마에서 다른 스키마로 변환시킬때 정보 손실이 있어선 안됨

2. 최소 데이타의 중복성 : 중복으로 인한 여러가지 이상을 제거할수 있기 때문

3. 분리의 원칙 : 하나의 독립된 관계성은 별도의 릴레이션으로 분리시켜 표현

함수 종속 : 속성 X값에 대해 시간에 관계없이 항상 속성 Y의 값이 오직 하나만 연관되어 있을때, Y는 X에 함수 종속이라 함

    X(결정자) -> Y(종속자)

임의 접근 시간
- 헤드가 임의의 장소에서 원하는 트랙에 있는 레코드를 찾아 메인 메모리의 버퍼로 데이터를  전송하는데 걸리는 시간
- 접근시간 = 탐구시간(트랙 찾는시간) + 회전지연시간 + 데이터전송시간

데이타베이스 시스템에서 가장 중요한 성능 개선 초점은 디스크 접근 횟수를 최소화 하는것
- 디스크 배치, 저장하는 방법이 중요한 문제

<디스크 관리자>
- 운영체제의 한 구성요소로 모든 물리적 입출력 연산에 대한 책임을 지고 있음
- 디스크 관리자는 물리적 디스크 주소를 알고있어야함

<화일관리자>
- 디스크 관리자를 이용해서 DBMS가 디스크에 저장된 저장된 데이터베이스를 취급할수 있도록 지원함

<저장화일>
- 저장화일은 화일이름 또는 화일ID로 식별되기 때문에 페이지 세트내에서 유일해야 함

<저장레코드>
- 레코드 번호 또는 레코드 ID로 식별되는데, 저장화일 내에서는 유일,  보통화일뿐 아니라 전체디스크 내에서 유일함.
- 레코드ID <페이지번호, 슬롯번호> 로 구성

시스템이 얼마동안 삽입 삭제 연산을 계속 실행하고 나면 처음에 논리적 순서에 따라 물리적으로 인접했던 페이지들이 

더 이상 물리적으로 인접하지 않음. 따라서 포인터를 이용해 각 페이지 헤드에 다음 페이지 물리적 디스크 주소를 저장함

(헤드에 모든 제어정보 저장)

디스크는 보통 지정된 페이지(트랙0)에 정보(빈페이지, 자유공간, 데이터..)를 저장함

이 페이지를 디스크 디렉터리 또는 페이지 세트 디렉터리 라고 함

디스크관리자는 화일관리자로 하여금 물리적 디스크 입출력에 대한 세부적인 사항을 알 필요 없이 논리적 페이지로만 

동작할 수 있게 지원함

화일관리자는 DBMS로 하여금 페이지 입출력에 대한 세부적인 사항에 대해 알 필요 없이 저장 화일과 저장 레코드 만으로 

동작  이런 기능을 저장레코드관리 라고함

저장레코드는 내부적으로 레코드ID RID를 통해 식별됨. 이 방법은 레코드가 한 페이지 안에서 이동이 일어날때 RID를 변경시킬 

필요없이 페이지의 해당 슬롯내용만 변경해 주면 되는 이점을 가지고 있음

RID : <페이지번호, 슬롯번호>

<순차 방법>
레코드들의 물리적 순서가 레코드들의 논리적 순서와 같게 순차적으로 저장

<인덱스 방법>
레코드에 접근하기 위해 인덱스를 찾아, 그 인덱스가 가리키는 주소를 따라가 원하는 레코드를 접근할 수 있도록 데이타를 저장하는 방법

 - 다중 리스트 화일 : 하나의 인덱스 값마다 하나의 데이타 레코드 리스트를 구축

B+-, B-트리다른점

- B+트리는 키값을 찾아가는 경로만 제공

- 순차 세트의 모든 노드가 순차적인 연결리스트로 되어있음. 따라서 키값을 효율적으로 접근할수 있음  (순차접근이 빠름)

<무결성>
- 데이타 베이스의 무결성이란 데이터의 정밀성, 정확성을 의미
- 사용자가 데이터를 사용할때 무결성(깨끗)을 헤지치 않아야함

<무결성 서브 시스템>
- 데이타베이스 시스템은 무결성을 유지하기 위해 DBMS구성요소 가지고있음
- 무결성 규정을 관리 유지 하고 트랜잭션이 수행하는 갱신 연산이 무결성 규정에 위반
  되지 않는지를 검사

뮤결성 규정은 규정 이름, 검사 시기, 제약 조건, 위반 조치 등을 포함

<무결성 규정 요건>
1. 고급 언어 사용
2. 카탈로그 또는 사전에 저장(질의 할수 있음)
3. 시스템에 의해 바로 실행

<무결성 규정의 종류>
1. 상태 제약 - 일관성있는 상태 조건 명세
2. 과도 제약 - 다른상태로 변환되는 과정 조건 명세
3. 집합 제약 - 투플 집합 전체에 관한 규정
4. 투플 제약 - 처리되고 있는 투플에 적용 규정
5. 즉시 제약 - 디스크에 변경이 일어날때마다 매번 저장
6. 지연 제약 - 디스크에서 가져온 값이 모두 변경되면 디스크에 저장(로그를 둠)

<트리거>
- 무결성을 유지하는 프로그램

데이터베이스 보안 
- 불법적인 폭로, 변경, 파괴로부터 데이터 보호

<직접 접근 제어>
- 가장 쉬운 방법은 암호 사용
- 일반적인 방법은 권한 테이블 사용(사용자, 허가 데이타, 허용 연산, 허가 조건 포함)

<간접 접근 제어>
- 임의 접근 제어 방식
- 암호화 기법은 데이타를 뒤섞은뒤 다른 사람이 그대로 사용할수 없도록 하는것

<권한 부여 테이블>

- 시스템은 모든 사용자에 대한 권한 테이블을 하나의 테이블로 종합해서 관리

<보안 집행기>

- 데이터베이스를 마음대로 접근할수 있기 때문에 접근 요청이 오면 권한 테이블을 검사해 접근을 

   허가할 것인지 거부할 것인지 결정

<뷰 기법>

- 테이블에 직접 접근하지 못하고 view를 통해 접근

- 보안에 민감한 데이터를 권한이 없는 사용자로부터 은닉시킬수 있음, 불법적인 접근 예방 가능

- 단점 : 갱신, 삽입, 삭제 연산에 제약

<테이블 생성자>

- 테이블에 대한 모든 권한 가짐

- 권한 일부를 다른 사용자에게 부여 가능

- 테이블 제거 권한은 부여 불가

<GRANT/REVOKE 기법>

- SQL에서 권한부여는 GRANT명령문에 의해 명세됨

DBA가 사용자 U1에게 STUDENT 릴레이션에 대한 삽입과 삭제 권한을 부여

DBA가 사용자 U2에게 STUDENT 릴레이션 검색 기능 부여,

GRANT OPTION은 다른 사용자에게 권한 부여할수 있음

U2가 사용자 U3에게 STUDENT 릴레이션 검색 기능 부여

U2에게 검색 기능을 회수 시킴, CASCADE는 U2가 U3에게 부여한 권한까지 취소 시킴

만약 GRANT OPTION FOR가 사용되면 접근 권한을 취소하는 것이 아니라 다른 사용자에게 권한을 

부여할수 있게 한 권한 자체를 취소함

<데이터 암호화>

허가 받지 않은 사람이 데이터나 메세지의 내용을 알수 없도록 은폐 시키기 위해 데이타를 암호로 바꾸는것

트랜잭션 : 하나의 논리적 기능을 수행하기 위한 작업 단위

1. 원자성 : 연산 결과를 반영할때 모두 반영하거나, 모두 반영하지 않아야 함

2. 일관성 : 실행후에도 일관성유지(데이터가 모순되면안됨)

3. 격리성 : 트랜잭션이 수행중에 다른 트랜잭션이 접근할수 없음

4. 영속성 : 연산이 성공적으로 수행되면 결과값을 반영해야함

commit(완료) : 트랜잭션이 성공적으로 실행됬음을 의미

Rollback(복원) : 트랜잭션이 실패하였음을 의미, 데이터 베이스를 복원해야 한다, 그렇지 않으면 데이터베이스가 모순됨

소멸성 저장장치 : 메인 메모리와 같이 시스템이 붕괴되면 정보도 손실
비소멸성 저장장치 : 디스크나, 테이프와 같이 시스템이 붕괴되도 정보가 유지
안전성 저장장치 : 정보 손실이 발생하지 않게 여러개의 비소멸성 저장장치로 구성(동일 데이터를 여러 군대 저장)

회복 : 데이터베이스를 장애 발생 전의 일관된 상태로 복원하는것

일관된 상태 : 오류가 없는 상태를 말함(데이터베이스 모순이 없는 상태)

장애 : 정해진 명세대로 시스템이 작동하지 않는것

1. 트랜잭션 장애 - 트랜잭션 내의 논리적 오류나 내부문제(데이터베이스 불량, 불명..)
2. 시스템 장애 - 교착현상, 하드웨어 오동작, 메인메모리 정보 손실
3. 미디어 장애 - 디스크 헤더 붕괴나 고장으로 인해 데이터베이스 일부 혹은 전부가 손상

데이타 중복
덤프 - 주기적으로 다른 저장장치에 복제
로그 - 일지라고도 하며 데이타베이스가 변경될때마다 데이타 옛값과 새로운 값을 별도 화일에 저장

Redo : 가장 최근 복제본으로 복원시킨뒤 로그를 재실행 함으로써 데이터를 복원
Undo : 로그를 이용하여 모든 변경을 취소하여 원래의 데이터베이스로 복원

<T1, start> : T1 트랜잭션 실행 시작
<T1, X1, v1, v2> : 트랜잭션 T1이 데이타아이템 X1값을 v1에서 v2로 변경함
<T1, Commit> : T1트랜잭션 실행 완료

즉시 갱신
-트랜잭션이 연산을 실행하고 있는 상태에서 데이터변경결과를 그대로 반영(연산시 바로바로 반영)
-시스템 붕괴나 트랜잭션 장애가 일어나면 트랜잭션이 실행되기 이전 상태의 데이터 값으로 복원시키는 Undo작업 수행할때
 레코드의 옛값이 사용됨 
 <트랜잭션id, 데이타아이템, 변경 전 값, 변경 된값>

지연 갱신
-트랜잭션이 부분 완료 될때까지 데이터베이스 변경을 로그에 기록해 두었다가 한꺼번에 실행
-Undo연산이 필요가 없음(즉시갱신과차이)

<트랜잭션id, 데이타아이템, 변경 된값>

미디어 회복 

- 데이터 베이스 내용 전체를 주기적으로 또다른 안전한 저장장치에 덤프 시키는 것

- 디스크가 붕괴되어도 최근 덤프를 이용해 이전 상태로 복귀

검사 지점(checkpoint) : 실행하고 있는 일을 모두 멈추고 디스크에 모두 반영시켜 놓음(실시간 백업과 비슷)

병행수행 : 몇개의 트랜잭션들을 동시에 수행시키는 것, 시작과 종료가 서로 중복되는 것을 말함

1. 갱신분실 : 같은 레코드에 동시 접근
2. 모순성 : 덧셈과 곱셈 순서에 따라 결과가 달라짐
3. 연쇄 복귀 : T1에서 오류가 나 복구 하려할때, T2에서 T1를 가져다 썻으므로 T1도 복귀해야함

일반적으로 n개의 트랜잭션의 직렬 스케줄 방법은 n!개

직렬 스케줄 : 스케줄에 포함된 트랜잭션의 연산들을 각 소속 트랜잭션 별로 모두 연속적으로 실행하는 스케줄
비직렬 스케줄 : 트랜잭션을 병행 실행시키는 스케줄

만일 n개의 트랜잭션에 대한 비직렬 스케줄 S가 똑같은 n개의 트랜잭션에 대해 직렬 스케줄 S'과 항상 동일한 결과를 생성하면

이 스케줄 S를 직렬 가능 스케줄이라고 한다.

로킹(Locking)방법

- 아이템에 접근할때 Lock연산실행, 이미 Lock이 걸렸다면 기다림

- 사용이 끝나면 unLock실행
- 트랜잭션이 어느 한 데이타 아이템의 마지막 접근이 끝나자 마자 unlock을 하는 것은 바람직하지 않다.

   왜냐하면 병행수행에 의한 무결성(직렬 가능성)이 보장되지 않기 때문에 

   -> 다음 처리할 데이타아이템을 다른곳에서 Lock했을 경우

2단계 로킹
- 사용할때 lock하고 사용이 끝나면 unlock함
- 2단계 로킹 은 직렬 가능성을 보장하는 반변에 교착상태[더이상 어느것도 실행하지 못하는 상태(서로기다림, 사이클 형성)]
  문제를 내포하고 있음.

- 스케줄 내의 모든 트랜잭션 들이 2단계 로킹 규약을 준수한다면, 그 스케줄은 직렬 가능

- 교착상태 예방 lock를 요청하는 과정에 어떤 제약을 가함, 트랜잭션을 실행시키기 전에 필요한 lock를 한꺼번에 모두 요청
  부여받지 못하면 실행시키지 않음

- 교착상태 탐지 교착상태가 탐지되면 한 트랜잭션을 취소시켜 다시 스케줄을 짜는 방법

정규화 순서도

* 4, 5 정규형은 생략

제 1 정규형(First Normal Form)

▶ 반복그룹(repeating group)이란?

- 복합 애트리뷰트(composite attribute)

- 다치 애트리뷰트(multivalue attribute)

- 중첩 릴레이션(nested relation)

▶ Example 분석

<고객테이블 - 2>에 대한 갱신이상 분석

◑ 수정이상(Modification Anomaly)

- 고객명이 취미의 수만큼 중복되어 저장 -> 취미의 수가 많을 경우 수정이상이 발생할

가능성 높다

◑ 삭제이상(Deletion Anomaly)

- 등산을 취미로 갖는 고객이 홍길동 1명인 경우, 홍길동 고객정보를 삭제하면 등산의

취미정보도 삭제되고, 등산정보를 삭제하는 경우 홍길동 고객정보도 같이 삭제된다.

◑ 삽입이상(Insertion Anomaly)

- 고객번호가 주키이므로 테니스라는 취미정보를 추가하는 경우, 테니스를 취미로 갖는

고객이 아직 없으므로 삽입이 불가능하다(주키는 null값을 못가지므로).

<고객테이블 - 2>에 대한 갱신이상 발생 원인

고객번호와 고객명은 (고객번호) -> (고객명) 으로 함수적 종속관계를 갖으나

고객번호와 취미는 함수적 종속관계가 아니다.

★ 보충 - L자형 테이블 ★

테이블의 데이터를 null값을 가지고 있는 데이터를 위쪽으로 정리했을 때 위쪽의 컬럼들이 null값을 가지는 관계로 빈 공간이 되어 전체적 모양이 L자 형태로 나타나는 테이블

위에서 보는 바와 같이, 반복그룹을 column을 추가하여 제거하는 <고객테이블 - B>경우, L자형 테이블이 나타난다. <고객테이블 - A>의 경우는 앞서 설명한 바와 같이 불필요한 데이터의 중복이 나타나고 있다.

L자형 테이블은 일반적으로 가장 많이 나타나는 테이블구조로서, 모든 정보를 한꺼번에 한 테이블에 넣도록 설계하는 경우에 자주 나타난다. 규모가 작은 웹사이트에서 회원정보를 적절히 분리하지 않고 한 테이블에 모조리 다 넣는 경우가 그 대표적 예이다.

A, B 두 테이블 모두 비효율적인 테이블구조이며 앞서 본 바와 같이 두 개의 테이블로 분해하는 것이 바람직하다.

제 3 정규형(Third Normal Form)

▶ Example 분석

<학생>테이블이 제 2 정규형을 만족하고 있다 <- 키가 아닌 (학과명), (학과전화번호)

애트리뷰트가 키인 (학번)에 완전하게 함수적으로 종속하고 있다.

step 2. 이행적 함수적 종속성 여부

◑ (학번) -> (학과명), (학번) -> (학과전화번호)

◑ (학과명) -> (학과전화번호) <- (학과전화번호)가 (학번)에 이행적으로 함수적

종속을 하고 있다.

step 3. <학생>테이블에 대한 갱신이상 분석

◑ 수정이상(Modification Anomaly)

- 학과에 속한 학생 수만큼 학과명과 학과전화번호의 정보가 중복하여 나타남

-> 수정이상 발생 가능성

◑ 삭제이상(Deletion Anomaly)

- 학생이 한 명인 학과의 경우, 학생정보 삭제 시 학과정보도 완전 삭제됨

◑ 삽입이상(Insertion Anomaly)

- 학번이 기본키 구성요소이므로 학생이 한 명도 없는 학과정보 삽입 불가능

step 4. <학생>테이블에 대한 갱신이상 발생 원인

- 기본키에 대한 이행적 함수적 종속성이 <학생>테이블에 존재함

step 5. <학생>테이블에 대한 갱신이상 해결책

▶이행적 함수적 종속성을 제거하기 위하여 두 릴레이션으로 분리(제 3 정규형)

▶ 제 3 정규형(Third Normal Form)에 대한 결론

- 이행적 함수적 종속성 제거하기 위하여 두 릴레이션으로 분리

- 보이스(R.F. Boyce)와 코드(E.F. Codd)가 개발한 정규형.

- 제3정규형(3NF)을 확장한 것으로 이 정규형에 가까워질수록 데이터의 중복성이 배제되어

갱신 시에 부정합 또는 불일치가 잘 생기지 않는다.

step 1. 기본조건 분석

- <수강>테이블에 나타난 함수적 종속성

(학번, 과목) → (강사)

(강사) → (과목)

- 제 3 정규형을 만족하고 있다 <- (강사)는 (학번)이나 (과목)에 함수적으로 종속하지

않으며, 따라서 (강사)는 기본키인 (학번, 과목)에 완전하게 함수적으로 종속하고 있다.

- <수강>테이블의 후보키는 (학번, 과목), (학번, 강사)

step 2. 모든 결정자의 후보키 여부

- (학번, 과목)은 결정자이면서 후보키이다.(<- 기본키이므로 당연히 후보키)

- (강사)는 결정자이면서 후보키가 아니다.

- 따라서, <수강>테이블은 제 3 정규형이면서, BCNF는 아니다.

step 3. <수강>테이블에 대한 갱신이상 분석

◑ 수정이상(Modification Anomaly)

- 예를 들어, ‘노련한’ 강사의 ‘데이터베이스’강좌를 수강하는 학생이 많은 경우,

수강학생 수만큼 강사명의 정보가 중복하여 나타남 -> 수정이상 발생 가능성

◑ 삭제이상(Deletion Anomaly)

- 학생이 한 명인 강좌의 경우, 학생정보 삭제 시 강사정보도 완전 삭제됨

◑ 삽입이상(Insertion Anomaly)

- 학번이 기본키 구성요소이므로 미개설강좌에 대한 강사정보 삽입 불가능

step 4. <학생>테이블에 대한 갱신이상 발생 원인

- 후보키가 아닌 애트리뷰트가 다른 애트리뷰트의 결정자이기 때문

- 후보키가 여러 개인 경우 발생하는 현상으로, 만약 하나의 후보키만을 가진 릴레이션이

제3정규형을 만족하면 동시에 BCNF도 만족함

step 5. <학생>테이블에 대한 갱신이상 해결책

▶ 키가 아니면서 결정자 역할을 하는 애트리뷰트와 그 결정자에 함수적으로 종속하는 애트

리뷰트로 하나의 테이블을 구성. 이 테이블에서 결정자는 기본키가 됨

▶ 기존 릴레이션에 결정자를 남겨서 기본키의 구성요소가 되도록 함. 또한 이 결정자는

새로운 릴레이션에 대한 외래키 역할도 함

- 모든 결정자가 후보키가 되도록 한다 

[출처] 13. 정규화(Normalization)4 - 제 3 정규형

데이타베이스론_이석호_(1).hwp