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