Solutions Manual
Chapter 15
Section 15.2
Exercise 15.2.1
(a) The pseudocode for the iterator for projection πA1,A2,..,An(R) is as follows:
Open ( )
{
R . Open ( ) ;
}
GetNext ( )
2
(b) The pseudocode for the iterator for distinct δ(R) is as follows:
Open ( )
{
R . Open ( ) ;
GetNext ( )
{
r e p e a t f o r e v e r
}
Close ( )
{
R . C l o s e ( ) ;
Deallocate Search Structure H;
}
(c) The pseudocode for the iterator for grouping γL(R) is as follows:
Open ( )
{
R . Open ( ) ;
{
/∗
∗We are done retrieving tuples. At this point H contains all the
∗groups. We position to the first group in H and return.
∗Note that there may not be any groups (i.e. R is empty), in
∗which case the position will be set to NotFound.
∗/
∗/
xGroup ←H . F i n d ( grouping attributes of x T u p l e ) ;
i f ( xGroup =NotFound )
{
xGroup ←create new group ;
H . I n s e r t ( grouping attributes of xTup le , xGroup ) ;
}
GetNext ( )
{
/∗
∗All groups were created during Open. Note that we did not finalize
∗groups during Open since it is not known when a certain group ends
∗/
i f ( ne x t G r o u p ,NotFound )
{
c u r r G r o u p ←n e x t G r o up ;
Finalize c u r r G r o u p ;
Close ( )
{
/ / note that R was closed already (at completion of Open)
Deallocate Search Structure H;
}
5
(d) The pseudocode for the iterator for set union R∪S is as follows:
Open ( )
{
S . Open ( ) ;
GetNext ( )
{
/∗
∗We first process all tuples in S, then all tuples in R. For each
∗/
i f ( wo rki ng Wit hS =t r u e )/ / if working with S
{
xTuple ←S . Get Nex t ( ) ;
i f ( xTuple ,NotFound ) / / got tuple from S
}
/ / we get here if we are working with R
r e p e a t
{
xTuple ←R . Ge tNe xt ( ) ;
6
}
7
(e) The pseudocode for the iterator for set intersection R∩S is as follows:
Open ( )
{
S . Open ( ) ;
Allocate Search Structure H for tuples of S and
initialize it to empty;
GetNext ( )
{
/ / For each tuple in R, search H. If found, return it.
r e p e a t
}
Close ( )
{
R . C l o s e ( ) ;
Deallocate Search Structure H;
}
8
(f) The pseudocode for the iterator for set difference R–S is as follows:
Open ( )
{
S . Open ( ) ;
Allocate Search Structure H for tuples of S and
initialize it to empty;
}
GetNext ( )
{
/ / For each tuple in R, search H. If not found, return it.
r e p e a t
}
Close ( )
{
R . C l o s e ( ) ;
Deallocate Search Structure H;
}
The pseudocode for the iterator for set difference S–R is as follows:
Open ( )
{
S . Open ( ) ;
∗/
xTuple ←S . Get Nex t ( ) ;
i f ( xTuple =NotFound ) r e t u r n ;/ / S is empty, H will be empty
r e p e a t
{
H . I n s e r t ( xTuple ) ;
xTuple ←S . Get Nex t ( ) ;
}
i f (H . F i n d ( x Tu p l e ) =t r u e )
{
H . D e l e t e ( x T uple ) ;
}
}/ / of repeat forever
}
10
GetNext ( )
{
/∗
∗At this point the only entries in H are the ones we need
Close ( )
{
Deallocate Search Structure H;
}
11
(g) The pseudocode for the iterator for bag intersection R∩S is as follows:
Open ( )
{
S . Open ( ) ;
Allocate Search Structure H for tuples of S and
initialize it to empty; In addition to storing tuples,
xTuple ←S . Get Nex t ( ) ;
i f ( xTuple =NotFound )
{
c u r r T u p l e ←NotFound ; / / early out
S . C l os e ( ) ;
r e t u r n ;
}
r e p e a t
{
H . I n s e r t ( xTuple ) ; / / will either insert new entry with
12
GetNext ( )
{
/∗
∗At this point, we have Search Structure H that has tuples
∗/
i f ( c u r r T u p l e =NotFound )
{
r e t u r n NotFound ;
}
r e p e a t
{
Search H for c u r r T u p l e entry with non-zero counter ;
Close ( )
{
R . C l o s e ( ) ;
Deallocate Search Structure H ;
}
13
(h) The pseudocode for the iterator for bag difference R–S is as follows:
Open ( )
{
}
S . Open ( ) ;
Allocate Search Structure H for tuples of S and
initialize it to empty; In addition to storing tuples,
we keep a counter that represents the number of times
∗/
xTuple ←S . Get Nex t ( ) ;
r e p e a t w h i l e ( x T u p l e ,NotFound ) ;
{
r e t u r n ;
}
14
GetNext ( )
{
/∗
∗For each tuple in R, search H. If not found, return it.
∗If found, check the counter. If counter is zero, return
}
r e p e a t
{
Search H for c u r r T u p l e entry with non-zero counter ;
i f ( entry not found )
{
Close ( )
{
R . C l o s e ( ) ;
}
The pseudocode for the iterator for bag difference S–R is as follows:
Open ( )
{
S . Open ( ) ;
Allocate Search Structure H for tuples of S and
∗/
xTuple ←S . Get Nex t ( ) ;
i f ( xTuple =NotFound ) / / S is empty
{
c u r r T u p l e ←NotFound ; / / early out
S . C l os e ( ) ;
r e t u r n ;
}
u n t i l ( xTuple =NotFound ) ;
S . C l os e ( ) ;
/∗
∗We now read R, and for each R tuple we search H.
}
r e p e a t
{
Search H for xT u p l e entry with non-zero counter ;
i f ( entry found )
}
GetNext ( )
{
/∗
∗At this point the only entries in H we need to return
∗are the ones with the positive counter. The counter also
}
Close ( )
{
Deallocate Search Structure H
}
(i) The pseudocode for the iterator for product R×S is as follows:
Open ( )
{
S . Open ( ) ;
/ / Read all tuples of S and save them into memory
xTuple ←S . Get Nex t ( ) ;
i f ( xTuple =NotFound ) / / S is empty
}
u n t i l ( xTuple ←NotFound ) ;
S . C l os e ( ) ;
R . Open ( ) ;
}
GetNext ( )
{
/∗
∗At this point we have S in memory, so for each tuple read from R
∗we concatenate that tuple with all of the tuples of S. Note that
18
i f ( c u r r T u p l e S =NotFound ) / / S is exhausted
{
}
Close ( )
{
R . C l o s e ( ) ;
}
19
lows:
Open ( )
{
S . Open ( ) ;
Allocate Search Structure H for attributes of Y and
initialize it to empty;
}
GetNext ( )
{
/∗
∗For each tuple in R, search H based on attributes of Y.
∗Return any matching tuples (joined together). Note that
∗there could be multiple tuples that match current R tuple.