질의(Query) 처리의 개요

질의 처리 정의 데이터베이스에 저장된 데이터에 접근하는 것과 관련된 일련의 작업 질의 처리는 파싱 및 변환, 최적화, 평가의 단계로 수행 질의 처리를 시작하기 전에 시스템은 질의를 사용 가능한 내부 형식으로 변환해야 함 SQL과 같은 질의어는 사람이 사용하기는 편리하지만, 시스템을 위한 표현 형식이 아님 시스템을 위한 표현 방법이 확장 관계 대수에 기반을 둔 표현 형식으로 변환하는 것이 필요 질의 처리 절차 파싱 및 변환 입력된 질의어의 구문을 검사하고, 내부 표현 형식(즉, 관계 대수식)으로 변환 최적화 하나의 관계 대수식은 많은 동등한 관계 대수식을 가질 수 있고, 각각의 관계 대수 연산은 서너 개의 다른 알고리즘들 중의 하나를 사용하여 평가될 수 있으므로, 하나의 관계 대수식은 다양한 방법으로 평가..

• format_list_bulleted 밥벌이/데이터베이스
• · 2011. 1. 31.
• textsms

셀렉션(Selection) 연산

파일 스캔 셀렉션 조건을 만족하는 레코드들을 찾아서 검색하는 탐색 알고리즘 선형 탐색(Linear Search) 각각의 파일 블록을 스캔하고 모든 레코드들에 대해 셀렉션 조건을 만족하는지를 검사 속도가 가장 느림 이진 탐색(Binary Search) 파일이 순서화되어 있는 속성에 대해 셀렉션이 동등(Equality) 비교일 경우 적용 가능 순서적으로 정렬된 파일에서, 파일의 중간 레코드의 키와 조건 키와의 비교를 반복하면서 탐색하는 방법 인덱스 스캔 인덱스를 사용하는 탐색 알고리즘 후보키에 대한 기본 인덱스, 동등 대응하는 동등 조건을 만족하는 단일 레코드 검색 비(非) 키(Non-key)에 대한 기본 인덱스, 동등 다중 레코드 검색 탐색키에 대한 보조 인덱스, 동등 탐색키가 후보키인 경우는 단일 레코드..

• format_list_bulleted 밥벌이/데이터베이스
• · 2011. 1. 31.
• textsms

정렬(Sorting)

정렬의 정의 정렬은 주어진 레코드들을 특정한 순서대로 나열하는 것 레코드의 정렬 순서에 따라 오름차순 또는 내림차순으로 구분 정렬하려는 속성에 대해 인덱스가 구축된 경우, 해당 인덱스를 통해 정렬된 순서에 따라 접근 가능 내부 정렬(Internal sort) 데이터 양이 적어서 주기억 장치 내에서만 수행되는 정렬 정렬하기 전에 모든 데이터가 주기억 장치에 올라와 있어야 함 내부 정렬의 종류 종류 설명 힙 정렬 (Heap Sort) 힙이란, 모든 단말 노드가 루트에서부터 거리가 h 또는 h-1 인 완정 이진 트리를 말함 정렬되지 않은 레코드로 구성된 파일을 트리 구조인 힙 형태로 변환하고, 가장 큰 레코드 키값을 가지는 루트 노드를 출력하고, 나머지 트리를 다시 힙으로 구성하는 과정을 반복 수행 하는 방법..

• format_list_bulleted 밥벌이/데이터베이스
• · 2011. 1. 31.
• textsms

조인(Join) 연산

정의 조인은 하나의 처리 문장을 이용해 데이터베이스의 테이블 2개를 연결하여 새로운 테이블을 생성하는 기능 데이터베이스의 성능에 영향을 미치게 되어 추후 반정규화 또는 튜닝의 대상이 되기도 함 분류 동등 조인(Equi-Join) 조인 조건에 동등 연산자만을 사용한 조인 비동등 조인(Nonequi-Join) 조인 조건에 비동등 연산자만을 사용한 조인 카테시안 프로덕트(Cartesian Product) 조인 조건이 없는 조인 각 테이블의 튜플 건수의 곱만큼 결과가 생성됨 상호 조인(Cross Join)이라고도 하며, 실제로는 거의 사용하지 않음 내부 조인(Inner Join) 조인 조건을 만족하는 튜플들만 결과 테이블에 포함하는 조인 대부분의 조인이 이에 해당하며, 어떤 조인인지 지정하지 않으면 내부 조인으..

• format_list_bulleted 밥벌이/데이터베이스
• · 2011. 1. 31.
• textsms

기타 연산

중복 제거 해싱을 수행하면 중복이 같은 버킷 내로 들어오게 되므로 제거 정렬을 수행하면 중복이 서로 인접하게 나타나므로 제거 프로젝션 각각의 튜플에 대해서 프로젝션을 수행 위 결과에 대해서 중복을 제거 집단(Aggregation) 연산 중복 제거와 유사한 방법으로 구현 가능 정렬이나 해싱을 수행하여 튜플들을 같은 그룹들로 구분한 후 , 각 그룹에 대해서 Aggregate함수를 적용함 집합 연산( U, ∩, -) 정렬한 후에 정렬-병합 조인의 변형을 사용 해시 조인의 변형을 사용

