COMPSCI 351 S1 C : Assignment 4
1. Sort relation Student with StudentIDs
7, 5, 11, 23, 15, 41, 35, 10, 9.
• Assume that the memory can hold up to m = 3 blocks of data, and
• Each block can hold at most 1 record of the relation.
Show the intial runs and passes of the sorting. [4 marks]
2. Below are the vital statistics for four relations, w, x, y, and z.
• w(A,B): nw = 1000, V (w, A) = 20, V (w, B) = 60
• x(B,C): nx = 2000, V (x, B) = 50, V (x, C) = 100
• y(C,F,D): ny = 3000, V (y, C) = 50, V (y, D) = 50
• z(D,E): nz = 4000, V (z, D) = 40, V (w, E) = 100
Estimate the sizes of the results of the following expressions:
(a) w ./ x ./ y ./ z
(d) σC=20(y) ./ z
(e) w ./ y
(g) σA=1 and b=2(w).
3. Consider the same settings of relations in Problem 2. To compute expression w ./ x ./ y ./ z,
(a) List all the equivalent (relational algebra) expressions of w ./ x ./ y ./ z that satisfy the following constraint:
• The expression does not join two relations that form a Cartesian product e.g., ((w ./ x) × z) ./ y will not be
considered since it has a Cartesian product (disjoint attributes of the two relations to be joined).
(b) Estimate the sizes for expression (w ./ x) ./ (y ./ z) including its the intermediate results (w ./ x, y ./ z), and final
results ((w ./ x) ./ (y ./ z)) given that each block holds 20 tuples from any relations. [3 marks]
(c) Estimate the I/O cost of (w ./ x) ./ (y ./ z) under the following settings:
• Each relation (w, x, y, z) occupies 100 blocks,
• The memory has m = 102 pages,
• w ./ x uses one-pass join,
• y ./ z uses one-pass join, and
• (w ./ x) ./ (y ./ z) uses sort (multi-way merge sort) merge join.
4. Consider a relation r(A, B, C, D) that has a clustering index on A and non-clustering indexes on each of the other attributes.
The parameters are br = 1000, nr = 5000, V (r, A) = 20, V (r, B) = 1000, V (r, C) = 5000, and V (r, D) = 500. Give the best
query plan, specifically, index-scan or table-scan followed by a filter step, and the corresponding I/O cost (under the default
uniform distribution assumption), for the following selections (please only count the I/Os for retrieving the underlying tuples):
(a) σA=1 AND B=2 AND D=3r,
(b) σA=1 AND B=2 AND C≥3r,
(c) σA=1 AND B≤2 AND C≥3r.
5. Conflicts in scheduling. Draw the precedence graph of the schedule r2(X), r1(Y ), w2(X), r2(Y ), r3(X), w1(Y ), w2(Y ) of three
transactions T1, T2 and T3 and then show if the schedule is conflict-serializable. [3 marks]
本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！
E-mail: [email protected] 微信:itcsdx