스니스니 닷넷

⊙ 동전 바꾸기!
이건 Greedy Algorithm을 설명하기 위해서 가장 많이 사용되는 예제인데, 1000원을 동전으로 바꿀 때, 가장 적은 수의 동전으로 바꿀 수 있는 경우는? 당연히, 500원짜리 2개이다. 900원을 동전으로 표현하면, 500원짜리 1개와 100원짜리 4개가 될 것이다. 여기에서는 Greedy algorithm을 사용하여, 가장 큰 동전부터 뽑아내면 된다.
⊙ Suffix Dictionary
Prefix Dictionary와 반대되는 개념으로, 각각의 phrase들의 suffix가 dictionary 내의 다른 phrase를 이루고 있는 dictionary이다.
Suffix Dictionary를 이용한 encoding 방법의 예를 들어보자. ∑={a,b,c}인 D={abc, bc, c, a, b, d, dac, ac}라는 suffix dictionary가 있고, 이것들은 각각 {0,1,2,3,4,5,6,7}로 encoding한다. 이때, D에 있는 모든 phrase들의 suffix는 다른 phrase의 suffix라는 것을 알 수 있다.
그러면 이 때, T=abcabdaccd 라는 입력값이 주어졌을 때, 가장 짧은 codeword를 얻을 수 있는 방법은? 정답은 바로, Greedy Algorithm을 이용하는 것이다. 단, 여기에서는 모든 codeword가 같은 수의 bit를 가진다는 것이다. 여기에서는 총 8개가 필요하므로, 3bit면 되겠다. 저 T를 가장 짧게 encoding하면, O=034625이다. (prefix와는 경우가 다르다. prefix에서는 greedy algorithm을 적용할 수 없다.)

Dynamic Programming(이하 DP)은 어떤 고정된 조건이 주어졌을 때, 그 조건에 부합됨과 동시에 결과값이 최대 또는 최소가 되게하는 최적화 문제(Optimization problem)에 대한 해답을 주는 알고리즘이다. 그러나 모든 최적화 문제에 DP를 적용할 수 있는 것은 아니다. 다음과 조건을 만족할 때에만 사용 가능하다.
1. Optimal Substructure를 가질 때 : 최종적인 최적값이 그 하부에서의 최저값을 포함하고 있는 경우.
2. Overlapping Subproblems가 있을 때 : 자기 반복적인 (recursive) 알고리즘의 경우, 이미 한 번 풀어놓은 문제를 다시 풀어야 하는 경우가 생긴다. 이 때, 계산을 다시 하기 보다는 적당한 기억 장소에 결과값들을 저장해 놓고, 단순히 참조해서 사용한다.
( 밑에 보면 z[] 배열을 볼 수 있는데, 그것이 바로 요것!)
→ "Solve problem for input size 1...i-1, and use it for solving problem with input size i; then iterate."

⊙ 계단을 오르는 문제로 Dynamic Programming을 이해해보자.
총 n개의 계단이 있을 때,
T(n): n개의 계단을 오르는 총 방법의 수.
T(n-1): n-1 계단까지 오르는 방법의 수 (1칸 남은 상태)
T(n-2): n-2 계단까지 오르는 방법의 수 (2칸 남은 상태)

그리고 계단은 보통 한 번에 한칸, 두칸씩 오르기도 한다. (지식인은 급하면 세 칸씩도 오르더라만은... 나에겐 불가능이므로 제외!)
그러면, 내가 지금 n개의 계단을 올랐다면, 그것은 n-1번째 계단에서 한 칸 오른 것이거나, n-2번째 계단에서 두 칸 올라서 도달한 것이다. 그래서,
T(n) = T(n-1) + T(n-2) : recurrence equation (점화식 -ㅇ-)
가 성립한다. 그리고 다음과 같이 표현된다.
T(n) = ( ((√5)+1 )/2 )ⁿ

이것이 바로, DP의 fundamental intuition 이다. 대충 어떤 것인지 느낌이 오시는지? ^^

⊙ Prefix Dictionary
: 이것은, Dictionary 속에서 특정 phrase(여기에서는 encoding의 대상이 되는 문자들의 단위라고 생각하면 된다.)의 앞머리가, 같은 dictionary에 있는 다른 phrase이기도 하다는 것이다. 이는 tree 구조로 표현이 가능하며, 그림으로 나타내면 다음과 같다.

이 prefix dictionary의 전제는, ∑ = {A, B} 이며 최대 두 문자까지 encoding이 가능하다는 것이다. 또한 이것은 prefix code 이다.

이제, 본격적인 encoding 작업을 해보자.
입력 문자열이 AABABBAA일 때, 어떻게 하면 가장 짧은 encoding이 가능할까? (A는 0, B는 1로 나타내면 8개로 가능하다~ 할 수 있겠지만.... -.- 이건 간단한 예이고, general한 과정으로 풀어보자..흐흐)
이것은, 앞의 계단 문제와 매우 흡사하다. phrase를 encoding할 때, '이번에 encoding할 문자를 한 문자로 볼 것이냐, 이전것과 함께 두 문자로 불 것이냐?'는 것은 한 칸씩 오를 것이냐, 두 칸씩 오를 것이냐와 같다. 그래서 총 문자열 수는 총 계단수와 같다.

다음의 DP 알고리즘을 살펴보자.
z[1:n] : z[i]에는 i번째 까지 parsing했을 때 가능한 최소의 길이를 담아둔다.

z[0] ← 0
for i ← 0 to n
z[i] = ∞
for j ← i-1 down to 1
z[i] ← MIN(z[i], z[j] + length of codeword of input[j+1:i])

이것은, 길이 k인 phrase를 사용하게 되는 DP 알고리즘으로, O(kn) =O(n)이다.

