Database Reference
In-Depth Information
where
λ
is the value returned by
OPT
(
D,AC,
D
)
. It is easy to see that, for every
solution
s
of
MILP
∗
(
D,AC,
D
,
q
)
:
)
(
D,AC,
)
∪{λ
=
∑
i
∈I
δ
}
1
s
can be obtained from a solution of
MILP
D
by ap-
i
propriately setting the new variables
x
i
and
μ
(
)
i
of
In
q
;
2
)
for each
i
∈ I
(
q
)
, the inequalities
z
j
−
z
i
−
2
M
· μ
≤
0 occurring in
In
(
q
)
(where
i
μ
i
can take the value 0 only if
z
i
is not less than every
other
z
j
(that is, if
z
i
has the maximum value among all
z
j
);
j
∈ I
(
q
)
\{
i
}
) imply that
3
)
the equality
∑
i
∈I
(
q
)
μ
i
=
|I
(
q
)
|−
1 occurring in
In
(
q
)
imposes that there must
be exactly one
i
such that
s
[
μ
i
]=
0, while for every
j
=
i
it must be the case that
s
[
μ
j
]=
1;
4
)
considering both the inequalities discussed in 2
)
and 3
)
imposes that, if
s
[
μ
i
]=
0,
then
z
i
takes the max
im
um value among var
iab
les
z
j
;
5
)
the inequalities
x
i
−
M
· μ
i
≤
0 and
−
x
i
−
M
· μ
i
≤
0 impose that
s
[
x
i
]=
0if
s
0. Hence, there is exactly one
i
such that
x
i
is assigned 0 in
s
, and this
i
is such that
z
i
has the maximum value among the variables
z
j
. Observe that
these inequalities do not i
m
pose any restriction on a varia
bl
e
x
i
if
s
[
μ
i
]=
[
μ
i
]=
1.
6
)
the inequalities
z
i
−
x
i
−
2
M
·
(
1
− μ
i
)
≤
0 and
−
z
i
+
x
i
−
2
M
·
(
1
− μ
i
)
≤
0 impose
1.
On the whole, for any solution
s
of
MILP
∗
(
D,AC,
that
s
[
z
i
]
−
s
[
x
i
]=
0if
s
[
μ
i
]=
, there is exactly one
x
i
which is assigned 0, while every other
x
j
is assigned the same value as
z
j
. In partic-
ular, the index
i
such that
s
D
,
q
)
0 corresponds to a variable
z
i
having the maximum
value among all the variables
z
j
. Hence,
[
x
i
]=
)
(
s
[
z
i
]
−
s
[
x
i
])
results in the maxi-
∑
i
∈I
(
q
mum value assigned to variables
z
i
in
s
.
Now, consider the following optimization MILP problems:
minimize
)
(
z
i
−
x
i
)
∑
i
∈I
(
q
OPT
MAX
glb
(
D,AC,
q
,
D
)
:
=
ILP
∗
(
D,AC,
subject to
D
,
q
)
maximize
∑
i
∈I
(
q
)
(
z
i
−
x
i
)
OPT
MAX
lub
(
D,AC,
q
,
D
)
:
=
ILP
∗
(
D,AC,
,
)
subject to
D
q
Basically, the problems above return the maximum and the minimum values
taken by
among all the solutions of
MILP
∗
(
D,AC,
)
(
z
i
−
x
i
)
D
,
q
)
. Since the
∑
i
∈I
(
q
solutions of
MILP
∗
(
D,AC,
D
,
q
)
correspond to the solutions of
MILP
(
D,AC,
D
)
∪
{λ
=
∑
∈I
}
, which in turn encode the
card
-minimal repairs for
D
w.r.t.
AC
, max-
i
imizing (resp., minimizing)
∑
i
∈I
(
q
)
(
z
i
−
x
i
)
means evaluating the maximum (resp.,
minimum) value of the
-query
q
among all the “minimally”-repaired databases.
As a matter of fact, the following theorem states that the boundaries of the range-
CQA of a
MAX
-query
q
are the optimal values returned by the above-introduced
optimization problems.
MAX
Theorem 5.3.
Let
D
be a database scheme,
AC
a set of steady aggregate con-
straints on
D
,qa
-query on
D
, and D an instance of
D
. Then, either
MAX
i) CQA
q
D,AC
(
D
)=
0
,or
Search WWH ::
Custom Search