Structuring the process of integrity maintenance (extended version)

Structuring the Process of Integrity Maintenance (Extended Version) Enric Mayol Ernest Teniente Universitat Politècnica de Catalunya Facultat d'Informàtica Jordi Girona Salgado 1-3, Edifici C6 E-08034 Barcelona - Catalonia e-mail: [mayol | teniente]@lsi.upc.es Abstract Two different approaches have been traditionally considered for dealing with the process of integrity constraints enforcement: integrity checking and integrity maintenance. However, while previous research in the first approach has mainly addressed efficiency issues, research in the second approach has been mainly concentrated in being able to generate all possible repairs that falsify an integrity constraint violation. In this paper we address efficiency issues during the process of integrity maintenance. In this sense, we propose a technique which improves efficiency of existing methods by defining the order in which maintenance of integrity constraints should be performed. Moreover, we use also this technique for being able to handle in an integrated way the integrity constraints enforcement approaches mentioned above. KEYWORDS: deductive database, updating, integrity checking, integrity maintenance 1. Introduction Database updating has attracted a lot of research during last years ([Abi88, Win90]). In general, several problems may arise when updating a deductive database [TU95]. One of the most important problems is that of enforcing database consistency. A deductive database is called consistent if it satisfies a set of integrity constraints. When performing an update, database consistency may be violated. That is, the update, together with the current content of the database, may falsify some integrity constraint. A well-known approach to deal with this problem is that of integrity maintenance [CW90, KM90, ML91, CFPT92, GL93, Wüt93, TO95, Dec96], which is concerned with trying to repair constraints violations by performing additional updates that restore consistency of the database. In this way, it is guaranteed that the state resulting from applying the update does not violate any integrity constraint and that it satisfies the update requested by the user. In general, integrity constraints are very interrelated because they may have some predicates in common. These predicates may appear explicitly in their definition or implicitly because they participate in the definition of a certain derived predicate that appears in the integrity constraint definition. For this reason, the integrity maintenance process uses to be very complex since, for instance, repairs of an integrity constraint may correspond to violations of other integrity constraints; or since an already repaired integrity constraint could be violated again by the repair of another integrity constraint. This situation is aggravated by the fact that even simple integrity constraints can be violated through several updates and because often a multitude of repairs exist. The methods proposed so far for integrity maintenance [KM90, ML91, CFPT92, Wüt93, TO95, Dec96] have been mainly concerned with the generation of a complete set of repairs of integrity constraints violations, but they have paid little attention to efficiency issues. Thus, for instance, when a constraint is repaired all other constraints are checked for consistency even though they were already satisfied prior to the repair and they could not be violated by the performed repair. In this paper we propose a technique for determining the order in which integrity constraints should be handled to minimize the number of times that an integrity constraint must be reconsidered; improving in this way efficiency of the whole integrity maintenance process. This technique provides two important advantages. First, it minimizes the number of recomputations of testing whether a given constraint is violated. Second, it ensures that a repair of a certain integrity constraint is performed only when all repairs of other constraints that could induce a violation of it have been performed. Our technique is based on the definition of a graph, the Precedence Graph, which explicitly states all relationships between repairs and potential violations of integrity constraints. Information provided by this graph is directly applicable to the methods we have proposed in the past for handling consistent updates in deductive databases [MT93, MT95, TO92, TO95] and it could be easily adapted to be applicable to other existing methods. A different approach to enforce database consistency is integrity checking; which is concerned with developing methods for checking whether a given update violates an integrity constraint (see for example [Oli91, GCMD94]). In this case, when a violation is detected, the transaction is rejected. Both integrity constraint enforcement approaches are reasonable [Win90]. The correct choice of an approach for a particular integrity constraint depends on the semantics of the integrity constraint and of the deductive database. Most of the existing methods are only concerned with handling one of the approaches in an isolated manner, without taking into account the strong relationship between the problems to be solved in both cases. As far as we know, the only proposal towards this direction is that of [CHM95] which presents a method that follows the integrity checking approach, but makes some exceptions by using certain constraints to suggest new updates. To further contribute to enforcing database consistency, we also propose in this paper a technique for integrating the treatment of integrity checking and integrity maintenance. This technique is based on incorporating also in the previous graph the information corresponding to the integrity constraints to be checked, and considering its relationship with constraints to be maintained. This paper is organised as follows. Next section reviews basic concepts of deductive databases. Section 3, which is based on [Oli91, UO92], reviews the concepts of event, transition rules and event rules. In Section 4 we propose the Precedence Graph as a tool for structuring the process of integrity enforcement. In Section 5 we propose a mechanism to execute that graph. In Section 6 we relate our approach to other relevant previous work. Finally, in Section 7 we summarize our conclusions. 2. Deductive Databases In this section, we briefly review some definitions of the basic concepts related to deductive databases [Llo87, Ull88] and present our notation. Throughout the paper, we consider a first order language with a universe of constants, a set of variables, a set of predicate names and no function symbols. We will use names beginning with a capital letter for predicate symbols and constants (with the exception that constants are also permitted to be numbers) and names beginning with a lower case letter for variables. A term is a variable symbol or a constant symbol. If P is an m-ary predicate symbol and t1, ..., tm are terms, then P(t1, ..., tm) is an atom. The atom is ground if every ti (i = 1, …, m) is a constant. A literal is defined as either an atom or a negated atom. A fact is a formula of the form: P(t1, ..., tm) ←, where P(t1, ..., tm) is a ground atom. A deductive rule is a formula of the form: P(t1, ..., tm) ← L1 ∧...∧ Ln, with n ≥ 1, where P(t1,..., tm) is an atom denoting the conclusion, and L1,...,Ln are literals representing conditions. Any variable in P(t1, ..., tm), L1, ..., Ln is assumed to be universally quantified over the whole formula. A derived predicate P may be defined by means of one or more deductive rules. In this paper, we assume that all variables appearing in some condition of a rule appear also in its head. An integrity constraint is a closed first-order formula that the deductive database is required to satisfy. We deal with constraints in denial form: ← L1 ∧ ... ∧ Lm, with m ≥ 1, where the Li are literals and all variables are assumed to be universally quantified over the whole formula. More general constraints can be transformed into this form by first applying the range form transformation [Dec89] and then using the procedure described in [LT84]. For the sake of uniformity, we associate to each integrity constraint an inconsistency predicate Icn, with or without terms, and thus they have the same form as the deductive rules. We call them integrity rules. Then, we rewrite the former denial as: Icn ← L1 ∧ ... ∧ Lm, with m ≥ 1 A deductive database D is a triple (EDB, IDB, IC), where EDB is a set of facts, IDB a set of deductive rules and IC a set of integrity constraints. The set EDB of facts is called the extensional part of the database and the set of deductive rules and integrity constraints is called the intensional part. We assume that deductive database predicates are partitioned into base and derived (view) predicates. A base predicate appears only in the extensional part and (eventually) in the body of deductive rules. A derived predicate appears only in the intensional part. Any database can be defined in this form [BR86]. We deal with stratified databases [Llo87] and, as usual, we require the database to be allowed [Llo87]; that is, any variable that occurs in a deductive rule has an occurrence in a positive condition of an ordinary predicate. Example 2.1: The following example of deductive database which is concerned about members of a club or an association will be used throughout the paper: Acc(Paul) Rec(Paul) Part(Paul) Mem(x) ← Rec(x) ∧ Acc(x) Active(x) ← Part(x) Ic1(x) ← Acc(x) ∧ Neg(x) Ic2(x) ← Active(x) ∧ ¬ Mem(x) Ic3(x) ← Rec(x) ∧ ¬ Part(x) This database contains four base predicates and two derived ones: Rec(x) states that a person x is recommended to be member of a club Acc(x) states that a person x is accepted as a member of the club Part(x) states that a person x has some participation in an activity of the club Neg(x) states that a person x has a negative report Mem(x) states that a person x is a member of a club if he/she is recommended and accepted Active(x) states that a person x has an active attitude if he/she participates in an activity of the club Notice that the database contains also three integrity constraints stating, respectively, that people that are accepted to the club could not get a negative report; that people with an active attitude must be members; and, that it is required that a recommended person participates in some activity. 3. The Augmented Database The main goal of this paper is to propose a technique for determining the order in which integrity constraints should be handled. This order is provided by the Precedence Graph, which explicitly states all relationships between repairs and potential violations of integrity constraints. The definition of this graph, given in next section, will take into account a set of rules that precisely define the difference between two consecutive database states. This set of rules, together with the original database D, form the Augmented Database [Oli91, UO92], denoted by A(D), which explicitly defines the insertions and deletions induced by a transaction T that consists of a set of base fact updates. The concept of Augmented Database is strongly based on the concept of event. For each predicate P in the underlying language of a given deductive database D, a distinguished insertion event predicate ιP and a distinguished deletion event predicate δP are used to define the precise difference of deducible facts of consecutive database states. If P is a base predicate, ιP and δP facts (called base event facts) represent insertions and deletions of base facts, respectively. For this reason, we assume that a transaction T consists of a set of base event facts. If P is a derived predicate, ιP and δP facts represent induced insertions and induced deletions, respectively. If P is an inconsistency predicate, ιP represents a violation of the corresponding integrity constraint. For inconsistency predicates, δP facts are not defined since we assume that the database is consistent before the update. The definition of ιP and δP depends on the definition of P in D, but is independent of any transaction T and of the extensional part of D. For each derived or inconsistency predicate P, the Augmented Database contains the rules about ιP and δP, called event rules, which define exactly the insertions and deletions of facts about P that are induced by some transaction T. Event rules are defined as follows: ιP(x) ← Pn(x) ∧ ¬P(x) δP(x) ← P(x) ∧ ¬Pn(x) where P refers to a predicate evaluated in the old state of the database, Pn refers to the predicate P evaluated in the new state of the database and x is a vector of variables. The Augmented Database contains also a set of transition rules associated to each derived or inconsistency predicate P. These transition rules define the evaluation of predicate P in the new state (denoted by Pn) in terms of the old state of the database and the events that occur in the transition between both states. We illustrate event and transition rules by means of an example. Example 3.1: Consider the derived predicate Mem(x) from example 2.1 defined by the rule Mem(x) ← Rec(x) ∧ Acc(x). Event and transition rules associated to this predicate are the following: ιMem(x) ← Memn(x) ∧ ¬Mem(x) δMem(x) ← Mem(x) ∧ ¬Memn(x) Memn(x) ← Rec(x) ∧ ¬δRec(x) ∧ Acc(x) ∧ ¬δAcc(x) Memn(x) ← Rec(x) ∧ ¬δRec(x) ∧ ιAcc(x) Memn(x) ← ιRec(x) ∧ Acc(x) ∧ ¬δAcc(x) Memn(x) ← ιRec(x) ∧ ιAcc(x) Transition rules for Memn(x) define all possible ways of having facts about Mem(x) in the new state. The first one corresponds to the case that a fact of Mem(x) was true in the old state and has not been deleted by the transaction, while the others reflect all possible ways to insert a fact of Mem(x) by the transaction. Given a deductive database D, the Augmented Database A(D) consists of D, its transition rules and its event rules. Description and discussion of the procedure for automatically deriving an Augmented Database from a database can be found in [Oli91, UO92]. These references also describe several syntactical simplifications of transition and event rules. Example 3.2: The following example shows the Augmented Database of example 2.1, after simplification. Mem(x) ← Rec(x) ∧ Acc(x) Active(x) ← Part(x) Ic1(x) ← Acc(x) ∧ Neg(x) Ic2(x) ← Active(x) ∧ ¬ Mem(x) Ic3(x) ← Rec(x) ∧ ¬ Part(x) ιMem(x) ← Rec(x) ∧ ¬ δRec(x) ∧ ιAcc(x) ιMem(x) ← ιRec(x) ∧ Acc(x) ∧ ¬ δAcc(x) ιMem(x) ← ιRec(x) ∧ ιAcc(x) δMem(x) ← δRec(x) ∧ Acc(x) δMem(x) ← Rec(x) ∧ δAcc(x) ιActive(x) ← ιPart(x) δActive(x) ← δPart(x) (C1)ιIc1(x) ← Acc(x) ∧ ¬ δAcc(x) ∧ ιNeg(x) (C2)ιIc1(x) ← ιAcc(x) ∧ Neg(x) ∧ ¬ δNeg(x) (C3)ιIc1(x) ← ιAcc(x) ∧ ιNeg(x) (C4)ιIc2(x) ← Active(x) ∧ ¬ δActive(x) ∧ δMem(x) (C5)ιIc2(x) ← ιActive(x) ∧ ¬ Mem(x) ∧ ¬ ιMem(x) (C6)ιIc2(x) ← ιActive(x) ∧ δMem(x) (C7)ιIc3(x) ← Rec(x) ∧ ¬ δRec(x) ∧ δPart(x) (C8)ιIc3(x) ← ιRec(x) ∧ ¬ Part(x)) ∧ ¬ ιPart(x) (C9)ιIc3(x) ← ιRec(x) ∧ δPart(x) Rules C1 to C9 define all possible ways of inserting facts about predicates Ic1, Ic2 and Ic3. These rules deserve special attention since they define all possible situations in which database consistency is violated by the application of some transaction. 4. Structuring the Process of Integrity Maintenance Structuring the process of integrity maintenance is concerned with determining the order in which integrity constraints should be handled. This order is provided by the Precedence Graph, which explicitly states all relationships between repairs and potential violations of integrity constraints. In this section we define how this graph is obtained and how it can be used for integrating integrity maintenance and integrity checking. To obtain the Precedence Graph we only take into account syntactical information associated to the definition of each integrity constraint. Thus, we do not need to consider the contents of the EDB nor the transaction to be applied to the database. Therefore, we generate the Precedence Graph at definition time, and we delay to run time to test whether potential dependencies defined in the graph correspond to real violations. We take advantage of assuming that the database is consistent before the application of a transaction T. Then, violations of database consistency due to the transaction T are only produced because some insertion event rule associated to an integrity constraint becomes true. Moreover, repairs of the constraint are defined by the violated insertion event rule, since a repair corresponds to an additional update that falsifies the effect of T on the corresponding event rule. For this reason, we refer to the insertion event rules of an integrity constraint as the conditions of that integrity constraint. In order to state dependencies between integrity constraints more precisely, we consider the conditions associated to an integrity constraint instead of the own integrity constraint definition. Thus, the Precedence Graph will state all relationships between repairs and potential violations of these conditions. Example 4.1: Conditions associated to integrity constraint Ic1 of the example 3.2 are the following: Identifier Condition C1← Acc(x) ∧ ¬ δAcc(x) ∧ ιNeg(x) C2← ιAcc(x) ∧ Neg(x) ∧ ¬ δNeg(x) C3← ιAcc(x) ∧ ιNeg(x) Note that each condition describes a situation to be avoided to ensure that an update does not violate integrity constraint Ic1. Therefore, ensuring that no condition holds we guarantee that no integrity constraint is violated. In the following we will refer to each condition by its identifier Ci (i=1..n). 4.1 Events Dependency Graph Several derived events and several conditions may be induced when applying a transaction consisting of a set of base event facts. For instance, in the previous example the application of the base event ιAcc may induce the derived event ιMem as well as conditions C2 and C3. Obtaining the Precedence Graph requires to determine which repairs of a condition are potential violations of other conditions. To determine this information, we need first to explicitly state the relationship between base events and their effect on derived events and conditions. Given the Augmented Database A(D), we can identify the following dependencies: Definition 4.1 Let E be an event and C be a condition or a derived event. We say that C directly depends on E if there is a rule in A(D) with event C as head and such that E appears in its body. A direct dependence is positive (resp. negative) if E is a positive literal (resp. negative). By considering together all direct dependencies between events and conditions we can build the Events Dependency Graph [Cos95], which explicitly states the relationship between the application of events on a database and their induced effect, and which builds the basis for the process of structuring integrity maintenance. Definition 4.2 An Events Dependency Graph EDG for a set of events and a set of conditions, is a pair EDG = <Nod, Edg> where Nod is a finite number of nodes, Edg ⊆ (Nod x Nod) is a set of directed edges such that each node n ∈ Nod is labelled with a condition identifier or an event . Given two nodes v and v', there exists an edge e=(v,v') iff v' directly depends on v. Edges are marked positive (resp. negative) if the dependence is positive (resp. negative). Example 4.2: Consider again the database D of Example 3.2. Figure 1 represents the Events Dependency Graph derived from the Augmented Database A(D). Black arrows correspond to positive edges, while grey arrows correspond to the negative ones. C1 C2C3 C4 C5C6 ιRec δRec ιNeg δNeg ιAcc δAcc ιPart δPart ιMem δMem ιActive δActive C7C8 C9 Fig.1. Events Dependency Graph of our example Definition 4.3 Let EDG be an Events Dependency Graph and v and v' two nodes in EDG. We say that: - v depends on v' if EDG contains a path from v' to v. - v depends evenly (resp. oddly) on v' if there is a path from v' to v in EDG containing an even (resp. odd) number of negative edges. Dependencies between events and conditions allow us to determine potential violations and repairs of a condition. Intuitively, a potential violation of a condition Ci is an event that when applied to the database may induce an insertion of the inconsistency predicate associated to Ci. That is, Ci may become true due to that event. On the other hand, a potential repair of a condition Ci is a base event that when applied to the database may falsify Ci. This notion can also be generalized for derived events and we will refer to them as potential falsifiers. This information can be syntactically identified by considering the dependencies defined by the Events Dependency Graph. Definition 4.4 Let E be an event and Ci a condition. - E is a potential violation of Ci if Ci depends evenly on E. - E is a potential repair of Ci if E is a base event and Ci depends oddly on E. - E is a potential falsifier of Ci if E is a derived event and Ci depends oddly on E. At definition time we can not ensure that an event will be a real violation of a certain condition at run time since the database must also satisfy other requirements that may be unknown at this moment. This is why we talk about potential violations. We talk about potential repairs and falsifiers since, in general, repairing a condition may require the application of more than one event. Example 4.3: Consider again condition C2 of Example 3.2: C2 ← ιAcc(x) ∧ Neg(x) ∧ ¬ δNeg(x) Event ιAcc(x) is a potential violation of C2 because it could make C2 true depending on the rest of literals of the condition. Event δNeg(x) is the only potential repair of condition C2. It may happen that no potential repair exists for a certain condition. So, we distinguish between two different kinds of conditions. Checking conditions are those that have no potential repair; while conditions with some potential repair are called generation conditions. Each condition can be classified only into one of these two categories. Definition 4.5 Let Ci be a condition. Ci is a checking condition if there is no potential repair associated to it. Otherwise, Ci is a generation condition. Checking conditions of the example are C3, C6 and C9. All other conditions are generation conditions. 4.2 Precedences Between Conditions We are interested on minimizing the number of times that a condition should be reconsidered. For this reason, we should first deal with those conditions whose repairs may induce a violation of other conditions. The Events Dependency Graph does not tell us which conditions should precede which others, but it provides the basis for determining this information. In general, a condition will have several potential repairs. Moreover, due to the multilevel structure of derived predicates, derived events must also be considered when determining precedences among conditions. Thus, some of the potential repairs may be meaningless since they are already implied by considering potential falsifiers. Therefore, we have to define first which are the meaningful events that must be considered to determine the precedence between two conditions. We call them meeting events and they are defined as follows: Definition 4.6 Let Ci and Cj be two different conditions. A base or derived event E is a meeting event if one of the following conditions holds: - it appears in the definition of both Ci and Cj. - it appears in the definition of Ci and it defines a derived event that appears in Cj but not in Ci - it defines a derived event that appears in Ci and another derived event that appears in Cj but not in Ci. Intuitively, it can be seen that to determine the precedence between two conditions we have to consider only those events that participate on the definition of both conditions. This may be done either explicitly by considering the definition of the conditions or implicitly by taking into account the derived events they define and that appear in the definition of the conditions. Example 4.4: Consider again the database example 3.2. The only meeting event for conditions C1 and C4 is δAcc(x); while meeting events for conditions C4 and C7 are δRec(x) and δPart(x). Now, by taking into account meeting events we can identify precedences between conditions. Intuitively, condition Ci must precede condition Cj if there exists a meeting event that, depending on whether it holds or not, it may falsify condition Ci and satisfy condition Cj. That is, this event will be considered when generating a - Remove_Mark (C, GT): it unmarks node C from GT and returns the new marked graph. - Select_Next_Node (GT): given a marked graph GT it selects the next node to be processed. Nodes with unmarked predecessors are selected with priority. If there are different candidates to select, nodes corresponding to checking conditions are considered first. This helps to improve efficiency of the whole process since if this condition is violated, no other node will be considered. - Check_Condition (C, T): given a condition C and a transaction T, it tests whether C is violated by T. To improve efficiency, this can be done by means of any arbitrary method for integrity checking. - Compute_All_Repairs (C, T): given a condition C and a transaction T, it returns the set of all possible repairs of C. This function must take into account the translation of potential falsifiers into potential repairs. Treatment of subgraphs is performed by means of a recursive call to the function Execute_Graph(T, GT), where T is the current transaction and GT corresponds to the subgraph defined by the selected node. Example 5.1: Consider again the database of example 4.8 and its associated Precedence Graph shown in Fig.4. The following table summarizes the execution of the Precedence Graph given the initial transaction T = {ιNeg(Paul)}. In each row, an 'V' shows the node selected at each step and an 'X' indicates that a node is marked. The column 'Transaction' indicates which events belong to the transaction T and each new inclusion into it is denoted in italic. C 1 C 2 C 3 C4 C 5 C 6 C 7 C 8 C9 C 10 C1C1Transaction VXιNeg(Paul), δ Acc(Paul) XXXVιNeg(Paul),δAcc(Paul) XXVιNeg(Paul),δAcc(Paul) VXιNeg(Paul),δAcc(Paul) VιNeg(Paul),δAcc(Paul), δ Part(Paul) VιNeg(Paul),δAcc(Paul), δPart(Paul), δ Rec(Paul) Initially, marked nodes are C1 and C3. Node C1 is selected first because it does not have any predecessor. Transaction T violates it, and it is repaired with the event δAcc(Paul). Then, node C1 is unmarked and nodes C4, C5 and C6 are marked. In next steps, nodes C6, C5 and C3 are selected in this order and unmarked since their corresponding conditions are not violated by the current transaction. At step 5 condition of node C4 is violated, and it is repaired by including δPart(Paul) in the transaction. As a consequence, node C7 is marked and it is considered at step 6. Since C7 is violated, the additional event δRec(Paul) is included in the transaction. After this step, there is no marked node in the Precedence Graph. Then, the integrity maintenance process finishes and the transaction T'={ιNeg(Paul), δAcc(Paul), δPart(Paul), δRec(Paul)} is obtained. Note that this is the only transaction that maintains database consistency in our example. To maintain database consistency in this example, we have processed only 6 conditions. In particular, we should note that none of them has been considered more than once. On the contrary, if we had not taken into account the information provided by the Precedence Graph, 45 conditions would had been processed. The reason is that in the latter case, when a condition is repaired all other conditions must be checked again for consistency even though they were already false prior to the repair and they could not be violated by it. This important drawback is shared by all methods proposed up to now for integrity maintenance. In fact, it is sufficient for us that only one integrity constraint is repaired to have a better performance than integrity maintenance methods proposed up to now. Even in this simple case, current methods must reconsider again previously processed constraints. The number of unnecessary constraints processed by these methods significantly increases when the complexity of the database, of the considered transactions and of the number of necessary repairs augments. 6. Relation with Previous Work A significant amount of work has been devoted to the area of integrity checking to define the order in which derived predicates should be evaluated to optimize the test of whether a transaction violates an integrity constraint [Ple93, Sel95]. In this sense, several graphs that define this order have been proposed. Similar work has been performed in the area of active databases to explicitly state the relationship between the activation of rules for predicting termination and confluence of active rules [BW94, KU94, AHW95]. Work in these two areas is different from ours since we are aimed at determining the order in which integrity constraints should be handled and not the order of evaluation of predicates involved in an integrity constraint definition. In fact, this latter order is defined by our Events Dependency Graph which states the relationship between base events and their potential effect on derived events and conditions. However, as we have seen, this graph is not sufficient to determine the order of processing integrity constraints. Work most related to ours has been proposed in the area of integrity maintenance. As we said, methods proposed up to date in this area have paid little attention in efficiency issues. A significative exception is the work performed by Gertz in [Ger93, Ger94, GL93], which is considered in detail in the following subsection. 6.1 Gertz's Approach [Ger93, Ger94] Gertz proposes to carry out at definition time the analysis and the specification of reactions on constraint violations. In this sense, he provides a declarative specification language for reactions on violations suitable to express several integrity constraints enforcement approaches. He describes how to obtain, once the integrity constraints and their corresponding reactions have been specified by the designer, a dependency graph which expresses the relationship between repairs and potential violations of integrity constraints. Finally, he presents also a procedure for deriving integrity enforcing triggers from this dependency graph. Execution of these triggers guarantees that a transaction applied to a database maintains the integrity constraints. Several differences exist between Gertz's proposal and ours. The first one is related to the way of handling integrity maintenance. Gertz proposes the designer to explicitly specify reactions to integrity constraints violations, while we consider these reactions to be automatically generated from the definition of the integrity constraints. Thus, looking for dependencies between integrity constraints is more complex in our approach since they are not explicitly stated and have to be implicitly derived from the integrity constraints definition. Another important difference refers to the expressiveness of the definition language considered in both proposals. Gertz's proposal is restricted to databases without deductive rules, thus considering only flat integrity constraints (i.e. constraints that are defined only by means of base predicates); and it is restricted also to integrity constraints in Implicative Normal Form (which does not allow negation in the body of a constraint). On the contrary, we handle deductive rules as well as non-flat integrity constraints and we allow negation to appear in the body of the rules and of the constraints (in fact, the only requirements we impose on the database are those of allowedness and stratification which are much more general than Gertz requirements). Thus, our technique can be applied in more cases than Gertz's technique. It is also worth to mention the additional complexity of our approach due to the fact that we have to take the definition of derived predicates into account. Finally, if more than one dependency exists between two integrity constraints, Gertz forces to the designer to weight all possible reactions to indicate which reaction should be considered with priority. Thus, it is guaranteed that at execution time only one repair is considered for a concrete violation of an integrity constraint. On the contrary, we take into account all possible repairs of a given integrity constraint definition. Thus, we will be able to restore database consistency in cases where Gertz approach is not able to do it since the designer may not have appropriately weighted the repairs of integrity constraints. 7 Conclusions In this paper we have proposed a technique for improving efficiency of the integrity maintenance process. This technique is based on the definition and execution of a graph, the Precedence Graph, which explicitly states the relationship between repairs of an integrity constraint and potential violations of other integrity constraints. The proposed technique contributes to improving efficiency of integrity maintenance in two different ways. First, it minimizes the number of recomputations of testing whether a given constraint is violated. Second, it ensures that a repair of a certain integrity constraint is performed only when all repairs of other constraints that could induce a violation of it have been performed. Another contribution of the technique proposed in this paper is that it allows to take into account integrity constraints to be checked in addition to integrity constraints to be maintained. Thus, we have shown a possible way of integrating into a single method both integrity constraint enforcement approaches. Acknowledgements We are grateful to D. Costal, A. Olivé, J. A. Pastor, C. Quer, M. R. Sancho, J. Sistac and T. Urpí for many useful comments and discussions. This work has been partially supported by the CICYT PRONTIC program project TIC94-0512. References [Abi88] Abiteboul, S. "Updates, a New Frontier", Int. Conf. on Database Theory (ICDT'88), Springer, 1988, pp.1-18. [AHW95] Aiken, A.; Hellerstein, J.M.; Widom, J. "Static Analysis Techniques for Predicting the Behavior of Active Database Rules", ACM Transactions on Database Systems, Vol. 20, Nº 1, Mrach 1995, pp. 3-41. [BR86] Bancilhon, F.; Ramakrishnan, R, "An Amateur's Introduction to Recursive Query Processing", Proc. ACM SIGMOD Int. Conf. on Management of Data, Washington D.C., 1986. [BW94] Baralis, E.; Widom, J. "An Algebraic Approach to Rule Analysis in Expert Database Systems", Proc. of the 20th VLDB Conference, Santiago, Chile, 1994, pp. 475-486. [GCMD94] García, C.; Celma, M; Mota, L.; Decker, H. "Comparing and Synthesising Integrity Checking Methods for Deductive Databases", Int. Conf. on Data Engineering (ICDE'94), Houston (Texas), 1994, pp. 214-222. [CHM95] Chen, I.A.; Hull, R.; McLeod, D. "An Execution Model for Limited Ambiguity Rules and Its Application to Derived Data Update". ACM Transactions on Database Systems, Vol. 20, Nº 4, December 1995, pp. 365-413. [Cos95] Costal, D. "Un mètode de planificació basat en l'actualització de vistes en bases de dades deductives", PhD Thesis, Barcelona, 1995 (in catalan). [CW90] Ceri, S.; Widom, J. "Deriving Production Rules for Constraint Maintenance", Proc. of the 16th VLDB Conference, Brisbane, Australia, 1990, pp. 566-577. [CFPT92] Ceri, S.; Fraternali, P.; Paraboschi, S.; Tanca, L. "Integrity Maintenance Systems: an architecture", Third Int. Workshop on the Deductive Approach to Information Systems and Databases, Roses, Catalonia, 1992, pp. 327-344. [Dec89] Decker, H. "The Range Form of databases or: How to avoid Floundering", Proc. 5th ÖGAI, Springer-Verlag, 1989. [Dec96] Decker, H. "An Extension of SLD by Abduction and Integrity Maintenance for View Updating in Deductive Databases", To appear in Joint International Conference and Symposium on Logic Programming (JICSLP'96), Bonn (Germany), 1996. [Ger93] Gertz, M. "On Specifying the Reactive Behavior on Constraint Violations", Informatik-Berichte 2/93, Institut für Informatik, Universität Hannover, 1993. [GL93] Gertz, M.; Lipeck, U.W. "Deriving Integrity Maintaining Triggers from Transaction Graphs", International Conference on Data Engineering (ICDE'93), Vienna, 1993, pp. 22-29. [Ger94] Gertz, M. "Specifying Reactive Integrity Control for Active Databases", Research Issiues on Data Engineering: Active Databases (RIDE-ADS'94), Houston, Texas, 1994, pp. 62-70. [KM90] Kakas, A.; Mancarella, P. "Database Updates through Abduction", Proc. of the 16th VLDB Conference, Brisbane, Australia, 1990, pp. 650-661. [KU94] Karadimce, A.P.; Urban, S.D. "Conditional Term Rewriting as a Formal Basis for Analysis of Active Database Rules" Research Issiues on Data Engineering: Active Databases (RIDE-ADS'94), Houston, Texas, 1994, pp. 156-162. [Llo87] Lloyd, J.W. "Foundations on Logic Programming", 2nd edition, Springer, 1987. [LT84] Lloyd, J.W.; Topor, R.W. “Making Prolog More Expressive”. Journal of Logic Programming, 1984, No. 3, pp. 225-240. [ML91] Moerkotte, G; Lockemann, P.C. "Reactive Consistency Control in Deductive Databases", ACM Transactions on Database Systems, Vol. 16, No. 4, December 1991, pp. 670-702. [MT93] Mayol, E.; Teniente, E. " Incorporating Modification Requests in Updating Consistent Knowledge Bases", Fourth Int. Workshop on the Deductive Approach to Information Systems and Databases, Lloret de Mar, Catalonia, 1993, pp. 335-360. [MT95] Mayol, E.; Teniente, E. "Towards an Efficient Method for Updating Consistent Deductive Databases", Basque International Workshop on Information Techlogogy (BIWIT'96): Data Management Systems, IEEE Computer Society Press, San Sebastian, Spain, 1996, pp. 113-122. [MT96] Mayol, E.; Teniente, E. "Analysing the Process of Enforcing Integrity Constraints", Technical Report RR-96/38, 1996, Universitat Politècnica de Catalunya. [Oli91] Olivé, A. "Integrity Checking in Deductive Databases", Proc. of the 17th VLDB Conference, Barcelona, Catalonia, 1991, pp. 513-523. [Ple93] Plexousakis, D. "Integrity Constraint and Rule Maintenance in Temporal Deductive Knowledge Bases", Proc. of the 19th VLDB Conference, Dublin, Ireland, 1993, pp. 146-157. [Sel95] Seljée, R. "A New Method for Integrity Constraints Checking in Deductive Databases", Data & Knowledge Engineering, Vol. 15, 1995, pp. 63-102. [TO92] Teniente, E.; Olivé, A. "The Events Method for View Updating in Deductive Databases", Int. Conf. on Extending Database Technology (EDBT’92), Vienna, 1992, pp. 245-260. [TO95] Teniente, E.; Olivé, A. "Updating Knowledge Bases while Maintaining their Consistency", The VLDB Journal, Vol. 4, Num. 2, 1995, pp. 193-241. [TU95] Teniente, E.; Urpí, T. "A Common Framework for Classifying and Specifying Deductive Database Updating Problems", International Conference on Data Engineering (ICDE'95), Taipei, 1995, pp. 173-182. [Ull88] Ullman, J.D. "Principles of Database and Knowledge-Base Systems", Computer Science Press, New York, 1988. [UO92] Urpí, T.; Olivé, A. "A Method for Change Computation in Deductive Databases", Proc. of the 18th VLDB Conference, Vancouver, 1992, pp. 225237. [Win90] Winslett, M. "Updating Logical Databases", Cambridge Tracts in Theoretical Computer Science 9, 1990. [Wüt93] Wüthrich, B. "On Updates and Inconsistency Repairing in Deductive databases", Int. Conf. on Data Engineering, Vienna, 1993, pp. 608 - 615.