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