[데이터베이스] 15. 자료구조 - 자료구조의 분류와 종류(스택, 큐, 데크, 트리, ...)

1. 자료구조의 분류

• 선형 구조 : 선형 리스트(배열), 연결 리스트, 스택, 데크, 큐
• 비선형 구조 : 트리, 그래프

2. 자료구조의 종류

2-1. 선형리스트

• 배열을 기반으로 구현한 리스트이다.

2-2. 연결리스트

• 메모리 동적 할당을 기반으로 구현한 리스트이다.
• 자료들을 임의의 기억공간에 기억시키되, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료구조이다.
• 노드의 삽입, 삭제 작업이 용이하다.
• 접근 속도가 느리다.
• 기억 공간이 연속적으로 놓여있지 않아도 저장이 가능하다.
• 연결을 위한 링크(포인터) 부분이 필요하기 때문에 기억공간 이용 효율이 좋지 않다.
• 연결 리스트 중에서 중간 노드의 연결이 끊어지면 다음 노드를 찾기 힘들다.

2-3. 스택(Stack)

• 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료구조이다.
• 가장 나중에 삽입된 자료가 가장 먼저 삭제되는 후입선출(LIFO; Last-In, First-Out) 방식으로 자료를 처리한다.
• TOP : Stack으로 할당된 기억공간에 가장 마지막으로 삽입된 자료가 기억된 위치를 가리키는 요소로 스텍 포인터라고도 한다.
• Bottom : 스택의 가장 밑바닥이다.
• PUSH : 스택에 자료를 입력하는 명령이다.
• POP : 스택에서 자료를 출력하는 명령이다.

• 부프로그램 호출 시 복귀주소를 저장할 때 이용한다.
• 함수 호출의 순서를 제어할 때 이용한다.
• 인터럽트가 발생하여 복귀주소를 저장할 때 이용한다.
• 후위 표기법(Postfix Notation)으로 표현된 산술식을 연산할 때 이용한다.
• 0 주소지정방식 명령어의 자료 저장 시 이용한다.
• 재귀(Recursive) 프로그램의 순서를 제어할 때 이용한다.
• 컴파일러를 이용한 언어 번역 시 이용한다.

2-4. 데크(Deque)

• 삽입과 삭제가 리스트의 양쪽 끝에서 모두 발생할 수 있는 자료구조이다.
• Double Ended Queue의 약자.
• 스택과 큐의 장점만 가져와서 구성한 것이다.
• 입력이 한쪽에서만 발생하고 출력은 양쪽에서 일어날 수 있는 입력 제한과 입력은 양쪽에서 일어나고 출력은 한쪽에서만 이루어지는 출력 제한이 있다.

입력 제한 데크(Scroll)

출력 제한 데크(Shelf)

2-5. 큐(Queue)

• 선형 리스트의 한쪽에서는 삽입 작업이 이루어지고 다른 한쪽에서는 삭제 작업이 이루어지도록 구성한 자료구조이다.
• 시작과 끝을 표시하는 두 개의 포인터가 있다.
• 가장 먼저 삽입된 자료가 가장 먼저 삭제되는 선입선출(FIFO; First-In, First-Out) 방식으로 처리한다.
• 프런트 포인터 : 가장 먼저 삽입된 자료의 기억공간을 가리키는 포인터로, 삭제 작업을 할 때 사용한다.
• 리어 포인터 : 가장 마지막에 삽입된 자료가 위치한 기억장소를 가리키는 포인터로, 삽입 작업을 할 때 사용한다.

• 창구 업무처럼 서비스 순서를 기다리는 등의 대기 행렬의 처리에 사용한다.
• 운영체제의 작업 스케줄링에 사용한다.

2-6. 트리(Tree)

• 정점(Node, 노드)과 간선(= edge, 엣지)을 이용하여 사이클을 이루지 않도록 구성한 그래프의 특수한 형태이다.
• 가족의 계보, 연산 수식, 회사의 조직 구조도, 히프(Heap) 등을 표현하기에 적합하다.