지금 우리가 예로 보고 있는 것은, k=2이다. encoding해보자.
Input : AABABBAA
1. 제일 먼저 A가 등장했으므로, 10으로 encoding하고, z[0] = 2.
2. 그 다음 A가 나오면, 그냥 A로 parsing하면 10으로, z[1]= z[0]+2=4이고, 앞의 A와 함께 AA로 parsing하면 11로, z[1]=2가 되므로, z[1]=2가 된다.
3. 다음 문자는 B로, 그냥 B로 parsing하면 0000으로, z[2] = 2+4=6이 되고, 앞의 문자와 함께 AB로 parsing하면 z[2] = z[0] + 2 = 4가 되므로, z[2]=4이다.
4. 이런 식으로 반복하면, z[] = {2,2,4,5,6,9,9,11}로, 최소값이 들어가서, 전체 encoding의 길이는 11이 된다.

만약 k=3이라면, z[5]를 계산하기 위해서 z[4], z[3], z[2]까지 거슬러 올라가 보게 될 것이다.

여기에서 우리는, DP에서 z[n]이 매우 중요한 역할을 하고 있다는 것을 알 수 있다. 이것은 DP의 큰 특징 중에 하나이다.

⊙ Knapsack Problem (0-1 Knapsack Problem)
아주 간단한 예로, Knapsack Problem에 대해 이해해보자.
▪ knapsack의 크기가 50일 때, 어떤 물건들은 넣어야 가장 이익일까?
물건 1 : 부피 10, 가격 60만원 // 단위 부피 : 6만원
물건 2 : 부피 20, 가격 100만원 // 단위 부피 : 5만원
물건 3 : 부피 30, 가격 120만원 // 단위 부피 : 4만원
단위 부피로 생각해보면, 물건 1, 2를 챙겨야 겠지만(160만원), 사실 물건 2,3을 챙겨야 한다 (220만원). 이건 그냥 딱 봐도 알겠는데, 문제는! 물건이 무지무지 많으면 어쩌냐는 것이다! 이럴 때, DP를 사용한다. :)

1. A[1:n] 배열을 정의한다. 이것은 바로 knapsack이다. 1≤j≤n이라고 했을 때, 각 단계의 j에는 1 만큼 해당되는 부피의 물건을 넣을 수 있게된다. 그리고 j단계에서의 최대 이익값을 담고 있는 변수 maxBenefit(j)=0으로 초기화한다.
2. 전체 물건들의 집합을 S라고 했을 때, j를 하나씩 증가시키면서 그 때 knapsack A에 들어갈 수 있는 최대 가치의 물건 s를 넣는다.
3. 현재 j=i이고, s의 크기가 k였다고 가정하자. 그러면 j=i에서 j=i-k까지 물건 s로 채우고, 나머지는 j=i-k=1 단계 때의 물건들로 채워준다. 그리고 새롭게 갱신되는 maxBenefit(i)값 (= maxBenefit(i-k-1) + k의 가치)을 maxBenefit(i-1)과 비교해서 더 커졌다면 S=S-{s}로 만든 뒤, A의 상태를 저장한다. 이 때, maxBenefit(i-1)에 비하여 총합 가치가 커진 것이 아니라면, 이번 step은 차라리 빈 공간으로 둔다.
4. 2단계를 j=n이 될 때 까지 반복한다.

이렇게 DP를 사용하게 되면, j=i-k=1 번째의 최적화 답을 가져오는데 걸리는 시간은 O(1)이므로, n을 Knapsack크기, m을 물건의 개수라 하면, running time은 O(nm)이 되고, n과 m이 비슷할 때에는 O(n²)으로 polynomial time이 된다.

⊙Matrix-chain Multiplication
행렬의 곱을 어떤 순서로 행하면 가장 빠르게 할 수 있는가에 대한 문제인데, 앞의 3가지 예제외는 달리, 복잡하므로 따로 다루어야 겠다. (언제 할 지는 모르겠다. -.- )

⊙ Dynamic Programming VS Greedy Algorithm
DP에서는 모든 것이 정수라는 가정하에서 이루어졌다. 그런데, 정수가 아니라면? 예를 들어, Knapsack에서, 물건을 나눌 수 있다면 어떻게 할 것인가? (우유나 금가루 같은것들.) 이것은 바로 fractional knapsack problem으로, Greedy algorithm에 속한다. Greedy algorithm은 말 그대로, '탐욕적인 알고리즘'이다..;;


출처 : http://vorlon.eecs.cwru.edu/~kxm73/ : 덮옹님 홈페이지. 므흣.

9.2 Tries
KMP나 BM 알고리즘에서는 search 속도를 높이기 위해 pattern을 preprocess했지만(failure function, last function), Tries에서는 text를 preprocess한다. 따라서, fixed text에 연속된 query들이 있을 때 사용한다. 처음에 text를 preprocessing하는 데 비용은 많이 들지만, 이것은 나중에 계속되는 query 속도를 증가시킴으로 보상된다.
trie 는 'a tree-based data structure for storing strings in order to support fast pattern matching'이다. information을 retrieval 하는데 주로 사용된다고, "retrieval"에서 이름을 따왔다. trie에서 지원하는 주요 query operation들로는, pattern matching과 prefix matching이 있다.

1) Standard tries
⊙ S에 대한 standard trie 는 ordered tree T로, 다음과 같은 성질을 가진다.
1. T의 root를 제외한 모든 node에는 ∑의 한 문자가 labeled.
2. ordered tree 이므로, child는 정렬되어있다.
3. root->external path는 S의 string이 된다.
trie에서는, no string in S(∑으로 만들어진 string들의 집합) is a prefix of another string. 밑에 있는 trie 구조를 보면 알겠지만, 한 string이 다른 string의 prefix가 되면, 즉, bil, bill 이란 단어는 함께 S에 있으면 안된다. 이것때문에, S의 string은 unique하게 external node랑 짝을 이루게 되고, 이는 search를 간단하게 만든다. 또한, trie에서는, string들의 common prefix를 간결하게 저장한다.
→ 따라서, standard trie는
▪ 모든 internal node는 최대 d(∑ size)개의 child 가진다.
▪ s(string개수)개의 external을 가진다.
▪ 높이는 가장 긴 string의 길이와 같다.
▪ 전체 node 수는 O(n)이다. n은 total length.

