Exercise 1 EECS, Peking University Exercise in Query Processing.

Presentation on theme: "Exercise 1 EECS, Peking University Exercise in Query Processing."— Presentation transcript:

1 Exercise 1 EECS, Peking University Exercise in Query Processing

2 Exercise 2 EECS, Peking University Buffer ♠ Give an example of a relational-algebra expression and a query-processing strategy in each of the following situations: ♣MRU is preferable to LRU. ♣LRU is preferable to MRU.

3 Exercise 3 EECS, Peking University B+ Tree ♠ Construct a B+-tree for the following set of key values: (2, 3, 5, 7, 11, 17, 19, 23, 29, 31) Assume that the tree is initially empty and values are added in ascending order. Construct B+-trees for the cases where the number of pointers that will fit in one node is as follows: ♣Four ♣Six ♣Eight

4 Exercise 4 EECS, Peking University Liner Hash Table k=4 : The total numbe of bits for Hash function i=2: The maximal number of bits used n=4 : The total # of enties r =3: The total # of elements Usage ratio r/n=1.5, which is lower than 1.55 00 00 01 01 10 10 0001 11 11 0011 假定 Hash 值在使用时从低位考虑 Usgage ratio 的控制阈值为 1.55 在 hash 表当前的状态上增加元素 k0, k1, k2 with h(k0) = 0010, k(k1)=1100, h(k2)=1001 请画出线性 hash 的变化

5 Exercise 5 EECS, Peking University Nested Loop Join ♠ 内存 M = 100+2 memory buffers ♠ R 的数据块 B(R) = 1005 ♠ S 的数据块 B(S) = 507 分析外循环表为 R 或者为 S 的情况下的 IO 代价

6 Exercise 6 EECS, Peking University External Sort ♠ Relation r 的数据块 B(r) =1000, 内存块有 30 块，计 算 r 排序的 IO 代价

7 Exercise 7 EECS, Peking University Division Algorithm ♠ R(A, B), S(B) ，设计一个基于排序的算法，直接实 现 R 除 S

8 Exercise 8 EECS, Peking University Heuristic Plan Optimization ♠ Consider the following SQL query for bank database ♣select T.branch-name from branch T, branch S where T.assets>S.assets and S.branch-city ="Brooklyn" ♠ Write an efficient relational-algebra expression that is equivalent to this query. Justify your choice

9 Exercise 9 EECS, Peking University 问答题 ♠ 为什么说查询优化实现困难，其复杂性来源是什 么？