The Breakdown of the Information Model in Multi-Database Systems

1 INTRODUCTION

2 INFORMATION MODELING IN A DATABASE

A database tries to present a faithful model of some body of information we can loosely call "reality" (even though the information might be historical, obsolete, fictional, speculative, or even erroneous). The model is constructed from whatever sorts of materials a particular data model provides, such as relations and attributes, or entities, attributes, and relationships. In this paper, we will build models using the materials provided by functional object models such as Iris [F1]: objects, types, and functions. Functions collectively model the notions of attributes, relationships, and operations.

2.1 Identity and Naming

The most fundamental principle on which modeling rests is a one-to-one correspondence between the proxy objects in the database and the entity objects in the real world the proxies are supposed to represent. The assumption is strongest in object-based systems, a bit weaker in value-based systems. So long as there is such a tight correspondence, we even want to forget the distinction between the two. We are content to think we can create an employee named Sam, rather than having to be so picky as to request the creation of a proxy object intended to represent the real Sam. The fact that we're creating something whose "age" is considerably greater than zero at the moment of creation doesn't seem to bother us.

Naming is also essential to make modeling work. If it stands for Sam, we want to call it Sam. If we are thinking about employees, we want a type called "Employee". If we are concerned with salaries, there ought to be a function called "Salary". We can think of such types and functions in the database as themselves being proxies for their real-world counterparts.

We have long ago learned that mechanistic systems, from paper ledgers to computer systems, don't have nearly the sophisticated power of the human mind to resolve ambiguous references in context. So we have grown accustomed to assigning unique identifying codes to things, such as employee numbers, social security numbers, part numbers, department numbers, airport and city codes, etc. We accept those as serving the purpose of "naming", even though people rarely use them in conversational references to things. In spite of our best intentions, though, such identifiers can still be unreliable. Several of them might be the same (some employee number might match some part number), not all entities might have one, some entities might have several - and they might even change, meaning that we need something else to identify the thing whose identifier has changed. That's why object-oriented systems have gone one step further, generating their own unique and invariant identifiers for proxy objects in order to preserve the correspondence with the entity objects being modeled.

How do we know whether x and y refer to the same object [K1,K2]?

In a single object-oriented database (or other object-oriented system), the identity of most objects can be traced back to recognizable creation events, which leave their mark in terms of unique object identifiers. Distinct creation events yield distinct oid's. x and y refer to the same object if and only if their values are matching oid's.

Value-based systems such as relational databases don't provide quite as good a model of identity. They don't have explicit creation events as the basis for identity and existence. Primary and foreign keys provide a rough approximation: insertion of a new key value in a "primary" (entity) relation approximates the creation of a new object. The scheme is imperfect in several respects:

• Some objects may have no primary relation in which their identifiers serve as the primary key. This might be the case for such things as dependents, cities, schools, etc. A database might still contain information "about" such objects, sometimes - but not always - in unnormalized relations, such as the social security number, name and age of a dependent. It's quite difficult to associate a creation event with such objects.
• The same key might be a primary key in several tables, so that insertion into a table does not necessarily imply creation of a new object. This might arise simply from vertical partitioning (e.g., keeping employee benefits and payroll information in separate tables). It might also arise from subtypes: if data about salesmen is kept in a separate table, then inserting an employee into the table doesn't necessarily connote creation of a new object. In some cases the problem might be solved by designating one of the tables to be the real primary one, but that doesn't always work.
• Nothing prevents several primary keys from belonging to the same object. Different relations might be keyed by social security number, employee number, and military service number. There is no inherent mechanism to detect when several such identifiers identify the same person.

2.2 Constraints

2.3 Certitude

2.4 Stability

3 THE BREAKDOWN IN MULTI-DATABASE SYSTEMS

Any one database does a pretty fair job of maintaining the realism of its model. We know what to expect of it, and we know to expect different things of different databases. We don't expect the parts database to know about employee benefits. We expect a database in another country to spell the Salary function differently, and to give results in a different currency.

