with with

Overview parser and translator에서 문법 검사과 유효한 테이블에 접근하는지 검사한다. evaluation engine에서 최적화된 실행 계획에 맞게 쿼리문을 실행한다. optimizer는 같은 결과를 내는 여러 관계 대수식(실행문) 중 Cost가 가장 낮은 실행문을 고른다. Cost Disk access, CPU, network communication 등의 시간 비용을 의미한다. 여기서는 CPU비용은 너무 작으니 무시하도록 하고, 분산 시스템에서는 network communication이 중요하지만, 여기선 단일 시스템으로 가정하기에 역시 무시한다. Disk access는 실제 시간이 아닌, 몇 블럭을 읽어오는지, 공간 단위로 측정하도록 한다. Disk cost는 아래와 같은 비..

Index 인덱스는 table의 attribute의 부분집합을 복제하여 구조화, 정렬한 것으로 빠른 접근을 가능케 한다. 따라서 attribute로 만들 수 있는 모든 조합의 집합으로 인덱싱 해놓으면 어떻게 검색을 하든 매우 빠르게 데이터를 찾을 수 있을 것이다. 하지만, 이런 경우에는 저장공간이나, 업데이트시에 오버헤드가 매우 커지기 때문에 현실적으론 불가능하다. 따라서 공간 효율적으로 인덱싱 하기 위해 자료구조를 잘 사용해야 하는데, 이번 포스팅의 주제인 B+Tree는 DBMS에서 사용하기에 매우 적합한 자료구조이다. B+Tree B-Tree는 BST의 밸런싱 문제를 해결하고자 나온 자료구조인데, B+Tree는 이런 B-Tree의 특성을 살리면서 데이터베이스 시스템에서 사용하기 좋게 기능이 추가된 버..

hash table은 해시 함수를 이용해서 어떠한 입력이라도 특정 정수로 치환된 주소에 데이터를 저장할 수 있는 자료구조로 일반적으로 O(1)의 시간복잡도를 갖는다. 사실 해시함수를 구현하기에 따라 해시 테이블의 탐색 시간 복잡도가 크게 차이날 수 있는데, 이 포스트는 자료구조의 해시 테이블를 다루는 것 보다, 데이터베이스에서 데이터를 다룰 때 해시 테이블을 사용하는 방식을 다루기 때문에 깊은 내용은 생략합니다. 해시 테이블을 설계함에 있어 몇가지 부분에서 Trade-off가 요구됩니다. - Hash function 해시 함수는 큰 범위의 입력 값을 작은 도메인으로 줄여야 합니다. 그 과정에서 필연적으로 다른 입력에 대해 같은 값(collision)이 나올 수도 있습니다. 이 과정에서 collision ..

DBMS를 개발할 때는 아래의 사항을 고려해야 한다. 가용한 메모리보다 큰 데이터를 처리할 수 있어야 한다. Disk I/O는 성능저하의 원인이기 때문에 신중하게 사용해야 한다. Disk에서의 탐색은 Random보다 Sequential access가 더 빠르기 때문에 순차탐색을 최대화 해야한다. 이 사항들을 염두하고 DB 저장소를 관리하는 법을 알아보자. File Storage DBMS는 그들만의 file format을 이용하거나, OS에서 제공하는 파일 시스템을 이용해서 데이터베이스를 관리한다. 이런 파일들은 Storage Manager가 관리해준다. Storage Manager 기본적으로 데이터베이스의 파일을 여러 page 단위로 쪼개어 관리하게 된다. 여기서 page는 데이터가 들어있는 고정된 크기..

Normalization 정규화는 간단하게 말하면 비 정상상태의 테이블을 정상상태로 만들어 주는 것을 의미한다. 비 정상상태 비 정상상태의 테이블은 insert, update, delete의 명령을 수행할 때 적절치 못하게 동작하는 테이블을 의미한다. - insert시 쓸데없는 null값을 허용하는 경우 회원 정보를 저장할 때 ID가 null값이 들어가는 상황 - update시 데이터의 불 일치가 일어나는 경우 같은 ID값을 갖고있는 회원의 이름이 다르게 저장되는 상황 - delete시 특정 튜플이 모두 삭제되는 경우 교수가 강의가 끝나 course_id를 지웠는데, 해당 column의 데이터가 모두 삭제되는 상황 Lossless Decomposition 비 정상상태를 해결하는 방법은 보통의 경우 테이블..

E-R model에서 E는 Entity, R은 Relationship을 지칭하는데 이 용어가 무엇을 뜻하는지를 우선 알아보자. Entity set entity(개체)란 구분이 가능한 객체로 attribute의 집합으로 표현되기도 한다. tuple과 헷갈리기 쉬운데 tuple은 실제 DB에서 사용되는 용어이고, attribute의 순서가 중요하지만, entity는 DB 설계에서 사용되는 용어이고, attribute의 순서가 중요하지 않다. 이런 entity의 집합을 entity set이라 하고, 다음과 같이 그릴 수 있다. relation과 생김새가 비슷하지만, 여기에는 표현되지 않은 attribute가 나중에 구현에 가서는 생기는 등 차이점이 존재한다는 점을 알아두자. 밑줄친 attribute는 prim..

모든 예시는 sqlite3을 기준으로 작성하였습니다. 이 포스트에서는 아래의 내용을 다룹니다. Join inner left outer right outer full outer natural on using Views update view Simple View Transactions Integrity Constraints not null primary key unique check references on (Action) Built-in Data Type date time timestamp interval julianday Large-Object Type blob clob Index Output Redirection Join join 연산은 Cartesian-Product와 Select 연산의 합으로 구현..

모든 예시는 sqlite3을 기준으로 작성하였습니다. 이 포스트에서는 아래의 내용을 다룹니다. 테이블 생성 Domain Type 테이블 업데이트 insert delete drop alter update Query select from where Relational Language DML DDL Aggregate Function avg min max sum count Window Function row_number rank 기타 Query operation like (%, _), substring, || Set operation (union, intersect, except) Set membership (in) / Set comparison (exists, unique) order by limit Null..