Repairing and Querying: the Fundamental Decision Problems - Repairing and Querying Databases under Aggregate Constraints - page 26

The main consequence of this lemma regards minimal repairs. That is, the exis-
tence of an

S ρ S ∈{ }

-minimal repair (with card , set ) such that q is true (resp.,

ρ such ρ ( ) S

false) on D implies the existence of a polynomial-size -minimal repair

ρ ( )

that q is true (resp., false) on . This will allow us to restrict the search space

of minimal repairs making a query either true or false to polynomial-size repairs.
Intuitively enough, this property can be exploited to provide an upper bound on the
complexity of the CQA problem for both the set - and card -minimal semantics.
A tight characterization of the complexity of the CQA problem is provided by the
following theorem.

D

p p

2 [

Theorem 3.3. CQA set

2 -complete, whereas CQA card

is Π is Δ log n ] -complete,

where Δ ∈{ Z , Q }

In order to provide tight lower bounds on the complexity of CQA , the analogy
between CQA and the implication problem in belief revision [32] is exploited. The
implication problem is that of deciding whether a formula is true according to the re-
vised theory resulting from applying a revision formula on a given theory. Basically,
the application of a revision formula on a theory results in revising the beliefs by
taking into account more precise or reliable information on the real world. Specifi-
cally, different revision operators can be exploited to revise a given knowledge base,
each of them corresponding to a different semantics ensuring that as much informa-
tion as possible is preserved. For our set - and card -minimal semantics, we rely on
the revision operators introduced by Satoh and Dalal, respectively. The analogy be-
tween the implication problem of IP and CQA is that the knowledge base and the
revision formula of IP can be viewed as a database and a set of constraints of CQA ,
respectively. Technically, the main difference is that in the formulation of IP , the
revision formula is part of the input, while in our formulation of CQA aggregate
constraints are fixed. To prove Theorem 3.3, we defined reductions where both the
knowledge base and the revision formula of an IP instance are translated into the
database D of a CQA instance, where appropriate aggregate constraints of fixed size
are defined.

3.4 RE , MRC and CQA under Steady Aggregate Constraints

In this section, we characterize the complexity of the decision problems introduced
in the previous sections in the case that the aggregate constraints considered are
steady. We will denote as STEADY - RE Δ (resp., STEADY - MRC Δ , STEADY - CQA Δ ),

, the problem RE Δ (resp., MRC Δ , CQA Δ ) in the case that aggregate
constraints are steady. Interestingly, we will show that the “steadiness” of constraints
makes the complexity of some of these problems become sensitive to the domain of
measure attributes. In particular, the following theorem states that the complexity of
the steady-version of these problems does not change w.r.t. the general case in the
case of integer measure attributes.

with Δ ∈{ Z , Q }