정보처리기사 필기 정리 데이터베이스

제 1 장 자료 구조

1. 기본 개념

1) 자료의 단위

BIT → BYTE → WORD → FIELD → RECORD → BLOCK → FILE → DB(DataBase) → DataBank

① bit : 기억, 정보표시의 최소단위 ② byte : 문자, 주소지정 단위(1byte=8bit)

③ word : 명령처리 단위 ④ field : 자료구성 단위

⑤ record : 자료처리 단위 ⑥ block : 입출력 단위

2. 선형 구조

1) 배열

― 동일한 크기, 형식 등으로 구성된 연속적인 기억공간.

	A(10)
① 1차원 배열 :
	a(1)	a(2)	a(3)	․․․․․					a(9)	a(10)

	A(4,5)
② 2차원 배열 :	a(1,1)	a(1,2)	a(1,3)	a(1,4)	a(1,5)		※ A(M,N)에서 A(i,j)는 몇번째 ?
	a(2,1)	a(2,2)	a(2,3)	a(2,4)	a(2,5)		행우선 : (i-1)N + j
	a(3,1)	a(3,2)	a(3,3)	a(3,4)	a(3,5)		열우선 : (j-1)M + i
	a(4,1)	a(4,2)	a(4,3)	a(4,4)	a(4,5)

③ 3차원 배열

※ 3차원 배열의 주소 : A(L,M,N)에서 A(i,j,k)의 주소=?

행우선 : α+(i-1)MN + (j-1)N + (k-1)

열우선 : α+(k-1)LM + (j-1)L + (i-1)

2) 스택(Stack)

― LIFO 구조를 가진 기억장소 구조.

PUSH(삽입)		POP(삭제)
				※ Top : 가장 최근에 삽입된 자료 또는 가장 먼저 삭제될 자료를 가리키는 포인터. ※ Bottom : 스택의 밑바닥.
			←Top, Bottom

 

 

① 삽입 알고리즘

if top ≧ n then overflow else top = top + 1 stack(top) ← 삽입

② 삭제 알고리즘

if top ≦ 0 then underflow else 삭제 ← stack(top) top = top-1

※ 스택의 운영(n=3)
초기상태		A 삽입		B 삽입		C 삽입		삭제		삭제
						C	←top
				B	←top	B		B	←top
		A	←top	A		A		A		A	←top

③ 다중 스택 : 하나의 기억 공간에 여러 개의 스택으로 운영하는 형태로 overflow의 발생 방지를 위해 사용.

④ 스택의 응용 : 서브루틴 호출, 순환 프로그램, 인터럽트 처리, 수식 표기, 0-주소, 컴파일러 등

3) 큐(Queue)

― FIFO구조를 가진 기억장소 구조.

삭제(front)←

←삽입(rear)

※ rear(tail) : 삽입 포인터, front(head) : 삭제 포인터

① 삽입 알고리즘

if rear = n then overflow else rear = rear + 1 Queue(rear)←삽입

② 삭제 알고리즘

if front = rear then underflow else front = front + 1 삭제 ← Queue(front)

※ 큐의 운영(n = 3)

초기 상태

A 삽입

B 삽입

A

A

B

↑↑ f r

↑ f

↑ r

↑ f

↑ r

삭제

C 삽입

D 삽입→overflow

B

B

C

B

C

↑ f

↑ r

↑ f

↑ r

↑ f

↑ r

③ 큐의 단점 : 큐의 구조는 삽입(rear)과 삭제(front)시 앞으로만 이동하기 때문에 한 번 사용한 기억공간은 사용할 수 없다. → 환형 큐로 보완.

④ 환형(원형) 큐 : 원형으로 표현된 큐.

㉠ 삽입 : rear = (rear+1) MOD n

㉡ 삭제 : front = (front+1) MOD n

㉢ rear = front : overflow 또는 underflow

4) 데큐(Deque)

― 양쪽 모두 삽입과 삭제가 가능한 형태.

① SCROLL : 입력 제한 ② SHELF : 출력 제한

5) 링크드 리스트(Linked list)

― 선형 구조에서 포인터를 사용하는 경우.

data 부분

link 부분

※link 부분 : 다음에 찾아갈 기억장소의 주소 기억.

① 링크드 리스트의 장단점

장 점	단 점
․ 중간 노드의 삽입, 삭제시 효율적. ․ 기억장소로부터 독립적.	․ Access time이 느리다. ․ 링크 포인터만큼의 기억공간 소모.

② 링크드 리스트의 종류

㉠ 단일 선형 링크드 리스트(Singly Linked list)

10			20			30			40
A	20		B	30		C	40		D	∧

․장점 : 간단하다.

․단점 : 뒤에 있는 노드를 추적할 수 없고, 중간 노드 포인터를 잃어버리면 후속노드를 추적할 수 없다.

㉡ 단일 환형 링크드 리스트(Singly Circular Linked list)

10			20			30			40
A	20		B	30		C	40		D	10

 

․장점 : 어디에서 시작하든지 모든 노드의 엑세스가 가능하다.

․단점 : 없는 노드를 찾을 경우 무한 루프에 빠질 수 있다. (head 포인터 이용)

㉢ 이중 선형 링크드 리스트(Doubly Linked list)

	10				20				30				40
