1 Interoperability for Digital Libraries Problems and Directions

Directions

Andreas PaepckeChen-Chuan K. ChangHector Garcia-MolinaTerry Winograd

Stanford University (paepcke/changcc/hector/winograd@cs.stanford.edu)

Introduction

Interoperability is a central concern whenever digital libraries are con-structed as collections of independently developed components that rely oneach other to accomplish a larger task. The ultimate goal for such a systemis to have components evolve independently, yet to allow all components tocall on each other efficiently and conveniently. For digital libraries to scaleto an international level, they need to be constructed from such interopera-ble pieces. This is the case not only for technical reasons, but also becauseinformation repositories and information processing services for digitallibraries often need to be operated by independent organizations.

Frequently, the terms “heterogeneous” or “federated” systems are used todescribe cooperating systems where individual components are designedor operated autonomously. This is in contrast to the more general term “dis-tributed systems” that also includes collections of components deployed atdifferent sites that are carefully designed to work with each other. Ourfocus here is on heterogeneous or federated systems of informationresources and services and how they can be made to interoperate.Interoperability is one of the most critical problems in the 1990’s andbeyond, as the number of computer systems, information repositories,applications, and users multiply at an explosive rate. It gets even worse assystem design and software production becomes a global activity, wherefor example, the politics of each region may dictate what services a compo-nent may provide, or what data can be exchanged. Interoperability is also,by its very nature, an extremely complex and evolving problem. Althoughresearchers have been struggling with interoperability for over 20 years, it

1

is often not clear what principles or key results have been established.Our goal in this paper is to present a broad introduction to the issues ofinteroperability, suggesting factors that may be used in evaluating interop-erability solutions, and providing an overview of solution classes. Interop-erability has been surveyed before, but mostly in the context of a specificdomain (e.g., database systems, or programming languages). We believethat the advantage of taking a broad “systems” approach is that it lets usidentify common issues and solutions that span domains and applications.However, in this article, we cannot provide a broad overview of the litera-ture, or explore any one issue in depth. To compensate, we have preparedan annotated bibliography [1] which points to in-depth examinations ofmore narrowly focused scope.

In the following section we show that interoperability is not just an issue ofinter-component communication, but that it needs to be considered inmany different functional parts of a system. We introduce an informal set ofcriteria by which interoperability solutions may be classified and evaluated.We follow this by a high-level survey of approaches for accomplishinginteroperability. This survey shows that there is no single “magic bullet,”and that indeed, new approaches have to be used in conjunction with oldertypes of solutions.

The Problem Space

One reason interoperability has been receiving broad attention is that theproblem permeates almost all aspects of digital libraries that are imple-mented as distributed computing systems. In this section we illustrate themany places where interoperability issues enter into the constituent systemfunctions. We also highlight some requirements that frequently arise ininteroperable systems. Careful decisions around these requirements canimpact the cost of solutions significantly. Finally, we informally study theimpact and costs of those solutions to interoperability problems.

Interoperability Issues Permeate Systems

In Figure 1, five large functions of digital libraries are listed along the hori-zontal dimension. The first function (column) refers to the storage, organi-zation, and retrieval of information, the second to its presentation to users;

2

System Functions:DataManagementLong-TermGoalsDataPresentationCommunicationOperationsAnonymous Supplyand Consumption of ServicesNaming,Knowledge InterchangeProtectionDeclarativeTerms and ConditionsModel/Format/Language IndependenceCurrentR&DMediationNetworked Documents,Distributed AnimationCoordinationSecure Comm.,ContractsEnablingTechnologyModelingDistributedDisplayComponentInterconnectRemoteComputationAccessControlFigure 1: Examples of system functions where interoperability issues arise

the third function is concerned with the communication among parts of theoverall system; the fourth covers the initiation and control over a system’sactions, and the fifth provides protection for users, their property, and infor-mation resources.

The rows list respective examples of corresponding enabling technologies,of current research thrusts, and of some long term goals. The purpose ofthis figure is not to provide a complete overview of the space, but to illus-trate at a glance the broad relevance of interoperability.

For example, the modeling cell in the information management column rep-resents basic technologies for organizing information in such a way that itcan be shared with other parts of a system, even if those follow differentinformation structure conventions. Early federated database systems [11],for instance, created global database schemas to help smooth over syntac-tic differences. Translators would convert data field specifications to localconventions at the target components. For example, a global schema for aset of business directory databases might specify that the names of firmsare stored in a field called companyName. A directory of corporate donors tocharitable organizations might locally store this information in a field calledcorporation. Another directory, which lists corporations currently involvedin law suits might call the same field defendant. A client could now issuequeries searching over companyName in all directories at once. This could beused to answer questions like “find the earnings of corporate donors that

