5 Backward Propagation

|Title |Introduction |Integrating App's |Integrity Maintenance |AOODB Model |Backward Propagation |HVC |Constraint Maintenance |Conclusion |References|
5 Backward Propagation
since 24 June, 1996, last modified 24 June, 1996

Even if the current trigger mechanism of AOODBSs is known to be an effective tool for user-defined integrity constraints, it cannot adequately support certain integrity constraints defined on a class composition hierarchy. When a constraint is specified on multiple classes that consist of a class composition hierarchy, an update on a participating object in a leaf class of the hierarchy should be propagate to whole the hierarchy to confirm the acceptance of the update. The propagation against the class composition hierarchy of the updated object is impossible in most object-oriented databases [Bert93]. The deficiency in the object-oriented databases prohibits the proper constraint checking and enforcement on the participating classes. We call the propagation against the class composition hierarchy, the backward propagation and provide resolution methods (the backward propagation approaches).
Current AOODBSs without the backward propagation capability cannot adequately support integrity constraints specified on a class composition hierarchy. No AOODBSs, known to date, provide facilities for the backward propagation. In this chapter, we investigate the problem of the backward propagation and how to support it using the model presented in the previous chapter. We chose an approach to enhance an existing DBS [UniS93a] to allow the backward propagation.
Three backward propagation approaches are considered. The first approach is to simply attach a trigger with a method (or an expression) which checks the integrity constraint to each participating class. The second approach is to place a method for integrity constraint checking only in the root class of the hierarchy and call the method when there is an update on each participating class. The third approach is to use a virtual class which is a counterpart of the view in relational DBSs. A virtual class is to be built from all the participating classes to properly maintain the integrity constraint. In Chapter 5, we will propose an integrity constraint constructor with the backward propagation capability based on the third method.
This chapter is organized as follows. The backward problem is illustrated with an example in Section 5.1. In Section 5.2, the concept of the backward propagation is discussed along with a more general example. In Section 5.3, we describe three backward propagation approaches to resolve the illustrated problem.
5.1 Problems in User Defined Integrity Constraint

To illustrate the backward propagation problem, we provide the following example.

Figure 5-1 Part class and its weight integrity constraint

Figure 5-2 Class and object diagram for the Part class in the Object Modeling Technology (OMT) notation [Rumb91]

The class composition hierarchy in Figure 5-1 and Figure 5-2 includes the'Part' and 'Material 'classes'. The user has defined objects 'p' and 'm' which are instances of the 'Part 'and 'Material 'classes, respectively (in the figure, they are denoted by 'p:Part' and 'm:Material)'. The domain of the 'material_type' attribute is the 'Material' class, and the value of the attribute of object 'p' is object 'm' ('p.material_type=m' in the figure). The 'Part 'class has the 'PartWeight()' method for weight calculation. The method calculates the weight of a 'Part' class instance by multiplying its volume and the density of its material which are denoted by 'p.volume' and 'p.material_type.density', respectively. Containing the method in the condition clause, the trigger named 'weight_constraint' is defined on the 'Part' class. It tests the weight returned from the method application and decides whether an update can be committed.

To elaborate the mechanism of checking the integrity constraint with the trigger, we will trace the transition of database states caused by updates on participating classes. The current state 'S' of the database is specified as follows:

S = {p.volume = 30, m.density = 2, ...}

Once we update 'p.volume' in state 'S' from 30 to 60, the database transits from state 'S' to a new state 'S'':

S' = {p.volume = 60, m.density = 2, ...}

After the transition, the weight of object 'p' in state 'S'' becomes 120. This violates the integrity constraint defined in the 'weight_constraint' trigger. The transaction will be invalidated by the trigger and rolled back to state 'S'.

Given the 'weight_constraint' trigger definition, the weight of each instance of the 'Part' class is guaranteed to be less than 100 against updates on the 'Part' class. The weight integrity constraint, however, cannot be properly enforced if there is an update on the 'Material' class. To show the problem, consider another case of an update on the 'Material' class which changes the value of 'm.density' from 2 to 5. The new database state 'S"' is as follows:

