Guillaume Feuillade
email: guillaume.feuillade@irit.fr

Andreas Herzig
email: andreas.herzig@irit.fr

Christos Rantsoudis
email: christos.rantsoudis@irit.fr

A Dynamic Logic Account of Active Integrity Constraints

Keywords: active integrity constraints, dynamic logic, propositional assignments

Active integrity constraints have been introduced in the database community as a way to restore integrity based on a set of preferred update actions. We view active integrity constraints as dynamic logic programs and show how several semantics of database repair that were proposed in the literature can be characterised in Dynamic Logic of Propositional Assignments DL-PA. We moreover propose a new definition of repair which makes use of the programs of Dynamic Logic to provide repair solutions based on an iterating procedure. After an analysis of their properties and a comparison to the previous approaches, we provide complexity results for the problem of existence of these new repairs. Furthermore, an extension on databases with history is explored and the behavior of the various repairs is adjusted to work in this setting. For all these definitions we provide DL-PA counterparts of reasoning and decision problems, such as the existence of a repair or the existence of a unique repair.

Introduction

One of the most important (but notoriously difficult) issues in the database and AI literature is the problem of updating a database under a set of integrity constraints. The latter are usually expressed by logical formulas and their role is to impose conditions that every state of the database must satisfy. In the course of database maintenance several changes are applied to the databases and checking whether these constraints are no longer satisfied is of the highest priority. When a database fails to satisfy the integrity constraints, it has to be repaired in order to restore integrity. Given a database, the procedure of repairing and restoring its consistency with respect to a set of integrity constraints has been extensively studied in the last decades [START_REF] Abiteboul | Updates, A New Frontier[END_REF][START_REF] Ceri | Automatic Generation of Production Rules for Integrity Maintenance[END_REF][START_REF] Bertossi | Database Repairing and Consistent Query Answering[END_REF]. Apart from the problem of finding a repair though, a significant part of the research has focused on the distinction between which types of repairs are more suitable for integrity maintenance, given the fact that the number of all possible repairs can be remarkably large. A number of different types of repairs came into fruition, with one of the most prevalent being the ones based on the minimality of change principle [START_REF] Winslett | Updating Logical Databases[END_REF][START_REF] Herzig | Propositional Belief Base Update and Minimal Change[END_REF][START_REF] Chomicki | Minimal-change integrity maintenance using tuple deletions[END_REF]. Despite this, however, the need to have 'more informed' ways of maintaining database integrity arose.

In light of this, active integrity constraints were proposed as an extension of integrity constraints (or static constraints) with update actions, each one suggesting the preferred update method when an inconsistency arises between the database and a constraint [START_REF] Flesca | Active integrity constraints[END_REF][START_REF] Caroprese | Active Integrity Constraints for Database Consistency Maintenance[END_REF][START_REF] Caroprese | Active integrity constraints and revision programming[END_REF][START_REF] Cruz-Filipe | Optimizing Computation of Repairs from Active Integrity Constraints[END_REF]. For example, the integrity constraint (∀X)[A(X) → B(X)] can be extended to the active constraint (∀X)[A(X)∧¬B(X) → -A(X)], indicating that any violation of the formula A(X) → B(X) should be reacted to by making A(X) false (instead of making B(X) true). In the propositional case, an active integrity constraint can be represented as a couple r = C(r), R(r) where C(r) is a Boolean formula (called the static part of r and denoting a static constraint) and R(r) is a set of update actions, each of which is of the form +p or -p for some atomic formula p. The idea is that (1) when C(r) is false then the constraint r is violated and (2) a violated constraint can be repaired by performing one or more of the update actions in R(r). The two most prevalent types of repairs w.r.t. a set of active integrity constraints are the founded and the justified repairs. Note that while these approaches can greatly reduce the number of possible repairs, the choice between different repair procedures can still lead to different sets of possible repairs or even no repairs at all (for example when R(r) is the empty set). Now, although the setting of active integrity constraints is well established and thoroughly explored, there exist cases where even founded and justified repairs cannot provide a satisfactory solution. Recent approaches have also exhibited that the debate about the 'right' semantics is not yet entirely settled [START_REF] Bogaerts | Fixpoint semantics for active integrity constraints[END_REF]. In our opinion, a more dynamic procedure could provide solutions to inconsistencies that arise between a database and a set of active constraints that build upon and extend one another. We showcase such an example in the following scenario. Consider a company with two departments, D 1 and D 2 , where temporary employees (e.g. interns) are assigned to D 1 and permanent employees work at D 2 (so D 1 has no permanent members and D 2 has no temporary members). Every employee must be in a department, i.e., we have the integrity constraint D 1 ∨ D 2 . Furthermore, consider that every person working on D 2 has previously worked on D 1 , i.e., D 1 is like a 'training ground' for becoming a permanent member. Consider now a database for permanent members which keeps track of their status. Every employee should be declared in the database as starting to work on D 1 and we can express this by the active constraint D 1 ∨ D 2 , +D 1 which declares that if D 1 ∨ D 2 is violated and an employee is not assigned to any department then s/he should be assigned to D 1 . Furthermore, since the database is for permanent employees, if an employee is assigned only to D 1 then this should be rectified by assigning them to D 2 as well. This is expressed by the active constraint ¬D 1 ∨ D 2 , +D 2 . Finally, consider that the database loses track of an employee, i.e., a permanent employee is declared as working at neither D 1 nor D 2 . How would the status of this employee, which is inconsistent w.r.t. the active constraints, be repaired according to the available repair procedures? Whereas founded and justified repairs cannot provide a solution to this problem (see Section 2.3.2 for more details), a dynamic procedure which would check each active constraint at a time and apply an update action before repeating seems able to do so. Indeed, as we will witness in Section 5.2, the set {+D 1 , +D 2 } will be the only solution using such a dynamic procedure. Note also that a repair which conforms to the minimal change principle would suggest that {+D 2 } should be the only repair. While this is indeed the only minimal solution, it can be argued that it should not be the case that this employee was assigned to D 2 directly, without having worked on D 1 first.

In this paper we examine active integrity constraints in the framework of dynamic logic and argue that they can be viewed as particular programs: the sequential composition of the test of C(r) and the nondeterministic choice of an action in R(r). Repairing a database can then be done by means of a complex program that combines active integrity constraints. We use a simple yet powerful dialect of dynamic logic: Dynamic Logic of Propositional Assignments, abbreviated DL-PA [START_REF] Herzig | A Dynamic Logic of Normative Systems[END_REF][START_REF] Balbiani | Dynamic Logic of Propositional Assignments: A Well-Behaved Variant of PDL[END_REF][START_REF] Balbiani | DL-PA and DCL-PC: model checking and satisfiability problem are indeed in PSPACE[END_REF]. The latter is a simple instantiation of Propositional Dynamic Logic PDL [START_REF] Harel | Dynamic Logic[END_REF][START_REF] Harel | Dynamic Logic[END_REF]. Instead of PDL's abstract atomic programs, the atomic programs of DL-PA are update actions: assignments of propositional variables to either true or false, written p← and p←⊥. Just as in PDL, these atomic programs can be combined by means of program operators: sequential and nondeterministic composition, finite iteration and test. The language of DL-PA has not only programs, but also formulas. While DL-PA programs describe the evolution of the world, DL-PA formulas describe the state of the world. In particular, formulas of the form π ϕ express that ϕ is true after some possible execution of π, and [π]ϕ expresses that ϕ is true after every possible execution of π. The models of DL-PA are considerably simpler than PDL's Kripke models: valuations of classical propositional logic are enough. The assignment p← inserts p, while the assignment p←⊥ deletes p. Apart from being simple yet quite expressive, its biggest computational advantage over PDL comes in the form of the elimination of the Kleene star: it is shown in [START_REF] Herzig | A Dynamic Logic of Normative Systems[END_REF][START_REF] Balbiani | Dynamic Logic of Propositional Assignments: A Well-Behaved Variant of PDL[END_REF] that every DL-PA formula can be reduced to an equivalent Boolean formula (something that is not possible in PDL). This is an important attribute and a very useful tool, as it will allow us to construct repaired databases syntactically. The most significant advantage of using a dynamic logic framework though is the fact that we can easily study extensions (like the history-based repairs of Section 7) that are expressible in the language by simply extending the formulas in the appropriate ways. Last but not least, just as in [START_REF] Caroprese | Active integrity constraints and revision programming[END_REF][START_REF] Cruz-Filipe | Optimizing Computation of Repairs from Active Integrity Constraints[END_REF][START_REF] Bogaerts | Fixpoint semantics for active integrity constraints[END_REF] we only consider ground constraints in the current paper, i.e., we work with a propositional language.

The paper is organized as follows. In Section 2 we provide a thorough background on all the aforementioned points: the logic DL-PA, static and active constraints, as well as the associated repairs for both (weak repairs, PMA repairs, founded and justified repairs). In Section 3 we provide an embedding of the associated repairs of static constraints (weak repairs and PMA repairs) into DL-PA. In Section 4 we do the same for the associated repairs of active constraints (founded and justified repairs). Section 5 comprises the main contribution of the paper: we propose some new definitions of repairs in terms of while programs and compare them with the aforementioned founded and justified repairs in various ways. Their computational complexity is investigated in Section 6. In Section 7 we push the envelope of the active constraint paradigm and examine databases with history as well as how the various repairs are integrated in their framework. Finally, Section 8 concludes with some examples of related reasoning problems and a brief discussion on future work. This paper extends [START_REF] Feuillade | A Dynamic View of Active Integrity Constraints[END_REF] by the analysis of justified repairs, a thorough discussion on the dynamic repairs introduced as well as how they compare with the available repair procedures from the literature, a complexity analysis and a look into databases with history.

Background

We consider languages of classical propositional logic, built from a countable set of propositional variables (alias atomic formulas) P = {p, q, . . .}. Boolean formulas are built from P by means of the Boolean operators , ⊥, ¬, and ∨ and are denoted by A, B, etc. The other Boolean connectives ∧, →, and ↔ are abbreviated in the usual way. A literal is an element of P or the negation of an element of P and a clause is a disjunction of literals.