3

are currently involved in lawsuits”. Before being submitted to each data-base, the query would be modified to use the correct local field name.If we move to the component interconnection cell of Figure 1, we find a sim-ilar approach in a very different arena. This cell represents the networkingtechnology of inter-component communication. For example, if a collectionis available to one set of patrons through a propriety mainframe connectionprotocol, gateways can translate traffic between the mainframe’s nativeprotocol and the World-Wide Web.

In the remote computation cell (in the operations column) we find this trans-lation approach represented yet again. This column of Figure 1 providesexamples of interoperability for invoking operations in a target component.‘Heterogeneous computing’ is a term sometimes used in this context [12].CORBA and DCOM are both protocols that provide the ability for compo-nents to be written in different languages and for different computing plat-forms. The components remain interoperable in the sense that they caninvoke operations on each other. Appropriate facilities translate among themechanics of invoking an operation in each participating system.

We can take the information presentation column of Figure 1 as an exam-ple to illustrate the differences between the focus on enabling technology,and currently more prevalent research thrusts. Early interoperability for dis-playing information on disparate system components relied on some mini-mal, universal agreement, such as bitmap display technology. Later, thedegree of interoperability was enriched by facilities such as the X Windowsystem. An alternative approach, exemplified by Display Postscript in SUNMicrosystem’s News system, provides a way of describing exactly what isto be rendered, without relying on agreement at the level of a common win-dow system. All receiving components are responsible for finding someway of rendering the descriptions locally.

An increase in focus on this declarative style of display interoperability isexemplified by the SGML/HTML standards. They attempt to communicatesemantic intent by tags indicating that a portion of text is to assume the roleof ‘title’, or of ‘a bulleted list’. It is up to the receiving components to renderthese semantic notions appropriately.

4

Current research thrusts (middle row of Figure 1) are building on basictechnologies, usually attempting to provide richer functionality whileexpanding platform independence. For example, research for the informa-tion presentation function of Figure 1 has begun to leverage the enablingremote computation technology provided by Java. Multivalent documents[8], for instance, are renderings of information in a Java virtual machine.These renderings can include behaviors that dynamically turn the image ofa text document into ASCII, or that convert a single-spaced documentimage to be double-spaced. Other behaviors might include reachingthrough the Internet and requesting another service to summarize the doc-ument’s contents. Interoperability in this example hinges on the commoninfrastructure provided by Java and its standard user interface elements.This infrastructure ensures that these richer documents can still moveamong components of a system.

Similarly, in the operations column of Figure 1, the remote computationfacilities provided by CORBA, DCOM, and mobile code, like Java applets,are raising interoperability issues in the context of coordination amongindependently executing components. Full-scale distributed transactionapproaches with guarantees for continuous information consistency can attimes be too heavy-weight and too limiting. Some systems thereforeattempt to allow heterogeneous components, such as the word processorof remotely collaborating authors of a document, to operate independentlyfor periods of time. The programs then synchronize occasionally, so thatover a long period of time, document consistency is assured (see, forexample, the Bayou system in [1]).

As a long-term goal (see top row of Figure 1), systems would simply oper-ate by allowing heterogeneous components to come online, advertise theircapabilities, and engage in peer-to-peer interactions with other compo-nents. This vision is, of course, very difficult to realize, because it is notclear how to describe arbitrary functionality such that other componentscan inspect the description and ‘decide’ automatically that this functionalityis appropriate for a given task, and what all the parameters are intended toconvey.

5

Similarly, a long-term goal for the protection function is simply to declareterms and conditions for an interaction, and to have the system take care ofthe rest. For example, a document might travel among components withattached instructions stipulating that the document’s contents may be readand passed on to another component, but that it must not be copied.Appropriate watermarking, or even preventative measures would causethese stipulations to be adhered to.

For the information management, information presentation, and communi-cation functions, a major long-term goal is to achieve complete indepen-dence from data formats, document models, and languages. The vision isthat each component would use, for example, its own way to represent doc-uments, but that documents could still be freely exchanged and widely dis-played on different computing platforms, and that maybe even humanlanguage barriers might be overcome. While complete human languagetranslation continues to be an elusive goal, some progress is being made inthe information management function. For example, Reference [10]describes a system in which queries can be issued using keywords fromone human language, but which is able to identify relevant documents writ-ten in another language. Still, much more work is needed before the toprow of Figure 1 describes reality.

As is evident from Figure 1, interoperability may concern information, oper-ations, and protection functions. Beyond that, there are differences ininteroperability requirements that need to be considered when designing adigital library consisting of collaborating components.

