【個人筆記】數據庫原理（西電）

寫在前面：文中提到的頁面指向（如“p45”），除特別說明，都是指對應ppt上的頁面，非同款ppt的友友可忽略?

第一章

ER圖和關系分解見課本p69

ER圖是常用的 概念模型?

方形：實體
圓形：屬性
菱形：關系?

常用的邏輯模型

說白了：增刪改查?

?幾種數據模型的基本概念

層次模型：樹狀結構【只能處理一對多的關系，只有沿著從根節點到子節點的方向看才有意義】

【找到逐級的包含關系，構建樹】?

網狀模型：每個實體分別建表，然后實體間聯系再建一個表【維護代價大】

關系模型p45

?關系，就是元組的集合；元組的核心，在于主碼。

模式p53

數據庫模式體系：三層模式，兩層映射?

外模式【多個】：【局部數據的邏輯結構和聯系】一對多，一個應用只能訪問一個外模式對應數據，但一個用戶可以有多個應用，因此可以訪問多個外模式，用戶只能看見和訪問對應外模式的數據
模式【一個】：【全部數據的邏輯結構和聯系，和完整性、規范性約束】
內模式【一個】：【數據的物理結構和存儲方式】

第二章ppt1

n元關系只要n個域就行，不要求是不同的域?

列是同質的：一個列上的所有元素的類型是一樣的

原子值：比如“姓名” 屬性的值就是一個原子值，像 “張三”，它不能再分割成更小的有意義的數據部分。

記：同質/來源/ 行序/列序 /元組唯一/分量原子值

參照關系

可以自己和自己參照！比如員工和其上級

兩個完整性約束?

下圖最后一句是說：如果R的外碼包含多個屬性，那么他們要么全都是空的，要么就是要和S中的某個元組對應

第二章ppt2

?四大范式NF

函數依賴【課本p76】

?函數依賴x->y可以有，對于相同的y，有不同的x

?易錯例！

平凡& 非平凡函數依賴

完全依賴F，部分依賴P& 傳遞依賴T【注意有“不包含，不反推”的要求】【注意各自箭頭上的字母】

上面的這些叫函數依賴

多值依賴p30開始【不考】

第三章：

關系代數：\pi，\sigma，除法和多表查詢

//去重問題：根據豆包的說法，一般投影運算pai會自動去重，但是sigema不會對元素去重

//注意：一般要綜合使用，比如要選出“選出運送了1號貨物的商家的編號”，應該先用sigema選出“1號貨物”，再用pai選出商家編號?

多表查詢：查詢的表為多個表的自然連接

sigema的角標“且，或”?的表示：用析取合取號

下圖二：除法的使用

看右圖用例比較方便，注意除法變換不可逆（乘法是包含關系）

除法使用例：找出至少使用了S1提供的全部零件的JNO<看到“全部”，想到除法>

<=> 找出S1提供的全部零件（用sigema_S1再用pai選出零件列），找出包含全部零件和JNO映射關系的列（用pai選出），最后用后者除以前者。

自然連接的定義&特殊的自然連接?

左外連接（Left Outer Join）的結果中，左邊表的所有記錄都會保留，而右邊表中與左邊表匹配的記錄會正常顯示，右邊表中缺失的匹配項對應的字段值填 NULL。

內連接：刪除所有不滿足條件的

SQL語句

課本索引：

表、視圖的創建【p100】

字符串匹配?LIKE【p115】

聚集函數【p117】

GROUP BY【p118】

嵌套查詢【p125】 where Sno in （select Sno where 。。。）

數量關系上的查詢（如最值）運算符和聚集函數如 any， <max，>min【p128】

集合操作 Union Intersect Except?等【p129】

數據更新【p132】Insert， Update， Delete

數據控制語言【權限授予等p134】

表、視圖和索引

表：中間的屬性 not null；unique; primary key【其余可用check（第四章有講）】

表的內部修改（列） Alter Table 表名+
- ADD? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?--增加列
- DROP? ? ? ? ? ? ? ? ? ? ? ? ? ? --刪除列
- Alter 列名列的新屬性；--改屬性值

視圖View：創建后可以像Table一樣查找

表和視圖的刪除都有Cascade級聯選項，A（子表）參照B（父表），父表被級聯刪除，子表一并被刪
物化視圖（一般用于對于相同量的反復查找）：Create materialized view 視圖名

索引：

Create [unique][cluster] index on?
Alter 舊索引名 rename to 新索引名