∧	A	20		20	B	30		30	C	40		40	D	∧

․장점 : 임의의 링크 포인터를 잃어버려도 역으로 읽는 포인터로 복구가 가능.(순방향, 역방향으로 융통성이 좋다.)

․단점 : 운영이 복잡하다.

㉣ 이중 환형 링크드 리스트(Doubly Circular Linked list)

	10				20				30				40
40	A	20		20	B	30		30	C	40		40	D	10

 

․ 가장 융통성이 좋으나, 대단히 복잡하다.

3. 비선형 구조

1) 트리(Tree)

① 트리의 용어

㉠근(root) 노드 : 최상위 노드.

㉡노드의 차수(degree) : 노드의 가지 수.

㉢단말(terminal)노드 : 차수가 0인 노드.

㉣간 노드 : 차수가 0이 아닌 노드.

㉤형제 노드 : 같은 레벨의 노드 중 부모가 같은 노드들.

㉥노드의 레벨 : 근 노드로부터 각 노드들이 속해 있는 깊이.

㉦트리의 높이 : 트리 에서 노드의 최대 레벨.

② 트리의 종류

㉠이진 트리(Binary tree) : 모든 노드의 차수가 2이하인 트리.

   ㉡정이진 트리(Full binary tree) : 깊이가 n일 경우, n번째 레벨의 노드의 수가 2n－1개이고, 트리의 전체 노드 수가 2n－1개인 트리.(마지막 레벨까지 꽉 채워진 트리)

               ㉢전이진 트리(Complete binary tree) : 깊이가 n일 때, n－1 레벨까지 정이진트리로 된 트리.

㉣사향이진 트리(Skewed binary tree) : 왼쪽이나 오른쪽으로만 치우쳐진 트리.

㉤K진 트리 : 모든 노드의 차수가 K 이하인 트리.

③ 트리의 이진 트리 변환

  

―형제 노드끼리 연결하고, 연결한 부분 중 기존의 가지는 삭제.

※트리를 이진 트리로 변환하는 이유 : 널 링크 점유율이 적기 때문.

④ 이진 트리의 특성

㉠ 레벨 n에서의 최대 노드 수는 2n－1개이고, 트리의 전체 노드 수는 2n－1개.

㉡ 차수가 2인 노드 수와 단말 노드 수와의 관계(n0 : 단말 노드 수, n2 : 차수가 2인 노드 수) → n0 = n2 + 1

⑤ 이진 트리의 메모리 표현

㉠ 배열에 표현하는 방법

․장점 : 엑세스가 효율적이다.

․단점 : 기억공간 낭비가 심하다.(사향이진 트리인 경우)

㉡ 링크를 이용하는 방법

․장점 : 노드의 삽입, 삭제가 용이, 기억공간이 절약.

․단점 : 엑세스가 느리다.

⑥ 트리의 운행법

㉠ Level order 운행법 : 같은 레벨의 노드를 좌에서 우로 검사하는 방법.

․하향식 : 근노드에서 최하위 레벨까지 좌에서 우로 검사.

․상향식 : 최하위 레벨에서부터 근노드까지 좌에서 우로 검사.

㉡ Preorder 운행법 : Root → Left → Right

㉢ Inorder 운행법 : Left → Root → Right

㉣ Postorder 운행법 : Left → Right → Root

ex) 트리 운행 예

하향식 : a, b, c, d, e, f, g, h 상향식 : h, d, e, f, g, b, c, a

Preorder : a, b, d, e, c, f, h, g

Inorder : d, b, e, a, h, f, c, g

Postorder : d, e, b, h, f, g, c, a

⑦ 쓰레디드 이진 트리(Threaded Binary Tree) : 널 링크를 트리내의 다른 노드를 가리키도록 구성한 트리.

㉠ 왼쪽 널 링크 : 전 노드의 위치 지정.

㉡ 오른쪽 널 링크 : 다음 노드의 위치 지정.

⑧ 이진 트리의 패스 길이

㉠ 내부 패스 길이(Internal path length) : 각 노드의 패스 길이를 합산한 것.

㉡ 외부 패스 길이(External path length) : 단 노드에 가상적 노드를 추가하여, 근노드와 가상 노드와의 길이를 합산한 것.

 

 

 

 

내부 패스 길이 : 0+1+1+2+2+2+2+3+3=16

외부 패스 길이 : 3+3+3+3+4+4+4+4+3+3=34

 

2) 그래프(Graph)

― 정점과 간선의 집합으로 이루어진 구조.

① 그래프의 종류

㉠ 무방향 그래프 : 정점들의 쌍의 순서가 없는 그래프.

㉡ 방향 그래프 : 간선들의 방향을 표시하는 그래프.

㉢ 완전 그래프 : 모든 정점에 대해 각각 간선을 갖는 그래프.

② 그래프 표현법

㉠ 인접 행렬 ㉡ 인접 리스트 ㉢ 역 인접 리스트

③ 그래프의 운행

㉠ 깊이 우선(DFS) : 스택 이용.

㉡ 너비 우선(BFS) : 큐 이용.

④ 최소 비용 신장 트리 : 그래프 상에서 최소 비용으로 모든 정점을 방문하는 방법.