⊙ Search : root에서 내려가면서 string을 찾는다. path가 존재하고, external node에서 끝나면, 해당 string이 존재하는 것이고, running time은 O(dm)이다. (d는 size of ∑이고, m은 size of string이다.) 최대 m+1개(root 1개 포함)의 node를 visit하고, 각 node에서 O(d) 걸린다. 여기에서, dictionary of characters를 hash table이나 lookup table로 구현하면 O(d)를 O(1) 이나 O(logd)가 될 수 있지만, d는 주로 constant이므로, 그냥 간단하게 O(d) approach를 사용한다.
따라서, standard tires는 word matching에 사용된다. word matching은 말 그대로, text에 있는 word를 찾는 것이다. 이는, text에서의 임의의 substring을 찾는 것(앞에서 배웠던 Brute-Force, BM, KMP와 같은)이 아니라, text에서의 한 단어와 정확히 일치하는 단어만 찾는것이다. tire를 사용하면, 길이 m인 단어를 찾는데 걸리는 시간은 역시, O(dm)이다. 이는 간단하게 prefix matching에 사용될 수도 있지만, pattern이 proper suffix이거나 두 단어로 span했을 때에는 효율적으로 수행되지 못한다.


⊙ Standard Trie 만들기
Standard trie를 만드는 것은, 아주 직관적이다. 그냥 S에 있는 string들을 trie T에 한 번에 하나씩 넣어주면 되는데, prefix-free이므로, 한 word를 넣을때, root부터 탐색을 하다보면, 한 internal node에서 멈추게 된다. 그러면 pattern의 그 다음 char부터는 child node를 만들어가면서 insert 해주면 된다. 역시, 한 단어를 insert하는데 걸리는 시간은 O(dm)이다. 따라서, S에 속한 string들의 총 길이가 n이라하면, trie하나를 만드는 데 걸리는 시간은 O(dn)이 된다.

⊙ Performance
전체 노드 수의 worst-case는, 모든 string이 다른 string과 common prefix를 가지지 않을 때이다. 이 때에는, 모든 internal node는 1개의 child node를 가지게 되기 때문이다.


2) Compressed tries
Standard trie에서의 공간 낭비 때문에 만들어진 것이 compressed trie이다. Standard trie에서, 많은 node들이 child가 1개이고, 이것은 단어 수보다 node 수가 더 많을 수가 있어서 낭비인 것이다. 따라서, compressed tire는 standard trie와 비슷하지만, 모든 internal node는 각각 최소 2개의 child node를 가진다.
Internal node v가 root도 아닌데 child node를 한 개 가지고 있으면 그 node는 redundant하다 하고, 이런 redundant node들의 chain을 하나의 node로 만든다.

⊙ Compressed Trie의 특징
▪ 모든 internal node는 2~d개의 child node를 가진다.
▪ s개의 external node를 가진다.
▪ 전체 노드 수는 O(s)이다.

⊙ Compact Representation
Compressed trie가 진짜 장점을 가지기 위해서는, 보조적인 index구조를 가져야 한다. 이 보조적인 index 구조는, 따로 저장할 필요는 없고, primary structure에 이미 저장된 string들의 collection에 구현된다.
예를 들어, S가 S[0], S[1], ..., S[s-1]의 배열이라 하자. 한 노드에 char들을 바로 적지 말고, (i, j, k) 로 적어넣는다. 이것은 S[i][j..k]를 의미하는 것으로, S[i]의 j~k 번째의 substring이라는 의미이다.



3) Suffix tries
한 String X에 대한 Suffix trie는 X의 모든 suffix들의 compressed tire이다. (suffix tree, position tree라고도 한다.) Trie이기 때문에, 한 suffix가 다른 suffix의 prefix가 되지 않게 하기 위해서, 기존의 ∑에 없던 문자 $를 suffix 뒤에 붙인다. 예를 들어, X가 "amizemize" 라면, 뒤의 mize는 mizemize의 prefix가 될 수 있기 때문이다. 그러나, mize$는 mizemize$의 suffix이기는 하지만 prefix는 아니다.
그리고 compact representation은 더 간단하다. (i,j)로 나타낼 수 있는데, 이것은 X[i..j]를 가리킨다.


⊙ Saving Space
string의 길이가 n일 때, 전체 suffix들의 길이의 합은,
1+2+3+...+n = n(n+1)/2
이므로, suffix들을 저장하는데 드는 공간은 O(n²)가 된다. 하지만, implicitly O(n) 의 공간이 사용된다.

⊙ Suffix trie 만들기
전체 suffix들의 길이는 string의 길이를 n이라 할때, O(n²)이다. 따라서, standard trie와 같은 방법으로 만들면 O(dn²)의 시간이 걸린다. 그러나 compact suffix trie는 O(n) 시간안에 만들어지지만, 복잡해서 여기에서는 다루지 않는다.

⊙ Using a Suffix Trie
arbitrary pattern matching을 지원하고, O(dm) 시간 걸린다.

1. Strings and Pattern Matching Algorithms
T : text (길이 n)
P : pattern (길이 m)

1) Brute Force Pattern Matching
: 가장 기초적인 방법. text의 처음부터 끝까지 alphabet 하나씩 옮겨가며 비교. 따라서, TC 는 O( (n-m+1)m ) = O(nm) => O(n^2)


2) The Boyer-Moore Algorithm
: P와 sizable fraction of T의 비교를 줄여준다.
Brute-Force 알고리즘은 unbounded alphabet에서도 사용 가능하지만, BM 알고리즘은 finite size에서만 가능하다.
=> alphabet이 moderately sized하고 pattern이 상대적으로 길 때 가장 빠르다.