三者的刪除都是DROP

數據更新（對表中的元組）

Insert into 表名（列1，列2）values （值1，值2）

Update 表名 Set 列名1 = 表達式1，列名2 = 表達式2? [where ..]

Delete From 表名 [where ..]

使用Exists語句之前：將自然語言最終轉換成 “（不）存在。。。樣的的記錄” 的形式

嵌套查詢：注意父子之間的連接：“他”<也即父查詢“輸出他的”，子查詢“不存在他的”>，所以要記得在子查詢的where語句中加入Sno = Student.Sno 的判斷

用 Exists 語句實現全稱量詞：兩次嵌套

選修全部課程 <==> 不存在這樣的課程，不存在該同學對該課程的選修記錄<p29>

典例?tip：記住就好了~

下面語義：找這樣的學生，不存在?95002 選修的課程，該學生沒選（即對于該學生而言，不存在自己選修該課程的記錄）

理解：SCX，SCY，SCZ分別是不同層次對表的代稱，其中SCY用來指代‘95002’號學生，SCX和SCZ都是用來指最終要輸出的學生，層次關系是：SCX和SCZ學號相等

記憶：

第一層：找學生，這個好理解
第二次：在exists內部，所以select*，然后限制是95002
第三層：同二用select*，與第一層，第二層分別聯系：和第一層是同樣的學生，和第二層是同樣的課程

換一種方式實現上面的功能【Group by + Having】

一樣的課程 <=> 找出我選了你也選了的課程，發現數量是一樣的

SELECT SCX.Sno
FROM SC SCX
WHERE SCX.Cno IN (SELECT Cno FROM SC WHERE Sno = '95002')--現在只留下了兩人都選的課程
GROUP BY SCX.Sno    --用group by A，則select后面要么是A，要么是對于各列的聚集函數
HAVING COUNT(DISTINCT SCX.Cno) = (SELECT COUNT(DISTINCT Cno) FROM SC WHERE Sno = '95002');
--select 后面的東西本質上就是這一部分查詢最終輸出的東西select scx.sno
from sc as scx
where sc.cno in (select cno from sc where sno = '95002')
group by scx.sno
having count(distinct scx.sno) = (select count(distinct cno) from sc where sno = '95002')

注意Distinct在聚集函數<比如count>中的使用?

例題：查詢同時選了兩個指定課程的學生ID

【利用子查詢】

SELECT ID
FROM takes
WHERE course_id = 'CS-101'AND ID IN (SELECT ID FROM takes WHERE course_id = 'CS-190');

SQLSheet系統注意事項

表格重命名要用as，“from student ST”會出錯，只能用 from student as s,?且一旦重命名就不能再用原始名字！
注意去重，查詢要去重DISTINCT，習慣性select DISTINCT ID,注意：DISTINCT不能用于多個列
多表連接，select 對象要指明，比如from的多個表都有ID列，select的時候不能寫select ID，而要具體寫比如student.ID
?

畫下劃線的是表的主碼，即這幾列的整體才能唯一確定一個元組，也即單獨幾列不可以唯一確定一個元組

易錯示例

注意from的范圍：選了課程的學生！= 總學生

注意：下面這種查詢對應的是“takes中沒有選course_id 的學生”，而不是題目要求的“（所有學生中）沒有選course_id 的學生”

Q8 [Query the student ID of students who have taken all courses]

select distinct student.ID
from student, takes
where student.ID = takes.ID
and takes.course_id in (select distinct course_id from takes)
group by student.ID
having count(takes.course_id) = (select count(distinct takes.course_id) from takes);

?T16

誤！題目理解錯誤！number of courses是指每個符合要求學生的具體85分以上課程的數量，并不是“總共有多少個85分以上課程（所有課程滿分都💯哇！）”

后記：關于SQL

SQL是一種聲明式語言，而不是一種過程式語言，即用戶只指出做什么，但不指定怎么做（不描述執行的具體步驟）

但任何一個SELECT語句，都可以等價轉化為關系代數? $\pi \sigma$ ?的語句，后者是具有一定過程性的（先做笛卡兒積，再用 $\sigma$ 篩選，最后 $\pi$ 投影）?

關系代數的局限性：關系代數算子的實現不清楚（實際上要落實到具體的物理操作符上）

第四章：完整性和安全性【自學】

GRANT?語句的書寫者，需?具備 “授權權限”?，具體分場景：

