CSIE - Database

Chapter 1 Introduction

資料庫的四種語言

• 資料庫的四種語言

DML

• Data Manipulation Language 資料操作語言
• 提供從數據庫中查詢信息以及將元組插入、刪除和修改數據庫中的元組的能力
• 常見指令: Insert、Update、Delete

DDL

• Data Definition Language 資料定義語言
• 用來定義資料庫、資料表、檢視表、索引、預存程序、觸發程序、函數等資料庫物件
  1. 每個 relation 的 schema
  2. 每個 attribute 的關聯值類型
  3. Integrity 的規範
  4. relation 的各種維護索引集
  5. 每個 relation 的安全與授權資訊
  6. 每個 relation 的實體儲存結構
• 可以用來建立、更新、刪除 table, schema, domain, index, view
• 常見指令: Create、Alter、Drop

DCL

• Data Control Language 資料控制語言
• 用來控制資料表、檢視表之存取權限，提供資料庫的安全性
• 常見指令: Grant(賦予使用者使用權限)、Revoke(取消使用者的使用權限)、Commit(完成交易作業)、Rollback(交易作業異常，將已變動的資料回復到交易開始的狀態)

DQL

• Data Query Language 資料查詢語言
• 負責進行資料查詢，不會對資料本身進行修改的語句
• 常見指令: Select
  • 輔助指令: From、Where、Group by、Order by

Referential integrity 參考完整性

• Referential integrity
• tables 之間的 relationship，確保在一個 relation 中出現的給定 attribute set 的值也出現在另一個 relation 中的特定屬性集
  • 每個 table 一定有 Primary key，這個 Primary key 可以透過 table 之間的 relationship 在其他 table 出現(此時此 Primary key 在該引用他的表內被稱為 Foreign key)
  • 當刪除包含 Primary key 的 row 或使用不同的 Primary key 更新它時，會破壞包含該值作為 Foreign key 的任何 row 的含義
  • Referential Integrity 是 Foriegn key對 Primary key 的邏輯依賴。
  • 包含 Foreign key 的 row 的 Integrity 取決於它引用的 row 的 Integrity(包含匹配 Primary key 的 row)

ACID

• ACID 是什麼

• 資料庫管理系統（DBMS）在寫入或更新資料的過程中，為保證交易（transaction）是正確可靠的，所必須具備的四個特性:
  1. atomicity 不可分割性: transaction 裡面的操作要馬全部成功，要馬全部失敗。這點蠻理所當然的，就像剛剛的舉例，如果 1. 成功 2. 不成功就會憑空多錢
  2. consistency 一致性: 不同的數據都會有一些基本的約束，而這些約束在交易前跟交易後都必須要遵守，如果沒辦法遵守交易就必須失敗，聽起來很抽象，舉剛剛的匯款的舉例，匯款有一些基本的限制：
     1. 雙方的錢都不能小於 0
     2. 雙方錢的總和不能改變
     • 上面兩個限制在交易前跟交易後都必須要遵守，這就是一致性
  3. isolation 獨立性: 多個 transaction 不會互相干擾，不能修改到同一個值
  4. durability 持久性: 事務處理結束後，對數據的修改就是永久的，即便系統故障也不會丟失

Chapter 2 Key & Relation Algera

Keys

• Key 鍵

• Super key Candidate key Primary key、Alternate key Foreign key

Superkey

• Superkey: Superkey 是關聯表 Schema 的單一屬性或屬值的集合，但 Superkey 需滿足「唯一性」
  • ID、ID.name..

    唯一性(Uniqueness)：在關聯表中絕不會有兩個值組擁有相同的值

• Superkey K is a candidate key if K is minimal
• Super Keys(超鍵)：包含Candidate Key(候選鍵)、Primary Key(主鍵)、Alternate Keys(替代鍵)、Foreign Keys(外來鍵)
• 超鍵可能有很多

Candidate key

• Candidate Keys 是一個超鍵，在每一個關聯表至少擁有一個候選鍵，不只要滿足唯一性，還需要滿足最小性

  最小性(Minimality)：最小數性數的超鍵。即在超鍵中沒有一個屬性可以刪除，否則將違反性一性

• 候選鍵也能是多個屬性的集合
• Candidate Keys：包含Primary Key(主鍵)、Alternate Keys(替代鍵)

Primary key

