申論題

五、有兩個關聯 R（X, Y, Z）與 S（U, V, W）要相結合（join），假設 R 共有 TR 筆紀 錄，分別存放在 BR 個磁碟區塊（block）中，S 共有 TS 筆紀錄，分別存放在 BS 個磁碟區塊中，而 BR >> BS>0，且暫時存放 R 和 S 磁碟區塊資料之記憶體磁碟緩 衝區（disk buffer in memory），共可存放 n 個磁碟區塊，BS>n>1，若資料庫管理 系統（DBMS）評估處理方式後，決定以巢狀迴圈結合（nested-loop join）方式處 理 R join S on X=U。

⑴請說明 DBMS 之查詢處理器如何處理該結合，才能將該巢狀迴圈結合方式最佳 化，而對磁碟所存取之磁碟區塊總數量會最少？（註：同一個磁碟區塊若被存 取 H 次，則總數量會加上 H，而不是 1，亦請保留一個磁碟區塊大小之記憶體 磁碟緩衝區，當作輸出處理結果之輸出緩衝區）（10 分）