• 노드(Node) : 트리의 기본 요소로서 자료 항목과 다른 항목에 대한 가지를 합친 것
• 근 노드(Root Node) : 트리의 맨 위에 있는 노드.
• 디그리(Degree, 차수) : 각 노드에서 뻗어나온 가지의 수.
• 트리의 디그리 : 노드들의 디그리 중에서 가장 많은 수.
• 단말 노드(Terminal Node) = 잎 노드(Leaf Node) : 자식이 하나도 없는 노드로 디그리가 0인 노드.
• 비단말 노드(Non-Terminal Node) : 자식이 하나라도 있는 노드로 디그리가 0이 아닌 노드.
• 자식 노드(Son Node, Children Node) : 어떤 노드에 연결된 다음 레벨의 노드들.
• 부모 노드(Parent Node) : 어떤 노드에 연결된 이전 레벨의 노드.
• 형제 노드(Brother Node, Sibling) : 동일한 부모를 갖는 노드들.
• Level : 근 노드의 Level을 1로 가정한 후 어떤 Level이 L이면 자식 노드는 L+1이다
• 깊이(Depth, Height) : 어떤 Tree에서 노드가 가질 수 있는 최대의 레벨.

* 이진 트리의 운행
: 이진트리란 한 노드가 최대 2개까지 자식 노드를 가지는 트리를 말하며, 첫 번째 노드인 부모는 Root, 자식 노드는 왼쪽(Left), 오른쪽(Right)라고 불린다.

- 전위 운행(Pre-order) : Root → Left → Right 순서로 운행.
- 중위 운행(In-order) : Left → Root → Right 순으로 운행.
- 후위 운행(Post-order) : Left → Right → Root 순으로 운행.

전위 운행 순서 : A → B →D → E → G → H → C → F → I

중위 운행 순서 : D → B → G → E → H → A → C →F → I

후위 운행 순서 : D → G → H → E→ B → I → F → C → A

2-7. 그래프(Graph)

• 버텍스(Vertex, =노드)와 아크(Arc, =엣지)로 구성되어 있으며 다른 버텍스로부터 오는 아크의 개수를 In-degree, 다른 버텍스로 가는 아크의 개수를 Out-degree라고 부른다.
• 트리의 노드가 하나의 In-degree만 가지는 반면, 그래프의 버텍스는 하나 이상의 In-degree를 가질 수 있다.

[데이터베이스] 14. 트랜잭션의 병헹 제어(Concurrency Control)와 DB 회복(Recovery)

1. 병행 제어(Concurrency Control)

1-1. 병행 제어란?

• 동시에 여러 개의 트랜잭션을 병행 수행시킬 때, 데이터베이스의 일관성이 파괴되지 않도록, 트랜잭션의 독립성을 유지할 수 있도록 트랜잭션 간의 상호작용을 제어하는 것이다.

1-2. 병행 수행의 문제점

• 갱신 분실(Lost Update) : 2개 이상의 트랜잭션이 같은 자료를 공유하여 갱신할 때 갱신 결과의 일부가 없어지는 현상.
• 비완료 의존성(Uncommitted Dependency) : 하나의 트랜잭션 수행이 실패한 후 회복되기 전에 다른 트랜잭션이 실패한 갱신 결과를 참조하는 현상.
• 모순성(Inconsistency) : 두 개의 트랜잭션이 병행 수행될 때 원치 않는 자료를 이용함으로써 발생하는 문제.
• 연쇄 복귀(Cascading Rollback) : 병행 수행되던 트랜잭션들 중 어느 하나에 문제가 생겨 롤백하는 경우 다른 트랜잭션도 함께 롤백되는 현상.

1-3. 병행 제어의 목적

• 데이터베이스의 공유를 최대화한다.
• 시스템의 활용도를 최대화한다.
• 데이터베이스의 일관성을 유지한다.
• 사용자에 대한 응답 시간을 최소화한다.

1-4. 로킹(Locking)

• 트랜잭션이 사용하는 DB내의 데이터를 다른 트랜잭션이 접근하지 못하게 Lock을 설정해 접근을 제어, 상호 배제하는 것이다.
• 트랜잭션들이 어떤 로킹 단위를 액세스하기 전에 Lock을 요청해서 Lock이 허락되어야만 그 로킹 단위를 액세스할 수 있도록 하는 기법이다.

1-5. 로킹 단위(Locking Granularity)