• 是候選鍵的其中一個，而且只能有一個
  1. 不可有空值(Not Null)
  2. 永遠不會改變(Never Change)

     例如身份證字號不會變

  3. 非識別值(Nonidentifying Value)

     「值」本身沒有意義
     例如買電子產品都會有一個「序號」，假設第一碼代表供應商麼，第二碼代表所在地區(台北、台中…)，有一天供應商搬家了，從台北搬到台中，那第二碼就不會符合現況。

  4. 簡短且簡單的值(Brevity and Simplicity)

     資料庫通常會使用主鍵建立索引資料，主鍵越短，能節省空間，更能加快資料查詢。所以儘量選單一屬性候選鍵

• Primary Key 與 Alternate Keys 可能包含 Foreign Key

Alternate key

• 在候選鍵中不是主鍵的其他候選鍵都是替代鍵

Foreign key

• 關聯表的單一或多個屬性的集合，它的屬性值是參考其他關聯表的主鍵

  A個人資料表(身份證字號, 姓, 名, 性別, 出生, 連絡電話)
  B員工資料表(員工編號, 身份證字號, 抬頭, 部門, 電子郵件, 分機)

• B.身份證字號是從A.身份證字號而來，所以在B關聯表的身份證字號稱「外來鍵」。以圖來看是這樣
  
  圖片來源
• 外來鍵一定參考其他關聯表的主鍵
• 外來鍵在關聯表內不一定是主鍵
• 外來鍵(Employee.PID)與參考的主鍵(Person.PID)屬於相同定義域。即Employee.PID的值應該都包含在Person.PID之中(或子集)
• 外來鍵(Employee.PID)與參考的主鍵(Person.PID)，如果是單一屬性，那外來鍵就是單一屬性，如果是複合屬性，那外來鍵就是複合屬性
• 外來鍵可以參考同一關聯表的主鍵

最重要的 key

• 以上最重要的Key是主鍵與外來鍵，通常整個關聯表都是由主鍵與外來鍵所來建構而成

Relational Algebra

Select Operation

• 限制(Restrict)
• 指從資料表中，只抓取符合條件的資料。例如 : 從學生資料表抓取系編號大於2的資料
• 
  

Project

• 投影(Project)
• 指從資料表中，只抓取部分欄位的資料。例如 : 從學生資料表只抓取姓名的資料。
• 
  

Cartesian Product

• 卡氏積 (Cartesian Product)
• 指兩個資料表相乘。例如 :
• 
  

Join

• 合併(Join)
• 是指將兩關聯表 R 與 S 依合併條件合併成一個新的關聯表R3，假設P為合併條件，以 表示此合併運算。
• 
  
  

Union

• 聯集(Union)
• 是指兩個資料表全部取出，但是重複的只出現一次。例如 : 聯集兩個學生資料表
• S T
  

Intersection

• 交集
• S T
  

Difference

• 差集(Difference)
• 取得在 S 但不在 T 中的元素
• 
  

Rename

• The RENAME operation is used to rename the output of a relation.
• 選擇 S 中 d 最大的數字
• 
  

Equivalent

• 兩種寫法表達的意義是一樣的

Chapter 3 SQL

Create

1
2
3
4
5
6

CREATE TABLE customers (
  C_Id INT,
  Name varchar(50),
  Address varchar(255),
  Phone varchar(20)
);

圖片來源

• with key

  1 2 3 4 5 6 7

  create table instructor ( ID char(5), name varchar(20) not null, dept_name varchar(20), salary numeric(8,2), primary key (ID), foreign key (dept_name) references department);

Update

Insert Into

• Insert Into: INSERT INTO 是用來新增資料至某資料表 (table)
  • INSERT INTO table_name VALUES (value1, value2, value3...);

Delete From

• Delete From: DELETE FROM 是用來刪除資料表中的資料
  • DELETE FROM table_name WHERE column_name operator value;

    WHERE 條件式記得要加哦！不然 “全部的” 資料都會刪除了

• 一次刪除資料表中所有的資料
  • DELETE FROM table_name;
  • DELETE * FROM table_name;

Drop Table

• 我們可以用 DROP TABLE / TRUNCATE TABLE / DROP DATABASE 來刪除資料表或資料庫
• 刪除資料表 (DROP TABLE): 完全刪除整個資料表
  • DROP TABLE table_name;
• 僅刪除資料表內容，但保留結構 (TRUNCATE TABLE): 資料表還在，只是資料清空了
  • TRUNCATE TABLE table_name;