• format_list_bulleted 밥벌이/데이터베이스
• · 2011. 1. 31.
• textsms

관계 대수식 평가(Evaluation)

Materialization 최하위 단계에서 시작하여 한번에 한 연산을 계산하여 임시 렐레이션에 저장하고, 임시 릴레이션에 저장된 중간 결과를 다음 단계 연산을 계산하기 위해 사용 Materialization 평가는 항상 적용 가능 Pipelining 몇 개의 연산들을 동시에 계산하며, 한 연산의 결과가 다음 연산에 직접 전달됨 임시 릴레이션을 디스크에 저장할 필요가 없기 때문에 Materialization보다 비용이 적게 소모됨 Pipelining은 항상 적용이 불가함(예, 정렬, 해시 조인 등)

• format_list_bulleted 밥벌이/데이터베이스
• · 2011. 1. 31.
• textsms

질의 최적화

비용 기반 질의 최적화 비용 기반 질의 최적화 단계 동등 규칙(Equivalence Rules)을 이용하여 논리적으로 동등한 관계 대수식들을 생성 이러한 관계 대수식들을 질의-평가 계획들로 변형 가장 비용이 적게 드는 질의-평가 계획을 선택 동적 프로그래밍을 사용하더라도 비용이 많이 듬 Heuristic 최적화 실행 성능을 향상시키기 위해 규칙들을 이용하여 질의-트리를 변형함 규칙 셀렉션을 먼저 수행(튜플 수를 줄임) 프로젝션을 먼저 수행(속성 수를 줄임) 다른 비슷한 연산들보다는 가장 엄격한(즉, 결과 양을 많이 줄일 수 있는) 셀렉션과 조인연산을 먼저 수행(가장 적은 결과 크기를 갖게 됨) 어떤 시스템들은 오직 Heuristic만 사용하고, 다른 시스템들은 Heuristic과 부분 비용 기반 최적화를..

• format_list_bulleted 밥벌이/데이터베이스
• · 2011. 1. 31.
• textsms

물리적 저장 매체의 종류

저장 매체 계층 : 속도와 용량에 따라 구분 1차 저장 장치(Primary Storage) : 캐시, 메인 메모리 2차 저장 장치(Secondary Storage) 또는 온라인 저장 장치 : 자기 디스크 3차 저장 장치 또는 오프라인 저장 장치 : 자기 테이프,광 디스크 캐시(Cache) 캐시는 저장 장치 중에서 가장 빠르고 비싸며 휘발성임 SRAM(Static Random Access Memory)으로 사용됨 하드웨어가 캐시 메모리의 사용을 관리 메인 메모리(Main Memory) 정전이나 시스템의 충돌이 발생하면 메모리의 내용을 잃게 됨(휘발성) DRAM(Dynamic Random Access Memory)으로 사용됨 프로그램과 데이터를 처리하기 위한 작업 공간 내용 접근 시간이 일정하고 빠름 플래시..

• format_list_bulleted 밥벌이/데이터베이스
• · 2011. 1. 28.
• textsms

데이터 구조 및 파일 구조

데이터 구조 데이터 구조는 데이터를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법 효과적으로 설계된 데이터 구조는 실행시간 또는 메모리 용량과 같은 자원을 최소한으로 사용하면서 연산을 수행하도록 보장 데이터 구조는 각자의 연산 및 목적에 적합하도록 설계됨 B-트리는 데이터베이스에 효율적이며, 라우팅 테이블은 네트워크에 일반적으로 사용 다양한 프로그램을 설계함에 있어 어떠한 데이터 구조를 선택할지 우선적으로 고려해야 함 일단 데이터 구조가 선택되면 적용할 알고리즘은 상대적으로 명확해짐 데이터 구조에 있어 가장 기초적인 단위로는 행령, 레코드, 트리, 그래프 등이 있음 파일 구조 파일 구조는 데이터를 효율적으로 이용할 수 있도록 파일에 저장하는 방법 릴레이션을 구성하는 레코드는 일반적으로 하나의 파일로..

• format_list_bulleted 밥벌이/데이터베이스
• · 2011. 1. 28.
• textsms

인덱스(Index)와 해싱(Hashing)

인덱스(Index)의 개요 인덱스의 정의 인덱스는 데이터 레코드(튜플)들을 빠르게 접근하기 위해 쌍으로 구성되는 데이터 구조인데, 포인터는 해당 키를 가지는 1개 이상의 레코드를 가리킴 기본키를 위한 인덱스를 기본 인덱스라 하고, 기본 인덱스가 아닌 인덱스를 보조 인덱스라고 함 대부분의 관계형 DBMS에서는 모든 기본키에 대해서 자동적으로 기본 인덱스를 생성함 밀집 인덱스(Dense Index)와 희소 인덱스(Sparse Index) 밀집 인덱스 인덱스 레코드는 모든 키 값에 대해 나타남 (즉, 데이터 파일의 각 레코드의 키 값이 인덱스 엔트리에 포함) 인덱스 레코드는 키 값과 해당 키를 가지는 첫 번째 레코드에 대한 포인터를 포함 희소 인덱스 인덱스 레코드는 키 값에 대해 단지 몇 개만 나타남 (즉, ..

• format_list_bulleted 밥벌이/데이터베이스
• · 2011. 1. 28.
• textsms