(*) Two heuristics
1. Looking-Glass Heuristic : P의 제일 뒤부터 compare한다.
2. Character-Jump Heuristic : mismatch 일어나면 (T[i] = c),
pattern에서 'c' 포함하면 (역시 backward로 검사) 거기까지 pattern shifting,
pattern에 'c'가 없으면 그 다음까지 pattern 모~두 shifting
=> last occurrence function 만들어 사용.
(*) Last-Occurrence Function
L(c) = P[i]의 가장 큰 인덱스 i (pattern에 포함 안되면 -1)
Pattern을 뒤에서 앞으로 한 번 scan해야하고,
alphabet 전체도 한 번 scan해야하므로 (-1인 것 찾기)
last-Occurrence Function의 TC = O(m+s) // s는 alphabet size
(case1 은 last occurrence가 j를 pass 한 경우 그냥 한 칸만 shift 하는 것이다.)
worst-case : T = aaaa.....a, P = baaa....a 일 때.
O(nm + s) 가 된다. 거의, Brute-Force 알고리즘이랑 막상막하
그러나, English text와 같은 text에서는 skip이 많이 일어나서 효과적이다. experimental evidence로, 5 문자 pattern string에서는 비교가 0.24번 일어났다.
그리고, 이 것은 simplified된 BM 알고리즘이고, 실제는 다른 shift heuristic(KMP에서 아이디어)을 사용하여, running time은 O(n+m+s)이다.

3) The Knuth-Morris-Pratt Algorithm
: Brute-Force와 BM 알고리즘에서는, match가 실패하면, 그 전에 compare 했던 information을 다 버리고 from scratch로 알고리즘을 수행했다. 그러나 KMP 알고리즘에서는 전에 비교했던 정보를 다 이용하여, O(n+m)의 수행시간을 갖는다. 이것은, worst case에 text와 pattern 전 체를 최소 한 번 읽어들인다는 것이다. 그래서 left-to-right로 pattern을 text와 비교하지만, shift를 더 지능적으로 하기 때문에 Brute-Force 알고리즘 보다는 훨씬 효율적이다. (어떤 경우에서는 BM 보다 못하기 때문에, BM 보다 효율적이라 말할 수는 없다. )

KMP 알고리즘의 핵심은, Failure Function이다. f(j)는 P[1..j]의 suffix인 가장 긴 P의 prefix 길이이다. (convention으로, f(0) = 0 ) 이 Failure Function은 pattern 내에서 repeated substring을 "encodes" 해주기 때문에 매우 중요하다.

i never goes back!
(*) Performance 증명
failure function 계산시간 제외하면, KMP의 running time은 while-loop의 iteration 수에 비례한다. 분석을 위해서 k (= i-j)를 두어 T에서 pattern P가 shift된 total amount 라 하면, k<=n임을 알 수 있다. loop 실행중에는 다음 세 가지 경우 중 하나이다.
case 1: T[i] = P[j] -> i++, k는 그대로 (j++ 이므로)
case 2: T[i] =/= P[j] AND j>0 -> i는 그대로, k는 최대 1증가 (k가 i-j에서 i-f(j-1)이 되고, f(j-1) < j 이기 때문)
case 3: T[i] =/= P[j] AND j = 0 -> i++, k++ (j가 그대로임)
따라서, KMP에서 while-loop의 총 실행 수는 최대 2n 이다.
(*) KMP Failure Function 만들기
여기에 사용된 알고리즘은, KMPMatch 알고리즘과 비슷한, "bootstrapping" 프로세스이다. else if j>0 then 부분에서, f(j-1)을 사용하고 있는데, i>j 이기 때문에 f(j-1)은 항상 정의되어있다.

전체적으로, KMP 알고리즘의 running time = O(n+m) 이다.
(s에 영향을 받지 않는다. )

Chap 1. Database and Database Users

1.1 Introduction
▪ Database : a collection of related data
▪ Data : kwon facts (that can be recorded and have implicit meaning)
▪ Database의 implicit properties
① Miniworld 또는 UoD 를 반영.
② A logically coherent collection of data with some inherent meaning.
③ A specific purpose를 위해 설계, 구현됨.
▪ DBMS
: A collection of programs that enables users to create and maintain a DB.
(Defining, constructing, manipulating, sharing)
▪ Database system
: DBMS + Application Program + Stored DB + Stored DB Definition(Meta-Data)

1.2 An Example
▪ DB manipulation : querying & updating

1.3 Characteristics of the Database Approach
: 각 application마다 각각 따로 file을 만들어 관리해야 했던 file processing에 비해, 하나의 data repository만 유지하는 DB system approach가 훨씬 효율적이다.
① Self-Describing Nature of a Database System
DB system = DB 그 자체 + DB 구조와 제약에 대한 complete 정의나 설명.
catalog : meta-data (각 파일의 구조, 데이터 형, 제약 조건 등의 DB 정의)가 저장되어있다.
특정 DB에 있는 파일 구조를 알려면 catalog만 참조하면 되므로, DBMS software는 general-purpose로 만들 수 있다.
② Insulation between programs and data, and data abstraction
program-data independence : DBMS catalog에 저장된 data file의 구조와 access programs는 별개이다. => 데이터 구조 변경 =/=> 프로그램 변경
program-operation independence : 사용자는 operation이 어떻게 구현되었나 몰라도 사용 가능.
data abstraction : 위의 두 개를 가능하게 하는 것. Conceptual representation만 제공. (data model)
=> 사용자에게는 conceptual representation만 제공하고, DBMS가 필요하면 자세한 사항은 catalog에서 꺼내어 보고 file access.
③ Support of multiple views of the data
④ Sharing of data and multiuser transaction processing

1.4 Actors on the Scene
① Database Administrators
② Database Designers : 데이터 정의 및 저장 구조 설계
③ End Users
casual end user : DB 사용 빈도수 적지만 다양하고 복잡한 정보를 원함
naïve, parametric user : 정형화된 질의/갱신 작업 반복 (canned transactions)
sophisticated end user : 데이터의 복잡한 작업 수행
stand-alone user : 개인 데이터 베이스 사용자
④ System Analysts and Application Programmers (Software Engineers)