• 刪除資料庫 (DROP DATABASE):
  • DROP DATABASE database_name;

Alter

• Alter: ALTER TABLE 是用來對已存在的資料表結構作更改。語法型式如下:

  1	ALTER TABLE table_name ...;

  
  圖片來源
• 增加欄位 (ADD COLUMN): ALTER TABLE table_name ADD column_name datatype;
• 更改欄位資料型別 (ALTER COLUMN TYPE): ALTER TABLE table_name ALTER COLUMN column_name datatype;
• 刪除欄位 (DROP COLUMN): ALTER TABLE table_name DROP COLUMN column_name;

Query

1
2
3

select A1, A2, ..., An
from r1, r2, ..., rm
where P

• Select: 要 “拿什麼” 資料
• From: “從哪拿”
• Where: 取出 “符合條件” 的紀錄值
  • 可以搭配 and、or…

Null Value

• 設 true = 1、unknown = 0.5、false = 0
• and: 取最小
  • ex: true and unknown = unknown
• or: 取最大
  • ex: true or unknown = true

Aggregate Function 聚合函數

• avg、min、max、sum、count
• group by: 將查詢結果中特定欄位值相同的資料分為若干個群組，而每一個群組都會傳回一個資料列
  
  圖片來源

  1 2	SELECT Customer, SUM(Price) FROM orders GROUP BY Customer;

  
  圖片來源

  它將 Customer 欄位值相同的資料都分作同一組來計算 (加總)
  若 GROUP BY 後面指定兩個以上的欄位時，則要符合所有欄位值皆相同資料才會被分為一組

• having: 用來取代 WHERE 搭配聚合函數 (aggregate function) 進行條件查詢，因為 WHERE 不能與聚合函數一起使用
  
  圖片來源

  1 2 3

  SELECT Customer, SUM(Price) FROM orders GROUP BY Customer HAVING SUM(Price)<1000;

  
  圖片來源
• exists: EXISTS 運算子可以連接子查詢，用來判斷子查詢是否有返回的結果
  • 我們以 IN 運算子來與 EXISTS 作一比較，下列兩個 SQL 查詢皆會返回同樣的結果：

    1 2 3

    SELECT * FROM table_a WHERE EXISTS (SELECT * FROM table_b WHERE table_b.id=table_a.id);

  • 相當於

    1 2 3

    SELECT * FROM table_a WHERE id in (SELECT id FROM table_b);

• unique: UNIQUE 用來保證欄位在資料表中的唯一性，約束資料表中的欄位不能有重複的資料
• update: 修改資料表中的資料我們就會需要用到 UPDATE
  
  圖片來源

  1	UPDATE customers SET Phone='03-87654321' WHERE Name='王二';

  
  圖片來源

Chapter 4 Intermediate SQL

Inner Join & Outer Join

• Inner Join: 只有那些滿足匹配條件的 tuples，其餘被排除
  1. Theta join
  2. Equi join
  3. Natural join
• Outer Join
  1. Left Outer Join
  2. Right Outer Join
  3. Full Outer Join

Inner Join

Theta Join

• θ-合併(Theta Join): It is a general case of Join. And it is used when we want to join two or more relation based on some conditions

Equi Join

• 對等合併(Equi-Join)：是θ-合併的特例 (條件是等號時)

Natural Join

• 自然合併(Natural Join): 兩資料表之間同名的欄位會被自動結合在一起
  
  圖片來源
  • Natural join

    1 2 3

    SELECT table_column1, table_column2... FROM table_name1 NATURAL JOIN table_name2;

  • 效果等同於 Inner join 寫法

    1 2 3 4

    SELECT customers.Name, orders.Order_No FROM customers INNER JOIN orders ON customers.C_Id=orders.C_Id;

  • On 相當於 Where

    1 2 3

    SELECT * FROM student JOIN takes ON student_ID = takes_ID

  • 效果等同於

    1 2 3

    SELECT * FROM student , takes WHERE student_ID = takes_ID

    
    圖片來源
• 危險: 不相干但有著相同名稱的屬性可能會被連接起來，所以條件要設好
  • Correct version

    1 2 3

    select name, title from student natural join takes, course where takes.course_id = course.course_id;

  • Incorrect version

    1 2	select name, title from student natural join takes natural join course;

Outer Join

Left Outer Join

