정보처리 요약정리 3-1장 ✔

서린·2024년 4월 10일
정보처리
0

정보처리산업기사

목록 보기
7/8
post-thumbnail

3과목 - 데이터베이스 활용

자료 구조의 분류

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

스택(Stack)

  • 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료구조이다.
  • 가장 나중에 삽입된 자료가 가장 먼저 삭제되는 후입선출(LIFO)방식으로 자료를 처리한다.

스택의 응용 분야

  • 함수 호출의 순서 제어
  • 인터럽트의 처리
  • 수식 계산 및 수식 표기법
  • 컴파일러를 이용한 언어 번역
  • 부 프로그램 호출 시 복귀주소 저장
  • 서브루틴 호출 및 복귀 주소 저장

스택의 삽입(Push)과 삭제(Pop)

  • PUSH : 스택에 자료를 입력하는 명령
  • POP : 스택에서 자료를 출력하는 명령

큐(Queue)

  • 리스트의 한쪽에서는 삽입작업이 이루어지고 다른 한쪽에서는 삭제 작업이 이루어지는 자료구조이다.
  • 가장 먼저 삽입된 자료가 가장 먼저 삭제되는 선입선출(FIFO)방식으로 처리한다.

데크(Deque)

  • 삽입과 삭제가 리스트의 양쪽 끝에서 모두 발생할 수 있는 자료구조이다.
  • 입력 제한 : 입력은 한쪽에서만 일어나고 출력은 양쪽에서 일어남
  • 출력 제한 : 입력은 양쪽에서 일어나고 출력은 한쪽에서만 일어남

방향/무방향 그래프의 최대 간선수

  • 무방향 그래프의 최대 간선 수 : n(n-1)/2
  • 방향 그래프의 최대 간선 수 : n(n-1)

트리(Tree)

  • 정점(Node, 노드)과 선분(Branch, 가지)을 이용하여 사이클을 이루지 않도록 구성한 그래프(Graph)의 특수한 형태이다.
  • 노드(Node) : 트리의 기본 요소로서 자료 항목과 다른 항목에 대한 가지(Branch)를 합친 것
    • A,B,C,D,E,F,G,H,I,J,K,L,M
  • 디그리(Degree, 차수) : 각 노드에서 뻗어 나온 가지의 수
    • A = 3, B = 2, C = 1, D=3
  • 단말 노드(Terminal Node) = 잎 노드(Leaf Node) : 자식이 하나도 없는 노드, 즉 디그리가 0인 노드
    • K, L, F, G, M, I, J

이진 트리의 운행법


수식의 표기법(Infix -> Postfix)

  • Infix로 표기된 수식에서 연산자를 해당 피연산자 두개의 뒤(오른쪽)에 오도록 이동하면 Postfix가 된다.

수식의 표기법(Infix -> Prefix)

  • Infix로 표기된 수식에서 연산자를 해당 피연산자 두 개의 앞(왼쪽)에 오도록 이동하면 Prefix가 된다.

수식의 표기법(Postfix -> Infix)

  • Postfix는 Infix 표기법에서 연산자를 해당 피연산자 2개의 뒤(오른쪽)로 이동한 것이므로 연산자를 다시 해당 피연산자 2개의 가운데로 옮기면 된다.

삽입 정렬(Insertion Sort)

선택 정렬(Selection Sort)

버블 정렬(Bubble Sort)

해시 테이블 관련 용어

  • Collistion(충돌 현상) : 서로 다른 두 개 이상의 레코드가 같은 주소를 갖는 현상
  • Synonym : 충돌로 인해 같은 Home Address를 갖는 레코드들의 집합

해싱 함수(Hashing Function)

  • 제산법(Division)
  • 제곱법(Mid-Square)
  • 폴딩법(Folding)
  • 기수 변환법(Radix)
  • 대수적 코딩법(Algebraic Coding)
  • 숫자 분석법(Digit Analysis, 계수 분석법)
  • 무작위법(Random)

DBMS의 필수 기능

  • 정의 기능 : 모든 응용 프로그램들이 요구하는 데이터 구조를 지원하기위해 데이터베이스에 저장될 데이터의 형(Type)과 구조에 대한 정의, 이용 방식, 제약 조건 등을 명시하는 기능
  • 조작 기능 : 데이터 검색, 갱신, 삽입, 삭제 등을 체계적으로 처리하기 위해 사용자와 데이터베이스 사이의 인터페이스 수단을 제공하는 기능
  • 제어 기능 : 데이터베이스를 접근하는 갱신, 삽입, 삭제작업이 정확하게 수행되어 데이터의 무결성이 유지되도록 제어해야함

