Consistent Answers to Aggregate Queries - Repairing and Querying Databases under Aggregate Constraints - page 48

min z 2 + z 12

⎧
⎨
⎩

2 = ∑ i = ∈I δ w 11 = z 11 − 80 i

z 2 + z 3 = z 4 w 12 = z 12 − 1110

z 5 + z 6 + z 7 = z 8 w 13 = z 13 − 90

z 12 + z 13 = z 14 w 14 = z 14 − 1200

z 15 + z 16 + z 17 = z 18 w 15 = z 15 − 1130

z 4 − z 8 = z 9 w 16 = z 16 − 40

z 14 − z 18 = z 19 w 17 = z 17 − 20

z 1 z 10

z 11 − z 19 = z 20
w 1 = z 1 − 50
w 2 = z 2 − 900
w 3 = z 3 − 100
w 4 = z 4 − 1250
w 5 = z 5 − 1120
w 6 = z 6 − 20
w 7 = z 7 − 80
w 8 =

− z 9 = w 18 1120

w 19 = z 19 − 10
w 20 = z 20 − 90
w i − M 2 δ i ≤ 0 ∀ i ∈ [ 1 .. 20 ]
− w i − M 2 δ i ≤ 0 ∀ i ∈ [ 1 .. 20 ]
z i − M 1 ≤ 0 ∀ i ∈ [ 1 .. 20 ]
− z i − M 1 ≤ 0 ∀ i ∈ [ 1 .. 20 ]
z i , w i ∈ Z ∀ i ∈ [ 1 .. 20 ]
δ i ∈{ 0 , 1 }∀ i ∈ [ 1 .. 20 ]

= z 18 −

z 8 − 1220

w 9 = z 9 − 30

w 10 = z 10 − 80

Instance of OPT SUM
glb

Fig. 5.1 ( D,AC, q 3 , D ) obtained for “Balance Sheet” example

5.3.2 - and -queries

MAX MIN

We now show how range-consistent answer to MAX -queries can be computed. MIN -

queries can be handled symmetrically.
Given a

I

MAX -query q , we denote the set of indices in of the variables z i occur-

ring in T ( q ) as I ( q ) . Let In ( q ) be the following set of inequalities:

⎧
⎨

z j − z i − 2 M · μ i ≤ 0 ∀ j , i ∈ I ( q ) , j = i

) μ i = |I (

q ) |− 1

∑ i ∈I ( q

x i − M · μ i ≤ 0 ∀ i ∈ I ( q )

− x i − M · μ i ≤ 0 ∀ i ∈ I ( q )

z i − x i − 2 M · ( 1 − μ ) ≤ 0 ∀ i ∈ I ( q ) ;

i

In ( q ) : = − z i + x i − 2 M · ( 1 − μ ) ≤ 0 ∀ i ∈ I ( q ) ;

i

⎩

x i − ≤ ∀ ∈ I ( )

M 0 i q ;

− − ≤ ∀ ∈ I ( )

x i M 0 i q ;

x i ∈ Q ∀ ∈ I Q ( )

i q

x i ∈ Z ∀ i ∈ I Z ( q )

μ i ∈{ 0 , 1 } ; ∀ i ∈ I ( q ) ;

where I Q ( q ) ⊆ I ( q ) (resp., I Z ( q ) ⊆ I ( q ) ) is the the set of the indexes of the

variables z i in I ( q ) which are defined on the domain Q (resp., Z ).

Consider the following optimization problem:

MILP ∗ ( D,AC,

D , q )= MILP ( D,AC, D ) ∪{λ = ∑

i

δ i }∪ In ( q )

∈I