류프리

제1절 데이터베이스 고급기능

제1항 트랜잭션 개념

(１) 트랜잭션의 정의

1) 데이터베이스 응용 프로그램에서 하나의 논리적 기능을 수행하는 연산자들의 집합

2) 데이터베이스 시스템에서 복구 및 병행 시행 시 처리되는 작업의 논리적 단위

3) 데이터베이스의 내용에 접근 혹은 수정하려는 단일 사용자나 응용 프로그램에 의해 수행되는 일련의 과정

(２) 트랜잭션의 속성

1) 원자성(atomicity)

① 트랜잭션 내의 모든 명령은 완벽히 수행되던지, 모두 취소되어야 함 (all or nothing)

② 트랜잭션은 일부만 수행된 상태로 종료되어서는 안 됨

2) 일관성(consistency)

① 트랜잭션이 성공적으로 완료되면 언제나 일관성 있는 데이터베이스 상태 유지

② 시스템이 가지고 있는 고정요소는 트랜잭션 수행전과 트랜잭션 수행 완료 후에 같아야 한다.

3) 독립성, 격리성(isolation)

① 둘 이상의 트랜잭션이 동시에 병행 실행되는 경우 어느 하나의 트랜잭션 실행중에 다른 트랜잭션의 연산이 끼어들 수 없다.

4) 영속성(durability)

① 트랜잭션이 일단 그 실행을 성공적으로 완료하면 그 결과는 영속적이어야 함

(３) 트랜잭션의 특징

1) 트랜잭션은 작업의 논리적 단위

2) 하나의 트랜잭션은 commit 되거나 rollback 되어야 함

3) 트랜잭션은 일반적으로 회복의 단위가 됨

제2항 트랜잭션의 연산

(１) commit

1) 한 작업의 논리적 단위가 성공적으로 끝났고, 데이터베이스가 다시 일관된 상태에 있으며 이 트랜잭션이 행한 갱신 연산이 완료된 것을 트랜잭션 관리자에게 알려주는 연산

2) SQL 명령어로 수행된 결과를 실제 물리적 디스크로 저장하는 SQL 명령

(２) Rollback

1) 개념

① 트랜잭션의 실행이 실패하였음을 알리는 연산자로 트랜잭션이 수행한 결과를 원래의 상태로 원상 복귀시키는 연산

② 트랜잭션들이 장애가 발생하여 데이터베이스가 손상되었을 때 손상되기 이전의 정상 상태로 복구하는 작업

2) 장애의 유형

① 트랜잭션 장애

ü 입력데이터 오류, 불명확한 데이터 등 내부의 비 정상적인 상황으로 인한 장애

② 시스템 장애

ü 하드웨어 오작동, 소프트웨어의 손상, 교착상태 등에 의한 장애

③ 미디어 장애

ü 저장장치인 디스크 블록의 손상이나 디스크 헤드의 충돌 등에 의해 데이터베이스가 물리적으로 손상된 상태

(３) SAVEPOINT

1) 개념

① SAVEPOINT는 하위 트랜잭션을 실현하기 위한 데이터베이스 언어 SQL 구문중 하나이다. 트랜잭션의 특정 지점에 이름을 지정하고, 그 지점 이전에 수행한 작업에 영향을 주지 않고, 그 지점 이후에 수행한 작업을 롤백(rollback)할 수 있다.

② SAVEPOINT는 데이터베이스를 이용하는 응용 프로그램에서 복잡한 오류 복구 최리를 실현하는데 효과적이다. 여러 문이 갖춰진 트랜잭션 도중에 에러가 발생했을 경우, SAVEPOINT를 사용하면 전체 트랜잭션을 롤백하지 않고 오류에서 복귀할 수 있다.

2) 사용예

① SAVEPOINT name에서 해당 지점에 이름을 지정하고 ROLLBACK TO SAVEPOINT name으로 롤백하면 된다.

 BEGIN;

제3항 트랜잭션의 상태

(１) 활동(active)

1) 트랜잭션이 실행중인 상태

(２) 실패(failed)

1) 오류가 발생하여 중단된 상태

(３) 철회(aborted)

1) 비정상 종료되어 rollback 연산을 수행한 상태

(４) 부분완료(partially committed)

1) Commit 연산이 실행되기 직전 상태

(５) 완료(committed)

1) 성공적으로 완료된 상태

제4항 데이터베이스제어(보안, 무결성, 병행제어, 회복기법) 개념

(１) 보안

1) 보안의 개요

① 데이터베이스의 일부분 또는 전체에 대해서 권한이 없는 사용자가 액세스하는 것을 금지하기 위해 사용되는 기술

② 무결성은 권한이 있는 사용자로부터 데이터베이스를 보호하는 것이고, 보안은 권한이 없는 사용자로부터 데이터베이스를 보호하는 것

2) 보안의 특성

① 보안을 위한 데이터 단위는 테이블 전체로부터 특정 테이블의 특정한 행과 열 위치에 있는 특정한 데이터 값에 이르기까지 다양함

② 각 사용자들은 일반적으로 서로 다른 객체에 대하여 다른 접근권리 또는 권한을 갖게 됨

③ SQL의 경우에는 보안 규정에 포함된 독립적인 기능으로 뷰 기법(view mechanism)과 권한 인가 서브시스템(authorization subsystem)이 있음

3) 암호화 기법

① 개인키(대칭키) 암호 방식(private key encryption)

ü 암호화할 때 사용하는 키와 복호화할 때 사용하는 키가 동일한 암호 알고리즘 방식

ü 속도가 빠르지만, 키 배송 문제가 있다.

ü DES, 3DES, AES, SEED, ARIA

② 공개키(비대칭키) 암호 방식(public key encryption)

ü 암호화할 때 사용하는 키와 복호화 할 때 사용하는 키가 서로 다른 암호 알고리즘 방식

ü 속도는 느리지만, 키 배송 문제르 해결 함.

ü 전자서명 : 송신자의 개인키 / 송신자의 공개키

ü 메일: 수신자의 공개키 / 수신자의 개인키

③ 하이브리드 암호 시스템

ü 대칭키 암호와 공개키 암호를 조합한 암호 방식을 하이브리드 암호 시스템이라고 한다.

(２) 병행제어(concurrency control)

1) 개념

① 다중 프로그램의 이점을 활용하여 동시에 여러 개의 트랜잭션을 병행 수행할 때, 동시에 실행되는 트랜잭션들이 데이터베이스의 일관성을 파괴하지 않도록 상호 작용을 제어하는 것

2) 병행제어의 목적

① 데이터베이스의 공유를 최대화한다.

② 시스템의 활용도 최대화한다.

③ 사용자에 대한 응답시간 최소화한다.

④ 데이터베이스 일관성 유지한다.

3) 병행수행의 문제점

병행제어 기법에 의한 제어 없이 트랜잭션들이 데이터베이스에 동시에 접근하도록 허용할 경우 다음과 같은 문제점이 발생한다.

① 갱신 분실(lost update)

ü 두개 이상의 트랜잭션이 같은 자료를 공유하여 갱신할 때 갱신 결과의 일부가 없어지는 현상

② 모순성(inconsistency)

③ 불일치 분석문제(inconsistent analysis problem)

ü 트랜잭션이 병행 수행될 때 원치 않는 자료를 이용함으로써 발생하는 문제

④ 연쇄복귀(cascading rollback)

ü 병행수행 되던 트랜잭션들 중 어느 하나에 문제가 생겨 rollback하는 경우 다른 트랜잭션들도 함께 rollback 되는 현상

⑤ 비완료 의존성문제, 임시 갱신(uncommitted dependency problem)

ü 트랜잭션이 실패한 후 회복되기 전에 다른 트랜잭션이 실패한 결과를 참조하는 현상

4) 병행제어 기법의 종류

① 로킹(locking)

ü 개념

• 데이터의 접근을 상호 배타적으로 만들어 병행제어를 하는 방법

• 하나의 트랜잭션이 데이터를 액세스하는 동안 다른 트랜잭션이 그 데이터 항목을 액세스할 수 없도록 하는 방법

• 트랜잭션들이 어떤 로킹 단위를 액세스하기 전에 lock(잠금)을 요청해서 lock이 허락되어야만 그 로킹 단위를 액세스할 수 있도록 하는 기법이다.

ü 종류

• 공유 로크(S, shared lock)

• 배타 로크(X, exclusive lock)

• 의도 로크(I, intention lock)

• 의도공유 로크(IS, intention-shared lock)

• 배타의도 로크(IX, intention-exclusive lock)

• 공유의도 독점로크(SIX, shared and intention-exclusive lock)

ü 2단계 로킹(two-phase locking) 규약

• 각 트랜잭션의 로크 요청과 해제(unlock) 요청을 2단계로 실시한다.

• 직렬성을 보장하는 대표적인 로킹 규약이다.

• 직렬성을 보장하는 장점은 있지만, 교착상태를 예방할 수 없다는 단점이 있다.

ü 로킹 단위(locking granularity)

• 병행제어에서 한꺼번에 로킹할 수 있는 객체의 크기를 의미함.

• 데이터베이스, 파일, 레코드, 필드 등은 로킹 단위가 될수 있다.

• 로킹 단위가 크면 로크수는 작아져서 관리하기 쉽지만, 병행성 수준이 낮아지고, 로킹 단위가 작으면 로크수가 많아져서 관리하기 복잡하고 오버헤드가 증가하지만 병행성 수준이 높아진다.

• 페이지 차원(page-level)의 잠금 > 테이블 차원(table-level)의 잠금 > 행차원(row-level)의 잠금

② 타임스탬프 순서(time stamp ordering)

ü 직렬성 순서를 결정하기 위해 트랜잭션 간의 처리 순서를 미리 선택하는 기법들 중에서 가장 보편적인 방법이다.

ü 트랜잭션과 트랜잭션이 읽거나 갱신한 데이터에 대해 트랜잭션이 실행을 시작하기 전에 시간표(time stamp)를 부여하여 부여된 시간에 따라 트랜잭션 작업을 수행하는 기법이다.

ü 교착상태가 발생하지 않는다.

(３) 회복

1) 회복의 정의

① 데이터베이스 운영 시 데이터베이스에 손상이 가해졌을 때 손상되기 이전의 상태로 되돌리는 작업

2) 장애의 종류

① 트랜잭션 장애(transaction failure)

② 시스템 장애(system failure)

③ 미디어 장애(media failure)

④ 네트워크 장애(network failure)

3) 회복기법

① 트랜잭션으로 쓰기가 수행될 때마다 데이터베이스가 변경되기 전에 로그 레코드를 생성

② Undo

ü Log에 저장된 정보를 이용하여 가장 최근의 변경(트랜잭션) 부터 취소하여 데이터베이스를 복구하는 것

③ redo

ü 트랜잭션의 오류시 가장 최근의 정상상태로 데이터베이스를 되돌린 후 트랜잭션을 다시 실행

제5항 분산 데이터베이스

(１) 분산 데이터베이스 정의

1) 분산 데이터베이스

① 논리적으로는 하나의 시스템에 속하지만 물리적으로는 네트워크를 통해 연결된 여러개의 컴퓨터 사이트에 분산되어 있는 데이터베이스

② 동질 분산 데이터베이스 관리시스템과 이질 분산 데이터베이스 관리 시스템으로 구분할 수 있음

③ 수평 분할은 전역 테이블을 구성하는 튜플들을 부분집합으로 분할하는 방법을 말함

④ 데이터의 처리나 이용이 많은 지역에 데이터베이스를 위치시킴으로써 데이터의 처리가 가능한 해당 지역에서 해결될 수 있도록 하는 데이터베이스 시스템

2) 분산 데이터베이스의 구성요소

① 분산 처리기

