방송대 데이터베이스시스템 - 15강. 연습문제 풀이 2 (9-14강)

---

문제 1번

다음 중 물리적 저장장치를 데이터 접근 속도가 빠른 것부터 느린 것 순서로 나열된 것은? [9강]

 

① 캐시 - 메인메모리 - 레지스터 - 자기디스크
② 자기디스크 - 메인메모리 - 레지스터 - 캐시
③ 레지스터 - 캐시 - 메인메모리 - 자기디스크
④ 메인메모리 - 자기디스크 - 레지스터 - 캐시

---

(비쌈, 빠름, 휘발성) 레지스터 - 캐시 - 메인 메모리 - 자기디스크, 플래시 메모리 - 광학 디스크, 자기 테이프 (저렴함, 느림, 비휘발성)

휘발성	전원 공급이 중단되면 기억장치 안의 모든 데이터가 소멸됨. • 캐시 : 고비용 저장장치로 빠른 접근 속도를 보장 • 메인 메모리 : 실제 프로그램과 데이터 적재 공간
비휘발성	용량은 많지만 조회 속도는 느려서 읽고 쓰는 빈도는 적고, 주로 데이터 보관 용도로 사용됨. • 플래쉬 메모리 : 메인 메모리와 유사하나 비휘발성 • 자기 디스크 : 데이터베이스 전체를 안정적으로 저장, 가장 많이 사용되는 외부 저장장치 • 광학 디스크 드라이브 : CD, DVD, Blue-ray 등 • 테이프 장치 : 용량이 크고 저렴하나 순차 접근 방식으로 접근 속도가 매우 느림

---

문제 2번

다음과 같은 테이블의 스키마에 대해 각 고정 길이 레코드에 할당되는 바이트 수는? [9강]

(단, INT는 4바이트 길이를 갖는다)

속성	데이터타입
회원번호	CHAR(10)
회원이름	CHAR(45)
나이	INT
전화번호	CHAR(13)

 

① 4
② 68
③ 70
④ 72

---

바이트 수 = 10 + 45 + 4 + 13 = 72

 

고정 길이 레코드 : 고정적인 바이트 수를 갖는 레코드를 저장하는 기법

8바이트 + 20바이트 + 10바이트 + 4바이트  1개의 레코드 길이 대략 42바이트	모든 레코드는 42 바이크 크기로 구성 (가정) i번째 레코드는 (i - 1) * 42 + 1 번째 바이트부터 42 개의 바이트를 읽어 접근

잔여 고정 길이 레코드 할당	고정 길이 레코드 할당
블럭의 길이가 레코드 길이로 정확히 나눠지지 않아 잔여 공간을 비워두는 방법	블럭의 길이가 레코드 길이로 정확히 나눠지지 않아 한 레코드를 두 블럭으로 나누어 저장하는 방법
블럭 내의 남은 공간 낭비	레코드 접근 시 두 블럭을 접근하므로 성능 저하

---

문제 3번

다음은 어떤 파일구조에 대한 설명인가? [9강]

모든 레코드를 파일 내 임의의 위치에 저장하며, 저장하는 순서를 고려하지 않는 파일 구조

 

① 힙 파일구조
② 순차 파일구조
③ 클러스터링 파일구조
④ 해시 파일구조

---

---

문제 4번

다음 중 가변 길이 레코드 방식이 필요한 이유가 아닌 것은? [9강]

 

① 레코드가 멀티셋(multiset)을 이용하는 컬럼을 가질 때
② 한 블록 내에 저장되는 레코드 유형이 둘 이상일 때
③ 길이가 고정되지 않은 컬럼이 한 개 이상일 때
④ 레코드의 수정이 매우 자주 발생할 때

---

가변 길이 레코드 : 블럭에 저장되는 레코드의 길이가 서로 다른(가변적) 레코드를 할당하는 방법

 

가변 길이 레코드가 사용되는 상황

- 한 블럭 내에 저장되는 레코드 유형이 둘 이상

- 길이가 고정되지 않은 컬럼의 개수가 하나 이상 (ex. VARCHAR)

