일] character set, character encoding, code page, unicode

1 character set


  - 직역하면 문자 집합
  - 컴퓨터에서 문자를 표현하기 위해 각 문자를 정수 값에 대응 시켜 놓은 체계
    숫자 코드가 컴퓨터상에서 어떻게 표현되는 가는 정해지지 않은상태


  - 예를 들어 '가' 라는 문자를 '0xac00' 이라는 숫자값으로 매핑기켜 사용하도록 정의한것을 의미
  - character set 은 언어 종류만큼 다양함,  character set 에 따라 표현하고자 하는 문자의 값과 대응하는 
     숫자도 달라짐.  따라서 문자를 주고 받을때 서로간의 character set 을 일치 시켜야 함
  
  - 웹페이지 작성시 content-type 의 일부로 character set 을 명시하는 것은 웹브라우저 에게 사용하는 
     character set 을 알려주어 오해가 없도록 하기 위함


2. Enconding
  -  character set 이 문자에 대해 정수값을 지정한 것이라면, enconding 은 문자를 표현하는 정수값을
     어떤 bit 배열로 표현할 것인지를 의미해야 함.
     즉 encoding 은 character set 에서 더 나아가 컴퓨터 상에서 어떻게 표현되는 가까지 정해진 상태의 문자 집합
 - 완성형 한글인 KSC-5601 character set 은 UNIX 에서는 EUC-KR 이란 encoding 으로 표현되고 있으며
    윈도우즈에서는 cp949란 encoding 으로 표현됩니다.


 - character set 이 같다면 그 charset 을 지원하는 어떤 encoding 을 사용하든지 각문자에 대응하는
    논리적읜 정수값은 동일 하다고 볼수 있으나 encoding 이 다를수 있으니 encoding 도 맞춰라




* encoding = bit


3. EUC & codePage


  - EUC = Extended Unix Code 
  - Unix 가 세계화 되며 각국 언어 표기의 character set 을 개발함
  - codepage는 microsoft windows 가 각나라 문자 표기를 위해 개발된 character set ( cp949)


 4 Unicode
  - 모든글자 표현 체게를 하나로 통합하려고 개발된 character set
  - 

[전자계산기] 용어정리

saving
 - 주기억 장치에 있는 내용을 보조기억장치에 옮기는 기능

storing
 - cpu 에 있는 레지스터 내용을 주기억장치로 옮기는 기능

staging
 - 자기테이프나 디스크에 있는 블록들을 주기억장치에 미리 옮겨놓는 기능

spooling
 - 처리할 데이터를 디스크나 테이프에 잠시 저장시켰다가 나중에 다른 장치가 이용하는 기능


interrupt
 - 컴퓨터에 이상이 발생했을때 업무가 계속 처리할수 있도록 하는 기능

데이지 체인
 - 컴퓨터에 예기치 않는 문제가 발생 했을때 우선 순위가 높은것 부터 처리하기 위해 만들어 놓은 회로

명령어 사이클
 - 마이크로 작동 수행을 위한 제어신호를 가하는 것

 1) fetch cycle
 - 주기억 장치로 부터 명령을 읽어 cpu 로 가져 오는 주기

 2) indirect cycle
 - operand 가 간접 주소일 때 operand 가 지정하는 곳으로 유효주소를 읽기 위해 기억장치에 접근 하는 주기

 3) interrupt cycle
 - 현재 수행중인 명령이 중단되는 상태
 사이클을 제어하기 위한 플립플롭 FR 이 11일 때 컴퓨터 인터럽트 사이클이 된다
 이때 메모리의 번지는 return address 를 저장하는 영역으로 사용되며, 메모리의 1번지는 분기번지를 저장하기 위한 영역으로 사용된다.

execute state 가 끝나면 인터럽트를 조사해서 인터럽트가 발생했으면 인터럽트 구기 그렇지 않으면 fetch state 로 간다

간접주소  지정 방식인 경우에 대해서는 indirect state

메이저 사이클은 fetch, indirect, execute, interrupt 과정에서 필요에 따라서 간접 주소 지정 방식인 경우 indirect가 필요하고 인터럽트가 발생한 경우만 interrupt 상태가 필요하다



인터럽트의 종류 및 특징

1. 기계검사 인터럽트 (machine check interrupt)
 - 컴퓨터 하드웨어 검사 회로가 기계의 에러를 발견했을 때 발생되는 인터럽트

2. 불법 명령어 사용 인터럽트 (user bad command interrupt)
 - 정의되지 않은 명령어나 불법적인 명령어를 사용하여 발생하는 인터럽트

