ABSTRACT

The Pegasus project at Hewlett-Packard Laboratories is extending the Iris prototype OODBMS and its language OSQL to support integration of multiple heterogeneous data sources.

Heterogeneity of data models is managed by mapping to a common Pegasus object model, an extension of the Iris model. The power of the object model is then applied to reconciling schema and data heterogeneity within a uniform model.

Each foreign data source has an image as a Pegasus database. The richness and extensibility of the object model facilitate mappings from other data models to the Pegasus model. Mapping capabilities for specific target models will be available as modular extensions of Pegasus and HOSQL.

A Pegasus user perceives the data as a single database, incorporating the data and schemas of attached databases as extensions of the data and schema of the database to which the user is connected. Database boundaries are transparent in this view whenever possible, but they are also visible when needed or desired through appropriate naming conventions.

1 INTRODUCTION

1.1 Objectives

Globalization of economies has made information a more valuable strategic asset than ever before. At the same time, increasingly decentralized and multi-vendor computing environments have made it more difficult to gain efficient access to the data.

In the workplace a decade from now, it is expected that most data will be in databases and there will be many databases around. For instance, a manager will usually have a database of employees who report to him. Each employee will have his or her own personal database. The company will also have employee databases, but their contents will not always coincide with the personal ones. A lab will have a database dealing with its projects and group life insurances. Departments will have databases concerning their suppliers, clients, hardware and software they produce, buy or sell. Employees' e-mail, personal documents, reference materials, schedules, pieces of work under progress, etc. will reside in databases. Many of the current productivity tools will become database applications. There will be many multimedia applications involving voice, image and text. Management and presentation of heterogeneous data residing in heterogeneous databases with local autonomy will be key concerns in such environments.

The Database Technology Department at Hewlett-Packard Laboratories is developing a heterogeneous multidatabase management system called Pegasus to support an open information environment which provides the interoperability required by diverse applications in the 1990s.

Pegasus responds to the need for effective access and management of shared data used by a wide range of applications. Pegasus will provide facilities for multidatabase applications to access and manipulate multiple autonomous heterogeneous distributed object-oriented, relational and other information systems through a uniform interface. The system is intended to interoperate with existing object management systems. Pegasus is not just a front-end to multiple databases but has complete data management capabilities.

Pegasus deals with the problem of heterogeneous database models and data languages by defining a common object data model and data language. The data definition and data manipulation language of Pegasus, called HOSQL (Heterogeneous Object SQL), is a functional language that provides non-procedural statements to manipulate multiple databases. HOSQL allows for transparent and explicit access to multiple heterogeneous databases in a single declarative statement.

The objectives of Pegasus are:

• Access Transparency - Provide a single entry point with location-transparent access to information stored in multiple heterogeneous geographically distributed information systems.
• Schema Integration - Provide a semantically rich integrated view of related information in different databases.
• Data Model and Language Independence - Provide users with a common model and language. Additionally, allow them to access information stored in different systems with their desired data model and language.
• Representation Homogeneity - Resolve conflicts in naming, structures, and data domain.
• Cooperative Autonomy - Promote cooperative information sharing while preserving site autonomy of participating information systems. Existing databases do not have to be modified to participate in a Pegasus multidatabase system.
• Efficient Information Access - Optimize multiple-database queries.
• Update Consistency - Support global consistency of local changes in the presence of data replication and integrity constraints.
• Application Compatibility - Existing applications should run without modifications.
• Localized Cost - There should be no adverse effect on participating information systems. That is, the performance and autonomy of the participating databases will not be compromised and system overhead for single-DBMS queries will be minimized.

1.2 Related Work

There are a number of heterogeneous database projects and systems that have been described in the literature. [L4] is a survey paper on the subject. In the following we briefly discuss those systems which have interesting differences or similarities with Pegasus.

Multibase [Sm,LR,DH] represents an approach to access multiple existing heterogeneous databases through a single global schema using a high level query language. Multibase uses the concepts of type generalization coupled with an extensive view definition facility. The Multibase query processor decomposes a global query into subqueries against the local schemas. A local database interface translates queries received from the query processor into queries expressed in the local DML. The query language of Multibase is DAPLEX [S2], which provides certain procedural constructs like iteration. The data models of both Pegasus and Multibase are based on the functional paradigm. However, Pegasus does not require a global integrated schema and unlike multibase it is a complete DBMS. Pegasus users can create Pegasus databases without a need for an underlying foreign DBMS.

The Amoco Distributed Database System (ADDS) [BO] uses an extended relational data model to integrate relational, network and hierarchical databases. Like Pegasus, an equivalent description of the local databases is generated in terms of the ADDS data model. ADDS suggests that an extended relational algebra (with joins, natural joins, outer joins, intersection, and selects), rather than the functional approach taken in Multibase, is all that is needed to implement a composite global schema.

Mermaid [Te] started as a research project at UNISYS corporation and is marketed by System Development Corporation. Mermaid allows the user to manipulate the data stored under various relational DBMSs running on different machines using SQL and a common language called ARIEL. The SQL or ARIEL queries get translated into a distributed intermediate language (DIL). A distributor process optimizes DIL and sends subqueries to the underlying DBMSs. There is a driver process at the local site for each DBMS. The driver translates DIL subqueries to the local DBMS query language. All information about schemas, databases, users, host computers and the network is contained in a data dictionary/directory (DD/D). Mermaid provides data translation from local to global representation and vice-versa. Pegasus has a more powerful multidatabase language and it does not require a global schema.

DATAPLEX is a heterogeneous distributed database management system developed at GM Research Labs [Ch]. Like most of the other systems, the data definitions of all participating databases are transformed to an equivalent relational data definition. One of the contributions of this project is the mapping of non-relational (e.g. IMS) data definitions to relational schemas, and translation of relational subqueries to equivalent non-relational queries.