- 레코드가 멀티셋을 허용한 컬럼을 가질 때

 

※ 멀티셋

- 레코드의 컬럼값이 여러 개인 컬럼

- 관계형 모델을 사용하는 DBMS에서는 허용되지 않음.

- 몇몇 상용 데이터베이스에서 컬럼값의 원자성을 확대시키는 경우가 있음.

---

문제 5번

가변 길이 레코드를 저장하기 위해 파일 또는 블록의 헤더에 유지하는 다음과 같은 형식의 구조를 무엇이라고 하는가? [9강]

① 페이지 구조화
② 웹 페이지 구조
③ 슬롯 페이지 구조
④ 페이지 테스트

---

레코드를 페이지(page) 단위로 관리하며, 각 페이지는 고정된 크기를 가지고 있음.

각 페이지는 여러 개의 슬롯(slot)으로 나뉘어져 있으며, 각 슬롯은 가변길이 레코드를 저장하는 단위임.
슬롯페이지 구조에서는 가변길이 레코드가 저장되기 위해 빈 슬롯을 찾아서 할당함.

 

가변길이 레코드는 슬롯에 저장되며, 레코드의 길이에 따라 필요한 만큼의 슬롯을 사용함.

가변길이 레코드의 크기가 작을 경우에는 하나의 슬롯에 저장될 수도 있고, 크기가 큰 경우에는 여러 개의 슬롯을 사용할 수 있음.
가변길이 레코드가 저장되는 슬롯은 헤더 정보를 포함하고 있어서, 레코드의 길이와 같은 정보를 저장하고 관리함.

삭제된 레코드의 경우에는 해당 슬롯을 다시 사용 가능한 상태로 표시하고, 새로운 레코드가 추가될 때 해당 슬롯을 재활용함.

 

신규 레코드는 슬롯 페이지의 중간에 있는 가용 공간의 뒤쪽에서부터 저장되는데 이를 위해 블럭 헤더에 가용 공간의 끝에 대한 위치가 저장됨.

---

문제 6번

다음 중 요청된 레코드에 빠르게 접근할 수 있도록 하는 구조인 인덱스의 효율성에 대한 평가기준이 아닌 것은? [10강]

 

① 새로운 데이터 삽입 시 발생하는 인덱스 구조 유지 비용
② 인덱스를 통해 데이터를 찾고 접근하는데 걸리는 시간
③ 인덱스를 저장하기 위해 부가적으로 필요한 공간 비용
④ 사용자의 인덱스를 사용하는 질의 요청 빈도

---

인덱스의 평가기준

· 접근시간(access time) : 데이터를 찾는 데 걸리는 시간

· 유지 비용(maintenance cost) : 새로운 데이터 삽입 및 기존 데이터 삭제 연산으로 인한 인덱스 구조 갱신 비용

· 공간 비용(space cost) : 인덱스 구조에 의해 사용되는 부가적인 공간 비용

---

문제 7번

다음의 설명은 어떤 인덱스에 대한 설명인가? [10강]

모든 탐색키 값에 대해 탐색키 <값, 포인터> 쌍으로 구성된 인덱스 엔트리를 갖는 인덱스로, 인덱스 파일의 크기가 커서 I/O 비용이 증가하여 탐색 시간이 오래 걸릴 수 있는 단점을 지님

 

① 밀집 인덱스
② 희소 인덱스
③ 해시 인덱스
④ 다단계 인덱스

---

밀집 인덱스	모든 레코드에 대해 탐색키 값, 포인터 쌍을 유지 · 장점 : 인덱스만으로도 레코드의 블럭 내 위치를 정확하게 찾을 수 있어서 검색 속도가 빠름. · 단점 : 많은 공간을 사용하여 비효율적임.
희소 인덱스	인덱스의 엔트리가 일부의 탐색키 값만을 유지 찾고자 하는 탐색키보다 작거나 같은 값 중 가장 큰 값을 찾음. · 장점 : 인덱스 크기가 작아 저장 공간을 적게 차지하며 적은 저장장치 접근 횟수로도 사용할 수 있음. · 단점 : 블럭 내부에서 레코드에 대한 작은 규모의 검색을 다시 해야 함.
다단계 인덱스	밀집 인덱스와 희소 인덱스가 결합된 구조 외부 인덱스에 대해서는 희소 인덱스, 내부 인덱스에 대해서는 밀집 인덱스 방식으로 블럭을 읽어들임. · 외부 인덱스 : 내부 인덱스를 가리키는 인덱스 엔트리의 집합 · 내부 인덱스 : 레코드를 직접 가리키는 인덱스 엔트리의 집합