S" = {p.volume = 30, m.density = 5, ...}

Values of 'p.volume' and 'm.density' in state 'S"' cause the weight of object 'P' to be 150, which violates the integrity constraint. However, the transaction is successfully committed, and the database is left in an inconsistent state. It is because a trigger for the weight integrity constraint is not defined on the 'Material' class. In the 'weight_constraint' trigger definition, both object 'p' and object 'm' participate. So, the trigger definition on object 'p' alone cannot enforce the weight integrity constraint when an update on object 'm' occurs.

As observed in the above example, integrity constraints defined on a class composition hierarchy must be maintained not only in the forward direction along the class composition hierarchy but also in the backward direction (e.g., from the 'Material' class to the 'Part' class). We call the enforcement of an integrity constraint in the backward direction along a class composition hierarchy the backward propagation of the integrity constraint.

5.2 Concept of The Backward Propagation

When an integrity constraint involves several classes (that is, the integrity constraint defines a condition that must be satisfied by the classes participating in the constraint), as illustrated in Section 5.1, constraint checking must be done in each participating class. This means that the constraint definition and constraint checking must be duplicated in each participating class. In other words, if some of the participating classes do not have the constraint definition and checking mechanism, the constraint may not be preserved when an update occurs on one of those classes.
We investigate the problem that arises when the participating classes of an integrity constraint form a class composition hierarchy, since it offers an interesting research opportunity and sheds light on the issue of integrity constraints involving several classes. We will assume that initially only the root class has the trigger with a method (or an expression) for constraint checking and enforcement. The backward propagation of an integrity constraint is to have all participating classes satisfy the constraint defined on the root class of a class composition hierarchy.
Our research focus is to facilitate definition of triggers and/or methods for the constraint in the non-root classes (i.e., intermediate classes or leaf classes) participating in the constraints. Further, avoiding duplication of evaluation for constraint checking and reducing overhead are other research concerns. For instance, we seek to avoid duplicating the method in all participating classes.
To define a trigger and/or method for the integrity constraint on an intermediate class or leaf class requires referencing classes in the backward direction of the hierarchy. Contrary, forward referencing of participating classes in an integrity constraint defined on a class composition hierarchy is accommodated via object identifiers. Most existing OODBSs do not offer a mechanism for retrieving required classes in the backward direction except for the join operation [Bert93]. So, we look for ways to reduce referential complexity when using currently available mechanism such as join operation.
The example in Section 5.1 is a simple case which has only one level class composition hierarchy. Real applications may include complex multi-level class composition hierarchies and shared objects. The multi-level class composition hierarchy means a nested composition hierarchy among more than

Figure 5-3 Weight integrity constraint on Machine class

two classes. The shared object is an object that is referenced by more than two objects. The following is an example of an integrity constraint which is specified on a complex class composition hierarchy.

Figure 5-3 (continued) Weight integrity constraint on Machine class