ü 자체적 처리능력을 지닌 지리적으로 분산되어 있는 컴퓨터 시스템

② 분산 데이터베이스

ü 지리적으로 분산되어 있는 데이터베이스, 해당 지역의 특성에 맞게 구성됨

③ 통신 네트워크

ü 분산 처리기를 통신망으로 연결하여 논리적으로 하나의 시스템이 되도록 하는 네트워크 시스템

(２) 분산 데이터베이스 목표

1) 위치 투명성

① 데이터가 물리적으로 저장되어 있는 곳을 알 필요 없이 논리적인 입장에서 데이터가 모두 자신의 사이트에 있는 것처럼 처리하는 특성

② 액세스하려는 데이터베이스의 실제 위치를 알 필요가 없다.

2) 중복 투명성(replication transparency)

① 트랜잭션이 데이터의 중복 개수나 중복 사실을 모르고도 데이터 처리가 가능함

② 동일 데이터가 중복되더라도 사용자는 하나의 데이터만 존재하는 것처럼 사용

3) 병행 투명성(concurrency transparency)

① 분산 데이터베이스와 관련된 다수의 트랜잭션들이 동시에 실현되더라도 그 트랜잭션의 결과는 영향을 안 받음

4) 장애 투명성(failure transparency)

① 트랜잭션, DBMS, 네트워크, 컴퓨터 장애에도 불구하고 트랜잭션을 정확하게 처리함

(３) 분산 데이터베이스 특징

1) 분산 데이터베이스의 장점

① 지역 자치성이 높음

② 효용성과 융통성이 높음

③ 점진적 시스템 용량 확장이 용이

④ 신뢰성과 가용성이 높음

⑤ 특정한 사이트에서 장애가 발생하더라도 다른 사이트는 계속 운용할 수 있음

⑥ 데이터의 공유성 향상

⑦ 질의 처리(query processing) 시간의 단축

⑧ 분산제어가 가능하고 시스템의 성능이 향상됨

2) 분산 데이터베이스의 단점

① 중앙 집중 시스템보다 구현하는 복잡하고 처리 비용이 증가

② 자료의 중앙 통제시 저장된 자료의 일관성 유지가 용이함

3) 미들웨어 (middle-ware)

① 복잡한 이기종 환경에서 응용 프로그램과 운영환경 간에 원만한 통신을 이룰수 있게 해 주는 소프트웨어

② 서로 다른 기종간의 서버와 클라이언트들을 연결해주는 소프트웨어

③ ODBC

ü 분산 환경에서 서로 다른 데이터베이스를 연결하여 사용할 수 있게 하는 미들웨어

4) 분산 데이터베이스 설계

① 설계시 고려사항

ü 작업부하(work load)의 노드별 분산 정책

ü 지역의 자치성 보장 정책

ü 데이터의 일관성 정책

ü 사이트나 회선의 고장으로부터 회복 기능

ü 통신 네트워크를 통한 원격 접근 가능

② 데이터베이스 서버(server)의 선정 시 조건

ü 고성능의 주기억장치와 빠른 입∙출력 연산등이 수행될 수 있는 기능이 지원되어야 함

ü 다양한 사용자 인터페이스가 지원되어야 함.

ü 대용량의 자료를 저장, 탐색할 수 있으며, 분산 데이터 관리가 지원되어야 함.

제1항 관계 데이터베이스의 정규화

(１) 정규화

1) 개요

① 데이터베이스의 릴레이션이나 튜플을 불필요한 중복없이, 수정할 때 의도하지 않았던 불필요한 사실이 추가, 삭제, 갱신되는 일이 없도록 DB를 재구성하는 과정을 공식화한 과정

2) 필요성

① 중복에 따른 갱신이상 현상의 제거로 일관성 유지

ü (갱신이상, 삽입이상, 삭제이상 현상제거)

② 효율적인 검색이 가능

③ 중복의 제거로 인한 저장 공간의 최소화

④ 데이터 신규 발생시 DB 재구성의 필요성을 감소(유연한 구조)

3) 목적

① 정보의 중복을 피하기(최소화) 하기 위해

② 삽입, 삭제, 갱신 이상의 발생을 방지

③ 효율적인 데이터 조작

4) 기본 개념

① 하나 이상의 릴레이션을 두개 이상의 릴레이션으로 분해(decomposition) 시키는 과정을 포함

② 무손실 분해(lossless decomposition)

ü 분해한 릴레이션을 조인하여 저장 정보의 손실없이 원래의 릴레이션을 생성할 수 있는 것

5) 정규화 단계

(２) 함수적 종속성 (Functional Dependency)

1) 정의

① 정규화 과정에서 중요하게 이용되는 개념으로서 관계형 데이터베이스의 릴레이션에서 애트리뷰트간의 관계를 정의할 때 사용되는데 좋은 릴레이션을 판단하는 기준을 정하는 요소로 사용된다.

② 어떤 릴레이션 R에서 애트리뷰트 X의 값 각각에 대해 애트리뷰트 Y의 값이 오직 하나만 연관되어 있을 때 Y는 X에 함수적으로 종속된다.

③ 함수적 종속성은 애트리뷰트들 사이의 관계에 대한 제약조건으로 애트리뷰트 X가 Y의 결정자이면 Y는 X에 함수적으로 종속된다.

2) 함수적 종속성 표기

① X → Y

ü X는 Y의 결정자(determinant), Y는 X의 종속자(dependent)이다.

② 결정자(determinant)

ü 결정자는 주어진 릴레이션에서 다른 애트리뷰트를 고유하게 결정하는 하나 이상의 애트리뷰트이다.

ü 기본적으로 기본키는 결정자이다.

        학번 → 이름, 학번 → 학년 함수 종속성 성립.  이름 → 학번은 성립하지 않는다.

3) 종류

① 완전 함수적 종속성

ü 어떤 릴레이션 R에서 속성 X가 속성 집합일 때, 속성 Y가 속성 A에 함수적으로 종속하면서, 속성 X의 어떤 진부분 집합에도 함수적으로도 종속하지 않으면, 속성 Y가 속성 X에 완전하게 함수적으로 종속한다.

ü 여러 개의 속성이 모여서 하나의 기본키를 이룰 경우 기본키 전체가 있어야지만 어떤 속성이 결정될 때 완전 함수적 종속이다.

② 부분 함수적 종속성

ü 완전하게 함수적으로 종속하지 않으면 부분 함수적 종속성을 갖는다.

ü 여러 개의 속성이 모여서 하나의 기본키를 이룰 경우, 기본키를 구성하는 부분 속성만으로도 결정되어지면 부분 함수적 종속이다.

③ 이행 함수적 종속성

ü X → Y 이고, Y → Z 일 때 X → Z를 만족하는관계를 이행적 함수 종속이라 한다.

‘학번’ → ‘지도교수’ 이고, ‘지도교수’ → ‘학과’ 일 때 ‘학번’ → ‘학과’를 만족

(３) 이상현상

1) 개념

① 데이터의 중복으로 인해 릴레이션을처리할 때 발생한느 곤란한 현상

② 데이터베이스 사용자의 의도와는 다르게 다른 데이터가 삽입, 삭제, 갱신되는 현상

2) 갱신이상(update anomaly)

① 릴레이션 R에서 특정 속성값 갱신시에 중복 저장되어 있는 속성중 하나만 갱신하고 나머지는 갱신하지 않아서 발생하는 데이터의 불일치 현상

② 예제

ü 데이터베이스의 수강료를 200원 인상할 경우 ‘700100’번 학생의 수강료만 갱신하고, ‘700400’번 학생의 수강료는 200원 인상하지 않은 경우

3) 삭제이상(delete anomaly)

① 릴레이션 R에서 튜플을 삭제할 경우, 원하지 않는 정보까지도 삭제되는 현상

② 예제

ü 학번이 ‘700200’인 학생을 삭제할 경우 ‘데이터통신’의 수강료가 10,150이라는 정보까지 잃게 되는 경우

4) 삽입이상(insertion anomaly)

① 릴레이션 R에 특정 튜플을 삽입시, 원하지 않는 불필요한 정보까지도 삽입해야 하는 현상. 그렇지 않으면 삽입이 되지 않는 현상

② 예제

ü ‘암호학’ 과목을 삽입하기 위해서는 ‘학번’ 이 기본키이므로 아무 학번이라도 함께 넣어야 하는 경우

→ 정규화 과정을 거쳐서 이러한 이상 현상을 줄여 나갈 수 있음

(４) 데이터 종속성과 정규화

1) 제1정규형 (1NF, first normal form)

① 모든 도메인의 값이 원자값 (atomic value) 를 가지고 있을 때 1차 정규형에 속한다.

② 반복/복수의 속성값 갖는 속성제거

반복집합이 있는 비정규 릴레이션

반복 집합을 제거하여 모든 속성값이 원자값으로 구성된 1NF로 만듬.

2) 제2정규형 (2NF, second normal form)

① 어떤 릴레이션 R이 제1정규형을 만족하면서, 키가 아닌 모든 속성이 기본키에 완전 함수적 종속인 릴레이션

② 부분 함수 종속성 제거

제1정규형 릴레이션에서 부분함수 종석성을 제거함.

모든 속성이 키에 대해서 완전 함수적 종속인 제2정규형 릴레이션을 만듬.

3) 제3정규형 (3NF, third normal form)

① 어떤 릴레이션 R이 2NF이고, 키에 속하지 않은 애트리뷰트들이 기본키에 이행적 함수 종속이 아닐 경우 제3정규형(3NF)에 속한다.

② 이행적 종속성 제거

제2정구형 릴레이션에서 이행적 함수 종속을 제거함.

이행적 함수 종속을 없앤 제3정규형 릴레이션을 만듬.

4) BCNF (boyce-codd normal form)

① 정의

ü 모든 결정자가 후보키(candidate key)인 관계

ü 결정자이면서 후보키가 아닌 것 제거

5) 제4정규형

① 다치종속성(multivalued dependency)

ü 릴레이션 R의 속성 X, Y, Z가 있을 때 (X, Y)에 대응하는 Z의 집합이 X값에만 종속되고, Y값에 무관하면 Z는 X에 다치종속이라 하고, X  Y로 표기한다.

ü 다치종속성이란 속성들이 집합 값을 가지지 못하게 하는 제1정규형의 함수 종속성에 기인한다.

ü 다치종속의 예

• 사원테이블에는 사원이 담당하는 거래처와 가족인 부양자가 각각 여러 개씩 존재한다.

• 거래처는 사원의 업무에 관련된 사항이며, 부양자는 사원의 급여에 관련된 사항이다. 거래처와 부양자 간에는 아무 관련성이 없다.

• 테이블의 일관성을 유지하기 위해서 사원마다 거래처와 부양 가족의 모든 가능한 조합들을 모두 포함해야 하며, 이로 인해서 거래처와 부양자가 여러 개 중복될 수 밖에 없다.

• 이런 제약 조건은 사원 테이블에 대한 다치 종속으로 표현된다. 두개의 독립적인 1:N 관계인 사원:거래처와 사원:부양자가 동일한 테이블에 존재할 때 다치 종속성이 발생한다.

• 자료의 성격에 따라서 사원:거래처 테이블과 사원:부양자 테이블로 분해한다면 중복은 사라진다.

6) 제5정규형

① 모든 조인 종속은 후보키를 통해서만 성립된다.

② 조인종속

ü 한 테이블을 분해했다가 분해된 결과들을 다시 조인하면 당연히 원래의 테이블로 복원된다고 기대하지만 그렇지 못한 경우가 있다. 다시 조인하면 예상하지 못했던 튜플들이 생성되는 경우가 발생한다.

ü 조인 종속(JD, join dependency)은 테이블을 분해한 결과를 다시 조인했을 때 원래의 테이블과 동일하게 복원되는 제약조건이다. 조인 종속성은 다치 종속의 개념을 더 일반화한 것이다.