3. 입출렵 인터럽트 ( I/O interrupt)
 - 입출력 장치에서 컴퓨터의 CPU 에 인터럽트 신호를 보내는 것
 - 입출력의 시작이나 끝, 오류의 발생 등을 CPU 에 알리는 역할

4. 외부 인터럽트 ( External Interrupt )
 - 컴퓨터의 CPU 바깥에서 발생한 원인으로 일어나는 인터럽트

5 . 인터럽트 동작 순서

 1) 인터럽트 발생 장치로 부터 인터럽트 기능을 요청한다
 2) 현재 실행 중이던 프로그램 상태를 안전한 장소에 보관시킨다
 3) 인터럽트 처리 루틴을 실행 시킨다
 4) 인터럽트 처리 루틴에서는 해당 인터럽트에 대한 조치를 취한다
 5) 원래 프로그램이 계속 되도록 한다



Flynn 분류
 - 명령어 갯수 에 따른 데이터 처리량

 S: 싱글, M : 멀티  I : 명령어  D: 데이터

SISD
SIMD
MISD
MIMD

파괴성 판독 (DRO : Destructive Read  Out
 - 데이터를 읽어내면서 원래의 데이터를 소거하는 판독 방법,
 정보를 보존하려면 읽어낸 뒤 즉시 재기입하여야 하는 성질을 의미 한다 -> 자기 코어 메모리


MAR ( Memory Address Register) 는 주소를 기억하는 레지스터
MBR (Memory Buffer Register) 는 주기억장치에 일거나 쓰기 위한 데이터를 기억시키는 레지스터 


문자 동기 방식
- Syn 등의 동기 문자 ( 전송제어 문자)  에 의해 동기를 맞추는 방식
- BSC 프로토콜에서 사용

비트 동기 방식
- 데이터 블록의 처음과 끝에 8 비트의 플래그 비트 (01111110) 를 표시하여 동기를 맞추는 방식
- HDLC, SDLC 프로토콜에서 사용됨

즉시 주소 방식 (Immediate address Mode)
 - 주소 ( operand) 부분에 실제 데이터가 들어있는 방식
 - 명령어 수행이 즉각적으로 이루어지는 방식

직접 주소 방식 (Direct address Mode)
 - 명령어의 주소 (operand ) 부분에 실제 데이터가 들어있는 주기억 장소의 주소값이 명령어에 들어있는 경우

[전자계산기] 자료표현

1. 구성단위
  비트 : 정보의 최소단위
  니블 : 4개의 비트로 구성
  원드 : 연산 처리의 단위
  바이트 : 8개의 비트로 구성

2. 코드 종류
  BCD 코드  :  8421 코드
  ASCII 코드 :  표준코드, 128개 문자 , 숫자, 영문 표현
  GRAY 코드 : A/D 주로 사용, BCD 코드의 첫 비트는 그대로 사용 -> 옆에 있는 비트와 XOR 연산
  패리티 검사 코드 : 데이터 오류 검사
  해밍 코드 : 에러 검출 및 수정
  EXcess-3  코드 : BCD 코드


3. 표현 방식
고정소수점  /  부동 소수점  /  존형 10진수  /  보수

[전자계산기] 논리회로

조합 논리 회로

반가산기 : 하나의 and 회로과 ex-or 회로의 조합 ( S=a'b + ab , C = 뮤 )
전가산기 : 두개의 반가산기와 한개의 or 회로
병렬가산기 : 여러개의 전가산기를 병렬로 연결
디코더 : n 개의 입력 -> 2n 개를 출력
멀티 플랙서 : 단일 출력선으로 전달하는 회로 - 순서논리 회로 = " Flip - Flop " ( count, register, ram ) 구성 가능
   ex)  J-K Flip-Flop, R-S Flip - Flop

[데이터베이스] 데이터베이스란

정의

1. Integrated Data  : 통합된 데이터
2. Stored Data : 저장된 데이터
3. Operational Data : 운영 데이터
4. Shared Data : 공용 데이터


특징
1. Real-Time Accessbility  :  실시간 접근성
2. Continous Evolution  :  계속적인 변화
3. Concurrent Sharing  :  동시 공유
4. Content Reference  :  내용에 의한 참조

독립성

1. 논리적 데이터 독립성
2. 물리적 데이터 독립성

[데이터베이스] 동시성제어

- 다수의 트랜젝션을 병렬로 처리함에 있어, 갱신손실, 불이치 모순성을 방지하기 위해 트랜잭션을 직렬화 시킴

- 목적 : 다수의 트랜잭션 처리시 갱신손실, 분일치 모순성 방지

1. 갱신손실 ( Lost Update)
 - 지연된 업데이트로 트랜젝션의 업데이트 내용이 반영되지 않음

2. 불일치 모순성 ( Inconsistency )
 - 연산중 중첩 업데이트로 인해 트랜젝션의 연산 내용의 불일치

3. 동시성 제어기법 종류
 1) Locking : 데이터 읽기, 쓰기제한, 간단한 알고리즘, 사전에 안전성 보장, Lock 대시시간, DeadLock 우려
 2) TimeStamp : 트랜젝션 수행시간 정렬, DeadLock 없음, Lock 대기시간 없음, Rollback 확률 높음, Cascading Rollback
 3) Validation : 낙관적 수행후 오류 검증, 동시 처리능력 증가, 트랜젝션 대기시간 없음, 장기 트랜잭션 철회시 낭비

