JOINs 

Concept

What is 'JOIN'?

• 두 테이블(혹은 view)의 결과 row들을 하나의 결과 row들로 결합하는 과정을 Join이라 한다.
  이 때, 결합하는 과정에서 조건 이 존재할 수 있는데, 이를 'Join 조건' 이라 한다.
• 일반적으로 Join의 처리과정은 Tree 형태로 표현한다.
• Join의 Tree에서, Join의 하위 노드 중 왼쪽 노드를 'Outer node', 오른쪽 노드를 'Inner node'라 한다..

Various Types of Joins

정말 다양한 Join의 종류가 있지만, 

1. Cross Join
2. Inner Join
3. Outer Join
4. Semi Join
5. Anti Join

이 5가지를 먼저 살펴보자.

또한 설명에 사용될 테이블( t1, t2 )

SQL> 

SELECT * FROM t1;

A B
- -
1 a
2 b

2 rows selected.



SQL> 

SELECT * FROM t2;

C D
- -
4 d
5 e

2 rows selected.

들을 예로 들겠다.

1. Cross Join

• Join 조건이 없는 가장 기본적인 Join. Outer node와 Inner node의 모든 row가 결합되어 반환된다.

예 : Cross Join

SQL>

SELECT a, c FROM t1, t2;

A C
- -
1 4
1 5
2 4
2 5

4 rows selected.

2. Inner Join

• Join 조건이 있는 Join. node의 각 row에 대해 조건을 만족하는 row에 대해서만 결합하여 반환한다.
• Join 조건은 column들간의 연산자로 구성되어 있으며, 
  이 때 이 연산자가 등호(=)이면 'Equi-Join'이라 한다.

예 : Inner Join ( Equi-Join )

SQL>

SELECT a, b, c, d
FROM t1, t2
WHERE a + 3 = c;

A B C D
- - - -
1 a 4 d
2 b 5 e

2 rows selected.

예 : Inner Join ( Non-Equi-Join )

SQL>

SELECT a, b, c, d
FROM t1, t2
WHERE a < c;

A B C D
- - - -
1 a 4 d
1 a 5 e
2 b 4 d
2 b 5 e

4 rows selected.

3. Outer Join

• Join 조건을 만족하는 row에 대해 결합하고, 만족하지 않는 row에 대해 NULL 데이터만을 갖는 row와 결합하여 반환한다.
• Left Outer Join, Right Outer Join, Full Outer Join이 있다.
• ( A LEFT OUTER JOIN B ) 와 ( B RIGHT OUTER JOIN A )는 완전 동치이다.
• Join 조건을 where에서가 아닌 'ON'에서 힌트를 준다.

ON vs WHERE 

ON은 말 그대로 JOIN 수행 중 계속 검사하는 Join 조건이지만,
WHERE는 조인이 다 끝난 후의 filtering을 시행한다. 
미세한 차이점 알아두기 !

예 : Left Outer Join

SQL>

SELECT a, b, c
FROM t1 LEFT OUTER JOIN t2
ON a > 1;

A B    C
- - ----
1 a null
2 b    4
2 b    5

3 rows selected.

예 : Full Outer Join

SQL>

SELECT a, b, c
FROM t1 FULL OUTER JOIN t2
ON a > 1
AND c < 5;

   A B       C
---- ---- ----
   1 a    null
   2 b       4
null null    5

3 rows selected.

4. Semi Join

• Join 조건이 존재해야 하며, 부합하는 row들 중 Outer node와의 Join 결과를 반환한다. ( Outer node의 row만 )
• 또, SQL 구문상 직접 기술할 수 없어, 'IN' , 'EXISTS' 등의 ANY형 연산자 로 표현한다.
• Join 조건에 대한 Index가 존재하고, Inner node의 Unique가 보장되면 'Inverted Semi Join'또한 할 수 있다.

예 : Semi Join

SQL>

SELECT a
FROM t1
WHERE a + 3 IN ( SELECT C
                  FROM t2
                  WHERE d = 'd' );

A
-
1

1 row selected.

5. Anti Join

• Join 조건에 부합하지 않는 Outer node의 row들만을 반환한다.
• 반드시 NULL 처리가 필요하다. ( oracle 11 버전부터는 명시하지 않아도 가능 )

예 : Anti Join

SQL>

SELECT a
FROM t1
WHERE a + 3 NOT IN ( SELECT C
                                   FROM t2
                                   WHERE d = 'd' );

A
-
2

1 row selected.

마침.

Index Structures

What is INDEX?

Why do we need it and What is it?

• 다양하고 방대한 블록들에 흩어져 있는 레코드를 표현하기란, 여간 간단한 일이 아니다.
  
• 모든 블록들은, 레코드의 시작과 끝, 그 레코드에 속하는 릴레이션이 무엇인지 알려주는
  '레코드 헤더' 에 대해 많은 정보들을 알고 있어야 한다.
  

'인덱스(Index)' 라는 자료 구조를 통해 원하고자 하는 레코드의 정보를 '빠르게'찾을 수 있다. 
또한 인덱스 자체도 물리적 구조이므로, 인덱스 데이터의 삽입/삭제도 꽤 복잡하다.
이런 인덱스 값을 기반으로 하는 필드를 'Search key(검색 키 혹은 탐색 키)' 라 한다. 
많은 다양한 인덱스의 구조가 있지만, 지금부터 살펴볼 내용은

1. Simple indexes : 정렬되어있는 파일에 대한 간단한 인덱스
2. Secondary indexes : 정렬되어있지 않은 파일에 대한 인덱스
3. B-trees : 가장 널리 쓰이는, 트리 구조 인덱스
4. Hash tables : 비트리와는 다르지만 또한 유용한 인덱스

Keys and More Keys

Key라는 건 더 많은 의미가 있다.
primary key, sort key 등...
Search key는 값이 주어지며, 
인덱스로 tuple의 matching-value를 찾기 위한 Column(s)를 말한다.

primary, sort, search등 Key의 의미가 명확하도록
이러한 표현들을 덧붙인다!

Indexes on Sequential Files

우선, 간단한 상황의 인덱스 구조에 대한 알아보자.
정렬된 파일인 Data file에게, Key-Pointer 쌍을 가지고 있는 Index file이 주어진다.
인덱스 파일 안의 Search key K는, 이 K를 보유한 Data file 레코드를
참조하고있는 포인터와 연관이 있다. 이러한 인덱스들은 기본적으로 두 가지로 구분할 수 있는데,

• Dense Index : Data file의 모든 레코드 항목이 존재하는 인덱스 구조.
• Sparse Index : 몇몇 데이터 레코드들만 표현되는 인덱스 구조. 보통 데이터 파일의 블록당 하나의 항목.

Sequential Files

• Sequential File : 인덱스의 Column(s)에 의해 정렬되는 파일.
  이러한 구조는 Search key가 릴레이션의 PK일 때 특히 유용하다(useful).

시퀀셜 파일에서는, 튜플들이 PK에 의해 정렬되어 있고,
그림과 같이 일반적으로 key를 10 and 20, 즉 10의 배수 상태로 구별한다

Dense Indexes

Dense Index

• Key와 레코드 자체에 대한 포인터만 보유하는 블록의 나열(인덱스).
• 'Dense(:밀집한)'라 불리는 이유는, 데이터파일의 모든 키가 인덱스에서 표현되기 때문이다.
• 덴스 인덱스는 Key들을 그 파일 자체 순서와 동일하게 유지한다.
• 키와 포인터만 보유한 인덱스는, 완전한 레코드보다 훨씬 적은 공간을 차지하기 때문에
  파일 자체보다 훨씬 적은 공간을 소모할 것이다.
• 즉, 인덱스는 데이터 파일을 위한다기보단, 메모리를 위해 설계된 것이다.
• 또한 인덱스를 사용하면, 1회의 Disk I/O 만으로도 주어진 Search key를 이용하여 어떤 레코드던 찾을 수 있다.

• Dense index는 인덱스 블록을 주어진 Search key 값 K로 검색하며, 찾을 경우 그 포인터로 연관된 레코드를 따라간다.
  
• 여.기.서
  K를 찾을 때까지 인덱스의 모든 블록을 탐색해야한다. (평균적으로 절반만큼)
• 성능이 좋아보이지 않지만, 인덱스 기반의 서치는 보기보다 효과가 대단하다.

Why?

1. 인덱스 블록의 수는 대개 데이터 블록의 수보다 비교적 적다.
2. 키값들이 정렬되어 있기 때문에 이진탐색을 할 수 있다. 인덱스에 n개의 블록이 있다면, log2(n)만큼이 소요
3. 인덱스는 메인 메모리 버퍼에 영구 유지될 수 있을 만큼 작다. 
   그렇다면 메인 메모리 액세스만 하면 되기 때문에 expensive한 disk I/O 수행이 필요 없다.

Sparse Indexes

Sparse Index

• Dense index는 모든 키를 가지고 있기에는 비교적 크다.
• 이런 단점을 보완하여 설계한 것이 바로 이 Sparse Index이다.
• 데이터 블록마다 오직 한 개의 Key-pointer 쌍을 보유한다.
• 훨씬 적은 공간을 사용하지만, 주어진 레코드의 key를 찾는데 더 많은 시간이 걸린다.
• 인덱스 블록만 보고, 찾고자하는 K가 존재하는 지 아닌지를 알 수 있는 Dense index와는 달리
  같은 쿼리문으로, Sparse index는 해당 블록에 K가 '있을지도 모르니' disk I/O를 요구한다.
  