제1항 개체-관계(E-R) 모델

(１) E-R 모델

1) E-R (Entity Relationship) 모델

① 세상의 사물을 개체(entity)와 개체간의 관계(relationship)로 표현함

2) E-R (Entity Relationship) 모델의 특성

① 1976년 Peter Chen(P.Chen)에 의하여 발표된 모델링 도구임

② 개체(Entity), 관계(Relationship), 속성(Attribute) 개념을 도입

③ 개념적 설계에 가장 많이 사용되는 모델

④ 각 개체 집합은 여러 개의 속성으로 표현되며, 각 속성은 현실 세계의 객체들이 갖는 특성

3) E-R 다이어그램의 구성요소

(２) 개체(Entity)

1) 사람, 사물, 장소, 개념, 사건과 같이 유·무형의 정보를 가지고 있는 독립적인 실체

2) 독립적인 의미를 지니고 있는 유·무형의 사람 또는 사물·개체의 특성을 나타내는 속성(attribute)에 의해 식별됨. 개체끼리 서로 관계를 가짐.

3) 비슷한 속성의 개체 타입(entity type)을 구성하며, 개체 집합(entity set)으로 묶임

4) 개체 타입(entity type)

① 같은 개체를 가지는 속성들의 집합

5) 개체 인스턴스(entity instance)

① 개체를 구성하고 있는 각 속성들이 값을 지녀 하나의 개체를 나타내는 것으로 개체 어커런스라고도 함.

6) 개체 세트(entity set)

① 개체 인스턴스의 집합

(３) 관계(relation)

두개 이상의 개체 사이에 존재하는 연관성

1) 관계의 기수성

① 특정 실체와 관련된 대상 실체의 최대 instance 수(1, many)

2) 관계의 서수성

① 특정실체와 관련된 대상실체의 필수 존재여부 (optional, mandatory)

3) 기수성/서수성 사례

① A의 어커런스는 반드시 B의 한 어커런스와 연관된다.

② A의 어커런스는 B의 한 어커런스와 연관되거나 안될수도 있다.

③ A의 어커런스는 B의 한 개 또는 다수의 어커런스와 연관된다.

④ A의 어커런스는 B의 다수의 어커런스와 연관되거나 안될수도 있다.

4) 관계의 형태

① 1:1 관계(일대일)

ü 개체집합 A의 각 원소가 개체 집합 B의 원소 1개와 대응

② 1:N 관계(일대다)

ü 개체집합 A의 각 원소는 개체집합 B의 원소 여러 개와 대응할 수 있고, 개체 집합 B의 각 원소는 개체 집합 A의 원소 1개와 대응

③ N:M 관계(다대다)

ü 개체집합 A의 각 원소는 개체집합 B의 원소 여러 개와 대응할 수 있고, 개체집합 B의 각 원소는 개체집합 A의 원소 여러 개와 대응할 수 있음

5) 새발(crow-feet) 표기법

(４) 관계 타입의 E-R 다이어그램 표현

1) 관계 타입

2) 관계 타입의 예

(５) 차수에 따른 유형

1) 차수(degree)

① 관계 집합에 참가하는 개체 타입의 수를 관계 타입의 차수(degree)라고 함

2) 차수에 따른 관계 타입의 유형

① 1진관계(unary relationship)

ü 한 개의 개체가 자기 자신과 관계를 맺음

② 2진관계(binary relationship)

ü 두개의 개체가 관계를 맺음

③ 3진관계(ternary relationship)

ü 세개의 개체가 관계를 맺음

(６) 확장 E-R 모델 (EER model: Extended E-R model)

1) 개체-관계 모델과 확장 E-R 모델

① 개체-관계 모델

ü 1976년 Peter Chen에 의해 발표됨

ü 개념 스키마 설계시 가장 널리 이용되는 도구

ü 구성요소: 개체(entity), 관계(relationship), 속성(attribute) 등

② 확장 E-R 모델

ü E-R 모델의 개체, 관계 속성등의 개념에 일반화, 세분화, 약한 개체 유형, 복합 속성등과 같은 개념이 추가된 새로운 개념의 E-R 모델

2) 세분화와 일반화

① 세분화 (specialization)

ü 개체를 작은 그룹으로 분리하는 것 (상위클래스와 하위클래스)

② 일반화 (generalization)

ü 여러 개체의 공통적인 특징을 하나의 클래스 개체로 일반화시키는 것

3) 약한 개체(weak entity)란?

① 개체중에 독자적으로 존재할 수 없는 개체를 말함

② 교수와 부양가족 개체의 관계에서 교수는 부양가족이 없을수도 있고 있을수도 있으므로 약한 개체라고 할 수 있다.

4) 복합속성이란?

① 주소속성은 시-도, 구-군, 읍-면-동, 번지, 우편번호 속성들로 이루어진 복합속성이다.

5) 기타

① 개체를 구성하는 속성들은 작은 원으로 표시

② 속성 중에서 기본적 속성(기본키) 검고 작은 원으로 표시

③ 관계와 개체를 연결하는 선 위에는 (최소 대응수, 최대 대응수)로 표시

ü 최소대응수 : 관계에 참여하는 최소한의 개체 인스턴스

- 0 : 참가해도 안해도 무관

- 1 : 최소 하나의 관계

- N : 여러 개 관계

ü 최대대응수 : 관계에 참여하는 최대한의 개체 인스턴스

- 1 : 최대 1개

- N : 여러 개

6) 관계 대응수의 최소값과 최대값

① 개념

ü 관계 대응수 1:1, 1:N, N:M에서 1, N, M은 각 개체가 관계에 참여하는 최대값을 의미

ü 관계에 참여하는 개체의 최소값을 표시하지 않는다는 단점을 보완하기 위해 다이어그램에서는 대응수 외에 최소값과 최대값을 관계 실선위에 (최소값, 최대값)으로 표기

② 관계 대응수의 최소값과 최대값의 표기

③ 관계 대응수에 따른 관계 타입의 유형

④ (최소값, 최대값) 표기의 예

(７) 속성(attribute)

1) 정의

① 개체 또는 관계에 대한(속성)을 기술하는 데이터 항목을 말함

② 속성의 그래픽 표현은 타원으로 표시한다.

2) 속성의 분류

① 단일값 속성(single-valued attribute)

ü 속성값이 원자값인 것으로 하나의 값만 존재하는 것 (속성 하나에 한 개의 값을 가지는 경우)

ü 주민등록번호와 같은 속성은 반드시 하나의 값만 존재한다.

② 다중값 속성(multi-valued attribute)

ü 속성값이 여러 개 존재할 수 있는 것

ü 사람의 전화번호는 집, 휴대전화, 회사 전화번호와 같이 여러 개의 값을 가질수 있다.

③ 복합속성

ü 속성값이 여러 의미를 포함하는 것

④ 유도속성(derived attribute)

ü 다른 엔티티나 속성으로부터 유도되거나 계산된 속성들은 유도 속성이라고 함

ü 다른 속성값으로부터 어떤 계산을 통해 새로운 값을 얻게 되므로 집합의 본질이나 특성을 규명하기 위한 속성을 고려할 때 제외할 수도 있다.

ü 저장속성과 유도속성

• 저장 속성(stored attribute)은 다른 속성의 영향 없이 단독으로 저장되는 속성이고, 유도 속성(derived attribute)은 다른 저장 속성으로부터 유도된(계산 되어진) 속성이다.

제1절 데이터모델링 및 설계

제1항 모델링의 이해

(１) 모델링의 정의

1) 모델이라고 하는 것은 모형, 축소형의 의미로서 사람이 살아가면서 나타날 수 있는 다양한 현상에 대해서 일정한 표기법에 의해 표현해 놓은 모형

2) 사람이 살아가면서 나타날 수 있는 다양한 현상은 사람, 사물, 개념 등에 의해 발생된다고 할 수 있으며, 모델링은 이것을 표기법에 의해 규칙을 가지고 표기하는 것 자체

3) 모델링은 ‘현실세계를 추상화, 단순화, 명확화하기 위해 일정한 표기법에 의해 표현하는 기법

4) 정보시스템 구축에서는 모델링을 계획/분석/설계 할 때 업무를 분석하고 설계하는데 이용하고 이후 구축/운영 단계에서는 변경과 관리의 목적으로 이용

(２) 모델링의 특징

1) 추상화

① 추상화(모형화, 가설적)는 현실세계를 일정한 형식에 맞추어 표현을 한다는 의미

② 다양한 현상을 일정한 양식인 표기법에 의해 표현한다는 것

2) 단순화

① 복잡한 현실세계를 약속된 규약에 의해 제한된 표기법이나 언어로 표현하여 쉽게 이해할 수 있도록 하는 개념

3) 명확화

① 누구나 이해하기 쉽게 하기 위해 대상에 대한 애매모호함을 제거하여 정확하게 현상을 기술하는 것

제2항 정보 모델링과 데이터 모델링

(１) 정보 모델링(information modeling)

1) 현실 세계에 존재하는 개체를 인간이 이해할 수 있는 정보 구조(현실 세계에 대한 인식을 추상적 개념으로 표현)로 표현하는 과정

2) 정보모델링을 통하여 얻어진 결과를 정보 구조화라 함

3) 정보 구조를 구성하는 추상적 개념은 현실 세계의 객체에서 추상화된 개체(entity) 집합

(２) 데이터 모델링(data modeling)

1) 현실세계에 존재하는 개체를 컴퓨터 세계의 데이터 구조로 기술하는 것

2) 데이터 모델링의 과정

제3항 데이터 모델링

(１) 데이터 모델 (data model)의 개념

1) 현실 세계를 데이터베이스에 표현하는 중간 과정, 즉 데이터베이스 설계과정에서 데이터 구조를 표현하기 위해 사용되는 도구

2) 현실 세계의 데이터 구조를 컴퓨터 세계의 데이터 구조로 기술하는 개념적인 도구

3) 단순화, 추상화를 제공하기 위해 사용

4) 데이터베이스의 구조를 묘사하기 위해 사용되는 개념들의 집합

5) 데이터베이스의 구조는 데이터의 타입, 데이터간의 관계, 데이터를 유지하기 위해 필요한 제약들을 의미

(２) 개념적 데이터 모델링

1) 처음 현실세계에서 추상화 수준이 높은 상위 수준을 형상화하기 위해 개념적 데이터 모델링을 전개

2) 추상화 수준이 높고 업무중심적이고 포괄적인 수준의 모델링을 진행한다.

3) 속성들로 기술된 개체 타입과 이 개체 타입들 간의 관계를 이용하여 현실 세계를 표현하는 방법

4) 요구사항을 수집하고 분석한 결과를 토대로 업무의 핵심적인 개념을 구분하고 전체적인 뼈대를 만드는 과정

5) 개체(entity)를 추출하고 각 개체들 간의 관계를 정의하여 E-R 다이어그램을 만드는 과정까지를 말함

(３) 논리적 데이터 모델링

1) 엔티티 중심의 상위 수준의 데이터 모델이 완성되면 업무의 구체적인 모습과 흐름에 따른 구체화된 업무중심의 데이터 모델을 만들어 내는데 이것을 논리적인 데이터 모델링이라고 함.

2) 필드로 기술된 데이터 타입과 이 데이터 타입들 간의 관계를 이용하여 현실 세계를 표현하는 방법

3) 논리적 모델링 과정

① 개념적 모델링에서 추출하지 않았던 상세 속성들을 모두 추출함

② 정규화 수행

③ 데이터 표준화 수행

(４) 물리적(하위수준) 모델의 개념

1) 데이터베이스 저장구조에 따른 테이블스페이스 등을 고려한 방식을 물리적인 데이터 모델링이라고 함.

