[DB개념] :: Representing Data Elements (데이터 엘리먼트의 표현)

Representing Data Elements

Relation의 Object들은 Secondary Storage(보조기억장치)에 나타나게 된다. 
이러한 Object들의 종류와 관리 및 표현 방법에 대해 알아보자.

Data Elements

RDM이나 OODM에서 등장하는 값들과 같은 가장 기본적인 Data Element(s)를 표현하기 위해 
Field를 사용하며, 더 나아가 레코드(Records), 블록(Blocks), 파일(Files)과 같은 저장 시스템의 
더 큰 요소를 형성하기 위해 어떻게 합쳐지고 조합하는 지 알아보자.

Field, Record, Block, and File

• Field
  고정 길이(fixed-length) 또는 가변 길이(variable-length)의 순차적 바이트로, 
  Column을 표현할 때 사용한다. 
  

• Record
  이러한 Field들이 모여 Tuple, Object 들을 형성하는데, 이를 'Record'로 표현한다.
  레코드는 물리적 Block에 저장되어야 하며, modified될 때 'Various Data Structure(가변 데이터 구조)'가 유용하다.
  

• Block
  Relation, 또는 클래스의 범위(extent of a class)를 형성하는 레코드의 모임을 말한다. 
  

• File
  이러한 Block의 모임을 File이라 한다.
  효율적인 querying과 modification을 위해 file에 'Index'를 부여한다.
  

Representing Relational Database Elements

DBMS는 CREATE TABLE 선언에 의해 묘사되는 Relation을 표현하고 저장하는 일을 한다.
Tuple(s)는 C나 C++의 구조체(struct)와 비슷한데, 각 Tuple들은 레코드로써 디스크에 저장된다고 할 수 있다.
기본 Idea는 간단하지만, Detail은 매우 험난하다. (devil is in the details)
앞으로 살펴볼 항목들은,

1. SQL Data type을 필드로 표현하는 방법
2. Tuple을 레코드로 표현하는 방법
3. Memory's block에서 레코드/튜플의 집합을 표현하는 방법
4. 서로 다른 튜플, 혹은 블록의 크기를 균등하게 나누지 않은 레코드의 size에 대해 관리하는 방법
5. Record's Modification

더 나아가, 근래의 Object-relational/Object-oriented system, BLOBS(binary, large objects)에 출현하는
몇몇의 특별한 Data를 표현하는 방법도 살펴보자.

Representing Objects 

Object는 Tuple이라 할 수 있고, 이 Object의 Field는 Column이다.
이 때, 두 가지 중요 사항

1. Object는 Object끼리 관련된 Method나 Special-purpose functions를 가질 수 있다.
   
2. Object identifier (OID)라는, 해당 object를 unique하게 해주는 전역 주소값을 가질 수 있다.
   또한 object끼리 relationship을 가질 수 있고, 이는 pointer로 표현할 수 있다.

'Methods'는 일반적으로 schema와 함께 저장되며, 
액세스하려면 레코드에 Object의 클래스를 나타내는 Field가 있어야 한다.
또한 OID를 이용하거나, 다른 Object를 참조하여 표현할 수도 있다.

Representing Data Elements

레코드의 필드로 SQL의 Data type들이 어떻게 표현되는지 고려해보자. 
우선 기본적으로, 모든 data는 바이트의 나열(sequence of bytes)로 표현된다. ( 예 : INT = 2 or 4 bytes)

Fixed-Length Character Strings (고정 길이의 문자열)

• CHAR(n) : 입력 Data의 바이트 값이 n보다 작을경우 나머지를 특수 pad문자(⊥)로 채운다.

Variable-Length Character Strings (가변 길이의 문자열)