[데이터베이스] 병행제어

1. 다중 사용자 DBMS 의 동시적 트랜잭션 실행을 조정하는 기술

2. 단일 사용자 일때는 불필요

3. 병행제어는 갱신분실 때분에 필요하다

* 갱신분실
 - 트랜젝션이 데이터베이스를 갱신 할 때 사용자가 원하지 않는 결과를 초래하는 것
 - 트랜젝션 수행중 다른 트랜젝션이 끼어들어 순차적 수행을 방해하기 때문
 - 2개이상의 트랜젝션이 같은 데이터를 공유하여 갱신할때 발생하는 문제

4. 갱신분실 해결 방법
 - 차단 방식
 1) 차단 (Lock) 방식
  - 한 트랜잭션이 데이터 베이스 갱신을 위해 수행중에 다른 트랜젝션이 접근 못하게 함
  - 차단 단위 : 데이터베이스> 테이블, 페이지, 레코드, 필드
  - 데이터 베이스 성격에 따라 차단 단위가 달라짐
  - 차단 수준이 높을 경우 활용도 낮아짐 , 수준이 낮을수록 활용도는 높아지나 그밖에 문제가 발생할 수 있음
 
  2) 차단 유형
   - 독점 차단 : 해당 차단이 해제되기 전까지 접근할 수 없다.
   - 공유 차단 : 작업중에도 검색은 가능하나 데이터 변경은 불가

  3) 2단계 차단
   - 확장단계 트랜잭션은 실행에 필요한 모든 차단을 설치, 이단계에서 어떤 차단도 해제해서는 안됨
   - 수축단계 : 트랜젝션이 차단을 해제, 새로이 차단을 해제 해서는 안됨, 새로이 차단하게 되면 교착상태 유발
   - 시작부터 확장단계로 하여 완전히 차단한 차단단계로 해서 처리가 끝난 후 수축단계로 완전 해제 하여 종료

  4) 교착 상태
  - 서로 다른 트랜잭션이 차단을 하고 있는 상태에서 교차하여 획득하려 할 때 발생
  - 둘중하나가 자신이 차단한 것을 풀지 않는한 진행 불가
  - 효율적인 사용이 불가
  - 이를 막기위해 시스템 자체에서 처음부터 예방 할 방안을 마련 하던가 하나가 취소가 되도록 우선권 부여
     또는 회피 등의 방법이 있다

-타임스탬프(timestamp)
  - 교착상태의 미발생과 자원의 효율적인 사용이 가능한 반면 오류 처리한 트랜잭션을 다시 수행해야 함
  - 다시 수행하는 트랜잭션이 기억장치 일부를 차지하여 처리속도가 느려지고 저장 단위가 커짐

[데이터베이스] 뷰

1. 데이터 베이스 관리자가 기본테이블에서 임의로 유도하여 만드는 테이블
2. 사용자에게 접근이 허용된 자료만 보여줌

3. 장점
  - 논리적 데이터 독립성 제공
  - 접근 제어를 통해 보안
  - 사용자 데이터 관리를 간단히

  * 기본테이블에서 유도된 가상 테이블, 간단하게 생성, 삭제 하지만 변경이 불가능하여 다시 설치 해야함

4. 기본 테이블은 물리적으로 구성되어 데이터가 실제로 저장되지만 뷰는 물리적이지 않다

5. 하나이 상의 기본 테이블로 유도된 가상 테이블

6. Drop : 제거 , Create : 생성 , 검색 : Select

7. 뷰를 이용해 또 다른 뷰의 생성이 가능

8. 삽입, 갱신, 삭제 연산에는 제약

9. View1 을 이용하여 View2 생성후 테이블 R 과 View2 를 조인하여 View3 를 생성하였다
 
  그 후 Drop View V1 Restrict 명령어 실행 하면 View1 이 삭제 되지 않는다.