2) 레코드의 형식, 순서, 접근 경로와 같은 정보를 사용하여 데이터가 컴퓨터에 저장되는 방법을 묘사

3) 작성된 논리적 모델을 실제 컴퓨터의 저장 장치에 저장하기 위한 물리적 구조를 정의하고 구현하는 과정

4) DBMS의 특성에 맞게 저장 구조를 정의해야 데이터베이스가 최적의 성능을 낼 수 있음

5) 물리적 모델링 시 트랜잭션, 저장 공간 설계 측면에서 고려할 사항

① 응답시간을 최소화

② 얼마나 많은 트랜잭션을 동시에 발생시킬 수 있는지 검토

③ 데이터가 저장될 공간을 효율적으로 배치

(５) 데이터 모델의 구성요소

1) 논리적으로 표현된(추상적인 개념) 데이터 구조

2) 구성요소의 연산

3) 구성요소의 제약조건

(６) 데이터 모델, 스키마, 인스턴스의 관계

1) 모델 → 스키마 → 인스턴스

제4항 데이터 모델의 구성요소

(１) 개체 타입(entity type)

1) 같은 개체를 가지는 속성들의 집합

(２) 개체 인스턴스(entity instance)

1) 개체를 구성하고 있는 각 속성들이 값을 지녀 하나의 개체를 나타내는 것으로 개체 어커런스라고도 함.

(３) 개체 세트(entity set)

1) 개체 인스턴스의 집합

제5항 데이터베이스 설계

(１) 데이터베이스 생명주기(database life cycle)

1) 요구조건 분석 → 데이터베이스에 저장할 내용을 정하기 위해 사용자 요구사항 분석

2) 설계 → 개념적 설계 > 논리적 설계 > 물리적 설계

3) 구현 → 스키마 정의, 데이터베이스 구축

4) 운영 → 사용자의 요구에 맞는 서비스 제공

5) 감시 및 개선 → 새로운 요구조건 감시 및 성능 향상

(２) 데이터베이스 설계 단계

1) 요구조건 분석 → 데이터베이스에 저장할 내용을 정하기 위해 사용자 요구사항 분석

2) 개념적 설계 → DBMS에 독립적인 개념 스키마 설계 (트랜잭션 모델링 및 정의)

3) 논리적 설계 → DBMS에 맞는 스키마 설계 (트랜잭션 인터페이스 설계)

4) 물리적 설계 → DBMS에 맞는 물리적 구조 설계 (트랜잭션 세부 설계)

5) 구현 → DDL로 스키마 작성 (트랜잭션 작성)

(３) 데이터베이스 설계의 두가지 활동

1) 데이터중심 설계: 데이터베이스의 내용과 구조에 치중

2) 처리중심 설계: 데이터의 처리와 응용에 치중

(４) 데이터베이스 설계의 각 단계별 특징

1) 요구조건 분석

① 요구조건

ü 개체, 애트리뷰트, 관계성, 제약조건 등의 요구 조건 분석

ü 트랜잭션의 유형, 트랜잭션의 실행 빈도 등의 요구 조건 분석

ü 기관의 경영목표 및 정책, 규정 등의 제약조건 분석

② 요구조건 분석 절차

ü 사용자 그룹이나 응용 분야별로 정보의 내용과 처리 요구 조건의 수집

ü 범기관적 경영 목표 및 외적 환경 등 연구 분석

ü 수집된 정보로 공식적 요구조건 명세 작성 (관련 데이터 요소 및 트랜잭션 정의 포함)

ü 요구 조건 명세의 검토 (소프트웨어 공학기법: HIPO, SADT, DFDS 등)

2) 개념적 설계

① 개념 스키마 모델링 (데이터 중심 설계)

ü 데이터의 조직과 표현 (개체타입, 애트리뷰트, 관계성 결정)

ü E-R 다이어그램 같은 개념적 데이터 모델 사용

ü DBMS에 독립적인 추상적 데이터에 기초를 둔 개념

② 트랜잭션 모델링 (처리 중심 설계)

ü 요구조건 분석 결과로 식별된 응용을 검토하여 이들을 구현할 트랜잭션 기술

3) 논리적적 설계

① 특정 목표 DBMS가 처리할 수 있는 스키마 생성

② 논리적 설계의 3단계

ü 논리적 데이터 모델로 변환

ü 트랜잭션 인터페이스 설계

ü 스키마의 평가 및 정제

4) 물리적 설계

① 논리적 데이터베이스 구조로부터 효율적이고 구현 가능한 물리적 구조를 생성하는 것

ü 저장 레코드 양식 설계

ü 레코드 집중의 분석 및 설계

ü 접근 경로 설계

② 물리적 설계시 고려사항

ü 응답시간

ü 저장 공간 효율화

ü 트랜잭션 처리도

5) 구현

① 설계 단계에서 생성한 스키마를 실제 DBMS에 적용하여 테이블 및 관련 객체(뷰, 인덱스등)를 만듦

6) 운영

① 구현된 데이터베이스를 기반으로 소프트웨어를 구축하여 서비스를 제공

7) 감시 및 개선

① 데이터베이스 운영에 따른 시스템의 문제를 관찰하고 데이터베이스 자체의 문제점을 파악하여 개선

(５) 트랜잭션

1) 트랜잭션(Transaction)의 특징

① 원자성(atomicity)

ü 자기 연산을 전부 또는 전무 실행만 한다.

② 일관성(consistency)

ü 트랜잭션 실행 후 일관성 있는 데이터베이스 상태로 변환한다.

③ 격리성(isolation)

ü 트랜잭션 실행 중 연산의 중간 결과에 다른 트랜잭션이 접근할 수 없다.

④ 영속성(durability)

ü 실행이 성공적으로 완료되면 그 결과는 영속적이다.

제1항 SQL 언어(DDL, DML, DCL, Embedded SQL)

(１) 개요

1) SQL은 현재 DBMS 시장에서 관계 DBMS가 압도적인 우위를 차지하는데 중요한 요인 중 하나이다.

2) SQL은 IBM 연구소에서 1974년에 System R이라는 관계 DBMS 시제품을 연구할 때 관계 대수와 관계 해석을 기반으로 집단함수, 그룹화, 갱신 연산등을 추가하여 개발된 언어이다.

3) 1986년에 ANSI(미국 표준 기구)에서 SQL 표준을 채택함으로써 SQL이 널리 사용되는데 기여

4) 다양한 상용 관계 DBMS마다 지원하는 SQL 기능에 다소 차이가 있음.

(２) 정의 (Structure Query Language)

1) 데이터베이스에서 정보를 얻거나 갱신하기 위한 표준화된 언어로서 대화형으로 이용하거나, 또는 프로그램내에 삽입하여 쓸수 있다.

(３) 분류

그림 58. SQL 분류

1) 데이터 정의어(DDL, Data Definition Language)

① 정의

ü 데이터베이스의 구조나 스키마를 가진 오브젝트를 다루는(생성(create), 삭제(drop), 변경(alter) 등) 데이터베이스 언어이다.

ü 키 제약조건, 개체(Entity) 무결성 제약조건, 참조 무결성 제약조건 등을 포함하는 관계 데이터베이스 스키마를 생성한다.

ü 데이터베이스 관리 시스템(DBMS) 에서 사용자의 편의와 구현상의 편의를 위해 명령어를 제공함

2) 데이터 조작어(DML, Data Manipulation Language)

① 정의

ü 사용자나 응용 프로그램과 데이터베이스 관리 시스템(DBMS) 간의 인터페이스를 제공

ü 데이터베이스 사용자에게 적절한 명령어를 사용하여 데이터를 수정하거나 데이터를 질의

3) 데이터 제어어(DCL, Data Control Language)

① 정의

ü 데이터의 보안, 무결성, 데이터 회복, 병행 수행 제어에 관련하여 데이터를 관리하기 위한 데이터 제어를 정의한다.

ü 데이터 관리자가 데이터를 관리할 목적으로 사용한다.

(４) 데이터 정의어(DDL, data definition language)

1) 제약조건

릴레이션 정의에서 다양한 제약 조건을 명시

① 무결성 제약조건

ü 속성(attribute) 제약조건

• Not null

- 널 값을 허용하지 않을 때

• Unique

- 동일한 속성값을 갖는 튜플이 두개 이상 존재하지 않도록 보장

• default

- default 값을 지정

• check

- 속성이 가질수 있는 값들의 범위 지정

ü 기본키(primary key) 제약조건

• 각 릴레이션마다 최소 한 개의 기본키 지정

ü 참조무결성 제약조건

• 외래키의 무결성 보장

• On delete no action

- 다른 테이블의 기존행에 있는 외래키에서 참조하는 키가 포함된 행을 삭제하려고 하면 오류가 발생하고 delete 문이 롤백되도록 지정

• On delete cascade

-  다른 테이블의 기존행에 있는 외래키에서 참조하는 키가 포함된 행을 삭제하려고 하면 해당 외래키가 포함되어 있는 모든 행도 삭제되도록 지정합니다.

• On delete set null

- 내용이 삭제된 외래키의 값을 null로 만든다.

• On delete set default

- 내용이 삭제된 외래키의 값을 default로 설정한다.

• On update no action

- 다른 테이블의 기존행에 있는 외래키에서 참조하는 키가 포함된 행에서 키 값이 업데이트하려고 하면 오류가 발생하고 update 문이 롤백되도록 지정합니다.

• On update cascade

- 다른 테이블의 기존행에 있는 외래키에서 참조하는 키값이 포함된 행에서 키값을 업데이트하려고 하면 해당 외래키를 구성하는 모든값도 키에 지정된 새 값으로 수정되도록 지정합니다.

• On update set null

- 내용이 수정된 외래키의 값을 null로 만든다.

• On update set default

- 내용이 수정된 외래키의 값을 default로 만든다.

2) CREATE

SQL에서는 동일한 데이터베이스 응용에 속하는 릴레이션, 도메인, 제약조건, 뷰, 권한등을 구룹화하기 위해서 스키마 개념을 지원한다.

① CREATE SCHEMA

ü 스키마를 정의한다. 스키마에 대한 정보는 연결한 데이터베이스의 시스템 카탈로그 테이블에 저장된다.

ü 스키마의 식별을 위한 스키마와 해당 스키마의 소유권자/허가권자를 정의함

ü 기본구조

• CREATE SCHEMA schema-name [ AUTHORIZATION schema-owner-name ]

• 여기서 schema-name은 스키마 이름입니다. 이 이름은 카탈로그에 이미 기록된 스키마 내에서 고유해야 합니다. 선택적 authorization절이 지정되어 있으면 schema-owner-name이 스키마의 소유자가 됩니다.

② CREATE DOMAIN

ü 도메인을 정의

ü 정의된 도메인명은 일반적인 데이터 타입처럼 사용

ü 기본구조

• Create domain 도메인이름 data-type default ‘기본값지정’

• Data-type의 종류

- 정수, 실수, 날짜, 시간

- 형식화 된 숫자

- 고정길이 문자, 가변길이 문자

- 고정길이 비트열, 가변길이 비트열

• 예제

- Create domain sung char(1) default ‘여’ constraint valid sung check (value in (‘남’, ‘여’));

③ CREATE TABLE

ü 테이블을 정의

ü 기본 구조

create table 테이블 명칭 {

(속성명 data-type),

Primary key (기본키 속성명),

Unique (대체키 속성명),

Foreign key (외래키 속성명),

References 참조테이블(기본키 속성명),

Check (조건식);

};

ü 예제

Create table 학생 {

학번 char(20),

이름 char(20) not null,

생년월일 date,

Primary key(학번),

Unique(생년월일),

Foreign key(과목코드) references 과목(과목코드)

On delete set null on update cascade,

Check 생년월일>=’1995-03-02’

};

