정규화정규화란 이상 현상이 발생하지 않도록, 릴레이션을 분해하는 과정을 말한다. 데이터베이스 설계 또는 설계 결과를 검증하는 용도로 사용된다. 두 설계 방법 중 적절한 방법을 선택하자.E-R 모델과 릴레이션 변환 규칙정규화이상 (Anomaly)데이터 중복이 발생하여 릴레이션에 대한 데이터 삽입, 수정, 삭제 연산 시의 부작용을 말한다. 정규화 과정을 진행하면 이상 현상이 제거된다. 이상 현상의 종류삽입 이상 : 새 데이터를 삽입하기 위해 불필요한 데이터도 함께 삽입해야 하는 문제갱신 이상 : 중복 튜플 중 일부만 변경하여 데이터가 불일치되는 문제삭제 이상 : 튜플을 삭제하면 꼭 필요한 데이터까지 함께 삭제되는 문제결정자하나의 릴레이션을 구성하는 속성들의 부분 집합을 X와 Y라고 하자. 어느 시점에서든 X..
서론B Tree와 B+ Tree는 이진 탐색 트리를 확장해 하나의 노드가 2개 이상의 자식을 가질 수 있게 만든 트리이며 주로 데이터베이스, 파일 시스템에서 사용된다. 하드 디스크는 블록 단위로 읽기/쓰기 작업을 수행한다. DB의 모든 행은 블록에 저장된다. 만약 특정 행을 조회하는 쿼리를 수행하려면 행이 저장된 모든 블록을 모두 탐색해야하는데 이는 비효율적이다. 그래서 인덱스를 사용한다. 행의 키를 키로, 블록 주소를 값으로 갖는 인덱스를 사용한다. 인덱스가 저장된 블록 + 1개의 행이 저장된 블록만 탐색하면 되므로 탐색할 블록 개수가 줄어든다. 인덱스를 위한 인덱스행이 많아지면 인덱스 블록 개수도 증가한다. 때문에 인덱스를 위한 인덱스(high level index)를 둔다. DB 행이 증가할수록 ..
해시인덱스의 범위가 상당히 큰데에 비해 사용되는 공간이 적은 경우를 생각해보자. 예를 들어 인덱스 범위가 1 ~ 1억인 경우 1억 크기 배열을 사용해야하는데 이는 공간 낭비이다.또한 인덱스가 정수가 아닌 문자열이나 객체인 경우 어떻게 해야할까? 이 경우 해시 함수와 해시 테이블을 사용할만 하다. 키로 원소를 O(1)에 찾는 검색 알고리즘해시 테이블 - 원소를 저장하고 있는 공간(배열)해시 함수 - 키를 해시 테이블의 인덱스로 바꾸는 함수. 키를 해시 테이블 인덱스로 쓸 수 있다면 해시 함수가 필요 없겠지만 보통 키의 범위가 너무 크고, 정수형이 아닐기 있기에 변환 함수인 해시 함수가 필요하다. 해시 함수의 결과값을 해시 값이라 한다.충돌서로 다른 키의 해시 값이 동일 할 때 충돌이 발생했다고 한다. 키의..
Heap힙은 힙 속성을 만족하는 완전 이진 트리(이진 힙의 경우)이다. 우선 순위가 가장 높은 원소를 빠르게 찾는 용도로 사용된다. 힙을 사용하면, 원소를 추가하는 연산, 가장 우선순위가 높은 연산을 O(logN)으로 수행할 수 있다. 우선순위가 가장 높은 수가 가장 큰수라면 최대힙, 가장 작은 수라면 최소힙이라 부른다. 힙 속성 : 부모 노드는, 항상 자식 노드보다 우선순위가 높다.따라서 힙은 힙 속성, 완전 이진 트리를 만족해야한다.BBST를 쓰면 안되나?BBST보다 힙이 훨씬 빠르다. BBST도 같은 시간 복잡도를 가지며, 심지어 우선 순위가 가장 낮은 원소도 가져올 수 있지만, 같은 시간 복잡도라도 힙은 간단한 작업을 수행하기에 더 빠르다. BBST는 트리의 균형을 맞추기 위해 복잡한 작업을 수행..
서브 쿼리 쿼리 내부에 포함된 select 쿼리를 서브 쿼리(Sub Query)라 부른다. select 쿼리에 들어가는 서브 쿼리 종류에는 인라인 뷰, 스칼라 서브쿼리, 중첩 서브쿼리가 있다. 이때 서브 쿼리를 포함한 select 쿼리를 메인 쿼리라 하며 서브 쿼리가 실행 된 후 메인 쿼리가 실행된다. 1. 인라인 뷰 from 절에 들어가는 서브 쿼리 서브 쿼리의 조회 결과를 테이블 처럼 사용할 때 씀 alias 지정 필수 select * from ( select l.common, l.col_l, r.col_r from table_l l left join table_r r #on table_l.common = table_r.common; using(common) union select r.common, ..
Join MySQL의 sql로 관계 대수의 자연 조인, 세타 조인, 외부 조인, 세미 조인, 카티션 곱 등이 가능하다. inner join 두 릴레이션에 있는 모든 튜플을 조회 한다. 조인을 할 때 주로 ANSI 조인 형태를 사용한다. ANSI 조인은 JOIN 키워드와 ON이 있기 때문에 쉽게 조인 조건을 알 수 있다. # ANSI 조인 형태 # 다른 sql에서도 범용적으로 사용 가능 # where 조건절과 join 조건이 분리되므로 가독성이 높음 select * from table_l [inner] join table_r on table_l.common = table_r.common; # 조인 속성이 동일 하다면 아래와 같이 쓸 수 있음 select * from table_l [inner] join t..
Segment Tree구간 트리(Segment Tree)는 저장된 자료의 특정 구간 질의를 빠르게 대답하기 위해 저장된 자료를 전처리한 트리를 말한다. 흔히 구간 트리는 일차원 배열의 특정 구간 질의를 빠르게 대답하는데 사용된다. 예를 들어 [1, 7, 5, 3, 2] 라는 일차원 배열이 있을 때 [1, 2] 구간의 최소치를 찾는 연산을 해야 한다. 이를 연산하는 간단한 방법은 구간의 시작부터 끝까지 순회하면서 최소치를 찾으면 되며 시간 복잡도는 O(N)이 된다. 반면 구간 트리를 한 번 만들어두면 위 연산을 O(log N)으로 할 수 있다. 구간 트리의 핵심 아이디어는 배열 구간에 대한 이진 트리를 만드는 것이다. 구간 트리의 노드는 구간을 표현한다. 루트 노드는 항상 배열의 전체 구간 [0, n-1]..
최단 경로최단 경로 문제(shortest path problem)는 그래프에서 주어진 두 정점을 연결하는 가장 짧은 경로를 찾는 문제로, 그래프 관련 문제 중에서 최단 경로 문제가 많다. 최단 경로 문제를 해결하기 위해서는 그래프가 어떤 그래프인지 파악하고, 그에 맞는 최단 경로 알고리즘을 적용해야한다. 최단 경로 알고리즘은 최단 경로를 구성하는 정점들의 목록을 구해 주는 것이 아닌 최단 경로의 길이를 찾아줄 뿐이라는 점에 유의해야한다. 실제 경로를 계산하기 위해서는 BFS에서 그랬듯이 탐색 과정에서 별도의 정보를 저장하고, 이것으로부터 실제 경로를 찾아내야한다. 가중치가 없는 그래프에서는 BFS로 최단 경로를 구할 수 있다. 여기서의 최단 경로는 경로의 길이가 가장 짧은 경로를 말한다. 가중치가 있는 ..
