가전제품 이것저것 이야기

0. 프로세스는 다음의 순서로 자원을 이용한다.

자원 요청 -> 사용(점유) -> 해제

1. 교착 상태란?

: 프로세스에 의해 발생할 사건(Event)을 프로세스들이 서로 기다리고 있는 상태이다.

둘 이상의 작업이 보류 상태에 놓여 자원을 이용하기 위해 서로 기다린다.

2. 교착 상태 발생의 네가지 조건

1) 상호배제 : 한 번에 한 프로세스만 해당 자원을 사용할 수 있어야 한다.

2) 점유와 대기 : 최소한 자원 하나를 보유하고, 다른 프로세스에 할당된 자원을 얻기 위해 기다리는 프로세스가 있어야 한다.

3) 비선점 : 자원을 갖에로 빼앗을 수 없다.

4) 순환대기(환형대기) : 교착상태를 따라가면 원이 만들어진다.

-> 이 중 하나라도 발생하지 않으면 교착 상태가 발생하지 않는다 !

2. 자원 할당 그래프, G = (V, E)

V = 정점들의 집합 (시스템 내의 모든 자원 R 과 프로세스 P )

E = 간선들의 집합( 요청 / 할당 간선 )

ex 1)

-> P1은 R2를 보유하고 있고, R1을 기다리고 있다.

-> P2는 R1을 보유하고 있고, R3를 기다리고 있다.

-> P3는 R3 하나를 보유하고 있다.

< 교착 상태 발생 여부 확인 >

상호 배제 : O

점유와 대기 : X -> P3가 다른 프로세스에 할당된 자원을 기다리고 있지 않다.

비선점 : O

순환대기 : X

-> 순환대기를 만족하지 않기 때문에 교착상태가 아니다.

ex 2)

: P1 -> R1 -> P2 -> R3 -> P3 ->R2 -> P1

: P2 -> R3 -> P3 -> R2 -> P2

-> 두 개의 사이클 

< 교착 상태 발생 여부 확인 >

상호 배제 : O

점유와 대기 : O

비선점 : O

순환대기 : O

-> 모든 조건을 만족하기 때문에 교착상태이다.

ex 3)

: 사이클이 있지만, 모든 프로세스가 참여하는 것은 아니므로 교착상태가 아니다.

< 교착 상태 발생 여부 확인 >

상호 배제 : O

점유와 대기 : X -> P2, P4가 만족하지 않는다.

비선점 : O

순환대기 : X

-> 교착상태가 아니다.

3. 교착 상태 처리 방법

1) 운영체제가 관여하여 프로토콜을 사용한다.

- 교착 상태 예방 (정적 - 현재 상황에 영향을 안 받음 )

- 교착 상태 회피 (동적 - 현재 상황에 영향을 받음 )

2) 운영체제가 교착 상태에 들어가도록 허용한 다음 회복한다.

- 교착 상태 탐지 및 회복 (어렵고 비용 많이 소요)

3) 교착 상태가 시스템에서 발생하지 않은 것처럼 무시한다. ( 운영체제가 관여하지 않는다. 제일 많이 사용하는 방법 )

- UNIX 등 대부분의 운영체제에서 사용한다.

- 응용 프로그래머가 자체적으로 해결한다.

4. 교착 상태 예방

: 교착 상태 네 가지 조건 중 하나만 성립하지 않도록 한다.

1) 상호 배제 

- 결정성 (같은 입력값에 대해 항상 같은 결과가 나오는 것)이 위배될 가능성이 높다.

- 주변 장치의 특성 때문에 상호 배제를 피하기는 힘들다.

2) 점유와 대기

: 프로세스가 자원을 요청할 때에는 언제나 다른 자원을 점유하지 않도록 한다.

- 각 프로세스는 수행 전에 필요한 모든 자원을 요청하여 할당한다. (자원 활용의 효율성 감소)

- 프로세스가 자원을 가지고 있지 않은 상태에서만 자원 요청을 할 수 있도록 허용한다. (기아 상태 유발)

3) 비선점

: 선점을 허용한다.

- 구현 복잡

4) 순환 대기

: 모든 자원에 번호를 부여한다.

: 한 프로세스는 자신이 가진 자원보다 번호가 큰 것만 요청한다. 