Among the requirements for interoperable systems, two will be outlinedhere: The degree to which component heterogeneity needs to be hidden,and the degree to which components must be bridged at a syntactic versusa semantic level.

How Much to Hide Heterogeneity?

Alternative degrees of hiding heterogeneity can be illustrated by examiningtransparency for three aspects of distributed digital libraries: differing levelsof functionality in participating components, heterogeneity among userinterfaces, and the effects of data and functionality distribution on the use

6

of components in the system. We look at each in turn.

Ideally, all components of an interoperable system would be made toappear equally fast, equally rich in functionality, and equally expressive inmodeling data. For example, a digital library of independently maintainedcollections would appear to the user as one big resource whose sucollec-tions all behaved identically. In practice, this is usually not possible.Instead, a series of design choices must be made, depending on howmuch homogeneity is required. For example, if homogeneity of functionalityacross all collections is very highly desired, a designer might decide not tomake any functionality available that may be obtained at only some of theparticipating collections. This will ensure that all collections appear maxi-mally homogeneous in functionality, but this approach also sacrifices func-tionality that would be available if some heterogeneity in the functionality ofthe digital library’s collections were deemed tolerable.

Similarly at the user interface level: If differences in interaction styles aretolerable, it is permissible to display multiple, different user interfaces asusers interact with the various collections. On the other hand, if a commonlook and feel is considered crucial to the success of a system, an interoper-ability solution may need to include a complete user interface thatbypasses the collections’ native interfaces.

Finally, usage requirements may demand that the physical distribution ofdata and operations be transparent. This makes design for interoperabilitymore complex, because it implies that access time differences among thecollections need to be eliminated or minimized. This may involve pre-com-putation, data caching, precise scheduling, or even the artificial slowing ofthe faster collections. On the other hand, if the transparency of distributionis of less importance, appropriate indicators, such as a cursor turning to anhour glass for some operations, may be acceptable. Alternatively in thiscase, a human user may be asked to decide whether an expensive opera-tion is to be performed or not. However, this approach assumes the abilityto predict system behavior, which is frequently not possible.

The degree to which all aspects of an interoperable digital library are tolook homogeneous therefore significantly impacts the complexity of solu-7

tions.

Syntax vs. Semantics

The degree to which component differences are to be bridged at a syntac-tic versus a semantic level is the second range of requirements we con-sider. This difference is frequently stressed when describing recentinteroperability projects. Often, the implication is that semantic interopera-bility is more important or sophisticated than syntactic approaches. In fact,the differences are not always clear-cut.

To a first approximation, a simple example can illustrate the differencebetween syntactic and semantic interoperability: Consider a componentpublishing the fact that anyone may remotely call its functionprint(String:author, String:pubData, Float:price, String:address).Assuming appropriate remote invocation technology, this publication pro-vides syntactic interoperability. Anyone can call this function without caus-ing an invocation error. Semantic interoperability would be improved if thiscomponent would in addition publish the fact that it will print in 600dpi onthe printer in Hall A, that the parameters are supposed to specify a book tobe be paid for in Japanese Yen, and that the printed output will be an orderform as required by standard company procedure.

This kind of simple example is generally used when describing the differ-ence between syntactic and semantic interoperability. In fact, the differenceis actually more complex, in that it recurs at multiple layers. For example,looking at the formula (Forall x (Exists y (Knows y x))) one might saythat the syntax is Lisp-like, but the implied semantics is first-order logic. Onthe other hand, one might say that its being a statement in first-order logicis really just syntactic, and the semantics has to do with what Knows meansin some axiom system. Or one might in turn characterize the whole formalaxiom system as syntactic, and conclude that the real semantics is in itsmapping onto some domain of interest in the world. Two representationsmight therefore be said to be “semantically interoperable” if they can beused with a common inferential system. But are they really interoperable, ifKnows in one system has a different shade of meaning than in the other? Similar complexity arises in programming languages. What most people

8

refer to as the “semantics” of a program, is really the syntax of its execu-tion, with no reference to what the program is about, for instance whether itis playing chess or balancing a bank account.

The difference between syntactic and semantic interoperability is thus notclear-cut. We can say loosely that the more ambitious a system becomes inconsidering semantic interoperability, the more flexibility we have in optionsfor interacting with it, but the more difficult it is to implement.

Measuring Success

One of the biggest problems with interoperability is that solutions are verydifficult to compare. Different approaches operate under differing assump-tions, and design goals frequently conflict with one another. It is thereforeimportant to articulate the potentially relevant goals, and to understandtradeoffs among them.

