練習題解答[第十章基本的查詢處理與最佳化]

習題題庫 [第十章：基本的查詢處理與最佳化]
習題10-1
假設你想找出「黃三益」曾經放到購物車且定價超過500 元的相關商品資訊，所以你下達以下SQL 查詢句： SELECT pId, name, pName, unitPrice FROM Product, Order, Member WHERE Product.unitPrice > 500 AND Product.pNo = Order.pNo AND Order.mId = Member.mId AND name = ‘黃三益’; 請畫出該查詢句的初始查詢樹，並按本章所提的經驗法則一步一步轉換至較佳的查詢樹。

習題題庫 [第十章：基本的查詢處理與最佳化]

習題10-1

假設你想找出「黃三益」曾經放到購物車且定價超過500 元的相關商品資訊，所以你下達以下SQL 查詢句：
SELECT pId, name, pName, unitPrice
FROM Product, Order, Member
WHERE Product.unitPrice > 500 AND Product.pNo = Order.pNo AND Order.mId = Member.mId AND name = ‘黃三益’;
請畫出該查詢句的初始查詢樹，並按本章所提的經驗法則一步一步轉換至較佳的查詢樹。

習題10-2
假設你想找出所有購買過「系統分析理論與實務」且在1970 年以後出生的會員之會員編號和會員姓名，所以你下達以下SQL 查詢句： SELECT mId, name FROM Member, Transaction, Record, Product WHERE birthday >= to_date (‘19700101’, ‘yyyymmdd’) AND transMid = mId AND Record.tNo = Transaction.tNo AND Product.pNo = Record.pNo AND pName = ‘系統分析理論與實務’; 請畫出該查詢句的初始查詢樹，並按本章所提的經驗法則一步一步轉換至較佳的查詢樹。
[一. 初始查詢樹] [二. 將SELECT的動作往下移，盡量接近葉節點] [三. 將條件較嚴格的SELECT中間節點盡量往左邊移] [四. 將相鄰的×中間節點和 σ中間節點合併成一個中間節點 ] [五. 將PROJECT的動作往下移，盡量接近葉節點（或SELECT的中間節點）]

習題10-2

假設你想找出所有購買過「系統分析理論與實務」且在1970 年以後出生的會員之會員編號和會員姓名，所以你下達以下SQL 查詢句：
SELECT mId, name
FROM Member, Transaction, Record, Product
WHERE birthday >= to_date (‘19700101’, ‘yyyymmdd’)
AND transMid = mId AND Record.tNo = Transaction.tNo
AND Product.pNo = Record.pNo AND pName = ‘系統分析理論與實務’;
請畫出該查詢句的初始查詢樹，並按本章所提的經驗法則一步一步轉換至較佳的查詢樹。

習題10-3
假設你有一個複合索引 (unitPrice, catalog)，請描述如何利用它來處理 σ_{catalog =‘Book’ AND unitPrice > 500}Product。

習題10-3

假設你有一個複合索引 (unitPrice, catalog)，請描述如何利用它來處理 σ_{catalog =‘Book’ AND unitPrice > 500}Product。