Things start to break down, though, when we deal with several databases at a time [Ba,Da,Sh]. To begin with, we ask our system designers to make that transparent to us, so that we don't have to know or care which databases we're dealing with, or how many, at any point in time. We still want to be presented with the illusion of a single database, a single faithful model of reality.

3.1 Identity and Naming

Above and beyond the aforementioned problems of value-based systems, multi-database systems present us with the problems of multiple creation events and uncoordinated object identifiers.

Just to keep things clear, let's agree that each act of creation creates a distinct proxy object, so that proxies created in different databases are necessarily different. If we "create" the employee Sam in several databases, we have created several proxies.

That immediately breaks down the fundamental modeling assumption, the one-to-one correspondence between proxies and entities. We might have different proxies in the system representing the same entity - and they might not behave consistently. The fundamental problem of multi-database systems is to restore consistency of the model, i.e., to provide an environment in which there appears to be one proxy per entity.

We can no longer ignore the difference between proxies and entities quite so casually, though we'd like to provide a system in which end users can. "Same proxy?" and "Same entity?" are no longer the same question; the answer to one can be different from the other. Let's use x=y when x and y refer to the same proxy, and x==y when they refer to the same entity. The first should imply the second, but not vice versa.

Creating a proxy no longer corresponds uniquely to creating an entity, and we even need to re-think what "creation" means here. It's a little harder to pretend that we are "creating" a new Sam each time. While we are creating a new proxy, we are only introducing an entity that wasn't previously known to that particular database.

How shall we know that two proxies represent the same entity, that x==y even though x¬=y? That's the $64,000 question. To begin with, the question can only arise in a context where both proxies are known.

A simple but tedious solution is to have someone tell us, either when a proxy is created or at some later time, that one proxy represents the same entity as another, e.g., that the Sams we've created in several databases really represent the same thing. We would keep tables of such correspondences around, and look them up every time we need to evaluate x==y when x¬=y.

Though such a solution must be available as a last resort, it's not very nice. Our job is to make life easier than that for the user whenever we can. Which means we should try to infer x==y from available information whenever we can - which is possible in various degrees, and with various levels of confidence. It's easiest when there's a suitable identifying property, such as employee number. Two employee proxies represent the same entity if they have the same employee number (assuming we can detect identity of the employee number functions). This method is reliable to the extent that the property is a reliable identifier: unique (no two employees have the same one), singular (no employee has two of them), total (each employee has one), and stable (the same one always identifies the same employee).

More complex situations arise when there are several such identifying properties, or properties which are almost reliable. For instance, some people might have social security numbers and some might have employee numbers; some might have both, and some neither. Two databases might show the same social security number assigned to people having different employee numbers. An even more complex approach is to try to establish equivalence with some level of confidence based on similarities.

This problem applies to meta objects (types and functions) as well as to ordinary objects, reflected in the problems of schema integration. Not only do we have to figure out whether two proxies represent the same person, we also have to figure out whether two types are the same, or two functions are the same. Before we can observe that Sam has different birthdays in two databases, how did we figure out that two "birthday" functions are the same thing? They may or may not have the same names, and they may or may not match in other properties. Just what would it mean to say two things are the "same function" if they have different names, or different argument or result types, or if they return different result values for the "same" argument? What does it mean to say two types are the same if they have different instances or subtypes or supertypes, or if they have different functions defined on them?

3.2 Constraints

We currently don't know how to enforce constraints across autonomous databases. We are fuzzy as to whether constraints apply to proxies or to entities. Paradoxes arise if we do or don't assume that two proxies represent the same entity. In Figure 1, if the proxy objects @1dick and @2richard represent the same thing, it has two birthdays. If they are different things, then we have two things with the same employee number.

Hidden constraints, which we didn't even realize were implicit in single databases, emerge to plague us in multi-database systems. In a single system, only one person has a given employee number and only one has a given social security number, so we don't bother to say that persons having the same employee number must have the same social security number. This rule can be violated in multi-database systems.

Some examples in two databases are shown in Figure 1 (@1xxx denotes an oid from the first database).