1.5 Workers behind the Scene
① DBMS system designers and implementers
② Tool developers
③ Operators and maintenance personnel

1.6 Advantages of Using the DBMS Approach
① Controlling Redundancy
▪ File processing : 모든 사용자 그룹은 각자 파일을 보관하고 있어서 같은 정보라도 여러 파일에 중복하여 보관됨.
=> redundancy 문제 발생. (duplication of effort, 저장공간 낭비, inconsistent)
▪ DB approach : redundancy 해결. (때로는 controlled redundancy 필요.)
② Restricting Unauthorized Access : security 보장.
③ Providing Persistent Storage for Program Objects
④ Providing Storage Structures for Efficient Query Processing
⑤ Providing Backup and Recovery : H/W, S/W 고장시에도 DBMS가 데이터 유지
⑥ Providing Multiple User Interfaces : 다양한 사용자 유형 및 숙련도 지원
⑦ Representing Complex Relationships among Data
⑧ Enforcing Integrity Constraints : semantics of DB (무결성 보장)
⑨ Permitting Inferencing and Actions Using Rules
⑩ Additional Implications of Using the Approach
▪ Potential for Enforcing Standards
▪ Reduced Application Development Time
▪ Flexibility
▪ Availability of Up-to-Date Information : concurrency control
▪ Economies of Scale : 중복투자, 데이터 관리 인력 감소

1.7 A Brief History of Database Applications

1.8 When Not to Use a DBMS
simple, well defined, not expected to change, real-time, no multiple user access

Chap 2. Database System Concepts and Architecture
2.1 Data Models, Schemas, and Instances
▪ data model : a collection of concepts that can be used to describe the structure of a database
▪ Categories of Data Models
① High-level (or conceptual) data model
DB 사용자가 이해하는 데이터베이스의 구조
entity, attribute, relationship으로 miniworld 표현
② Low-level (or physical) data model
데이터가 어떻게 컴퓨터에 저장되는지를 자세하게 설명하는 개념 제공
③ Representational (or implementation) data model
DBMS에서 사용하는 모델로, 위 두 데이터 모델의 중간 모델.
▪ Database Schemas (meta-data)
DB 설명. 대부분의 데이터 모델은 schema diagram을 가지고 있음.
▪ Instances : 저장된 데이터
▪ Database State : 특정 시점에서의 instances의 집합.

2.2 Three-Schema Architecture and Data Independence
2.2.1 The Three-Schema Architecture
▪ Internal schema : DB의 물리적 저장 구조 기술 ( physical data model 이용)
▪ Conceptual schema: DB구조 기술 ( conceptual, implementation data model이용)
▪ External schema : 사용자의 필요에 따라 DB 일부분 기술

2.2.2 Data Independence
① Logical data independence : external schemas나 응용 프로그램을 바꾸지 않고 conceptual schema 변경 가능.
② Physical data independence : conceptual schemas 바꾸지 않고 internal schema 변경 가능.

2.3 Database Languages and Interfaces
▪ Schema 정의 언어 : DDL(data), SDL(storage), VDL(view)
▪ 검색, 삽입, 삭제, 갱신 언어 : DML(data manipulation), SQL(structured query)
high-level DML : 내가 원하는 것을 표현한다.
low-level DML : 어떻게 가져올 지에 대해서도 표현한다.
▪ Host language : C, COBOL등 응용 프로그램이 사용하는 언어.
▪ DBMS Interfaces
: User-friendly, natural language, for parametric users, for DBA.

2.4 The Database System Environment
2.4.1 DBMS Component Modules
▪ Stored data manager : 디스크에 저장된 DBMS 정보에 대한 접근 제어
▪ DDL compiler : schema definition 처리, catalog에 저장.
▪ Runtime database processor : runtime에 DB에 접근하는 것을 다룸.
▪ Query compiler : interactive하게 들어오는 high-level query들을 다룸.
▪ Pre-compiler : host programming language로 적힌 응용 프로그램에서 DML 명령들을 뽑아낸다.

2.4.2 Database System Utilities
: loading, backup, file reorganization, performance monitoring
2.4.3 Tools, Application Environments, and Communications Facilities

2.5 Centralized and Client/Server Architectures for DBMSS

2.6 Classification of Database Management Systems
▪ Data model -> relational, network, hierarchical, object-oriented 등.
▪ Number of users -> single-user, multi-user systems
▪ Number of sites -> centralized, distributed DBMS
▪ 목적 -> general, special-purpose DBMS

[요구사항]
때는 바야흐로 22세기. 21세기에 유행하던 얼짱 신드롬이 사회 전반적으로 확산되고, 짱이 연예인의 유일한 등용문이 되면서, 이를 효과적으로 대처하기 위해 "짱 키우기 신개념 프로젝트"를 추진하기에 이르렀다. 당시 연예인 협회 회장이 된 데이터베이스 롸목 반장은, "짱 키우기 신개념 프로젝트"를 위해 얼짱 이회에 각종 짱들을 육성하고 이들을 관리하기 위하여 데이터베이스 시스템을 구축하기로 하였다. 각종 사이트를 통하여 다수의 추천을 받은 짱들은 주민등록번호와 이름을 기본적으로 등록하고, 각자의 재능에 따라 얼짱, 몸매짱, 노래짱이 될 수 있으며, 워낙 능력이 뛰어나 재능을 크게 인정 받은 짱들은 몇몇 분야(얼굴 또는 몸매 또는 노래)를 아우르는 짱이 될 수도 있다. 짱으로 인정을 받으면, 얼짱인 경우 코높이와 눈크기, 얼굴 비율을 등록해야 하고, 몸매짱인 경우는 키와 몸무게를, 노래짱인 경우는 성량과 음역대를 등록해야 한다.
모든 짱들은 자신을 좋아하는 팬들로 구성된 팬클럽을 여러 개 가질 숙 있으며, 한 짱에 소속된 팬클럽들은 그 팬클럽 이름으로 구별이 가능하고, 팬클럽 관리 차원에서 매년 팬클럽이 결성된 날 팬 캠프를 하기 위하여 비상 연락처로 팬클럽의 회장 이름과 연락처를 관리한다.
짱들은 등록된 연예기획사와 오디션을 통해서만 연예인으로 데뷔할 수 있으며, 오디션의 관리를 위하여 시행된 날짜와 응시 분야, 평가 점수를 기록하도록 한다. 한 명의 짱은 같은 날 같은 분야에 대해서 여러 연예기획사의 오디션을 볼 수도 있다. 오디션의 평가점수에 의해 등록된 연예기획사들로부터 지목된 짱들은 연예인으로써 하나의 등록된 연예기획사와 계약을 통해 연예인이 되는데, 이 때는 계약금과 계약 기간을 명시하도록 한다. 연예인이 되면, 코디와 매니저 및 연락처를 추가로 관리한다. 10명 이상의 연예인을 관리하는 연예기획사가 각 시/도별로 사업자 등록이 가능하며 등록 시에는 등록번호가 주어지고, 회사 주소와 대표이름을 관리하도록 한다.