Valuations are subsets of P and are denoted by V, V 1 , V 2 , etc. The set of all valuations is therefore V = 2 P . It will sometimes be convenient to write V(p) = instead of p ∈ V and V(p) = ⊥ instead of p V. A valuation determines the truth value of every Boolean formula. The set of valuations where A is true is denoted by ||A||. We sometimes write V | = A when V ∈ ||A||. In the context of the present article a valuation is called a database.

An update action is of the form p← and p←⊥, for p ∈ P. The former is the insertion of p and the latter is the deletion of p. We denote the set of all update actions by U. We sometimes use X as a metavariable for and ⊥ and write p←X. For subsets P of P it will be convenient to write P← to denote the set of update actions {p← : p ∈ P}, and likewise for P←⊥. A set of update actions U ⊆ U is consistent if it does not contain both p← and p←⊥, for some p. The update of a valuation V by a set of update actions U is defined as:

V U = V \ {p : p←⊥ ∈ U} ∪ {p : p← ∈ U}
So all the deletions are applied first, followed by the application of all insertions. We could as well have chosen another order of application. When U is consistent then all of them lead to the same result. In particular: Proposition 2.1. Let {α 1 , . . . , α n } be a consistent set of update actions. Let k 1 . . . k n be some permutation of 1 . . . n . Then V {α 1 , . . . , α n } = . . .

(V {α k 1 }) . . . {α k n }.
In the following subsections, we recall Dynamic Logic of Propositional Assignments and the definitions of the various repair procedures w.r.t. static and active integrity constraints.

Dynamic Logic of Propositional Assignments

The first studies of assignments in the context of dynamic logic are due, among others, to Tiomkin and Makowski and van Eijck [START_REF] Tiomkin | Propositional Dynamic Logic with Local Assignments[END_REF][START_REF] Van Eijck | Making Things Happen[END_REF]. Dynamic Logic of Propositional Assignments DL-PA was introduced in [START_REF] Herzig | A Dynamic Logic of Normative Systems[END_REF] and was further studied in [START_REF] Balbiani | Dynamic Logic of Propositional Assignments: A Well-Behaved Variant of PDL[END_REF][START_REF] Balbiani | DL-PA and DCL-PC: model checking and satisfiability problem are indeed in PSPACE[END_REF] 1 . Evidence for its widespread applicability was provided in several recent publications, including belief update and belief revision, argumentation, planning and reasoning about knowledge [START_REF] Herzig | Belief Change Operations: A Short History of Nearly Everything, Told in Dynamic Logic of Propositional Assignments[END_REF][START_REF] Doutre | A Dynamic Logic Framework for Abstract Argumentation[END_REF][START_REF] Herzig | On the revision of planning tasks[END_REF][START_REF] Herzig | Epistemic Boolean Games Based on a Logic of Visibility and Control[END_REF][START_REF] Cooper | A Simple Account of Multi-Agent Epistemic Planning[END_REF][START_REF] Charrier | A Succinct Language for Dynamic Epistemic Logic[END_REF]. We briefly recall syntax and semantics of DL-PA.

Language

The language of DL-PA is defined by the following grammar:

ϕ p | | ⊥ | ¬ϕ | ϕ ∨ ϕ | π ϕ π α | π; π | π ∪ π | π * | π -| ϕ?
where ϕ are the formulas of DL-PA, π are the programs of DL-PA, p ranges over the set of atomic formulas P and α ranges over the set of update actions U. In DL-PA, update actions are singletons and are called atomic assignments. The operators of sequential composition ";", nondeterministic composition "∪", finite iteration (the so-called Kleene star) "(.) * " and test "(.)?" are the familiar operators of PDL. The operator "(.) -" is the converse operator. The formula π ϕ is read "there is an execution of π after which ϕ is true". So e.g. p←⊥ -(p ∧ q) expresses that p ∧ q is true after some execution of p←⊥ -, i.e., p ∧ q was true before p was set to false. The star-free fragment of DL-PA is the subset of the language made up of formulas without the Kleene star. We define P ϕ to be the set of variables from P occurring in formula ϕ, and we define P π to be the set of variables from P occurring in program π. For example, P p←q∪p←¬q = {p, q} = P p←⊥ q .

Several program abbreviations are familiar from PDL. First, skip abbreviates ? and fail abbreviates ⊥?. Second, if ϕ then π 1 else π 2 is expressed by (ϕ?; π 1 ) ∪ (¬ϕ?; π 2 ). Third, the loop while ϕ do π is expressed by (ϕ?; π) * ; ¬ϕ?. The nondeterministic composition α∈U α equals fail when U is empty. We also define π + to be π; π * . Let us moreover introduce assignments of literals to variables by means of the following two abbreviations: p←q = if q then p← else p←⊥ p←¬q = if q then p←⊥ else p←

The former assigns to p the truth value of q, while the latter assigns to p the truth value of ¬q. In particular, the program p←¬p flips the truth value of p. Note that both abbreviations have constant length, namely 14. Finally and as usual in modal logic, π ϕ abbreviates ¬ π ¬ϕ.

Semantics

DL-PA programs are interpreted as relations between valuations. The atomic programs α update valuations in the usual way (see the beginning of the section) and complex programs are interpreted just as in PDL by mutual recursion.

||p|| = {V : p ∈ V} ||α|| = V 1 , V 2 : V 2 = V 1 {α} || || = V = 2 P ||π; π || = ||π|| • ||π || ||⊥|| = ∅ ||π ∪ π || = ||π|| ∪ ||π || ||¬ϕ|| = 2 P \ ||ϕ|| ||π * || = ||π|| * ||ϕ ∨ ψ|| = ||ϕ|| ∪ ||ψ|| ||π -|| = ||π|| -1 || π ϕ|| = V : ∃V 1 s.t. V, V 1 ∈ ||π|| and V 1 ∈ ||ϕ|| ||ϕ?|| = V, V : V ∈ ||ϕ||
if p does not occur in ϕ then ϕ → p← ϕ and ϕ → p←⊥ ϕ are valid. This is due to the following semantical property that is instrumental in the proof of several results in the rest of the paper.

Proposition 2.2. Let P be a subset of P. Suppose that P ϕ ∩ P = ∅, i.e., none of the variables of P occurs in ϕ.

Then V ∪ P ∈ ||ϕ|| iff V \ P ∈ ||ϕ||.
As already mentioned in the introductory section, a distinguishing feature of DL-PA is that its dynamic operators can be eliminated (which is not possible in PDL). Just as for QBF, the resulting formula may be exponentially longer than the original formula.

Theorem 2.3. ( [START_REF] Balbiani | Dynamic Logic of Propositional Assignments: A Well-Behaved Variant of PDL[END_REF], Theorem 1) For every DL-PA formula there is an equivalent Boolean formula.

For example, the DL-PA formula p←⊥ (¬p ∧ ¬q) is equivalent to the formula p←⊥ ¬p ∧ p←⊥ ¬q, which is in turn equivalent to ∧ ¬q. Therefore, the DL-PA formula p←⊥ (¬p ∧ ¬q) reduces to the Boolean formula ¬q.

Every assignment sequence α 1 ; . . . ; α n is a deterministic program that is always executable: for a given V, there is exactly one V such that V, V ∈ ||α 1 ; . . . ; α n ||. Moreover, the order of the α i in a sequential composition is irrelevant when the set of update actions {α 1 , . . . , α n } is consistent. The following can be viewed as a reformulation of Proposition 2.1 in terms of the DL-PA operator of sequential composition. Proposition 2.4. Let {α 1 , . . . , α n } be a consistent set of update actions. Let k 1 . . . k n be some permutation of 1 . . . n . Then V {α 1 , . . . , α n } equals the unique V such that V, V ∈ ||α k 1 ; . . . ; α k n ||. This entitles us to use sets of consistent update actions as programs: one may suppose that this stands for a sequential composition in some predefined order (based e.g. on the enumeration of the set of propositional variables).

Static constraints and the associated repairs

In this subsection we consider the classical notion of database integrity that is defined in terms of static integrity constraints, or static constraints for short. In our propositional language they are nothing but Boolean formulas. Two ways of repairing databases based on such constraints can be found in the literature [START_REF] Caroprese | Active integrity constraints and revision programming[END_REF]. Both consist in first finding an appropriate set of update actions U and then building the update V U of V by U as defined in the beginning of the section. We relate them to wellknown operations in belief revision and update [START_REF] Katsuno | On the difference between updating a knowledge base and revising it[END_REF], which allows us to reuse their embeddings into DL-PA [START_REF] Herzig | Belief Change Operations: A Short History of Nearly Everything, Told in Dynamic Logic of Propositional Assignments[END_REF].

Weak repairs and drastic updates

Let V be a database, U a set of update actions and C a set of static constraints, i.e., a set of Boolean formulas. In the rest of the paper we will only consider finite sets of static constraints. We say that U is relevant w.r.t. V iff p← ∈ U implies p V and p←⊥ ∈ U implies p ∈ V. The definition of a weak repair immediately follows.

Definition 2.5. Let V be a database and let C be a set of static constraints. A weak repair of V achieving C is a consistent set of update actions U ⊆ U such that V U | = C and U is relevant w.r.t. V.

The next example illustrates that weak repairs are indeed very weak.

Example 2.6. Let V = ∅ and C = {p∨q}. The weak repairs of V achieving C are all those subsets of the set of positive update actions {r← : r ∈ P} that contain either p← , or q← , or both.

As the following result shows, if we consider what is true in all possible weak repairs then we obtain what is called a drastic update in the literature on belief revision and update. 2Proposition 2.7. Let V be a database and let C be a set of static constraints. Then:

V U : U is a weak repair of V achieving C = C
Note that a weak repair may contain assignments of variables that do not occur in C. To witness, in the above example {p← , q← , r← } is a weak repair of V achieving C. To remedy this we consider every weak repair U from now on to be such that if p← or p←⊥ occurs in U then p ∈ P C , where P C is the set of variables from P occurring in C. This corresponds to a very basic update semantics that is sometimes called Winslett's standard semantics [START_REF] Winslett | Updating Logical Databases[END_REF][START_REF] Herzig | Propositional Belief Base Update and Minimal Change[END_REF].

