NFADFA의 전이함수 δ는 가능한 모든 상태와 알파벳에 대하여, 하나의 다음 상태를 반환한다고 했다. 이 특징은 DFA의 이름에 들어간 "Deterministic(결정적인)" 이라는 수식어에서도 알 수 있다. 반면 "Non"-deterministic한 유한 오토마타인 NFA(Nondeterministic Finite Automata)의 전이함수 δ는 반환값이 하나가 아닌 여러개이거나, 0개일수도 있다.위 diagram의, $q_0$에서 뻗어나오는 화살표를 보자. 0이라는 입력에 대해 두 개의 화살표로 뻗어나오고 있다. 반면 $q_1$의 경우, 0이라는 입력에 대해 어떤 뻗어나오는 화살표도 찾아볼 수 없다. 위 오토마타에 "00101"이라는 입력이 들어왔을 때를 생각해보자. 이제는 상태변화가 한 줄기가 ..

컴퓨터란 무엇인가?컴퓨터는 무엇을 할 수 있고, 무엇을 할 수 없는가?컴퓨터가 연산하기 쉬운 문제와 어려운 문제의 차이는 무엇인가? 위 질문들은 컴퓨터 과학의 가장 근본적인 질문들이다. 연산 이론(computational theory)은 위 질문들을 고민하는 전산학의 한 꼭지다. 이 질문들이 어려운 이유는 현대의 컴퓨터는 수학적으로 정의하기 너무나도 복잡한 기계장치이기 때문이다. 컴퓨터란 무엇일까? 컴퓨터의 특징을 생각해보자. 컴퓨터의 메모리는 유한하다. 즉 메모리가 표현할 수 있는 상태들도 유한하다.컴퓨터의 연산 결과 또한 유한한 메모리로 표현가능하다.컴퓨터는 연산을 수행하는 장치이다. 그러나 컴퓨터는 입력이 들어오기 전까지, 다음에 자신이 수행해야 할 연산에 대해 알 수 없다.컴퓨터는 몇 가지 기본 ..

5.1 Introduction책꽂이에서 매번 책을 찾아 읽는것보다는, 많이 읽는 책을 책상 위에 두면 시간을 절약할 수 있다. 우리가 필요한 정보는 모든 책에 균등하게 분포되어있지 않기 때문이다. 프로그램 또한, 필요한 코드와 데이터가 균등하게 분포되어 있지 않다. 비슷한 방법으로, 프로그램에게 우리의 메모리가 더 빨라진듯한 환상을 느끼게 해줄 수 있다. 하지만, 빠르면서 큰 메모리는 존재할 수 없다. 책꽂이를 책상위에 얹을수는 없기 때문이다.프로그램의 실행은 지역성의 원리(principle of locality)를 따른다. 프로그램은 시간적/공간적으로 이미 참조한 데이터와 가까운 데이터를 다시 참조할 것이라는 의미이다. 구체적으로 설명하자면, 지역성에는 두 가지 종류가 있다.시간적 지역성(Tempora..

4.1 Introduction이 챕터는 프로세스의 구현방법에 대해서 다룬다. 아주 추상화/단순화된 관점에서부터 datapath를 만들고 간단한 버전의 MIPS를 구현하기에 이른다. 또한, 현실 세계에서 x86같은 복잡한 ISA 구현에 필수적인, 병렬적인(pipelined) 구현 방법 또한 다룬다.우리는 일부 정수 인스트럭션이나, 부동 소수점 인스트럭션 등을 제외하고 아래의 3종류로 분류되는, 간단한 MIPS 인스트럭션들만을 구현할 것이다.메모리 참조 인스터럭션: lw(load word), sw(store word)산수연산 인스트럭션: add, sub, AND, OR, slt브랜치 인스트럭션: beq(branch equal), j(jump)큰 그림모든 인스터럭션은 아래의 두 과정을 거친다.Program C..

15장과 16장은 쿼리 처리를 다룬다. SQL은 쿼리를 매우 높은 수준에서 표현하기 때문에, 쿼리 프로세서는 쿼리를 단순히 실행만 하기 보다, 어떻게 실행할지 고민하여 실행 효율을 높여야 한다. 15장에서는 쿼리 실행, 16장에서는 쿼리 컴파일에 집중한다.쿼리 컴파일 단계는 세 가지 단계로 나뉜다.파싱(parsing): 쿼리로부터 맥락 트리(parse treee)를 만듦논리적 계획 생성(Logical Plan Generation): 맥락 트리로부터 논리적 계획(보통 대수적 표현)을 생성한다. 실행시간을 최소화 하기 위해, 동등하지만 더 효율적인 계획으로 변경한다.물리적 계획 생성(Phyisical Plan Generation): 논리적 계획을 물리적 계획으로 변경한다.2번과 3번 단계를 흔히 쿼리 옵티마..

SELECT * FROM R이라는 쿼리를 실행 하기 위해서 어떻게 해야할까? 저장소의 모든 블럭을 검사해야한다면, 너무 비효율적이다. 일부 블록과 실린더를 따로 R을 위해 예약할 수도 있지만, 여전히 비효율적이다.인덱스는 하나 이상의 필드 값을 받아서, 그 값을 가진 레코드를 빠르게 찾을 수 있게 해주는 자료구조다. 인덱스를 사용하면 전체 레코드 중 일부만 보고, 원하는 레코드를 모두 찾을 수 있다. 인덱스가 기반하는 필드를 검색 키(search key)라고 한다.이 챕터에는 가장 흔한 형태의 인덱스를 다룬다. B-tree 이다. 또 다른 중요한 인덱스 구조인 2차 저장소의 해시 테이블도 다룬다. 마지막으로, 다차원의 데이터를 다루기 위해 디자인 된 인덱스 구조도 다룬다. 이 이덱스 구조들은 여러 값이나..

데이터베이스는 항상 디스크 등의 대용량의 데이터를 저장하는 2차 저장소를 갖습니다. 이 챕터에서는 전통적인 컴퓨터가 어떻게 스토리지를 관리하는지 요약합니다. 또, 릴레이션의 튜플들을 어떻게 저장하는지 다룹니다.13.1 메모리 계층(The Memory Hierarchy)컴퓨터 속 메모리 계층을 시작으로 챕터를 시작해봅시다. 메모리를 저장하는 부품들은 7종류로 나뉩니다. 크기와 접근 속도가 모두 다르며, 크기가 작을수록 접근속도는 빠르고, 바이트 당 가격도 올라갑니다.캐시(Cache): 내장 캐시(On-board cache)는 프로세서 그 자체 안에 포함되어 있고, 추가적인 level-2 캐시는 다른 칩에 포함됩니다. 프로세서가 요구하는 데이터는 메인 메모리에서 캐시로 옮겨져서, 몇 나노초 안에 데이터를 프..

SQL은 관계형 데이터베이스에서 널리 쓰이는 쿼리언어이다. SQL은 쿼리의 기능 뿐 아니라 데이터를 수정하는 DML(Data Manipulation Language)의 기능과 스키마를 정의하는 DDL(Data Definition Language)의 기능도 갖는다.SQL도 다양한 버전이 있다. ANSI, SQL-92(SQL2, SQL:1992), SQL-99(SQL3, SQL:1999), SQL:2023 등이다. 이 글에서 다루는 것은 SQL-92이다.6.1 Simple Queries in SQLSELECT, FROM, WHERE을 가지고 기초적인 쿼리를 할 수 있다. 관계대수(relational algebra)로 치자면, SELECT는 사영(projection) 조건, WHERE은 선택(selection..