• Sparse index는, 주어진 search key 값 K와 작거나 같은 값 중 가장 큰 값을 찾는다.
  
• 역시 인덱스 키 값들이 정렬되어 있기 때문에 이진 탐색이 가능하며, 찾을 경우 그 포인터로 연관된 블록을 따라간다. 
  
• 그 뒤로, key값 K를 찾기 위해 블록을 탐색한다. 
  물론 블록은 각 레코드의 컨텐츠가 식별될 수 있을만큼 충분한 정보를 가지고 있어야 한다.(저번에 살펴본)

Multiple Levels of Index

Multiple Level Index)

인덱스 자체로는, 많은 블록을 커버할 수 있다는 장점이 있지만, 
이진탐색으로 인덱스 항목을 찾더라도, 원하는 레코드를 찾고자 
여전히 수차례의 Disk I/O를 수행해야 할 수도 있다.
이럴 땐, 인덱스를 위한 인덱스를 둠으로 써, 인덱스를 좀 더 효율적으로 사용할 수 있다. 
 

• 그림은, 원래의 sparse index에 레벨을 하나 더 추가한 것이다.
  
  • 원래의 인덱스를 First level index(혹은 inner index),
    
  • 추가한 인덱스를 Second level index(혹은 outer index)라 한다.
    
  • 같은 아이디어로, third, fourth 등 계속해서 추가할 수 있다.

    
    
    

    
    
    

Warning

조그마한 주의사항으로, 
최초의 인덱스가 아니라면(최초의 인덱스는 dense/sparse 둘다 가능) 
반드시 sparse index여야 한다. (당연하게도..아니면 의미가 없어지므로) 

하.지.만 
이 원리는 한계가 존재하고, 많은 레벨의 인덱스들을 B-tree 구조로 빌드하는 것이 더욱 좋다. 

Indexes With Duplicate Search Keys

레코드의 Search key가 중복이 없다면, Dense index는 의미가 없을 수도 있다.

-> (모든 레코드의 값을 인덱스에 반영하므로)

하지만 대개의 경우, Search key의 중복이 여럿 발생하여 index를 배치한다.
이러한 중복을 해결하기 위해, 중복되는 Key값에 대해서는 한개의 인덱스 항목과 포인터만을 두자.
즉, 

• Dense Index의 경우, 중복 Key들에 대해 첫 번째 Key 값에 대해서만 인덱스 항목과 포인터를 두게 설계.
  
• Sparse Index의 경우, 블록당 한 개의 인덱스 항목과 포인터를 두며, 그 포인터는 항상
  블록의 첫 번째 Key 값만을 가리키게 설계.

Managing Indexes During Data Modifications

지금까지는 고정된, 정렬된 데이터 파일에 대해서만 인덱스를 살펴보았다. 
하지만, 데이터는 시간이 지남에 따라 발전하기 때문에, 레코드는 삽입/삭제/갱신될 수 있다. 
앞으로는 Sequential File(순차적 파일)같은 구조도, 한 블록에 들어 맞는 것이 존재하지 않게(더욱 거대하게) 변할 것이다. 
저번에 알아봤듯, 데이터 파일을 재구성 하는 방법처럼, 다양한 기법을 사용해야 한다. 

1. Overflow block 생성/삭제 : 오버플로 블록은 스파스 인덱스에 존재하지 않고, 차라리 기본 블록의 확장으로 간주되어야 한다.
2. 오버플록 대신, 순차적인 정렬 하에 새로운 블록을 삽입할 수 있다.
   이 경우, 새로운 블록에 대한 항목을 스파스 인덱스에 추가해야 한다.
   즉, 데이터 파일의 삽입/삭제 시 발생한 문제들과 같은 현상이 발생할 가능성이 있다는 걸 염두하자. 
   (인덱스 역시 물리적 공간에 저장되어야 하기 때문)
   
3. 튜플을 블록에 삽입할 공간이 없으면, 인접 블록(Adjacent Block)에 끼워 넣을 수 있다.
   반대로 또 인접 블록이 너무 텅텅 비게 되면 Combined(병합)될 수도 있다.
   

하지만, 데이터 파일의 변경은 해당 인덱스의 빈번한 변경을 야기한다.
정확한 방법은, 인덱스가 덴스/스파스 인지, 그리고 위에 열거한 세 가지 방법 중 어떤걸 사용하는지에 달려있다.
기억해야 할 하나의 기본 원리는

• 인덱스 파일 자체도 파일의 나열(Sequential file)이다. 
  ( 키-포인터 쌍은 search key값으로 정렬된 레코드로 취급 ) 
  그러므로, 데이터 파일을 유지보수 하는 데 사용한 것과 동일한 전략을 사용할 수 있다. 
  

위의 표에 나와있듯, 우리가 숙지해야 할 것들은,

• 빈 오버플로 블록을 생성/삭제하는 것은 어떤 인덱스든 효과가 없다.
  덴스 인덱스의 경우, 레코드를 참조하므로 무의미하고
  스파스 인덱스의 경우, 참조하는 것은 오버플로 블록이 아닌 주 블록만 참조하기 때문이다.
  

• 빈 정렬된 블록을 삽입/삭제하는 것은 
  덴스 인덱스에겐 효과가 없지만, (마찬가지로 블록을 보는게 아니라 레코드를 보기 때문)
  스파스 인덱스의 경우 각 블록의 삽입/삭제에 따른 인덱스 삽입/삭제가 반드시 필요하다.

• 레코드의 삽입/삭제에 대해서는, 
  덴스 인덱스는 무조건 key-pointer 쌍이 같이 변경되지만
  스파스 인덱스는 그 레코드가 블록의 첫부분이냐 아니냐에 따라 update/none이 결정되기 때문에 물음표를 첨가했다.

• 레코드 끼워넣기도
  덴스 인덱스는 같이 가고,
  스파스 인덱스 역시 그 끼워넣는 부분이 블록의 어디냐에 따라 달라진다.

Secondary Indexes

여태껏 살펴본 '인덱스'들은, 'Primary Indexes'라고 할 수 있다. 
즉, 인덱스가 레코드와 직접적으로 연결되어 위치를 결정하기 때문인데,
다양한 쿼리문을 좀더 용이하게 하기 위해 대부분의 경우 한 릴레이션에 대해 여러 개의 인덱스를 두고자 한다.

예시)

students ( name, dept_name, grade, ... )