2 AN OVERVIEW OF PEGASUS

Figure 1 shows the major functional layers of the Pegasus system. Intelligent Information Access (IIA) provides such services as information mining, schema exploration, and free-form queries. Cooperative Information Management (CIM) deals with schema integration, query processing, and transaction management. Foreign Data Access (FDA) manages schema mapping, query and command translation, network communications, foreign system invocation, and data conversion and routing.

\begin{figure}[htbp] \vspace*{7in} \vspace*{6in} \caption{Functional layers of Pegasus.\label{pegsys}} \end{figure}

Figure 1. Functional layers of Pegasus.

2.1 Intelligent Information Access

2.2 Cooperative Information Management

CIM is responsible for processing HOSQL statements and for coordinating multidatabase transactions. It handles registration of foreign systems and schema mapping and integration (e.g., supertype creation, object equivalence, and identifier management).

User requests are submitted to RM (Request Manager) through various interfaces. RM parses the requests and routes them to the appropriate operational managers which are SM (Schema Manager), QM (Query Manager), and TM (Transaction Manager).

SM implements data definition operations, catalog management, and schema integration services. All information about the mapping of schemas defined in a FS (Foreign System) will be kept in the catalog to be used for query translation and processing, and transaction management. Additional information, e.g., statistical data, are collected by SM.

QM generates efficient execution plans for queries and coordinates the execution of queries and data manipulations. Query processing is described in section 5.

TM manages all transaction-related facilities. As the new computing environments encompassing heterogeneous and autonomous information systems begin to emerge, it becomes increasingly clear that the limitations of the traditional transaction concept begin to outweigh its advantages. The main source of difficulty in applying the traditional transaction management techniques in these new environments is the requirement of local autonomy for the individual FSs which participate in the transactions.

In conventional distributed DBMSs, the execution coordinator communicates with the component databases to enforce data integrity through the well-known two-phase locking and two-phase commit protocols. This is possible because all the component databases which participate in the transaction provide the same transaction management facilities. In a heterogeneous environment, not all FSs will have the same transaction management facilities. Therefore, Pegasus is exploring new transaction management facilities which provide more flexibility[L5].

2.3 Foreign Data Access

Access to foreign systems is implemented via Mapper and Translator modules and P-shells. FDA allows the rest of the Pegasus system to be independent of specific syntax, semantics, and implementations of FSs. FDA is modular, and can easily be extended to support new kinds of FSs by providing new modules.

One Mapper and Translator module is provided for each kind of FS that is supported by Pegasus. A Mapper supports mapping a foreign schema into a Pegasus schema. Mappers for OSQL (the Iris query language) and HP AllBase SQL have been developed [AR]. A translator translates an HOSQL statement into a request to an FS.

To respect the autonomy of FSs, the P-shell is designed to be a stub to perform those functions which cannot be performed efficiently by FSs. The intent is for the Pegasus site to bear the overhead of integration, rather than imposing it on the FS. A P-shell provides such services as FS invocation, network communication, data format conversion, data blocking/deblocking, and data routing to Pegasus.

3 THE PEGASUS DATA MODEL

Pegasus provides an object-oriented model which serves as a framework for uniform interoperation of multiple data sources with different data management systems. The Pegasus model, based on the Iris object-oriented model [F2], contains three basic constructs: types, functions and objects.

A type has a unique name and represents a collection of objects that share common characteristics. Types are organized in a directed acyclic graph that supports generalization and specialization and provides multiple inheritance. A type may be declared to be a subtype of other types. A function defined on a given type is also defined on all its subtypes except on those subtypes which are explicitly prohibited by the supertype from inheriting the function. Objects that are instances of a type are also instances of its supertypes. A simplified version of the Pegasus system type hierarchy is shown in Figure 2, where the subtype relationship is shown by an arrow from a supertype to a subtype. User objects belong to user-defined types, either locally created or obtained by attaching other databases.

\begin{figure}[htbp] \begin{figure}[ht] \vspace*{7in} \vspace*{4.5in} \caption{Simplified type hierarchy.\label{types}} \end{figure}

Figure 2. Simplified type hierarchy.

Objects are instances of types and are uniquely identified by their object identifiers. Some objects such as integers are self-identifying. These objects are instances of literal type shown in Figure 2. Objects may gain and lose types dynamically. For example, an object representing a given person may be created as an instance of the Student type. Later it may lose the Student type and acquire the type Employee.

3.1 Pegasus Data Language

Pegasus provides a unifying data definition and data manipulation language called HOSQL (Heterogeneous Object SQL), a superset of OSQL [F2]. HOSQL is a functional object-oriented language that incorporates non-procedural statements to manipulate multiple heterogeneous databases. HOSQL provides statements for creating types, functions, and objects in both Pegasus and underlying databases. Specifications of types and functions can also be imported from underlying databases into a Pegasus imported database, which can then be integrated into global schemas and application views.

Databases, types, functions, and instances are defined by statements of the form:

CREATE ObjectSpecification AS ObjectImplementation;

ObjectSpecification is DATABASE or TYPE followed by a user-defined name, or FUNCTION followed by a function name and the specification of its inputs and outputs. The AS ObjectImplementation clause is optional. Figure 3 shows several examples of CREATE statements.

REGISTER System-1 ...;
REGISTER DATA-SOURCE Teachers ON System-1...;
REGISTER DATA-SOURCE Students ON System-1...;
CREATE IMPORTED DATABASE TeacherDB FROM Teachers...;
CONNECT TeacherDB;
CREATE TYPE Teacher AS RDBMS1(Table=TchrTable, OID=TchrNum)

