Database Reference
In-Depth Information
sisting only of constants or single attributes are used. As an example, the con-
straint
( φ (
)= ⇒ χ (
)
K
)
χ (
)=
R
, (
c 1 A 1
x
x
y
where
y
+
c 2 A 2
) (
y
)
can be ex-
( φ (
)=
c 1
pressed as
x
x
· χ
(
y
)+
c 2
· χ
(
y
)
K
)
where
χ
(
y
)=
R
,
A 1
(
y
)
1
2
1
χ
(
)=
R
,
A 2
(
)
and
. On the other hand, when general multiplication on nu-
merical attributes is allowed in attribute expressions, the expressive power of aggre-
gate constraints increases. For instance, the constraint
y
y
2
x
( φ (
x
)= ⇒ χ (
y
)
K
)
,
where
, cannot be expressed by our form of aggregate
constraints. Interestingly, with respect to this extended form of constraints, if, for
each product occurring in the attribute expressions, at most one measure attribute
occurs, then it can be shown that all the complexity results presented in Table 3.1
still hold and our strategy for computing repairs can be extended as well (basically,
this form of products behaves similarly to what happens when the product between
a constant and a single measure attribute is used in our form of constraints). On the
contrary, in the more general case where products between any number of measure
attributes is allowed in the attribute expressions, the complexity results presented
in Table 3.1 are not guaranteed to hold. In particular, the repair existence problem
becomes undecidable in this case. This can be proved by reducing to the repair ex-
istence problem the problem of deciding the solvability of a system of k quadratic
diophantine equations, which was shown to be undecidable in [53], for a fixed k
χ ( y )=
R
, (
A 1
·
A 2
) (
y
)
2.
The interested reader can find a hint on how this reduction can be formalized in [12],
where the repair-existence problem was shown to be undecidable for a class of ag-
gregate constraints less expressive than ours. Indeed, in [12] this result was proved
under combined complexity, but an analogous reasoning can be adapted to work
under data complexity in our case, by exploiting the higher expressive power of
our constraints (which enable conditions relating aggregates evaluated on different
relations to be expressed).
The expressiveness of aggregation functions can be increased also by allowing
them to be evaluated on the Cartesian product of multiple relations. However, this
preserves the validity of the results reported in Table 3.1 (see [25] for details).
Moreover, aggregation functions can be extended by allowing aggregate oper-
ators other than SUM to be used. The COUNT operator can be already expressed
exploiting the SUM operator (see Example 2.8). In the presence of general aggregate
constraints, it can be proved that if only the COUNT operator is used (while SUM is
not allowed), all the results in our framework still hold. However, in the case that the
aggregate constraints are steady and the aggregation functions use only the COUNT
operator, determining the lower bounds of the problems studied in this topic re-
mains an open issue. Another open issue is extending the framework to the case
that the use of other aggregation operators, such as AVG, MIN, MAX, is allowed
in the constraints. In fact, these operators introduce a form of non-linearity, which
makes our strategies for characterizing the complexity of RE , MRC , CQA , and our
linear-programming-based approaches for computing repairs and range-consistent
answers unsuitable.
Finally, an interesting issue which is not covered by the results summarized in
this topic is the problem of extracting reliable information when the data are not
consistent not only w.r.t. aggregate constraints, but also w.r.t. “classical” constraints,
>
Search WWH ::




Custom Search