數據庫管理員（DBA）：擁有最高權限，可寫?GRANT?給任意用戶授權。
對象屬主（OWNER）：創建表、視圖等對象的用戶，能寫?GRANT?分配自己對象的權限。
有傳播權限的用戶：若被授予權限時帶?WITH GRANT OPTION，可寫?GRANT?把權限再授給他人（但不能循環授權）。

普通 “僅訪問” 的用戶，若無上述權限，不能寫?GRANT?

收回權限REVOKE

關于寫和不寫Cascade的區別：

不寫?CASCADE?：

執行?REVOKE INSERT ON TABLE SC FROM U5（會檢查U5是否有級聯，如果有，拒絕回收任何一個權限）：
數據庫發現?U5?把權限傳給了?U6，會拒絕回收（報錯或提示需級聯），U5、U6、U7?的權限都保留。
若?U5?沒傳給任何人：
執行?REVOKE... FROM U5（不寫?CASCADE?），僅回收?U5?的權限，不影響其他用戶。

數據庫的角色：將一組權限打包

Create Role?

With Admin Option

強制存取控制【解決自主存取方法的問題】

給用戶和數據都標有一定敏感度標記

??：只有同等級才能寫！

DAC【自主訪問控制】，MAC【強制訪問控制】

視圖機制就是，把A用戶能訪問的數據打包成一個視圖，然后把對該視圖的相關權限授予給A，替代直接對原始表授權p26

三種完整性定義

實體完整性【主碼，Primary key】

參照完整性【Foreign key A references on S(Sno)】

用戶完整性【定義表的時候設置要求，char（9），unique，not null等設置對單個屬性的限制，用check實現對于單個或不同屬性組之間的關系的限制】

綜合例：【check 搭配使用】

between 200 and 500（取的數值在什么范圍之間）
not like（“（用于字符串）不能是”）
in（“取值只能是”）

域的完整性約束Domain

觸發器p46

?使用示例【轉載】

DELIMITER $$
?
CREATE TRIGGER update_is_leave_cleanup
AFTER INSERT ON community
FOR EACH ROW
BEGIN-- 檢查新增小區樓棟數量是否 大于20棟 且 住戶是否不低于150人IF NEW.term_count > 20 AND NEW.per_count >= 150 THEN-- 刪除所有離開時間超過一年的訪客記錄DELETE FROM manual_recordWHERE is_leave = 1AND out_time < DATE_SUB(NOW(), INTERVAL 1 YEAR);END IF;
END$$
?
DELIMITER;

第五章：索引

藍塊中的感覺比較雜，不確定考不考

隨機訪問的意義：適用于非連續的存儲：不同記錄可能分布在不同磁盤塊。隨機訪問允許直接定位并讀取這些分散的數據，無需按順序遍歷大量無關數據。在特定場合下，隨機訪問有不可被替代的作用

文件內的三種組織類型

OLAP：適合列存；
OLTP：適合行存
HTAP（散列）：不同hash桶之間無序，hash桶內部有序

多表聚簇類似于將多個表連接后再存儲，方便多表查詢，適用于需要同時對多個表的查詢

兩種堆文件存儲方式【page之間的存儲】：鏈表堆和目錄堆（文件內部的頁面之間的存儲）

每個頁page里面的存儲：

定長元組：順序存儲

變長元組的存儲：分槽slot頁面結構

Entries：實體數量
空閑空間末尾指針：指向空閑空間
slot中的元組：存儲指針和大小

下圖：上邊是元組的內容，下面是對應的存儲

注意存儲順序：1 空值位圖，2 定長屬性值，3 變長屬性的索引記錄（起始位置，長度），每個索引長度固定為4 <有點像指針的思想> ；4 變長屬性的具體值

空值位圖：指示哪一位為空（NULL），為空的那一位計為1【如下圖，第三位為1，就是第三個信息計為NULL】

行存：適合點查詢（目標是精準定位 “單個或極少特定記錄”）和刪改
列存：適合對部分屬性的大量查詢，減少讀負載上的IO使用

緩沖池：對應書 5.9節

CLOCK置換算法：只需要一個bit位作為標記位就可以大概實現LRU的效果

想象有一個環形的時鐘，每個時鐘位置都可以放置一個數據頁。當數據頁被訪問時，標記位就從0變成1（但此時時鐘指向的位置不變）。