SELECT  name
FROM  students
WHERE  dept_name = 'Comp. Sci.';

 name이 PK인 students라는 릴레이션에서(인덱스는 name에 관련한 쿼리를 돕기 위해 name으로 생성하겠지만,
 dept_name이 컴공인 학생을 검색하고 싶을 때

 -> dept_name을 search key로 가지는 인덱스가 있다면 더 효율적인 검색을 할 수 있다.(보조 인덱스의 필요성)

이렇듯 Secondary Index(보조 인덱스)는, 다른 인덱스를 돕는, 말그대로 보조 인덱스이다.
주 인덱스와의 가장 큰 차이로, 이 보조 인덱스는 데이터파일 내 레코드의 위치를 결정짓지는 않는다는 것이다.
위치를 결정해주는 건 주 인덱스고, 보조 인덱스는 그저 레코드의 위치가 어딘지 알려주는 역할을 할 뿐이다. 

이 두 인덱스의 차이점은, 

• 보조 인덱스로 스파스 인덱스를 사용하는 건 말도 안된다. 
  보조 인덱스는 위치에 영항을 끼치지 않기 때문에, 인덱스에서 명시적으로 언급을 해야지만 레코드의 위치를 알 수 있다. 
  -> 즉, 보조 인덱스는 항상 덴스 인덱스이다.

Design of Secondary Indexes

Design

• 보조 인덱스는 덴스 인덱스이며 중복이 보통 발생한다. 
  
• Key-pointer 쌍의 key는 search key 이며, 유니크할 필요는 없다.
  
• 주어진 Key 값으로 항목을 찾기 위해, 인덱스 파일의 쌍은 Key 값에 의해 정렬된다.

만약 상위 레벨의 인덱스를 설계하고싶으면 그 인덱스는 스파스이다!

보조 인덱스와 멀티레벨 인덱스를 혼동하지 말자.

• 데이터는 정렬되어 있지 않아도 인덱스는 정렬되어 있다. 
  
• 20이 무려 세개나 있는데, 이렇게 보조 인덱스를 이용할 땐
  주 인덱스만 이용할 때보다 Disk I/O횟수가 오히려 더 많을 때도 있다.
  
• 하지만, 데이터 블록의 튜플들은 아마 다른 column(s)에 의해 정렬된 상태일 테니 
  우리가 순서를 조정할 수 없어 이 문제는 해결할 수 없다!

Indirection in Secondary Indexes

• 위의 그림처럼 보조 인덱스를 설계한다면,
  상당히 많은 공간의 낭비가 생길 수밖에 없다.
  
• 즉, 데이터 파일의 Search key 값이 n회 나타나면 인덱스파일에도 n회 기록될 것이다.
  
• 반대로, 특정 값을 가진 데이터 레코드에 대한 모든 포인터에 대해서, 키 값을 한 번만 쓴다면 더 나을 것이다.
  

B-Trees

What is B-Tree?

1~2 level의 인덱스도 쿼리의 속도를 많이 향상시켜 주지만,
실제 상용 시스템에서 더 널리 쓰이는 구조가 있다.
바로 'B-tree' 라 하는 데이터 구조이며,
이 중에서도 특정 변형 형태인 'B+tree'를 가장 많이 사용한다. 
이제 B-tree에 대해 설명할것이지만, Detail은 모두 B+tree로의 변형을 위한 것임을 염두하자. 

• B-tree는, 인덱스를 생성할 파일의 크기에 적절한 만큼의 인덱스 레벨을 자동으로 유지한다.
• 블록의 공간도 관리하여, 모든 블록은 꽉 차있거나 최소 절반 이상 차있게 된다. 오버플로블록은 필요없다.

The Structure of B-trees

Structure

이름에서 알 수 있듯 B-tree 구조는, 블록을 트리로 구성한 것이다. 
B는 'balanced'의 약자이며, 이 밸런스는 루트로부터 리프까지 모든 경로는 같은 길이라는 것을 의미한다. 
B-tree에는 보통 세 종류의 레이어 ( Root, leaves, intermediate layer )가 있다. ( 더 추가할 수도 있다 )

• Root : 루트 노드
• Leaf : 리프 노드 (트리의 외부 노드(External node))
• Intermediate layer : 루트와 리프가 아닌 중간 단계에 있는 노드

각 인덱스와 관련된 파라미터 n이 존재하며, 이 n은 B-tree의 모든 블록의 레이아웃을 결정하게 된다.

• 각 블록은 n개의 Search key 값과 n+1개의 포인터를 위한 공간이 존재한다.
• 리프 노드의 Key 값은 데이터 파일의 Key값이다. 이 Key값은 왼쪽에서 오른쪽으로 정렬되어있다.
• 루트에는 적어도 두 개의 포인터가 사용된다. 또한 모든 포인터들은 하위(자식) 노드를 가리킨다.
• 리프의 마지막 포인터는 그 다음 크기의 Key를 보유한, 바로 오른쪽의 노드를 가리킨다.

• 또한 리프 블록 내의 다른 n 개의 포인터들 중, 적어도 (1+n)/2(나머지 버림)개의 포인터들은 데이터 레코드를 가리킨다. 
  (안쓰이는 포인터는 널을 의미하며 아무데도 가리키지 않음)
  

• 또한 i번째 포인터는 데이터의 i번째 key를 보유한 레코드를 가리킨다.

• 중간 노드들의 모든 n+1개의 포인터들은 그 다음 하위의 B-tree 블록을 가리킨다. 
  적어도 (1+n)/2(올림)개의 포인터가 사용된다.
  

Lookup in B-Trees

B-tree 인덱스를 가지고, Search-key K를 보유한 레코드를 찾는 작업을, 'Lookup' 이라 칭한다. 
K를, 루트부터 리프까지 Recursively(재귀적)으로 찾는다.

• BASIS : leaf에 도달하면, 거기서 key를 보자. i번째 key K라면, i번째 포인터가 레코드를 가리키고 있을 것이다.
• INDUCTION : 중간 내부 노드 (K1, K2, ... Kn)라면 원하는 key값 K를 찾아 child로 내려간다. 이 내려가는 절차를 재귀로 적용한다.

Range Queries

B-tree는 search key의 단일 값이 요구되는 쿼리문 뿐만 아니라,
값의 범위를 요구하는 쿼리문에서도 유용하다.
'Range queries' 는 WHERE 절에 '=' 나 '<>' 를 제외한 비교 연산을 이용하여 search key 값(들)을 비교하는 형태를 일컫는다.

예 :

SELECT  *
FROM  R
WHERE  R.k > 40;

or

SELECT  *
FROM  R
WHERE  R.k >= 10 AND R.k <= 25;

• [a, b]범위 내 모든 key를 B-tree의 리프에서 찾으려면, 먼저 a를 찾는다.
• a가 있든 없든 a가 있어야 할 위치를 알게 될 것이고, a가 있다면 a부터, a가 없다면 a보다 큰 제일 작은 값부터 범위 내에서 찾기 시작한다.
• 즉, 계속해서 다음 리프를 찾아가다가 마침내 b보다 큰 값을 보유한 노드를 찾게 되면, 그 지점에서 멈춘다.
• a가 마이너스 무한대여도, b가 무한대여도 (바운더리가 없다는 뜻일 뿐이므로) 충분히 가능하다.

Insertion Into B-Trees

Insertion

앞전에서, simpler multilevel index는 한계가 존재하여 B-tree로 구성하는게 좋다고 했는데
재귀에 따른 삽입 과정을 보며 그 이유를 살펴보자.

• 새로운 Key가 위치할 적절한 리프 노드를 찾고(lookup), 그곳에 공간이 있으면 넣는다.
  
• 오버플로가 발생하면, Split(리프 노드를 두 개로 나누고), 
  이 두 노드에 원래 보유했던 Key를 나눈다((1+n)/2 올림 까지)
  그러면 각 두 노드는 절반이 차거나 아니면 절반 조금 넘거나 할 것이다.
  
• 그리고선, 부모에 중간값을 올린다. 부모에 중간값이 들어가는 것 자체도 삽입 연산으로 취급한다.
  
• 예외적으로, 루트에 삽입하려고 했는데 공간이 없어서 분할한 경우,
  이 두 노드를 자식으로 갖는 새로운 루트 노드를 상위 레벨에 생성한다.
  (루트 노드는 slot의 개수와 상관 없이 한 개의 key를 갖고 두 개의 자식을 갖는다.)
  

노드를 분할하고 부모로 삽입할 때마다 키 관리는 무척 조심스럽게 해야한다.

먼저, n개의 슬롯을 가진 리프 N을 가정하자.(슬롯은 다 꽉찬상태)
그리고 이 리프에 n+1번째 key를 삽입한다고 가정해보자.
그럼, N을 나눠 새로운 노드 M을 N 바로 오른쪽에 만든다.
첫번째 부터 (1+n)/2까지의 key-pointer쌍은 N에 그대로 두고,
나머지 쌍들은 M에 옮긴다. (여기서, 적어도 (1+n)/2개의 쌍을 가져야 한다는 걸 주의하자)

< 파일첨부 >

Deletion From B-Trees

Deletion

특정 Key값 K를 삭제하려면, 일단 레코드 위치를 찾고, 리프노드의 key-pointer 쌍에 대한 정보를 알아야 한다..
찾은 후 삭제를 했는데, 이때

1. 삭제가 발생한 노드가 최소한의 key-pointer쌍 개수 이상을 보유하고 있다면
   그대로 삭제 연산은 끝난다.
   

하지만, 삭제 전에 최소의 개수를 가지고 있었을 수도 있어서,
삭제 후 키의 개수 제약을 깰 가능성은 다분하다.

2. 만약 부족하다면, 다음의 두 가지 방법 중 하나를 사용하여 B-tree 상태를 유지할 수 있다.
   
   • N의 인접한 형제 노드 중 하나가 최소의 key-pointer 쌍 개수보다 많이 보유하고 있을 경우,
     한 쌍을 N에게 전해주고, key의 순서를 그대로 유지한다. 
     이 때엔, N의 부모 노드가 새로운 상황을 반영해야 할 수도 있다.
     즉, 예를 들어 N의 오른쪽 형제 노드 M이, key중 가장 작은 값을 N에게 넘겨주면
     N,M의 부모 노드에게 M의 smallest key 값을 올려준다.
     
   • N의 인접한 형제 노드 중 아무도 최소 개수보다 많이 보유한 노드가 없는 경우도 있다.
     이 때엔 근접한 형제노드 두 개를 하나로 Merge(합친 뒤), 부모와 잘 연결해 주기만 하면 된다. 
     (합쳐도 한 노드가 가질 수 있는 최대 key-pointer 쌍의 개수보다 작거나 같으므로)
     부모가 삭제되어 또 최소 갯수를 만족하지 못한다면 이 알고리즘을 재귀로 돌려 부모 노드에서 시행한다.
     

<파일첨부>

Efficiency of B-Trees

B-tree는 레코드의 위치찾기(lookup)/삽입/삭제 면에 있어, 각 파일에 대한 disk I/O 횟수를 무척 줄여준다.
우선, 블록당 소유할 수 있는 key의 개수가 충분히 크면 Splitting / Merging같은 이벤트는 매우 드물게 된다.
일어난다 해도, 거의 대부분은 두개의 리프 노드, 그들의 부모 노드 정도만 영향을 받는다.
그러므로, I/O cost를 거의 무시할 수 있다고 봐도 과언이 아니다.

하지만, search key로 레코드에 대해 '검색'하는 것자체가 루트부터 리프 노드까지 포인터를 찾는것이다. 
즉, B-tree의 level 수만큼 disk I/O가 일어나고, 여기에 (lookup을 위한 1회), (insert/delete를 위한 2회) 
정도의 횟수가 더 발생한다. 

Hash Tables

Structure of Hash Table

해시 테이블 구조는,
search key를 인자로 받는 'Hash Function' 이 존재하고, 이 해시함수는 받은 search key 값을
'Bucket' (디스크 블록 같은 개념) 에 대응시킨다. (매핑한다)
즉, 레코드가 search key K를 보유한다면, 버켓넘버 h(K)번째 리스트 버켓에 링크 해놓음을써 저장한다. (h는 hash function)

Choice of Hash Function

'Hash function'은 key를 말그대로 'hash'할 수 있어야 한다.
또한 결과값이 정수형으로 나와야 한다는 게, 꼭 랜덤함수처럼 보인다.
이러한 해쉬함수는 보통 소수 bucket 수 B로 key 값 K를 나누는 형태를 띈다.
만약 search key가 문자라면, 문자들을 다 숫자로 치환해 더한 값을 B로 나누는 식으로 시행한다.

Insertion Into a Hash Table

Insertion

search key K를 가진 새로운 레코드가 삽입되면, h(K)를 수행한다.
h(K)번째 bucket에 공간이 있으면, 이 버킷의 블록에 레코드를 삽입한다.
만약 첫 번째 블록에 공간이 없으면 이 블록에 체인된 오버플로 블록 중 하나에 삽입한다.
(체인된 블록이 없다면 새로운 오버플로 블록을 만들고 그곳에 삽입)

Deletion from a Hash Table

Deletion

삭제도 같은 패턴이다.
버킷의 h(K)번째로 가 K로 삭제할 레코드를 찾고, 지운다.
만약 블록 사이에서 레코드의 이동이 가능하면 삭제 후
체인을 한 개 줄여 통합할 수도 있다 .

Efficiency of Hash Table Indexes

이상적으로, 각 블록을 알맞게 담을만한 충분한 크기의 버킷들이라면,

Key를 찾는데 1회의 Disk I/O, 
Insert / Delete는 2회의 Disk I/O밖에 하지 않는다.

이 횟수는 덴스/스파스/B-tree 인덱스 구조보다 현저히 낮은 숫자이다.
하지만, 파일이 점점 커지면 특정 버킷에 체인된 블록들이 주렁주렁 달리는 사태가 발생할 것이다.
따라서, 적어도 한 번의 Disk I/O가 발생하는 각 블록의 리스트가 아주 길어지면 좋을 것이다.
그러므로 버킷 당 블록 수를 낮게 유지할 필요가 있다.

우리는 지금껏 'Static Hash Tables(정적 해시 테이블)' 에 대해 살펴보았다. (버킷의 길이는 B로 고정)
이번엔 'Dynamic Hash Table(동적 해시 테이블)' (거의 모든 버킷들이 버킷 당 블록 하나씩만 매핑되게 유도가능한 해시 테이블)
에 대해 간단히 살펴보자.

1. Extensible hashing : 해시 테이블이 너무 작다고 느껴질 때, 두배 늘리는 기법
   
2. Linear hashing : 약간의 growing이 필요할 때, 매번 1씩 늘리는 기법
   

Extensible Hash Table & Linear hash Table

Extensible Hash Table(확장 해시 테이블)

1. 버킷에 Indirection level 도입. 즉, 데이터 블록 자체를 직접 포함하는 배열 대신, 버킷을 참조하는 블록에 대한 포인터의 배열을 둔다.
   
2. 포인터의 배열은 커질 수 있다. 그 길이는 항상 2배씩 커지며, 버킷 수도 2배씩 증가한다.
   
3. 그러나, 각 버킷당 데이터 블록이 반드시 하나씩만 있어야 하는 건 아니다.
   -> 해당 버킷의 총 레코드 개수가 블록 안에 들어갈 수 있다면, 특정 버킷들은 블록을 공유할 수도 있다.
   

Linear Hash Table(선형 해시 테이블)

1. 선형 해싱은, 해시 테이블이 한 번에 한 개의 슬롯씩 증가시킨다.
   
2. 슬롯 생성이 자주 일어나 효과적이지 않아 보이지만,
   이런 빈번한 싱글 슬롯 생성은 컬리젼 체인(Collision Chain) 길이를 조절하는 데 매우 효과적이다.

마침.

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).