④ CREATE VIEW

ü 사용자에게 접근이 허용된 자료만 보여주기 위해 하나 이상이 테이블에서 유도된 가상 테이블

ü 물리적으로 존재하지 않고 논리적으로만 존재

ü 기본 구조

Create view 뷰이름(속성명, …)

As select 속성명, …

From 테이블명

Where 조건;

[with check option]

ü 예제

Create view 컴퓨터(이름, 과목) as

             Select 이름, 과목

             From 학생

             Where 과목=’DB’;

⑤ CREATE INDEX

ü 검색 성능 향상 위해 사용

ü 기본 구조

• Create [unique] index 인덱스이름 on 기본테이블이름(속성이름 정렬방식)

ü 예제

• Create unique index 인덱스이름 on 고객(속성이름 정렬방식);

• 정렬방식: asc(오름차순),  desc(내림차순)

3) ALTER TABLE

① 테이블, 인덱스, 스키마 등에 대한 구조를 변경

② 기본 구조

ü Alter table 테이블이름 add 속성이름 data-type [default 값];

ü Alter table 테이블이름 alter 속성이름 data-type [set default 값];

ü Alter table 테이블이름 drop 속성이름 data-type [cascade];

③ 예제

ü Alter table 학생 add 주민번호 char(18);

ü Alter table 학생 drop 전화번호;

4) DROP

① 스키마, 도메인, 테이블, 뷰, 인덱스를 제거하는 명령문

② 기본 구조

Drop         schema 테이블 이름 [cascade | restrict]

                  Domain

                  Table

                  View

                  Index

Cascade : 릴레이션을 참조하는 뷰, 인덱스, 제약조건, 외래키 모두 삭제

Restrict : 다른 릴레이션에서 참조되지 않는 릴레이션만 제거

③ 예제

ü Drop schema 학교 cascade;

ü Drop table 학생 restrict;

※ 데이터 제어어(dcl)은 데이터의 보안, 무결성, 데이터 회복, 병행 수행 제어 등을 정의하는데 사용하는 언어이다.

(５) 데이터 조작어(DML, data manipulation language)

1) SELECT

① 테이블을 구성하는 튜플들 중에서 조건에 만족하는 튜플을 검색하여 임시 테이블을 만드는 명령

② 기본 구조

Select [all | distinct] 검색대상

From 테이블명

[where 조건식]

[group by 열명칭]

[having 검색조건]

[order by 열명칭 [asc | desc];

• Distinct : 중복된 데이터 한번만 출력

• Asc : 오름차순

• Desc : 내림차순

③ 설명

ü Select

• 질의 결과를 포함하려는 속성들을 열거

• Distinct 절을 사용해서 중복 제거

ü from

• 질의에서 필요로 하는 릴레이션들을 열거

ü where

• 관계대수의 셀렉션 연산의 조건에 해당

ü Group by

• 동일한 값을 갖는 튜플들을 한 그룹으로 묶는다

ü having

• 튜플들의 그룹이 만족해야 하는 조건

④ 별칭(alias)

ü 서로 다른 릴레이션에 동일한 이름을 가진 속성이 속해 있을 때 속성의 이름을 구분하는 방법

ü Select e.dno, d.dno from employee as e, department as d

⑤ 예제

ü 테이블의 전체 속성(*) 보기

• Select * from 테이블명

• 테이블의 존재하는 모든 튜플과 모든 속성을 보여준다.

ü 테이블에서 중복을 없앤 속성(attribute) 보기

• Select distinct 속성명 from 테이블명

• 테이블에서 지정한 속성만을 보여주는데, 중복된 속성은 하나만 보여준다.

ü 테이블에서 조건에 만족하는 튜플만 보기

• Select * from 테이블명 where 속성명 <> ’값’

• 테이블에서 지정된 속성의 값이 일치하는 튜플만을 보여준다.

• 부정연산자 : <>

ü 테이블에서 여러 개의 조건을 만족하는 튜플만 보기

• Select * from 테이블명 where 속성명=’값’and 속성명=’값’

• 테이블에서 지정된 속성들의 값과 일치하는 튜플만을 보여준다.

• 연산자들의 우선순위

ü 테이블에서 % 조건에 만족하는 튜플만 보기

• Select * from 테이블명 where 속성명 like ‘류%’

• 테이블에서 지정된 속성의 값이 ‘류’로 시작하는 모든 튜플을 보여준다.

• ‘%’는 모든 문자를 말하며, ‘_’는 한 문자를 의미함

ü 테이블에서 범위 조건에 만족하는 튜플만 보기

• Select * from 테이블명 where 속성명 between 0 and 100

• Select * from 테이블명 where 속성명 >= 0 and 속성명 <= 100

• 속성명의 값이 0보다 크거나 같고 100보다 작거나 같은 튜플만 보여준다.

ü 테이블에서 지정된 속성의 값이 null인 모든 튜플 보기

• Select * from 테이블명 where 속성명 is null

• Select * from 테이블명 where 속성명 is not null

⑦ Group by 속성 [having 조건]

ü 조건에 맞게 속성들을 그룹별로 처리한다.

ü Group by는 특정 속성을 기준으로 그룹화하여 검색할 때 그룹화 할 속성을 지정한다.

ü Having은 group by와 함께 사용되며, 그룹에 대한 조건을 지정한다.

ü 예제

• Select 속성명, count(*) as 표시명 from 테이블명 where 속성명 >= 90 group by 과목 having count(*)>=2

⑧ Order by 속성 [asc | desc]

ü 지정된 속성으로 정렬을 한다.

ü Asc: 오름차순(a-z, ㄱ-ㅎ), desc: 내림차순(z-a, ㅎ-ㄱ)

ü 예제

• Select * from 속성명 where 속성명=’값’ order by 속성명 desc

• 속성명이 ‘값’이 튜플을 보여주는데, order by에 지정된 속성명으로 내림차순 정렬을 해서 보여준다.

⑨ in

ü 조건절에 명시된 속성값이 in 다음에 나열되는 값들과 일치되는 튜플들만 표시한다.

ü Select * from 테이블명 where 속성명 in (select 속성명 from 테이블명)

⑩ Null 값

ü 널값을 포함한 다른 값과 널값을 +, - 등을 사용하여 연산하면 결과는 널이 됨

ü Count(*)를 제외한 집단 함수들은 널값을 무시함

ü 어떤 속성에 들어 있는 값이 널인지 비교하기 위해서 ‘속성=null’ 처럼 사용하면 안됨

ü 다음과 같은 비교 결과는 모두 거짓

• Null > 300

• Null = 300

• Null <> 300

• Null = null

• Null <> null

ü 바른 표현

• Select * from 테이블명 where 속성 is null;

⑪ 집단함수

ü 정의

• 각 집단함수는 한 릴레이션의 한 개의 속성에 적용되어 단일값을 변환함

• Select절과 having절에만 나타날 수 있음

• count(*)를 제외하고는 모든 집단함수들이 널값을 제거한 후 남아 있는 값들에 대해서 집단 함수의 값을 구함

• count(*)는 결과 릴레이션의 모든 행들의 총 개수를 구함

• count(속성명)는 해당 속성에서 널값이 아닌 값들의 개수를 구함

• distinct가 집단 함수 앞에 사용되면 집단 함수가 적용되기 전에 먼저 중복을 제거함

ü 종류

• Count(속성): 튜플이나 값들의 개수

• Avg(속성): 값들의 평균값

• Sum(속성): 값들의 합

• Max(속성): 값들의 최대값

• Min(속성): 값들의 최소값

⑫ Exists(q), not exists(q)

ü Exists: 질의 q의 결과에 최소한 한 개의 튜플이 있으면 참, 그렇지 않으면 거짓을 반환한다.

ü Not exists: 질의 q의 결과에 튜플이 없다면 참, 그렇지 않으면 거짓을 반환한다.

⑬ 비교연산자

ü = : 같다

ü <> : 같지 않다

ü > :크다

ü < :작다

ü >= : 크거나 같다

ü <= : 작거나 같다

ü In : 포함되어 있다

⑭ select에서의 집합 연산

ü 정의

• 집합연산을 적용하려면 두 릴레이션이 합집합 호환성을 가져야 함

• 입력 릴레이션 결과 릴레이션에서 중복 튜플 배제

- Union(합집합)

- Except(차집합)

- Intersect(교집합)

• 입력 릴레이션 결과 릴레이션에서 중복 튜플 허용

- Union all(합집합)

- Except all(차집합)

- Intersect all(교집합)

⑮ select에서의 조인(join)

ü 정의

• 조인은두개의 릴레이션으로부터 연관된 튜플들을 결합

• 조인의 일반적인 형식은 아래의 select문과 같이 from절에 두개 이상의 릴레이션들이 열거되고, 두 릴레이션에 속하는 애트리뷰트들을 비교하는 조인 조건이 where절에 포함됨

• 조인 조건은 두 릴레이션 사이에 속하는 속성값들을 비교 연산자로 연결한 것

• 가장 흔히 사용되는 비교 연산자 ‘=’

• 조인 조건을 생략했을 때와 조인 조건을 틀리게 표현했을 때는 카티션 곱이 생성됨

• 조인 질의가 수행되는 과정을 개념적으로 살펴보면 먼저 조인 조건을 만족하는 튜플들을 찾고, 이 튜플들로부터 SELECT절에 명시된 속성들만 프로젝트하고, 필요하다면 중복을 배제하는 순서로 진행됨

• 조인 조건이 명확해지도록 속성 이픔 앞에 릴레이션 이름이나 튜플변수를 사용하는 것이 바람직

• 두 리레이션의 조인 속성명이 동일하다면 반드시 속성명앞에 릴레이션 이름이나 튜플변수를 사용해야 함

2) INSERT

① 데이터베이스에 저장된 튜플을 삽입하기 위한 언어

② 기본 구조

Insert into 테이블명

Values (데이터 값, 데이터 값2, …);

③ 예제

ü 테이블에 튜플을 추가해라

• Insert into 테이블명 values (‘값1’, ‘값2’, ‘값3’)

• 지정된 테이블에 튜플을 추가한다.

ü 테이블에 지정된 속성들의 값을 추가해라

• Insert into customers (customerName, ContactName, Address, City, PostalCode, Country) values (‘Cardinal’, “Tom’, ‘Skagen’, ‘Stavanger’, ‘4006’, ‘Norway’);

ü 테이블에 지정된 속성들의 값을 추가해라

• Insert into Customers (CustomerName, City, Country) values (‘Cardinal’, ‘Stavanger’, ‘Norway’)

ü 테이블에 지정된 속성들의 값을 추가해라

• Insert into Customers (CustomerName, City, Country) values (‘Cardinal’, ‘Stavanger’, ‘Norway’)

Customers 테이블

Suppliers 테이블

ü 여러 개의 튜플들을 추가해라

• Insert into Customers (CustomerName, Country) select SupplierName, Country from Suppliers;

• Insert into Customers (CustomerName, Country) select SupplierName, Country from Suppliers where country=’USA’;

3) UPDATE

① 테이블에 있는 튜플들 중에서 지정된 튜플의 내용을 수정할 때 사용하는 언어

② 기본 구조

Update 테이블명

Set 열명칭 = 변경값

[where 조건식];

③ 예제

ü 지정된 튜플의 값을 변경하라.

• Update Customers set ContactName=’Alfred Schmidt’, City=’Hamburg’ where CustomerName=’Alfreds Futterkiste’;

4) DELETE

① 테이블에 있는 튜플들 중에서 지정된 튜플을 삭제할 때 사용하는 언어

② 기본 구조

Delete from 테이블명

[where 조건식];

③ 예제

ü 지정된 튜플을 삭제하라