Repairs tout court and their relation to Winslett's PMA

We now present the definition of a repair which, as we already mentioned, uses the principle of minimal change to produce repair solutions that are considered more practical in contrast to the more general weak repairs. Definition 2.8. Let V be a database and let C be a set of static constraints. A repair of V achieving C is a weak repair of V achieving C that is minimal w.r.t. set inclusion: there is no weak repair of V achieving C that is strictly contained in it.

The next example is a follow-up to Example 2.6.

Example 2.9. Let V = ∅ and C = {p∨q}. There are exactly two repairs of V achieving C, viz. {p← } and {q← }.

We are now going to relate repairs to Winslett's possible models approach PMA [START_REF] Winslett | Reasoning about Action Using a Possible Models Approach[END_REF][START_REF] Winslett | Updating Logical Databases[END_REF]. Remember that the update of a database V by a Boolean formula A according to the PMA is the set of valuations V such that V | = A and such that the symmetric difference between V and V is minimal w.r.t. set inclusion. Formally, the symmetric difference is defined as D(V, V ) = {p : V(p) V (p)} and the PMA update of V by A is the set:

V : V | = A and there is no V ∈ ||A|| such that D(V, V ) ⊂ D(V, V )
For example, the PMA update of ∅ by p∨q is {p}, {q} and the PMA update of ∅ by (p∧q)∨r is {p, q}, {r} . Proposition 2.10. Let V be a database and let C be a set of static constraints. Then:

V U : U is a repair of V by C is the PMA update of V by C
The above result justifies the term PMA repair that we are going to employ henceforth (because the mere term 'repair' might lead to confusions).

Active constraints and the associated repairs

Active integrity constraints were proposed more than ten years ago [START_REF] Flesca | Active integrity constraints[END_REF] and various ways of repairing a database V by such constraints were studied in the literature. We refer to [START_REF] Caroprese | Active integrity constraints and revision programming[END_REF] for an overview. Just as for static constraints, all definitions are based on the notion of a repair set: an appropriate set of update actions U such that V U no longer violates the integrity constraints. V U is once again the result of updating V by U as defined in the beginning of the section and is called the repaired database.

In the present subsection we recall syntax and semantics of the two main routes that have been explored in the literature.

Active integrity constraints

An active integrity constraint (or active constraint for short) combines a static integrity constraint with a set of preferred repair actions. Definition 2.11. An active constraint is a couple r = C(r), R(r) , where C(r) is a Boolean formula and R(r) is a finite set of update actions that is consistent.

As before, C(r) is a static integrity constraint that is violated when C(r) is false. If this is the case and R(r) ∅ then r is applicable and R(r) indicates how to get rid of the violation and restore integrity. The elements of R(r) are viewed as permitted update actions: when C(r) is violated then each of the actions in R(r) gets a 'license to update'. This is a rather imprecise description of the job the update actions in R(r) are expected to do and in the literature various semantics were proposed. One of the most prominent of them are founded repairs which make use of the foundedness condition in order to apply the correct update actions, while justified repairs build upon and refine this condition in order to tackle the so-called circularity of support issue that can be witnessed by founded repairs.

We say that an active constraint r = C(r), R(r) is standard if C(r) is a clause and each update action in R(r) makes one of the literals of C(r) true: if p← ∈ R(r) then p has to be one of the literals of C(r) and if p←⊥ ∈ R(r) then ¬p has to be one of the literals of C(r).

Remark 2.12. The definition in the literature differs in several respects from ours here. First, C(r) is usually not viewed as a static integrity constraint but as the negation of a static integrity constraint: r is violated when the first component of r is true. Second, active constraints are denoted by C(r) → R(r), which makes them look like formulas. However, "→" is different from material implication as the right hand side of the implication is not a formula but a set of programs. So their semantics remains to be given: in the literature this is typically done by means of disjunctive logic programs under a non-monotonic semantics. Third, all active constraints have to be standard.

We denote finite sets of active constraints by η, η 1 , etc. The set of static integrity constraints associated with η is defined as

C(η) = {C(r) : r ∈ η}. Furthermore, the size of C(η), denoted by | C(η) |, is the sum of the lengths of each C(r) for all r ∈ η, i.e., | C(η) | = r∈η | C(r) |, where | C(r) | is the length of the Boolean formula C(r) as defined in propositional logic.
It remains to give a semantics to active constraints. In the rest of this subsection we discuss the two main existing directions, viz. founded and justified repairs. We later propose a new one in Section 5 using the programs of DL-PA.

Founded weak repairs and founded repairs

In the literature, founded repairs are considered to be a basic semantics of active constraints. They provide a basis for further refinements. The key notion they rely on is the foundedness condition. 3Definition 2.13. Let V be a database and let η be a set of active constraints. A consistent set of update actions U is founded w.r.t. V and η if for every α ∈ U there is an r ∈ η such that:

(a) α ∈ R(r) (b) V U | = C(r) (c) V (U \ {α}) | = C(r)
Given this condition, the definitions of a founded weak repair and a founded repair immediately follow.

Definition 2.14. Let V be a database and let η be a set of active constraints. A set of update actions U is a founded weak repair of V by η if U is a weak repair of V achieving C(η) and U is founded w.r.t. V and η. Moreover, if U is also a PMA repair of V achieving C(η), then U is a founded repair of V by η.

The following simple example showcases this definition.

Example 2.15. Let V = ∅ and η = p, {p← } , p∨q, {q← } . The set {p← } is the only founded weak repair of V by η. Indeed, the second update action in {p← , q← } cannot be founded on the second active constraint of η. It is also the only founded repair.

There are sets of active constraints for which there is no founded repair, although there is a founded weak repair [9, Example 2]. The next example, which is adapted from the example of the introductory section, shows that there are sets of active constraints for which there is not even a founded weak repair.

Example 2.16. Let V = ∅ and η = p∨q, {p← } , ¬p∨q, {q← } . The set {q← } is a PMA repair of V achieving C(η). However, there is no founded weak repair (and thus no founded repair either).

Last but not least, the next example illustrates circularity of support: each update action that is individually founded owes this to the presence of the other update actions in the repair.

Example 2.17. ( [START_REF] Caroprese | Active integrity constraints and revision programming[END_REF], Example 3) Let V = ∅ and η = p∨q, {p← } , ¬p∨q, {q← } , p∨¬q, {p← } . The set {p← , q← } is the only founded weak repair of V by η: p← is founded on p∨¬q, {p← } and q← is founded on ¬p∨q, {q← } . It is also a founded repair. Such repairs were considered to be unintended in [START_REF] Caroprese | Active integrity constraints and revision programming[END_REF] and the notion of justified repair was proposed to overcome the problem. We discuss this issue further in Section 5.3.

Justified weak repairs and justified repairs

Justified repairs use a stronger condition than foundedness in order to avoid the aforementioned circular dependencies. We start with the definition of a closed set of update actions. Definition 2.18. Let η be a set of standard active constraints. For r ∈ η, all the literals in C(r) which cannot be affected by an update action in R(r) are called non-updatable. A set of update actions U is closed under an r ∈ η when the following holds: if the update actions in U falsify all the non-updatable literals in C(r), then U must contain an update action from R(r). Furthermore, U is closed under η if it is closed under every r ∈ η.

For example, {p← , q← } is closed under p∨¬q, {p← } , ¬p∨q, {q← } and p∨q, {p← } , while it is neither closed under ¬p∨¬q, {p←⊥} nor under ¬p∨r, {r← } . The second step is to define the no-effect actions associated with an initial database V and an updated database V . Definition 2.19. Let V and V be two databases. The update action p← is a no-effect action of (V, V ) if p ∈ V ∩ V and the update action p←⊥ is a no-effect action of (V, V ) if p V ∪ V . The set ne(V, V ) denotes the set of all no-effect actions of (V, V ).

Clearly, for given V and U, we have that V U = V (U \ U ) for every U ⊆ ne(V, V U). Returning to our initial aim now, the definitions of a justified weak repair and a justified repair are the following.

Definition 2.20. Let V be a database and let η be a set of standard active constraints. A consistent set of update actions U is a justified weak repair of V by η iff: 4(a

) U ∩ ne(V, V U) = ∅ (no 'no-effect' actions) (b) U ∪ ne(V, V U) is closed under η (c) there is no U ⊂ U ∪ ne(V, V U) such that: (1) U contains ne(V, V U) (2) U is closed under η Finally, if U is also a PMA repair of V achieving C(η), then U is a justified repair of V by η.
The next theorem shows the relationship between founded and justified repairs.

Theorem 2.21. ( [START_REF] Caroprese | Active integrity constraints and revision programming[END_REF], Corollaries 1 and 2) Let V be a database, U a consistent set of update actions and η a set of standard active constraints. If U is a justified weak repair of V by η, then U is also a founded weak repair of V by η (and likewise, if it is a justified repair of V by η, then it is also a founded repair of V by η).

The next example shows that the converse does not hold. Furthermore, it illustrates that for justified repairs circularity of support is no longer an issue.

Example 2.22. ([9], Example 5)

Consider again V = ∅ and η = p∨q, {p← } , ¬p∨q, {q← } , p∨¬q, {p← } . In contrast with Example 2.17 and its founded repair, there is no justified weak repair of V by η. As justified weak repairs are also founded weak repairs, we only have to check whether U = {p← , q← } is a justified weak repair of V by η. Supposing that P = {p, q}, we have ne(V, V U) = ne(∅, {p, q}) = ∅ and U ∪ ne(V, V U) = U is not a minimal set of update actions containing ne(V, V U) and closed under η, as ∅ also has these properties.

