Original articles

System design and architecture

Federated integration of replicated information within hospitals

Wilhelm Hasselbring

University of Dortmund, Department of Computer Science, Informatik 10, D-44221 Dortmund, Germanye-mail: hasselbring@ls10.informatik.uni-dortmund.de

Received: 10 March 1997 / Revised: 5 June 1997 /Accepted: 5 August 1997

Abstract. A fundamental concern in hospital informa-tion systems is the integration of information acrossheterogeneous subsystems at the data level. Consistentdata replication is a central problem to be solved in thisdomain. The speci®c requirements and problems forintegration of information within hospitals are discussedand a software architecture which has been designedaccording to these requirements is presented. The pur-pose of this paper is to study the problems and solutionsof propagation of information updates across heteroge-neous subsystems within hospitals. The general structureof the presented architecture is based on the referencearchitecture for federated database systems (Sheth andLarson 1990) and adapted to the speci®c demands onintegration of replicated information within hospitalinformation systems. This architecture is the basis foralgorithms that restore the integrity of replicated infor-mation when changes occur. A prototype implementa-tion is discussed.

Key words: Hospital information systems ± Electronicmedical records ± Federated database systems ± Datareplication

1 Introduction

Digital libraries store materials in electronic format andmanipulate large collections of those materials. However,the meaning of the term digital library has di�erentmeanings to di�erent people as discussed in Fox et al.(1995).

In any case, hospitals o�er an environment for de-ploying digital library techniques. The ®eld relies heavilyon visual observation, e.g., of magnetic resonance imag-ing (MRI), computed tomography (CT), or x-ray ®lms.Hospitals generate complex databases of electronic med-

ical records which are a potential research resource. Ad-ditionally, hospitals require complex information ¯ow.

Most current work on digital libraries is concernedwith o�ering access to collections of materials that wereformerly stored in traditional libraries. Typical examplesare journal articles and books. A central concern in thisarea is the retrieval and display of documents which meetthe requirements of users who are searching within a li-brary or within a collection of libraries for speci®c in-formation. Therefore, most research on integration ofheterogeneous information has focused on informationaccess.

The purpose of a hospital information system (HIS) isto manage the information that health professionals needto perform their jobs e�ectively and e�ciently (Shortli�e,Perreault, Fagan, and Wiederhold 1990). Integratedsystems which satisfy all requirements on informationprocessing in hospitals are not available, even if somevendors promise this. Also, from an economical per-spective, it is desirable to install a number of applicationsthat e�ectively support the speci®c needs of the individ-ual organizational units of a hospital. Typical examplesare systems for patient registration, admission, dischargeand transfer, appointment scheduling, management oflaboratory tests as well as decision support for medicaltreatment. This situation naturally leads to a collection ofheterogeneous subsystems scattered across the hospital.To e�ectively support the work in hospitals, it is neces-sary to integrate these subsystems avoiding multiple entryof the same information and inconsistencies among in-formation that is stored in di�erent subsystems. Inte-gration is a decisive factor for the successful operation ofa computer-based HIS (Ehlers, Schillings, and Pietrzyk1992). The integration of data from various sources in thehospital produces a rich database supporting healthprofessionals with their work. A modular system ofinteroperable and cooperating subsystems, which retaintheir autonomy as far as reasonable, is required.

As a small portion, Fig. 1 illustrates the overlappingareas of information relevant for individual subsystemsin hospitals for a laboratory, a radiology and an ad-ministration subsystem. It is important to note that it isCorrespondence to: W. Hasselbring

Int J Digit Libr (1997) 1: 192±208

not the goal to provide access from all places in thehospital to all the information that is relevant for thehospital, but to integrate the overlapping areas. The basicpatient data such as name and birthday are in the over-lapping area of all systems, but insurance informationand therapy results are only relevant to the correspond-ing subsystems. Note, however, that the sizes of the areasin Fig. 1 are not proportional; only the structural seg-mentation is illustrated.

Even management information systems do not storeall the information: relevant information from multiplesources is integrated and copied into so-called datawarehouses (materialized views) for analytical processing(Inmon 1996; Zhuge, Garcia-Molina, Hammer, andWidom 1995). Consequently, such systems also do notrequire all the relevant information within the hospital.

A major need of HISs is, therefore, the integration ofthe overlapping areas of information stored among dif-ferent and heterogeneous applications, even if they havebeen developed at di�erent times, by di�erent vendorsand with di�erent technologies. An open federation ofautonomous but interworking systems should provideoptimized support to the speci®c needs of the individualunits by enabling di�erent vendors to o�er specializedapplications and allowing the users to select the moste�ective solutions for their needs.

Furthermore, there will not be one `right' databasesystem for all components of HISs. In selecting the mostappropriate sort of systems for components of a HIS, thetechnology that most completely satis®es the needs of thespeci®c user groups should be selected. Multiple data-bases will be necessary since no single database structureis likely to be optimal for each of the various require-ments on HISs. Each of the available software andhardware alternatives can have a place in the operation

of a HIS. Mainframe facilities may remain appropriatefor storage of large databases. Workstations have anadvantage in memory-intensive operations such asgraphics. Intermediate processing nodes will be requiredto transform information from dissimilar nodes andmake it accessible.

To summarize: within hospitals, it is usually not re-quired to use applications which o�er access to allavailable information in the hospital. Therefore, the userrequirements on information systems in hospitals arerather di�erent to the requirements on electronic versionsof traditional libraries. In HISs, exchange of informationbetween autonomous subsystems is a central concern forintegration of information.

Section 2 discusses some aspects of HISs that arerelevant to the paper, before the current state of the art inconnecting subsystems within hospitals through com-munication servers is discussed in Sect. 3. The generalarchitecture of federated database systems is discussed inSect. 4, and a federated software architecture for inte-gration of replicated information within hospitals ispresented in Sect. 5. Section 6 sketches the implementa-tion of a prototype system, which is built to evaluate thepresented architecture. Section 7 discusses related workand Sect. 8 draws some conclusions.

2 Hospital information systems

The di�erent demands of di�erent user groups of HISs ±physicians, nurses, administrators, health care research-ers, patients, etc. ± are discussed in Ball and Collen(1992). These di�erent demands lead to di�erent require-ments on HISs. For instance, physicians have a patient-oriented view to the information stored in medicalrecords for treating patients, and administrators have acase-oriented view to the medical record for charging thetreatment. It is unlikely that one integrated system will beable to satisfy all of them. Corresponding to the di�erentdemands of user groups, components of HISs are usuallydedicated to such diverse tasks as nursing, laboratories,pharmacies, radiology units, patient monitoring, admin-istration, decision support, medical research, etc.

A note concerning our terminology: a Hospital In-formation System or HIS is often regarded as a particulartype of product that only focuses on patient registration,admission, discharge, transfer, and other administrativefunctions. HIS in the context of this paper is a broaderconcept of Healthcare Information Systems as a federa-tion of autonomous information systems (which mayinclude a traditional HIS). However, we use the termHospital Information System because we restrict ourselvesto Healthcare Information Systems in hospitals. Wewould call a traditional HIS a Hospital AdministrationInformation System as one component of a HIS.

Electronic medical records are central components ofHISs, in particular with respect to the integration of in-formation. Section 2.1 discusses some concerns of elec-tronic medical records and Sect. 2.2 discusses somestandards for HISs and electronic medical records whichare relevant to the integration of heterogeneous systems.

Fig. 1. The overlapping areas of information stored among subsystems in

hospitals

193

2.1 The electronic medical record

The purpose of electronic medical records is to store theinformation about patients that is generated by physi-cians, nurses, hospital administrators, etc. The informa-tion that originates from diagnosis and therapy is acentral concern. Goals of digitizing medical records are,for instance, improving medical treatment of patients andthe computerized evaluation of patient data to supportresearch in medicine. Electronic medical records are notmerely automated forms of today's paper-based medicalrecords, but encompass the entire scope of healthinformation in all media forms. Thus, electronic medicalrecords may include medical history, current medica-tions, laboratory test results, x-ray ®lms, etc.

The electronic medical record has several advantagesover the conventional paper-based medical record, in-cluding:

± Patient information is available at several workingplaces at the same time.

± The information is available within a short time. Thisis important in case of emergency.

± Acquisition of data may be improved by the use ofadvanced user interfaces.

± Reuse of results of medical operations is supported,even over the lifetime of a patient. This may relievepatients from being checked with the same medicaloperations several times.

± Medical research is supported. An application area isthe control of the results of speci®c therapies (Ullrich,Hasselbring, Jahnke, RoÈ ser, and Christmann 1996).

However, the electronic medical record also has itsdisadvantages:

± It requires a larger initial investment than its papercounterpart because of hardware, software andtraining costs for the personnel.

± Capturing the physician-collected data for an elec-tronic medical record can require a lot of time ande�ort: physicians often use a great deal of informationto make one decision.

± New techniques to facilitate direct entry of such in-formation (e.g. speech input) can reduce this problem.

± It is only possible to read and enter patient data wherecomputer terminals are available.

± Mobile computing is a solution for this problem. Fora discussion of problems and solutions of mobilecomputing refer to Imielinski and Badrinath (1994).

± Data security may be a problem when the systemadministration is not done carefully and responsibly.Access control will be discussed in Sect. 5.2.6.

2.2 Standards for hospital information systems

There exist several initiatives for standardizing healthcaresystems (Bakker, Hammond, and Ball 1995; McDonald1995). Standards are under development for transferringinformation across subsystems, codifying text, describingthe content of the medical record, etc. The following

subsections take a short look at four standardizationinitiatives which are related to our work: the HL7protocol, CORBAmed of the Object ManagementGroup, coding systems for medical information, andthe European healthcare standards organization's e�orts.

2.2.1 The Health Level 7 protocol

The Health Level 7 (HL7) protocol has been designed tostandardize the data transfer within hospitals (Hammond1993). It is an application level protocol and so relatesto level seven of the ISO/OSI-protocol hierarchy(Tanenbaum 1996), but does not fully concur with theISO standard. HL7 covers various aspects of dataexchange in HISs, e.g., admission, discharge, and transferof patients, as well as the exchange of analysis andtreatment data. The HL7 standard represents hospitalrelated transactions as standardized messages. HL7 is ade-facto standard for data exchange between commercialsystems for hospitals (McDonald 1995).

HL7 de®nes messages as strings to be exchanged bysubsystems. The messages themselves contain standard-ized information, but do not invoke speci®c methods atthe destination. In Sect. 3, we will discuss how subsys-tems are usually connected within hospitals throughcommunication servers. Some communication servers forhospitals support standard protocols such as HL7.

The current version of the HL7 protocol (2.2) doesnot cover all requirements of hospital applications. Forinstance, the exchange of images is not supported. ACR-NEMA DICOM (Bidgood and Horii 1992) is a standardfor transmitting medical images, which can be used forthis purpose.

2.2.2 CORBAmed of the Object Management Group

CORBA is the `Common Object Request Broker Archi-tecture' of the Object Management Group to standardizeinteroperability among heterogeneous hardware andsoftware systems (Mowbray and Zahavi 1995). Simplystated, CORBA allows applications to communicate withone another no matter where they are located or who hasdesigned them. CORBA de®nes the Interface De®nitionLanguage (IDL) and the Application ProgrammingInterfaces (API) that enable client/server object interac-tion within a speci®c implementation of an ObjectRequest Broker (ORB). CORBA also de®nes interoper-ability by specifying how ORBs from di�erent vendorscan interoperate.