※ 비용이 가장 적은 순서대로 선택 → 선택된 간선이 Cycle을 형성하면 제외.

⑤ 위상 정렬 : 방향 그래프에서 작업의 순서에 따라 나열해 놓은 것.

⑥ 임계 경로 : 작업의 시작에서 종료될 때까지 가장 긴 경로.

 

4. 정렬(Sort)

1) 내부 정렬

― 주기억 공간을 이용하는 방법(속도가 빠르다)

※ 내부 정렬의 종류

․삽입법 : 삽입 소트(insertion sort), 쉘 소트(shell sort)

․교환법 : 버블소트(bubble sort), 셀렉션 소트(selection sort), 퀵 소트(quick sort)

․선택법 : 힙 소트(heap sort)

․머지법 : 2―웨이 머지 소트(2―way merge sort)

․분배법 : 래딕스 소트(radix sort)

① 삽입 소트 : 레코드에 하나씩 삽입하면서 정렬하는 방법. (평균 수행 시간 : O(n2))

② 쉘 소트 : 매개 변수를 이용하는 방법.

③ 버블 소트 : 인접한 두 자료를 비교하면서 정렬하는 방법으로 뒤에서부터 정렬. (평균 수행 시간 : O(n2))

④ 셀렉션 소트 : 하나의 자료를 기준으로 나머지 모든 자료와 비교하는 방법으로 앞에서부터 정렬. (평균 수행 시간 : O(n2))

⑤ 퀵 소트 : 제어키를 이용하여 제어키보다 큰 값은 제어키 오른쪽에, 작은 값은 제어키 왼쪽으로 이동시킨다. 스택을 이용하는 방법으로 소트 방법 중 가장 빠르다. (평균 수행 시간 : O(n log2 n))

⑥ 힙 소트 : 힙 트리를 이용하는 방법. (평균 수행 시간 : O(n log2 n))

※ 힙 트리 : 부노드가 자노드보다 큰 트리.

⑦ 2―웨이 머지 소트 : 2개의 자료를 하나로 합치면서 정렬하는 방법. (평균 수행 시간 : O(n log2 n))

2) 외부 정렬

― 보조기억공간를 이용하는 방법.

① Natural Merge sort

② Balanced Merge sort

③ Polyphase Merge sort(다단계 합병 정렬) : 피보나치 수열 이용.

④ Cascade Merge sort(계단식 합병 정렬) : 여러 개의 테이프를 한꺼번에 처리하다가 그 중 1개의 테이프만 끝나면 멈추는 방식.

⑤ Oscillation Merge sort : 순방향과 역방향 읽기가 가능한 방법.

 

5. 검색(Search)

1) 검색의 종류

① 선형 검색(순차 검색) : 처음부터 차례대로 검색.

② 제어 검색 : 자료가 정렬되어 있어야 함

㉠ 이분 검색 : 상한값(high)과 하한값(low)을 설정한 후 중간값(mid)을 구해, 중간값과 비교 후 검색.

㉡ 피보나치 검색 : 피보나치 수열을 이용.

㉢ 보간 검색 : 있음직한 부분을 선택하여 검색.(사전식 검색)

③ 블록 검색 : 전체 데이터를 일정한 개수의 블록의 구분하여 검색. (효율적인 블록의 크기 : )

④ 이진 트리 검색 : 이진 탐색 트리를 이용하는 방법.

․이진 탐색 트리 : 왼쪽 서브 트리 키들은 루트보다 작다.

오른쪽 서브 트리 키들은 루트보다 크다.

 

※ prefix, infix, postfix 표현법(수식 표현)

prefix : 연산자, 변수, 변수 (+AB)

infix : 변수, 연산자, 변수 (A+B)

postfix : 변수, 변수, 연산자 (AB+)

① infix → prefix (※infix를 prefix나 postfix로 바꿀 때는 먼저 연산순위를 결정한다.)

ex) A/B**C+D (infix)

 

 

 

A/(**BC)+D → (/A**BC)+D → +/A**BCD (prefix)

② infix → postfix

ex) A/B**C+D (infix)

 

 

A/(BC**)+D → (ABC**/)+D → ABC**/D+ (postfix)

 

③ prefix → infix : 앞에서부터 연산자, 변수, 변수 순으로 된 것을 찾아 연산자를 변수와 변수 사이로 옮긴다.

+/A**BCD → +/A(B**C)D → +(A/B**C)D → A/B**C+D (infix)

 

④ postfix → infix : 앞에서부터 변수, 변수, 연산자 순으로 된 것을 찾아 연산자를 변수와 변수 사이로 옮긴다.

ABC**/D+ → A(B**C)/D+ → (A/B**C)D+ → A/B**C+D (infix)

 

  

제 2 장 파일구조

1. 파일 구조

1) 파일의 종류

① 순차 파일(SAM) : 파일 내의 각 레코드를 논리적 순서에 따라 물리적으로 연속된 위치에 기록한 파일.

장 점	단 점
․기억장소의 낭비가 없다. ․취급이 용이하다.	․삽입, 삭제가 어렵다. ․순차 처리만 가능하다.

 

② 직접 파일(DAM) : 해싱 함수를 이용하여 디스크내의 물리적 주소로 직접 저장․검색하는 파일.