Given the problem space sketched above, and considering associatedsolutions, we can isolate criteria for evaluating the tradeoffs made by anygiven approach. There are many such criteria, but the following six standout:1.2.3.4.5.

High degree of component autonomyLow cost of infrastructure

Ease of contributing componentsEase of using components

Breadth of task complexity supported by the approach

6.Scalability in the number of components

These are not quantitative measures, but they do provide useful guidelinesfor understanding distributed and interoperable digital libraries. Sometimes,tradeoffs that optimize one criterion can negatively impact another. Forexample, a system that minimizes the cost of infrastructure may then onlybe usable for simple tasks, or may be very difficult to use. We limit the fol-lowing discussion to the first four criteria.

Component Autonomy

The degree of component autonomy (Criterion 1) refers to the amount of

9

compliance to global rules that is required of each participating component.Not considering interactions with other goals, higher autonomy is better,because it provides more local control over implementation and operationof components, and because it makes it easier to include legacy systemsas participating components. At one extreme, complete autonomy wouldmake no assumptions of components complying with any global rules.Components could present arbitrary interfaces, and could insist on anyinteraction protocol or data format they chose. These could be freelychanged without notice. At the other extreme, components participating inthe system might be required to engage in global procedures such astransactions or information store-and-forward, or to organize all their infor-mation by Library of Congress organizational schemes.

Limitations in autonomy may affect many aspects of a component. Theremay be limitations on how a component may schedule its activities: it maybe required to react right away to interrupts, or it may instead be allowed toaccept requests asynchronously and return results via callbacks. Anotherlimitation on autonomy may require a component to make all its capabilitiesavailable at startup time, at a particular address or port, and in a particularform. Less autonomy limitation in this area may instead allow late bindingof functionality. Yet another aspect of autonomy concerns security: Limitedautonomy in this area may require all participating components to guaran-tee certain behaviors, while a higher level of autonomy may instead notmake any a-priori rules, but may curb security transgressions dynamicallyat runtime.

While desirable in principle, high autonomy can lead to solutions that onlyallow interoperation over the lowest common denominator of functionality,or that require very expensive construction of component descriptions ortranslation facilities. This in turn can negatively impact other desirable char-acteristics, such as the ease of using the components.

Practical interoperable systems therefore lie between these extremes. Forexample, the translation scheme of federated databases with global sche-mas provides very high autonomy for participating local DBMSs. In con-trast, consider the use of blackboard architectures for coordinating largetasks. In this scheme, all components of an interoperable system coordi-10

nate their work by posting tasks and results to a centrally accessible loca-tion. This approach would provide less autonomy to the components,because they must all agree to use the blackboard, and to adhere to therespective data exchange formats. On the other hand, the system might beeasy to use and implement.

Cost of Infrastructure and Entry

The cost of a solution is another aspect to consider in any evaluation. Crite-rion 2 refers to the cost of the infrastructure that is needed to support asolution. These costs can be very difficult to assess because they areshared among many users, or even non-users if funds are raised fromtaxes. Examples include the development of widely available ‘free’ soft-ware, such as SGML parsers, and the development and maintenance ofthe Internet. These are costs born by entities beyond the scope of a singleorganization. If the infrastructure costs are local, such as the installation offiberoptic wiring in a building, they are easier to assess. We do not furtherconsider these more obvious costs here.

Criterion 3, in contrast, refers to the incremental cost of enabling interoper-ability when building a new component. This could involve hardware invest-ment necessitated by the approach, or the cost could be in the form ofsoftware complexity required to ensure interoperability.

A good example arises in the coordination area. If the operations of inter-operating components are coordinated by transactions that initially lock allresources needed by a component, then any individual component can beassured that once it is finished and commits its transaction, it will not needto undo what it has done. On the other hand, if coordination is achieved byoptimistic concurrency control where all actions are performed even in theface of possible interoperation conflicts with other components, then allcomponents must be much more sophisticated and ready to undo theiractions.

Obviously, a low cost of entry is highly desirable, but a higher cost of pro-viding new components may well be justified if it provides other engineeringadvantages. In the example above, such an advantage potentially arises inthe second solution: If there are few conflicts, the overall system will run

11

faster, because components do not need to wait for resources as often.Another reason for choosing to accept a higher cost of contributing newcomponents is to make them easier to use.

Ease of Use

A component’s ease of use (Criterion 4) refers both to the complexity ofcreating client components and to the complexity of interacting with thecomponent at runtime. For example, an information service that providedonly a very simple query interface might make the creation of clients easy,but everyday usage might be more complex.

The ease of using existing components in an interoperable system needsto be considered separately from the cost of service component creation(Criterion 3) because the construction of a service component only occursonce and might warrant higher costs, and because it may be desirable toensure that the creators of client components need not be as well trainedas the creators of service components.

