Database Reference
In-Depth Information
Corollary 5.1.
Let
D
be a database scheme,
AC
a set of steady aggregate con-
D
D
D
straints on
, q an aggregate query on
, and D an instance of
. Then,
CQA
q
D,AC
(
D
)=
0
iff MILP
(
D,AC,
D
)
has no solution.
Let
q
=
SELECT
f
R
WHERE
α
be an aggregate query over the relation
FROM
scheme
R
, where
f
is one of
MIN
(
A
j
)
,
MAX
(
A
j
)
or
SUM
(
A
j
)
and
A
j
is an attribute of
R
. Given an instance
r
of
R
, we define the translation of
q
as
T
(
q
)=
∑
t
:
t
∈
r
∧
t
|
=
α
z
t
,
A
j
.
5.3.1
-queries
SUM
We now show how to compute range-consistent to aggregate queries involving the
SUM
function. Consider the following optimization MILP problems:
minimize
T
(
q
)
OPT
SUM
glb
(
D,AC,
q
,
D
)
:
=
subject to ILP
(
D,AC,
D
)
∪{λ
=
∑
∈I
δ
i
}
i
maximize
T
(
q
)
OPT
SUM
lub
(
D,AC,
q
,
D
)
:
=
subject to ILP
(
D,AC,
D
)
∪{λ
=
∑
∈I
δ
i
}
i
where
λ
is the cardinality of any card-minimal repair for
D
w.r.t.
AC
, that is, the
value returned by the optimization problem
OPT
(
D,AC,
D
)
. Intuitively enough,
since the solutions of
MILP
(
D,AC,
D
)
correspond to the repairs for
D
w.r.t.
AC
,
the solutions of
MILP
(
D,AC,
D
)
∪{λ
=
∑
i
∈I
δ
i
}
correspond to the repairs whose
λ
cardinality is equal to
, that is,
card
-minimal repairs. Hence, the above-introduced
OPT
SUM
glb
and
OPT
SUM
lub
return the minimum and the maximum value of the query
q
on all the consistent databases resulting from applying
card
-minimal repairs. These
values are the boundaries of the range-CQA of
q
, as stated in the following theorem.
Theorem 5.2.
Let
D
be a database scheme,
AC
a set of steady aggregate con-
straints on
D
,qa
-query on
D
, and D an instance of
D
. Then, either
SUM
i) CQA
q
D,AC
(
D
)=
0
,or
ii) CQA
q
is the value returned by OPT
SUM
glb
D,AC
(
D
)=[
,
u
]
, where
(
D,AC,
q
,
D
)
and u the value returned by OPT
SUM
lub
(
D,AC,
q
,
D
)
.
Example 5.4.
Given the set of steady aggregate constraints
AC
=
{κ
1
,κ
2
,κ
3
}
and
the query
q
3
of our running example,
OPT
SUM
(
D,AC,
q
3
,
D
)
for “Balance Sheet”
glb
is shown in
Fig. 5.1.
Herein,
•
the cardinality of card-minimal repairs
λ
is equal to 2 (as shown in Example 2.12)
•
the objective function encoding
q
3
is
T
(
q
3
)=
z
2
+
z
12
•
M
1
is
eq
ual to the given boun
d
on measure attributes
M
•
M
2
=
M
+
1
+
max
i
∈I
|
v
i
|
=
M
+
1
+
1250.
Search WWH ::
Custom Search