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

We will show that both the problems of finding a card -minimal repair and a
preferred repair for a database D w.r.t. a set of steady aggregate constraints

AC

can
be modeled as a MILP 1 (Mixed Integer Linear Programming) problem [33], thus
allowing us to adopt standard techniques addressing MILP problems to accomplish
the computation of reasonable repairs. We point out that translating the problem
of finding a card -minimal repair (as well as that of finding a preferred repair) into
an MILP problem (which is NP -hard) is reasonable, since the search problem we
are considering is NP -hard too. This easily follows from the fact that there is a
straightforward reduction to this problem from the coNP -hard problem STEADY -
MRC card , the steady version of the card -minimal repair checking problem studied
in Chapter 3. In fact, an instance of STEADY - MRC card can be solved by computing
a card -minimal repair for the given database w.r.t. the given set of steady aggregate
constraints, and then comparing its cardinality with that of the repair whose card -
minimality has to be checked.
Our technique for computing card -minimal repairs is introduced in the next two
sections. First, we explain how aggregate constraints can be translated into sets of
inequalities (Section 4.2). Then, we show how this translation can be used to define
a MILP instance which computes the card -minimal repairs (Section 4.3). Later, in
Sections 4.4 and 4.5, we will formalize the concept of preferred repairs, and extend
our technique for computing card -minimal repairs to deal with this kind of repairs.

4.2 Expressing Steady Aggregate Constraints as Sets of
Inequalities

D

, an instance D of

D

In the following we assume that a database scheme , and a

set of steady aggregate constraints AC on D are given. We show how the triplet

D,AC, D can be translated into a set of linear inequalities S ( D,AC, D ) such

that every solution of S ( D,AC, D ) corresponds to a (possibly not-minimal) repair

for D w.r.t. .

We first describe the translation for a single steady aggregate constraint ac having
the following form:

AC

x

i = 1 c i · χ i ( y i ) ≤ K

n

∀ φ ( x )= ⇒

where . The

translation results from the three steps described in what follow. We assume that,
for every relation scheme R in

∀ i ∈ [ 1 .. n ] , the aggregation function χ i ( y ) has the form R i , e i ,α i ( y i )

D

, its instance in D is r .

1

If the domain of numerical attributes is restricted to Z , then it can be formulated as an ILP

problem.