• Left outer join
  • LEFT JOIN 可以用來建立左外部連接，查詢的 SQL 敘述句 LEFT JOIN 左側資料表 (table_name1) 的所有記錄都會加入到查詢結果中，即使右側資料表 (table_name2) 中的連接欄位沒有符合的值也一樣
    
    圖片來源

    1 2 3 4

    SELECT customers.Name, orders.Order_No FROM customers LEFT JOIN orders ON customers.C_Id=orders.C_Id;

    
    圖片來源

    LEFT JOIN 會返回左側資料表中所有資料列，就算沒有符合連接條件，而右側資料表中如果沒有匹配的資料值就會顯示為 NULL

Right Outer Join

• Right outer join
  • RIGHT JOIN 可以用來建立右外部連接，查詢的 SQL 敘述句 RIGHT JOIN 右側資料表 (table_name2) 的所有記錄都會加入到查詢結果中，即使左側資料表 (table_name1) 中的連接欄位沒有符合的值也一樣
    
    圖片來源

    1 2 3 4

    SELECT customers.Name, orders.Order_No FROM customers RIGHT JOIN orders ON customers.C_Id=orders.C_Id;

    
    圖片來源

Full Outer Join

• Full outer join
  • FULL JOIN 即為 LEFT JOIN 與 RIGHT JOIN 的聯集，它會返回左右資料表中所有的紀錄，不論是否符合連接條件
    
    圖片來源

    1 2 3 4

    SELECT customers.Name, orders.Order_No FROM customers FULL JOIN orders ON customers.C_Id=orders.C_Id;

    MySQL 資料庫中沒有 FULL JOIN，但是可以用 UNION 來模擬

View

• View 是由查詢得到的結果集組合而成的資料表，實際上資料庫裡面是不存在這一個資料表的
• 特性:
  1. 加強資料庫的安全性，View 可以將實體資料表結構隱藏起來，同時限制使用者只可以檢視及使用哪些資料表欄位
  2. 檢視表是唯讀的，亦即外部使用者無法直接透過 View 去修改內部資料。
  3. 將複雜的 SQL 查詢包裝在 View 中，可以簡化查詢的複雜度。
  4. 當資料表結構有變更時，只需要更改 View 的設定，不需更改程式

Transactions 交易

• 如果交易成功，便會確定交易期間所修改的所有資料，且會成為資料庫中永久的內容；如果交易發現錯誤，必須取消或回復，便會清除所有的資料修改
  • COMMIT: 完成交易作業
  • ROLLBACK: 交易作業異常，將已變動的資料回復到交易開始的狀態

Assertions

• 一種希望 database 總是滿足條件的術語

Authorization

• GRANT: 賦予使用者使用權限
• REVOKE: 取消使用者的使用權限

Role

• 是一種區分不同用戶的方法，這些用戶可以訪問/更新 database

Chapter 6 ER Model

以下截圖之來源

Roles

• Entity sets of a relationship need not be distinct，Each occurrence of an entity set plays a “role” in the relationship，The labels “course_id” and “prereq_id” are called roles.
  

Weak Entity

• ER Model
• 實體關係模型
• 不能獨立存在，必須依靠某個實體而存在的物件

  用雙框線框起的 entity

ER Model

discriminating attribute: 辨別屬性

Schema Model

• 先設計好 ER Model
  
  圖片來源
• 然後轉成 Schema Model

  連結實體的主鍵與外鍵，彙整為資料表，再轉給簡潔版格式

  
  圖片來源

Chapter 7 Normalization 正規化

• 建構嚴謹的資料庫 (上)

不當設計造成的異常

1. 新增異常：新增時，資料不齊全
   • 新增老師，但未授課
2. 刪除異常：刪除時，造成資料遺失
   • 刪除課程時，學生的成績資料遺失
3. 更新異常：更新時，可能會漏改
   • 更新課程資料時，需一次修改多筆資料

• 另類解釋:

1. 「資料重複」(Data redundancy)如果資料有多筆重複，可能產生資料不一致的情形。
2. 「新增異常」(Insertion anomaly)例如產品的單價欄位設計在訂單資料表中，且訂單標號為此資料表的主鍵，則未接單時，產品價格無法輸入。
3. 「刪除異常」(Deletion anomaly)刪除資料表中的某筆資料，可能也把一些重要欄位的資料也一併刪除。
4. 「修改異常」(Update anomaly)例如某項目的價格變更，在修改時，由於有資料重複的現象，必須做多筆資料的更新才能完全修改