1. 요구사항에서, entity, attribute, relationship을 분석해 보자.
짱 : 주민등록 번호, 이름
얼짱 : 코높이, 눈크기, 얼굴 비율
몸짱 : 키, 몸무게
노래짱 : 성량, 음역대
팬클럽 : 팬클럽 이름, (회장의 이름, 회장의 연락처)
연예기획사
등록 (연예인 10명 이상): 등록번호, 회사 주소, 대표이름.
=> 각 시/도 별로 등록이 가능하고 등록할 때 마다 등록번호가 주어지므로, multivalued attribute.
미등록 : x
오디션 : 시행된 날짜, 응시 분야, 평가 점수
=> 오디션은 연예기획사에서 주최하므로, 연예기획사를 owner entity로 하는 weak entity가 되어야 한다.
연예인 : 코디, 매니저, 연락처
=> 짱이 등록된 연예기획사와의 계약으로 연예인이 되므로,
짱을 owner entity로 하고, 계약을 owner relationship으로 하는 weak entity가 된다.

2. 애매하여 가정이 필요한 부분이 있는가?
(1) 연예기획사에 대하여.
10명 이상의 연예인이 있어야 등록이 가능하고, 짱들은 등록된 연예기획사의 오디션만 볼 수 있고, 오디션에 합격하면 계약하여 연예인이 될 수 있다. 이 등록된 연예기획사는 짱이 연예인이 되기 위한 유일한 등용문이기 전부터 연예인을 관리하여 등록된 기획사이며, 새로 생기는 기획사는 기존의 연예인을 10명 이상 다른 연예기획사로부터 스카웃 해와야 한다.
연예기획사는 기본적으로 회사 이름을 가지며, 같은 이름의 연예기획사가 두 개 이상 있을 수 없다.
(2) 오디션
오디션은 등록된 연예기획사만 주최할 수 있으며, 미등록 기획사는 주최할 수 없다. 왜냐하면, 짱들은 등록된 연예기획사에서만 오디션을 볼 수 있기 때문이다.
(3) 짱과 팬클럽
팬클럽을 가지지 않는 짱이 있을 수도 있다.

3. relationship을 뽑아내보자.
4. 모두 생략하고 걍 그려봤다.

1. 연예기획사 등록된 연예기획사와 미등록된 연예기획사로 나누는데,
미등록 연예기획사는 다른 기획사에 있는 연예인을 10명 이상 스카우트 해야만 등록이 가능하고,
등록 되기 전에는 DB에서 다루지 않는다.
2. 등록시의 문제로, 연예 기획사는 모두 다른 이름을 가지며, 이름과 대표이사 이름으로 관리한다.
3. 연예기획사는 시/도 별로 등록을 한 지사를 한 개 이상 가지고 있다.
각 지사는 회사 주소와 등록 번호로 관리되는데, 등록 번호로 지사를 identify할 수 있다.
4. 팬클럽을 가지지 않는 짱이 있을 수도 있다. 팬클럽은 한 짱에게 속하여 이름으로 구분된다.
5. 짱이더라도 오디션을 보지 않을 수도 있고, 등록된 연예기획사도 오디션을 주최하지 않을 수 있다.
6. 연예인은 오직 한 연예 기획사와만 계약을 할 수 있고, 짱은 꼭 얼짱, 몸짱, 노래짱 중에 하나 이상이다.
7. 오디션은 등록된 연예 기획사의 지사 아무 곳에서나 볼 수 있고,
그 기획사와의 계약은 모든 해당 회사의 모든 지사에서 유효하다.

<조교가 올려준 정답>

1. Logic Functions and Switches
⊙ Axioms of Boolean Algebra
1. B contains at least two elements, a, b, such that a≠b
2. Closure a,b in B,
(i) a + b in B
(ii) a •b in B
3. Commutative Laws: a,b in B,
(i) a + b = b + a
(ii) a •b = b •a
4. Associative Laws: a,b in B,
(i) (a + b) + c = a + (b + c) = a + b + c
(ii) (a • b) • c = a • (b • c) = a • b • c
5. Identities: 0, 1 in B
(i) a + 0 = a
(ii) a •1 = a
6. Distributive Laws:
(i) a + (b •c) = (a + b) •(a + c)
(ii) a •(b + c) = a • b + a •c
7. Complement:
(i) a + a' = 1
(ii) a •a' = 0

⊙ Thm : truth tabel로 표현되는 Boolean function은 Boolean Algebra로 표현될 수 있다.
⊙ NAND, NOR gate는 AND, OR 보다 더 효과적이라, 많이 사용되고, 어떤 Boolean expression도 NAND, NOR, NOT 만으로 구현될 수 있다. 사실, NOT 역시, NAND나 NOR의 input을 묶어 같이 넣어주면 구현가능하다.
⊙ Literal : Boolean expression 에서 한 문자는 하나의 literal 이며, 이는 나중에 wire 개수에 해당한다. literal이 적을 수록 wire가 적게 필요해서 좋다.
(예) Z = AB'C + A'B + A'BC' + B'C : 3 variables, 10 literals

