정보처리기사 필기 제1과목 데이터베이스 요약정리

소개글

정보처리기사 필기 제1과목 데이터베이스 요약정리에 대한 보고서 자료입니다.

목차

[Ⅰ.데이터베이스 시스템]
[Ⅱ. 데이터 모델링]
[Ⅲ. 관계 데이터 모델]
[Ⅳ.관계데이터베이스 언어]
[Ⅴ. 데이터 베이스 설계]
[Ⅵ. 고급 데이터 베이스]
[Ⅶ. 자료구조]
[Ⅷ. 파일 구조]

본문내용

됩니다. E는 D보다 커서 D오른쪽에있습니다.
(3회)D의 오른쪽이고 H의 왼쪽인 블럭 [E F G] 에거 가운데값은 F이고, E는 F의 왼쪽에 있습니다.
(4회)F의 왼쪽에 남은 블럭은 E만 있습니다. E를 찾았습니다.
2) 아래보기의 자료에서 이진탐색을 적용할 때 14를 찾기 위한 비교횟수는?
(보기) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
(답)3회
(풀이) (1회) 전체 개수가 15개이고 양쪽을 똑같이 나누어주는 값(가운데값)은 6입니다. 찾고있는 14는 8의 오른쪽입니다.
(2회) 8의 오른쪽 나머지들 [9 10 11 12 13 14 15] 에서 가운데 값은 12 입니다. 14는 12의 오른쪽에 있습니다.
(3회) 12의 오른쪽 나머지 블럭 [13 14 15] 에거 가운데 값은 14이고 찾고있는 14과 같습니다. 찾았습니다.
3) 다음 자료들 중 58을 찾기 위해 이진탐색을 할 경우 비교 횟수는 ?
(보기) 25, 29, 34, 37, 41, 43, 54, 58, 62, 70, 83
(답) 4회 (풀이) (1회) 가운데 값은 43, (2회) 가운데값은 62
(3회) 54, 58의 두수중 작은 값을 찾아 비교한다. (4회) 58을 찾음
4) 이진탐색 알고리즘에서 데이터가 (1,2,3,4,5,6,7,8,9,10,11)로 구성되어 있을 때 찾고자 하는 key 값이 2일 때 데이터와 찾고자하는 key값의 비교횟수는 ? (답)4회
(풀이) (1회) 가운데 값은 6 (2회) 1,2,3,4,5 중 가운데값은 3,
(3회) 1,2 중 작은 값인 1을 비교함 (4회) 2를 찾음
(2) 스레드 이진 트리(threaded binary tree) : 이진트리(binary tree)에서 발생하는 널(null) 링크를 트리 운행에 필요한 다른 노드의 포인터로 사용하도록 고안된 트리
(3) B 트리 :
1) 정의
- 한 노드 안에 있는 킷값은 오름차순을 유지한다.
- 모든 리프(leaf) 노드는 같은 레벨에 있다.
- 루트(root) 노드는 리프가 아닌 이상 적어도 두 개의 서브트리를 갖는다.
- 리프가 아닌 노드의 킷값의 수는 그 노드의 서브트리수보다 하나 적으며, 각 리프 노드는 최소한 "m/2-1", 최대 "m-1"개의 킷값을 갖는다.
(아닌 것 : 킷값의. 삽입이나 삭제시 트리의 총 노드수는 변함이 없다.)
(4) 트라이(Trie) : 키 탐색을 위해 킷값을 직접 표현하지 않고 키를 구성하는 문자나 숫자의 순서로 킷값을 표현한 자료구조
- 트라이의 차수는 킷값을 표현하기 위해 사용하는 문자의 수(radix)에 의해 결정된다.
- 킷값의 분포를 미리 예측할 수 있다면 기억장소를 절약할 수 있다.
- 트라이의 크기는 나타내려고 하는 킷값의 기수와 키 필드 길이에 의해 결정된다.
2. 파일 구조
(1) 저장장치
(2) 직접파일(Direct file)
1) 해싱(Hashing)
① 직접 파일을 구성하는 방법은 저장하고자 하는 데이터의 키값을 저장 공간의 물리적 주소(home address)로 변환할 수 있는 어떤 관계(relationship)를 정의해 두었다가 이를 활용하는 방법
이 관계를 사상함수(mapping function)또는 해싱함수 라고 하고 주소변환 프로그램을 의미한다.
해싱함수를 통하여 레코드키를 디스크의 물리적 주소로 변환하여 그 주소에 레코드를 저장하는 과정을 hashing이라고 한다.
② 해싱을 사용하여 파일을 만들 때 고려할 필수 요소는 버킷크기, 적재율, 해싱함수, 오버플로 해결기법이다.
- 버킷(bucket) : 하나의 주소를 갖는 파일의 한 구역. 버킷의 크기는 같은 주소에 포함될 수 있는 레코드의 수
- 슬롯(slot) : 한 개의 레코드를 저장할 수 있는 공간으로 n개의 슬롯이 보여 하나의 버킷을 형성한다.
- 충돌(collision) : 레코드를 삽입할 때 2개의 상이한 레코드가 똑같은 버킷으로 해싱되는 것
(아닌 것 : 해싱은 충돌이 발생하면 항상 오버플로우가 발생한다)
③ 해싱함수의 종류
ⅰ. 제산 잔여 해싱(제산(division) 방법) : 키값을 적당한 수로 나누어 이 나눗셈의 나머지를 레코드에 대한 물리적 주소로 사용하는 방법
ⅱ. 중간 제곱(mid-square)해싱 : 킷값을 제곱한 수의 중앙 위치에서 미리 정해진 위치의 숫자를 뽑아내어 주소를 만든다.
ⅲ. 중첩(folding) 해싱 : 키 값을 주소와 같은 자릿수를 갖는 몇 개의 부분으로 나누어 이 부분들을 접어서 그 합을 구한 다음, 그 합에서 주소와 같은 자리수만을 취하는 방법
ⅳ. 숫자 이동 변환해싱( 숫자분석(digit analysis)) : 키를 중앙으로 양분한 뒤에 주소 길이만큼 겹치도록 안쪽으로 각각 이동시켜 이들을 더하는 방법
ⅴ. 진수 변환 해싱 : 키 숫자의 진수를 다른 진수(11진수)로 변환시켜 주소 크기를 초과한 높은 자릿수는 절단시키고 이를 다시 주소 범위에 맞게 조정한다.
(3) 인덱스된 순차 파일(ISAM : Indexed Sequential Access-Method : Indexed Sequential File)
- 인덱스를 저장하기 위한 공간과 오버플로우 처리를 위한 별도의 공간이 필요하다.
- 실제 데이터 처리 외에 인덱스를 처리하는 추가적인 시간이 소모되므로 파일 처리 속도가 느리다.
- 순차 처리와 직접처리가 모두 가능하다.
1) 정적(static) 인덱스 방법
- ISAM파일의 인덱스 : master index, cylinder index, track index (섹터 인덱스는 없다.)
고정길리 레코드만 수용,
2) 동적 인덱스 방법
- VSAM 파일 : 기본 데이터 영역과 오버플로우 영역을 구분하지 않는다.
레코드를 삭제하면 그 공간을 재사용할 수 있다.
제어 구간에 가변 길이 레코드를 쉽게 수용할 수 있다.
(아닌 것 : 특정 레코드에 대해 빠르고 직접적인 접근을 지원할 수 있기 때문에 대화형 처리에 많이 이용된다.)
(아닌 것 : VSAM(virtual storage accdess method file) : 검색속도를 빠르게 하기 위하여 기본 데이터 구역과 오버플로우 구역을 구분하여 갖추어야한다.)

키워드

정보처리,   기사,   필기,   제1과목,   데이터베이스,   요약정리