Database Reference
In-Depth Information
get refreshed at sufficient rates. Our model of input paths enables us to gain further
insights into the
result staleness
problem. We observe that each input path contains one
or more of these
staleness susceptible states
. Moreover, each susceptible state, say S
CD
,
may receive input from multiple paths. For example, S
CD
gets input from (c
S
D
)and
(d
S
CD
). Thus,
staleness suscepti-
ble states
may be refreshed
synchronously
by allocating resources to the paths covering
those states. The
freshness
predicates can be satisfied by fulfilling the corresponding
refresh rates
of a half-way join (Def. 5) of each
staleness susceptible state
,i.e,ifthe
input rate
S
C
). Also S
CDE
gets input from (cd
S
E
)and(e
λ
j
(
λ
j
for leaf) at each half-way join exceeds the desired R
S
j
.
Definition 5.
The
refresh rate
R
S
j
of a state S
j
, denotes the minimum number of new
tuples required to be inserted per time unit into state S
j
to prevent it from becoming
stale. A
staleness susceptible state
S
j
is said to be covered if its refresh rate R
S
j
is
fulfilled.
Given the foundation, in Problem 2 we translate the
freshness
satisfiability problem into
a
weighted multiple set cover problem (WMSCP)
[18] over the
staleness susceptible
states
. Given the set of all
staleness susceptible states
and the input paths that include
those states, the goal is to identify the set of paths, called the
minimal coverage paths
,
that cover all the
staleness susceptible states
utilizing the
minimum
computing resources
Δμ
μ
μ
Δμ
out of the total
resources. The remaining (
-
) resources are used by GrePP
for throughput optimization. In Fig. 9.a, Path
A
and Path
C
are such
minimal coverage
paths
covering all staleness susceptible states in
4
.
Problem 2.
Coverage of staleness susceptible states as a weighted multiple set cover
problem (WMSCP):
The Universe U consists of m staleness susceptible states = S
1
,
S
2
,...,S
m
with required refresh rates = R
S
1
,R
S
2
,...,R
S
m
, respectively. The k input paths
P=Path
1
,Path
2
,..., Path
k
3
and
k
I
Pa th
I
cover all the staleness susceptible states where
∪
=
1
= U such that each path Path
I
has a positive real cost (resources used) X
I
. If a n-hop
Pa th
I
contains state S
j
, then the resources used for S
j
in Path
I
are denoted as X
j
,such
that for the n states of Path
I
1
X
j
=X
I
.
A k-tuple M = M
1
,M
2
,...,M
k
constitutes a multiple cover for U in which the number
of times state S
j
is covered is defined to be the sum of M
I
's for those Path
I
's which
contain S
j
. Total weight of the
multiple cover
is defined as
n
j
Σ
=
k
I
1
X
I
M
I
. WMSCP seeks
the minimum weight multiple cover for U such that every state S
j
is covered for at least
its refresh rate R
S
j
. By defining b
j
Σ
×
=
Pa th
I
to be 1 if S
j
and 0 otherwise, we can now
write our WMSCP problem as:
k
I
1
X
I
Δμ =
Minimize
Σ
×
M
I
=
subject to:
k
I
1
b
j
×
X
j
×
Σ
M
I
≥
R
S
j
,
∀
j = 1,2,...,m
.
=
Complexity and Optimality Analysis.
WMSCP is strongly NP-Hard and the cost of
an optimal solution may be too high for our dynamically scenario. Thus, we use a
greedy algorithm called
GH-WMSCP
[18]. We use GH-WMSCP to satisfy the refresh
rates and in turn to fulfil
freshness
predicates. The time complexity TC(GH-WMSCP)