마침.

Constraints and Triggers

Necessity

무결성 제약조건(Integrity Constraint)

• 우리가 어떤 특정한 Relation을 삽입할 때 혹은 DB가 변할 때 큰 문제중 하나에 직면하게 된다.
  (Domain에 벗어나는 값이라던가, 말이 안되는 값이라던가 하는)
  
• 즉, Update, Insert 같은 Modification 후에 테스트를 하며 항상 반복적으로 확인해야 할 필요가 있다. 
  
• SQL은 '무결성 제약(Integrity Constraint)' 이라는, 제약조건을 표현하는 다양한 기법을 제공한다. 
  
  1. Keys
  2. Referential Integrity ( Foreign-Key Constraint )
  3. Domain & NOT NULL
  4. CHECK
  5. Assertions
  6. Triggers

• 프로그래밍 작업이 복잡해지고, 반복해서 구현해야 하고, 무결성 제약 조건들 간에 서로 충돌이 발생할 수도 있다는 단점이 있지만,
  저장된 데이터가 좀 더 실세계의 의미에 충실하게 되며, 에러의 발생 여지가 크게 감소된다는 장점이 있다.

1. Primary-Keys and Foreign-Keys

Keys

• DB의 가장 중요한 제약은, Key를 지정하는 'Column의 선언' 에 있다.
• Keys 제약도 다른 많은 제약들 처럼 CREATE 문에서 선언된다.
  두 가지 종류 : Primary Key(주 키, 이하 PK), UNIQUE
  

Primary Key

• Key(s)중 user에 의해 선정된 Key
• Relation당 최대 하나만 보유할 수 있다.
• CREATE TABLE 문에서 PK를 선언하는 두 가지 방법
  1. Column 선언 후 해당 Column이 PK라고 선언하기
  2. Column 선언을 모두 마치고 마지막에 특정 Column을 가리키며 PK라고 선언하기
     ( 둘 이상을 묶어서 PK로 사용하고 싶으면, 2번 방법을 쓴다. ) 
     

< 1번 방법 >

CREATE  TABLE  Students (
    s_id  INT  PRIMARY KEY,       <-
    name  VARCHAR(20),
    dept  VARCHAR(30),
    grade  INT
);


< 2번 방법 >

CREATE  TABLE  Students (
    s_id  INT,
    name  VARCHAR(20),
    dept  VARCHAR(30),
    grade  INT,
    PRIMARY KEY  ( s_id, name )       <-
);

Student Table의 학번 (2번은 학번과 이름 모두)을 PK로 지정.

UNIQUE

• PK가 아닌 UNIQUE를 쓰는 기법
• PK와 의미는 거의 유사하지만 다른 두가지는
  1. PK는 Relation당 한개지만, UNIQUE 개수는 상관없다.
  2. NULL값 허용 ( NULL을 값으로 본다면 중복이 발생한다.하지만 허용함 )
     

CREATE  TABLE  Students (
    s_id  INT  UNIQUE,                   <-
    name  VARCHAR(20)  UNIQUE,       <-
    dept  VARCHAR(30),
    grade  INT
);

2. Referential Integrity ( Foreign-Key Constraint )

Concepts about Foreign-key

• 다음으로 중요한 제약은, '특정 Column은 말이 되야 한다는 것(Make Sense)' 이다.
  즉, 참조 하는 쪽의 Column 값은 참조 받는 쪽의 Column 중에서만 값이 존재해야 한다.
• SQL에서는, Foreign key(외래 키, 이하 FK)라는 특수한 Key를 둠으로 써 Referential Integrity를 준수하는데,
  이는 FK의 Column(s)값이 다른 Relation의(같은 Relation도 가능하긴 함) PK값을 참조하는 것이다. 
  
• 이 선언의 조건은 두 가지로 볼 수 있는데,
  
  1. 참조 받는, 두 번째 Relation의 Column은 반드시 Unique이거나 PK여야 한다.
  2. 참조 하는 Relation의 Column 내 값은 참조 받는 Relation의 어느 Tuple에라도 반드시 존재해야 한다. 
     더 정확하게 말하면, Relation R1의 Column C1의 Tuple t1, Relation R2의 Column C2의 Tuple t2에 대해 
     t1[C1] = t2[C2]를 만족해야 한다. (여기서 C1은 FK, C2는 PK/UNIQUE) 
     

How to use it

CREATE 시 표기 법

1. column_name data_type REFERENCES < table > ( < column_name > )

2. Column들을 다 명시한 뒤 맨 마지막에 
   FOREIGN KEY ( < column_name > ) REFERENCES < table > ( < column_name > ) 
   

CREATE  TABLE  Department (
    dept_name  VARCHAR(30)  PRIMARY KEY,
    building  VARCHAR(20),
    budget  INT
);


CREATE  TABLE  Students (
    s_id  INT  PRIMARY KEY,
    name  VARCHAR(20),
    dept  VARCHAR(30)  REFERENCES  Department ( dept_name ),            <-
    grade  INT
);


CREATE  TABLE  Students (
    s_id  INT  PRIMARY KEY,
    name  VARCHAR(20),
    dept  VARCHAR(30),
    grade  INT,
    FOREIGN  KEY  ( dept )  REFERENCES  Department ( dept_name )         <-
);

Students table의 dept column을 Department table의 PK인 dept_name을 참조하게 하는 외래키로 설정.

• 한 가지 예외가 있다면, NULL값도 참조해야 하는 건 아니다. ( 받는 쪽은 PK라 NULL값이 없지만서도 )

Maintaining Referential Integrity

과연 이 까다로운 제약을 '어떻게' 유지할까? 
Implementor는 다음과 같은 세 가지 방법으로 유지할 수 있다.