PROPERTIES

(Name AS RDBMS1(Column=TchrTable.Name),

...

 );
DISCONNECT;
CREATE IMPORTED DATABASE StudentDB FROM Students...;
CONNECT StudentDB;
CREATE TYPE Student AS RDBMS1(Table=StudTable, OID=StudNum)

 PROPERTIES

 (Name AS RDBMS1(Column=StudTable.Name),

 ...

 );
DISCONNECT;
CREATE DATABASE PeopleDB ...;
CONNECT PeopleDB;
ATTACH TeacherDB ALIAS TDB;
ATTACH StudentDB ALIAS SDB;
CREATE TYPE Person SUPERTYPE OF t Teacher, s Student,

IDENTITY(TDB.SocSecNum(t) = SDB.SocSecNum(s));
CREATE FUNCTION Name(Person) -> String;
CREATE FUNCTION Activities(Person p) -> String time, String cname, String role 

AS SELECT time, Name(c), role

FOR EACH String time, Course c, String role

WHERE (p=TDB.TeacherOf(c) AND time=TDB.Start(c) AND role="teacher")

OR (c IN SDB.Courses(p) AND time=SDB.Begin(c) AND role="student");
SELECT Activities(:john);
<1:15, Chemistry, teacher>

<2:30, Algebra, student>

<5:00, Psychology, student>

Figure 3. A data integration example.

HOSQL is a uniform functional/object-oriented query and data manipulation language. Variables, which are references to objects in the result or argument of a function, can be used in queries and update statements. Variables range over the domains of types they refer to. An object can be retrieved into a variable which can then be used to refer to the object.

An HOSQL query can be expressed using the following syntax:

SELECT list of variables or functions
FOR EACH list of all variables and their types
WHERE Predicate expression

The SELECT clause contains a list of variables or functions. The FOR EACH clause contains quantification and the types of all variables being used in the select and where clauses. The WHERE clause contains a predicate expression that may involve nested functions (possibly nested), variables, constants or nested subqueries.

Update is done by functional assignment, e.g.,

Age(:john) := 30.

4 MAPPING

Mapping generates a Pegasus schema for a foreign data source in order to

• Give the data source the appearance of a Pegasus database.
• Define the data and operations available from the data source.

Mapping capabilities are provided in modular fashion, with a separate module for each target data model, e.g., relational models, Codasyl models, IMS, hypertext, spreadsheets, etc. Such modules could be developed, sold, and installed independently.

Each module provides:

• A mechanism for specifying mappings between the data model of the data source and the data model of Pegasus.
• A mechanism for translating requests expressed in Pegasus DDL/DML into the language of the data system.

Mapping mechanisms support variants of the AS clause of the CREATE statements described in section 3.1. For example, after installing a module for a relational DBMS (RDBMS1), Pegasus will understand the following:

CREATE TYPE Employee AS RDBMS1(Table=Emp, OID=EmpNo)
PROPERTIES
(EmpNo Integer AS RDBMS1(Column=Emp.Empnum),
Name String AS RDBMS1(Column=Emp.Name),
Skills MANY AS RDBMS1(Table=Skills, Cols=Empnum->Skill));

4.1 Schema Mapping For Relational Databases

Depending on the amount of information available from the relational schema, one of the following cases may apply [AR]:

• Primary and foreign keys are given.

  A user-defined Pegasus type is created for each relation that has a simple primary key. Then for each user-defined type and for every nonkey attribute in the associated relation, a function is created with the type as argument and the attribute as result. For relations with composite primary key, multiargument functions are created with the primary key fields as arguments and the attribute as result. No type creation is needed in the mapping. If an attribute in the mapped relation is a foreign key, it is replaced with the type corresponding to that key.

• Foreign keys are not given.

  In the absence of any foreign key information, user-defined types cannot be created, since the attributes that refer to a primary key field cannot be substituted by its associated type. However, a functional view of the underlying relations are created in a manner similar to the previous case.

• Primary keys are not given.

  As functional dependencies of any kind are not known, only a predicate function is created for each relation, where all the attributes of the relations form the argument of the function. A predicate function contains one or more arguments and a Boolean valued result.

HOSQL provides facilities for defining and referencing parameter names in a function. This facility is similar to named parameters provided by some programming languages such as Ada. It allows information provided by the attribute names of a relation to be preserved in this mapping.

For determining the mapping between HOSQL and SQL schemas, the following correspondences between functions, types and relations are maintained:

• Each user-defined type t (if any) is equivalent to a relation with a single-attribute primary key.
• For each function f(a_1,...,a_i) = , the arguments and results of F are equivalent to attributes of a relation R.

5 QUERY PROCESSING

The overall query processing flow is shown in Figure 4. The user's query is formulated in HOSQL based on a Pegasus schema. QM (see Figure 1) parses the query into an intermediate structure called an F-tree, which is the syntax tree of HOSQL functional expressions. The nodes of an F-tree include function calls, variables, and literal objects. F-trees are transformed into B-trees which are annotated with catalog information. For queries involving foreign data source this would include the database name, site network id, etc. A query against a single FS will bypass the Pegasus optimization process and will go directly to the FS. This is an attempt to minimize the overhead of Pegasus for single database queries.

\begin{figure}[htbp] \begin{figure}[ht] \vspace*{5in} \vspace*{4.5in} \caption{Query processing flow.\label{qproc}} \end{figure} Figure 4. Query processing flow.

Portions of the query referring to data at the same FS will be identified and grouped in order to reduce the number of invocations to each FS (subject to other optimization criteria). QM will enumerate possible groupings based on FS site information. For each grouping all data nodes in the B-tree belonging to the same group will be merged and become a single data node, called a virtual data node. This process decomposes the original query into a set of subqueries, each of which refers to data residing in only one FS. Pegasus trees produced for each grouping are called D-trees.