• 병행 제어에서 한꺼번에 로킹할 수 있는 데이터 단위이다.
• 데이터베이스, 파일, 레코드, 필드 등은 로킹 단위가 될 수 있다.
• 로킹 단위가 크면 로크 수가 작아 관리하기 쉽지만 병행성 수준이 낮아지고, 로킹 단위가 작으면 로크 수가 많아 관리하기 복잡하지만 병행성 수준이 높아진다.

2. 회복(Recovery)

1-1. 회복이란?

• 회복은 트랜잭션들의 처리를 수행하는 도중 장애가 발생하여 데이터베이스가 손상되었을 때 손상되기 이전의 정상 상태로 복구시키는 작업이다.

1-2. 장애의 유형

• 트랜잭션 장애 : 입력 데이터 오류, 불명확한 데이터, 시스템 자원 요구의 과다 등 트랜잭션 내부의 비정상적인 상황으로 인하여 프로그램 실행이 중지되는 현상이다.
• 시스템 장애 : 데이터베이스에 손상을 입히지는 않으나 하드웨어 오동작, 소프트웨어의 손상, 교착 상태 등에 의해 모든 트랜잭션의 연속적인 수행에 장애를 주는 현상이다.
• 미디어 장애 : 저장장치인 디스크 블록의 손상이나 디스크 헤드의 충돌 등에 의해 데이터베이스의 일부 또는 전부가 물리적으로 손상된 상태이다.

1-3. 회복 관리기(Recovery Management)

• DBMS의 구성 요소이다.
• 트랜잭션 실행이 성고적으로 완료되지 못하면 트랜잭션이 데이터베이승 ㅔ만들었던 모든 변화를 취소(Undo) 시키고 트랜잭션 수행 이전의 원래 상태로 복구하는 역할을 한다.
• 메모리 덤프, 로그를 이용하여 수행한다.

1-4. 회복 기법의 종류

• 연기 갱신 기법(Deferred Update)
• 즉각 갱신 기법(Immediate Update)
• 그림자 페이지 대체 기법(Shadow Paging)
• 검사점 기법(Check Point)

[데이터베이스] 13. 트랜잭션이란? (트랜잭션의 정의, 특성)

1. 트랜잭션의 정의

• 사용자가 제기한 데이터베이스의 작업 수행을 위한 데이터 조작의 집단
• 하나의 트랜잭션은 Commit 되거나 Rollback 된다.
• 트랜잭션은 일반적으로 병행수행 제어 및 회복의 기본 단위가 된다.

2. 트랜잭션의 특성

2-1. 원자성(Atomicity)

• 트랜잭션의 연산은 데이터베이스에 모두 반영되든지 아니면 전혀 반영되지 않아야 한다.
• 즉, 트랜잭션 내의 모든 명령은 반드시 완벽히 수행되어야 하며, 모두가 완벽히 수행되지 않고 어느 하나라도 에러가 발생하면 트랜잭션 전부가 취소되어야 한다.

2-2. 일관성(Consistency)

• 트랜잭션이 그 실행을 성공적으로 완료하면 언제나 일관성 있는 데이터베이스 상태로 변환한다.
• 시스템이 가지고 있는 고정 요소는 트랜잭션 수행 전과 수행 완료 후의 상태가 같아야 한다.

2-3. 독립성, 격리성(Isolation)

• 둘 이상의 트랜잭션이 동시에 실행되는 경우, 어느 하나의 트랜잭션 실행 중에 다른 트랜잭션의 연산이 끼어들 수 없다.
• 수행 중인 트랜잭션은 완전히 완료될 때까지 다른 트랜잭션에서 수행 결과를 참조할 수 없다.

2-4. 영속성, 지속성(Durability)

• 성공적으로 완료된 트랜잭션의 결과는 영구적으로 유지되어야 한다.

3. 트랜잭션의 원자성을 위한 연산

• COMMIT

- 트랜잭션의 성공적인 종료로 데이터베이스가 다시 일관된 상태에 있을 때 이 트랜잭션이 행한 갱신 연산이 완료된 것을 트랜잭션 관리자에게 알려주는 연산이다.
- COMMIT이 성공적으로 이루어지면 데이터베이스에 대한 갱신 작업이 영구적으로 반영된다.
- 명시적 COMMIT(Explicit Commit) : 데이터베이스 사용자가 COMMIT 명령을 직접 사용.
- 암시적 COMMIT(Implicit Commit) : DBMS가 사용자 session 종료 시 자동으로 COMMIT.