• Delete from Customers where CustomerName=’Alfreds Futterkiste’;

ü 테이블의 모든 튜플을 삭제하라

• Delete from Customers

• Delete * from Customers

• 테이블에 있는 모든 튜플들이 삭제되는 것이지 테이블 자체가 삭제되는 것은 아니다. 테이블 자체를 삭제하는 명령어는 drop 이다.

(６) 데이터 제어어(DCL, data control language)

1) GRANT

① 데이터베이스 사용자에게 사용권한 부여

② 기본 구조

Grant 권한 on 테이블명 to 사용자명 [with grant option];

③ 예제

• Grant select on 테이블명 to rhk [with grant option];

• 권한: all, insert, delete, update, select 등

• With grant option : 사용자가 받은 권한을 다른 사용자에게 부여할 수 있음

2) REVOKE

① 데이터베이스 사용자의 사용 권한을 취소

② 기본 구조

Revoke 권한 on 테이블명 from 사용자명 [cascade];

③ 예제

• Revoke select on 수강생 from rhk [cascade]

• Cascade : 권한을 부여받은 사용자가 다른 사용자에게 부여한 권한도 취소

3) COMMIT

① 데이터베이스 조작 작업을 영구적으로 반영하여 완료함

4) ROLLBACK

① 데이터베이스 조작 작업이 비정상적으로 종료되었을 때 원래의 상태로 복구

제1항 관계데이터언어(관계대수, 관계해석)

관계 데이터베이스의 릴레이션을 조작하기 위한 기본연산에는 관계대수(relational algebra)와 관계해석(relational calculus)이 있다. 이 연산은 사용자의 입장에서 볼 때 데이터를 처리하는 데이터 언어가 되며 관계대수는 절차적 언어이며 관계해석은 비절차적 언어이다.

(１) 관계대수(relational algebra)

1) 대수

① 수 대신 문자를 사용해서 문제를 쉽게 하고, 수학적인 법칙을 간단하고 명확하게 표현하는 것

2) 관계대수 정의

① 관계대수는 E.F. Codd가 관계 데이터 모델을 처음 제안할 때 정의

② 관계 대수(relational algebra)는 관계 해석(relational calculus)과 함께 관계 데이터 모델에서 릴레이션을 처리하기 위한 정형적인 데이터 언어이다. 이 관계 대수는 원하는 데이터를 얻기 위해서 어떻게(how) 질의를 수행할 것인지 일련의 연산을 순서대로 명시해야 하는 절차적 언어이다.

③ 데이터베이스에 저장된 데이터를 문자와 연산을 통해 요청한 데이터를 정보화하여 얻을 수 있는데 그 원리가 산술 연산자와 유사

④ 관계 데이터베이스의 관계(relation), 즉 테이블을 조작하는 언어

⑤ 하나 또는 그 이상의 테이블을 피연산자로 하여 결과로 하나의 테이블을 만들어내는 연산을 말한다.

⑥ 관계대수는 질의에 대한 결과를 생성하기 위해 수행해야 할 연산의 순서를 명시하는 절차적 언어이다.

⑦ 연산자의 종류

3) 순수 관계 연산자

① 디비전(division)

ü 나누어지는 릴레이션인 A는 릴레이션 B의 모든 튜플에 연관되어 있는 A의 튜플을 선택한다.

ü X⊃Y인 2개의 릴레이션에서 R(X)와 S(Y)가 있을 때, R의 속성이 S의 속성값을 모두 가진 튜플에서 S가 가진 속성을 제외한 속성만을 구함

ü R[속성r ÷ 속성s]S

② 프로젝트(project, P)

ü 릴레이션에서 주어진 조건에 만족하는 속성(attribute)만을 검색하는 연산

ü 형식 : P속성리스트(R)

ü 릴레이션의 열(세로)에 해당하는 속성들을 추출하는 연산자로써 수직 연산을 수행

③ 조인(join, ⋈)

ü 릴레이션에서 조건에 만족하는 레코드를 분리해 내는 연산을 의미하는 것으로 하나의 릴레이션에서 수평적인 부분 집합을 취하는 것이다.

ü 두개의 릴레이션으로부터 연관된 튜플들을 결합하는 연산자

ü 공통 속성을 중심으로 두개의 릴레이션을 하나로 합쳐서 새로운 릴레이션을 만듦

• Natural join(자연 조인)

- 동등 조인의 결과 릴레이션에서 조인 속성을 한 개 제외한 조인

- 여러가지 조인 연산자들 중에서 가장 자주 사용됨

• Equi join(동등 조인)

- 동등 조인의 결과 릴레이션에서 조인 속성을 모두 나타낸다.

ü 학생[학번⋈학번]성적

④ 셀렉트(selection, σ)

ü 릴레이션에서 주어진 조건을 만족하는 튜플들을 선택하는 연산자

ü σ조건(R)

ü 튜플 단위로 조건에 만족하는 튜플들을 가져오는 수평 연산을 수행

ü 학생 릴레이션에 대한 셀렉션 연산

4) 일반 집합연산자

① 집합 연산자

ü 릴레이션이 튜플들의 집합이기 때문에 기존의 집합 연산이 릴레이션에 적용

ü 집합 연산자의 입력으로 사용되는 두개의 릴레이션은 합집합 호환(union compatible)이어야 함

② 합집합(union)

ü 합병 가능한 두 릴레이션 A 또는 B에 속하는 튜플들로 구성된 릴레이션이다.

ü 두 릴레이션 R과 S의 합집합 R∪S는 R 또는 S에 있거나 R과 S 모두에 속한 튜플들로 이루어진 릴레이션

ü 결과 릴레이션에서 중복된 튜플들은 제외됨

③ 교집합(intersection)

ü 합병 가능한 두 릴레이션 A와 B에 공통적으로 속하는 튜플들로 구성된 릴레이션이다.

ü 두 릴레이션 R과 S의 교집합 R∩S는 R과 S 무두에 속한 튜플들로 이루어진 릴레이션

④ 차집합(difference)

ü 합병 가능한 두 릴레이션 A에만 있고 B에는 없는 튜플들로 구성된 릴레이션이다.

ü 두 릴레이션 R과 S의 차집합 R – S는 R에는 속하지만 S에는 속하지 않은 튜플들로 이루어진 릴레이션

⑤ 카티션 곱(cartesian product)

ü A에 속한 각 튜플 a에 대하여 B에 속한 튜플 b를 모두 접속시킨 튜플들(a, b)로 구성된 릴레이션이다.

5) 관계 대수의 한계

① 관계 대수는 산술 연산을 할 수 없음

② 집단 함수(aggregate function)를 지원하지 않음

③ 정렬을 나타낼 수 없음

④ 데이터베이스를 수정할 수 없음

⑤ 프로젝션 연산의 결과에 중복된 튜플을 나타내는 것이 필요할 때가 있는데 이를 명시하지 못함.

6) 추가된 관계 대수 연산자

① 집단함수(aggregate function)

ü 모든 사원들의 급여 평균은 얼마인가?

② 그룹화

ü 각 부서별 사원들의 급여 평균은 얼마인가?

③ 외부조인

ü 상대 릴레이션에서 대응되는 튜플을 갖지 못하는 튜플이나 조인 속성에 널값이 들어 있는 튜플들을 다루기 위해서 조인 연산을 확장한 조인

ü 두 릴레이션에서 대응되는 튜플들을 결합하면서, 대응되는 튜플을 갖지 않는 튜플과 조인 애트리뷰트에 널값을 갖는 튜플도 결과에 포함시킴

ü 왼쪽 외부 조인(LEFT OUTER JOIN), 오른쪽 외부 조인(RIGHT OUTER JOIN), 완전 외부 조인(FULL OUTER JOIN)

④ 왼쪽 외부조인

ü 릴레이션 R과 S의 왼쪽 외부 조인 연산은 R의 모든 튜플들을 결과에 포함시키고, 만일 릴레이션 S에 관련된 튜플이 없으면 결과 릴레이션에서 릴레이션 S의 속성값을 널값으로 채움

⑤ 오른쪽 외부조인

ü 릴레이션 R과 S의 오른쪽 외부 조인 연산은 S의 모든 튜플들을 결과에 포함시키고, 만일 릴레이션 R에 관련된 튜플이 없으면 결과 릴레이션에서 릴레이션 R의 속성값을 널값으로 채움

⑥ 완전 외부조인

ü 릴레이션 R과 S의 완전 외부 조인 연산은 R과 S의 모든 튜플들을 결과에 포함시키고, 만일 상대 릴레이션에 관련된 튜플이 없으면 결과 릴레이션에서 상대 릴레이션의 속성값을 널값으로 채움

(２) 관계해석(relational calculus)

1) 정의

① 원하는 데이터만 명시하고 질의를 어떻게 수행할 것인가는 명시하지 않는 선언적인 언어

2) 관계해석의 특징

① 비절차 언어

② 튜플 관계 해석과 도메인 관계 해석이 있다.

③ 기본적으로 관계해석과 관계대수는 관계 데이터베이스를 처리하는 기능과 능력면에서 동등함

④ 수학의 predicate calculus에 기반을 두고 있음

⑤ 관계해석으로 질의어를 표현

⑥ 원하는 릴레이션을 정의하는 방법을 제공, 즉 원하는 정보가 무엇이라는것만 정의하는 비절차적인 언어

⑦ 연산들의 절차(sequence)를 사용하여 데이터를 가져옴

⑧ 기본적인 연산자로 union, intersection, difference를 사용함

⑨ 전체관계를 조작하는데 사용되는 연산들의 집합

제1항 관계데이터모델

(１) 정의

1) 열과(column)과 행(row)으로 이루어진 테이블(릴레이션, relation)과 수학적으로 정의된 연산들로 구성된 것

2) 논리적인 데이터 모델에서 데이터간의 관계를 기본키(primary key)와 이를 참조하는 외래키(foreign key)로 표현하는 데이터 모델

3) 개체 집합에 대한 속성 관계를 표현하기 위해 개체를 테이블(table)로 사용하고 개체 집합들 사이의 관계를 공통 속성으로 연결하는 독립된 형태의 데이터 모델

4) 1970년 E.F.Codd의 논문에서 언급된 개념이다.

5) 관계 데이터 모델의 핵심은 릴레이션(relation) 이다.

① 릴레이션(relation)

ü 정의

• 열(column)과 행(row)으로 이루어진 테이블을 말한다.

• 릴레시션 스킴(relation scheme)과 릴레이션 인스턴스(relation instance)로 구성된다.

ü 특성

• 한 릴레이션에는 중복된 투플이 존재하지 않음.

• 한 릴레이션에 저장된 투플들 간에는 순서가 없음.

• 한 릴레이션을 구성하는 속송들간에는 순서가 없음.

• 모든 속성값은 원자값(atomic value) 이다.

그림 42. relation database schema

(２) 특징

1) 데이터와 데이터간의 관계가 테이블로 표현된다.

2) 테이블(table) = 릴레이션(relation)

3) 구조가 간단해서 이해하기 쉬우며, 데이터 조작면에서도 명확하다.

(３) 관계형 모델용어 vs DBMS 용어

1) 릴레이션(relation)

① 열과 행을 가지는 테이블

② 테이블(table), 개체(entity), 파일(file)과 같은 개념

※ 속성(attribute)의 원자값

모든 속성값은 원자값(atomic value) 이다. 이 성질이 뚯하는 것은 더 이상 분해할 수 없는 원자값을 의미한다.

2) 속성(attributes)

① 개체의 성질, 분류, 식별, 수량, 상태 등을 나타내는 세부 정보의 관리 요소로서 개체를 구성하는 항목

② 열(column), 필드(field), 항목(item)과 같은 개념

3) 튜플(tuple)

① 릴레이션의 행을 구성하는 속성(attribute) 값들의 집합