• The Default Policy : Reject Violating Modifications ( DEFAULT )
  디폴트 정책으로, 시스템 차원에서부터 거절(Reject)하는것이다.
  
  1. NULL이 아니면서 t2[C2]도 아닌 것을 Insert하려고 할 때
  2. NULL이 아니면서 t2[C2]도 아닌 것으로 Update하려고 할 때
  3. C2의 Tuple 중 C1에 등장하는 값을 Delete하려고 할 때
  4. C2의 Tuple 중 C1에 등장하는 값을 Update하려고 할 때

• The Cascade Policy 
  계단식 정책으로, 참조받는 값이 변하면, 참조하는 값도 같이 따라서 변하게 설정하는 것이다. 
  즉, C2의 값이 Update나 Delete되면 C1의 값도 같이 Update나 Delete된다. 
  

CREATE  TABLE  Students (
    s_id  INT  PRIMARY KEY,
    name  VARCHAR(20),
    dept  VARCHAR(30)  REFERENCES  Department ( dept_name )
        ON UPDATE CASCADE,                                                                   <-
    grade  INT
);

• The Set-Null Policy 
  FK에 독립적으로 설정함으로써 지워진 값은 NULL로 지정하는 것이다. 
  

CREATE  TABLE  Students (
    s_id  INT  PRIMARY KEY,
    name  VARCHAR(20),
    dept  VARCHAR(30)  REFERENCES  Department ( dept_name )
        ON DELETE SET NULL,                                                                   <-
    grade  INT
);

Delete에 있어선 Set Null을, Update에 있어선 Cascade를 설정하는게 유리하다. 

CREATE  TABLE  Students (
    s_id  INT  PRIMARY KEY,
    name  VARCHAR(20),
    dept  VARCHAR(30)  REFERENCES  Department ( dept_name )
        ON UPDATE CASCADE                                                                    <-
        ON DELETE SET NULL,                                                                   <-
    grade  INT
);

3. Domain & Not-Null Constraints

• 각 Column의 값들에 대한 Data type, Default value, 범위 등을 제한/결정한다.
• 또한 해당 Column의 맨 마지막에 NOT NULL을 기재하면, NULL값을 불허한다. 
  이 때엔, Insert에서 모든 Column에 대해 명시해준다거나 Tuple의 모든 값들을 일일이 명시할 필요가 있다.
  
• 위에서 살펴본 Set-Null policy는 사용 불가이다. 
  

CREATE  TABLE  Students (
    s_id  INT  PRIMARY KEY,
    name  VARCHAR(20),
    dept  VARCHAR(30)  REFERENCES  Department ( dept_name )
    grade  INT  NOT NULL                                                                <-
);

4. CHECK

• 새로운 값을 받으면, 그 때마다 check하는(말 그대로 CHECK) 역할이며 
  주어진 Condition에 부합하는 지 확인하는, 일종의 New Value에 대한 제약이다.
  
• Column-based와 Tuple-based 두 가지가 있지만 거의 유사하여 구분하진 않겠다. 
  
• 하지만 Insert나 Update시 WHERE cluase에서 조건을 명확히 주면 되기도 하고 
  새로운 값에 대해 일일이 확인하는 작업이라 무거워 진다는 단점이 있다.
• Relation마다 걸 수 있으며, 다른 Relation에겐 보이지 않는다(Invisible). 
  

CREATE  TABLE  Employees (
    name  VARCHAR(20),
    age  INT,
    gender  CHAR(1)  CHECK ( gender  IN  ( 'F', 'M' ) ),             <-
    part  VARCHAR(10)
);

5. Assertions

• General Constraint 라고도 불리우며, SQL expression상에서 
  항상 True만 나오게 하는 boolean-value이다.
  

CREATE ASSERTION < name > CHECK ( < condition > )

• Condition은 항상 True여야 한다. ( False로 오게 하는 어떤 Modification이든 전부 Reject) 
  
• Assertion에서 언급된 relation의 어떠한 change라도 발생하면 그 즉시 발동된다.
• 위에서 살펴본 CHECK와의 차이점
  • CHECK는 선언되고 나타난 그 Relation 안에서 참조를 하는 거라면,
  • ASSERTION은 독립적으로 생성하여 어떤 Column이든 상관없이 수행한다. 
    즉 Condition에 Subquery가 등장할 수도 있다는 말이다. 
    또한 Boolean-Value를 갖기 때문에 Condition의 결과를 Aggregate하여 상수와의 비교를 하거나 
    NOT EXISTS같은 표현도 사용할 수 있다. 
    

CREATE  ASSERTION  Graduate_Yet  CHECK
    (  NOT  EXISTS 
        (  SELECT  *
           FROM  Students
           WHERE  grade  =  4
        )
    );

Student에 4학년이 없도록 하는 Assertion 생성.

• DROP을 이용해 제거할 수 있다.
  

DROP  ASSERTION  Graduate_Yet;

6. Triggers

What is Trigger?

Triggers ( Event-Condition-Action Rules / ECA Rules )는 이전에 살펴본 제약들과 3가지 측면에서 다르다. 

1. DB 프로그래머로부터 어떠한 event가 발생할 때만 발동한다( 깨어난다 ). ( 보통은 Insert, Delete, Update )
2. 깨어나면, event 실행 전 Condition을 확인한다. 이 때 Condition을 충족하지 않으면, 가만히 냅둔다.
3. Condition을 충족하면, 특정 action을 취한다. ( 다른곳으로 옮긴다던가, 실행취소한다던가 )

Kinds of Options for Triggers in SQL

SQL에서, Trigger는 사용자에게 Event, Condition, Action 부분에서 다양한 옵션을 제공한다. 

1. Action은 Trigger Event 전/후로 실행될 수 있다.
2. Action은 Tuple의 취해지기 전(old)값 혹은 새로운(new)값을 참조할 수 있다.
   
   • 여기서 old, new개념은 Modification기준이 아닌 Trigger 발동 기준
3. Update Event는 특정 Column(들)에 대해 한정적일 수 있다.
4. Condition은 WHEN clause를 통해 기재된다.
5. 한 번에 한 Tuple(Row 단위) 혹은 한 번에 모든 Tuple(Statement 단위)에 대한 옵션을 취할 수 있다.

CREATE  TRIGGER  Graduate
AFTER  UPDATE  OF  grade  ON  Students
REFERENCING
    NEW TABLE  AS  nTable
FOR  EACH  STATEMENT
WHEN  (  4  >  (  SELECT  grade  FROM  nTable  ) )
BEGIN
    DELETE  FROM  Students
    WHERE  (  s_id, name, dept, grade )  IN  nTable;
END;

Students 에 학년이 +1 될 때마다(Update 될 때마다), 학년이 4를 초과하면 삭제하는 Trigger.

6. Instead-Of Trigger를 통해, 좀 더 간단히 표현할 수 있다. 
   상업DB에서도 많이 서포트 되는 것이며, BEFORE/AFTER 대신 INSTEAD OF를 사용한다.
   

CREATE  VIEW  Marvel  AS
    SELECT  title, year
    FROM  Movies
    WHERE  studioName  =  'Marvel';


CREATE  TRIGGER  MarvelInsert
INSTEAD  OF  INSERT  ON  Marvel
REFERENCING  NEW  ROW  AS  nRow
FOR  EACH  ROW
INSERT  INTO  Movies ( title, year, studioName )
VALUES ( nRow.title, nRow.year, 'Marvel' );

View에 삽입되는 tuple들을 view 대신 Base Table로의 삽입으로 대체하는 Trigger.

마침.

Extended Operators of Relational Algebra

Bags

What is Bags?

• 일반적으로, Database의 각종 Data들은 간단한 순수 집합 베이스의 tuple들이다.
  
• 가끔, Database system의 Relation은 Duplicate tuple(중복튜플)이 허용된다. 
  
  • (말인 즉슨 같은 tuple이 1회 이상 발생 허용) 
    
• 이 때, 그 set을 Bag 혹은 Multiset이라 부른다. 
  
  

여기서의 '중복'이란, tuple의 중복이다 ( component의 중복과 다름 )

Set, Bag 둘 다 집합의 의미이며 tuple의 순서 역시 상관 없다.

Why Bags?

• 개념상으로는, 중복을 허용하지 않아 tuple 개수가 더 적은
  Set이 Bag보다 Speed가 빠르고, 효율적인 Implementation에 유리한 것 처럼 보인다.
  하지만 이전에 언급했듯이, Union 연산은 Bag이 더 빠르다. 
  또, Projection 연산은 작업을 각 튜플에 대해 독립적으로 할 수 있게 해준다.
  
• Set으로 결과를 얻으면 연산 후 일일이 다 비교하여 중복이 있는지 체크해야한다.
  반면 Bag으로 결과를 얻으면 비교 없이 작업이 종료된다.
  이와 같이, 연산을 수행하고 곧바로 종료되는 Bag과 달리, 중복 튜플을 확인작업하는 Set이 더 느리다.
  (단지 결과 Relation은 Set based가 크기가 작아서 빠르게 보이기만 할 뿐 사실상 훨씬 소요시간 ↑)
  
• 또한, 평균 계산 등 아예 결과가 다른 경우도 있다. (그림 참조)
  

Union, Intersection, and Difference of Bags

• Relation R에 튜플 T가 n개, Relation S에 튜플 T가 m개 있을 경우,
  
