Complete Linux

home *** CD-ROM | disk | FTP | other *** search

/ Complete Linux / Complete Linux.iso / docs / apps / database / postgres / postgre2.z / postgre2 / doc / papers / shared_object_ < prev next >

Wrap

Text File | 1992-08-27 | 56.4 KB | 1,772 lines

.\" .\" To print this paper do the following: .\" tbl xxx | troff -me .\" .\" .\" .ds l] /usr/new/lib/bmac .\".so \*(l]/bmac.std .\" @(#)bmac.std 2.4 10/15/84; .\" standard format troff commands .\" citation formatting strings .ds [[ [ .ds ]] ] .ds ], ,\| .ds ]- - .ds [. " \& .ds .] . .ds [, " \& .ds ,] , .ds [? " \& .ds ?] ? .ds [: " \& .ds :] : .ds [; " \& .ds ;] ; .ds [! " \& .ds !] ! .ds [" " \& .ds "] \&" .ds [' " \& .ds '] ' .ds [< " \& .ds >] .\" reference formmating strings .ds a] " \& .ds b] , \& .ds c] , \& .ds n] "\& and \& .ds m] "\& and \& .ds p] . .\" reference formmating macros .de s[ \" start reference .nh .IP [\\*([F] 5m .. .de e[ \" end reference .[- .. .de [] \" start to display collected references .LP .. .de ][ \" choose format .ie !"\\*([J"" \{\ . ie !"\\*([V"" .nr t[ 1 \" journal . el .nr t[ 5 \" conference paper .\} .el .ie !"\\*([B"" .nr t[ 3 \" article in book .el .ie !"\\*([R"" .nr t[ 4 \" technical report .el .ie !"\\*([I"" .nr t[ 2 \" book .el .nr t[ 0 \" other .\\n(t[[ .. .de 0[ \" other .s[ .if !"\\*([A"" \\*([A\\c .if !"\\*([T"" , \\*([T\\c .if !"\\*([V"" , Vol. \\*([V\\c .if !"\\*([O"" , \\*([O\\c .if !"\\*([D"" , \\*([D\\c \&. .e[ .. .de 1[ \" journal article .s[ .if !"\\*([A"" \\*([A, .if !"\\*([T"" \\*(lq\\*([T\\*(rq, \\fI\\*([J \\*([V\\fP\c .ie !"\\*([N"" , \\*([N .el .if !"\\*([D"" (\\*([D)\c .if !"\\*([P"" , \\*([P\c .if !"\\*([I"" , \\*([I\c \\&. .if !"\\*([O"" \\*([O. .e[ .. .de 2[ \" book .s[ .ie !"\\*([A"" \\*([A, .el .if !"\\*([E"" \{\ . ie \\n([E-1 \\*([E, eds., . el \\*([E, ed.,\} .if !"\\*([T"" \\fI\\*([T\\fP, .rm a[ .if !"\\*([I"" .ds a[ \\*([I .if !"\\*([C"" \{\ . if !"\\*(a["" .as a[ , \\& . as a[ \\*([C\} .if !"\\*([D"" \{\ . if !"\\*(a["" .as a[ , \\& . as a[ \\*([D\} \\*(a[. .if !"\\*([G"" Gov. ordering no. \\*([G. .if !"\\*([O"" \\*([O. .e[ .. .de 3[ \" article in book .s[ .if !"\\*([A"" \\*([A, .if !"\\*([T"" \\*(lq\\*([T\\*(rq, in \\fI\\*([B\\fP\c .if !"\\*([V"" , vol. \\*([V .if !~\\*([E~~ \{\ . ie , \\n([E-1 \\*([E (editors)\c . el , \\*([E (editor)\c\} .if !"\\*([I"" , \\*([I\c .if !"\\*([C"" , \\*([C\c .if !"\\*([D"" , \\*([D\c .if !"\\*([P"" , \\*([P\c \\&. .if !"\\*([O"" \\*([O. .e[ .. .de 4[ \" report .s[ .if !"\\*([A"" \\*([A, .if !~\\*([E~~ \{\ . ie \\n([E-1 \\*([E, editors. . el \\*([E, editor.\} \&\\*(lq\\*([T\\*(rq, \\*([R\c .if !"\\*([G"" \& (\\*([G)\c .if !"\\*([I"" , \\*([I\c .if !"\\*([C"" , \\*([C\c .if !"\\*([D"" , \\*([D\c \\&. .if !"\\*([O"" \\*([O. .e[ .. .de 5[ \" conference paper .s[ .if !"\\*([A"" \\*([A, .if !"\\*([T"" \\*(lq\\*([T\\*(rq, \\fI\\*([J\\fP, .if !"\\*([C"" \\*([C, .if !"\\*([D"" \\*([D\c .if !"\\*([P"" , \\*([P\c \\&. .if !"\\*([O"" \\*([O. .e[ .. .de [- \" clean up after yourself .rm [A [B [C [D .rm [E [F [G .rm [I [J [K .rm [N [O [P .rm [R [T .rm [V [W .. .de s[ \" start reference .nh .IP [\\*([F] 10n .. .nr tp 12 .nr fp 11 .nr sp 14 .nr pp 12 .nr fn 1 .\" "@(#)bibmac.me 2.2 9/9/83"; .de IP .ip \\$1 \\$2 .. .de LP .lp .. .\" macros for where lists... .de BL .ta .25i 1.25i .in +1.25i .ti -1.25i .. .de NI .ti -1.25i .. .de EL .in -1.25i .re .. .sz \n(pp .fo ''%'' .(l C .sz \n(sp .b A Shared Object Hierarchy\u\(dg\d .sz \n(pp .\".sp .\".r .\"(Draft printed: \*(td) .sp .i Lawrence A. Rowe .r .sp Computer Science Division - EECS University of California Berkeley, CA 94720 .)l .\" ***** commands to set-up for conference paper **** .\".bp .\" set-up for conference paper printing .\" set 1.5 lines spacing. .vs 16 .nr $r \n(.vu/\n(.su .nr $R \n($r .\" set margins for conf paper .\".nr L 4.0i .\".ll \nLu .\" ***** end commands to set-up for conference paper **** .(f \(dg This research was supported by the National Science Foundation under Grant DCR-8507256 and the Defense Advanced Research Projects Agency (DoD), Arpa Order No. 4871, monitored by Space and Naval Warfare Systems Command under Contract N00039-84-C-0089. .)f .sp 2 .(l C .sz \n(sp .b Abstract .)l .pp This paper describes the design and proposed implementation of a shared object hierarchy. The object hierarchy is stored in a relational database and objects referenced by an application program are cached in the program's address space. The paper describes the database representation for the object hierarchy and the use of POSTGRES, a next-generation relational database management system, to implement object referencing efficiently. The shared object hierarchy system will be used to implement OBJFADS, an object-oriented programming environment for interactive multimedia database applications, that will be the programming interface to POSTGRES. .sh 1 "Introduction" .pp Object-oriented programming has received much attention recently as a new way to develop and structure programs \*([[GoR83\*(],StB86\*(]]. This new programming paradigm, when coupled with a sophisticated interactive programming environment executing on a workstation with a bit-mapped display and mouse, improves programmer productivity and the quality of programs they produce. .pp A program written in an object-oriented language is composed of a collection of objects that contain data and procedures. These objects are organized into an \fIobject hierarchy\fP. Previous implementations of object-oriented languages have required each user to have his or her own private object hierarchy. In other words, the object hierarchy is not shared. Moreover, the object hierarchy is usually restricted to main memory. The LOOM system stored object hierarchies in secondary memory\*([<\*([[KaK83\*(]]\*(>], but it did not allow object sharing. These restrictions limit the applications to which this new programming technology can be applied. .pp There are two approaches to building a shared object hierarchy capable of storing a large number of objects. The first approach is to build an object data manager \*([[Afe85\*(],CoM84\*(],Dae85\*(],Dee86\*(],KhV87\*(],MaS86\*(],Tha86\*(]]. In this approach, the data manager stores objects that a program can fetch and store. The disadvantage of this approach is that a complete database management system (DBMS) must be written. A query optimizer is needed to support object queries (e.g., ``fetch all \fIfoo\fP objects where field \fIbar\fP is \fIbas\fP''). Moreover, the optimizer must support the equivalent of relational joins because objects can include references to other objects. A transaction management system is needed to support shared access and to maintain data integrity should the software or hardware crash. Finally, protection and integrity systems are required to control access to objects and to maintain data consistency. These modules taken together account for a large fraction of the code in a DBMS. Proponents of this approach argue that some of this functionality can be avoided. However, we believe that eventually all of this functionality will be required for the same reasons that it is required in a conventional database management system. .pp The second approach, and the one we are taking, is to store the object hierarchy in a relational database. The advantage of this approach is that we do not have to write a DBMS. A beneficial side-effect is that programs written in a conventional programming language can simultaneously access the data stored in the object hierarchy. The main objection to this approach has been that the performance of existing relational DBMS's has been inadequate. We believe this problem will be solved by using POSTGRES as the DBMS on which to implement the shared hierarchy. POSTGRES is a next-generation DBMS currently being implemented at the University of California, Berkeley \*([[StR86\*(]]. It has a number of features, including data of type procedure, alerters, precomputed procedures and rules, that can be used to implement the shared object hierarchy efficiently. .pp Figure \n(fn shows the architecture of the proposed system. .(z .hl .sp .sp 5.75i .sp .ce Figure \n(fn. Process architecture. .hl .nr fn \n(fn+1 .)z Each application process is connected to a database process that manages the shared database. The application program is presented a conventional view of the object hierarchy. As objects are referenced by the program, a run-time system retrieves them from the database. Objects retrieved from the database are stored in an object cache in the application process so that subsequent references to the object will not require another database retrieval. Object updates by the application are propagated to the database and to other processes that have cached the object. .pp Other research groups are also investigating this approach \*([[AbW86\*(],Ane86\*(],KeS86\*(],Mae87\*(],Mey86\*(],Ske86\*(]]. The main difference between our work and the work of these other groups is the object cache in the application process. They have not addressed the problem of maintaining cache consistency when more than one application process is using an object. Research groups that are addressing the object cache problem are using different implementation strategies that will have different performance characteristics \*([[KhV87\*(],Kra85\*(],MaS86\*(]]. .pp This paper describes how the OBJFADS shared object hierarchy will be implemented using POSTGRES. The remainder of this paper is organized as follows. Section 2 presents the object model. Section 3 describes the database representation for the shared object hierarchy. Section 4 describes the design of the object cache including strategies for improving the performance of fetching objects from the database. Section 5 discusses object updating and transactions. Section 6 describes the support for selecting and executing methods. And lastly, section 7 summarizes the paper. .sh 1 "Object Hierarchy Model" .pp This section describes the object hierarchy model. The model is based on the Common Lisp Object System (CLOS) \*([[BoK87\*(]] because OBJFADS is being implemented in Common Lisp \*([[Ste84\*(]]. .pp An \fIobject\fP can be thought of as a record with named \fIslots\fP. Each slot has a data type and a default value. The data type can be a primitive type (e.g., \fIInteger\fP) or a reference to another object.\** .(f \** An object reference is represented by an \fIobject identifier\fP (\fIobjid\fP) that uniquely identifies the object. .)f The type of an object is called the \fIclass\fP of the object. Class information (e.g., slot definitions) is represented by another object called the \fIclass object\fP.\** .(f \** The term \fIclass\fP is used ambiguously in the literature to refer to the type of an object, the object that represents the type (i.e., the class object), and the set of objects of a specific type. We will indicate the desired meaning in the surrounding text. .)f A particular object is also called an \fIinstance\fP and object slots are also called \fIinstance variables\fP. .pp A class inherits data definitions (i.e., slots) from another class, called a \fIsuperclass\fP, unless a slot with the same name is defined in the class. Figure \n(fn shows a class hierarchy (i.e., type hierarchy) that defines equipment in an integrated circuit (IC) computer integrated manufacturing database.\*([<\*([[RoW87\*(]]\*(>]. .(z .hl .sp .sp 4.25i .sp .ce Figure \n(fn: Equipment class hierarchy. .nr fn \n(fn+1 .hl .)z Each class is represented by a labelled node (e.g., \fIObject\fP, \fIEquipment\fP, \fIFurnace\fP, etc.). The superclass of each class is indicated by the solid line with an arrowhead. By convention, the top of the hierarchy is an object named \fIObject\fP. In this example, the class \fITylan\fP, which represents a furnace produced by a particular vendor, inherits slots from \fIObject\fP, \fIEquipment\fP, and \fIFurnace\fP. .pp As mentioned above, the class is represented by an object. The type of these class objects is represented by the class named \fIClass\fP. In other words, they are instances of the class \fIClass\fP. The \fIInstanceOf\fP relationship is represented by dashed lines in the figure. For example, the class object \fIEquipment\fP is an instance of the class \fIClass\fP. Given an object, it is possible to determine the class of which it is an instance. Consequently, slot definitions and, as described below, procedures that operate on the object can be looked-up in the class object. For completeness, the type of the class named \fIClass\fP is a class named \fIMetaClass\fP. .pp Figure \n(fn shows class definitions for \fIEquipment\fP, \fIFurnace\fP, and \fITylan\fP. .nr f1 \n(fn \" set figure number for use below. .(z .hl .in +10n .nf \fBClass\fP\ \fIEquipment\fP \fBMetaClass\fP \fIClass\fP \fBSuperclass\fP\ \fIObject\fP \fBSlots\fP Location \fIPoint\fP Picture \fIBitmap\fP DateAcquired \fIDate\fP \fBClass\fP\ \fIFurnace\fP \fBMetaClass\fP \fIClass\fP \fBSuperclass\fP\ \fIEquipment\fP \fBSlots\fP NumberOfTubes \fIInteger\fP MaxTemperature \fIDegreesCelsius\fP \fBClass\fP\ \fITylan\fP \fBMetaClass\fP \fIClass\fP \fBSuperclass\fP\ \fIFurnace\fP \fBSlots\fP .in -10n .sp .ce Figure \n(fn: Class definitions for equipment. .nr fn \n(fn+1 .hl .)z The definition of a class specifies the name of the class, the metaclass, the superclass, and the slots. The metaclass is specified explicitly because a different metaclass is used when the objects in the class are to be stored in the database. In the example, the class \fITylan\fP inherits all slots in \fIFurnace\fP and \fIEquipment\fP (i.e., \fILocation\fP, \fIPicture\fP, \fIDateAcquired\fP, \fINumberOfTubes\fP, and \fIMaxTemperature\fP). .pp Variables can be defined that are global to all instances of a class. These variables, called \fIclass variables\fP, hold data that represents information about the entire class. For example, a class variable \fINumberOfFurnaces\fP can be defined for the class \fIFurnace\fP to keep track of the number of furnaces. Class variables are inherited just like instance variables except that inherited class variables refer to the same memory location. For example, the slot named \fINumberOfFurnaces\fP inherited by \fITylan\fP and \fIBruce\fP refer to the same variable as the class variable in \fIFurnace\fP. .pp Procedures that manipulate objects, called \fImethods\fP, take arguments of a specific class (i.e., type). Methods with the same name can be defined for different classes. For example, two methods named \fIarea\fP can be defined: one that computes the area of a \fIbox\fP object and one that computes the area of a \fIcircle\fP object. The method executed when a program makes a call on \fIarea\fP is determined by the class of the argument object. For example, .(b area(x) .)b calls the \fIarea\fP method for \fIbox\fP if \fIx\fP is a \fIbox\fP object or the \fIarea\fP method for \fIcircle\f if it is a \fIcircle\fP object. The selection of the method to execute is called \fImethod determination\fP. .pp Methods are also inherited from the superclass of a class unless the method name is redefined. Given a function call ``\fIf\|(\|x\|)\|\fP'', the method invoked is determined by the following algorithm. Follow the \fIInstanceOf\fP relationship from \fIx\fP to determine the class of the argument. Invoke the method named \fIf\fP defined for the class, if it exists. Otherwise, look for the method in the superclass of the class object. This search up the superclass hierarchy continues until the method is found or the top of the hierarchy is reached in which case an error is reported. .pp Figure \n(fn shows some method definitions for \fIFurnace\fP and \fITylan\fP. .(z .hl .in +10n \fBmethod\fP Lock(self: \fIFurnace\fP) \ \. \. \. .sp 0.5v \fBmethod\fP UnLock(self: \fIFurnace\fP) \ \. \. \. .sp 0.5v \fBmethod\fP CompileRecipe(self: \fITylan\fP, recipe: \fIText\fP) \ \. \. \. .sp 0.5v \fBmethod\fP LoadRecipe(self: \fITylan\fP, recipe: \fICode\fP) \ \. \. \. .sp .in -10n .ce Figure \n(fn: Example method definitions. .nr fn \n(fn+1 .hl .)z Furnaces in an IC fabrication facility are potentially dangerous, so they are locked when they are not in use. The methods \fILock\fP and \fIUnLock\fP disable and enable the equipment. These methods are defined for the class \fIFurnace\fP so that all furnaces will have this behavior. The argument to these methods is an object representing a furnace.\** .(f \** The argument name \fIself\fP was chosen because it indicates which argument is the object. .)f The methods \fICompileRecipe\fP and \fILoadRecipe\fP compile and load into the furnace code that, when executed by the furnace, will process the semiconductor wafers as specified by the recipe text. These methods are defined on the \fITylan\fP class because they are different for each vendor's furnace. With these definitions, the class \fITylan\fP has four methods because it inherits the methods from \fIFurnace\fP. .pp Slot and method definitions can be inherited from more than one superclass. For example, the \fITylan\fP class can inherit slots and methods that indicate how to communicate with the equipment through a network connection by including the \fINetworkMixin\fP class in the list of superclasses.\** .(f \** The use of the suffix \fIMixin\fP indicates that this object defines behavior that is added to or mixed into other objects. This suffix is used by convention to make it easier to read and understand an object hierarchy. .)f Figure \n(fn shows the definition of \fINetworkMixin\fP and the modified definition of \fITylan\fP. .(z .hl .in +10n \fBClass\fP\ \fINetworkMixin\fP \fBMetaClass\fP \fIClass\fP \fBSuperclass\fP\ \fIObject\fP \fBInstance Variables\fP HostName \fIText\fP Device \fIText\fP \fBMethods\fP SendMessage(self: \fINetworkMixin\fP; msg: \fIMessage\fP) ReceiveMessage (self: \fINetworkMixin\fP) \fBreturns\fP \fIMessage\fP \fBClass\fP\ \fITylan\fP \fBMetaClass\fP \fIClass\fP \fBSuperclass\fP\ \fIFurnace\fP \fINetworkMixin\fP \\. \. \. .in -10n .sp .ce Figure \n(fn: Multiple inheritance example. .nr fn \n(fn+1 .hl .)z With this definition, \fITylan\fP inherits the slots and methods from \fINetworkMixin\fP and \fIFurnace\fP. A name conflict arises if two superclasses define slots or methods with the same name (e.g., \fIFurnace\fP and \fINetworkMixin\fP might both have a slot named \fIStatus\fP). A name conflict is resolved by inheriting the definition from the first class that has a definition for the name in the superclass list. Inheriting definitions from multiple classes is called \fImultiple inheritance\fP. .sh 1 "Shared Object Hierarchy Database Design" .pp The view of the object hierarchy presented to an application program is one consistent hierarchy. However, a portion of the hierarchy is actually shared among all concurrent users of the database. This section describes how the shared portion of the hierarchy will be stored in the database. .pp Shared objects are created by defining a class with metaclass \fIDBClass\fP. All instances of these classes, called \fIshared classes\fP, are stored in the database. A predefined shared class, named \fIDBObject\fP, is created at the top of the shared object hierarchy. The relationship between this class and the other predefined classes is shown in figure \n(fn. All superclasses of a shared object class must be shared classes except \fIDBObject\fP. This restriction is required so that all definitions inherited by a shared class will be stored in the database. .(z .hl .sp .sp 3.5i .sp .ce Figure \n(fn: Predefined classes. .nr fn \n(fn+1 .hl .)z .pp The POSTGRES data model supports attribute inheritance, user-defined data types, data of type procedure, and rules \*([[RoS87\*(],StR86\*(]] which are used by OBJFADS to create the database representation for shared objects. System catalogs are defined that maintain information about shared classes. In addition, a relation is defined for each class that contains a tuple that represents each class instance. This relation is called the \fIinstance relation\fP. .pp OBJFADS maintains four system catalogs to represent shared class information: \fIDBObject\fP, \fIDBClass\fP, \fISUPERCLASS\fP, and \fIMETHODS\fP. The \fIDBObject\fP relation identifies objects in the database: .(b CREATE DBObject(Instance, Class) .)b where .BL Instance is the \fIobjid\fP of the object. .NI Class is the \fIobjid\fP of the class object of this instance. .EL This catalog defines attributes that are inherited by all instance relations. No tuples are inserted into this relation (i.e., it represents an abstract class). However, all shared objects can be accessed through it by using transitive closure queries. For example, the following query retrieves the \fIobjid\fP of all instances: .(b RETRIEVE (DBObject*.Instance) .)b The asterisk indicates closure over the relation \fIDBObject\fP and all other relations that inherit attributes from it. .pp POSTGRES maintains a unique identifier for every tuple in the database. Each relation has a predefined attribute that contains the unique identifier. While these identifiers are unique across all relations, the relation that contains the tuple cannot be determined from the identifier. Consequently, we created our own object identifier (i.e., an \fIobjid\fP) that specifies the relation and tuple. A POSTGRES user-defined data type, named \fIobjid\fP, that represents this object identifier will be implemented. \fIObjid\fP values are represented by an identifier for the instance relation (\fIrelid\fP) and the tuple (\fIoid\fP). \fIRelid\fP is the unique identifier for the tuple in the POSTGRES catalog that stores information about database relations (i.e., the \fIRELATION\fP relation). Given an \fIobjid\fP, the following query will fetch the specified tuple: .(b RETRIEVE (o.all) FROM o IN \fIrelid\fP WHERE o.oid = \fIoid\fP .)b This query will be optimized so that fetching an object instance will be very efficient. .pp The \fIDBClass\fP relation contains a tuple for each shared class: .(b CREATE DBClass(Name, Owner) INHERITS (DBObject) .)b This relation has an attribute for the class name (\fIName\fP) and the user that created the class (\fIOwner\fP). Notice that it inherits the attributes in \fIDBObject\fP (i.e., \fIInstance\fP and \fIClass\fP) because DBClass is itself a shared class. .pp The superclass list for a class is represented in the \fISUPERCLASS\fP relation: .(b CREATE SUPERCLASS(Class, Superclass, SeqNum) .)b where .BL Class is the name of the class object. .NI Superclass is the name of the parent class object. .NI SeqNum is a sequence number that specifies the inheritance order in the case that a class has more than one superclass. .EL The superclass relationship is stored in a separate relation because a class can inherit variables and methods from more than one parent (i.e., multiple inheritance). The sequence number is required to implement the name conflict resolution rule. .pp Methods are represented in the METHODS relation: .(b CREATE METHODS(Class, Name, Source, Binary) .)b where .BL Class is the \fIobjid\fP of the class that defines the method. .NI Name is the name of the method. .NI Source is the source code for the method. .NI Binary is the relocatable binary code for the method. .EL Method code is dynamically loaded into the application program as needed. Method determination and caching are discussed below. .pp Object instances are represented by tuples in the instance relation that has an attribute for each instance variable. For example, if the classes \fIEquipment\fP, \fIFurnace\fP, and \fITylan\fP shown in figure \n(f1 were defined with metaclass \fIDBClass\fP, the relations shown in figure \n(fn would be created in the database. .(z .hl .in +10n .nf CREATE Equipment(Location, Picture, DateAcquired) INHERITS (DBObject) .sp CREATE Furnace(NumberOfTubes, MaxTemperature) INHERITS (Equipment) .sp CREATE Tylan() INHERITS (Furnace) .in -10n .fi .sp .ce Figure \n(fn: Shared object relations. .nr fn \n(fn+1 .hl .)z When an OBJFADS application creates an instance of one of these classes, a tuple is automatically appended to the appropriate instance relation. Notice that to create a shared class, the superclass of \fIEquipment\fP must be changed to \fIDBObject\fP. .pp The POSTGRES data model uses the same inheritance conflict rules for attributes that CLOS uses so attribute inheritance can be implemented in the database system. If the rules were different, OBJFADS would have to simulate data inheritance in the database or POSTGRES would have to be changed to allow user-defined inheritance rules as in CLOS. .pp Thus far, we have not described how OBJFADS data types (i.e., Common Lisp data types) are mapped to POSTGRES data types. Data types will be mapped between the two environments as specified by type conversion catalogs. Most programming language interfaces to database systems do not store type mapping information in the database\*([<\*([[Ale85\*(],Ale78\*(],Ate83\*(],Mye85\*(],RoS79\*(],Sch77\*(]]\*(>]. We are maintaining this information in catalogs so that user-defined data types in the database can be mapped to the appropriate Common Lisp data type. .pp The type mapping information is stored in three catalogs: \fITYPEMAP\fP, \fIOFTOPG\fP, and \fIPGTOOF\fP. The \fITYPEMAP\fP catalog specifies a type mapping and procedures to convert between the types: .(b CREATE TYPEMAP(OFType, PGType, ToPG, ToOF) .)b where .BL OFType is an OBJFADS type. .NI PGType is a POSTGRES type. .NI ToPG is a procedure that converts from the OBJFADS type to the POSTGRES type. .NI ToOF is a procedure that converts from the POSTGRES type to the OBJFADS type. .EL The table in figure \n(fn shows the mapping for selected Common Lisp types. .(z .hl .TS center box; l | l | l l | l | lw(1.5i). \fBCommon Lisp POSTGRES Description\fP = fixnum int4 4 byte integer. _ float float 4 byte floating point number. _ T{ (simple-array string-char) T} char[] Variable length character string. _ symbol char[] T{ .fi A string that represents the symbol (e.g., ``'x'' for the symbol \fIx\fP). T} _ (local) object char[] T{ .fi A string that contains a function call that will recreate the object when executed. T} .TE .sp .ce Figure \n(fn: Data type mapping examples. .nr fn \n(fn+1 .hl .)z Where possible, Common Lisp values are converted to equivalent POSTGRES types (e.g., \fIfixnum\fP to \fIint4\fP). In other cases, the values are converted to a print representation when they are stored in the database and recreated by evaluating the print representation when they are fetched into the program (e.g., symbols and functions). We expect over time to build-up a set of user-defined POSTGRES types that will represent the commonly used Common Lisp types (e.g., \fIlist\fP, \fIrandom-state\fP, etc.). However, we also expect application data structures to be designed to take advantage of the natural database representation. For example, it makes more sense to store a list as a separate relation with a common attribute (e.g., a \fIPO#\fP that joins a purchase order with the line items it contains) than as an array of \fIobjid\fP's in the database. .pp Class variables are more difficult to represent than class information and instances variables. The straightforward approach is to define a relation \fICVARS\fP that contains a tuple for each class variable: .(b CREATE CVARS(Class, Variable, Value) .)b where \fIClass\fP and \fIVariable\fP uniquely determine the class variable and \fIValue\fP represents the current value of the variable. This solution requires a union type mechanism because the attribute values in different tuples may have different types. POSTGRES does not support union types because they violate the relational tenet that all attribute values must have the same type. .pp Two other representations for class variables are possible with POSTGRES. First, a separate relation can be defined for each class that contains a single tuple that holds the current values of all class variables. For example, the following relation could be defined for the \fIFurnace\fP class: .(b FurnaceCVARS(NumberOfFurnaces) .)b Unfortunately, this solution introduces representational overhead (the extra relation) and requires another join to fetch the slots in an object. Moreover, it does not take advantage of POSTGRES features that can be used to update the count automatically. .pp The second alternative uses POSTGRES rules. A rule can be used to define an attribute value that appears to the application as if it was stored \*([[SHH87\*(]]. For example, the following command defines a rule that computes the number of furnaces: .(b REPLACE ALWAYS Furnace*( NumberOfFurnaces = COUNT{Furnace*.Instance}) .)b A reference to \fIFurnace.NumberOfFurnaces\fP will execute the COUNT aggregate to compute the current number of furnaces. The relation variable \fIFurnace*\fP in the aggregate specifies that tuples in \fIFurnace\fP and all relations that inherit data from \fIFurnace\fP (e.g., \fITylan\fP and \fIBruce\fP) are to be counted. With this representation, the database maintains the correct count. Notice that the command replaces this value in \fIFurnace*\fP which causes the rule to be inherited by all relations that inherit data from \fIFurnace\fP. The disadvantage of this approach is that the COUNT aggregate is executed every time the class variable is referenced. .pp POSTGRES provides another mechanism that can be used to cache the answer to this query so that it does not have to be recomputed each time the variable is referenced. This mechanism allows the application designer to request that a rule be evaluated early (i.e., precomputed) and cached in the appropriate relation. In other words, the furnace count will be cached in the relations \fIFurnace\fP, \fITylan\fP, and \fIBruce\fP so that references to the variable will avoid recomputation. Updates to \fIFurnace\fP or subclasses of \fIFurnace\fP will cause the precomputed value to be invalidated. POSTGRES will recompute the rule off-line or when the class variable is next referenced whichever comes first. .pp Class variables that are not computable from the database can be represented by a rule that is assigned the current value as illustrated in the following command: .(b REPLACE ALWAYS Furnace(x = \fIcurrent value\fP) .)b Given this definition, a reference to \fIFurnace.x\fP in a query will return the current value of the class variable. The variable is updated by redefining the rule. We plan to experiment with both the single tuple relation and rule approaches to determine which provides better performance. .pp This section described the object hierarchy model and a database design for storing it in a relational database. The next section describes the application process object cache and optimizations to improve the time required to fetch an object from the database. .sh 1 "Object Cache Design" .pp The object cache must support three functions: object fetching, object updating, and method determination. This section describes the design for efficiently accessing objects. The next section describes the support for object updating and the section following that describes the support for method determination. .pp The major problem with implementing an object hierarchy on a relational database system is the time required to fetch an object. This problem arises because queries must be executed to fetch and update objects and because objects are decomposed and stored in several relations that must be joined to retrieve it from the database. Three strategies will be used to speed-up object fetch time: caching, precomputation, and prefetching. This section describes how these strategies will be implemented. .pp The application process will cache objects fetched from the database. The cache will be similar to a conventional Smalltalk run-time system\*([<\*([[Kae81\*(]]\*(>]. An object index will be maintained in main memory to allow the run-time system to determine quickly if a referenced object is in the cache. Each index entry will contain an object identifier and the main memory address of the object. All object references, even instance variables that reference other objects, will use the object identifier assigned by the database (i.e., the \fIinstance\fP attribute). These indirect pointers may slow the system down but they avoid the problem of mapping addresses when objects are moved between main memory and the database.\** .(f \** Most Smalltalk implementations use a similar scheme and it does not appear to be a bottleneck. .)f The object index will be hashed to speed-up object referencing. .pp Object caching can speed-up references to objects that have already been fetched from the database but it cannot speed-up the time required to fetch the object the first time it is referenced. The implementation strategy we will use to solve this problem is to precompute the memory representation of an object and to cache it in an OBJFADS catalog: .(b CREATE PRECOMPUTED(Objid, ObjRep) .)b where .BL Objid is the object identifier. .NI ObjRep is the main memory object representation. .EL Suppose we are given the function \fIRepObject\fP that takes an object identifier and returns the memory representation of the object. Notice that the memory representation includes class variables and data type conversions. An application process could execute \fIRepObject\fP and store the result back in the \fIPRECOMPUTED\fP relation. This approach does not work because the precomputed representation must be changed if another process updates the object either through an operation on the object or an operation on the relation that contains the object. For example, a user could run the following query to update the values of \fIMaxTemperature\fP in all \fIFurnace\fP objects: .(b REPLACE Furnace*(MaxTemperature = \fInewvalue\fP) .)b This update would cause all \fIFurnace\fP objects in \fIPRECOMPUTED\fP to be changed.\** .(f \** \fIFurnace\fP objects cached in an application process must also be invalidated. Object updating, cache consistency, and update propagation are discussed in the next section. .)f .pp A better approach is to have the DBMS process execute \fIRepObject\fP and invalidate the cached result when necessary. POSTGRES supports precomputed procedure values that can be used to implement this approach. Query language commands can be stored as the value of a relation attribute. A query that calls \fIRepObject\fP to compute the memory representation for the object can be stored in \fIPRECOMPUTED.Objrep\fP: .(b RETRIEVE (MemRep = RepObject($Objid)) .)b \fI$Objid\fP refers to the object identifier of the tuple in which this query is stored (i.e., \fIPRECOMPUTED.Objid\fP). To retrieve the memory representation for the object with \fIobjid\fP ``Furnace-123,'' the following query is executed: .(b RETRIEVE (object = PRECOMPUTED.ObjRep.MemRep) WHERE PRECOMPUTED.objid = ``Furnace-123'' .)b The nested dot notation (\fIPRECOMPUTED.ObjRep.MemRep\fP) accesses values from the result tuples of the query stored in \fIObjRep\fP \*([[Zan83\*(]]. The constant ``Furnace-123'' is an external representation for the \fIobjid\fP (i.e., the \fIFurnace\fP object with \fIoid\fP 123). Executing this query causes \fIRepObject\fP to be called which returns the main memory representation of the object. .pp This representation by itself does not alter the performance of fetching an object. The performance can be changed by instructing the DBMS to precompute the query in \fIObjRep\fP (i.e., to cache the memory representation of the object in the \fIPRECOMPUTED\fP tuple). If this optimization is performed, fetching an object turns into a single relation, restriction query that can be efficiently implemented. POSTGRES supports precomputation of query language command values similar to the early evaluation of rules described above.\** .(f \** The POSTGRES server checks that the command does not update the database and that any procedures called in the command do not update the database so that precomputing the command will not introduce side-effects. .)f Database values retrieved by the commands will be marked so that if they are updated, the cached result can be invalidated. This mechanism is described in greater detail elsewhere \*([[Sto86\*(],Sto87\*(]]. .pp The last implementation strategy to speed-up object referencing is prefetching. The basic idea is to fetch an object into the cache before it is referenced. The \fIHINTS\fP relation maintains a list of objects that should be prefetched when a particular object is fetched: .(b CREATE HINTS(FetchObject, HintObject, Application) .)b When an object is fetched from the database by an application (\fIApplication\fP), all \fIHintObject\fP's for the \fIFetchObject\fP will be fetched at the same time. For example, after fetching an object, the following query can be run to prefetch other objects: .(b RETRIEVE (obj = p.ObjRep.MemRep) FROM p IN PRECOMPUTED, h IN HINTS WHERE p.Objid = h.HintObject AND h.FetchObject = \fIfetched-object-identifier\fP AND h.Application = \fIapplication-name\fP .)b This query fetches objects one-at-a-time. We will also investigate precomputing collections of objects, so called \fIcomposite objects\fP\*([<\*([[StB86\*(]]\*(>]. The idea is to precompute a memory representation for a composite object (e.g., a form or procedure definition that is composed of several objects) and retrieve all objects into the cache in one request. This strategy may speed-up fetching large complex objects with many subobjects. .pp We believe that with these three strategies object retrieval from the database can be implemented efficiently. Our attention thus far has been focussed on speeding up object fetching from the database. We will also have to manage the limited memory space in the object cache. An LRU replacement algorithm will be used to select infrequently accessed objects to remove from the cache. We will also have to implement a mechanism to ``pin down'' objects that are not accessed frequently but which are critical to the execution of the system or are time consuming to retrieve. .pp This section described strategies to speed-up object fetching. The next section discusses object updating. .sh 1 "Object Updating and Transactions" .pp This section describes the run-time support for updating objects. Two aspects of object updating are discussed: how the database representation of an object is updated (database concurrency and transaction management) and how the update is propagated to other application processes that have cached the object. .pp The run-time system in the application process specifies the desired update mode for an object when it is fetched from the database into the object cache. The system supports four update modes: local-copy, direct-update, deferred-update, and object-update. Local-copy mode makes a copy of the object in the cache. Updates to the object are not propagated to the database and updates by other processes are not propagated to the local copy. This mode is provided so that changes are valid only for the current session. .pp Direct-update mode treats the object as though it were actually in the database. Each update to the object is propagated immediately to the database. In other words, updating an instance variable in an object causes an update query to be run on the relation that represents instances of the object. A conventional database transaction model is used for these updates. Write locks are acquired when the update query is executed and they are released when it finishes (i.e., the update is a single statement transaction). Note that read locks are not acquired when an object is fetched into the cache. Updates to the object made by other processes are propagated to the cached object when the run-time system is notified that an update has occurred. The notification mechanism is described below. Direct-update mode is provided so that the application can view ``live data.'' .pp Deferred-update mode saves object updates until the application explicitly requests that they be propagated to the database. A conventional transaction model is used to specify the update boundaries. A begin transaction operation can be executed for a specific object. Subsequent variable accesses will set the appropriate read and write locks to ensure transaction atomicity and recoverability. The transaction is committed when an end transaction operation is executed on the object. Deferred-update mode is provided so that the application can make several updates atomic. .pp The last update mode supported by the system is object-update. This mode treats all accesses to the object as a single transaction. An intention-to-write lock is acquired on the object when it is first retrieved from the database. Other processes can read the object, but they cannot update it. Object updates are propagated to the database when the object is released from the cache. This mode is provided so that transactions can be expressed in terms of the object, not the database representation. However, note that this mode may reduce concurrency because the entire object is locked while it is in the object cache. .pp Thus far, we have only addressed the issue of propagating updates to the database. The remainder of this section will describe how updates are propagated to other processes that have cached the updated object. The basic idea is to propagate updates through the shared database. When a process retrieves an object, a database alerter\*([<\*([[BuC79\*(]]\*(>] is set on the object that will notify the process when it is updated by another process. When the alerter is trigger by another process, the process that set the alerter is notified. The value returned by the alerter to the process that set it is the updated value of the object. Note that the precomputed value of the object memory representation will be invalidated by the update so that it will have to be recomputed by the POSTGRES server. The advantage of this approach is that the process that updates an object does not have to know which processes want to be notified when a particular object is updated. .pp The disadvantages of this approach are that the database must be prepared to handle thousands of alerters and the time and resources required to propagate an update may be prohibitive. Thousands of alerters are required because each process will define an alerter for every object in its cache that uses direct-, deferred-, or object-update mode. An alerter is not required for local-copy mode because database updates by others are not propagated to the local copy. POSTGRES is being designed to support large databases of rules so this problem is being addressed. .pp The second disadvantage is the update propagation overhead. The remainder of this section describes two propagated update protocols, an alerter protocol and a distributed cache update protocol, and compares them. Figure \n(fn shows the process structure for the alerter approach. .nr f2 \n(fn \" save figure number for later reference. .(z .hl .sp .sp 3.5i .sp .ce Figure \n(fn. Process structure for the alerter approach. .hl .nr fn \n(fn+1 .)z Each application process (AP) has a database process called its POSTGRES server (PS). The POSTMASTER process (PM) controls all POSTGRES servers. Suppose that AP\di\u updates an object in the database on which M \(<= N AP's have set an alerter. Figure \n(fn shows the protocol that is executed to propagate the updates to the other AP's. The cost of this propagated update is: .(b .ta 0.8i +0.8i 2M+1 process-to-process messages .sp 0.5v \ \ \ \ 1 database update .sp 0.5v \ \ \ \ 1 catalog query .sp 0.5v \ \ \ \ 1 object fetch .)b The object fetch is avoidable if the alerter returns the changed value. This optimization works for small objects but may not be reasonable for large objects. .(z .hl .in +15n .ti -3n 1.\ \ AP\di\u updates the database. .sp 0.5v .ti -3n 2.\ \ PS\di\u sends a message to PM indicating which alerters were tripped. .sp 0.5v .ti -3n 3.\ \ PM queries the alerter catalog to determine which PS's set the alerters. .sp 0.5v .ti -3n 4.\ \ PM sends a message to PS\dj\u for each alerter. .sp 0.5v .ti -3n 5.\ \ Each PS\dj\u sends a message to AP\dj\u indicating that the alerter has been tripped. .sp 0.5v .ti -3n 6.\ \ Each PS\dj\u refetches the object. .in -15n .sp .ce Figure \n(fn. Propagated update protocol for the alerter approach. .hl .nr fn \n(fn+1 .)z .pp The alternative approach to propagate updates is to have the user processes signal each other that an update has occurred. We call this approach the \fIdistributed cache update\fP approach. The process structure is similar to that shown in figure \n(f2, except that each AP must be able to broadcast a message to all other AP's. Figure \n(fn shows the distributed cache update protocol. .(z .hl .in +15n .ti -3n 1.\ \ AP\di\u acquires the update token for the object. .sp 0.5v .ti -3n 2.\ \ AP\di\u updates the database. .sp 0.5v .ti -3n 3.\ \ AP\di\u broadcasts to all AP's that the object has been updated. .sp 0.5v .ti -3n 4.\ \ Each AP\dj\u that has the object in its cache refetches it. .in -15n .sp .ce Figure \n(fn. Propagated update protocol for the distributed cache approach. .fi .hl .nr fn \n(fn+1 .)z This protocol uses a primary site update protocol. If AP\di\u does not have the update token signifying that it is the primary site for the object, it sends a broadcast message to all AP's requesting the token. The AP that has the token sends it to AP\di\u. Assuming that AP\di\u does not have the update token, the cost of this protocol is: .(b 2 broadcast messages .br 1 process-to-process message .br 1 database update .br 1 object fetch .)b One broadcast message and the process-to-process message are eliminated if AP\di\u already has the update token. The advantage of this protocol is that a multicast protocol can be used to implement the broadcast messages in a way that is more efficient than sending N process-to-process messages. Of course, the disadvantage is that AP's have to examine all update signals to determine whether the updated object is in its cache. .pp Assume that the database update and object fetch take the same resources in both approaches and that the alerter catalog is cached in main memory so the catalog query does not have to read the disk in the alerter approach. With these assumptions, the comparison of these two approaches comes down to the cost of 2 broadcast messages versus 2M process-to-process messages. If objects are cached in relatively few AP's (i.e., M << N) and broadcast messages are efficient, the distributed cache update appears better. On the other hand, if M is larger, so the probability of doing 2 broadcasts goes up, and broadcasts are inefficient, the alerter approach appears better. We have chosen the alerter approach because an efficient multicast protocol does not exist but the alerter mechanism will exist in POSTGRES. If this approach is too slow, we will have to tune the alerter code or implement the multicast protocol. .pp This section described the mechanisms for updating shared objects. The last operation that the run-time system must support is method determination which is discussed in the next section. .sh 1 "Method Determination" .pp Method determination is the action taken to select the method to be executed when a procedure is called with an object as an argument. Conventional object-oriented systems implement a cache of recently called methods to speed-up method determination \*([[GoR83\*(]]. The cache is typically a hash table that maps an object identifier of the receiving object and a method name to the entry address of the method to be executed. If the desired object and method name is not in the table, the standard look-up algorithm is invoked. In memory resident Smalltalk systems, this strategy has proven to be very good because high hit ratios have been achieved with modest cache sizes (e.g., 95% with 2K entries in the cache)\*([<\*([[Kra83\*(]]\*(>]. .pp We will adapt the method cache idea to a database environment. A method index relation will be computed that indicates which method should be called for each object class and method name. The data will be stored in the \fIDM\fP relation defined as follows: .(b CREATE DM(Class, Name, DefClass) .)b where .BL Class is the class of the argument object. .NI Name is the name of the method called. .NI DefClass is the class in which the method is defined. .EL Given this relation, the binary code for the method to be executed can be retrieved from the database by the following query: .(b RETRIEVE (m.Binary) FROM m IN METHODS, d IN DM WHERE m.Class = d.DefClass AND d.Class = \fIargument-class-objid\fP AND d.Name = \fImethod-name\fP .)b The DM relation can be precomputed for all classes in the shared object hierarchy and incrementally updated as the hierarchy is modified. .pp Method code will be cached in the application process so that the database will not have to be queried for every procedure call. Procedures in the cache will have to be invalidated if another process modifies the method definition or the inheritance hierarchy. Database alerters will be used to signal object changes that require invalidating cache entries. We will also support a check-in/check-out protocol for objects so that production programs can isolate their object hierarchy from changes being made by application developers\*([<\*([[Kat83\*(]]\*(>]. .pp This section described a shared index that will be used for method determination. .sh 1 "Summary" .pp This paper described a proposed implementation of a shared object hierarchy in a POSTGRES database. Objects accessed by an application program are cached in the application process. Precomputation and prefetching are used to reduce the time to retrieve objects from the database. Several update modes were defined that can be used to control concurrency. Database alerters are used to propagate updates to copies of objects in other caches. A number of features in POSTGRES will be exploited to implement the system, including: rules, POSTQUEL data types, precomputed queries and rules, and database alerters. .sp 2 .ne 6 .(l C .sz \n(sp .b References .)l .sp .[] .[- .ds [F AbW86 .ds [A R\*(p]\*(a]M\*(p] Abarbanel .as [A \*(n]M\*(p]\*(a]D\*(p] Williams .ds [T A Relational Representation for Knowledge Bases .ds [O Unpublished manuscript .ds [D Apr. 1986 .][ .[- .ds [F Afe85 .ds [A H\*(p] Afsarmanesh .as [A \*(n]et.\ al. .ds [T An Extensible, Object-Oriented Approach to Databases for VLSI/CAD .ds [J Proc. 11th Int. Conf. on VLDB .ds [D Aug. 1985 .][ .[- .ds [F Ale85 .ds [A A\*(p] Albano .as [A \*(n]et.\ al. .ds [T Galileo: A Strongly-Typed, Interactive Conceptual Language .ds [J ACM Trans. Database Systems .ds [D June 1985 .nr [P 1 .ds [P 230-260 .][ .[- .ds [F Ale78 .ds [A E\*(p] Allman .as [A \*(n]et.\ al. .ds [T Embedding a Relational Data Sublanguage in a General Purpose Programming Language .ds [R Proc. of a Conf. on Data: Abstraction, Definition, and Structure, \fISIGPLAN Notices\fR, .ds [V 11 .ds [D Mar. 1978 .nr [P 1 .ds [P 25-35 .][ .[- .ds [F Ane86 .ds [A T\*(p] Anderson .as [A \*(n]et.\ al. .ds [T PROTEUS: Objectifying the DBMS User Interface .ds [J Proc. Int. Wkshp on Object-Oriented Database Systems .ds [C Asilomar, CA .ds [D Sep. 1986 .][ .[- .ds [F Ate83 .ds [A M\*(p]\*(a]P\*(p] Atkinson .as [A \*(n]et.\ al. .ds [T An Approach to Persistent Programming .ds [J Computer Journal .ds [V 26 .ds [N 4 .ds [D 1983 .nr [P 1 .ds [P 360-365 .][ .[- .ds [F BoK87 .ds [A D\*(p] Bobrow .as [A \*(n]G\*(p] Kiczales .ds [T Common Lisp Object System Specification .ds [R Draft X3 Document 87-001 .ds [I Am. Nat. Stand. Inst. .ds [D February 1987 .][ .[- .ds [F BuC79 .ds [A O\*(p]\*(a]P\*(p] Buneman .as [A \*(n]E\*(p]\*(a]K\*(p] Clemons .ds [T Efficiently Monitoring Relational Databases .ds [J ACM Trans. Database Systems .ds [D Sep. 1979 .nr [P 1 .ds [P 368-382 .][ .[- .ds [F CoM84 .ds [A G\*(p] Copeland .as [A \*(n]D\*(p] Maier .ds [T Making Smalltalk a Database System .ds [J Proc. 1984 ACM-SIGMOD Int. Conf. on the Mgt. of Data .ds [D June 1984 .][ .[- .ds [F Dae85 .ds [A U\*(p] Dayal .as [A \*(n]et.al. .ds [T A Knowledge-Oriented Database Management System .ds [J Proc. Islamorada Conference on Large Scale Knowledge Base and Reasoning Systems .ds [D Feb. 1985 .][ .[- .ds [F Dee86 .ds [A N\*(p]\*(a]P\*(p] Derrett .as [A \*(n]et.al. .ds [T An Object-Oriented Approach to Data Management .ds [J Proc. 1986 IEEE Spring Compcon .ds [D 1986 .][ .[- .ds [F GoR83 .ds [A A\*(p] Goldberg .as [A \*(n]D\*(p] Robson .ds [T Smalltalk-80: The Language and its Implementation .ds [I Addison Wesley .ds [C Reading, M\&A .ds [D May 1983 .][ .[- .ds [F Kae81 .ds [A T\*(p] Kaehler .ds [T Virtual Memory for an Object-Oriented Language .ds [J Byte .ds [V 6 .ds [N 8 .ds [D Aug. 1981 .][ .[- .ds [F KaK83 .ds [A T\*(p] Kaehler .as [A \*(n]G\*(p] Krasner .ds [T LOOM \- Large Object-Oriented Memory for Smalltalk-80 Systems .ds [E G\*(p] Krasner .nr [E 1 .ds [B Smalltalk-80: Bits of History, Words of Advice .ds [I Addison Wesley .ds [C Reading, M\&A .ds [D May 1983 .][ .[- .ds [F Kat83 .ds [A R\*(p] Katz .ds [T Managing the Chip Design Database .ds [J Computer Magazine .ds [V 16 .ds [N 12 .ds [D Dec. 1983 .][ .[- .ds [F KeS86 .ds [A J\*(p] Kempf .as [A \*(n]A\*(p] Snyder .ds [T Persistent Objects on a Database .ds [R Report STL-86-12 .ds [I Sftw. Tech. Lab., HP Labs .ds [D Sep. 1986 .][ .[- .ds [F KhV87 .ds [A S\*(p] Khoshanfian .as [A \*(n]P\*(p] Valduriez .ds [T Sharing, Persistence, and Object Orientation: A Database Perspective .ds [R DB-106-87 .ds [I MCC .ds [D Apr. 1987 .][ .[- .ds [F Kra85 .ds [A G\*(p]\*(a]L\*(p] Krablin .ds [T Building Flexible Multilevel Transactions in a Distributed Persistent Environment .ds [R Persistence and Data Types, Papers for the Appin Workshop .ds [I U. of Glasgow .ds [D Aug. 1985 .][ .[- .ds [F Kra83 .ds [E G\*(p] Krasner .nr [E 1 .ds [T Smalltalk-80: Bits of History, Words of Advice .ds [I Addison Wesley .ds [C Reading, M\&A .ds [D May 1983 .][ .[- .ds [F MaS86 .ds [A D\*(p] Maier .as [A \*(n]J\*(p] Stein .ds [T Development of an Object-Oriented DBMS .ds [J Proc. 1986 ACM OOPSLA Conf. .ds [C Portland, OR .ds [D Sep. 1986 .][ .[- .ds [F Mae87 .ds [A F\*(p] Maryanski .as [A \*(n]et.al. .ds [T The Data Model Compiler: a Tool for Generating Object-Oriented Database Systems .ds [R Unpublished manuscript .ds [I Elect. Eng. Comp. Sci. Dept., Univ. of Connecticut .ds [D 1987 .][ .[- .ds [F Mey86 .ds [A N\*(p] Meyrowitz .ds [T Intermedia: The Architecture and Construction of an Object-Oriented Hypermedia System and Applications Framework .ds [J Proc. 1986 ACM OOPSLA Conf. .ds [C Portland, OR .ds [D Sep. 1986 .nr [P 1 .ds [P 186-201 .][ .[- .ds [F Mye85 .ds [A J\*(p] Mylopoulos .as [A \*(n]et.\ al. .ds [T A Language Facility for Designing Interactive Database-Intensive Systems .ds [J ACM Trans. Database Systems .ds [V 10 .ds [N 4 .ds [D Dec. 1985 .][ .[- .ds [F RoS79 .ds [A L\*(p]\*(a]A\*(p] Rowe .as [A \*(n]K\*(p]\*(a]A\*(p] Shoens .ds [T Data Abstraction, Views, and Updates in Rigel .ds [J Proc. 1979 ACM-SIGMOD Int. Conf. on the Mgt. of Data .ds [C Boston, MA .ds [D May 1979 .][ .[- .ds [F RoS87 .ds [A L\*(p]\*(a]A\*(p] Rowe .as [A \*(n]M\*(p]\*(a]R\*(p] Stonebraker .ds [T The POSTGRES Data Model .ds [R to appear in \fIProc. 13th VLDB Conf.\fP .ds [C Brighton, England .ds [D Sep. 1987 .][ .[- .ds [F RoW87 .ds [A L\*(p]\*(a]A\*(p] Rowe .as [A \*(n]C\*(p]\*(a]B\*(p] Williams .ds [T An Object-Oriented Database Design for Integrated Circuit Fabrication .ds [R submitted for publication .ds [D Apr. 1987 .][ .[- .ds [F Sch77 .ds [A J\*(p] Schmidt .ds [T Some High Level Language Constructs for Data of Type Relation .ds [J ACM Trans. Database Systems .ds [V 2 .ds [N 3 .ds [D Sep. 1977 .nr [P 1 .ds [P 247-261 .][ .[- .ds [F Ske86 .ds [A A\*(p]\*(a]H\*(p] Skarra .as [A \*(n]et.\ al. .ds [T An Object Server for an Object-Oriented Database System .ds [J Proc. Int. Wkshp on Object-Oriented Database Systems .ds [C Asilomar, CA .ds [D Sep. 1986 .][ .[- .ds [F Ste84 .ds [A G\*(p]\*(a]L\*(p] Steele .ds [T Common Lisp - The Language .ds [I Digital Press .ds [D 1984 .][ .[- .ds [F StB86 .ds [A M\*(p] Stefik .as [A \*(n]D\*(p]\*(a]G\*(p] Bobrow .ds [T Object-Oriented Programming: Themes and Variations .ds [J The AI Magazine .ds [V 6 .ds [N 4 .ds [D Winter 1986 .nr [P 1 .ds [P 40-62 .][ .[- .ds [F StR86 .ds [A M\*(p]\*(a]R\*(p] Stonebraker .as [A \*(n]L\*(p]\*(a]A\*(p] Rowe .ds [T The Design of POSTGRES .ds [J Proc. 1986 ACM-SIGMOD Int. Conf. on the Mgt. of Data .ds [D June 1986 .][ .[- .ds [F Sto86 .ds [A M\*(p]\*(a]R\*(p] Stonebraker .ds [T Object Management in POSTGRES Using Procedures .ds [J Proc. Int. Wkshp on Object-Oriented Database Systems .ds [C Asilomar, CA .ds [D Sep. 1986 .][ .[- .ds [F Sto87 .ds [A M\*(p]\*(a]R\*(p] Stonebraker .ds [T Extending a Relational Data Base System with Procedures .ds [R to appear \fIACM TOD\fP .ds [D 1987 .][ .[- .ds [F SHH87 .ds [A M\*(p]\*(a]R\*(p] Stonebraker .as [A \*(c]E\*(p] Hanson .as [A \*(m]C\*(p]\*(a]H\*(p] Hong .ds [T The Design of the POSTGRES Rules System .ds [J IEEE Conference on Data Engineering .ds [D Feb. 1987 .ds [C Los Angeles, CA .][ .[- .ds [F Tha86 .ds [A S\*(p]\*(a]M\*(p] Thatte .ds [T Persistent memory: A Storage Architecture for Object-Oriented Database Systems .ds [J Proc. Int. Wkshp on Object-Oriented Database Systems .ds [C Asilomar, CA .ds [D Sep. 1986 .][ .[- .ds [F Zan83 .ds [A C\*(p] Zaniola .ds [T The Database Language GEM .ds [J Proc. 1983 ACM-SIGMOD Conference on Management of Data .ds [C San Jose, CA. .ds [D May 1983 .][