티끌모아 태산

Dynamic hashing Good for a database that grows and shrinks in size Allows the hash function to be modified dynamically Extendable hashing - one form of dynamic hashing Example 다음과 같은 search-key를 따르는 레코드에 대한 파일이 있을 때 주어진 hash function h(x)를 통해 반환된 extendable hash structure가 아래와 같이 주어져 있다. (20점) (h(x) : x를 8로 나누었을 때의 나머지를 이진법으로 반환) (h(x) : Returns the remainder of x divided by 8 in binary number) ..

이번 시간에는 concurrency control 기초인 recoverbility와 트랜잭션들이 동시에 실행될 때 rollback이 발생하면 어떻게 될지 알아 보겠습니다. 지난번에 배웠을 때 처럼 K가 H에게 20만원을 이체할 때 H도 본인 계좌에 30만원을 입금하면 여러 형태의 실행이 가능 할 수있다는 것을 확인했습니다. 그리고 각 case 마다 나다타는 operations의 순서를 우리는 schedule이라고 하였습니다. 여러 transaction들이 동시에 실행될 때 각 transaction에 속한 operation들의 실행 순서를 Schedule 이고 합니다. 자 그럼, 저번 시간에는 serializability에 대해서 배워보았는데요 이번시간에는 recoverbility에 대해서 배워보겠습니다...

이번 시간에는 concurrency control의 기초가 되는 schedule과 serializability에 대해서 알아보도록 하겠습니다. Schedule 자, K라는 사람이 H라는 사람에게 20만원을 이체할 때 H도 ATM에서 본인 계좌에 30만원을 입금한다면 여러 형태의 실행이 가능할 수 있습니다. 1 case K의 트랜잭션이 발생한 이후에 H의 트랜잭션이 발생하는 경우 입니다. 즉 K에서 read, write, commit 한 후 H에서 read, write하고 commit하는 순서입니다. 2 case 이번에는 30만원을 입금하는 트랜잭션이 먼저 발생하고 그 후에 K가 H에게 20만원을 송금하는 트랜잭션이 발생한 것입니다. 3 case 이번에는 20만원을 송금하는 트랜잭션을 먼저 시작을 했습니다..

이번시간에는 트랜잭션과 관련된 중요한 속성들인 ACID에 대해서 공부해 보겠습니다. Transaction 다음과 같이 간단한 예제를 통해서 개념에 대해 배워보겠습니다. J가 H에게 20만원을 이체한다면 각자의 계좌는 어떻게 변경돼야 할까요? 현재 상태를 살펴보면, 먼저 J는 계좌에 100만원이 있고 H는 200만원이 있다고 가정해 보겠습니다. J가 H에게 20만원을 보내게 되면 J는 100만원에서 80만원이 되고 H는 200만원에서 최종적으로 220만원이 됩니다. 그러면 이 과정을 SQL문으로 표현하면 어떻게 될까요? account 테이블에서 잔액을 의미하는 balance 를 업데이트 해주는 과정입니다. // J part UPDATE account SET balance = balance - 200000 ..

이번 시간에는 B tree 데이터 삭제 방식에 대해서 배워보도록 하겠습니다. B tree BST를 일반화한 트리입니다. 부모 노드는 자녀 노드를 두 개 이상 가질 수 있습니다. 노드가 자녀를 x개 가졌다면 key는 x-1개를 가집니다. 노드 내의 key들은 오름차순으로 저장됩니다. 모든 leaf 노드들은 같은 레벨에 있습니다. B tree parameter M: 각 노드의 최대 자녀 노드 수 M - 1: 각 노드의 최대 key 수 [M/2]: 각 노드의 최소 자녀 노드 수 [M/2] - 1: 각 노드의 최소 key 수 *Root node제외 B tree 데이터 삭제 *데이터 == key를 의미 삭제도 항상 leaf 노드에서 발생 삭제 후 최소 key 수보다 적어졌다면 tree 재조정! 삭제도 root n..