當緩存空間滿了，需要淘汰一個數據頁時，算法就從當前指針位置開始，沿著時鐘方向逐個檢查數據頁。如果一個數據頁沒有被標記，那么就把它淘汰掉，因為這意味著它最近沒有被使用過。如果遇到被標記的數據頁，就把它的標記清除（熄滅燈），然后繼續檢查下一個數據頁，直到找到一個沒有標記的數據頁并淘汰它，替換成新的頁面，并將新的頁面記為0（調入后再執行缺頁指令，才訪問這個頁面，然后將其置為1）。（理解：如果初始值設成1的話會出問題）

這里涉及到操作系統中 “頁面調入” 和 “頁面訪問” 的時序區別。在 CLOCK 算法中，新頁面初始標記為 0 而非 1 的核心原因是：頁面調入內存的操作本身不等于對該頁面的訪問。

頁面調入（Page Fault Handling）
當發生缺頁中斷時，操作系統需要從磁盤將所需頁面調入內存。這個過程分為兩個步驟：
- 步驟 1：物理頁面分配
  系統選擇一個空閑幀（或淘汰一個舊頁面），將新頁面從磁盤復制到該幀。此時，新頁面只是被加載到內存中，但尚未被 CPU 訪問。
- 步驟 2：訪問權限恢復
  當頁面加載完成后，CPU 會重新執行導致缺頁的指令，此時才會真正訪問該頁面（讀 / 寫數據）。
關鍵點：CLOCK 算法在步驟 1（頁面加載）時就將新頁面的標記位設為 0，而訪問標記（設為 1）是在步驟 2（CPU 實際訪問）時才發生的。

索引的分類

根據存儲的物理結構

聚簇索引：索引和數據綁定在一起，按照索引順序存儲（如果索引對應了n個元組，則這n個元組應該連續存儲）
非聚簇索引：索引和數據分開存儲

根據索引是否覆蓋所有的搜索碼

稠密索引
稀疏索引

根據是否按照數據的順序存儲

順序索引

注意：上面幾個沒有絕對的包含關系，而是不同層面的實現形式

B+樹

查找的復雜度與樹的深度線性相關

各方面的數據限制

注意：B+樹對葉子節點是元素數量的要求，但對非葉子（根節點和中間節點）節點是子節點數量（本質就是指針）的限制

m路B+樹根節點的孩子數量：2~m個

插入&刪除算法

都是先用find找到要操作的葉子節點，然后操作

注意，插入并不是簡單放在空位上，還要對節點內部進行排序

潛在問題和解決：

插入導致過滿？拆分，拆分會反應到父節點改變，存在網上級聯影響的可能
刪除導致元素過少？先嘗試和左右兄弟節點合并（旁邊兄弟有足夠空位），合并會反應到父節點改變，存在網上級聯影響的可能
當刪除導致節點元素過少時，優先嘗試與兄弟節點合并（如果兄弟節點有足夠空間）。
合并后，父節點的指針需要重新調整（例如，兩個子節點合并為一個，父節點原本指向這兩個節點的指針需要合并為一個），這就是指針重分布。

B+樹的查詢

下圖中符號含義的說明：

$node.P_{i}$ ?指該節點左邊指針對應的子樹
$node.P_{i+1}$ ?指該節點右邊指針對應的子樹
$P_{n}$ ?為該節點最右邊的子樹（確定的）

哈希表

先計算該項對應的哈希值，作為插入的索引

兩類哈希表&靜態哈希表的兩種實現形式

靜態哈希表的 “靜態” 體現在其哈希表的結構和大小在初始化后就不再改變。哈希表的桶數量固定，使用的哈希函數也是確定不變的。靜態哈希表若要應對超出當前容量的數據，往往需要重建整個哈希表，開銷較大。動態哈希表則具備相應機制，如可擴展哈希表通過按需擴展目錄深度、分裂桶等方式來容納更多數據；線性哈希表以線性方式逐個增加桶來實現擴容。

靜態

閉哈希：兩種查找方式
開哈希：哈希鏈表

動態【下圖中】

可擴展哈希表& 其問題
線性哈希表

i 位二進制，可以映射到? $2^{i}$ ?個哈希桶

右上角小的 j = 1，2代表“局部深度”，代表用 j 位二進制就可以識別到，比如00和01合并以后，用一位“0”就可以確定是第一個桶，所以是 j = 1

可擴展哈希表~插入操作（插入但當前桶滿？）

先計算要插入項對應的哈希值