The ORB is the middleware that establishes the client-server relationships between objects. Clients can trans-parently invoke a method on a server object, which canbe on the same machine or across a network. The ORBintercepts the call and is responsible for ®nding an objectthat can accept the request, pass it the parameters, invokeits method, and return the results. The client does nothave to be aware of where the object is located, its pro-gramming language, its operating system, or any othersystem aspects that are not part of an object's interface.

194

CORBAmed is the Healthcare Special Interest Groupfor CORBA. In 1996, CORBAmed started the process ofadopting standard interfaces for healthcare related ob-jects by issuing a `request for information' which re-quested the healthcare and information technologyindustry to give the OMG guidance in its upcomingstandardization e�orts for CORBAmed.

It can be expected that the CORBAmed serviceswithin the CORBA framework will be an importantstandard for the interoperation among subsystems inhospitals [Sokolowski 1997]. However, in the currentstage of standardization it is not clear what exactlyCORBAmed will contribute to the challenge of inte-grating information within hospitals.

The HL7 Special Interest Group for Object BrokeringTechnologies is mapping the forthcoming version 2.3 ofHL7 to the IDL of CORBA, and version 3 of HL7 willbe based on a structurally object-oriented model of theunderlying data (Rishel and Quinn 1996). So, we canexpect a combination of CORBAmed and HL7 in thefuture.

2.2.3 Coding systems for medical vocabulary

Several initiatives for standardizing coding systems formedical vocabulary exist. The Systematized Nomencla-ture of Human and Veterinary Medicine (SNOMED) is acode structure which is widely accepted for describingpathological test results (Campbell and Musen 1992). Ithas a multi-axial coding structure for symptoms, diag-noses, procedures, etc. The Uni®ed Medical LanguageSystem (UMLS) (Lindberg, Humphreys, and McGray1993) contains a metathesaurus that links biomedicalterminology, semantics, and formats of the major clinicalcoding and reference systems. It links medical terms (e.g.SNOMED) to so-called medical index subject headings(MeSH codes) and to each other. The UMLS alsocontains a specialist lexicon, a semantic network, and aninformation sources map. Together, these elements areintended to represent all of the codes, vocabularies,terms, and concepts to become a foundation for themedical informatics infrastructure (Lindberg, Hum-phreys, and McGray 1993).

These coding systems are used to encode medical in-formation independent of any speci®c natural language.They can, for instance, be used to allow the exchange ofmedical records across di�erent language areas.

2.2.4 The European Committee for Standardisation

Working Group 1 on `Healthcare information modellingand medical records' of the European Committee forStandardisation CEN TC 251 recently de®ned a generalarchitecture which is intended as a basis both for thecomparison, evolution and integration of existing sys-tems as well as for the planning and high-level design ofnew open and modular systems of healthcare organiza-tions. To quote from the `Healthcare Information System

Architecture' pre-standard [CEN TC/251 WorkingGroup 1 1997]:

``with respect to the de®nition of the architecture for ahealthcare information system, it is enough to noticethat, at a high level of abstraction, any healthcare orga-nisation can be described by means of a federative model,as a set organisational components, mutually interactingfor the e�ective delivery of services.

By re®ning this concept, it can be also realised thateach organisational component of the healthcare enter-prise has a certain level of autonomy and independence,in terms of information managed and activities sup-ported, which can vary according to the speci®c organi-sational, clinical and logistical characteristics of theindividual centre and, even within the same centre, ac-cording to the speci®c aspects of the individual units.

Finally, it is important to stress that the architectureshould not prescribe a certain organisational form,rather, it should allow system structures that may align todi�erent organisational structures. A federated architec-ture does not dictate a speci®c organisational structure, itprovides a ¯exibility for the structuring of systems so thatthe information technology infrastructure may follow theadopted organisational structure.''

