Note: DB/네트워크/무선이동통신

데이터베이스

데이터베이스의 정의

상호 연관된 자료를 집중화하여 체계적으로 조직한 자료의 집합

정의의 의미? 통합된 자료저장소, 자료의 공유를 전제

파일방식의 단점

자료의 중복성(Redundancy)

파일간 자료 불일치(Inconsistency)

자료 의존성(Data Dependence)

자료의 통합성(Integration) 부족

자료의 비호환성(incompatibility)

자료의 공유성(Sharing) 결여

DBMS의 장점

데이터의 중복을 피할 수 있음

저장된 자료를 공동으로 이용할 수 있음 

데이터의 일관성, 무결성, 보안을 유지할 수 있음

데이터를 표준화할 수 있음

데이터를 통합하여 관리할 수 있음

항상 최신의 데이터를 유지함

데이터의 실시간 처리가 가능함

데이터의 논리적/물리적 동립성이 보장됨

DBMS의 단점

데이터베이스 전문가 부족

전산화 비용의 증가

대용량 디스크로의 집중적인 Access로 과부하(Overhead)가 발생

파일의 백업(Backup)과 복구(Recovery)가 어려움

시스템이 복잡함

데이터베이스를 보는 세 가지 관점

데이터베이스를 중심으로 보는 물리적 관점(내부적 관점)

DBMS를 중심으로 보는 논리적 관점(개념적 관점)
사용자, 또는 응용프로그램 별로 보는 사용자 관점(외부 관점)

데이터베이스 스키마

 데이터베이스에서 자료의 구조, 자료의 표현 방법, 자료 간의 관계를 정의한 것을 말하는 전산학 용어이다. 데이터베이스 관리 시스템(DBMS)이 주어진 설정에 따라 데이터베이스 스키마를 만들어 내며, 데이터베이스 사용자가 자료를 저장, 조회, 삭제, 변경할 때 DBMS는 그것이 생성한 데이터베이스 스키마를 참조하여 명령을 수행한다.

데이터베이스 스키마는 3층 구조로 되어 있다.

외부 스키마(External Schema): 프로그래머나 사용자의 입장에서 데이터베이스의 모습으로 조직의 일부분을 정의한 것

개념 스키마(Conceptual Schema): 모든 응용 시스템과 사용자들이 필요로하는 데이터를 통합한 조직 전체의 데이터베이스 구조를 논리적으로 정의한 개념

내부 스키마(Internal Schema): 전체 데이터베이스의 물리적 저장 형태를 기술하는 개념

DB에서 데이터를 읽어오는 단위는 Block. 즉 I/O는 Block 단위로 이동

블록이 메모리에 있으면 페이지, 디스크에 있으면 블록

임의 접근시간(random access time)

데이터 접근시간(data access time), 헤드가 원하는 트랙에 있는 레코드를 찾아 전송하는 데 걸리는 시간

탐구시간(seek time) + 회전지연시간(rotational delay) + 데이터 전송시간(block transfer time)

10~30ms로 메인메모리 접근시간(10~100ns)에 비해 매우 느림

Database의 성능향상의 초점은 디스크 접근 회수의 최소화: 디스크에 배치, 저장하는 방법이 중요한 문제!

DBMS가 File Manager에게 명령할 수 있는 연산

1. 저장 파일 f에서 저장 레코드 r을 검색

2. 저장 파일 f에 있는 저장 레코드 r을 대체

3. 저장 파일 f에 새로운 레코드를 첨가하고 새로운 레코드 ID, r을 반환

4. 저장 파일 f에서 저장 레코드 r을 제거

5. 새로운 저장 파일 f를 생성

6. 저장 파일 f를 제거

File Manager가 Disk Manager에게 명령할 수 있는 연산

1. page set S로부터 페이지 P의 검색 file manager의 요청

2. page set S 내에서 페이지 P의 교체 file manager의 요청

3. page set S에 새로운 페이지 P의 첨가(자유공간 page set의 빈 페이지를 할당) disk manager의 필요

