e.Guard.
View integration is the most effective technique for developing a conceptual database model. The universe of discourse is described from the viewpoint of different user groups or parts of the system resulting in a set of external models. In a second step these models have to be integrated into a common conceptual database schema.
In this work we present a new methodology for integrating views based upon an object oriented data model, where we concentrate on the integration of the behavior of objects, which is already not supported by existing view integration methods.
In [5] we made a comparative analysis of various view integration methodologies, two for extended E-R models ([1] and [13]) and two for object oriented models ([8] and [9]). We found, that these integration methodologies support the integration of the static models well. However, none of them considers the integration of the dynamic models. [8] state that behavior describes application semantics and, therefore, should not be part of a conceptual database schema. [9] divide behavior into operations and path methods. The later are used to access attributes via relationships of types. Also in their opinion operations should not be part of the conceptual database schema.
We do not share these opinions. First, we believe that path methods are a kind of redundancy, which should be part of the conceptual database schema for special reasons at least, for instance for comfortable access (just like views). Second, in our opinion important common behavior of objects must be part of the conceptual database schema and not implemented in applications.
Our integration methodology consists of two major phases, the integration of the static models and the integration of the dynamic models.
The integration of the static models deals with the structural parts (types, attributes and their relationships to other types). The aim of this phase is to identify and solve conflicts (naming conflicts or structural conflicts) among the types of the various views. The result of this integration phase is the common conceptual static model of the universe of discourse. Several integration strategies, mainly for the entity relationship model ([4]) were published in the past, for instance [1, 8, 9, 13] or [18]. Further comparative analysis of view integration methodologies were made in [2] and [17]. For our methodology we did not develop another strategy for integrating the structural part of types but use already published methodologies, mainly [13] and [14].
Through the integration of the different static models of the views we get the integrated conceptual static model. Afterwards the integration of the dynamic models of the views takes place. For each integrated type its corresponding dynamic models of the views have to be integrated.
In an earlier paper ([6]) we presented a meta model for state charts together with a set of transformation which are proven to keep the semantics of the models and which are complete in the sense that they suffice to derive any equivalent model from a given one. This forms the basis of the integration of dynamic models, which consists of the following steps:
First, we formalize the dynamic model by formally defining the range of all states in all dynamic models with constraints or conditions on the given static type. The range of a model is thus defined as a subspace of the object space spanned by the definition of the type. Then we analyze the relationship of the models on basis of their ranges and their marginal states (begin and end states). Relationship classes are disjoint, consecutive, alternative, parallel, and mixed.
Second is the integration-in-the-large where we develop an integration plan with the goal of minimizing the integration effort. The integration plan consists of integration operators for the different relationships of models. For mixed relationships, a further analysis is necessary where all states and events of two models have to be analyzed to integrate the models. For the other relationships integration operators only consider the marginal states. A crucial part of the development of an integration plan is to derive the relationship of the model resulting from the integration of two models with all the other models without actually performing the integration.
Third, in the integration-in-the-small the integration is performed by executing the integration plan.
In the next sections we concentrate on the integration of dynamic models. In section 2 we present an overview of the used data model. In section 3 an example from the domain of a library is presented to demonstrate our methodology. The integration process for dynamic models is shown in section 4 illustrated by the library example. However, in this paper we give an overview of our integration approach in a more descriptive way without presenting all the formal details and proofs. Interested readers are referred to [7] and [6].
For the integration methodology we use TQL++ for designing the static model (types with their attributes and relationships to other types) of the views and state charts for describing the behavior of objects. However, for the integration we had to made some extensions to dynamic models to formalize the semantics of state charts. In [6] we presented this language in detail. Let us discuss them briefly in the next paragraphs.
A dynamic model of a type primarily consists of states and events. We allow an event to occur several times within a dynamic model and, therefore, distinguish between the event and its event occurrences. An object which is in a state S1 can react to an event's occurrence e resulting in a transition of the object to a new state S2. We call S1 the source state of the event occurrence e and S2 the target state of the event occurrence.
To reduce the complexity and to make dynamic models more readable states can be structured to state hierarchies. That are state generalizations, to express alternatives, and state aggregations, to express parallelism according to OMT [15].
States are provided with conditions, which an object must fulfill to be in the state. These conditions, we call them the range of a state, are based upon the attributes and relationships of the type. The range of a state S1 can be regarded as a logical expression resulting in true if an given object is in the state S1, in false otherwise. Dynamic models have a range too, which is defined as the disjunction of ranges of the states of the dynamic model.
States may be marked as start and end states ("marginal" states). For instance the initial and final states are start and end states. However, the designer is allowed to mark any further state too.
Furthermore event occurrences have pre- and postconditions, which again are logical expressions. The preconditions of an event occurrence are the conditions, an object must comply to enable the event occurrence causing a state transition. The precondition of an event occurrence is defined as the conjunction of the range of its source states and its guard.
The postcondition of an event occurrence are those conditions an object must fulfill after the application of the event occurrence. Therefore, the postcondition of an event occurrence must imply the ranges of its target states.
As specification language for these conditions we use TQL++. For
addressing these additional characteristics we use meta methods of
dynamic models, states or event occurrences. With S1.Range() the
conditions (the range) of the state S1 is meant. We write e.PreC()
to get the preconditions of an event occurrence e. As these conditions are
logical expressions we may combine them by disjunction, conjunction or
negation. For instance the preconditions of an event occurrence e is
computed by the conjunction of the range of its source state and its
guard, that is e.Source_State.Range( ) e.Guard.
Ranges of states as well as pre- and postconditions of event occurrences are additional characteristics of dynamic models, which are used to define the semantics of state charts. In [6] we defined the semantics of state charts and a complete set of schema transformations to transform a dynamic model into any other equivalent dynamic model. As an example we have transformations to decompose and to construct state hierarchies, to split and to combine states and to shift event occurrences within state hierarchies.
In the next sections we discuss the process of integrating the dynamic models of an integrated type. We assume that the integration of the static models has already been finished. Therefore, we have to deal with one integrated type and several dynamic models to integrate. We start with a short example followed by a discussion of each integration step.
Book having the following TQL++ syntax:
Book = [
Isbn: str,
Title: str,
Authors: {Author},
reserved: bool,
status: (requested, ordered, lost, in library,
borrowed, in textbook collection)]
The behavior of a book from the viewpoint of the Book Ordering
Department is shown in figure 1(a). The department treats
incoming book requests, checks for doublets and orders books. Delivered
books are registered and placed into the library.
Book
Books can be borrowed at the Book Service Desk if they are
available. Books may get lost. The dynamic model of a book from the viewpoint
of the Book Service Desk is shown in figure 1(b).
At least the Educational book department is responsible for the
administration of educational books, which are necessary for a lecture during
a certain period. Such books may not be borrowed by anyone until the end of
the lecture.
If the book in question is out of stock it can be reserved by the
department. Reserved books may not be borrowed by anyone except the
educational book department. The behavior of a book from the viewpoint of
this department is shown in figure 1(c).
For the integration of dynamic models we demand the specification of states as well as the postconditions of the event occurrences, which are shown in the tables 1, 2 and 3. The postconditions of the event occurrences are equivalent with their target states. Start and end states are marked with (S) and (E) in the views.
book request | this.Isbn is UNKNOWN this.status = requested
|
doublet control | this.Isbn is KNOWN this.status = requested
|
rejection | this.Isbn IN book.Isbn this.status = rejected
|
book order | this.Isbn # book.Isbn this.status = ordered
|
book on stock | this.status = in library this.reserved = false
|
book available | this.status = in library this.reserved = false |
book on loan | this.status = borrowed |
book lost | this.status = lost |
book in the library | (this.status = in library  this.status
= borrowed)
this.reserved = false |
book reserved | this.status = borrowed this.reserved = true |
educational book | this.status = in textbook collection |
Let us discuss the consecutive relationship more detailed. Consider the example in figure 2, where you can see the dynamic models M1 and M2. Except an overlapping area between "marginal" states (end states of M1 and start states of M2) the ranges of the dynamic models have to be disjoint. The ranges of the "marginal" states must either be equivalent or the range of one state has to imply the range of the other state. Figuratively spoken an object travels first through M1, reaching for example the end state m1 of M1. As the range of m1 is equivalent (or implies) the range of the start state n1 of M2 the object gets into the dynamic model M2.
For each relationship class between dynamic models we have developed integration operators. An integration operator gets two dynamic models to integrate and delivers the integrated dynamic model. The integration operator IPar integrates two parallel dynamic models into a state aggregation. IDis, which integrates disjoint dynamic models, is very simple as there is nothing to integrate. It simply builds the union of both dynamic models to the integrated dynamic model. ICons integrates consecutive dynamic models by combining the "marginal" states of the overlapping area to single states. The same does IAlt with alternative related dynamic models. However, IMix, which integrates mixed related dynamic models, is much more complicated. A detailed analysis of the states and events of both dynamic models is necessary, which we will discuss later on.
In our example of figure 1 we determine the following
relationships between the dynamic models. The dynamic models of the
Book Ordering Department and Book Service Desk are
consecutive. The end state Book on Stock from the
Book Ordering Department and the start state Book
available from the Book Service Desk are equivalent, the
remaining states are disjoint (compare the state specifications
in the tables 1 and 2). The dynamic models of the
Book Ordering Department and Educational Book Department
are consecutive too, because the range of the state book
on stock implies the range of the state book in the library
(compare tables 1 and 3). The dynamic models of the
Book Service Desk and the Educational Book
Department are mixed related (compare tables 2 and
3).
Therefore, we have to consider the consequences of each integration step. Suppose we would like to integrate two dynamic models M1 and M2 with an integration operator. This results into a dynamic model MI, the relationship graph must be changed. M1 and M2 have to be replaced by the model MI. But which are the relationships of MI to other dynamic models of the integrated type?
According to the definition of the relationships between dynamic models the answer to this question depends on the range of the integrated dynamic model and its start and end states. For each integration operator, except IMix, which integrates mixed related dynamic models, we know the range as well as the start and end states of the integrated dynamic model.
Consider a small example. Suppose we integrate M1 and M2, which are disjoint, to MI. Suppose further that M3 is consecutive to M1 but disjoint to M2. Obviously MI and M3 will be consecutive too. Another example, suppose we integrate M1 and M2 with a mixed relationship. This cannot be done automatically. We may conclude only the range of the integrated model MI, but not the "marginal" states of MI. Therefore, if there is a relationship between another dynamic model M3 and M1 (except a disjoint relationship) M3 and MI will be mixed too.
It is possible to derive the consequences to the relationship graph caused by the application of an integration operator for each thinkable combination of relationships without actually recomputing them. Interested readers are referred to [7], where changes of the relationship graph due to an application of an integration operator are proven.
The integration plan determines an integration sequence with minimal integration effort, which depends on the automatization possibilities of the integration operators. Integrating mixed related dynamic models with the integration operator IMix requires an additional analysis and cannot be done fully automatically. Therefore the integration effort for the application of IMix is high. Furthermore in general the more states the dynamic models have the higher is the integration effort. In contrast to IMix the other integration operators are automizable, their integration efforts are low. This leads to a sketch of a rule based algorithm to compute the integration plan:
Educational Book Department and Book Service Desk which are mixed related, the integrated dynamic
model would have a mixed relationship to the model of the Book
Ordering Department We would need another usage of the "expensive"
integration operator IMix. However, if we first integrate the models of the
Book Ordering Department and the Book Service Desk
with the integration operator ICons to M1 and afterwards M1
model with the dynamic model of Educational Book Department to MI we
would need IMix only once. Our integration plan looks like:
|
ICons (Book Ordering Department, Book Service Desk, M1) IMix (M1, Educational Book Department, MI) |
According to the integration plan of our library example we have to integrate
the dynamic models of the Book Ordering Department and the
Book Service Desk using the integration operator ICons. The
operator ICons simply combines the annotated states on the edge of the
relationship graph, that are Book on Stock and Book
available to one state. The integrated dynamic model M1 is shown in
figure 4.
However, integrating dynamic models whose relationship is mixed is much more complicated, a further detailed analysis is necessary. Furthermore the integration of mixed related dynamic models cannot be done automatically. We are only able to support the designer by computing integration recommendations.
Just as dynamic models the states of different dynamic models have relationships. For instance the ranges of states may be equivalent or disjoint or the range of a state may imply the range of another state ( we say a state subsumes another state). Ranges of states may be overlapping. Once more a graph, the state relationship graph, is used to represent the relationships between states. The nodes of this graph are the states of the dynamic models. An edge between a state of one model and a state of another model exists if there is a relationship other than a disjoint one between them.
A part of the state relationship graph which is computed by the usage of IMix in our library example is shown in figure 5. The ranges of the other states between the dynamic models to integrate are disjoint.
As we do not consider disjoint relationships in the state relationship graph, the graph must not be fully connected. For each connected subgraph the states of the dynamic models have to be integrated according to the following way:
book in the library - not reserved | this.status = in library
reserved = false
|
book borrowed - not reserved | this.status = borrowed
this.reserved = false
|
book borrowed - reserved | this.status = borrowed
this.reserved = true
|
To conclude our library example we transform
the involved states of the state relationship graph into disjoint states,
resulting in the states Book in the Library - not reserved,
Book borrowed - not reserved and Book borrowed -
reserved. The specification of these states are shown in
table 4.
The transformed states with their event occurrences are shown in figure 6 (not involved states are dotted). Note, that the application of schema transformation leads to copying event occurrences.
In the second step we may consider combining some of the
states or creating state hierarchies. For instance we may build a
state generalization based upon the states Book borrowed - not
reserved and Book borrowed - reserved as they
have some event occurrences in common, e.g. loosing.
As all states of the state relationship graph of our example are integrated we finish the integration with the integration operator IMix and return to the integration plan.
Our methodology of integrating behavior models consists of the phases integration-in-the-large and integration-in-the-small. The aim of the first integration phase is to determine an overall structure of the integrated dynamic model. Based upon relationships between dynamic models integration operators are defined, which integrates the dynamic models. The result of the integration-in-the-large is the integration plan stating an integration order with minimal effort.
Within the integration-in-the-small phase the integration of the dynamic models takes place. Most of the defined integration operators can be performed automatically. However, for mixed related dynamic models a further detailed analysis of states and events is necessary.
It was our aim to relieve the designer by automizing the integration as much as possible. In some situations the integration of behavior models can be done without the aid of a designer. Even the integration of mixed related dynamic models could be computed by using additional heuristics for the combination of states. However, the designer is allowed to make changes in order to improve quality.
We see the main advantages of our approach in the formal treatment of the integration process which allows a highly automatic integration while giving the designer the possibility to make decisions and automatically carry out their consequences in the model.
[1] C. Batini and M. Lenzerini. A Methodology for Data Schema Integration in the Entity Relationship Model. IEEE Transactions on Software Engineering, 10(6):650-664, November 1984.
[2] C. Batini, M. Lenzerini, and S. B. Navathe. A Comparative Analysis of Methodologies for Database Schema Integration. ACM Computing Surveys, 18(4):323-364, December 1986.
[3] R. Cattell, D. Barry, D. Bartels, M. Berler, J. Eastman, S. Gamerman, D. Jordan, A. Springer, H. Stickland, and D. Wade. The Object Database Standard: ODMG 2.0. Morgan Kaufmann Publishers, Inc, 1997.
[4] P. Chen. The Entity-Relationship Model - Toward a Unified View of Data. ACM Transaction on Database Systems, pages 9-36, March 1976.
[5] J. Eder and H. Frank. Schema Integration For Object Oriented Database Systems. In M. Tanik et al., editor, Software Systems in Engineering. ASME, 1994. Procceedings of the ETCE, New Orleans.
[6] H. Frank and J. Eder. A Meta-Model for Dynamic Models. Technical report, Institut für Informatik, Universität Klagenfurt, March 1997. http://www.ifi.uni-klu.ac.at/cgi-bin/publ_search.
[7] H. Frank. View Integration für objektorientierte Datenbanken. PhD thesis, Institut für Informatik, Universität Klagenfurt, 1996.
[8] W. Gotthard, P. C. Lockemann, and A. Neufeld. System Guided View Integration for Object-Oriented Databases. IEEE Transaction on Knowledge and Data Engineering, 4(1):1-22, January 1992.
[9] J. Geller, Y. Perl, E. Neuhold, and A. Sheth. Structural Schema Integration with Full and Partial Correspondence using the Dual Model. Information Systems, 17(6):443-464, 1992.
[10] D. Harel. On Visual Formalisms. Communications of the ACM, 31(5):514-530, May 1988.
[11] H. Lam and M. Missikoff. On Semantic Verification of Object-Oriented Database Schemas. In Proceedings of Int. Workshop on New Generation Information Technology and Systems - NGITS, pages 22-29, June 1993.
[12] M. Missikoff and M. Toaiti. Mosaico: an Environment for Specification and Rapid Prototyping of Object-Oriented Database Applications. EDBT Summer School on Object-Oriented Database Applications, September 1993.
[13] S. B. Navathe, R. Elmasri, and J. Larson. Integrating User Views in Database Design. IEEE Computers, pages 185-197, January 1986.
[14] S. B. Navathe and G. Pernul. Advances in Computers, volume 35, chapter Conceptual and Logical Design of Relational Databases, pages 1-80. Academic Press, 1992.
[15] J. Rumbaugh, M. Blaha, W. Premerlani, F. Eddy, and W. Lorensen. Object-Oriented Modeling and Design. Prentice Hall International, Inc, 1991.
[16] J. Rumbaugh. Controlling Code: How to Implement Dynamic Models. Journal of Object-Oriented Programming, May 1993.
[17] M. Schrefl. A Comparative Analysis of View Integration Methodologies. In R. Traunmüller R Wagner and H. Mayr, editors, Informationsbedarfsermittlung und -analyse für den Entwurf von Informationssystemen, pages 119-136, 1987. Fachtagung EMISA.
[18] A. P. Sheth. Issues in Schema Integration: Perspective of an Industrial Researcher. In ARO-Workshop on Heterogeneous Databases, September 1991.