Skip to content

Latest commit

 

History

History
287 lines (202 loc) · 8.54 KB

220304.md

File metadata and controls

287 lines (202 loc) · 8.54 KB

THEMA 63 정렬

1. 정렬 알고리즘

정렬 시간복잡도 특징
버블정렬 O(n^2)
선택정렬 O(n^2)
삽입정렬 O(n^2)
퀵정렬 평균: O(nlogn), 최악: O(n^2) 정렬된 입력이 들어오면 최악
2-way merge 정렬 O(nlogn)
힙정렬 O(nlogn) 완전이진트리
기수정렬 O(n) 분배에 의한 정렬, 공간복잡도 크다.

THEMA 64 퀵 정렬

(1) 피봇 지정

(2) L과 H 교환

  • L >= pivot 까지 증가
  • H <= pivot 까지 감소
  • L과 H 교환

(3) 피봇과 H 교환

  • H >= L 까지 (2) 반복
  • H <= L 이면 pivot과 H 교환

THEMA 65 힙정렬 / 2-way 합병 정렬 / 기수 정렬

1. 힙정렬

  • 공백힙에 데이터를 하나씩 삽입하며 최대힙 구성

2. 2-way 합병 정렬

3. 기수 정렬

THEMA 66 탐색

1. 탐색 방식 비교

탐색 시간 복잡도 특징
순차탐색 O(n)
이진탐색 O(logn) 정렬파일만 가능, 고정된 데이터에 적합
이진탐색트리 균형적: O(logn), 불균형적: O(n) 중위 순회 시 오름차순으로 정렬된 결과를 얻음
해싱 완전해싱: O(1), 충돌발생: O(n)

THEMA 67 이진탐색트리 / AVL 트리

THEMA 68 m차 B-트리

THEMA 69 해싱(hashing)

1. 오버플로우 해결

(1) 개방주소법

  • 선형조사법
  • 이차조사법
  • 이중해싱: (해시주소 + 2차해시함수) % n

(2) 폐쇄주소법

  • 체이닝

THEMA 70 데이터베이스 개요

1. 데이터베이스 정의

  • 통합 데이터(Integrated Data): 데이터의 중복을 최소화한 데이터의 집합
  • 저장 데이터(Stored Data): 컴퓨터가 접근할 수 있는 저장매체에 저장된 데이터
  • 운영 데이터(Operational Data): 조직의 존재 목적이나 기능을 수행하는데 없어서는 안 될 데이터의 집합
  • 공용 데이터(Shared Data): 한 조직에 있는 여러 응용 시스템들이 공동으로 소유하고 유지하며 이용하는 공용 데이터

2. 데이터베이스 특성

  • 실시간 접근성 (real-time accessibility)
  • 계속적인 변화 (continuous evolution)
  • 동시 공용 (concurrent sharing)
  • 내용에 의한 참조 (contents reference)

THEMA 71 파일시스템 / DBMS

1. 파일시스템

  • 같은 내용의 데이터가 여러 파일에 중복 저장됨
  • 데이터 파일의 구조가 변경되면 그 데이터 파일에 접근하는 응용 프로그램도 변경해야 함
  • 데이터 관리 기능 포함

2. DBMS

  • 논리적 데이터 독립성
  • 물리적 데이터 독립성

THEMA 72 데이터베이스 시스템

1. 3단계 스키마

(1) 외부스키마 (External Schema)

  • 가장 바깥쪽 스키마
  • 사용자 관점

(2) 개념 스키마 (Conceptual Schema)

  • 범 기관적 관점
  • 1개 존재

(3) 내부 스키마 (Internal Schema)

  • 물리적 저장장치 관점
  • 데이터베이스가 저장되는 방법

(4) 응용 인터페이스

  • 외부스키마 - 개념스키마
  • 논리적 독립성

(5) 저장 인터페이스

  • 개념스키마 - 내부스키마
  • 물리적 독립성

(6) 장치 인터페이스

  • 내부스키마 - 장치

2. 데이터베이스 용어

  • 데이터 사전(Data Dictionary)/시스템 카탈로그: 필요한 스키마 및 여러 개체에 관한 정보를 포함하고 있는 시스템 데이터베이스, 사용자와 시스템 모두 접근 가능
  • 데이터 디렉터리(Data Directory): 데이터 사전에 있는 데이터를 실제로 접근하는데 필요한 정보를 유지하는 시스템, 시스템만 접근 가능

3. DML

절차적 DML 비절차적 DML
무슨(what)데이터, 어떻게(how)접근하는지 무슨(what)데이터를 원하는지

THEMA 73 데이터 모델링

1. 데이터 모델

(1) 개념적 데이터 모델

  • 개체-관계 모델
  • 개체-관계 다이어그램

(2) 논리적 데이터 모델

  • 계층 데이터 모델
  • 네트워크 데이터 모델
  • 관계 데이터 모델
  • 객체지향 데이터 모델
  • 객체-관계 데이터 모델

THEMA 74 관계 데이터 모델

