一、關係查詢處理和查詢優化 關係資料庫系統的查詢處理 查詢處理的步驟分為4個階段：查詢分析、查詢檢查、查詢優化和查詢執行。 查詢語句（由此語句進行查詢） 1、查詢分析 首先對查詢語句進行掃描、詞法分析和語法分析。對SQL關鍵字、屬性名和關係名等，進行語法檢查和語法分析 ，即判斷查詢語句是否符合SQL ...
一、關係查詢處理和查詢優化
關係資料庫系統的查詢處理
查詢處理的步驟分為4個階段：查詢分析、查詢檢查、查詢優化和查詢執行。
查詢語句（由此語句進行查詢）
1、查詢分析
首先對查詢語句進行掃描、詞法分析和語法分析。對SQL關鍵字、屬性名和關係名等，進行語法檢查和語法分析 ，即判斷查詢語句是否符合SQL語法規則。
2、查詢檢查
對合法的查詢語句進行語義檢查，即根據數據字典中有關的模式定義檢查語句的資料庫對象，如關係名、屬性名是否存在和有效。
3、查詢優化
查詢優化和分為代數優化和物理優化：代數優化是指按照一定的規則，通過對關係代數表達式進行等價變換，改變代數表達式中操作的次序和組合，使查詢執行更高效；
物理優化則是指存取路徑和底層操作演算法的選擇。選擇的依據可以是基於規則的，也可以是基於代價的，也可以是基於語義的。
4、查詢執行
依據優化器得到的執行策略生成查詢執行計劃，有代碼生成器（code generator）生成執行這個查詢計劃的代碼，然後加以執行，回送查詢結果；
實現查詢操作的實例：(資料庫優化的最終操作：儘量減少IO的塊數)
1、選擇操作的實現
（1）、簡單的全表掃描演算法(table scan)（全掃：io代價：總的塊數m block + O(n)元組代價）
（2）、索引掃描演算法（index scan）
通過索引先找到滿足條件的元組指針，再通過元組指針在查詢的基本表中找到數組；
2、連接操作的實現：（連接操作是查詢處理中最常用也是最耗時的操作之一。）
（1）、嵌套迴圈演算法（nested loop join）:在實際實現中數據存取是按照數據塊讀入記憶體，而不是按照元組進行I/O的。
（2）、排序-合併演算法（sort-merge join或merge join）：1、如果參與連接的表沒有排好序，首先對錶按連接屬性排序 。2、在取表中的連接屬性，把它們表中的屬性連接起來。
（3）、索引連接（index join）演算法：（B+樹 索引+基地址的方式）
（4）、hash join演算法：以數組的方式：基地址+偏移（快）；
關係資料庫系統的查詢優化
查詢優化的優點不僅在於用戶不必考慮如何最好的表達查詢以獲得較高的效率，而且在於系統可以比用戶程式的“優化”做的更好，這是因為：（1）、優化器可以從數據字典中獲取許多統計信息 （2）、如果資料庫的物理統計信息改變了，系統可以自動對查詢進行重新優化以選擇相適應的執行計劃。（3）、優化器可以考慮數百種不同的執行計劃，而程式員一般只能考慮有限的幾種可能性。
（4）、優化器中包括了許多複雜的優化技術，這些技術往往只有最好的程式員才能掌握。
總代價=I/O代價 +CPU代價 +記憶體代價+通信代價（數據結構：記憶體地址 ； 資料庫：硬碟的邏輯地址）
代數優化
代數優化策略是通過對關係代數表達式的等價變換來提高查詢效率。
1、連接，笛卡爾積的交換律
2、連接、笛卡爾積的結合律
3、投影的串接定律
4、選擇的串接定律
5、選擇與投影操作的交換律
6、選擇與笛卡爾積的交換律
7、選擇與並的分配律
8、選擇與差運算的分配律
9、選擇對自然連接的分配律
10、投影與笛卡爾積的分配律
11、投影與並的分配律
查詢樹的啟髮式優化
（1）、選擇運算應儘可能先做
（2）、把投影運算和選擇運算同時進行
（3）、把投影同其前或其後的雙目運算結合起來
（4）、把某些選擇同在它前面要執行的笛卡爾積結合起來成為一個連接運算。
（5）、找出公共子表達式。
物理優化
代數優化改變查詢語句中操作的次序和組合，但不涉及底層的存取路徑。物理優化就是要選擇高效合理的操作演算法或存取路徑。
選擇的方法可以是：
（1）、基於規則的啟髮式優化
（2）、基於代價估算的優化
（3）、兩者結合的優化方法
二、資料庫恢復技術
1、事務
所謂事務是用戶定義的一個資料庫操作序列，這些操作要麼全做，要麼全不做，是一個不可分割的工作單位。
事務和程式是兩個概念。一般來講，一個程式中包含多個事務。
在SQL中，定義的事務的語句一般有三條：（1）、BEGIN TRANSACTION (2)、COMMIT：即是提交事務的所有操作。將事務中所有對資料庫的更新寫回到磁碟上的物理資料庫中去。 (3)、ROLLBACK：所有已完成的操作全部撤退，回滾到事務開始時的狀態。
事務是恢復和併發控制的基本單位。
2、事務的ACID特性
原子性（Atomicity）:事務是資料庫的邏輯工作單位，事務中包括的諸操作要麼是都做，要麼都不做。
一致性（Consistency）:事務執行的結果必須是使資料庫從一個一致狀態變到另一個一致性狀態。
隔離性（Isolation）:一個事務的執行不能被其他事務干擾。
持續性（Durability）:也稱永久性（Permanence）,指一個事務一旦提交，它對資料庫中數據的改變就應該是永久性的。
3、故障的種類
（1）、事務內部的故障：例如運算溢出、併發事務放生死鎖而被選中撤銷該事務、違反了某些完整性限制而被終止等。事務故障意味著事務沒有達到預期的終點，恢復程式要在不影響其他事務運行的情況下，強行回滾該事務，即撤銷該事務已經作出的任何對資料庫的修改，使得該事務好像根本沒有啟動一樣，該類恢復操作稱為事務撤銷（UNDO）
（2）、系統故障：系統故障是指造成系統停止運轉的任何事件，使得系統要重新啟動。第一個：一些尚未完成的事務的結果可能已送入物理資料庫，從而造成資料庫可能處於不正確的狀態，需要（UNDO）；第二個：發生系統故障時，有些已完成的事務可能有一部分甚至全部留在緩衝區，尚未寫回到磁碟上的物理資料庫中，系統故障使得這些事務對資料庫的修改部分或全部丟失，這也會使資料庫處於不一致狀態，因此應將這些事務已提交的結果重新寫入資料庫（REDO）。
（3）、介質故障
（4）、電腦病毒
總結：各類故障對資料庫的影響有兩種可能性，一是資料庫本身被破壞，二是資料庫沒有被破壞，但數據可能不正確，這是由於事務的運行被非正常終止造成的。恢復的基本原理十分簡單，冗餘；利用別處的冗餘數據進行重建。
4、恢復的實現技術
建立冗餘數據最常用的技術是數據轉儲和登記日誌文件（logging）。資料庫恢復是將資料庫從錯狀態恢復到某一已知的正確狀態的功能。
4.1、數據轉儲
靜態轉儲（停機更新）是在系統中無運行事務時進行的轉儲操作。
動態轉儲（不停機更新）是指轉儲期間允許對資料庫進行存取或修改。缺點：轉儲結束時後援副本上的數據並不能保證正確有效。
海量轉儲是指每次轉儲全部資料庫
增量轉儲則指每次只轉儲上一次轉儲後更新過的數據。
4.2、登記日誌文件
日誌文件的格式和內容
日誌文件是用來記錄事務對資料庫的更新操作的文件；兩種格式：已記錄為單位的日誌文件和以數據塊為單位的日誌文件
日誌文件中需要登記的內容包括：1、各個事務的開始（BEGIN TRANSACTION）標記 2、各個事務的結束（COMMIT或ROLLBACK）標記 3、各個事務的所有更新操作。
每個日誌記錄的內容包括：事務標識，操作的類型，操作對象，更新前數據的舊值，更新後數據的新值；對於以數據塊為單位的日誌文件，日誌記錄的內容包括事務標識和被更新的數據塊。
日誌文件的作用：日誌文件用於保存對數據的更新操作；
（1）、事務故障恢復和系統故障恢復必須用日誌文件
（2）、在動態轉儲方式中必須建立日誌文件，後備副本和日誌文件結合起來才能有效地恢複數據庫。
5、恢復策略
5.1、事務故障的恢復
（1）、反向掃描日誌文件，查找該事務的更新操作。
（2）、對該事物的更新操作執行逆操作
（3）、繼續反向掃描日誌文件，查找該事務的其他更新操作，並做同樣處理
（4）、如此處理下去，直到讀到此事務的開始標記，事務故障恢復就完成了。
5.2、系統故障的恢復
（1）、正向掃描日誌文件，找出在故障發生前已經提交的事務，將其事務標識記入重做隊列（REDO-LIST）。同時找出故障發生時尚未完成的事務（這些事務只有BEGIN TRANSACTION記錄，無相應的COMMIT記錄），將其事務標識記入撤退隊列（UNDO-LIST）。
（2）、反向掃描日誌文件，對每個撤退事務的更新操作執行逆操作，將日誌文件記錄中“更新前的值”寫入資料庫。
（3）、對重做隊列中的各個事務進行重做處理
6、具有檢查點的恢復技術
具體的檢查點（checkpoint）記錄相關技術請查閱相關的書籍。
系統使用檢查點方法進行恢復的步驟是：
（1）、從重新開始文件中找到最後一個檢查點記錄在日誌文件中的地址，由該地址在日誌文件中找到最後一個檢查點記錄。
（2）、由該檢查點記錄得到檢查點建立時刻所有正在執行的事務清單ACTIVE-LIST.
UNDO-LIST：需要執行UNDO操作的事務集合
REDO-LIST：需要執行REDO操作的事務集合
把ACTIVE-LIST暫時放入UNDO-LIST隊列，REDO隊列暫為空。
（3）、從檢查點開始正向掃描日誌文件。1、如有新開始的事務Ti,把Ti暫時放入UNDO-LIST隊列；2、如有提交的事務Tj，把Tj從UNDO-LIST隊列移到REDO-LIST隊列；直到日誌文件結束；
（4）、對UNDO-LIST中的每個事務執行UNDO操作，對REDO-LIST中的每個事務執行REDO操作。
三、併發控制
事務可以一個一個地串列執行，即每個時刻只有一個事務運行，其他事務必須等到這個事務結束以後方能運行。在單處理機系統中，事務的並行執行實際上是這些並行事務的並行操作輪流交叉運行。1、CPU時間切片 2、搶占式的運行：誰搶到CPU，誰運行。
併發操作帶來的數據不一致性包括丟失修改（lost update）、不可重覆讀（non-repeatable read）、讀“臟”數據（dirty read）.
具體的操作可以參考相關的資料
併發控制的主要技術有封鎖（locking）、時間戳（timestamp）、樂觀控製法（optimistic scheduler）和多版本併發控制（multi-version concurrency control，MVCC）等。
封鎖
基本的封鎖類型有兩種：排它鎖（exclusive locks，簡稱X鎖）和共用鎖（share locks,簡稱S鎖）。
排他鎖又稱為寫鎖。
共用鎖又稱為讀鎖。
