Database Reference
In-Depth Information
Definition 4.2. Let
D
be a database scheme,
AC
a set of steady aggregate con-
D
, and
D
an instance of
D
straints on
.
OPT
(
D,AC,
D
)
:
=
minimize
∑
i∈I
δ
i
subject to MILP
(
D,AC,
D
)
, then
there is a
card
-minimal repair for
D
which is
M
-bounded) and Theorem 4.1 en-
tails the following corollary, which provide a strategy for computing
card
-minimal
repairs.
Lemma 3.1 (which ensures that if a repair exists for
D
w.r.t.
D
and
AC
Corollary 4.1.
A repair for D w.r.t.
D
and
AC
exists iff MILP
(
D,AC,
D
)
has at
least one solution. Moreover, the optimal value of OPT
(
D,AC,
D
)
coincides with
the cardinality of any
card
-minimal repair for D w.r.t.
AC
, and every solution s of
OPT
(
D,AC,
D
)
define an M-bounded
card
-minimal repair
ρ
(
s
)
for D w.r.t.
AC
.
obtained for “Balance
Sheet” example is shown in
Fig. 4.1
, where we assume that the domain of attribute
Value
is
Example 4.3.
The optimization problem
OPT
(
D,AC,
D
)
Z
(hence
I
Z
=
{
1
,...,
20
}
and
I
R
=
0).
20
i
min
δ
∑
i
⎧
⎨
⎩
=
1
z
2
+
z
3
=
z
4
w
11
=
z
11
−
80
z
5
+
z
6
+
z
7
=
z
8
w
12
=
z
12
−
1110
z
12
+
z
13
=
z
14
w
13
=
z
13
−
90
z
15
+
z
16
+
z
17
=
z
18
w
14
1200
w
15
=
z
15
−
1130
w
16
=
z
16
−
40
w
17
=
z
17
−
20
w
18
=
z
18
−
1120
w
19
=
z
19
−
10
w
20
=
z
20
−
90
w
i
−Mδ
i
≤
0
=
z
14
−
z
4
− z
8
=
z
9
z
14
− z
18
=
z
19
z
1
− z
9
=
z
10
z
11
− z
19
=
z
20
w
1
=
z
1
−
50
w
2
=
z
2
−
900
w
3
=
z
3
−
100
w
4
=
z
4
−
1250
w
5
=
∀i ∈
[
1
..
20
]
−w
i
−Mδ
i
≤
0
∀i ∈
[
1
..
20
]
z
5
−
1120
z
i
−
M
≤
0
∀
i
∈
[
1
..
20
]
w
6
=
z
6
−
20
−
z
i
−
M
≤
0
∀
i
∈
[
1
..
20
]
w
7
=
z
7
−
80
z
i
,
w
i
∈
Z
∀
i
∈
[
1
..
20
]
w
8
=
z
8
−
1220
δ
i
∈{
0
,
1
}∀
i
∈
[
1
..
20
]
w
9
=
z
9
−
30
w
10
=
z
10
−
80
Fig. 4.1 Instance of
OPT
(
D,AC,
D
)
obtained for “Balance Sheet” example
This problem admits two optimal solutions, where the value of the objective
function is equal to 2. In the first solution,
δ
2
and
δ
18
are equal to 1, whereas the
other
w
20
is 0 except
for
w
2
and
w
18
which are assigned 250 and 60, respectively. In the other solution,
δ
i
are assigned 0. Moreover, the value of each variable
w
1
,...,
Search WWH ::
Custom Search