※ 해싱 : 계수적 성질을 이용하여 해싱함수에 의해 기억장소 주소로 직접 변환시켜 접근하는 방법.

※ 해싱함수의 종류 : 제산 방법, 진법 변환, 제곱 방법, 중첩 방법, 계수 분석법 등

※ 해싱의 오버플로 처리 방법 : Random method, Chain method, Linear method, Quadratic method

장 점	단 점
․특정 레코드의 access가 빠르다. ․중간레코드의 삽입, 삭제용이.	․기억장소 낭비가 심하다. ․주소를 계산해야 한다.

 

③ 인덱스된 순차 파일(ISAM) : 순차 접근을 지원하는 순차 파일과 직접 접근 방법을 지원하는 직접 파일을 결합한 형태의 파일을 말하며, 키 값에 따라 정렬된 레코드를 순차적으로 접근하거나 주어진 기 값에 따라 직접 접근하는 파일이다.

※ISAM 파일의 구성

․기본 영역 : 기본적인 데이터가 저장.

․인덱스 영역 : 데이터의 위치 저장.

(마스터 인덱스 → 실린더 인덱스 → 트랙 인덱스)

․오버플로우 영역 : 기본 영역 이외의 데이터 또는 추가된 데이터 저장. (독립 오버플로우, 실린더 오버플로우)

장 점	단 점
․순차, 직접처리 모두 가능. ․추가, 삭제 용이.	․기억공간 낭비. ․접근 기간이 느리다. ․재편성의 문제. ․고정길이 레코드만 수용.

 

④ VSAM(Virtual Storage Access Method) : ISAM과 비슷하나, 인덱스 부분과 자료를 기억하는 부분으로 나뉘고, 각 블록에는 나중에 레코드가 삽입될 것을 감안하여 빈 공간을 미리 준비해두는 방법.(가변길이 레코드 수용 가능.)

⑤ 다중 키 파일(Multi-key File)

㉠ 역 파일(inverted file) : 키 값을 갖는 레코드들에 관한 정보 포인터가 각각의 인덱스 자체에 모두 있다.

장점 : 인덱스만으로도 접근이 가능하다.

단점 : 인덱스의 길이가 가변적이다.

㉡ 다중 리스트 파일(multi-list file) : 인덱스가 키값을 갖는 첫 번째 데이터에만 포인터를 갖고, 후속 데이터는 포인터로 추적해야 하는 파일.

장점 : 인덱스가 고정적이고, 수정, 삭제, 검색이 효율적.

단점 : 인덱스만으로 모든 데이터를 접근할 수 없다.

 

※ B-트리

― 인덱스를 조직하는 방법으로 가장 많이 사용되는 것.

― 특 징

․루트와 리프(단말 노드)를 제외한 모든 노드는 최소 m/2개, 최대 m개의 서브트리를 갖는다.

․모든 리프는 같은 레벨에 있다.

․루트는 리프가 아닌 이상 적어도 두 개의 서브트리를 갖는다.

․한 노드 안에 있는 키값들은 오름차순으로 유지한다.

․검색은 루트에서부터 시작한다.

 

  

제 3 장 데이터베이스 시스템

1. 데이터베이스 개념

1) 데이터베이스 정의

― 어느 한 조직에서 다수의 응용 시스템들이 공용으로 사용하기 위해 통합, 저장된 운영 데이터의 집합.

① 통합된 데이터(중복 최소) ② 저장된 데이터

③ 운영 데이터 ④ 공용 데이터

2) 데이터베이스 특징

① 실시간 접근이 가능 ② 계속적인 변화

③ 동시 공유 가능 ④ 내용에 의한 참조 가능

3) 데이터베이스의 논리적 구성

① 개체(entity)

․표현하려는 유형, 무형 정보의 대상으로 존재하면서 서로 구별이 되는 것.

․생각하는 개념이나 정보의 단위.

․하나 이상의 속성으로 구성.

② 속성(attribute) : 개체의 특성이나 상태를 기술하는 것. (단독으로 존재하기는 어렵다.)

③ 관계(relationship) : 개체간 또는 속성간의 상호 작용. (1 : 1, 1 : n, n : m)

4) 데이터베이스 구조

① 논리적 구조 : 일반 사용자 관점에서 본 구조.

② 물리적 구조 : 저장 장치 관점에서 본 구조.

 

2. 데이터베이스 관리 시스템(DBMS : DataBase Management System)

1) 종래 자료 처리 시스템의 문제점

― 데이터 종속성, 데이터 중복성

2) DBMS의 정의

― 사용자와 데이터베이스의 중재자로서 모든 사용자나 응용 프로그램들이 데이터베이스를 공유할 수 있도록 관리해 주는 소프트웨어 시스템.

3) DBMS의 필수 기능

① 정의 기능 : 데이터의 형태, 구조, 데이터베이스의 저장에 관한 내용 정의.

② 조작 기능 : 사용자의 요구에 따라 검색, 갱신, 삽입, 삭제 등을 지원하는 기능.

③ 제어 기능 : 정확성과 안전성을 유지하는 기능.(무결성 유지, 보안, 병행 수행 제어)

4) DBMS의 장단점

