Computing Card-minimal Repairs - Repairing and Querying Databases under Aggregate Constraints - page 34

solution of MILP take values which, once assigned to the corresponding

pairs tuple , attribute , make the database satisfy the aggregate constraints

( D,AC, D )

AC

.
In the definition above, each variable w i represents the difference between the
variable z i associated with a pair

t , A j

and the original database value v i

= t [ A j ]

.
The constant M is introduced for a twofold objective: considering solutions of the
first two inequalities with polynomial size 2 w.r.t. the database size, and building
a mechanism for counting the number of variables z i which are assigned a value
different from the original value of the corresponding pair tuple , attribute . The value
of M derives from a well-known general result shown in [44] regarding the existence
of bounded solutions of systems of linear equalities. In our case, this result implies
that, if the first two (in)equalities of MILP

have at least one solution,
then they admit at least one solution where (absolute) values are less than M . Hence,
the inequalities of MILP

( D,AC, D )

( D,AC, D ) where M occurs entail that:

- MILP has solution iff the first two inequalities have a solution. In par-

ticular, each solution of MILP

( D,AC, D )

can be obtained by taking any solution
of the first two inequalities with values less than M and then properly adjusting
each

( D,AC, D )

δ i ;
-every solution of MILP is of polynomial size w.r.t. the size of the

database. In fact, solutions of the first two inequalities with values larger than M
do not correspond to solutions of MILP

( D,AC, D )

( D,AC, D ) , as, if | w i | > M , there is no

way of choosing δ i to satisfy both w i − M δ i ≤ 0 and − w i − M δ i ≤ 0.

-for every solution of MILP

( D,AC, D )

, the sum of the values assigned to variables
δ i is an upper bound on the number of variables z i different from the correspond-
ing v i . In fact, if w i has a value different from 0 (meaning that z i has a value
different from the “original” v i ) then δ

i is assigned 1. It is easy to see that the
vice versa does not hold, thus this sum does not represent the exact number of
variables z i different from the original values.
For any solution s of MILP

( D,AC, D ) , the value taken by variable z in s will be

denoted as s [ z ] . The above-mentioned properties of MILP ( D,AC, D ) are stated in

the theorem below.

Theorem 4.1. Every solution s of an instance of MILP ( D,AC, D ) one-to-one cor-

responds to a repair ρ ( s ) for D such that:

(i) for each z i associated with the pair t , A j and such that s [ z i ] = t [ A j ] , ρ ( s ) con-

tains the atomic update t , A i , s [ z i ] ;

(ii) ∀ i ∈ I , it is the case that − M ≤ s [ z i ] ≤

M;

(iii) |ρ ( s ) |≤ ∑ i∈I s [ δ ] .

i

Hence, the repair ρ ( s ) defined by solution s of MILP ( D,AC, D ) is such that its

cardinality is bounded by

∑ i∈I δ i and its atomic updates assign values bounded by
M . Card -minimal repairs can be evaluated by exploiting the following optimization
problem.

2 The size of M is polynomial in the size of the database, as it is bounded by log n +( 2 ·m + 1 ) ·
log ( ma ) .