② 행(row), 레코드(record)와 같은 개념

4) 차수(degree)

① 속성(attribute)들의 수

5) 카디날리티(cardinality)

① 튜플(tuple)들의 수

6) 도메인(domain)

① 하나의 속성(attribute)가 취할 수 있는 같은 타입의 원자(atomic) 값들의 집합

② 표현되는 속성 값의 범위를 나타냄

③ 예) 성별의 도메인은 ‘남’, ‘여’ 만이 가능.

7) 릴레이션 인스턴스(relation instance)

① 릴레이션의 어느 시점에 들어 있는 튜플들의 집합 (동적인 성질)

② 튜플들의 집합으로 현재 들어가 있는 실제 데이터를 지칭한다

(４) 키(key)

1) 정의

① 데이터베이스에서 조건에 만족하는 튜플(tuple)을 찾거나 순서대로 정렬할 때 튜플들을 서로 구분할 수 있는 기준이 되는 속성(attribute)들을 말한다.

2) 특성

① Not null

ü 속성의 값은 null이 될수 없다. (null = undefined)

• 기본키의 속성값은 not null이다.

ü Null

• 데이터베이스에서 아직 알려지지 않거나 모르는 값으로서 해당 없음등의 이유로 정보 부재를 나타내기 위해 사용하는 특수한 데이터 값이다. 즉, 공백(space)도, 영(zero)도 아닌 부재정보(missing information)를 나타냄

② 유일성(uniqueness)

ü 하나의 키 값으로 하나의 튜플만을 유일하게 식별할 수 있어야 함

ü 속성의 집합인 키의 내용이 릴레이션 내에서 유일하다는 특성임

ü 즉, 릴레이션 내에서는 중복되는 튜플이 존재하지 않는 것을 말함

ü 유일성을 만족하는 키의 종류

• 기본키(primary key) : 후보키중에서 선택된 키이므로 유일성과 최소성 모두 만족한다.

• 후보키(candidate key) : 유일성과 최소성 모두 만족

• 슈퍼키(super key): 유일성만 만족

③ 최소성(minimality)

ü 속성의 집합인 키가 릴레이션의 모든 튜플을 유일하게 식별하기 위해 꼭 필요한 속성들로 구성된 것을 의미한다.

ü 즉, 속성들의 집합에서 특정 속성 하나를 제거하면 튜플을 유일하게 식별할 수 없는 경우에 해당 함.

ü 최소성을 만족하는 키의 종류

• 후보키(candidate key) : 유일성과 최소성 모두 만족

• 기본키(primary key): 후보키에서 선택된 키이므로 유일성과 최소성 모두를 만족한다.

3) 종류

① 후보키(candidate key)

ü 릴레이션을 구성하는 속성들 중에서 튜플을 유일하게 식별할 수 있는 하나 또는 몇 개의 속성(attribute)의 집합

ü 유일성과 최소성을 모두 만족

② 기본키(primary key)

ü 릴레이션의 유일한 식별자

ü 릴레이션에서 기본키 지정된 속성(attribute)은 같은 값을 가질 수 없다.

ü 후보키 중에서 선정된 키로 중복값을 가질 수 없다.

ü 후보키의 성질을 가짐 (유일성, 최소성 모두 만족)

ü 기본키의 특성

• Not null

• Unique

• 외래키(foreign key)로 참조될 수 있다.

③ 대체키(alternate key)

ü 후보키가 둘 이상 되는 경우에 기본키로 선택되지 못한 후보키들을 대체키라고 한다.

ü 후보키 = 기본키 + 대체키

④ 슈퍼키(super key)

ü 유일성만 있고 최소성이 없는 속성(attribute)의 집합을 말한다.

⑤ 외래키(foreign key)

ü 한 테이블의 키 중 다른 테이블의 튜플을 식별할 수 있는 키를 말한다.

4) 키와 데이터 무결성

① 정의

ü 권한이 부여된 사용자에 의하여 발생할 수 있는 데이터베이스의 오류를 방지하기 위함

ü 데이터의 정확성, 일관성, 신뢰성을 위해 무효 갱신으로부터 데이터를 보호하여 관계 데이터베이스를 의미 있게 하는 제약조건

② 기본 데이터 무결성

제1항 정렬, 탐색기법

(１) 정렬

1) 정렬(sort)의 정의

① 레코드나 데이터에 담긴 키값에 따라 순서대로 나열하는 것

② 정렬은 정렬되지 않은 항목 또는 레코드의 리스트를 각 레코드의 값에 기초한 기준에 따라 순서 있게 나열하는 것이다.

③ 초기에 정렬되지 않은 레코드의 순서를 정렬될 때까지 재배치하는 과정

그림 37. 정렬의 종류

2) 정렬기법

① 내부정렬기법

ü 정의

• 데이터량이 적을 때 주기억장치 내에서 정렬하는 방법

ü 특징

• 속도는 빠르나, 정렬할 자료의 양이 많은 경우 부적합

ü 종류

• 히프 정렬(heap sort)

• 기수 정렬(radix sort)

• 선택 정렬(selection sort)

• 버블 정렬(bubble sort)

• 퀵 정렬(quick sort)

• 삽입 정렬(insertion sort)

• 쉘 정렬(shell sort)

② 외부정렬기법

ü 정의

• 대용량의 데이터를 몇 개의 서브 파일로 나누어 각각 내부 정렬을 한 후에 테이프나 디스크 내에서 각 서브 파일을 합병하는 방법

ü 특징

• 속도는 느리지만 정렬하고자 하는 자료의 양이 많을 경우 효과적 (주기억장치+보조기억장치)

ü 종류

• 진동 병합 정렬(oscillating merge sort)

• 밸런스 병합 정렬(balanced merge sort)

• 캐스캐이드 병합 정렬(cascade merge sort)

• 폴리파즈 병합 정렬(polyphase merge sort)

3) 정렬기법 종류

① 버블 정렬(bubble sort)

• 버블정렬은 인접한 두 키를 비교한 결과로 정렬하는데 만약 비교하였을 때 두 키의 순서가 다르다면 교환하고 그렇지 않다면 그대로 두는 방법이다.

• 정렬과정이 물속 깊은 곳에서 일어난 거품이 수면을 향해 올라오는 모습과 같다고 해서 붙여진 이름이다.

② 삽입 정렬(insertion sort)

• 데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아내어 이를 다시 적당한 곳에 삽입해 나가는 알고리즘

- 데이터 집합에서 정렬 대상이 되는 요소들을 선택합니다. 이 정렬 대상은 왼쪽부터 선택해 나가며, 그 범위가 처음에는 2개이지만 알고리즘 반복횟수가 늘어날 때마다 1개씩 커집니다. 정렬 대상의 최대 범위는 “데이터 집합의 크기 – 1” 이 됩니다.

- 정렬 대상의 가장 오른쪽에 있는 요소가 정렬 대상 중 가장 큰 값을 갖고 있는지 확인합니다. 만약 그렇지 않다면, 이 요소를 정렬 대상에서 뽑아내고, 이 요소가 위치할 적절한 곳을 정렬 대상 내에서 찾습니다. 여기서 적절한 곳이라 함은 데이터 집합의 가장 왼쪽을 기준으로 했을 때 자신보다 더 작은 요소가 없는 위치를 말합니다.

- 뽑아 든 요소를 삽입할 적절한 곳을 찾았다면, 정렬 대상 내에서 삽입할 값보다 큰값을 갖는 모든 요소를 한자리씩 오른쪽으로 이동시키고 새로 생긴 빈 자리에 삽입시킵니다.

- 전체 대이터 집합의 정렬이 완료될 때까지 1~3를 반복합니다.

• 이 정렬 알고리즘은 지급 완료 수표나 카드를 정렬된 채로 손에 쥐고서 그것들 사이에 적당한 위치에 정렬되지 않은 것을 한 개씩 삽입할 때 발생할 수 있다.

③ 선택 정렬(selection sort)

• 레코드의 최소값을 찾아 첫 번째 위치에 놓고 다음 최소값을 찾아 두 번째 위치에 놓는 방법을 반복하여 정렬함.

④ 히프 정렬(heap sort)

• 연산 시간이 최악과 평균의 경우, 모두 0(n logⁿ)으로 빠른 속도를 가짐

• 전이진 트리(complete tree)를 이용한 정렬 방식

• 이진 트리를 힙 정렬로 변환

- 주어진 레코드들을 순서대로 넣어 진이진 트리로 구성

- 전이진 트리의 노드의 역손으로 자식노드와 부모노드를 비교하여 큰값을 위로 올림

- 교환된 노드들을 다시 검토하여 위의 고정을 반복한다.

⑤ 퀵 정렬(quick sort)

• 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어가면서 정렬하는 방법으로 키를 기준으로 작은 값은 왼쪽에 큰 값은 오른쪽에 모이도록 서로 교환시키는 부분 교환 정렬법

⑥ 기수 정렬(radix sort)

• 레코드의 키 값을 분석하여 같은 수 또는 같은 문자끼리 그 순서에 맞는 버킷에 분배하였다가 버킷의 순서대로 레코드를 꺼내어 정렬하는 기법

⑦ 2-way 합병 정렬

• 주어진 입력 파일을 크기가 2인 서브 파일로 모두 나누어서 각 서브 파일들을 정렬하는 방법

4) 정렬 알고리즘의 선택 시 고려사항

① 키 값들의 분포상태

② 소요 공간 및 작업시간

③ 정렬에 필요한 기억공간의 크기

④ 데이터의 양

⑤ 초기 데이터의 배열상태

⑥ 사용 컴퓨터 시스템의 특성

(２) 탐색기법

1) 탐색기법의 종류

① 이진 검색(binary search)

ü 일정한 순서로 배열된 레코드를 2개 부분으로 되풀이하여 나누어서 한 부분은 버리고 남은 부분을 검색하는 방법

ü 자료가 반드시 정렬되어 있어야 함 (이진 검색의 선행 조건)

ü 정렬된 연접 리스트에서 특정 레코드가 있다고 알려진 리스트의 남겨진 반쪽 부분을 되풀이하여 보면서 특정 레코드를 찾는 빠른 방법

ü 다음과 같이 R={2,3,5,7,8,9,10} 일 때, 이진 검색 방법으로 8을 찾을 경우 비교 횟수는?

② 보간 검색(Interpolation search)

ü 찾고자 하는 레코드 키가 있음직한 위치를 추정하여 검색하는 방법

2) 해싱(hashing)

① 해싱의 정의

ü 키 값으로부터 레코드가 저장되어 있는 주소를 직접 계산하여, 산출된 주소로 바로 접근하는 방법, 키-주소 변환 방법이라고도 함

ü 검색 방법 중 속도는 가장 빠르지만 충돌현상 시 오버플로 해결의 부담이 과중되며 많은 기억공간을 요구하는 검색 방법

② 해시 테이블(hash table)

ü 자료가 저장되는 전체 저장소를 해시 테이블(hash table)이라고 한다.

ü 해시 테이블은 여러 개의 버킷(bucket)으로 나누어지는데 데이터를 삽입할 때 데이터의 값으로부터 적절한 버킷을 선택해서 삽입해야 한다.

ü 버킷은 여러 개의 슬롯(slot)으로 구성되는데 슬롯은 버킷에 데이터가 저장되는 단위이다. 예를 들면 주소록의 각 페이지별로 한 명만 적을 수 있는 것이 아니라 여러명을 적을 수 있어야 하는데 이때 한명의 주소를 적는 칸을 슬롯이라고 한다.

ü 버킷(bucket)

• 하나의 주소를 갖는 파일의 한 구역을 의미하며, 버킷의 크기는 같은 주소에 포함될 수 있는 레코드 수를 의미

ü 슬롯(slot)