Functional Dependency

• a R and b R

• functional dependency: a b

  • t1[a] = t2[a] then t1[b] = t2[b]

• Ex:

  • b a hold; a b does NOT hold

    a	b
    1	4
    1	5
    3	7

Armstrong’s Axioms

• 基本定理:
  1. 反身性(Reflexivity)：若 B 是 A 的子集合，則 A B。
  2. 擴增性(Augmentation)：若 A B，則 AC BC。
  3. 遞移性(Transitivity)：若 A B，且 B C 則 A C
• 延伸定理:

1. 分解性(Decomposition)：若 A BC 則 A B 且 A C。
2. 聯合性(Union)：若 A B 且 A C 則 A BC。
3. 虛擬遞移性(Pseudotransitive)：若 A B 且 BC D 則 AC D

F & F^+^

• If A B and B C, then we can infer that A C
• F^+^ 是所有 F 的 functional dependency 的集合

Key and Functional Dependency

• K is a superkey for relation schema R if and only if K R
• K is a candidate key for R if and only if
  • K R, and for no a K, a R
• r satisfies F: If a relation r is legal under a set F of functional dependencies
• F holds on R: all legal relations on R satisfy the set of functional dependencies F
• Trivial: it is satisfied by all instances of a relation
  • Example:
    • ID, name ID
    • name name
    • In general, a b is trivial if b a

Lossless Decomposition 無損分解

• 舊關聯表中所有的功能相依性都可以由分解後所產生的新關聯中不多不少地保留著(可由阿姆斯壯定理推回)，這種分解稱之為無損分解

• $\amalg$R1 ( r ) $\Join$ $\amalg$ R2 ( r ) = r
  

Closure of a Set of Functional Dependencies

• 資料庫的封閉性

資料庫正規化

• 正規化一二三
• 資料庫正規化筆記
• 資料庫正規化
• 正規化的資料庫特性
  1. 欄位唯一性：每個欄位只儲存一項資料
  2. 主關鍵欄位：每筆資料都擁有一個主鍵，來區別這些資料
  3. 功能關聯性：欄位之間的關聯應該要明確
  4. 欄位獨立性：欄位之間不應存在遞移相依
• 每個階段的正規化，都會產生一個要解決的問題
  • 1NF:去除重複資料
  • 2NF:去除部分功能相依
  • 3NF:去除遞移相依
  • BCNF:去除因功能相依產生的異常

第一正規化 1NF

1. 一個欄位只能有單一值
2. 消除意義上重複的欄位
3. 決定主鍵

   重點

   第一正規化會把原本一個欄位儲存多項資料的部份分開來儲存，然後刪除意義重複的column，
   最後給每一筆資料一個primary key來當作他們的標識

第二正規化 2NF

1. 消除部分相依

   重點

   部分相依的意思為跟主鍵只有一部份有關係，另一部份沒有關係的欄位，我們要把這些欄位獨立於另一張表

   很多框架在建表時預設會以id作為pk，若該表以完成第一正規化，設定id為pk則直接滿足第二正規化，
   因為pk為單一鍵(已經是最小單位了，自然不會有和pk”部分相依的情況”)

第三正規化 3NF

1. 消除資料表中的遞移相依

   遞移關係

Boyee-Codd 正規化（BCNF）

3NF的改良式(必須滿足3NF)。
視情況使用，實務上大多都只會做到3NF

1. 每個欄位跟PK沒有間接相依的關係
2. PK的各個欄位不可以相依於其他非PK的欄位

Chapter 9 SQL Injection

• ex: select * from instructor where name = ’" + name + "’
  • 如果使用者輸入 X’ or ’Y’ = ’Y
  • 查詢就會變成 select * from instructor where name = ’" + "X’ or ’Y’ = ’Y" + "’
    • 也就是 select * from instructor where name = ’X’ or ’Y’ = ’Y’
• solution
  • 參數化查詢
• 永遠不要用明文存密碼

Chapter 14 Indexing

以下截圖之來源