然后嘗試映射到對應的桶，看這個桶是否已經滿了，若滿了，進行下面判斷：

j<i (說明有桶合并了)：展開合并的桶
j=i: 進行擴容（i值增加一位，原有的哈希桶重新映射到新的目錄上去）

缺點：可能總是因為某一個桶滿，導致所有桶都要擴展，致使填充率降低【下面未解決】

刪除鍵值：墓碑標記（p113）

線性哈希表（利用哈希值的后m位）【優化了上面的缺點】

具體原理公式見下圖

以插入1111為例，如果一開始沒有對應11索引，11B = 3D（B指二進制，D指十進制），3-2^{m-1} = 1，所以先存在01桶

汲取可擴展哈希表的分裂桶經驗，但以插入后填充率超過閾值作為判斷，若超過，加新桶，分裂舊桶

避免全表擴展：由于不是某個桶滿就全表擴展，而是關注整體填充率，所以不會因個別桶的情況輕易對整個哈希表進行操作。當填充率未超閾值時，即使有桶滿了，也不會觸發全表擴展，減少了不必要的空間浪費，維持了相對較高的填充率。

哈希表適合點查詢，B+樹進行范圍查詢更方便

第六章

總體脈絡

查詢解析

八大rules

（A ::= B 表示了一種映射關系，如果有B，那么就映射為A并存儲）

如下圖所示，A一般是類型，B一般是SQL具體的語言原子

邏輯重寫

提高查找效率的方式：謂詞拆分 &?投影下推（見下段）& 笛卡爾積轉成等值連接來進行操作（兩個表都有C列，笛卡兒積里面可能有兩個C列不相同的合并到同一行）

謂詞拆分 &?投影下推：凡是只涉及單表的操作，都可以放到前面去完成，比如多個σ，實際上選擇操作可以拆分在單個表上完成，于是可以在笛卡兒積前先篩選

關于嵌套查詢的處理方法

下圖所示：【重寫】將原始嵌套查詢重寫為連接查詢【把子查詢中的表放到外查詢，與外查詢的表連接起來】
【實體化臨時表】對于同一個復合表（如A join B on..）的多次查詢，實體化只要進行一次聚合操作（然后講這個聚合的結果就存下來了），反之就要每次查詢都聚合。所以這個實體化的優勢在于多次查詢，單次查詢的話實不實體化沒區別【下圖未明顯體現】

三. 物理算子

查找的兩種方式

?兩個變量的定義：B， T【這個關系所包含的塊數，元組數】

選擇率：滿足這個條件的元組數/ 總的元組數

關于查找唯一項的處理（=）【點查詢】
關于查找范圍的處理（>,<等比較謂詞）【范圍查詢】

對于有序表

查找>=v：找到v，向右掃
查找<=v：直接從頭節點開始，向右掃，直到找到v

兩類索引及其查找特點

聚簇索引（葉子節點包含索引和數據塊）：先定位到?v?對應的葉子節點（經過?h?次查找，h為索引對應的B+樹的樹高?），然后從該葉子節點指向的數據塊開始順序掃描后續所有數據塊 。由于數據按索引順序物理存儲，后續數據塊在磁盤上大概率是相鄰的，是順序 I/O? 。
非聚簇索引（葉子節點只有索引）：先定位到?v?對應的葉子節點（h?次查找），之后順序掃描葉子節點來提取所有指向記錄的指針 。因為非聚簇索引葉子節點只存指針，需根據指針再去訪問實際數據塊，是隨機 I/O 。

概念解析

搜索碼不唯一：即待搜索對象可能有多個，找到一個不能保證剩下沒有了
全表掃描（Table Scan）：遍歷整張表的所有元組（記錄）來查找滿足條件的數據。比如要在學生信息表找年齡大于 20 歲的學生，全表掃描就會把表中每個學生記錄都看一遍。
索引掃描（Index Scan）：利用已建立的索引來查找數據。索引類似書本目錄，能快速定位數據位置。
選擇率 $S_p(R)$ ：滿足謂詞條件 p 的元組數量與關系 R 總元組數量的比值，衡量滿足條件數據在全表中的占比。
B(R)：關系 R 占用的塊數，這里表示表數據占用磁盤塊數量。
T(R)：關系 R 中的元組（記錄）總數。
聚簇索引：數據物理存儲順序與索引順序一致，查找時可利用順序 I/O 特性，性能較好。
非聚簇索引：索引順序與數據物理存儲順序不同，查找時涉及隨機 I/O ，相對復雜。
二叉樹相關：對于一棵二叉樹（分支因子n = 2?），如果樹高為h?，最多能存儲$2^h - 1$個節點（滿二叉樹情況）。當要查找一個節點時，最多需要比較h次（也就是樹的層數）。如果有N個節點，在平衡二叉樹中，樹高? $h\approx\log_2 N$ ?，這就是對數和查找次數相關的基本原理。在下面的情景中，N就是元組數T（R）
?兩個變量的定義：B， T【這個關系所包含的塊數，元組數tuple】