For example, consider a remote client/server communication mechanismthat is modeled on Unix pipes: clients and the server produce output bywriting to a ‘standard’ output port. Other components consume this outputby reading from a ‘standard’ input port. This design makes client compo-nents very easy to build, if the interoperation consists of components pro-ducing single data types, such as ASCII encoded words, or a fewpredefined types, which are then processed by another component. TheCommon Gateway Interface (CGI) used in the World-Wide Web is an onlyslightly more involved version of the piping mechanism.

In contrast, the CORBA/DCOM approach requires the programmer toacquire and process a special file that uses a specification language todescribe the interface of the service component at a syntactic level. The cli-ent program must then faithfully adhere to the conventions laid out in thatinterface. For simple tasks, this approach makes it more complicated towrite client components than in the piping solution. On the other hand, ifcomplex data structures and multiple component methods are involved, aCORBA-like approach is much easier to use, because it takes care of pack-aging parameters appropriately for travel over the communication link

12

(parameter marshalling), and it syntactically allows components to beviewed as if they were local objects.

Our examples show that evaluation criteria tend to be interrelated in com-plex ways. Evaluation also depends on the complexity of tasks the systemin question is to be used for. In general, to select particular strategies for agiven scenario, one must weigh the importance of each goal by how welleach strategy meets the goal. It is of course hard to quantify this wholeevaluation process, and one must rely on experience and intuition.

The Solution Space

Over the years, many, very different approaches to achieving interoperabil-ity have been developed. Curiously, as we will see, these solutions arebeginning to blend into each other. Figure 2 shows a layout of the solution

Strong standards( ISO 802, Z39.50, DOS, X, TCP/IP, HTTP)Mobile functionality(Lisp, applets)Families of standards(online payment, OSI)Specification-BasedInteraction(KIF, SETL, PAISLey)External mediation(Wrappers, gateways, global schema translation)Figure 2: Families of interoperability solutions

space. Each point on the circle represents one cluster of approaches. Wewill sketch each cluster in turn.

Strong Standards

One of the oldest approaches to achieving interoperability among hetero-geneous components is to agree on a standard that achieves a limitedamount of homogeneity among them. These standards come about in dif-ferent ways. Standards such as ISO 802 for network connections and theZ39.50 standard for information retrieval were created by committees that

13

convened because a large and diverse enough community agreed that astandard was needed. Sometimes one product gains enough market sharethat it becomes a de facto standard by virtue of its broad deployment, ashappened with DOS, and later Windows in the area of desktop operatingsystems. Other times, government organizations can help a standard gainwide acceptance, as happened with USMARC, one important method fororganizing metainformation about books.

Occasionally, a de facto standard will arise spontaneously because a smallgroup of people has developed an approach that is compelling, easy todeploy, and that fills an important need at the right time. The initial versionsof the document markup language HTML, the World-Wide Web’s communi-cation protocol HTTP, and MIME are examples.

The success or failure of standards, and the design philosophies underly-ing standardization efforts are very often determined more by social andbusiness decisions than by technical merits. Sometimes companies mayresist an official standardization process, because they believe that theyare strong enough to establish a de facto standard earlier than an officialstandard would evolve. This gives them a lead over competitors, becauseonce the de facto standard is then ratified and elevated to official status,their products and technologies have the advantage of deep market pene-tration. A careful exploration of these connections is important for under-standing the impact of standards on interoperability, but it is beyond thescope of this paper. Reference [6] provides a broader treatment of theseissues.

If an appropriate standard can be created and is widely adhered to, it pro-vides a powerful interoperability tool. For example, a well-designed, strongstandard will make it worthwhile for vendors or free-lance programmers tocreate easy-to-use modules that implement the standard. When such mod-ules are widely available, the ease of contributing new services that use thestandard as a foundation (Criterion 3) is enhanced. A reliable standard alsohelps encourage infrastructure investment, even when infrastructure costsare high.

One drawback of standards is that they are difficult to agree on, and there-14

fore often end up being complex combinations of features that reflect theinterests of many disparate parties. A more fundamental reason is that astandard by its very nature infringes on site autonomy (Criterion 1). With asingle standard, component providers are no longer free to introduce localoptimizations, or to satisfy the preferences of different customer groups.One solution is to include optional portions to the standard. This canquickly lead to increased complexity, and it bears the danger of diluting thestandard. An alternative approach to increasing site autonomy withoutcompletely losing the benefit of standards is to have more than one stan-dard.

Families of Standards

