[New Zealand Digital Library] [Computer Science Technical Reports] [Query Results] --------------------------------------------------------------------------- TM-0014-06-88-165 Distributed Object Management Technology Frank Manola June 30, 1988 GTE LABORATORIES INCORPORATED 40 Sylvan Road Waltham, MA 02254 Copyright ? 1988 GTE Laboratories Incorporated TM-0014-06-88-165 --------------------------------------------------------------------------- This document is a GTE Laboratories Technical Memorandum. It describes interim research results and preliminary conclusions derived from them. The ideas and views put forth by the author have been reviewed and accepted by the Department Manager. _____________________________________ _______________ Author Date _____________________________________ _______________ Manager Date Intelligent Database Systems --------------------------------------------------------------------------- Abstract The Distributed Object Management (DOM) project is currently conducting research into "distributed object management" technology, which we believe will provide a significant step towards interconnectivity and interoperability among heterogeneous computer systems. This Technical Memorandum surveys current research areas which we believe will contribute to distributed object management technology, and which help define its scope. This memorandum also presents an overview of the research issues contained within these research areas, some of which will be addressed in the DOM project. --------------------------------------------------------------------------- Table of Contents Page 1. Introduction and Background 1 1.1 Introduction 1 1.2 Background 3 1.3 Possible Applications of DOM Technology 12 1.3.1 Integration of Heterogeneous Components 12 Using Distributed Object Technology 1.3.2 Integration of Knowledge-Based Processing 20 Using Distributed Object Technology 2. Survey of Component Technologies 23 2.1 Programming Languages 23 2.1.1 Object-Oriented Programming Languages 23 2.1.2 Knowledge Engineering Tools and 29 Knowledge Representations 2.1.3 Declarative Programming Languages 31 2.1.4 Multiparadigm Languages and Systems 34 2.2 Programming Language/Database Interfaces 35 2.2.1 AI/Database Interfaces 35 2.2.1.1 Prolog/Database Interfaces 36 2.2.1.2 Knowledge Engineering Tool/ 37 Database Interfaces 2.2.2 Persistent/Database Programming Languages 38 --------------------------------------------------------------------------- Page 2.3 Database Management Systems 40 2.3.1 Object-Oriented Database Management Systems 40 2.3.2 "Extended" Database Management Systems 48 2.3.3 Distributed Database Management Systems 51 2.4 Operating Systems 53 2.4.1 Network Operating Systems 54 2.4.2 Distributed Operating Systems 55 2.4.3 Database Operating Systems 56 2.5 Heterogeneous/Distributed System Architectures 57 2.6 Standards 60 2.6.1 Data Storage and Exchange Standards 60 2.6.2 Data Definition Standards 61 2.6.3 Protocol Standards 62 2.6.4 SAA 65 2.7 Distributed Artificial Intelligence 67 3. DOM Technical Issues 68 3.1 Object Models 68 3.1.1 Modeling Object Movement and Storage 70 3.1.2 Modeling Object Concurrency and Sharing 75 3.1.3 Integrating Multiple Component Models 80 and Interpreters --------------------------------------------------------------------------- 3.1.4 Other Issues Relating to Object Models 85 --------------------------------------------------------------------------- Page 3.2 Distributed Object Management 88 3.2.1 Support for Persistent Objects 89 3.2.2 Shared Distributed Object Management 97 3.3 System Architecture 101 3.3.1 Strawman Architecture 101 3.3.2 Location of Method Execution 104 3.3.3 Internal Components of DOM 106 3.3.4 Requirements of System Operation 107 3.4 System Security 108 3.5 Applications and Methodologies 112 4. Concluding Remarks 115 5. References 116 Appendix A: Some Representative Distributed Operating System Projects 130 --------------------------------------------------------------------------- 1. Introduction and Background The Distributed Object Management (DOM) project is currently conducting research into "distributed object management" technology, which we believe will provide a significant step towards interconnectivity and interoperability among heterogeneous computer systems. This Technical Memorandum surveys current research areas which we believe contribute to distributed object management technology, and which help define its scope. This report also presents an overview of the research issues contained within these research areas, some of which will be addressed by the DOM project. The purpose of this memorandum is to document our understanding of the range of technical subject matter within the general subject area of distributed object management. This documentation will help us in our identification of specific research issues within this general area to actively pursue, since our group cannot possibly pursue all these issues simultaneously. 1.1 Introduction Today, computer usage is expanding into all parts, and all functions, of large organizations such as GTE. This can be seen in the widespread appearance of powerful personal computers for desktop use, and powerful workstations for more specialized uses. Such computers are becoming commonplace in routine business functions of all kinds. As the result of the continuation of this trend, information processing environments of the future will consist of a vast network of heterogeneous (dissimilar) computers (from mainframe to personal), information intensive applications, and data resources (files or databases). With the appearance of increasing numbers of heterogeneous information resources, including processors (hardware), process descriptions (programs), and data resources (files, databases) within large organizations, there are corresponding requirements to manage these resources, and allow their use in unanticipated combinations to address new requirements (create new "systems"), so as to obtain the greatest possible leverage from available resources. We see these requirements being met in two general phases. The first phase is interconnectivity. Current computer systems are often disjoint, and unable to communicate with other systems. Two or more systems are interconnected if they can exchange messages. There are increasing demands for interconnectivity (for example, increasing usage of local area networks) to enable different people, functions, or organizations to communicate, and to share data and processing resources. However, interconnectivity only guarantees communication. The user (human or computer system) of a computer system on a network must still understand the distinct interface of that particular system in order to use it. A more ambitious goal is interoperability. Two or more systems are interoperable if they can interact to jointly execute tasks, ideally functioning as intelligent agents concerning their computing capabilities. Distributed query processing is a very simple example of interoperability in the domain of database management, in which a global access plan is developed that attempts to optimize use of individual database systems attached to a network. Interoperability provides the maximum benefit in making effective use of existing computing resources to perform new tasks, and in integrating new computing resources to support changing requirements. --------------------------------------------------------------------------- Effective and efficient interconnectivity requires considerable generality of interface capabilities between information systems. These needs are not fully addressed by current communications or distributed systems technologies. The heterogeneity of existing systems constitutes a major barrier to addressing these needs. The heterogeneity that must be addressed comes in many forms, including: ? Hardware ? General types of systems that must interact: database management systems (DBMSs), knowledge-based systems, operating systems, etc. ? specific systems within these general types, e.g., DBMSs and their languages: DB2, Adabas, Oracle, IMS, IDMS; SQL, QUEL, ... ? Programming languages: conventional languages (FORTRAN, COBOL, Pascal, Ada, C, Lisp), object-oriented languages (C++, Smalltalk, CLOS), etc. ? Data types: integers, reals, strings, conventional record structures; voice, image, graphics data, formatted text (embedded font information), arbitrary mixtures. Effective and efficient interoperability requires intelligent mediation between information systems, some of which may be intelligent themselves. These needs are only beginning to be addressed by research. Many applications would benefit from fast, efficient access to large information systems that manage information of the type they need. A specific example of interest to us is interaction between knowledge-based systems (such as expert systems) and database systems. Knowledge-Based Systems should be able to provided value-added reasoning over large databases. Currently, this requires ad hoc interfaces to be built. Neither class of systems provide general purpose means to build such interfaces. The Distributed Object Management project is conducting basic research into the development of technology to support requirements of interconnectivity and interoperability. As one of its specific tasks, the DOM project is developing a Distributed Object Manager (DOM) component to facilitate efficient interconnectivity between Knowledge-Based Systems and DBMSs. Such components will be a significant step towards generic technology that facilitates interconnectivity between any application and a remote database. 1.2 Background We can characterize systems architectures in terms of a rough (not necessarily linear) progression from current disjoint systems through a number of stages as follows: Disjoint: Dissimilar systems that do not exhibit interconnectivity. Failing: lack of communications capability between systems. Ad Hoc Interconnection: Dissimilar systems that are interconnected via ad hoc means (i.e., coded for the specific systems). Failing: lack of general purpose solution, hence related inefficiencies. --------------------------------------------------------------------------- Encapsulated: (Shared protocol): Each system is encapsulated, and a "published" protocol for accessing it is provided in terms of a common language. The interconnection is established via the protocols. Failing: No particular knowledge by one system of how to optimally use other systems. Shared Data: Systems interact by shared common data formats (e.g., communication between Apple Macintosh software via the "Clipboard"). This differs from ad hoc interconnection, because the interconnection is not hand coded for each system. It also differs from encapsulated because the systems interact via shared data, rather than shared protocols. Failing: systems are restricted to the common data formats known to other systems, and particular pairs of systems may not share the "right" data format, thus requiring possible loss of information. Global Manager: A global (network) manager is provided that coordinates execution of tasks involving multiple system components (e.g., applications and databases). With knowledge of the capabilities and protocols of the available components, it decomposes the task into subtasks, calls the component systems to execute subtasks, monitors the subtasks, performs any required compensating actions, and provides the requesting component with the result. Failing: As the number of components increases, the global object manager becomes more and more complex and becomes a bottleneck (processing, communications, knowledge, etc.) in the system. Also, the solution is centralized, which complicates the addition and modification of component systems. Cooperative Agents: The functions of the global manager are distributed so that each system has a "negotiator" that does not necessarily know about all systems in the network but can negotiate and interact to find out how to execute the task at hand. There has been and continues to be increasing pressure to move along this progression. Our observation is that when the problem of integration is restricted to data, this progression models the development of database technology. Since our approach is based somewhat on this progressive development of database technology, we will review it here to describe the basis of the DOM approach. Centralized Database Management Systems The development of the database management system created a basic change in overall system architectures, as shown in Figure 1.1. This represented a move from a disjoint approach, through an approach involving ad hoc interconnection, to a shared data/global manager approach. Pre-DBMS systems involved disjoint applications, accessing application-specific file structures. While these applications were often effective in dealing with their intended tasks, the overall approach suffered from a number of shortcomings. Applications requiring access to the same data were forced to duplicate it, causing problems in maintaining the consistency of the data. Applications were forced to contain, often with considerable redundancy, code for data staging, and file structure maintenance, in addition to application-specific code. There was no way to handle requests for unanticipated combinations of data that might reside in more than one application file, short of writing a new application. Finally, there was no easy way to exert management control over the entire collection of data residing in the various files (e.g., impose standards). These shortcomings were a primary reason for the development of the database concept. Early database systems were constructed by building ad hoc --------------------------------------------------------------------------- interconnections between existing files, but gradually the database management system was adopted, in effect, as a global manager for the collection of data. The database manager allowed centralization of much of the file access and file structure maintenance code. It also (necessarily) assumed responsibility for controlling data sharing among the applications (concurrency control) and recovery. It also provided a logical control point for exerting overall controls over the data (together with data dictionary/directory facilities). Object-Oriented Database Systems While the introduction of DBMSs was an important step in terms of integrating computer processing, there are a number of reasons why it does not address the full scope of the problem we have identified. One reason is that there are a great many forms of data that cannot be successfully stored in databases managed by today's DBMSs. While DBMSs have been successfully applied to the relatively simple data structures required for conventional data processing and other similar applications, the pre-DBMS situation, with separate applications and application-specific file structures, remains for such complex data types and applications as engineering data --------------------------------------------------------------------------- Application Application-specific processing Data staging File/access method maintenance File access processing ? ? ? ? ? ? Application Application-specific processing Data staging File/access method maintenance File access processing Applicationspecific file Applicationspecific file Before DBMS: With DBMS: Application-specific processing Data staging Application Application-specific processing Data staging Application ? ? ? Database DBMS File/access method maintenance File access processing Concurrency control Recovery Figure 1.1 From Separate Applications to the Database --------------------------------------------------------------------------- (CAD, software engineering), artificial intelligence (knowledge representations), and text, image, and voice data. There are a number of reasons for this situation. First, the data types are more highly structured than the relatively simple data structures for which DBMSs have been generally designed. Second, access patterns to this data by applications are less predictable, and thus the query processing strategies used in today's DBMSs are not applicable. Third, the sharing protocols used in DBMSs, which generally involve guaranteeing the appearance of exclusive access to data, are too restrictive and inefficient for the new applications. Finally, many of the new applications are highly interactive. A conventional centralized DBMS acting as a passive "server" in these applications can become a performance bottleneck This situation creates problems similar to those that existed prior to the introduction of DBMSs, such as no integration of database and non-database data, lack of overall control mechanisms, and lack of DBMS support facilities for the new data types. The DBMS research community recognized the problems of supporting new data types some time ago (see, e.g., [LORI82]), and major research was conducted to push DBMS technology toward solutions to these problems. This has resulted in the current general type of proposed solution, the Object-Oriented DBMS (OODBMS), illustrated in Figure 1.2. More details of OODBMS technology will be provided in later sections. However, the general idea is that an OODBMS stores, not data, but "objects": encapsulated combinations of data structures together with associated procedures ("methods"). This allows instances of arbitrary data types to be stored within the "database". The OODBMS provides data integration, overall control, and DBMS support facilities for all types of objects. Applications using any of these types can then communicate via the shared database. The introduction of OODBMS technology will be a further important step in integrating computer processing. However, OODBMS technology is in its infancy, and does not yet provide required functionality in a number of areas. For example, object-oriented concurrency (control of data sharing) and recovery, efficient storage structures for general objects, and optimization of requests involving general method processing, among many others, are open areas of research in OODBMS technology. The DOM project will have to investigate some of these issues. Moreover, there are important issues not yet addressed by this technology. --------------------------------------------------------------------------- Multimedia Data Access Knowledge-based Processing Backend Data/Knowledge Server Application-specific processing Data staging Application Application-specific processing Data staging Application ? ? ? Database File/access method maintenance File access processing Concurrency control Recovery OODBMS Data Type Processing Data Type Processing ? ? ? Data and data-type-specific processing encapsulated as objects Figure 1.2 The Object-Oriented DBMS Heterogeneous Distributed Database Systems One issue not addressed by OODBMS technology (and conventional DBMS technology in general) is that of integrating the different database systems that have been created within organizations with the advent of database technology (and might be created in the future with the use of different OODBMSs). The existence of multiple heterogeneous database systems within organizations models that of the independent applications and files described earlier, except that instead of separate files, each with its own application, there are separate databases, each with its own cluster of applications. However, similar problems of data redundancy and inflexibility in the face of new applications exist in both cases. One approach to dealing with this problem has been the heterogeneous distributed database system (HDDBMS). A HDDBMS is a set of components designed to --------------------------------------------------------------------------- integrate existing DBMSs and their associated databases. Examples include Multibase [LAND82], and GTE Laboratories' CALIDA project (described further in Section 2). The general approach taken by many of these systems is illustrated by the Multibase component architecture shown in Figure 1.3. Local Data Interface Request/Data Translation Database Local DBMS Local DBMS Database Global Data Manager ? Global/Local Request Translation ? Optimization ? Result Integration Local Data Interface Request/Data Translation Local Query LanguageLocal Query Language ? ? ? ? ? ? Global Query Language (Daplex) Global Query Language (Daplex) ? ? ? Application end user Global Request Local Request Local Request Global Query Language (Daplex) Figure 1.3 A Heterogeneous Distributed DBMS In this approach, a Global Data Manager (GDM) component is responsible for creating a global view of the collection of heterogeneous databases for use by applications and end users. Requests expressed in terms of this global view are --------------------------------------------------------------------------- then translated by the Global Data Manager into a plan of requests on the individual local databases containing data needed in satisfying the request. Each local request, expressed in a system-wide protocol, is sent to the Local Data Interface (LDI) component responsible for that local system. The LDI is then responsible for translating the request into the language used by the local DBMS, accepting the response from the local DBMS, translating it into the system-wide protocol, and returning the response to the GDM for further processing, or integration into the final result. These systems (today research prototypes only) allow queries over multiple databases to be expressed without the user having to deal with the complexities of multiple database languages or communications protocols. They (at this time) generally do not permit database updating, however. Distributed Object Management The HDDBMS provides an approach to deal with integrating databases within an organization. Moreover, this approach is becoming increasingly feasible as the amount of actual heterogeneity among DBMSs is being reduced somewhat by the widespread adoption of the SQL standard for database languages. However, there are still a number of problems remaining to be addressed. 1. Neither the HDDBMS nor the OODBMS support true integration of processing, as opposed to data, i.e., the creation of unanticipated combinations of processing components is not supported. In the case of the HDDBMS, this is because it only provides for integrating data. In the case of the OODBMS, some integration of processing, namely that in the procedures associated with the objects, is supported. However, processing associated with applications is not integrated (as can be seen in Figure 1.2). Moreover, a single OODBMS does not allow integration of processing defined in multiple object models, only that supported by the given OODBMS. 2. Neither the HDDBMS nor the OODBMS are designed to support advanced forms of interoperability, such as cooperation in staging data between a data/knowledge base and an application, or other forms of cooperation among components. To deal with these problems, we are proposing a revised approach, termed Distributed Object Management, which can be viewed as a generalization of the OODBMS and HDDBMS as described above. This can conceptually be viewed as shown in Figure 1.4. --------------------------------------------------------------------------- ? ? ? Application/ Data Type Processing Application/ Data Type Processing DOM Concurrency Control Staging Recovery Type Mapping ? ? ? Application/ Data Type Processing Application/ Data Type Processing DOM Common Object Protocol DOM Concurrency Control Staging Recovery Type Mapping DOM Concurrency Control Staging Recovery Type Mapping Data/Object Repository DOM Concurrency Control Staging Recovery Type Mapping Data/Object Repository ? ? ? ? ? ? Figure 1.4 Distributed Object Management In this architecture, new components called Distributed Object Managers (DOMs) are used to integrate heterogeneous components into a single system. The DOMs do this by mapping the data and processing resources of the system into a single, system-wide "object space", defined by a common object model called the DOM Common Object Protocol (DCOP). The data for the objects in this object space comes from data located on attached database components (the "Data/Object Repositories" in Figure 1.4) or from data associated with specific applications (such as the knowledge bases of expert systems) and located on other attached components, such as workstations. The object procedures (methods) associated with these objects come from the functions associated with any attached system component (e.g., specific applications, database systems). A component attached to the network can, through its DOM, interact with the resources of the entire network as if it were a single object space, ignoring the location of the data and methods --------------------------------------------------------------------------- making up the objects (they may be in different locations), and any movement of object data and methods between components that might be necessary in executing methods on objects. Initially, this mapping of data and processing resources into an object space will only involve existing components not designed to function in this type of environment. As such, the mapping may be somewhat difficult, and less than optimal in its performance. However, with increasing use of object technology in components, with increasing modularity of individual component architectures, and with increasing development of components designed to function within such integrated architectures, integration of components will become easier, and performance will greatly increase. At the same time, the capabilities of the DOMs themselves will increase, taking greater advantage of system-oriented knowledge to solve more difficult tasks. Knowledge incorporated in DOMs will include: ? knowledge about the individual components in the network, including their capabilities and requirements, enabling DOMs to, for example, pre-fetch data from remote locations to an application in time for the application's actual request to be handled locally. ? knowledge about how to cooperate both with each other, and with increasingly-intelligent subcomponents of attached components to further improve performance and reliability. This approach is intended to provide a number of desirable characteristics: 1. It provides flexible access to arbitrary combinations of system resources (processing as well as data) in support of unanticipated requirements. 2. It provides a common protocol for component interaction (the DCOP). 3. It supports a variety of object granularities, ranging from complete existing (and possibly non-object-oriented) components , e.g., CAD tools, interfaced via shared files, to individual instances of data types (where components are designed to interact at that level). This allows integration to be accomplished at whatever level is appropriate to the particular system being developed. 4. It supports various component coupling styles. Control can be logically centralized or distributed. Attached components can be unmodified and autonomous if desired. Initial developments can be relatively kludgey, using existing technology, while at the same time providing the framework for tighter coupling and cooperation between components as technology evolves and requirements demand. 1.3 Possible Applications of DOM Technology This section gives a few examples of how distributed object management technology, of the type we are investigating, might be used in particular applications. The specific applications illustrated are: ? supporting generalized distributed DBMS requirements --------------------------------------------------------------------------- ? integrating different tools and applications for use in combination ? providing transparent object store to AI systems These applications are far from "ivory tower". There is a great deal of interest in applying object technology to many such applications, and, as Section 2 will show, a great deal of research is ongoing in related technology areas. 1.3.1 Integration of Heterogeneous Components Using Distributed Object Technology Object-oriented approaches provide a very natural framework for use in integrating heterogeneous components. As a design approach, thinking of the components to be integrated as objects allows a common design methodology to be applied to objects at all levels of granularity. Whether the objects to be integrated are entire systems, or individual object classes within a single system, the approach has a number of important effects: ? It focuses attention on the definition of the message protocols that give access to the object behavioral semantics, as implemented by the object methods. In a distributed environment, development of such protocols and support for them would have to be done anyway, whether the components were heterogeneous or homogeneous. ? It focuses attention on the definition of mutually understandable message protocols so that the objects can communicate. ? It directs attention away from arbitrary syntactic differences among the components (e.g., among the query languages if the components are heterogeneous database systems). As an implementation approach, the encapsulation provided by the object paradigm allows internal details of individual components to be concealed. Moreover, the object provides a framework for the incorporation of procedures required in inter-object communication to be incorporated directly in the objects, such as procedures for data conversion. Also, the method inheritance concept (illustrated below) provides a valuable facility for "homogenizing" heterogeneous components. The examples below illustrate these points. --------------------------------------------------------------------------- Heterogeneous DBMSs Figures 1.5 and 1.6 show the steps involved in integrating heterogeneous DBMSs using an object-oriented approach. Figure 1.5 shows "objects" defined to encapsulate each of three entire heterogeneous DBMSs. The object encapsulation allows the operations provided by each DBMS to be invoked by messages from other objects. Clearly, nothing very exciting has happened so far with regard to integration; all that has been done is to establish communications among the components. Since the systems implement different data models, a given system will be unable to understand messages sent by the others. This illustrates the fact that thinking about, or implementing, components as objects is not an automatic solution to any problem. The design of the objects is an important consideration too. method code method code method code method code DBMS relational select start transactiontransaction end update method code method code method code method code DBMS find next find owner connect store CODASYL method code method code method code method code DBMS other model update change metadata rollback retrieve Figure 1.5 Heterogeneous Database Systems Encapsulated As Objects Figure 1.6 illustrates the second step in the process, which involves defining (and implementing) object methods that implement messages whose semantics are mutually understandable by the various components. The approach is basically to surround the DBMS with a layer of software that implements a common interface, using the object concept to encapsulate this software. In this case, the common interface has been chosen to be relational, and to implement the relational select operation on all systems. This requires no translation on the relational system, but requires a translation method to be implemented on the other systems. (This --------------------------------------------------------------------------- "translation method" may, of course, be a very substantial piece of software if it is required to implement a complete relational interface on another form of DBMS!) A component playing the role of the translation method is frequently found in heterogeneous distributed DBMS architectures, an example being the Local Data Interface of CCA's Multibase system described in Section 1.2. The point is thus not to claim that the object-oriented approach provides entirely new capabilities in this case, but rather to illustrate that it provides a natural way to think about how they fit into an overall design approach, as well as to show how, as an implementation approach, object-orientation provides a direct way of implementing these required capabilities. Figure 1.7 shows the definition of objects at a smaller level of granularity. In this case, a part object class has been defined on each of two heterogeneous DBMSs. Note that while both classes implement a part_number method, the other methods are different. In the case of the display and show methods, the semantics are the same, but the names of the methods are different. In the case of the other methods, the semantics are different as well. This makes it difficult to integrate parts from the two systems. For example, without additional system facilities, the user would have to know what system a part came from in order to know how to display it (i.e., whether to issue the command show or display). Figure 1.8 shows the use of the inheritance mechanism of an object-oriented model to define a generic type of part object class that permits integration of the two part object classes. The generic object class is defined as a supertype of the existing object classes, and as having methods that correspond to the methods possessed in common (at least semantically) by the two existing object classes. Once this definition has been completed (and assuming the underlying support mechanisms exist), the system will support a generic part object class that consists of the union of the parts of the two underlying object classes, and that uniformly responds to the part_number operation. This technique of using inheritance to integrate heterogeneous object classes has also been used in CCA's Multibase system [DAYA84b], utilizing the inheritance capabilities of its Daplex data model. Figure 1.9 shows the use of object encapsulation to implement the generic part object class defined in Figure 1.8. The translation method that implements the part_number operation on the generic part object class is effectively null, since this operation is supported by both underlying part object classes. However, the translation method that implements the output operation must determine whether the display or show operation should be sent to the underlying part. --------------------------------------------------------------------------- method code method code method code method code DBMS relational select start transaction end update transaction select method code method code method code method code DBMS find next find owner connect store CODASYL select translation method method code method code method code method code DBMS other model update change metadata rollback retrieve select translation method Figure 1.6 Integration of Heterogeneous DBMSs using Object Encapsulation --------------------------------------------------------------------------- display weight Part method code method code method code method code DBMS 1 part_number specification show Part method code method code method code method code massrotate DBMS 2 part_number Figure 1.7 Part Object Classes on Two Heterogeneous Database Systems display weight Part method code method code method code method code DBMS 1 part_number specification show Part method code method code method code method code massrotate DBMS 2 part_number Part method code method code part_numberoutput global Figure 1.8 Definition of Generic Part Object Class Using Inheritance Concept --------------------------------------------------------------------------- rotate show mass method code method code method code method code Part DBMS 2 part_number method code method code method code method code Part DBMS1 part_number weight specification display output part_number Part global translation method translation method Figure 1.9 Integration of Part Object Classes Using Object Encapsulation As in the previous example, the translation methods are effectively implementing what in conventional database technology would be called a view. Basically, a view consists of a set of data objects derived or transformed from stored data in the database, the purpose being to allow a user or application to "view" the data in a way that is more useful to it than the way the data is actually stored. Views are generally defined in database system using the facilities of the database's query language, but views defined in this way have a number of important limitations [KELL86]. Work such as [DAYA84b] in heterogeneous distributed database technology has established that integration of these systems is basically similar to a view mapping problem. By allowing arbitrary procedures to be integrated into the model as object methods, the object-oriented approach provides a convenient way to provide increased view mapping capability. While some level of these facilities can be provided in more conventional approaches, it is often difficult and clumsy to do. These examples illustrate that the object-oriented approach can be valuable in integrating heterogeneous systems (and data types), but it is not a panacea. The conceptual framework provided by the object-oriented approach must be backed up by implementation of facilities that support it. Moreover, protocol standardization and rationalization is vital, since without this objects may not understand the messages directed to them, or be able to direct messages to other objects in ap- --------------------------------------------------------------------------- propriate ways. Users and designers of object-oriented systems will still require considerable interface support, since they must now understand a large set of objects in order to make use of the system. Finally, research and experience is needed in realizing the object-oriented approach in a heterogeneous environment. Current research on object-oriented database systems is addressing some of these issues, but little work exists that combines both elements of object-oriented research and heterogeneous distributed DBMS research. Heterogeneous Tools and Applications The reality of both the system vision and many of the requirements we have identified is illustrated by the VHSIC Engineering Information System project [LINN86]. The project is a large-scale systems integration effort designed to support the engineering of integrated circuits for the Air Force. Overall, the project involves: Integration of VLSI (and software engineering) design tools Development of consistent methodologies (management, control) Development of consistent interfaces (workstations, users) Development of data exchange formats and protocols A major focus of the effort, however, is the design of an integrated information system that allows a degree of interoperability among heterogeneous design tools, editors of various types, databases, and other components that may be attached to the system. For example, it is desired that a user at a workstation be able to call up an engineering design from a design repository, and apply a sequence of design tools and checkers to it, without concern for where the various pieces of data making up the design, or the tools, may be located in the system, what processors are involved, etc. Moreover, the system is supposed to automatically lead users through predefined procedures for performing various tasks, coordinate the activities of different users involved in cooperative tasks, etc. The overall architecture of the VHSIC EIS is shown in Figure 1.10. The details are described in Section 2.5. However, the architecture has many features in common with the DOM architecture described in the previous section, including its use of a system-wide object space and associated common object model, and the implementation of this object space using a specialized Object Management System (which is actually distributed among the various network components, like the DOMs in our architecture). --------------------------------------------------------------------------- tool invocation services user interface services data exchange services Object Management System (OMS) OODL KERNEL distributed, heterogeneous data management services distributed OS services OS and Network Adapters Database Adapters Operating Environment System Services Operating System Services & Networking Communications Services Data Management Services Execution Services Input/Output Services Common Exchange Format: OODL User 1 User 2 Tool 1 External System Tool 2 tool adapter user interface service adapters editors query languages interface to services interface to services interface to services External System Interchange Format (compound document) CAIS 2.0 (+OODL) metadata SQL,OODL Figure 1.10 VHSIC EIS System Concept --------------------------------------------------------------------------- Still another example of these requirements, this time in a communications context, is the Bellcore IN2 Intelligent Network concept [BLOO86]. The concept is to provide enhanced services through the public telephone network. Features of the network include: ? wideband digital services ? user-customized service elements ? enhanced informational services (e.g., 800 services) ? open network architecture ? computer automation into the public network The need to provide an open network architecture and integrate the heterogeneous components providing the various services makes this network a natural application for DOM concepts. Specifically, the DOMs could be used to: ? "objectify" (encapsulate) externally-developed services ("service objects") for integration into the network ? provide a system-wide common object protocol (the DCOP) for invoking integrated services ? support definition of complex services in terms of existing ones by allowing the definition of sequences (or other control structures) of messages to these "service objects" in terms of the common object protocol. 1.3.2 Integration of Knowledge-Based Processing Using Distributed Object Technology In future information systems, knowledge-based processing will be important in a number of ways: ? providing knowledge-based application processing (e.g., expert systems) ? providing assistance to users and designers ? resolving differences in data semantics ? implementing advanced concurrency control mechanisms ? providing improved efficiency (through techniques such as "semantic query optimization") ? versioning, configuration management, and security Integrating this knowledge-based processing into a system object model could be useful for a number of reasons. First, the generality, flexibility, and extensibility provided by the object-oriented approach should be extended to knowledgebased processing as well. For example, it is reasonable to expect that, over the system life cycle, existing knowledge-based components will have to be modified, and new knowledge-based components added. Moreover, these knowledgebased components may use heterogeneous knowledge representation techniques, either because the different techniques are more adapted to specialized requirements, or because advances in technology create new knowledge representation techniques that are included in new components. It seems likely that object-oriented techniques for the integration of heterogeneous components can also be used for the integration of heterogeneous knowledge-based components. --------------------------------------------------------------------------- A second reason to integrate knowledge-based processing into the object model is that it enables the behavior of objects in the model to be derived from knowledgebased processing. In many cases, it may be irrelevant to outside objects whether the behavior of a given object is based on conventional processing, or on knowledge-based processing. The nature of the processing may thus be encapsulated within the object, and only the external behavior revealed. This provides a flexible way to integrate both conventional and knowledge-based components within the same system. Finally, integration of knowledge-based processing into the object model allows DBMS components to provide persistent object support for knowledge-based applications. It is anticipated that knowledge-based applications will increasingly require database support facilities, either because they are dealing with databasesized knowledge bases, or because the raw data they use as input to their processing is stored in databases so as to provide for access by other application programs. The coupling of knowledge-based and database systems is currently a very active area of research, and attempts have already been made to "looselycouple" existing knowledge-based and database systems (by embedding database calls where database data is required). However, it is believed that performance considerations will demand a much tighter degree of integration of knowledge-based and database processing than can be achieved by such loosecoupling techniques (see, e.g., [JARK84]). Research aimed at integrating knowledge-based processing with object-oriented database management will need to investigate a number of enhancements to object technology that increase support for knowledge-based applications. Such enhancements include, among many others: ? Capturing heterogeneous knowledge-representations within a common object model to enable knowledge-based applications to use object-oriented database systems as persistent storage. ? Support for condition monitoring over the database (the active DBMS paradigm). This enables a knowledge-based application to download situationaction (production) rules to the DBMS, so that the DBMS can notify the application of "interesting" situations in the database (a simple version of this capability is described in [STON86a]). The action triggered by the condition becoming true could also involve more complex processing, including uploading of data from the database into an application's workspace, for knowledge-based analysis of the details of the situation. ? Representation of plans to support time-constrained scheduling. This is important to enable the DBMS to give priority to processing that might be extremely urgent, or to take compensating action when the time requirements of applications cannot be satisfied. Work in these areas can build to some extent on existing work in multiparadigm knowledge programming systems, such as LOOPS [STEF86b], which integrates conventional, object-oriented, and rule-based programming styles with condition monitoring (triggers, active values). Object-oriented approaches also identify other required research directions. For example, to take full advantage of the ability to support user-defined types, required implementation support, such as extensible query optimization facilities, --------------------------------------------------------------------------- must be present in the underlying system. Methods of defining procedural information within object-oriented data models also require investigation. The ability to define procedures in conventional programming languages and invoke them from the object model is one approach, but in general we expect "tighter coupling" of procedural and conventional DBMS capabilities, so as to support query optimization and concurrency. Adding persistent objects to an object-oriented programming language, as in the GEMSTONE DBMS [MAIE86], is a possible approach. However, this does not address the need to support multiple programming languages. Architecturally, this raises the issue of where one draws the line between "database system" and "application program" in such a framework (or whether such lines are still appropriate). Optimization to achieve good performance in such architectures is a challenge, since it involves closely integrating DBMS and programming language forms, intelligent staging over a large "object memory", and dealing with complex and possibly large objects. Ultimately, this may lead to new organizations of "operating system", "programming language", and "DBMS" facilities, in order to support these advanced requirements. These and other issues are described in more detail in Section 3. --------------------------------------------------------------------------- 2. Survey of Component Technologies This section consists of a number of individual subsections describing key component technologies which will contribute to the Distributed Object Management project. In each subsection, the component technology will be described, and its relationship to the DOM project outlined. Most of the technologies listed here are relevant because elements of them will be used in any heterogeneous distributed system that might be constructed. In addition, in most cases explicit object-oriented or distributed variants of these technologies have actually been developed. As such, examination of the interaction of these technologies with DOM goals becomes important. The description of each technology will necessarily be brief, since a detailed survey of each technology is beyond the intended scope of this report. However, an attempt has been made to cite sufficient references, in some cases themselves surveys, to enable the interested reader to follow up specific topics of interest in more detail. 2.1 Programming Languages Programming language technology is a relevant technical area for the DOM project for a number of reasons. A primary reason, of course, is that many of the fundamental developments providing background for our work have been developed in the context of programming languages. This includes database technology which, while considered in a separate section in this report, had many of its roots in programming language developments. A more specific reason for our interest in programming languages is that they provide the basic mechanisms for specifying processes, a crucial aspect in the definition of any computer system. While general programming language technology is relevant to our work, we will be concentrating our attention on the specific subclasses of that technology identified in the following sections. 2.1.1 Object-Oriented Programming Languages The original notion of objects is generally attributed to the Simula programming language [DAHL66]. However, object-oriented programming did not emerge as a new programming paradigm until the development of the Smalltalk language [GOLD83]. At the present time, many object-oriented languages have been developed, and some are in wide use. The DOM project assumes the use of the object paradigm as part of its basic methodology. Since the object paradigm was originally developed in the context of programming languages, the technology of these languages is highly relevant to the DOM project. Of particular interest are the various object models embodied in these languages, and the various run time systems that have been developed to support them. In a pure object-oriented language or system, all information is represented in the form of objects. An object is a self-contained entity which encapsulates: ? its own private data (called instance variables in the Smalltalk object-oriented programming language) ? a set of operations (sometimes called its protocol) These operations constitute the object's external interface to the rest of the system. --------------------------------------------------------------------------- In an object-oriented language or system, the conventional operator/operand model of computation, involving the use of separate procedures and data, is replaced by an object/message model. In the operator/operand model, a user (programmer) is given a set of data (operands), and a set of operators (functions) which take various combinations of operands as parameters. The user is responsible for determining which operations to apply to any data to be manipulated, and for making sure that the operands match the type requirements specified for the operations being called. Languages employing this model include C, Pascal, and Fortran. If the same type of function (say "print") must be performed on operands of different types, separate functions must be defined and employed, e.g., prnPoint(point) for data of type point, or prnRectangle(rect) for data of type rectangle. Some languages, such as Simula, Ada* , and CLU [LISK81], allow an extension of this approach, in which the programmer specifies an abstract operation name, and the compiler differentiates which specific routine to call at compile time, based on the type of the operand. For example, the programmer might write print(point), or print(rect), but the compiler would refer to a different procedure in these cases. In the object-oriented approach, all interaction with an object occurs through messages sent to the object requesting it to execute one of the operations in its interface. A computation is defined as a sequence of interactions among objects in the system. Message sending is a form of indirect procedure call. Instead of naming a procedure to perform an operation on an object, the user selects the object and sends it a message. A selector in the message specifies the specific operation to be performed. An object that receives a message is responsible (conceptually, at run time) for deciding how to respond to the message, using its own procedures (called methods) for performing the requested operation. These methods have the exclusive capability to manipulate the object's private data, and can also carry out other activities. When discussing the use of messages in an object model, it is important to distinguish between the use of message passing as a conceptual model for interaction among objects, and the use of messages as a method of communication between concurrent processes (possibly modeled as objects). This is because there are a number of important design issues that arise when there is actual concurrency among processes. Most of these issues can be safely ignored when there is no real concurrency. Some of these issues are illustrated in the ConcurrentSmalltalk language [YOKO86], which extends conventional Smalltalk with concurrent semantics. Some of these issues will be discussed in section 3 of this report. In most object-oriented systems, objects are defined as members of one or more classes. The class defines the internal form of every object of the class, as well as defining the protocol associated with objects of the class. New object classes can be defined as extensions of existing ones by a technique called inheritance. If object B is specified as inheriting from object A, this means that B will respond to the same messages as A, in addition to those defined specifically for B. The use of inheritance in object definitions assists in defining object protocols in a relatively standardized way. This, coupled with the use of messages, provides a facility called polymorphism. Polymorphism is the capability for the same message to elicit a different (but semantically similar) response depending on the class of the receiving * Ada is a trademark of the Department of Defense (Ada Joint Program Office) --------------------------------------------------------------------------- object,. This facility enables a program to treat objects from different classes in a uniform manner. Object-oriented languages have also generally (but not always) associated with certain specific implementation techniques, namely the dynamic binding of messages to method code, and automatic storage management, in the form of garbage-collection. In Smalltalk, methods are not called directly by name, but indirectly at run time via a dispatch table associated with the object class. If the method is not found there, the object's superclass in the inheritance hierarchy is searched, and so on upward until the root class of all objects is found. If the message is not found there, an error is reported. This allows a great deal of the flexibility generally associated with object-oriented programming, but adds additional run time overhead that can adversely affect performance. In other object-oriented languages, such as C++ [STRO86], a more static, compile-time binding is used, trading some flexibility for performance. In object-oriented languages, relationships between objects are represented by pointers to related objects, and in a pure object-oriented language like Smalltalk, values are almost entirely replaced by object pointers. Garbage collection is felt to be important in some object-oriented languages in order to guarantee the safety of object pointers due to the highly dynamic nature of object creation and deletion. In these languages, there is no way to explicitly delete an object. Rather, objects are garbage collected when they are no longer referenced by any other object. Again, however, other object-oriented languages, such as C++, prefer to trade some safety for improved performance, and use explicit object deletion operations rather than garbage collection Figure 2.1 illustrates some simple objects in an object-oriented model. The top left object represents a Part object class that might be defined for a CAD application. The object class has display, weight, specification, and part_number methods. The top right object represents a Part object (instance), with its associated method calls and instance variables. The bottom left object represents the object class for a specialized type of Part object, a 3Dsolid object. --------------------------------------------------------------------------- Object Classes Object Instances (method inheritance) display weight aPart instance variables part_number specification display weight specification intersection:anotherPart instance variables part_number a3Dsolid anotherPartunion: display weight Part method code method code method code method code specification part_number anotherPart intersection: method code method code 3Dsolid anotherPart union: Figure 2.1 Object Classes and Objects in an Object-Oriented Model The 3Dsolid object class defines two additional methods that apply only to 3Dsolid objects, union and intersection operations. When directed at a given 3Dsolid, these operations take another 3Dsolid object as an argument, and return the 3Dsolid that represents the union or intersection, respectively, of the argument object and the given object. Only the two new methods are defined for object class 3Dsolid. However, because it is a specialization of object class Part, the 3Dsolid object (instance) on the bottom right is shown as inheriting all the method calls that apply to Part objects, together with the specialized ones defined for 3Dsolid objects. A number of advantages are generally cited for object-oriented programming: 1. Defining a system in terms of objects facilitates the construction of software components that closely parallel the application domain, thus assisting in the design and understandability of systems. 2. The use of objects and messages encourages modular design, since the implementation of one object cannot depend on internals of another, only on how they respond to messages. In addition, because the private information of an object --------------------------------------------------------------------------- can only be accessed by the methods of the object, modularity is reinforced, and software can be made more reliable. 3. The use of classes and inheritance provides a simple and expressive model for the relationship of various parts of the system's definition, and also assists in making components reusable or extensible in the construction of revised or new systems There has been a great deal of debate about what facilities a language or system must have in order to make it "object-oriented", and object languages differ greatly, even in the fundamentals described above. Useful surveys of object-oriented language principles, and the variants that exist among the various languages, can be found in [MICA88, STEF86a, STRO88, YONE87]. In addition, collections of papers that illustrate the scope of object-oriented technology in general can be found in [MEYR86, MEYR87, SHRI87a]. The following paragraphs discuss a few (by no means all) important variations found in object-oriented languages. One form of variation is whether there is a distinction made between classes and instances. Most object languages make such a distinction, since they anticipate that instances will greatly outnumber classes (as in database systems and most programming languages). In this situation, the class can be used to retain information common to all instances (such as method code), saving considerable storage. However, some object-oriented languages do not distinguish between classes and instances. For example, the KEE knowledge representation system (see section 2.2) does not, nor do the actor languages (see below). Another form of variation is the form of inheritance defined in the language. As noted above, inheritance is the concept used to define objects that are similar to other objects. Inheritance makes it possible to declare that certain specifications are shared by other parts of the program, and facilitates extending and redefining programs. Some object-oriented languages, such as C++, define inheritance as a strict hierarchy. In this case, an object class is defined in terms of a single superclass. The subclass modifies the superclass by adding or substituting definitions. Other objectoriented languages, such as Loops [BOBR86] and the Common LISP Object System (CLOS) [KEEN88] currently being developed for Common Lisp, permit multiple inheritance, in which a class can be defined as a subclass of more than one class (for example, a houseboat can be defined as a subclass of the classes house and boat. When multiple inheritance is permitted, there can sometimes be conflicts as to which method is to be invoked when a given message is received. The various systems use different means to determine this. Actor languages (mentioned above) represent a particular variant of the objectoriented paradigm. The actor model of computation has been under development for over a decade, and was motivated by the idea that trends in VLSI will lead to wide availability of computers with very large numbers of relatively small processors. The classic paper on this approach [HEWI77] describes all computation in terms of various patterns of message passing among entities called actors. As in other object-oriented languages, actors encapsulate procedural and declarative information into a single entity. In the actor model, systems are composed entirely and uniformly of actors, just as systems in Smalltalk are composed uniformly of objects. However, in the actor model, each actor is active in a manner that is completely independent of all other actors, and also all the actions taken by an actor on receipt of a message are concurrent. The actor model views computation as inherently concurrent and extremely fine-grained, and is intended primarily to support large-scale concurrent symbolic computations. --------------------------------------------------------------------------- As mentioned above, the actor model does not distinguish between instances and classes. Another variation exhibited by the actor model is that it substitutes a facility called delegation for the inheritance found in other object-oriented languages. Delegation is based on the idea that any actor that "does not know how" to respond to a message should have one or more actors to which it can delegate or pass the request onward for processing. It can be seen that this is can be viewed as a message-based way of accomplishing the same thing as inheritance, since passing a message on to another actor in deletion is in a sense similar to passing the message upward in a class hierarchy in inheritance. A more detailed comparison of these two mechanisms can be found in [STEI87]. Further information about the actor model can be found in [AGHA87]. While a few object-oriented languages have been designed from scratch, such as Smalltalk, Trellis/Owl [SCHA86], and Eiffel [MEYE86], many of them are hybrid languages, i.e., conventional languages with object-oriented facilities added to them. Examples of these include extensions to C such as Objective-C [COX86] and C++, extensions to Pascal such as Clascal and Object Pascal [SCHM86], and extensions to Lisp such as Flavors [MOON86], Loops, and CLOS . Objectoriented extensions, or ways of using an object-oriented approach, have also been proposed for Prolog [RETT87c, ZANI84], and various production rule systems [MCAR84]. A number of these hybrid object-oriented languages are available on microcomputers [RETT87b,SCHM86]. Advantages sometimes cited for using a hybrid language are the ability to choose between an object-oriented approach and a conventional one, the ability to make use of existing software libraries, the ease of learning by programmers familiar with the base language, and the ability to choose between a method and a conventional subroutine call (which is sometimes more efficient). Finally, it is worth mentioning the HyperTalk language of Apple Computer's HyperCard application [GOOD87]. This is a relatively high level object-oriented language which, while perhaps not as computationally-complete as a conventional programming language, provides an English-like way of programming customized facilities in HyperCard. HyperTalk and HyperCard are object-oriented in the classic sense, with "objects", "messages", and "inheritance". The approach taken in HyperTalk might be a useful model in constructing relatively high level objectoriented languages for writing scripts in terms of high level functions defined in more conventional languages. 2.1.2 Knowledge Engineering Tools and Knowledge Representations Knowledge Engineering Tools, also sometimes referred to as "expert system shells", are software systems that support the development, execution, and maintenance of knowledge-based systems (KBSs), such as expert systems [METT87]. These tools are based on previous knowledge representation mechanisms, usually built on top of Lisp, that were developed to assist the process of KBS development (and the relationship of these tools to programming language extensions is the main reason why they are being discussed together with programming languages). Representative examples of these tools include: ? Automated Reasoning Tool (ART), Inference Corporation ? Knowledge Engineering Environment (KEE), IntelliCorp ? KnowledgeCraft, Carnegie Group Inc. --------------------------------------------------------------------------- ? S.1, Teknowledge Inc. These tools typically support multiple knowledge representation and inferencing paradigms, hypothetical reasoning, truth maintenance, object-oriented programming, extensive debugging aids, and graphic interfaces. This is a relevant technology to the DOM project for several reasons. First, one of the intended goals of the DOM project is to support the requirements of KBSs, and an examination of the technology of their supporting environments is important in understanding these requirements. Second, these tools illustrate the integration of multiple programming and knowledge representation and processing paradigms, and the integration of heterogeneous systems involving such paradigms is another goal of the project. Finally, the knowledge representations used in these tools often represent interesting variations of object models that should be studied in developing the object model to be used in the project. At a minimum, commercial knowledge engineering tools support the use of rules for knowledge representation. Rules provide a modular and uniform approach to knowledge representation, and are relatively simple to learn and use. As rule-based systems grow, however, they can become increasingly difficult to understand and maintain. As a result, several tools designed for large KBSs also provide other knowledge representation approaches. A number of tools support frames in addition to rules. For example, S.1 uses frames as templates for classes or logical groupings of entities. When a class instance is created, S.1 generates a frame that inherits the attributes (slots) of the class, but does not inherit any values. ART, KEE, and KnowledgeCraft support inheritance of slots and values as well as the ability to attach metaknowledge to slots. This metaknowledge can be used to constrain values, govern the actions of procedures attached to slots, and redefine inheritance behavior. ART, KEE, and KnowledgeCraft also support objects as a knowledge representation approach. Each object is represented by a frame with methods (procedures) attached to the frame's slots. Objects communicate with each other by sending messages. When an object receives a message, the message is interpreted, and the appropriate method (written in Lisp) is activated. Objects and message passing provide a natural way to represent entities in problems involving complex relationships. Tools for building large KBSs also typically provide multiple inference paradigms. Among the rule-based inference features that typically characterize these tools are support for both forward and backward chaining, sophisticated conflict resolution strategies (required when more than one rule may be eligible to fire), and the ability to compile rules for greater efficiency. Several tools furnish language constructs that allow specific procedural control to be specified. For example, S.1 supports a Pascal-like procedural language that can be used to create objects and assign values to their attributes, query users, and display results, and initiate backward chaining. ART provides constructs such as "for" and "while" that can be specified in rules to specify iteration. In addition, most tools allow the user to escape to external procedures (frequently in LISP), either to implement additional functionality, or to interface with other systems. --------------------------------------------------------------------------- As mentioned above, ART, KEE, and KnowledgeCraft support conventional object-oriented programming. In these systems, since methods are attached to specified slots in frames, methods are inherited in the same manner as conventional slot values. This inheritance allows methods to be shared by all objects that belong to a particular class. These same systems also support demons, a form of accessoriented programming. These demons are procedures that are activated as side effects when specified variables are accessed. Methods and demons are conceptually very similar, the chief difference being in the way they are activated. Methods are activated by a message, while demons are activated when their associated values are accessed. Most of these tools were originally developed for Lisp machines. However, these tools are increasingly appearing on more conventional hardware. This includes workstations, such as microVAXes, Suns, and Apollos, mainframes, and more "personal" microcomputers. At least two such shells exist for Macintosh computers, NEXPERT Object and Humble, the latter a shell written in Smalltalk. In addition, KEE is currently being ported to the Texas Instruments MicroExplorer add-on coprocessor board for the Macintosh II. Current KBSs typically operate in a stand-alone "consultation" mode. However, there is an increasing need to support features that allow KBSs to be integrated into traditional software systems, and interface with other components, such as database management systems, in a relatively seamless way. One factor that inhibits these objectives is the lack of adequate execution-time input-output facilities furnished by tools. Direct support of I/O facilities by current tools is primitive by most standards, although this is rapidly changing (this topic is discussed further in Section 2.2.1). In addition, in order for KBSs to be used effectively in applications on multiuser computing systems, tools must allow access to a number of operating system services. In particular, they will need the ability both to respond to interrupts and to be scheduled in multitasking environments that allow a number of cooperating processes to synchronize and share data. Such capabilities are not generally supported by current KBSs. 2.1.3 Declarative Programming Languages The so-called declarative programming languages represent a departure from the concepts present in conventional languages, such as Pascal and Ada. These imperative languages require the programmer to specify the manner and especially the sequence in which processing should occur. An important reason for this is that these languages are based on the use of variables that refer to specific storage locations. The value of these variables can change during the course of the computation, and hence the value at any point during the computation is based on the previous history of the computation. The declarative languages, on the other hand, are based on expressions defining mathematical relationships between mathematical variables. The mathematical wellfoundedness of the declarative languages is expected to convey certain benefits, such as greater expressive power, possibility of formal manipulation, and ease of parallel evaluation [DARL86]. Within the declarative languages, there are two prominent schools. The functional languages trace their origins to the lambda calculus and recursion equation systems, and are based on the definition of functions. Examples of functional languages --------------------------------------------------------------------------- include pure Lisp, FP [BACK78], and HOPE [BAIL87]. The relational languages are based on the definition of relations. The most prominent of the relational languages are the logic programming languages, notably Prolog. These languages are based on a procedural interpretation of the first order predicate calculus. Although both styles of language share most of the benefits of their declarative style, there are important differences between them, and each school has its enthusiastic advocates. In addition, there have been a number of attempts to integrate features from the two approaches, such as FUNLOG [SUBR84], LOGLISP [ROBI82], and EQLOG [GOGU84], and other forms of extensions, such as the extensions to support Prolog parallelism contained in Parlog [CLAR84]. A program in a modern functional language consists of a set of equations defining functions. For example, the following program computes the length of a list of elements of arbitrary type: --------------------------------------------------------------------------- dec length : list alpha -> num; length(nil) <= 0; length(X::L) <= 1 + length(L); (alpha is a type variable; :: is the list constructor function) Executing a functional language program involves reducing an expression using the equations as left to right rewrite rules until it contains no defined functions, on constants or constructor functions. For example, to evaluate the length of [1,2,3], the expression length([1,2,3]) would be evaluated. Mature functional languages are generally higher order, i.e., functions are first class objects, and can be passed as parameters and returned as values. Programs in a logic programming language such as Prolog consist of sets of clauses defining relations. The length program above would be represented in Prolog (taking liberties with the syntax) as: length(nil,0) <- length(X::L,N+1) <- length(L,N) Instead of a reduction process, logic languages use resolution. Executing a logic program involves submitting a goal statement involving variables, and the system attempts to discover all values of the variables that make the statement true. Although not necessarily true in every case, the following general differences are often cited between functional and logic languages: Typing: Prolog and other logic programming languages are generally untyped, whereas most modern functional languages are strongly typed, and allow polymorphism. Higher-order: Logic programming languages are first order languages, unlike most functional languages. Functional vs. relational notation: Output from each function in a functional languages is defined implicitly by construction on the right hand sides of the equations defining the function. The same definition in a logic language requires each output component to be named explicitly within clause heads. Extra variables must also be introduced within the clause body to represent what in the functional program would be expressed by function composition. Multi-mode use of relations: Because a logic program makes no commitment as to which variables in a relation are to be treated as inputs and which as outputs, a relation once defined can be used in several modes (e.g., driven either forward or backward). On the other hand, functional programs are committed as to which variables are inputs and which are outputs, and a separate function would have to be defined for each "direction". Non-ground outputs: Another capability found in logic programming but not in functional programming is that results produced need not be totally ground, i.e. they may contain variables. Determinism: Functional languages are deterministic, i.e., the forms that can be written are syntactically restricted so that they only denote proper many to one --------------------------------------------------------------------------- functions. Only one output value will be computed for any set of input values. Furthermore, certain safeness properties can be shown to hold for functional languages, so no searching is necessary when evaluating a functional program. In contrast, logic programming languages are inherently non-deterministic, and any query may produce several solutions. Furthermore, evaluating a logic program involves a search process, since at any point in the evaluation there may be several different ways of attempting to prove a subpart of the goal, not all, or any, of which may succeed. Although there exist complete search strategies for Horn clause logic programs, e.g., breadth-first search, Prolog implements an incomplete strategy, because depth-first backtracking may choose to explore one nonterminating part of the search space before exploring a terminating part. Thus Prolog may fail to find solutions when such solutions exist according to the denotational reading of the program. Declarative programming represents an attempt to address the difficulties in the software engineering of large, complex programs, based on the use of formal specification and design languages, higher level, problem-oriented programming languages, and formal correctness proofs. For example, some of the claims that have been made for functional programming in this regard are: ? Functional languages are more problem-oriented than conventional languages; the jump from a formal specification to a functional program is thus much shorter and easier. ? Functional languages have a simple mathematical basis, the l-calculus, and because of the lack of side-effects, program correctness proofs are easier. ? Functional programs are generally shorter than their conventional counterparts, and thus easier to enhance and maintain. ? Functional languages seem to provide one answer to the problem of exploiting the parallelism offered by multiprocessor systems. These declarative programming paradigms are potentially relevant to the DOM project for a number of reasons: ? They represent a class of programming languages that may be used to write individual components that must be integrated into DOM-based systems. ? They provide a potential source of higher-level languages for writing object methods that may be more optimizable than conventional programming languages ? They provide higher-level facilities for users to combine large-granularity objects (network components) together into higher-order facilities, with less reliance on "programming" per se. ? They suggest mechanisms for integrating programming language and persistent storage (database) capabilities at a relatively high level, due to relationships between these paradigms and various aspects of database technology. This final point deserves some amplification. The basic operations of the relational data model are defined by the relational algebra, which is basically a functional --------------------------------------------------------------------------- programming language on relations (with the exception of side-effects on update). Dataflow techniques are commonly used in representing and analyzing relational queries, just as they are in functional programming languages. This relationship suggests functional programming as a possible way of integrating database processing and ordinary programming. Examples of research pursuing this approach include FQL [BUNE82] and, to a certain extent, PDM [MANO86b]. The frequently-observed similarity of Prolog and relational database processing suggests another relationship in the case of relational programming. This is further discussed in section 2.2.1. The general subject of integrating logic and functional programming with database facilities is also thoroughly discussed in [ATKI87]. 2.1.4 Multiparadigm Languages and Systems Conventional programming languages restrict the user to a single programming paradigm, or approach to defining the program. For example, both Algol and Pascal encourage the use of block-structured, sequential programs, and so belong to the same paradigm. A multiparadigm programming language or environment is one that does not restrict the user to a single paradigm. Instead, it combines several paradigms into an integrated language or system. This gives the programmer or developer a wider selection of tools in which to develop the program or system [HAIL86]. The most common multiparadigm system is the conventional operating system, which allows the use of several different programming languages. Such systems typically require the use of a linkage editor that combines object files from the different language compilers into one executable program. This approach is often difficult to use, since the user must understand the calling conventions of each of the languages involved. The Unix operating system provides a somewhat more flexible approach in its use of pipes. Normally, a Unix program takes its input from standard input and sends its output to standard output. The pipe facility allows the standard output from one program to be tied to the standard input of another program, forming one large program out of a chain of small programs. The programs may be written in any available language. This is a relatively restricted form of multiparadigm system, because the composition is restricted to a linear chain of programs, and the interface between programs is restricted to a sequence of ASCII characters. Extensions to the pipe facility to allow for multiple inputs and outputs have also been proposed. In general, conventional operating systems are not adequate multiparadigm systems because of the strict separation of the different paradigms, and the static nature of the linkage. Ideally, a multiparadigm system would allow language constructs from different paradigms to coexist within one program or module; each paradigm should be able to refer to and depend upon services provided by the others. A number of more tightly-coupled multiparadigm languages and systems have already been cited in previous sections. For example, any of the hybrid objectoriented programming languages, such as C++ or Loops, discussed in section 2.1.4 can be considered as multiparadigm languages (the Loops system combines features of the Lisp, functional, rule-oriented, access-oriented, and object-oriented paradigms). Similarly, a number of multiparadigm knowledge representations were discussed in section 2.1.2, an example being that of KEE Many variants of the --------------------------------------------------------------------------- descriptive programming approaches discussed in section 2.1.3 are also multiparadigm, examples being LOGLISP and EQLOG. Database systems also exhibit some multiparadigm characteristics. Most database systems provide interfaces to multiple programming languages, and thus provide a multiparadigm capability in that sense. Also, some individual database languages provide combinations of facilities from multiple paradigms, such as "triggers" (demons) combined with ordinary imperative query facilities. In addition to the reasons given in previous sections for interest in specific multiparadigm languages, multiparadigm language technology is of interest to the DOM project because one of the goals of the project is the integration of programs (or parts of programs) written in heterogeneous languages, and thus potentially using different paradigms. Thus, the techniques used in multiparadigm languages may provide some insights into various techniques available for such integration, both at the language and the implementation level. 2.2 Programming Language/Database Interfaces 2.2.1 AI/Database Interfaces An important requirement for future knowledge-based systems will be the ability to access data that is now stored in databases. For example, expert systems provide a way to make those who access a database follow established business rules and policies. Similarly, data from the database can be extracted into information that is used to make policy decisions, or can trigger expert analysis procedures. In recognition of these requirements, there has been considerable interest in both the research and software development communities in investigating various aspects of providing such interfaces. In some cases, this merely involves providing a relatively loose coupling between the KBS and a database. In other cases, this involves a tighter integration of AI and database concepts. The resulting systems have been variously referred to under such titles as "intelligent database systems" or "knowledge base management systems". A number of special cases of integrating AI and databases are described in the following subsections. General references on this topic include [BROD86a] and [KERS86,88]. 2.2.1.1 Prolog/Database Interfaces One area that has received a lot of attention is that of interfacing Prolog with relational database systems. The initial impetus behind this was the observation that Prolog stores data in tuples, just as relational databases do, and that Prolog is in fact a relational database language (it is also, as observed above, a relational programming language). This relationship has been noted by many researchers, and a number of research projects have attempted to implement combined systems. One approach to doing this has been "loose coupling", that is, to attempt to use an existing relational database system as a back end to a Prolog language processor. The most straightforward method for doing this is to simply incorporate a mechanism for explicitly requesting database access from the Prolog program, in a manner similar to the Prolog "consult" predicate. A more sophisticated approach is to modify --------------------------------------------------------------------------- the processing of the Prolog program so that it collects in an unevaluated form the Prolog requests that access data stored in the database. These are then translated into the database query language and dispatched to the DBMS for processing. A commercial example of this approach is found in the Arity/SQL product, which is an add-on package to Arity's Prolog interpreter and compiler. In this product, SQL statements can be used within a Prolog program by reading them from a disk file, having the user enter them, or building them within the Prolog program. Query results can either be displayed to the user, or stored into the Prolog database for manipulation by the Prolog program [RETT87a]. A loose-coupling approach is clearly an attractive short-term solution, but considerable inefficiencies are possible with this approach, since neither system is necessarily optimized in any way to interact with the other. In order to avoid these problems, other researchers have investigated more tightly-coupled approaches. These have taken two directions: borrowing ideas from database technology to create extended Prolog systems that include database support, and borrowing logic programming concepts to create extended database systems that support logic programming capabilities. Examples of papers on this topic include [BROD86b, JARK84, SCIO86, ULLM86]. 2.2.1.2 Knowledge Engineering Tool/Database Interfaces An example of a commercially-available facility that has been recently introduced to allow a KBS implemented on a Knowledge Engineering Tool to access data on a database is the KEEconnection product from Intellicorp. KEEconnection is a mechanism that allows KEE KBSs to use data in SQL-based DBMSs. Essentially, it allows the KBS to define a view of the relational database in terms of KEE object (unit) classes. The mapping between a KEE unit class and a relation may be simple (1-1 between a relation and a KEE unit, with each column mapped to a single slot in the unit), or somewhat more complicated (tuples may be qualified for membership, the mapping between a relation and unit may be n-1 or 1-n, data conversions may be defined, etc.). Foreign keys may also be translated into direct references to other KEE unit instances when data is read from the database. Actual data is read from the database as tuples and converted to KEE unit instances (the view is materialized) either on command (an explicit download function referencing the KEE units required) or as a result of a rule evaluation. Rules are KEE units themselves, and thus have slots. Two slots used by KEEconnection are DOWNLOAD-AFTER-PREMISE and DOWNLOAD-AFTER-CONCLUSION. A qualifying condition (involving KEE units) stored as the value of the former slot will cause an SQL query to be issued after the LHS of a rule has been matched; the same condition stored as the value of the latter slot will cause the query to be issued after the RHS has been matched. Data can also be uploaded to the database from KEE. KEEconnection is a reasonably straightforward approach to the problem of connecting a KBS with a DBMS. Relatively little optimization is attempted; everything except the actual relational form of the data is apparent to and under the control of the application developer. Queries are issued explicitly, either using the download command or within rules. By using KEE "proxy objects" (the target unit classes of the database retrievals), most of the KEE implementation is isolated from --------------------------------------------------------------------------- the effects of this added facility (aside from whatever processing is required to handle the special rule slots mentioned above). KEE's "data model" resembles in many respects many of the advanced semantic data models that have been defined. KEE's inheritance is potentially more complex than in many (but not all) semantic data models, but the object-oriented data models have moved fairly far in this direction too. KEE's procedural slots (such as DOWNLOAD-AFTER-PREMISE) are similar in some respects to triggers, and are even more similar to the concept of storing a query as a relational column value in POSTGRES, since the procedural reference is actually included as the value of a slot or column, rather than in a separate structure. This commonality raises interesting questions about the impact of implementations of these more advanced database models on database systems and products such as KEE. Will there continue to be separate knowledge-base and database components, or will these components be integrated in some way? One possible scenario would be for an overall system to adopt a common "knowledge language" based on a merger of semantic data model and knowledge representation concepts, using an object-oriented approach. Methods supporting data-oriented operations would be defined using DBMS technology, while methods supporting reasoning over the knowledge represented in the model would be defined using AI technology. Implementation of this approach would involve, to a great extent, addressing many of the same fundamental research issues concerning AI/DBMS integration being considered in the DOM project. 2.2.2 Persistent/Database Programming Languages Persistence is a property of data that determines how long it should be remain in existence as far as the computer system is concerned. With most programming languages and expert system shells -- even object-oriented ones like Smalltalk, KEE, and CommonLoops -- data and knowledge objects in the program's address space are transient, i.e., they exist only as long as the program executes. Some data, such as locally declared data or procedure parameters, has an even shorter lifetime (the execution of the individual block or procedure). In a conventional programming language, to make an object persist beyond the lifetime of a single program execution, the programmer must include explicit instructions to save the object on stable storage, usually in a file on disc. Conversely, to reuse an object that was created in an earlier execution, or by some other program, the programmer must include explicit instructions to fetch the object from stable storage. There are several problems with this approach. First, it is the programmer's responsibility to decide when to save and fetch objects. Second, the programmer must write code to translate between the internal representations of objects (e.g., arrays) in the program's address space and their external representations on secondary storage (e.g., a file of records), which may be quite different. This mapping is especially complicated in an object-oriented environment, where a complex object may be composed of many component objects linked together with pointers; translating pointer-based structures requires care. Type-checking, too, is the programmer's responsibility: modern programming languages have elaborate type systems, often with strong type checking; however, once an object is written out to stable storage, it can be modified by another program that has access to the file, with no guarantee that the modified object will conform to the original type when it --------------------------------------------------------------------------- is reread into the address space of the program that created it. Finally, for coordinating access to shared objects, the programmer must rely on the synchronization mechanisms provided by the file system or must write his own. Most file systems provide concurrency control only at the granularity of files, not at the granularity of program objects. Modern "database programming languages" address some of these problems by integrating a programming language (or expert system shell) and a DBMS. They allow some distinguished programming language data types to be persistent (e.g., the type "relation" in PASCAL/R [SCHM77]; "entity types" in ADAPLEX [SMIT83]). These languages incorporate powerful high-level query facilities that allow the programmer to fetch a set of data objects from the database in one access. Also, by allowing database operations to be bracketed in transactions, they support the controlled sharing of concurrently accessed data objects. However, the programmer still sees two type systems (and two address spaces), one for the transient objects in the program's address space, and another for the persistent objects in the database, and is responsible for translating between them. Also, the concurrency control mechanisms provided by conventional DBMSs may be too stringent and restrictive for the cooperative knowledge-based applications of interest to us. The recent work on "persistent programming languages" is predicated on the principle of "orthogonal persistence" [ATKI87], i.e., any instance of any programming language data type should be allowed to persist, not just some distinguished types. This principle has motivated the design of persistent programming languages and object managers for them (e.g., Trellis/Owl [OBRI86] and Galileo [ALBA86]). It is important to understand that, with the tight coupling of programming language and underlying data/object manager that is the basis of persistent programming languages, it is sometimes difficult to distinguish between a persistent programming language and a database management system. For example, ADAPLEX is referred to above as a database programming language, but it requires a full-function DBMS to support it (known as the LDM in its centralized version). Similarly, OPAL has been described both as a persistent version of Smalltalk and as the method definition language for the GemStone object-oriented database system (see below). Similar difficulties exist with regard to the tight coupling of programming language and operating system (with persistent storage) that is the basis of Argus [LISK83, LISK88]. Argus is described further in the Appendix. [ATKI87] contains a very thorough discussion of the issues involved in developing persistent and database programming languages, and a very thorough survey of work that has been done in the area. It is interesting to note that the authors identify as particularly important problems those of providing a uniform type system and mechanisms for data to persist, and as particularly important issues those relating to polymorphism, type inheritance, object identity, and the choice of structures to represent sets of similar values. All of these are key issues in object management technology as well, and certainly the entire area of persistent and database programming languages is highly relevant to the DOM project. In fact, one of the issues mentioned in Section 3 involves whether the result of DOM project object model investigations should be a persistent programming language. --------------------------------------------------------------------------- 2.3 Database Management Systems Database management technology is a relevant technical area for the DOM project because (together with the file system technology from which much of it is derived) it provides the basis for long-term (persistent) storage of information within a system. While general database technology is relevant to our work, our specific interest is in the subclasses of database technology identified in the following sections. In each section, only a few of the relevant projects are explicitly discussed. 2.3.1 Object-Oriented Database Management Systems As noted previously, object-oriented programming encapsulates into a single structure data and the operations (methods) that are appropriate to execute on that data. The external interface of each object is defined by the object's methods. The exact form of each method, as well as any data contained in the object, are not accessible or visible from outside the object. Object-oriented DBMSs [LOCH85, DITT86] generally attempt to capture these same concepts, but also emphasize certain additional characteristics necessary to support large, shared, persistent object stores. These characteristics include efficient processing of set-oriented requests (query optimization), efficient processing over large secondary storage organizations, concurrency control, and recovery. Compared to a conventional relational DBMS, a typical object-oriented DBMS differs primarily in trying to support user-defined operations on object classes, and (method) inheritance. Other aspects found in object-oriented DBMS descriptions include support for the concept of object identity (the object has an identify independent of its attribute values), and direct object relationships (objects related to a given object are accessed by invoking a method of the given object, as if the related objects were part of the given object's internal data). Representative examples of current OODBMS work are described later in this section. These systems have been developed to support applications whose data structures are too rich to fit into conventional the simple structures provided by conventional database models, such as the tables provided in the relational model. Examples of these applications include support for spatial objects, graphics objects (e.g., images), AI knowledge representations, and software engineering environments. The basic idea of an object-oriented database is to represent an entity or object in the real world being modeled with a corresponding object in the database. This includes modeling the behavior of each object as well as the object's structure, and relationship to other defined objects. This one-to-one mapping reduces the semantic gap between the real world and the database modeling of that world. Moreover, when coupled with an object-oriented programming style, this reduces the semantic gap between a program and its supporting database data. Just as the term "object-oriented" has been used to describe a number of distinct collections of facilities in programming languages, the same is true of database systems. For example, the introduction to [DITT86] defines three levels of "object orientation" for database systems: a. If the data model allows the definition of data structures to represent entities of any complexity (sometimes called complex objects in the database literature), the model is structurally object-oriented. --------------------------------------------------------------------------- b. If the data model includes (generic) operators to deal with complex objects in their entirety (rather than forcing the decomposition of the necessary operations into a series of simpler operations, e.g. on relational tuples), the model is operationally object-oriented. Models in this class are necessarily structurally object-oriented. c. If the data model, like an object-oriented programming language, allows the definition of arbitrarily-complex object types, together with a set of specific operators, such that objects may be used only by calling these operators, and the internal structure of the objects may only be accessed by the implementation of these operators, the model is behaviorally object-oriented. Models in this class are necessarily both structurally and operationally object-oriented. The reader is cautioned that this categorization, while useful, is only one of many attempts to describe the concept of an object-oriented database system. Instances of database systems (or "object servers") of all three types have been referred to as object-oriented database systems in the literature. Researchers and developers have approached implementation of these systems from two main directions: extending relational systems, or applying the ideas of object-oriented programming to persistent storage. Extended relational models tend to be operationally object-oriented, and in this report are considered as "extended" DBMSs in Section 2.3.2. Behaviorally object-oriented systems are frequently extensions of object-oriented languages or environments , operating systems, or previous extended DBMSs. The development of object-oriented DBMSs is a very active area, both in terms of research prototypes and commercial products. This technology is relevant to the DOM project because it includes capabilities (or research into such capabilities) for providing persistent storage of arbitrary objects, and integration of method processing with database functions. These are core capabilities in distributed object management. A number of object-oriented DBMS developments are briefly described below. Vbase Vbase is a object-oriented database system developed by Ontologic [ANDR87a]. It is intended to provide an integrated software development environment for CAD and other design-oriented applications. It is commercially-available, and runs on Sun and microVAX workstations. In Vbase, persistent object types are defined using a type definition language (TDL). The object model defined by TDL includes the usual object features, including inheritance. Methods of these objects are defined using the C Object Processor (COP) language, an extension of C. COP uses strong type checking (based on TDL declarations) to detect errors and perform code optimization. Vbase also provides an object-oriented version of SQL for querying databases, facilities for clustering objects on secondary storage to improve performance, and triggers. The Vbase run time system supports concurrent object sharing, access control, and backup and recovery facilities. GemStone --------------------------------------------------------------------------- GemStone is an object-oriented database server developed by Servio Logic [MAIE86]. GemStone's data language, OPAL, is based on Smalltalk, but adds facilities for persistent storage, concurrent access, transactions, and indexing. Methods for GemStone objects are written in OPAL. GemStone runs as a server in a VAX/VMS environment, and supports applications running on attached workstations. GemStone software in the workstations includes a set of C functions or Smalltalk methods that are used to create interactive user interfaces to OPAL programs defined on GemStone. Because OPAL provides full programming power, applications can be designed to execute primarily on workstations, or primarily on GemStone. GemStone also provides a calculus-based associative access language, designed to be easily-translated to OPAL. G-BASE G-BASE is an object-oriented DBMS developed by Graphael. It is written in Common Lisp for workstations (Symbolics, TI, Explorer, and Sun), and is intended to support knowledge-based engineering, AI applications, and software tools development. It can store alphanumeric, graphic, video-imaged, and audio information. The object model in G-BASE is based on a combination of the ER model and frames; methods in G-BASE are written in Lisp. G-BASE does not currently support multiple users, but a version that can be used as an object server is scheduled for completion this year. ORION ORION is a prototype object-oriented database system developed at MCC [WOEL87]. It is a single-user, multi-tasking system which runs in a workstation environment, and is intended for applications from the AI, multimedia documents, and CAD domains. ORION is implemented in Common Lisp, and runs on the Symbolics Lisp machine or Sun workstation. The ORION data model consolidates and modifies a number of major concepts found in many object-oriented systems, such as objects, classes, class lattice, methods, and inheritance. Much of the research related to ORION has concentrated on three major enhancements to the conventional object-oriented data model, namely, schema evolution, composite objects, and versions. Schema evolution is the ability to dynamically make changes to the class definitions and the structure of the class lattice. Composite objects are recursive collections of exclusive components that are treated as units of storage, retrieval, and integrity enforcement. Versions are variations of the same object that are related by the history of their derivation. ENCORE/ObServer ENCORE is a prototype object-oriented DBMS being developed at Brown University [ZDON85]. The ENCORE data model is a fairly conventional high-level semantic model, in which objects are defined with properties and associated operations. Multiple inheritance and versions are supported. The type structure of this object model is supported by one process, with lower level storage of object data being handled by a separate object server (ObServer) component [SKAR86]. In addition to supporting ENCORE, ObServer is being used as a platform for the construction of the GARDEN visual programming environment. --------------------------------------------------------------------------- Iris Iris is a prototype object-oriented DBMS developed by Hewlett-Packard [LYNG86, FISH87,88]. It is intended to provide database capabilities for a wide variety of applications including object-oriented programming languages, CAD, and AI. The data model of Iris is based on the object, type, and operation constructs, and supports inheritance, constraints, complex objects, user-defined operations, versions, and inference. The model is based to some extent on DAPLEX [SHIP81] and Taxis [MYLO80], and thus resembles PDM in some respects. The model is implemented by an Object Manager, which is based on an extended relational algebra as its computation model. The Object Manager interface consists of a set of C functions. The Object Manager is in turn supported by a Storage Manager, which is currently a conventional relational storage subsystem. IRIS supports its own interactive query interface, an interactive interface for an objectoriented extension to SQL (OSQL), and interface modules for programs written in Lisp and C. In addition, an object-oriented interface to Iris from Common Lisp has been implemented that presents the model of an Iris database object to the Lisp programmer. The various entities in this interface are implemented as Lisp Objects, the methods of which are the C functions defining the Object Manager interface. --------------------------------------------------------------------------- PROBE PROBE is a prototype object-oriented database system under development at the Computer Corporation of America [DAYA86]. We briefly describe the characteristics of PROBE, in order to illustrate the capabilities of one specific objectoriented database system. PROBE was primarily intended to support applications involving such "nontraditional" data types as spatial, image, and time data. PROBE incorporates an object-oriented data model that allows integration of programs implementing object behavior together with data, is extensible, and allows the use of special-purpose processors for new data types. In supporting spatial data, it incorporates efficient recursive query processing [ROSE86] (for use in queries on parts hierarchies or task precedence networks), as well as spatial and temporal query processing [MANO86a, OREN88] (using special object types). PDM, PROBE's data model [MANO86b], is an extension of the Daplex (functional) model [SHIP81]. Daplex already contained the concept of "entities" (objects) to which "functions" (messages) could be applied in a dynamic way, inheritance hierarchies of entity types, and other characteristics similar to those of an objectoriented model. Daplex was also the basis of several implemented CCA systems, including the ADAPLEX LDM/DDM, a DBMS implemented in, and designed to work with, the Ada* programming language, and the MULTIBASE heterogeneous distributed database system, designed to integrate multiple existing database systems into a single system, so there was implementation experience available with at least some aspects of an object-oriented DBMS in developing PROBE. The basic areas in which Daplex has been extended in PDM are: ? multiargument and computed functions are supported. ? a collection of operations, called PDM algebra, is defined as the basis for defining system operations. ? the ability to define new object classes with specialized operations (extensibility) is supported. PDM contains two basic concepts: entities and functions. An entity is a construct that denotes some individual thing (and thus corresponds to an object, as described earlier). Entities with similar characteristics are grouped into collections called entity types(e.g., PART). Properties of entities, relationships between entities, and operations on entities (behavioral aspects) are all uniformly represented in PDM by functions (which correspond to methods). In order to access properties of an entity or other entities related to an entity, or to perform operations on an entity, one must evaluate a function having the entity as an argument. The examples below illustrate some of the aspects of PDM functions (the syntax used is illustrative only): ? the single-argument function PART_NUMBER(PART) --> character allows access to the value of the part number attribute of a PART entity. ? the multi-argument function COLOR(X,Y,PHOTO) --> COLOR_VALUE allows access to the color values at particular points in a photograph. * Ada is a trademark of the Department of Defense (Ada Joint Program Office) --------------------------------------------------------------------------- ? the function LOCATION(CONNECTION,LAYOUT) --> (X,Y) allows access to the value of the coordinates of a connection in a diagram (note that a function can return a complex result). ? the function UNION(3DSOLID,3DSOLID) --> 3DSOLID provides access to a union operation defined for 3-dimensional solid models of parts. ? the set-valued function COMPONENTS(PART) --> set of PART allows access to the component parts of a group part (assembly). Functions may also be defined that have no input arguments, or that have only Boolean (truth-valued) results. For example: ? the zero-argument function PART() --> set of ENTITY is implicitly defined for entity type PART, and returns all entities of that type (a corresponding function is implicitly defined for each entity type in the database). ? the function ADJACENT(PART,PART,ASSEMBLY) --> boolean defines a predicate that is true if two parts are adjacent within a given assembly. All predicates within PDM are defined as Boolean-valued functions. Functions in PDM may be either intensionally-defined, with output values computed by procedures (such as the UNION function above), or extensionally-defined, with output values determined by a conventional database search of a stored table (such as the PART_NUMBER function above). Specializations (subtypes) of entity types may be defined, forming an inheritance (isa) hierarchy. For example, the declarations: entity PART function PART_NUMBER(PART) --> character function WEIGHT(PART) --> real entity 3DSOLID isa PART function UNION(3DSOLID,3DSOLID) --> 3DSOLID define entity types similar to the object classes shown in Figure 1. They define a PART entity type having two functions, and a subtype 3DSOLID having an additional function. Because 3DSOLID is a subtype of PART, any 3DSOLID entity is also an entity of the PART supertype, and automatically "inherits" the PART_NUMBER and WEIGHT functions. Generic operations on objects (entities and functions), such as selection, function application, set operations, and formation of new derived function extents, have been defined in the form of an algebra [MANO86b] similar in many respects to the algebra defined for the relational data model. Like the relational algebra, this PDM algebra provides a formal basis for a powerful data manipulation and view definition facility, as well as the potential for developing extensible query optimization strategies. The PROBE architecture is intended to provide efficiency as well as extensibility, by careful integration of type-specific operations with set-at-a-time database operations [OREN88]. --------------------------------------------------------------------------- Statice Statice [WEIN88] is an object-oriented database system under development at Symbolics Inc. It runs on Symbolics Lisp workstations, running the Genera programming environment, and connected in a local-area network. Statice provides client programs with persistent, shared storage for information. Persistent information stored in Statice exists outside and beyond the boundaries of the Lisp world that created it, and is protected against failure. Shared information is shared by distinct Lisp worlds on different workstations, for writing as well as reading. Statice uses an object-oriented data model. Objects are modelled by entities in the database. Each entity has its own identity, implemented by a globally unique ID, and each is a member of an entity type. Entities have attributes, each of a particular type. The type of an attribute can be an entity type, a conventional value type (such as integer or string), or a user-defined value type for efficient representation of specialized data. The programmer's interface to Statice is closely integrated with Symbolics Common Lisp and with its object-oriented programming system. For example, entities and entity types correspond to (and are implemented using) instances and classes in the object-oriented programming system. Generic operations are added to Statice types in exactly the same way as they are added to classes in the object-oriented programming system. Strings can be of any length and can include character style information (that is, fonts and size); integers can be of arbitrary precision. As a result, Statice is "just Lisp," which makes the programmer's interface a seamless extension of the standard programming language. Storage efficiency and speed are high priority goals of Statice. For example, the common and easy cases, like integers that fit into 32 bits and strings without style information, are internally stored in an efficient format, invisibly to the user. In support of efficiency, Statice's access paths allow disk pages to be prefetched and data to be requested over the network in large blocks. Very large amounts of data can cached at the local workstation, resulting in minimal network traffic when there is little write-contention on the data (the expected common case in Statice applications). Statice uses a novel semi-optimistic caching scheme to retain cached data outside of transaction boundaries and to avoid waiting for the server, allowing more concurrency between client and server hosts. Statice includes many of the features found in corresponding parts of conventional database systems. It provides concurrency control using two-phase locking with deadlock detection, system recovery using a write-ahead log, and media recovery using dumps and an archive log. B-tree indexes and parent-child "prejoin" links are provided, but are carefully kept invisible to programs, to provide the same kind of data independence that relational databases achieve. All Statice interactions are done within transactions. Statice has also undergone some product engineering to provide good error messages and automatic recovery from network failures. An early implementation of Statice is in use at Symbolics by several applications, including a source code version control system. Further features and performance improvements are planned, including clustered storage, a new underlying RPC network protocol, and an improved underlying file system. --------------------------------------------------------------------------- Comments A number of problems have been cited with an object-oriented approach to databases: ? It lacks a coherent data model with a mathematical foundation such as relational algebra (this problem has several implications, including the difficulty of specifying queries and ensuring the database is consistent). ? Research into storage structures for efficient object storage is in the very early stages. ? Use of an object-oriented database from a conventional programming language such as COBOL, Pascal, or C is difficult because of the semantic gap. These languages lack the concept of an object. While it is true that research into storage structures (and many more aspects of object-oriented DBMSs) is in the very early stages, such comments should not be taken too seriously. For example, formal foundations for object-oriented models is one of many active research areas, and [MANO86b] describes an object model (PDM) having an associated formal algebra similar to the relational algebra. The semantic gap between object-oriented DBMSs and conventional programming languages is certainly a problem, but not much more so than that between relational DBMSs and such languages. The Iris work on an object-oriented form of SQL shows that this gap is not a large one. Significant research is going on in the areas of object-oriented database systems and related languages, and numerous conferences have been and are being held on this subject (e.g., [DITT86]). Important research areas include data models, object versions, object identity, high-level language facilities, request optimization, protection and locking mechanisms for objects and subobjects, and advanced transaction processing mechanisms. Many of these areas are not unique to objectoriented DBMSs. However, these areas assume greater importance in the context of object-oriented DBMSs, since object-oriented DBMSs generalize the data and applications that can be supported, and thus generalize the class of solutions required in these areas. 2.3.2 "Extended" Database Management Systems This category lumps together DBMSs that are "extended" beyond the conventional relational DBMS, but are for some reason not considered object-oriented DBMSs. In some cases, this work could be classified as "object-oriented" by some criteria. In other cases, it preceded the concept of object-oriented DBMS, but includes many common features and goals. In still other cases, it is pursuing work that is to some extent orthogonal to object-oriented DBMS research, such as work on "active" DBMSs. All this work is relevant because it addresses issues of extending DBMS technology in ways that may be useful in distributed object management. ADAPLEX LDM/DDM The ADAPLEX language is cited in Section 2.2.2 as a database programming language. It results from the embedding of the database sublanguage DAPLEX --------------------------------------------------------------------------- [SHIP81] in the Ada programming language. The ADAPLEX Local Database Manager (LDM) was designed as the run time support system for the database functionality of ADAPLEX. The LDM is of interest as a full-scale implementation of an "extended" (semantic) data model, containing concepts such as object identity and inheritance that are now incorporated in object-oriented models. As such, it addresses many implementation issues that will arise in full-scale object-oriented database systems [CHAN82]. The LDM is also of interest in the way it was integrated into the Ada programming environment. In ADAPLEX, the coupling between Ada and DAPLEX was made at the expression level, and is thus more complete that the statement-level integration found in conventional database systems using an embedded query approach. Such tight coupling poses new implementation problems, but also creates new opportunities for request optimization. The ADAPLEX Distributed Database Manager (DDM) is a distributed database component for ADAPLEX that interconnects multiple LDMs in a network. As with the LDM, the DDM is of interest as an implementation of a distributed DBMS capability for an "extended" data model. This system is relevant to the DOM project because it is still one of the few comprehensive implementations of a data model including "semantic" constructs, such as inheritance and relationships based on entity (or object) identifiers. As such, it may give useful guidance in implementation issues related to DOM. POSTGRES POSTGRES is a new database management system being developed at the University of California, Berkeley [STON86a,b]. It is intended as a successor to the INGRES relational database system. The intent is to make as few changes as possible (preferably none) to the relational data model, while incorporating numerous desirable features that have been identified in the database research literature (many of them prototyped in previous work related to INGRES). The system is intended to be publically-available in 1988. POSTGRES provides extensions to support the definition of abstract data types, instances of which can then participate as the values of columns in relations. The procedures defined for these abstract data types can then be used in queries that manipulate these types. For example, DATE might be defined as an abstract data type, along with procedures for converting input data into DATE format, addition, subtraction, and comparison. POSTGRES also provides facilities for storing queries in tuples for producing derived data, for defining forward and backward chaining "inference" operations over databases, and for supporting "active" databases via alerters and triggers, among other facilities. Other work related to POSTGRES includes the design of a query language (POSTQUEL), a programming language interface, system architecture, query processing strategies, and storage system. This system is relevant to the DOM project because many of the facilities it provides, such as extensibility and support for "inference" and triggers, are also facilities in which we are interested (although we intend to investigate them in a more general, object-oriented framework, as opposed to the extended relational model used in POSTGRES). --------------------------------------------------------------------------- EXODUS EXODUS is an extensible database project at the University of Wisconsin [CARE86a,b]. EXODUS takes a "database generator" approach to extensibility, as opposed to being an attempt to build a single (although extensible) DBMS for use by all applications, such as POSTGRES, PROBE, or Starburst. EXODUS provides a set of kernel facilities for use across all applications, such as a versatile storage manager and a general-purpose type manager. In addition, it provides a set of tools to help a "database implementor" (DBI) develop new database system software as required for specific applications. The implementation of some of this software is supported by tools that actually generate specific components from specifications. For example, tools are provided to generate a query optimizer from a rule-based description of a data model, its operators, and their implementations [GRAE87]. Other components, such as new data types, access methods, and database operations, must be explicitly coded by the DBI (although a library of generally useful software components, such as access methods, is being provided as well). In support of this, EXODUS provides a set of high-leverage programming language constructs for use in coding these components, embedded in an extension of C++ called "E" [RICH87] GENESIS GENESIS is an extensible database project at the University of Texas at Austin [BATO86]. GENESIS, like EXODUS, takes a "database generator" approach. However, it differs from EXODUS in emphasizing the construction of DBMSs on the basis of building blocks and pluggable modules, rather than an approach based on a common kernel plus development tools. Specifically, GENESIS is based on a unified theory of DBMS components which defines DBMS storage architectures as compositions of basic building blocks. with carefully-defined interfaces [BATO85]. GENESIS provides facilities for specifying a desired storage architecture based on this theory, and then synthesizing a DBMS implementing the architecture from a library of software modules corresponding to building blocks identified in the theory. The library itself is extensible, so that new modules can be added. Once a storage architecture has been designed, only modules not present in the library must be written. Since modules are reusable, it is anticipated that the need to write new modules will decrease as the library expands. Work on extensible DBMSs such as EXODUS and GENESIS is of interest to the DOM project because it is directed toward identifying pieces of a DBMS that can be broken off as separate components, and identifying the appropriate interfaces between such components. The work also addresses technology for automatically generating components from high-level descriptions. Such technology will be very important in making large-scale heterogeneous systems feasible. Starburst Starburst is a project at the IBM Almaden Research Center [SCHW86,LIND87]. It has four major goals: (1) portability, (2) better internal structure, (3) extensibility, and (4) distributed data and function in a heterogeneous network. In order to make Starburst portable to any environment, it is being developed in C. Based on past --------------------------------------------------------------------------- experience with System R and R*, the project hopes to streamline the internal data structures and overall design, while at the same time eliminating some of the implementation-dependent limitations on SQL. The third major objective, and perhaps the most challenging, aims at developing a DBMS kernel can be customized for applications other than traditional commercial applications, e.g. CAD/CAM, office documents (text & image), AI (e.g., recursive queries), etc. Finally, the fourth goal expands upon the work of R* to distribution between heterogeneous hardware, e.g. between a PC and host machine, and addresses the issues of naming, availability, transaction management, optimization, and security raised by large networks of thousands of workstations, servers, and host machines. Key aspects of this work so far have been an architecture to support new, "extension" storage managers and access path managers, and an efficient algorithm for refreshing snapshots of data. The ability to add new access paths and new ways of storing relations is key to achieving Starburst's goal of extensibility. This architecture and basic storage and access path managers have been implemented in Starburst. Snapshots, read-only but refreshable copies of data, are expected to be an important part of workstation-host database coupling. This system is relevant to the DOM project because of its focus on extensibility, and support of distribution on heterogeneous hardware. HiPAC The HiPAC (High Performance ACtive database system) project [DAYA88] is addressing two key problems in time-constrained data management. One is the handling of timing constraints in databases that must support real-time applications. The other is the avoidance of wasteful polling of the database by applications, e.g., to determine if some key data relevant to the application has been updated by a concurrently executing program. This is done through the use of situation-action rules that are an integral part of the database, and are monitored by a condition monitor within the DBMS, thus providing an "active DBMS" capability. Such facilities are relevant to the DOM project because they improve the capability of a DBMS, or any other persistent object repository, to increase overall efficiency by cooperating actively with applications, rather than passively waiting for requests. 2.3.3 Distributed Database Management Systems Distributed database technology is of interest to the DOM project because it addresses mechanisms for performing conventional database functions (concurrency, reliability, query processing) in a distributed environment. We characterize distributed DBMSs (DDBMSs) as either homogeneous, heterogeneous, or federated, although these are not strictly orthogonal categories. Homogeneous DDBMSs are those incorporating multiple instances of a single DBMS, usually designed to work together, into a single DBMS. Examples include R*, and the ADAPLEX DDM described in the last section. Heterogeneous DDBMSs are those incorporating dissimilar DBMSs into a single DBMS. There is a wide variation in the degree of heterogeneity that is acceptable to a given system. In some cases, "heterogeneous" means multiple DBMSs, all of which support the same query language (usually SQL). In other cases, "heterogeneous" means multiple DBMSs and file systems, which may support virtually any data model. Both Multibase, described in Section 1, and CALIDA, described below, fall into this --------------------------------------------------------------------------- category. Finally federated DDBMSs are those incorporating multiple autonomous databases, which may be heterogeneous, that agree to share information and cooperate in some controlled way. The characteristic that governs whether a DDBMS is considered "federated" or not is how much cooperation there is among the various systems, with "federated" systems being rather loosely coupled compared to others. The loose coupling implied by federation has implications on such things as integration of data descriptions, query processing, security, and concurrency control. A collection of papers on federated DDBMSs can be found in [SARI87]. R* R* [LIND84, LOHM85] is a prototype relational DDBMS constructed as a distributed version of System R [BLAS81] at IBM's San Jose Research Laboratory. The R* system is a confederation of autonomous, locally-administered databases that may be geographically dispersed, yet which appear to the user as a single database. Naming conventions permit R* to access tables at remote sites without resorting to a centralized or replicated catalog, and without the user having to specify either the current location of or the communication commands required to access that table. Tables may be moved physically to other databases without affecting existing SQL statements. SQL data manipulation statements are compiled at each site having a table referenced in the statement, coordinated by the site at which the statement originated. As part of compilation, the distributed optimization process chooses the best place and the best way to access tables and join them together. Optimization uses dynamic programming and careful pruning to minimize total estimated execution cost at all sites, which is a linear combination of CPU, I/O, and communications costs. Specific issues addressed by R* included: ? Naming and locating users and database objects ? Compiling SQL at multiple sites ? Optimization ? View definition ? Communication protocols ? Assuring database consistency in multi-site transactions ? Exploiting redundancy to improve performance CALIDA CALIDA [JAKO88] is a knowledge-based system developed at GTE Laboratories providing integrated access to multiple heterogeneous databases. Its main features include a menu-guided interface with user-defined concepts, automatic join generation, warning of expensive queries, automatic generation of target database queries, and transparent network access to the databases. As a powerful database analyst workstation, CALIDA provides a unified environment for query specification, database integration, and communications. CALIDA is a specific application system built using the generic procedural modules and tools of IDA (Intelligent Database Assistent) [JAKO86]. New applications are build by adding an application-specific knowledge base containing database-, database-management-, and communication-specific knowledge. --------------------------------------------------------------------------- An experimental version of CALIDA, developed on the Xerox 1186 AI workstation using Lisp, has network links to remote database hosts. The system has been successfully tested with production databases. Test results showed that the query turnaround time for complex requests was reduced by more than an order of magnitude using the system. 2.4 Operating Systems There are several reasons why we include operating systems as a component technology. An obvious reason is that operating system functionality is an important part of any computer system, and the interaction of that technology with distribution and inclusion of database processing in the system should be investigated. Another reason is that homogenization of distributed systems at the operating system level is a very active area of research, and the potential impact of that research on DOM objectives should be investigated. Finally, there is a close relationship between the run-time support required for object-oriented systems and what are typically operating system functions. For example, in "pure" object-oriented languages, execution of methods in objects is dealt with very much like process scheduling in operating systems. The analogy is particularly strong if the methods can execute asynchronously. This is in keeping with the concept of an object in such languages as a separate unit of computation. In general, object-oriented systems tend to interact heavily with what are conventionally OS services, such as process and memory management. Object-oriented operating systems also serve themselves as examples of object-oriented systems, although with different functions and object granularity than object-oriented programming languages typically have. Of particular interest are two specialized subareas of operating system technology, distributed operating systems, and database operating systems. The concept of a distributed operating system was developed in order to eliminate the need for users of a computer network to access each computer on the network individually. Such access would ordinarily require obtaining multiple accounts, learning and using different command languages (if the computers were heterogeneous), and explicitly managing the distribution of data and programs. In contrast, one of the various forms of network-wide operating systems would provide a uniform interface to operating system functions over the network, concealing differences among machines and host operating systems. These operating systems have developed along roughly two different lines. In what is often termed a network operating system, each host continues to run its original (non-network) operating system; the network operating system is implemented as a collection of additional programs running on each network host which creates an interface between that host and the network. In contrast to a network operating system, the term distributed operating system is then often used to describe the case in which the original operating systems are discarded, and a single operating system implementing distributed capabilities is implemented on the bare hardware [TANE81]. (In a distributed operating system, the hardware may still be heterogeneous, as long as the same operating system is implemented on it). Each of these approaches involves its own tradeoffs and design assumptions. In the long run, the distributed operating system solution is probably to be preferred, but this approach requires more work. Long haul networks with large multiprogrammed hosts and substantial existing software will, in the short term, tend --------------------------------------------------------------------------- to go the network operating system route, while local mini- and microcomputer networks are beginning to employ distributed operating systems. We use the term "database operating system" here to refer both to operating systems that have in some sense been modified or designed from scratch to support database processing, and to the general subject area of the interaction between database and operating system processing. 2.4.1 Network Operating Systems A common way to superimpose a network operating system on top of a collection of heterogeneous hosts is to provide each user with a process, termed an agent, whose job it is to provide a uniform interface to all hosts. The agent may run on one (or all) of the hosts, or on a separate network access machine. It may or may not attempt to hide the existence of multiple hosts from the user. If it does not attempt to hide the network from the user, typical commands to the agent are of the form AT HOST X DO COMMAND Y. If it does attempt to hide the network from the user, the agent must select the appropriate host to run each command on. The agent would maintain a database containing information about each host, and user data and programs. The agent might protect the user from different file naming conventions on the hosts by providing a network virtual file system. In the simplest form, the agent simply acts as a command processor, translating individual user commands from a common network command language into the command language of the appropriate host, and then sending the command to the host for execution. In some cases the hosts may not even be aware of the existence of the network. However, this simple case is rather limited in functionality. For example, it is often difficult to arrange for interactive input and output without the application program being aware of the existence of the network. A more general solution is to encapsulate the running process, intercepting all its system calls, so they can be carried out in the context of the network environment rather than the local one. An example of a network operating system that attempts to use this more general encapsulation solution is the National Software Works (NSW), which was implemented on the ARPANET [LAMP81]. The intent was to provide networkwide access to a collection of software development tools (compilers, linkers, debuggers, editors) available throughout the network. In NSW, each user is provided a front end process which provides the common interface to NSW. NSW maintains a logically centralized database which maintains information on the user's virtual file system, available tools, and accounting and status information. When a user commands his front end to run a tool, the front end sends a message to a works manager process, which searches the database to locate hosts having that tool. The works manager then creates a process called a foreman on the tool-bearing host to create, encapsulate, and manage the tool during its execution. The foreman is designed to catch all system calls made by the tool, so that they can be carried out in the context of the NSW network environment. This encapsulation is highly machinedependent. In come cases, parent processes automatically have the power to control their children. On other hosts, a special version of the tool would be created that has been linked with a modified system call library which calls the foreman instead of the local system. The assumption was that, as time passed, more and more tools would be integrated into NSW; i.e., they would be designed to make NSW calls rather than local operating system calls. The type of encapsulation --------------------------------------------------------------------------- described here would have been greatly facilitated through use of a common object model throughout the system. This is one of the approaches being taken in the DOM project. 2.4.2 Distributed Operating Systems The development of distributed operating systems is a very active research area. This is due to the perceived need for this technology in order to fully exploit the distributed collections of computers (particularly local area networks) increasingly being created within organizations. Descriptions of specific systems may be found in the Appendix, and in [NORT87, TANE85]. (The reason for a separate appendix on this particular subject is that this technology is less-familiar to some members of the project team than the other relevant technology areas. Having the separate appendix allows for somewhat longer descriptions of individual systems to be included.) Most research on distributed operating systems uses one of two models. In the process model (or client-server model), each resource (file, disk, etc.) is managed by some process, and all the operating system does in manage interprocess communication. Traditional operating system services, such as file systems, processor scheduling, etc., are managed by specific server processes that can be requested to perform the service. In the object model, the world consists of various objects, each of which has a type, a representation, and a set of operations that can be performed on it. To carry out an operation on an object (e.g., read from a file), a user process must possess a capability (permission) for the object (this is typically an object identifier, plus additional information used in performing access control). Operating systems using the object model frequently appear to be a hybrid of the two models, since the objects sometimes look like servers, and a process abstraction separate from the object concept is sometimes defined. A key issue in the design of systems based on the object model is the assumed object granularity. For operating systems, this is typically larger than many of the objects found in a language like Smalltalk (e.g., individual integers), but smaller than an entire program. A key issue in either model is the semantics of the interprocess communication mechanism (e.g., Remote Procedure Call or message passing, blocking versus nonblocking, virtual circuits versus datagrams). 2.4.3 Database Operating Systems This research area refers to investigations into specialized operating systems, or operating systems facilities, to support the specific requirements of database processing. A collection of papers on this general subject can be found in [BORA86]. The impact of the general-purpose operating system on DBMS performance is substantial, often in a negative way, as discussed in [GRAY78], a classic paper on the subject. This has led to numerous suggested changes in operating systems to resolve the problem [STON81]. A number of specific services have been proposed as operating system services to support data management. These include: ? transaction management facilities --------------------------------------------------------------------------- ? network file systems and location independence ? remote procedure calls ? lightweight processes Many of these services appear useful on the surface, and are the subjects of active investigation. An example is the provision of generalized transaction management services that is the goal of the CAMELOT project at Carnegie Mellon [SPEC86]. However, their actual utility must be assessed through more detailed examination. For example, [STON86c] examined these four facilities, and concluded that provision of the latter two facilities would be extremely helpful. On the other hand, it was concluded that operating system transaction management facilities would probably go unused by a DBMS, while use of a network file system would actually be harmful to DBMS performance. This is based on the lack of knowledge by the operating system of DBMS data model semantics. Such objections to providing facilities in operating systems do not necessarily apply to operating systems that can be specifically tailored to the support of a particular DBMS, and do not have to provide general-purpose support to other applications. Such operating systems are found in backend database machines [NYBE86], and could also be used in network nodes dedicated as database servers. Investigation of this area is relevant to the DOM project because the issues being investigated affect the system architecture that would be best suited to distributed object management, specifically issues related to the distribution of functionality among the various software components of a distributed system. 2.5 Heterogeneous/Distributed System Architectures This category of systems include those that fit into no one of the above categories, but are relevant to the DOM project in some way. Specific examples of such systems are described below. VHSIC EIS The VHSIC Engineering Information System [LINN86] is a large-scale systems integration project intended to support the engineering process in the Air Force's Very High Speed Integrated Circuit program. Some aspects of this system were described in Section 1. The overall project has a number of goals, including integration of VLSI (and SE) design tools, development of consistent methodologies (management, control) and interfaces (workstations, users), and determination of data exchange formats and protocols for engineering and related data. A major focus of the effort is the design of an integrated information system that allows a degree of interoperability among heterogeneous design tools, editors of various types, databases, and other useful components that may be attached to the system. For example, it is desired that a user at a workstation be able to call up an engineering design from a design repository, and apply a sequence of design tools and checkers to it, without concern for where the various pieces of data making up the design, or the tools, may be located in the system, what processors are involved, etc. Moreover, the system is supposed to automatically lead users --------------------------------------------------------------------------- through predefined procedures for performing various tasks, coordinate the activities of different users involved in cooperative tasks, etc. The overall architecture of the VHSIC EIS is shown in Figure 2.2. This project is relevant to the DOM project because its architecture has many features in common with the DOM architecture we envision as a goal of our project. These common features include: ? creation of a system-wide object space through the use of a common object model to allow interoperability among existing components ? use of a specialized Object Management System which is distributed among the various network components --------------------------------------------------------------------------- tool invocation services user interface services data exchange services Object Management System (OMS) OODL KERNEL distributed, heterogeneous data management services distributed OS services OS and Network Adapters Database Adapters Operating Environment System Services Operating System Services & Networking Communications Services Data Management Services Execution Services Input/Output Services Common Exchange Format: OODL User 1 User 2 Tool 1 External System Tool 2 tool adapter user interface service adapters editors query languages interface to services interface to services interface to services External System Interchange Format (compound document) CAIS 2.0 (+OODL) metadata SQL,OODL Figure 2.2 VHSIC EIS System Concept --------------------------------------------------------------------------- ? use of specialized adapter components to create interfaces between the common object model (and associated object management components) and individual interfaced tools and external systems. ? incorporation of database management facilities to provide persistent storage for local components. Another feature of the EIS architecture is its use of CAIS [OBER88] (see Section 2.6.3) as a common interface to local operating systems to enhance portability. Use of such an interface might be one way in which heterogeneity should be reduced in DOM-based systems. Hypertext Systems Hypertext is a computer-supported medium for information in which many interlinked documents are displayed with their links on a high-resolution computer screen. The links may be directly activated by a pointing device such as a mouse, which causes the document referenced by the link to appear instantly in a new window on the screen. While the concepts of hypertext are not new, the technology to make it effective is new. The architecture of an experimental Hypertext system developed at Texas Instruments includes: ? multi-media data types and subtypes (text, graphics, speech, etc.) ? a persistent object storage system POS; ? a hyper editor, based on integrated type-dependent editors such as text editors and graphics editors ? a change management system ? an extensible relational database ? a user-friendly menu-based natural language interface The system runs on Explorer lisp machines, is built from existing tools like the Zmacs text editor, and is portable to Common Lisp environments. Benchmark applications include VLSI chip design, travel planning, software development, and a CAI application. Such systems are relevant to the DOM project because of the similarities of the elements to be included in the system architectures, such as multi-media data facilities, and persistent object storage. It also seems likely that there will be interaction between user interfaces developed for hypertext systems and those that will be required in large-scale integrated systems constructed using DOM technology, as well as interaction due to the need to integrate Hypertext systems with specific information sources (and knowledge-based components) using DOM technology. --------------------------------------------------------------------------- 2.6 Standards Standards can play a key role in various parts of a system architecture. In general, the basic role of any standard is that of providing a common "language" (both syntax and semantics) that can be shared by a set of system components, and in terms of which the components can interact in a way that is mutually understandable. In the context of the DOM project, standards developments are relevant in two ways. First, the development of industry standards for particular system interfaces would reduce the heterogeneity possible at that interface, and thus allow concentration of attention on other aspects of the system. Second, the development of standards helps define particular aspects of systems that should be the object of more detailed attention (for example, the SQL relational language standard might suggest that attention should be paid to optimizing the class of queries that can be expressed in that language, as opposed to other nonstandard relational languages). There are several different types of standards that are potentially relevant, including: ? data storage and exchange formats ? data definitions (e.g., data element standards) ? protocols between system components In addition, lower level communications protocols and other potential areas for applications of standards exist in the architecture. The concentration here will be on the higher-level standards. (These explicitly do not include such things as corporate standards, standard products, etc. that may be relevant in the design of a particular system, and which may further simplify the design of that system. Such standards, while clearly crucial to system design, are not directly relevant to our current research effort, although they may become so later). The area of standards is a complex one, and we can only begin to scratch the surface here. 2.6.1 Data Storage and Exchange Standards A number of standards exist for interchange of formatted data of various types. Several specific standards are mentioned below. Other such standards include IBM's Document Content Architecture (DCA) format for documents and various standards developed for specialized purposes, such as the Spatial Data Transfer Specification (SDTS) developed for exchange of digital cartographic data [DCDS88], and and protocols developed for banking documents by the ANSI banking standards group (X9). DDF The Data Descriptive File (DDF) for information interchange is (as of the last reference available) a draft international standard under development by ANSI and ISO. It establishes media and machine independent formats for interchanging information between computing systems. The proposed ISO standard specifies: --------------------------------------------------------------------------- ? media-independent file and data record descriptions for information interchange ? the description of data elements, vectors, arrays, and hierarchies containing character strings, bit strings, and numeric forms ? a data descriptive file comprised of a data descriptive record and accompanying data records that enable information interchange to occur with minimal specific external description. DIF The Data Interchange Form (DIF) standard is used widely in PC software. A number of commercial software houses dealing with personal computer software have agreed to use DIF for interchanging simple, two-dimensional tables of data (initially, spreadsheets) Like the DDF, a DIF file has two parts: a "header section" containing descriptive information about the table, and a "data section" containing the data values. The DIF format is much simpler than the DDF format in that it does not attempt to handle variable length records, variable occurrences of data values, sequences, arrays, bit string data, or nested repeating groups. IGES The Initial Graphics Exchange Specification (IGES) is a neutral format developed to facilitate translating data from one CAD system to another. Vendors need only provide translators from their proprietary internal formats into and out of IGES. File translations can then be performed by converting one system's file into IGES using the translator supplied by that vendor, and converting from IGES into the format of the other system using the second system's IGES translator. 2.6.2 Data Definition Standards These include standards for the definition of various types of frequently-used data, such as standards for dates, Social Security numbers, etc., and specify standard meanings for certain data elements, what values may exist, lengths, etc. They facilitate integrating data from multiple systems, even when other aspects of the systems, such as data models, may be heterogeneous. Examples of data element standards used in the government include MIL-STD-482A, for configuration status accounting data and DoD 5200.12M "Manual for Standard Data Elements". The universal numbering system suggested for use within some systems is another example of a data element standard. A set of standard cartographic database entities, attributes, and relationships is specified in [DCDS88]. 2.6.3 Protocol Standards These include standards for protocols between components in systems. Such standards define a mutually-understood "language" among the components, which enables them to communicate. Such standards are relevant to the DOM project is providing examples of protocols that may be used in distributed systems that may be created using DOM technology, as well as providing models of protocol --------------------------------------------------------------------------- specification and development that may be used in developing DOM-specific protocols, such as the DOM Common Object Protocol (DCOP) described in Sections 1 and 3. X.400 Recommendations The X.400 recommendations are a set of protocols for message-handling systems defined by the CCITT (Comit? Consultatif International de T?l?phone et T?l?graphe) in conjunction with the ISO (International Standards Organization) OSI (Open Systems Interconnection) layered architecture. These protocols define how messages are transferred among public and private communication networks. Messages can include text, graphics, facsimile, voice, and other forms of information. The protocols cover such things as representation standards for various types of data and conversion rules, as well as protocols for message exchange and invoking remote operations. SQL The ANSI Structured Query Language (SQL) definition specifies the syntax and semantics of a set of interfaces to a relational DBMS. The specification was developed by ANSI Technical Committee X3H2 (Database) from the original IBM definition. The specifications provide facilities for both defining, querying, and updating relational databases, and include facilities for using SQL expressions from within programs written in host programming languages such as COBOL, PL/1, and Fortran. SQL is used in IBM's DB2 DBMS, as well as other DBMS products, such as ORACLE, available on both mainframes and PCs. In addition, a number of independent DBMS vendors have announced that they are developing SQL interfaces for their DBMSs. Thus, SQL is rapidly becoming both an actual, as well as a formal, DBMS language standard, at least for relational or quasi-relational DBMSs. RDAP The Remote Database Access Protocol (RDAP) [ECMA85] is a protocol to allow applications (called "clients") to interact with remote "database services" over a communications network. It is being developed by the European Computer Manufacturers Association to function at the Application Layer of the OSI reference model. In its original form, it was based on the ANSI SQL specification, but is currently being generalized to operate with multiple DBMS languages. It is also being further developed to enable it to work with various existing standards developed in connection with the OSI model, such as file transfer protocols. The RDAP is based on the semantics of an ordinary data manipulation language (DML), such as SQL, plus additional functions necessary within a distributed database system, such as a mechanism for negotiating the type of service required, commands to negotiate the data types and their encoding, facilities for matching the number of rows retrieved by the database service to the number of rows needed by the client, facilities for the exchange of status information (e.g., for recovery), and concurrency control functions. --------------------------------------------------------------------------- CAIS The Common Ada Programming Support Environment (APSE) Interface Set (CAIS) is a set of operating system level interfaces designed to facilitate the sourcelevel transportability of tools between APSEs [OBER88]. The CAIS is intended to provide the transportability interfaces most often required by common software development tools. The interface specification, designated DOD-STD-1838, was issued in 1987. CAIS is supported by a layer of software called a Kernel APSE (KAPSE) which translates services defined at the CAIS interface to codes on the underlying host computer system (native operating system and hardware). The CAIS provides a common system model, based on an entity-relationshipattribute (ERA) approach. This model allows tools to share and understand common data. In addition to the database-oriented ERA model, CAIS includes a process model. Current work is ongoing to extend the capabilities of CAIS to include: ? user-defined typing within the ERA model, including type inheritance. ? definition of event-driven triggers ? transactions ? explicit support for distribution CAIS is among the standards being used in the VHSIC EIS effort described in Section 2.5. Another set of operating system level interfaces being developed as a standard is the Posix standard. This is currently under development by IEEE (IEEE 1003.1 draft 12), as well as by the National Bureau of Standards as a Federal Information Processing Standard (FIPS). Daisy This is not a protocol per se, but represents important work relating to protocol development. Daisy (Distributed Aspects of Information SYstems) [HATZ87] was an ESPIRIT project which, among other things, defined an architecture to permit knowledge-based systems to interact in a logically-direct fashion, using lower layers of the OSI architecture. The project developed an architecture and a protocol for the interactions and is looking at concurrency control and higher level manipulations. This report tries to draw attention to the fact that there is a large gap in advanced research for the integration of distributed database concepts with the worldwide accepted OSI methods and architecture. Moreover, as knowledge based system technology becomes more and more tied to modern database technology great emphasis is given to the aspect of integrating this technology into the overall architectural approach for distributed systems. The report noted that the OSI Reference Model for Open Systems Interconnection has contributed invaluably to the progress and especially to compatible structures of modern communication systems during the last years. Work on standards for the various layers of the model has reached such a level of maturity that for certain well defined applications concrete interworking in multi-vendor environments could be demonstrated [HANN87]. An important application in the uppermost layer of the --------------------------------------------------------------------------- ISO reference model is the interworking of the distributed components of database management systems. However, no communication standards are available today for this interworking [but see the discussion of the Remote Database Access Protocol above]. On the other hand, work on a reference model for database management system's standardization has been finished by a task group of ANSI/X3/SPARC [RMD85]. It is clearly stated in this ANSI report that, although the database reference model must relate and use the OSI framework, it cannot be framed within the OSI model. In [POPE83] the compatibility and some drawbacks of both models were discussed and a proposal was made for a gross architecture for the design of distributed database systems in an OSI environment. The report also cites a nationwide research and development program on "Interoperable Database Systems" (and its role in OSI promotion) started in Japan in 1986 [TOJO87], which will investigate a broad range of interrelated topics from: - distributed database system technology, - multi-media technology, - high reliability technology, - interoperable network system technology. Some of these are also investigated within the ESPRIT-Program. However, an integrated approach to the distributed database problem at the European level is not identified. The report also cites another important aspect of distributed processing beyond the current reference model that must be taken into account. This relates to the very recent efforts in standardization within ISO/TC97/SC21 toward developing a Basic Reference Model for "Open Distributed Processing - ODP" This encompasses the important concepts of modern information processing systems, including database technology [ODI86]. It should be noted that ECMA is one of the strongest supporters of this extended new approach to a standard open architecture [ECMA87]. 2.6.4 SAA Systems Application Architecture (SAA) is a collection of selected software interfaces, conventions, and protocols, and thus includes all the types of standards mentioned above. These are being published by IBM, and are now or will be embodied in IBM software and hardware products. SAA is described in some detail here because of the widespread interest in the industry it has created, and because of its scope. Further information about SAA may be found in its technical documentation, such as [IBM87a,b]. A description of how SAA may impact GTE Corporation is given in [GTESC87]. A brief description of how SAA's goals differ from those of the DOM project may be found in [MANO88]. SAA will be the framework for developing consistent applications across the future offerings of the three major IBM computing environments: ? System/370 (TSO/E under MVS/XA and CMS under VM) ? System/3X ? Personal Computer (Operating System/2 ?) --------------------------------------------------------------------------- The goal of SAA is, by defining a standard set of services, and associated interfaces, to make its various operating system environments "look the same" to: ? application programmers using standard SAA programming tools ? applications utilizing common services, such as the same compilers and database management systems that recognize SQL calls ? users interfacing with SAA applications that appear identical in all operating system environments. Ideally, SAA would render the underlying operating system and hardware irrelevant in these cases. SAA has four major elements: Common Programming Interface, Common User Access, Common Communications Support, and Common Applications. More detailed descriptions of SAA can be found in the references cited above. The components of the Common Programming Interface (CPI) element consist of languages, including an Application Generator, C, COBOL, and FORTRAN, and services, including Database Interface, Dialog Interface, Presentation Interface, and Query Interface. For each component, IBM is establishing a definition or specification. In general, these have been developed with regard for established industry standards. A number of existing IBM products are already aligned with these specifications. Examples include compilers for COBOL and FORTRAN (based on ANS standards). Similarly, the Database Interface services specification is based on ANS SQL (including its cursor and host language interface facilities). The Dialog Interface is based on the functions provided in the OS/2 Dialog Manager. The Presentation Interface is based on functions provided in a number of the IBM environments (the windowing functions are entirely based on the OS/2 Window Manager). The Common User Access (CUA) element defines the rules for the dialog between the human and the computer. The idea here is to provide a familiar user interface across multiple applications and host systems. An approximate equivalent to the CUA are the specifications and guidelines for the Macintosh user interface (e.g., that the leftmost menu item is always the File menu; that "SAVE AS" on that menu always does the same thing). The Common Communications Support (CCS) element provides connectivity between applications, systems, networks, and devices. It tries to do this by the consistent implementation of designated communications architectures in each of the SAA hardware environments. These communications architectures will serve as the building blocks for distributed functions to be defined in later developments of the CPI and IBM-supplied SAA applications. The architectures defined exist at multiple levels of an OSI-like architecture. Examples include Data stream level (Document Content Architecture; 3270 Data Stream), Session Services (LU Type 6.2 program-to-program communications protocol.), Application Services (Document Interchange Architecture; SNA Network Management Architecture) and Data Link Controls (Token-Ring Network; X.25). Most of the defined architectures are already supported in the SAA environments. In the Common Applications element, IBM has indicated its intent to develop applications that conform to the SAA, making use of the CUA, CPI, and CCS facilities. These will be key applications that satisfy significant customer needs for --------------------------------------------------------------------------- use across the three SAA computing environments. Initial application development focus will be on integrated office and decision support facilities. The initial elements being defined include document processing, document library, personal services and mail, and decision support. 2.7 Distributed Artificial Intelligence Distributed artificial intelligence (DAI) is concerned with cooperative solution of problems by a decentralized and loosely coupled collection of "knowledge sources" or "intelligent agents" (IAs), each potentially located in a distinct processor node [SMIT85]. The IAs cooperate in the sense that no one of them has sufficient information to solve the entire problem; mutual sharing of information is necessary to allow the group as a whole to produce an answer. The agents are decentralized in the sense that both control and data are logically and often geographically distributed; there is neither global control nor global data storage. The agents are loosely coupled in the sense that the individual IAs spend most of their time in computation rather than communication. The processor nodes may be physically as well as logically distinct. There are a number of reasons for studying such systems. One motivation is the ability to build more powerful problem solving systems with greater speed, reliability, and extensibility. Another is that some problems exhibit characteristics to which DAI might naturally apply, such as natural spatial or functional distribution. Still another motivation is that some issues in problem solving and reasoning (such as communication and coherent cooperation) are most naturally studied in a distributed system. A wide variety of issues have been investigated in the context of DAI, including: organizational structures of the IAs, modes of cooperation between them, amounts of intelligence required of agents, amounts of communications required between them, and methods of determining parallelism possible in computational tasks. Pragmatic issues are also important, and DAI has also included work on underlying computer system architectures to support this type of distributed processing, such as the Agora project at CMU [BISI87], and the use of blackboards as a means of sharing information. The development of the actor model, discussed in Section 2.1.1, is also closely related to work in DAI. Work in DAI is relevant to the DOM project because of our interest in improving cooperation among system components, some of which may themselves be "intelligent agents", and because of the relationship of this work to object technology, as exhibited by the actor model. Also, relevant work has been and is currently being performed at GTE Laboratories in this area [DAVI88, SAND84], and we hope to fruitfully interact with these colleagues. --------------------------------------------------------------------------- 3. DOM Technical Issues The development of the technology underlying the distributed object management capabilities described in Section 1 requires dealing with a wide range of issues, some of which have been mentioned already. In many cases, these issues are active areas of research in the various technology areas described in the previous section: programming languages, database management systems, operating systems, and artificial intelligence. This section provides an overview of these issues. The intent is not to be exhaustive, but rather to provide an idea of the range and types of issues that exist, and are being investigated, in connection with this topic. The issues have been divided into several general topic areas. These areas are not orthogonal, since the issues are highly interrelated, as will become clear from the discussion. These areas are: Object Models: These are issues related to the definition of models describing the characteristics of objects within the system. Distributed Object Management: These are issues related to supporting distributed, persistent, shared object management for cooperating components running on a network. System Architectures: These are issues related to what network components must exist to provide DOM functions, how object management functions are distributed among components, and how these components must interact in order to support required processing. System Security: These are issues related to providing adequate protection for components (and objects residing on them) that are a part of the system. Applications and Methodologies: These are issues related to interactions between assumed applications of our system and design requirements and methodologies. Each of these areas will be discussed in a separate section. 3.1 Object Models An object model can be considered as an extension of a data model, namely, a set of object classes, together with the operations permitted on those object classes, at a particular interface within a system. The model may be considered as a mathematical model of the semantics of the interface. The capabilities defined by the object model must then be supported by the various languages and run-time facilities associated with the system. Distributed object management requires dealing with multiple object models, in order to provide interoperability between the heterogeneous components implementing them. This requires understanding the wide range of object model issues. In addition, a key part of our current system concept is the DOM Common Object Protocol (DCOP). The DCOP is effectively created by the DOMs (i.e., the specialized components added to the system to provide DOM functions), implementing the objects in the model using the processes and data provided by both the DOM components themselves, and the applications, knowledge-based --------------------------------------------------------------------------- systems, database systems, etc. that are integrated into the overall system via the DOMs. Users will then be able to interact with the system as a unit in terms of the DCOP. The DCOP will provide a set of built-in object classes, together with methods defining the semantics of a set of messages to which each of these object classes is prepared to respond. As is usual in object-oriented models, the DCOP can then be extended by users to support application-specific requirements, by adding their own object classes defined in terms of those provided in the DCOP. The primary goal of the DCOP is not necessarily to subsume application processing or database management functions, but rather to capture sufficient information to allow the DOMs to efficiently perform their task of coordinating and managing objects within a large, heterogeneous, shared collection of components, including workstations, large persistent data/object stores, mainframes, etc. Such information is not necessarily captured by either individual application development or database languages (even object-oriented ones), since they are generally not designed to deal with such a range of object characteristics. However, the DCOP will have to integrate concepts from object-oriented programming languages, AI knowledge representation languages, and object-oriented database systems, in order to provide the required functionality. Thus, a key challenge in designing the DCOP will be the integration of required concepts from many different paradigms, and the development of necessary new concepts, in order to deal with the new requirements. Key issues in designing the DCOP will be the extent to which such a model is feasible, and whether it will be possible to design a DCOP without subsuming a great deal of the local component semantics, and the desirability of doing this if it is required. There are many issues associated with the design of object models, because there are differing notions of object among the models found in various object-oriented systems. For example, the intraobject computation style may be based on any of the paradigms described for object-oriented systems in Section 2, such as imperative, functional, or rule-based. An object may or may not be thought of as having an inherent process associated with it. Messages may be passed in different modes, such as asynchronous messages, or synchronous or asynchronous remote procedure calls. The models may have different mathematical foundations (or none at all), raising issues such as completeness and consistency of the models. Related issues also exist regarding languages or notation associated with the object models. The same object model may support multiple languages (just as a data model, such as the relational model, may support multiple languages) tailored to specific purposes or user preferences. Issues associated with languages include the set of required features, user environments in which the language can be used, and whether or not the language can developed as an extension of some existing (and thus perhaps more familiar) language, or whether an entirely new language is required. The following subsections describe a range of issues associated with object models. 3.1.1 Modeling Object Movement and Storage A major issue in distributed object management is the development of techniques to support efficient movement of objects between distributed components, such as staging between knowledge-based applications and large, shared, persistent object stores supported by database systems. In order to provide this service, the DCOP must capture information about component (e.g., application) object --------------------------------------------------------------------------- requirements that the DOMs can use in efficiently supporting those requirements. (In many cases, this information will be provided by the application itself, through the use of specific constructs in the DCOP that indicate what the application requirements are, such as the use of a query specification to indicate that the application wishes to deal with a set of objects.) Similarly, the DCOP must capture information about component capabilities that the DOM can use in determining how to support those requirements. Thus, an important set of issues concerns how to capture object movement and storage information in the DCOP. As noted in Section 2, the languages used for many of the applications we are considering, such as knowledge-based applications, generally do not provide the type of information required to optimize object movement, usually because they are not designed with access to external components, such as persistent object stores, as a built-in concept. For example, while some production rule languages such as OPS5 [BROW86] provide for access to external files, these files are not treated as an extension of the working memory of these systems. Instead, users of these languages must explicitly indicate when data from external files is necessary, and the data must then be explicitly converted into objects that can be accessed by the production rules. Swapping data out onto external files when the working memory becomes full is even more difficult, and the use of external files for rules (as opposed to data) is often not available at all. One type of efficient access to be provided by the DOM is that of access to groups of objects, based possibly on conditions to be satisfied by the objects (i.e., queries). As in the case of conventional database queries, if the application is able to indicate that it wishes to process all objects in a particular group of objects, rather than accessing each object separately, the DOM may be able to optimize processing of the request. In particular, the DOM will be able to move the group from secondary to primary storage efficiently. The difficulty of providing this type of information from the Prolog logic programming language to an underlying database system has already been the subject of some investigation (e.g., [JARK84]), but the problem also exists in more conventional languages [SMIT83]. The DCOP can provide a number of facilities to allow this type of access. First, it can allow specification of objects representing groups of objects (such as the sets and bags in Smalltalk [GOLD83]), or groups of objects satisfying specified conditions (such as the selection expressions in PDM [MANO86b]), together with constructs for accessing individual objects via those group objects. Second, it can allow facilities for indicating which methods will be most frequently used in selection expressions, so that, for example, indexing techniques can be employed to improve performance in secondary storage. The DCOP can also allow applications to specify type constraints on method parameters used in expressions in order to allow for request optimization (since in this case the classes of objects referenced in the expression, and thus object staging strategies, can be determined in advance). When such optimized expressions are used as selection expressions in the definition of group objects, the DCOP can allow these group object definitions to be saved in their optimized form if they will be frequently used, as a form of "saved query". In addition to those defined by selection expressions, the groups of objects to be accessed together may be based on predefined relationships among the objects established by the definition of object methods. Any object model must allow for the definition of interobject relationships, such as the relationship of an employee with his or her employer, the relationship of a program with its subroutines, or the --------------------------------------------------------------------------- relationship of a VLSI component with its subcomponents. In addition, it is important to be able to capture the fact that a certain group of objects (related in specified ways) constitute a "template" for composite objects that will appear repeatedly [BATO84,DAYA85]. In addition to such "data" relationships, "processing" relationships may also be involved, such as groups of rules likely to be evaluated together in a knowledge-based application. Efficiency can be gained if it is possible to determine whether objects related by such relationships are likely to be accessed together by any application accessing one of the objects, since the related objects can then be staged from secondary storage at the same time. Efficiency can also be gained if it is possible to determine, when a message is sent to the object, how much of the object is required to execute the operation referenced in the message, since unrequired portions need not be staged. If the objects are likely to be accessed together, efficiency can be gained by clustering the objects together on secondary storage. However, it is also necessary to allow separate storage of object subcomponents when they will not be accessed together. This is important in order to avoid unnecessary movement of data to and from secondary storage, and particularly if object components are very large (and perhaps larger than the workstation primary memory). Users of the DCOP (who may in fact be application developers rather than end-users) should be able to specify when objects will be accessed together, and to control aspects of object clustering, either directly in the DCOP, or in related, but hidden, specifications in the underlying DOM. These facilities will be based on those found in some database systems [CHAN82], but extended to support the more complex requirements of knowledge representations and object-oriented systems. Another type of inter-object relationship exists when aspects of one or more objects (e.g., the values of their attributes) are dependent on or derived from aspects of some other objects. In an object-oriented model, the distinction between stored and derived (computed on demand) data is blurred, since the user of an object sees only the message that can be sent asking for the value, not how the value is produced. However, when a derived object (or one of its attributes) is only infrequently accessed, it is inefficient to rederive it each time one of the states on which it depends changes; rather, it should only be derived on demand. On the other hand, if a derived object is frequently accessed, but the objects on which it depends are infrequently changed, it would be more efficient to derive the object and store it once. As a result, it should be possible to specify in the DCOP information describing how and when derived objects should be maintained. An example of work investigating some of these issues is [DAYA84]. Still another form of relationship among objects is when new objects that are created should be considered as new versions of existing objects, rather than as entirely new objects [KATZ85]. Capturing information identifying these semantics can have important performance implications. For example, when changes are made to an existing object, and it is known that such changes create a new version of the object, it may be possible to save processing time and storage space by recording only the changes in persistent storage, rather than creating an entire new object. This can be a significant savings in applications dealing with potentially very large objects. Also, data sharing (discussed below) can be simplified in this case, since concurrent users may freely access the original object while the new version is being created. Object model issues exist relating to the transparency and location independence of such facilities. Transparency and location independence refer to whether the user of the language must be or can be aware of whether object interactions involve remote --------------------------------------------------------------------------- versus local interactions [TOML88]. By generalization, these issues also include whether a user must be aware of object interactions that involve movement within a memory hierarchy (main memory vs. disk memory), or transient versus persistent objects. The distinction of remote versus local tends to be of concern in distributed or looselycoupled systems, due to the large difference in cost between messages sent to local versus remote objects. In some architectures the cost of sending messages is relatively insensitive to location due either to the use of shared memory or interconnection networks of very low latency (e.g., 2 to 3 times a local memory reference). On the other hand, message passing over local area networks is typically in the 10 millisecond range as opposed to local times on the order of 10 to 100 microseconds. Most object models support some degree of location independence, but if the object model is intended for use in distributed implementations (or with large object spaces on secondary storage) models sometimes provide mechanisms for specifying relative placement of objects (clustering). This issue is illustrated by a number of distributed Smalltalk implementations that have been described recently. For example, [BENN87] describes a distributed implementation of Smalltalk based on the use of the built-in DoesNotUnderstand message in Smalltalk to trigger processing of distributed messages. The system provides for objects on different machines to send and respond to messages with location transparency. Each node contains a remote object table, and remote objects are represented by local proxy objects. These are, in effect, local stubs in a remote procedure call mechanism to which the local objects can send messages that trigger distributed access. Another paper [MCCU87] in the same proceedings [MEYR87] described a similar approach. In effect, this implementation approach relies on an "object fault" mechanism, similar to the page fault mechanism used in virtual memory systems, in order to provide location transparency. Unfortunately, waiting for "object faults" creates problems similar to those associated with "record-at-a-time" database access: the requests are difficult to optimize. This is a particular problem when distributed accesses are involved. Thus, providing explicit model constructs that provide indications when sets of objects are likely to be involved in application processing can help considerably. Related techniques might involve the use of descriptive programming techniques for defining methods, which might allow a tighter integration of programming language compilation techniques with object access methods, and "application models" that might allow the DOM to anticipate component requirements for objects and prestage them. The feasibility of using these approaches is related to the data access patterns that can be expected in the various applications. It may be that for many applications, one can either expect programs or users to explicitly indicate ahead of time when they want a collection of objects, by accessing objects representing collections of other objects, or through the use of explicit queries as is done currently in programming language interfaces to relational DBMSs, or get adequate performance by "object at a time" methods. Implementing these facilities may require providing them in the DCOP first, and then propagating corresponding enhancements into the application development languages Providing a facility for an object or application to indicate the objects it is interested in by a description (query) involves a certain knowledge by the object or application of what types of objects are available in the system. This is a general issue in large- --------------------------------------------------------------------------- scale distributed systems. In this type of environment, there will be a large population of independent objects. These objects can migrate in the network, and the population will be continuously evolving and expanding. When an object is created, it "knows" (has information) about a number of objects in its immediate environment. However, in general, the object may need to communicate with other, totally unknown, objects. The problem is how two objects unknown to each other can be "introduced"; that is, how an object determines the identity of another object with which it may want to communicate. This cannot totally rely on the user or the object's local (application or component) object manager, since the user does not (and should not) know all the existing objects, and the local object manager does not necessarily know objects outside its jurisdiction. In database systems, information about the types (classes) of objects available in the database is provided to application programs in the database schema, possibly together with a view of that schema defined for the particular application. This metadata must be generalized in an object-oriented system to include not only the classes of objects, but their protocols (what messages they respond to). Such facilities are provided in object-oriented programming languages, such as Smalltalk, by browsers [GOLD84]. However, current browsers are generally used when programs are being written. In the more general environments we are considering, it is desirable that these browsers be accessible at run time as well, since the configuration of the distributed system, and the objects available over it, can change dynamically. The beginnings of facilities of this type can be found in the "location brokers" and name servers found in some distributed operating systems. Ultimately, these facilities will need to help support the more general negotiation protocols found in distributed AI systems among cooperating agents. Since an object-oriented system consists of units comprising both procedures and data, it should be pointed out that the issues of object movement described above relate not only to the movement of object data, but to the methods (procedures) as well. For example, in a distributed Smalltalk system, an object might reside at one location and its class object (containing the methods) at another. In a given access to the object, it may be cheaper to move the method to the data rather than the data to the method. In general, it may be the case that the code for object methods resides in one location (e.g., a large data repository storing a subroutine library), but must be executed at another. Moreover, it may be that "clusters" of methods can be identified, and moved to the required data as a unit (a functional language employing function composition would identify groups of methods to be applied in a very direct way). It is possible to think of the problem as a generalization of the problem faced by a distributed database query optimizer, where both the data and the operations to be performed on the data can move. Related technology involving migration of executing processes has been investigated in the context of distributed operating systems. Finally, the distinction between transient and persistent objects is another issue related to transparency. Section 2.2.2 defined persistence as a property of data that determines how long it should be remain in existence as far as the computer system is concerned, noted that, with most programming languages and expert system shells, data and knowledge objects in the program's address space are transient, i.e., they exist only as long as the program executes. On the other hand, some of the components that we will be attempting to integrate are database or file systems that maintain data whose persistence does extend beyond the execution of individual programs. Such data is termed persistent. Persistent data may be maintained for archival purposes. However, a particularly important use is to maintain --------------------------------------------------------------------------- state information about some aspect of the system itself, or of the real world. This use is often reflected in database systems. Section 2.2.2 describes the advantages of having transparency between persistent and transient data types, in terms of ease of mapping, type checking, and concurrency control. For those reasons, incorporation of the semantics of persistent objects in the DCOP is an important design goal. Achieving this, particularly in a transparent way, involves a number of issues. Some of these relate to exactly what aspects of persistence ought to be transparent, as opposed to those that should be explicit in the model. Some of these decisions may be made for practical reasons, or in order to more easily accommodate conventional database components. Algorithms that are appropriate for main memory may be highly inappropriate for secondary storage. This means that, whatever the syntactic similarities, the programmer must be aware sometimes of whether an object is persistent or not. Furthermore, the streaming, indexing, and filtering operations that are provided by database management systems have seldom been provided, or needed, by programming languages, because their storage is truly random access, and the amounts of in-memory data manipulated by programs have been relatively small. It may therefore be necessary to add extra operators for persistent objects in order to provide access to these facilities. In addition, it may be necessary to provide some means to explicitly indicate when an object's state should become persistent, if this cannot be determined automatically. Since the persistent storage supported by database systems is often used to implement long-term shared memory for components to interchange state information, these issues interact heavily with issues related to sharing discussed in the next section. They also interact heavily with issues related to location transparency, since persistent object storage is often implemented by a separate component (a network file server or database system). Finally, persistent object storage exacerbates the problem of an object determining what other objects are available in the system, since it creates the possibility of much larger object spaces than can be attained in individual application workspaces. 3.1.2 Modeling Object Concurrency and Sharing Another major issue in distributed object management is the development of techniques to support efficient coordination, sharing, and control of concurrent (parallel) processing activities within the system. In order for the DOM to assist in these activities, the DCOP must capture information about concurrency that can be used in efficiently supporting those requirements. In particular, the object model will invariably be based on a particular model of concurrent processing, and must contain specific operators to allow concurrent processing to be expressed. Thus, issues exist relating to what model of concurrency should be adopted, and what constructs should be provided to support it. The basic motivation for modeling logical concurrency is that the real world consists of activities that take place in parallel. Thus, being able to model this concurrency allows a more natural and modular system design. Such a model also allows the use of parallelism among components in order to gain performance, and the use of shared information to reduce redundancy. The languages used for some of the applications we are considering, such as knowledge-based applications, were not designed for use with a shared data --------------------------------------------------------------------------- space, and thus contain no primitives for synchronizing concurrent access by multiple users. In certain cases, primitive facilities are provided. For example, mutually exclusive use of certain facilities by separate processes can be ensured in the Smalltalk language through the use of Semaphore objects, which allow critical code sections to be defined, and availability of shared resources to be signaled. Still other languages have been explicitly designed to support concurrent processing. Object-oriented systems have generally adopted one of two approaches to modeling concurrency [TSIC88]. The first is to view objects as passive entities manipulated and shared by concurrently executing application programs. The object management system then controls and synchronizes access to these objects. This is the point of view taken by object-oriented DBMSs that do not include functionality for executing methods directly ("object servers"). The second approach is to consider objects as active entities themselves. In this case objects incorporate the notion of process (or multiple processes), and passive objects are modeled as "server" processes that do nothing but wait for and respond to incoming requests. This model directly reflects in its objects and messages the view of objects as separate computational components that communicate (share state information) by passing messages. This is the point of view reflected in actor systems. There are also choices within these two points of view. For example, among the object models that allow active objects, some object models provide only for autonomous objects that are constrained to execute their operations sequentially. Other object models provide for concurrent execution of object operations. Further, within those models that allow for object concurrency, we can distinguish between those models that allow for multiple objects to execute single operations concurrently, and those models that allow a single object to execute multiple operations (either the same or different methods) concurrently. Both the passive and active object views, and their variants have advantages and disadvantages. The "database" point of view explicitly models threads of control (encapsulated in the applications). It also directly models the characteristics of major classes of existing components ("applications", whether conventional or knowledgebased, and databases or file systems). Moreover, there may be implementation and performance reasons for expecting this separation to continue to exist. However, it has the disadvantage of separating the world into passive entities (objects) and "applications", which are not objects. This means that applications cannot be directly included in the object model. In particular, applications cannot directly communicate by passing messages to one another, unless a separate application communication model is defined. Further, this model does not generalize well to distributed applications, since in this case sharing must ultimately be modeled by message-passing. Finally, an additional synchronization mechanism is required to tell the object manager when objects are locked and when they are sharable. This means that semaphores, or some other mechanism, must be added orthogonally to communication through object interfaces. The active object view solves some of these problems at the expense of others. The advantages of this approach are that it is homogeneous (everything becomes an object), it is inherently distributed ( message-passing is used for all communications), and no additional synchronization mechanism is required (objects synchronize themselves through message-passing). It also allows direct modeling of "active DBMS" features such as condition-monitoring and rule processing that are currently being investigated, and would otherwise have to be modeled as "applications" on a passive DBMS. Such features reflect a trend toward added --------------------------------------------------------------------------- distribution of functionality in architectures that may be more easily modeled using the active object view. The disadvantage is that the model lacks an explicit notion of threads of control. Instead, specific message-passing patterns must be used in order to create the necessary control structures. This can create dangers similar to those that exist with arbitrary use of gotos. Also, the active object model does not explicitly say whether objects are persistent or not, and thus persistence semantics must be defined, and associated communication protocols developed, unlike the "database" model, in which objects are implicitly persistent. Frequently, research into object concurrency adopts either the database view [OBRI86] or the actors view [YONE86], although there have been attempts to integrate these approaches into a single model [NIER87]. It should be noted, however, that message-passing in object-oriented models is a paradigm, and the actual semantics required in a given case are determined by the definers and implementers of the particular language involved. Thus, different implementation strategies can be used in the actual implementation, even when the object model is that of active objects, and the underlying support for managing concurrency is an object-oriented database. Models can also be distinguished on the basis of the interaction primitives they support. These, of course, interact with the degree of concurrency that the model intends to support. An interaction between two objects involves at least one object sending a message to at least a second object that receives it (this includes the idea that broadcasts may be received by multiple objects). There may be more than one construct provided to send or receive messages in a given design. Another consideration for each of the constructs is whether the construct is synchronous or asynchronous. A synchronous construct is one that causes the sending object to block until some other message-related event occurs. An asynchronous construct is one that permits the sending object to continue processing once the construct is executed locally. These two dimensions give four possible choices for constructs: blocking send, non-blocking send, blocking receive, and non-blocking receive. All of these have been used in one way or another in various designs. There are four sets of constructs that characterize the main design approaches that have been taken [TOML88]: ? Asynchronous message passing: This consists of a blocking receive construct and a non-blocking send. Here, the underlying system is responsible for buffering messages that have been sent but not yet received. This style of interaction is basic to the actor model. ? Synchronous message passing: This consists of a blocking send and a blocking receive. The send blocks until the receiver accepts the message and the receive blocks until there is a message available. This style of interaction is basic to the Communicating Sequential Process (CSP) [HOAR85] family of languages. ? Non-blocking remote procedure call (RPC): This consists of two sends, call and reply, and a receive. Here, the sender is blocked from the time it issues a call until it receives the reply (indicating the message has been received). A related approach is the future RPC, in which the caller may proceed until the result is actually needed. In this case, the caller is given a handle (called a future) to a value to be supplied in the future. This approach is used in ABCL/1 [YONE86]. --------------------------------------------------------------------------- ? Blocking RPC: This approach preserves the usual serial programming model, but implements serial procedural interfaces via a communications facility. It is concurrent only to the extent that it supports relatively autonomous workstations that can concurrently share access to objects across a network. Language designs usually include composite constructs that allow larger actions to be specified in terms of the set of interaction primitives supported. Choices among these alternatives must be made on the basis of the requirements identified for the particular object model being designed. An important issue in the context of the DCOP will be the potential need to interface objects employing dissimilar approaches. This may be done in more than one way, such as defining a general concurrency model in DCOP, of which the individual approaches of the various objects are special cases, or adopting a particular approach for the system model, and developing interface components that map one approach into another when interfaces are required. A particular class of concurrency-related issues exists when considering the sharing of objects residing in large, persistent, shared object repositories, such as databases. In conventional DBMSs, data sharing is controlled through the DBMS's concurrency control mechanism, which provides facilities to ensure that users do not interfere with each other while reading and writing data. DBMSs divide user accesses to the database into transactions, and attempt to guarantee that transaction data accesses behave as if each transaction is the only one accessing the database (a condition known as serializability). This is usually done by giving transactions exclusive access to parts of the database for a limited period of time. The language syntax used to access the database allows the DBMS to determine the beginning and end of transactions (either by defining any given command as a transaction, or through the use of explicit commands indicating the beginning and ending of the transaction (such as SQL's COMMIT [ASTR76]), and what data is read or written by the transaction (although the latter often cannot be determined prior to run time). For the more general types of applications to be supported in distributed object management, more sophisticated forms of data sharing and application interaction must be supported. In particular, it is important to address forms of sharing that do not require exclusive access, or which reduce the use of exclusive access, since exclusive access reduces the amount of parallelism possible in the system, and thus reduces overall system performance. These new forms of sharing in turn require that the DCOP provide facilities to support the specification of the various forms of data sharing and application interaction. Examples are: 1. locks on objects that release themselves after some period of inaction on the part of the user process so that other processes can have access [SARI86]. 2. read locks that allow the object state to be periodically "refreshed" on the basis of changes made by concurrent updaters. 3. definition of policies for which transaction should wait or abort when conflicts occur on accesses to objects. 4. definition of protocols to allow negotiation over access to shared objects, or to at least allow notification that a conflict has occurred. --------------------------------------------------------------------------- 5. definition of compensating actions that can be performed when inconsistencies arise due to shared access [SARI86]. 6. definition of when a process can accept read access to an older consistent state (while allowing other processes to change the data) [CHAN81], or in which a process wishes to simply allow concurrent updates. 7. definition of when the object being constructed is a future or hypothetical object, and that therefore consistency checks can be deferred until it is determined that the object should be considered "real". 8. definition of when an update is to be considered as creating a new version as opposed to modifying an existing object. The DCOP should also provide support for information related to recovery, an issue that is distinct, but related to concurrency control. Again, efficiency can be improved if such information can be captured. For example, it should be possible to specify "save points" in long transactions, so that the DOMs, in cooperation with a persistent object store, will be notified to establish points from which efficient recovery can take place. Units of concurrency control and recovery can be defined either in terms of the operations that make up the transaction, as in usual transaction brackets (and thus by inference, involving all data used by those operation), or in terms of specialized data groupings defined in the DCOP (similar to the clustering constructs used to define groupings for data movement described in Section 3.1.1), such as the AREA construct defined in the CODASYL data model [DBTG71]. A possible way of organizing the above concurrency control mechanisms in the DCOP is to adopt the active object view, considering each object as performing its own concurrency control, using methods inherited from a supertype such as a type SharedObject. This is reasonable (at least in theory) in the context of an objectoriented system, given that instance variables are internal to an object, and are (conceptually) only updatable by its methods. In this view, each object schedules its pending requests independently. This is particularly reasonable if methods are implemented on special-purpose processors or distributed databases that can run in parallel. In this case, concurrency control methods would be defined as required methods to be supported by all (concurrently accessible) objects, that will be inherited from the generic SharedObject class. Optionally, specialized concurrency control methods can be specified to override the built-in ones. The DOM can implement concurrency control by sending messages calling the "concurrency control" methods to the objects involved. These messages will invoke whatever concurrency control technique is defined for the object, either the standard one, or some specialized technique. This idea, of course, must be investigated in detail before any conclusions can be reached about it. A particularly difficult special case will be coordination of intelligent agents involved in cooperative work on shared data. This requires relaxation of the database notion of "transaction", and a more flexible specification of correctness conditions, so that permissible interleavings of actions can be determined. Some strategies in distributed AI involve each agent having more or less information about the current and future activities of other agents, so that each agent can more efficiently coordinate its activities with the others. One approach to doing this extensibly might be to use a group of augmented transition networks (state transition graphs). This effectively --------------------------------------------------------------------------- creates a schema of the actions involved, rather than of the data, since that is where the complexity of the problem is. A similar approach could be used to anticipate data movement requirements required by the agents. 3.1.3 Integrating Multiple Component Models and Interpreters Another key requirement of the DCOP is the ability to allow the definition of objects that reside on heterogeneous components, are based on different object models, and are implemented by different interpreters or processors. In particular, we wish to support various types of knowledge representation techniques (such as situationaction rules for production rule systems such as OPS5, or Horn clauses for Prolog), as well as conventional programming languages and database systems. This is a concern for the DCOP because the DOM is intended support the requirements of multiple applications and components, which may be based on these different paradigms. Providing this capability requires more than the ability to merely capture, for example, the "text" of rules or Horn clauses as attributes of objects. It also requires the ability to capture knowledge about the forms of processing used in application systems employing these knowledge representation techniques. Moreover, this must be done in a "representation-independent" manner; i.e., it should not be necessary to bias the DCOP toward one particular style in order to be able to represent that style in objects. Ideally, the DCOP should deal with messages having rather general semantics. Message semantics may differ depending on the language paradigm being used, as this subject was described in section 2. For example, in Smalltalk, messages are imperative directives to an object to perform some operation, and must explicitly specify the object that is to receive the message, and the specific method selector. However, messages should not necessarily be restricted to being function calls with parameters that return results. Instead, a message might be a request to unify the message parameters with values local to the object. This would allow message parameters to be unbound variables. Generality of this sort has been described in the context of actor languages, e.g. [THER83]. Similarly, actor models allow patternmatching to determine how a message will be handled. Issues related to such distinctions become important in modeling objects found in multiparadigm languages, and particularly in knowledge-based systems, which frequently employ such languages. One class of issues involves what object model capabilities are required to deal with object characteristics found in the components to be integrated, and how best to reflect those characteristics in an object model. Investigating these issues will involve examining current attempts to develop knowledge-based systems in languages like Smalltalk, and to develop object-oriented forms of paradigms such as functional and logic programming, and rule-based languages. Also, the issue of whether to include such characteristics directly in the model, or to build them up from more primitive functions using the extensibility facilities of an object-oriented model, will have to be addressed. Another class of issues involves what information is contained in messages, and the semantics of method invocation based on that information. For example, in Smalltalk, a message must designate a specific object as the receiver, and must also contain a selector (textual name) for the method to be invoked. The run time system --------------------------------------------------------------------------- determines the actual message based on the class of the receiver object, and the selector (and may search up the class hierarchy in the case of inherited methods). However, [STEF86a] points out that this process is a special case of a general function application process. In general, the particular function (method) to be invoked can be determined by considering the classes of the various parameter objects specified in the message, as well as the receiver object. This more generalized approach is used in the CLOS object model, and could also be used directly to generalize database models, such as PDM [MANO86b], that use an object model based on a functional approach. This type of generalization could be used to allow a single object model to subsume a number of other object models of the same class. For example, in considering integrating programming language and database object models, [FISH88] observes, "...it is remarkable how much alike most programming languages are when they are stripped of syntactic differences and specialist features. Thus it seems possible that a well-chosen object-oriented data model will be able to support a fairly wide variety of object-oriented programming languages, and that interfaces to these languages can be provided which hide most of the differences between language objects and database objects." This work goes on to identify four basic mechanisms for operating on objects provided by any object-oriented programming language: ? the creation of a type, and its placement in the type hierarchy ? the creation of an operation for one or more types, with its associated data structures ? the creation of a new object (and possibly its later destruction) ? the application of an operation to one or more objects The integrating object model must provide operations for each of the individual steps that make up the creation of a type with its operations. Once these basic operations are provided, it may possible to put a syntactic layer around them that makes an object in the common model look very much like an object in one of the individual models. However, much of the above generalization is entirely imperative, in the sense that messages have the semantics of "perform this operation", and are issued from within other methods that are themselves imperative in style. It is also necessary to consider multiparadigm message and method semantics in order to directly incorporate constructs from, e.g., knowledge-based systems. In order to do this, it will be necessary to decide how to model such things as rules in an object-oriented way. There are a number of ways of doing this. (This, to an extent, depends on whether the "active" or "passive" object view is taken, as described above). For example, production rules are of the form if then . One can think of the condition part as being a message "doYouMatchThis" broadcast to the entire object memory (in parallel with the condition parts of all the other rules specified). The action part (method) of some rule would then be invoked --------------------------------------------------------------------------- on the basis of this match (together with other criteria used in rule selection activities, such as conflict resolution [BROW86]). This, in turn, requires considering how to model the condition parts. They may be separate, active objects, continually engaged in broadcasting these messages. However, such broadcasts still must be synchronized (so that, e.g., modifications to object memory do not interfere with condition checking). Work on some of these aspects of object models is being undertaken in CCA's HiPAC project [DAYA88]. How some of these concepts should be represented in an object model involves issues of modularity. For example, where should rules be thought of as residing? As associated with specific objects as methods, or as separate objects? Associating rules with specific application objects may be unnatural if the rules contain conditions that involve multiple objects. Such issues can be significant, given that one of the important aspects of a knowledge representation mechanism is how it can be used as a means of organizing knowledge. A related area to be investigated involves object model enhancements and information capture requirements for mechanisms supporting objects that allow different interpreters for their methods. In conventional object-oriented systems, the method interpreter is fixed, and effectively inherited from the environment. Probe [DAYA85] describes the concept of invoking arbitrary special-purpose processors to handle messages on specialized types of data (such as geometric data). It would be desirable to more thoroughly encapsulate the semantics of message interpretation in the objects. For example, it should not matter to the overall system whether a message effectively invokes a function on some instantiated arguments, returning a value (as in Smalltalk), or effectively asks whether the object (which happens to be a Horn clause in Prolog) unifies with the message, and returns some variable instantiations, as long as the sender and recipient of the message understand it. Similarly, it should not matter whether the message goes to one object, or is "broadcast" to a whole collection of them. Given a message to an object, the DOM might have information that tells it "in which processor" the object method must execute, where the definition of "processor" includes the combination of hardware, software, and (in a distributed system) location necessary to identify the correct interpreter for the method code. It would also have information concerning which fragments of the object's representation are required to execute the method (since the object representation may be fragmented among different sites). The DOM could then handle any data or code movement, resource allocation, and interpreter invocation necessary to execute the method. As noted above, this resembles in some respects the problem of executing a query in a distributed database system, since the algorithms for this process typically involve the movement of both data and parts of the query (the method). Performance and support requirements for these various message semantics must also be considered. Languages that involve pattern-matching of various kinds, such as logic programming or rule-based languages, must spend overhead determining when some instruction is to be executed. In imperative languages, this takes place largely in the mind of the programmer. The tradeoff between this programmer "think time" and the system determination may be (and obviously is, in some cases now) more favorable to one approach or the other with different hardware (e.g., parallel hardware) and applications. Finally, general issues exist in interfacing multiple object classes similar to those regarding interfacing multiple type systems among programming languages. --------------------------------------------------------------------------- Heterogeneous type systems and representations will exist in the architecture due to the need to support multiple machine architectures, multiple programming languages, and multiple software components. The basic approach to dealing with heterogeneous types is to have metadata about the source and target forms required (possibly including a type hierarchy/type equivalence declaration mechanism [KATZ81]), together with conversion (encode/decode) routines for use when needed. The conversion routines may or may not assume the use of canonical ("neutral") forms for the data. The use of a neutral (common) data format is frequently suggested in dealing with heterogeneous data types. The idea is that each data source provides an export routine to convert data from its local form into a "neutral" form, and each component requesting data provides an import routine to convert data from the neutral form into a local form acceptable to the requesting component. A request for data transfer then involves application of the export routine on one end of the transfer, and application of the import routine on the other end. This approach reduces the number of conversions that have to be provided for within the system. However, applying this approach in practice involves a number of issues that are often overlooked: ? It is not necessarily the case that data will require translation when moving between systems. This depends on the characteristics of the source and target systems. For example, moving data between components supporting the same type system will not require conversion. Use of a neutral form in such cases is unnecessary overhead. ? The difficulties of defining a neutral format suitable for all data in the system is generally underestimated. ? The overheads associated with conversion of data can become quite large. The tradeoffs must therefore be carefully evaluated. If storage space is available, it may make sense to retain data in all the forms to which it has been converted. Thus, if the data has been converted from an internal to a neutral form for transfer between systems, and the internal form has not been subsequently modified, the system can avoid the need for retranslation if the data is requested in a neutral form again by retaining the neutral form. This creates the problem of keeping track of the multiple copies of the data that now exist, but may make sense in some cases. On the other hand, if storage space is in heavy demand but there is available processing capacity, the opposite decision would make sense. The model must allow capture of information relating to these various aspects of conversion, e.g., what routines exist, what the representation of a particular object is, etc. Another consideration is that some type conversions necessarily involve losing data. It is necessary for the model to capture information concerning when such conversions are invertable, in order to provide both efficiency and safety. 3.1.4 Other Issues Relating to Object Models --------------------------------------------------------------------------- In addition to the issues described in the previous sections, there are a wide range of other issues relating to object models that are relevant to our work. Only some of them will be covered in this subsection. One such class of issues has to do with which facilities are provided by the model as "built in" facilities, and which must be added to the model by extending it using whatever facilities are provided for that purpose. For example, the actor model is generally considered to be a very "minimal" object model, lacking such things as inheritance, object classes, and complex data types as built-in constructs. In actor languages these would be defined, if desired, as scripts of simpler operations. Considering the object model as a type system in a programming language, the issue can be characterized as what primitive types and type constructors should be available in the model. In theory, this line is difficult to draw with an inherently extensible model. However, in some cases it is extremely difficult to "add on" facilities by extension in an efficient way, since it may be difficult to integrate extensions in the "ideal" location in the underlying software. Thus, this choice may have serious performance and ease-ofuse ramifications. The importance of these considerations has been recognized by the database community. For example, it has been observed that the basis of efficient processing in relational database systems is that relational (database model) operations (set-oriented queries) encapsulate iteration over all elements of a set (tuples of a relation); the user provides a property of individual objects, and the operator retrieves all objects that satisfy. This has led to suggestions to encapsulate iteration as a defined operation over other structured collections of objects, such as graphs, 2D objects in a plane, arrays, etc., that might be used in an object-oriented environment. Unbounded iteration (transitive closure), specifying a halting condition, has also suggested as a desirable facility, particularly in CAD applications [ROSE86], as is the basis of providing Prolog-like (logic programming) capabilities in database systems. Thus, in this context, issues arise concerning enhanced type facilities that might be useful, e.g., union types, arrays, nested structures, and graphs. Similar considerations have been raised about explicit support for temporal semantics in object models. Objects in general operate independently, possibly in coordination with other objects. In some situations, however, it may be necessary to force objects to be at certain points or states at certain times. This suggests the need to introduce a notion of time, real or artificial, in terms of which to define not only ordering of operations, but also sychronization of object actions. This is particularly important in the case of real-time applications, such as control of machines, in which it may be necessary to force objects to act under strict temporal constraints. Similar considerations apply in some cases of distributed AI. However, dissimilar notions of time have been identified for use in computer systems [TURN84, DAYA85], and thus incorporating a single model of time in an object model may not be appropriate. Alternative approaches are to use the model's extensibility facilities to add time-oriented concepts, or at least to define alternative concepts in terms of a simple, underlying concept. Determining what underlying concepts are required to support both efficient internal system functioning, and application-oriented extensions, is an issue. These issues also concern how the system architecture supports such extensions. This is discussed further in Section 3.3. The effect of object granularity is also an issue in designing object models. Object granularity refers to the bias that the model or language gives toward the sizes of --------------------------------------------------------------------------- objects that are intended to be cost-effective in an implementation [TOML88]. The actor model expresses computations at an extremely fine grain of concurrency (for example, there are no native serial data structures like lists or arrays). Other object models are biased toward larger granularity in that the programmer or user has more familiar data structures available. It is unclear to what extent the added potential parallelism available with smaller granularity can be taken advantage of in practice, at least on conventional hardware. On such hardware, the implementation of larger grained models would appear to provide better performance over longer serial sections of code. A larger grained model might also facilitate incorporation of existing components. A number of issues in the design of object models concern tradeoffs between the encapsulation provided by the model, and the ability of objects to share information. In the ideal object-oriented model, each object maintains its own local state that is accessible only by its own local methods. All other (external) accesses are achieved via message passing. In practice, some models violate this principle in various ways, which can create problems in a concurrent setting [TOML88]. Class variables in Smalltalk are an example of this type of problem. Class variables are accessible by instances of the class in the same way as local variables, but are actually shared by all instances of the class, and are stored in the class object. This creates two forms of object interaction in the model, one via message passing, and one via variable access up the class hierarchy. This can create complications both in implementation, and enforcing mutual exclusion on accesses to the class variables. Class inheritance can also be thought of as violating encapsulation by permitting methods defined for new subtypes to access inherited instance variables. One approach to these issues is to replace inheritance by delegation, the approach used in actor languages. Effectively, delegation is a purely message-based way of obtaining the types of sharing that are achieved in other languages via inheritance. However, it is not clear whether the purity of such a pure message-based approach is worth the possible implementation efficiencies that can be achieved by an explicit recognition of inheritance. Inheritance semantics are themselves an issue in object-oriented languages. Many feel that inheritance is a central characterizing feature that distinguishes object-oriented programming from other programming styles. However, there are many different forms of inheritance, examples being single-inheritance vs. multiple inheritance. These forms were described in Section 2.1.1. Multiple inheritance allows the declaration of more complex interactions among defined object classes. However, it has disadvantages. It requires a means of disambiguating multiply-inherited attributes and behavior, which can often be rather arbitrary and inelegant. This ambiguity sometimes makes it difficult to understand the semantics of a class, and may severely complicate schema modification. Moreover, viewing "inheritance" as a general term for a mechanism for sharing information in an object-oriented system, there are other mechanisms for gaining somewhat similar effects. One example is delegation, as noted above. Effects similar to multiple inheritance can be achieved by allowing objects to be instances of multiple classes, perhaps having one class serve as a core class, and other others serving to indicate various roles the object has during its lifetime. Also, there are many different forms of information-propagation and sharing that may be desirable in object-oriented systems. For example, there is ISA class inheritance, and the form of "inheritance" that might be desirable in a CAD system, where the color of a part --------------------------------------------------------------------------- assembly is inherited by the various parts comprising that assembly. Discussions of these issues can be found in, for example, [STEF86a, WEGN87b, STEI87]. A more general problem exists in the need for objects to share information about themselves for purposes of efficiency, or in cooperation among objects in concurrent processing activity. Some of the issues related to this have been described earlier. For example, conventional programming language interfaces to relational DBMSs involve the program indicating its intent to process a set of relational tuples by formulating and sending to the DBMS an explicit expression denoting this set. On the basis of this expression, the DBMS can then formulate an efficient access strategy. Extensions to this concept have been proposed involving applications sending DBMSs high level "application models", which can be used by the DBMS to anticipate application information requirements, and perform prefetching of data. Similarly, some strategies in distributed AI involve each agent having more or less information about the current and future activities of other agents, so that each agent can more efficiently coordinate its activities with the others. Each of these strategies involves some degree of violation of encapsulation, creating some dependence of one object or agent on internal characteristics of another. The extent to which this is a problem depends on the type of dependence established, and how easily changes can be made in the characteristics depended upon. Assuming that it is desired to share such information, issues exist related to the best means for representing such information, and distributing it to the intended recipients. A general issue in the context of developing a global model for coordinating heterogeneous components, such as the DCOP, is whether such a model does not invariably result in the development of yet another object-oriented programming language, by the time all necessary facilities are provided. This issue has been recognized by a number of groups developing such global models for specific applications, such as integrating software engineering tools. The problem that this creates is that it adds yet another model and/or language to the growing collection of object-oriented languages, and thus to the complexity of integrating them. On the other hand, if it is felt that existing models and languages are unsatisfactory, there is no real alternative. In particular, our own work will be concentrating on the model's ability to capture specific types of information relating to integration, as described in previous sections. Existing models and languages have not had this specific application in mind. Thus, we hope our own investigations will contribute to the solution, rather than to the problem. The overlap with existing work will, however, be something that has to be constantly kept in mind. Finally, the general idea of considering an object model as a programming language type system leads to a whole collection of issues involving how to identify concepts from programming languages, database systems, and other technologies related to data abstraction and strong typing in object models. Examples include such things as what strong typing means in this context, and how applicable it is, how strong typing can cope with dynamic binding of variables to object instances, how typecasting and coercion can be understood in an object-oriented language, and how type theories can capture the semantics of the various aspects of object-oriented languages, such as forms of inheritance. 3.2 Distributed Object Management In this section, we describe research issues in the development of Distributed Object Manager (DOM) facilities that provide distributed, persistent, shared object --------------------------------------------------------------------------- management for cooperating components running on a network. The DOMs perform a number of key functions. By providing unified access to heterogeneous objects found on network components, they allows integration of capabilities found on these components. By intelligently staging objects between components executing applications and components providing persistent storage, the DOMs provide applications with the illusion of a single, persistent, potentially unlimited object space. Finally, working in concert with the various components, they coordinate access to shared data and knowledge from cooperating components that may be running concurrently on different network sites. Research issues involved in the support of persistent object memory (for individual applications running on a given component) provided by a DOM, in cooperation with other components providing persistent storage are outlined in the first subsection. Research issues dealing with shared distributed object management (to support cooperating applications running on a network of components), provided through the interaction of multiple DOMs and other components providing persistent storage, are discussed in the second subsection. 3.2.1 Support for Persistent Objects The DOM is intended to provide relatively transparent access to components providing persistent storage facilities for components lacking such facilities. This will allow a DOM component to use persistent storage as stable storage to expand the address space available to individual programs, and to make objects persistent for sharing with other programs. In order to fully support persistent object data, it will be necessary to provide traditional database management facilities. In addition, DOM support for persistent, shared object management must build on work on object managers for persistent programming languages and object-oriented database systems. Like this work, our intent is to support the principle of orthogonal persistence. However, rather than supporting the simple object models of languages like Smalltalk and LISP, DOM is intended to support the richer DCOP discussed in the previous section, which combines features from object-oriented programming languages, knowledge representations, and database access languages. Facilities to be provided must include the following: 1. A strong notion of object identity that is independent of the key used in object selection and persists across programs, and ideally across components. 2. Support for traditional database queries (set-at-a-time processing), but defined in terms of objects. Queries in relational database languages may be viewed as select operations on the aggregate type relation [WEGN87a]. They have the form: select(relation,predicate) Query complexity and efficiency are determined by the nature of the predicate. Relational query languages specify all queries in terms of a restricted set of relational query primitives whose optimization has been extensively studied. Objectoriented query languages must accommodate the greater richness of object-oriented specifications for which optimization is not as well understood. 3. The ability to specify constraints and check that constraints are not violated as the database is modified. Specification of constraints is primarily an object model issue. If the model incorporation of rule-based capabilities, specification of constraints is --------------------------------------------------------------------------- straightforward. However, there are a number of open research issues involved in supporting rule processing over large, shared, persistent object stores [DAYA84, DAYA88]. 4. Support for multiple views of data. Ideally, this will include automatic updating of all views when base data is modified, and lazy updating for views that are not currently active [WEGN87a]. These issues are thus related to the "cache consistency problem" when portions of the views are materialized in local components for efficiency. 5. Support for object sharing by multiple applications. Databases must support transaction processing and concurrency control so that user requests can be processed in a safe but efficient manner. However, the model of sharing must be more flexible than for conventional DBMSs: the model should support cooperative work among designers, knowledge engineers, software engineers, or problem solvers, instead of assuming (as conventional DBMS concurrency control does) that all concurrent accesses to shared data necessarily conflict and hence must be serialized. 6. A high level of safety and resilience in the face of software and hardware failures. Facilities for aborting transactions and for failure recovery must be provided. 7. Security facilities that provide protection from unauthorized access or other use for data that may be created by different users. The combination of security and integrity facilities must also prevent damage to object data from malfunctioning object procedures (methods). 8. Efficiency in handling large volumes of data. Significant issues in this research involve techniques for improving performance -- exploiting semantic hints to prefetch related objects, using auxiliary index structures, and distributed query optimization techniques, for example. A large collection of issues exists regarding how best to provide these facilities within a DOM-based architecture. Some of these issues are described in subsequent sections of this report. Particular issues to be addressed in this section include the following: How are objects represented in the program's transient address space and on stable storage? How does the DOM automatically map between these representations (if they are different) when it fetches an object from stable storage into transient memory, and when it makes a transient object persistent? How does the DOM efficiently stage objects between the transient address space and stable storage? How is storage reclaimed in both spaces? And, how do objects persist in the event of a system crash? Object Representation and Mapping The fundamental characteristic of an object is its identity that distinguishes it from all other objects known to the system, and that is immutable for the life of the object. Internal to the system, an object is represented by an identifier or surrogate, which is usually a logical name or physical address. Objects can refer to other objects. Internally, these references are usually implemented by pointers to the referred objects; the value of a pointer is the identifier of the referred object. In the transient address space, it is desirable to use physical addresses for efficient access. However, when an object is made persistent, it (and all objects referenced by it) --------------------------------------------------------------------------- must be given a logical name. Conversely, when a persistent object is fetched from stable storage into transient memory, logical names and pointers may have to be translated into physical addresses. The problem is exacerbated when we consider the sharing of objects across the name spaces of different components. Fairly elaborate schemes based on persistent heaps and object tables are described in [ATKI87, MAIE86, KHOS87, KAEH86]. However, all of these schemes force a single representation for objects in transient memory (using object tables), and a single representation for objects in secondary storage (typically based on the clustering of component objects with their parent objects). Ideally, we want to support a range of possible representations both in main memory and in secondary memory. This is so for several reasons. Programs typically build elaborate data structures in main memory that are optimized for their specific algorithms. In the database, however, very different storage structures may be needed to optimize the execution of queries. For example, it is important to support associative search capabilities and flexible object representations on disk. However, in main memory physical structures must compete in efficiency with record and array structures, and so in main memory you want direct, fixed object structures not requiring search (i.e., allowing direct calculation of where data is relative to the overall structure). Moreover, these structures need to cope with aggregates other than sets. Finally, efficiency of moving objects between main memory and secondary memory adds additional considerations to both the storage structures that may be required, and how information about the source and target storage formats can be captured and effectively used by the DOM in optimization. Clustering Clustering (grouping objects in memory so they can be moved as a unit) is very important in object-oriented systems, since method evaluation frequently involves following pointers between objects, and pointer following on disk is very expensive. Issues include how to cluster object data so that appropriate parts of the object are staged to match the operations to be performed (the entire object may not be needed, and may be too large to fit in an application's memory in any case), and how to detect when related objects have to be moved along with another one, which may depend on the operations that have to be performed on the moved object. Many object-oriented database systems have defined physical clustering units ("cluster" in Vbase, "segment" in GemStone) in which application designers can explicitly place objects to indicate clustering. In an alternative approach, Trellis/Owl [OBRI86] uses information from the application to determine what part of an object is really used by a particular method or application, in addressing the issue of when and what (objects or parts of an object) should be moved from disk to main memory ("eager" vs. "lazy" movement). They provide hints to the system in the form of specialized forms of (interobject) references: always links, sometimes links, and never links. A prefetch(X) operation gets objects connected by both always and sometimes links. An ordinary reference gets only always objects. These same issues were the reasons behind a number of concepts used in PDM [MANO86b] involving the structure of extensionally-defined functions, and possible physical representations of them. An additional issue is that while prefetching is frequently considered as a possible optimization in object-oriented systems, prefetching is not cost-free. It only --------------------------------------------------------------------------- provides significant benefit if the hit rate is relatively high, since otherwise, the cost of moving unnecessary data will outweigh any efficiencies that might be achieved. Hence the tradeoffs between prefetching and basic "demand paging" must be carefully evaluated, and taken into account in optimization strategies. The approach to clustering used may need to be different on disk and in main memory as well. For example, instead of always clustering component objects with their parent objects, it may be better to cluster objects based on some other relationship between them (e.g., the designer) or not to cluster them at all. Special techniques may be needed for complex objects that share components or that are recursively structured. Many of the techniques developed for semantic databases may be appropriate [CHAN82]. The DCOP will also include knowledge representation capabilities. Designing an appropriate set of representations for the objects of the DCOP, both in transient address space and in stable storage, and the mappings between them, will thus be potential subjects of investigation. Indexing Searching a long collection by a sequential scan gives unacceptable performance with disk-based objects, and a large persistent object store should support associative access on elements of large collections. This means that it should supply storage representations and auxiliary structures, such as indexes, to support locating an element by its internal state. However, supporting these requirements brings with it a number of issues. For example, the need to create indexes creates a corresponding need for typing on collections and instance variables. To index a collection E of employees on the value of the salary instance variable, the system needs assurances that every element of E has a salary entry. Furthermore, if that index is to support range queries on salary, the system needs a declaration that all salary values will be comparable according to some total order. A related issue is whether indexes are based on the structure--the instance variables--of objects, or the protocol--the responses to messages [BRET88]. If indexes are based on message notation, the system must know which structural changes in an object can influence the result of a message, so that when to update the appropriate indexes is known. Indexing based on structure has the advantage that it can be supported without accessing the execution model, while message-based indexing requires access to the execution model. On the other hand, indexing on structure violates the privacy of objects, as it bypasses an object's protocol. One suggestion for dealing with this has been to reveal parts of the internal object structure in the object protocol, and only allow indexes on revealed structures. Intelligent Staging In some persistent programming language systems or expert system shells with DBMS interfaces, when an application attempts to access an object that is not in main memory, an "object fault" occurs, and the application's object manager automatically attempts to fetch the object from the database. This is inefficient, in general, for two reasons. First, the application must wait until the required object is fetched from the database and is converted to its main memory representation. It would be more efficient if the required objects are staged in ahead of the time they are needed by the application. Second, accessing the database to fetch a single --------------------------------------------------------------------------- object is usually inefficient. Typically, the application needs to iterate through a collection of objects. It would be more efficient to execute a database query to fetch all these objects at once, and then to iterate over them. For very large objects (those that span more than a page of secondary storage), the opposite problem also occurs: not all of the object may be needed at a time, and it would be more efficient to fetch only that portion of the object that is actually needed. For the DOM to intelligently prefetch objects, some additional semantic information about the applications must be supplied. Object model constructs for supplying this semantic information are issues in the development of the DCOP. For conventional database applications, transactions can provide such information: a transaction can be preanalyzed to determine its readset and writeset and all the data objects in these sets can be prefetched. Views provide another contextual mechanism. For knowledge based applications, other hints may be provided. For instance, frames and scripts are contextual devices that can be exploited by the DOM. For rule-based knowledge representations, a preanalysis of the rules may yield relationships between the left and right hand sides of rules, and these relationships can be used to set up an index structure that aids in determining which objects to prefetch. For complex objects that have many components or that are transitively linked via pointers to many other objects, hints on how much of the object to bring in, would be useful. In [ROWE86], a hint mechanism for hierarchical objects that may share substructure is described. These and other approaches to exploiting semantic hints or contextual information in intelligent staging are research issues. The use of this information to set up auxiliary data structures that aid the DOM in intelligently staging objects is an issue both in the design of components, and as it affects the design of the object model. From the semantic hints and contextual information, the DOM will need to construct queries to the persistent object stores to fetch the required objects. Because the objects may be distributed throughout the network, e.g., in databases or in the local storage of other components, distributed query optimization techniques, which have been developed for distributed database management systems, may be useful. Most query optimization research has focused on the problem of optimizing relational queries. These techniques will have to be extended to work for queries in the DCOP. In the relational data model, there is a fixed set of operations (e.g., selection, projection, join). Object-oriented models, however, are extensible: arbitrary operations can be defined by the applications. The optimizer must correspondingly be extensible. When an object class is defined, the methods for implementing the operations of the class must be defined as well. In addition, various properties of these methods (e.g., their relative costs, the sizes of temporary results relative to the sizes of the operands, algebraic properties of the operations) must be specified: these descriptions are used by the optimizer in determining the optimal strategy for processing a given query that involves these application-defined operations. Finally, the location of the methods themselves may be a factor in the optimization, since the methods need not be located on the same site as the data on which they will be operating. This might be true if the "method" is actually a pre-existing software tool which must be fed data from different locations in the network. Extensible, description-driven query optimization is still very much an open research problem [GRAE87], and techniques for optimizing queries in the DCOP are significant issues. Related issues include whether the use of descriptive programming techniques for defining methods will help in this optimization, either by allowing more thorough analysis of the method semantics, or by allowing the source --------------------------------------------------------------------------- form of the methods themselves to be moved through the network, in situations where it would be advantageous to move the method rather than the data. A related problem is that of intelligent buffer management: determining which objects to swap out when a fresh set of objects is brought into main memory from a remote component. Conventional DBMSs use a fixed set of buffer pages and a straightforward page replacement policy (usually, least recently used). However, recent work on the "hot set" model has shown that significant performance improvements can result if buffers are managed more intelligently [SACC86, CHOU85]. For a given query, an analysis of the optimal query execution plan produced by the optimizer shows the number of buffers needed and the pattern in which they should be replaced for a certain level of performance. Adapting these mechanisms to work with various query optimization techniques is an issue. Also, the consequences of object-oriented buffering, instead of page-oriented buffering, would have to be investigated. Storage Reclamation Many object-oriented programming languages eliminate unneeded objects automatically, using garbage collection. Objects are garbage-collected when no references to the object exist in other system-maintained objects. This approach has the advantage that the programmer need not worry about doing this explicitly, or ascertaining the correct conditions under which an object is no longer needed. This also guarantees that references to an object that might exist in other objects are always valid (assuming, of course, that the garbage collection mechanism is correctly implemented), since the fact that a reference exists assures that the object exists. Various algorithms, based on reference counting and mark-sweep techniques, for object-oriented systems, have been compared in [BUTL87]. Each algorithm incurs an overhead. Moreover, implementing garbage collection is sometimes thought to be unnecessary overhead, particularly in situations where performance is especially important. Thus, some object-oriented languages, such as hybrid languages and languages associated with DBMSs, support explicit deletion of objects. The tradeoffs in using these algorithms are relevant issues. The choice between garbage collection and explicit deletion is more than just an implementation issue, since there are interactions between this choice and the object model supported. The basis of this distinction is the distinction between classes that are defined extensionally or intensionally [BRET88]. In Smalltalk, a class describes the intended use of its instances by describing their structure and behavior, and is intensional. The class does not serve to denote the collection of all its instances, its extension. Garbage collection matches this intensional class semantics. On the other hand, some object-oriented database systems, like relational database systems, assume that an object can always be referenced via its type or class, as in the query "find all employees", even when more explicit interobject references to employee objects do not exist. In such cases, the class has extensional semantics. Under this assumption, the usual type of garbage collection would make no sense, since a reference to each employee object from the class object would always exist [BLOO87]. Investigation of this issue will involve determining the actual need for the various forms of class semantics. In the relational world, where there is rarely more than one relation on a given scheme ("relation type"), relation schemes may be considered extensional. However, in some cases it is necessary to consider a distinction --------------------------------------------------------------------------- between intensional and extensional definitions of relation schemes [MANO82] in defining the semantics of relational operations. In an object-oriented environment, the semantics and usefulness of extensional schemes is even less clear. There will probably be multiple explicit collections of instances of a given class, particularly in a shared environment where several users or independent applications may maintain separate, possibly disjoint, collections of instances. It is these collections over which users will iterate, not necessarily all instances of a class. Thus the need for extensional semantics in this case may need to be reevaluated. Another relevant issue is the relative ability of the approaches to provide integrity. Relational systems have great difficulty in managing dangling tuples and supporting referential integrity. The difficulty stems in no small part from the extensional semantics of relational schemas. Referential integrity comes for free in Smalltalk. One object refers directly to another object, not to a name for that object. The reference cannot be created if the other object does not exist, and the referenced object will exist as long as the reference to it is maintained. The alternative of allowing objects to be explicitly deleted makes the enforcement of referential integrity extremely difficult. Systems that do not support referential integrity can attempt to "fix" dangling references by removing them or taking some other corrective action. Such actions almost always involve finding the objects containing dangling references or recording all references to an object. Thus, from a semantic point of view, explicit deletion can be extremely dangerous. From a performance point of view, there may be no inherent advantage to fixing dangling references over garbage collection. Recovery To guarantee persistence, the objects in the applications' transient address space and in the database must be resilient to crashes. Besides system (i.e., hardware and software) crashes, resilience against media (i.e., secondary storage device) crashes, and application-initiated aborts are usually required. Conventional DBMSs provide a variety of recovery schemes, based on logging of update operations, periodic checkpointing of the entire database, and shadow page techniques [LORI77]. These techniques guarantee that transactions are executed atomically, i.e., if a crash occurs during the execution of a transaction, the system will recover to a state in which either all the updates of the transaction will be reflected (if the transaction had already been committed) or none will (if the transaction had not been committed). These DBMS recovery techniques have been generally adopted in object managers for persistent programming languages [MAIE86]. The persistent virtual memory described in [THAT86] goes even further: by logging every operation, it can recover after a crash not just to a "clean" point (which reflects the execution of committed transactions), but to the exact state at which the crash occurred. This is useful because it means that valuable work done by long, uncommitted transactions will not have to be redone. The level of persistence required may vary from object to object. Temporary objects created by a transaction need not persist beyond the execution of the transaction. Session variables (e.g., window parameters, user profile) may have to persist beyond individual transactions within a user session. Yet other variables --------------------------------------------------------------------------- (e.g., system parameters) may have to persist beyond individual sessions [KHOS87]. In addition, in some models, such as Argus [LISK83], an object becomes persistent when it is referenced from a persistent object. This means that to commit a transaction the system must follow pointers from persistent objects to find any newly-persistent objects that must be moved to stable storage. Issues involve what available recovery techniques are best suited to the various classes of application requirements, and which situations require new solutions. A particular issue to be resolved is the appropriate unit of atomicity for knowledgebased applications, analogous to the concept of a transaction for database applications. It may be that the computations performed by the applications are so expensive that it is necessary to log all of them, as in the scheme of [THAT86]. Alternatively, it may be necessary to provide application control over which objects to save and when (e.g., temporary results can be discarded). 3.2.2 Shared Distributed Object Management Section 3.1.2 noted that most expert system shells and other systems for knowledge-based application development and execution (e.g., PROLOG, OPS5, KEE) assume a single locus of control, and so provide no mechanisms for concurrent execution of multiple application programs. DBMSs (and some programming languages), on the other hand, do allow concurrent execution, and provide mechanisms for synchronizing transactions, which are the atomic units of computation. In the DOM project, mechanisms for supporting the concurrent execution of knowledge-based application programs on a network of workstations, accessing large shared knowledge/data bases are an important area of investigation. Issues to be addressed include the following. What are the atomic units of computation that must be synchronized, and what level of synchronization is required? What concurrency control mechanisms will provide the required level of synchronization? Because shared objects may have been fetched into the transient address spaces of the application programs, how should updates be propagated between the database and the applications? Because objects are shared, dependencies may be established between concurrent application programs; what distributed recovery mechanisms are needed to guarantee resiliency against site and communication failures? Concurrency Control In conventional DBMSs, the atomic units of computation are transactions. A transaction may be viewed as a "temporal module", in contrast with an object, which is a "spatial module" [WEGN87a]. The system may interleave the execution of several transactions (to improve resource utilization and throughput), but it guarantees that the interleaved execution is serializable, i.e., equivalent to a serial (non-interleaved) execution of the transactions [ESWA76]. Various mechanisms, based on locking and timestamping, have been devised to synchronize accesses to shared data in order to guarantee this property [BERN81]. For the range of applications of interest to us, these mechanisms are too restrictive for two reasons. First, many of these applications deal with long-lived activities (e.g., design, software development and maintenance, problem solving) and large, complex objects. A long transaction will either lock out a large part of the database for a long period (the pessimistic approach), or will defer setting locks but will run a high risk of aborting when it tries to commit (the optimistic approach). In such --------------------------------------------------------------------------- applications, the amount of work that must be undone on such an abort may be unacceptable. Second, the conventional model assumes that concurrent transactions necessarily conflict and hence must be precluded from concurrently accessing shared data. However, objects in an object-oriented system may span the continuum between objects that correspond to values of variables in traditional programming languages and the large, complex objects mentioned already. Contention is unlikely on objects that correspond to program variables. Imposing pessimistic concurrency control on objects of this type is an unnecessary overhead. Moreover, for knowledge-based applications, a different paradigm is appropriate, namely that the concurrent programs are cooperating to perform some global task (design, planning, scheduling, problem solving, etc.). In this case, it may be desirable for some programs to "see" the partial results of computations performed by others. Various mechanisms have been proposed to support long transactions and cooperation. These include the following: multilevel atomicity (in which the set of transactions is recursively partitioned into equivalence classes; transactions within the same equivalence class are synchronized less strictly than transactions from different equivalence classes); checkin/checkout of objects into/from the shared knowledge/data base (objects are checked out in a few specified modes -- permitting or precluding concurrent checkout by any other program); "blackboard" mechanisms for posting messages and partial results; and support for the various kinds of notification rules and locks discussed in Section 3.1.2. More sophisticated mechanisms include preanalysis to determine how best to schedule potentially conflicting activities; generalizations of optimistic concurrency control that permit the concurrent creation of multiple versions of an object, followed by the invocation of an arbitration procedure to resolve inconsistencies among these versions; and the packaging of special synchronization methods with each object. Most advanced systems and research prototypes support a fixed subset of these mechanisms. Which of these mechanisms (or which additional mechanisms) can be used to provide the flexibility and extensibility required for our applications is an open issue. This issue also impacts the development of the DCOP, since it must capture the information necessary for specifying synchronization requirements. Still another area of investigation is how interaction between DOMs and other "active" components, such as active DBMSs being investigated in some projects [DAYA88], could be used to support efficient cooperation. For instance, an active DBMS can easily implement notify locks, tickle locks, and timed locks. It can implement a blackboard mechanism for posting messages and partial results, and can alert specified cooperating components that the blackboard has been updated (or even propagate the updates as desired). It can also easily implement various version control policies and the invocation of arbitration procedures. Update Propagation There are several reasons for propagating updates between components: a unit of computation on an application's workstation may have reached its commit point and want to store its updates on the persistent storage provided by a database system; an application program may decide to share some partial results with cooperating applications; or, an application workstation's extract of the database may need to be refreshed to reflect changes made to shared objects by "input" transactions that directly update the shared database, e.g., with the latest design change (in order to support "cache consistency"). --------------------------------------------------------------------------- The rules for specifying when updates should be propagated can be included in the synchronization rules for cooperation among the components, and can be implemented by the concurrency control mechanisms discussed above. How to actually install the updates is an interesting research problem. If updates are always installed as new versions, then mechanisms a needed to efficiently implement versions. Instead of creating a complete new version of a large, complex object, it may be more efficient to keep only the incremental differences between the previous version and the new one. The tradeoff is in the time for reconstructing the new version when accessed versus the time for installing the new version at update. Some techniques for incremental versioning of objects are described in [CARE86b, LUM84]. Some techniques for propagating changes in a database to extracts (or snapshots) in application workstations are described in [LIND86, DAYA84]. Additional research is needed to integrate these techniques and to understand the tradeoffs between them. Class Consistency This issue arises from the interaction of support for object migration in a distributed system and the potential for independent redefinition or modification of class definitions. Object migration is desirable in distributed systems in order to provide for load balancing, and to bring objects together in a single location to minimize the cost of interaction between them. This latter purpose gives rise to the need to distinguish between passing object names (or pointers) or actually moving objects. If objects do not migrate, and creation of an object requires the existence of a corresponding class object at the same node, then objects are guaranteed to be consistent with their classes. On the other hand, if object migration is allowed, the object may migrate to a node with an incompatible or missing class object. This situation can arise, for example, in a federation of conventional, single-user Smalltalk systems. Since each users is typically free to alter the structure of existing classes or the class hierarchy at a node, inconsistencies can be expected to arise between nodes. How to define and support class consistency is thus an issue. One approach to dealing with this is to work with a system-wide class hierarchy so that there is only one definition of each class in effect at any one time. This requires paying attention to the design of the method lookup system, which is critical to performance (e.g., caching class objects at nodes). However, this may not be adequate if users are to be allowed to modify and augment the class hierarchy in the usual way. It may be necessary to provide a version facility for class objects, and keep track of which instances correspond to which versions. A related issue is the definition of how mixtures of persistent and transient data are handled. This relates to the question of how transparent persistence is, and also relates to whether garbage collection or explicit deletion is supported. Distributed Recovery Conventional distributed DBMSs use distributed transaction commit protocols to guarantee that, even if some sites and communication links fail, each transaction will be atomically committed at all sites where it read or wrote data, or will be aborted at all these sites. These protocols, therefore, guarantee serializability of distributed transactions in the face of failures. --------------------------------------------------------------------------- In a cooperative work environment, however, the problem of recovery is more complex. As discussed above, "transactions" are typically long, and weaker criteria than serializability may be used. Consequently, dependencies may be set up between application programs running at different sites. When one program crashes, dependent programs (those that read partial results from it), may have to be rolled back, or some human or automated agent may have to be notified to run "compensating" transactions to achieve some desired level of consistency. Relying on compensation is appropriate when temporary inconsistencies can be tolerated and it is more important not to lose work performed than to guarantee strict consistency at all costs. This technique of recording dependency information and compensation is a relatively unexplored area in cooperative work; however, it has been studied in the context of highly available distributed database systems that must continue to operate after a network partition [SARI86]. The applicability of those techniques to the problem of distributed recovery in the DOM architecture is a potential area of investigation. We expect that the compensating transactions can be implemented in the same way as arbitration procedures (indeed, they are manifestations of the same primitive concept -- procedures for resolving potential inconsistencies caused by unsynchronized updates). This will involve investigating interactions between the DOM components and the individual component object managers to provide the required level of consistency in the face of failures. In the general case, object methods are written in computationally-complete programming languages, and thus may fail in many ways. This means that issues of "error recovery" arise in their full programming language richness. In such cases, rather than simply rolling back to the end of the last successful transaction, the system must be prepared to return useful error information to methods, and the methods must be able to do useful things in response. How to support such error recovery is also a significant issue. --------------------------------------------------------------------------- 3.3 System Architecture The distributed object systems we are considering may initially consist of arbitrary combinations of existing hardware and software components, such as programming languages, database systems, knowledge-based systems, operating systems, and applications. It is the goal of distributed object management (DOM) technology to support tighter coupling between these classes of components, so as to create the possibility of new combinations of "operating system", "application" (including knowledge-based applications), and "DBMS" facilities to support overall organizational requirements. Architectural issues are important in distributed object management technology because they affect what components are required in a given system, and how these components are intended to interact. These requirements in turn affect the technology required for the components. In this section, we provide an overview of the sorts of architectural issues involved in distributed object management. The issues to be addressed can best be described in the context of a generic, strawman architecture of a system providing DOM functions. Following the description of this architecture, the various issues will be discussed. 3.3.1 Strawman Architecture Initially, we can think of the problem of providing DOM functions as involving the development of a specific component within a distributed system architecture called a "Distributed Object Manager" (DOM) (subsequent sections will generalize this assumption). The DOM is an object-oriented component that has been specificallydeveloped to deal with the application of integrating knowledge based (and other) applications and heterogeneous persistent data/knowledge sources (databases, file systems). In general, the DOM can be characterized as providing something of the functionality of the Multibase Global Data Manager (GDM) and Local Data Interface components described in Section 1, but considerably generalized, and applying to processing as well as data. The DOM will provide distributed object management for all objects in a network of computing systems. It permits a request or transaction to be expressed involving objects that reside in the system without knowledge of the location, format, etc. of the objects or methods involved being known by the requestor. DOM will locate the required information, access it, and, if necessary, move it to a site so that "local object management" can be performed to satisfy the request, as efficiently as possible. Unlike a DDBMS, the DOM will permit arbitrary operations to be executed over arbitrary objects on any machine in the system. DOM will use knowledge of of the object requirements and location to determine an efficient optimal plan to achieve the desired result (e.g., where to execute the methods and what results to transmit). Figure 3.1 shows a system architecture based on this concept. The architecture can include an arbitrary number of nodes each running one or more systems. There are two types of system shown in the figure: DBMS/Object Management Systems and Applications. DBMS/Object Management Systems represent components such as DBMSs (possibly object-oriented) and similar components, such as file systems, that provide persistent, shared object management facilities to the network. Applications require services of Data/Object Managers to share and access objects that persist outside their run time systems and local object stores, and also serve as object methods for some of the objects. The long term objective is to support interoperability for any type of application. Initially we are considering --------------------------------------------------------------------------- Knowledge-Based Systems (KBS) applications requiring access to shared, persistent information. The application is considered as having two parts, the application code and the application run time system. These same components, suitably reinterpreted, apply to non-knowledge-based applications as well. Application code for a KBS consists of objects/frames/rules that implement the KBS. The application run time system is the inference engine that executes the application code together with any local object manager and its local object memory (object base). Every system in the network has (or is assigned) a DOM which provides means for interacting with other systems in the network. There may be many applications on that system interacting via a single DOM. The DOM is shown as having three components. The general functions assumed for these components are as follows: The Adapter or Local System Interface provides mappings between the target system and the DOM, similar to the Local Data Interface in MULTIBASE. The Adapter accepts messages (e.g., data requests) in the DCOP and translates them into an application-specific protocol for the local system, and vice versa. The Adapter performs a similar function for objects flowing between the local system and the DOM. The Global Object Manager (GOM) provides global or system-wide object management capabilities for the local system over objects in the entire distributed system, similar to the Global Data Manager in MULTIBASE. Unlike a GDM, the GOM itself is distributed in that each system in the network has a GOM. A GOM attempts to do object management by interaction with GOMs in the DOMs associated with other systems. More specifically, the GOM receives tasks or requests in the form of messages in the DOM Common Object Protocol (DCOP) from either the local system (through the adapter) or from other DOMs. If global optimization is possible, the GOM plans an efficient task execution by decomposing the task into subtasks that can be executed by different systems in the network, negotiates or assigns subtasks to systems, monitors the execution, performs any additional functions that may be necessary, and returns results to the requesting systems. The GOM uses the DOM run time system and DOM internal object base, which contains global information (such as directory information) about objects in the network (this object base may itself be distributed among the DOMs). If an individual GOM cannot determine the necessary information itself to decide how to deal with a given request, the GOM will interact with other DOMs to determine how the request can be executed. The DOM Run Time System/Object Manager provides dedicated local object management capabilities required for both the Adapter and the GOM. Other components at lower levels of the architecture are required that are not explicitly shown. These include such things as components that support communications among the nodes, and local operating systems (and possibly a distributed kernel specifically to support DOM requirements). --------------------------------------------------------------------------- Application Code Application Run Time System incl. Object Manager Appl. Object Base Application Application-specific protocol Application Node Adapter/Local System Interface DOM Internal Object Base Global Object Manager Distributed Object Manager DOM Run Time System/ Object Manager Application Code Application Run Time System incl. Object Manager Appl. Object Base Application Application-specific protocol Application Node Adapter/Local System Interface DOM Internal Object Base Global Object Manager Distributed Object Manager DOM Run Time System/ Object Manager Adapter/Local System Interface DOM Internal Object Base Global Object Manager Distributed Object Manager DOM Run Time System/ Object Manager Data/ Object Base DBMS/Object Management System DBMS/OMS-specific protocol DBMS/OMS Node Adapter/Local System Interface DOM Internal Object Base Global Object Manager Distributed Object Manager DOM Run Time System/ Object Manager Data/ Object Base DBMS/Object Management System DBMS/OMS-specific protocol DBMS/OMS Node DOM Common Object Protocol ? ? ? ? ? ? ? ? ? ? ? ? Figure 3.1 A DOM-Based System Configuration 3.3.2 Location of Method Execution When considering the use of DOM technology to integrate a collection of existing systems, there may not be much choice in where the procedures associated with various objects execute -- they must execute in the components in which they are defined. For example, database functions must be executed in a DBMS, application functions must be executed in an application, and so on. However, with the expansion of object-oriented technology in various component classes, such as in object-oriented database systems and object-oriented programming languages, and the integration of such systems using DOM technology, systems may begin to allow choices of where object methods may be executed. --------------------------------------------------------------------------- For example, if an application, a backend DBMS providing persistent storage to it, and the associated DOMs are all object-oriented, a given method might, in principle, be executed on any one of these components. In this case, to execute a method over a set of objects, we could either fetch the objects from the knowledge/data base into the application node, and execute the method there, we could move the method code down to the backend DBMS (it might already be stored there), and execute it there, or we could move both method and data to one of the DOMs and execute the method there. Alternatively, some of the methods might be executable only on certain specific processors. For example, there might be a specialized processor for cartographic (map) data. A tax assessment application may need to invoke methods that are executed by this processor. Similarly, in a heterogeneous environment, it would be desirable for an application (written in KEE, say), running on one component, to invoke a method (written in OPS5 or PROLOG, say) that can only execute on another component. Ideally, the DOM architecture must be flexible enough to support these requests, and the system must include a powerful enough global optimizer to determine the best execution plan for such requests. A related architectural question is where the global optimizer itself can execute. One of the issues involved is being able to identify the class of methods that can best be performed within various components. For example, one of the classic arguments made by the database community is that operations involving iterations over sets of data should be identified, and moved into the DBMS for processing, since DBMSs contain optimization facilities and access methods specifically designed for this class of processing. However, this does not necessarily mean that just because one can identify a particular method with a given database object, that this method should be executed in the DBMS. For example, generalizing the above argument about iteration over sets to iteration over arrays, one might conclude that matrix inversions should be performed on the DBMS. It might save data movement between the application and the DBMS to perform this processing in the DBMS (i.e., in a DBMS main memory workspace). But the part of the DBMS that handles method execution (as opposed to strictly data access and storage) would soon become a process bottleneck, and many DBMSs are process-bound already. Moreover, the DBMS machine might be less suited to this type of processing than an application running on a supercomputer. This illustrates one facet of the additional complexity of the optimization problem in object-oriented systems, since one may have the choice of either sending the method to the data, or vice-versa. The conclusion on an appropriate division of labor reached in the PROBE extensible DBMS was to have the database system carry out suitably generalized basic database operations (e.g., joins, selections) on sets of generic objects, while each object class (specifically, methods within the object class) is responsible only for working on individual objects of more specialized types. This division of labor corresponds well with a desirable division of labor among implementers as well -- no implementer will be concerned with both database and application issues. For example, consider a proximity query: "find all objects within a given distance of a given object". Instead of requiring an object class capable of processing this entire query, a system designed for this purpose, such as PROBE, only requires the object class to provide a function that indicates whether a pair of objects satisfy the selection condition [OREN88]. The decision to have the database system handle generic types and leave the more specialized types to the object classes raises issues of where the dividing line should be. --------------------------------------------------------------------------- Such a division of labor creates the issue of "foreign functions" [FISH88]. If object methods are written in an arbitrary language (one that the DBMS does not understand), these are "foreign", because the DBMS cannot optimize them along with the rest of any query in which they may be embedded. Dealing with this issue generally involves attempting to optimize the usage of the function, even if the implementation of the function cannot be optimized. This raises issues of developing rule-based (and hence extensible) query optimizers, and methods for expressing relevant function semantics in rules. Examples of work related to such optimizers is described in [FREY87, GRAE87]. Many object-oriented systems, such as Smalltalk, already maintain a clean separation (with a well-defined interface) between "object memory", which deals with objects as static entities, and "method interpreter", which deals with the execution of methods. This parallels the classic separation of function in a conventional Von Neumann processor. A similar division can be found in some object-oriented database systems. For example, in the ENCORE system, one component is an Object Server providing generic object storage functions, while a higher-level component implements the more complex aspects of an objectoriented data model (including methods). This suggests a general way to partition an object-oriented component: (a) the storage subsystem that just deals with object access; (b) the upper layer that deals with method execution. This upper layer is in many respects similar to an object-oriented programming language run-time system, and could perhaps be made interchangeable with one or more such run-time systems. One of the goals that might be achieved by such a separation is modularity of performance. For example, one of the requirements of some types of applications, such as real time applications or on-line transaction processing, is predictability of performance. For such applications, it is desirable to separate processing whose performance can be predicted from processing whose performance is unpredictable. This has been used as an argument against supporting garbagecollection in the database, since this would mean that the DBMS might stop to garbage-collect at possibly-inappropriate and unpredictable points. This suggests an architecture, such as that used in the ENCORE system, that separates a component that supports a model requiring garbage collection from a component providing more basic, but more predictable, database functions. A similar suggestion has been made with respect to join processing in a relational DBMS, the idea being to separate the join processing, which is sometimes hard to predict, in one component, and provide selection and projection, for example, in another component. Similar considerations might apply to rule processors supporting condition monitoring in "active" DBMSs. Such considerations suggest that the most effective interaction among components will take place if today's monolithic systems, such as DBMSs, are broken up into separate cooperating components, with well-defined interfaces between them. This is, for example, the basis of work on DBMS generators and toolkits, such as EXODUS [CARE86a]. Such component architectures could allow tighter coupling between internal components in these systems and DOM components, in order to improve efficiency and provide new combinations of functions. 3.3.3 Internal Components of DOM --------------------------------------------------------------------------- This class of issues concerns those relating to the internal components of the DOM illustrated in Figure 3.1 and, by extension, the interfaces between those components, and other components of the distributed system. The components and interfaces shown in Figure 3.1 are illustrative only, and may be modified during the course of our work. An example of such an issue is whether the DOMs have any local stable storage (independently of any attached DBMSs). If the DOMs do have local stable storage, then a DOM attached to a non-DBMS component may have to perform many of the functions of a full-fledged DBMS. In that case, the interactions between these DOMs and DOMs interfacing DBMSs for intelligent staging and support of cooperative work may be quite different from what they would be otherwise. In fact, we imagine that systems of the future may have completely symmetric federated architectures in which the DOMs at some components become "application servers" that execute some applications, manage their local knowledge/data stores, and negotiate among themselves for access to remote knowledge/data and for remote execution of methods. Other issues involve the internal DOM components that may be required to support knowledge-based processing in support of intelligent cooperation, and the interfaces that may exist between these DOM components and other intelligent components that may exist in the system. Finally, the DOMs shown in Figure 3.1 all have the same internal components. However, this may be neither appropriate nor necessary, depending on the functionality provided (and needed) by the local system with which a given DOM is associated. Providing DOMs tailored to individual system requirements would be greatly assisted by the use of DBMS generator/toolkit technology [CARE86a]. 3.3.4 Requirements of System Operations This class of issues concerns those relating to how the potentially large and complex DOM-based systems will be operated and managed, and associated technology required to support this. For example, at the 1988 SIGMOD Conference, a panelist (Jim Gray from Tandem) made a number of interesting points concerning scale issues associated with very large database systems. He noted, for example, that to load a 1012 byte SQL database at typical loading rates would take 60 days. Similarly, he noted the incredible difficulties in starting or recovering a system with 1000 terminals. Yet, many normal operating procedures in large installations involving periodic requirements to stop the system (installing a new operating system release), or to reload large databases (reorganization). His conclusion was that we can easily imagine building systems today that would be impossible to manage, and that some technical developments are going to have to be made to allow realistic construction of such systems. Examples include improving the use of parallelism, duplexing machines, and software provisions for making online database changes (adding columns, building indexes, reorganizing storage structures), on which a surprisingly little amount of work has been done. Another relevant issue in the context of developing specific systems of this type is how to control complexity. For example, heterogeneity can be addressed at many different levels in a system architecture, and it may be that the only feasible way to construct operational systems will be to restrict the levels at which heterogeneity can --------------------------------------------------------------------------- occur. This may involve the use of standards of various sorts. Issues exist as to the appropriate levels, and the appropriate standards. Examples of different levels include the "virtual machine" concept, used in Smalltalk, and the use of operating system standards such as CAIS [OBER88]. Another issue in developing operational systems in the short term is the extent to which conventional database management systems, and database technology, can be used in an unmodified form to support the more general data types of objectoriented systems. The former is particularly important in integrating existing systems into more general object-oriented frameworks. The current general feeling is that if a conventional relational system was used, it should be used to support conventional data only, with more general data types implemented in specialized components, and the two linked at a higher level. A similar approach would be to use an OODBMS as a front-end so that users could access both relational DBMSs and instances of unconventional data types, possibly on files. The main difficulty is performance of relational systems on general objects. At OOPSLA87, someone from DEC noted that they had tried to use relational systems to model objects in a CAD application (using system-generated object identifiers to relate the various parts of the objects stored in relational tuples) and that performance was unacceptable. This merely confirms the predictions of the research community. On the other hand, much of conventional database technology might well be applicable to object systems, possibly with enhancements, if used at suitable levels in the architecture. For example, it has been suggested that a relational storage manager (as opposed to a relational DBMS) might well work as a component in an object-oriented system, the problem being with the data model, not so much with the storage-level constructs. This reinforces the concept, described above, that existing monolithic systems would function better in the new, objectoriented environments, if broken into subcomponents which could be directly accessed for new purposes. 3.4 System Security Distributed object management technology creates the potential for integrating large collections of heterogeneous components, possibly owned or managed by different authorities, and consisting of data or processes requiring varying levels of security. This gives rise to many issues related to the ability of the overall system to provide this security. These issues include the protection of the integrity of the system itself, as well as the security of the various components. If adequate security cannot be provided, the utility of the technology may be seriously affected. Examples of such systems are those in which databases belonging to different organizations are being connected both to exchange data, and to be viewed as part of a larger integrated database. Examples in the government include the Computer-Aided Logistics Support (CALS) initiative, and the Very High Speed Integrated Circuit (VHSIC) Engineering Information System (EIS) program [LINN86] described in Section 2. For example, in the CALS program [CALS86], the government is attempting to allow defense contractors to exchange information (both with the government and each other) in digital form in support of government logistics activities. Examples of this information are specifications, drawings, and manuals (including both text and graphics). The intent is to not require the various participants to use standard hardware or software, but rather to interchange information in standard formats. The systems developed under these programs --------------------------------------------------------------------------- may be loosely-coupled "federations". Moreover, the participation of individual contractors in such federations may be for only short periods of time (e.g., the duration of a contract), and thus the overhead in coupling the component systems cannot be high. Obviously, the various participants will require that a certain amount of security be provided before they allow their systems to be interconnected in this way. Over the years, there has been a considerable research effort directed toward developing computer security technology (several crucial areas of this technology are surveyed in [CHEH81, LAND81]), and specialized conferences have arisen in the area [IEEE87]. Originally, most of this technology was directed as developing secure operating systems. However, recently there have been substantial efforts directed at integrating both distributed systems and database systems with the concepts of Trusted Computing Bases (TCBs) arising from work on secure operating systems for military security requirements. Descriptions of the research issues and examples of work in this area can be found in [NCSC86,NRC83]. In spite of this effort, computer security remains an elusive goal. While operating systems that provide specified levels of security have been built for specialized military applications, they are not in general purpose use, and impose significant performance penalties. Current DBMSs offer relatively simple facilities for security and integrity, and security typically not a major consideration in their design and implementation. Attempts to build secure DBMSs to satisfy military requirements have had extremely limited success. Moreover, the increased generality, flexibility, and interconnectivity required by applications will increasingly complicate the problem of maintaining security. Security-related issues include issues related to modeling security, implementing secure systems, and verifying the security of such systems. Modeling Security One of the goals of an object model is to allow the semantics of that part of the "real world" being modeled by the system to be accurately represented. It will be important that the object model allow security-related aspects of these semantics to be represented as well. However, there has been relatively little interaction between work in developing object models and that of developing security models, in spite of the fact that enterprise semantics surely include the rules under which information flows (or is restricted from flowing) between objects in the model, and under which various operations are performed or prevented from being performed. For example, neither the DoD Trusted Computer System Evaluation Criteria (TCSEC) [DODCSC83] nor the Bell-LaPadula model (widely used as a model of military security policy) include rules for determining the security level of a newlycreated object [BOEB86], yet each operation of the relational algebra (effectively the "object model" of a relational database system) is defined as creating a new relation from old ones. DBMS architectures such as the ANSI/SPARC 3-schema architecture [TSIC77] explicitly identified security rules as one of the elements of the "conceptual schema". Synergy between object and security model development will be particularly important as object-oriented approaches carry database style modeling into other parts of the system, such as applications, since this accentuates the need to integrate design across the system. Such integrated design would help with issues such as --------------------------------------------------------------------------- maintaining consistent security labels across different component levels (e.g., operating system and DBMS) and among heterogeneous systems. Such integrated design requires "systems models" that consider the semantics (and thus the security) of the whole system, as opposed to models related to individual components. Integrated design also requires design methodologies that cross component boundaries. Object-oriented systems illustrate a growing emphasis on considering issues across entire system architectures, as opposed to just individual components of such architectures, to get better integration of system components. This is consistent with the need to assess the security of the entire system, not just of individual components. Considering security in object models requires a certain amount of rethinking. For example, if the object model uses the "active object" perspective, it may be inaccurate to think in terms of "protection of objects" since the objects can, at least in principle, actively provide for their own defense. For example, an object can refuse to allow certain operations, hide information, provide disinformation (lie), or move into a context where it cannot be reached. An object can even defend itself by directly or indirectly attacking an "aggressive" object. All these possibilities potentially give protection mechanisms a new meaning, and require addressing security-related issues in the development of both object models and object management systems. Differences also exist at more detailed levels. For example, the classical data security notions of "read" and "write" access are slightly different in an object model. Having the identity of an object is not the same as reading the object. Also, having permission to access an object does not imply the same permission on all its subobjects. Implementing Security Such advances as object-oriented DBMSs create difficult technical problems in implementing security. In such systems, much of what used to be application code may be included in the DBMS in the form of object "method" definitions, and protecting other parts of the system from possible errors in this code may be more difficult. This will require development of underlying operating system technology as well, and is related to current work on secure system architectures. Also, the definition of security policy must include references to the many new operations defined by these methods, rather than a few simple operations such as read and write. Thus, it will be more difficult both to define security policies, and to verify implementations. On the other hand, the methods can be written to include the definition of derived security labels for the results of applying the methods. Typical mandatory security and integrity policies would, if strictly interpreted, rule out basic DBMS capabilities, or various techniques commonly used in DBMSs to provide these capabilities. For example, a simple query involving data classified at both high and low levels potentially involves the sending of messages by a process acting on behalf of a high user to a low process. This creates a channel that could be exploited by Trojan horses. It has also been noted in the research literature that concurrency control mechanisms involve such channels [HINK75]. Such channels, while of concern from a security point of view, are basic to the functioning of a typical DBMS. The tradeoffs between functionality of components and system security are therefore issues. --------------------------------------------------------------------------- A number of research issues arise out of interconnecting heterogeneous systems. One such issue is how to evaluate the overall security of the system when components of different assurance levels or reliability are interconnected. Another is how to enforce a global security policy on systems that may not have been designed to support this capability (in this case, the definition is a problem as well). Technically, this issue resembles that of providing concurrency control for heterogeneous systems, in the sense that: ? individual systems may not provide the proper facilities to implement global protocols over them ? while the definition of correctness or "policy" (e.g., serializability in the case of concurrency control, or "security" in this case) may be precise, the level of correctness actually obtained may not be easy to define, and may be dependent on which systems are actually involved in a given transaction. ? formal definitions and analysis are needed to provide assurance that the mechanisms provided actually implement the desired policy. It may be that, at least at some level of abstraction, work on one of the problems may possibly contribute to a solution of the other. It has been frequently observed that systems that provide users access only to high-level, specialized interfaces can be made more secure that those that allow more ad-hoc interaction between user and system (with application programming being a particularly difficult case). However, this presents a difficult tradeoff if the system is also to be highly flexible and responsive to changing user requirements. Work on higher-level interfaces to database systems, such as the tailorable interfaces provided by object-oriented DBMSs, may provide the means for the modular construction of "closed systems" that are also sufficiently functional and relatively flexible. Verifying Security Specification and verification techniques provide an area for synergy between object management and security technology. Formal specification and verification plays an important role in providing assurance that security properties have been correctly specified and implemented. However, security is not the only system property where a high degree of assurance may be required. For example, such assurance is also of importance where real-time and/or unattended computer operations are involved, or where transaction safety must be guaranteed without considerable concurrency control overhead. Contributing to the development of these techniques may be work in the area of high level requirements definition languages, declarative programming, and executable specifications as applied to database and other object management systems. Formal specifications involve the use of such requirements definition languages. These specifications can also be used for rapid prototyping and simulation if the specification language can itself be executed. The declarative style of such languages is very similar to that of some of the high-level data description languages, query languages, and integrity constraint definition languages used in database systems. Such languages are desirable not only because they are easier --------------------------------------------------------------------------- to use and more powerful than lower-level languages, but also because they provide more scope for optimization. This area will be increasingly relevant as highlevel languages used in connection with database systems become computationally more complete, and thus more capable of specifying the complete semantics of database transactions (such as the TAXIS language [MYLO80]) or built-in operations on database objects, as in the methods defined in object-oriented database systems. 3.5 Applications and Methodologies This class of issues involves those related to the interaction of applications of DOM technology and technical requirements. It also includes those relating to methodologies that must be developed in designing and using DOM-based systems. Applications The generalized concurrent object-oriented systems that can be constructed with DOM trechnology should be useful in a wide variety of applications, such as knowledge based systems, database systems, system descriptions, system simulation, office systems, factory management, process control, and other real-time systems and animation. They should also be good for doing distributed AI [TSIC88]. This range of potential applications creates issues with regard to the "technology agenda" of research work on object-oriented technology. An example of this can be seen in the development of object-oriented database technology. In pursuing work on implementation of object-oriented systems, the goal of OODBMS technology ought to be the application of this technology in general DBMS applications (those for which conventional DBMSs are used now), as well as in specialized applications such as engineering databases [MANO87]. This is because: (a) the technical problems are more interesting when the general case is addressed; (b) an important reason why people want to apply DBMS technology in these specialized applications is because they want to integrate conventional database applications (order/inventory; contracts; general MIS) with the new ones (i.e., they do not just want to invent a new source of incompatible database systems which they will later have to integrate at great expense in order to manage their organizations). However, a general consensus at OOPSLA87 database sessions (with a few exceptions, including the author of this document) was that OODBMSs should worry about competing with relational systems later, and push non-set-oriented facilities immediately (the intent being that issues such as optimization of set-oriented queries are not to be considered immediately in OODBMS research). This is a reasonable conclusion if the intended applications for OODBMSs are only design applications, as is the assumption of some OODBMS vendors. However, this is less reasonable if OODBMSs are to be immediately applied in a wider range of applications, or are to be applied to design applications in a wider context. For example, not considering optimization of set-oriented queries might create problems for distributed OODBMSs, due to the large communications overheads for single-object accesses over the network. This is one indication of the importance of issues relating to intended applications in determining characteristics of DOM research. --------------------------------------------------------------------------- To give an example of this relationship at a more detailed level, potential users of OODBMSs have noted that, in general, OODBMS applications require objects of widely-varying sizes, and that implementation support for these is required. However, it is possible to assume only a particular class of applications, and entirely ignore some facility that would be needed in a more general class. This was also illustrated at OOPSLA87, where an OODBMS vendor had described their product's caching facilities, and indicated that they supported up to 2MB caches. A person from NASA said he wanted to process 280MB LANDSAT images, and that these 2MB caches were clearly not going to be very helpful in that application. For this application, the system would have to support object streaming of some kind, since the whole object could not be in memory at once. Another example of an issue related to applications is how "federated" the connected systems are assumed to be. As in the subject of heterogeneous distributed DBMSs, the range of issues is rather different if one assumes that all connected systems have a minimal common interface, have nothing at all in common, are accessed via some "supermodel" (as in Multibase using the Daplex model), or all implement the same query language (SQL, in many "heterogeneous" DDBMSs described in the trade press). A more general approach is to identify various classes of systems that can be connected, with different assumptions about each class. An example is the VHSIC EIS, which distinguishes between "attached" and "integrated" applications (the former only require file transfer facilities between components, while the latter require tighter integration, moving toward interoperability. Methodologies Finally, in order to take maximum advantage of the facilities provided by objectoriented approaches, such as object reusability, polymorphism, class inheritance, parameterized types, etc., changes in programming and design methodologies will be required. Applications must be organized so as to be consistent with these possibilites. Techniques have been developed for decomposing problems into relatively independent components, but generally understood methodologies for viewing applications in terms of objects are still lacking [TSIC88]. Methodologies are also required for producing integrated designs involving multiple component types, since such designs will be crucial in implementing the types of systems that DOM technology will make possible. Such methodologies, and accompanying software tools that encourage use of object-oriented design, will come about only through experience with object-oriented approaches. Issues in defining system administration and development tools such as method finders, information retrieval for methods, reusable code technology, etc. are also relevant, since these the existence of such tools may determine the usability of general object technology in practice. In fact, the whole area of software development methodology and CASE tools becomes relevant, due to the computational power of the object model and the various components based on it. --------------------------------------------------------------------------- 4. Concluding Remarks This Technical Memorandum has described the general problem area that the Distributed Object Management (DOM) project is attempting to address, surveyed relevant technology areas, and identified technical issues related to the development of distributed object management technology. The general problem area that we have identified is an important one. Moreover, the requirements we have identified for interconnectivity and interoperability are not unrealistic, as is demonstrated by some of the applications and research projects cited in Sections 1 and 2. The breadth of relevant technology described in Section 2 is impressive, but not unexpected, since distributed object management technology lies within the intersection of programming language, operating system, database, and artificial intelligence technologies. The need for work within this intersection has been generally recognized within interested segments of the relevant research communities. This is illustrated by current work in such areas as persistent programming languages, object-oriented database systems, knowledge-based system/database interfaces, and distributed operating systems described in Section 2. There has also been considerable agreement that the research issues identified in Section 3 require investigation, even when agreement has not been reached on specific details and approaches. Our intent in preparing this report was to lay the groundwork for further research activities. These activities are proceeding along two tracks. The first track is the development of a simple breadboard DOM component for interfacing an expert system with a DBMS. The intent of this activity is to give the project implementation experience with various aspects of DOM-like components. The second track is the pursuit of fundamental research into some of the issues identified in Section 3. Identifying which issues to attack, given limited project resources, will be the immediate focus of activity on this track. This will require, among other things, the identification of areas where we can obtain maximum leverage, given the experience and interests of the project staff, and related ongoing research elsewhere. Acknowledgements I would like to thank Michael Brodie and Pam Talbourdet for their help during the preparation of this report. --------------------------------------------------------------------------- 5. References [AGHA87] Gul Agha and Carl Hewitt, "Actors: A Conceptual Foundation for Concurrent Object-Oriented Programming", in [SHRI87] [ALBA86] A. Albano, et. al., "A Strongly Typed, Interactive Object-Oriented Database Programming Language", in [DITT86]. [ANDR87a] Timothy Andrews and Craig Harris, "Combining Language and Database Advances in an Object-Oriented Development Environment", in [MEYR87]. [ANDR87b] Andrews, G.R., Schlichting, R.D., Hayes, R., and Purdin, T.D.M., "The Design of the Saguaro Distributed Operating System", IEEE Trans. Softw. Eng. SE-13, 1 (Jan. 1987), 104-118. [ASTR76] Astrahan, M. M., et. al., "System R: Relational Approach to Database Management", ACM Trans. Database Systems, 1, 1976. [ATKI87] Malcolm P. Atkinson and O. Peter Buneman, "Types and Persistence in Database Programming Languages", ACM Computing Surveys, 19(2), June 1987. [BACK78] John Backus, "Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs", ACM Turing Lecture, Comm. ACM, 21(8), August 1978. [BAIL87] Roger Bailey, "An Introduction to Hope", in S. Eisenbach, ed., Functional Programming: Languages, Tools, and Architectures, Ellis Horwood, Chichester, 1987. [BATO84] D.S. Batory and A.P. Buchmann, "Molecular Objects, Abstract Data Types, and Data Models: a Framework", Proc. Tenth Intl. Conf. on Very Large Databases, 1984. [BATO85] D.S. Batory, "Modeling the Storage Architectures of Commercial Database Systems", ACM Trans. Database Systems, 10(4), December 1985. [BATO86] D.S. Batory, et. al., "GENESIS: A Reconfigurable Database Management System," Technical Report TR-86-07, University of Texas, Austin, 1986. [BENN87] John K. Bennett, "The Design and Implementation of Distributed Smalltalk", in [MEYR87]. [BERN81] P. A. Bernstein and N. Goodman, "Concurrency Control in Distributed Database Systems", ACM Computing Surveys, June 1981. [BISI87] R. Bisiani, et. al., "Heterogeneous Parallel Processing, The Agora Programming Environment", Technical Report CMU-CS-87-113, Carnegie-Mellon University, March 1987. [BLAS81] M. W. Blasgen, et. al., "System R: An Architectural Overview", IBM Systems Journal, 20(1), 1981. --------------------------------------------------------------------------- [BLOO86] Paul Bloom and Patrick Miller, "Intelligent Network/2", Proc. National Communications Forum, Professional Education International, 1986. [BLOO87] Toby Bloom and S. B. Zdonik, "Issues in the Design of ObjectOriented Database Programming Languages", in [MEYR87]. [BOBR86] Daniel G. Bobrow, et. al., "CommonLoops: Merging Lisp and ObjectOriented Programming", in [MEYR86]. [BOEB86] W. E. Boebert, B. B. Dillaway, and J. T. Haigh, "Mandatory Security and Database Management Systems", in [NCSC86]. [BORA86] Haran Borel, ed., Database Engineering, 9(3), September 1986, Special Issue on Operating Systems Support for Data Management. [BRET88] Robert Bretl, et. al., "The GemStone Data Management System", unpublished paper to appear in [KIM88]. [BROD86a] Michael L. Brodie and John Mylopoulos, (eds), On Knowledge Base Management Systems, Springer-Verlag, 1986. [BROD86b] Michael L. Brodie and Matthias Jarke, "On Integrating Logic Programming and Databases", in [KERS86]. [BROW86] Lee Brownston, et. al., Programming Expert Systems in OPS5, Addison-Wesley, Reading, 1986. [BUNE82] O. P. Buneman, R. E. Frankel, and R. Nikhil, "An Implementation Technique for Database Query Languages", ACM Trans. Database Systems, 7(2), June 1982. [BUTL87] M. H. Butler, "Storage Reclamation in Object Oriented Database Systems", Proc. 1987 ACM-SIGMOD Intl. Conference on Management of Data, ACM, New York, 1987. [CALS86] Office of the Assistant Secretary of Defense (Acquisition and Logistics), "Automated Logistic Systems, Part I -- Computer Aided Logistic Support (CALS)", Report to the Committees on Appropriations of the U.S. House of Representatives and the U.S. Senate, Washington, D.C., March 28, 1986. [CARE86a] M. J. Carey, et. al., "The Architecture of the EXODUS Extensible DBMS: A Preliminary Report", in [DITT86]. [CARE86b] M. J. Carey, et. al., "Object and File Management in the EXODUS Extensible Database System", Proc. Twelfth Intl. Conf. on Very Large Data Bases, August 1986. [CHAN81] A. Chan, et. al., "The Design of an Ada Compatible Local Database Manager", Technical Report CCA-81-09, Computer Corporation of America, November 1981. [CHAN82] A. Chan, et. al., "Storage and Access Structures to Support a Semantic Data Model", Proc. Eighth Intl. Conf. on Very Large Data Bases, September 1982. --------------------------------------------------------------------------- [CHAN83] A. Chan, et. al., "Overview of an Ada Compatible Distributed Database Manager", Technical Report CCA-83-01, Computer Corporation of America, January 1983. [CHEH81] M.H. Cheheyl, et.al., "Verifying Security", Computing Surveys 13, 3, Sept. 1981. [CHOU85] H.-T. Chou and D. J. DeWitt, "An Evaluation of Buffer Management Strategies for Relational Databases", Proc. Eleventh Intl. Conf. on Very Large Data Bases, 1985. [CLAR84] K. Clark and S. Gregory, "Parlog: Parallel Programming in Logic", Research Report DOC 84/4, Department of Computing, Imperial College, 1984. [COX86] Brad J. Cox, Object Oriented Programming: An Evolutionary Approach, Addison-Wesley, 1986. [DAHL66] O.J. Dahl and K. Nygaard, "SIMULA--An Algol-based Simulation Language", Comm. ACM 9, 671-678. [DARL86] J. Darlington, A.J. Field, H. Pull, "The Unification of Functional and Logic Languages", in [DEGR86]. [DAVI88] Alvah Davis and Ralph Worrest, "Experiments in Conflict Resolution for Cooperative Agents: Design", Technical Note TN 88-172.1, GTE Laboratories Incorporated, March 1988. [DAYA84a] U. Dayal, et. al., "Knowledge-Oriented Database Management", Technical Report CCA-84-02, Computer Corporation of America, 1984. [DAYA84b] U. Dayal and H. Hwang, "View Definition and Generalization for Database Integration in a Multidatabase System", IEEE Trans. Software Engineering, 10(6), 628-645, 1984. [DAYA85] U. Dayal, et. al., "PROBE: A Research Project in Knowledge-Oriented Database Systems: Preliminary Analysis", Technical Report CCA-85-03, Computer Corporation of America, July 1985. [DAYA86] U. Dayal and J.M. Smith, "PROBE: A Knowledge-Oriented Database Management System," in M.L. Brodie and J. Mylopoulos (eds.), On Knowledge Base Management Systems: Integrating Artificial Intelligence and Database Technologies, Springer-Verlag, 1986. [DAYA88] U. Dayal, et. al., "The HiPAC Project: Combining Active Databases and Timing Constraints", SIGMOD Record, 17(1), March 1988. [DBTG71] CODASYL Data Base Task Group, April 1971 Report, ACM, New York, 1971. [DCDS88] Digital Cartographic Data Standards Task Force, "The Proposed Standard for Digital Cartographic Data", The American Cartographer, 15(1), American Congress on Surveying and Mapping, January 1988. --------------------------------------------------------------------------- [DECK87] Keith S. Decker, "Distributed Problem-Solving Techniques: A Survey", IEEE Trans. Systems, Man, and Cybernetics, 17(5), Sept./Oct. 1987. [DEGR86] Doug DeGroot and Gary Lindstrom, Logic Programming: Functions, Relations, and Equations, Prentice-Hall, 1986. [DITT86] Klaus R. Dittrich and U. Dayal, eds. Proc. 1986 Intl. Workshop on ObjectOriented Database Systems, Washington, IEEE Computer Society Press, 1986. [DIXO87a] G.N. Dixon and S.K. Shrivastava, "Exploiting Type-Inheritance Facilities to Implement Recoverability in Object-Based Systems", Proceedings of the Sixth Symposium on Distributed Software and Database Systems, IEEE, March 1987, pp.17-19 [DIXO87b] G.N. Dixon, S.K. Shrivastava, and G.D. Parrington, "Managing Persistent Objects in Arjuna: A System for Reliable Distributed Computing", Proceedings of the Workshop on Persistent Object Systems: their Design, Implementation and Use, Appin, Scotland, August 1987 [DODCSC83] Department of Defense Computer Security Center, Department of Defense Trusted System Evaluation Criteria, CSC-STD-001-83, August 1983. [ECMA85] "Remote Database Access Service and Protocol", TR/30, European Computer Manufacturers Association, November 1985. [ECMA87] ISO/TC97/SC21/N363, "ECMA-Proposed Technical Assumptions for Open Distributed Processing", 1987. [ESWA76] K. P. Eswaran, et. al., "The Notions of Consistency and Predicate Locks in a Database System", Comm. ACM, 19(11), November 1976. [FISH87] D. H. Fishman, et. al., "Iris: An Object-Oriented Database Management System", ACM Trans. Office Inf. Systems, 5(1), January 1987. [FISH88] D. H. Fishman, et. al., "Overview of the Iris DBMS", unpublished paper to appear in [KIM88]. [FREY87] J. C. Freytag, "A Rule-Based View of Query Optimization", Proc. 1987 ACM-SIGMOD Intl. Conference on Management of Data, ACM, New York, 1987. [GASS87] Les Gasser, "The 1985 Workshop on Distributed Artificial Intelligence", The AI Magazine, Vol. 8, No. 2, Summer 1987. [GLAS84] Hugh Glaser, Chris Hankin, and David Till, Principles of Functional Programming, Prentice-Hall International, 1984. [GOGU84] J. A. Goguen and J. Meseguer, "Equality, Types, Modules, and Generics for Logic Programming", Proc. 2nd Intl. Logic Programming Conf., Uppsala, 1984. [GOLD83] Adele Goldberg and D. Robson, Smalltalk-80: The Language and Its Implementation, Addison-Wesley, 1983. --------------------------------------------------------------------------- [GOLD84] Adele Goldberg, Smalltalk-80 - The Interactive Programming Environment, Addison-Wesley, 1984 [GOOD87] Danny Goodman, The Complete HyperCard Handbook, Bantam Books, New York, 1987. [GRAE87] G. Graefe and D. J. DeWitt, "The EXODUS Optimizer Generator", Proc. 1987 ACM-SIGMOD Intl. Conference on Management of Data, ACM, May 1987. [GRAY78] J. N. Gray, "Notes on Data Base Operating Systems", in Operating Systems, an Advanced Course, Lecture Notes in Computer Science 60, SpringerVerlag, 1978. [GTESC87] "Systems Application Architecture (SAA): An Overview and Architectural Analysis", PA7051, GTE Service Corporation, September 1987. [HAIL86] Brent Hailpern, ed., IEEE Software, Vol. 3, No. 1, January 1986, special issue on Multiparadigm Languages and Environments. [HANN87] Demonstration of Cooperating Message Handling/X400 Products from 11 manufacturers, Hannover Fair, 1987. [HATZ87] M. Hatzopoulos, ed., "Distributed Aspects of Information Systems (DAISY)", Report from the Working Group DAISY of the COST 11ter European Action in Teleinformatics, Commission of the European Communities DG XIII, 1987. [HEWI77] Carl Hewitt, "Viewing Control Structures as Patterns of Passing Messages", Journal of Artificial Intelligence, 8(3), June 1977. [HINK75] T. H. Hinke and M. Schaefer, "Secure Data Management System", System Development Corporation, TM-5407/007/00, June 1975. [HOAR85] C. Hoare, Communicating Sequential Processes, Prentice-Hall, 1985. [HUDS86] S. E. Hudson and R. King, "CACTIS: A Database System for Specifying Functionally-Defined Data", in [DITT86], 26-37. [IBM87a] "Systems Application Architecture: An Overview", IBM Corporation, GC26-4341-1, September 1987. [IBM87b] "Systems Application Architecture Common Programming Interface: Application Generator Reference", IBM Corporation, SC26-4355-0, September 1987. [IEEE87] Proc. 1987 Symp. on Security and Privacy, IEEE Computer Society Press, Apr. 1987. [JARK84] Matthias Jarke, J. Clifford, and Y. Vassiliou, "An Optimizing Prolog FrontEnd to a Relational Query System", Proc. 1984 ACM-SIGMOD Conf., Boston. [JACO86] G. Jakobson, et. al., "An Intelligent Database Assistant", IEEE Expert, 1(2), Summer 1986. --------------------------------------------------------------------------- [JACO88] G. Jakobson, et. al., "CALIDA: A Knowledge-Based System for Integrating Multiple Heterogeneous Databases", Technical Note TN 88-174.1, GTE Laboratories Incorporated, 1988. [JONE86] Michael B. Jones and Richard F. Rashid, "Mach and Matchmaker: Kernel and Language Support for Object-Oriented Distributed Systems", Technical Report CMU-CS-87-150, Carnegie Mellon University, September 1986. [KAEH86] T. Kaehler, "Virtual Memory on a Narrow Machine for an Object-Oriented Language", in [MEYR86]. [KATZ81] R. H. Katz, et. al., "Database Integration and Incompatible Data Handling in MULTIBASE -- A System for integrating Heterogeneous Distributed Databases", Technical Report CCA-81-06, Computer Corporation of America, May 1981. [KATZ85] R. H. Katz, Information Management for Engineering Design, SpringerVerlag, New York, 1985. [KEEN88] Sonya Keene, Object-Oriented Programming in Common Lisp, Addison-Wesley, 1988. [KELL86] A. Keller, "Choosing a View Update Translator by Dialog at View Definition Time", Proc. Twelfth Intl. Conf. on Very Large Data Bases, Kyoto, Japan, August 1986. [KERS86] Larry Kerschberg, ed., Expert Database Systems: Proceedings from the First International Workshop, Benjamin/Cummings, Menlo Park, 1986. [KERS88] Larry Kerschberg, ed., Expert Database Systems: Proceedings of the Second International Conference on Expert Database Systems, George Mason University, 1988. [KHOS87] S. Khoshafian and P. Valduriez, "Sharing , Persistence, and Object Orientation: A Database Perspective", MCC Technical Report DB-106-87, Microelectronics and Computer Technology Corporation, April 1987. [KIM88] Won Kim and F. Lochovsky (eds.), Object-Oriented Languages, Applications, and Databases, unpublished manuscript to be published by AddisonWesley, 1988. [KRAM85] J. Kramer and J. Magee, "Dynamic Configuration for Distributed Systems", IEEE Trans. on Software Eng. SE-11:4 April 1985. [KRAM87] J. Kramer, J. Magee, M. Sloman, "The CONIC Toolkit for Building Distributed Systems", IEE Proceedings Part D, vol 134, no.2, March 1987, pp. 73- 82. [LAMP81] B.W. Lampson, M. Paul, and H.J. Siegert (eds), Distributed Systems - Architecture and Implementation, Springer-Verlag, 1981. [LAND81] C. E. Landwehr, "Formal Models for Computer Security", Computing Surveys 13(3), Sept. 1981. --------------------------------------------------------------------------- [LAND82] T. Landers and R. L. Rosenberg, "An Overview of MULTIBASE", in H. J. Schneider, ed., Proc. 2nd Intl. Symp. on Distributed Databases, Berlin, W. Germany, September 1982. [LIND84] Bruce Lindsay, et. al., "Computation and Communication in R*: a Distributed Database Manager", ACM Trans. Computer Syst., 2(1), Feb. 1984. [LIND86] Bruce Lindsay, et. al., "A Snapshot Differential Refresh Algorithm", Proc. 1986 ACM-SIGMOD Intl. Conference on Management of Data, ACM, New York, 1986. [LIND87] Bruce Lindsay, John McPherson, and Hamid Pirahesh, "A Data Management Extension Architecture", Proc. 1987 ACM-SIGMOD Intl. Conference on Management of Data, ACM, New York, 1987. [LINN86] J. L. Linn and R. I. Winner (eds.), "Department of Defense Requirements for Engineering Information Systems", Vols 1 & 2, Institute for Defense Analyses, Alexandria, VA, July 1986. [LISK81] B. Liskov, CLU Reference Manual, Lecture Notes in Computer Science 114, Springer-Verlag, 1981. [LISK83] B. Liskov and R. Scheifler, "Guardians and Actions, Linguistic Support for Robust Distributed Programs", ACM Trans. Prog. Systems and Languages, July 1983. [LISK88] B. Liskov, "Distributed Programming in Argus", Comm. ACM, 31(3), March 1988. [LITM88] A. Litman, "The DUNIX Distributed Operating System", Operating Systems Review, ACM, January 1988. [LOCH85] F. Lochovsky (ed.), Database Engineering, Vol. 8, No. 4, Special Issue on Object-Oriented Systems, IEEE Computer Society, 1985. [LOHM85] Guy M. Lohman, et. al., "Query Processing in R*", in Won Kim, D. S. Reiner, and D. S. Batory (eds), Query Processing in Database Systems, SpringerVerlag, 1985. [LORI77] R. A. Lorie, "Physical Integrity in a Large Segmented Database", ACM Trans. Database Systems, 2(1), March 1977. [LORI82] R. A. Lorie, "Issues in Database for Design Applications", in J. Encarnacao and F.-L. Krause (eds.), File Structures and Data Bases for CAD, NorthHolland, Amsterdam, 1982. [LUM84] V. Lum, et. al., "Designing DBMS Support for the Temporal Dimension", Proc. 1984 ACM-SIGMOD Intl. Conference on Management of Data, ACM, New York, 1984. [LYNC86] N. Lynch and M. Merrit, "Introduction to the Theory of Nested Transactions", MIT/LCS/TR-367, Mass. Inst. of Technology, July 1986. --------------------------------------------------------------------------- [LYNG86] Lyngbaek, P., and W. Kent, "A Data Modeling Methodology for the Design and Implementation of Information Systems", in [DITT86], 6-17. [MAGE87] J. Magee, J. Kramer, M. Sloman, "Constructing Distributed Systems in Conic", Imperial College Research Report DOC 87/4, October 1987, to be published in IEEE Transactions on Software Engineering. [MAIE86] David Maier, Jacob Stein, Allen Otis, and Alan Purdy, "Development of an Object-Oriented DBMS", in [MEYR86]. [MANO82] Manola, F., A. Pirotte, B. T. Blaustein, and D. R. Ries, "A Family of Data Model Specifications for DBMS Standards," Technical Report CCA-82-03, Computer Corporation of America, (25 May 1982). Available as NBS-GCR-82- 419, National Bureau of Standards, Washington, D.C. (May 1982). [MANO86a] Manola, F.A., and J.A. Orenstein, "Toward a General Spatial Data Model for an Object-Oriented DBMS," Proc. Twelfth Intl. Conf. on Very Large Data Bases, Kyoto, August 1986. [MANO86b] Manola, F., and U. Dayal, "PDM: An Object-Oriented Data Model", in [DITT86], 18-25. [MANO87] F. Manola, "A Position Paper on Implementation Aspects of ObjectOriented Database Systems", unpublished position paper submitted for the workshop on Object-Oriented DBMS Implementation Issues, OOPSLA 87. [MANO88] F. Manola, "IBM's Systems Application Architecture (SAA) and its Relationship to the DOM Project", DOM Project Technical Memorandum, GTE Laboratories Incorporated, March 28, 1988. [MCAR84] Heinz McArthur, "The Design and Implementation of an ObjectOriented, Production-Rule Interpreter", MS Thesis, Naval Postgraduate School, Monterey, CA, December 1984. [MCCU87] Paul L. McCullough, "Transparent Forwarding: First Steps", in [MEYR87]. [METT87] William Mettrey, "An Assessment of Tools for Building Large Knowledge-Based Systems", The AI Magazine, 8(4), Winter 1987. [MEYE86] Bertrand Meyer, "Genericity versus Inheritance", in [MEYR86]. [MEYR86] N. Meyrowitz, ed., OOPSLA '86 Conference Proceedings, ACM, Sept., 1986, published as SIGPLAN Notices, 21(11), Nov., 1986. [MEYR87] N. Meyrowitz, ed., OOPSLA '87 Conference Proceedings, ACM, Oct., 1987, published as SIGPLAN Notices, 22(12), Dec., 1987. [MICA88] Josephine Micallef, "Encapsulation, Reusability and Extensibility in Object-Oriented Programming Languages", Journal of Object-Oriented Programming, 1(1), April/May 1988. [MOON86] David A. Moon, "Object-Oriented Programming with Flavors", in [MEYR86]. --------------------------------------------------------------------------- [MYLO80] J. Mylopoulos, P. A. Bernstein, and H.K.T. Wong, "A Language Facility for Designing Database-Intensive Applications", ACM Trans. Database Systems, 5(2), 1980. [NCSC86] National Computer Security Center, Proc. National Computer Security Center Invitational Workshop on Database Security, June 1986 [NIER87] O. M. Nierstrasz, "Active Objects in Hybrid", ACM SIGPLAN Notices, 22(12), December 1987. [NORT87] J. Duane Northcutt, Mechanisms for Reliable Distributed Real-Time Operating Systems: The Alpha Kernel, Academic Press, 1987. [NRC83] National Research Council, Multilevel Data Management Security, National Academy Press, 1983. [NYBE86] Chris Nyberg, "An Operating System for a Database Machine", in [BORA86]. [OBRI86] P. O'Brien, B. Bullis, and C. Schaffert, "Persistent and Shared Objects in Trellis/Owl", in [DITT86]. [OREN88] J. A. Orenstein and F. A. Manola, "PROBE Spatial Data Modeling and Query Processing in an Image Database Application", IEEE Trans. Software Engineering, 14(5), May 1988. [OBER88] P. A. Oberndorf, "The Common Ada Programming Support Environment (APSE) Interface Set (CAIS)", IEEE Trans. Software Engineering, 14(6), June 1988. [ODI86] ISO/TC97/SC21/N1548, "Consolidation of Technical Contributions Relevant to the Development of a Basic Reference Model of Open Distributed Processing", 1986. [PASC86] Geoffrey Pascoe, "Elements Of Object-Oriented Programming", Byte Magazine, Volume 11 Number 8 (August 1986), pp. 139-144 [POPE83] R. Popescu-Zeletin and H. Weber, "Distributed Database Management Systems in Open System Environment", Proc. European Teleinformatic Conference, EUTECO, Varese, 1983. [RETT87a] Marc Rettig, "Prolog and SQL: A Happy Union", AI Expert, July 1987, pp. 19-24. [RETT87b] Marc Rettig, "LISPs with Class: Digitalk's PROLOG/V", AI Expert, March 1988, pp. 13-16. [RETT87c] Marc Rettig, "PROLOG with Class: Three Object-Oriented LISPs", AI Expert, November 1987, pp. 15-23. [RICH87] Joel E. Richardson and M. J. Carey, "Programming Constructs for Database System Implementation in EXODUS", Proc. 1987 ACM-SIGMOD Intl. Conference on Management of Data, ACM, New York, 1987. --------------------------------------------------------------------------- [RMDS85] ANSI/X3/SPARC Database System Study Group, "Reference Model for DBMS Standardization", SIGMOD Record, 15(1), March 1985. [ROBI82] J. A. Robinson and E. E. Sibert, "LOGLISP: Motivation, Design and Implementation", in K. L. Clark and S.-A. Tarnlund, eds., Logic Programming, Academic Press, 1982. [ROSE86] Rosenthal, A., et al., "Traversal Recursion: A Practical Approach to Supporting Recursive Applications," Proc. 1986 ACM-SIGMOD Intl Conf. on Management of Data. [ROWE86] L. A. Rowe, "A Shared Object Hierarchy", in [DITT86]. [SACC86] G. M. Sacco and M. Schkolnick, "Buffer Management in Relational Database Systems", ACM Trans. Database Systems, 11(4), December 1986. [SAND84] Henrik Sandell and Ralph Worrest, "Distributed Artificial Intelligence: Issues and Applications", Technical Note TN 84-172.4, GTE Laboratories Incorporated, December 1984. [SARI86] S. K. Sarin, "Robust Application Design in Highly Available Distributed Databases", Proc. Fifth Symp. Reliability in Distributed Software and Database Systems, 1986. [SARI87] S. K. Sarin (ed.), Database Engineering, Vol. 10, No. 3, Special Issue on Federated Database Systems, IEEE Computer Society, 1987. [SCHA86] Craig Schaffert, et. al., "An Introduction to Trellis/Owl, in [MEYR86]. [SCHL86] Schlichting, R.D., Andrews, G.R, and Purdin, T., "Mechanisms to Enhance File Availability in Distributed Systems", Proc. 16th Int. Symp. on FaultTolerant Computing, Vienna (July 1986), 44-49. [SCHM77] J. W. Schmidt, "Some High Level Language Constructs for Data of Type Relation", ACM Trans. Database Systems, 2(3), Sept. 1977. [SCHM86] Kurt Schmucker, Object-Oriented Programming for the Macintosh, Hayden, 1986 [SCHW86] P. Schwarz, et. al., "Extensibility in the Starburst Database System", in [DITT86]. [SCIO86] Edward Sciore and David S. Warren, "Towards an Integrated DatabaseProlog System", in [KERS86]. [SHIP81] Shipman, D., "The Functional Data Model and the Data Language DAPLEX," ACM Trans. Database Systems, 6 (1) (March 1981). [SHRI87a] Bruce Shriver and Peter Wegner, eds., Research Directions in ObjectOriented Programming, MIT Press, 1987 (early versions of some of these papers appeared in SIGPLAN Notices, 21(10), October 1986). --------------------------------------------------------------------------- [SHRI87b] S.K. Shrivastava, G.N. Dixon, G.D. Parrington, "Objects and Actions in Reliable Distributed Systems, Software Engineering Journal, V 2, N 5, IEE, September 1987, pp.160-168 [SKAR86] A. H. Skarra, S. B. Zdonik, and S. P. Reiss, "An Object Server for an Object-Oriented Database System", in [DITT86], 196-204. [SMIT81] J. M. Smith, et. al., "MULTIBASE -- Integrating Heterogeneous Distributed Databases", Proc. AFIPS National Computer Conf., 50, June 1981. [SMIT83] J. M. Smith, S. A. Fox, and T. A. Landers, "ADAPLEX: Rationale and Reference Manual", Technical Report CCA-83-08, Computer Corporation of America, May 1983. [SMIT85] Reid G. Smith, "Report on the 1984 Distributed Artificial Intelligence Workshop", The AI Magazine, Vol. 6, No. 3, Fall 1985. [SOMS87] Joseph Somsel, "Object-Based Shells", AI Expert, November 1987, pp. 75-79. [SPEC86] A. Z. Spector, "The Camelot Project", in [BORA86]. [SRID87] N. S. Sridharan, "1986 Workshop on Distributed AI", The AI Magazine, Vol. 8, No. 3, Fall 1987. [STEF86a] Mark Stefik and Daniel G. Bobrow, "Object-Oriented Programming: Themes and Variations", The AI Magazine, 6(4), 1986. [STEF86b] M. J. Stefik, D. G. Bobrow, and K. M. Kahn, "Integrating AccessOriented Programming into a Multiparadigm Environment", IEEE Software, 3(1), January 1986. [STEI87] Lynn Andrea Stein, "Delegation is Inheritance", in [MEYR87]. [STON81] Michael Stonebraker, "Operating System Support for Data Managers", Comm. ACM, April 1981. [STON86a] Michael Stonebraker and Larry Rowe, "The Design of POSTGRES", Proc. 1986 ACM-SIGMOD Intl. Conference on Management of Data, ACM, New York, 1986. [STON86b] Michael Stonebraker, "Object Management in POSTGRES Using Procedures", in [DITT86]. [STON86c] Michael Stonebraker and Akhil Kumar, "Operating System Support for Data Management", in [BORA86]. [STRO86] Bjarne Stroustrup, The C++ Programming Language, Addison Wesley, 1986 [STRO88] Bjarne Stroustrup, "What is Object-Oriented Programming?", IEEE Software, 5(3), May 1988. --------------------------------------------------------------------------- [SUBR84] P. A. Subrahmanyam and J.-H. You, "FUNLOG = Functions + Logic: A Computational Model Integrating Functional and Logical Programming", Proc. 4th Intl. Symp. on Logic Programming, IEEE Computer Society, 1984. [TANE81] Andrew S. Tanenbaum, Computer Networks, Prentice-Hall, 1981. [TANE85] Andrew S. Tanenbaum and Robbert van Renesse, "Distributed Operating Systems", ACM Computing Surveys, 17(4), December 1985. [THAT86] S. M. Thatte, "Persistent Memory: A Storage Architecture for ObjectOriented Database Systems", in [DITT86]. [THER83] D. G., Theriault, "Issues in the Design and Implementation of Act2", AI- TR 728, Mass. Inst. of Technology, 1983. [TOJO87] A. Tojo, "The Interoperable Database System System and OSI Promotion in Japan", Proc. Intl. Symp. on Interoperable Systems, Tokyo, 1987. [TOML88] Chris Tomlinson and Mark Scheevel, "Concurrent Object-Oriented Programming", unpublished paper to appear in [KIM88] [TSIC77] D. Tsichritzis and A. Klug, "The ANSI/X3/SPARC DBMS Framework Report of the Study Group on Database Management Systems", AFIPS Press, Montvale, NJ, 1977. [TSIC88] D.C. Tsichritzis and O.M. Nierstrasz, "Directions in Object-Oriented Research", unpublished paper to appear in [KIM88] [TURN84] Raymond Turner, Logics for Artificial Intelligence, Ellis Horwood Limited, Chichester, 1984. [ULLM86] Jeffrey Ullman, "An Approach to Processing Queries in a Logic-Based Query Language", in [BROD86a]. [WEGN87a] Peter Wegner, "Dimensions of Object-Based Language Design", in [MEYR87]. [WEGN87b] Peter Wegner, ed., "Workshop on Object-Oriented Programming, ECOOP 1987, Paris, June 18, 1987", in SIGPLAN Notices, 1987. [WEIN88] D. Weinreb, "An Object-Oriented Database System to Support an Integrated Programming Environment", Data Engineering, 11(2), June 1988. [WOEL87] Darrell Woelk and Won Kim, "Multimedia Information Management in an Object-Oriented Database System", Proc. Thirteenth Intl. Conf. on Very Large Data Bases, Morgan Kaufmann, 1987. [YOKO86] Y. Yokote and M. Tokoro, "The Design and Implementation of ConcurrentSmalltalk", in [MEYR86]. [YONE86] A. Yonezawa, J-P Briot, and E. Shibayama, "Object-Oriented Concurrent Programming in ABCL/1", in [MEYE86]. --------------------------------------------------------------------------- [YONE87] A. Yonezawa and M. Tokoro, eds., Object-Oriented Concurrent Programming, MIT Press, 1987. [ZANI84] C. Zaniolo, "Object-Oriented Programming in Prolog", Proc. 4th Intl. Symp. on Logic Programming, IEEE Computer Society, 1984. [ZDON85] S. B. Zdonik, "Object Management Systems for Design Environments", in [LOCH85]. --------------------------------------------------------------------------- Appendix A: Some Representative Distributed Operating System Projects The following are descriptions of some representative distributed operating system projects. In some cases, the descriptions were copied from descriptions of the projects "broadcast" by the projects themselves over the UseNet network news, and edited (somewhat) for insertion here. In other cases, the descriptions were taken from the cited references. Alpha Alpha [NORT87] is a highly adaptable decentralized OS oriented towards real-time applications. It provides reliable resource management transparently across physically dispersed nodes, integrating them together so they can all contribute to the same application. Alpha achieves this global resource management without employing any physically or even logically centralized entities or services. Alpha's programming model is based on passive objects (i.e., abstract data types) and node-transparent threads. Because instances of Alpha execute cooperatively as a distributed program on physically dispersed nodes, it maintains consistency of its data structures and correctness of its actions with nested atomic transactions. All contention for resources are resolved by Alpha on the basis of application specified time constraints (e.g., deadlines). Time constraints are nested block structures with asynchronous aborts, exactly like transactions. Time constraints are among the attributes propagated across node boundaries with threads so that resource management can be global. Alpha provides orphan detection and elimination in response to node or communication link failures, and to transaction or time constraint aborts. Alpha's performance is optimized for the most important cases, which for real-time systems are the emergency exceptions as opposed to the normal or most frequent cases. Alpha is kernelized with strict adherence to policy/mechanism separation; for example, it provides atomicity, serializability, and permanence as orthogonal mechanisms rather than bundling them together with the resulting overhead regardless of application requirements. The prototype of Alpha is being created by the Archons Project at CMU, directly on Sun hardware, and applications have already been done by its first user on another copy of the system at General Dynamics. A second-generation, commercial-quality, portable version of Alpha is being created by Kendall Square Research, in Cambridge MA. The second-generation "industrial strength" Alpha has additional features (e.g., UNIX interoperability) and will be portable and supported by Kendall Square Research. Release 2 will occur in 9/89 and release 3 in 9/90; 3 will have very extensive and elaborate facilities for fault tolerance, an unusual object store, and other features. Amoeba Amoeba is a research project on distributed operating systems being carried out at the Vrije Universiteit in Amsterdam under the direction of Andrew Tanenbaum and at the Centre for Mathematics and Computer Science under the direction of Sape J. --------------------------------------------------------------------------- Mullender. Its goal is to investigate capability-based, object-oriented systems, and to build a working prototype system to use and evaluate. The Amoeba architecture consists of four principal components: 1. Workstations, one per user, which are essentially intelligent terminals. At present SUN-3s are used as workstations. 2. Pool processors, where most of the computing occurs. At present two racks of pool processors are in use. One rack has 16 Motorola 68020s each with 3 MB, its own backplane and its own Ethernet connection. The other also has 16 68020s, but these are on a single VME bus and have access to shared memory on the bus. These two configurations allow parallel algorithms to be implemented with and without shared memory for comparison purposes. 3. Specialized servers, such as file servers, directory servers, and data base servers. The Amoeba file server, called the bullet server, has been designed to provide support for atomic actions, which are implemented with the help of the directory server. The bullet server has a 16 MB cache and extremely high performance. Users programs can read data at over 650 kbytes/sec (assuming cache hits). This is the user-to-user rate (not kernel-to-kernel) and includes all the protocol overhead. 4. Gateways, which are used to link Amoeba systems at different sites. Amoeba runs on 680x0, 16032, VAX, and other processors in about half a dozen countries. Work is currently in progress to produce a wide-area system that will be completely transparent. All the Amoeba machines run the same kernel, which primarily provides messagepassing services and little else. The basic idea behind the kernel was to keep it small, not only to enhance its reliability, but also to allow as much as possible of the operating system to run as user code, providing for flexibility and experimentation. The basic idea behind the Amoeba design is the abstract data type. Each Amoeba object has a capability which must be presented to allow operations to be performed. The capabilities are cryptographically protected, and are held in user space, not in the kernel. A language for parallel and distributed programming has also been designed in connection with the project. The idea is that programs in this language should be simple to write and suitable for both the shared memory and disjoint memory processor pools. The system is currently running in an experimental form. A UNIX emulation environment has been created on top of Amoeba, and most of the UNIX software, including the shell, editors, compilers, and most of the standard utilities, has been ported. A parallel 'make' has also been implemented that spreads compilations over multiple processors to gain large performance improvements. The problem of locating objects in the contents of the Amoeba system has proven to be an interesting issue. In Amoeba, objects are managed by services. Services can have a distributed implementation and many server processes. In principle, all server processes in a single service give identical service; if an object can be accessed through one of them, it can also be accessed through another. Objects are --------------------------------------------------------------------------- addressed using capabilities. Each capability consist of a port--which names the service that manages the object--and a private part--which names the object within the service. The port, for the purposes of locating servers, is just a random number. In a local-area network, locating objects is fairly straightforward: A client wishing to do an operation on an object locates a server by broadcasting a `where are you' message. The server responds and the request can be sent. The results of these locate operations are cached and our experience is that locates need not be done very often. Servers and clients can migrate and servers can crash to be replaced by new ones, because when cached information is found to be incorrect, a new locate can be done. (Servers and clients can even migrate in the middle of an operation, but this is another story.) Amoeba also runs over wide-area networks. In fact, Amoebas are running in half a dozen European countries and operations by clients in one country on objects on servers in another work. Locating objects over wide-area networks using broadcast is impractical, however. This is dealt with by considering the network to be essentially a two-level hierarchy. The bottom level is called the `local internet,' one or more local networks, connected by bridges or gateways. The essence of the local internet is that it is small enough to do broadcast over. Objects in a local internet are thus located using the broadcast method described above. The second level is the wide-area network. An Amoeba (i.e., Amoeba running over a local internet) is connected to the wide-area network via a gateway. The gateway converts from the high-performance Amoeba protocol which runs over the local internet to whatever has to run over the wide-area network (usually X.25, in Europe). It also assists in locate operations. Capabilities have a third field, called a location hint. The hint is essentially the name of a gateway on the local internet where the server for the associated object resides. What happens when a client locates a server for an object is this: The client broadcasts the port (with the hint) over the local internet as usual. If there is a local server, everything proceeds as described above. If there is not, and the hint indicates a remote gateway, the local gateway will respond as if it is the server. The request will then be sent to the gateway, the gateway will send the request to the remote gateway as prescribed by the hint, and the remote gateway will then broadcast for the server on its local internet. This should find the server. There are restrictions on the mobility of servers in this scheme. When a server migrates from one local internet to another, it can no longer be located. Note that this restriction does not apply to objects, as long as a server stays behind to do the forwarding. In the context of our project, we do not feel that this is a restriction; so far, there seems to be no need for migrating servers or objects over vast distances. The project has concluded that efficient locate algorithms must take into account that: 1. Local traffic dominates. Get that to work efficiently first. 2. You can't afford to broadcast over large networks. You must keep track of migrating object's locations, either by using forwarding addresses or by using name servers. Argus --------------------------------------------------------------------------- Argus [LISK83, LISK88] attempts to provide an integrated language and associated run-time support system for the construction of distributed programs. It has been under development at MIT since 1979. The Argus programming interface is provided by a dialect of CLU, extended to support distribution, concurrency control, and atomic actions. CLU itself is strongly-typed, and includes automatic garbage collection. The intended application domain for Argus is systems where the preservation of persistent data is very important (airline reservations, office automation, database applications), and response time is less critical. In Argus, distributed programs are created from a collection of communicating guardians. Guardians are effectively virtual nodes, with stable data storage and unlimited main memory, connected by a communication network. Like objects, guardians encapsulate data, and contain procedures (called handlers) that provide the only means of accessing the data contained within the guardian. Each guardian can contain a number of processes that execute asynchronously with respect to other processes in the system. Each handler is associated with a separate process within the guardian. In addition, other processes can also be defined within guardians (e.g., to perform background or housekeeping functions within the guardian). Atomic actions are used to synchronize access to the shared data within guardians. In addition, critical regions can also be used to synchronize processes within a guardian. The language allows the invocation of operations (handlers) on guardians in a manner which is independent of the location of the destination guardian. Currently, Argus runs on Unix. Each guardian is implemented as a Unix process, and invocations are performed by an RPC service built on top of the Unix IPC facility. Each Argus (internal) process has its own stack segment, transient data segment, and process control block, and each guardian has its own scheduler for its internal processes. Stable storage is simulated using the Unix raw disk interface. Arjuna Arjuna [DIXO87a, DIXO87b, SHRI87b] is an object-based fault-tolerant distributed programming system at the University of Newcastle upon Tyne. The system is being designed and implemented in the language C++ on a set of UNIX workstations connected by Ethernet. Arjuna employs atomic actions (transactions) for structuring programs. Programs operate on objects which are instances of abstract data types. In Arjuna, objects are long-lived entities (persistent) and are the main repositories for holding system state. By ensuring that objects are only manipulated within atomic actions, it can be guaranteed that the integrity of the objects (and hence the integrity of the system) is maintained in the presence of failures such as node crashes and the loss of network messages. There are several unusual aspects of Arjuna. These include (i) use of multicast remote procedure calls for managing a variety of activities of process groups, such as commit processing; (ii) use of type-inheritance for specifying and implementing recovery and concurrency control strategies; and (iii) use of nested, concurrent actions for program structuring. Arjuna objects are normally resident in local object stores in a passive mode; an object invocation activates the stored object. When an object commits (terminates), active objects are put back on the respective object stores (passivated). Major parts have been implemented, and these are currently being integrated to form a complete system. --------------------------------------------------------------------------- CHORUS Chorus was a research Project on Distributed Systems at INRIA in France from 1979 to 1986. In December 1986, most of the researchers that had been working on the Chorus research project formed a Company called Chorus Systemes to further develop, industrialize and market CHORUS on a commercial basis. CHORUS is based on a message passing kernel. CHORUS basic concepts for handling distribution are "Ports" and "Messages". System as well as Application services are provided by means of processes (called Actors), communicating by exchanging messages. CHORUS-V2 is UNIX compatible, at the object code level. It supports all standard Unix programs, in a distributed environment. Files, devices, processor resources, etc., distributed over several machines on a LAN, can be accessed in the same way, and with the same programs, as on a conventional Unix system. CHORUS provide transparent access to "distributed names" that can be associated with any type of service and/or resource, rather than to a specific set of particular remote resources as does NFS for example with files. The current version, being developed by Chorus systems, is called CHORUS-V3. Its main features are: 1. Unix compatibility for user programs is at the EXECUTABLE code level, with other Unix systems running on the same hardware (assuming same compilers and linker), i.e. Unix application executables can be run unchanged on CHORUS-V3. 2. The Unix interface supported includes POSIX, System V (X/OPEN) and 4.3 BSD/SUN extensions (sockets, NFS). 3. Distributed Virtual Memory will be provided with object (e.g. files) mapping into memory over the network. 4. Actors (i.e. processes) can be "multiplexed" into several "activities" (i.e. "threads" as used in the Mach system described later in this Appendix), sharing the actor's resources. 5. Unix modularity of user programs has been extended to system services: file, process, network management, device drivers, etc. are implemented as "standard" actors, and are not part of the kernel. Therefore, only those system functions actually required need to be installed. They can be complemented or reduced dynamically while the system is running. In particular, drivers can be installed, changed or removed on-line. This provides extremely powerful tools for dynamically optimizing distributed system configurations to evolving application requirements. 6. The CHORUS kernel itself is implemented as a "multi-threads actor" and "userlevel" threads can be dynamically attached to the kernel. 7. User procedures may also be attached dynamically to interrupt vectors to allow efficient handling of interrupts, thus providing tools for real-time applications. --------------------------------------------------------------------------- 8. Unix compatibility is also provided at drivers level, allowing to port such drivers at very low-cost. 9. Portability of the system has been considerably improved by means of careful study of various hardware architectures, increased modularity of the system components and programming language used for implementation (C++ and C). A first release of CHORUS-V3 is planed to be available for beta-testing 3Q-88, on Bull/SPS-7, SUN-3, and PC/AT-386. Conic Toolkit The Conic toolkit [KRAM85, KRAM87, MAGE87] is a project at Imperial College, London. It is intended to simplify the problems of building distributed systems by means of a language-based approach. The Toolkit provides a comprehensive set of tools for program compilation, configuration, debugging and execution in a distributed environment. Flexible configuration, modularity and reuse of software components is facilitated by separation of the language for programming individual task modules ("programming in the small") from the language for configuring programs from predefined modules ("programming in the large"). Conic permits applications to be distributed across multiple Unix (is a trademark of AT&T Bell Laboratories) systems as well as target computers with no resident operating system other than the Conic executive. Targets can be used for those parts of an application which require real-time response. The host Unix systems are used for software development and to provide the targets with run-time access to the services and facilities expected from a general purpose operating system. A distributed application program in a Conic environment consists of one or more interconnected logical nodes. A logical node is a unit of configuration and executes on a host as a UNIX process or directly on a target. Each logical node is composed from a set of tasks which execute pseudo-concurrently. Tasks within a logical node share the same address space. Targets with memory management hardware may run more than one logical node. The Main Features of the Conic Toolkit are: ? Conic Programming Language: a Pascal based language, with extensions for modularity and message passing, used to program individual tasks (processes). ? Support for both asynchronous (unblocked) message transactions and synchronous request-replies . ? Local and remote communication has the same syntax and logical behavior. Tasks running on targets can communicate directly with tasks running inside host logical nodes. ? Compile time type checking detects programming errors and improves safety. ? The configuration language is used to specify the module instances within a logical node and their interconnection. --------------------------------------------------------------------------- ? An on-line configuration manager supports the initial configuration and subsequent change to a set of logical nodes running in a variety Unix systems and target computers. ? Configuration time type checking detects interface incompatibilities. ? Hides differences in processor type in a mixed machine environment. Automatic transformation of information representation between heterogeneous hardware. ? The Conic run-time support facilities are implemented using the same tools and techniques as distributed applications. This permits users to tailor or extend the system facilities to suit their particular requirements. Current State The Conic Toolkit is available on VAX computers running Unix BSD 4.2, 4.3, Ultrix and Sun Computers running their Sun Version 3.x Unix. The targets currently supported are LSI 11 microcomputers, Motorola 68000 (MVME 101)and 68020 (MVME 133). Local area network support is provided to access the User datagram protocol from the Unix host computers and drivers are available for LRT VME Ethernet boards and DEC DEQNA boards in targets. Current research is being directed toward ? Specification of behavior of individual modules and composition rules for the behavior of groups of modules. ? Support for distributed real-time data bases. ? Heterogeneous Systems: Use of Conic Configuration Language with other programming languages. ? Support for management domains. ? The provision of fault tolerance and atomic transactions. Current Users of the Conic Toolkit include: British Coal, British Petroleum Research Centre, GEC Research PLC, British Telecom Research Laboratory, and the universities of Sussex, Glasgow in the U.K., Toronto & York in Canada, Nice & Ecole Nationale Superieure De Techniques Avancees in France, Linkoping in Sweden, KIT & KAIST in Korea. --------------------------------------------------------------------------- DUNIX DUNIX [LITM88] is an operating system being developed at Bell Communications Research that integrates several computers, connected by a packet switching network, into a single UNIX* machine. As far as the users and their software can tell, the system is a single large computer running UNIX. This illusion is created by the cooperation of the computers' kernels. The illusion is so complete, that the kernels are able to migrate any process from one computer to another without disturbing the behavior of the process. The DUNIX kernel is procedure call oriented and follows the principle of information hiding. The code that implements a specific system call (e.g., open) does not know whether the object in question (the file) is local or remote. This uniformity makes the kernel small and easy to maintain. The system behaves gracefully under subcomponents' failures. Users who do not have objects (tty, files, processes) in a given computer are not disturbed when that computer crashes. The system administrator may switch a disk from a sick computer to a healthy one, and remount the disk under the original path-name. After the switch, users may access files in that disk via the same old names. DUNIX exhibits surprisingly high performance. For a compilation benchmark, DUNIX is faster than 4.2 BSD, even if in the DUNIX case all the files in question are remote. A DUNIX installation consisting of five VAXes connected by an Ethernet has been running in Bell Communications Research since September 1986. This system is on the Internet network and speaks the TCP/IP protocols. Researchers in Bellcore and other institutes are porting DUNIX to Suns and Micro-VAXes. Mach Mach [JONE86] is a multiprocessor operating system kernel currently under development at Carnegie Mellon University. The design of Mach draws heavily on CMU's previous experience with the Accent network operating system. Important aspects of the Mach design are: ? kernel objects are referenced via object capabilities ? all system services are provided via a capability-based interprocess communication mechanism ? all systems abstractions allow extensibility to multiprocessors and networks of uniprocessor or multiprocessor nodes ? The underlying mechanism for communications provides support for protection as well as network transparency ? support for parallelism allows for a wide range of tightly coupled and loosely coupled multiprocessors Mach is binary compatible with Berkeley Unix 4.3, and is source compatible with existing Accent code. Mach is currently in production use by CMU researchers for various applications, such as multiprocessor speech recognition and construction of parallel production systems. Mach runs on a range of machines, including the Apple Macintosh II, IBM RT, MicroVax II, Sun 3, VAX, BBN Butterfly GP1000, and Encore Computer Multimax. --------------------------------------------------------------------------- Included in the Mach environment is an interface specification language called Matchmaker, which provides programming language support for distributed objectoriented programming. Specifically, Matchmaker provides: ? support for multiple existing programming languages ? language support for object references ? language interfaces for object operations ? language- and machine-independent operation interface specifications ? automated interface code generation from interface specifications Mach and Matchmaker do not provide a pure object-oriented environment, in that not everything is an object. The only true objects present are ports (communication channels used as protected capabilities for objects), and other types defined as ports. Both "normal" data and object references are supported. Neither Mach nor Matchmaker provide directly for inhieritance of operations between classes of objects, but some servers within the environment do provide for inheritance. Network Computing System NCS (Network Computing System) is a portable implementation of NCA (Network Computing Architecture) developed at Apollo Computer. NCA is an objectoriented framework for building distributed applications. Its design is based on the concepts of object, object type, operation, and interface. Objects are manipulated only through well-defined operations. The object type defines the semantics of the operations. Operations which are behaviorally related are gathered into interfaces. The intent of the architecture is to enable application designers to think in terms of invoking operations on remote objects in a location independent manner, rather than as calls to a particular machine. Objects, types, and interfaces are all named uniformly by Universal Unique Identifiers (UUIDS). A uuid is similar to a capability, except it doesn't carry access rights. The architecture is more suited to "heavyweight" objects (files, processes, devices, array processors, databases, etc.) than to "lightweight" objects (i.e. typical programming language data types). NCA consists of four components: an interface description language (NIDL) for describing interfaces exported by type managers; an at-most-once RPC protocol; a "Global Location Broker", for locating objects; and a network data representation which describes the format of data on the wire. The NIDL language enforces the object oriented view in the following manner. All operations in an interface are expected to have 'handle' as their first parameter. This handle denotes the object on which the operation is being invoked. It is similar to the 'self' parameter of Smalltalk, or the 'this' parameter of C++. The architecture defines a primitive type, called handle_t which is used as the type of the handle parameter. One could imagine the handle as just being a socket address, but in the NCS implementation it actually has a bit more structure. In any case, handle_t is opaque to clients. The architecture also provides for user-definable handle types as well. The abstract overview of how a client invokes operations on a an object as follows. Objects are managed by a type manager, which registers its managed objects with the Global Location Broker (GLB), along with the associated types and exported --------------------------------------------------------------------------- interfaces. A client program that wishes to invoke operations on a remote object calls the GLB passing it the object's UUID. The GLB returns a list of exported interfaces and the network address for that interface. This network address can be turned into a handle and used in conjunction with the RPC protocol to invoke operations on the remote object. The concrete way this is done in NCS is by calling an runtime routine that converts a socket address into one of these primitive handles. (In this approach, the socket address must be taken as a hint. It doesn't deal directly with the movement of an object while a client is bound to it). NCS is an implementation of the above architecture. It provides an RPC runtime based on datagrams. The Berkeley socket abstraction is used for transport independence. The runtime is designed to use lightweight processes if the host OS provides them. The interface compiler takes interfaces described by NIDL input and generates client and server side stubs which interface to the RPC runtime. The compiler is fairly sophisticated in that it does as much of the marshalling and unmarshalling (and data conversion) of parameters inline as possible. The compiler can also hide much of the work of locating and binding to objects from clients. The GLB is implemented as a loosely consistent replicated database. "Loosely consistent" means that updates are not immediately propagated to all replicas, but the replicas will become consistent over time in the absence of conflicting updates. The architecture (NCA) has been put into the public domain. NCS is available from Apollo in either source form or binary form for a variety of machines. Saguaro Saguaro [ANDR87b, SCHL86] is a distributed operating system for computers connected by a local-area network being developed at the University of Arizona. Saguaro is implemented in the SR distributed programming language. Features of Saguaro include: channels - an interprocess communication and synchronization facility that generalizes UNIX pipes. Specifically, channels provide the communication and synchronization mechanism to connect the input and output streams of different commands. Each channel has one write port and one or more read ports. Data written to a channel's write port is buffered on each of the channel's read ports. More than one process can write to a channel's write port, in which case the different streams are merged in the order in which the writes are serviced by the channel. Also, more than one process can read from the same read port, in which case each process consumes some subset of the data buffered on that port. reproduction sets and metafiles - In Saguaro, semi-transparent file replication and access is supported by two mechanisms: reproduction sets and metafiles. A reproduction set is a collection of two or more files that the system attempts to keep identical each time a file is closed. If one member of the reproduction set is inaccessible at that time, the user is notified of the error. A metafile is a special file that contains symbolic pathnames of other files, a generalization of UNIX symbolic links. When a metafile is encountered during the pathname traversal performed upon file open, an open is attempted on each of the names contained in the metafile until one succeeds. The open fails only when it has been determined that every component file is inaccessible. --------------------------------------------------------------------------- UTS - Saguaro makes extensive use of the Universal Type System (UTS), a type system containing a type expression language and an external data representation. The type expression language is used in the system to describe user data such as files and to specify the types of arguments to commands and procedures; the external data representation is used as the basis for representing the data stored in system constructs such as files and channels. These uses of UTS enable the system to assist in type checking and leads to a user interface in which commandspecific templates are available to facilitate command invocation. Sprite Sprite is an operating system under development at U.C. Berkeley over the last three years. Sprite aims to optimize use of the emerging technologies of local-area networks, workstations with large physical memories, and multiprocessor workstations. While Sprite's facilities are similar in appearance to those of 4.3 BSD UNIX, the kernel has been completely re-implemented to provide a highperformance network file system, process migration, and shared address spaces. Sprite is intended to provide high-quality support to a relatively small internet or local-area network, ranging from a few dozen to a few hundred users, and to combine the advantages of timesharing with the high performance of personal workstations. One of the features of the Sprite kernel implementation is its remote-procedure call (RPC) facility, which kernels of different nodes (workstations) use to request services from each other. The basic round-trip time for a simple RPC with no parameters is about 2.5 ms on Sun-3 workstations. Fragmentation of large packets allows bulk data transfers to occur at speeds upward of 700 kbytes/sec on Sun-3 workstations. Also, Sprite's kernel is multi-threaded, enabling the system to support multiprocessors. To allow more than one process to execute kernel code safely at one time, there are explicit locks on modules and data structures. The network file system appears to users as a single shared hierarchy, even though the file storage is distributed among several server machines. File operations behave exactly the same as if they were executed on a single BSD timesharing system. To achieve high performance in the network file system, both clients and servers keep main-memory caches of recently-used disk blocks. The Sprite file system negotiates with the virtual memory system over usage of physical memory, so the file caches can grow very large when virtual memory demands are low. The caches improve performance by reducing disk traffic and eliminating network traffic between servers and clients. To coordinate shared access to files, Sprite disables client caching for any file that is open for writing on one node (workstation) while open for either reading or writing on another. Consistency actions are implemented by the servers when files are opened or closed. The resulting performance degradation is judged --based on measurements on UNIX systems-- to be minimal, because files are open only for very short intervals and write-sharing of files is infrequent. Preliminary performance measurements show that the Sprite caching mechanism allows most programs to execute only 1-5% slower on diskless workstations than on workstations with disks. Many programs run 10-40% faster under Sprite's network file system than under other network file systems, such as Sun's NFS. Sprite provides a process migration facility that allows processes to be moved between nodes with compatible instruction sets. This allows users to take --------------------------------------------------------------------------- advantage of idle workstations around the network by offloading large jobs. For example, Sprite contains a new version of the ''make'' utility that uses process migration to run independent portions of the make concurrently on different workstations. The network file system plays a large role in process migration by allowing any file to be accessed by any workstation. Thus it isn't necessary to move files when migrating processes. In addition, Sprite uses ordinary files for backing storage in the virtual memory system. Thus, all that needs to be done to transfer a process's address space is to page it out from its old workstation to the backing file and page it in again on the new workstation. In order to support multiprocessors, Sprite's implementation of virtual memory provides a simple mechanism for shared address spaces. It allows multiple processes to share the heap segment of memory using a new form of the ''fork'' system call. Sprite's sharing mechanism is all-or-nothing: a process cannot share one portion of its heap with one process and another portion with other processes. The Sprite team was formed in the fall of 1984, and coding began in 1985. At present all of the major pieces of the system except for process migration are operational; migration is temporarily disabled, pending a revision of the file system. All Sprite development is done on Sprite, and members of the project use Unix systems only for those few tools that have not yet been ported to Sprite (generally, programs that do not run under X11). Current work includes studying the interaction between virtual memory and the file system, adding user-level processes to implement parts of the file system, and reimplementing the file system to use an append-only log format (suitable for use on write-once optical disks). ---------------------------------------------------------------------------