Database Reference

In-Depth Information

RankConfigurations
(
C
=C
1
,C
2
,
...
,C
n
:configurations)

returns
ranked list of configurations

1

foreach
C
i

∈
C

2

rank(C
i
)=
|{
C
j

∈
C
:C
j
dominates C
i
}|

3

for
i=1
to
n

L
i
=
{
C
∈
C
: rank(C) = i
}

4

5

R = random permutation of L

return
R

6

FIGURE 11.4
Ranking configurations. (Used with permission from Bruno,

N. & Chaudhuri, S. In
Proceedings of the VLDB Journal
, 19, 1, 2010.)

ranking is then obtained by probabilistically choosing a total order consis-

tent with the partial order given by equivalence classes
L
i
(see Figure 11.3d).

We shue elements in each equivalence class to avoid local minima due to

some arbitrary ordering scheme. This step can be implemented as shown in

Figure 11.4. The search strategy relies on the ability to rank configurations at

two specific points. First, in step 3 in Figure 11.2, we pick the transformation

that would result in the most promising configuration. Second, after pruning

the current configuration in step 2 in Figure 11.2, we backtrack to the most

promising configuration that can still be further transformed.

11.2.2 Search Space Pruning

The idea of pruning relies on identifying when future transformations would

not be able to improve the current configuration. To handle multiple con-

straints, we introduce a function

that takes a configuration and the left-

hand-side function
F
of an
ASSERT
clause and returns one of four possible

values (which intuitively represent the “direction” on which
F
moves after

applying transformations to the input configuration). Thus,

D

D
:
configuration
×
function
→{↑
,
↓
,
↔
,
?
}

Recall that for any given configuration
C
∗
, we evaluate the value
F

C
∗
)

by

binding the free variable
C
in
F
(i.e., the objective configuration) with
C
∗
.

The semantics of

(

D(

,

)

C

F

are

⎧

⎨

↑

if
F

(

C
)
≥

F

(

C

)

for all
C
∈

closur e

(

C

)

C
)
≤

)
for all
C
∈

↓

if
F

(

F

(

C

closur e

(

C

)

D(

C

,

F

)
=

⎩

C
)
=

)
for all
C
∈

↔

if
F

(

F

(

C

closur e

(

C

)

?

otherwise

Search WWH ::

Custom Search