各類查詢算法的平均復雜度

三種連接（PPT中p95開始）

I/O操作是對應取表（頁面）操作的，下面用T（R）是因為在當前邏輯下，對于每個R中元組，都要取出一次頁面，所以數量是T（R）

注：【比較后的寫回都不考慮IO，但排序/ 哈希后的寫會考慮IO？】

【重要！】三種連接方式效率的比較

注意：只有嵌套循環能實現? $\theta$ ?連接【對應非等值連接】

要實現效率最大化，需要提前知道B(R),B(S)的值，帶入運算后比較

嵌套循環

關于B(R)的說明：將R中的每個頁面逐一拉進內存（由此產生了B（R）），為后續比較做準備

左圖算法：對每個元組，都將S中的一個頁面拉進內存

右圖（優化）：對R的每一個頁面，將當前頁面中的所有元組，和S中拉進來的頁面都做了比較以后，再拉入下一個S的頁面【因為比較只能在主存中進行，并且要求比較的雙方（外表的頁面& 內表的頁面）都在主存中。所以，一次拉入S頁面，能比較的R頁面越多，拉入S的頁面次數就越少】

注意：把小一點的表作外表（外層循環）

對于內存空間較大/ 或者有緩沖池的情況：

緩沖池相當于主存的擴容彈匣

S的頁面，一幀存比較的

PS：預留出兩幀：

一幀專門存?中間結果（比如連接、比較運算產生的臨時數據），存滿后寫回外存；
另一幀給?內表（或小表）?做緩沖（避免頻繁換入換出，加速數據訪問）。

PS：這個叫做“寫回外存”

排序合并【存疑】

排序和哈希都是基于“先通過某種方式將相等的元組聚集，再進行等值連接”的思想

關于排序R的cost說明：

第一次操作（數據分塊與內排序）

把表 R 的數據按塊讀入內存進行內排序。這里確實涉及對每一塊數據進行一次內排序操作。總共有 B (R) 塊數據，每一塊都要經歷讀入內存、內排序、寫回磁盤的過程。這一步的主要開銷是將 B (R) 塊數據依次處理，從磁盤 I/O 角度看，讀入和寫回操作整體上相當于對 B (R) 塊數據進行了一次讀寫，再加上每一塊內排序的計算開銷（可近似看作一次操作對應一塊數據），所以從成本計算角度，這部分開銷和 B (R) 相關。

第二次操作（歸并階段）

歸并過程類似二叉樹的合并。將已經內排序好的 B (R) 個有序子塊進行歸并，構建一棵歸并樹（類似二叉樹結構）。在這棵歸并樹中，每一層的歸并操作都涉及對一些子塊的合并。
假設子塊數量為 B (R) ，那么歸并的趟數近似于以 2 為底 B (R) 的對數（向上取整），即?log?B (R)? 。在每一趟歸并中，又要對 B (R) 塊數據進行處理（因為最終要把所有子塊合并成一個有序序列），所以歸并階段的 I/O 開銷就是 B (R) * ?log?B (R)? 。

考不考慮寫回的Io呀，我覺得是一倍的B（R）*（1+log）呀

把這兩部分開銷綜合起來，就是總的排序成本 2B (R) × (1 + ?log?B (R)?) ，其中 2B (R) 體現了兩遍磁盤操作（讀入分塊排序、歸并寫出），(1 + ?log?B (R)?) 分別對應內排序和歸并階段的相關操作次數。你之前的理解準確抓住了關鍵的兩個操作階段和對應的開銷影響因素呢。

哈希連接

用相同的哈希函數，將R,S映射到桶里面，再分別在桶里面進行比較?

2（BR+BS）：將R，S的頁面分別拉進主存哈希運算后，寫回外存【此時元組可以視作已經被映射到同一個桶里面了】