• VARCHAR(n) : 글자수에 상관없이 항상 n+1 bytes가 사용된다.
  -> SQL의 VARCHAR(n)는 실제론 길이가 가변적이지만, 고정 길이의 필드를 표현한다.
  VARCHAR strings의 표현 두가지
  1. Length plus content
     • n + 1 bytes의 array를 할당한다.
     • 첫 1byte는 8bit의 정수값으로, 문자열의 바이트 수를 나타낸다.
     • 문자열은 n 개를 초과할 수 없으며, n 자체는 255 개를 넘을 수 없다. (넘으면 길이를 단일 바이트로 나타낼 수 없다)
     • 최대길이보다 작아 사용되지 않는 array의 byte는 무시된다.
     • 이 무시되는 byte(들)은, 첫 byte가 언제 끝나는지 알려주므로 값의 일부로 해석하지 않는다.
  2. Null-terminated string
     • n + 1 bytes의 array를 할당한다.
     • Fill this array
     • 그 뒤에는 null 문자가 온다.
     • 1번 방법은, 사용되지 않는 위치는 값의 일부로 해석하지 않는다고 했지만, 이 방법은 null 뒤는 보지 않는다.

• Dates and Times
  DATE는 자주 쓰이는 고정 길이 문자열로써, 다른 어떠한 고정 길이 문자열로 표현할 수 있다.
  TIME은, 일반적으로 한계치를 두어 varchar(n)으로 표현하기도 하고, 또 가변 길이 값으로 다룰 수도 있다.

• Bits
  BIT(n) : 8bit로 byte를 표현한다.
  만약 n이 8로 나누어 떨어지지 않으면, 마지막 1byte의 나머지를 0으로 채운다.
  특별하게 11111111은 true, 00000000은 false인 boolean값을 표현하기도 한다.

• Enumerated Types
  가끔 Column값이 적은 값들의 집합 내에 있어야 하는 경우에 쓴다.
  {SUN, MON, TUE, WED, THU, FRI, SAT} 등

Packing Fields Into a Single Byte

적은 양의 데이터일 경우, 1byte에 다 묶어버리는 건 어떨까?
boolean, day, color라고 하면, 1bit - 3bit - 2bit 심지어 2bit가 남는다.
이렇게 하는 데 문제는 없지만, 검색/삽입 시 에러가 발생하기 쉽다.
저장 공간이 매우 expensive할 경우에만 고려되는 방법이자, 일반적으로는 사용하지 않는다.

Records

필드들이 모여 레코드를 이룬다고 했는데, 어떻게 모이는 지를 알아보자. 
일반적으로, 각 타입의 레코드들은 DB에 의해 저장된 'schema'를 보유하고 있는데, 
이 Schema는 레코드 내의 'name of the field', 'data type', 'offset'을 포함한다.
레코드 내에서의 중요한 access 시 schema를 찾는다. 

Fixed-Length Records

Relation 선언 시 필드들이 생기고, 튜플은 정렬된 필드를 포함하는 레코드에 의해 표현된다. 
레코드의 필드가 전부 고정 길이일 때를 먼저 살펴보자.

CREATE  TABLE  MovieStar (
name  CHAR(30)  PRIMARY KEY,
address  VARCHAR(255),
gender  CHAR(1),
birthdate  DATE
);

몇몇의 Machines은 Reading / Writing의 효율을 위해 4의 배수를 사용한다. (64-bit processor면 8)
즉,

이렇게 하면, 블록 내 레코드와, 모든 필드들은 4 의 배수지점에서 시작한다는 장점이 있다.

Record Headers

레코드 설계에 있어 Header에 대해 언급을 하지 않을 수 없다.
레코드가 분명히 가지고 있어야 하지만, 필드의 값은 아닌 정보가 종종 있는데,

1. 해당 레코드의 스키마 ( 혹은 그 스키마를 저장하는 장소에 대한 포인터 )
2. 해당 레코드의 길이
3. 가장 최근 modified/read 시간을 나타내는 Timestamps

등등이 이 레코드 헤더에 존재한다. 
즉, 레코드는 앞서 언급한 부가 정보들을 제공하기 위한, 소량 byte의 'Header'를 포함한다.

DB System은 CREATE TABLE 때 등장하는 Schema Information을 Header에 유지하는데,
이 Schema Information이란

1. Columns
2. Their types
3. Tuple에 등장하는 Columns 순서
4. Constraints (PK, 값의 범위 등)