장 점	단 점
․데이터 중복의 최소화 ․데이터 공유 ․일관성 유지 ․무결성 유지 ․데이터 보완 보장 ․표준화 가능	․많은 운영비 ․자료 처리의 복잡 ․backup, recovery의 어려움

3. 데이터베이스 시스템의 구성

※ DBMS의 궁극적인 목적 : 데이터 독립성 제공.

1) 3단계 데이터베이스

① 외부 스키마 : 가장 바깥쪽 스키마로, 전체 데이터 중 사용자가 사용하는 한 부분에서 본 구조. (사용자가 무엇을 사용하느냐에 따라 다름)

② 개념 스키마 : 논리적 관점에서 본 구조로 전체적인 데이터 구조.

③ 내부 스키마 : 물리적 저장장치 관점에서 본 구조.

2) 데이터 언어

① 정의어 : 데이터베이스의 정의 및 수정 등에 사용.

② 조작어 : 데이터베이스 내에서 검색, 삽입, 수정, 삭제 등에 사용되는 언어.

※질의어 : DB를 사용자가 이용하도록 만든 언어로 자연어이며 대화식 언어.

③ 제어어 : 데이터를 보호하기 위해 데이터의 보안, 무결성, 회복, 병행 수행 등에 사용되는 언어.

3) 데이터베이스 관리자(DBA)

― DBMS의 전체적인 관리 운영에 책임을 지는 사람.

― DBA 의 역할

① 데이터베이스 구성 요소 결정 ② 스키마 정의

③ 저장 구조와 접근 방법 선정 ④ 보안, 권한 부여, 유효성 검사

⑤ 예방, 회복 절차 수립 ⑥ 무결성 유지 등

 

4. 데이터베이스 시스템의 내부적 운영

 

제 4 장 데이터 모델링

1. 개체-관계 모델(E-R, Entity-Relationship Model)

1) 개체-관계 모델

― 개체 타입과 관계 타입을 기본 개념으로 현실 세계를 개념적으로 표현하는 방법.

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

기 호	의 미
	개 체
	속 성
	다중속성 : 여러 개의 값을 가질 수 있는 속성.
	관 계 : 개체간의 상호 작용.
	키속성 : 모든 개체들이 모두 다른 값을 갖는 속성.
	복합속성 : 하나의 속성을 부분으로 나누어질 수 있는 속성.

ex) E-R 다이어그램 예

 

 

 

 

 

 

2. 논리적 데이터 모델(DB 모델)

1) 관계 데이터 모델

― 표 데이터 모델이라고도 하며, 구조가 단순하며 사용이 편리하고, n : m 표현이 가능하다.

2) 네트워크 데이터 모델

― 망 데이터 모델이라고도 하며, 레코드 타입간의 관계에 대한 도형적 표현(그래프 형태) 방법이다. 오너-멤버 관계 즉, 1 : n 관계로 이루어져 있다.

3) 계층 데이터 모델

― 트리 데이터 모델이라고도 하며, 부모-자식 관계 즉, 1 : n 관계로 이루어져있다.

 

 

제 5 장 관계 데이터 모델

1. 관계 데이터 구조 및 제약

1) 관계 데이터 구조

① 릴레이션 : 정보 저장의 기본 형태가 2차원 구조의 테이블.

② attribute(속성) : 테이블의 각 열을 의미.

③ 도메인 : 어트리뷰트가 취할 수 있는 값들의 집합.

④ 튜플 : 테이블이 한 행을 구성하는 속성들의 집합.

 

학생
학번	이름	학년	학과
100	나연묵	4	컴퓨터
200	이찬영	3	전기
300	정기태	1	컴퓨터
400	송병호	4	컴퓨터
500	박종화	2	산․공

 

  

 

2) 릴레이션 특성

① 릴레이션의 토플들은 유일하며 순서가 없다.

② 릴레이션에서 어트리뷰트들 간의 순서는 의미가 없다.

③ 어트리뷰트는 원자값으로서 분해가 불가능하다.

3) 키의 종류

① 후보키 : 속성 집합으로 구성된 테이블의 각 튜플을 유일하게 식별할 수 있는 속성이나 속성의 조합들을 후보키라 한다.(유일성, 최소성)

② 기본키 : 개체 식별자

③ 대체키 : 기본키를 제외한 후보키들

④ 외래키 : 다른 테이블을 참조하는데 사용되는 속성.

4) 무결성 제약

① 개체 무결성 : 기본키 값은 널이 될 수 없다.

② 참조 무결성 : 외래키 값은 참조 릴레이션에 있는 기본키와 같아야 함.

 

2. 관계 데이터 연산

1) 관계 대수

― 릴레이션 조작을 위한 연산의 집합으로 연산자를 이용하여 표현된다.(절차적 언어)

일반 집합 연산자 : 합집합, 교집합, 차집합 등

순수 관계 연산자 : SELECT, PROJECT, JOIN, DIVISION

 

 

ex) 학생

학 번	이 름	학 년	전 공	점 수
01	오태훈	3	컴퓨터	80
02	이재현	2	수학	85
03	노병두	1	수학	70
04	이영덕	1	수학	79

① 셀렉트(SELECT, σ)

․표기 형식 →

σ<선택조건> (테이블 이름)

σ점수≥80 (학생) → ‘학생’ table에서 점수 속성 값이 80점 이상인 튜플 선택.