In this approach, components have the choice of implementing one ormore of several standards. When two components begin to communicate,an initial automatic or human-mediated negotiation process determineswhich standards they share. Mirroring everyday life, this approach isincreasingly encountered in the area of online payment. Any given vendoror customer may implement payment by a variety of payment schemes,such as First Virtual, DigiCash, or one of several credit cards.

The ISO standard for interconnecting systems (OSI) created an interopera-bility framework based on the family of standards approach. The OSI con-ceptually partitions interconnection tasks into seven layers. Each layercontains a family of standards concerned with a given set of interoperabilityissues in the area of interconnection. For example, the bottom layer con-tains a set of standards concerned with the physical interconnection ofcomponents, such as transmission speeds, or voltage levels. One of thelayers above is concerned with packaging information for transport, suchas partitioning large bodies of data into packets. Layers near the top areconcerned with issues such as establishing sessions. Each layer is to func-tion without knowledge of choices made at the layers below. For example,the session layer is intended to operate without regards to whether the rel-evant lower layer is using token ring or CSMA access facilities. Interactionnegotiations take place only among corresponding layers in communicatingcomponents.

The family of standards approach does somewhat alleviate the problem of

15

autonomy infringement, while maintaining the benefits of standards. But itbreaks down when standards are not available, or are not adhered to fortechnical or business reasons. This can happen, for instance, when appli-cations or infrastructure are still poorly developed, and multiple organiza-tions are attempting to gain market dominance. For these cases, aninfrastructure explicitly constructed to provide interoperability among highlyautonomous components can be put in place.

External Mediation

The only way to provide very high levels of autonomy for components is tolocate interoperability machinery outside of the participating local systems.This machinery mediates between the components. One primary functionof such mediation machinery is the translation of data formats and interac-tion modes. For example, in the area of interconnection, network gatewaysplay such a mediation role. Similarly, facilities that map global schemas tolocal ones are examples of this approach.

However, translation in the sense of simple mapping, is not always suffi-cient for full interoperability. Sometimes, components completely lack cer-tain data types or operations, and can therefore not interoperate with someclients without further work. For example, consider two collections of docu-ments being provided by different digital library search services. The firstprovides a ranking feature that sorts search results by estimated relevance,the second does not. In order for a client to interact with both collectionsequally conveniently, a mediation facility could provide a separate rankingfacility. It would be used to augment the less sophisticated collection’s func-tionality. When dealing with the first collection, clients can simply call thesearch operation. Instead of interacting with the second componentdirectly, clients would always interact with the mediation facility which wouldrank the results. Such mediation facilities are sometimes called wrappers,or proxies. An extensive example is described in [7], where proxy objectsplay a major mediation role in a digital library environment. Another exam-ple is the context mediator component of [9], which is a module that isplaced between information clients and servers, and that converts dataattributes of queries, and the corresponding result values.

An even more severe mismatch occurs when components differ in their

16

interaction models. For example, if some components expect to establishlong-lasting interaction sessions, while others are stateless, then mediationtechnology may need to simulate session-based interactions for the state-less components. Connecting HTTP and Z39.50 based components is anexample of such mismatches.

Mediation approaches to interoperability are particularly strong along thecriteria of autonomy, ease of use, and scalability. They require no compli-ance from the components, and to the extent that mediation can be suc-cessful, clients have the illusion of a highly integrated system. All mediationfacilities can be replicated, so scalability tends not to be a problem.The drawbacks of this approach lie mostly in the area of ease of contribut-ing a new component: whenever a new component is added, a correspond-ing mediation facility (e.g., wrapper, schema augmentor, etc.) needs to bebuilt as well. Notice that for cases where family of standards solutions arein use by some of the components, this drawback is much less severe.Mediation technology then reaps the benefit of standardization just like anyregular client would. For example, in an external mediation system whichprovides interoperability for highly autonomous search components, a sin-gle mediation facility will cover all of the Z39.50 sources at once. Differentfacilities still need to be constructed for the non-Z39.50 sources.

More generally, if mediation technologies are used to make n kinds of com-ponents interoperate with m other kinds, one needs to construct n x mmediation facilities. One way out of this complexity is to design the media-tion facility such that it uses one common standard (set of operations, datastructures, etc.) internally. Then mediation is provided between that internalstandard and all the components that are to interoperate. For example, amediation facility translating among n metadata attribute sets might firstattempt to translate to USMARC, and then translate from there to thedesired target set. Some systems apply the family of standards approach inthis context: they translate to one of a small number of intermediate stan-dards, and from there to the final target. This is appropriate if translation toone single common standard is too lossy, because no single standard issufficiently similar to all components.

17