Based on the available statistical data, QM will start a cost-based optimization for a D-tree. This includes choice of join order, join methods, join sites, and intermediate data routing and buffering, etc. The result of this process is a globally optimized execution plan for each particular group. The cheapest plan is chosen as the query execution plan.

Once the query execution plan is determined, QM will translate the FS access requests represented by a virtual data node into the FS-specific application program interface languages and will set up other structures to facilitate the run-time process. Steps in a final execution plan are either FS DML statements acceptable by their destination FSs or are operational primitives. Examples of operational primitives are commands to perform joins in Pegasus, to move data across FSs, and to synchronize steps executed in parallel.

QM distributes the relevant execution steps to each P-shell associated with the involved FSs and coordinates the overall execution. This includes establishing network connections, control blocks and buffer allocation, parameter binding of FS queries, invocations of FS, and assembly of results.

Unlike distributed DBMSs, Pegasus has limited statistical information for data residing in FSs. Moreover, Pegasus has no control over the optimization of subqueries sent to each FS. For example, Pegasus has no right and cannot enforce a particular access path to be used at an FS site. Otherwise, it will violate site autonomy. Therefore, Pegasus emphasizes global optimization and tries to find the best possible decomposition and grouping of queries. Accordingly, research on query processing in Pegasus is focused on:

• Efficient determination of optimal global query execution plans.
• Dynamic run-time reconfiguration of global query execution plans.
• Run-time statistical data collection.
• Exploration of techniques to assemble the results returned by the individual data systems.
• Global query optimization criteria such as response time vs. resource utilization and parallel execution vs. load balancing.
• Tools for cost estimation of multidatabase queries with incomplete information about underlying databases.

6 DATA INTEGRATION

The interrelationships among systems and data sources are illustrated in Figure 5. A client deals with one Pegasus system. Any other system is a foreign system.

\begin{figure}[htbp] \vspace*{7in} \caption{Interrelationships among systems and databases.\label{pegrels}} \end{figure}

Figure 5. Interrelationships among systems and databases.

A data source is typically a database, though it might be some other type of data source, such as a file system. A foreign system may support one or more data sources. Data sources not in Pegasus are foreign data sources.

A foreign data source is represented in Pegasus by an imported schema, which looks like a native Pegasus schema except that its underlying data is maintained at the foreign system. To preserve the full autonomy of the foreign databases, only that part of the foreign database which is exported is visible through Pegasus. The exported schema of a foreign database is a foreign schema for Pegasus.

A native database is created in Pegasus in the usual fashion, having both schema and data in Pegasus. Other databases (imported or native) may be attached to a native database, providing access to multiple data sources.

A root database is a native database to which a client is connected, and through which he may have access to other attached databases.

The following facilities are provided for creating Pegasus multidatabases:

• Registration introduces a foreign system to the Pegasus system, making future interaction possible. Registration is carried out at the DBMS level in a given system environment (platform and network). Registration describes such things as data management systems, network protocols, network nodes, machine types, etc.
• Creation makes a new Pegasus database, either native or imported.
• Import (an option of the Create operation) makes a foreign data source known to Pegasus, by creating an imported schema to serve as the image of the foreign schema.
• Mapping makes a foreign schema look like a Pegasus schema. Section 4.1 describes mapping of relational schemas to Pegasus schemas.
• Attachment logically extends a native database with other databases and creates integrated Pegasus schemas. The database to which the others are attached serves as a root database. Attached databases may be native or imported. The Attachment will persist after the client disconnects, unless requested as a transient attachment, or explicitly detached.
• Integration deals with semantic heterogeneity of different databases, all having Pegasus schemas. A root database and all attached databases automatically have a default minimum level of integration described in the next subsection. Further integration is achieved by defining additional constructs in a root database to reconcile heterogeneity in the attached databases.
• View definition allows applications to define their desired views of databases on top of Pegasus integrated schemas. One of the objectives of Pegasus is to allow existing applications to access multiple databases through Pegasus without major modifications. Views can be used to present data to applications in the forms they require.

6.1 Minimal Integration

Basic attachment creates a union of database schemas. As an example, Figure 6 shows the schema of the working environment that a client has when he connects to db0 as the root database and then attaches database db1.

\begin{figure}[htbp] \vspace*{7in} \caption{Minimal schema integration.\label{minschem}} \end{figure}

Figure 6. Minimal schema integration.

The user-created types, functions, and other objects in the root and attached databases are presumed distinct and disjoint from each other. Names of types and functions may be prefixed by their database name or alias to prevent ambiguity. Ambiguities involving the root database will be resolved in favor of the root. Other approaches to resolve ambiguities are being investigated.

6.2 Supertypes and Functions

One fairly natural integration technique which is supported in the first Pegasus prototype is the creation of supertypes of types defined in attached databases. If db1 and db2 each contain a Student type, and both are attached to db0 we might create a common supertype in db0:

CREATE TYPE Student SUPERTYPE OF db1.Student, db2.Student;

The new type Student (also known as db0.Student) will continue to exist in db0 even if db1 or db2 are detached. The instances of db0.Student will include the instances of db1.Student and db2.Student if and only if those databases are attached. For now, we assume that the students in the two databases are disjoint, so no student exists in both. This restriction will be relaxed when multidatabase object identification schemes are provided in Pegasus.

What functions are applicable to db0.Student? Initially, none. The approach we have adopted for now is to require functions to be defined explicitly on the supertype. In the future we will support a notion of upward inheritance.