• 資料庫索引 Database Indexing
• Indexing 如何運作

  重點

  大部分的 DBSM (Database Management System 資料庫管理系統) 都會預設把主鍵（Primary Key / ID）加上索引，
  現在假設有一個資料表（table）A，A 的 ID 欄位有被加上索引，
  則實際上在資料庫中，有另外一張表（我們叫它 A’）裡面儲存了 A 裡面的所有 ID，
  而 A’ 每一個資料（ID）都對應到 A 中的完整資料

  今天我們想要找 A 中一個 ID = 3 的資料，
  資料庫會用 Binary Search Algorithm 在 A’ 中快速找到 ID = 3 這筆資料，
  然後再從這筆資料連到 A 中對應的資料

  • A’ 這個擁有 A 的 ID 資料的儲存結構通常會以 Hash 或是 B-tree 實作
    • Hash 在搜尋不能重複的資料時，效率會比較好，因此適合用在主索引鍵（Primary Index）和唯一索引（Unique Index）
    • B-tree 適合用在可以允許重複資料的一般索引（Non-Unique Index）

索引結構（Index Architecture）

• 叢集（Clustered）
  • 直接修改原本的資料表順序，將資料按照要索引的欄位排
  • 一張資料表只會有一個叢集索引，通常就是主鍵欄位（primary key column）
  • 因為叢集索引會調整資料順序，所以實體的資料（physical data rows）跟索引表（index block/index table）中的順序會是一樣的
• 非叢集（Non-Clustered）
  • 不管資料在原本資料表中的排序，而在索引表中自己依照索引值建立排列
  • 非叢集索引的排列順序不會/無法影響到實際資料的排列順序，也因此，一個資料表中可以包含很多非叢集索引
  • 通常會使用非叢集索引的會是在 JOIN, WHERE 或是 ORDER BY 使用的非主鍵欄位（non-primary key columns）
• search key
  • Search Key 是用來查找數據庫記錄的屬性集合，索引是由一個個index entry組成的，每個entry由兩部分組成：search key和pointer
  • 根據是否按照search key的順序存儲，可以將索引分為有序索引（ordered indices)和哈希索引（hash indices)
• 索引的類別
  • Dense Index Files 密集索引文件
  • Sparse Index Files 稀疏索引文件
• 索引對數據庫的修改帶來了開銷
  • 當一條記錄被插入或刪除時，關系上的每個索引都必須被更新
  • 當一條記錄被更新時，更新的屬性上的任何索引都必須被更新
• Multilevel Index
  • 如果索引不適合在內存中，訪問就會變得昂貴。
    • 解決方案：將保存在磁盤上的索引視為一個順序文件，並在其上構建一個 sparse index
      • 外索引–基本索引的 sparse index
      • 內部索引–基本索引文件
    • 如果即使是外層索引也太大了，無法在主內存中容納，那麽可以創建另一級索引，以此類推。
    • 所有級別的索引都必須在插入或從文件中刪除時被更新

Ordered Indices 有序索引

• ordered indices: search keys are stored in sorted order
  • 在一個有序的索引中，索引條目是根據 search-key 值排序存儲的
    • Clustering index: 在一個順序排列的文件中，其 search-key 指定文件的順序排列的索引
      • Also called primary index
      • 主索引的 search-key 通常是但不一定是主鍵
    • Secondary index: 其 search-key 指定的順序與文件的順序不同，也被稱為 nonclustering index
    • Index-sequential file: 按搜索键排序的顺序文件，搜索键上有一个 clustering index
• Hash indices: search keys are 均勻分布 across “buckets” using a “hash function”

Dense Index Files 密集索引文件

• Dense index 索引記錄出現在文件中的每一個 search-key 值
  
• Dense index on dept_name, with instructor file sorted on dept_name
  

Sparse Index Files 稀疏索引文件

• Sparse Index: 只包含部分 search-key 值的索引記錄
  • 當記錄按 search-key 順序排列時適用
• 為了找到一個 search-key 值為K的記錄
  • 找到具有最大 search-key 值 < K的索引記錄
  • 從索引記錄所指向的記錄開始按順序搜索文件
    
• 與 Dense Index Files 相比。
  • 優點: 空間小，插入和刪除的維護開銷小
  • 缺點: 定位記錄的速度比密集索引慢

權衡 Dense Index 與 Sparse Index

• for clustered index: sparse index with an index entry for every block in file, corresponding to least search-key value in the block
  
• For unclustered index: sparse index on top of dense index (multilevel index)

Secondary Indices 二級指數

• Index record points to a bucket (包含指向具有該特定 search-key 值的所有實際記錄的 pinter)
• Secondary indices have to be dense (索引記錄出現在文件中的每一個 search-key 值)