習題10-4
考慮以下的運算式： σ_{amount >2 AND salePrice > 1000} Record 假設資料字典裡存了以下的資訊： r_Record = 200,000, b_Record= 40,000, x_salePrice= 3, bI1_salePrice = 1,000, x_{amount,salePrice} = 4, bI1_{amount,salePrice} = 5,000。其中 salePrice 欄位設為群聚索引，而 (amount, salePrice) 為非群聚索引。考慮 (SL)、(SSI) 和 (SCI) 三種查詢處理法，對於每一種處理法 1. 描述其處理方式。 2. 估算其成本。哪一種方式的成本最低？哪一種方式的成本最高？
1. SL(Select 循序搜尋)：將資料表的每一資料頁裡的每一筆記錄都拿出來做條件比對，如果成立就將該筆資料放置結果裡。 SSI(Select 單一索引結構搜尋)：其中一個子條件的屬性有建立適當的索引結構，這種方式利用該索引結構找出所有滿足條件的記錄之記錄指標，從而取出記錄，(之後為CPU處理時間)最後再將這些記錄做其他條件比對，滿足條件的才放置在結果裡。 SCI(Select 複合索引結構搜尋)：有一多屬性值索引是由多個子條件所組合而成，這種方式式利用該索引結構找出所有滿足條件之記錄指標，從而取出記錄，必要時(之後為CPU處理時間)再將這些記錄做整個條件比對，滿足條件的才放置在結果裡。 2. (a) SL方式的成本： bRecord → 40000 (b) SSI使用salePrice索引： x_salePrice+b_Record/2：3+40000/2=20003 (c) SCI計算的成本公式：使用（amount, salePrice）索引成本：由於沒有其他資訊，所以假設合乎條件的佔1/2*1/2=1/4，因此選擇幅度 s_{amount, salePrice} =200000/4=50000 x_{amount, salePrice}-1 +bI1_{amount, salePrice} /2+s_{amount, salePrice} =3+5000/2+50000=52503 結論：使用SSI (salePrice)索引的成本最低，而使用SCI （amount, salePrice）索引，成本最高。

習題10-4

考慮以下的運算式：
σ_{amount >2 AND salePrice > 1000} Record
假設資料字典裡存了以下的資訊：
r_Record = 200,000, b_Record= 40,000, x_salePrice= 3, bI1_salePrice = 1,000,
x_{amount,salePrice} = 4, bI1_{amount,salePrice} = 5,000。
其中 salePrice 欄位設為群聚索引，而 (amount, salePrice) 為非群聚索引。
考慮 (SL)、(SSI) 和 (SCI) 三種查詢處理法，對於每一種處理法
1. 描述其處理方式。
2. 估算其成本。
哪一種方式的成本最低？哪一種方式的成本最高？

習題10-5
在第五節第三小節的範例四裡，假設所建立的多欄位索引是 (unitPrice, catalog)，而非 (catalog, unitPrice)。請問利用 (SCI) 來運算的成本為何？
s_{unitPrice,catalog}仍為500，但因滿足條件的記錄指標在葉節點裡並沒有連續儲存，所以葉節點需造訪bI1_{unitPrice,catalog}/2次，因此成本為 x _{unitPrice,catalog}-1＋bI1_{unitPrice,catalog}/2＋s_{unitPrice,catalog} =3+1000+500 =1503

習題10-5

在第五節第三小節的範例四裡，假設所建立的多欄位索引是 (unitPrice, catalog)，而非 (catalog, unitPrice)。請問利用 (SCI) 來運算的成本為何？

習題10-6
考慮以下的查詢句： SELECT * FROM Product WHERE unitPrice > 500 AND catalog = ‘Book’; 假設 DBMS 裡記載著有約 1/4 的商品為書，有約 1/5 的商品定價高於500。此外，r_Product = 100,000, b_Product = 5,000, x_catalog = 2，bI1_catalog = 100，x_unitPrice = 3,bI1_unitPrice = 1,000，假設 catalog 和 unitPrice 皆非群聚索引。 1. 若利用catalog 的索引結構來處理此查詢句，成本約為多少？ 2. 若利用unitPrice 的索引結構來處理此查詢句，成本約為多少？ 3. 若用資料頁循序搜尋 (SL) 來處理此查詢句，成本約為多少？

習題10-6

考慮以下的查詢句：
SELECT *
FROM Product
WHERE unitPrice > 500 AND catalog = ‘Book’;
假設 DBMS 裡記載著有約 1/4 的商品為書，有約 1/5 的商品定價高於500。此外，r_Product = 100,000, b_Product = 5,000, x_catalog = 2，bI1_catalog = 100，x_unitPrice = 3,bI1_unitPrice = 1,000，假設 catalog 和 unitPrice 皆非群聚索引。
1. 若利用catalog 的索引結構來處理此查詢句，成本約為多少？
2. 若利用unitPrice 的索引結構來處理此查詢句，成本約為多少？
3. 若用資料頁循序搜尋 (SL) 來處理此查詢句，成本約為多少？