- 새로운 자원이 시스템에 추가되면 프로그램과 시스템을 재구성해야 한다.

- 사용자가 손쉽게 응용 프로그램을 작성하는데 어려움이 있다.

5. 교착 상태 회피

: 교착 상태 예방보다 덜 엄격한 조건을 요구한다. 자원의 효율성도 향상된다.  비행기 테러를 방지하기 위해

- 예방 : 자원 사용 제약 조건을 정적으로 사전에 설정한다. (상대적으로 경직)   비행기를 안 타고 배를 탄다.

- 회피 : 자원 사용 제약 조건을 동적으로 실행중에 결정한다. (상대적으로 유연)   탑승자에 아랍 사람이 있는지 여부로 탑승여부 결정한다.

: 자원 요청 시, 자원할당으로 인해 교착상태 유발 가능성 검사한다.

- 유발 가능성이 전혀 없으면 안정 상태, 자원 할당

- 유발 가능성이 존재하면 불안정 상태, 자원 할당 연기

1) 안정 상태 vs 불안정 상태

시스템이 안전 상태에 있다는 것은 교착 상태가 유발되지 않았다는 것이다.

불안정 상태에서 안정 순열이 존재하지 않을 경우, 교착 상태 가능성이 존재한다.

교착상태 회피란?

시스템이 불안정 상태가 아님을 보장하는 것

2) 안정 상태

: 안정 순열의 존재를 의미한다.

안정 순열 <P1, P0, P2>

3) 불안정 상태

: 사용 가능한 자원 1개를 어느 프로세스에 할당해도 프로세스를 만족시킬 수 없다.

만약, P2가 자원 1개를 더 요구할 경우,

P1 종료 이후 잔여량이 4로 종료시킬 수 있는 프로세스가 없어 불안정 상태에 놓이게 된다.

6. 자원 할당 그래프 알고리즘을 활용해보자

예약 간선 : 프로세스가 자원을 요청할 것을 의미한다. 점선으로 표시한다.

예약 간선은 프로세스가 자원을 요청할 때에 요청 간선으로 변환된다.

자원은 시스템에서 미리 예약되어야 한다.

- 자원 할당 후에 사이클이 존재하면 불완전 상태이다.

1. 물리적 데이터베이스

관계형 데이터베이스의 테이블과 레코드들은 디스크에 저장된다.

운영체제가 관리하는 파일 시스템을 이용한다.

- 기본 저장 구조 : 파일

- 입출력 단위 : 블록 (512 bytes ~ 수천 bytes)

2. 테이블의 물리적 저장 구조

파일 : 하나 이상의 테이블들을 저장

블록 : 하나 이상의 레코드들을 저장

각 블록은 하나의 테이블에 속한다.

3. 블록 내 레코드 저장 방식

1) 고정 길이로 저장된 레코드

-> 전체길이 = 28 x 5 = 140 bytes 

2) 가변 길이로 저장된 레코드

-> 전체 길이 : 90 bytes(한 단어당 2byte 가정)

4. 클러스터링

: 자주 검색되는 필드를 기준으로 관련된 레코드들을 같은 블록이나 인접한 블록에 저장하여 검색 성능을 높이는 방법이다.

ex) credit 필드를 기준으로 클러스터링

5. 인덱스

: 레코드에 대한 물리적 저장 위치를 별도로 기록한다.

- 레코드가 저장된 위치를 빨리 찾기 위해 사용한다.

1) 인덱스의 구조

- 인덱스 엔트리 : (검색 키, 주소) 쌍 

- 검색 키 : 테이블에 속한 한 개 이상의 필드 값들이다. 

- course 테이블의 Title 필드에 대한 인덱스이다.

2) SQL 질의와 인덱스

ex 1) 인덱스가 생성된 필드에 대한 조건을 포함하는 질의 처리 시 활용 예

: student 테이블의 레코드 수가 10,000개, dept_id가 '920'인 레코드가 500개라고 가정한다.

SELECT *
FROM STUDENT
WHERE DEPT_ID = '920' AND ADDRESS = '서울';

- 인덱스가 없을 경우,

모든 레코드를 순차적으로 검색해야 하므로 10,000개의 레코드를 모두 검색해야 한다.

- dept_id 필드에 인덱스가 있을 경우,

dept_id가 '920'인 레코드들만 검색 가능하다. -> 500개의 레코드만 검색하면 된다.