• T의 개수 #T는
  
  • #T in (R ∪ S) = n+m (개) 
    
  • #T in (R ∩ S) = MIN(n, m) (개) 
    
  • #T in (R - S) = MAX(0, n-m) (개) 
    

Bag' operations on Sets 
Relation R과 S가 set이라고 하자.
이때 방금 언급한 Intersection, Difference 연산은
Bag-rule로 실행해도 같은 결과를 보인다.
하지만 Union 연산의 경우, Bag-rule로 실행하면
결과 Relation에 중복이 생길 수도 있다.
그러므로 Union 연산은 조심하자! 

Projection & Selection on Bags

• Bag에 Projection, Selection을 적용할 때, 
  각 tuple마다 독립적으로 수행(즉, 이와 같은 tuple이 있나 신경쓸 것 없이 자신만 신경쓰고)할 수 있다. 
  또한 Selection Condition 역시 각 tuple에 독립적으로 적용해야한다. 
  
• Set의 연산과 중복을 허용한다는 점만 빼면 별 다를 게 없어서 그림은 생략했다. 
  
  

Algebraic Laws for Bags (연산법칙) 
Algebra(대수)에는 많은 법칙들이 있다. 
예를들어, Union 연산의 교환법칙 같은경우 Set이든 Bag이든 상관없이 성립한다. 
하지만, (R ∪ S) - T = (R - T) ∪ (S - T)같은 분배법칙같은 경우, 성립하지 않음에 주의! 

Product of Bags

• Set의 Product 연산과 같다. 
  R에 tuple T1이 n개, 
  S에 tuple T2가 m개 있을 때 
  Product R × S에 tuple T1T2가 nm회 나올 뿐이다. 
  

Joins of Bags

• Join 연산 역시 별거 없다. 
  그냥 Set의 Join 연산처럼 각 tuple들에 대해 
  조건에 맞는지 비교하고 결과 tuple을 결정하기만 하면 된다. 
  또한 연산 중 중복을 제거하지 않는다. 
  즉, 각각 별개의 독립적인 tuple로 취급한다. 
  

Extended Operators of Relational Algebra

• 지금까지 기본 Relational Algebra와 Set&Bag구별을 해 보았는데, 이들 모두 기초 질의어이다. 
  
• SQL같은 언어는 실제 Application Processing에서 상당히 중요한 몇가지 다른 연산들도 더 가지고 있다. 
  
• 추출 부분에 산술이 허용되는 등 기본 관계 대수 연산이 몇 가지 측면에서 확장되었다.
  

Duplicate Elimination

• 말 그대로 중복을 제거하는 연산이다. 
  
• δ(R) [ :델타]로 표현하며, Bag인 R의 중복튜플들을 제거함으로써 Set으로 변환한다.
  

Aggregation Operators

• 결과를 특정 연산을 취함으로써 하나의 결과로 반환한다. 
  
  • SUM : Column의 SUM(합)값을 반환한다.
    
  • AVG : Column의 Average(평균)값을 반환한다.
    
  • COUNT : Column의 Count(개수)값을 반환한다. ( 이 때, 별다른 언급이 없으면 중복 포함 )
  • MIN and MAX 
    
    • Numerical values : 각각 smallest, largest값을 반환한다.
    • Character-String values : 각각 
      Lexicographically(Alphabetically: 사전순서대로)하게 first, last 값을 반환한다. 
      

엄밀히 따지자면, Aggregation operator는
Relational Algebra는 아니다. 하지만
뒤에 나올 Grouping에서 사용하기 때문에
같이 학습하도록 한다.

Grouping

• 보통, 전체 Column을 가지고 Average같은 Aggregation 연산을 하지는 않는다.
  각각 Column 1개 전체의 연산 말고 좀 더 Column들을 묶어서 연산을 행한다.
  
  • 예를 들어, Studio마다 상영시간의 총합을 알고싶은 경우엔 어떻게 하나?
    → Studio마다 묶어서 상영시간의 총합 Group마다 독립적으로 계산한다.
    
• γL(R) [ :감마]로 표현하며, List L : Attribute 및 Aggregation으로 나타낸다. 
  이 때, 그룹화의 기준이 되는 Column을 Grouping attribute, 
  Aggregation 연산을 하는 Column(들)을 Aggregated attribute라 한다.
  
• γL(R)의 특징
  1. R의 일부를 Group화한다. 각 Group들은 Grouping attribute에 해당하는 1개의 값을 갖는 모든 tuple들로 구성된다.(중복은 제거) 
     즉 Grouping attribute에는 NULL값이 허용되지 않는다. 
     
  2. 만약 Grouping attribute가 없다면, Relation R은 1 Group이다. 
     
  3. L에는 Attribute, 연산, →(Renaming)등을 기재할 수 있다.
  4. L에 연산(Aggregation)이 들어가면, 각 Group당 1개의 tuple만 존재하게 된다. 
     

Grouping은 쉽게 말해, 공통점을 찾아 그룹화 하는 것이다.

δ is a special case of γ
델타(Duplicate Elimination)는 여러 개의 표현이 존재한다.
예를들어, R(A,B,C)에 대해 δ(R) = γA, B, C(R)이다.
즉, 델타는 Aggregation 없이 모든 Columns를 각각 그룹화 하는것과 같다.
그럼 각각의 Group들은 감마 연산자 자체가 중복을 제거하기 때문에 결국 같아진다.
하지만, 델타는 더 일반적이고 중요한 연산자라 Algebraic측면에선 더욱 고려할 필요가 있다.

혹자는 감마(Grouping)를 Set Projection의 확장(Extension)이라 여긴다.
즉, γA1A2..An(R) = πA1A2..An(R)이다. (물론 Set 한정, Bag이면 다름) 
그러므로 감마는 종종 일반화된 추출(Generalized Projection)이라 불린다.

Extending the Projection Operator

• Extended Projection도 저번에 보았던 Projection과 거의 유사한데, 
  Attribute list L에 다음과 같은 요소들을 기재하여 좀 더 구체적인 추출이 가능하다.
  
• πL(R) [ :파이]로 표현하며, 여기서 L값의 의미는,
  
  1. Relation R의 Column.
     
  2. x→y 표현 : x와 y는 둘 다 Column name이고, x를 y로 Renaming한다. 결과 Schema 역시 y로 표기된다.
     
  3. E→z 표현 : E는 Expression(Column, 상수, 산수, 스트링 연산자 등)
     z는 그 E의 계산 결과를 Renaming한 Column name이다.
     

신기하게도, 중복이 생길 수 있다.

The Sorting Operator

질의의 결과 데이터를 저장해두고, 다음에 또 보고 싶을 때가 있다.
이를 위해 τL(R) [ :타우]을 사용해 정렬하는데, L은 Column의 list, R은 역시 Relation이다.
즉, τL(R)는

1. L이 하나의 Column : 이 Column의 값만을 기준으로 tuple을 정렬한다. (같다면 임의로 배치)
   
2. L이 다수의 Column : 앞의 Column 기준으로 tuple을 정렬하고
   만약 같은 tuple이 있다면 그 다음 Column 기준으로 정렬하고,
   이런 방식으로 계속 정렬한다. ( L = A1,A2,...An에서 A1기준, A2기준,...An기준 )
   이 때도, n개 의 Column 말고 다른 Column만 다른 tuple이 존재하고, n개의 Column 값이 전부
   같으면, 임의로 배치한다. 즉, 기준Column이 아닌 다른 Column으로는 정렬상태를 알 수 없다.
   

τ는 Anomalous(변칙적, 가변적)이기 때문에, 결과가 Set(순서가 상관이 없는)이 아니라 
List of tuples(순서가 상관이 있는)로 반환하는 유일한 연산이다.
그래서 Sorting은 Final Step 연산이다. 만약 τ 뒤에 또 다른 Operator가 나온다면, 
정렬된 순서는 다시 섞이게 된다.

Outerjoins

Why? 

• 조건에 부합하는 tuple만을 반환하는 Join연산을 지난번에 살펴보았다.
  하지만, 결과 Relation에서는 흔적도 찾아볼 수 없는,
  조건에 부합하지 않고 'dangling'되는 tuple(들)이 있어,
  원래의 Relation을 완벽하게 표현할 수는 없다.
  → To avoid dangling tuple's loss
  
• 이를 위해, Outerjoin 연산을 사용하며,
  실제로 많은 상용 DB system에서 다양하게 쓰인다.
  

How to use it 

• 기본 Join으로 연산을 하되, 부합하지 않아 삭제될 tuple들도 
  결과 Relation의 하위에 기재한다. 이 때, 빈 칸( NULL값 )은 ⊥로 표시한다.
  
• Theta-join의 조건(Predicate, Condition) 역시 추가할 수 있다.
  (이 때는 먼저 Condition에 만족하는 튜플들을 반환한 뒤
  나머지 제거되는 튜플들을 NULL 값과 같이 표시한다)
  

마침.

Relational Algebra

Relational Data Operation

What is Relational data Operation?

• 원하는 데이터를 얻기 위해 Relation에 필요한 Query를 수행하는 것으로,
  DB system의 구성 요소 중 데이터 언어의 역할을 한다.
  