하지만, 이 모든 정보를 모두 헤더에 담을 순 없다.
그 튜플의 Relation에 대한 정보가 저장되어 있는 곳을 가리키는 포인터면 충분하다.
이렇게 해두면 언제든지 이 모든 정보를 필요할 때마다 얻을 수 있다.
또한, 레코드의 길이를 자신이 알고 있는 게 편리 할 때도 있다.
레코드 값으로 무언가를 하려기 보단, 다음 레코드의 시작점만 알고 싶을 때도 있으니 말이다.

 

Packing Fixed-Length Records into Blocks

Records는 Disk의 'Block'에 저장되고,
access나 update 가 필요할 때 Main Memory로 옮겨진다. 
이러한 'Block' 역시 header가 있는데, 이 header에는

1. 'Block Network' 내 다른 blocks들에 대한 Link.
2. Network 내에서 이 Block의 역할 (Role)
3. 이 block의 Relation에 대한 정보
4. Block내 레코드의 offset을 제공하는 'Directory'
5. Block ID
6. 최근 modification/access를 나타내는 Timestamps

 

Representing Block and Record Addresses

레코드의 복잡한 구조를 학습하기 전,
'주소', 포인터(혹은 참조하는 다른 레코드와 블록) 등 여러가지를 고려해야 한다.

Client-Server Systems

일반적으로, Database는 'Server process', 'Client process' 두 가지를 포함한다.

• 'Server process' : 보조 기억장치(secondary storage)의 data를 하나 이상의 client process에게 제공한다.
• 'Client process' : data를 사용하는 Applications로, server process에게서 data를 받는다.

서버와 클라이언트 프로세스는 한 개의 machine에 있을 수도 있고, 서버와 다양한 클라이언트가 많은 machines에 분포되어 있을 수도 있다.

클라이언트는 관례적으로 32비트의 'Virtual'한 address space 를 사용한다.

OS나 DBMS는 주소 공간의 어느 부분이 현재 Main memory에 위치하는지 결정하고,
virtual address space를 Main memory의 물리적 위치로 맵핑시킨다.
어떻게 맵핑하는지 보다는 일단 클라이언트 주소공간이 메인메모리 그 자체인 경우를 살펴보자.

서버의 데이터는 'Database address space' 에 있다.
이 공간의 주소는 block을 참조하고, 가능하다면 block내의 offset을 참조한다.
이러한 주소를 표기하는 방법은

1. Physical Addresses

• 블록이나 레코드가 있는 보조 기억장치 시스템 내의 장소를 결정하는 Byte strings (실제 주소).
• 이러한 Byte strings는 각각
  1. 저장소가 연결된 'Host' (DB가 1개 이상의 machine에 걸쳐 존재할 때)
  2. 블록이 위치한 디스크/기타 장비들에 대한 'Identifier'
  3. 디스크의 cylinder 개수
  4. 그 cylinder 내의 track 개수 (디스크가 하나 이상의 surface를 가질 때)
  5. 그 track 내의 블록 개수
  6. 블록 내 레코드의 시작점 'offset' (일부의 경우)

2. Logical Addresses

• 고정 길이의 임의 문자열
• 디스크에 저장되는 'Map table'은, 이 logical to physical addresses와 관련있다.

Logical and Structured Addresses

왜 굳이 Logical Address를 두는걸까?

Physical address로의 필요한 모든 정보는 Map table에 있다.
또한, 레코드의 논리 포인터도 맵 테이블을 참조한 뒤에야 물리적 주소로 이동한다.

그러나, Map table의 간접적인 참조는 상당한 유연성을 제공한다.
예를 들어, 데이터들은 블록 내에서, 또는 블록에서 블록으로 레코드를 이동해야 하는데,
이 때 맵 테이블을 사용하면 레코드에 대한 모든 포인터가 이 맵 테이블을 참조하는데,
레코드를 이동/삭제시 맵 테이블의 레코드에 대한 항목을 변경하기만 하면 되기 때문이다.

또한, Physical address는 필수 요소만을 나타내는 데 8 bytes나 사용한다. (system에 따라 16 bytes도 있다.)
-> 즉, 너무 길다.

logical/physical 주소의 수많은 조합(Combination)도 가능하며, 'structured' 주소 체계를 만들 수 있다.
예를 들면, 물리 주소를 사용하고 싶어, 레코드에 키 값을 추가해 그것을 참조하게 해놓으면,
이러한 구조화된 주소체계에서 원하는 레코드를 포함하는 블록을 찾을 때 특정 키값만 보면 쉽게 찾을 수 있다.