1. 관계 데이터 모델 기본 용어

  • relation(릴레이션)
  • attribute(애트리뷰트, 속성): 열
  • domain(도메인)
  • tuple(투플): 행
  • Degree(차수): 속성의 개수
  • Cardinaliry(기수): 투플의 개수

2. 데이터 무결성 제약조건

  • 개체 무결성(entity integrity): 릴레이션의 기본키를 구성하는 어떤 속성도 null일 수 없고, 중복 입력되지 않는다.
  • 참조 무결성(referential integrity): 외래키 값은 널이거나 참조 릴레이션에 있는 기본키와 같아야 한다.
  • 도메인 무결성(domain integrity): 특정 속성의 값이 그 속성이 정의된 도메인에 속한 값이어야 한다.

THEMA 75 관계 데이터 연산

1. 관계대수/관계해석

  • 관계대수: 원하는 결과를 얻기 위해 데이터의 처리 과정을 순서대로 기술
  • 관계해석: 원하는 결과를 얻기 위해 처리를 원하는 데이터가 무엇인지만 기술, 비절차적 언어

2. 관계대수

  • 일반 집합 연산자: 합집합(∪), 교집합(∩), 차집합(-), 카티션 프로덕트(X)
  • 순수 관계 연산자: 셀렉트(σ), 프로젝트(π), 조인(⋈), 디비전(÷)

THEMA 76 구조적 질의어(SQL)

1. DDL (SQL 정의어)

(1) CREATE 문

  • Cascade, No Action, Set Null, Set Default

(2) ALTER 문

(3) DROP 문

2. DML (SQL 조작어)

(1) SELECT 문

  • <>(!=): 같지 않음
  • in ( , ): 조건의 범위 지정
  • like '%': 와일드카드 사용

(2) INSERT 문

(3) UPDATE 문

(4) DELETE 문

3. DCL (SQL 제어어)

  • DCL: Grant, Revoke, Deny
  • TCL: Commit, Rollback

THEMA 77 View(뷰)

  • ALTER문 사용 불가
  • 독자적 인덱스 가질 수 없음

THEMA 78 데이터베이스 설계

1. 분석

2. 개념적 설계

  • 개념스키마 모델링 → 개체관계모델(ERD)

3. 논리적 설계

  • 스키마 변환
  • 논리적 데이터 모델
계층형 트리
망형 그래프
관계형 2차원테이블
객체지향형 객체(속성+메소드)
객체관계형 객체+테이블

4. 물리적 설계

THEMA 79 정규화 체계

1. 정규화 체계

구분 내용 이상 현상 원인
비정규형 원자값이 아닌 도메인
제1정규형 릴레이션의 모든 도메인이 원자값 부분 함수종속
제2정규형 부분 함수종속 제거, 기본키에 속하지 않은 애트리뷰트는 모두 기본키에 완전 함수종속 이행적 함수종속
제3정규형 이행적 함수종속 제거, 기본키에 속하지 않은 애트리뷰트는 모두 기본키에 이행적으로 함수종속되지 않는다. 결정자가 후보키가 아닌 함수 종속
BCNF 모든 결정자가 후보키
제4정규형 다치종속 제거
제5정규형 후보키를 통하지 않은 조인 종속 제거

THEMA 80 질의어 최적화

1. 질의트리 구성

  • 단말노드: 릴레이션
  • 루트 노드: 검색 결과값
  • 부노드: 조인(가능한 나중에)
  • 부노드가 아닌 비단말 노드: 셀렉트(가능한 먼저), 프로젝트(가능한 먼저)

2. 경험적 기법에 따른 질의 최적화

  • 논리곱 조건을 가진 셀렉트 연산은 분해
  • 셀렉트 연산은 가능한 한 아래로 내림
  • 가장 제한적인 셀렉트 연산을 가장 먼저 수행
  • 카티션 프로덕트와 해당 셀렉트 연산은 조인 연산으로 통합

THEMA 81 트랜잭션

THEMA 82 회복 / 동시성 제어

1. 회복 종류

즉시 갱신 지연 갱신
체크포인트 이전 commit No-Operation No-Operation
체크포인트 이후 commit REDO REDO
체크포인트 이후 commit X UNDO No-Operation

2. Locking(로킹)

(1) 로킹 단위

로킹 단위 로크의 수 병행 제어 기법 로킹 오버헤드 병행성 수준
커짐 적어짐 단순 감소 낮아짐
작아짐 많아짐 복잡 증가 높아짐

3. 2단계 로킹 규약(2PLP)

  • 확장 단계: lock 연산만 수행
  • 축소 단계, unlock 연산만 수행
  • 직렬 가능성 제공
  • 교착상태 발생 가능

THEMA 83 분산 데이터베이스

THEMA 84 데이터 웨어하우스

1. 데이터 마이닝(Data Mining)

  • 연관 규칙
지지도 A, B를 동시에 포함하는 거래의 비율 {A, B} 거래 / 전체 거래 * 100(%)
신뢰도 A를 포함하는 거래 중 B가 포함된 거래의 비율 {A, B} 거래 / A 거래 * 100(%)