• ROLLBACK

- 트랜잭션의 비정상적인 종료로 데이터베이스이 비일관적인 상태에 놓였을 때, 이 트랜잭션의 일부가 정상적으로 처리되었더라도 트랜잭션의 원자성을 구현하기 위해 이 트랜잭션이 행한 모든 연산을 취소시키는 연산이다.

4. 트랜잭션의 상태

• 활동(Active) : 트랜잭션이 실행 중에 있는 상태.
• 장애(Failed) : 트랜잭션 실행에 오류가 발생하여 중단된 상태.
• 철회(Aborted) : 트랜잭션이 비정상적으로 종료되어 ROLLBACK 연산을 수행한 상태.
• 부분 완료(Partially Committed) : 트랜잭션의 마지막 연산까지 실행했지만, COMMIT 연산이 실행되기 직전의 상태.
• 완료(Committed) : 트랜잭션이 성공적으로 종료되어 COMMIT 연산을 실행한 후의 상태.

[데이터베이스] 12. 뷰 (View)

1. 뷰(View) 란?

• 사용자에게 접근이 허용된 자료만을 제한적으로 보여주기 위해 하나 이상의 기본 테이블로부터 유도된 가상 테이블이다.
• 저장장치 내에 물리적으로 존재하지 않지만, 사용자에게는 존재하는 것처럼 간주된다.
• 데이터 보정 작업, 처리 과정 시험 등 임시 작업을 위한 용도로 활용된다.

2. 뷰(View)의 특징

• 기본 테이블로부터 유도된 테이블이기 때문에 기본 테이블과 같은 형태의 구조를 가진다.
• 조작도 기본 테이블과 거의 같다.
• 가상 테이블이기 때문에 물리적으로 구현되어 있지 않다.
• 필요한 데이터만 뷰로 정의해서 처리할 수 있기 때문에 관리가 용이하고 명령문이 간단해진다.
• Join문의 사용을 최소화하여 사용상의 편의성을 최대화 한다.
• 뷰를 통해서만 데이터에 접근하게 하면 뷰에 나타나지 않는 데이터를 안전하게 보호할 수 있다.
• 기본 테이블의 기본키를 포함한 속성(Attribute)의 집합으로 뷰를 구성해야만 삽입, 삭제, 갱신 연산이 가능하다.
• 정의된 뷰는 다른 뷰의 정의에 기초가 될 수 있다.
• 하나의 뷰를 삭제하면 그 뷰를 기초로 정의된 다른 뷰도 자동으로 삭제된다.

3. 뷰(View)의 장점

• 논리적 데이터 독립성을 제공한다.
• 동일 데이터에 대해 동시에 여러 사용자의 응용이나 요구를 지원해준다.
• 사용자의 데이터 관리를 간단하게 해준다.
• 접근 제어를 통한 자동 보안이 제공된다.

4. 뷰(View)의 단점

• 독립적인 인덱스를 가질 수 없다.
• 뷰는 ALTER문을 이용하여 정의를 변경할 수 없기 때문에 삭제 후 다시 생성해야 한다.
• 뷰로 구성된 내용에 대한 삽입, 삭제, 갱신 연산에 제약이 따른다.

5. 뷰(View)의 생성과 삭제

5-1. 뷰 정의문

CREATE VIEW 뷰이름(속성이름1, 속성이름2, ...) AS SELECT문 ;

• SSELECT문을 부질의로 사용하여 SELECT문의 결과로서 뷰를 생성한다.
• 부질의로서의 SELECT문에는 UNION이나 ORDER BY절을 사용할 수 없다.
• 속성 이름을 생략하면 SELECT문의 속성 이름이 자동으로 사용된다.

5-2. 뷰 삭제문

DROP VIEW 뷰이름 ;

ex) DROP VIEW 뷰입니다 RESTRICT

• RESTRICT : 뷰를 다른 곳에서 참조하고 있으면 삭제가 취소된다.
• CASCADE : 뷰를 참조하는 다른 뷰나 제약 조건까지 모두 삭제된다.