習題10-7
考慮以下的查詢句： SELECT * FROM Product WHERE unitPrice > 500; 假設 DBMS 裡記載著有約 1/4 的商品定價高於 500，此外，r_Product = 100,000, b_Product = 5,000, x_catalog = 2，bI1_catalog = 100，x_unitPrice = 3, bI1_unitPrice = 1,000。 1. 若利用資料頁循序搜尋 (SL) 來處理此查詢句，成本約為多少？ 2. 若unitPrice 的索引是群聚索引，則利用 unitPrice 的索引結構來處理此查詢句，成本約為多少？ 3. 若unitPrice 的索引不是群聚索引，則利用unitPrice 的索引結構來處理此查詢句，成本約為多少？

習題10-7

考慮以下的查詢句：
SELECT *
FROM Product
WHERE unitPrice > 500;
假設 DBMS 裡記載著有約 1/4 的商品定價高於 500，此外，r_Product = 100,000,
b_Product = 5,000, x_catalog = 2，bI1_catalog = 100，x_unitPrice = 3, bI1_unitPrice = 1,000。
1. 若利用資料頁循序搜尋 (SL) 來處理此查詢句，成本約為多少？
2. 若unitPrice 的索引是群聚索引，則利用 unitPrice 的索引結構來處理此查詢
句，成本約為多少？
3. 若unitPrice 的索引不是群聚索引，則利用unitPrice 的索引結構來處理此查詢
句，成本約為多少？

習題10-8
考慮以下的查詢句： SELECT * FROM Product WHERE unitPrice > 500 AND catalog = ‘Book’; 假設DBMS 裡記載著有約1/4 的商品為書，有約1/5 的商品定價高於500，此外，r_Product = 100,000, b_Product = 5,000, x_catalog = 2，bI1_catalog = 100，x_{catalog, unitPrice} = 3, x_{unitPrice, catalog} = 3, bl1_{catalog, unitPrice} = bl1_{unitPrice, catalog} = 1,000。其中catalog 為群聚索引，(catalog, unitPrice) 和 (unitPrice, catalog) 皆非群聚索引。 1. 若利用catalog 的索引結構來處理此查詢句，成本約為多少？ 2. 若利用 (catalog, unitPrice) 的索引結構來處理此查詢句，成本約為多少？ 3. 若利用 (unitPrice, catalog) 的索引結構來處理此查詢句，成本約為多少？
預估滿足本查詢的記錄為s=r_Product×1/4×1/5=5,000 1. catalog索引結構搜尋(SIC): x_catalog＋b_Product/4=2＋1,250=1,252 2. (catalog,unitPrice)索引結構搜尋(SCI): x_{catalog,unitPrice}-1＋bI1_{catalog,unitPrice}×1/4×1/5＋s = 2+50+5,000 = 5,052 3. (unitPrice,catalog)索引結構搜尋(SCI): x_{unitPrice,catalog}-1＋bI1_{unitPrice,catalog}/5＋s = 2+200+5,000 = 5,202

習題10-8

考慮以下的查詢句：
SELECT *
FROM Product
WHERE unitPrice > 500 AND catalog = ‘Book’;
假設DBMS 裡記載著有約1/4 的商品為書，有約1/5 的商品定價高於500，此外，r_Product = 100,000, b_Product = 5,000, x_catalog = 2，bI1_catalog = 100，x_{catalog, unitPrice} = 3, x_{unitPrice, catalog} = 3, bl1_{catalog, unitPrice} = bl1_{unitPrice, catalog} = 1,000。其中catalog 為群聚索引，(catalog, unitPrice) 和 (unitPrice, catalog) 皆非群聚索引。
1. 若利用catalog 的索引結構來處理此查詢句，成本約為多少？
2. 若利用 (catalog, unitPrice) 的索引結構來處理此查詢句，成本約為多少？
3. 若利用 (unitPrice, catalog) 的索引結構來處理此查詢句，成本約為多少？