---------------------------------------------------------------------------
| Employee1 = {@1tom, @1dick}      | Employee2 = {@2richard, @2harry}     |
|                                  |                                      |
| EmpNum1: Employee1 -> Integer    | EmpNum2: Employee2 -> Integer        |
|               [single,unique]    |               [single,unique]        |
|   EmpNum1(@1tom) = 111111        |   EmpNum2(@2harry) = 333333          |
|   EmpNum1(@1dick) = 222222       |   EmpNum2(@2richard) = 222222        |
|                                  |                                      |
| Birthday1: Employee1 -> Date     | Birthday2: Employee2 -> Date         |
|                     [single]     |                     [single]         |
|   Birthday1(@1tom) = 4/4/44      |   Birthday2(@2harry) = 6/6/66        |
|   Birthday1(@1dick) = 5/5/55     |   Birthday2(@2richard) = 4/5/67      |
|                                  |                                      |
| SSNum1: Employee1-> Integer      | SSNum2: Employee2-> Char             |
|             [single,unique]      |          [single,unique]             |
|   SSNum1(@1tom) = 123456789      |   SSNum2(@2harry) = `012345678'      |
|   SSNum1(@1dick) = 987654321     |   SSNum2(@2richard) = `987564321'    |
|                                  |                                      |
| Manager1: Employee1 -> Employee1 | Address2: Employee2 -> Char          |
|                         [single] |                    [single]          |
|   Manager1(@1tom) = @1dick       |   Address2(@2richard) = `77 Main St' |
---------------------------------------------------------------------------

Figure 1. Discrepancies between two databases.

3.3 Certitude

3.4 Stability

4 SOLUTION APPROACHES

4.1 Spheres of Knowledge

A database is not so much a faithful model of reality as a repository of "knowledge" about reality. Like people, different databases may "know" different things about the same situation.

End users and administrators need different views. End users should still see a consistent model, like a single database, without seeing underlying problems. Administrators need a broader view. They need to see the underlying databases and their problems, and they need tools to provide nicer views for end users.

A sphere of knowledge is an abstraction of one of these databases or views. It might in fact be a subset of the information in a database, or a combination of several databases, or perhaps be some other sort of information source. Every object exists, and every function is executed, with respect to a sphere.

We model a multi-database system as a system of such spheres (Figure 2). Spheres s1 and s2 correspond to underlying databases to be integrated. In the example, they contain four proxy objects intended to represent three entity objects (along with much other information not shown). Each of these spheres is internally consistent within itself. Sphere s* is an integrated view seen by an end user. It too is internally consistent, showing three proxies representing three entities, together with consistent information about them. s' is a super-sphere seen by an administrator. He sees all the proxies and all the inconsistencies. In the sphere s', the administrator can define the functions that map the sub-spheres s1 and s2 into the consistent sphere s* for the end user [K3]. Such mappings have to establish correspondences for meta-objects (types and functions) as well as ordinary objects.

s'
  ------------------------------------------------
  |                                              |
  |    s*                                        |
  |    ......................................    |
  |    : s*.e1         s*.e2          s*.e3 :    |
  |    ....|.........../...\.................    |
  |        |          /     \           |        |
  |        |         /       \          |        |
  |    s1  |        /         \         |  s2    |
  |    ....|......./...     ...\........|....    |
  |    : s1.e1  s1.e2 :     : s2.e2   s2.e3 :    |
  |    ................     .................    |
  |                                              |
  |                                              |
  ------------------------------------------------

Figure 2. Spheres of knowledge.

4.2 Integration Techniques

Other integration techniques being pursued in the Pegasus project are beyond the scope of the present paper. They are described in [Ah,K1,K3,Kr]. Of the problems described above, the ones currently receiving most attention are in the areas of identity and naming, e.g.,

• Mechanisms for identifying and managing object identifiers for non-object-oriented data sources.
• Mechanisms required to define and assert equivalence among proxy objects in different databases.
• Investigation of the conditions under which supertypes do or don't provide an appropriate integrating mechanism.
• Various name resolution mechanisms for multi-database name spaces.

5 REFERENCES

[Ah] 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.

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

[Da] 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.

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