Index Evaluation Metrics 指數評估指標

• Access types supported efficiently
  • 有一個指定的屬性值的記錄、屬性值落在指定數值範圍內的記錄
  • Access time、Insertion time、Deletion time、Space overhead

Index Update: Deletion

• 如果被刪除的記錄是文件中唯一具有其特定 search-key 值的記錄，則該 search-key 也將從索引中刪除
• Single-level index entry deletion:
  • Dense indices – search-key 的刪除類似於文件記錄的刪除
  • Sparse indices –
    • 如果在索引中存在 search-key 的條目，則通過用文件中的下一個 search-key 值（按 search-key 順序）替換索引中的條目來刪除它
    • 如果下一個 search-key 值已經有一個索引條目，該條目將被刪除而不是被替換

Index Update: Insertion

• Single-level index insertion:
  • 使用要插入的記錄的搜索鍵值進行查詢
    • Dense indices - 如果搜索鍵值沒有出現在索引中，則插入它
      • 索引以順序文件的形式維護
      • 需要為新條目創造空間，可能需要溢出 blocks
    • Sparse indices –如果索引為文件的每個塊都存儲一個條目，除非創建一個新的塊，否則不需要對索引進行改變
      • 如果創建了一個新的區塊，出現在新區塊中的第一個搜索鍵值將被插入到索引中

B+-Tree Index Files

B+ Tree Visualizations

• 從根到葉的所有路徑都是相同長度的
  • 每個不是根或葉的節點都有n/2到n個孩子
  • 一個葉子節點有(n-1)/2和n-1之間的值
  • 特殊情況
    • 如果根不是葉，它至少有2個孩子
    • 如果根是葉子（也就是說，樹上沒有其他節點），它可以有0到（n-1）個值

• Ki are the search-key values
• Pi are pointers to children (for non-leaf nodes) or pointers to records or buckets of records (for leaf nodes).
• The search-keys in a node are ordered
  • K1 < K2 < K3 < . . . < Kn–1 (Initially assume no duplicate keys, address duplicates later)

Leaf Nodes in B+-Trees

• For i = 1, 2, . . ., n–1, pointer Pi points to a file record with search-key value Ki
  • If Li, Lj are leaf nodes and i < j, Li’s search-key values are less than or equal to Lj’s search-key values
  • Pn points to next leaf node in search-key order

Non-Leaf Nodes in B+-Trees

• Non leaf nodes form a multi-level sparse index on the leaf nodes. For a non-leaf node with m pointers:
  • All the search-keys in the subtree to which P1 points are less than K1
  • For 2 <= i <= n – 1, all the search-keys in the subtree to which Pi points have values greater than or equal to Ki–1 and less than Ki
  • All the search-keys in the subtree to which Pn points have values greater than or equal to Kn–1
  • General structure
    

Example of B+-tree

• Leaf nodes must have between 3 and 5 values
  • ([(n–1)/2] and n–1, with n = 6)
• Non-leaf nodes other than root must have between 3 and 6 children ([(n/2] and n with n=6)
• Root must have at least 2 children.

Queries on B+-Trees

• function find(v)
  1. C=root
  2. while (C is not a leaf node)
     1. Let i be least number s.t. V <= Ki
     2. if there is no such number i then
     3. Set C = last non-null pointer in C
     4. else if (v = C.Ki ) Set C = Pi +1
     5. else set C = C.Pi
  3. if for some i, Ki = V then return C.Pi
  4. else return null /* no record with search-key value v exists. */
     

Hashing

hash index

圖片來源

• hash 完是2，就在 bucket 2 的地方放pointer 指到存的地方

Bucket Overflows

• bucket: is a unit of storage containing one or more entries
  • 我們用一個 hashing function 從一個條目的 search-key 值中獲得該條目的 bucket
• bucket overflow 發生原因
  • buckets 不夠
  • 多個紀錄有著相同的 search-key
  • hash function 產生了非均勻的分布

Dynamic Hashing

• 定期重新 rehashing

Reference

fooish.com
edX
RelaX
Referential integrity
Left outer join
Right outer join
Full outer join
ER Model
hash index
參考書
資料庫的四種語言
ACID 是什麼
Key 鍵
實體關係模型
建構嚴謹的資料庫 (上)
資料庫的封閉性
正規化一二三
資料庫正規化筆記
資料庫正規化
資料庫索引 Database Indexing
「筆記」- 實體關聯圖