비슷하게, 이 논리/물리 주소의 조합은 레코드들의 offset 정보를 담고 있는, 
'Offset table' 도 블록 내에 유지시킬 수 있다.

• 블록의 끝부분에서 시작하여 레코드가 배치되기 때문에, 테이블이 블록의 앞쪽 끝에서 커지는 걸 알 수 있다.
  레코드가 모두 다른 길이일 때 매우 유용하다. 
  이 때, 우린 블록이 몇 개의 레코드를 보유하는지 미리 알지 못하고, 고정된 블록 헤더를 초기 테이블에 할당할 필요가 없기 때문이다.
  

 

레코드의 주소 = 블록의 Physical address + OFFSET (해당 레코드에 대한 블록의 offset table을 보고 )
이러한 block 내의 level of indirection은 전체 맵 테이블을 보는것 없이 논리 주소의 많은 장점을 제공한다.

• Block 내의 레코드 이동 시 offset table 값만 변경해주면 된다. 레코드를 가리키는 포인터로 여전히 찾을 수 있다.
  
• Block 간의 레코드 이동에도 offset table이 레코드의 '보내지는 주소(forwarding address)'를 담을만한 충분한 크기이면 문제없다.
  
• 레코드가 삭제될 경우 'Tombstone' 이라는 special value를 offset table에 두어 삭제됨을 알린다.
  이 때 이 레코드를 가리키는 포인터가 DB 여러 위치에 저장되어 있을 수 있는데, 
  삭제 이후에 따르는 이 포인터는 tombstone을 가리키게 된다.
  이는 널 포인터로 대체되거나 레코드 삭제가 반영된, 수정된 데이터 구조를 가리키게 된다.
  tombstone을 떠나지 않으면 포인터는 새로운 다른 레코드를 가리키거나 잘못된 결과를 가리킬 수도 있다.
  

Pointer Swizzling

포인터나 주소나 둘다 레코드의 일부다.
이제 살펴볼 상황은, '레코드'에서는 좀처럼 볼 수 없는 상황이지만 
객체를 표현하는 '튜플'에 있어서 흔히 일어나는 상황이다.
인덱스 구조는, 보통 포인터를 보유한 블록으로 구성된다. 
그러므로, 블록이 메인 메모리와 보조 기억장치 사이에서 옮겨질 때 포인터를 다루는 방법을 숙지해야한다.
이전에도 언급했듯 모든 블록, 레코드, 객체, 혹은 다른 참조할 수 있는 data item들은 주소에 대해 2가지 형태를 띄고 있다.

1. Database address : 시스템의 보조 기억장치에 item을 배치하는 8 bytes정도의 나열된, 서버의 DB 주소 공간
2. Memory address : virtual memory 상의 주소로, 대개 4 bytes.

보조 기억장치에서 데이터베이스 주소를 사용하는 건 명확하다.
하지만, 메인 메모리에서는 데이터베이스 주소/메모리 주소중 하나를 이용한다.
어떤 item이 포인터를 가지고 있으면 메모리 주소를 두는 것이 효율적이다.
-> 이 포인터들은 단일 기계 명령어를 이용하여 간단하게 추적할 수 있기 때문! 

반면, 데이터베이스 주소는 시간이 오래걸린다.
현재의 가상 메모리 내 모든 데이터베이스주소를 현재의 메모리 주소로 변환하는 테이블이 필요하기 때문이다.
바로, 'Translation table' . map table을 연상시키기도 하지만,

1. 논리/물리 주소들은 데이터베이스 주소 표현법이다. 반면 '변환 테이블'의 메모리 주소는 메모리 상 해당 객체의 복사본이다.
2. 주소를 가질 수 있는 DB item들은 map table에 entry가 있지만, 현재 메모리에 있는 item은 '변환 테이블'에서 언급된다.

 

데이터베이스 주소를 메모리 주소로 변환하는 비용의 반복을 피하기 위해, Pointer Swizzling이라는 기술을 사용한다.
보조기억장치에서 메인메모리로의 블록 이동을 할 때, 블록 내의 포인터는 'swizzled'된다.
그 말은, 데이터베이스 주소 공간(물리적 공간)에서 Virtual address space(가상 공간)으로의 변환을 말한다.
포인터가 포함해야 할 두 가지

