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

Theorem 4.2. Let D be a database scheme, AC a set of aggregate constraints on

D , W a set of weak constraints on D , and D an instance of D . The following hold:

- given an integer k, deciding whether there is a preferred repair ρ for D w.r.t. AC

and W such that γ ( ρ,W , D ) ≥ k is in NP, and is NP-hard even in the case that

consist of steady constraints only;
- given a repair

AC and W

ρ for D w.r.t. D and AC , deciding whether ρ is a preferred repair

for D w.r.t. AC and W is in coNP, and is coNP-hard even in the case that AC

and W consist of steady constraints only.

Although steady aggregate constraints are less expressive than (general) aggre-
gate constraints, Theorem 5.1 states that both the preferred-repair existence problem
and the preferred-repair checking problem are hard also in the presence of steady
constraints only.
In this section, we extend the technique presented in Section 4.3 in order to com-
pute preferred repairs for a database w.r.t a set of steady aggregate constraints and
a set of steady weak constraints . This technique is based on a translation of the
preferred-repair evaluation problem into an instance of MILP problem [33]. In par-
ticular, we refine the transformation introduced in Sections 4.2 and 4.3 by adding
an appropriate set of linear inequalities and defining a new objective function, so
that the solutions of the resulting optimization problem one-to-one correspond to
preferred repairs.
In the following we will exploit the notations defined in Sections 4.2 and 4.3.
Given the system of linear inequality MILP

(see Definition 4.4), we
define a new system of linear inequality which takes into account the semantics of
the set

( D,AC, D )

W ρ ( s )

of weak aggregate constraints. Specifically, given a repair corre-

sponding to solution s of MILP

( D,AC, D )

(see Theorem 4.1), we define a mecha-
nism for counting the number of ground weak constraints which are not satisfied by
ρ ( s ) . This is achieved as follows. For each (steady) weak constraint ω ∈ W having

the following form (see Definition 2.1):

x

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

n

∀ φ ( x )= ⇒

and for each ground substitution θ ∈ Θ ( ω ) , we define the variable

n
i = 1 c i ·P ( χ i ,θ )

σ ω,θ = K −

where the summation on the right-hand side derives from the translation of ω w.r.t.

θ , as defined in the third step of Section 4.2. Variables σ ω,θ will be exploited for

detecting whether for the substitution θ ∈ Θ ( ω ) , the weak constraint ω is not satis-

fied: if in a solution s of MILP ( D,AC, D ) , it is the case that σ ω,θ < 0 then the

ground weak constraint . The equations in-

troduced above will be exploited for defining the system of linear (in)equalities
MILP

θ ( ω ) is not satisfied by repair ρ ( s )

( D,AC,W , D ) below.