In CEN TC/251 Working Group 1 (1997), the pro-posed basic `Conceptual Architectural Framework' isstructured in three layers. We will relate these layers to thefederated architecture which will be presented in Sect. 5.

3 Current state of the art: connecting subsystemswithin hospitals through communication servers

To connect heterogeneous subsystems in hospitals,communication servers are often deployed (Lange,Osada, Prokosch, and Hasselbring 1996). Figure 2 dis-plays an example con®guration of a HIS with a centralcommunication server. In this con®guration, a laborato-ry, a radiology, two wards, an administration, and apharmacy application are connected by the server. Thecommunication server enables the subsystems to sendmessages to each other. Each subsystem is connected tothe communication server and sends messages only tothis server. The communication server determines thereceivers and forwards the messages. Hospital commu-nication servers usually support standard protocols suchas HL7 (see Sect. 2.2.1) and the translation acrossdi�erent protocols when forwarding messages.

The requirement for building complex systems thatcombine heterogeneous subsystems can be met at the lowlevel of interconnectivity or at the higher level of inter-operability (Pitoura, Bukhres, and Elmagarmid 1995).Interconnectivity simply supports system communication,while interoperability additionally supports systems tocooperate in the joint execution of tasks. A communi-cation server primarily supports interconnectivity±thesubsystems themselves:

± Need to know where to send which messages.± Must take the initiative to update replicas and send

messages for this purpose.

195

± Must be aware to receive messages from other systemsand store the message contents appropriately in theirlocal data stores.

With an integration that is based on a communicationserver, it is not known at the integration level at whichsites data actually is stored. It is only known that data isexchanged. A communication server does not knowwhether data is replicated or just needed temporarily bya client for answering a user query.

4 Federated database systems

A database system (DBS) consists of a database man-agement system and one or more databases that itmanages. As already discussed, data is usually distributedover a multitude of heterogeneous, autonomous DBSswithin hospitals. These systems are often isolated and anexchange of data among them is not easy. These are theproblems to be solved.

A federated DBS is an integration of such autono-mous database systems, where both local applicationsand global applications accessing multiple database sys-tems are supported (Sheth and Larson 1990). The workon federated DBSs focuses on three issues: autonomy,heterogeneity, and distribution:

± Federated DBSs are characterized by a controlled andsometimes limited integration of autonomous DBSs.Often, there are con¯icts between requirements ofintegration and autonomy.

± Causes for heterogeneity are di�erent database man-agement and operating systems utilized, as well as thedesign autonomy among component DBSs.

± In the case of federated DBSs, much of the distribu-tion is due to the existence of individual DBSs beforea federated DBS is built (legacy systems).

There exist several meanings of the terms federated DBS,multidatabase system, distributed DBSs, etc. Below, webrie¯y explain our interpretation of these terms to putour work in context.

Federated DBSs may be distinguished as being tightlyand loosely coupled (Sheth and Larson 1990). In the caseof loosely coupled federated DBSs, each component site

builds its own federated schema by integrating its localschema with the export schemas of some other compo-nent sites. Loose-coupling promotes integration andinteroperability via multidatabase query languages whichallow uniform access to all component DBSs (Tresch andScholl 1994). It does not require the existence of an in-tegrated schema, leaving many responsibilities, such asdealing with multiple representations of data and re-solving semantic mismatch, to the programmers ofcomponent DBSs. The schema architecture of tightlycoupled federated DBSs will be discussed in Sect. 4.2.There is no centralized control in federated systems be-cause the administrators of component DBSs controlaccess to their local data.

In contrast to federated DBSs, integrated DBSs donot distinguish local and nonlocal users, because thecomponent DBSs are not autonomous. Integrated DBSswhich provide a single global schema to the applicationsare called distributed DBSs (OÈ zsu and Valduriez 1991).Integrated DBSs provide the full functionality of DBSs(transaction and query processing, structured data or-ganization, etc).

Both federated and integrated DBSs are multidatabasesystems. Multidatabase systems can be classi®ed alongthe dimensions of autonomy, heterogeneity and distri-bution as shown in Fig. 3. Figure 4 displays the corre-sponding taxonomy. Other taxonomies and termin-ologies for multidatabase systems have been suggested(Bright, Hurson, and Pakzad 1992; Pitoura, Bukhres,and Elmagarmid 1995; Tresch and Scholl 1994; andothers).

4.1 The general system architecture

Figure 5 displays the general system architecture offederated DBSs. In a federated DBS, both globalapplications and local applications are supported. Thelocal applications remain autonomous, but must restricttheir autonomy to some extent to participate in the

server

communicationradiology

pharmacy

ward 1

ward 2

system

system

system

system

system

systemadministrationlaboratory

messages

database

database

database

database

database

database

messages messages

messages

messagesmessages

Fig. 2. A possible con®guration for the integration of a distributed HIS

through a communication server

Fig. 3. Classi®cation of multidatabase systems along the dimensions

autonomy, heterogeneity, and distribution (based on OÈ zsu and Valduriez

1991)

196

federation. Global applications can access multiple localDBSs through the federation layer. The federation layercan also control global integrity constraints such as datavalue dependencies across multiple component DBSs.

4.2 The schema architecture

For federated DBSs, the traditional three-level schemaarchitecture (Date 1995) must be extended to support thedimensions of distribution, heterogeneity, and autonomy.

The generally accepted reference architecture forschemas in tightly coupled federated DBSs is presented inSheth and Larson (1990) and, in the same form, inPitoura et al. (1995) where approaches to object-orien-tation in multidatabase systems are surveyed. The dia-gram in Fig. 6 displays this schema architecture whichpresents, apart from the dots that indicate repetition, onepossible con®guration of a federated database system.The di�erent schema types are:

Local schema: A local schema is the conceptual schemaof a component DBS which is expressed in the (na-tive) data model of that component DBS.

Component schema: A component schema is a localschema transformed into the (common) data model ofthe federation layer.

Export schema: An export schema is derived from acomponent schema and de®nes an interface to thelocal data that is made available to the federation.

Thus, only exported schema elements and their dataare accessible by the federation layer.

Federated schema: A federated schema is the result of theintegration of multiple export schemas, and thusprovides a uniform interface for global applications.

External schema: An external schema is a speci®c view ona federated schema or on a local schema. Externalschemas may base on a speci®c data model di�erentfrom the common data model. Basically, externalschemas serve as speci®c interfaces for applications(local or global).

4.3 The processing architecture

The edges between the schemas in Fig. 6 correspond tosoftware processors as indicated in the right hand columnof Fig. 6.

Transforming processors translate commands from asource language to a target language. Their purpose is toprovide data model transparency through hiding di�er-ences in query languages and data formats.

Filtering processors constrain the commands and as-sociated data that can be passed to another processor.

A constructing processor transforms commands onthe federated schema into commands on one or moreexport schemas: constructing processors and federatedschemas support the distribution feature of a federatedDBS. A constructing processor integrates the informa-tion from the export schemas.

As discussed in Sheth and Larson (1990), severaloptions in the schema and processing architecture areavailable, some of which are:

± Any number of external schemas can be de®ned, eachwith its own ®ltering processor.

± Any number of federated schemas can be de®ned,each with its own constructing processor.

± A tightly coupled federated DBS with multiple fed-erations allows the tailoring of the use of the federatedDBS with respect to multiple classes of global feder-ation users with di�erent data access requirements.

Fig. 4. A taxonomy of multidatabase systems. For HISs, tightly coupled

federated DBSs are most appropriate (indicated in the dotted blob)

Fig. 5. General system architecture of federated DBSs

...

...

...

...

...

Transforming Processors

Filtering Processors

Constructing Processors

Filtering Processors

Export Schema

Common Data Model

Component Schema

Common Data Model

Local Schema

Native Data Model

External Schema

Any Data Model

External Schema

Any Data Model

Common Data Model

Federated Schema

Common Data Model

Federated Schema

External Schema

Any Data Model

Export Schema

Common Data Model

Export Schema

Common Data Model

Component Schema

Common Data Model

Local Schema

Native Data Model

Fig. 6. The 5-level schema architecture as presented in Sheth and Larson

(1990) and annotated with the corresponding processor types

197

± Schemas on all levels, except the local and federatedschemas, are optional and may be combined into asingle schema of another level.

± A component DBS can participate in more than onefederation and continue the operation of local appli-cations.

Note, that a schema architecture which consists of justone federated schema and some local schemas concurswith the 5-level schema architecture of Sheth and Larson(1990). The other levels contain no schemas in this case.

These constraints are not de®ned formally. In Sect. 5,a re®ned model for our tightly coupled federated DBSarchitecture will be presented in a more formal way. Ourarchitecture requires schema integration and consist ofcomponent DBSs that can (and usually do) operate in-dependently but also participate in a federation to maketheir local data sharable. Component DBSs must grantpermission to access the data they manage and, therefore,restrict their autonomy to some extent.

With a tightly coupled federated DBS whose dataintegration is on the basis of schema integration, thefederation layer is capable of supporting subsystems tointeroperate. Instead of enabling the subsystems with acommunication server to send messages for informationexchange (Sect. 3), the exchange of information can beaccomplished through updates of replicated data insubsystems by the federation layer as will be discussed inSect. 5.

5 A federated software architecturefor hospital information systems

This section presents our federated software architecturewhich has been designed according to the speci®crequirements of integrating replicated informationamong heterogeneous components of HISs. The follow-ing subsections present an extended schema architectureand the associated algorithms that restore the integrity ofreplicated information when changes occur. The generalsystem architecture coincides with the architecture aspresented in Fig. 5.

5.1 Extending the schema architecture

It is rather obvious that the reference schema architectureof Sheth and Larson (1990) has been designed primarilyto support global access to the component DBSs, onlysecondarily to support integrity control. However, it is agood approach for resolving the syntactical and seman-tical con¯icts among heterogeneous schemas and forintegrating the schemas. Therefore, we extend thisreference schema architecture by import, export andimport/export distinction for public schemas to ade-quately support the algorithms for changing replicatedinformation (Hasselbring 1997a; Hasselbring 1997b).This distinction does not exist in the reference architec-ture of Sheth and Larson (1990), which is displayed inFig. 6.

Figure 7 displays a meta model for this extendedschema architecture for federated DBSs using the Uni®edModeling Language (UML) notation for class diagrams(Fowler and Scott 1997; Rational Software Corporation1997). In this model, some of the constraints and optionsfor the architecture, which are discussed in Sect. 4, arede®ned by means of the cardinalities at the associations.The distinct classes of public schemas replace the exportschemas in the reference architecture of Sheth andLarson (1990).

The diagram in Fig. 6 (apart from the dots that in-dicate repetition) can be regarded as an instance of themodel in Fig. 7. The model in Fig. 7 is a meta model forschemas and their associations. The class diagrams of theUML are very similar to the class diagrams of its pre-decessor OMT (Rumbaugh, Michael, William, Freder-ick, and William 1991).

Specifying an import schema in our architecture is asubscription to change noti®cations for the correspond-ing data. Export schemas specify data to be exported toother systems. Import/export schemas de®ne data to beboth imported and exported. The schema types deter-mine the change algorithms for integration of replicatedinformation as will be discussed below.

To explain the diagram in Fig. 7: rectangles are theUML symbols for classes. In the UML, cardinalities forassociations are speci®ed through numerical ranges at theassociation links. The default cardinality is 1. If thecardinality speci®cation comprises a single star, then itdenotes the unlimited non-negative integer range (zero ormore). The arrows attached to the association namesindicate the direction for reading the names which areannotations to associations (called name direction) (Ra-tional Software Corporation 1997).

The association between local schema and componentschema in Fig. 7 speci®es that each component schema istransformed from exactly one local schema, but eachlocal schema can be transformed into multiple compo-nent schemas when the corresponding component DBSparticipates in more than one federation.

A constraint in the UML is a semantic relationshipamong model elements that speci®es conditions whichmust be maintained (Rational Software Corporation

transformed intofiltered and

Federated Schema

Component Schema

integ

rated

into

tran

sfor

med

and

filt

ered

into

filter

ed in

to

application layer

middleware layer

{at least one}

Local Schema

transformed into

tran

sfor

med

and

filte

red

into

*

External schema**

*

*

{or}

{abstract}Public Schema

*

SchemaImport/Export

*

*

Export Schema

Import Schema

Fig. 7. Modeling the extended 5-level schema architecture as a UML class

diagram (Rational Software Corporation 1997)

198

1997). A constraint represents semantic information at-tached to a model element syntactically enclosed inbraces. The prede®ned or-constraints indicate situationsin which only one of several potential associations maybe instantiated at one time for any single object. This isshown as a dashed line connecting two or more associ-ations, all of which must have a class in common, withthe constraint forg labeling the dashed line. Any instanceof the class may only participate in at most one of theassociations at one time. This is simply a particular use ofthe constraint notation.

Each Public Schema is ®ltered from at least onecomponent or local schema and integrated into exactlyone federated schema. Each external schema is derivedfrom either one federated or one local schema, etc. Ex-ternal schemas which are directly derived from localschemas are used for local applications.

Inheritance is shown in the UML as a solid-line pathfrom the sub-class to the super-class, with a large hollowtriangle at the end of the path where it meets the super-class (Rational Software Corporation 1997).

In Fig. 7, Public Schema is an abstract class (Meyer1997). The concrete classes Export Schema, ImportSchema, and Import/Export Schema inherit all associa-tions from Public Schema. There will be no instances(schemas) of the abstract class Public Schema in an in-stantiated schema architecture.

As indicated in Sect. 2.2.4, Working Group 1 of theEuropean Committee for Standardisation proposes tostructure HISs in three layers (CEN TC/251 WorkingGroup 1 1997), to which we intend to relate our schemaarchitecture:

Application layer: The application layer consists of a setof applications individually supporting the speci®crequirements and functionalities in the various unitsof the hospital.

Middleware layer: The middleware layer relates to theoperation of the hospital as a whole, and is thereforeresponsible for supporting the functional and infor-mation interworking both of the individual applica-tions and of the de®nition and management ofinformation and procedures which are of relevance tothe hospital. It supports the cooperation of the dif-ferent applications.In order to comply with these requirements, theoverall HIS is to be described as a federation of in-formation systems, individually responsible for thesupport of the functional areas and individual orga-nizational units (CEN TC/251 Working Group 11997).

Bitways layer: The bitways layer is the basic technologicalplatform for the physical connection and interactionof all components of the system. It provides the basictechnological infrastructure.

In the right hand column of Fig. 7, the ®rst two layers arerelated to our schema architecture to place it into thecontext of the European pre-standard for the `HealthcareInformation System Architecture' (CEN TC/251 Work-ing Group 1 1997). As the basic technological infrastruc-ture, the bitways layer is not related to the schema