• 관계 대수/관계 해석 으로 나눌 수 있다. (기능과 표현력 측면에서 능력은 동등하다)
  • 관계 대수(Relational Algebra) : 절차식 언어, 원하는 결과를 얻기 위해 데이터의 처리 과정을 순서대로 기술한다.
  • 관계 해석(Relational Calculus) : 비절차식 언어, 원하는 결과를 얻기 위해 처리를 원하는 데이터가 무엇인지만 기술한다.

Why do we use it?

• 원하고자 하는 데이터를 쉽고, 빠르고, 정확하게 얻고자 사용한다.
  
• 새로운 데이터 언어 제안 시, 해당 데이터 언어의 유용성을 검증하는 기준
  관계 대수나 해석으로, 기술할 수 있는 모든 query를 기술할 수 있으면
  데이터 언어를 관계적으로 완전(Relationally Complete)하다고 판단할 수 있다.
  
  

Relational Algebra

What is Relational Algebra?

• Relation을 다루는 연산으로, 검색 질의를 기술하는데 사용한다.
• 절차식 언어이다. (User가 원하는 결과를 위해 어떤 연산을 수행해야 할 지 system에 알려준다)
• 간단하며 명시적(Powerful) 표현을 사용한다.
• 폐쇄 특성(Closure Property)을 가진다.

->피연산자와 그 연산의 결과 역시 Relation이다.

• 대표 연산자는 8개로, 일반 집합 연산자 4개와 순수 관계 연산자 4개로 분류할 수 있다.
  
• 피연산자의 특성 두가지
  • Variables that stand for relations(relation을 나타내는(대표하는) 변수)
  • Constants which are finite relations(유한한 relation의 상수)
    
    

  연산 : By System     vs     언어 : By User

Normal Set Operator

일반 집합 연산자

• Relation이 tuples의 set이라는 개념을 이용하며, 수학의 집합 연산자를 차용한다.
• 조건 : 피연산자가 두 개이며, 합병가능(Union-compatible)이어야 한다.
• 합병가능 (Union-compatible)이란?

UNION

INTERSECTION

DIFFERENCE

Cardinality	차수	특징
│Ｒ－Ｓ│≤│Ｒ│	Ｒ과Ｓ의 차수와 같다	교환/결합법칙 불가

CARTESIAN PRODUCT

Cardinality	차수	특징
│Ｒ × Ｓ│＝│Ｒ│×│Ｓ│	Ｒ과Ｓ의 차수를 더한 값	교환/결합법칙 성립

Cartesian Product는 두 Relation의 구조가 달라도 가능하다.

Pure Relational Operator

순수 관계 연산자

• Relation의 구조와 특성을 이용하는 연산자이다.

SELECTION

PROJECTION

JOIN

DIVISION

RENAME

Bag vs Set

     초기 DBMS는 Bag을 이용한 data modeling을 하였다.
     Bag은 한마디로, 중복을 허용하는 집합 개념이다.
     그렇기 때문에 implementation 관점에서, 
     Set을 이용한 것보다 효율이 좋다.(두 Relation을 합칠 경우
     복사해서 붙여넣기만 하면 된다.)
     현재는 Data의 종류에 따라 저장 방법이 매우 다르므로
     이 두가지를 적절히 사용한다! ( All과 Distinct 개념 )

Combining Issues

Ordering

아무 조건(Predicate)이 없는 연산들은, 그 순서대로(괄호가 있다면 괄호부터) 행하면 되지만,
위에서 살펴본 Selection, Theta Join 등의 다양한 조건들을 갖는 연산들은
어떤 순서로 조건을 만족시키는 지 정하는 것이 좋다.

• 예를 들어, 두 릴레이션 R1, R2를 ∧(AND)가 포함된 Theta join을 한다고 가정하자. 이 때 AND 양옆의 조건들을
  먼저 행하고 합칠 것이냐, 아니면 Cartesian Product 등으로 먼저 합친 뒤 조건을 행할 것이냐
  하는 등의 issue를 말할 수 있겠다.
  

이러한 것들은 Optimizer가 다양한 비용, 공간, 시간 등을 고려해 '적절히' 정한다.

A Linear Notation for Algebraic Expressions

대수식의 선형 표현법

• Assignment : 복잡한 표현들 대신, 빈 relation을 만들어 순차적 assignment에 따라 표현한다.
  1. Relation 이름, 괄호안에 column 리스트를 입력한다. 보통 마지막 결과 relation 이름은 Answer로 칭한다.
  2. Assignment 기호는 :=를 사용한다.
  3. 대수 표현을 우변에 작성한다.
• 이와 같은 작업을 행하면, 마치 C++의 Pseudocode처럼, 우측 대수를 좌측 relation에 대입한다.
  
  

예)

     Movies relation에서, 

     상영시간이 90분을 넘고 Fox사 배급인 영화의 제목과 개봉 년도를 찾아라.

     R(t,y,l,i,s,p) := σlength>90(Movies)
     S(t,y,l,i,s,p) := σstudioName='Fox'(Movies)
     T(t,y,l,i,s,p) := R ∩ S
     Answer(title, year) := π t,i(T)

The Relational Data Model

Data modeling

What is data modeling?

• 컴퓨터에 저장할 데이터의 구조를 논리적으로 표현하기 위한 행위.
• 주어진 개념으로부터 논리적인 데이터 모델을 구성하는 작업을 말하며,
  일반적으로 이를 물리적인 데이터베이스 모델로 환원하여 고객의 요구에 따라
  특정 정보 시스템의 데이터베이스에 반영하는 작업을 포함한다.
• DB구조 기반으로 데이터, 데이터 관계, 데이터 의미, 데이터 제약 등을 기술하기 위한 개념적 표현 방법.
• 시스템의 대상이 되는 업무를 분석하여 정보시스템으로 구성하는 과정에서 
  업무의 내용과 정보시스템의 모습을 적절한 표기법으로 표현하는 것.
  
  

즉, 추상적인 데이터베이스 구조를 가시적으로 구현화(형태화)시키는 것으로, 
데이터베이스 설계 시 어려움을 도와주는 등의 역할을 한다. 

Why do we use it?

• Leverage(파급력) : 계속 변화되는 데이터들을 변경하는 데 용이하다. 즉, 유지보수의 이점이 있다.
• Conciseness(간결한 표현) : 설계도면처럼, 가시적인 Diagram으로 표현하여
  복잡한 유저들의 요구를 쉽게, 직관적으로 이해할 수 있다.
• Data Quality(품질) : 데이터들의 중복, 비유연성, 비일관성 등 기존 file system의
  단점들을 극복할 수 있다.
  
  

3 Steps to data modeling

아래로 내려올수록 구체적이며 위에 있을수록 추상적이다.

Relational Data Model

About Relation

• Data를 담은 2차원 Table, ROW(행)과 COLUMN(열)로 이루어진다.
  
• Relation의 특징
  
  1. 튜플의 유일성, 무순서
     
     • 유일성 : 각각의 튜플을 식별할 수 있어야 한다. 즉, 릴레이션에서 애트리뷰트들의 값의 조합이 유니크 해야한다. 
       ( 물론 1개로도 각각의 튜플을 식별할 수 있어도 상관없다. )
       
     • 무순서 : 순서를 부여하면 오히려 품질을 떨어트릴 수 있다. 튜플의 순서는 가치판단의 기준이 되는 것이 아니기 때문이다. 
       
  2. 애트리뷰트들의 무순서, 원자값 
     
     • 무순서 : 마찬가지로, 필요한 속성을 사용자로 하여금 취사 선택하도록 설계되었다. 
       오히려 순서에 의미를 부여하면 변화에 취약하게 되어 유지보수 비용이 증가될 염려가 있다.
       
     • 원자값 : 속성의 값의 범위가 하나여야만 한다는 의미이다. 그렇지 않으면 역시 비용이 증가될 염려가 농후하다.
       
       

Then, What is RDM?

Relation을 이용한 Data model

데이터를 표현하는 방법 중 하나인 '데이터 모델'의 여러 갈래 중 하나이며
설계의 의미보단 '데이터를 어떻게 표현할까'하는 개념적 의미이다.

Issues about RDM

• 단순하며 유용하다. (실제로 DB implementation의 대부분이 RM 기반)
• SQL(Structured Query Language)이라는 high-level language를 이용하여 Relation의 Data를 원하는 대로, 쉽게 조작할 수 있다.
  
  

Design

• Design 측면에서는, E/R(Entity Relationship) 표기법을 기반으로,
  Entity(개체), Relationship(관계), Attribute(속성)들을 적절하게 
  RM 표기법으로 변형하여 Design 할 수 있다.
  
• 이러한 설계 방식으로 각 Relation 간의 제약(Constraint), 함수 종속(Functional Dependency), 
  Key 등을 명확하게 이해하고, 보다 정확한 Relation을 설계할 수 있다.
  
  

Structure of RDM

RDM은 그림과 같이 구성되어 있다.

Schemas

Data Model에 대해 이야기할 때 항상 'Schema(스키마)'를 언급한다.
Schema란, DB를 구성하는 레코드의 크기, 키(key), 레코드들의 관계(relationship), 
검색 방법 등 '자료를 저장하는 구조와 표현법을 정의한 것'이라고 칭할 수 있다.
relation 이름 뒤에 괄호로 묶어 표기하며 (예 : Movies(title, year, length, filmType))
Relational database schema (혹은 그냥 Database schema)라고 한다.

주의 : 여기서 attributes들은 list등의 레코드가 아니라 set이다 !

