The Role of Polymorphic Reuse Mechanisms in Schema Evolution in an Object-Oriented Database.
AbstractA seamless approach to the incremental design and reuse of object-oriented methods and query specifications is presented. We argue for avoiding or minimizing the effort required for manually reprogramming methods and queries due to schema modifications, and demonstrate how the role of polymorphic reuse mechanisms is exploited for enhancing the adaptiveness of database programs against schema evolution in an object-oriented database. The salient features of our approach are the use of propagation patterns and a mechanism for propagation pattern refinement. Propagation patterns are employed as an interesting specification formalism for modeling operational requirements. They encourage the reuse of operational specifications against the structural modification of an object-oriented schema. Propagation pattern refinement is suited for the specification of reusable operational modules. It promotes the reusability of propagation patterns toward the operational requirement changes. This approach has a formal basis and emphasizes structural derivation of specifications. The main innovations are in raising the level of abstraction for behavioral schema design, and for making possible the derivation of operational semantics from structural specifications. As a result, both the modularity and reusability of object-oriented schemas are increased.
Introduction
Schema evolution, in general, is the ability of a database system to respond to the real world requirement
changes by allowing the schema to evolve as seamlessly as possible. Seamless extension of an
The work carried out at the University of Frankfurt was supported partly by the European Committee under ESPRIT
Project 6612 F-cube. The work at Northeastern University was supported in part by the IBM Corporation, Mettler-
Toledo AG, and the National Science Foundation under Grants CCR-9102578, CCR-9402486, and CDA-9015692 (Research
Instrumentation). The current address of Ling Liu is Department of Computer Science, University of Alberta, Edmonton,
T6G 2H1, Alberta, Canada.
object-oriented schema is important not only for increasing application developers' productivity but
also for facilitating and supporting extensibility. For example, if additional functionality can be added
seamlessly, existing application programs may either optionally ignore it or only require minimal modifications
when the added functionality becomes available. Therefore, how to effectively manage the
impact of schema modification, clearly, becomes an important issue for achieving such seamlessness.
We argue that one way to achieve seamless extensions is to employ polymorphic reuse mechanisms in
object-oriented database specifications. Thus, application programs can remain syntactically unchanged
or can be incrementally modified in the presence of schema evolution. In this paper, we assume that
schema modifications for an object-oriented database system are performed after the database is populated
with object instances, and application programs have been implemented and tested. Thus, the
impact of schema modifications implies not only the propagation of restructuring operations into the
database instances, but also the reprogramming of existing application programs (e.g., relevant methods
and queries). For example, in most existing method definition or query specification languages, each
name used in methods or queries must be associated with a precise path expression in order to traverse
the nested structure of the objects. Whenever a schema modification involves more than one existing
class, the path expressions relevant to those classes are changed in the modified schema. The methods
and queries which use those "old" path expressions must be updated accordingly to enable them to
be valid in the modified schema. Up to now, many researchers have studied issues related to avoiding
database restructuring and reorganization due to schema modification ([1, 3, 10, 21, 22, 23]). However,
the issue of avoiding or minimizing database reprogramming due to schema modification has received
surprisingly little attention in the database research community.
Why should reprogramming due to schema modification be avoided? Reprogramming of
object methods and database queries usually follows evolutionary changes of the logical object structure
(i.e., the database schema). Operations for reprogramming of methods and queries can be expensive,
especially when the relevant application programs are large and complex. Moreover, these operations
conflict with the reuse of software components and with the objective of seamless extension.
How can reprogramming be avoided? The concept of polymorphism and the mechanisms for
reuse of software components are useful utilities for avoiding or minimizing the reprogramming effort
required by schema modifications. One of the major reasons for manually reprogramming of methods
and queries after schema modifications is to keep the path expressions required in method definitions
or query specifications consistent with the modified schema. The precise knowledge of path expressions
is actually derivable from the logical object structure of the corresponding schema, although very
few object-oriented systems (and none of the existing object-oriented DBMS products we know of)
include support for structuring and deriving operational semantics from structural specifications. We
believe that adding support for automatically or semi-automatically deriving the semantics of operation
propagation over the hierarchical structure of complex objects opens new possibilities for the reuse of
operational specifications (such as methods or query programs) in object-oriented database systems.
Can reprogramming always be avoided? In most cases, when a schema modification incurs a
change in the propagation paths of existing methods or queries (e.g., a new class is added in between
two of the existing classes having construction (is-part-of) relationship), or when a schema modification
changes the properties of objects (e.g., a new property is added to an existing class), manually
reprogramming of existing methods or queries (due to schema modification) can be avoided by structural
derivation of operation propagation semantics, especially when polymorphic reuse mechanisms
are employed for the specification of methods and database queries. Unfortunately, when a schema
modification has substantially updated the logical object structure of a schema (in particular, when a
schema modification changes the minimal knowledge required for specifying a method or a query), the
reprogramming cannot be avoided completely.
With these baselines in mind, we propose a seamless approach to the incremental design and reuse of
object-oriented methods and query specifications and show how the polymorphic reuse mechanisms are
exploited for improving the adaptiveness of software programs against schema modification in an object-oriented
database. We argue that, by using this approach, operational specifications become more robust
and adaptive towards schema modifications. The effort to manually reprogram methods and queries
necessitated by schema modifications can be avoided or minimized. The salient features of our approach
are the use of propagation patterns and a mechanism for propagation pattern refinement. Propagation
patterns can be seen as an interesting specification formalism for modeling operational requirements
in object-oriented database systems. They encourage the reuse of operational specifications against
the structural modification of an object-oriented schema. Using propagation patterns provides method
designers and query writers with an opportunity to specify operations without detailed navigational
information. Propagation pattern refinement is suited for the specification of reusable operational mod-
ules. It promotes the reusability of propagation patterns towards the operational requirement changes.
We provide a number of examples to illustrate the concepts of propagation patterns and propagation
pattern refinement, and to show why these concepts are important polymorphic reuse mechanisms and
how they are employed to avoid or to minimize the effort required by manually reprogramming of
methods and queries after schema modifications.
In Section 2, we give a brief presentation of our reference object model. We discuss propagation patterns
and their formal semantics in Section 3. Several characteristics of propagation patterns are formally
studied too. In Section 4, we introduce a mechanism for propagation pattern refinement, present the
formalization of the concept and a number of examples for illustration. We compare our approach with
related work in Section 5. Section 6 concludes with a summary and a discussion on implementation
considerations as well as further research directions.
2 The Reference Object Model
We use the kernel of the Demeter data model [16] as our reference object model because this allows
us to show how our polymorphic approach is directly available using an existing tool: the Demeter
System/C++ TM ( [11], [12], [19]). In the object reference model, we describe the structure of objects
and classes in terms of a class dictionary graph (or so called schema graph). Two kinds of classes
are distinguished: alternation classes and construction classes. Alternation classes are regarded as abstract
classes. Construction classes are instantiable classes. Two kinds of relationships are distinguished
between classes: inheritance relationships (called alternation edges) and object reference relationships
(called construction edges). Information about what methods need to be attached to a class is deliberately
omitted from the class dictionary graph at this stage; it will be "injected" into a class via
propagation patterns at method propagation time. (See Section 3 for details.)
dictionary graph)
A class dictionary graph G is defined as a labeled, directed graph
and V A are finite sets of construction and alternation vertices, respectively; both are collectively called
the vertices of G; L is an ordered set of labels, each described by a character string; EC
is a ternary relation on V \Theta L \Theta V , representing construction edges; EA is a binary relation on V \Theta V ,
representing alternation edges. 2
For presentation brevity, we sometimes denote a class dictionary graph simply as
A.
Example 1 Suppose we want to model a document which is described by its title, the authors, a date,
annotations, and a document body. The annotations consist of a number of pages. A document body
contains a number of components each of which consists of a collection of pages. A component can
either be a text component or a figure component. A class dictionary graph representing the above
situation is shown in Figure 1.