10. 뷰의 정의는 Alter 문을 이용해 변경할수 없다

[데이터베이스] 트리

1. 일반트리
 - 일반적인 트리

2. 이진트리
 - 차수가 2이하인 트리
 - 트리내부 노드 차수가 전부 2를 넘지 않는다.
 - 노드가 하나도 없어도 이진트리라고 할수 있다

 1)이진트리의 성질
  - 높이가 h 인 이진트리에서 최소 노드갯수는 h
  - 최대 노드 개수는 2^h -1
  - 노드가 n 개 있을 때 최대높이는 n
  - 최소높이는 logN +1

 2) 이진트리의 종류

    - 포화 이진트리 (Full Binary Tree)
      : 모든레벨의 노드가 있음, 노드 차수가 전부 2, 새레벨을 만들지 않고 더이상 노드가 추가 될수 없다

   - 완전 이진트리 (Complete Binary Tree)
      : 노드가 차례로 들어감, 노드에 번호를 붙일경우  위에서 아래, 왼쪽에서 오른쪽 순서로 붙인다고 하면 빈 곳이 없는 트리

   - 기타 이진 트리
     :  포화도 완전도 아닌 나머지 이진 트리. 순서중 빈 노드 자리가 있으면 완전 이진트리가 아님

[데이터베이스] 데이터 모델

1. 관계형 데이터 모델
 - 계층 모델과 망 모델의 복잡한 구조를 단순화 시킨 모델
 - 표(Table)를 이용해서 데이터 상호 관계를 정의 하는 DB구조
 - 데이터 간의 관계를 기본키(Priamry Key)와 이를 참조하는 외래키(Foreign Key)로 표현
 - 대표적인 DBMS : Oracle, MS-SQL, Informix
 - 장점 : 간결하고 편리, 다른 인터페이스로 변환 용이
 - 단점 : 성능이 다소 떨어짐


2. 계층형 데이터 모델
 - 데이터의 논리적 구조가 트리형태, 개체가 트리를 구성하는 노드 역할
 - 개체 집합에 대한 속성 관계를 표시하기 위해 개체를 노드로 표현, 개체 집합들 사이를 링크로 연결
 - 개체 간의 관계는 부모와 자식으로 표현
 - 개체 타입간 상위와 하위가 존재,  1 : N 대응 관계만 존재
 - 레코드 삭제 시 연쇄삭제 (Triggered Delete)
 - 개체 타입들 간에는 Cycle 허용 안됨
 - 계층형 모델에서는 개체(Entity)를 Segment 로 표현
 - 대표적 DBMS는 IMS

3. 망 형 데이터 모델
 - CODASYL 이 제안, CODASYL DBTG 모델 이라고도 함
 - 그래프를 이용해서 데이터 논리 구조를 표현
 - 상위와 하위 레코드 사이 N:M (다대다) 관계
 - 상위레코드를 Owner, 하위레코드를 Member 라 하여 Owner-Member 관계라고도 함
 - 레코드 타입 간의 관계는 1:1, 1:N, N:M 이 될수 있음
 - 대표적인 DBMS : DBTG, EDBS, TOTAL

[데이터베이스] 스택

1. 스택이란 
  - 리스트 내의 데이터 삽입, 삭제가 한쪽 끝에서 이루어지는 데이터 구조

2. 오버 플로우 처리
  - 스택 알고리즘에서 T가 스택 포인터, m 이 스택이 길이 일때 서브루틴 AA 가 처리해야 하는것

  * 서브루틴
    - 주 프로그램의 임의 지점
    - 일반적으로 서브루틴이 다 끝났을 때 되돌아가는 지점은 자동적으로 서브루틴 으로 들어온 분기점 바로 다음 명령
    - 임의적으로 되돌아가는 지점을 서브루틴 내에서 지정 할 수 있다
    - 프로그램 작성을 더 쉽고 빠르게 하기 위함.
    - 프로그램 일부를 한 번만 적재하여 주프로그램에서 필요로 할때만 서브루틴으로 분기 하여 메모리 절약
    
    *  오버플로우처리
      T<- T+1   //스택 포인터 증가
     IF T > m Then   //스택 포인터가 m 보다 커진다면
      GOTO AA
     Else
      X(T) <- Y


3. Stack 응용분야
  - 인터럽트 처리
  - 수식계산
  - 서브루틴의 복귀 번지 저장

4. Stack 메모리에 대한 정보 입출력 방식 : LIFO, FILO

[데이터베이스] 파일구조