ex 2) Join 연산의 효율적인 처리

student 테이블의 레코드 수가 10,000개, department 테이블의 레코드 수가 100개라고 가정한다.

SELECT COUNT(*)
FROM STUDENT S, DEPARTMENT D
WHERE ADDRESS = '서울' AND S.DEPT_ID = D.DEPT_ID;

- 인덱스가 없을 경우,

: 조인 연산을 위해 student 와 department 테이블을 모두 순차적으로 검색해야 한다.

-> 시간 비용 : 10,000 x 100 

- student 테이블에 dept_id 필드에 대한 인덱스가 구축되어 있다면,

: department 테이블을 순차적으로 조회하면서 

각 레코드의 dept_id 값에 대해 위 인덱스를 사용하여 student 테이블에대응되는 레코드를 직접 조회한다.

-> 시간 비용 : 10,000 + 100

ex 3) 인덱스 만을 이용한 질의 처리

SELECT DEPT_ID, COUNT(*)
FROM STUDENT
GROUP BY DEPT_ID

- 인덱스가 없을 경우,

student 테이블의 모든 레코드를 조회해야 한다.

- student 테이블에 dept_id 필드에 대한 인덱스가 있을 경우,

인덱스에서 각 dept_id 값에 대한 인덱스 엔트리 개수를 세면 된다.

테이블에 접근할 필요도 없다.

3) 기본 키와 인덱스

: 기본 키에 대해서는 대부분의 DBMS가 자동으로 인덱스를 생성한다.

< 인덱스의 장단점 >

장점

- 검색 속도 향상

단점

- 테이블에 레코드를 삽입, 삭제, 수정 시 인덱스도 갱신이 필요하다.

- 인덱스의 개수가 많으면 삽입, 삭제, 수정 연산 속도가 저하된다.

- 인덱스를 저장하기 위한 디스크 공간이 필요하다.

-> 질의(검색) 시간 및 빈도, 삽입/삭제/수정 시간 및 빈도, 저장 공간의 크기 등을 종합적으로 고려하여 결정해야 한다.

1. 정규화 란?

: 불필요한 데이터 중복을 피하기 위해 스키마를 분해하는 과정

: 함수적 종속이 중요한 역할을 함

정규화의 효과

: 이상현상 방지 , 데이터 중복으로 인한 문제 해결

단, 함수적 종속이 유지되도록 데이터베이스를 설계해야 함

2. 정규형

: 각 단계별 정규화 과정을 통해 분해된 테이블들의 구조

< 테이블의 분해 조건 >

1) 종속성 보존 분해

: 분해되기 전의 함수적 종속들이 분해 후에도 유지되어야 함

테이블 R이 R1, R2 로 분해되었을 경우,

{FD(R1) U FD(R2)} = FD(R) 을 만족할 때 종속성이 보존된다 고 한다.

2) 무손실 조인 분해

테이블 R이 R1, R2 로 분해되었을 경우, 

ex) 무손실 조인 분해의 예

ex) 손실 조인 분해의 예

3. 1차 정규형

1) 정의

: 모든 도메인이 원자값으로만 구성되어 있을 때  

( 관계형 데이터 모델의 정의를 따르는 모든 테이블은 1차 정규형이다. )

2) 1차 정규형의 문제점

: 삽입, 삭제, 수정 이상

3) 문제의 원인

부분 종속 : 키가 아닌 필드(A)가 피의 일부인 필드(X) 에 함수적으로 종속되는 경우

ex) 

4. 2차 정규형

: 부분 종속의 제거

BUT ! 부분 종속의 제거하였다고 하더라도, 추가적인 부분 종속이 남아있는지 확인해야 한다.

+ 테이블을 정규화하더라도 함수적 종속이 그대로 유지된다.

즉, 2차 정규형은 종속성 보존 분해가 지켜진다.

1) 2차 정규형 정의

: 테이블 R에서 키가 아닌 모든 필드가 키에 함수적으로 종속되며, 부분 종속이 존재하지 않으면 2차 정규형이다.

- 하나의 필드가 키가 되는 경우는 모두 2차 정규형이다.

- 부분 종속에 의한 (삽입/삭제/수정) 이상현상이 발생하지 않는다.

2) 2차 정규형의 문제