1（BR+BS）：將每個哈希桶拉進主存，進行比較【這里沒考慮寫會IO】

【開銷模型p160左右】

基于代價的優化

基于代價的優化（CBO）【代價估計& 選代價最小的】

為了提前知道哪種操作比較合適，需要提前統計一些數據的信息，統稱：“統計信息”

左深樹【所有節點的右節點都是葉子節點】的數量比濃密樹小不少

定義與原理：側重于查詢的物理優化，運用代價模型對操作進行代價估計，生成由物理操作符組成的物理執行計劃（樹），且與關系實例相關。
目的：從物理執行角度，通過評估不同操作代價，選擇較優執行方案。

對于兩種假設造成的選擇率的計算偏差的解決方法

對于均勻分布假設：通過統計直方圖
對于屬性獨立假設：通過選擇性地收集某些列的信息

對于上面這種復合謂詞計 v：

連續合取：選擇率 =?選擇率 i 的乘積【這些就是基于”屬性之間是相互獨立的“假設運算的】
連續析取：選擇率 = 1 - 選擇率i的乘積

p169

基于規則的優化（RBO）【邏輯重寫】

定義與原理：通過查詢的邏輯重寫，依據關系代數的等價變換規則，減少不合理開銷。它不依賴具體關系實例。
目的：利用既定規則對查詢進行優化，在邏輯層面提升查詢效率。

兩種優化模型【RBO 與 CBO 】的結合

現狀與問題：二者結合在查詢優化中占比高，甚至占據整個查詢響應時間一半以上【也就是說，在開始執行之前，差不多會花這么久的時間先應用兩個模型】，但由于是 NP 問題，無法確保找到最優執行計劃（只能相對優化），不過仍是必要手段。

三大類（解釋型）執行器【PPTp173開始】

物化模型：每一步操作后的結果存下來，作為下一步執行的輸入

優化：邊執行邊嘗試合并，輸出一個結果，就嘗試合并，不需要等到所有都處理完

火山模型：逐元組執行

優化：上一個菜就開吃，可能不夠所有人吃，應該按照人數估計大概上幾個菜開吃比較合適

向量化模型：按向量執行【一組元組】（攢夠一定規模再去執行）

編譯型執行

即時編譯：根據具體的數據情況生成查詢代碼，更有針對性

編譯型和解釋型區別?

執行過程
編譯型：先編譯后執行，執行前完成翻譯工作，生成可獨立運行的可執行文件。
解釋型：邊執行邊翻譯，程序運行時，由解釋器逐行讀取源代碼，逐行翻譯成機器可執行指令并立即執行，不生成獨立可執行文件 。例如 Python 程序運行時，Python 解釋器逐行處理代碼。

執行效率
編譯型：執行速度快、效率高，運行時無需額外翻譯開銷。
解釋型：逐行解釋執行，每次運行都要翻譯，存在額外性能開銷，執行速度相對較慢。不過部分解釋型語言采用即時編譯（JIT）等技術提升了效率。

開發效率與靈活性
編譯型：開發過程中編譯環節耗時，修改代碼后需重新編譯，開發效率相對低，代碼修改不靈活。
解釋型：開發靈活，代碼修改后可立即運行，無需繁瑣編譯過程，適合快速原型開發和小型項目，開發效率相對較高。

有i個索引和有i個索引查找方式有什么區別【A：注意區別查找和連接！查找是對一個表進行的，有i個索引就是i個列上有索引，那么查找就可以分別從一個列的索引進去，進行初步篩選，再在剩下的元組里面看其他列，所以對應了i種索引入手的查找方式，外加一種全表查找：每一行，看條件中的所有篩選項】

第七章

事務：一個程序執行單元，要執行就要一起執行（原子性）【BEGIN ... COMMIT】，否則返回原始狀態【BEGIN ... ROLLBACK】

數據庫事務管理要解決的兩個核心問題

