Chap. 11  Storage and File Structure

*Textbook: Chapter 10(6판), Chapter 12,13(7판)

Data Structures for DBMS

① Data files: store the data.

- Heap file

- Sequential file: Sequential accessing in search key order.

- Relative file: Direct accessing by hashing.

hashing (저장 주소를 함수로 직접 계산)

- Cluster: Intra- or Inter-file clustering by an clustering attribute.

② Indices: provide for fast access to data items.

ex) indexing (such as books, libraries and buildings): indexed file

⇒ Heap/Sequential/Cluster + indices

③ Data dictionary (= System catalog): store info about the structure of the DB.

⇒ DB 구조를 관리하기 위한 것.

- Names of the relations

- Names of the attributes of each relation

- Domains (types) of attributes of each relation

- Names of views defined on the relations

- Integrity constraints for each relation

- Names of authorized users

- Info. about users (Authorization of DB, table, view 등)

④ Statistical data: store info about the statistical data in the DB.

- no. of tuples in each relation

- no. of accesses for each relation

⑤ Log file: relation의 변동상황들(insertion, deletion, update)을 저장.

⇒ for recovery when a system crash happens.

▪ Layering architecture of system S/W

- System S/W의 구조: 상위 layer는 하위 layer의 service를 사용해야만 함.

ex)

사용자

OS		DBMS		N/W S/W
command		DB manager		application
system call		file manager		transport
process & file control		disk manager		network
H/W control (driver routine)		disk controller		data link

H/W

- Why?

Abstraction: Independent from the underlying architecture.

보안성: 사용자로부터 system을 보호

확장성: 새로운 기술을 도입시 해당 layer만 교체.

- Abstraction

DB manager

⇒ regards the disk as a logical collection of "files" & provides "tables"

file manager

disk manager

⇒ regards the disk as a logical collection of "page sets" & provides "files"

a  b  c

c  d

x  y  z

⇒ regards the disk as a logical collection of "cylinders, tracks and sectors" & provides "page sets"

create table M ( … );

create table N ( … );

select * from M;

c:\mydb\m

A	B	C		C	D
a x	b y	c z		c	d

a	b	c
c	d
x	y	z

Disk Controller

r1	a	b	c
r2	c	d
r3	x	y	z

A	B	C		C	D
a x	b y	c z		c	d

B	C	D
b y	c z	d d

DBMS - views 제공

DBMS - tables 제공

file manager

conceptual level - DBA가 관리

physical level - 물리적 구조

view level - user, programmer의 관점

물리적 독립성

논리적 독립성

Disk System

▪ 자기를 이용: 알루미늄 판 위에 자성에 민감한 감마산화철(γ-Fe3O3)이라는 자성 물질을 입힘.

▪ History

- IBM 350 RAMAC (Random Access Method of Accounting and Control): 1955

- IBM 3340 disk unit (일명 Winchester): 1973

․1,700K bit/inch 저장.

18/1,000K inch

- Now for PC, 2GB/disk → 8GB/4 disks

5400, 7200, 10000

RPM(revolutions/min.)

- 구조/질서

원자 ⇒ 분자 ⇒ 세포 ⇒ 개체 ⇒ 사회 ⇒ World	; by God

비트 ⇒ Sector ⇒ Track ⇒ Cylinder ⇒ 파일 ⇒ 데이터베이스 ⇒ Web ; by Human

▪ Structure

- Cylinder: R/W head의 움직임이 없이 접근할 수 있는 다른 표면상의 모든 track들의 집합. ⇒ 가능한한 하나의 file은 한 cylinder내에 저장.

Track: 수백개/면.

Sector: 입출력 단위.

- Access: cylinder → track → sector

access time =   seek time	; 해당 cylinder까지 arm이 움직인 시간.

+ latency time	; 지정된 sector까지 disk가 회전하는 시간.

+ transfer time	; 실제적인 정보를 출력하는 시간.

Which one is the biggest & Why?

- 평균 검색시간: 13.3 ms (4500 RPM)

11 ms  (5400 RPM)