Suppose, for example that functions called Name exist for the Student type in both db1 and db2 i.e., db1.Name is defined on db1.Student and db2.Name is defined on db2.Student. In db0 after

CREATE FUNCTION Name(Student)->String;

the query

SELECT Name(x) FOR EACH Student x;

will return db1.Name(x) if x is an instance of db1.Student and db2.Name(x) if x is an instance of db2.Student.

Simple mismatches of function names can be handled by using the ALIAS feature of HOSQL, allowing functions with different names to participate in inheritance as though they had the same name:

CREATE FUNCTION Name(Student)->String
ALIAS db1.SName, db2.StudentName;

Semantic or behavioral differences among functions in different databases cannot in general be reconciled automatically. The Pegasus mechanisms for defining derived or foreign functions allow a database administrator to specify the appropriate reconciliation strategy. Suppose, for example, the Grade function in db1 and the Points function in db2 did not behave consistently. The user can define functions Map1 and Map2 which convert each to a common result, and then

CREATE FUNCTION Score(Student x)->Real r AS
IF db1.Student(x) THEN Map1(Grade(x))
ELSE IF db2.Student(x) THEN Map2(Points(x))
ELSE ERROR;

7 DOMAIN MISMATCH AND SCHEMA MISMATCH

Domain mismatch and schema mismatch are two of the important semantic integration problems for interoperating heterogeneous databases [K1,K2,BL,DH], and will be focused on in the second Pegasus prototype.

Domain mismatch generally arises when several databases treat some common conceptual territory in different ways, the simplest example being differences in units of measurement. Schema mismatch is much the same thing at the schema level; an interesting "cross-over" problem arises when things in the data of one database correspond to things in the schema of another.

7.1 Domain Mismatch

The domain mismatch problem begins when some common conceptual territory is treated in different ways by different domains in different spheres. Consider the "conceptual territory" of money. The different "domains" correspond to different currencies in which money might be represented. A "sphere" is some scope in which a single domain, i.e., a single currency, is used. While we often think of a sphere as a database, a sphere might be a subset of a database in which several currencies are used, or it might span several databases.

\begin{figure}[htbp] \begin{center} \begin{tabular}{r||c|c|c|l} Conceptual&\multicolumn{3}{c|}{Spheres}\\ \cline{2-4} Territories&US &France&Germany& \\ \hline money &m_1&m_2 &m_3 &\leftarrowdomain group \\ jobs &j_1&j_2 &j_3 &\leftarrowdomain group \\ colors &c_1&c_2 &c_3 &\leftarrowdomain group \\ \hline \end{tabular} \end{center} \vspace*{.1in} \caption{Domains.\label{domfig}} \end{figure}

Figure 7. Domains.

A domain group is a set of domains d_i which cover some conceptual territory. Each domain d_i is typically in a distinct sphere s_i. In Figure 7, the domains m_1, m_2, m_3 might be different currencies in which money is represented.

Currencies represent a relatively simple sort of domain mismatch, involving computational conversion among literal data values. More complex discrepancies arise when the same conceptual territory is perceived as being populated, or partitioned, in different ways. The concept of "job" might be common to several spheres, yet each sphere has a different notion of what the specific jobs are. One sphere might have engineer, secretary, and salesman as jobs, while the jobs in another might include technician, designer, engineer, secretary, administrative assistant, and customer representative. The same thing might arise with the sets of skills one might possess, or with ethnic groupings, or with organizational units within different business entities (projects, departments, sections, labs, divisions, groups, operations, sectors, etc.).

Other examples might include different palettes of colors covering the same spectrum, different grading systems at different schools, different rating systems for restaurants (or for movies, or for hotels, etc.), terms in different languages for the same or similar concepts, different kinds of geographic units (counties vs. postal codes vs. voting districts vs. assessment districts, etc.). Another kind of mismatch arises if things are represented in one sphere as character strings but in another as persistent objects.

The domain mismatch problem can generally be decomposed into two aspects:

• Mappings between domains.

  Currency conversions represent mappings between different domains, i.e., different ways of representing the territory of money values. The mapping is independent of usage.

• Integrator facilities which use such mappings.

  Integrator facilities depend on how the domains are being used. The paradigm for reconciling stock prices in different currencies may differ from the paradigm for reconciling salaries in different currencies, even though the same currency conversions are used. We might wish to see the average of stock prices but the sum of salaries.

A typical domain mismatch problem requires presentation of information maintained in different spheres s_i in some globally unified form in an integrating sphere s*. For example, corporate headquarters (the integrating sphere) may wish to see the starting salaries for all jobs. Different divisions (the local spheres s_i) may have different definitions of jobs, different algorithms for defining starting salaries, and different currencies in which they are expressed. Thus there is a global integrator function

f*: ad* -> rd*

which provides a global view of a function (e.g., starting salaries) from an argument domain ad* (e.g., the job set defined at the corporate level) to a result domain rd* (e.g., the common currency used at the corporate level).

The integrator function in turn has to be mapped to a set of localized functions

f_i: ad_i -> rd_i

which provide the corresponding information in each local sphere s_i.

7.1.1 Domain Mappings

A domain mapping µ_D_ij translates from elements of d_i to elements of d_j in a domain group D. We are mostly interested in mappings to and from an integrating domain µ_D_i* and µ_D_*i.

An ideal domain mapping is an invertible computation on a stable population of literal data values, as with currency or units conversions. Real mappings may not be.

The populations may not be stable, requiring the mapping to be updated. Jobs may be added or dropped in various divisions. New letter grades might be adopted at certain schools, requiring an update of the mapping to numeric grades. New colors might be introduced.