如何應對系統崩潰（后的恢復）：
日志的作用：數據庫使用日志記錄事務對數據的所有修改操作，而不是簡單的 “記事本”。日志按時間順序記錄每個事務的開始、結束以及對數據的修改細節，包括修改前的值（舊值）和修改后的值（新值）等。日志記錄先于實際數據修改寫入持久存儲【預寫日志】，這是保證數據可恢復的關鍵。
恢復過程：當系統崩潰后進行恢復時，數據庫系統會讀取日志。【對于（用戶界面顯示）已經提交的事務（但是內核中可能并沒有執行完成），系統會根據日志中的記錄重新執行對數據的修改操作，將數據恢復到事務提交后的狀態，這稱為重做（Redo）操作；【對于未完成（未提交）的事務<完成了一半，比如執行了A（根據持久性原則，已經寫到了A的外存），但還沒有操作B】，系統會根據日志中的舊值將數據回滾到事務開始前的狀態，撤銷這些未完成事務對數據的部分修改，這稱為回滾（Undo）操作。【例如，一個事務對某條數據進行了多次修改但還未提交時系統崩潰，恢復時就利用日志中的舊值把數據恢復到事務開始前的狀態，避免未完成事務對數據一致性的破壞。
說明：上面兩種操作，本質是要保證外存的存儲和用戶界面的效果是一致的

多事務并發執行

事務四大元素&實現手段【ACID】

A原子性：一個事務內的操作，要執行就要一起執行，要不然就全部回滾
Consistence一致性要求：修改數據前后，數據之間的核心關系應保持一致，執行過程中，允許暫時的不一致，比如轉賬，總額不變
Isolation隔離性要求：本質：從每條數據的角度來講，單獨訪問得到的結果和與其他事務并發執行的結果應該一致
Durable持久性要求：只要A，B有一個執行完了【不要求事務執行完成】，就要被固定下來【反饋到外存的持久性存儲上】（就是說每次修改完就有寫回操作）

實現手段：

I（隔離性）：并發控制完成
AID：影子頁面，日志；且由DBMS自動完成
C：由事務語句的編寫人完成

沖突等價& 沖突可串行化

視圖等價p30：關注首尾，和中間順序

視圖等價要求：說白了開始，中間和結束的一致性

開始呀，你讀我也讀、
最后呀，你寫我也寫
中間呀，你讀的值和我讀的要一樣

最先讀誰，最后寫了誰，中間讀操作關系（誰讀另一個寫的值，若中間沒有讀操作，省略），二者保持一致【滿足這個定義即可】

每個沖突可串行化都是視圖可串行化的

判斷沖突可串行化的方法

有向邊：凡是有寫就是

?見右圖：可串行化《=》優先圖無環【注意，環看的不是邊，而是有向邊，也就是對于同一變量的有向邊首尾相連構成一個環才是不可串行化】

破壞一致性：臟讀和丟失更新【相關幾個概念】

調度：多個操作穿插執行

臟讀（Dirty Read）【還沒提交B就讀，最后A回滾了】

定義：指一個事務讀取了另一個未提交事務修改的數據。這就像是在一本書還沒寫完校對就被別人拿去閱讀，可能讀到的是錯誤或不完整的內容。
示例：假設有兩個事務，事務 A 和事務 B。事務 A 修改了某條數據，但還未提交；此時事務 B 讀取了被事務 A 修改后的數據。如果事務 A 隨后回滾了操作，那么事務 B 讀取到的數據就是無效的 “臟數據”。比如在銀行系統中，事務 A 將賬戶余額從 1000 元改為 1100 元但未提交，事務 B 讀取到余額為 1100 元。若事務 A 回滾，賬戶實際余額還是 1000 元，事務 B 讀取的 1100 元就是臟數據，可能導致后續業務邏輯出錯。

丟失更新（Lost Update）【AB都寫，A還沒寫完B就寫】

定義：兩個或多個事務同時對同一數據進行更新操作，其中一個事務的更新結果被其他事務覆蓋，造成部分更新丟失。這類似于多人同時修改一份文檔，后保存的人覆蓋了前面人的修改。
示例：假設事務 A 和事務 B 都讀取了賬戶余額為 1000 元。事務 A 將余額增加 100 元并提交，此時余額變為 1100 元；事務 B 也進行同樣的增加 100 元操作，但它是基于最初讀取的 1000 元進行計算的（比如A的執行后還沒有來得及將數據寫回外存，就被B給讀出了），所以事務 B 提交后，余額還是變為 1100 元，事務 A 增加的 100 元就被 “丟失” 了。正常情況下，兩個事務都增加 100 元，余額應該是 1200 元，但由于丟失更新，少了 100 元的更新效果。

ps:幻讀：數據庫的幻讀是指在同一事務中，對于同一個數據項，一個進程在寫小范圍，一個進程在讀所有項，讀進程兩次讀取同一范圍的記錄時，第二次讀取發現有新的符合條件的記錄被插入，使得兩次讀取結果不一致的現象。