However if we replace η with η = p∨q, {p← , q← } , ¬p∨q, {q← } , p∨¬q, {p← } then the set {p← , q← } is both a justified and a founded repair of V by η (and both are the only ones). The reason that the set {p← , q← } is a justified repair now is because ∅ is not closed under η anymore (it trivially falsifies all the non-updatable literals in the first constraint, since now there aren't any, but it contains no update actions).

In the next two sections, we show that weak, PMA, founded and justified repairs can be captured in DL-PA.

Repairs and weak repairs in DL-PA

We now embed Winslett's standard semantics (and thereby weak repairs) and the PMA (and thereby repairs tout court) into DL-PA. This was already done in [START_REF] Herzig | Belief Change Operations: A Short History of Nearly Everything, Told in Dynamic Logic of Propositional Assignments[END_REF], but our embeddings are slightly more elegant and are presented in a more uniform and streamlined way. We start with some auxiliary definitions.

To each propositional variable p we associate a fresh propositional variable p ± . Each p ± will register whether or not the proposition p has been modified along the update. 5 This is necessary to ensure that every variable is modified at most once during a repair. We extend the definition to sets of variables P ⊆ P: P ± = {p ± | p ∈ P}. With the information stored in the fresh variables P ± , we can retrieve the initial valuation from a valuation V ⊆ P ∪ P ± through the set:

{p ∈ V : p ± V} ∪ {p V : p ± ∈ V}
First, we need a program that sets all the propositions in a given set P to ⊥: P←⊥ is the sequence of assignments p←⊥ for all p ∈ P (whose order does not matter, see Proposition 2.4). Second, the following two DL-PA programs (1) modify a single proposition and store this and (2) undo that modification: toggle(p) = if ¬p ± then p←¬p; p ± ← else fail = ¬p ± ?; p←¬p; p ± ← undo(p) = if p ± then p←¬p; p ± ←⊥ else fail = p ± ?; p←¬p; p ± ←⊥ As announced above, p ± keeps track of the modifications of p: we are going to ensure that it is true only once p has been modified during the current update. The program toggle(p) flips the truth value of p if this value has not been modified yet and records the modification by setting p ± to ; if p has already been made true then toggle(p) fails. The program undo(p) undoes this.

It is easy to see then that starting from a database V that contains none of the variables p ± , a weak repair of V achieving C can be obtained through the following DL-PA program:

weakRepair(C) =          p∈P C toggle(p)          * ; C ?
Since each variable can be updated at most once and since the order of the updates does not matter, this can be rewritten without the Kleene star as a sequence:

toggle(p 1 ) ∪ skip ; . . . ; toggle(p k ) ∪ skip ; C ?
where p 1 , . . . , p k are the variables in P C . Furthermore, given that none of the variables p ± occur in the database, the program toggle(p) simplifies to just: p←¬p; p ± ← .

Finally, we define the following DL-PA formula:

Minimal(C) = ¬          p∈P C undo(p)          + C 5
The difference with [START_REF] Herzig | Belief Change Operations: A Short History of Nearly Everything, Told in Dynamic Logic of Propositional Assignments[END_REF] is that our programs memorise that a variable has been flipped instead of storing its previous value.

The program in this formula undoes a nonempty set of toggle(p) actions (and nondeterministically so, failing when there was no change at all). Therefore the formula Minimal(C) says that there is no execution of that program leading to a database closer to the actual database that satisfies the constraints. Hence the actual database corresponds to a minimal change of the initial database. We sum up all the above in the following theorem.

Theorem 3.1. Let C be a set of static integrity constraints in the language of P and let V ⊆ P be a database (i.e., no p ± occurs in either of them). Let U be a consistent set of update actions that is relevant w.r.t. V.

• U is a weak repair of V achieving C iff:

V, V U ∈ || weakRepair(C) ; P C ± ←⊥ || • U is a PMA repair of V achieving C iff: V, V U ∈ || weakRepair(C) ; Minimal(C)? ; P C ± ←⊥ ||

Founded and justified repairs in DL-PA

We will now move on to the embedding of the notions of founded and justified repairs into DL-PA.

For this, we will re-use the programs defined in the previous section for finding a weak repair and checking minimality, as well as the set of fresh variables P ± we had at our disposal in order to keep track of modifications. Moreover, we will need to define a program for checking the foundedness condition in order to generate the founded repairs as well as programs for adding the no-effect actions to a database and checking if a set of update actions is closed under a set of active constraints.

We start with the embedding of founded repairs into DL-PA, for which we will need the following formula:

Founded(η) = p∈P C(η)               p ± → r∈η p←X∈R(r) p←¬p ¬C(r)              
where X ranges over { , ⊥}. We can see then that this formula is true if and only if all current update actions (encoded in the current valuation by means of the fresh variables p ± ) are founded w.r.t. the initial valuation and η.

The embedding of justified repairs into DL-PA is a bit more complex. Firstly, we use the set nup(r) of all the non-updatable literals in r that we saw in Definition 2.18, i.e., all the literals in C(r) for which there is no preferred update action in R(r). By nup(r) + we denote the set of propositional variables of the form p in nup(r), i.e., nup(r) + = nup(r) ∩ P. Similarly, nup(r) -comprises the propositional variables of the form ¬p in nup(r), i.e., nup(r) -= {¬p | p ∈ nup(r) \ P}. Furthermore, we introduce two new sets of fresh propositional variables, P + and P -, defined similarly to P ± as follows: P + = {p + | p ∈ P} and P -= {p -| p ∈ P}. Intuitively, the proposition p + will keep track of the no-effect action of the form p← , while the proposition p -will keep track of the no-effect action of the form p←⊥. This is realized by the following two programs:

ne + (p) = p ∧ ¬p ± ? ; p + ← ne -(p) = ¬p ∧ ¬p ± ? ; p -←
Moreover, we will need a program that skips when neither p← nor p←⊥ is a no-effect action and fails otherwise (where 'ea' stands for 'effect action'):

ea(p) = p ± ?
Then we associate with the current database all the no-effect actions between the initial database and the current state through the following program:

ne(η) = ne + (p 1 ) ∪ ne -(p 1 ) ∪ ea(p 1 ) ; . . . ; ne + (p k ) ∪ ne -(p k ) ∪ ea(p k )
where p 1 , . . . , p k are the variables in P C(η) (so the no-effect actions that are added are only those that are relevant w.r.t. η). Next, we define A(r) and B(r) to be the following formulas:

A(r) = p∈nup(r) + (¬p ∧ p ± ) ∨ (¬p ∧ p -) ∧ p∈nup(r) - (p ∧ p ± ) ∨ (p ∧ p + ) B(r) = p← ∈R(r) p ∨ p←⊥∈R(r)
¬p Using these then we define:

Closed(η) = r∈η A(r) → B(r) MinimallyClosed(η) =¬          p∈P C(η) undo(p)          + Closed(η)
Given a set of standard active constraints η, the first formula is true exactly when all current update actions (again, encoded in the current valuation through the set P ± ) plus all the no-effect actions (encoded in the current valuation through the sets P + and P -) are closed under η, while the second formula is true if and only if the set comprising of all current update actions is the minimal set of update actions that (together with the no-effect actions) has this property. Finally, we define the following abbreviations:

Justified(η)? = ne(η) ; Closed(η)? ; MinimallyClosed(η)?

ClearAll = P C ± ←⊥ ; P C + ←⊥ ; P C -←⊥
The following two theorems now give a complete characterisation of founded and justified repairs in terms of DL-PA programs.

Theorem 4.1. Let η be a set of active integrity constraints in the language of P and let V ⊆ P be a database (i.e., no p ± occurs in either of them). Let U be a consistent set of update actions that is relevant w.r.t. V.

• U is a founded weak repair of V by η iff:

V, V U ∈ weakRepair(C(η)) ; Founded(η)? ; P C ± ←⊥
• U is a founded repair of V by η iff:

V, V U ∈ weakRepair(C(η)) ; Founded(η)? ; Minimal(C(η))? ; P C ± ←⊥ Theorem 4.2. Let η be a set of standard active constraints in the language of P and let V ⊆ P be a database (so no p ± , p + and p -occurs in either of them). Let U be a consistent set of update actions that is relevant w.r.t. V.

• U is a justified weak repair of V by η iff:

V, V U ∈ weakRepair(C(η)) ; Justified(η)? ; ClearAll
• U is a justified repair of V by η iff:

V, V U ∈ weakRepair(C(η)) ; Justified(η)? ; Minimal(C(η))? ; ClearAll

A new definition of repair in DL-PA

We now propose some new definitions that take advantage of the resources of DL-PA. More precisely, we make use of while loops in order to iterate the application of active constraints. We start by discussing how databases can be repaired by applying active constraints in sequence. This will lead us to the definition of dynamic repair. We show that it is incomparable with both founded and justified repairs and discuss its properties and some variants.

Repairing a database: a dynamic view

Suppose there is only one active constraint r that is standard. Then it is clear how to proceed: either V | = C(r) and there is nothing to do, or V | = C(r) and we have to apply r. In the second case, each α i ∈ R(r) provides a PMA repair of V achieving C(r). 6 What about the case where R(r) is empty? Well, then V cannot be repaired and we are stuck. So far so good. The situation may get way more intricate when the set of active constraints η contains two or more elements that can interact. Firstly, the example of the introductory section and Example 2.16 illustrated an instance of active constraints which intuitively should have a repair (and it does, in the case of PMA repairs) but for which there is no founded or justified weak repair. We would like to find a definition of a repair which depends only on the preferred update actions and always provides a repaired database, as long as there are update actions from each C(r) to choose from. Moreover, even for standard active constraints it might not be enough to apply an update action α i ∈ r∈η R(r) only once: some of the active constraints might have to be applied several times in order to obtain integrity. The following active constraints that are inspired by an (n+1)-bit counter highlight this.

Suppose for n ≥ 0 we represent binary numbers up to 2 n+1 -1 by means of n+1 propositional variables p 0 , . . . , p n : ¬p n ∧ • • • ∧¬p 0 represents the integer zero and

p n ∧ • • • ∧p 0 represents 2 n+1 -1.
For each bit we also need an auxiliary variable x i . Let:

r 1 = p 0 ∨x 1 ∨ • • • ∨x n , {p 0 ← } r 2 k = p k ∨¬p k-1 ∨ • • • ∨¬p 0 ∨x k , {x k ← } , for 1 ≤ k ≤ n r 3 k i = ¬p i ∨¬x k , {p i ←⊥} , for 1 ≤ k ≤ n and 0 ≤ i ≤ k -1 r 3 k k = p k ∨¬x k , {p k ← } , for 1 ≤ k ≤ n r 4 k = ¬p k ∨p k-1 ∨ • • • ∨p 0 ∨¬x k , {x k ←⊥} , for 1 ≤ k ≤ n
The idea is that when ¬p k ∧p k-1 ∧ • • • ∧p 0 is true, i.e., when the number 011. . .1 has to be incremented to 100. . .0, then x k is made true by r 2 k and remains so until 100. . .0 has been attained. This involves flipping the k digits in the conjunction ¬p k ∧p k-1 ∧ • • • ∧p 0 : with active constraints this is done oneby-one by r 3 k i and r 3 k k . Then x k is set to false again by r 4 k . Let η n be the set of all the above rules, for a given n:

η n = r 1 } ∪ {r 2 1 , . . . , r 2 n } ∪ {r 3 1 0 , r 3 1 1 } ∪ {r 3 2 0 , r 3 2 1 , r 3 2 2 } ∪ . . . ∪ {r 3 n 0 , . . . , r 3 nn } ∪ {r 4 1 , . . . , r 4 n }
Successive repairing steps implement an (n+1)-bit counter counting from the initial database ∅ to the database {p n , . . . , p 0 }.