architecture. However, the bitways layer is used by thefederation layer to carry out the integration of distrib-uted subsystems, but this is not relevant at the schemalevel. It is remarkable that the `Healthcare InformationSystem Architecture' assigns the healthcare-related datato the middleware layer and not to the application layer(CEN TC/251 Working Group 1 1997).

5.2 Change algorithms

The schema architecture is the basis for algorithms thatrestore the integrity of replicated information whenchanges occur. For generality, we use the term changefor insertion, deletion and update of data. Below, achange algorithm with one master copy for data itemsand a change algorithm with multiple master copies fordata items are motivated and discussed. In the sequel, thespeci®cation of change propagation and the detection ofchanges are discussed.

5.2.1 Change algorithm with one master copyfor data items

As discussed in Stead et al. (1992), each datum in adistributed DBS for electronic medical records (and,consequently, in a HIS) should have only one mastercopy at which changes are allowed. Note, however, thatsuch a master (server) can cooperate with multiple clientsthat intend to modify the datum. The restriction to onemaster copy does not imply a restriction for data entryfrom just one location within a hospital. A system that isthe client in one situation may be the server in anothersituation provided only one system is the master for aparticular datum. A datum may be allowed to reside inmultiple places (replica), but changes must be handledthrough the master who forwards the changes to allplaces where copies of this datum exist. The federatedschema relates elements of export and import schemas toeach other, in which each element relates exactly oneexport element to one or more import elements. Thisconstraint should be enforced by the integration tools.

Figure 8 illustrates an example scenario for changingreplicas. Component DBS 1 exports a datum through anexport schema. Data about the same real world phe-nomenon is stored in component DBSs 2, 3 and 4. Thelatter three component DBSs import this datum throughsome import schemas. Component DBSs 2 and 3 sharethe same import schema. To integrate the semantic rep-lication of the same real world phenomenon, the feder-ated schema relates the appropriate parts of exportschema 1 to the corresponding parts of import schemas 2and 3. A change event in component DBS 1 on an ex-ported data item triggers corresponding change opera-tions of the replicas which are imported by the otherthree component DBSs. The dotted lines illustrate thedata ¯ow.

Figure 9 illustrates the passing of information up anddown in the schema architecture by means of a moredetailed example. The schemas in this example are more

199

detailed than in the scenario in Fig. 8, but Fig. 9 showsfewer schemas. On the lower left corner in Fig. 9, thelocal relational schema of a simple patient administrationsystem consisting of two tables is indicated. This localschema is mapped to the corresponding componentschema in the canonical data model of the federationlayer, which could be the object model of the ODMG-93standard (Cattell 1996). Here, the foreign key relationbetween Patient and Invoice is transformed to an object-oriented relationship. The patient administration systemexports the basic patient data through an export schemavia the federated schema to the object-oriented researchsystem as indicated by the dashed arrows. On the otherside, the object-oriented research system exports infor-mation about medical materials to the relational patientadministration system. Here, the research system storesused materials, which are transformed via the federatedschema to materials on invoices for the administrationsystem. When transmitting material, the patient identi®-

cation is attached to identify the corresponding patient.For simplicity, we assume that a patient is registered inthe administration system before the treatment starts forwhich materials are entered into the research system. Wewill present more details about the schema architecture inSect. 6.

5.2.2 Change algorithm with multiple master copiesfor data items

There exists the need to integrate pre-existing legacydatabase and ®le systems into HISs. Typically, theselegacy information systems have evolved over many yearsand play a crucial role in the day-to-day informationprocessing of the hospital. They are often di�cult tomodify and virtually impossible to rewrite.

There is, therefore, a need to provide techniques notonly for accessing the data which is locked inside thesesystems from newer systems, but also for providing astrategy which allows the gradual migration of the sys-tems to new platforms and architectures. A smooth mi-gration from legacy systems to modern informationsystems can be accomplished with federated DBSs(Radeke and Scholl 1995).

To integrate replicated information across legacysystems, it cannot be expected that only one master copyfor each datum exists at which changes are allowed,because legacy systems usually store the data in theirown repositories where the data items must be consid-ered as master copies. To incorporate such situations inwhich multiple master copies for speci®c data items areneeded, the import/export schemas can be used in ourarchitecture. An import/export schema speci®es that thecorresponding data items are imported as well as ex-ported.

The di�erence to a combination of an import with anexport schema is that data which is changed by the fed-eration layer does not trigger additional changes to bepropagated by the federation layer. Only changes by lo-cal applications trigger change events to be propagatedby the federation layer.

This mechanism avoids endless loops of changes bythe federation layer when the same information is ex-ported as well as imported by multiple component DBSs.However, import/export schemas should only be usedwhen multiple master copies for speci®c data items arerequired. For import/export schemas we do not have theconstraint that only one data source is allowed.

5.2.3 Speci®cation of change propagation

For the speci®cation of change mechanisms, agentsconnected to the component DBSs are introduced asactive DBSs (The ACT-NET Consortium 1996; Widomand Ceri 1996). Figure 10 illustrates this division of laborbetween kernel and agents. The local database manage-ment systems of the component DBSs consider the activeagents as local applications.

export schema import schema import schema

federated schema

CDBS 1 CDBS 2 CDBS 4local schema local schema local schema local schema

CDBS 3

2 31

schema 1component

schema 2component

schema 3component

schema 4component

event change change change

Fig. 8. An example scenario for changing replicas. The model in Fig. 7 is

the meta model for the schemas and their associations in this scenario. The

dashed lines illustrate the data ¯ow

Class: Patient(PID, ...) Class: UsedMaterialrelation

*1Tables: Patient(PID, ...); Invoice(PID, Material)

local schema of the relational database local schema of the object-oriented database

component schema

import schema

export schema

federated schema

export schemaimport schema

component schema

Class: Patient(PID, ...)

Class: Patient(PID, ...) Class: Material*1

relation

Class: Invoice(Material)*1

relationClass: Patient(PID) Class: Patient(PID, ...) Class: UsedMaterial

*1relation

Class: Patient(PID)

Class: Patient(PID, ...) Class: UsedMaterial*1

relationClass: Patient(PID, ...) Class: Invoice(Material)*1

relation

Fig. 9. An example for exporting basic patient data by a relational patient

administration system to an object-oriented research system and for

exporting information about used materials by an object-oriented research

system to the relational patient administration system

200

This approach allows a `separation of concerns' be-tween the federation kernel and the component agents.Separation of concerns is an important principle forsoftware engineering (Ghezzi, Jazayeri, and Mandrioli1991). The responsibility for monitoring and announcingchanges in component DBSs is delegated from the kernelof the federation layer to the agents for the individualcomponent DBSs.

This way, the kernel of the federation layer sees thecomponent DBSs as active DBSs. An active DBS is anextended conventional DBS which has the capability tomonitor prede®ned situations (situations of interest) andto react with de®ned actions (Widom and Ceri 1996).Such re-active behavior is generally expressed by the so-called event-condition-action rules (ECA rules) whichde®ne what to do if a certain situation occurs in theDBS.

The production rule paradigm ± which originated inthe ®eld of Arti®cial Intelligence with expert system rulelanguages ± has been generalized for active DBSs to ECArules. These are of the form:

on eventif conditionthen action

This allows rules to be triggered by events such asdatabase operations, by occurrences of database states,by transitions between states, etc. The triggering mech-anism is the addition to the production rule paradigm ofArti®cial Intelligence. When the triggering event occurs,the condition is evaluated; if the condition is satis®ed, theaction is executed.

ECA rules are a promising principle not only for in-tegrity enforcement in single, centralized DBSs, but alsofor federated DBSs (TuÈ rker and Conrad 1997). The ac-tive rule mechanism can be considered as a communica-tion mechanism between the component DBSs and thefederation layer. Therefore, it is rather straightforward touse ECA rules to specify integrity constraints for replicasand actions which have to be executed in case of potentialintegrity violations.

Let ExportSchemas denote the set of export schemas,ImportSchemas denote the set of import schemas andImExSchemas denote the set of import/export schemas.The change mechanisms for our architecture are speci®edas follows:

