Database Reference
In-Depth Information
10.7.6
Exercises for Section 10.7
EXERCISE
10.7.1 How many triangles are there in the graphs of:
EXERCISE
10.7.2 For each of the graphs of
Exercise 10.7.1
determine:
(i) What is the minimum degree for a node to be considered a “heavy hitter”?
(ii) Which nodes are heavy hitters?
(iii) Which triangles are heavy-hitter triangles?
!
EXERCISE
10.7.3 In this exercise we consider the problem of finding squares in a graph.
That is, we want to find quadruples of nodes
a, b, c, d
such that the four edges (
a, b
), (
b, c
),
(
c, d
), and (
a, d
) exist in the graph. Assume the graph is represented by a relation
E
as in
Section 10.7.4
.
It is not possible to write a single join of four copies of
E
that expresses all
possible squares in the graph, but we can write three such joins. Moreover, in some cases,
we need to follow the join by a selection that eliminates “squares” where one pair of op-
posite corners are really the same node. We can assume that node
a
is numerically lower
than its neighbors
b
and
d
, but there are three cases, depending on whether
c
is
(i) Also lower than
b
and
d
,
(ii) Between
b
and
d
, or
(iii) Higher than both
b
and
d
.
(a) Write the natural joins that produce squares satisfying each of the three conditions
above. You can use four different attributes
W
,
X
,
Y
, and
Z
, and assume that there are
four copies of relation
E
with different schemas, so the joins can each be expressed
as natural joins.
(b) For which of these joins do we need a selection to assure that opposite corners are
really different nodes?
!!
(c) Assume we plan to use
k
Reduce tasks. For each of your joins from (a), into how
many buckets should you hash each of
W
,
X
,
Y
, and
Z
in order to minimize the com-
munication cost?
(d) Unlike the case of triangles, it is not guaranteed that each square is produced only
once, although we can be sure that each square is produced by only one of the three
joins. For example, a square in which the two nodes at opposite corners are each
lower numerically than each of the other two nodes will only be produced by the