평균 전송속도: 16MB/sec (fast ATA 방식)

32MB/sec (ultra ATA 방식) ⇒ SCSI보다 빠름.

- Disk scheduling : How to reduce the seek time?

① FCFS(First Come First Serve): fair, but 이동 거리가 너무 길다.

② SSTF(Shortest Seek Time First): 현재 head 위치에서 가까운 요구부터 먼저 처리. ⇒ 이동거리 최소, but starvation.

③ SCAN: disk의 한쪽 끝과 다른 쪽 끝 사이를 계속 왕복.

⇒ 엘리베이터 알고리즘.

ex) queue: 53, 98, 183, 37, 122, 14, 124, 65, 67

0	14	37	53   65 67	98	122 124	183	199

▪ RAID (Redundant Arrays of Inexpensive Disks)

- Using a large no. of "cheap" small disks may be more cost-effective than is using a smaller no. of expensive large disks.

- If the disks are operated in "parallel",

․ The R/W rate can be improved.

․ Improve the "reliability" of data by using the “redundancy” of data.

disk

disk

disk

disk

disk

disk

disk

disk

disk

channel

channel

channel

disk

controller

- 데이터의 중복(redundancy) 정도에 따라

⇒ RAID 0 ～ RAID 6 (p.409, Fig.11-4)

Ex) RAID 0: Block 단위로 분산 저장.

RAID 1: Block을 mirroring하여 중복 저장.

Disk Controller

․ OS와 디스크 드라이브의 H/W를 연결.

․ Sector를 읽고 쓰기 위한 고수준의 명령어를 수용해서, 디스크 암을 정확한 track에 이동시켜서 해당 데이터를 읽고 쓰는 작업을 수행함.

Disk Manager

▪ Page set

- A collection of fixed sized pages

- Each page set is identified by a unique page set ID.

Each page is identified by a page no. that is unique withing the disk.

page set #1

page set #2

page: the unit of I/O in OS and DBMS.(typically 512～4096 bytes)

(≠ block - a group of pages)

▪ The operations supported by the disk manager

- create a new page set t.

- remove a page set t.

- add a new page to page set t.

- remove a page p from page set t.

- retrieve a page p from page set t.

- update a page p within page set t.

File Manager

▪ Page set을 file로 mapping하여 줌.

⇒ Each file is identified by a file name of file ID.

Each record is identified by a record no. or record ID.

▪ The operations supported by the file manager

- create a new file f.

- remove a file f.

- add a new record to file f.

- remove a record r from file f.

- retrieve a record r from file f.

- update a record r within file f.

▪ Many large-scale DBMSs:

- Do NOT rely on "directly" on the underlying OS for file management.

⇒ Instead, 'large' OS files are allocated to each DB.

- Tables are stored in these files.

- The management of these files is left to the DBMS.

(ex) MySQL의 경우

- 하나의 테이블이 하나의 file에 저장됨.

File	Purpose
tbl_name.frm	table definition file
tbl_name.myd	data file
tbl_name.myi	index file

(ex) Oracle의 경우

- Tablespace에 파일들이 할당.

- 하나의 file은 각각의 segment로 나누어져 있고, 하나의 segment에 하나의 table, 혹은 index가 저장되어 있음. (data segment, 혹은 index segment)

-  page set → segment, block → extent, page → block로 각각 불리움.

- 각각의 extent는 연속된 block의 묶음으로 구성.

Database

System Tablespace

Data Tablespace

DDBFile1

DBFile1

DBFile2

Table

Index

Cluster

Cluster

Index

Index

Table

Index

Index

Table

File

Table

Table

Index

Files Allocated by OS

Segment

각 User가 사용할 수 있는 테이블들의 저장소

CREATE TABLE employee ( … … )

STORAGE (INITIAL	84K  NEXT 28K

MAXEXTENTS 10)

⇒ 처음에 84K, 필요시 28K씩 할당함.

Block size = 2K

- CRATE DATABASE에서 block size 결정.

- Multiple of OS's block size.

