---
# System prepended metadata

title: Introduction of Computer Science<br>Ch14 & Ch15
tags: [必修, Introduction of Computer Sciencce, NTNU, CSIE]

---

# Introduction of Computer Science<br>Ch14 & Ch15
NTNU 計算機概論

##### [Back to Note Overview](https://reurl.cc/XXeYaE)
##### [Back to Introduction of Computer Science](https://hackmd.io/@NTNUCSIE112/SyU5Uuyhr)
{%hackmd @NTNUCSIE112/csabb %}
{%hackmd @NTNUCSIE112/csch %}
<!--
https://hackmd.io/@sophie8909/csabb
https://hackmd.io/@sophie8909/csch
-->
###### tags: `NTNU` `CSIE` `必修`  `Introduction of Computer Sciencce`
# Ch14 Databases
## 14-1 Introduction<!---->
A database is a collection of related, logically coherent data used by the application programs in an organization.

- Database system application
	- Bank
	- School
	- etc.
- the method to build database system
	- using programming language
	- using specialized database software (e.g. Microsoft Access)

### Database Management Systems(DBMS)
```graphviz
digraph hierarhcy 
{
	nodesep=1.0
	node[color = pink, fontname=Courier,shape=box]
	edge [color=black,style=line]
	user->Application->DBMS
    "Database Manager"->DBMS->{Database1 Database2 Database3}
    
    
}
```
```graphviz
digraph hierarhcy 
{
	nodesep=1.0
	node[color = pink, fontname=Courier,shape=box]
	edge [color=black,style=line]
	DBMS->{Hardware Softare Data Users Procedures}
      
}
```
---
## 14-2 Database Architecture

### ANSI/SPARC structure
```graphviz
digraph hierarhcy 
{
	nodesep=1.0
	node[color = pink,                     fontname=Courier,shape=box]
	edge [color=black,style=line]

	{" user view" "user view" "user view "}->"External level" 
	"External level"->"conceptual level"->"Internal level"
	"External level" 
}
```

+ **External level**
    interacts directly with the user.(what the user see)
+ **Conceptual level**
    defines the logical view of data. (connection between internal and external)
+ **Internal level**
    determines where data are actually stored.
---
## 14-3 Database models
+ A database model defines the logical design of data.
+ The model also describes the relationship between different parts of data.
+ Three models:
     + Hierarchical model： obsolete
     + Network model： obsolete
     + Relational model：widely used today

