다음과 같이 Sailors, Boats, Reserves 테이블이 정의되어 있다. Sailors (sid, sname, rating, age)Boats (bid, bname, color)Reserves (sid, bid, day) 구체적인 데이터 표기는 생략하였다.이제 이 테이블에 대해 관계대수 문제를 풀어보자. 1. bid = 103 인 보트를 예약한 선원들의 이름 구하기  예약 테이블에서 bid = 103 인 예약만 가져온 뒤, 선원 테이블과 자연조인하였다.그러면 두 테이블의 모든 공통필드를 기준으로 동등 조인을 걸고, sid 가 동일한 경우만 추려낸다.그러면 103번 보트를 예약한 선원들만 남게 되므로, 여기에서 sname 을 프로젝션하여 조회하면 된다.  강의록에서는 이렇게 복잡하게 푼 경우도 제..

질의언어 (Query Language) 는 데이터베이스로부터 데이터를 가져오고 조작하는 언어이다.질의언어는 모든 알고리즘을 표현할 수 없는, Turing Complete 하지 않은 언어이다. 쿼리는 relation instance 에 적용되며, 쿼리의 적용결과 역시 relation instance 이다.또한 관계 대수를 정의할 때 각 릴레이션(테이블)의 필드는 위치 기반 또는 이름 기반으로 표현할 수 있는데, SQL에서는 두 방법 모두 사용가능하며, 상황에 맞게 적절하게 사용하면 된다.   관계 대수를 정리하기 위해 위 그림과 같은 테이블을 준비하였다.S1, S2 는 같은 스키마를 가진 Sailors 테이블이고, R1 테이블은 Reserves 테이블이다.선원과 선원이 예약한 보트에 대한 정보를 볼 수 있..

Sleep and Wakeup프로세스를 동기화하여 서로 다른 프로세스가 동시에 임계 구역에 존재하지 못하도록 막는 알고리즘을 '상호 배제' 라고 하였다.상호 배제를 달성하는 간단한 알고리즘들을 정리하였는데, 이 알고리즘들은 모두 busy waiting 알고리즘으로 계속해서 공유 변수를 체크하면서 자신이 임게 구역에 들어갈 수 있는지 직접 확인해야했다. busy waiting 방식은 CPU 시간을 낭비하고, 우선순위 스케줄링 방식에서 우순선위 역전 문제를 일으키기도 한다.그래서 그 대안으로 나온 방법이 Sleep and Wakeup 이다. sleep, wakeup 은 모두 시스템 콜이다.sleep 시스템 콜을 호출하면 다른 프로세스가 wakeup 시스템 콜을 호출할 때까지 호출한 프로세스를 blocked ..

뷰뷰는 일종의 테이블이다. 하지만 그 스키마와 데이터가 저장되는 것이 아니라, 뷰 정의에 따라 계산된다.따라서 이름 그대로 한 테이블에 대한 '뷰', 관점을 저장하는 것과 같다. 뷰는 다음과 같이 생성한다.CREATE VIEW YoungActiveStudents(name, grade) AS SELECT S.name, E.grade FROM Students S, Enrolled E WHERE S.sid = E.sid AND S.age > 21 AS 절 이후에 이 뷰의 정의를 SQL 형식으로 적으면 된다.그래서 어떻게보면 뷰는 일종의 함수처럼 생각하여 그때 그때 계산하는 값으로 볼 수 있다. 뷰는 기본 테이블(데이터베이스에 저장된 실제 테이블)처럼 ..

DFA지난 글에서 오토마톤에 대해 정리하면서 오토마톤은 다양한 기준으로 분류할 수 있다고 하였다.그 중에서 이번 글에는 DFA 오토마톤에 대해 정리해보려고 한다. DFA (Deterministic Finite Accepter)는 지난 내용에 따라 다음과 같이 이해할 수 있다. - 결정적이며 (Deterministic, 각 상태에서 주어진 입력에 대해 갈 수 있는 경로가 유일하다.)- 유한한 (Finite, 메모리 == 저장공간이 유한하다.)- Accepter (기계의 output 이 yes(accept) / no(reject) 로 이진적이다.)  DFA는 오토마톤의 일종이지만, 특이하게 temporary storage 가 없다.그렇다고 저장공간이 없는 것은 아니고, control unit 에 마치 플립플..