1. 순차파일

 정의
  - 레코드들을 연속적으로 저장하고, 저장된 순서대로 연속적으로 접근하는 방식의 파일

 종류
  - 입력 순차 파일, 키 순차 파일


2. 스트림 파일
 정의
  - 연속적인 판독 연산을 통해 레코드가 파일에 저장되어 있는 순서에 따라 데이터를 접근

 종류
 1) 순차 접근 스트림 파일 ( Sequential Access Stream File )
  - 판독 모드 : 판독 포인터는 파일의 첫번째 바이트
    * N 번째 바이트 값을 판독하기 위해서는 반드시 N-1 번째 바이트값을 판독 해야함

  - 기록 모드 : 기록 포인터는 파일의 첫 번째 바이트가 기록될 위치를 가리킴
    * N 번째 바이트 값을 기록하기 위해서는 반드시 N-1 번의 기록연산을 수행

  - 연속적으로 파일을 접근 하고 파일에 있는 모든 바이트를 처리해야 하는 경우에 유용함

  - 특정 바이트를 찾기 위한 방법으로는 부적절

 2) 임의 접근 스트림 파일 ( Random Access Steam File )
  - 이원 탐색법 : 배열의 인덱스를 이용하여 배열 원소를 직접(임의로) 접근
  * 이원 탐색법의 탐색 횟수  :  배열의 원소가 N 이라면 log2N 번


3. 순차 파일의 유형

  1) 임의 순차 파일 : 필드의 순서, 길이에 대한 제한이 없고, 레코드 길이 , 타입도 일정치 않음.
   - 삽입, 삭제, 변경 작업 : 새로운 순차 파일을 생성하면서 수행
  
   - 레코드 삭제 연산 : 삭제할 레코드는 생략하고 나머지 레코드 들만 새로운 파일로 출력

  2) 키 순차 파일

   - 저장 장치의 레코드 순서와 레코드 리스트의 논리적 순서가 같은 구조의 파일
   - 파일 내의 레코드 들은 키 필드 값에 따라 정렬

   - 특징 : 일괄 처리에 많이 사용, 차위 레코드를 신속하게 접근
   - 설계시 고려사항 : 필드 배치, 키 필드 선정, 블럭킹 인수 지정

     * 필드 배치 : 활동 파일/ 비활동 파일,  고정길이/가변길이
     * 키 필드 선정 : 키 필드는 레코드 접근 순서를 결정하는 요서, 응용 요건에 따라 선정
     * 블럭킹 인수 : 가능한 한 블록을 크게 하는것이 일반적


4. 순차 파일의 생성

 1) 생성
   - 데이터 저장 장치에 레코드를 순서대로 입력
   - 트랜젝션 파일 생성 : 키 순차 파일의 갱시에 트랜젝션 파일 이용

 2) 편집
   - 트랜젝션 파일 생성 과정에서 입력되는 데이터 값에 오류여부를 검사하는 과정


5. 순차 파일의 갱신
 
  1) 검색 : 레코드 저장 순서에 따라 연속적으로 검색
  
  2) 파일의 질의 적중 비율  일의 응답을 위해 접근해야 할 레코드 수 / 파일 전체 레코드 수

  3) 키 순차 파일의 갱신
   - 삽입 : 기존 레코드 사이에 삽입 위치를 검색 => 삽입점 앞의 모든 레코드를 새파일로 복사
                 => 새로운 레코드 삽입 => 삽입점 뒤의 나머지 레코드를 새파일로 복사
   - 삭제 , 수정도 비슷한 절차

  4) 순차 마스터 파일의 갱신 : 트랜젝션 파일의 트랜젝션은 갱신 코드를 포함( I : 삽입 , D : 삭제 , C : 수정 )

   - 삽입 : 트랜젝션 코드, 키 값은 반드시 필요
   - 삭제 : 삭제 하려는 해당 마스터 레코드의 키 값만 지정 해도 됨
   - 수정 : 키값과 수정될 필드들 해당값만 명세

  5) 마스터 파일 갱신 빈도수
 
    * 갱신 빈도수를 결정하는 요인
     - 데이터 변경률 : 클수록 빈도수 증가
     - 마스터 파일의 크기 : 클수록 갱신 비용증가, 빈도수 감소
     - 마스터 파일의 최신 데이터 요구  : 요구가 클수록 빈도수 증가
     - 파일 활동 비율 : 클수록 빈도수 증가

       * 파일 활동 비율
         -일련의 트랜젝션에 의해 영향을 받는 마스터 파일의 레코드 수 / 마스터 파일의 총 레코드 수

  6) 파일 활동 비율이 낮을수록 신 마스터 파일로 단순히 복사하는 레코드 수가 증가한다.

  7) 키 순차 마스터 파일의 갱신 알고리즘
   - 마스터 파일과 트렌젝션 파일 비교
   - 어느 한 키 값이 두 파일에서 일치하면 갱신 프로그램은 갱신 코드에 따라 레코드 수정 / 삭제
   - 트랜젝션 레코드 키 값이 마스터 파일의 어떤 레코드의 것과도 일치하지 않으면, 새로 삽입할 레코드로 간주하여 마스터 파일에 삽입



  8)