4. page set S에서 페이지 P의 제거(자유공간 page set으로 반환) disk manager의 필요

File의 구성/조직방법 4가지

1. 순차파일(Sequential File)

  들어온 순서대로 자료가 저장된 파일, 특정자료를 찾기 위해서는 처음부터 찾아야 함.

2. 직접파일(Direct File)

  자료가 키값에 의해 지정된 곳에 저장된 파일. 따라서 즉시 찾을 수 있다.

  사상함수: 키 값을 저장장치의 물리적 주소(실린더, 트랙, 섹터번호 등)로 변환시켜주는 함수. 대표적인 것으로 해싱(Hashing) 함수.

3. 색인된 순차파일(Indexed Sequential File)

  색인파일이 추가된 순차파일. 색인 구역을 통해 자료에 직접접근.

  순차파일은 레코드들이 키값 순으로 저장되어 있어야 함.

  색인은 B트리를 개선한 트리구조로, 자료는 선형구조로 되어있다.

  기억공간의 낭비를 줄이고 접근속도를 빠르게 해준다.

4. 다중 키파일(Multi Key File)

  여러 경로를 통해 파일의 자료에 접근할 수 있는 파일. 중복성이 사라지고 무결성이 유지된다.

  물리적 데이터베이스 구축의 기본.

  ⓐ 역파일(Inverted File)

    각 응용에 적합한 인덱스를 선정하여 구축.

    역색인(Index)은 레코드의 필드와 주소 or 필드(보조키)와 기본키의 쌍으로 구성됨.

    기본 키는 레코드가 저장된 주소에 직접 연관.

    역파일이란 여러개의 역색인표를 통해 자료에 접근할 수 있도록 된 파일.

    역색인표만을 검색해 많은 질의에 바로 응답할 수 있고, 역색인표는 트리나 테이블로 구현됨.

    역색인은 직접파일이나 색인된 순차파일 위에 만들어 질 수 있음.

  ⓑ 다중 리스트 파일(Multi List File)

    하나의 인덱스 값마다 데이터 레코드 리스트를 구축

    자료파일에서 특정항목(필드)의 같은 자료값들을 가진 레코드들을 포인터로 연결한 리스트 형태의 파일.

    필드의 항목값과 시작포인터 쌍으로 된 색인표에서 자료탐색이 시작됨.

    레코드에 포인터 필드가 추가되며 여러 필드에 대해 연결리스트를 구축할 수 있음

    자료파일이 추가되는 다중리스트는 단순연결, 이중연결, 원형연결 등으로 구축됨.

균형트리

모든 리프노드가 같은 레벨에 위치

B 트리

아래 조건을 충족하는 m-원 탐색트리

ⓐ 균형트리

ⓑ 루트를 제외한 모든 노드는 최소 반 이상 공간 사용

ⓒ 키 값들이 내부 및 리프 노드들에 저장되어 있음

B+ 트리

아래 조건을 충족하는 m-원 탐색트리

ⓐ 균형트리

ⓑ 루트를 제외한 모든 노드는 최소 반 이상 공간 사용

ⓒ 모든 키 값들이 리프 노드에 저장됨(내부 노드에 저장된 값은 분리값(split value) 또는 분리자(separator))

B-Tree Example

버디 버킷(Buddy Bucket)

두 버킷이 똑같은 버킷깊이 p를 가지고 있고 저장된 레코드 모조 키들의 처음 (p-1) 비트들이 모두 같은 버킷

Select 연산의 비용(Cost)

ⓐ 키 애트리뷰트(Key Attribute)

  선형 탐색: b/2

  이원 탐색: log_2 b(worst case)

  기본 인덱스 이용: x + 1

  해싱 함수를 이용한 비용: 1

ⓑ 키가 아닌 애트리뷰트(Non-key Attribute(multiple records))

  집중 인덱스 이용: x + s/b_r

  비집중 인덱스 이용: x + s(worst case)

  이원 탐색: log_2 b + s/b_r

해시조인의 비용

