C H A P T E R12
Query Processing
Practice Exercis
12.1Assume(for simplicity in this exerci)that only one tuplefits in a block
and memory holds at most3blocks.Show the runs created on each pass
of the sort-merge algorithm,when applied to sort the following tuples on
thefirst attribute:(kangaroo,17),(wallaby,21),(emu,1),(wombat,13),
(platypus,3),(lion,8),(warthog,4),(zebra,11),(meerkat,6),(hyena,9),
(hornbill,2),(baboon,12).
Answer:We will refer to the tuples(kangaroo,17)through(baboon,12)
using tuple numbers t1through t12.We refer to the j th run ud by the i th
pass,as r i j.The initial sorted runs have three blocks each.They are:
r11={t3,t1,t2}
r12={t6,t5,t4}
r13={t9,t7,t8}
r14={t12,t11,t10}
Each pass merges three runs.Therefore the runs after the end of thefirst
pass are:
r21={t3,t1,t6,t9,t5,t2,t7,t4,t8}
r22={t12,t11,t10}
At the end of the cond pass,the tuples are completely sorted into one
run:
r31={t12,t3,t11,t10,t1,t6,t9,t5,t2,t7,t4,t8}
国际品牌香水排行12.2Consider the bank databa of Figure12.13,where the primary keys are
underlined,and the following SQL query:
1
2Chapter12Query Processing
lect T.branch name
from branch T,branch S
where T.asts>S.asts and S.branch city=“Brooklyn”
Write an efficient relational-algebra expression that is equivalent to this
query.Justify your choice.
Answer:
设计主题怎么写
Query:
T.branch name(( branch name,asts(T(branch)))1T.asts>S.asts
( asts((branch city=’Brooklyn’)(S(branch)))))
This expression performs the theta join on the smallest amount of data
possible.It does this by restricting the right hand side operand of the join
to only tho branches in Brooklyn,and also eliminating the unneeded
attributes from both the operands.
12.3Let relations r1(A,B,C)and r2(C,D,E)have the following properties:r1
has20,000tuples,r2has45,000tuples,25tuples of r1fit on one block,and
30tuples of r2fit on one block.Estimate the number of block transfers and
eks required,using each of the following join strategies for r11r2:
a.Nested-loop join.
b.Block nested-loop join.
c.Merge join.
d.Hash join.
Answer:
r1needs800blocks,and r2needs1500blocks.Let us assume M pages
of memory.If M>800,the join can easily be done in1500+800disk
access,using even plain nested-loop join.So we consider only the ca
where M≤800pages.
a.Nested-loop join:
Using r1as the outer relation we need20000∗1500+800=
30,000,800disk access,if r2is the outer relation we need45000∗
800+1500=36,001,500disk access.
b.Block nested-loop join:
If r1is the outer relation,we need⌈800
M−1⌉∗1500+800disk access,
if r2is the outer relation we need⌈1500
M−1
⌉∗800+1500disk access.
c.Merge-join:
Assuming that r1and r2are not initially sorted on the join key,the to-
tal sorting cost inclusive of the output is B s=1500(2⌈log M−1(1500/M)⌉+
Exercis3
2)+800(2⌈log M−1(800/M)⌉+2)disk access.Assuming all tuples
with the same value for the join attributesfit in memory,the total
cost is B s+1500+800disk access.
d.Hash-join:
We assume no overflow occurs.Since r1is smaller,we u it as the
build relation and r2as the probe relation.If M>800/ need
for recursive partitioning,then the cost is3(1500+800)=6900disk
access,el the cost is2(1500+800)⌈log M−1(800)−1⌉+1500+800
disk access.
12.4The indexed nested-loop join algorithm described in Section12.5.3can be
inefficient if the index is a condary index,and there are multiple tuples with the same value for the join attributes.Why is it inefficient?Describe
a way,using sorting,to reduce the cost of retrieving tuples of the inner
阿凡提的故事relation.Under what conditions would this algorithm be more efficient than hybrid merge join?
Answer:
If there are multiple tuples in the inner relation with the same value for the join attributes,we may have to access that many blocks of the inner relation for each tuple of the outer relation.That is why it is inefficient.
鱼竿怎么绑线
To reduce this cost we can perform a join of the outer relation tuples with just the condary index leaf entries,postponing the inner relation tuple retrieval.The resultfile obtained is then sorted on the inner relation address,allowing an efficient physical order scan to complete the join.
Hybrid merge–join requires the outer relation to be sorted.The above algorithm does not have this requirement,but for each tuple in the outer relation it needs to perform an index lookup on the inner relation.If the outer relation is much larger than the inner relation,this index lookup cost will be less th
an the sorting cost,thus this algorithm will be more efficient.
12.5Let r and s be relations with no indices,and assume that the relations
are not sorted.Assuming infinite memory,what is the lowest-cost way (in terms of I/O operations)to compute r1s?What is the amount of memory required for this algorithm?
Answer:
We can store the entire smaller relation in memory,read the larger relation block by block and perform nested loop join using the larger one as the outer relation.The number of I/O operations is equal to b r+b s,and memory requirement is min(b r,b s)+2pages.
12.6Consider the bank databa of Figure12.13,where the primary keys are
underlined.Suppo that a B+-tree index on branch city is available on relation branch,and that no other index is available.List different ways to handle the following lections that involve negation:
a.¬(branch city<“Brooklyn”)(branch)
4Chapter12Query Processing
b.¬(branch city=“Brooklyn”)(branch)
c.¬(branch city<“Brooklyn”∨asts<5000)(branch)
Answer:
a.U the index to locate thefirst tuple who branch cityfield has
value“Brooklyn”.From this tuple,follow the pointer chains till the
end,retrieving all the tuples.
b.For this query,the index rves no purpo.We can scan thefile
quentially and lect all tuples who branch cityfield is anything
other than“Brooklyn”.
c.This query is equivalent to the query
(branch city≥′Brooklyn′∧asts<5000)(branch)
Using the branch-city index,we can retrieve all tuples with branch-city
value greater than or equal to“Brooklyn”by following the pointer
chains from thefirst“Brooklyn”tuple.We also apply the additional
criteria of asts<5000on every tuple.
12.7Write pudocode for an iterator that implements indexed nested-loop
join,where the outer relation is pipelined.Your pudocode must define
the standard iterator functions open(),next(),and clo().Show what state
information the iterator must maintain between calls.
Answer:Let outer be the iterator which returns successive tuples from
the pipelined outer relation.Let inner be the iterator which returns suc-
cessive tuples of the inner relation having a given value at the join at-
tributes.The inner iterator returns the tuples by performing an index
lookup.The functions IndexedNLJoin::open,IndexedNLJoin::clo and
IndexedNLJoin::next to implement the indexed nested-loop join iterator
are given below.The two iterators outer and inner,the value of the last
read outer relation tuple t r and aflag done r indicating whether the end of
the outer relation scan has been reached are the state information which
need to be remembered by IndexedNLJoin between calls.
IndexedNLJoin::open()
begin
outer.open();
inner.open();
done r:=fal;
()=fal)
move tuple from outer’s output buffer to t r;
el
done r:=true;
end
Exercis5
IndexedNLJoin::clo()
begin
outer.clo();
inner.clo();
end
boolean IndexedNLJoin::next()
begin
while(¬done r)捶背表情包
begin
(t r[JoinAttrs])=fal)
先外后内begin
move tuple from inner’s output buffer to t s;
compute t r1t s and place it in output buffer;
return true;
end
el
withdraw()=fal)
begin
move tuple from outer’s output buffer to t r;
rewind inner tofirst tuple of s;
end
el
done r:=true;
end
return fal;
end
12.8Design sort-bad and hash-bad algorithms for computing the relational
division operation(e Practi Exercis of Chapter6for a definition of the division operation).
Answer:Suppo r(T∪S)and s(S)be two relations and r÷s has to be computed.
李姓名字大全
For sorting bad algorithm,sort relation s on S.Sort relation r on (T,S).Now,start scanning r and look at the T attribute values of thefirst tuple.Scan r till tuples have same value of T.Also scan s simultaneously and check whether every tuple of s also occurs as the S attribute of r,in
a fashion similar to merge join.If this is the ca,output that value of T
and proceed with the next value of T.Relation s may have to be scanned multiple times but r will only be scanned once.Total disk access,after
