《数据库理论与技术》复习题-2008小妖版(4)

(c) for $p in //part

Where ($p//name=”sopke”)and(not($p//name=”tire”)) Return $p

12. Consider the relation PARTS, which has Part# as hash key and which includes

records with the following Part# values: 2369, 3760, 5046, 4871, 5659, 2222, 1821, 1074, 7115, 1620, 2428, 3943, 4750, 3157, 6975, 4981, 9208. The hash function uses 8 buckets, numbered 0 to 7. Each bucket is one disk block and holds two records.

1) Load these records into the file in the given order using the hash function

h1(K)=K mod 8. Calculate the average number of block accesses for a random retrieval on Part#. 2) Now load the records into expandable hash files based on linear hashing. Start with a single disk block, using the hash function h2(K)= K mod 2, and show how the file grows and how the hash functions change as the records are

inserted. Assume that blocks are split whenever an overflow occurs, and show the value of n at each stage. 解:

1)

平均查找代价：(8＋6＊2＋3＋3＋3）/ 17＝1.71 2)

13. Consider a hash-join of two relations R and S having B(R) = 1000 and B(S) =

500. The values in R and S are skewed such that the hash function assigns three times as many tuples to even-numbered hash buckets as to odd-numbered buckets.

1) How much memory would be required to perform the join in two passes? 2) What is the performance of the hash-join given the skewed hashing? 3) How would the performance of using the hash-join compare to using a sorted-merge algorithm?

4) 解： 5) 1。散列连接要用两趟完成，则需要递归划分，对关系s的划分所需趟数估计为

logM?1(b(s))?1，所以有500?(2log99500/100?1)?8502?logM?1500?1，

M=8.9。

6) 对关系r进行划分所需趟数估计为logM?1(b(r))?1，且2?logM?11000?1，M=11。 7) 因为散列算法要求内存满足小的操作对象，所以需要8.9*4KB=35.6KB的内存。 8) 2. 增加分区的个数，使得每个分区的大小（包括该分区上的散列索引在内）小于内存容量。 9) 3.基于散列的算法使用一个散列函数将操作对象分割到桶中，然后操作被分别应用到桶和桶对上能被内存所容纳。基于排序归并连接的算法可对大于内存的关系进行排序，可知在关系以排序的情况下，归并连接是比较可取的。散列和排序在某种意义下是对偶的，因为能用散列实现的连接也可用排序来实现，反之亦然。基于散列的算法常常优于基于排序的算法，我们假设内存能容纳100个块，则用散列连接对S划分为5个划分，则代价为3（1000+500）=4500次块传输，用排序归并对R的排序需

1000?(2log991000/100?1)?2000次快传输，对

S的排序需

500?(2log99500/100?1)?850次块传输，把排序写回磁盘需要1500次块传输，归

并步骤还需1500次块传输以读回数据，因此归并排序总代价为5850次块传输。

14. Assume that the following relation is fragmented horizontally by plant-number:

employee (name, address, salary, plant-number)

Assume that each fragment is stored at the corresponding plant site. Describe a good processing strategy for the following queries issued at the San Jose site.

1) Find all employees at the New York plant.

2) Find the highest-paid employee at New York, Boston, Toronto,

respectively.

3) Find the average salary of all employees.

答：1）a.纽约节点发送查询 ;

b.让纽约节点返回查询结果。

2）a.分别向NewYorl,Boston,Toronto发送查询最高工资员工的请求； b.在所有的节点上计算查询； c.向San Jose返回结果。

3）a.向所有的节点发送查询员工平均工资和人数的请求； b.各个节点将计算结果返回到San Jose；

c.在San Jose对各个节点返回的结果进一步求所有员工工资的平均值； d.返回计算出的结果。

15. Consider a relation T(A, B) that contains 10000 records partitioned onto 5 disks

according to the following strategies:

? Round robin.

? Hash-partition based on hash function (A mod 5)

? Assume the 5 disks corresponding to has values 0, 1, ?, 4 contain

3000, 1500, 1500, 2000, 2000 tuples respectively.

? Range-partition based on vector on B [20, 40, 60, 80]

? Assume the disk responsible for <20 has 1000 records, the one for

[20, 40) has 2000 records, and the other disks in this order have 2000, 2000, 3000 records, respectively.

? No index is created. Assume processing one tuple takes 1ms for any

query.

What are the costs of processing the following queries using each of the above strategies?

1) select * from T

2) select * from T where A = 20

3) select * from T where 20 < A < 30 4) select * from T where 70 < B < 85 Round robin Hash-partiton Range-partition 1 2 3 3 2 2 3 3 3 2 3 3 4 2 3 3

16. Consider the following log where the DPT represents the Dirty Page Table

and TT represents the Transaction Table

Answer the following questions (using the ARIES-like algorithm we studied in class):

1) What is the smallest LSN accessed during the Analysis phase. 2) Fill in the contents of the Dirty Page Table and the Transaction

Table at the end of the Analysis phase. (you may not need all the space we give you)

3) At which LSN does the Redo phase begin?

4) What entries (specify only LSNs) do get undone as part of the

Undo phase?

解:

1)the smallest LSN accessed during the Anaylsis phase is 10 2)see this PageID 1 3 5 8 3)10 4)40, 10

RecLSN 10 40 50 70 XID T1 Status abort LastLSN 90

17. Consider the following natural language description:

John Smith is the author of \John Smith's agent is Mary Jones. John Smith is 35 years old.

The son of Bob Smith is John Smith.

Represent the information in this description as RDF triples . Use the RDF graph format to represent the triples, with labeled ovals and labeled directed arcs. That is, you do not need to use XML syntax to describe the RDF statements. Use sensible label names, but your labels do not need to be in URI syntax.

解：