데이터베이스 설계순서

물리적 설계 옵션 선택 시 고려 사항

  • 반응 시간(Response Time)
  • 공간 활용도(Space Utilization)
  • 트랜잭션 처리량(Transaction Throughput)

데이터 모델에 표시할 요소

  • 구조(Structure) : 논리적으로 표현된 개체 타입들 간의 관계로서 데이터 구조 및 정적 성질을 표현함
  • 연산(Operation) : 데이터베이스에 저장된 실제 데이터를 처리하는 작업에 대한 명세로서 데이터베이스를 조작하는 기본 도구
  • 제약 조건(Constraint) : 데이터베이스에 저장될 수 있는 실제 데이터의 논리적인 제약 조건

E-R 다이어그램

튜플(Tuple)

  • 릴레이션을 구성하는 각각의 행을 말한다.
  • 튜플의 수 = 카디널리티(Cardinality)

속성(Attribute)

  • 데이터베이스를 구성하는 가장 작은 논리적 단위이다.
  • 속성의 수 = 디그리(Degree) = 차수

도메인(Domain)

  • 하나의 애트리뷰트가 취할 수 있는 같은 타입의 원자(Atomic)값들의 집합이다.

릴레이션의 특징

  • 한 릴레이션에는 똑같은 튜플이 포함될 수 없으므로 릴레이션에 포함된 튜플들은 모두 상이하다.
  • 한 릴레이션에 포함된 튜플 사이에는 순서가 없다.
  • 속성의 유일한 식별을 위해 속성의 명칭은 유일해야 한다.
  • 속성의 값은 논리적으로 더 이상 쪼갤 수 없는 원자값만을 저장한다.

후보키(Candidate Key)

  • 릴레이션을 구성하는 속성들 중에서 튜플을 유일하게 식별하기 위해 사용하는 속성들의 부분집합, 즉 기본키로 사용할 수 있는 속성들을 말한다.
  • 릴레이션에 있는 모든 튜플에 대해서 유일성과 최소성을 만족시켜야 한다.

널 값(NULL Value)

  • 데이터베이스에서 아직 알려지지 않거나 모르는 값으로서 '해당없음'등의 이유로 정보 부재를 나타내기 위해 사용하는, 이론적으로 아무것도 없는 특수한 데이터를 말한다.

기본키(Primary Key)

  • 후보키 중에서 특별히 선정된 주키(Main Key)로 중복된 값을 가질 수 없다.
  • NULL 값을 가질 수 없다.

대체키(Altermate Key)

  • 후보키가 둘 이상일 때 기본키를 제외한 나머지 후보키를 의미한다.
  • 보조키라고도 한다.

슈퍼키(Super Key)

  • 한 릴레이션 내에 있는 속성들의 집합으로 구성된 키이다.
  • 릴레이션을 구성하는 모든 튜플에 대해 유일성은 만족시키지만, 최소성은 만족시키지 못한다.

외래키(Foreign Key)

  • 다른 릴레이션의 기본키를 참조하는 속성 또는 속성들의 집합을 의미한다.
  • 한 릴레이션에 속한 속성 A와 참조 릴레이션의 기본키인 B가 동일한 도메인 상에서 정의되었을 때의 속성 A를 외래키라고 한다.

무결성

  • 개체 무결성 : 기본 테이블의 기본키를 구성하는 어떤 속성도 NULL 값이나 중복값을 가질 수 없다는 규정
  • 참조 무결성 : 외래키 값은 NULL이거나 참조 릴레이션의 기본키 값과 동일 해야함. 즉 릴레이션은 참조할 수 없는 외래키 값을 가질 수 없다는 규정

관계대수

  • 관계형 데이터베이스에서 원하는 정보와 그 정보를 검색하기 위해서 어떻게 유도하는가를 기술하는 절차적인 언어이다.
  • 질의에 대한 해를 구하기 위해 수행해야 할 연산의 순서를 명시한다.

순수 관계 연산자 - Select

  • 릴레이션에 존재하는 튜플 중에서 선택 조건을 만족하는 튜플의 부분집합을 구하여 새로운 릴레이션을 만드는 연산이다.
  • 기호 : 시그마(σ)