An important tool for mediation technology is the use of metadata todescribe and translate among components. Metadata is information thatdescribes the elements that the mediation technology deals with, such ascomponents, or data items to be passed among these components. Exam-ples are the global schemas of some federated databases, routing tablesfor gateways, catalogs for document repositories, the ‘semantic values’ of[9], or tags in document formats like SGML. Due to a current increase inemphasis on component autonomy and consequent interest in interopera-bility solutions that are strong in this criterion, representation and acquisi-tion of metadata are being widely explored [5].

Metadata plays an even more important role for another approach tointeroperability which attempts to avoid the additional infrastructurerequired by mediation approaches.

Specification-Based Interaction

When interoperability is achieved by thoroughly describing the semanticsand structure of all data and operations, we speak of a specification-basedapproach. The vision of these approaches is to allow the use of compo-nents without prior arrangement, and without the help of mediators. Thegoal is to describe each component’s requirements, assumptions, and ser-vices such that components can interact with each other after inspecting,and reasoning about each others’ specifications. Various enabling technol-ogies have been developed towards this end goal. For example, an AgentCommunication Language (ACL), a knowledge sharing facility for softwareagents, has included a ‘Knowledge Interchange Format’ (KIF) which is anextension of first order predicate calculus. Also included is a ‘KnowledgeQuery and Manipulation Language’ (KQML) for passing constraints andinstructions among agents [3]. This approach assumes that all componentsuse the same knowledge exchange facilities, although the use of differentontologies to cover varying application domains is anticipated.

The software reuse community also has been interested in methods fordescribing component functionality succinctly, and as completely as possi-ble. Very High-Level Languages (VHLLs), such as SETL and PAISLey(summarized in [4]), attempt to describe the semantics of a component’sfunctionality in purely declarative form. That is, the procedural means by

18

which the functionality is achieved is not the subject of VHLL specifications.The goal in the context of software reuse is to describe component func-tionality so that the best component can be selected for each job. Thesame descriptions could also be used to further interoperability in the tradi-tion of specification-based approaches.

Specification-based solutions rate high in autonomy, because of their strictseparation of functionality/data description from their implementation. Thegeneral lack of non-replicable centralized facilities ensures good scalability.The approaches suffer most from the complexity, and sometimes impossi-bility, of completely describing components. This drawback makes themrank low in the ease of component contribution criterion.

Mobile Functionality

At least beginning with the introduction of Lisp, which made programs anddata share the same representation, the movement of functionality imple-mentation has been considered from time to time. General Magic’s MagicCap mobile agent system is one example. Its system had software agentstravel through the network to the sites where they could get access to theservices they needed. The agents could move even after they had startedto execute code. They would then report back to their origin with the resultsof their work.

More recently, Java applet facilities have enabled approaches that usemobile functionality to deliver new capabilities to client components at runt-ime, rather than relying on service components to provide functionalityremotely, or making all components fully functional from the outset. Interop-erability is an important application of mobility: the functionality delivered toa component could be the ability to communicate successfully with anothercomponent. Instead of complex component descriptions, third-party media-tion, or the use of standardization, this approach accomplishes interopera-bility by exchanging code that ‘does the right thing’ to communicatesuccessfully among components. Of course, it is still true that one interfaceof the applet must be well-known, or hand-adapted. For example, a newkind of search engine might supply clients with an applet that allowssophisticated interactions with that search engine. This makes the search

19

engine component very autonomous in that its interface can be arbitrary, aslong as it supports the request for the applet. On the other hand, the clientstill needs to know how to communicate with the applet once it arrives.Today, this problem is solved by the fact that most Java applets interfacedirectly to the user, and the user interface standards that are part of Javaand Java-enabled browsers are wide-spread. In that sense, Java reliesheavily on a standards approach. If applets were used also to implementmobile functionality that is invoked by programs at the client side, then theclient-side interaction with the applet would be subject to the same interop-erability issues as the original client/service component interaction.An example of mobile functionality used in the service of interoperabilitycan be found in [2] where a Java applet is used to deliver a small CORBA-based distributed digital library interface. After the applet is received, itssender and the receiving component can communicate via remote methodcalls. This again solves some of the client/applet interoperability problemthrough a standards approach, namely CORBA, except that the standardsimplementation itself is delivered through mobile functionality.

Mobile functionality scores lower in the autonomy criterion than some ofthe other solutions, because all the components must share the same exe-cution environment (e.g., the Java runtime). On the other hand, contributinga new component is easier in this approach than, for example, in the speci-fication-based approach, because attaining interoperability through mobilefunctionality involves the creation of concrete programs, rather than asophisticated, often mathematical, abstraction of functionality. Ease of usetends to be good, except that the client component bears all the risk ofimporting another component’s programs. Until proper security safeguardsare worked out, this will continue to represent a significant cost.

