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

card -minimal repair for D w.r.t. rep-

resents minimum number of the ground weak constraints which are not satisfied by
any preferred repair.

AC , whereas the value

∑ ω∈W ∧θ∈Θ ( ω ) s

[ μ ω,θ ]

Example 4.6. The optimization problem OPT ( D,AC,W , D ) obtained for “Bal-

ance Sheet” example, where AC = {κ 1 ,κ ,κ } and W = {ω ,ω } is shown in

2 3 1 2

Fig. 4.2. Herein, the substitutions θ 1 ,...,θ

4 are such that:

20
i = 1 5

min ( ∑ · δ i + μ ω 1 ,θ 1 + μ ω 1 ,θ 2 + μ ω 2 ,θ 3 + μ ω 2 ,θ 4 )

⎧
⎨
⎩

z 2 + z 3 = z 4 w 16 = z 16 − 40

z 5 + z 6 + z 7 = z 8 w 17 = z 17 − 20

z 12 + z 13 = z 14 w 18 = z 18 − 1120

z 15 + z 16 + z 17 = z 18 w 19 = z 19 − 10

z 4 − z 8 = z 9 w 20 = z 20 − 90

z 14 − z 18 = z 19 w i − M δ ≤ 0 ∀ i ∈ [ 1 .. 20 ] i

z 1 − z 9 = z 10 − w i − M δ ≤ 0 ∀ i ∈ [ 1 .. 20 ] i

z 11 − z 19 = z 20 z i − M ≤ 0 ∀ i ∈ [ 1 .. 20 ]

w 1 = z 1 − 50 − z i − M ≤ 0 ∀ i ∈ [ 1 .. 20 ]

w 2 = z 2 − 900 z i , w i ∈ Z ∀ i ∈ [ 1 .. 20 ]

w 3 = z 3 − 100 δ ∈{ 0 , 1 }∀ i ∈ [ 1 .. 20 ] i

w 4 = z 4 − 1250 σ ω 1 ,θ 1 = z 2 − 1000

w 5 = z 5 − 1120 σ ω 1 ,θ 2 = z 12 − 1000

w 6 = z 6 − 20 σ ω 2 ,θ 3 = 200 − z 3

w 7 = z 7 − 80 σ ω 2 ,θ 4 = 200 − z 13

w 8 1220

w 9 = z 9 − 30
w 10 = z 10 − 80
w 11 = z 11 − 80
w 12 = z 12 − 1110
w 13 = z 13 − 90
w 14 = z 14 − 1200
w 15 = z 15 − 1130

= z 8 − − · μ ω 1 ,θ 1 ≤ σ ω 1 ,θ 1

−M· μ ω 1 ,θ 2 ≤ σ ω 1 ,θ 2
−M· μ ω 2 ,θ 3 ≤ σ ω 2 ,θ 3
−M· μ ω 2 ,θ 4 ≤ σ ω 2 ,θ 4
μ ω 1 ,θ 1 ∈{ 0 , 1 }
μ ω 1 ,θ 2 ∈{ 0 , 1 }
μ ω 2 ,θ 3 ∈{ 0 , 1 }
μ ω 2 ,θ 4 ∈{ 0 , 1 }

M

Fig. 4.2 Instance of OPT ( D,AC,W , D ) obtained for “Balance Sheet” example

θ ( ω )= BalanceSheets ( 2008 , Receipts , cash sales , det , 900 )= ⇒

1 1

χ 2 ( 2008 , 'cash sales' ) ≥ 1000

θ 2 ( ω 1 )= BalanceSheets ( 2009 , Receipts , cash sales , det , 1110 )= ⇒

χ 2 ( 2009 , 'cash sales' ) ≥ 1000

θ 3 ( ω 2 )= BalanceSheets ( 2008 , Receipts , receivables , det , 100 )= ⇒

χ 2 ( 2008 , receivables' ) ≤ 200

θ 4 ( ω 2 )= BalanceSheets ( 2009 , Receipts , receivables , det , 90 )= ⇒

χ 2 ( 2009 , receivables' ) ≤ 200