[데이터베이스] 관계형데이터베이스

관계형 데이터 베이스를 구성하는 개체(Entity) 나 관계(Relationship)를 모두 릴레이션(Relation) 이라는
표(Table) 로 표현한다.  - Table = Entity = Relation

1. 관계형 데이터 베이스의 구조
 1) 튜플 (Tuple)
  - 릴레이션을 구성하는 각각의 행
  - 행(Row), 가로
  - 파일 구조에서 레코드와 같은 의미
  - 튜플의 수를 Cardinality 또는 기수, 대응수 라고 한다
 
  2) 속성 (Attribute)
   - 데이터베이스를 구성하는 가장 작은 논리적 단위
   - 열(Column) , 세로
   - 개체(Entity)의 특성
   - 속성의 수를 Degree 또는 차수 라고 한다

  3) 도메인 (Domain)
   - 하나의 Attribute 가 취할 수 있는 같은 타입의 원자 (Atomic) 값들의 집합
   - 실제 Attribute 값이 나타날 때 그 값의 합법 여부를 검사하는 데에도 사용


2. 릴레이션의 특징

 - 한 릴레이션에 포함된 튜플들은 모두 상이함 (유일성)
 - 한 릴레이션에 포함된 튜플 사이에는 순서가 없다
 - 모든 속성은 원자값
 - 속성은 릴레이션 내에서 유일한 이름을 가짐
 - 속성들간 순서 없음


릴레이션 = 파일                = 테이블
튜플          = 레코드            = 행
속성          = 필드, 아이템 = 열
릴레이션 차수         =         속성의 개수
카디널리티               =         튜플의 개수


3. 관계 데이터베이스의 제약조건

 1. 키(Key) 개념 및 종류
   - 키는 데이터 베이스에서 조건에 만족하는 튜플을 찾거나 순서대로 정렬할 때 튜플들을 서로 구분할수 있는 기준이 되는  Attribute

   1) 기본키 (Primary Key)
     - 후보키 중에 선택한 주 키 (Main Key)
     - 한 릴레이션에서 튜플을 유일하게 구별할 수 있는 Attribute
     - NULL 값을 가질수 없다
     - 후보키의 성질중  유일성, 최소성 을 모두 만족

    2) 외래키 (Foreign Key)
     - 한릴레이션 R1 의 기본키의 값들과 일치함을 요구하는 다른 릴레이션 R2 의 한 Attribute
  
    3) 후보키 (Candidate Key)
     - 기본키로 사용될 수 있는 Attribute
     - 후보키는 릴레이션에 있는 모든 튜플에 대해 유일성과 최소성을 만족시켜야 함
     - 유일성(Unique) : 하나의 키값으로 하나의 튜플만을 식별할 수 있어야 함
     - 최소성(minimality) : 모든 레코드들을 유일하게 식별하는 데 필요한 속성으로만 구성 되어야 함
   
    4) 대체키 (Alternate Key)
     - 후보키가 둘 이상일 때 기본키를 제외한 나머지 후보키


4. 무결성 (Integrity)
    - 권한이 부여된 사용자에 의하여 발생할 수 있는 데이터베이스의 오류를 방지하기 위함.
    - 데이터베이스를 정확하고 유효하게 유지