3(B_r + B_s) = R의 해싱 + S의 해싱 + R의 버켓과 S의 해당 버켓간의 조인(해시검사)

When H(K)=K mod M일 때, 메모리 버퍼가 최소 M 페이지 이상 존재(R 및 S의 해싱 단계)

         & 해시검사단계: R 또는 S의 한 버켓이 메모리로 동시적재 가능

참고자료

http://goo.gl/fpU4zu

http://blog.naver.com/cheinvan?Redirect=Log&logNo=80022762038

---

네트워크

종단 간 해결해야 할 문제점(End-to-End Issues)

연결의 설정과 해제가 불분명 → 많은 다른 호스트들의 연결이 가능

적절한 타임아웃 기법이 필요(왕복지연시간(RTT)가 다를 수 있음)

네트워크의 긴 지연 발생 - 오래된 패킷의 도착에 대한 준비 필요

목적지마다 용량이 다를 경우 - 다른 양의 버퍼링에 대비할 필요

네트워크마다 용량이 다를 경우 - 네트워크 혼잡에 대한 준비 필요

 TCP는 흐름제어(flow control)과 혼잡제어(congestion control) 두 개의 제어 메커니즘을 이용하여 end-to-end 간의 신뢰성 있는 전송을 보장함. 흐름제어는 송신자가 수신자의 수신 속도보다 빨리 전달하지 못하도록 막는 기법, 혼잡제어는 과다한 데이터가 네트워크로 유입되어 교환기나 링크가 과부화되는 것을 막는 기법. 즉 흐름제어가 종단 간의 문제라 한다면 혼잡제어는 종단 호스트와 네트워크의 상호작용 방식에 관한 문제.

Advertised Window

수신자가 수신을 하는 데 쓸 수 있는 가용용량

Effective Window

더 보낼 수 있는 양

Network Transparency

상대방이 어디에 있건, 응용해서. Physical한 것은 안보이고 알아서 통신

Marshalling(마샬링, Encoding)

응용 데이터를 메시지화 함, 인코드

하나 이상의 프로그램 또는 연속되어 있지 않은 공간으로부터 데이터를 모은 다음, 데이터들을 메시지 형식으로 버퍼에 넣은 뒤 특정 수신기나 프로그래밍 인터페이스에 맞게 해당 데이터를 조직화하거나 미리 정해진 형식으로 변환하는 과정

Unmarshalling(언마샬링, Decoding)

메시지를 응용데이터화 함, 디코드

마샬링을 통해 보내진 데이터들을 원래 구조로 복원시키는 것.

마셜링 데이터 유형

기본(Base) 타입: int, float, ...

플랫(Flat) 타입: structure, array, ...

컴플렉스(Complex) 타입: pointer, tree, ...

변환전략 2가지 +1옵션

규범적 중재유형(Canonical Intermediate Form), 수신 측 교정 방식(Receiver-makes-right)

+동일한 구조를 갖는 다는 것을 송신 측에서 아는 경우, 수신 측 교정 방식을 그대로 사용하는 방식

태그(Tag)

메시지에 포함되는 일종의 추가적인 정보(기본 유형을 보다 구체적으로 표현),

수신 측에서 메시지를 디코드하는 데 도움을 줌.

데이터의 타입, 길이 등

언태깅의 경우 보낼 때부터 제한된 형식에 맞춰서 보내기 때문에 효율성은 높으나 융통성이 떨어짐.

스텁(Stub)

인자 마셜링을 수행하는 코드로, 일반적으로 RPC를 지원하기 위해 사용.

서버 측에서 스텁은 원격 프로시저를 부르는 데 사용되는 인자로 활용할 수 있도록 메시지를 여러 개의 변수로 변환.

인터프리트되거나 컴파일되어 구현할 수 있음. 디스크립션의 변경이 쉬워, 인터프리트 스텁이 유연하며 더 많이 사용됨.

XDR(External Data Representation)

배열의 길이 제외하고 Untagged
Compiled Stubs

ASN.1(Abstract Snytax Notation One)