### Hierarchical model
- Data are organized as an upside down tree.
- Each entity has only one parent but can have several children.
- Advantage：easy to insert and delete structure
- Disadvantage：delete parent node will both delete child nodes
- Examples：IBM's IMS and DL/1
- ![](https://i.imgur.com/qxCdwCc.png)


### Network model
- The entities are organized in a graph, where some entities can be accessed through several path.
- Advantage：variability
- Disadvantage：complex
- Examples：HP's IMAGE and Honeywell's IDS
- ![](https://i.imgur.com/2lf2uAA.png)
---
## 14-4 Relationship model
- ![](https://i.imgur.com/sDYI0O6.png)
-  Data are organized in two-dimensional tables called relations(關係).
 
 
    | Attributes |       v       |   v    |        |
    |:----------:|:-------------:|:------:|:------:|
    |     No     |  Course-Name  |  Unit  |        | 
    |  -------   |    -------    | ------ | Tuples |
    |   CIS17    | Intro to java |   5    | **<-** |
    |   CIS15    |  Intro to C   |   5    | **<-** |
    |   CIS19    |     Unix      |   4    | **<-** |
    |   CIS51    |  Networking   |   5    | **<-** |
<!-- 這樣是對的ㄇ -->
- The number of **attributes** in a relation is its **degree**
- The number of **rows** in a relation is its **cardinality**
- Advantage：Suitable for expressing more complex relationships
- Disadvantage：This structure is inefficient when the number of random queries is small
- Relational database is using widest
    - e.g. Microsoft SQL Server, Sybase, Informix, MySQL, PostgreSQL, Dbase III Plus, Microsoft Access
---
## 14-5 Operations on relations
+ Select : unary operation
+ Insert : unary operation
+ Delete : unary operation
+ Update : unary operation
+ Project : unary operation
    + 選取一關係圖中特定幾項元素顯示
<br>
+ Join : binary operation
    + ![](https://i.imgur.com/csNPpWw.png)加入額外元素成為新關係圖
+ Union : binary operation
    + ![](https://i.imgur.com/Af6n2gX.png)取兩關係圖間的聯集

+ Intersection : binary operation
    + ![](https://i.imgur.com/xa1jOb8.png)取兩關係圖間的交集
+ Difference : binary operation
    + ![](https://i.imgur.com/rrCybv0.png)A關係圖多餘B關係圖之元素

### SQL(Standard Query Language)

SQL is the language standardized by ANSI and ISO for use on relation database

SQL語言可以分為三個部分：
1. Data Definition Language（DDL）:可用來建立新的或刪除已有的表格
2. Data Manipulation Language（DML）:可用來對已有的表格進行新增,刪除,存取......等
3. Data Control Language（DCL）:可用來控制資料存取的權限
4. Online SQL Test：[SQL Tryit Editor](https://www.w3schools.com/sql/trysql.asp?filename=trysql_op_in)
5. SQL Library：[Microsoft SQL](https://docs.microsoft.com/zh-tw/sql/sql-server/?view=sql-server-ver15)

(以下示範左邊為原表格，右邊為經過指令修改/後顯示的東西)
#### Data Definition Language
- Create table
	```SQL=
	CREATE TABLE member
	(
	member_id 	CHAR(8),
	person_id	CHAR(10),
	name		VARCHAR(8),
	birtday		DATE,
	)
#### Data Manipulation Language
- Select Operation
	```SQL=
	SELECT * --SQL指令大寫 註解用--
	FROM relation_name
	WHERE criteria
	```
    - COURSES
    
        |  No   |  Course-Name  | Unit |        |  Course-Name  | Unit |
        |:-----:|:-------------:|:----:|:------:|:-------------:|:----:|
        | CIS17 | Intro to java |  5   |   ->   | Intro to java |  5   |
        | CIS15 |  Intro to C   |  5   | select |  Intro to C   |  5   |
        | CIS19 |     Unix      |  4   |   ->   |     Unix      |  4   |
        | CIS51 |  Networking   |  5   |        |  Networking   |  5   |

- Insert Operation
	```SQL=
	INSERT INTO relation_name
	VALUES (xx,xx,xx)
	```
    - COURSES   
    
        |  No   |  Course-Name  | Unit |        |    No     |  Course-Name  | Unit  |
        |:-----:|:-------------:|:----:|:------:|:---------:|:-------------:|:-----:|
        | CIS17 | Intro to java |  5   |   ->   |   CIS17   | Intro to java |   5   |
        | CIS15 |  Intro to C   |  5   | insert |   CIS15   |  Intro to C   |   5   |
        | CIS19 |     Unix      |  4   |   ->   |   CIS19   |     Unix      |   4   |
        | CIS51 |  Networking   |  5   |        |   CIS51   |  Networking   |   5   |
        |       |               |      |        | **CIS52** |  **TCP/IP**   | **6** |

- Delete Operation
	```SQL=
	DELETE FROM relation_name
	WHERE criteria
	```
    - COURSES
    
        |    No    |  Course-Name   | Unit  |        |  No   |  Course-Name  | Unit |
        |:--------:|:--------------:|:-----:|:------:|:-----:|:-------------:|:----:|
        |  CIS15   |   Intro to C   |   5   |        | CIS15 |  Intro to C   |  5   |
        |  CIS17   | Intro to java  |   5   |   ->   | CIS17 | Intro to java |  5   |
        |  CIS19   |      Unix      |   4   | delete | CIS51 |  Networking   |  5   |
        | **CIS5** | **Networking** | **5** |   ->   | CIS52 |    TCP/IP     |  6   |
        |  CIS52   |     TCP/IP     |   6   |        |       |               |      |

- Update Operation
	```SQL=
	UPDATA relation_name
	SET attribute1 = value1, attribute2 = value2...
	WHERE criteria
	``` 
    - COURSES
    
        |  No   |  Course-Name  | Unit |        |  No   |  Course-Name  | Unit |
        |:-----:|:-------------:|:----:|:------:|:-----:|:-------------:|:----:|
        | CIS15 |  Intro to C   |  5   |        | CIS15 |  Intro to C   |  5   |
        | CIS17 | Intro to java |  5   |   ->   | CIS17 | Intro to java |  5   |
        | CIS19 |     Unix      |  4   | update | CIS19 |     Unix      |  4   |
        | CIS51 |  Networking   |  5   |   ->   | CIS51 |  Networking   |  **6**  |
        | CIS52 |    TCP/IP     |  6   |        | CIS52 |    TCP/IP     |  6   |

- Project Operation
	```SQL=
	SELECT attribute_list
	FROM relation_name
	```
    - COURSES
    
        |  No   |  Course-Name  | Unit |         |  No   | Unit |
        |:-----:|:-------------:|:----:|:-------:|:-----:|:----:|
        | CIS15 |  Intro to C   |  5   |         | CIS15 |  5   |
        | CIS17 | Intro to java |  5   |   ->    | CIS17 |  5   |
        | CIS19 |     Unix      |  4   | project | CIS19 |  4   |
        | CIS51 |  Networking   |  5   |   ->    | CIS51 |  5   |
        | CIS52 |    TCP/IP     |  6   |         | CIS52 |  6   |

- Join Operation
	```SQL=
	SELECT attribute_list
	FROM relation1, relation2 
	WHERE criteria
	```
    - join
        - COURSES　　　　　　　　　　　　　　　

            |  No   |  Course-Name  | Unit |
            |:-----:|:-------------:|:----:|
            | CIS15 |  Intro to C   |  5   |
            | CIS17 | Intro to java |  5   |
            | CIS19 |     Unix      |  4   |
            | CIS51 |  Networking   |  5   |
            | CIS52 |    TCP/IP     |  6   |

        - TAUGHT-BY

            |  No   | Professor |
            |:-----:|:---------:| 
            | CIS15 |    Lee    | 
            | CIS17 |    Lu     |
            | CIS19 |  Walter   |
            | CIS51 |    Lu     |
            | CIS52 |    Lee    |
    - Result

        |  No   |  Course-Name  | Unit | Professor |
        |:-----:|:-------------:|:----:|:---------:|
        | CIS15 |  Intro to C   |  5   |    Lee    |
        | CIS17 | Intro to java |  5   |    Lu     |
        | CIS19 |     Unix      |  4   |  Walter   |
        | CIS51 |  Networking   |  5   |    Lu     |
        | CIS52 |    TCP/IP     |  6   |    Lee    | 

- Union Operation
	```SQL=
	SELECT *
	FROM relation1
	UNION
	SELECT *
	FROM relation2
	```
    - Union
        - CIS15-Roster　　
    　　　　　　　　　　　　　
            |  StudentID  | F-Name | L-Name | 
            |:-----------:|:------:|:------:|
            | 145-67-6754 |  John  | Brown  | 
            | 232-56-5690 | George | Yellow | 
            | 245-89-6580 |  Anne  | Green  | 
            | 459-98-6789 |  Ted   | Purple | 
        
        - CIS52-Roster　
        
            |  StudentID  | F-Name | L-Name |
            |:-----------:|:------:|:------:|
            | 145-67-6754 |  John  | Brown  |
            | 232-56-5690 | George | Yellow |
            | 342-88-9999 |  Rich  | White  |
        
    - Result
    
        |  StudentID  | F-Name | L-Name |
        |:-----------:|:------:|:------:|
        | 145-67-6754 |  John  | Brown  | 
        | 232-56-5690 | George | Yellow |
        | 245-89-6580 |  Anne  | Green  | 
        | 459-98-6789 |  Ted   | Purple |
        | 342-88-9999 |  Rich  | White  |

- Intersection operation
    ```SQL=
    SELECT*
    FROM relation1
    INTERSECT
    SELECT*
    FROM relation2
    ```
    - Intersection
        - CIS15-Roster
    
            |  StudentID  | F-Name | L-Name |
            |:-----------:|:------:|:------:|
            | 145-67-6754 |  John  | Brown  |
            | 232-56-5690 | George | Yellow |
            | 245-89-6580 |  Anne  | Green  |
            | 459-98-6789 |  Ted   | Purple |
        - CIS52-Roster

            |  StudentID  | F-Name | L-Name | 
            |:-----------:|:------:|:------:| 
            | 145-67-6754 |  John  | Brown  |
            | 232-56-5690 | George | Yellow |
            | 342-88-9999 |  Rich  | White  |
    - **Result**

         |  StudentID  | F-Name | L-Name |
         |:-----------:|:------:|:------:|
         | 145-67-6754 |  John  | Brown  |
         | 232-56-5690 | George | Yellow |





- Different Operation
	```SQL=
	SELECT *
	FROM relation1
	MINUS
	SELECT *
	FROM relation2
	```
    - Different
        - CIS15-Roster
            |  StudentID  | F-Name | L-Name |
            |:-----------:|:------:|:------:|
            | 145-67-6754 |  John  | Brown  |
            | 232-56-5690 | George | Yellow |
            | 342-88-9999 |  Rich  | White  |
        
        - CIS52-Roster　
            |  StudentID  | F-Name | L-Name |
            |:-----------:|:------:|:------:|
            | 145-67-6754 |  John  | Brown  |
            | 232-56-5690 | George | Yellow |
            | 245-89-6580 |  Anne  | Green  |
            | 459-98-6789 |  Ted   | Purple |
    - Result
        |  StudentID  | F-Name | L-Name |
        |:-----------:|:------:|:------:|
        | 245-89-6580 |  Anne  | Green  | 
        | 459-98-6789 |  Ted   | Purple |
---
## 14-6 Database Design
```graphviz
digraph{
nodesep=1
	node[color = pink, fontname=Courier,shape=box]
	edge [color=pink,style=line]
    了解顧客需求->邏輯資料設計->實體資料設計->建立資料庫
}
```
### Entity-Relationship Diagram(E-R)
```graphviz
digraph{
	nodesep=1
	node[color = pink, fontname=Courier,shape=box]
	edge [color=pink]
	
    
    
    {
    No, Name, Unit
    }->Course
	{
    s_id[flag=ID] 
	s_name[flag=Name]
	s_add[flag=Address]
    }->Student  
	
	{
	p_id[flag=ID]
	p_name[flag=Name]
	p_add[flag=Address]
	node[shape=diamond]
    }->Professor
    Student->takes->Professor
	
	Course->teaches->Professor

}
```
### Normalization
Normalization is the process by which a given set of relation are transformed to a new set of relations with a more solid structure.
- First normal form (1NF)
    - 避免資料表上有多筆資料的情況
    - 分割放置在不同row
- Second normal form (2NF)
    - 某欄位只與Primary Key 的部分有相依性
    - 拆解出來建一個新表
- Also having 3NF, 4NF...
---
## 14-7 Other Database Models

- 分段式資料庫
    - 片段分散式資料庫(fragmented distributed database)<br>
        資料局部分散在各電腦，每部電腦維護部分資料庫。
    - 複製分散式資料庫(replicated distributed database)<br>
        一部電腦擁有另一部電腦精確複製的資料，儲存於某一部電腦資料所駔的修改，會確切的在其他電腦重複該動作。
- 物件導向資料庫(object-oriented database)
    - 例：Jasmine、Alltalk、GemStone、O2
---
# Ch15 Data Compression
## 15-1 Introduction
### Objectivese
- Realize the need for data compression
- Differentiate between lossless and lossy compression
- Understand three lossless compression encoding techniques
    - run-length
    - Huffman
    - Lempel Ziv
- Understand two lossy compression methods
    - JPEG
    - MPEG
- Understand the main idea behind the MP3 standard for compressing audio

### Data compression methods
- Data compression methods are either lossless(all information is recoverable) or lossy(some information is lost)
- Data compression takes the original message and reduces the number of bits that are to be transmitted
## 15-2 Lossless Compression Methods
### Run-length encoding
- replace consecutive repeating occurrences of a symbol by number of occurrences
- AAAAAABBBBBB -> A6B6
- for two symbols
	- encode one symbol which is more frequent than the other 
	- This example only encode 0 between 1
	- {00001|0100} {0001|0011}{1|0000} {0001|0011}


### Huffman encoding
- Frequency ↑ bits ↓ (fewer bits represent for the letter with higher frequency)
- Optimization Algorithm
- 二元樹避免歧異

### Morse Code
- 1836 built by Samuel F.B. Morse
- 1838 Morse improve Telegraph receiver
- 1844 The USA built 60km
- 1949 G.K. Zipf 統計每一英文字母出現的頻率
- 缺點：
    - 良好的壓縮率
    - 太慢，讀取二次才可編碼
        - 第一次統計各符號的數量
        - 第二次對訊息編碼
        - LZ解決問題
### Lempel Ziv encoding
- Dictionary-based encoding
- GIF and TIFF using this
- One parsed

## 15-3 Lossy Cpmpression Methods
### Format
#### GIF
- Compression：Lempel Ziv
- 優點：
    - 可有效節省壓縮空間，提高壓縮比例
    - 支援動畫(將多幅的圖案合為一個GIF檔案後依序顯示)
- 缺點：僅支援256色
#### TIFF
- Compression：LZ, Huffman Coding, Run Length Encoding
- 色彩：
    - 單色
    - 灰階
    - 全彩

#### PCX影像壓縮技術
- 以Run Length Encoding 作為壓縮的核心技術
- 優點：演算法簡單、易懂且易實作
- 缺點：壓縮率會隨著影像複雜度的不同而有所改變。遇到重複性低的影像資料，PCX處理後的影像空間有時反而會不減反增
#### JPEG
- 由ISO及CCITT在1991年發表
- JPEG為一種有損影像壓縮法，解壓縮後無法完全恢復為原始影像
- JPEG壓縮效果比較好，成為現今最常用的影像壓縮法之一
- 壓縮全彩或是8位元的灰階影像
- Compression：[DCT](####DCT)
<br>(過程詳情請見講義)


### Animation and Video
#### MPEG
- [I-frames](####I-frames)
- [P-frames](####P-frames)
- [B-frames](####B-frames)
### Audio
#### MP3
- 1987由德國Fraunhofer與Erlangen大學共同制定的數位聲音壓縮演算法
- MP3是MPEG影音壓縮演算法中針對聲音部分所制定的演算法標準
- 原理：為降低聲音失真度，MP3利用人耳聽覺的特性，去除掉人耳聽不到的過高或過低的頻率，大幅減少儲存空間

#### 聲音檔比較
| 格式 |         簡介         |   優點   |      缺點      |example|
|:----:|:--------------------:|:--------:|:--------------:|:-:|
| WAV  |  從CD或直接錄音而來  | 原音呈現 |     占空間     |44.1kHz 16bits <br>單聲道取樣<br>22675KB 263秒|
| MP3  | 聲音檔的壓縮格式之一 | 壓縮率高 | 某種程度的失真 | 24kHz 16bits <br>單聲道取樣<br>1029KB 263秒|


### Compression Methods
#### DCT
- F(i,j)
- Uniform Gray Scale
    - Case 1: Uniform gray scale
    - Case 2: Two sections
- Gradient Gray Scale
    - Case 3: 
- Quantization & Compression 
- Reading the table
#### I-frames
- It is an **independent frame** that is not related to any other frame.
    - JPEG encoding
- They are presented at regular intervals.
    - 12~15 images having 1 I-frame 
#### P-frames
- Motion compensation can be predicted from the previous I-frame and P-frame changes
- MPEG:Motion compensation
- only saving different part
#### B-frames