2K	…				2K	…
2K					…
…
Extent 84K					Extent 28K

Segment = 112K

▪ How to store records in a File (or Segment): File의 구조에 따른 분류

① Heap File: Any record can be placed "anywhere" in the file where there is space for that record.

⇒ There is NO ordering of records.

② Sequential File: Records are stored in "sequential" order, based on the value of the "search key".

⇒ Usually, in primary key order.

③ Hashing File: A ‘hash function’ is computed on the search key.

⇒ The result of the hash function specifies in "which page" of the file the record should be placed.

④ Clustering File: Records of several 'different' tables can be stored in the same file.

⇒ "Related records" of the different tables are stored on the "same" page.

1) Heap File

- 페이지 내의 레코드가 정렬되지 않은 파일 구조.

- 구조: 페이지 디렉토리(page directory)를 사용

⇒ 디렉토리의 각 엔트리는 히프 파일에 속한 페이지를 가리킴.

데이터

Page

데이터

Page

데이터

Page

헤더 page

자	유	공	간

- 자유공간(free space) 관리 방법

① 엔트리당 ‘1비트’씩 두어서 해당 페이지에 자유공간의 유/무를 표시.

② 엔트리당 ‘계수’를 두어서 해당 페이지에 자유공간의 양을 표시.

2) Sequential File

- A file is simply a sequential collection of records.

⇒ It is always possible to access all of the records in a file sequentially.

⇒ NO "random" access to a record.

- The physical sequence for any given file is usually "primary key" sequence.

⇒ In practice, there is a good reason for physically sequencing a give file in some "other" manner, e.g., by the values of some other attribute.

- Access to a file in physical sequence is possible even if multiple files share the same page set. (i.e., if the files are interleaved - inter-file clustering)

- Page Allocation

ex)	We have 3 files - Supplier, Parts, Partsupply.

Suppose that each record requires an entire page

Supplier				Parts					Partsupply
S#	SNAME	CITY		P#	PNAME	WEIGHT	CITY		S#	P#	QTY
S1 S2 S3 S4 S5	Smith Jones Blake Clark Adams	London Paris Paris London Athens		P1 P2 P3 P4 P5 P6	Nut Bolt Screw Screw Cam Cog	12 17 17 14 12 19	London Paris Rome London Paris London		S1 S1 S1 S1 S1 S1 S2 S2 S3 S4 S4 S4	P1 P2 P3 P4 P5 P6 P1 P2 P2 P2 P4 P5	300 200 400 200 100 100 300 400 200 200 300 400

① Initially, only one page set, the free space page set. After the creation of 3 page sets for each file, there are 4 sets. (Supplier, Parts, Shipments, Free)

									0				1			2	2			3	3			4	4			5	5			×
page set				address of the first page
														s1				s2				s3				s4				s5
free space suppliers parts shipments				24 1 6 12
									6			7	7			8	8			9	9			10	10			11	11			×
										p1				p2				p3				p4				p5				p6
									12			13	13			14
										s1	p1			s2	p2			…				…				…				…
									18																				23			×
										…				…				…				…				…				s4	p5
									24			25

② Insert S6, Delete S2, Insert P7, Delete S4

⇒ After the system has been running for a while, it can no longer be guaranteed that pages that are logically adjacent are still physically adjacent.

⇒ The logical sequence of pages must be represented NOT by physical adjacency but by pointers.

Ex) p.428 Fig.11-15, Mobile phone의 경우 (전화번호부)

- It is desirable to have pages that are logically adjacent physically adjacent also as far as possible.

⇒ The disk manager normally allocates and deallocates to and from page sets is 'physically contiguous groups' of (say) 64 at a time.

⇒ 불연속할당 기법

① sector 단위 할당: 필요할 때마다 sector 단위로 할당.

- fragmentation problem

② block 단위 할당: 필요할 때마다 block 단위로 할당.

- 일반적으로 disk의 한 track 전체를 하나의 block으로 정함.

(≠ 연속할당 기법: 미리 file size 만큼의 연속된 page들을 할당.)

- Record management