Tagged

Compiled/Interpreted Stubs

NDR(Network Data Representation)

Architecture Tag(Receiver-makes-right)

Compiled Stubs

데이터 압축

ⓐ 무손실: 압축/비압축 후의 데이터가 원래의 데이터와 정확히 일치

ⓑ 손실: 받는 데이터가 보낸 데이터와 정확히 같다는 것을 보장하지 않음. 사람이 인지하지 못할 정도는 제거해 압축.

무손실 압축 알고리즘

ⓐ RLE(Run Length Encoding): AAABBCDDDD → 3A2B1C4D, C가 1C가 된 것처럼 변화가 많은 데이터의 경우 역효과.

ⓑ DPCM(Differential Pulse Code Modulation): AAABBCDDDD → A0001123333. B와 1의 비트 수가 다르다. 영상에서 RLE보다 좋음.

ⓒ Dictionary-Based Methods: 자주 나오는 Term들의 사전을 만들어 놓고, 각 구절에 대해 해당 인덱스를 전송.

DicBased ex) Lempel-Ziv(LZ), LZ의 변형이 GIF 압축에 사용됨. 10대 1 압축비율도 때로 가능하나 보통 x3.

4가지 애플리케이션

SMTP(Simple Mail Transfer Protocol): 전자우편용 프로토콜

HTTP(HyperText Transport Protocol): 웹 브라우저와 웹 서버 간에 통신하기 위해 사용

DNS(Domain Name System Protocol): 네임 서버에게 질의하고 응답하기 위해 사용

SNMP(Simple Network Management Protocol): 원격 네트워크에 위치하는 노드의 상태를 알아보기 위해 사용

참고자료

http://cafe.naver.com/gaury/17726

http://blog.daum.net/tlos6733/48

---

무선이동통신

Cell Size

기지국이 커버하는 영역

PMF, PDF, CMF, CDF[RVs can be of two types: Discrete(PMF/CMF), Continuous(PDF/CDF)]

PMF(Probability Mass Function): 확률질량함수, 이산형분포의 확률 함수

PDF(Probability Density Function): 확률밀도함수, 연속형분포의 확률 함수, 그래프에서 높이

CMF(Cumulative Mass Function): 누적질량함수, 이산형분포의 누적확률함수

CDF(Cumulative Density Function): 누적밀도함수, 연속형분포의 누적확률함수, 그래프에서의 면적

RP ⊃ Markov ⊃ BDP(BiDecision Process) ⊃ Poisson

Source Coding

정보 전송을 효율적으로 수행하기 위해 전송하고자 하는 정보에서 필요치 않은 정보를 제거하여 전송량을 줄이는 것을 의미

아날로그 형태를 디지털로 변환, 신호를 압축 부호화하여 전송효율↑

인터넷에 흔한 ZIP 파일

ADM, ADPCM, DM, DPCM 등의 파형부호화, 파형 변환 후 계수값만을 보내는 변환 부호화(DCT 등), 음원 부호화(LPC, Vocoder 등), 복합부호화(CELP, QCELP 등)

Channel Coding

데이터를 착오없이 전송할 수 있도록 잉여 비트를 추가하는 오류 정정 기법을 의미

디지털 형태를 디지털로 변환, 전송 오류의 검출 및 정정

NASA-우주를 오가는 신호들

해밍코드, CRC, BCH, 콘볼루션 코드 등

Source Coding - Prefix Coding

 A prefix code is a type of code system (typically a variable-length code) distinguished by its possession of the "prefix property"; which states that there is no valid code word in the system that is a prefix (start) of any other valid code word in the set. For example, a code with code words {9, 55} has the prefix property; a code consisting of {9, 5, 59, 55} does not, because "5" is a prefix of both "59" and "55". A prefix code is an example of a uniquely decodable code: a receiver can identify each word without requiring a special marker between words.

Fourier Transform Properties

Fourier Transform of Various Functions

참고자료

http://thefouriertransform.com

http://en.wikipedia.org/wiki/Prefix_code