The mapping may not be invertible, perhaps being many-to-one. Numeric grades map unambiguously into letter grades, but not vice versa. Lead Programmer might be a distinct job in some divisions, which the corporate level chooses not to distinguish from Programmer; both jobs map into the same one at the corporate level.

Non-literal values, e.g., persistent objects, require object existences to be managed. If corporate has an object-oriented database, then the appearance of a new job name in a relational database at one of the divisions may require explicit creation of a new job object in the corporate database.

The easiest solution to implement puts the burden of responsibility on users, requiring them to manually maintain the domains and mappings by appropriately creating and deleting objects, and by modifying mapping rules or data. In this case, when a mapping encounters an unfamiliar value it simply returns an error. The complexity of the problem still requires this solution as a fall-back for the general case.

These problems are explored in detail in [K2]. An example of possible automation arises when the correspondence between jobs can be established on the basis of their names. The mapping from job names to job objects, with automatic creation of job objects as needed, might be achieved as follows in a database programming language (in the style of the Iris IPL):

CREATE FUNCTION MapName2Job(Char n) -> Job AS
BEGIN
VAR j;
j := SELECT Job jj WHERE Name(jj)=n;
IF IsNull(j) THEN j := CREATE Job;
Name(j) := n;
RETURN j;
END;

7.1.2 Integrator Functions

An ideal integrator function

f*: ad* -> rd*

would have a simple mechanism for evaluating y*=f*(x*):

• There is a simple inverse mapping from x* to exactly one x_i in exactly one domain ad_i.
• The corresponding function f_i is readily identified.
• The single result y_i=f_i(x_i) is simply mapped into the desired result y*.

Real integrators aren't always so simple. The domain mappings might not be well behaved, as described earlier. Among other things, a given x* might map into several x_i's in several domains d_i, e.g., if a given job exists in several divisions.

The corresponding functions f_i might not be so readily identifiable. They might not be identifiable by naming conventions, having a variety of names, perhaps in several languages. They might not exist at all, in which case some sort of default action needs to be specified. It might be possible to fabricate a missing localized function f_i from other information. One division might have a range of starting salaries depending on prior experience, for which the average should be reported for this inquiry. Another division might specify starting salaries indirectly, via job categories.

When x* maps into several x_i's in several domains d_i, then the results of several local functions f_i need to be reconciled by some algorithm in f*. This might be a sum or average of values, or a list of all of them, perhaps annotated with some information about the sources.

In some cases, operator overloading can be used to automatically implement the integrator function. Integrators and overloaded operators both require choosing from a set of other functions to be executed. The simplest such case arises when the argument domains ad_i correspond to disjoint types, and all the functions f* and f_i have the same name.

Assume we have disjoint sets of employees AEmployee...ZEmployee, perhaps in different divisions of the company, and there is a Salary function on each, all returning salaries in US dollars.

In order to access the salaries of all employees, all we have to do is define a supertype spanning all the employees [DH], with a Salary function defined on it (Figure 8):

\begin{figure}[htbp] \begin{center} \verb Employee \\ \verb | Salary \\ \verb | \\ \verb ---------------------- \\ \verb | | \\ \verbAEmployee ... ZEmployee \\ \verb Salary Salary\\ \end{center} \vspace*{.1in} \caption{\label{simp2}} \end{figure}

Figure 8. 

CREATE TYPE Employee SUPERTYPE OF AEmployee ... ZEmployee;

CREATE FUNCTION Salary(Employee) -> Number AS 0;

The Salary function on Employee is defined to provide a default value, in case the Employee supertype is instantiable. Via late binding and overload resolution [Ly], an invocation of Salary(x) will bind to the Salary function defined on whichever subtype x belongs to.

If the salary functions don't all have the same name, overload resolution could be extended with a simple aliasing mechanism to allow them to behave as though they had the same name.

7.2 Schema Mismatch

Schema mismatch arises when similar concepts are expressed differently in the schema. A common byproduct is that data instances in one sphere correspond to schema elements in another. Depending on the model, the schema elements might be such thing as relations and attributes, entities and relationships, classes and methods, types and functions, etc. Our work is expressed in terms of the types and functions in the Iris functional object model [F1,F2].

Many schema mismatch problems are really domain mismatch problems, except that some of the domains are in the schema instead of in the data. Jobs, for example, are often modeled as types, i.e., subtypes of Employee. Instead of AsgJob(Sam)=Engineer, we know that Sam is an engineer because he is an instance of the type, i.e., Engineer(Sam) is true.

For this sort of mismatch, one of the domains is a set of types (a type group), i.e., those subtypes of Employee which correspond to jobs. (Not all subtypes of Employee qualify. There may be other subtypes corresponding to Male and Female, or Exempt and Nonexempt, or Active and Retired, etc.)

An example involving functions is adapted from the stock market examples of [KL]. We have a sphere StockSphere_1 containing a base stock market Activity function on three arguments

Activity: Company x Reading x Date -> Price

whose extension at the moment is shown in Figure 9.

\begin{figure}[htbp] \begin{center} \begin{tt} \begin{tabular}{|l|l|l||c|} \multicolumn{4}{l}{Activity}\\ \hline Company&Reading& Date & Price \\ \hline hp & close & 1/3/91 & 50 \\ hp & close & 1/4/91 & 51 \\ hp & high & 1/3/91 & 52 \\ hp & high & 1/4/91 & 53 \\ ibm & close & 1/3/91 & 52 \\ ibm & close & 1/4/91 & 51 \\ ibm & high & 1/3/91 & 55 \\ ibm & high & 1/4/91 & 54 \\ \hline \end{tabular} \end{tt} \end{center} \vspace*{.1in} \caption{StockSphere_1.\label{aa}} \end{figure}

Figure 9. StockSphere_1.