Figure

Annotation
Date
String
annotate
content
date
authors
title
pages
Page
Component
Document
components
doc-body
Doc-Body
one-to-one
construction edge
one-to-many
construction edge
alternation edge
construction class
alternation class

Figure

1: A class dictionary graph of schema Document.
The class dictionary graph of this example is described as follows:
Figure, Annotation, String, Date.
(Document,date,Date), (Document,doc-body,Doc-Body),
(Document,annotate,Annotation), (Doc-Body,components,Component),
(Component,pages,Page), (Annotation,content,Page).
(alternation reachable: =)   )
be a class dictionary graph. A vertex alternation reachable from vertex
denoted by w =)   u, if and only if (iff ) one of the following conditions is satisfied:
Let us take a look at Figure 1. According to Definition 2(ii), class Text is alternation reachable from
class Component. Note that "=)   " is the transitive closure of EA, since it is reflexive, antisymmetric
and transitive. No cyclic alternation path is allowed. We say a class dictionary graph is legal if there
are no cyclic alternation paths:
In the sequel, we assume that class dictionary graphs are legal.
Definition 3 (construction reachable: \Gamma!   )
be a class dictionary graph. A vertex construction reachable from w
one of the following conditions is satisfied:
Consider Figure 1, by the condition (ii) of this definition, class vertex Page is construction reachable
from class vertex Text.
By applying construction reachability and alternation reachability, we may directly obtain the inheritance
property of a class hierarchy [4] over alternation edges. More specifically, when a class vertex v
is alternation reachable from vertex u, then for any vertex w 2 V which is construction reachable from
u, w is also construction reachable from v. We prove this property in the following Proposition.
Proposition 1 Let class dictionary graph. For any vertices u;
is alternation reachable from u (i.e., u =)   v), then for any class vertex w 2 V , if u \Gamma!   w holds, we
have v \Gamma!   w.
Proof:
Given u =)   v, let w 2 V such that u \Gamma!   w. The proof follows the cases of Definition 2.
(i) when v, the proposition is trivially satisfied.
(ii) when (u; v) 2 EA, from u \Gamma!   w, we follow the cases of Definition 3.
Case (a) if 9(u; '; w) 2 EC, then by u =)   v and Definition 3(ii), we have v \Gamma!   w.
Case (b) if 9u by u =)   v
and Definition 2(iii), we have u 0 =)   v; by Definition 3(ii), we get v \Gamma!   w.
OPERATION void print-document()
FROM Document
TO Page
WRAPPER Document
PREFIX (@ date -? g-print() @)
WRAPPER Page
PREFIX (@ this -? g-print() @);

Figure

2: The propagation pattern "print-document".
Case (c) if 9u by induction on u \Gamma!   u
i.e., the number of construction edges from u to u 0 ) and Definition 3(ii), we obtain
since u =)   v. From v \Gamma!   u 0 and u 0 \Gamma!   w, by using Definition
3(iii), we obtain v \Gamma!   w.
(iii) when 9u 0 s.t. u =)   u 0 and u 0 =)   v, by induction on u \Gamma!   w, and Definition 3(ii),
we obtain u 0 \Gamma!   w since u =)   u 0 . Similarly, by induction on u 0 \Gamma!   w and u 0 =)   v, we
3 Propagation Patterns
3.1 Informal Overview
The concept of propagation patterns was originally introduced in the Demeter system TM in order to
specify the object-oriented programs at a higher level of abstraction ([13], [15]). We believe that propagation
patterns are also a useful conceptual programming technique for database applications, which
enables system designers and programmers to conceptualize application programs and system behavior
with minimal knowledge of the data structure. Propagation patterns are seen as a kind of behavioral
abstraction of application programs which define patterns of operation propagation by reasoning
about the behavioral dependencies among cooperating objects. They have proved to be an effective aid
for building highly adaptive database programs (methods and queries) and for supporting incremental
schema evolution. Consider the following example.
Example 2 Consider the class dictionary graph as shown in Figure 1. Suppose we want to have a
method "print-document" which prints the creation date of a document and the entire document body
but none of its annotations. We may define the method by writing the following propagation pattern
(see

Figure

2).
This propagation pattern states that the method "print-document" will print the creation date of a
document before printing the entire document content. Besides, all the Annotation objects of a document
will be excluded from this printing task. The idea behind this propagation pattern is based on the
fact that a number of classes in the class dictionary of Figure 1 need to cooperate to accomplish the task
"print-document", but only little information is necessary for specifying this task since the rest can easily
be derived from the structural specifications of the schema. For instance, in Figure 2, we specify the interface
of the method to be propagated with the clause OPERATION void print-document. The source
of this propagation pattern is given with the clause FROM Document, specifying where the propagation
pattern starts. The target of the propagation pattern is provided with the clause TO Page, indicating
which class(es) the propagation pattern terminates with. The clause BYPASSING *,annotate,*
identifies the restriction (propagation constraints) over this propagation pattern in order to exclude
all the annotations from this printing task. The source clause, the target clause and the propagation
constraint clause together are called a propagation directive of pattern "print-document". Note
that if instead, only the clause FROM Document and clause TO Page had been used, then the edge
(Document,annotate,Annotation) would have participated in the propagation too, an undesired ef-
fect. The clauses WRAPPER Document and WRAPPER Page, followed by the actual programming code
(e.g., C++ code) surrounded by "(@" and "@)", specify the method body. We provide a detailed
syntax description in Appendix A.
Remarks: (i) Writing a propagation pattern does not require knowledge of the detailed data struc-
ture. One obvious benefit of this feature is to allow reuse of propagation patterns at hand for several
similar data structures and thus to increase the adaptiveness of the operational specifications against
future schema changes. For instance, for writing the propagation pattern "print-document", the minimal
knowledge we need to know is Document, Page, Date, and annotate, and by Figure 2 they
are critical information (called hooks) for defining this function. Suppose now we need to modify the
schema of Figure 1 by changing the layout of the Document logical structure (see Figure 3). The schema
modification as such needs no reprogramming of the method "print-document" although the path from
Document to Page is changed in the modified schema; because all the critical information for specifying
"print-document" is unchanged and included in the modified Document schema. Thus, the above propagation
pattern "print-document" can still be used as a valid and meaningful propagation pattern to
this modified Document schema. (See Section 3.3 for further explanation.)
(ii) If the BYPASSING option is not included in the above propagation pattern, the propagation path
implied by the given propagation directive will include both the path from Document through doc-body
to Page and the path from Document through annotate to Page. It means that the task "print-
document" will print both the entire document content of a document itself and all the annotations of
it.
(iii) Propagation patterns can automatically be translated at so-called method propagation time into
code written in any object-oriented programming language (e.g., C++). The code fragments are inserted
into those classes which participate in the propagation pattern traversal. We will provide an illustration
of this point in Section 3.3.
Contrast the above robustness of propagation patterns with conventional object-oriented database languages
and their reaction to the schema modifications. To express the operation "print-document"
using most of the existing object-oriented languages the method designers or query writers must refer
Article
Document
Page