Figure 5-3 shows that instance 'c' of the 'Machine' class (denoted by 'c:Machine') has attribute 'components' whose value is a set of the 'Assy_Part' objects, 'ap1' and 'ap2' (c.components = {ap1, ap2}' in the figure). Objects 'ap1' and 'ap2' have sets of 'Part' objects (assume that the 'Part' class has the same definition as in Figure 5-1) as their 'sub_part' attribute values (denoted by 'ap1.sub_part = {p1,p2}' and 'ap2.sub_part={p2,p3}'). The 'Machine' class has the 'MachineWeight() 'method to calculate its weight. The method calculates the weight of a 'Machine' object from the attribute values referenced through class composition hierarchy (in fact, it calls the 'AssyPartWeight()' method which in turn calls the 'PartWeight()' method of the 'Part' class). Figure 5-4 depicts the class and object hierarchies.
In the example, if the user defines a trigger for the machine's weight integrity constraint only on the 'Machine' class (the 'trigger_1' trigger in the figure), updates on other classes such as the 'Assy_Part', 'Part' and 'Material' classes on a path from the root class to the leaf class of the hierarchy will cause the backward propagation problem. Furthermore, multi-level class composition hierarchies (e.g., 'c.components.sub_part.material_ type') and shared objects (e.g., the 'p2' object shared by 'ap1' and 'ap2') make the backward propagation more complex.

As mentioned earlier, referencing objects in the backward direction of a class composition hierarchy is impossible in some current OODBSs. However, since the data model we employ, provides the join operation between classes, we can use it to retrieve required classes in the backward direction along the

Figure 5-4 Class and object diagrams for weight integrity constraint on the Machine class

multi-level class composition hierarchy. The following query shows how a class can be retrieved in the backward direction along the multi-level class composition hierarchy (e.g., from the 'Material' class to the 'Machine' class in Figure 5-3 ).

SELECT Machine FROM Material, Part, Assy_Part, Machine 'WHERE Part.material_type = Material AND Assy_Part.sub_part SETEQ Part AND Machine.components SETEQ Assy_Part;

As shown in Figure 5-3, object 'p2' is a subpart of' 'objects 'ap1' and 'ap2'. In other words, objects 'ap1' and 'ap2' both have object 'p2' as part of their 'sub_part' attribute values. We call such an object a shared object. Shared objects make backward propagation more complex. For example, an update on object 'p2' requires checking the constraint in terms of both objects 'ap1' and 'ap2.
To define an integrity constraint on a complex class composition hierarchy, the user will have difficulty in considering the propagation of an update to the participating objects and specifying triggers for the integrity constraint on proper classes. Hence a systematic way to control the update propagation and to maintain the integrity constraint against the update is needed. In the next section, we propose three approaches for the backward propagation of an integrity constraint on a class composition hierarchy.
5.3 Backward Propagation Approaches

5.3.1 Backward Propagation with Method (Expression) Duplication

The simplest way to support the backward propagation of an integrity constraint is to define triggers with the method (it can be replaced with an expression that has the same functionality) that check the constraint in all participating classes. All methods in the triggers have the same functionality in that they all retrieve the objects involved in the constraint and return a calculated value from referenced objects for constraint checking. However, their codes are all different because they retrieve the objects in different manners according to their positions in the composition hierarchy. The methods in leaf classes or intermediate classes of the composition hierarchy must traverse the hierarchy in the backward direction to the root (recursively) retrieving the objects which (recursively) reference the updated object of the (leaf or intermediate) classes. Contrary, the method in the root class of the composition hierarchy retrieves the objects that participate in the constraint simply following the composition hierarchy. Therefore, traversal in the backward direction requires a method that retrieves objects which contain the object identifier (of the object given as a method parameter) as its attribute value. The definition of such a method may be given as follows:
OBJECT Backward(att_domain, attribute_name,referenced) { SELECT object FROM att_domain object WHERE object.attribute_name=referenced; return(object);}

The 'Backward()' method returns the instance of the 'att_domain' class whose 'attribute_name' attribute contains (the object identifier of) the 'referenced' object. In other words, it returns the object identifier that is a destination of traversal in the backward direction along the class composition hierarchy from the class that contains the 'referenced' object to the 'att_domain' class. For simplicity's sake, we do not consider methods that return multiple object identifiers in the case where the class composition hierarchy includes the shared objects.

To illustrate the first backward propagation approach, consider the example of weight integrity constraint on the 'Part' class introduced in Figure 5-1. To support the backward propagation, the 'PartWeight2()' method and the 'trigger_2' trigger that contains the 'PartWeight2()' method in its condition clause are defined on the 'Material' class as follows:
float PartWeight2(Material obj) { return(Backward(Part,material_type,obj). volume * obj.density }; CREATE TRIGGER trigger_2 AFTER UPDATE ON Material IF PartWeight2() ON obj > 100 EXECUTE INVALIDATE TRANSACTION;

The two methods, the 'PartWeight2()' and 'PartWeight()' methods, have the same functionality, retrieving objects involved in the integrity constraint and calculating the weight of a 'Part' object. However, the 'PartWeight2()' method is different from the 'PartWeight()' method in that it uses the 'Backward()' method to retrieve object 'p' from the updated object 'm' in the backward direction. Once there is an update on the 'Material' class (a leaf class of the class composition hierarchy), the 'trigger_2' trigger applies the 'PartWeight2()' method on the updated object. The method retrieves the related object in the 'Part' class (the root class of the class hierarchy) with the 'Backward()' method and calculates the weight for the integrity constraint.

Since this backward propagation approach needs basically identical methods for all participating classes, there is a problem of code redundancy. As the depth of the class composition hierarchy grows, the complexity of each method grows too. Moreover, if the composition hierarchy includes set-valued attributes or the shared objects, constraint checking methods (e.g., 'PartWeight2()' in the previous example) should be devised to control their complexity.

'Figure 5-5 depicts the referential complexity of this backward propagation approach, assuming that there are N participating classes which do not include set-valued attributes or shared objects. Under the assumption, only one referential path from the root to an updated object is to considered as a path for the backward propagation (if there are set-valued attributes or shared objects, multiple paths from the root class to the updated class must be considered). The method in the trigger of the updated class references objects before the updated object on the path in the backward direction (dotted arrows in Figure 5-5). It also references objects after the updated object in the forward direction along the class composition hierarchy (solid arrows in Figure 5-5). Therefore, N-1 references, some in the backward direction and some in the forward direction, (along the class composition hierarchy) are necessary for the method of the updated class to check the integrity constraint, whatever object on the path is updated.

Figure 5-5 Referential complexity of backward propagation with method duplication

To use the first backward propagation approach, the user who wants to check the integrity constraint on an updated object should have the read authority for all attributes in the composition hierarchy required for the constraint checking. Moreover, since the unit of authority is a class in our data model, the user should have the read authority for every participating class. For example, if the user wants to check the weight integrity constraint on the 'Material' class in Figure 5-3 using this backward propagation approach, he/she should have the read authority for the 'Part', 'Assy_Part', and 'Machine' classes. As a result, the user will be able to read other attributes in the class composition hierarchy which are not needed for the constraint checking.

5.3.2 Backward Propagation with Method Call

The second approach we propose overcomes the code redundancy problem of the first backward propagation approach. In this approach, after retrieving the object in the root class that has nested references to an updated object using the 'Backward()' methods, the trigger applies the initial method to the object (in the root class), and then examines the integrity constraint using the result of the method invocation.

To illustrate the second backward propagation approach, we will consider the weight integrity constraints of the Part class in Figure 5-1. In the example, the trigger initiated by an update on the 'Material' class is to apply the 'PartWeight()' method to object 'p' in the root class. For this purpose, the following trigger is defined in the 'Material' class.
TRIGGER trigger_2 AFTER UPDATE ON Material IF PartWeight() ON Backward(Part,material_type,obj)>100 EXECUTE INVALIDATE TRANSACTION;

If object 'm' is being updated, then the 'Backward()' method in the condition clause of the 'trigger_2' trigger will return object 'p' that contains object 'm' as its 'material_type' attribute value. The trigger applies the 'PartWeight()' method to object 'p,' which calculates the weight of the object. With the result of the method application, the 'trigger_2' trigger can test the integrity constraint of the updated object of the 'Material' class. Compared with the first backward propagation, this approach is superior since it can achieve the backward propagation without defining additional methods for constraint checking in other participating classes. In other words, the initial method is not duplicated in other participating classes.

Under the same assumption in the first backward propagation approach, this approach needs N-1 backward references in the worst case and additional N-1 forward references as illustrated in Figure 5-6. The backward references are needed to search and invoke the initial method. The worst case in the references is when an update occurs on the leaf class. The N-1 forward references are required for the method to retrieve objects for checking the integrity constraint.

Figure 5-6 Referential complexity of backward propagation with method call

The best case is when an update occurs on the root class. In this case, since there is no need to backward reference, only N-1 forward references for constraint checking are needed. Under the assumption that there is even probability of an update that occurs on an object in the N participating objects, the complexity can be calculated with the following formula:
access number = + N-1 = (N-1)

In this approach, the execution authority for the initial method is needed for the user who wants to test the integrity constraint. The read authority for the participating classes is also needed for the user to reference the participating classes in the method. For example, the user who wants to test the weight integrity constraint on the 'Material' class should have the read authority for the 'Part' class as well as the execution authority for the 'PartWeight()' method.

5.3.3 Backward Propagation with Virtual Class

The last backward propagation approach we propose supports the backward propagation through a virtual class that has the participating classes as its base classes. It directly invokes the initial method of the root class through the virtual class when there is an update on one of the base classes.

The weight integrity constraint on the 'Part' class in Figure 5-1 is used again as an example. First, a virtual class, 'HVC', is defined from the base classes including the 'Part' and 'Material' classes as follows:
CREATE VCLASS HVC { part Part, material Material } AS SELECT p, p.material_type FROM Part p;

Assume that (virtual) object 'h' have the object identifiers of object 'p' and object 'm' as its 'material' and 'part' attribute values, that is,
h: HVC h.part = p h.material = m

The 'trigger_2' trigger is specified on the 'Material' class to initiate the 'PartWeight()' method and to examine the returned weight.
TRIGGER trigger_2 AFTER UPDATE ON Material IF PartWeight() ON Backward(HVC,material,obj).part > 100. EXECUTE INVALIDATE TRANSACTION;

An update on object 'm' will cause the 'trigger_2' trigger to find object 'h' through the 'Backward()' method. Then, the trigger will apply the 'PartWeight()' method to the 'part' attribute of 'h' (its value is object 'p') to calculate the weight of object 'p'. Next, it will check the weight and decide whether the update can be committed.

This backward propagation approach needs fewer numbers of references to the participating classes than the second approach. Figure 5-7 shows the referential complexity when this approach is applied to N classes under the same assumption as those applied to the previous two approaches. An update on a class in the class composition hierarchy can directly initiate the initial method in the root class with one backward reference to a HVC object through the 'Backward()' method (e.g., in the figure, the dotted arrow represents the backward propagation). And then, the initiated method retrieves N-1 participating classes from base classes to check the integrity constraint. In the process, all references are made in the forward direction along the class composition hierarchy. As a consequence, total N references to the related objects are needed in this approach.

In this case the cost for establishing and maintaining the virtual class should be considered. To establish the virtual class, there are N-1 references for each participating object. In addition, if there is an update on the references of a participating object, the corresponding object in the virtual class should be changed.

Figure 5-7 Referential complexity of backward propagation with virtual class

Requiring the read authority only on the virtual class, this backward propagation approach enables the user to check integrity constraints on the classes for which he/she has no read authority. This is because the virtual class is able to hide specific attributes from the user. This means that the approach allows the user to check the integrity constraints of classes without exposing their classified attributes, if there is any. On the contrary, the previous two backward propagation approaches need the read authority for all participating classes so it is impossible for these approaches to check integrity constraints, if there is a class for which the user has no read authority. The advantage of the third backward propagation approach in terms of authorization is depicted in Figure 5-8. The figure shows that the approach is applied to the weight

Figure 5-8 Authorization control with virtual class

integrity constraint of the 'Machine' class in Figure 5-3. We suppose that the 'cost' attribute of the 'Part' object represented by 'Part.cost' in the figure is an unauthorized attribute to the user. If the user has the update authority for the 'Material' class and no read authority for the 'Part' and 'Machine' classes, he/she cannot check whether the update on an object of the 'Material' class violates the integrity constraint with the previous two backward propagation approaches. On the other hand, with the third approach, the user needs only object identifiers in the attributes of object 'h' in 'HVC' class. The user who wants to check the integrity constraint on the 'Material' class, therefore, can check the integrity constraint without access to the 'cost' attribute of the 'Part' class.

Korean Engineering Databases �� copyright Namchul Do, 1996