학번	이름	학년	전공	점수
01	오태훈	3	컴퓨터	80
02	이재현	2	수학	85

②프로젝트(PROJECT, π)

․표기 형식 →

π<속성 리스트> (테이블 이름)

π이름, 전공 (학생) → ‘학생’ table에서 이름과 전공 속성 선택.

이름		전공
오태훈		컴퓨터
이재현		수학
노병두
이영덕

③조인(JOIN, ▷◁ ) : 두 관계로부터 관련된 튜플 들을 하나의 튜플로 결합하는 연산.

학번 (STNO)	성명 (NAME)	학과 코드 (DNO0	학년 (YEAR)		학번 (STNO)	과목 (COURSE)	성적 (SCORE)
9801 9802 9803 9804 9805	오태훈 이재현 조남호 노병두 한바다	100 200 300 100 400	2 3 1 3 4		9801 9801 9802 9803 9803 9803 9804	자료구조 데이터베이스 컴퓨터 구조 자료 구조 운영체제 데이터베이스 데이터베이스	90 80 90 80 90 90 90

(a) (b)

㉠ 동일 조인

학번 (STNO)	성명 (NAME)	학과 코드 (DNO)	학년 (YEAR)	학번 (STNO)	과목 (COURSE)	성적 (SCORE)
9801 9801 9802 9803 9803 9803 9804	오태훈 오태훈 이재현 조남호 조남호 조남호 노병두	100 100 200 300 300 300 100	2 2 3 1 1 1 3	9801 9801 9802 9803 9803 9803 9804	자료구조 데이터베이스 컴퓨터 구조 자료 구조 운영체제 데이터베이스 데이터베이스	90 80 90 80 90 90 90

㉡ 자연조인 : 동일 조인 결과에서 중복되는 속성을 제거.

학번 (STNO)	성명 (NAME)	학과 코드 (DNO)	학년 (YEAR)	과목 (COURSE)	성적 (SCORE)
9801 9801 9802 9803 9803 9803 9804	오태훈 오태훈 이재현 조남호 조남호 조남호 노병두	100 100 200 300 300 300 100	2 2 3 1 1 1 3	자료구조 데이터베이스 컴퓨터 구조 자료 구조 운영체제 데이터베이스 데이터베이스	90 80 90 80 90 90 90

㉢ 외부조인 : 조인시 조인할 상대 릴레이션이 없을 경우 널 튜플로 만들어 결과 릴레이션에 포함

학번 (STNO)	성명 (NAME)	학과 코드 (DNO)	학년 (YEAR)	과목 (COURSE)	성적 (SCORE)
9801 9801 9802 9803 9803 9803 9804 9805	오태훈 오태훈 이재현 조남호 조남호 조남호 노병두 한바다	100 100 200 300 300 300 100 400	2 2 3 1 1 1 3 4	자료구조 데이터베이스 컴퓨터 구조 자료 구조 운영체제 데이터베이스 데이터베이스	90 80 90 80 90 90 90

④ 디비전(DIVISION, ÷) : 동시에 포함하는 속성.

2) 관계 해석

― 원하는 릴레이션을 정의하는 방법을 제공.(비절차적 언어)

{ 결과값 ｜ 조건 }

① 튜플 해석식

'수강' table에서 과목 C413이고, 성적이 A인 모든 학생의 학번은?

→ {e.SNO｜수강(e)∧e.과목='C413∧e.성적='A'}

② 도메인 헤석식

'수강' table에서 과목 C413이고, 성적이 A인 모든 학생의 학번은?

→ (DSNO 학번) (DGRADE 성적) (DCNO 과목번호)

{DSNO｜수강(DSNO, DCNO, DGRADE)∧DCNO='C413'∧DGRADE='A'}

  

 

제 6 장 관계 데이터베이스 언어

※SQL(구조적 질의어) : IBM에서 개발된 데이터베이스에 사용되는 언어.

※SQL의 특징

․관계대수와 관계해석을 기초로한 고급 데이터 언어.

․이해하기 쉬운 형태.

․대화식 질의어로 사용 가능.

․데이터 정의, 데이터 조작, 제어 기능 제공.

․COBOL, C, PASCAL 등이 언어에 삽입.

․레코드 집합 단위로 처리.

․비절차적 언어.

1. SQL 정의어

― 스키마, 도메인, 테이블, 뷰, 인덱스를 정의하거나 제거하는데 사용.

※ 데이터 타입

․정수 : INTEGER(INT), SMALLINT

․실수 : FLOAT, REAL, DOUBLE PRECISION

․정형 숫자 : DECIMAL(i, j), NUMERIC(i, j)

․고정길이 문자 : CHAR(n), CHARACTER(n)

․가변길이 문자 : VARCHAR(n), CHAR VARYING(n), CHARACTER VARYING(n)

․비트 스트링 : BIT(n), BIT VARYING(n)

․날짜 : YYYY-MM-DD ․시간 : HH : MM : SS

1) CREATE 문

― 스키마, 도메인, 테이블, 뷰, 인덱스의 정의에 사용.

① 스키마 정의

구문

CREATE SCHEMA 스키마_이름 AUTHORIZATION 사용자_id

② 도메인 정의

구문

CREATE DOMAIN 도메인_이름 데이터_타입