: 아직도 삽입 / 삭제 / 수정 이상현상이 존재(부분 종속으로 인한 문제 제외)

삽입 이상

: '물리학과'의 사무실이 '930호'라는 정보를 삽입할 경우, '물리학과'에 소속된 학생이 없으면 삽입 불가능

삭제 이상

: 학번이 '1292301'인 학생 정볼를 삭제할 경우, 산업공학과의 정보도 함께 삭제됨

수정 이상

: 컴퓨터공학과의 사무실을 변경할 경우 3개의 레코드에 대해 모두 변경해야 함

3) 문제의 원인

: 기본키의 이행 종속

stu_id -> dept_name

dept_name -> office

stu_id -> office

즉, office 필드가 stu_id에 이행 종속된다.(다른 필드를 거쳐 종속됨)

5. 3차 정규형

: 이행 종속 분해

1) 정의

: 테이블 R이 2차 정규형이면서, 키에 속하지 않은 모든 필드가 기본 키에 이행 종속되지 않는다면 3차 정규형이다.

2) 3차 정규형의 문제점

부분 종속과 이행 종속이 존재하지 않음  

BUT

삽입 이상

: '홍길동' 교수가 '자료구조'를 강의한다는 사실을 저장할 경우, 수강생이 없으면 저장할 수 없음

삭제 이상

: 학번이 '1292001'인 학생이 '운영체제'를 수강한다는 사실을 삭제할 경우, '장민석' 교수가 '운영체제'를 강의한다는 사실도 함께 삭제됨

수정 이상

: '박철재' 교수가 강의하는 과목이 '운영체제'로 변경되는 경우, 2개의 레코드를 변경해야 함

3) 문제 발생의 원인

: 키에 포함되는 필드 집합 A와 키에 포함되지 않는 필드 집합 X에 대하여

X->A 라는 함수적 종속이 존재할 경우, 데이터 중복이 발생

-> 부분 종속과 반대 !

6. 보이스 코드 정규형

: 분해

1) 정의

: 테이블 R에 존재하는 모든 함수적 종속에서 결정자가 후보키인 정규형

2) 보이스 코드 정규형의 문제점

: 함수적 종속이 보존되지 않을 수 있음

7. 관계형 데이터베이스 설계 원칙

이상 현상 방지 vs 종속성 보존

: 이상 현상 방지보다는 종속성 보존이 더 중요하기 때문에,

보이스-코드 정규화할 시에 종속성 보존이 안된다면 3차 정규형을 택한다.

< 정규형을 감안한 논리적 설계 과정 >

논리적 설계 단계에서 데이터 중복 문제는 테이블을 분해함으로써 해결이 가능하다. 

이 때, 데이터 중복의 발생 여부를 파악하는 데에 사용되는 것이 '함수적 종속'이다.

1. 함수적 종속이란?

: 무결성 제약의 한 종류로, 테이블 내 필드 값들 사이의 관계성을 표현한다.

< 정의 >

테이블 R에서 필드 X값이 동일한 임의의 레코드에 대해 필드 Y의 값도 동일하다면 "Y는 X에 함수적으로 종속된다"고 한다.

X -> Y (결정자, 종속자)

라고 표현한다.

ex)

2. 함수적 종속의 특징

: 다대일 또는 일대일 관계이다.

: 결정자 또는 종속자가 두 개 이상의 필드를 구성할 수도 있다.

: 기본키가 있으면 다른 필드들이 기본키에 함수적으로 종속된다.

1) 포함 규칙

ex) (A, B) -> A

2) 분해 규칙

(A, B) -> C 가 성립한다고 해서, A->C, A->B 가 만족되지는 않음

3) 합성 규칙

4) 이행 규칙

3. 키와 함수적 종속의 관계

: 테이블의 모든 필드는 키(수퍼키포함)에 함수적으로 종속된다. 즉, 함수적 종속은 수퍼키의 개념을 일반화한 것이다.

4. 함수적 종속의 유지 방법

: 기본키가 아닌 필드에 대해서는 DBMS가 함수적 종속을 보장해주지 않는다.

: 따라서 이러한 문제가 발생하지 않도록 테이블을 정의해야 한다.  =>  정규화

5. 데이터의 중복

: 논리적 설계 결과에서 하나의 테이블에 하나의 필드에서 데이터 중복 현상 발생 가능하다.

