Possible Extensions and Open Problems - Repairing and Querying Databases under Aggregate Constraints - page 54

database (the LS-distance is the sum of square differences between new and old
values). For the domains of rationals and integers, it is easy to see that there can be
card -minimal repairs which are not LS-minimal, and vice versa. In the specific case
of attributes defined on the domain

Z

, it can be shown that, in the presence of our

aggregate constraints:

- the MRC problem is still coNP-complete. Basically, the membership derives from

the fact that, in order to disprove the LS-minimality of a given repair whose
distance from the original database is K , it suffices to guess a repair where the
difference between any new value and the corresponding old value is not greater

than √ K . A hint to prove the hardness can be found in [25].

- for the CQA problem, the same characterization provided in [12] holds in our

case. That is, CQA is in

p
2 -hard (to prove this,
the same reasoning used in [12] for characterizing the consistent query answer
problem in the presence of denial constraints can be used, by properly translating
the denial constraints used in their reduction into a set of aggregate constraints
and new relations). Observe that the adoption of the LS-minimality instead of
the card -minimality makes the complexity of CQA increase from

p
2

Π (since MRC is in coNP), and is Δ

p
2

Δ [ log n ] to

p
2 . Intuitively, this derives from the fact that, while the cardinality of
repairs is bounded by a value proportional to the number of tuples in the database
to be repaired, a similar polynomial bound cannot be provided for the distance
of the LS-minimal repairs.

(at least) Δ

- since the LS-distance between a repair and a database is not a linear function,

our strategy for computing a card -minimal repair in terms of a solution of a lin-
ear system of inequalities cannot be exploited to compute an LS-minimal repair.
Devising a strategy for computing an LS-minimal repair in the presence of ag-
gregate constraints remains an open issue.

Q

, the authors of [12] them-
selves observed that LS-minimality seems to be unsuitable in this setting. In fact,
this semantics would prefer repairs consisting of many infinitesimal changes of nu-
meric values, instead of repairs changing a much smaller number of values to appro-
priate (still small) quantities - which is likely to be more reasonable in many cases.
Hence, in this case, when taking into account the differences between the values in
the original and the repaired database is a requirement, a different semantics, which
combines the card - and the LS- minimal semantics, is likely to be more suitable.
Extending the framework presented in this topic to this case is another open issue.
Finally, the strategies for computing minimal repairs and consistent answers pre-
sented in this topic work under the card -minimal semantics only. It would be inter-
esting to devise techniques enabling these computations also under the set -minimal
semantics.

In the case that measure attributes are defined on