8 ES: ExportSchemas [ ImExSchemas :on event (ES)if 9 IS: ImportSchemas [ ImExSchemas j

dependence (ES, IS)then -- change dependent values:8 IS 2 ImportSchemas [ ImExSchemas j

dependence (ES, IS) : change (IS)

Note, however, that this is only a super®cial speci®cationof the general mechanisms. For a detailed speci®cation, itwould be necessary to specify the structure of the schemasand the functions event, dependence and change whichoperate on the schemas. The change function must notraise events on ImExSchemas. A detailed and exhaustiveformal speci®cation is beyond the scope of the presentpaper which focuses on the overall system architectureand the general mechanisms of the associated algorithms.

The execution of rules consists of two phases. In the®rst phase, which is triggered by the occurrence of thecorresponding event, the condition of the rule is evalu-ated. If the evaluation yields true, the second phase,which is the execution of the action part of the rule, isstarted.

Both, condition evaluation and action execution, areperformed in transaction boundaries. These transactionsare called triggered transactions whereas the transactionin which the event occurs is called triggering transaction.Coupling modes between triggering and triggered trans-actions determine when the triggered transactions areexecuted (The ACT-NET Consortium 1996):

Immediate: the triggered transactions are executed asnested sub-transactions (Breitbart, Garcia-Molina,and Silberschatz 1992) directly after the event hasbeen signaled.

Deferred: the triggered transactions are executed at theend of the triggering transaction, but before it com-mits.

Decoupled: the triggered transactions are started asseparate (top-level) transactions.

For our approach, the decoupled mode is most reason-able, as we should not restrict the autonomy ofcomponent DBSs more than necessary.

In HIS, there occur predominantly insertions of newinformation; modi®cations of existing information occurvery seldom. Therefore, a weaker consistency criterion isacceptable: you rarely see outdated information that hasbeen updated somewhere else. You only see new insertedinformation later on. Therefore, it is reasonable to exe-cute the change operations in separate transactions in thisenvironment. Furthermore, immediate and deferredcoupling would restrict the autonomy substantially: thesubsystems would be forced to wait until the triggeredtransactions commit.

However, there are also important cases, usually re-ferred to as `merge' operations that must be dealt with.For example, a trauma patient who is imaged immedi-ately without being registered and identi®ed to an in-formation system. The acquired data is usually linked toa default patient identi®cation. At a later point in timethis information has to be merged with the correct

Fig. 10. Active agents in our architecture. Global applications are not

displayed in this ®gure, but they could be connected to the federation layer

as shown in Fig. 5

201

patient records. In legacy systems with redundant dataentry, improper identi®cation of patients often occurs.This also requires modi®cation operations. Such mergeoperations require tighter synchronization and we con-sider using some kind of (interactive) tools that applyimmediate coupling for these update operations which donot occur as frequently as insertions.

5.2.4 Concerns of rule processing

Rule processing is subject to in®nite loops, that is, rulesmay trigger one another inde®nitely. In general, it is anundecidable problem to determine in advance whetherrules are guaranteed to terminate, although conservativealgorithms have been proposed that warn the ruleprogrammer when looping is possible. Methods forstatically analyzing sets of active database rules todetermine if the rules are guaranteed to terminate, etc.,are discussed in Aiken et al. (1995).

A prevention against in®nite loops in our architectureis the prohibition of cycles in dependencies among importand export schemas via component and federated sche-mas.

A run-time solution to detecting and preventing in®-nite loops is to provide a rule triggering limit (Widomand Ceri 1996). In this case, the number of rules executedduring rule processing is monitored; if the limit isreached, rule processing is terminated. Another mecha-nism is to detect whether the same rule is triggered asecond time with the same parameters.

5.2.5 Detecting changes by the active agents

How do the agents ®nd out about changes to data? Tosolve this problem, a balance between autonomy andintegration must be found. Some approaches are:

± Some DBSs o�er active mechanisms such as triggersto detect and announce changes (Widom and Ceri1996). With the availability of active mechanisms,local applications do not have to be changed: triggersare assigned to monitor changes of exported data.

± If a component DBS does not support such detectingtechniques, polling techniques can be deployed:± The evaluation of system data can be used to detectthe speci®c operations. For instance, the transac-tions log ®le can be monitored (Eliassen andKarlsen 1991).

± Changes can be detected by comparing data snap-shots. Keys can be used to e�ciently compute thechanges, as described in Labio and Garcia-Molina(1996).

± In client/server systems, an interface between appli-cation and server can be used to analyze the clientrequests and announce detected changes (Kudrass,Loew, and Buchmann 1996).

± If the component DBS is an object-oriented DBS, thestored objects can be modi®ed by an overridingtechnique (Schmitt and Saake 1995). Any critical

method will have to be re®ned by adding operationsthat announce changes. This approach restricts theautonomy of local applications, since the local ap-plications are changed.

An additional approach in a hospital setting is thefollowing:

± Wrapping HL7-messages: A HL7 message is a string,which contains mandatory and optional segments (seealso Sect. 2.2.1). These segments consist of several®elds. The syntax of version 2.2 of HL7 messages isde®ned informally in HL7 Group (1994). To gain aninsight into the structure of the HL7 message types,we analyzed the informal description of HL7 fromHL7 Group (1994) and constructed a class diagramfor the data structure of HL7 messages (Hasselbringand KroÈ ber 1997). An extract of this model is dis-played in Fig. 11. This model can be used as the basisfor the component schema of the correspondingcomponent DBS, which could be speci®ed using, e.g.,the object de®nition language of ODMG-93 (Cattell1996) (see also Sect. 6.2). The corresponding agentwould intercept the HL7 messages from the subsystemand announce changes when they are detected. Theforthcoming version 3 of HL7 will be accompaniedwith a structurally object-oriented data model (Risheland Quinn 1996). Version 3 of HL7 is not really ob-ject-oriented in the sense that it does not specify anymethod for these objects. In any case, this will simplifythe task of wrapping HL7-messages. However, giventhe syntactic and semantic ambiguity of the existingHL7 speci®cation and implementations it is di�cult topredict how successful this approach will be in prac-tice, but HL7 interfaces are more readily available inHISs than the other methods mentioned.

5.2.6 Access control

Access control is an important concern in hospitals. Webrie¯y discuss how access control can be integrated intoour architecture.

Fig. 11. An extract of the data structure of version 2.2 of HL7 messages

modeled as a UML class diagram. Filled diamonds indicate part-of

relations (non-shared aggregation). The UML allows specifying shared

aggregation, too (Rational Software Corporation 1997). The correspond-

ing OMT model is presented in Hasselbring and KroÈ ber (1997)

202

Two important features of the schema architectureare how autonomy is preserved and how access control ismanaged (Sheth and Larson 1990). Autonomy is pre-served by dividing the administrative control amongsome component DBS administrators and a federationDBS administrator. The local, component and publicschemas are controlled by the component DBS admin-istrators. The federation DBS administrator de®nes andmanages the federated schemas and the external schemasrelated to the federated schemas. Access control can bemanaged by ®ltering processors associated with publicschemas under control of the component DBS adminis-trators. Note, however, that one person can take on therole of several DBS administrators.

The architecture must permit control of access to databy both category of data and category of user. In somecases, it will be necessary to control access at the indi-vidual datum and user level. In addition to category ofuser and data it appears to be reasonable that users havevarying rights depending on the clinical context, i.e., theirrelationship to the patient and the circumstances of thecase. For example, psychiatric history or HIV status maybe appropriately accessed by a class of users in restrictedcontexts but not in general.

6 A prototype implementation

A prototype system has been developed to evaluate thearchitecture with the associated change algorithms,which have been presented in Sect. 5. The prototypeintegrates a system which controls the results of therapiesin angiopathy (Ullrich, Hasselbring, Jahnke, RoÈ ser, andChristmann 1996) with a system which manages patientdata and supports charging the treatment. The therapycontrol system has been implemented in cooperation ofthe University of Dortmund and the University HospitalWuppertal (Ullrich, Hasselbring, Jahnke, RoÈ ser, andChristmann 1996) with the object-oriented databasesystem O2 (Bancilhon, Delobel, and Kanellakis 1992).The patient data management system has been imple-mented with the relational database system Oracle(Bronzite 1989).

As the infrastructure to overcome distribution andheterogeneity on the operating system level, we use theChorus Cool CORBA implementation (Jacquemot,Jensen, and Carrez 1995). Figure 12 illustrates the layersin the general architecture of the prototype implemen-tation which is based on an Object Request Broker ac-cording to the CORBA architecture (Mowbray andZahavi 1995) (see also Sect. 2.2.2). At the bottom, themeta data of the federation layer (federation graph etc.)are stored in O2 (Bancilhon, Delobel, and Kanellakis1992).

6.1 The CORBA-based communication interfaces

The communication interfaces encapsulate CORBAservices to send and receive operations which restore

the integrity of replicated information when changesoccur in a component DBS (see Fig. 12). The transferreddata objects contain speci®cations of the change opera-tions to be transferred between the federation layer andthe (active) database agents. The dependencies speci®edin the schema architecture determine the destinations forthe operation objects. Figures 13 and 14 illustrate thearchitecture of the communication interface, which usestwo basic mechanisms:

Operation Objects: for each type of operation a concreteclass is de®ned through inheritance from the abstractclass Operation which speci®es a uniform interface forall operation types (see Fig. 13). Each concrete classspeci®es the speci®c structure for the speci®cations ofone kind of change operations to be exchanged viaobject instances of this class. The communication in-terface itself is independent of this speci®c structure.The methods FromSeq and ToSeq (Fig. 13) areneeded to transform C++ structures into CORBAsequences and vice versa. The Clone method is neededto obtain copies of the object (see below).

Operation Handler: to receive operations of a concretetype, it is necessary to provide corresponding opera-tion handlers to process the operation in an appro-

to send and receive operationsencapsulates CORBA services

to send and receive operationsencapsulates CORBA servicescommunication interface

federation graph

operation processing

schemas

stores meta data

Object Request Broker

federation layer kernel

defines dependencies between

database

component database Oracle/O 2

determines what to do withthe operations

O2

communication interfacedatabase agent

operation processing

component and local schema transforms operations between

Fig. 12. The layers in the CORBA-based architecture of our prototype

implementation

Fig. 13. Operations and their handlers in the UML notation. The symbol

`/' at the lower `handled_by' associations indicates their inheritance

relationship to the corresponding upper association

203

priate way (see Fig. 13). On receipt of an operationobject, the communication interface uses copies ofprototype objects for operation/handler pairs, whichare managed by the class Pool (see Fig. 14). Thehandler is responsible for processing the associatedoperation.

This mechanism, which makes the communication inter-face independent of the concrete operation classes, isbased on the design pattern Prototype Factory (Gamma,Helm, Johnson, and Vlissides 1994, pages 117�). For-merly, we used the design pattern Abstract Factory(Gamma, Helm, Johnson, and Vlissides 1994, pages 87�)for this purpose, but with the Abstract Factory patternthe communication interface needs to know the names ofthe concrete classes yielding a less ¯exible design(Hasselbring and Ziesche 1997). Design patterns can beviewed as abstract descriptions of simple frameworksthat facilitate reuse of software architectures (Gamma,Helm, Johnson, and Vlissides 1994). Another designpattern used in Fig. 14 is called Singleton (Gamma,Helm, Johnson, and Vlissides 1994, pages 127�). EachCORBA object (a C++ program) contains exactly oneC++ object instance of the class Receiver, because eachdatabase agent is accessed as a CORBA object.

The classes Sender and Receiver inherit some generalmethods for using the Object Request Broker from theabstract class OrbOp (see Fig. 14). The return values ofthe methods for sending and receiving operations areeither the local object identi®ers of changed objects orerror codes to indicate the failure of a change operation.

It could be possible that the agent for a componentDBS is unable to accept a change operation due to var-ious reasons (out of memory, unavailability of the localdatabase management system, network error, violationof local integrity constraints, etc.). These situations arereported to the federation layer via the return values ofthe corresponding method calls. If an error occurs, thefederation layer keeps the failed operation and, depend-ing on the error type, informs the system administratorand/or manages the resulting inconsistency (Getta andMaciaszek 1995).

6.2 The canonical data model for the federation graph

The canonical data model is the data model for themiddleware layer in Fig. 7. In Saltor et al. (1991), it isshown that functional and object-oriented data modelsare most appropriate as a canonical data model. Theirexpressive power allows covering other data models andeases the mapping. The advantage of object-orienteddata models as canonical data models is due to theextensible nature and support of data abstraction andencapsulation which allow overcoming heterogeneitythrough the provision of abstract data types.

In our project, the object model of the ODMG-93standard (Cattell 1996) for object-oriented databases isused as the basis for the canonical data model. TheODMG-93 standard includes languages for object de®-nition (ODL), object manipulation (OML), and objectquery (OQL). Figure 15 displays an extract of the datamodel for our canonical data model in the UML nota-tion.

To explain Fig. 15: if we remove the classes Variableand Object with their associations from this class dia-gram, we obtain a simpli®ed version of the ODMG-93object model. A Type is either a PointerType, Simple-Type, ComplexType, or CollectionType (specializationthrough inheritance). A PointerType is related to a Typeat which it points (target_type). SimpleTypes are integers,¯oats, characters, or Booleans (atomic values). Com-plexTypes may be compared with records in Pascal: theycontain some Attributes with possibly di�erent Types(value_type). CollectionTypes are sets, bags, lists, or ar-rays where all the elements have the same type (ele-ment_type). Multiple PointerTypes, CollectionTypes andAttributes can be associated to the same abstract Type(speci®ed by the cardinalities at the corresponding asso-ciations).

Now let us take a look at the extensions to theODMG-93 object model in Fig. 15: each Type in aschema is related to proxy objects for Objects (instances)of this Type that are stored in the local databases. Asillustrated in Fig. 16, these proxy objects contain only the

Fig. 14. The general architecture of the communication interface in the

UML notation. The applied design patterns Singleton and Prototype

Factory are indicated

Fig. 15. An extract of the data model for our canonical data model which

is based on ODMG-93 (Cattell 1996)

204

object identi®ers for the local objects. This is necessary,because the federation layer stores local and global objectidenti®ers for replicas and the relations among them(Schmitt and Saake 1995). Figure 16 is a simpli®ed il-lustration of an instance of the UML model in Fig. 15.On insertion of a new data item, the federation layergenerates a new global object identi®er and relates it tothe local object identi®ers of the master copies and thereplicas. Therefore, as one of the extensions to ODMG-93, each object of class Type is related to the corre-sponding instances of class Object. The same_as associ-ations relate local object identi®ers in the componentschemas via the global object identi®er in the federatedschema to each other.

The relations between Variables and Objects inFig. 15 are needed when ComplexTypes are replicated.There is a correspondence between ComplexType/At-tribute and Object/Variable, but this constraint is notspeci®ed in the UML diagram in Fig. 15. Notice that theUML is a semi-formal notation which does not allowspecifying all possible constraints explicitly. The importand export schemas and their associations to the feder-ated and component schemas are not displayed inFigs. 15 and 16. A comprehensive discussion of the fed-eration graph can be found in Project Group FOKIS(1997).

To summarize: the purpose of a canonical datamodel, which is an instance of the UML model inFig. 15, is to specify the relationships among the schemas(intensional overlapping) and the objects (extensionaloverlapping) which are stored in the component DBSs.

A note on concerns of performance with respect to thetransfer of multimedia data: the federation graph onlystores object identi®ers and the relations among them todetermine the destinations of operation objects. The

operation objects may contain large multimedia data tobe transferred. To determine the destinations of this data,it is not necessary to touch the large multimedia com-ponents, only the small keys. As soon as the federationlayer knows the destinations, it can forward the changeoperation with the multimedia data. The processing ofthe schema architecture is independent of those datavalues to be transferred. Another optimization is the useof the Proxy design pattern (Gamma, Helm, Johnson,and Vlissides 1994, p 207� ) for the multimedia datavalues. The proxy objects contain only references (e.g.host and ®le name or access path to a picture archivingsystem) to the large data values which are stored exter-nally to the federation layer. The original multimediadata is only touched when it is actually needed fortransfer. However, it may be necessary to convert theformat of the multimedia values in a heterogeneous en-vironment.

This prototype implementation serves to evaluate thepresented architecture with the associated algorithmsthat restore the integrity of replicated information whenchanges occur. To save space, the present paper empha-sizes the conceptions, thus only a coarse overview of thisimplementation is presented. For a more detailed dis-cussion of using CORBA and ODMG-93 for imple-menting a federated DBS refer to Sander and Hasselbring(1996) and to Project Group FOKIS (1997).

7 Related work

Some standards which are related to our work have beendiscussed in Sect. 2.2. In some related approaches, thetechniques for federated DBSs are being deployed in theapplication domains of HISs (Roantree, Hickey, Crilly,Cardi�, and Murphy 1996) and digital libraries (Schatz,Mischo, Cole, Hardin, Bishop, and Chen 1996). Forinstance, Schatz et al. (1996) propose building digitallibraries as repositories of indexed multiple-source col-lections and federating them by searching the material viamultiple views of a single virtual collection. Roantree etal. (1996) discuss the management of changes to thestructure of federated DBSs. However, these approachesdo not discuss integrity control for replicated informa-tion. Other approaches aim at integrating informationwithin a hospital unit, viz. radiology (Wong and Huang1996), or at integrating the hospital with externalorganizations (Wiederhold, Bilello, Sarathy, and Qian1996). Below we discuss some related work concerningreplicated data in distributed DBSs.

Replicated data is employed in distributed DBSs toenhance data availability and performance: multiplecopies of some data items are maintained, typically onseparate sites, so that the data item can be retrieved evenif some copies of the data item cannot be accessed due tosystem failures (Guerraoui and Schiper 1997). However,this bene®t of data availability is only realized at the costof elaborate algorithms that hide the underlying com-plexity of maintaining multiple copies of a single dataitem. The di�culty lies in keeping the copies consistentwith each other while at the same time maximizing the

O-ID #1Patient

Key #1Patient

Patient Object

O-ID #1 ...

Patient

Patient Table

Key #1 ...

...

Patient

...

Patient

...Patient

component schema component schema

federated schema

is_instance_ofis_instance_of

same_as

sam

e_as

Object

Objectis_instance_of

Object

TypeType

Type

Fig. 16. Types and object instances. Objects of class Type are displayed as

rectangles and objects of class Object are displayed as boxes with rounded

corners. This is a simpli®ed illustration of an instance of the UMLmodel in

Fig. 15

205

data availability and performance. The algorithms whichaddress these problems are called replica control algo-rithms (Bernstein, Hadzilacos, and Goodman 1987).

With failures, however, writing all copies within atransaction can cause inde®nite blocking, which is un-acceptable in practice. Hence the write-all approach canbe modi®ed to write all copies available to the transactioncoordinator. Unavailable replicas receive changes on adeferred basis. The most commonly known protocol ofthis genre is the primary copy protocol. A two-phasedcommit protocol is required to guarantee a consistentview of the replica to obtain 1-copy serializability(Bernstein, Hadzilacos, and Goodman 1987). To someextent, the basic principle of this protocol can be com-pared to our change algorithm with one master copy fordata items, but we do not guarantee a consistent view ofthe replica since the changes are not executed in trans-action boundaries. Also, for distributed DBSs it has beensuggested to replace the 1-copy-serializability with, e.g.,�-serializability to allow asynchronous updates (Pu andLe� 1991). Temporary inconsistencies in replicas may beseen by queries with this asynchronous approach.

The integration of replicated information across au-tonomous subsystems within hospitals is only attainableby weakening the autonomy requirements of componentDBSs. Therefore, a way has to be found for introducingglobal integrity maintenance without restricting localautonomy too much. Our approach preserves a highdegree of local autonomy by applying mechanisms ofactive databases on the global level of integrity mainte-nance through decoupling triggered and triggeringtransactions.

Decoupling of triggered and triggering transaction ofchange operations is reasonable in HISs, because thereinpredominantly insertions of new information occur: yourarely see outdated information that has been updatedsomewhere else, you only see new inserted informationlater on. Therefore, the weaker consistency is acceptablein this environment. Additionally, lazy replication algo-rithms that asynchronously propagate replica changes toother subsystems after the updating transaction commitsare less deadlock prone than eager replication algorithmsthat propagate replica changes before the updatingtransaction commits, because the transactions haveshorter duration (Gray, Helland, O'Neil, and Shasha1996). Figure 17 illustrates the con¯icting goals in data

replication. It is necessary to ®nd compromises betweenthese goals.

8 Conclusions

A distributed HIS is a complex system of systems whichrequires a well designed organization at the softwarearchitecture level. For digital information that is neededin hospitals, it is a major requirement to integrate thereplicas of information about the same real worldphenomenon which are stored in dissimilar and auton-omous subsystems. Therefore, the requirements onintegration of information for electronic medical recordswhich are stored in HISs are rather di�erent to therequirements on electronic versions of traditional li-braries. However, the materials stored in electronicmedical records can be regarded as digital libraries ofpatient-related information (Fox, Akscyn, Furutu, andLeggett 1995).

This paper presents our approach to federated inte-gration of replicated information within hospitals wheretight coupling is emphasized. An architecture which isbased on the reference architecture for federated data-base systems (Sheth and Larson 1990) and adapted to thespeci®c demands on integration of replicated informationis presented. This architecture is the basis for associatedalgorithms that restore the integrity of replicated infor-mation when changes occur. The change algorithms arebased on the schema architecture. This approach keepsthese algorithms simple and the analysis of the depen-dencies within the schema architecture can be used todetect possibly in®nite loops of change propagation ordeadlocks.

The schema architecture is extended to supportchange algorithms with one or multiple master copies fordata items. Multiple master copies for data items shouldbe avoided (Gray, Helland, O'Neil, and Shasha 1996,Stead, Wiederhold, Gardner, Hammond, and Margolies1992), but sometimes legacy systems have to be inte-grated which store the data in their own repositories.However, a federated architecture supports a smoothmigration from legacy systems to modern informationsystems which do not require multiple master copies.

A prototype implementation of the presented soft-ware architecture which uses CORBA as the infrastruc-ture to overcome distribution and heterogeneity on theoperating system level, and ODMG-93 as a basis for thecanonical data model is outlined. The use of designpatterns for structuring the architecture is discussed.

Replication of information is the problem to besolved and not the suggested solution for the problems intodays HISs. We do not suggest replicating as much dataas possible, but to integrate the replicated data acrossautonomous (legacy) systems which are already in use inthe hospital. Here, you cannot avoid the replication ofinformation without re-engineering the local systems.However, there exist also some advantages of a distrib-uted architecture for HISs with data replication:

± E�cient data retrieval by reading local or close copiesof data.

Availability

ConsistencyPerformance

Goals: - few copies Goals: - 1-copy-serializability- asynchronous updates

- synchronous updates- few copies

Goals: - many copies - access to any copy

Fig. 17. The con¯icting goals for data replication

206

± Data availability in the presence of failures of indi-vidual subsystems: the failure of one subsystem in thenetwork does not necessarily take the entire systemdown as long as no interaction with componentswhich are out of order is required.

± Good e�ectiveness through a problem-oriented divi-sion of labor between subsystems.

± High scalability and ¯exibility.± Good price/performance ratio.± Low dependence on a single vendor.

Problems to be solved with distributed heterogeneousarchitectures are:

± Concurrency and security control is more di�cultthan in a centralized system.

± The e�ort for administration may be very costly, be-cause it is necessary to manage several dissimilarsystems.

In contrast to the current state of the art in connectingsubsystems within hospitals through communicationservers, a tightly coupled federated DBS whose data in-tegration is on the basis of schema integration is capableof supporting subsystems to interoperate. Instead of en-abling the subsystems to send messages for informationexchange, the exchange of information is accomplishedthrough updates of replicated data in subsystems by thefederation layer, which knows the dependencies amongreplicas. This approach allows analyzing and optimizingthe data ¯ow within hospitals.

Acknowledgement. The author would like to thank the members of our

project group `FOKIS' Andreas Dinsch, Mario Ellebrecht, Xi Gao,

Sven Gerding, BetuÈ l Ilikli, Djamel Kheldoun, Patrick Koehne, Mischa

Lohweber, Ulf Radmacher, Karl-Heinz Schulte, Dilber Yavuz, and

Peter Ziesche for carrying out the prototype implementation, as well as

Klaus Alfert and Stefan Sander for the cooperation in this project. The

comments on drafts of this paper by Klaus Alfert, Ernst-Erich

Doberkat and the anonymous referees were a valuable source to im-

prove the paper.

References

Aiken, A., J. Hellerstein, J. Widom (1995). Static analysis techniques for

predicting the behavior of active database rules. ACM Transactions

on Database Systems 20(1), 3±41

Bakker, A., W. Hammond, M. Ball (1995). Summary report of obser-

vations, conclusions and recommendation of the IMIA WG 10

Hospital Information Systems Working Group Conference, Dur-

ham, NC, August 1994. International Journal of Bio-Medical

Computing 39(1), 11±15

Ball, M., M. Collen (Eds.) (1992). Aspects of the computer-based pa-

tient record. New York Berlin Heidelberg: Springer-Verlag

Bancilhon, F., C. Delobel, P. Kanellakis (1992). Building an object-

oriented database system: The Story of O2. San Francisco: Morgan

Kaufmann

Bernstein, P., V. Hadzilacos, N. Goodman (1987). Concurrency control

and recovery in database systems. Reading, MA: Addison-Wesley

Bidgood, W., S. Horii (1992). Introduction to the ACR-NEMA

DICOM standard. Radiographics 12, 345±355

Breitbart, Y., H. Garcia-Molina, A. Silberschatz (1992). Overview of

multidatabase transaction management. VLDB Journal 1(2),

181±293

Bright, M., A. Hurson, S. Pakzad (1992). A taxonomy and current is-

sues in multidatabase systems. IEEE Computer 25(3), 50±60

Bronzite, M. (1989). Introduction to Oracle. London: McGraw-Hill

Campbell, K., M. Musen (1992). Representation of clinical data using

SNOMED III and conceptual graphs. In M. Frisse (Ed.), Proc.

Sixteenth Annual Symposium on Computer Applications in Med-

ical Care, Baltimore, MD, pp. 354±358. London: McGraw-Hill

Cattell, R. (Ed.) (1996). The Object Database Standard: ODMG-93,

Release 1.2. San Francisco: Morgan Kaufmann

CEN TC/251 Working Group 1 (1997, January). Healthcare informa-

tion system architecture part 1 (HISA): healthcare middleware

layer. European prestandard, CEN European Committee for

Standardisation. (available from www.imc.exec.nhs.uk:8000/tc251/

wg1)

Date, C. (1995). An introduction to database systems (6th ed.). Read-

ing, MA: Addison-Wesley

Ehlers, C.-T., H. Schillings, P. Pietrzyk (1992). HIS and integration. In

A. Bakker, C.-T. Ehlers, J. Bryant, and W. Hammond (Eds.),

Hospital Information Systems: Scope ± Design ± Architecture,

pp. 49±56. Amsterdam: North-Holland

Eliassen, F., R. Karlsen (1991, December). Interoperability and object

identity. ACM SIGMOD Record 20(4), 25±29

Fowler, M., K. Scott (1997). UML distilled: applying the standard

object modeling language. Object Technology Series. Reading, MA:

Addison-Wesley

Fox, E., R. Akscyn, R. Furutu, J. Leggett (1995). Introduction to the

special issue on digital libraries. Communications of the ACM

38(4), 23±28

Gamma, E., R. Helm, R. Johnson, J. Vlissides (1994). Design patterns

± elements of reusable object-oriented software. Reading: Addison

Wesley

Getta, J., L. Maciaszek (1995). Management of inconsistent informa-

tion in federated systems. In M. Papazoglou (Ed.), Proc. 14th In-

ternational Conference on Object-Oriented and Entity-Relationship

Modeling (OOER'95), Gold Coast, Australia, Lecture Notes in

Computer Science, 1021, pp. 412±423. Berlin Heidelberg New York:

Springer-Verlag

Ghezzi, C., M. Jazayeri, D. Mandrioli (1991). Fundamentals of soft-

ware engineering. Englewood Cli�s, NJ: Prentice Hall

Gray, J., P. Helland, P. O'Neil, D. Shasha (1996). The dangers of repli-

cation and a solution. SIGMODRecord 25(2), 173±182. (Proc. ACM

SIGMOD International Conference on Management of Data)

Guerraoui, R., A. Schiper (1997). Software-based replication for fault

tolerance. IEEE Software 30(4), 68±74

Hammond, W. (1993). Health Level 7: A protocol for the interchange of

healthcare data. In G. D. Moor, C. McDonald, and J. van Goor

(Eds.), Progress in standardization in health care informatics,

pp. 144±148. Amsterdam: IOS Press

Hasselbring, W. (1997a). Extending the schema architecture of feder-

ated database systems for replicating information in hospital in-

formation systems. In S. Conrad, W. Hasselbring, A. Heuer, and

G. Saake (Eds.), Engineering Federated Database Systems

EFDBS'97 (Proc. International CAiSE '97 Workshop), Barcelona,

Spain, Computer Science Preprint 6/1997, University of Magde-

burg, pp. 33±44

Hasselbring, W. (1997b, September). A federated schema-based

middleware architecture for hospital information systems. In Proc.

Conference on Architectural Concepts for Hospital Information

Systems (New Technologies in Hospital Information Systems),

Ulm, Germany. Amsterdam: IOS Press

Hasselbring, W., A. KroÈ ber (1997). Combining OMT with a proto-

typing approach. The Journal of Systems and Software (to appear)

Hasselbring, W., P. Ziesche (1997, September). The use of design pat-

terns in the development of a federated hospital information system

with CORBA. In Proc. `Verteilte Objekte in Organisationen'

(Mobis '97), Bamberg. Rundbrief Informationssystem-Arch-

itekturen. (in German)

207

HL7 Group (1994, December). Health level seven: an application pro-

tocol for electronic data exchange in healthcare environments,

version 2.2. Technical report, Health Level Seven, Inc., Ann

Arbor, MI

Imielinski, T., B. Badrinath (1994). Mobile wireless computing: Chal-

lenges in data management. Communications of the ACM 37(10),

18±28

Inmon, W. (1996). The data warehouse and data mining. Communi-

cations of the ACM 39(11), 49±50

Jacquemot, C., P. S. Jensen, S. Carrez (1995). CHORUS/COOL:

CHORUS object oriented technology. In Object-Based Parallel and

Distributed Computation (OBPDC '95), Lecture Notes in Com-

puter Science, 1107, pp. 187±204. Berlin Heidelberg New York:

Springer-Verlag

Kudrass, T., A. Loew, A. Buchmann (1996, June). Active object-rela-

tional mediators. In Proc. First IFCIS International Conference on

Cooperative Information Systems (CoopIS '96), Brussels, Belgium,

pp. 228±239. Piscataway: IEEE Computer Society Press

Labio, W., H. Garcia-Molina (1996, September). E�cient snapshot

di�erential algorithms for data warehousing. In Proc. 22th Inter-

national Conference on Very Large Data Bases, Bombay, India,

pp. 63±74. San Francisco: Morgan Kaufmann

Lange, M., N. Osada, H.-U. Prokosch, W. Hasselbring (1996, Sep-

tember). An approach to classify and compare communication

servers. In Abstracts of the 41. GMDS-Jahrestagung, Bonn, Ger-

many. (in German)

Lindberg, D., B. Humphreys, A. McGray (1993). The uni®ed medical

language system. Methods of Information in Medicine 32, 281±291

McDonald, C. (1995). News on U.S. health informatics standards.

M.D. Computing 12(3), 180±186

Meyer, B. (1997). Object-oriented Software Construction (second ed.).

Englewood Cli�s, NJ: Prentice Hall

Mowbray, T., R. Zahavi (1995). The essential CORBA: systems inte-

gration using distributed objects. New York: Wiley

OÈ zsu, M. T., P. Valduriez (1991). Distributed database systems: where

are we now? IEEE Computer 24(8), 68±78

Pitoura, E., O. Bukhres, A. Elmagarmid (1995). Object orientation

in multidatabase systems. ACM Computing Surveys 27(2), 141±

195

Project Group FOKIS (1997, August). A federated object-oriented

hospital information system. Project Report, University of

Dortmund, Dept. Computer Science. (in German)

Pu, C., A. Le� (1991). Replica control in distributed systems: an

asynchronous approach. ACM SIGMOD Record 20(2), 377±386

Radeke, E., M. Scholl (1995, March). Functionality for object migra-

tion among distributed, heterogeneous, autonomous database sys-

tems. In Proc. 5th International Workshop on Research Issues in

Data Engineering: Distributed Object Management (RIDE-DOM

'95), Taipei, Taiwan, pp. 58±66. Piscataway: IEEE Computer So-

ciety Press

Rational Software Corporation (1997, January). The Uni®ed Modeling

Language. Documentation Set Version 1.0, Santa Clara, CA.

(available from www.rational.com)

Rishel, W., J. Quinn (1996, March). Software components, the clinical

workstation and healthcare networks: How HL7 is helping you get

there. In Proc. Healthcare Information and Management Systems

Society's Annual Conference, Atlanta, GA

Roantree, M., P. Hickey, A. Crilly, J. Cardi�, J. Murphy (1996).

Metadata modelling for healthcare applications in a federated da-

tabase system. In O. Spaniol, C. Linnho�-Popien, and B. Meyer

(Eds.), Trends in Distributed Systems: CORBA and Beyond, In-

ternational Workshop TreDS '96, Aachen, Germany, Lecture

Notes in Computer Science, 1161, pp. 71±83. Berlin Heidelberg

New York: Springer-Verlag

Rumbaugh, J., B. Michael, P. William, E. Frederick, L. William

(1991). Object-Oriented Modelling and Design. Englewood Cli�s,

NJ: Prentice Hall

Saltor, F., M. Castellanos, M. GarcõÂ a-Solaco (1991). Suitability of data

models as canonical models for federated databases. SIGMOD

Record 20(4), 44±48

Sander, S., W. Hasselbring (1996, December). Realizing a federated

database system based on the standards CORBA and ODMG-93.

In W. Hasselbring (Ed.), Abstracts 2. Workshop ``FoÈ derierte

Datenbanken'', pp. 45±50. Software-Technik Memo Nr. 90, Uni-

versity of Dortmund. (in German)

Schatz, B., W. Mischo, T. Cole, J. Hardin, A. Bishop, and H. Chen

(1996). Federating diverse collections of scienti®c literature. IEEE

Computer 29(5), 28±36

Schmitt, I., G. Saake (1995). Managing Object Identity in Federated

Database Systems. In M. Papazoglou (Ed.), Proc. 14th Interna-

tional Conference on Object-Oriented and Entity-Relationship

Modeling (OOER '95), Gold Coast, Australia, Lecture Notes in

Computer Science, 1021, pp. 400±411. Berlin Heidelberg New York:

Springer-Verlag

Sheth, A., J. Larson (1990). Federated database systems for managing

distributed, heterogeneous, and autonomous databases. ACM

Computing Surveys 22(3), 183±236

Shortli�e, E., L. Perreault, L. Fagan, G. Wiederhold (Eds.) (1990).

Medical informatics: computer applications in health care. Read-

ing, MA: Addison-Wesley

Sokolowski, R. (1997, January). Integration services for clinical data

exchange. OMG/CORBAmed DTF White Paper 97-01-01,

Kurzweil Applied Intelligence. (available as ftp.omg.org/pub/

archives/docs/corbamed/97-01-01.pdf)

Stead, W., G. Wiederhold, R. Gardner, W. Hammond, D. Margolies

(1992). Database systems for computer-based patient records. In

M. Ball and M. Collen (Eds.), Aspects of the computer-based pa-

tient record, pp. 83±98. New York Berlin Heidelberg: Springer-

Verlag

Tanenbaum, A. (1996). Computer Networks (third ed.). Englewood

Cli�s, NJ: Prentice Hall

The ACT-NET Consortium (1996). The active database management

system manifesto: a rulebase of ADBMS features. SIGMOD Re-

cord 25(3), 40±49

Tresch, M., M. Scholl (1994). A classi®cation of multi-database lan-

guages. In Proc. 3rd International Conference on Parallel and

Distributed Information Systems, Austin, TX, pp. 195±202. Pis-

cataway: IEEE Computer Society Press

TuÈ rker, C., S. Conrad (1997, July). Towards Maintaining Integrity of

Federated Databases. In Proc. 3rd International Workshop on

Information Technology (BIWIT'97), Bayonne, France

Ullrich, I., W. Hasselbring, T. Jahnke, A. RoÈ ser, A. Christmann

(1996). An object-oriented system for therapy control in angiopa-

thy. In Abstracts of the 41. GMDS-Jahrestagung, Bonn, Germany.

(in German)

Widom, J., S. Ceri (Eds.) (1996). Active Database Systems ± Triggers

and Rules For Advanced Database Processing. San Francisco:

Morgan Kaufmann

Wiederhold, G., M. Bilello, V. Sarathy, X. Qian (1996, October). A

security mediator for health care information. In Proc. 1996 AMIA

Conference, Washington, DC, pp. 120±124

Wong, S., H. Huang (1996). A hospital integrated framework for

multimodal image base management. IEEE Trans. Systems, Man,

and Cybernetics 26(4), 455±469

Zhuge, Y., H. Garcia-Molina, J. Hammer, J. Widom (1995). View

maintenance in a warehousing environment. SIGMOD Record

24(2), 316±327. (Proc. ACM SIGMOD International Conference

on Management of Data)

208