---

문제 8번

다음은 B+-트리의 예시이다. 이순신을 탐색하는 과정에서 거치는 포인터를 올바른 순서로 나열한 것은? [10강]

① 1, 3, 6, 7, 9
② 1, 5, 9
③ 1, 4, 7, 8
④ 1, 5, 8

---

1) '정도전'보다 앞 순서 → '정도전'의 왼쪽으로

2) '박지성'과 '안창호' 중 이순신은 '안창호'의 뒷 순서 → '안창호'의 오른쪽으로

3) '이순신'의 왼쪽 포인터를 따라 가야 '이순신' 실제 레코드 값에 접근할 수 있음. → '이순신'의 오른쪽으로

---

문제 9번

위 그림에서 검색키를 버킷 주소에 대응시키는 h를 무엇이라고 하는가? [11강]

① 사용자 정의 함수
② 해시 함수
③ 도메인
④ 대칭 함수

---

 

해시(hash)/해싱(hasing)

탐색키에 산술적인 연산을 통해 버킷의 주소를 계산하는 해시함수를 사용하여 데이터 배분 및 접근하는 기법

마치 동물원에 영역을 구분하여 동물을 배치하는 것과 유사함.

· 정적 해싱(static hasing) : 저장 공간의 기본 단위인 버킷의 개수가 정해진 해싱 기법

· 동적 해싱(dynamic hashing) : 버킷의 개수가 데이터베이스의 크기에 따라 변하는 해싱 기법

 

버킷(bucket)

한 개 이상의 레코드를 저장할 수 있는 저장공간의 단위

크기는 일반적으로 디스크 블록의 크기와 일치 ('블럭' 대신 '버킷'이라는 용어 사용)

 

K : 모든 탐색키 Ki의 집합
B : 모든 버킷 주소 Bi의 집합
해시함수(h) : K를 B에 대응(mapping)시키는 함수

탐색키 Ki를 갖는 레코드를 삽입하려면,
해시함수를 사용하여 h(Ki)를 계산해서 해당 레코드를 위한 버킷 주소를 구한 다음 레코드를 해당하는 버킷에 저장함.

---

문제 10번

서로 다른 두 레코드 R1과 R2의 검색키가 h에 의해 동일한 버킷으로 대응되었을 때, R1과 R2를 무엇이라고 하는가?  [11강]

① 충돌
② 해싱

③ 오버플로
④ 동거자

---

· 충돌 : 서로 다른 두 레코드가 동일한 버킷에 대응되도록 하는 결과가 만들어진 것, 동거자의 생성

· 동거자 : 충돌에 의해 같은 버킷 주소를 갖는 레코드 → R1, R2의 관계

· 오버플로 : 버킷에 레코드를 저장할 수 있는 여유 공간이 없는 상황, 추가적인 버킷을 할당 또는 다음 버킷에 할당하여 처리

· 해시(hash)/해싱(hasing) : 탐색키에 산술적인 연산을 통해 버킷의 주소를 계산하는 해시함수를 사용하여 데이터 배분 및 접근하는 기법

---

문제 11번

데이터베이스의 크기에 따라 버킷의 개수 즉, B1, B2, ..., Bn이 조절되는 형태의 해싱을 무엇이라고 하는가?  [11강]

① 동적 해싱
② 공간 해싱

③ 복합 해싱
④ 정적 해싱

---

· 정적 해싱(static hasing) : 저장 공간의 기본 단위인 버킷의 개수가 정해진 해싱 기법

· 동적 해싱(dynamic hashing) : 버킷의 개수가 데이터베이스의 크기에 따라 변하는 해싱 기법

---