5. 무결성 제약조건
 
  1) 개체 무결성 제약조건
    - 한 릴레이션의 기본키를 구성하는 어떠한 속성 값도 NULL 값이나 중복값을 가질수 없음
  
  2) 참조 무결성 제약조건
    - 릴레이션 R1에 저장된 튜플이 릴레이션 R2 에 있는 튜플을 참조하려면 참조되는 튜플이 반드시 R2에 존재
    - 릴레이션은 참조할 수 없는 외래키를 가질 수 없음


  3) 도메인 무결성 제약조건
    -  속성값이 가질 수 있는 값의 범위를 벗어난 값은 가질 수 없다
    (예> 속성이 성별일 경우 도메인은 남,녀 를 벗어날 수 없다
 

5. 관계대수
   - 원하는 정보와 그 정보를 어떻게 유도하는가를 기술한 절차적인 방법
   - 주어진 관계로부터 원하는 관계를 얻기 위해 연산자와 연산규칙을 제공하는 언어
   - 피연산자와 결과가 모두 릴레이션이다
  - 질의에 대한 해를 구하기 위해 수행해야 할 연산의 순서를 명시한다

6. 순수 관계 연산자
   1) Project
     - 테이블에서 특정 속성에 해당하는 열을 선택하는데 사용
     - 릴레이션의 열(세로) 에 해당하는 Attribute를 추출 하는 것이므로 수직연산자라고도 함
     - 연산자의 기호는 파이

   2) Join
     - 공통 속성을 중심으로 두 개의 릴레이션을 하나로 합쳐서 새로운 릴레이션을 만드는 연산
     - 연산자 기호는 ▷◁
  
   3) Select
     - 릴레이션에 존재하는 튜플 중에서 선택 조건을 만족하는 튜플의 부분집합을 구하여 새로운 릴레이션을 생성
     - 릴레이션의 행(가로)에 해당하는 튜플을 구하는 것이므로 수평 연산자라고도 함
     - 연산자의 기호는 시그마 (δ)

[데이터베이스] 관계데이터베이스 정규화

1. 데이터의 논리적 표현

  1) 이상 ( anomaly) 
  -  attribute (속성) 간에 존재하는 여러 종속관계를 하나의 릴레이션에 표현함으로 나타나는 현상 
  - 삭제이상, 삽입이상, 갱신이상

  2) 정규화 ( nomalization)
  - 이상 문제를 해결하기 위해 attribute 간의 종속관계를 분석하여 여러 개의 relation 으로 분해하는 과정

2. 함수종속

  - 어떤 릴레이션에서 속성들의 부분집합을 x,y 라 할 때 , 임의 튜플에서 x값이 y 값을 함수적으로 결정한다면,
    y 가 x 에 함수적으로 종속되었다고 하고 x → y 로 표현함 (x가 y 에 영향을 줌)

  - 함수종속의 성질 : 완전 함수 종속, 부분 함수 종속

  - 이행적 함수종속 : a →b 이고 b→c 이면, a→c 이다

3. 정규형 ( 릴레이션을 분해하는 과정)

  - 제 1 정규형 ( 1NF )
   - 모든 도메인이 원자 값만으로 된 릴레이션
   - 중복을 제거한 원자값의 형태
   - 기본키는 NULL 이 될수 없다

 - 제 2 정규형 ( 2NF )
   - 1NF 이고 모든 attribute 들이 기본키에 완전 함수 종속인 경우
  - 키가 아닌 속성은 기본키에 완전히 함수적으로 종속되어야 한다
   - 종속을 가질수 있는 키는 하나여야 함
  - 부분적 함수 종속 제거
   - 한 릴레이션에 기본키로 이용되는 키가 1개 이상일 경우 분리
     (a,b,c,d,e) → (a,b,c) , (a,d,e)

 - 제 3 정규형 ( 3NF )
   - 2NF 이고 모든 attribute 들이 기본키에 이행적 함수 종속이 아닌 경우
   - 이행적 함수종속 제거
   - 기본키가 아닌 두열은 상호간 종속이 없어야 함
   - 기본키가 아닌 값들중 변경 발생시 다른 열에서 변경이 발생하면 안됨
   - 키가 아닌 모든 속성은 키값에 전부 함수적 종속 상태
   - 기본키가 있고 속성중에 다른 속성의 기본키가 되는 경우 이 부분을 제거

 - 보이스/코드 정규형 (BCNF) (제 4 정규형 ) ( 제5 정규형)
   - 릴레이션의 모든 속성이 후보키인 경우

 - 제 4 정규형 ( 4NF )
   - 릴레이션에서 다치종속 관계가 성립하는 경우
   - 한개의 속성에 두개 이상의 속성이 종속된 상태가 다치 종속
   - 종속자를 기준으로 다치 종속된 속성을 분리하면 제4 정규화

 - 제 5 정규형 ( 5NF )
   - 릴레이션에서 조인종속성이 성립하는 경우
   - 후보키를 통하지 않는 조인 종속제거
   - 모든 조인 종속이 적어도 다음중 하나를 가질때

[데이터베이스] 설계단계

1. 요구조건 분석

 - 사용자가 원하는 데이터 베이스 용도 파악

2. 개념적 설계 ( 산출물 : E-R 도표)

 - 사용자들의 요구사항을 이해하기 쉽게 간단히 기술