• 한 개의 레코드를 저장할 수 있는 공간으로 n개의 슬롯이 모여 하나의 버킷을 형성

ü 충돌(collision)

• 레코드를 삽입할 때 2개의 상이한 레코드가 똑 같은 주소로 해싱 되는 것을 의미

ü 동의어(synonym)

• 해싱 함수의 값이 같은 키들의 집합

③ 해싱함수의 종류

ü 중간제곱(mid-square) 방법

• 레코드의 키를 제곱한 후 그 중간 부분의 값을 목적 주소로 사용하는 방법

ü 숫자분석(digit analysis) 방법

• 레코드 키를 구성하는 수들이 모든 키들 내에서 각 자리별로 어떤 분포인지를 조사하여 비교적 고른 분포를 나타내는 자릿수를 필요한 만큼 선택하여 목적 주소로 사용하는 방법

ü 제산(division) 방법

• 레코드의 키를 해시테이블의 크기보다 큰 소수로 나누는 방법

ü 중첩(접지) 방법(Folding method)

• 주어진 키를 여러 부분으로 나누고, 각 부분의 값을 더하거나 배타적 논리합(XOR, exclusive OR) 연산을 통하여 나온 결과로 주소를 취하는 방법

ü 기수(radix) 변환법

• 어떤 진법으로 표현된 주어진 레코드 키 값을 다른 진법으로 간주하고 키 값을 변환하여 홈 주소로 취하는 방식

④ 오버플로 처리방법

ü 충돌(collision)이 발생했을 때 버킷에 저장할 슬롯이 없다면 오버플로우가 발생한다.

ü 재해싱 방법(rehashing)

• 여러 개의 해싱함수를 준비하였다가 충돌 발생시 새로운 해싱함수를 적용하여 새로운 해시표를 생성하는 방법

ü 개방 주소법(open addressing)

• 충돌(collision)이 발생했을 때 순서대로 다음 버킷에 저장하는 방법

ü 체인방법

• 오버플로우 발생시 이를 별도의 기억 공간에 두고 링크로 연결하여 사용하는 방법

ü 폐쇄 주소법(close addression)

• 별도의 오버플로우 영역에 저장하고 체인(chain)으로 홈 버킷에 연결한다.

• Direct chaining: 해시 테이블 내의 빈 공간에 오버플로우 레코드를 보관한다.

• Indirect chaining: 해시 테이블과는 별도의 기억공간에 오버플로우 레코드를 보관한다.

제2항 인덱스구조

(１) 인덱스 (index)

1) 인덱스의 정의

① 검색을 빠르게 하기 위해 만든 보조적인 데이터 구조

② B트리, B+트리, 트라이 등의 자료구조를 사용하여 구현함

③ 인덱스 파일

ü 검색수를 줄이기 위해 다단계 인덱스를 사용

2) 인덱스의 특징

① 인덱스는 하나 이상의 필드로 만들어도 됨

② 인덱스를 통해서 테이블의 레코드에 대한 액세스를 빠르게 수행할 수 있음

3) 트라이 (trie)

① 검색을 위한 키값을 직접 표현하지 않고 키를 구성하는 문자나 숫자 자체의 순서로 키값을 구성하는 구조

② 트라이의 차수는 키 값을 표현하기 위해 사용하는 문자의 수(radix)에 의해 결정함

③ 키 값의 분포를 미리 예측할 수 있다면 기억장소를 절약할 수 있음

④ 트라이의 크기는 나타내려고 하는 키 값의 기수와 키 필드 길이에 의해 결정됨

⑤ 키 값이 문자열 또는 숫자일 경우 일련의 키 값들에 대해 일부분이 같은 문자나 숫자로 구성되었을 때, 즉 전체 키 값의 길이보다 키 값들 사이에 별개의 전위(prefix) 수가 작을 때 적합함

⑥ 가변 길이의 키 값을 효과적으로 나타낼 수 있으며, 삽입 및 삭제 시 노드의 분열과 병합이 없음

4) 인덱스 구분

① 정적인덱스

ü 데이터 파일의 레코드가 삽입되거나 삭제됨에 따라 인덱스의 내용은 변하지만 구조자체는 변하지 않음

② 동적인덱스

ü 인덱스나 데이터파일을 블록으로 구성하고 각 블록에는 추가로 삽입될 레코드를 감안하여 빈 공간을 미리 예비해두는 인덱스 방법

ü 레코드의 삽입으로 인해 블록에 레코드가 가득 차면 동적으로 분열 됨

ü 레코드의 삭제로 인해 일정 수의 레코드가 블록에 유지되지 않으면 블록의 합병이 일어남

제1절 자료구조의 기본

제1항 자료구조의 개요

(１) 자료구조란?

그림 13. 자료구조

1) 자료를 효율적으로 사용하기 위해서 자료의 특성에 따라서 분류하여 구성하고 저장 및 처리하는 모든 작업

2) 컴퓨터에서 처리할 자료를 효율적으로 관리하고 구조화시키기 위한 학문이다. 자료를 효율적으로 사용하기 위해서 자료의 특성에 따라서 분류하여 구성하고 저장 및 처리하는 모든 작업을 의미한다.

3) 자료구조에 따라 저장공간의 효율성과 프로그램의 실행시간이 달라짐

(２) 컴퓨터 분야에서 자료구조를 배우는 이유?

1) 컴퓨터가 효율적으로 문제를 처리하기 위해서는 문제를 정의하고 분석하여 그에 대한 최적의 프로그램을 작성해야 한다.

2) 자료의 특성을 이해하고 분석하여 최적의 알고리즘을 개발하는 능력이 필요

(３) 자료구조에서 다루는 내용

(４) 자료구조의 분류

1) 단순구조

① 정수, 실수, 문자, 문자열 등의 기본 자료형

2) 선형구조

① 자료들 간의 앞뒤 관계가 1:1의 선형관계

② 리스트, 연결리스트, 스택, 큐, 덱 등

3) 비선형구조

① 자료들 간의 앞뒤 관계가 1:n, 또는 n:n 의 관계

② 트리, 그래프 등

4) 파일구조

① 레코드의 집합인 파일에 대한 구조

② 순차파일, 색인파일, 직접파일 등

기출문제) 비선형 구조와 선형 구조가 옳게 짝지어진 것은?

1. 스택(Stack)     2. 큐(Queue)

3. 트리(Tree)      4. 연결리스트(Linked List)

5. 그래프(Graph)

가. 비선형 구조: 1, 2, 5     선형구조: 3, 4

나. 비선형 구조: 3, 5         선형구조: 1, 2, 4

다. 비선형 구조: 1, 2, 3     선형구조 4, 5

라. 비선형 구조: 3             선형구조: 1, 2, 4, 5

답) 나

1.       

제2항 기본자료형

(１) 정수형

1) 십진수, 8진수, 16진수로 표현가능

2) 접미사

① l or L : long 상수

② u or U: unsigned 상수

3) 종류

(２) 실수형

1) 123.4, 1.234e2, 1.234E2, 1.234f, 1.234d 의 형태로 표현

2) 접미사

① f or F : float

② d or D : double

3) 종류

(３) 문자형

1) ‘a’, ‘A’, ‘0’ 과 같이 표현

2) Single quote 사용

3) 제어문자(Escape sequence) 표현

`

4) 종류

(４) 문자열형

1) “SEOUL”와 같이 double quote로 둘러싸인 일련의 문자들

2) “”: 빈 문자열

3) 문자상수 ‘a’와 문자열 상수 “a”는 구분되어야 한다.

4) 문자열은 반드시 null(‘\0’) 로 끝난다.

제3항 선형 구조(Linear Structure)

(１) 리스트 (List)

1) 리스트의 종류

① 선형리스트(Linear List)

ü 배열과 같이 연속되는 기억장소에 저장되는 리스트를 말한다.

ü Array(배열)

② 연결 리스트

ü 자료들이 반드시 연속적으로 배열되어 있지 않아도 노드 포인터 부분을 이용하여 서로 연결되어진 구조를 말한다.

ü 포인터

(２) 선형 리스트 (Linear List)

1) 연속적인 기억장소에 저장된 리스트

2) 순차리스트 또는 연접리스트(Dense List) 라고도 함

3) 임의의 노드에 접근을 할 때는 인덱스(Index)를 사용하므로 포인터가 없음

4) 장점

① 간단한 자료구조

② 저장 효율이 뛰어남 (기록밀도: 1)

③ 접근 속도(Access Time)가 빠름

5) 단점

① 삽입과 삭제가 어려움

② 삽입 및 삭제시 삽입하거나 삭제할 위치 이후의 모든 자료의 이동이 필요

(３) 연결 리스트 (Linked List)

1) 자료들을 임의의 기억공간에 기억시키고, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료 구조

2) 장점

① 자료의 삽입 및 삭제가 용이

② 비연속적 (한 리스트를 여러 개의 리스트로 분리하기 쉬움)

③ 희소행렬(행렬의 요소들 중에서 많은 부분이 0으로 되어 있는 행렬)을 연결 리스트로 표현시 기억장소 이용 효율이 좋음

3) 단점

① Access Time이 느림

② 기억장소 이용 효율이 나쁨(저장되지 않은 빈 공간 발생)

③ 포인터를 위한 추가 공간이 필요

④ 중간노드 연결이 끊어지면 그 다음 노드를 찾기 힘듬

4) 종류

① 단순 연결 리스트 (단순 링크드 리스트)

ü 한 방향으로만 가리키고 있다.

그림  SEQ 그림 \* ARABIC 20. single linked list

② 이중 연결 리스트

ü 양 방향으로 가리키고 있다.

그림  SEQ 그림 \* ARABIC 21. double linked list

③ 단순 환형 연결 리스트

(４) 스택 (Stack)

1) 정의

① top이라고 하는 리스트의 한쪽 끝에서만 삽입과 삭제가 일어나는 자료구조

② 자료의 후입선출(last-in-first-out) 방법

ü 자료의 삽입: TOP = TOP + 1

ü 자료의 삭제: TOP = TOP – 1;

ü Overflow 발생: 스택의 크기가 M일 때, TOP > M 이면 Overflow 발생

2) 용도

① 인터럽트의 처리

② 수식의 계산 (산술식 표현)

③ 서브루틴의 복귀번지 저장

④ 부 프로그램(sub program)의 호출 = 함수 호출의 순서 제어

3) 순환적 프로그램을 처리하기 위한 요소

① 스택

② 복귀주소

③ 순환에서 탈출하는 조건

4) 삽입 알고리즘

Top = Top + 1

if Top > M then

           Overflow

else

           X(Top) = item

5) 삭제 알고그림

if Top = 0 then

           Underflow

else

           item = X(Top)

Top = Top - 1

(５) 큐 (Queue)

1) 큐의 정의

① rear라고 하는 리스트의 한쪽 끝에서 삽입이 일어나고 front라 부르는 반대쪽 끝에서 삭제가 일어나는 자료구조

② FIFO(first-in-first-out) 구조

2) 형태

3) 용도

① 운영체제의 작업 스케쥴링 등에 응용되는 것으로 가장 적합한 자료구조

② 키보드 버퍼 이용시

③ 스풀(spool) 운용시

(６) 데크 (Deque, Double Ended Queue)

1) 데크의 정의

① 서로 다른 방향에서 입출력이 가능한 구조 (삽입과 삭제가 양쪽 끝에서 일어남)

② 입력이 한쪽에서만 발생하고, 출력은 양쪽에서 일어날 수 있는 입력제한과 입력은 양쪽에서 일어나고 출력은 한곳에서만 이루어지는 출력제한이 있음.

③ 스택과 큐를 복합한 형태

④ 양 끝에서 삽입과 삭제가 가능하게 하도록 큐를 일반화한 것