Another sphere StockSphere_2 might maintain the same data in separate functions for each company, such as

HPActivity: Reading x Date -> Price
IBMActivity: Reading x Date -> Price
.
.
.

The corresponding extensions of two of these functions are shown in Figure 10.

\begin{figure}[htbp] \begin{center} \begin{tt} \begin{tabular}{|l|l||c|c@{\ \ \ }|l|l||c|} \multicolumn{4}{l}{HPActivity} & \multicolumn{3}{l}{IBMActivity}\\ \cline{1-3} \cline{5-7} Reading & Date & Price & & Reading & Date & Price \\ \cline{1-3} \cline{5-7} close & 1/3/91 & 50 & & close & 1/3/91 & 52 \\ close & 1/4/91 & 51 & & close & 1/4/91 & 51 \\ high & 1/3/91 & 52 & & high & 1/3/91 & 55 \\ high & 1/4/91 & 53 & & high & 1/4/91 & 54 \\ \cline{1-3} \cline{5-7} \end{tabular} \end{tt} \end{center} \vspace*{.1in} \caption{A function group in StockSphere_2.\label{bb}} \end{figure}

Figure 10. A function group in StockSphere_2.

In StockSphere_1 the domain of interest is a set of Company instances in the data. In StockSphere_2 the corresponding domain is a set of functions, i.e., a function group.

7.3 Summary

[This could be shortened or eliminated if we want to conserve space.]

Domain mismatch and schema mismatch are complex problems. They can best be understood by structuring the environment in terms of domain groups corresponding to conceptual territories, with different domains occurring in different spheres. Integration then occurs using integrating domains in an integrating sphere. The domain mismatch problem separates into two parts, the definition and maintenance of domain mappings, and the definition and update of integrator functions. Schema mismatch can in many cases be reduced to the domain mismatch problem by treating type groups and function groups as domains in themselves. The problems can generally be decomposed into a mapping aspect (corresponding to the mappings in [KL]) and an integrating aspect (corresponding to the rules in [KL]).

Although such analysis and decomposition is helpful, the solutions generally require sophisticated language capabilities. The role of a database programming language is to permit the solutions to be expressed and maintained with the database, rather than in application code.

Thus behavior specification is an essential contribution of object-orientation to the solution of the mismatch problem. Subtypes and supertypes are another essential feature for reconciling disparate domains. Overloaded operators are also useful. Object identity, on the other hand, seems to add problems: maintaining domain mappings can require explicit creation or deletion of persistent objects.

In a context which includes type systems, persistent objects, and non-trivial correspondences between domains, desirable language facilities include:

• Arbitrary computational power: conditionals, iteration, and probably even recursion (though we haven't actively looked for examples requiring recursion), as well as aggregate types and operations.
• Type and function groups, including disjointness and covering specifications.
• Uniform treatment of system and user objects:
  • Uniform syntax/semantics for creating user- and system-type objects.
  • Variables and expressions allowed wherever system objects can occur, i.e., functions and types. This would include their occurrence in declarations and queries.
  • DDL within procedures, e.g., dynamic creation of types and functions, with parameterized arguments.
  • User subtypes of system types (e.g., type and function groups).
  • Creation of user-defined supertypes as well as subtypes.
• Update entry points.
• Extended overloading, via aliasing and compatible result types.
• Derived types.
• Subtypes of literals, including
  • Dimensioned types (units).
  • Enumerated types.
  • Length-constrained types.

8 OBJECT IDENTIFICATION

Object identification in single database systems is relatively simple. Most single database management systems have developed and adopted a workable approach. However, object identification in a heterogeneous multidatabase management systems is difficult because [Ne]:

• Logically different objects may have the same identifier in different data sources.

  The usual solution to the collision of object identifiers across multiple data sources is to introduce an independent system of globally unique identifiers which have to be mapped to the local identifiers of each participating database. In Pegasus we are investigating an alternative approach which assures a sufficiently high probability that independent Pegasus databases will generate distinct object identifiers.

• A single logical object may have different identifiers in different data sources.

  Sometimes the same object exists in multiple data sources. A given student might be attending several schools, or the same person might exist in separate databases as a student and as a teacher. They can be expected to have different object identifiers in the different databases. There is, in general, no fully automatic way to deal with this. Pegasus allows equivalences to be specified by a user. It might be an algorithm, such as matching social security numbers, or it might be a table of corresponding oids constructed by the user. Once specified, Pegasus will attempt to treat equivalent oids as synonyms for the same object.

• Some data sources do not provide unique object identification.

  Foreign data sources having no object identification scheme can be handled in two ways: model everything as literals, or introduce user-specified object identifiers. The latter case specifies that object identifiers are to be mapped from some property such as student numbers or part numbers in the foreign data source. Mechanisms for providing appropriate uniqueness and format compatibility need to be developed. Providing an independent system of globally unique identifiers will complement these solutions.

• Data sources may use different identifier lengths and formats.

  Foreign data sources having object identifiers in different format from Pegasus reduce to the previous case. They are, in effect, simply properties being maintained in the foreign data source.

These problems are being investigated for implementation in the second phase of the Pegasus project, which will begin after the completion of the first Pegasus prototype scheduled for the summer of 1991. Correctness criteria to be used in evaluating candidate solutions are:

• Uniqueness: An object must be distinguishable from any other object in the system.
• Stability: An object must retain its identity despite changes in its properties.
• Consistency: If a system supports several kinds of oids such as logical, local, and global oids, they must not conflict with each other. Distinct objects in one data source should be distinct globally.

The solution approaches being pursued include:

• Generation of unique identifiers based on user-specified properties maintained in a data source.
• Alternative mechanisms for generating global identifiers, such as randomization techniques or variable prefixes.

  Mapping equivalent objects into a single representative object in an integrating domain. This is closely related to the domain mismatch problem.

9 CURRENT STATE AND FUTURE DIRECTIONS

The design and implementation of a comprehensive flexible heterogeneous multidatabase system such as Pegasus is a significant undertaking. Such a system has to meet a large set of diverse applications requirements, should interoperate with existing information systems, and should function in heterogeneous distributed computer systems environments. It is important to have extensibility in mind from the beginning and develop a modular system architecture which lends itself to future extension.

The development of the Pegasus multidatabase management system will proceed in phases. In the first phase we are developing a prototype with the following functionality:

• A common model which provides an abstract unified view of participating databases.
• Retrieval of data from participating databases in a single query statement.
• Obtaining a single global schema by mapping the schemas of participating databases.
• Defining relationships across participating databases.
• Resolving domain mismatch by providing conversion functions.
• Data integration by generalizing identical functions defined on the imported databases.

The performance of data retrieval in this prototype should exceed the performance requirements of multidatabase applications which we intend to use as testbeds. This prototype will not support multidatabase update. Moreover, the prototype will not be a DBMS, i.e., all the data will reside in the participating databases. Only relational database management systems and Iris will be supported as participating databases. This prototype is due for completion by the summer of 1991.

10 CONCLUSIONS

There is consensus that flexible, efficient, and comprehensive heterogeneous multidatabases are needed to support the trend toward the extensive use of computers and information as a competitive tool in today's complex business world. However, the design and implementation of such a system is a major undertaking. There are several problems which must be solved before robust general purpose heterogeneous multidatabase management systems become possible. Distinguishing equal but logically different objects, consolidating different representations of the same object, materializing the views of existing applications, resolving the semantic heterogeneity of information stored in multiple databases, maintaining consistency of data in the presence of multidatabase concurrent transactions, and doing all this efficiently, are examples of problems that must be solved.

The Pegasus project at the Database Technology Department in Hewlett-Packard Laboratories has created an environment within which the problems in developing heterogeneous multidatabase management systems are being addressed.

11 REFERENCES

[AD] R. Ahmed, P. DeSmedt, W. Kent, M. Ketabchi, W. Litwin, A. Rafii, M. C. Shan, "Pegasus: A System for Seamless Integration of Heterogeneous Information Sources", Proc. IEEE COMPCON, March 1991, San Francisco, Calif.

[AR] Rafi Ahmed and Abbas Rafii, "Relational Schema Mapping and Query Translation in Pegasus", Workshop on Multidatabases and Semantic Interoperability, Nov. 2-4, 1990, Tulsa OK. Also HPL-DTD-90-4, Hewlett-Packard Laboratories, Oct. 9, 1990.

[An] Jurgen Annevelink, "Database Programming Languages: A Functional Approach", HPL-DTD-90-12, Hewlett-Packard Laboratories, Nov. 30, 1990.

[Ba] J. H. Balboni, "SQL Access Overview," Proceedings of CompCon91, Feb. 91, San Francisco.

[BL] C. Batini, M. Lenzerini, and S.B. Navathe, "A Comparative Analysis of Methodologies for Database Schema Integration", ACM Computing Surveys 18(4), Dec. 1986.

[BG] P. Bernstein, E. Goodman, E. Wong and J. Rothnie, "Query Processing in a System for Distributed Databases (SSD-1)", ACM Trans. on Database Systems, December 1981.

[BO] Breitbart, Olson and Thompson, "Database Integration in a Distributed Heterogeneous Database System", Data Engineering Conference, 1986.

[BS] Y. Breitbart, A. Silberschatz, G.R. Thompson, "Reliable Transaction Management in a Multidatabase System", Proc ACM SIGMOD, May 1990.

[Ch] Chin-Wan Chung, "DATAPLEX: An Access to Heterogeneous Distributed Databases", CACM, Vol. 33, No. 1, January 1990.

[DH] Umeshwar Dayal and Hai-Yann Hwang, "View Definition and Generalization for Database Integration in a Multidatabase System", IEE Trans. Software Engrg, Vol SE-10 No 6, Nov. 1984.

[ED] A.K. Elmagarmid and W. Du, "A Paradigm for Concurrency Control in Heterogeneous Distributed Databases Systems", Proceedings of IEEE Data Engineering, 1990.

[F1] D.H. Fishman et al, "Iris: An Object-Oriented Database Management System", ACM Transactions on Office Information Systems, 5(1), January 1987. Also in Readings in Object-Oriented Database Systems, Zdonik and Maier, editors, Morgan Kaufmann, San Mateo, California, 1989.

[F2] D.H. Fishman, et al, "Overview of the Iris DBMS", Object-Oriented Concepts, Databases, and Applications, Kim and Lochovsky, editors, Addison-Wesley, 1989.

[Fu] I.J. Fuller, "An Overview of the HP NewWave Environment", HP Journal, Vol. 40, No. 4, August 1989.

[HM] D. Heimbigner, D. McLeod, "A Federated Architecture for Information Management", ACM Trans. on Office Information Systems, Vol 3, No. 3, July 1985.

[HK] D.K. Hsiao and M.N. Kamel, "Heterogeneous Databases: Proliferation, Issues, and Solutions", IEEE Transactions on Knowledge and Data Engineering, Vol. 1, No. 1, March 1989.

[TP] ISO/IEC DIS 10026-2, OSI, "Distributed Transaction Processing".

[KD] M. Kaul, K. Drosten, and E.J. Neuhold, "ViewSystem: Integrating Heterogeneous Information Bases by Object-Oriented Views", Proceedings of IEEE Data Engineering, 1990.