3. 논리적 설계 (사용자 관점) ( 산출물 : 데이터모델)

 - 개념적 설계에서 만들어진 구조를 구현가능한
   data model ( 관계데이터모델,네트워크데이터 모델, 트리데이터모델,객체지향데이터모델)로 변환

4. 물리적 설계 ( 하위단계설정)

 - 논리적 데이터베이스 구조를 내부 저장장치 구조와 접근 경로등을 설계

 - 응답시간, 저장공간효율, 트랜잭션처리능력 고려

[데이터베이스] 정렬

1. 정렬(Sort)
 - 데이터 집합을 정해진 순서로 재배열
 - 정렬의 기본은 비교,교환
 - 정렬 방법에 따라 여러 알고리즘이 존재
 - 복잡성에 따라 단순정렬 (선택,삽입,버블), 고급정렬 (퀵,기수,힙,병합)
 - 장소에 따라 내부정렬,외부정렬
 - 교환방식에 따라 직접정렬, 간접정렬

2. 선택정렬(Selection Sort) 

 - 압부분 부터 정렬 되어 나감

 - 자료(N) : ↑ , 시간(T) : →

 - 비교 : N(N-1)/2, 교환 : N-1

 - worst case

   (2,3,4,5,1) -> (2,3,4,1,5) -> (2,3,1,4,5) -> (2,1,3,4,5) -> (1,2,3,4,5)

 - 단순하지만 입력자료에 둔감

3. 삽입정렬 (Insertion Sort)

 - 현재레코드를 일부 정렬된 부분의 적절한 위치로 옮김

 - 적절한 위치 검색 속도가 중요

 - Binary Search (이분법) 이용한 개선 가능

 - 정렬부분 관 미정렬 부분으로 구분 하여 미정렬 부분의 앞의값을 정렬부분의 뒤의값부터 앞으로 비교해 나감

- 자료(N) : ↑ , 시간(T) : →

-상대적으로 앞부분부터 정렬이 되어감

- 비교 : N(N-1)/2  * (1~(N-1)) , 교환 N(N-1)/2

- worst case  : Reverse

(5,4,3,2,1)-> (4,5,3,2,1) -> (3,4,5,2,1) -> (2,3,4,5,1) -> (1,2,3,4,5)

- 입력자료에 민감

- 난수배열에서는 삽입정렬이 약간 우수 하나 순차배열에서는 월등함, 일반적으로 삽입정렬이 성능이 좋음.


4.버블정렬

- 인접한 두개의 원소를 비교하여 자리를 교환

- 첫번째 원소부터 마지막 원소까지 반복해서 비교하여 가장 큰 원소가 가장 마지막으로 가는것이 한 단계

- 첫단계 이후 가장 큰 원소가 가장 큰 원소의 앞자리로 이동

- 메모리 사용공간 : N 개의 원소에 대하여 N 개의 메모리 사용

- best : 이미 정렬 되어 있음,  비교 : n(n-1)/2 , 교환 : 0

- worst : 자료가 역순으로 정렬 , 비교 : n(n-1)/2 , 교환 : n(n-1)/2

[데이터베이스] 스키마

1. 스키마 (schema)
 - collection of metadata
 - describing the structure and constraint of a database
 - defines data entities, attirubte, relations and constraint on data manipulation
 - save on data dictionary
 - 데이터 구조적 특성
 - 시간에 따라 불변인 특성
 - 데이터 논리적 단위에 명칭을 부여하고 그 의미를 기술

2. 외부스키마 (External Schema)
 - 데이터베이스 내용에 대한 전체적인 뷰(View)
 - 사용자나 응용프로그래머가 접근할 수 있는 정의 기술
 - Serve Schema
 - 하나의 DBMS에는 여러개의 외부스키마가 존재할 수 있다.
 - 하나의 외부스키마는 여러개의 응용프로그램이나 사용자에 의해 공유 될 수 있다

3. 개념스키마 (Conceptual Schema)
 - 개체간의 관계, 제약조건을 나타내고 DB접근권한, 보안정책 및 무결성 규정정의
 - 데이터베이스의 전체적 논리적 구조,  DB명세로서 하나만 존재
 - 기관이나 조직의 관점으로 DB를 정의 한 것
 - DBA에 의해서 작성

4. 내부스키마 (Internal Schema)
 - DB 물리적 구조를 정의
 - 물리적 저장장치의 관점에서 본 전체 데이터베이스의 명세로써 하나만 존재
 - 개념 스키마의 물리적 저장 구조에 대한 정의 기술
 - 시스템 프로그래머, 시스템 설계자 관점의 스키마