⊙ XOR, XNOR. (내가 초반에 젤 헷갈렸던 것.)
XOR : X or Y but not both ("inequality", "difference")
XNOR : X and Y are the same ("equality", "coincidence")



2. Gate Logic
⊙ Duality : AND ↔ OR, 0s ↔ 1s, literal은 그대로.
► 참이 expression은, 그 dual도 참이다.
(앞의 Boolean Algebra의 Axiom에서 빠진 내용만 보자.)
Simplification Theorems:
9. X •Y + X •Y' = X 9D. (X + Y) • (X + Y') = X
10. X + X •Y = X 10D. X •(X + Y) = X
11. (X + Y') •Y = X •Y 11D. (X •Y') + Y = X + Y
DeMorgan's Law: AND ≡ NOR, OR ≡ NAND, AND/OR ≡ OR/AND
12. (X + Y + Z + ...)' = X' •Y' •Z' •... 12D. (X •Y •Z •...) ' = X' + Y' + Z' + ...
13. {F(X1,X2,...,Xn,0,1,+, •}' = {F(X1',X2',...,Xn',1,0, •,+)}
Duality:
14. (X + Y + Z + ...) = X •Y •Z •... 14D. (X •Y •Z •...) = X + Y + Z + ...
15. {F(X1,X2,...,Xn,0,1,+, •} = {F(X1,X2,...,Xn,1,0, •,+)}
Theorems for Multiplying and Factoring:
16. (X + Y) •(X' + Z) = X •Z + X' •Y
16D. X •Y + X' •Z = (X + Z) •(X' + Y)
Consensus Theorem:
17. (X •Y) + (Y •Z) + (X' •Z) = X •Y + X' •Z
17D. (X + Y) •(Y + Z) •(X' + Z) = (X + Y) •(X' + Z)


⊙ Truth table은 Boolean function의 unique signature이다. 따라서, expression은 여러가지일지라도, truth table은 하나이다.
► Canonical form : Boolean expression의 표준 형식.
(truth table을 그대로 boolean function으로 나타내면 된다.)
► Sum of Product form = minterm (1:A, 0:A')
F = [F 값이 1인 것들의 product를 sum]
F' = [F 값이 0인 것들의 product를 sum]
► Product of Sum = maxterm (1:A', 0:A)
F = [F 값이 0인 것들의 sum을 product]
F' = [F 값이 1인 것들의 sum을 product]




3. Two-Level Simplification
⊙ 여기에서의 핵심은, The Uniting Theorem 이다.
A(B'+B) = A
① Boolean Cubes : 4 demensions 이상은 그리기 힘들다.
② Karnaugh Map Method : ~6 demensions
③ CAD Tools : 6 demensions 이상.
(Quine-McCluskey Method)
④ Esspresso Method ( skip )

몇 가지 1장에 있던 내용을 정리해 본다.

◎ Combinational logic : no feedback among inputs and outputs
Sequential logic : inputs and outputs overlap

◎ Synchronous systems : clock에 의해서 signal이 변한다.
Asysnchronous systems : 아무 때나 입력이 주어지면 state 변한다.

◎ Multiple representation of a digital desing
① Switches

② Truth tables
③ Boolean Algebra
④ Gates

⑤ Waveforms
⑥ Blocks

⑦ Behaviors : 이건 안배운거고, 나머진 다 알지? ( '')

[시작 전에]
더 적은 components와 wires로 Boolean functions를 구현할 수 있는 좀 더 customizable 하고 복잡한 building block들을 배운다.
▪ Design with structured circuit implementation styles based on programmable array logic and memories.
PALs/PLAs, ROMs : general-purpose digital building blocks 만드는 데 유용하다.
(특정 함수를 구현하는데 customized되고, 더 적은 공간을 차지한다.)
PAL : programmable array logic
PLA : programmable logic array

▪ Design with logic building blocks that are different from traditional logic gates.
Switch Logic
Multiplexers/Selecters and Decoders : 종종 switch 처럼 truth table이나 logic gate보다 Boolean function을 보여주기 더 쉽다.
Tri-State Gates/Open Collector Gates : output이 항상 0이나 1이 아닌 logic들.

▪ Combinational Logic Design Problems
Seven Segment Display Decoder
Process Line Controller
Logical Function Unit
Barrel Shifter


1. Programmable Arrays of Logic Gates
(1) PALs and PLAs
Pre-fabricated building block of many AND/OR gates (or NOR, NAND) "Personalized" by making or breaking connectins among the gates
(*) Product term 을 공유하는 것이라 보면 된다.
F0 = A + B' C'
F1 = A C' + A B
F2 = B' C' + A B
F3 = B' C + A
⇒ A, B'C', AC', AB, B'C' 이렇게 5개의 term만 있으면 된다.




(2) PAL PLA 차이점
⊙ PLA : generalized topologies in AND and OR planes.
즉, AND, OR subarray가 디자이너가 원하는대로 personalized 될 수 있다.
((장점)) product term들 공유

⊙ PAL : implemented by Monolithic Memories.
AND array는 programmable 하지만, product term들간의 연결과 OR gate는 고정되어있다. OR gate로 들어가는 product term input은 2,4,8,16개로 제한되어있다.
((장점)) pre-defined hardwired connection을 사용하기 때문에 빠르다.

(3) Design Examples
◎ BCD-to-Gray-Code Converter
Gray-code : 1 bit 씩만 다른 코드들.
shared product term 없으므로, PAL이 적당하다!


◎ Two-bit Magnitude Comparator
shzred product term 2개 -> PLA 사용.

[시작 전에 ]
In general, multi-level implementations are more gate efficient than two-level implementations but have worse propagation delay.
Factored form 으로 바꾸면, 훨씬 적은 수의 gate와 wire로 회로를 구성할 수 있다. 그러나, level 이 증가하므로, 그에 따른 delay가 증가한다. (어디에나 있는, trade-off!)


1. Multi-level logic을 NAND/NAND 와 NOR/NOR로 바꿔보자.
DeMorgan's Law와 Pushing Bubbles 이용.
(1) DeMortan's Law
(A + B)' = A'B' -> A + B = (A'B')'
(AB)' = A'+B' -> AB = (A'+B')'



여기에서도 알 수 있듯이,
AND/OR 즉, Sum of Product 는 NAND/NAND 로,
OR/AND, Product of Sum 은 NOR/NOR 로 바꾸는 것이 쉽다.
왜냐하면, 이런 변환에서는 두 gate 사이에 buuble이 쑝쑝 들어가기만 하기 때문이다. 그러나, SOP를 NOR/NOR로, POS를 NAND/NAND로 바꾸려면, input 단자와 output 단자에도 bubble을 달아줘야하기 때문이다.

(*) 위의 그림은 two-level 이다. multi-level 에서는 다음을 주의한다.
1. Any internal signal wires that undergo an odd number of inversions must have an additional inverter inserted in the path.
2. NAND-only network로 변환하려면, odd levels에 AND gate를, even levels에 OR gate를 둔다.
3. NOR-only netwrok로 변환하려면, odd levels에 OR gate를, even levels에 AND gate를 둔다.

2. AND-OR-Invert Blok (AOI)
AOI function : AND, OR, Invert의 세 stage. 하나의 circuit block 으로 "packaged"된 multiple gate 이다. (OAI : OR-AND-Invert)

여기에서 stack은 AND의 개수.
AOI 의 장점은, 이 것을 하나의 gate로 count한다는 것!
Even if the use of the AOI blocks represents no savings in circuit area, the transition away from discrete logic offers a considerable advantage in reducing wiring complexity.


3. Multi-level Optimization (called synthesis)
(1) Factor out common sublogic (reduce fan-in, increase gate levels), subject to timing constraints
(2) Map factored form onto library of gates
(3) Minimize number of literals (correlates with number of wires)

(*) factored form : SOP의 연속이다. 즉, AND/OR/AND/OR/....
two-level expression들의 연속이라고도 할 수 있다.


① Decomposition
F = ABC + ABD + A'C'D' + B'C'D' (12 literals)
⇒ F = XY + X'Y' (4 literals)
X = AB
Y = C + D

② Extraction
F = (A+B)CD + E
G = (A+B)E'
H = CDE
⇒ F = XY + E
G = XE'
H = YE
X = A+B
Y = CD (A+B, CD 는 primary divisor 이다.- kernel, cube)

③ Factoring
F = AC + AC + BC + BD + E
⇒F = (A+B)(C+D) +E

④ Substitution
F = A + BC
G = A + B
⇒F = G(A+C)

⑤ Collapsing
F = G(A+C)
= (A+B)(A+C)
= AA + AC + AB + BC
= A + BC


4. Time Response in Combinational Networks
: 좋게 사용될 수도 있고, glitch처럼 부정확한 회로 오작동 유발도 한다.

Gate delay : input -> output 딜레이 시간
Rise time : output 이 low->high voltage로 변화는 시간
Fall time : output 이 high->low voltage로 변하는 시간

glitch : transient(일시적인) output changes.
-> A logic circuit is said to have a hazard if it has the potential for these glitches.

(1) Hazards/Glitches and How to Avoid Them
방법 : 신호가 stable할 때 까지 기다리기. 절~~~대 asynchronous input 사용은 안됨. hazard-free 회로 만들기

(2) Hazard의 종류
Static hazard : 2-level 회로에서. 한 번 glitch
Dynamic hazard : multi-level 회로에서. 두 번 이상 glitch

(3) Hazard free network 만들기 (two-level 에서)
When the initial and final inputs are covered by the sameprime implicant, no glitch is possible. But when the input change spans prime implicants, a glitch can happen.
A strategy for eliminating the hazard is to add redundant prime implicants to guarantee that all single-bit input changes are covered by one such implicant.
① static 1-hazard 제거
F의 SOP (1's 묶기. 1을 A로) 만들어서 여분의 implicant 추가.

② static 0-hazard 제거
F의 POS (0's 묶기. 0을 A로) 만들어서 여분의 implicant 추가.
⇒ ② 를 SOP로 바꾸면 ①과 같은 식이 나온다. 따라서, shorcut으로 다음과 같은 방법을 사용할 수 있다.
static 1-hazard free expression의 complement를 만들어서, 그것이 K-map에서 0's 를 다 cover 하는지 확인한다. (필요하면 add)

(4) Multilevel Networks에서 Static Hazard free 만들기
: transient output function (multi -> 2-level)으로 mapping 한다. 여기에서는 X와 X'는 독립적 변수이다. (XX'=0, X+X'=1 사용 못한다.) XX'는 static 0-hazards를, X+X'는 static 1-hazards를 일으킨다. 따라서, static 1-hazards를 제거할 때는, XX'를 고려할 필요가 없고, static 0-hazards를 제거할 때는 X+X'를 고려할 필요가 없다.
(예) F = ABC + (A+D)(A'+C')
F1 = ABC + AA' + AC' + A'C + C'D (transient output function)
F2 = AC' + A'D + C'D + AB + BD ( AA'는 1-hazards랑 무관, AB가 ABC cover)
F' = (ABC + (A+C)(A'+C'))'
= A'D' + AB'C
F3 = (A+D)(A'+B+C')(B+C'+D) // F'에 B'CD'추가.

F3을 SOP로 바꾸면 F2가 나온다. 따라서, 둘 다 static 0-과 1-hazards에 free 하다.

(5) 결론, static-hazard-free circuits 디자인 방법!
: transient output function이 K-map 에서 인접한 모든 1을 커버하는 term을 가지게 하고, term이 A와 A'를 모두 가질 수는 없게 한다. 즉, AA' 이런 term 은 안된다.