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

Theorem 3.4. The complexity of STEADY - RE Z , STEADY - MRC S , and STEADY - CQA S

with S ∈{ card , set } is the same as that of their non-steady versions.

We now address the complexity characterization of STEADY - RE , STEADY - MRC S ,
and STEADY - CQA S in the case of rational measure attributes. We show that the
complexity of some of these problems decreases in the presence of rational measure
attributes.

Rational-variant of Repair Existence

Differently from the case where the numerical domain is , applying the steadiness

restriction in the presence of rational measure attributes makes the repair existence
problem tractable. Basically, this is due to two reasons. On the one hand, the fact that
the aggregate constraints are steady makes it possible to translate STEADY - RE to the
problem of deciding the feasibility of a system of linear inequalities. On the other
hand, the fact that measure attributes are rational makes this system of inequalities
contain rational variables only, which implies that its feasibility can be decided in
polynomial time [33].

Z

Theorem 3.5. STEADY - RE Q is P-complete.

Rational-variant of Minimal-Repair Checking

The complexity of both STEADY - MRC card and STEADY - MRC set is characterized in
the following theorem.

Theorem 3.6. STEADY - MRC card is coNP-complete, whereas STEADY - MRC set is P-
complete.

Although STEADY - MRC card has the same tight lower bound as the corresponding
more general problem MRC card , moving from the card -tothe set -minimal seman-
tics entails a lowering of the complexity of STEADY - MRC in the presence of rational
measure attributes, as STEADY - MRC set becomes tractable. Intuitively, the tractabil-
ity of STEADY - MRC set follows from the fact that a repair

ρ is not set -minimal iff

updating at least one value less than ρ suffices to fix the inconsistency (that is, iff

ρ such that λ ( ρ ) ⊂ λ ( ρ ) |λ ( ρ ) |≤|λ ( ρ ) |− there is a repair and 1). Hence, the

ρ can be decided by solving at most existence of such a repair instances of

STEADY - RE obtained from the instance of STEADY - MRC set by making unchange-
able (through appropriate aggregate constraints) all the measure attributes of the
database but

|λ ( ρ ) |

. Since STEADY - RE is
tractable (Theorem 3.5), it easy to see that the above-described strategy works in
polynomial time.

|λ ( ρ ) |− 1 chosen among those updated by ρ