The computation takes a number of steps that is exponential in n, while the number of update actions is 1 2 (n 2 +7n)+1, demonstrating that sometimes atomic repairs must be performed an exponential number of times: for example r 1 needs to be applied 2 n times in order to repair V 0 = ∅ by η n . Let us illustrate by the 3-bit counter how the repairs are done.

Example 5.1. Let's take n = 2 and try to obtain the integer 111 starting from 000. In Figure 1 we can see the steps needed through which we will reach the set of update actions U = {p 0 ← , p 1 ← , p 2 ← } that will update the database ∅ in order for it to satisfy the active integrity constraints in η 2 . The first column represents the current database (starting from ∅), the second column shows the constraint that was applied in order to reach it and in the third we see the current integer in the counter. Last but not least, the last column shows when an x k is kept true in order for the procedure to reach the integer 10 from 01 and the integer 100 from 011 when needed. We can see how some constraints need to be applied many times in order to succeed in repairing the original database. This calls for a dynamic way through which a database is updated in order for it to be repaired: a procedure that modifies the database according to the integrity constraints step by step, until it reaches a satisfactory form (i.e., satisfies the integrity constraints). Founded and justified repairs cannot do the job in this and other scenarios of that kind, as an active constraint can only be used once: indeed, in the example of the (n+1)-bit counter, no repair can be obtained by means of founded and justified repairs. That's why we introduce dynamic repairs.

¬p 2 ∧ ¬p 1 ∧ ¬p 0 ∧ ¬x 1 ∧ ¬x 2 000 - ¬p 2 ∧ ¬p 1 ∧ p 0 ∧ ¬x 1 ∧ ¬x 2 r 1 001 - ¬p 2 ∧ ¬p 1 ∧ p 0 ∧ x 1 ∧ ¬x 2 r 2 1 001 ¬p 2 ∧ ¬p 1 ∧ ¬p 0 ∧ x 1 ∧ ¬x 2 r 3 1 0 000 ¬p 2 ∧ p 1 ∧ ¬p 0 ∧ x 1 ∧ ¬x 2 r 3 1 1 010 ¬p 2 ∧ p 1 ∧ ¬p 0 ∧ ¬x 1 ∧ ¬x 2 r 4 1 010 - ¬p 2 ∧ p 1 ∧ p 0 ∧ ¬x 1 ∧ ¬x 2 r 1 011 - ¬p 2 ∧ p 1 ∧ p 0 ∧ ¬x 1 ∧ x 2 r 2 2 011 ¬p 2 ∧ p 1 ∧ ¬p 0 ∧ ¬x 1 ∧ x 2 r 3 2 0 010 ¬p 2 ∧ ¬p 1 ∧ ¬p 0 ∧ ¬x 1 ∧ x 2 r 3 2 1 000 p 2 ∧ ¬p 1 ∧ ¬p 0 ∧ ¬x 1 ∧ x 2 r 3 2 2 100 p 2 ∧ ¬p 1 ∧ ¬p 0 ∧ ¬x 1 ∧ ¬x 2 r 4 2 100 - p 2 ∧ ¬p 1 ∧ p 0 ∧ ¬x 1 ∧ ¬x 2 r 1 101 - p 2 ∧ ¬p 1 ∧ p 0 ∧ x 1 ∧ ¬x 2 r 2 1 101 p 2 ∧ ¬p 1 ∧ ¬p 0 ∧ x 1 ∧ ¬x 2 r 3 1 0 100 p 2 ∧ p 1 ∧ ¬p 0 ∧ x 1 ∧ ¬x 2 r 3 1 1 110 p 2 ∧ p 1 ∧ ¬p 0 ∧ ¬x 1 ∧ ¬x 2 r 4 1 110 - p 2 ∧ p 1 ∧ p 0 ∧ ¬x 1 ∧ ¬x 2 r 1 111 -

Dynamic weak repairs and dynamic repairs

We associate with every active constraint r the DL-PA programs: p←X; p ± ← Remember that α∈R(r) α equals fail when R(r) is empty. This matches the intuitive reading that we have given to active constraints in Section 2.3.1: the repair program π r checks whether the static integrity constraint associated with r is violated, and if so nondeterministically applies one of the update actions from R(r). The program π ± r moreover stores that p has been changed. These intuitions are also supported by the following proposition, which tells us that applicability of an active constraint r (the fact that C(r) is violated) is matched by the DL-PA notion of executability of the program π r . Proposition 5.2. Let r be an active constraint and let V be a database. Then applicability of r at V is equivalent to both V | = π r and V | = π ± r .

Proof:

It suffices to observe that when π is a nondeterministic composition of update actions then the equivalence ¬C(r) ↔ ¬C(r)?; π is DL-PA valid for every C(r).

Based on these, the definitions of a dynamic weak repair and a dynamic repair are the following. Definition 5.3. Let V be a database and let η be a set of active constraints. A dynamic weak repair of V by η is a consistent set of update actions U such that U is relevant w.r.t. V and:

V, V U ∈ while ¬ C(η) do r∈η π r
Moreover, if U is also a PMA repair of V achieving C(η), then U is a dynamic repair of V by η.

In the following example we see that dynamic repairs sometimes coincide with founded repairs.

Example 5.4. (Example 2.17, ctd.) Consider again V = ∅ and η = p∨q, {p← } , ¬p∨q, {q← } , p∨¬q, {p← } . There is a single dynamic weak repair (and also dynamic repair) of V by η, viz. {p← , q← }. Remember by Example 2.22 that there is no justified repair.

As we have already witnessed with the (n+1)-bit counter though, dynamic weak repairs are not necessarily founded. The next example is simpler. Remember also that at the beginning of Section 5.1 we argued against founded and justified repairs using Example 2.16 (itself an adaptation of the example discussed in the introductory section), for which we would like to have a way to repair V by η. The next example shows that dynamic weak repairs solve this problem. Let us also note that just like founded and justified repairs, dynamic weak repairs do not necessarily coincide with dynamic repairs.

Example 5.6. (Example 2.16, ctd.) Consider again V = ∅ and η = p∨q, {p← } , ¬p∨q, {q← } . The only dynamic weak repair of V by η is the set of update actions {p← , q← }. But {q← } is the PMA repair of V achieving C(η), so there is no dynamic repair.

Finally, in a similar manner as in the previous sections, the next theorem characterises dynamic repairs in terms of DL-PA programs.

Theorem 5.7. Let η be a set of active integrity constraints in the language of P and let V ⊆ P be a database (i.e., no p ± occurs in either of them). Let U be a consistent set of update actions that is relevant w.r.t. V. U is a dynamic repair of V by η iff:

V, V U ∈ while ¬ C(η) do r∈η π ± r ; Minimal C(η) ? ; P C ± ←⊥ Proof:
The proof is quite trivial and based on the definitions. Given a database V ⊆ P and a set of active integrity constraints η, a dynamic repair of V by η is both a dynamic weak repair of V by η and a PMA repair of V achieving C(η). In DL-PA terms then, this is given by the sequential composition of the programs while ¬ ( C(η)) do r∈η π ± r and Minimal C(η) ?, with the DL-PA program π ± r keeping track of which propositions have been modified along the update so that they can be checked again in the latter. Finally, as before the program P C ± ←⊥ ensures that no p ± exists in U.

Some interesting properties

In this subsection we present some interesting properties of this dynamic procedure that distinguishes it from the other main repairs which have been studied and prevailed in the literature, viz. weak repairs, PMA repairs, founded and justified repairs. Our goal is to provide a concrete argument that repairs produced in this way are an interesting kind of repairs, possessing the advantages of the others while not comprising some of their disadvantages.

The main problem with founded repairs is the so called circularity of support which has been already mentioned at the end of Section 2.3.2. This undesirable property is what ultimately led to the definition of justified repairs, which are way more complex and difficult to understand, at least at first sight. Dynamic repairs on the other hand provide a solution to this problem without straying too far from the initial definition, making it far less intricate. In contrast with founded repairs which need the foundedness property to give priority to the "preferred" repairs, dynamic repairs simply select an update action from the set that they have access to (the set of preferred ones) without checking for any other condition. This leads to no circular support between any set of preferred actions and can also be seen in Example 5.4 where {p← , q← } remains a dynamic repair of V by η even if the constraint ' p∨¬q, {p← } ' is absent (something that cannot be said for founded repairs, as this constraint is required for the foundedness of 'p'). Furthermore, although justified repairs solve this problem, they often do not exist, as can be seen by Example 2.22. Through dynamic repairs we can provide a solution to cases like this, avoiding the circularity of support found in founded repairs, while still being able to provide a repaired database. So not only are dynamic repairs more intuitive, but they also comprise the best of both situations.

Despite this however, one could still argue that they are too "strict", sometimes requiring that every integrity constraint in C(η) has a way to be repaired (i.e., an update action in R(r) should exist for all r ∈ η in order to make C(r) true). If R(r) = ∅ for some r ∈ η, then the whole dynamic repairing procedure could collapse and a dynamic weak repair never occur. The next example illustrates exactly this.