문제 12번

다음과 같은 테이블에 대해 성별 컬럼에 대한 비트맵 인덱스를 생성할 때, '남자'에 대한 비트 열로 올바른 것은?  [11강]

① 1010010
② 0001011

③ 0000101
④ 1110100

---

비트맵 인덱스의 구성

i번째 레코드가 컬럼 A에 해당 값을 가지면 비트맵의 i번째 비트를 1로, 그렇지 않으면 0으로 설정

남자 = 1, 여자 = 0 → 남자에 대한 비트열 : 1110100, 여자에 대한 비트열 : 0001011 (보기 2)

---

문제 13번

다음 중 트랜잭션의 특성이라고 할 수 없는 것은?  [12강]

 

① 확장성
② 원자성

③ 독립성(고립성)
④ 지속성

---

트랜잭션의 특징

다수의 연산으로 구성된 트랜잭션이 사용자에게 단일작업처럼 다뤄지도록 ACID 특징을 준수

ACID 특성 = 원자성, 일관성, 고립성(독립성), 지속성

원자성(Atomicity)	하나의 트랜잭션에 포함된 모든 연산은 완전히 수행되거나 전혀 수행되지 않음. (All or Nothing)
일관성(Consistency)	특정 트랜잭션이 수행되기 전과 후에 데이터베이스가 일관된 상태를 유지
고립성(Isolation)	특정 트랜잭션이 데이터베이스를 갱신하는 동안 다른 트랜잭션에 의해 방해받지 않음. 다수의 트랜잭션이 동시에 수행될지라도 각각의 트랜잭션은 DBMS 상에서 독자적으로 처리되는 것과 같음.
지속성(Durability)	완료된 트랜잭션의 결과는 어떠한 시스템의 장애에도 데이터베이스에 반영되어야 함(영구 지속).

---

문제 14번

다음 중 트랜잭션을 동시에 실행시키는 목적에 대한 설명으로 옳지 않은 것은? [12강]

 

① 데이터베이스의 일관성이 향상된다.
② 데이터의 가용성을 향상시킬 수 있다.

③ 트랜잭션의 대기시간을 감소시킬 수 있다.
④ 트랜잭션의 처리율과 자원의 이용률이 향상된다.

---

DBMS는 다수의 사용자가 데이터베이스를 공용으로 사용(②)하기 위한 목적으로 도입

트랜잭션 동시 실행의 이점

- 트랜잭션 처리율과 자원 이용률을 향상 (④)

- 트랜잭션의 대기 시간을 감소 (③)

다중 사용자 환경에서 트랜잭션의 동시 실행으로 데이터 갱신 시, 일관성 훼손 문제가 발생 (① X)

• 동시성 제어(concurrency control) : 다수의 트랜잭션이 성공적으로 동시에 실행되어도 일관성을 유지할 수 있도록 지원하는 기법

---

문제 15번

다음 빈 칸에 알맞은 말은? [13강]

 

스케줄에 대한 대기 그래프가 (     )을/를 포함하면, 그 스케줄은 교착상태에 있다는 것을 의미한다.

 

① 충돌
② 락

③ 동시성
④ 사이클

---

교착상태 탐지

대기 그래프(wait-for graph)를 이용하여 확인 가능

· 정점 V : 시스템 내의 트랜잭션으로 구성

· 간선 E : 트랜잭션의 순서쌍(Ti, Tj)

· Ti가 요청한 데이터의 락을 Tj가 소유하고 있으며, Ti는 Tj가 락을 반납하기 대기하는 상태

대기 그래프에 사이클이 있다면 교착 상태가 발생

트랜잭션 T12는 트랜잭션 T13과 T14를 기다리고 있다. 트랜잭션 T13은 트랜잭션 T15를 기다리고 있다. 트랜잭션 T14는 트랜잭션 T13을 기다리고 있다. 트랜잭션 T15는 트랜잭션 T14를 기다리고 있다. 이 그래프는 사이클 T13 → T15 → T14를 포함하고 있음. 트랜잭션 T13, T14, T15는 교착상태에 있음.

---

문제 16번