순수 관계 연산자 - Project

  • 주어진 릴레이션에서 속성 리스트에 제시된 속성 값만을 추출하여 새로운 릴레이션을 만드는 연산이다.
  • 기호 : 파이(π)

순수 관계 연산자 - Join

  • 공통 속성을 중심으로 두 개의 릴레이션을 하나로 합쳐서 새로운 릴레이션을 만드는 연산이다.
  • 기호 : ▷◁

순수 관계 연산자 - Division

  • X)Y인 두 개의 릴레이션 R(X)와 S(Y)가 있을 때, R의 속성이 S의 속성값을 모두 가진 튜플에서 S가 가진 속성을 제외한 속성만을 구하는 연산이다.
  • 기호 : ÷

일반 집합 연산자 - 기호

일반 집합 연산자 - 교차곱(CARTESIAN PRODUCT)

  • 두 릴레이션에 있는 튜플들의 순서쌍을 구하는 연산이다.
  • 디그리는 두릴레이션의 디그리를 더한 것과 같고, 카디널리티는 두 릴레이션의 카디널리티를 곱한 것과 같다.

관계해석

  • 관계 데이터 모델의 제안자인 코드(Codd)가 수학의 Predicate Calculus(술어 해석)에 기반을 두고 관계 데이터베이스를 위해 제안했다.
  • 원하는 정보가 무엇이라는 것만 정의하는 비절차적 특성을 지닌다.

정규화(Normalization)

  • 함수적 종속성 등의 종속성 이론을 이용하여 잘못 설계된 관계형 스키마를 더 작은 속성의 세트로 쪼개어 바람직한 스키마로 만들어 가는 과정이다.
  • 데이터 삽입 시 릴레이션을 재구성할 필요성을 줄인다.

이상(Anomaly)

  • 정구화를 거치지 않으면 데이터베이스 내에 데이터들이 불필요하게 중복되어 릴레이션 조작 시 예기치 못한 곤란한 현상이 발생하는 것을 의미한다.
  • 종류 : 삽입 이상, 삭제 이상, 갱신 이상

정규화 과정

이행적 종속 관계

  • A -> B이고 B -> C일 때 A -> C를 만족하는 관계를 의미한다.

함수적 종속

  • 데이터들이 어떤 기준값에 의해 종속되는 것을 의미한다

뷰(View)

  • 사용자에게 접근이 허용된 자료만을 제한적으로 보여주기 위해 하나 이상의 기본 테이블로부터 유도된, 이름을 가지는 가상 테이블이다.
  • 기본 테이블의 기본키를 포함한 속성(열) 집합으로 뷰를 구성해야만 삽입, 삭제, 갱신 연산이 가능하다.
  • 뷰를 정의할 때는 CREATE문, 제거할 때는 DROP문을 사용한다.

뷰의 장단점

  • 장점
    • 논리적 데이터 독립성이 제공된다.
    • 접근 제어를 통한 자동 보안이 제공된다.
  • 단점
    • 독립적인 인덱스를 가질 수 없다.
    • 뷰의 정의를 변경할 수 없다.
    • 삽입, 삭제, 갱신 연산에 제약이 따른다.

시스템 카탈로그(System Catalog)

  • 시스템 그 자체에 관련이 있는 다양한 객체에 관한 정보를 포함하는 시스템 데이터베이스 이다.
  • 사용자가 시스템 카탈로그 내용을 검색할 수는 있지만 갱신할 수는 없다.

트랜잭션의 특성

  • Atomicity(원자성) : 트랜잭션의 연산은 데이터베이스에 모두 반영되도록 완료(Commit)되든지 아니면 전혀 반영되지 않도록 복구(Rollback)되어야 함
  • Consistency(일관성) : 트랜잭션이 그 실행을 성공적으로 완료하면 언제나 일관성 있는 데이터베이스 상태로 변환함
  • Isolation(독립성) : 둘 이상의 트랜잭션이 동시에 병행 실행되는 경우 어느 하나의 트랜잭션 실행 중에 다른 트랜잭션의 연산이 끼어들 수 없음
  • Durability(영속성) : 성공적으로 완료된 트랜잭션의 결과는 시스템이 고장나더라도 영구적으로 반영되어야함
profile
서린
개발 일기 ( •̀ ω •́ )✧
이전 포스트

정보처리 요약정리 2-2장 ✔

다음 포스트

JWT

0개의 댓글

관련 채용 정보