각 component 값들은 structure, set, list 등의 record 타입이 아닌, atomic해야 한다. 
또한 같은 column에 존재하는 component 값들 모두 같은 타입(이거나 정해진 값 중 하나)이어야 한다.

Relation은 tuple들의 set이기 때문에 제시된 tuple들의 '순서'는 중요하지 않다.
즉, tuple들의 순서가 바뀌어도 동일한 Relation으로 본다.
더 나아가 attribute들의 순서 역시 재배치할 수 있다.
하지만 데이터가 섞이거나 변경되는 일 없이 재배치해야 한다. 
결과적으로 각각의 tuple은 attribute 순서대로 정렬된다.
그러므로 그림과 같은 두 개의 Relation은 완전히 '같다' 라고 할 수 있다.

 

Schema vs Instance

스키마와 인스턴스의 구별은 확실히 해두자.
스키마는 Relation의 attribute와 name이며 대개 '변하지 않는다.'
반면, 인스턴스는 tuple의 집합으로 값이 바로바로 변한다.
디자인 시 인스턴스는 고려하지 않는다.
다만, 어떤 구조로 설계할 지만 고려하자.

Functional Dependencies

Constraint

E/R design을 Relational schema로 컨버팅 시 Application의 요구에만
Relational schema를 제공하면 큰 위험이 따를 수 있다. ( 바꾸기 쉽지 않음에도 불구하고 )
또한 별개로 빈번히 특정 제약(Constraint)에 얽매일 수밖에 없다. 이 때 생기는 제약들 중
가장 중요한 것은 'Functional dependency'(이하 FD)라고 불리는 unique-value 제약이다.
이 제약은, 중복을 제거하는 Database redesign에 있어 아주 위험할 수 있다.
이 밖에도, 도메인 제약조건(Domain constraint), 참조 무결성(Referential integrity) 등이 있다.

NULL value

널 값(null value)은 공백, 0, 길이가 0인 문자열들과는 다른, 말 그대로의
아직 입력되지 않은 데이터를 의미한다. RM에서 NULL 허용을 하면,
한 개의 Relation으로 모든 데이터를 표현할 수 있다는, 이론상으로 좋아보이지만
쿼리 및 갱신이 복잡해지며 제약 조건을 위배할 수 있다는 문제점도 따른다.
따라서, 일반적으로 NULL 값은 허용하지 않는 것이 좋다.

Definition of Functional Dependency

Relation R의 두 튜플 T1, T2에 대해 n개의 attribute(A1, A2, ... An)값이 같다면
T1, T2의 m개의 attribute(B1, B2, ... Bn)도 반드시 같은 값이다.
즉, An이 결정되면 그 값에 따른 Bn도 단 하나의 값으로 결정된다.

• 표기 : A1A2...An -> B1B2...Bn
  

Functional dependency의 'Functional'이란?

마치 정의역의 한 값을 대입하면 그에 해당하는 치역이 단 한 개만 나온다는
수학의 'function'과 같기 때문 ! 

Keys of Relations

Key란, 

1. Relation 내 다른 모든 attributes를 unique하게 결정하는(hold, identify) attribute(s)이다.
   즉, 두 개의 distinct한 tuple의 모든 attribute값들은 각각 다 다른값이다.
2. Key 외엔 다른 attribute를 unique하게 결정하는 다른 부분집합이 없어야 한다.
   즉, Key는 minimal해야 한다. (key가 하나의 attribute A를 포함하면, A를 key라고 한다.) 
   
   

Key is minimal, not minimum'''

• Primary key : 여러 key 중 user가 지정한 key를 일컫는다.
  (Implementation issue가 될 수 있기 때문에 underline으로 명확하게 표시함)
  
• Superkeys(Superset of key) : Key의 제약이 걸려있는 attribute(들).
  Key는 모두 Superkey이지만, Superkey이면 Key는 아니다. (minimal의 조건)
  
• Foreign key : 다른 Relation의 Primary key attribute를 참조하는 key로,
  참조 무결성 제약조건과 더불어 두 Relation들의 일관성을 유지하는 데 사용한다.
  또한 외래 키는 일종의 'key'개념이라고 보기엔 다소 무리가 있다.
  
  

혹자는 Key개념을 다르게 설명한다. 

Superkey 중 최소의 Key(s)를 
후보 키(Candidate Key)라고 따로 정의하기도 한다.

마침.

Overview of Database Management System

What is DB?

DATA vs INFORMATION 

• DATA : 단순한 관찰이나 측정 등의 수단을 통해 현실 세계로부터 수집된 사실이나 값.
• INFORMATION : 데이터 중에서도 조직화되고 체계화 된 데이터로서 의사 결정권자에게 의미를 제공하는 것. 
  
  

DATABASE 

• 체계화된 데이터들의 모임으로, 여러 응용 시스템들의 통합된 정보들을 저장하여 운영할 수 있는 공용 데이터들의 묶음. 
  
  

What is DBMS?

• 이러한 데이터베이스의 모든 액세스를 관리하는 응용 소프트 웨어.
  
• 데이터들을 정의, 조작, 제어 하는 기능을 가지고 있다.
  
  1. 정의 기능 : DB 생성 시 DB를 정의한다.
     
  2. 조작 기능 : 다수의 이용자들이 공동으로 이용(검색, 삽입, 삭제, 갱신)할 수 있다.
     
  3. 제어 기능 : 정확도와 보안성을 높인다.
     
     

DBMS의 기능에 따른 언어

• DDL (Data Definition Language)' : DB의 구조(Schema, Domain, Table, View, Index)를 정의하는 언어로, 
  DBA(Database Administrator)는 해당 attribute, domain, authority 등을 명확히 이해하고 결정해야 한다.
  

• DML (Data Manipulation Language) : DB사용자, 어플리케이션 등 다수의 user들이 DB에 대해
  검색(select), 삽입(insert), 삭제(delete), 갱신(update)등을 하게 하기 위한 언어.
  
  1. 절차식(Procedural) DML : "어떤" 데이터를 "어떻게" 구할 지 명세.
     
  2. 비절차식(Non-procedural) DML : 방법은 따로 명시하지 않음.
     

• DCL (Data Control Language) : DB에 접근하고 객체들을 사용하도록 권한을 주고 회수하는 언어.
  

정보의 검색을 담당하는 부분을 Query라 한다.

Transaction

* What is transaction?

• DBMS에서 데이터들의 상호작용이 일어나는데, 이러한 상호작용의 한 단위(unit of work)를 말한다.
• 성공과 실패가 분명해야하고, 상호 독립적이어야 하며 일관되고 믿을 수 있어야 한다.
• Logical Units of Work (LUW) 라고도 한다.
• 트랜잭션이 안전하게 수행된다는 것을 보장하기 위한 성질인 ACID가 있다. 
  (하지만 성능을 위해 이런 특성들이 종종 완화되곤 한다.)
  • Atomicity (원자성) : all-or-nothing 개념으로, 한 번 트랜잭션 수행이 시작되었다면 중간에 중단되지 않아야 한다.
  • Consistency (일관성) : valid state(고립 상태 : 동시에 수행되는 트랜잭션이 없는 걸 보장하는 상태)에서의 
    트랜잭션 수행이 데이터베이스의 일관성을 보존하여야 한다.
  • Isolation (고립성) : 여러 트랜잭션들이 동시에 수행되더라도 어느 하나가 마친 뒤에 
    다른 트랜잭션이 시작하는 것과 같이 되도록 보장해야 한다.
  • Durability (지속성) : 트랜잭션이 성공적으로 수행 완료되고 나면 
    트랜잭션에 의해 데이터베이스에 변경된 내용은 지속되어야 한다. (이것이 만약 시스템에 오류를 발생시키더라도) 
    

예)

ATM기에서의 계좌 이체를 한 트랜잭션으로 생각해보자. 

A계좌로부터 B계좌로 x원을 계좌이체하는 트랜잭션에서

1. A계좌에서 x원 만큼 차감
2. B계좌에서 x원 만큼 증가 (중략)
   
   이러한 단계들로 되어 있는데(차감한 순간 B 계좌로 넣어지는 것은 아니므로) 단계 1만 진행한 상태로 오류가 나
   트랜잭션이 중단되면 A계좌의 잔고는 차감된 상태이며 B계좌에는 잔고가 변화가 없는, 있어서는 안 될 사태가 생긴다.
   이 때 ACID의 원자성 보장의 필요성을 알 수 있다. 또한 무결성 제약조건 및 잔고의 합이 같아야 한다는 일관적인
   조건들로 보아 일관성 보장도 따른다. 

Query processor

• 파일 혹은 데이터베이스 접근을 위해 사용자의 조회 요구를 직접 사용될 수 있는 명령어로 변환시키는 프로그램 혹은 프로그래머.
• Query compiler, Execution engine 두 가지로 표현할 수 있다.
• Query compiler : 사용자의 query를 query plan, 즉 Low-level language로 번역해 주며 3가지 주 요소를 포함한다. 
  또한 작업들을 가장 빠르게 수행하기 위해 메타데이터/통계 등을 이용한다.
• Execution engine : 데이터를 관리/제어/조작 하기위해 버퍼에 넣어 사용한다. 
  액세스 충돌 및 lock을 피하기 위해 Scheduler, 데이터의 변화를 확실히 하기위해 Log manager가 필요하다.