③ 테이블 정의

구문

CREATE TABLE 테이블_명 ( {열_이름 데이터_타입 [NOT NOLL][DERAULT 묵시값] } [PRIMARY KEY (열_이름)] {[UNIQUE(열_이름)]} {[FOREIGN KEY(열_이름) REFERENCES 기본테이블]} [ON DELETE 옵션] [ON UPDATE 옵션] [CHECK (조건식)] ) ※｛ ｝: 반복을 의미, ［ ］ : 생략을 의미

④ 인덱스 정의 : CREATE INDEX 문에 의해 생성, 시스템이 자동적으로 관리.

2) ALTER 문

― 기존 테이블에 대해 새로운 열의 첨가, 값의 변경, 기존 열의 삭제 등에 사용.

구문

ALTER TABLE 테이블_이름 ADD 열_이름 데이터_타입 ALTER TABLE 테이블_이름 ALTER 열_이름 SET DEFAULT 값 ALTER TABLE 테이블_이름 DROP 열_이름 CASCADE

※ ADD : 열 추가, ALTER : 값 변경, DROP : 열 삭제

3) DROP 문

― 스키마, 도메인, 테이블, 뷰, 인덱스 제거시 사용. (전체 삭제)

구문

DROP SCHEMA 스키마_이름 [CASCADE or RESTRICTED] DROP DOMAIN 도메인_이름 [CASCADE or RESTRICTED] DROP TABLE 테이블_이름 [CASCADE or RESTRICTED] DROP INDEX 인덱스_이름

※ RESTRICTED : 삭제할 요소가 참조 중이면 삭제되지 않는다.

※ CASCADE : 삭제할 요소가 참조 중이더라도 삭제된다.

 

2. SQL 조작어

1) 검색문(SELECT)

구문

SELECT 열_이름(검색 대상) FORM 테이블_이름 [WHERE 조건] [GROUP BY 열_이름 [HAVING 조건] ] [ORDER BY 열_이름 [ASC or DESC] ]

① GROUP BY : 그룹으로 나누어준다.

② HAVING : 그룹에 대한 조건, GROUP BY 사용시 반드시 사용.

③ ORDER BY : 정렬 수행.

④ 부분 매치 질의문 : % → 하나 이상의 문자, _ → 단일 문자.

※부분 매치 질의문 에서는 ‘=’ 대신 LIKE 사용.

⑤ 널(NULL)값 비교 시는 '=' (또는 <>) 대신 IS (또는 IS NOT)을 사용.

2) 삽입문(INSERT)

― 기존 테이블에 행을 삽입하는 경우 사용.

구문

INSERT INTO 테이블[(열_이름...)] VALUES (열값_리스트)

3) 갱신문(UPDATE)

― 기존 레코드 열값을 갱신할 경우 사용.

구문

UPDATE 테이블 SET 열_이름=변경_내용 [WHERE 조건]

4) 삭제문(DELETE)

― 기존 테이블의 행을 삭제할 경우 사용.

구문

DELETE FROM 테이블 [WHERE 조건]

 

3. SQL 뷰

― 하나 이상의 테이블로부터 유도되어 만들어진 가상 테이블.

1) 뷰의 특징

① 뷰가 정의된 기본 테이블이 제거(변경)되면, 뷰도 자동적으로 제거(변경)된다.

② 외부 스키마는 뷰와 기본 테이블의 정의로 구성된다.

③ 뷰에 대한 검색은 기본 테이블과 거의 동일.(삽입, 삭제, 갱신은 제약)

④ DBA는 보안 측면에서 뷰를 활용할 수 있다.

⑤ 뷰는 CREATE문에 의해 정의되며, SYSVIEWS에 저장된다.

⑥ 한 번 정의된 뷰는 변경할 수 없으며, 삭제한 후 다시 생성.

⑦ 뷰의 정의는 ALTER문을 이용하여 변경할 수 없다.

⑧ 뷰를 제거할 때는 DROP문을 사용한다.

2) 뷰의 장단점

① 장점

㉠ 논리적 독립성 제공 ㉡ 데이터 접근 제어로 보안 가능

㉢ 사용자의 데이터 관리를 간단하게 함

㉣ 하나의 테이블로 여러 개의 상이한 뷰를 정의

② 단점

㉠ 독자적인 인덱스를 가질 수 없다. ㉡ 정의를 변경할 수 없다.

㉢ 삽입, 삭제, 갱신 연산에 많은 제약이 따른다.

 

4. 시스템 카탈로그

1) 정의

―DBMS가 유지하는 데이터베이스의 각종 정보와 정보들 간의 관계를 저장한 것으로 그 자체가 하나의 작은 데이터베이스이다.

2) 특징

① 카탈로그 자체도 일반 테이블과 같이 시스템 테이블로 구성.

② 일반 사용자도 내용을 검색할 수 있으나, 카탈로그의 내용을 삽입, 삭제, 갱신 등은 불가능하다.

③ 사용자가 SQL문을 실행하면 시스템이 자동적으로 관련 카탈로그 테이블을 갱신한다.

  

제 7 장 데이터베이스 설계

1. 데이터베이스 설계 단계

1) 요구 조건 분석

― 사용자가 원하는 데이터베이스의 용도를 파악하는 것.