[데이터베이스] 11. 데이터 사전이란? (시스템 카탈로그의 정의, 특징)

1. 시스템 카탈로그란?

• 데이터베이스에 포함되는 모든 데이터 객체들에 대한 정의나 명세에 관한 정보를 유지, 관리하는 시스템 테이블이다.
• 데이터베이스 관리 시스템의 기능 수행을 위해 필요한 데이터베이스 및 사용자에 관한 모든 정보를 포함하는 메타 데이터베이스이다.
• 데이터 정의어의 결과로 구성되는 기본 테이블, 뷰, 인덱스, 패키지, 접근 권한 등의 데이터베이스 구조 및 통계 정보를 저장한다.
• 카탈로그들이 생성되면 자료 사전(Data Dictionary)에 저장되기 때문에 좁은 의미로는 카탈로그를 자료 사전이라고도 한다.
• 카탈로그에 저장된 정보를 메타 데이터(스키마)라고 한다.

2. 시스템 카탈로그의 특징

• 카탈로그 자체도 시스템 테이블로 구성되어 있기 때문에 일반 이용자도 SQL을 이용하여 내용을 검색해 볼 수 있다.
• INSERT, DELETE, UPDATE문으로 갱신하는 것은 허용하지 않는다.
• DBMS가 스스로 생성하고 유지한다.
• 카탈로그는 사용자가 SQL문을 실행시켜 기본 테이블, 뷰, 인덱스 등에 변화를 주면 시스템이 자동으로 갱신된다.

[데이터베이스] 10. 정규화란? (정규화의 정의, 목적, 과정)

1. 정규화(Normalization)란?

• 데이터 중복성 및 종속성 배체의 원칙을 공식화한 이론이다.
• 잘못 설계된 관계형 스키마를 더 작은 속성의 세트로 쪼개어 바람직한 스키마로 만들어 가는 과정이다.
• 정규형에는 제1정규형, 제2정규형, 제3정규형, BCNF형, 제4정규형, 제5정규형이 있으며, 차수가 높아질수록 만족시켜야 할 제약 조건이 늘어난다.
• 정규화는 데이터베이스의 논리적 설계 단계에서 수행한다.
• 정규화는 논리적 처리 및 품질에 큰 영향을 미친다.

2. 비정규화 시 일어나는 문제, 이상(Anomaly)

2-1. 이상(Anomaly)의 개념

• 정규화를 거치지 않은 데이터베이스 내에 데이터들이 불필요하게 중복되어 릴레이션 조작 시 발생하는 예기치 않은 현상이다.
• 사용자의 의도와는 다르게 다른 데이터가 삽입, 삭제, 갱신되는 곤란한 현상이다.
• 속성들 간에 존재하는 여러 종속 관계를 하나의 릴레이션에 표현하기 때문에 이상이 발생한다.

2-2. 이상(Anomaly)의 종류

3. 정규화(Normalization)의 목적

• 데이터 구조의 안정성을 최대화하기 위함이다.
• 어떠한 릴레이션이라도 데이터베이스 내에서 표현할 수 있게 만든다.
• 효과적인 검색 알고리즘을 생성할 수 있다.
• 중복을 배제하여 삽입, 삭제, 갱신 이상의 발생을 방지한다.
• 데이터 삽입 시 릴레이션을 재구성할 필요성을 줄인다.

4. 정규화(Normalization) 과정

* 함수적 종속 관계
: 어떤 릴레이션 R에서 속성 X의 값 각각에 대해 속성 Y의 값이 하나만 연관되는 관계를 Y는 X에 함수 종속적이라고 하며, X(결정자) → Y(종속자)로 표현한다.
ex) '수강' 릴레이션이 학번, 이름, 과목명 속성으로 구성되어 있을 때, 학번이 결정되면 과목명에 상관없이 학번에는 항상 같은 이름이 대응된다. 학번에 따라 이름이 결정될 때 '학번 → 이름' 으로 표현한다.

* 이행적 종속 관계
: A → B 이고, B → C 일 때, A → C 를 만족하는 관계.

[데이터베이스] 9. 관계형 데이터 모델 - 형식어(관계 해석, 관계 대수와 연산)