1. 포인터가 현재 '데이터베이스 주소'인지 '(swizzled)메모리 주소'인지 구별하는 bit
2. DB/Memory pointer 지금 어느 형태건 같은 공간을 사용한다.

Returning Blocks to Disk

블록이 메모리에서 디스크로 다시 되돌아 올 때, 포인터는 'unswizzled'되어야 한다.
즉, 이들의 메모리주소는 데이터베이스 주소와 같게 다시 변경해야 한다.
변환 테이블을 이용해 두 유형의 주소를 연결할 수 있으므로 
일반적으로 메모리 주소가 주어지면 그 주소가 할당된 데이터베이스 주소를 알아낼 수 있다.

Pinned Records and Blocks

Pinned : 메모리의 블록이 그 순간에 disk로 안전하게 다시 기록할 수 없을 때를 일컫는다.

• 블록의 헤더에 pinned상태인지 아닌지를 나타내는 bit가 있다.
  
• pinned되는 이유는 여러 가지가 있다 ( pointer swizzling도 중요 요소 중 하나).
  

Variable-Length Data and Records

이러한 간단한 고정 길이의 레코드 말고, 좀 더 복잡한 것을 알아보자.

1. Data items whose size varies : 실제 필요한 공간만큼만 사용한다면 공간을 아낄 수 있다.
2. Repeating fields : 아주 방대하게 많은 관계를 표현하고자 할 때
3. Variable-format records : 가변 형식 레코드
4. Enormous fields : 자료가 지나치게 거대할 때

1. Records With Variable-Length Fields

가변 길이의 '필드' 들은 레코드가 필드를 찾기 충분한 정보를 가지고 있어야 한다.
간단하고 효과적인 스키마 방법은 가변 길이의 필드에 고정 길이의 헤더를 두는 것이다.
이 헤더에 위치시킬 것들은

1. 레코드의 길이
2. 모든 가변 길이의 필드 시작점을 가리키는 포인터를 두는 것.

2. Records With Repeating Fields (반복필드)

레코드에 필드 F가 여러번 등장하지만, 필드 자체는 고정 길이인 경우엔 어떻게 처리할까.
이 때엔 필드 F의 모든 발생을 다같이 그룹화 시키고, 레코드 헤더에 첫 번째 필드 F에 대한 포인터를 두면 된다. 

필드 F의 한 인스턴스에만 사용되는 바이트 수가 L이라면, 
L, 2L, 3L, ... 몇 번째 F든지 offset에 도달할 수 있다. 

3. Variable-Format Records

더 복잡한 경우도 발생한다.
필드의 순서들이 릴레이션이나 클래스에 의해 결정되지 않을 때.
이럴땐 'tagged fields' 를 나열하여 간접적으로 표현하는데, 이 태그 필드에는

1. 필드의 역할 정보
   1. 필드 이름
   2. 필드 타입
   3. 필드 길이
2. 필드의 값

태그필드를 두는 이유

1. 정보의 무결성 : 수많은 릴레이션들에 의해 들어온 값은 null 값이 많을 수밖에 없다.
   -> 이럴 때 태그하고 리스트하여 null이 아닌값으로 필드를 채우는 것이다.
   
2. 유연한 스키마 : 지나치게 방대한 양을 담기보다는 태그해서 담아 유연하게 만든다.
   

 

4. Enormous fields

지나치게 거대한 값들을 블록이 전부 다 담지 못할 때도 있다. (예 : 비디오나 오디오 'clip')
이런 경우 이 거대한 값은 가변 길이인데(고정 길이일 수도 있지만), 이러한 값들에 대해서는 특별한 방법을 사용해야 한다.

기본 아이디어는 레코드를 split하는 것으로, 
한 블록에 나타나는 레코드의 부분을 'record fragment' 
이 fragment가 여러 개 있는 레코드를 'spanned' 라 한다. (한 블록의 바운더리를 넘지 않으면 unspanned)
레코드가 스팬되면, 모든 레코드와 프래그먼트는 별도의 헤더 정보가 필요하다.

