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