* 관계 해석과 관계 대수는 관계 데이터 모델에서 지원되는 두 가지 정형적인 언어이다.
* 관계 대수나 관계 해석은 상용 DBMS에서 직접적으로 사용되지는 않지만, SQL을 비롯한 대부분의 상용 데이터베이스 언어의 원리를 제공한다.

1. 관계 해석(Relational Calculus)

• 선언적, 비절차적 언어.
• 원하는 데이터만 명시하고 질의를 어떻게 수행할 것인가는 명시하지 않는다.

2. 관계 대수(Relational Algebra)

• 절차적 언어.
• 어떻게 질의를 수행할 것인가를 명시한다.
• 상용 RDBMS들에서 널리 사용되는 SQL의 이론적인 기초.
• 관계 대수는 SQL을 구현하고 최적화하기 위해 DBMS의 내부 언어로도 사용된다.
• 관계형 데이터 모델의 제안자 E.F.Codd 박사가 릴레이션의 처리에 필요한 일련의 연산자들을 모아서 관계 대수라고 명명했다.
• 관계 대수 연산은 한 개의 릴레이션에서 특정 조건에 맞는 튜플들을 추출해내거나 여러 릴레이션을 합해 새로운 릴레이션을 만드는 질의문을 작성하는데 사용된다.
• 관계 대수는 크게 일반집합연산과 순수관계연산으로 나눌 수 있다.

3. 일반집합연산

3-1. 합집합(Union)

• R1또는 R2에 속하는 튜플의 집합.

ex) R1={1, 2} R2{1, 2, 3} 일 때 T={1, 2, 3}

3-2. 교집합(Intersection)

• R1과 R2 모두에 속하는 튜플의 집합.

ex) R1={1, 2} R2{1, 2, 3} 일 때 T={1, 2}

3-3. 차집합(Set Difference)

• R1과 R2 모두에 속하는 튜플을 제외한 집합.

ex) R1={1, 2} R2{1, 2, 3} 일 때 T={3}

3-4. 카티션 프로덕트(Cartesian Product) = 교차곱

• 연산하려는 각 릴레이션의 카디날리티(튜플의 개수)의 곱과 연산하려는 각 릴레이션의 차수(속성의 개수)의 합으로 이루어진 릴레이션.
• 연산되는 튜플들로 조합이 가능한 모든 경우 수로 이루어진 릴레이션.
• 카티션 곱의 결과는 릴레이션의 크기가 매우 클 수 있다.

ex) R1의 카디날리티가 4이며 차수가 3, R2의 카디날리티가 3이며 차수가 1인 경우 R1 X R2 = 속성 4, 행 12개로 이루어진 릴레이션

4. 순수관계연산

4-1. Selection(Restriction)

• 릴레이션에서 셀렉션 조건(Selection Condition, Predicate)을 만족하는 튜플들의 부분 집합을 구하여 새로운 릴레이션을 만드는 연산.
• 하나의 입력 릴레이션에 적용되므로 단항 연산자.
• 셀렉션의 결과 릴레이션의 차수는 입력 릴레이션의 차수와 같다.
• 결과 릴레이션의 카디날리티는 항상 원래 릴레이션의 카디날리티보다 작거나 같다.
• 릴레이션 레코드(행)에 해당하는 튜플을 구하는 것이므로 수평 연산이라고도 한다.
• σ  = 시그마

4-2. Projection

• 주어진 릴레이션에서 속성 리스트에 제시된 속성(Attribute)만을 추출하는 연산.
• 릴레이션의 열에 해당하는 속성만을 추출하는 것이므로 수직 연산이라고도 한다.

4-3. Join

• 공통 속성을 중심으로 2개의 릴레이션을 하나로 합쳐 새로운 릴레이션을 만드는 연산.
• 관계 데이터베이스에서 두 개 이상의 릴레이션드르이 관계를 다루는데 중요한 연산자.
• 조인의 방법으로는 세타 조인(Theta Join), 동등 조인(Equi Join), 자연 조인(Natural Join), 외부 조인(Outer Join), 세미 조인(Semi Join) 등이 있다.

4-4. Division

• 릴레이션에서 조건에 맞는 속성을 선택하여 제거한 후 새로운 튜플을 구성하는 연산.