Example 5.8. Let V = {q} and η = p∨q, {p← } , p, ∅ . The set {p← } is a PMA repair of V achieving C(η). However, there are no dynamic weak repairs (and thus no dynamic repairs either).

As we can see, the problem arises when an integrity constraint has no preferred update actions and cannot be satisfied by the application of some other constraint when repairing the database. One could differentiate this behavior into three classes of repairs, based on the level of "strictness" of the preference that is involved in the active constraints. The more strict repairs are those conforming to the idea that every integrity constraint C(r) should be repaired only through an update action in R(r), the less strict allow any update actions in r∈η R(r) to be used for any integrity constraint C(r), while the middle ground is to keep a balance between the two. As we can see, the passing from the more strict class to the others changes the meaning of the update actions in R(r) from permitted repair actions to preferred ones, a distinction that is not always made clear in the literature. As Example 5.8 shows, dynamic repairs and dynamic weak repairs possess some of this "strict" nature: an update action will only arise while updating a database if it helps to repair some constraint. This forbids repairs in cases where all clauses apart from those having no preferred actions are already satisfied. In contrast, in such cases solutions with founded weak repairs can occur, as shown in the next example.

Example 5.9. ([9], Example 2) Let V = ∅ and η = p∨¬q∨¬r, {p← } , ¬p∨q∨¬r, {q← } , ¬p∨¬q∨r, {r← } , p, ∅ . The set {p← , q← , r← } is the only founded weak repair of V by η. Furthermore, the set {p← } is a PMA repair of V achieving C(η). There are no dynamic weak repairs (and thus no dynamic repairs either).

So this leads to the following question: should we require a repair to exist in such cases or not? Are we willing to agree with the fact that such databases do not and should not have a repair, or is repairing the database in order to satisfy the integrity constraints in C(η) of the highest priority?

If the answer to the last question is positive then dynamic repairs could be less interesting. We can however tweak the definition slightly and define global-dynamic weak repairs to be a kind of dynamic repairs with the same intuitive behavior as before but belonging to the least strict of the aforementioned classes of repairs. More precisely, the reason that dynamic repairs cannot repair a constraint using update actions found in the other clauses is the local nature of the do part in the while loop. Before trying to repair the whole set of active integrity constraints in η, a dynamic repair locally checks if every clause (integrity constraint) is satisfied. If we drop this requirement and allow the dynamic procedure to globally choose update actions found in the other clauses, then we will have a solution in Examples 5.8, 5.9 and more generally the cases we have discussed.

Definition 5.10. Let V be a database and let η be a set of active constraints. A global-dynamic weak repair of V by η is a consistent set of update actions U such that U is relevant w.r.t. V and:

V, V U ∈ while ¬ C(η) do r∈η α∈R(r) α
In the same vein as before, if U is also a PMA repair of V achieving C(η), then U is a global-dynamic repair of V by η.

It is easy to see now that this tweaked definition provides us with the desired repaired database in Examples 5.8 and 5.9. Specifically, the set {p← } is a global-dynamic repair of V by η in both examples. Furthermore, a dynamic weak repair is always a global-dynamic weak repair, as it can be created by the same procedure using one step less, namely by not checking the condition "¬C(r)?" in the do part of the program. This makes dynamic weak repairs a subset of global-dynamic weak repairs (and also dynamic repairs a subset of global-dynamic repairs).

It is our intention to use the global-dynamic repairs mainly as a tool of comparison between the different classes of repairs and less as a practical repairing technique that would replace the others. As we will see, the most important attribute of global-dynamic repairs is that they are exactly the globaldynamic weak repairs that are minimal w.r.t. set inclusion (i.e., if U is a global-dynamic repair of V then there is no global-dynamic weak repair U of V such that U ⊂ U). The recipe when defining repairs till now is to first give the definition of their weak versions and then state that they also have to be PMA repairs. This is of course different from saying that these repairs are the weak repairs that are minimal w.r.t. set inclusion, as in this case they would always exist if at least one of their weak counterparts existed. But it is not always the case that they may coincide with PMA repairs and usually may not exist altogether. This can be witnessed in Example 5.9 for founded repairs and in Example 5.6 for dynamic repairs.

However, when minimality w.r.t. set inclusion and coincidence with PMA repairs is the same, we have a much more powerful and reliable tool in our hands that avoids the main disadvantage of other repairs, namely that they may not exist (even if their weak versions do). This is shown in Theorem 5.12. Before this, a small lemma characterises this global-dynamic nature.

Lemma 5.11. Let η be a set of active integrity constraints in the language of P and let V ⊆ P be a database. Let U 1 be a global-dynamic weak repair of V by η and U 2 be a weak repair of V achieving C(η) such that U 2 ⊂ U 1 . Then U 2 is also a global-dynamic weak repair of V by η.

Proof:

By hypothesis, U 1 and U 2 are both consistent sets of update actions that are relevant w.r.t. V such that

V U 1 | = C(η) and V U 2 | = C(η) with U 2 ⊂ U 1 .
This means that V can be updated with less update actions than U 1 in order to satisfy the integrity constraints in η. But U 1 was constructed by iteration on checking the satisfaction of C(η) and applying update actions from r∈η R(r). Then U 2 can be constructed in exactly the same way, since it doesn't comprise any update actions outside of U 1 , with the difference of taking less update actions into account: namely, by restricting the nondeterministic choice to updates from U 2 and leaving the update actions in U 1 \U 2 out of consideration. This will also lead to a repaired database. So U 2 is a global-dynamic weak repair of V by η as well.

Theorem 5.12. Let η be a set of active integrity constraints in the language of P and let V ⊆ P be a database. Let U be a consistent set of update actions that is relevant w.r.t. V. U is a global-dynamic repair of V by η iff U is a global-dynamic weak repair of V by η that is minimal w.r.t. set inclusion.

Proof:

Let the set GDR consist of all the global-dynamic repairs of V by η and let MGDWR consist of all the global-dynamic weak repairs of V by η that are minimal w.r.t. set inclusion. For convenience we also define in the same way R as the set of all PMA repairs and WR as the set of all weak repairs of V achieving C(η). Finally, let GDWR be the set of all global-dynamic weak repairs of V by η. First of all, observe that GDR = GDWR ∩ R (1) and GDWR ⊆ WR (2). Let us show that GDR = MGDWR.

• GDR ⊆ MGDWR: let U 1 ∈ GDR. By (1) then, U 1 ∈ GDWR and U 1 ∈ R. Let U 2 ∈ GDWR such that U 2 ⊂ U 1 . By (2) we also have that U 2 ∈ WR. This means that U 1 ∈ R and U 2 ∈ WR with U 2 ⊂ U 1 .
But this cannot be the case, as a PMA repair is a minimal weak repair w.r.t. set inclusion. So there is no

U 2 ∈ GDWR such that U 2 ⊂ U 1 , where U 1 ∈ GDWR. Thus U 1 ∈ MGDWR.
Note that this also applies to founded, justified and dynamic repairs. The difference is in the other direction.

• MGDWR ⊆ GDR: let U 1 ∈ MGDWR. By definition then, U 1 ∈ GDWR and there is no

U ∈ GDWR such that U ⊂ U 1 (3). Let U 2 ∈ WR such that U 2 ⊂ U 1 . By Lemma 5.11
it is also the case then that U 2 ∈ GDWR. But this cannot be the case by [START_REF] Bertossi | Database Repairing and Consistent Query Answering[END_REF]. So there is no

U 2 ∈ WR such that U 2 ⊂ U 1 .
Since by (2) we also have