다음 중 아래의 스케줄과 충돌 동등한 스케줄이 아닌 것은? [12강]

① 같은 데이터 항목에 대한 Read 순서를 바꾸는 것은 어떠한 문제를 일으키지 않음.

② 서로 다른 데이터 항목에 대한 Write 순서를 바꾸는 것은  어떠한 문제를 일으키지 않음.

③  서로 다른 항목에 대한 Read와 Write의 순서를 바꾸어서 문제를 일으키지 않음.

④ 같은 항목에 대한 Read와 Write 연산을 교환하여 충돌이 발생함.

---

문제 17번

다음은 무엇에 대한 설명인가?  [12강]

두 트랜잭션 순서쌍 Ti와 Tj에 대해, Ti가 기록한 데이터 항목을 Tj가 읽는다면, Ti의 커밋이 Tj의 커밋보다 먼저 나타나는 스케줄

① 회복 가능한 스케줄
② 회복 불가능한 스케줄

③ 연쇄적인 스케줄
④ 비연쇄적인 스케줄

---

회복 가능한 스케줄	트랜잭션 실패 시 롤백이 가능하며, 일관성을 유지할 수 있는 스케줄 Ti와 Tj에 대해, Ti가 기록한 데이터를 Tj가 읽을 떄, Ti의 커밋이 Tj의 읽기 연산보다 먼저 나타나는 스케줄
회복 불가능한 스케줄	트랜잭션 실패 시 롤백이 불가능하며, 일관성이 깨지는 스케줄 커밋이 되기 이전의 값을 또다른 트랜잭션이 읽어서 처리한 경우
연쇄적인 스케줄	트랜잭션 간에 연쇄적인 의존관계가 있는 스케줄
비연쇄적인 스케줄	트랜잭션 간에 연쇄적인 의존관계가 없는 스케줄 모든 비연쇄적인 스케줄은 회복이 가능함.

---

문제 18번

락 기반 규약을 사용하는 시스템에서 다음의 두 트랜잭션이 병렬적으로 실행될 경우 어떤 스케줄이 작성될 수 있는가?  [13강]

① 충돌 직렬적 스케줄
② 회복 불가능한 스케줄

③ 교착상태 포함 스케줄
④ 비연쇄적 스케줄

---

UN(B)와 UN(A)가 맨 뒤에 나타나는 스케줄이므로 상호대기하는 스케줄

- 락을 너무 일찍 반납하면 일관성 훼손됨.
- 락을 너무 늦게 반납하면 교착 상태가 발생함.

---

문제 19번

교착상태 회복을 위해 교착상태의 트랜잭션 집합이 주어지면 교착상태를 해결하기 위해 롤백시킬 트랜잭션을 결정한다. 이때 롤백 대상 트랜잭션을 무엇이라 하는가?  [13강]

 

① 희생자
② 에러

③ 체크 포인트
④ 로그 레코드

---

교착상태의 회복

 

• 희생자 선정 : 롤백 비용이 가장 적은 트랜잭션을 선택

- 연산을 수행한 시간과 남은 작업을 마치기 위한 시간

- 사용한 데이터와 트랜잭션 실행에 필요한 추가적인 데이터 

- 롤백에 포함되는 트랜잭션의 개수

 

• 희생자 롤백 : 어느 시점까지 롤백할 것인지 결정

- 전체 롤백 VS 교착상태를 해결하는 지점

- 모든 트랜잭션의 상태에 대한 정보를 부가적으로 유지

 

• 무한정 기다림 해결 : 같은 트랜잭션이 항상 희생자로 선정되지 않도록 희생자 선정시 롤백 횟수를 고려

---

문제 20번

Write 연산을 수행할 때마다 데이터베이스가 변경되기 전에 로그 레코드를 우선 로그에 추가하는 방식은 무엇인가?  [14강]

 

① Non Read After Log
② Non Read Ahead Log

③ Write After Log
④ Write Ahead Log

---

데이터 항목 변경 과정

WAL (Write-Ahead Log) : 트랜잭션은 데이터베이스 수정 전, 로그 레코드를 생성하여 기록