이번 시간에는 B tree의 개념과 특징 그리고 데이터 삽입이 어떻게 동작하는지를 배워보겠습니다. -> DB 인덱스와 관련있는 자료구조! B tree 개념과 특징 B tree를 공부하기 전에 이진 탐색 트리(BST)에 대해서 알아보겠습니다. BST의 특징은 다음과 같습니다. 모든 노드(Node)의 왼쪽 sub-tree는 해당 노드의 값보다 작은 값들만 가지고 모든 노드의 오른쪽 sub-tree는 해당 노드의 값보다 큰 값들만 가집니다. 자녀 노드는 최대 두 개까지 가능하다. 그런데 자녀 노드를 세 개까지 갖고 싶으면?! 즉, 다음과 같이 자녀가 3명인 형태를 갖고싶으면 어떻게 해야할까요? BST의 대소 비교 아이디어를 적용해보면 부모 노드는 하나의 값만 갖는게 아니라 K1과 K2값을 갖도록 해야합니다. ..

이번 시간에는 데이터베이스에서 index가 중요한 이유와 동작 방식 등에 대해서 알아보도록 하겠습니다. Indexing 다음과 같이 쿼리문이 있다고 생각해 보겠습니다. 현재, customer table은 아래와 같이 구성되어 있고, 데이터의 수가 100만개라고 가정해 보겠습니다. SELECT * FROM customer WHERE first_name = 'Minsoo'; 이때, first_name에 index가 걸려있지 않다면 성능은 어떻게 될까요?! index가 걸려 있지 않다면 first_name이 'Minsoo'인 것을 찾기위해 100만개의 데이터를 모두 탐색해야합니다. 이렇게 하나하나 모두 다 확인하는 것을 Full scan or table scan이라고 합니다. 그리고 시간복잡도는 데이터의 개수..

이번 시간에는 수업 시간에 배운 데이터 분석 내용에 대해서 리뷰해 보도록 하겠습니다. 목차는 다음과 같습니다. Decision Support Systems Data Analysis and OLAP Data Warehousing Data Mining Decision Support System 결정 지원 시스템이란 단어를 보면 유추할 수 있듯이, 온라인 거래 처리 시스템으로부터 수집된 데이터를 기반으로 비즈니스 결정을 지원데 사용됩니다. Data analysis Statical analysis Data mining Data Warehouse Data Analysis and OLAP On-Line Analytical Processing (OLAP) - 데이터를 분석하여 비즈니스 결정을 지원하는데 사용되는 기술..

이번 시간에는 빅데이터와 Hadoop 개념에 대해서 간단히 알아보도록 하겠습니다. Big data Big data 출현 배경 먼저, 빅데이터는 인터넷과 모바일 확산으로부터 다양한 대규모의 데이터 발생과 데이터의 방대한 활용성 등으로 인해서 출현하게 되었습니다. 예를들어, IoT 기기의 확산은 대량의 데이터를 발생시켰고 이러한 방대한 양의 데이터를 어떻게 효율적으로 처리하고 관리하기 위한 연구가 활발히 진행되고 있습니다. Big data란 빅데이터는 기존 데이터베이스 관리도구로 데이터를 수집, 저장, 관리, 분석할 수 있는 역량을 넘어서는 대량의 정형 또는 비정형 데이터를 저장하고 이로부터 가치를 추출하고 결과를 분석할 수 있는 기술을 의미합니다. 쉽게 말해, 다양한 종류의 대규모 데이터로부터 원하는 데이..

이번 시간에는 DB schema 설계를 잘못하면 어떤 문제가 발생할 수 있는지 배워 보겠습니다. 그리고 DB 설계의 중요성에 대해서 알아보겠습니다. 먼저 이상 현상(anomaly)이 무엇인지 보면, 불필요한 데이터 중복으로 인해 테이블에 대한 데이터 삽입, 수정, 삭제 연산을 수행할 때 발생할 수 있는 부작용을 의미합니다. 그래서 이상 현상을 제거해 나가면서 데이터베이스를 올바르게 구축 혹은 설계해 나가는 과정을 정규화 과정이라고 합니다. 1. 중복 데이터 문제 Insertion anomalies 위 학생수강 테이블에서 튜플마다 강좌 이름과 강의실이 중복된 데이터가 있는 것을 확인할 수 있습니다. 이는 학생 정보와 강의 정보가 한 테이블에 있기 때문입니다. 이를 해결하기 위해서 테이블을 분리 시켜줘야합니..