If we think of incompatible components as discontinuities within an overallsystem, then mobile functionality is a technique for smoothing these dis-continuities dynamically, whenever the need arises. Note that in this sense,a system based on standards is perfectly smooth at all times: All compo-nents can interoperate from the outset. Observed over time, a systemwhose interoperability is implemented through mobile functionality is there-fore equivalent to an interoperable system based on standards. This is why

20

the solutions in Figure 2 are arranged in a circle.

However, implementing all of a system’s interoperability through mobilefunctionality is expensive in terms of latency and bandwidth consumption,because in the absence of long-term client-side caching, the same codeneeds to travel across the network again and again (in addition to anyrelated data). As mentioned, mobile functionality is also expensive in termsof risk management, because authenticity and safety of code needs to bechecked wherever the functionality travels. Consequently, in the case ofJava, interoperability efforts are now beginning to move through the circleof Figure 2 again. For example, facilities delivered frequently have beenmigrating into World-Wide Web browsers as standard components. Oneexample is the recent addition of Java-based CORBA facilities intoNetscape browsers. Of course, as soon as functionality is assumed bycomponent providers to be resident at all client components, interoperabil-ity is standards-based. Thus the natural movement of interoperability solu-tions along the circle of Figure 2. In the future, we could imagine otherdevelopments that combine multiple solution families of Figure 2.

Conclusion

Interoperability is gaining in importance as the Internet brings together dig-ital libraries of different types that are run by separate organizations in dif-ferent countries. At the same time, the increasing power of desktopcomputers, the increasing bandwidth of networks, and the popularity ofmobile code is changing the interoperability landscape. This results in anincreasing urgency for solving the many problems which remain in the wayof true interoperability on a national, and international level.

In this paper we have provided an overview of the interoperability spaceand its solutions. Our discussion has been necessarily informal becauseinteroperability is a complex topic for which no good metrics exist. Never-theless, we hope to have given the reader a feel for how interoperabilityissues across different domains are interrelated, for the spectrum of solu-tions, and for the primary criteria in comparing them.

The following references are a small selection of past work in this area. A

21

more comprehensive bibliography is available at [1].

References

[1]An Annotated Bibliography of Interoperability Literature. Stanford Uni-versity. http://www-diglib.stanford.edu/diglib/pub/interopbib.html.[2]Steve Cousins. Reification and Affordances in a User Interface for

Interacting with Heterogeneous Distributed Applications. PhD thesis, Stanford University, 1997.

[3]Michael R. Genesereth and Steven P. Ketchpel. Software Agent. Com-munications of the ACM, 37(7), July, 1994.

[4]Charles W. Krueger. Software Reuse. ACM Computing Surveys,

24(2):131–183, June, 1992.

[5]Carl Lagoze, Clifford A. Lynch, and Ron Daniel, Jr. The Warwick

Framework: A Container Architecture for Aggregating Sets of Meta-data. Number TR96-1593. Cornell University, June, 1996.

[6]T.W. Olle. Impact of Standardization Work on the Future of Information

Technology. In Nobuyoshi Terashima and Edward Altman, editors, Advanced IT Tools: IFIP World Conference on IT Tools, pp. 97–105. Chapman & Hall, September, 1996.

[7]Andreas Paepcke, Steve B. Cousins, Héctor García-Molina, Scott W.

Hassan, Steven K. Ketchpel, Martin Röscheisen, and Terry Winograd. Towards Interoperability in Digital Libraries: Overview and Selected Highlights of the Stanford Digital Library Project. IEEE Computer Mag-azine, May, 1996.

[8]Thomas A. Phelps and Robert Wilensky. Toward Active, Extensible,

Networked Documents: Multivalent Architecture and Applications. In Proceedings of DL'96, 1996.

[9]Edward Sciore, Michael Siegel, and Arnon Rosenthal. Using Semantic

Values to Facilitate Interoperability Among Heterogeneous Information Systems. Transactions on Database Systems, 19(2):254–290, June, 1994.

[10]Paraic Sheridan and Jean Paul Ballerini. Experiments in Multilingual

Information Retrieval Using the SPIDER system. In Proceedings of the Nineteenth Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 1996.

[11]Amit P. Sheth and James A. Larson. Federated Database Systems for

22

Managing Distributed, Heterogeneous, and Autonomous Databases. ACM Computing Surveys, 22(3):183–236, September, 1990.

[12]Howard Jay Siegel, Henry G. Dietz, and John K. Antonio. Software

Support for Heterogeneous Computing. ACM Computing Surveys, 28(1):237–239, March, 1996.

23