ex. 잔액이 10만 원인 계좌에서 5만원을 입금하는 경우

- 우선 들어온 5만 원을 입금 시킨 후 잔액 기록을 15만 원으로 변경함. (DB 수정 → 로그 기록)

→ 입금 시킨 후 오류가 난 경우 기록이 남지 않으므로 데이터 원복이 불가능함.

- 잔액 기록을 15만 원으로 변경한 후, 들어온 5만 원을 입금 시킴. (로그 기록 → DB 수정)

→ 로그 기록 후 반영이 안 된 경우 오류 발생 이전으로 원복 가능함.

---

문제 21번

다음 중 체크포인트 발생 시 수행되는 작업이라고 할 수 없는 것은?  [14강]

 

① 다음 체크포인트 발생 주기를 결정한다.
② 현재 메인 메모리에 존재하는 모든 로그 레코드를 안정 저장장치에 기록한다.

③ 수정된 모든 버퍼 블록을 디스크에 반영한다.
④ 로그 레코드 <checkpoint ListT>를 안정 저장장치에 기록한다.

---

체크포인트 기법

체크포인트 작업이 수행되는 동안 모든 수정 작업을 중단하며, 현재 시점에 메인 메모리의 버퍼 블록에 존재하는 모든 로그 레코드를 안정 저장장치로 기록

→ 체크포인트 수행 시점 이전의 로그 기록은 회복 시 데이터베이스 반영에 필요 없도록 만듦.

· 메인메모리에 존재하는 모든 로그 레코드를 안전 저장장치로 기록함. (②)

· 수정된 모든 버퍼 블록을 Output하여 디스크에 반영함. (③)

· 로그 레코드 <checkpoint ListT>를 안정한 저장장치에 기록 (④)

   ListT : 체크포인트 시점에 실행 중인 트랜잭션 목록

 

체크포인트 기법을 이용한 회복 과정

· 로그의 마지막부터 역방향으로(최근부터) 탐색하여 <𝑐ℎ𝑒𝑐𝑘𝑝𝑜𝑖𝑛𝑡𝐿𝑖𝑠𝑡𝑇> 레코드를 찾음

· 𝐿𝑖𝑠𝑡𝑇에 존재하는 <𝑐ℎ𝑒𝑐𝑘𝑝𝑜𝑖𝑛𝑡𝐿𝑖𝑠𝑡𝑇> 이후에 실행된 트랜잭션에 대하여 Redo 와 Undo 연산만 수행
- 로그에 <𝑇𝑖,𝑐𝑜𝑚𝑚𝑖𝑡> 또는 <𝑇𝑖,𝑎𝑏𝑜𝑟𝑡>가 없는 𝐿𝑖𝑠𝑡𝑇안의 모든 트랜잭션을 Undo
- 로그에 <𝑇𝑖,𝑐𝑜𝑚𝑚𝑖𝑡> 또는 <𝑇𝑖,𝑎𝑏𝑜𝑟𝑡>가 있는 𝐿𝑖𝑠𝑡𝑇안의 모든 트랜잭션을 Redo

---

문제 22번

checkpoint 로그 레코드의 ListT의 값으로 올바른 것은?  [14강]

 

① {T0, T1, T2, T3}
② {T0, T1, T2}

③ {T3}
④ {T0, T1}

---

checkpoint ListT에는 체크 포인트 발생 시점에서 실행 중이던 트랜잭션이 포함됨. → T0, T1

---

문제 23번

위 로그를 통해 Redo를 수행해야 하는 트랜잭션은?  [14강]

 

① T2
② T1

③ T0, T1
④ T0, T1, T3

---

과거
<T0, start>
<T0, B, 3000, 5000>
<T1, start>
<checkpoint ListT>	Undo list = {T0, T1}
<T1, C, 1000, 900>
<T1, commit>	T1을 Undo list에서 제거 → T1을 Redo Undo list = {T0}
<T2, start>	T2을 Undo list에 추가  Undo list = {T0, T2}
<T2, A, 300, 500>
<T0, B, 3000>
<T0, abort>	T0을 Undo list에서 제거 → T0을 Redo Undo list = {T2}
현재