Database Reference
In-Depth Information
to a repair
ρ
(
s
)
assigns to each
z
i
the value taken by
t
[
A
j
]
in the database
ρ
(
D
)
,
t
,
A
j
where
is the pair
tuple, attribute
associated with
z
i
. This correspondence may
not hold if the set of aggregate constraints
AC
is not steady, since performing on
D
updates corresponding to a solution of
S
(
D,AC,
D
)
may trigger violations of
S
(
D,AC,
D
)
constraints which were not encoded in
. Our technique exploits the
restrictions imposed on steady aggregate constraints w.r.t. general aggregate con-
straints to accomplish the computation of a repair. As explained above, this approach
does not work for (general) aggregate constraints.
Example 4.2.
Consider the solution of
S
(
D,AC,
D
)
which assigns to each
z
i
the
value
t
i
[
, except for
z
2
,
z
3
,
z
18
, which are assigned 1000, 250, and 1190, re-
spectively. This solution corresponds to the non-minimal repair
Value
]
ρ
2
of Example 2.10.
4.3 Computing Minimal Repairs
Our approach for computing card-minimal repairs is based on the resolution of spe-
cific MILP problems, defined starting from the MILP problem introduced below.
Definition 4.1 (
MILP
(
D,AC,
D
)
). Given a database scheme
D
, a set
AC
of
steady aggregate constraints on
D
, and an instance
D
of
D
,
MILP
(
D,AC,
D
)
is
a MILP of the form:
⎧
⎨
A
×
z
≤
B
w
i
=
z
i
−
v
i
∀
i
∈ I
w
i
−
M
δ
i
≤
0
∀
i
∈ I
−
w
i
−
M
δ
≤
∀
i
∈ I
0
i
z
i
−
M
≤
∀
i
∈ I
0
⎩
−
z
i
−
M
≤
0
∀
i
∈ I
z
i
,
w
i
∈
Q
∀
i
∈ I
Q
z
i
,
w
i
∈
Z
∀
i
∈ I
Z
δ
i
∈{
0
,
1
}
∀
i
∈ I
where:
(i) A
×
z
≤
B is the set of inequalities
S
(
D,AC,
D
)
(z is the vector of variables
z
i
with
i
∈ I
);
(ii) for each
i
,
v
i
is the database value corresponding to the variable
z
i
, that is,
if
z
i
is associated with the pair
∈ I
t
,
A
j
, then
v
i
=
t
[
A
j
]
;
1
, where:
a
is the maximum among the modules of the coeffi-
cients in A and of the values
v
i
, and
m
2
m
+
(iii)
M
=
n
·
(
ma
)
=
|I|
+
r
, and
n
=
2
·|I|
+
r
, where
r
is
the number of rows of A.
I
Q
⊆ I
I
Z
⊆ I
) is the set of the indexes of the variables
z
i
and
w
i
(iv)
(resp.,
defined on the domain
Q
(resp.,
Z
).
Basically, for every solution of
MILP
(
D,AC,
D
)
, the variables
z
i
are assigned
values which satisfy A
×
z
≤
B (that is,
S
(
D,AC,
D
)
). Hence, the variables
z
i
of a
Search WWH ::
Custom Search