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

ω 1 : BalanceSheets ( x , , , , )= ⇒ χ 2 ( x , 'cash sales' ≥ 1000

ω 2 : BalanceSheets ( x , , , , )= ⇒ χ 2 ( x , 'receivables' ) ≤ 200

where χ 2 is the aggregation function defined in Example 2.1.

Intuitively, a card -minimal repair satisfying n 1 weak constraints is preferred to
any other card -minimal repair satisfying n 2 n 1 weak constraints.

We exploit this ordering criterion implied by weak constraints on the set of card -
minimal repairs to define preferred (card-minimal) repairs , i.e., card -minimal re-
pairs which are the most “reasonable” ones, in the sense that they satisfy as many
weak aggregate constraints as possible.
Let

<

D be a database scheme, D an instance of D , and ω a weak aggregate con-

straint on D having the following form (see Definition 2.1):

x

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

n

∀ φ ( x )= ⇒

We denote the set of ground weak constraints obtained from the instantiation of ω

on D as gr ( ω, D ) . More formally, let Θ ( ω ) be the set of the ground substitutions of

variables in x with constants such that ∀θ ∈ Θ ( ω ) φ ( θ x ) is true on D , set of ground

weak constraints is

gr ( ω, D )= {θ ( ω ) | θ ∈ Θ ( ω ) }

Given a set of weak constraints W on D , we denote as gr ( W , D ) the set of ground

weak constraints obtained from the instantiation of every ω ∈ W on D , i.e.,

gr ( W , D )= { gr ( ω, D ) }

ω∈W

Let ρ be a card -minimal repair for D w.r.t. a set of aggregate constraints AC on D ,

and W be a set of weak constraints on D . We will denote as γ ( ρ,W , D ) the number

of ground weak constraints in gr ( W ,ρ ( D )) which are not satisfied.

Definition 4.3 (Preferred repair). Let D be a database scheme, AC a set of ag-

D W D

, and D an gregate constraints on , a set of weak aggregate constraints on

D

.A card -minimal repair

ρ

for D w.r.t.

D AC

is said to be a pre-

instance of and

ρ for D ferred repair for D w.r.t. AC W

iff there is no card -minimal repair

and

γ ( ρ ,W , w.r.t. D and AC such that D ) < γ ( ρ,W , D ) .

Example 4.5. As explained in Example 2.12, in our running example the set of card -
minimal repairs is

card

ρ

D,AC (

D )= { ρ 1 = { t 2 , Value , 1150 , t 18 , Value , 1190 }

ρ 5 = { t 3 , Value , 350 , t 18 , Value , 1190 }}

Let W = {ω 1 ,ω 2 } be the set of weak constraints introduced in Example 4.4. The

set gr ( W ,ρ 1 ( D )) of ground weak aggregate constraints on the database repaired by