-> 이는 < 삽입 이상, 삭제 이상, 수정 이상 > 의 이상현상을 발생시킨다.

1) 삽입 이상

: 데이터를 삽입할 수 없거나, 원치 않는 데이터를 삽입

ex_) 새로운 학과 정보,  ('930', '물리학과', '301호') 데이터를 넣으려면 ?

-> stu_id는 기본키이므로 null값이 허용되지 않는다.

이처럼 새로운 학과 정보를 넣고 싶은데 다른 정보들이 더 필요하다면 데이터를 삽입할 수 없다.

2) 삭제 이상

: 삭제하지 말아야 하는 정보까지 함께 삭제하는 현상

ex) 학번이 '1292501' 인 학생 정보를 삭제할 경우, 

-> '전자공학과'에 대한 정보도 사라지게 된다.

3) 수정 이상

: 중복된 정보의 일부만 수정하여 정보의 불일치가 발생하는 현상

ex) '컴퓨터공학과'의 office를 211호로 변경하고자 할 때,

-> 한 레코드만 수정하면 정보의 불일치가 발생한다.

4) 해결 방안

정규화 !

student 테이블에서 학과 정보를 분리하여 department 테이블을 생성한다.

-> dept_id 필드를 외래키로 설정하여 학과 정보 연결

0. 논리적 설계

: ERD로부터 테이블 스키마 생성 !

1. 강성 개체집합의 변환

하나의 강성 개체집합 -> 하나의 테이블

강성 개체집합의 속성 -> 테이블의 필드

* 테이블의 기본키는 개체집합의 기본키를 그대로 사용한다.

2. 약성 개체집합의 변환

테이블의 기본키 : 약성 개체집합의 부분키 + 대응되는 강성 개체집합의 기본키

3. 관계집합의 변환

: 연결되어 있는 개체집합의 기본키들을 테이블의 기본키로 설정한다.

4. 자기연관 관계집합의 변환

: 개체집합의 기본키를 테이블의 기본키로 사용하되, 역할의 의미에 맞게 이름을 변경하여 한번 더 써준다.

5. 테이블의 중복과 결합

: 관계집합에서 변환된 테이블의 모든 속성이 개체집합의 속성과 중복될 때, 관계집합 테이블을 생략할 수 있다.

-> opens 테이블 생략 가능 !

*** 1 : N 관계에서는

- 관계 테이블 만들 필요가 없다

- 1 에 해당하는 개체집합의 기본키를 N에 해당하는 개체집합의 테이블의 외래키로 추가한다.

- 만약 관계집합에서 필드가 있다면, N에 해당하는 개체집합 테이블에 추가해준다.

M : N 관계에서는

- 관계 테이블이 독립적으로 존재해야 한다.

1 : 1 관계에서는 

6. 다중값 속성의 변환

7. 복합 속성의 변환

8. 논리적 설계 실습  1 !

논리적 설계 실습  2 !

1. 개체(Entity) : 현실 세계에서 물리적 / 추상적으로 존재하는 실체

2. 개체집합 : 동일한 특성을 갖는 개체들의 모임

ex) 

3. 속성(Attribute) : 개체의 특성, 관계형 데이터 모델의 필드와 같은 개념

** 필드와 속성의 차이점

1) 필드(관계형 데이터 모델) : 원자값만 허용됨

2) 속성(개체관계 모델) : 다중값 속성(하나의 속성이 여러 개의 값을 가질 수 있음), 복합 속성(하나의 속성이 여러 개의 속성으로 구성됨)

다중값 속성 -> family_member 속성에는 여러 가족의 이름이 포함됨

복합 속성 -> address 속성은 세부적으로 (district, city, street) 로 구성됨

4. 관계(relationship)

: 개체 간의 대응성을 표현

5. 관계집합

ex) 소속(affiliated) 이라는 관계로 이어진 집합

1) 관계집합의 속성

: 개체집합에서 정의하는 것보다 두 개체집합의 관계에서 도출되는 속성일 때

ex) 학생이 학과에 소속되기 시작한 날짜 -> '소속' 관계집합의 속성으로 정의

2) 관계집합의 차수

: 관계집합에 참여하는 개체집합의 개수

- 이진관계: 두 개체집합 사이에 정의된 관계집합