Figure

Section
Annotation
Date
String
Chapter
annotate
content
date
affiliate
authors
title
chapters content
sections
pages

Figure

3: A modified class dictionary graph of schema Document.
to the objects of interest by their precise path expressions. For example, using a SQL-like language,
the propagation pattern "print-document", defined on schema Document (Figure 1), can be expressed
as follows:
PRINT d.date, d.title, d.authors, d.doc-body.components.pages
FROM d in Document.
If the schema is modified such that items in the above path expression are involved in the modifica-
tion, then the SQL-like operation becomes invalid. For instance, if the Document schema is updated to
the schema in Figure 3 by adding a new property, affiliate, to Document objects, and inserting a class
Section in between Doc-Body and Component, then the above expression d.doc-body.components.pages
becomes invalid. It must be manually updated to d.doc-body.sections.components.pages. For this
single case this might not seem like a lot of work. However, if many routines in a number of application
programs are implemented over the "old" schema, one single modification of the schema could possibly
require massive rewriting of the routines in all the relevant application programs, a rather tedious task.
In contrast, by using propagation patterns, schema modifications usually have no or less impact on
the existing database programs because propagation pattern specifications require neither knowledge of
the detailed structure of the schema nor the navigational information of how to traverse the schema.
For example, the propagation pattern "print-document" defined in Figure 2 remains valid for the modified
Document schema and thus there is no need to update this propagation pattern even after the
modification of Document schema.
In summary, propagation patterns propose a novel method specification technique which promotes
adaptive object-oriented schema design. They can be used as a database programming language for
enhancing robustness of database programs. Adaptiveness and robustness of propagation patterns is
achieved by delaying the binding of the concrete propagation paths used in each method or query
specification from method (or query) writing time to operation propagation time, prior to compile time.
3.2 Formal Definitions
In order to define some reuse mechanisms for propagation patterns, we below present the formal definitions
of propagation directives and propagation patterns and then introduce the concept of propagation
scope.
Definition 4 (propagation directive)
Given a class dictionary graph propagation directive ffi over G is defined by a
triple
ffl F denotes a nonempty set of source vertices and F '
ffl PC denotes propagation constraints and
- I is a set of through edges called restriction constraints;
- X is a set of bypassing edges called exclusion constraints.
ffl T denotes a nonempty set of target vertices and T ' V . 2
Each propagation directive specifies a set of propagation paths and is described by a set of source
vertices, a set of propagation constraints and a set of target vertices.
Definition 5 (propagation pattern)
be a class dictionary graph. A propagation pattern ff over G is defined by a
triple (M; PD;MA).
ffl M(ff) is a method interface defined by a triple (u; mn; Lpa), where
denotes the output type which is either a class vertex or the keyword "void",
indicating an empty result type,
- mn is the method name,
- Lpa is a list of n (n  0) parameters; that is,
is the parameter name
ffl PD(ff) denotes a nonempty set of propagation directives over G; that is,
ffl MA(ff) is a set of method annotations. A method annotation consists of a set of prefix or suffix
components, denoted as (w; fg PRE ) or (w; fg SUF ), where w is a class vertex in V , fg PRE and
fg SUF each denotes a code fragment, describing the user-defined method implementation.
fg i is a character string, containing a code fragmentg.Note that in this definition, we have classified a method annotation into prefix and suffix code fragments.
Such a classification plays an important role in identifying the activation sequence of those fragments.
We refer to an activation sequence of wrapper code fragments of a propagation pattern as the wrapper
order of the propagation pattern. When specific object types are encountered during the traversal, the
prefix code fragments are to be executed before suffix code fragments. The exact execution sequence
depends jointly on the propagation pattern, the class dictionary graph, and the object being traversed.
In general, the following rules for wrapper execution order hold. When a class in the propagation scope
(see Def. 7) is traversed,
1. its prefix fragments are executed before its suffix fragments;
2. if the class has more than one prefix, all its prefix fragments are executed in the order they appear
textually in the propagation pattern definition;
3. all suffix wrappers of the class are executed in the reverse textual
4. if a class vertex v is alternation reachable from another class vertex u, then the prefix wrapper
of u is executed before the prefix wrapper of v, and the suffix wrapper of u is executed after the
suffix wrapper of v.
5. if a class vertex v is construction reachable from another class vertex u, then the prefix wrapper
of u is executed before the prefix wrapper of v, and the suffix wrapper of u is executed after the
suffix wrapper of v.
Interesting to note is that Rule (4) describes the dependency relationship between code fragments of a
specialized class and code fragments of a more general class. The specific code could be dependent on
the general code, but the general code should not depend on the specific code at all. Rule(5) specifies
the dependency between a component class and its container class.
Example 3 Consider the propagation pattern defined in Figure 2. It has two wrapper fragments:
(Document,fg Document
PRE ) and (Page,fg Page
PRE ). The wrapper execution order of these fragments is as follows:
(Document; fg Document
To capture the relationships between a propagation pattern, a class dictionary graph, and an object
being traversed, we introduce the notions of propagation paths, propagation scope, as well as compatibility
of propagation patterns. Readers who are interested in formal semantics of the wrapper orders and
implementation considerations may refer to [?, 18, 8].
3.3 Scope and Compatibility of Propagation Patterns
In this section, we define the scope and compatibility of propagation patterns. The scope of a propagation
pattern identifies for a given class dictionary graph the complete set of classes (vertices) and
relationships (edges) involved in executing the task specified by the propagation pattern. The compatibility
of a propagation pattern defines a family of class dictionary graphs to which the propagation
pattern is directly applicable.
Definition 6 (legal path)
be a class dictionary graph. For two vertices u and v in G, the predicate
holds if it can be recursively derived using the following construction rules:
(ii) u \Gamma!   v;
Note that, for any legal path p: u ; v, the set of edges E(p) involved in a given path p can be
represented as:
and e is contained in pg:
The computation of E(p) can easily be obtained by using Definition 2, Definition 3 and Definition 7.
Put differently, we may compute E(p) by recursively constructing the edges involved in the path p:u ; v
as follows.
ffl If u =)   v, then by Definition 2, 9w
ffl If u \Gamma!   v, then by Definition 3 two cases are possible:
Note that if u ; v there could be several legal paths from u to v.
Example 4 Consider Document and Page in Figure 1 as an example. By Definition 3(ii), we have Text
\Gamma!   Page and Figure \Gamma!   Page, because Component =)   Text and Component =)   Figure hold,
and (Component, pages, Page)2 EC. Thus, according to Definition 6, we get the following three legal
paths from Document to Page.
1. Document
2. Document ; Doc-Body ; Component ; Figure; Page;
3. Document ; Doc-Body ; Component ; Page;
4. Document ; Annotation ; Page.
For the unique legal path from Document through Text to Page, we have:
E(Document ; Page) =f (Document,doc-body,Doc-Body), (Doc-Body,components,Component),
(Component,pages,Page)g.
Actually, due to the fact that class Component is a generalization of classes Figure and Text, traversing
the third path implies that both the first path and the second one will be visited.
Definition 7 (propagation scope)
Given a class dictionary graph propagation pattern
defined m) denote a propagation directive
described by We say a legal path p satisfies the propagation constraint
the following hold:
Let P i be the set of all possible legal paths from vertex u 2 F i to vertex v, v satisfying that v 2 T i or
g.
The propagation scope of a directive denoted by PS(ffi i ; ff), is defined as
follows:
E(p).
The propagation scope of pattern ff, denoted as PS(ff), is described by the union of the scopes of the
propagation directives of ff; that is,
ff)Note that for any given propagation pattern, the set of propagation directives decides what the propagation
scope is, whereas the method signature and the method annotations specify what is propagated
within this scope. A detailed discussion may refer to [18].
Example 5 Consider Figure 1, and the propagation pattern given in Example 2 (call it ff). Let
denote the propagation scope of directive denoting FROM Document BYPASSING *,annotate,*
TO Page . Let PS(ff) be the propagation scope of pattern ff over the schema (class dictionary graph)
defined in Figure 1. Thus, we have:
(Component,pages,Page), (Component,Text), (Component,Figure),
(Document,author,String), (Document,title,String), (Document,date,Date) g.
As propagation pattern ff has only one propagation directive, we have
It is important to note that a propagation pattern, which is syntactically correct according to Definition
5, may not be semantically correct. For example, consider a simple class dictionary graph
lcdg. It means that objects of class A are composed by objects of class B and of
class C, while objects of both class B and class C contain objects of class D as their subobjects. Now
assume that we have the following two propagation patterns PP 1 and
Operation void PP1 Operation void PP2
From A From A
To D Through (A,lab,B)
Wrapper A To D
. Wrapper A
Wrapper C .
. Wrapper C
Wrapper D .
. Wrapper D
Obviously, both are syntactically correct propagation patterns over G in terms of Definition 5. How-
ever, PP 2 is semantically incorrect propagation pattern over G, because class C is not included in the
propagation scope of PP 2 and the wrapper reference to C in PP 2 is invalid.
One possible means to define and check the semantic correctness of a propagation pattern over a given
class dictionary graph is to use the concept of propagation scope.
Definition 8 (semantic correctness of a propagation scope)
Given a class dictionary graph propagation pattern defined
over G with propagation scope PS(ff). Then V PS(ff) denotes the set of class vertices involved in PS(ff)
and is defined as follows:
(iii) nothing else is in V PS(ff).
The propagation pattern ff is said to be semantically correct over G, if and only if, for any (u; fg u
MA(ff), we have
In the sequel, we assume that all propagation patterns we deal with are correct both in syntax and in
semantics.
The major advantage of propagation patterns is that they can be applied to not just one class dictionary
graph but to a family of class dictionary graphs. This property makes them truly adaptive and reusable.
In order to determine the set of class dictionary graphs compatible with a given propagation pattern
we need to define the notion of compatibility. We say a propagation pattern to be compatible with a
class dictionary graph if the class dictionary includes all the information contained in the hooks of this
propagation pattern. Informally, the hooks of a propagation pattern consist of the To and From vertices,
the labels referred to in the Through and Bypassing edges, and the vertices referred to in the method
interface and the method annotations.
Definition 9 (compatibility of a propagation pattern)
\Gamma be a set of class dictionary graphs and, for G 2 \Gamma, let V (G), EA(G) and L(G) be a set of class
vertices, a set of alternation edges and a set of labels of G, respectively. Let be a
propagation pattern defined over G and HK(ff) denote the set of key information to pattern ff (we call
them "hooks" of pattern ff). For any x 2 we define that x 2 HK(ff) iff one
of the following conditions is verified.
Then, for any G 0 2 \Gamma, we say ff is compatible to G 0 iff HK(ff) '
Example 6 Recall the propagation pattern "print-document" defined in Example 2, denoted as ff. Let
the class dictionary graphs in Figure 1
and

Figure

3, respectively. We have
fDocument,annotate,Page,Dateg.
Thus, the propagation pattern "print-document" is compatible with both G 1 and G 2 .
3.4 Polymorphic Character of Propagation Patterns
As stated earlier, by using propagation patterns to model the dynamic part of an object-oriented
database system, we may achieve a certain degree of adaptiveness and flexibility of the database specifications
against future changes, especially with respect to several types of structural changes. For
example, the propagation pattern given in Figure 2 is defined over the class dictionary graph of Figure
1, but it can also be used as a propagation pattern for the class dictionary graph given in Figure 3,
because both class schemas include Document objects, which have Page objects as (sub)parts. By using
propagation patterns, schema designers and programmers may focus on only the most interesting
components of the class structure. No precise knowledge about how the structural details are modeled
in a particular schema (class dictionary graph) is required. We refer to this particular feature as the
polymorphic character of propagation patterns.
It is interesting to note that, for the same pattern print-document, its propagation scope over the class
schema of Figure 1 is quite different from the one over the class schema of Figure 3. Although the same
propagation pattern specification is valid for both schemas, the binding of it to the involved classes and
the code generated based on it are different. The polymorphic character of this propagation pattern is
only apparent. Generally speaking, the polymorphism of propagation patterns belongs to the family of
ad-hoc polymorphism [5]. We below provide another example.
Example 7 Suppose we define the Trip schema (class dictionary graph) as shown in Figure 4. The
Trip objects have parts called departure and arrival which can be printed. A Trip object contains
a list of Location objects each of which has an Ident object as a component, describing the city to
be visited during the trip. The list of Location objects is here modeled by a third kind of class, a
repetition class. A repetition class implements the one-to-many relationship between Trip class and
Location class. For the remainder of this paper, we will replace one-to-many construction edges with
repetition classes in order to show actual method code for all the classes.
Time
Trip
Location
Location
departure
arrival
locations
Number
value

Figure

4: A class dictionary graph of schema Trip.
Consider an operational requirement of printing trip itineraries in a travel agency. Given a Trip object,
we need to print the departure time and the list of cities to be visited, followed by the arrival time.
This application can be described by using the propagation pattern below (see Figure 5).
The following lists the key information (hooks) of this propagation pattern.
fTrip,departure,arrival,Identg.
OPERATION void print-itinerary()
FROM Trip
WRAPPER Trip
PREFIX (@ departure -? g-print() @)
SUFFIX (@ arrival -? g-print() @)
PREFIX (@ this -? g-print() @);

Figure

5: An example propagation pattern print-itinerary.
The wrapper order of MA(Trip) is as follows:
In this example, the prefix annotation is used to print the departure time before the Trip object
is traversed; the suffix annotation prints the arrival time after the Trip object has been traversed.
The primary annotation replaces the default traversal code when printing the current Ident object.
When the above propagation pattern is injected into the class structure of Figure 4 at propagation
time, program fragments will automatically be generated according to the given method annotations.
(See the C++ codes attached to the classes in Figure 6, which we obtained by running the Demeter
System/C++ on the example.) The C++ method definitions attached to each class in Figure 6 is
generated according to the propagation pattern given in Figure 5. The completeness of these C++
methods fully depends on the specification details of propagation patterns.
By using propagation patterns, any unnecessary information about the class structure need not be
hardwired into the specification. This allows the specification of a propagation pattern to be more
flexible towards schema modification. For example, suppose the schema shown in Figure 4 is extended
by adding the class DayTrip such that a Trip object now contains a list of DayTrip objects and each
DayTrip object contains a list of Location objects which are printable through Ident objects (see the
schema presented in Figure 7). Although the propagation pattern in Figure 5 is defined over the schema
in

Figure

4, the modification on Trip schema requires no reprogramming of this method, because all
the hooks of "print-itinerary" are included in the modified schema of Figure 7. Consequently, this
propagation pattern is also compatible with the schema of Figure 7. We can even reuse the propagation
pattern defined in Figure 5 for the Trip schema in Figure 7 without changing the specification of the
propagation pattern and the code generated previously based on the propagation pattern.
Clearly, with respect to the two Trip schemas, the propagation pattern "print-itinerary" also presents a
kind of ad-hoc polymorphism. More interestingly, this propagation pattern can actually be compatible
with a family of Trip class structures, as long as the Trip class has a departure and an arrival part,
and a "path" to class Ident. Polymorphism may provide a sound theoretical basis for investigating
the adaptiveness of object-oriented schema design and schema evolution in both the structural and the
dynamic aspect.
Time
Trip
Location
Number
Location
departure
arrival
value
locations
void
{
LocationList_iterator nextLoc( this );
Location *eachLoc;
while
void Trip::print_itinerary()
{
departure -> g_print();
locations -> print_itinerary();
arrival -> g_print();
void
{
this -> g_print();
void
{
city -> print_itinerary();

Figure

The Trip schema with generated C++ code attached to corresponding classes.
3.5 Remarks on Reuse Possibility
Up to now, we have shown by examples that propagation patterns are a promising conceptual programming
technique for modeling and programming the dynamic behavior of object-oriented database
systems, because of their adaptiveness to the structural changes of a schema.
The adaptiveness of propagation patterns results from a number of interesting features. First of all, the
specification of propagation patterns does not require hard-wiring them to a particular class structure.
This leaves room for deriving behavioral abstraction based on structure abstraction and for incremental
design of methods (e.g., propagation patterns). Secondly, propagation patterns are defined in terms of
only a few, essential classes and relationship specifications. They serve as hooks into the class structure
[11]. The rest of the knowledge required for behavior implementation can actually be derived on the basis
of these hooks and the corresponding class schema. Last but not least, propagation patterns promote
the well-known concept of late binding. Instead of binding methods to classes at program-writing time,
propagation patterns encourage the binding of methods to classes at propagation time, prior to compile
time. Therefore, given a propagation pattern defined over a class structure (say G), any change to the
structure of G (which does not affect the hooks of this propagation pattern) will have little impact on
the specification of this propagation pattern, even though its scope over the modified class schema could
be changed accordingly. In other words, the given propagation pattern specification by itself can be
reused in a modified class schema, if no additional propagation constraints or method annotations are
required. But the binding of the method interface and annotations to the relevant classes may need to
be re-adjusted implicitly at propagation time (through propagation pattern interpretation).
In contrast, when changes are required to the dynamic (behavioral) aspect of a schema and thus to some
existing propagation patterns, it becomes indispensable to redefine the affected propagation patterns or
Time
Trip
Location
Number
Location
departure
arrival
value
locations
void
{
this -> g_print();
daytrips
void
LocationList_iterator nextLoc( this );
Location *eachLoc;
while
void DayTripList::print_itinerary()
{
DayTripList_iterator nextDay( this );
while
eachDay -> print_itinerary();
void
{
city -> print_itinerary();
void DayTrip::print_itinerary()
{
locations -> print_itinerary();
void Trip::print_itinerary()
{
departure -> g_print();
dayTrips -> print_itinerary();
arrival -> g_print();

Figure

7: A second Trip schema with generated C++ code.
to further extend some existing propagation patterns (see Example 8 in the next section). It is definitely
beneficial if some reuse mechanisms are provided so that the adaptation of existing propagation patterns
to the new requirement changes do not have to start from scratch or be rewritten completely, even if
the affected propagation patterns are simple ones. Because once a propagation pattern is reused, both
the programming codes generated in terms of it and the existing binding of methods to classes at
propagation time may inherently be reused as well. Besides, by reusing the specification of propagation
patterns, information involved is maximumly localized such that any change to the existing specifications
is carried out only at one place. The effort to manually preserve the consistency of the specifications
due to schema modification is then minimized.
In what follows, we introduce a reuse mechanism for propagation patterns, which allows new propagation
patterns to be defined in terms of existing ones by a behavioral refinement mechanism.
Behavioral Refinement of Propagation Patterns
The refinement of propagation patterns is a behavioral abstraction mechanism, which allows us to define
more specialized propagation patterns in terms of existing propagation patterns by
(a) restricting propagation behavior to one or more specialized classes as arguments of the method,
(b) imposing extra propagation constraints, or
(c) adding additional method annotations.
4.1 A Motivating Example
Example 8 Consider again the Trip schema in Figure 7 and the propagation pattern for printing trip
itineraries in a travel agency defined in Figure 5. Suppose now we want to modify the Trip schema of

Figure

7 by adding a new property Date to class DayTrip (see Figure 8).
Time
Trip
Location
Number
Location
departure
arrival
value
void
this -> g_print();
daytrips
void
LocationList_iterator nextLoc( this );
Location *eachLoc;
while
void
{
city -> print_itinerary();
Date
locations date
day
year
month
void DayTripList::print_itinerary()
{
DayTripList_iterator nextDay( this );
while
eachDay -> print_itinerary();
void DayTrip::print_itinerary()
{
date -> g_print();
locations -> print_itinerary();
void Trip::print_itinerary()
{
departure -> g_print();
dayTrips -> print_itinerary();
arrival -> g_print();

Figure

8: An extended Trip schema with generated C++ code.
We also want to extend the task of printing trip itineraries by adding a new operational requirement that,
for each trip, the date for every travel day must also be printed. Comparing with the "old" propagation
pattern "print itinerary" defined in Figure 5, this extended task (let us call it "print-detailed-itinerary")
obviously includes all the functionalities of the "old" propagation pattern "print-itinerary" (see Figure 5)
and also some additional propagation constraints and method annotations. For instance, the following
annotation needs to be added for printing the date of each travel day within a trip:
WRAPPER DayTrip
PREFIX (@ date -? g-print() @)
OPERATION void print-detailed-itinerary()
FROM Trip
THROUGH (DayTrip,locations,LocationList)
TO Indent
WRAPPER Trip
PREFIX (@ departure -? g-print() @)
SUFFIX (@ arrival -? g-print() @)
WRAPPER DayTrip
PREFIX (@ date -? g-print() @)
PREFIX (@ this -? g-print() @);

Figure

9: A modified propagation pattern of "print-itinerary".
Additionally, in the schema of Figure 8, there is more than one path from Trip to
the edge locations and the other through the edge date. We also need to add the following extra
propagation constraint into the propagation pattern defined in Figure 5:
THROUGH (DayTrip,locations,LocationList)
or
BYPASSING (DayTrip,date,Date).
There are two ways to accomplish this operational requirement change. One way is to redefine (rewrite)
the previous propagation pattern "print-itinerary" completely and then redo the binding (injection) of
methods to classes at propagation time. For example, we may rewrite the propagation pattern "print-
itinerary" completely as shown in Figure 9. Although most of the previous bindings will remain the
same for this redefined propagation pattern (compare the code generated in Figure 7 and Figure 8), we
need to re-bind all methods to classes and regenerate the code for this modified propagation pattern
(see the code attached to the classes in Figure 8).
The other way is to employ some reuse mechanisms so that more specialized propagation patterns can
be defined in terms of existing ones. This means that only the propagation constraint and the method
annotation which are new need to be defined. The rest can be directly reused from (or shared with) the
existing pattern by means of the propagation refinement mechanism. Furthermore, at the propagation
time of the refined propagation pattern, only the new method annotations need to be injected to the
involved classes, since all previous bindings and code generated in terms of the "old" method annotations
may be reused accordingly. For example, compare the propagation pattern given in Figure 9 with the
one defined in Figure 5: only one prefix annotation is new and one extra propagation constraint is
added.
Moreover, the addition of date into the task of printing trip itineraries, in fact, only affects the "old"
binding of the method ("print-itinerary") to the class vertex DayTrip and the code generated for this
binding. The rest remains exactly the same. Thus, by using the propagation refinement mechanism
(see the next section), we may specify the desired requirement change as shown in Figure 10.
OPERATION void print-detailed-itinerary()
BEHAVIORAL REFINEMENT OF print-itinerary
ADD CONSTRAINT
THROUGH (DayTrip,locations,LocationList)
ADD ANNOTATION
WRAPPER DayTrip
PREFIX (@ date -? g-print() @).

Figure

10: A refined propagation pattern of "print-itinerary".
4.2 Definition
We now present a formal definition of propagation pattern refinement, based on the concept of signature
refinement and propagation directive refinement.
E) be a class dictionary graph. Given two method interfaces M 1 and M 2 , where
m). We say that the method interface M 2 is a signature refinement of the method interface M 1 ,
denoted by M 2  sig M 1 , iff the following conditions are verified:
Note that this definition also identifies that, given two operation interfaces M 1 and M 2 , if M 2 is a
signature refinement of M 1 , then M 2 may have more (additional) arguments than M 1 (see the condition
that (0  n  m)). This is an important property for behavioral refinement of propagation patterns.
For example, when propagation patterns are refined in groups, it often requires adding extra arguments
in calls.
Definition 11 (propagation directive refinement)
E) be a class dictionary graph, be two given
propagation directives defined over G. Let PC
propagation scopes of directives ffi 1 and ffi 2 respectively. Then ffi 2 is a propagation directive refinement of
the following conditions are verified:
1. 8y
that is, y is alternation reachable from x.
2. If
It means that whenever the hook of a propagation directive ffi 1 is included in the hook of a propagation
directive the propagation constraints of ffi 1 should be implied by the propagation constraints
of
3.
that is, for any vertex u in the set T 2 of target vertices of ffi 2 , there is a vertex v in the set T 1 of
target vertices of ffi 1 such that u is alternation reachable from v.
4.
Condition (1) amounts to saying that whenever ffi 2 is a propagation directive refinement of ffi 1 , then any
given source vertex u in F 2 must have a corresponding source vertex (say v) in F 1 and u is alternation
reachable from v (v =)   u). condition (3) identifies the similar result over the target sets T 1 and
Two cases are involved in condition (2) of Definition 11. We illustrate them in Example 10 and
Example 11, respectively. The following example combines conditions (1), (3) and (4) to infer that
propagation directive refinement holds.
Example 9 Let ffi 1 and ffi 2 be two propagation directives,
"FROM A' To C'". F fC'g. If A =)   A' and C =) \Lambda C',
then holds. It means that ffi 2 is a propagation directive refinement of ffi 1 .
Definition 12 (propagation pattern refinement)
E) be a class dictionary graph and
PD(fi), MA(fi)) be two given propagation patterns defined over G. Let
and propagation pattern fi is a behavioral refinement of
propagation pattern ff, iff the following conditions are verified:
1. M(fi)  sig M(ff); that is, M(fi) is a signature refinement of M(ff).
2.
It means that for any ffi i in PD(ff), there is a refined propagation
directive ! j in PD(fi).
3. MA(ff) ' MA(fi). 2
This definition states that if fi is a behavioral refinement of propagation pattern ff, then not only the
signature refinement condition and propagation directive refinement condition should hold but also
the inclusion of wrapper set of ff into the wrapper set of fi should be verified. If one of the three is
invalid, then fi is not a propagation pattern refinement of ff. Put differently, these three conditions
work together to guarantee that the scope of a refined propagation pattern can only be made smaller
to the limit that all wrappers of the generic propagation pattern still be applicable.
In addition, condition (3) presents the following wrapper refinement rule: if propagation pattern fi
is a behavioral refinement of propagation pattern ff, then the prefix wrappers of fi may extend the
prefix wrappers of propagation pattern ff by adding extra wrappers or by providing additional wrapper
fragments for the existing wrappers. We may introduce the keyword "ADD ANNOTATION" or the
"ADD FRAGMENT" within a WRAPPER clause to serve for this purpose. Also, Definition 11
has the property that if propagation pattern fi is a behavioral refinement of propagation pattern ff, then
all the code fragments defined in pattern ff are executed in the same order as they are in an execution
with propagation pattern fi.
Consider the motivating example given in the previous section and the schema in Figure 8.
Let ff denote the propagation pattern defined in Figure 5, page 16, and ffi be the propagation directive of
ff. Let fi be the modified propagation pattern defined in Figure 10 and ! be the propagation directive
of fi. We have:
The wrapper order of ff : (Trip, fg T rip
The wrapper order of fi : (Trip,fg T rip
g.
Therefore, by Definition 12, we conclude that propagation pattern fi is correctly defined as a behavioral
refinement of propagation pattern ff.
The above example also shows that all the wrappers of "print-itinerary" are activated in the same order
in the refined propagation pattern "print-detailed-itinerary". Put differently, the behavioral refinement
mechanism guarantees that the wrapper order of any refined propagation pattern should preserve (or
imply) the wrapper order of the (given) pre-defined propagation pattern. This important property
of propagation pattern refinement is stated formally in the following proposition. Readers who are
interested in the formal proof of the proposition may refer to our technical report [?]. The techniques
developed in [18, 8] can also be used for constructive proof of this proposition.
Proposition 2 (wrapper order property of propagation pattern refinement) Let E)
be a class dictionary graph and be two
given propagation patterns compatible with G. If propagation pattern fi is a behavioral refinement of
propagation pattern ff, then wrappers of pattern ff are executed in the same order over MA(fi) as over
MA(ff).
Note that the propagation pattern refinement mechanism not only increases the flexibility and adaptiveness
of propagation patterns against future operational requirement changes, but it can also be useful
for promoting the concept of propagation pattern inheritance under a class dictionary graph, especially
when there is a need of applying an existing method (function) to a subset of its current domain or
codomain instead.
Example 11 Recall the propagation pattern "print-document" given in Figure 2, page 6. Suppose this
propagation pattern is used as a propagation pattern over the Document schema given in Figure 3. Now
if we want to add a new method that prints only the documents of type Article, i.e., a subset of the
Document objects, by providing a support for behavioral refinement of propagation patterns, we could
easily reuse the propagation pattern "print-document" to obtain a more specialized propagation pattern
"print-article" to do the job (see Figure 11.)
OPERATION void print-article()
BEHAVIORAL REFINEMENT OF print-document
FROM Article TO Page.

Figure

11: A refined propagation pattern of Figure 2.
Let ff denote the propagation pattern "print-document" and fi denote "print-article", both defined over
the class schema in Figure 3. Obviously, we have
(i) M(fi) is a signature refinement of M(ff), since both ff and fi return void and have an
empty argument list;
(ii) PD(fi) is a propagation directive refinement of PD(ff), since
Document=)   Article, and Document62
Thus, by Definition 11, propagation pattern fi (print-article) is a correct behavioral refinement of
propagation pattern ff (print-document).
Another interesting feature of propagation pattern refinement is presented by its transitivity. We below
prove that for any propagation pattern ff; fi; fl, if pattern ff is a behavioral refinement of pattern fi and
pattern fi is a behavioral refinement of pattern fl, then pattern ff is also a behavioral refinement of
pattern fl.
Proposition 3 Let predicate PP-refinement(ff; fi) hold if and only if propagation pattern ff is a behavioral
refinement of propagation pattern fi. Then we have
Proof: Let ff denote any propagation pattern described by a triple (M(ff); PD(ff); MA(ff)). We need
to prove that
(ii) For any j 2 PD(fl), there exists a ffi 2 PD(ff) such that ffi  pd j;
The proof may proceed as follows.
By PP-refinement(ff; fi), PP-refinement(fi; fl) and Definition 11, M(ff)  sig M(fi) and M(fi)  sig M(fl)
are held. To prove M(ff)  sig M(fl), let
By M(ff)  sig M(fi), we get Similarly, by M(fi)  sig M(fl),
we get u 3 =)   Thus, according to Definition 2(iii), we have u 3 =)
holds.
The proof for (ii) goes as follows: by PP-refinement(fi; fl) and Definition 11, we get 8j 2 PD(fl); 9! 2
Quite similarly, from PP-refinement(ff; fi), we get 8! 2 PD(fi), 9ffi 2 PD(ff) s.t.
According to Definition 10, we could easily prove that 8j 2 PD(fl), 9ffi 2 PD(ff) s.t. ffi  pd j
holds.
The proof of (iii) follows directly from the transitivity of set inclusion, since according to the given
predicates and Definition 11, we have MA(ff) ' MA(fi) and MA(fi) ' MA(fl). 2
The transitivity of propagation pattern refinement provides a sound basis for incremental design of
propagation patterns.
So far, we have shown that propagation pattern refinement is an important behavioral abstraction mechanism
for reuse of method definitions and query specifications. It encourages information localization
and offers better flexibility and adaptiveness towards schema modifications, especially towards future
operational requirement changes. By means of the behavioral refinement mechanism, three levels of
reusability can be obtained for managing the operational schema changes:
(i) The specification of propagation patterns can easily be reused. (See Figure 10 and Figure 11.)
(ii) The binding of method annotations to classes at propagation time can largely be reused.
(Compare the binding shown in Figure 7 and Figure 8.)
(iii) The generated code (e.g., for C++) can possibly be reused as well. (Compare the code
generated in Figure 7 and Figure 8.)
We believe that the propagation pattern refinement mechanism will increase the potential benefits of
using propagation patterns as a higher level database programming technique.
5 Related Research
Schema evolution is commonly recognized as a required facility in a persistent object-oriented system.
Generally speaking, the schema describes the interface between the set of application programs and the
persistent repository of objects. When the schema changes, so does the interface, which possibly incurs
incompatible elements on both sides.
Up to now, there have been two main research directions for achieving seamless schema evolution in
an object-oriented database system. One is to effectively integrate schema modifications and the propagation
of schema changes into the object instances (instance adaptation) as well as the application
programs (program adaptation). Several research projects have contributed to this issue in one way or
the other, such as Encore [20], GemStone [6], O 2 [23], Orion [1], OTgen [?]. One of the recent contributions
along this direction is the lazy update propagation problem and solutions addressed in [?, ?].
It provides mechanisms to guarantee a correct update propagation in terms of conversion functions in
the presence of schema modification. Large efforts, however, remain required in practice in order to
provide adequate propagation mechanisms to make the instance adaptation and program adaptation
effective. The other direction is to improve the design of database method and query specification languages
such that software programs written in these advanced languages have higher adaptiveness and
seamlessness to the schema evolution. However, there has been surprisingly little attention paid in the
database community towards this direction, although software reuse has been one of the critical issues
in software engineering for the last decade. As [2] has shown, program adaptation can be exceedingly
hard for typed languages (such as C++) even for simple schema changes. Therefore, it is important
and beneficial to put some research effort on avoiding or minimizing program changes in anticipation of
schema updates rather than trying to fix things after changes occured. The work reported in this paper
presents our contributions on how to use polymorphic reuse mechanisms to achieve higher adaptiveness
in object-oriented database specifications. We have presented two polymorphic reuse mechanisms: propagation
patterns and propagation pattern refinement and shown the role of these two reuse mechanisms
in avoiding or minimizing the impact of schema evolution on application programs in an object-oriented
database.
This work has been mostly encouraged by the Demeter system ([11], [12], [19]), the contract model [7],
and the activity model ([?], [17]). In comparison with the contract model, both propagation patterns
and contracts encourage a separation of object behavior specification from object structure specification
and both present interesting techniques for operational specification. But there are also a number of
differences. First of all, propagation patterns provide better adaptiveness towards schema evolution and
change management, because by means of propagation patterns and the propagation pattern refinement
mechanism, the reprogramming of methods and queries due to schema modifications can be avoided or
minimized. Second, propagation patterns concentrate more on the specification of and reasoning about
operation propagations among a group of related classes; whereas contracts emphasize more on the obligation
specification of each participant class in accomplishing a task defined by a group of cooperating
classes. Third, the conformance of contracts with classes is required explicitly in the contract model,
whereas the conformance of propagation patterns with classes is derived implicitly at propagation time.
Comparing the reuse mechanism of propagation patterns with the behavioral abstraction mechanisms
defined in the activity model [17], it is interesting to note that although there is a similarity between the
concept of propagation pattern refinement and the concept of activity specialization, the emphasis and
functionality of the activity model is on the declarative specification and reasoning of communication
behavior of objects. There is no consideration on specifying and reasoning about operation propagations
among cooperating classes in the current activity model.
An efficient implementation of propagation patterns has been described in [18]. The paper shows how
to generate an efficient object-oriented program, say in C++, for a given propagation pattern and a
compatible class dictionary graph. A proof of the correctness of the core of the translation is given.
The work in [8] presented a formal framework for maintaining behavior and consistency of object-oriented
systems during software evolution. The framework effectively couples the change avoidance
approach of propagation patterns with a change management mechanism to fully automate evolution.
Class structure transformations may render existing objects and programs inconsistent. The paper
identifies the introduced inconsistencies and provides the necessary object and program transformations
to reinstate consistency while maintaining the behavior of the system. A formal definition of behavioral
equivalence is given. To prove behavioral equivalency of propagation patterns, the paper defines a formal
semantics for propagation patterns and describes a proof system for the semantics. The semantics
formally defines the order of wrapper execution for prefix and suffix wrappers. The feasibility of the
evolution framework is demonstrated for a representative set of primitive class structure transformations,
mainly based on the extension relations identified in [9] and [14]. Such extension relations are useful
means for quality control of schema transformations. Quite differently, the work presented in this
paper focuses on how to reuse the existing design and specification under the schema modifications and
requirement changes, and how the existing propagation patterns can be reused or extended incrementally
to cover the new requirements, especially when both structural and operational changes are required.
Another interesting project based on graph and class hierarchy is the OQL proposal [?]. A OQL query
is specified as a subgraph of the Schema graph. The subgraph contains the traversals of object classes
with AND and OR branches and association operators. Comparing with the calculus-based language
OQL, our approach emphasizes more on adaptive design and specification of databases to facilitate
program adaptation and change propagation in anticipation of schema changes.
6 Concluding Remarks
We have shown the viability of our approach to the incremental design and reuse of object-oriented
database specifications. We argue for raising the level of abstraction for specification of object methods
and database queries and show that this helps to avoid or minimize the reprogramming of methods
and queries due to schema modifications. The salient features of this approach are the use of propagation
patterns and propagation pattern refinement. The main benefits of using our polymorphic reuse
mechanisms in object-oriented database specifications are the following.
ffl The concept of propagation patterns presents a promising technique for enhancing the robustness
of methods and query programs with respect to schema modifications. Using propagation patterns
provides method designers and query writers with an opportunity to specify operations without
knowledge of detailed navigational information. Compared with most existing object-oriented
languages, the effort required for manually reprogramming methods and queries due to schema
modifications is largely avoided or minimized.
ffl The concept of propagation pattern refinement is an important mechanism for the abstraction
and reuse of propagation patterns. It promotes incremental design of methods and is especially
useful for dealing with a class of operational requirement changes. To our knowledge, none of
the existing object-oriented specification languages provides a similar support for the incremental
definition of methods.
ffl We have studied the formal semantics of both propagation patterns and propagation pattern
refinement. This formal basis provides a sound framework for the implementation and the further
development of the ideas presented here.
As shown by the examples in the previous sections, propagation patterns are currently well-supported in
a CASE tool called the Demeter System TM / C++. Therefore, they can easily be adopted to any C++
based object-oriented database system through the Demeter C++ tool. In order to give a road map
of possible implementation considerations of propagation patterns and propagation pattern refinement,
we would like to add a brief illustration on how the Demeter C++ tools translate propagation patterns
into C++ code. The Demeter tools can be divided into three categories: consistency checker, code
generators, run-time library. Both consistency checker and code generators are used before compile-time,
and each can be further divided into a structural and a behavioral part, which apply to class dictionary
graphs and to propagation patterns respectively. In other words, at compile time, the application
under development consists exclusively of C++ code. No run-time constructs are needed to implement
propagation patterns. This has gained two advantages: 1) the system has no speed degradation due
to propagation pattern run-time overhead. 2) if desired, the system could be decoupled from the
Demeter system at any time to become a stand-alone application. The structural consistency checker
first checks the class dictionary graph for validity. Then the structural code generator generates C++
class definitions in accordance with the class dictionary graph. The task of the behavioral consistency
checker takes as input a list of propagation patterns and a class dictionary graph, and examines whether
those propagation patterns are syntactically correct and whether they are compatible with the given
class dictionary graph. If so, the behavioral code generator generates the appropriate member function
headers and C++ implementations.
Future work on research and development of propagation patterns and behavioral refinement of propagation
patterns continues. We are interested in further investigation on both theoretical justification and
practical applicability of our approach. For example, it would be interesting to extend the polymorphic
reuse mechanisms discussed in this paper and use them as a candidate for object-oriented view defini-
tions. Object view is an important feature of persistent OODB systems and it becomes more and more
popular to use view approach to deal with interoperability in a distributed and heterogeneous database
environment. We believe that using the polymorphic reuse mechanisms would greatly enhance the adaptiveness
and robustness of a global (and virtual) view schema and thus of those application programs,
which were developed by users from different sites, against local schema changes. We are also interested
in further exploring issues such as what are the critical rules for achieving a good understanding and
an effective translation of propagation patterns and behavioral refinement of propagation patterns; and
how the polymorphic type theory may further enhance the formal development of propagation patterns
and other kinds of behavioral abstractions of propagation patterns.

Acknowledgement

We would like to thank the subject editor Stanley Su, the editor-in-chief Benjamin Wah, and the
reviewers for their helpful comments and suggestions. Our thanks are also due to Susan Even, Markku
Sakkinen, Ignacio Silva-Lepe and Cun Xiao for the discussion and remarks on an earlier version of this
paper. An extended abstract was published in the proceedings of ICDE'94 [?].



--R

Semantics and implementation of schema evolution in object-oriented data bases
Maintaining Behavioral Consistency during Schema Evolution.
A view mechnism for object-oriented databases
A semantics of multiple inheritance.
On understanding types
Development of an object-oriented dbms
Specifying behavioral compositions in object-oriented systems
Automating Change Management of Object-Oriented Systems

The breakdown of the information model in multi-database systems
The Art of Growing Adaptive Object-Oriented Software
Formulations and Benefits of the Law of Demeter.
Experience with a graph-based propagation pattern programming tool

Adaptive object-oriented programming using graph-based customization
Formal Foundations for Object-Oriented Data Modeling
Activity model: a declarative approach for capturing communication behavior in object-oriented databases
Efficient Implementation of Adaptive Software.
A Report on Demeter/C
Type evolution in an object-oriented data base
Schema modification without database reorganization.
A framework of schema updates in an object-oriented database
A framework of schema updates in an object-oriented database system

--TR

--CTR
Zahir Tari , Xue Li , Ling Liu, Type Safety in the Context of Method Updates, Journal of Intelligent Information Systems, v.13 n.3, p.279-298, Nov.-Dec. 1999
Salvatore T. March , Charles A. Wood , Gove N. Allen, Research Frontiers in Object Technology, Information Systems Frontiers, v.1 n.1, p.51-74, July 1999
program adaptation;adaptive software specification and development;object-oriented database systems;schema evolution;software reuse;knowledge reasoning