Database Reference
In-Depth Information
Definition 4.4 (
MILP
(
D,AC,W ,
D
)
). Let
D
be a database scheme,
D
be an in-
D
AC
D
W
stance of
,
be a set of steady aggregate constraints on
, and
be a set of
D
.
MILP
(
D,AC,W ,
D
)
steady weak constraints on
is a MILP obtained by assem-
bling the inequality in
MILP
(
D,AC,
D
)
(Definition 4.4) with the of inequalities
⎧
⎨
i
σ
ω,θ
=
K
−
∑
1
c
i
·P
(
χ
i
,θ
)
∀ω ∈ W
and
θ ∈ Θ
(
ω
)
=
−
M
· μ
ω,θ
≤ σ
ω,θ
∀ω ∈ W
and
θ ∈ Θ
(
ω
)
⎩
μ
ω,θ
∈{
0
,
1
}
∀ω ∈ W
and
θ ∈ Θ
(
ω
)
where the constant
M
introduced in Definition 4.4 is recalculated by choosing
m
=
|I|
+
|
r
, where
r
is the number of rows of
the coefficient matrix A and
var
W
is the union of the sets of new variables appearing
in the equations above where
gr
(
W ,
D
)
|
+
r
and
n
=
·|I|
+
|
var
W
|
+
2
σ
ω,θ
is defined.
In the above definition, in order to detect if for a substitution
θ
the ground
weak constraint
θ
(
ω
)
is not satisfied (that is, if
σ
ω,θ
<
0), a new binary vari-
able
μ
ω,θ
is defined. The inequality
−
M
· μ
ω,θ
≤ σ
ω,θ
entails that in a solution
of
MILP
(
D,AC,W ,
D
)
, it is the case that
μ
ω,θ
will have value 1 if
θ
(
ω
)
is not
satisfied, otherwise
μ
ω,θ
is assigned either 0 or 1.
In order to consider only the solutions of
MILP
(
D,AC,W ,
D
)
where each
δ
i
is 0 if
y
i
=
0 and where each
μ
ω,θ
is 0 if
σ
ω,θ
≥
0, we consider the following
optimization problem
OPT
(
D,AC,W ,
D
)
, whose goal is minimizing the weighted
sum of the values assigned to variables
δ
i
and
μ
ω,θ
.
Definition 4.5. Let
D
be a database scheme,
D
be an instance of
D
,
AC
be a set of
steady aggregate constraints on
D
, and
W
be a set of steady weak constraints on
D
.
OPT
(
D,AC,W ,
D
)
:
=
minimize
(
∑
i∈I
W
· δ
+
∑
ω∈W ∧θ∈Θ
(
ω
)
μ
ω,θ
)
i
subject to MILP
(
D,AC,W ,
D
)
where
W
=
|{μ
ω,θ
| ω ∈ W ∧ θ ∈ Θ
(
ω
)
}|
+
μ
ω,θ
1 is the number of variables
incremented by one.
Basically, the objective function of
OPT
(
D,AC,W ,
D
)
entails that it is prefer-
able that some
δ
i
is assigned 0 (i.e., a database value is not updated) with respect to
assign 0 to all
μ
ω,θ
(i.e., all weak constraints are satisfied).
Preferred repairs can be computed by exploiting the following corollary, which
extends Corollary 4.1.
Corollary 4.2.
Let
D
be a database scheme
D
,
AC
be a set of steady aggregate
constraints on
D
,
W
be a set of steady weak constraints on
D
and D be an instance
of
D
. Every (optimal) solution s of OPT
(
D,AC,W ,
D
)
corresponds to a preferred
repair
ρ
(
s
)
for D w.r.t.
AC
and
W
.
It is easy to see that, given an (optimal) solution
s
of
OPT
(
D,AC,W ,
D
)
, the
value
s
[
δ
i
)]
/
W
represents the number of atomic updates performed by any
∑
i
∈I
Search WWH ::
Custom Search