2) 개념적 설계

― 사용자들의 요구사항을 이해하기 쉬운 형식으로 간단히 기술하는 단계.

3) 논리적 설계

― 개념적 설계에서 만들어진 구조를 구현 가능한 data 모델로 변환하는 단계.

4) 물리적 설계

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

※ 물리적 설계시 고려 사항

․응답 시간 ․저장 공간의 효율화

․트랜잭션 처리도(처리 능력)

 

2. 관계 데이터베이스의 정규화

1) 데이터의 논리적 표현

① 이상(anomaly) : 어트리뷰트간에 존재하는 여러 종속관계를 하나의 릴레이션에 표현함으로 인해 발생하는 현상.

․삭제 이상 ․삽입 이상 ․갱신 이상

② 정규화(normalization) : 이상 문제를 해결하기 위해 어트리뷰트 간의 종속관계를 분석하여 여러 개의 릴레이션으로 분해하는 과정.

2) 함수 종속

― 어떤 릴레이션에서 속성들의 부분 집합을 X, Y라 할 때, 임의 튜플에서 X의 값이 Y의 값을 함수적으로 결정한다면, Y가 X에 함수적으로 종속되었다고 하고, 기호로는 X → Y 로 표기한다.

ex)	학 번	성 명	학 과	학 년	→ ‘학번’을 알면 그 학생의 성명, 학과, 학년을 알 수 있을 때 성명, 학과, 학년은 학번에 종속되었다고 한다. (학번→성명, 학번→학과, 학번→학년)
	21015	오태훈	컴퓨터	2
	12020	이재현	수학	1
	32005	노병두	수학	3

※ 함수 종속의 성질

․완전 함수 종속 ․부분 함수 종속

․이행적 함수 종속 : R.A→R.B이고, R.B→R.C 이면 R.A→R.C인 경우.

 

3. 정규형

1) 제 1 정규형(INF)

모든 도메인이 원자 값만으로 된 릴레이션.

2) 제 2 정규형(2NF)

1NF이고, 모든 어트리뷰트들이 기본키에 완전 함수 종속인 경우.

3) 제 3 정규형(3NF)

2NF이고, 모든 어트리뷰트들이 기본키에 이행적 함수 종속이 아닌 경우.

4) 보이스/코드 정규형(BCNF)

릴레이션의 모든 속성이 후보키인 경우.

5) 제 4 정규형(4NF)

릴레이션에서 다치종속 관계가 성립하는 경우.

6) 제 5 정규형(5NF)

릴레이션에서 조인 종속이 성립하는 경우.

 

  

제 8 장 고급 데이터베이스

1. 트랜잭션의 개념

1) 트랜잭션

― 한꺼번에 모두 수행되어야 할 일련의 데이터베이스 연산들.

※ 트랜잭션 내의 모든 연산은 반드시 한꺼번에 완료되어야 하며, 그렇지 못한 경우 한꺼번에 취소되어야 함(원자성)

2) 트랜잭션의 성질

① 원자성 ② 일관성 ③ 격리성

④ 영속성 ⑤ 순차성

3) 트랜잭션의 연산

① COMMIT : 성공적인 종료 ② ROLLBACK : 비정상적인 종료

 

2. 회복(Recovery)

― 여러 가지 장애로 인해 손상된 데이터베이스를 손상되기 이전의 정상적인 상태로 복구시키는 작업.(덤프와 로그 이용)

※덤프 : 현재 프로그램에서 사용되는 주기억장치 내용을 보조기억장치에 기억시켜 두는 것.

※로그 : 컴퓨터 시스템에서 이루어지는 작업을 기억시켜 두는 것.

1) 장애의 유형

① 트랜잭션 장애 ② 시스템 장애 ③ 미디어 장애

2) 시스템 장애시 회복 기법

① 지연 갱신 : 트랜잭션이 완료될 때까지 지연시킨 후 로그에 기록하는 기법.

② 즉시 갱신 : 트랜잭션이 활동 상태에서 변경 내용을 로그에 기록하는 기법.

③ 검사시점 기법 : 검사시점을 설정하여 검사시점 이전에 완료된 내용을 기록.

④ 그림자 페이징 기법 : 트랜잭션 실행 시작시 현재 내용을 그림자 페이지에 기록.(로그 사용 않음)

 

3. 병행 제어

― 다중 사용자 환경에서는 여러 개의 트랜잭션이 동시에 실행되는데 이러한 방법을 병행 실행이라 하고, 병행 실행시 병행 제어를 수행해야 한다.

※ 병행 제어를 안 할 때의 문제점

․갱신 분실 ․모순성 ․연쇄 복귀

 

4. 무결성과 보안

1) 무결성

― 데이터베이스에서 현실 세계의 상황과 동일하게 data 값을 유지하는 것.

2) 보안

―불법적인 데이터의 폭로나 파괴로부터 데이터베이스를 보호하는 것.

 

5. 분산 데이터베이스

― 컴퓨터 네트워크 상에 분산된 논리적으로 서로 연관된 다중 데이터베이스 모임.

※ 분산 데이터베이스 시스템의 장점

․지역 자치성 ․점진적인 시스템 용량 확장

․신뢰성 및 가용성 ․효율성 및 융통성