Distributed Data Allocation - Physical Database Design - page 367

16.4

Progressive Table Allocation Method

A practical extension of the all-beneficial sites method, called the progressive table alloca-
tion method , allocates the first copy of each table on the basis of maximum value of
benefit-cost. It remembers where that copy is, and bases the next allocation decision on
the location of that first copy and the maximum value of benefit-cost for the remaining
sites. This procedure is continued, one allocation at a time, until benefit no longer
exceeds cost for any of the remaining sites. Note that for this method, cost stays con-
stant for each decision because the update for an additional table is independent of pre-
vious allocations. However, benefit does not stay constant; it decreases each time a new
copy is allocated that is closer to a given site than the previous set of allocations. The
decrease in the benefit at a given site, which must have at least one query to this table, is
measured by the decrease in propagation delay between the former closest copy and the
proposed new copy of the table, relative to that given site. In the worst case, when a new
copy is no closer than any previous copies, the benefit does not increase.
This approach gives a more realistic allocation, based on a progressive set of alloca-
tions, rather than a set of independent allocation decisions. It is also a fast method
because sites where benefit is less than cost need no longer be evaluated in future itera-
tions.
As an example, let us assume that two tables, tab1 and tab2, are to be allocated to
either or both sites S1 and S2. The costs and benefits are computed to be:

tab1 S1 cost = 150 benefit = 200

S2 cost = 170 benefit = 175

tab2 S1 cost = 60 benefit = 30

S2 cost = 50 benefit = 45

Using the all-beneficial sites method, tab1 is allocated to both S1 and S2 because
benefit exceeds cost at both sites, and tab2 is allocated to S2 because it minimizes the
amount by which cost exceeds benefit. Note: It must be allocated at least once, regard-
less of costs and benefits.
Using the progressive table allocation method, tab1 is initially allocated to site S1
where benefit exceeds cost by the greatest amount; and tab2 is initially allocated to site
S2 where the differential between benefit and cost is minimized, even though cost
exceeds benefit at all sites. After this initial mandatory allocation, let us assume the ben-
efit of tab1 at S2 is decreased due to the presence of a copy of tab1 at S1:

tab1 S2 cost = 170 benefit = 165

At this point no further allocations can be made for tab1 (beyond site S1) because
cost now exceeds benefit. This decision is based on more precise data than the all-bene-
ficial sites method, and is more accurate.