r e t u r n joined c u r r T u p l e and matched tuple from H ;
}
/ / We come here if did not find a match; read next tuple in R
c u r r T u p l e ←R . GetNext ( ) ;
Exercise 15.2.2
(a) Projection is not a blocking operator.
(b) Distinct is not a blocking operator.
(f) Set difference can be blocking or not depending on which relation is read
first. For instance, when computing R–S, if S is read into M-1 blocks and
Exercise 15.2.3
If one or both arguments were not clustered, the entries for the Approximate M
required would not change, since the sizes of the relations when copied into des-
Exercise 15.2.4
(a) Read R into memory.
For each tuple x in S:
22
(b) Read S into memory.
For each tuple x in R:
if x joins with any tuples of S that are in memory,
then output x.
(d) Read S into memory.
For each tuple x in R:
if x joins with any tuples of S that are in memory,
then output x.
(e) Read R into memory.
For each tuple x in S:
(f) Read S into memory.
For each tuple x in R:
if x joins with any tuples T of S that are in memory,
then output all those joined tuples.
Otherwise (x does not join with any tuples of S),
pad x with nulls and output it.
(i) Read R into memory.
For each tuple x in S:
if x joins with any tuples T of R that are in memory,
Section 15.3
Exercise 15.3.1
Open ( )
{
m←NotFound ;
R . Open ( ) ;
r←R . GetNext ( ) ;
i f ( r ,NotFound )
{
}
}
24
GetNext ( )
{
i f (m =NotFound ) / / handle the cae when one
{/ / for next tuple in M
R . C l o s e ( ) ;
m←M. G et N e x t ( ) ;
i f (m =NotFound ) / / M exhausted, need to
{/ / read more of S
i f ( S i s c l o s e d ) / / already done with S
{
r e t u r n NotFound ;
}
/ / insert more tuples from S into M
r e t u r n NotFound ;
25
}
}
R . Open ( ) ;
r←R . GetNext ( ) ;
}
}
Exercise 15.3.2
Using the formula: Disk I/O cost =B(S)+B(R)B(S)
M−1
Exercise 15.3.3
Using the formula: Disk I/O cost =B(S)+B(R)B(S)
M−1
We need to find out the value of M, such that the number of disk I/O’s is no
26
Now we have a generic formula which, given some upper bound for the disk I/O
x, will give us the value of M that would be needed.
Exercise 15.3.4
(a) One way to do better than T(R)T(S)
Mwould be to use only one memory
block to read the smallest relation, say S, one block at the time. For each
block read, move only the tuples of S to fill the remaining M-1 blocks of
(b) If larger relation R is unclustered, we could minimize the number of disk
I/O’s for large relations by first using one memory block to read R and fill in
the remaining M-1 blocks of memory with R tuples. Then read the all tuples
27
(c) Similarly to (a), when both relations are large, it is more beneficial to pick
the unclustered relation as an outer relation, to minimize the number of
M. Thus, it is best to pick S as an outer relation of the join.
Exercise 15.3.5
Open ( )
{
R . Open ( ) ;
r←R . GetNext ( ) ;
GetNext ( )
{
i f ( s =NotFound ) / / handle the cae when one
{/ / of the relations is empty
r e t u r n NotFound ;
}
i f ( r =NotFound ) / / R exhausted, reset R
28
{/ / for next tuple in M
R . C l o s e ( ) ;
s←S . G e t N e x t ( ) ;
i f ( s =NotFound )
{
}
Close ( )
{
R . C l o s e ( ) ;
}
Section 15.4
Exercise 15.4.1
(a) Open ( )
{
R . Open ( ) ;
r e p e a t f o r e v e r
{
i f ( t h e r e i s memory l e f t )
29
Ri. Open ( ) ;
ri←Ri. GetNext ( )
M a i n t a i n s e a r c h e d s t r u c t u r e f o r ri
( b a se d on t h e g r o u p i n g a t t r i b u t e s o f L ) ;
}
r e t u r n ;
}
GetNext ( )
{
xT u ple ←g e t s m a l l e s t t u p l e rifrom t h e s e a r c h e d s t r u c t u r e ;
(b) Open ( )
{
R . Open ( ) ;
r e pe a t f o r e v e r
{
R . C l o s e ( ) ;
s av e c u r r e n t s o r t e d s u b l i s t Rit o d i s k
do ( For a l l nc r e a t e d s o r t e d s u b l i s t s )
}
}
}
GetNext ( )
{
xT u ple ←g e t s m a l l e s t t u p l e rifrom t h e s e a r c h e d s t r u c t u r e ;
i f ( xT u ple =NotFound )
{
r e t u r n NotFound ;
Close ( )
31
{
C l o s e a l l s o r t e d s u b l i s t s .
}
(c) Open ( )
{
R . Open ( ) ;
GetNext ( )
{
xT u ple ←g e t t h e s m a l l e s t t u p l e from t h e s e a r c h s t r u c t u r e ;
r e p e a t w h i l e ( x Tupl e d oe s n o t a p p e a r i n b o th R and S )
{
}
(d) Open ( )
{
32
R . Open ( ) ;
C r e a t e t h e s o r t e d s u b l i s t s f o r R ( l o g i c s i m i l a r t o ( a ) ) ;
R . C l o s e ( ) ;
GetNext ( )
{
xT u ple ←g e t t h e s m a l l e s t t u p l e from t h e s e a r c h s t r u c t u r e ;
Count t h e number o f t i m e s x t h e x Tupl e a p p e a r s i n R
( u s i n g GetNext ( ) , which w i l l a l s o r e p l e n i s h t h e memory l i s t ) ;
}
}
Close ( )
{
C l o s e a l l s o r t e d s u b l i s t s .
}
(e) Open ( )
{