1. 각 헤더는 프래그먼트인지 아닌지를 구별하는 bit가 필요하다.
2. 프래그먼트라면 이게 레코드의 몇 번째 프래그먼트인지를 알 수 있는 bits가 필요하다.
3. 다음/이전 프래그먼트가 존재하면, 다른 프래그먼트를 가리키는 포인터가 필요하다.

 

BLOBS

정말로 더더욱 엄청나게 거대한 레코드에 대한 표현은 어떠할까.
이미지 (GIF, JPEG), 동영상(MPEG)가 대표적인 사례이다.
이러한 값들을 BLOBS(binary, large objects)라 한다.
필드가 이러한 BLOB를 가지고 있다면, 두 가지 이슈 가 존재하는데,

1. Storage of BLOBS
   • 블록의 나열로 저장하며, 'stripe'하여 여러 개의 disk에 저장한다. (블록을 링크드 리스트로도 구현할 수 있다)

2. Retrieval of BLOBS
   • 한 개의 디스크에 저장하면, 검색 속도가 상당히 느리다.
     
   • client가 만약 2시간짜리 영화를 재생한다면(검색한다면) 재생하는 데 필요한 속도 이상으로 빨라야 할 필요가 있다.

Record Modifications

레코드의 modification은 Special problem이 발생한다.
고정 길이의 필드와 레코드임에도 길이가 변경될 수 있는데, 이 때 심각한 문제가 발생할 수 있다.

Insertion

블록으로의 레코드 삽입에 있어, 
각 레코드들을 헤더에서 포인터로 알고 있기에 (offset도)
Room (빈 공간(unused))을 알 수 있다.

1. room이 새로운 레코드를 담기에 충분한 경우,
   room을 찾아 새로운 레코드를 채워 넣고, 그 레코드의 시작점을 가리키는 포인터를 두면 삽입이 완료된다.
   

2. room이 없거나 새로운 레코드를 담지 못할 때 두 가지 방법
   
   • Find space on a 'nearby' block
     
     • B1에는 공간이 없고, 옆의 B2에 공간이 있을 경우 B1의 highest 레코드를 B2로 옮기고,
       새로운 레코드를 B1에 삽입한다. 이 때, 'forwarding address' 를 offset table에 잘 남겨야 한다.
       앞서 말했듯, 이 보내지는 주소를 담을 수 있을 만큼 offset table의 공간은 충분해야 한다.
       
   • Create an overflow block
     
     • overflow block을 생성하여 그 안에 새로운 레코드를 넣고, 원래 블록의 헤더에서 이 overflow block을 가리킨다.
     • 편리하지만, 공간적 손해를 본다.

Deletion

레코드를 삭제하면, 공간을 재반환하여 또 사용할 수 있다.
즉, 사용 가능한 공간이 늘어나고, 남은 레코드들을 
정렬(빈공간이 가운데라면 나머지 왼쪽 레코드들을 오른쪽으로 밀어준다)하여
빈 부분(사용하지 않는 블록의 여분)은 항상 한 개로 유지한다. 
또한, 총 사용공간과 남은 공간을 고려하여 앞서 만들었던 overflow block을 없앨 수도 있다.

이 때, 삭제된 레코드를 가리키고 있던 포인터는 offset table에서 tombstone을 가리킨다고 했다.
이 tombstone은 DB 자체가 reconstructed되지 않는 한 영구적으로 존재한다.

각 레코드의 맨앞에 tombstone인지 아닌지를 구별하는 비트 하나를 두어 관리할 수도 있다.
만약 tombstone이라면, 그 다음 바이트들은 읽지 않아도 된다.

 

Update

• 고정 길이의 레코드 update의 경우, 정확히 같은 공간에 수정하기만 하면 되기 때문에 문제는 없다.
  
• 가변 길이의 경우, 삽입/삭제에서 나타난 problems를 모두 겪을 것이다. ( delete & insert 개념으로도 보기 때문 )
  

전보다 길이가 길어지면, 다른 블록을 살펴보거나 overflow 블록을 생성해야 하고 (insert),
짧아지면 그 남는 부분의 공간을 관리해야 한다 (delete).

마침.