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