① Case 1: "Chain" the records together by pointers in search key order.

(ex) p.320 fig.10-15, fig.10-16. (p.231 fig.7-15, fig.7-16 in 2nd ed.)

② Case 2: If insertions rarely occur, it is possible always keep the file in "physically" sorted order.

(ex) Suppose a single page can accomodate multiple records.

① Initially,

P#	Header		Pointer
s1		s2
s3		s4
s5

② Inserts s9.

Deletes s2 & shifts s3, s4, s5, s9.

Insert s7 & shifts s9.

- Record ID

RID for r			001	Header				pointer
001	4
page no. offset from the foot of page.			record r
						4	3	2	1	0
						300

the byte offset of r from the top of page

- Indirect addressing: Records can be shifted up and down within the page without having to change RID.

⇒ Only offset have to be changed.

- DBMS에서는 일반적으로 heap file을 사용

⇒ sequential file은 순서를 유지하기 위한 overhead가 크기 때문.

ex) Oracle 테이블의 경우

- Heap file: tuple 입력 순서로 저장

≠ Sequential file

- Sequential access시 index를 사용.

- 또한, "Clustered" tables 기능을 제공.

․ Optional method for storing data

․ "One" or "more" tables physically stored together.

⇒ Intra-file/Inter-file clustering

3) Clustering File

- A performance objective in DBMS is to minimize the no. of disk accesses.

⇒ Try to store records that are logically related (and are therefore frequently used together) physically close together on the disk.

⇒ Physical data clustering is extremely important factor in performance.

- Suppose the record most recently accessed is r1 stored or p1,

and the next record required is r2 stored on page p2.

① Case 1: If p1 and p2 are one and the same, the access to r2 will not require any physical I/O at all.

← The desired page p2 is already in a buffer in main memory.

② Case 2: If p1 and p2 are distinct, but in the same cylinder, the seek time will be  zero.

→ small access time

③ Case 3: If p1 and p2 are distinct, and in the different cylinder, the seek time will be big.

- Clustering is 'application dependent'

ex)

supplier
s#	sname	city
s1 s2 s3 s4 s5

parts
p#	pname	weight
p1 p2 p3 p4

shipments
s#	p#	qty
s1 s2 s3 s4 s5 s5	p1 p2 p1 p2 p4 p5

① Case 1: If sequential access to all suppliers in s# order is a frequent application requirement, the 'supplier' records should be clustered;

⇒ 'intra-file' clustering.  ('sequential' file)

② Case 2: If access to some specific supplier together with all shipments for that supplier is a frequent application requirement, then the 'supplier AND shipment' records should be stored interleaved;

⇒'inter-file' clustering.

- A good DBMS should allow the DBA to specify different kinds of clustering for different files.

ex) Inter-file clustering

p.430 Fig.11-17, Fig.11-18

▪ File의 기능에 따른 분류

- Master file

․ 어느 한 시점에서 조직체에 관한 정적인 면을 나타내는 data의 집합.

․ 급여 file, 재고 file, 인사 file 등.

․ 얼마나 최신 상태를 잘 유지하고, 관련 상태의 변화를 얼마나 잘 수용하느냐에 따라 현실 세계의 어떤 상황에 대한 정확한 일면을 보여줌.

- Transaction file

․ master file의 내용을 변경시킬 transaction의 집합.

․ transaction은 master file에 새로운 record를 추가하거나 현존하는 record를 수정 혹은 삭제하기 위한 자료를 말함.

․ 입출금 file, 입출고 file, 인사이동 file 등 경영활동에 의해 시시각각 발생하는 data에 대한 file임.

- Temporary file

․ 필요에 따라 임시로 만들어서 사용하는 file.

․ 주로 복잡한 data 처리에서 어떤 작업 결과를 임시로 file에 담고, 다음 단계에서 이를 사용하여 다음 작업을 하는 경우에 사용.

․ temporary file을 잘 사용하면 program이 간단해지고, 또 system down이나 file의 파괴시 복구(recovery)를 용이하게 할 수 있음.