ex) 학생 - 학과의 소속관계

- 삼진관계 : 세 개체집합 사이에 정의된 관계집합

ex) 학생 - 과목 - 교수의 수강 / 강의 관계

3) 관계의 대응수(mapping cardinality)

: 관계집합에서 각 개체들이 참여할 수 있는 대응의 개수

ex) 각 학생은 하나의 학과에만 소속될 수 있다. (N : 1)

- 일대일 대응수 (1:1)

: x->y, y->x 함수이다. (x->y 에서 x에 따른 y가 하나로 수렴하기 때문에)

ex) 각 과목(course)의 강좌(class)를 하나씩만 개설할 수 있을 때

- 일대다 대응수 (1:N or N:1)

: y->x 함수이다.

ex) 각 과목(course)에 대해 여러 강좌(class)를 개설할 수 있다고 가정할 때

- 다대다 대응수 (M:N)

: 어느 쪽으로도 함수 관계가 성립하지 않는다. 

ex) 여러 학생과 여러 강좌가 있을 수 있을 때

4) 약성 개체집합 vs 강성 개체집합

- 강성 개체집합 : 기본키 형성에 필요한 모든 속성을 갖는 개체집합

ex) course 개체집합 { course_id, title, credit } -> 기본키 존재

- 약성 개체집합 : 기본키 형성에 필요한 모든 속성을 갖지 못한 개체집합

ex) class 개체집합 { year, semester, division, classroom, enroll }

-> { year, semester, divison } 이 모여도 기본키가 되지 않음, 동일 교과목(course) 내에서만 유일함

-> course 가 존재해야 그것에 대한 class 도 존재 가능하고, 식별 가능함

- 약성 개체집합은 강성 개체집합에 항상 종속된다.

즉, 약성 개체집합은 독립적으로 존재할  수 없으며, 강성 개체집합이 존재해야 존재할 수 있다.

- 식별 관계

: 강성 개체집합와 약성 개체집합 사이의 1:1 또는 1:N 관계 ( 약성 개체집합에서는 꼭 하나의 강성 집합으로 연결이 되어야 함 )

: 약성 개체집합의 모든 개체가 식별 관계에 참여해야 함

: 강성 개체집합의 일부 개체만 식별 관계에 참여함

- 약성 개체집합의 부분키

: 강성 개체집합의 기본키 + 약성 개체집합의 부분키로 구성

ex) course 와 class 예시에서, class 개체집합의 기본키는 (course_id, year, semester, divistion)

5) 부분키

: 약성 개체관계 속성 중 강성 개체집합의 특정 개체에 대해 유일한 값을 갖는 속성들의 집합 ( 구별자 라고도 함 )

ex) course 개체집합과 class 개체집합의 관계에서, { year, semester, division }은 특정 course 에 대해 유일한 값을 갖는 class 속성이다.

6) 일반화와 세분화

: 일반화 - 여러 개체집합의 공통적인 특징을 모아 상위 개체집합을 생성

: 세분화 - 하나의 개체집합을 여러 개의 하위 개체집합으로 분류

6. 개체관계 다이어그램(ERD)

: 개념적 설계에서 개체집합과 관계집합, 속성을 도식화한 것

: 대응 관계에서 '일'인 쪽이 화살표

1) ERD 일반 예시

2) 약성 개체집합 및 식별 관계의 표현

3) 삼진관계 ERD

4) 세 개의 이진관계 ERD

5) 자기연관관계 ERD

- 역할(role) : 관계에 참여하는 두 개체를 구분

ex) 각 직원은 자신을 관리하는 상관이 존재, but 상관도 직원 개체집합에 속함,

각 상관은 여러 명의 직원을 관리할 수 있음

- M:N의 자기연관관계

ex) 한 과목은 여러 개의 선수 과목과 여러 개의 후수 과목을 가진다.

7. ERD 그려보기 실습 1 !

- 주의할 점

: year, semester, enroll에 대한 직접적인 언급이 없었는데, 필요하다고 생각이 되면 추가

: 관계 개체의 속성은 관계 하나당 생기는 속성일 때에만 설정한다.

ERD 그려보기 실습 2 !

- 주의할 점

: 약성 개체집합 설정 시, 관계집합도 약성으로 표시할 것

: 새로운 개체집합 만드는 것을 두려워하지 말 것!