오토마톤은 디지털 컴퓨터에 대한 추상적인 모델이다.디지털 컴퓨터는 기본적으로 입력이 주어지면 저장공간을 활용하여 이를 적절히 처리한 뒤 결과물을 내보낸다. 이때 입력 데이터는 수학적 편의를 위해서 '알파벳 심볼에 의해 정의된 문자열' 이라고 정의한다. (꼭 이래야만 하는 것은 아니다)그리고 인풋 파일은 무한한 길이의 테이프로부터 문자열을 읽어들일 수 있다고 생각한다.이 테이프는 여러개의 셀로 구성되어 있으며, 각 셀에는 알파벳 심볼 하나가 저장된다. 디지털 컴퓨터는 내부적으로 연속된 시간이 아니라, 이산적인 시간 체계로 동작하며,각 시간마다 인풋 파일의 왼쪽에서 오른쪽을 향해 한번에 하나의 셀(심볼)을 읽어들인다.그리고 End-Of-File (EOF) 신호를 통해 문자열의 끝을 감지할 수 있도록 기계가 ..

비트코인의 트랜잭션에는 간단한 스크립트 코드를 넣을 수 있다.그래서 비트코인은 프로그래머빌리티가 없다, static 하다, 변하지 않는다고 하면 틀린 말이다.물론 이 스크립트 코드는 turing complete 하지는 않아서 모든 기능을 자유롭게 쓸 수 있지는 않지만, 제한적인 프로그래밍이 가능하다.(참고로 이더리움은 튜링 컴플리트를 지향하는 블록체인 프로젝트이다. 기말고사 범위에서 정리할 예정) 비트코인의 스크립트는 스택 기반으로 실행되는 코드이며,트랜잭션 검증과 서명 검증을 위한 다양한 명령어를 제공한다. 대표적인 스크립트 타입은 다음과 같다.- Pay To Public Key (P2PK) :비트코인의 초창기 트랜잭션 방식, 사카시 나카모토가 고안했던 방식으로 public key hash에 지불한다...

프로세스는 단독으로 자원을 경쟁적으로 사용하면서 실행되기도 하지만 서로 통신하고 협력하면서 실행되기도 한다.프로세스 사이에 통신할 때는 크게 3가지 문제점이 있다. 1. 어떻게 하나의 프로세스에서 다른 프로세스로 정보를 넘길 것인가?2. 어떻게 각 프로세스가 중요한 동작을 하고 있을 때 서로를 방해하지 않도록 보장할 것인가?3. 프로세스와 프로세스의 동작 사이에는 의존성이 존재할 수 있는데, 어떻게 올바르게 실행되도록 순서를 조정할 것인가?(프로세스 A가 생성한 데이터를 프로세스 B가 출력한다면, 프로세스 B는 프로세스 A의 동작이 끝날 때까지 기다려야 한다.) 이 문제를 해결하는 것을 가리켜 '프로세스 동기화' 라고 한다. 우선 첫 번째 문제인 하나의 프로세스에서 다른 프로세스로 정보를 넘기는 것은 단..

이번 글에서는 개념적 데이터베이스 설계를 통해 작성한 ERD를 관계 모델(테이블)로 구현해본다. 엔티티 셋엔티티 셋은 테이블로 만든다. 그림과 같은 엔티티 셋을 테이블로 만든다면 아래와 같이 SQL을 작성할 수 있다. CREATE TABLE Employees ( ssn char(11), name char(20), lot integer, PRIMARY KEY (ssn));  관계 집합 (relationship set)이진 관계관계 집합은 하나의 테이블로 만들 수 있다.이때 관계집합은 자신이 갖는 어트리뷰트 외에, 관계를 맺는 두 엔티티 셋의 PK 를 FK로 가져야 한다.(그리고 두 엔티티 셋의 PK 조합은 관계 집합의 슈퍼키가 된다.)  그림과 같은 ERD가 있을 때, Wo..

프로세스프로세스는 컴퓨터 메모리에 올라와있는, 실행중인 프로그램을 말한다.(실행중이지 않은 프로그램은 하드디스크나 SSD에 파일로서 존재하는 프로그램을 말한다.) 만약 여러 개의 프로그램을 실행해서 여러개의 프로세스가 생성되면 과연 정말로 여러 프로세스가 동시에 실행되고 있는 것일까?여러 개의 프로세스를 실행하는 것을 '멀티 프로그래밍' 이라고 하는데, 아래 이미지와 같이 구현된다.  그림에서 보는 것처럼 CPU가 프로세스를 하나씩 번갈아가면서 실행하는 것이 멀티 프로그래밍이다.하드웨어적으로는 (a) 와 같이 하나의 프로그램 카운터가 각 프로세스를 넘나들면서 실행하며,개념적으로는 4개의 독립된 프로그램 카운터가 존재하는 것처럼 동작한다.그래서 시간에 따른 프로세스별 실행 흐름은 (c)와 같은 모습으로 나..