U 1 ∈ WR, this means that U 1 ∈ R. Thus U 1 ∈ GDWR ∩ R and using (1) we get U 1 ∈ GDR.
So there is enough evidence to support the idea of using global-dynamic repairs as our repairs of choice when we want to update a database taking into account active integrity constraints in the cases where other repairs don't work. They are the closest thing to a PMA repair as shown by the next proposition, with the only limitation of being non-existent if the set of update actions r∈η R(r) is empty or if an integrity constraint can't be repaired even through update actions existing in other clauses (in both cases a solution to this problem shouldn't exist intuitively). Proposition 5.13. Let η be a set of active integrity constraints in the language of P and let V ⊆ P be a database. Let U be a consistent set of update actions that is relevant w.r.t. V. U is a global-dynamic repair of V by η iff U is a PMA repair of V achieving C(η) and U ⊆ r∈η R(r).

Proof:

The left-to-right direction is trivial by the definition of global-dynamic repairs, whereas the right-toleft direction follows immediately by Theorem 5.12.

But ultimately the choice between dynamic and global-dynamic repairs is traced back to what the answer should be regarding the repairing or not of a database in all of these cases. The former use a more restrictive procedure that makes it more local, while the latter do not.

Remark 5.14. In dynamic weak repairs and dynamic repairs we can use the p∈P R(r) toggle(p) program in the place of α∈R(r) α in π r without any change in the dynamic behavior of the repairs. In the case of global-dynamic weak repairs, at first sight the programs:

while ¬ C(η) do r∈η α∈R(r) α and while ¬ C(η) do r∈η p∈P R(r) toggle(p)
seem to once again bring the same results. This bears the question of whether we could instead use the second definition which abbreviates:

              ¬ C(η) ? ; r∈η p∈P R(r) toggle(p)               * ; C(η) ?
and which is highly reminiscent of the program weakRepair(C(η)), showing its close relationship with weak and PMA repairs. It should be clarified why toggle(p) doesn't work anymore. The reason is that toggling a propositional variable in this case is not the same as choosing the respective update action, as toggle(p) can bring the opposite results. We can see this when V = ∅ and η = ¬p∨q, {p←⊥} , ¬q∨p, {q←⊥} , r, {r← } . A global-dynamic weak repair of V by η using the alternative definition with toggle(p) is the set of update actions {p← , q← , r← }, which is obviously absurd.

As already mentioned, this does not happen with dynamic weak repairs and dynamic repairs. It is another aspect of their "strict" and local nature, as they check if a clause needs repairing before toggling any propositional variable, thus making any update action chosen to be exactly the intended one from the set of preferred ones.

Complexity of dynamic repairs

In this section we provide tight complexity bounds for the problems of existence of a dynamic weak repair and a dynamic repair. It is known that deciding the existence of a repair is NP-complete for weak repairs, PMA repairs and founded weak repairs, while it is Σ 2 P -complete for founded repairs, justified weak repairs and justified repairs [START_REF] Caroprese | Active integrity constraints and revision programming[END_REF]. As we will see, the same problem proves to be more difficult for dynamic weak repairs and dynamic repairs: deciding their existence is PSPACE-complete. For the lower bound (hardness) we provide a reduction from the problem of checking whether a fully quantified Boolean formula is true, whereas for the upper bound (membership) a reduction to the model checking problem of DL-PA will suffice. The result follows from the fact that checking whether a fully quantified Boolean formula is true and DL-PA model checking are both PSPACE-complete problems [START_REF] Stockmeyer | Word Problems Requiring Exponential Time: Preliminary Report[END_REF][START_REF] Balbiani | DL-PA and DCL-PC: model checking and satisfiability problem are indeed in PSPACE[END_REF].

Lower complexity bound

The hardness result is articulated in the following theorem, for which we only provide a proof sketch. Theorem 6.1. The problems of existence of a dynamic weak repair and a dynamic repair are both PSPACE-hard.

Proof Sketch:

In order to show that the existence of dynamic weak repairs and dynamic repairs is PSPACE-hard we will provide a reduction from the following problem: given a fully quantified Boolean formula G, decide whether G is true. We suppose w.l.o.g. that G is in prenex normal form, with the variables in the prefix being all different and the matrix containing only the Boolean connectives ¬ and ∧. Let subf(G) be the set comprising all the subformulas of G and let subf v (G) be the set comprising all the variables in G. We define the set P G of propositional variables to be composed of:

• all x, x ? and x ! such that x ∈ subf v (G)

• A +? , A -? , A +! and A -! for each A ∈ subf(G)
Intuitively, the elements of P G play the following roles: x stores the truth value of x in G, x ? indicates that a value for x must be chosen and x ! indicates that the value for x has been chosen. Similarly, A +? indicates that we check if A is true and A +! indicates that A has been proved to be true. The same goes for A -? and A -! , for checking and proving that A is false.

The idea now is to start from the initial formula G and to compute whether it is true by asking whether there is a dynamic procedure that repairs the database {G +? } under a set of active constraints. This set can be defined by first assigning a set of active constraints to each A ∈ subf(G), indicating the required steps for checking whether or not A can be proved true or false, and taking their union. For each A, the goal is to reach a state satisfying ¬A +? ∧ A +! if we want to prove that A is true and ¬A -? ∧ A -! if we want to prove that A is false. Indeed, each A ∈ subf(G) can be associated with a set of active constraints which repair any database satisfying A +? ∧ ¬A +! (respectively A -? ∧ ¬A -! ) to one satisfying ¬A +? ∧ A +! (respectively ¬A -? ∧ A -! ). So, starting from the database {G +? } which satisfies G +? ∧ ¬G +! , if there is a successful dynamic repair procedure using these sets of active constraints then ¬G +? ∧G +! will be reached and the initial formula G will be proved to be true. On the other hand, if there is no dynamic weak repair of {G +? } by these active constraints then G will be false.

In the following we define the set of active integrity constraints for the case when A = ∃x.B that encode the truth conditions that are used in the evaluation of A. The underlined literals highlight the differences between the static constraints while the rightmost column explains the taken action.

a 1 : ¬A +? ∨ A +! ∨ B +? ∨ B +! ∨ x ? ∨ x ! ∨ x , {x ? ← } ,
ask for a truth value for x; a 2 : ¬A +? ∨ A +! ∨ B +? ∨ B +! ∨ ¬x ? ∨ x ! ∨ x , {x← , x ! ← } , toggle x or set it to false; a 3 : ¬A +? ∨ A +! ∨ B +? ∨ B +! ∨ ¬x ? ∨ x ! ∨ ¬x , {x ! ← } , set x to true; a 4 : ¬A +? ∨ A +! ∨ B +? ∨ B +! ∨ ¬x ? ∨ ¬x ! , {x ? ←⊥} , end the choice of x; a 5 : ¬A +? ∨ A +! ∨ B +? ∨ B +! ∨ x ? ∨ ¬x ! , {B +? ← } , ask for B to be true; a 6 : ¬A +? ∨ A +! ∨ B +? ∨ ¬B +! ∨ x ? ∨ ¬x ! , {A +! ← } , A is now proved true; a 7 : ¬A +? ∨ ¬A +! ∨ B +? ∨ ¬B +! ∨ x ? ∨ ¬x ! , {x ! ←⊥} , free x; a 8 : ¬A +? ∨ ¬A +! ∨ B +? ∨ ¬B +! ∨ x ? ∨ x ! , {B +! ←⊥} , remove the result for B; a 9 : ¬A +? ∨ ¬A +! ∨ B +? ∨ B +! ∨ x ? ∨ x ! ∨ ¬x , {x←⊥} , remove x if it is set to true; a 10 : ¬A +? ∨ ¬A +! ∨ B +? ∨ B +! ∨ x ? ∨ x ! ∨ x , {A +? ←⊥} , end the request for A;

For A = ∃x.B and V ⊆ subf v (G) then the following holds: V | = A iff there is a dynamic weak repair of V ∪ {A +? } by {a 1 , . . . , a 10 }. Similar sets of active constraints then can be assigned to the rest of the formulas A ∈ subf(G). Finally, we define the active constraint g = G +? ∨ ¬G +! , {G +! ←⊥} which is used in the final step to ensure minimality of the repair procedure, i.e., in order to ensure that only the update action G +? ←⊥ survives at the end. We then define the set of active constraints η G to be the union of the aforementioned active constraints for each A ∈ subf(G) together with g. Due to the active constraint g, the set {G +? ←⊥} will always be the only dynamic weak repair of {G +? } by η G and, since ∅ is not a weak repair of {G +? } by η G , it is also a PMA repair. So if a dynamic weak repair of {G +? } by η G exists, it will be the set {G +? ←⊥} which is also a dynamic repair of {G +? } by η G . This gives the following: (1) if there is a dynamic weak repair of {G +? } by η G then there is also a dynamic repair of {G +? } by η G . It follows that:

(2) G is true iff there is a dynamic weak repair of {G +? } by η G

(3) G is true iff there is a dynamic repair of {G +? } by η G Note that (3) is an immediate outcome of ( 1) and [START_REF] Ceri | Automatic Generation of Production Rules for Integrity Maintenance[END_REF]. Now, since it is known that checking whether a fully quantified Boolean formula is true is a PSPACE-complete problem, the hardness result for both dynamic weak repairs and dynamic repairs follows from ( 2) and ( 3) and the fact that, given a formula G, the cardinality of the set η G is linear in the length of G.

Upper complexity bound

Next, in order to show that deciding the existence of dynamic weak repairs and dynamic repairs is in PSPACE we just need to reduce the problem into the model checking problem of DL-PA, since the latter is known to be PSPACE-complete [START_REF] Balbiani | DL-PA and DCL-PC: model checking and satisfiability problem are indeed in PSPACE[END_REF]. The reduction is easy and is based on the following proposition. Proposition 6.2. Let η be a set of active integrity constraints in the language of P and let V ⊆ P be a database.

• A dynamic weak repair of V by η exists iff V | = π η , where π η is the program while ¬ ( C(η))

do r∈η π r • A dynamic repair of V by η exists iff V | = π η , where π η is the program while ¬ ( C(η)) do r∈η π ± r ; Minimal(C(η))? ; P C ± ←⊥ Proof:
In both cases, for the left to right direction consider that a dynamic weak repair (respectively, dynamic repair) of V by η exists. By Definition 5.3 and Theorem 5.7 then, this means that there exists a set of update actions U such that U is relevant w.r.t. V and V, V U ∈ ||π η ||. Since V U | = , the result follows.

Again in both cases, for the right to left direction let V | = π η . This means that there exists a V such that V, V ∈ ||π η ||. It is easy to see that, if we set U = {p← : p ∈ V and p V} ∪ {p←⊥ : p ∈ V and p V } then V = V U and U is relevant w.r.t. V. So, in other words, there exists a U such that U is relevant w.r.t. V and V, V U ∈ ||π η ||. By Definition 5.3 and Theorem 5.7 then, this means that there exists a dynamic weak repair (respectively, dynamic repair) of V by η.

The theorem for membership then follows immediately. Theorem 6.3. The problems of existence of a dynamic weak repair and a dynamic repair are both in PSPACE.

Proof:

It is known that model checking in DL-PA is a PSPACE-complete problem. The result follows from Proposition 6.2 and the fact that, given a set of active integrity constraints η, the length of the program π η is linear in the size of the set C(η).

Using Theorems 6.1 and 6.3 then, we have the following corollary.

Corollary 6.4. The problems of existence of a dynamic weak repair and a dynamic repair are both PSPACE-complete.

History-based repairs

In this section we would like to discuss history-based repairs, an extension of the repairs seen so far taking into account databases with history. What we mean by history is the consistent set of transactions that took place from the last time the database satisfied the integrity constraints up until its current form. So let's say that apart from the initial database, we are also provided with a consistent set of update actions: these are what we refer to as history, the extra information of the route taken from an earlier point in time (more specifically, the last time the integrity constraints were satisfied) until the current state of affairs.

So given this extra information, how should we make use of it? A starting point would be to make sure that the update actions which took place in order to reach the current database will not appear again in the future. Imagine, for instance, that we are provided with the database V, a set of active integrity constraints η and an update action that took place in order to reach it, p←⊥. If there exist two repairs of V by η, namely U 1 = {p← } and U 2 = {q← }, then we would like to disregard U 1 as it would repair V by adding p and V would return to an "earlier state" (from which it was updated by removing p) thus violating the 'priority of the new information' principle that was widely considered in the update literature [START_REF] Katsuno | On the difference between updating a knowledge base and revising it[END_REF]. Furthermore, we should consider what happens in the case where, although repairs exist, there is no repair that updates the database without returning it to an "earlier state". Should we make use of them and disregard the given history or not? Intuitively, the repair actions of active integrity constraints are of the highest priority when repairing a database, whereas the aforementioned history is based on a set of update actions which was used to repair a previous database into the current one, but can be undone if needed. We can see this in the previous example as well, where if U 1 was the only repair of V by η then it should be applied regardless of p←⊥ being used to reach V.

But perhaps a more concrete example is the following, based on the "an employee cannot be in 2 departments" constraint: let P = {d 1 , d 2 }, where d 1 and d 2 denote departments 1 and 2 respectively, and the integrity constraint r = ¬d 1 ∨¬d 2 , {d 1 ←⊥, d 2 ←⊥} which says that no employee should work in both departments at the same time; if this is the case, then they should be removed from either one, without any specific preference. Assume now that H = {d 1 , d 2 }, {d 1 ← } is our history-based database, where {d 1 , d 2 } is our actual database V (saying that there is someone working on both departments) and the set {d 1 ← } represents the history, i.e., that the last department which they joined was d 1 . In this case, we would prefer the repairing of V by {d 2 ←⊥}, instead of {d 1 ←⊥}, considering the latest action of putting the specific employee recently in department 1 to be of higher priority. This is done by repairing V by r H = ¬d 1 ∨¬d 2 , {d 2 ←⊥} instead of r and actually disregarding the "preferred" update action d 1 ←⊥ in R(r) which conflicts with the provided history.

With that in mind, we call H = V, U a history-based database when V ⊆ P is a database and U ⊆ U a consistent set of update actions such that there is V ⊆ P with V U = V. We also define U -1 as the set comprising the opposite update actions in U: U -1 = {p←⊥ : p← ∈ U} ∪ {p← : p←⊥ ∈ U}.

According to what has been said so far, we would like U to be a repair of a history-based database H = V, U by a set of active integrity constraints η, only if U ∩ U -1 = ∅. In order for this to happen we have to repair V by η H instead of η, where η H has:

r H = C(r), R(r) \ U -1
, for r ∈ η

In this way we disregard update actions which have the risk of returning our current database to a previous state and give priority to the new ones. As already mentioned, by choosing to ignore update actions based on the history U that we have, we may risk reducing a set R(r) to be empty for some r ∈ η, thus leading to no repairs occurring. In this case, choosing to not take U into consideration is the only option and we return to the repairing of V by η, instead of H by η. The following example highlights everything that's been said so far. The next theorem characterises founded, justified, dynamic and global-dynamic history-based repairs in terms of DL-PA programs.

Theorem 7.2. Let η be a set of active integrity constraints in the language of P and let V ⊆ P be a database (so no p ± , p + and p -occurs in either of them). Let U and U be consistent sets of update actions such that U is relevant w.r.t. V.

• U is a founded repair of H = V, U by η iff:

V, V U ∈ weakRepairH(C(η), U ); Founded(η)? ; Minimal(C(η))? ; P C ± ←⊥

• U is a justified repair of H = V, U by η iff η is a set of standard active constraints and:

V, V U ∈ weakRepairH(C(η), U ); Justified(η)?; Minimal(C(η))?; ClearAll

• U is a dynamic repair of H = V, U by η iff:

V, V U ∈ while ¬ C(η) do we get exactly the active integrity constraints r H (instead of r) needed in order to repair a history-based database by the corresponding set of active integrity constraints η H .

Conclusion

We have shown how several definitions of database repair via active integrity constraints can be expressed in DL-PA, including new proposals in terms of their iterated application. More specifically, we have introduced a new, dynamic way of handling database repair under a set of active integrity constraints and have shown some interesting properties and alternatives by means of history-based repairs, all through the use of the quite simple but expressive Dynamic Logic of Propositional Assignments DL-PA. This allows us to claim that DL-PA is a nice integrated framework for database updates: it not only provides operators p← of insertion and p←⊥ of deletion and more generally sets U of such assignments that can be applied to a database V; it also provides a means to reason about the repair of the resulting V U when some element of the set of integrity constraints is violated.

In the following, the program repair denotes one of the repair programs of Theorems 3.1, 4.1, 4.2, 5.7, 7.2, as well as Definitions 5.3 and 5.10. We can witness the aforementioned treatment of DL-PA as a means of reasoning between repairs in the following two instances:

• V is a possible repair of the update of the database V by the insertion or deletion of p if and only if the couple V, V belongs to the interpretation of the DL-PA programs p← ; repair or p←⊥; repair respectively.

• The set of candidate repaired databases is the interpretation of the DL-PA formula repair -ϕ V , where ϕ V is a conjunction of literals describing V syntactically.

But beyond identifying possible repaired databases, what is even more interesting is that our programs repair also allow to solve decision problems. Some notable examples follow:

• We may check whether it is possible at all to repair V by model checking in DL-PA whether V | = repair .

• We can check whether there is a unique repair of V by model checking whether the set of databases V such that V, V ∈ ||repair|| is a singleton. This amounts to model check for each of the variables p occurring in the constraints whether V | = repair p ∨ repair ¬p.

• We might as well wish to check possibility or unicity of the repairs independently of a specific database V. For instance, we can check whether η can repair any database by checking whether the formula repair is DL-PA valid.

• A further interesting reasoning task is to check whether two sets of active constraints η 1 and η 2 are equivalent under a given semantics by checking whether ||repair η 1 || = ||repair η 2 ||.

All of the above demonstrate the usefulness of DL-PA as a logic dealing with database repair. The related decision problems also provide a hint of the variety of applications it provides. Furthermore, our way of handling active integrity constraints of the form r = C(r), R(r) allows us to generalise the condition C(r) from clauses to arbitrary formulas (that could actually even be DL-PA formulas). This opens up two perspectives. First, our definition also covers revision programs [START_REF] Caroprese | Active integrity constraints and revision programming[END_REF]; we leave it to future work to establish the exact relationship. Second, we could further generalise the action R(r) from a set of update actions to arbitrary DL-PA programs. Dynamic repairs would then still make sense, while it is not clear how founded and justified repairs would have to be defined.

Last but not least, although we have argued that there are real world problems, such as the one in the introductory section, where dynamic repairs are preferable over founded or justified repairs, we did see that this comes at a cost: the computational complexity of dynamic repairs is higher. We leave it to future work to explore possible avenues of improving this dynamic behavior, especially in terms of computational resources. A possible extension to a first order setting is also a good avenue for future research, seeing that the nature of the procedure is independent of the propositional setting that we worked on and that it could easily be adapted on higher level formalisms.

Figure 1 :

 1 Figure 1: Incrementing 000 to 111 through η 2

π

  r = ¬C(r) ? ; α∈R(r) α π ± r = ¬C(r) ? ; p←X∈R(r)

Example 5 . 5 .

 55 (Example 2.15, ctd.) Consider again V = ∅ and η = p, {p← } , p∨q, {q← } , whose only founded weak repair was {p← }. There are two dynamic weak repairs of V by η, namely {p← } and {p← , q← }. Only the former is a dynamic repair.

Example 7 . 1 .Finally

 71 Let H = {d 1 , d 2 }, {d 1 ← } and η 1 = ¬d 1 ∨¬d 2 , {d 1 ←⊥, d 2 ←⊥} . Both U 1 = {d 1 ←⊥} and U 2 = {d 2 ←⊥} are founded, justified, dynamic and global-dynamic repairs of V = {d 1 , d 2 } by η 1 .Only the second is a founded, justified, dynamic and global-dynamic repair of H by η 1 . Similarly, consider η 2 = ¬d 1 ∨¬d 2 , {d 1 ←⊥} . Then U 1 = {d 1 ←⊥} is a founded, justified, dynamic and globaldynamic repair of V = {d 1 , d 2 } by η 2 . There are no repairs of H by η 2 , however, making us reduce H to just V and use U 1 once again. π ± r,U = ¬C(r) ? ; p←X∈B p←X; p ± ← and π ± r,U = p←X∈B p←X; p ± ← where A = P C(η)\U -1 and B = R(r) \ U -1 .

;;

  Minimal C(η) ? ; P C ± ←⊥ • U is a global-dynamic repair of H = V, U by η iff: Minimal C(η) ? ; P C ± ←⊥Proof:Note that the construction of all history-based repairs in DL-PA terms are identical to their counterparts in the previous sections, with the difference being in the choice of p's and update actions p←X in the nondeterministic composition place of the programs. By removing the set U -1 from each nondeterministic choice imposed by the programs weakRepairH(C(η), U), π ± r,U and π ± r,U

Table 1 .

 1 Table1gives the interpretation of formulas and programs, where • is relation composition and (.) -1 is relation inverse.A formula ϕ is DL-PA valid iff ||ϕ|| = 2 P = V. It is DL-PA satisfiable iff ||ϕ|| ∅. For example, the formulas p←⊥ , p← ϕ ↔ ¬ p← ¬ϕ, p← p and p←⊥ ¬p are all valid. Observe that Interpretation of formulas and programs.

Note that[START_REF] Balbiani | DL-PA and DCL-PC: model checking and satisfiability problem are indeed in PSPACE[END_REF] fixes some complexity results that were erroneously established in[START_REF] Balbiani | Dynamic Logic of Propositional Assignments: A Well-Behaved Variant of PDL[END_REF].

It is actually also a drastic revision because V is a complete database and update and revision coincide in that case[START_REF] Peppas | Revision vs. Update: Taking a Closer Look[END_REF].

We have reformulated the original definition so that it applies to our more general definition of active constraints. Both are equivalent as far as standard active constraints are concerned.

The original definition of justified weak repairs is slightly different than the one given here. However it is shown that the two are equivalent in [9,Theorem 1].

For our more general active constraints where there is no syntactical link between C(r) and R(r) we have to compute all possible minimal subsets U ⊆ R(r) such that V U | = C(r). All of them will be PMA repairs.

Acknowledgements

The work presented in this paper has been partially supported by a Centre International de Mathmatiques et d'Informatique de Toulouse (CIMI Toulouse) doctoral fellowship. We also wish to thank the two anonymous reviewers for their constructive comments which resulted in improving the presentation of the paper.