習題10-9
考慮以下的查詢句： SELECT * FROM Product WHERE unitPrice > 500 AND catalog = ‘Book’; 利用以下的哪些索引可以有較低的查詢成本？ A. CREATE INDEX I1 ON Product (unitPrice DESC, catalog) B. CREATE INDEX I2 ON Product (unitPrice ASC, catalog) C. CREATE INDEX I3 ON Product (catalog, unitPrice DESC) D. CREATE INDEX I4 ON Product (catalog, unitPrice ASC)

習題10-9

考慮以下的查詢句：
SELECT *
FROM Product
WHERE unitPrice > 500 AND catalog = ‘Book’;
利用以下的哪些索引可以有較低的查詢成本？
A. CREATE INDEX I1 ON Product (unitPrice DESC, catalog)
B. CREATE INDEX I2 ON Product (unitPrice ASC, catalog)
C. CREATE INDEX I3 ON Product (catalog, unitPrice DESC)
D. CREATE INDEX I4 ON Product (catalog, unitPrice ASC)

習題10-10
假設有一個資料表 R (A1, A2, A3)，並在A1、A2 和 (A2, A1) 分別建立索引，其中A1 的索引為群聚索引，相關資訊如下： r_R = 100,000; b_R = 4,000 x_A1 = 2 d_A1 = 40 x_A2 = 3 bI1_A2 = 500 d_A2 = 1,000 x_{A2, A1} = 4 bI1_{A2, A1} = 1,000 考慮以下的查詢句： SELECT A3 FROM R WHERE A1 > 5 AND A2 = 10,000; 1. 若利用資料頁循序搜尋來處理此查詢句，成本約為多少？ 2. 若利用A1 的索引結構來處理此查詢句，成本約為多少？ 3. 若利用A2 的索引結構來處理此查詢句，成本約為多少？ 4. 若利用 (A2, A1) 的索引結構來處理此查詢句，成本約為多少？
1.b_R=4000 2.x_A1+b_R/2 = 2+2000 = 2002 3. 利用A2的索引結構可找到r_R/d_A2=100個滿足「A2 = 10000」的記錄之指標，這100個記錄之指標僅佔1個葉節點（因為一個A2索引結構的葉節點可容納100000/500=200個記錄指標），故成本為x_A2+r_R/d_A2 = 3+100=103 4. 利用(A2, A1)的索引結構可找到(r_R/d_A2)/2=50個滿足「A1 > 5 AND A2 = 10000」的記錄之指標，這50個記錄之指標僅佔1個葉節點（因為一個(A2, A1)索引結構的葉節點可容納100000/1000=100個記錄指標），故成本為x_A2,A1+r_R/(2•d_A2)=4+50=54

習題10-10

假設有一個資料表 R (A1, A2, A3)，並在A1、A2 和 (A2, A1) 分別建立索引，其中A1 的索引為群聚索引，相關資訊如下：
r_R = 100,000;
b_R = 4,000
x_A1 = 2
d_A1 = 40
x_A2 = 3
bI1_A2 = 500
d_A2 = 1,000
x_{A2, A1} = 4
bI1_{A2, A1} = 1,000
考慮以下的查詢句：
SELECT A3
FROM R
WHERE A1 > 5 AND A2 = 10,000;
1. 若利用資料頁循序搜尋來處理此查詢句，成本約為多少？
2. 若利用A1 的索引結構來處理此查詢句，成本約為多少？
3. 若利用A2 的索引結構來處理此查詢句，成本約為多少？
4. 若利用 (A2, A1) 的索引結構來處理此查詢句，成本約為多少？