William Kent
Database Technology Department
Hewlett-Packard Laboratories
Palo Alto, California
1992
> 1 INTRODUCTION . . . 2
> 2 THE DUALITY OF BEHAVIOR AND STATE . . . 2
> 3 OBJECT SYSTEMS . . . 3
> 4 STATE-SENSITIVE AND STATE-CHANGING OPERATIONS . .
. 3
> 5 THE ELUSIVE NATURE OF STATE . . . 4
> 6 ATTRIBUTES . . . 4
>> 6.1 Semantics . . . 5
>> 6.2 Syntax . . . 5
> 7 RELATIONSHIPS . . . 6
>> 7.1 Binary . . . 6
>> 7.2 N-ary . . . 7
>> 7.3 Where's the Relationship? . . . 7
> 8 ATTRIBUTE AND RELATIONSHIP INSTANCES AS OBJECTS .
. . 8
> 9 VARIABLES . . . 9
> 10 IMPLEMENTING STATE . . . 10
>> 10.1 Relationships . . . 11
>> 10.2 Dispersed and Coherent Objects . . . 11
>> 10.3 Location . . . 12
> 11 CONCLUSIONS . . . 13
> 12 REFERENCES . . . 13
State is needed information which has to be memorized because it can't be deduced from other known information. But it's not uniquely determined. If you remember the radius of a circle, you can figure out its diameter; if you remember its diameter, you can figure out its radius. And you might happen to remember both, though you don't need to.
It's analogous to the proposition in logic that a set of axioms does not always have a unique subset of independent axioms.
Attributes and relationships are constructs intended to specify the state of the objects in an object system, based on the unfounded assumption that such state is uniquely specifiable. In fact, such specifications violate the encapsulation boundary by describing a particular implementation of object state.
The language syntax for retrieving or updating computed information need be no different from the syntax for retrieving or updating memorized information, giving implementations the freedom to choose which should be computed and which should be memorized. Forcing attributes and relationships into special syntax robs implementers of this freedom, binding users to specific implementations.
This paper develops a model of object state purely in terms of operations associated with object interfaces. It is all carefully separated from any direct reference to stored data, respecting the object-oriented encapsulation principle of hiding the implementation.
Taking two fundamental tenets of object orientation to their logical conclusion yields a surprise. One tenet is that objects consist of behavior and state. The other tenet calls for a clean separation between interface specification and internal implementation. The surprise is that we then can't always distinguish between behavior and state.
This is much like the duality we've slowly learned to accept in physics between energy and matter, particle and wave. It is hard to accept, violating as it does the traditional legacy of programming languages: code is code and data is data. In object orientation, information and processing are closer than two sides of the same coin.
Consider circles. Either the radius or diameter of a circular object could be stored, with the other being computed. It's easy enough to implement a bit of code that will store a new value of one if a user updates the other. Some implementations might even store both. A given application should be able to work interchangeably with all such implementations. From the viewpoint of a user (interactive person or application program), the significant interface specifications are that the radius and diameter of a circle are numeric values, both can be retrieved and updated, and the diameter is always twice the radius. Which is stored or computed doesn't matter.
The examples aren't always so trivial. In a publishing application, the length of some articles might be a simple property assigned or modified by the layout editor. For others, the length might be computed from the text, font size, and illustrations. In some cases, assigning a length to an article might trigger a complex procedure which truncates or pads text, and adjusts fonts, sizes, headings, and illustrations to fit. Again, an application should be able to deal with such articles interchangeably, setting and retrieving their lengths in a uniform way, independent of underlying implementations.
So which is behavior and which is state? How do we classify these diameters, radii and lengths? Certainly not by the traditional criterion of stored vs. computed information.
What is the essential phenomenon here? Update, or side effects. ("Side effects" here means intentional updates rather than unintended consequences.) Broadly speaking, the effect of one operation (updating a diameter, radius, or length) is perceived later in the altered behaviors of other operations (those which retrieve the diameter, radius, or length, or yet other operations dependent on these). Some interactions are more complex than a simple read/write sequence, such as the interactions of Push and Pop operations on a stack. The principle is the same: the results of some operations are determined by the remembered effects of prior operations.
These are the semantic behaviors as externally perceived by a user. Clearly something has to be remembered internally from one operation to the other, but we can't say exactly what. The details of what is recorded in memory can vary from one implementation to another.
Not only do behavior and state blur together; the states of several objects sometimes intermingle as well. The distance between a point and a line, or between any two spatial objects, characterizes the state of both. The fact that an object is on a stack says something about the object as well as about the stack.
Thus we will start by describing the state of an "object system", then perhaps later focus on the state of individual objects.
An object system provides a system interface at which users can request the execution of a definite (though time-varying) set of operations applied to a definite (though time-varying) set of operand objects known to the system. This population of objects can be thought of as the result of an imaginary query requesting the system to enumerate all known objects, though in reality such a query is not likely to be supported; in any case, the result is likely to be infinite. The population can also be thought of as the set of all objects which could legally occur as the operands of valid requests to the system at a given point in time.
The state of an object system can only be known by the results of requested operations. Certain kinds of operations are not useful in characterizing state:
What remains is a set of state-sensitive operations, which may return different results for the same operands at different times, and which are considered relevant to the characterization of state. By definition, a change in the result of a state-sensitive operation for a given operand implies a change in state.
An operation g is state-changing (i.e., it has side effects) if there is some state-sensitive operation f such that an execution of g alters the result of f(x) for some operand x. We don't dwell on how the causality is established. We simply postulate that it is somehow known that g causes the result of f(x) to change. f and g could be the same operation: a Pop on a stack can alter the results of the next Pop on the same stack.
A state-changing operation might alter the results of many state-sensitive operations, and many state-changing operations might alter the results of the same state-sensitive operation.
An operation g directly updates a state-sensitive operation f if executing g(x,y) causes f(x) to subsequently return y, for all x and y (subject to type constraints, of course). g is then an updater of f, and we can postulate a system function such that Updater(f)=g. We then have
Updater(f)(x,y) => f(x)=y,
i.e., f(x) will return y after Updater(f)(x,y) is executed.
Such updaters can be manifest in a variety of syntactic forms, to be discussed later in connection with attributes [Section 6.2].
Time-dependent operations can be modeled by defining the clock such that each tick is an execution of an updating operation. It is the direct updater for an operation which returns the time.
We might naturally try to define state as the values of a minimal set of state-sensitive operations which are in some sense independent of each other, but such a minimum set is not in general unique. Minimal independent sets could contain either one of the operations returning the diameter or radius of a circle. Thus one of our conclusions is that state cannot be precisely defined in unique terms independent of implementation considerations. At best we might be able to achieve an equivalence class of minimum sets. This conclusion applies to individual objects as well as object systems.
What is an attribute? That question is at least as old as the relational and entity-relationship models [1]. One answer: anything a schema definer declares to be an attribute. That facetious answer may be the best we have.
Certain operations such as Move and Copy need to know the scope of data required to re-create the known information about an object. Attributes (or frame slots) reflect an attempt to specify that scope. The approach is rooted in the record-based heritage of relational and entity-relationship models, and has difficulty evolving beyond those basic instincts. The heritage brings with it a legacy of ill-defined concepts.
Attributes also represent an attempt to segregate state-related operations from other operations. Thus there are at least the following problems:
If Sam's age is 40, then "attribute" might refer to the notion of age, or to Sam's age, or to 40, or perhaps something else. We will use the term in the first sense, analogous to the notion of an instance variable: Age is an attribute, which can have different values for different operands. The other senses will be discussed later [Section 8].
Further definition rests on an underlying bed of quicksand, depending on unresolved issues regarding the subclassification of objects. For our present purposes we will use the undefined terms "non-literal" (e.g., an employee), "literal" (e.g., a number), and "aggregate" (e.g., a set).
Perhaps the most common notion of "attribute" corresponds to a side-effect-free (non-updating) operation which takes a single non-literal as operand and returns a single literal result. Variant definitions would allow it to take other kinds of operands (e.g., attributes of integers, or of sets) or return other kinds of results (e.g., non-literals, or sets).
Attributes usually correspond to operations which have direct updaters. The notion of a "non-updatable" attribute seems truly anomalous, indistinguishable in purpose from an ordinary side-effect-free operation which returns a result.
It is possible to manage attributes with the same syntactic forms as updatable operations. One such syntax mimics the assignment of values to variables, justifiable on the grounds that an operation like Radius can be considered an instance variable, having different values for different argument instances. Just as the value of a variable can be retrieved and set by the forms x and x<-10, so the value of a circle's radius can be retrieved and set by Radius(c) and Radius(c)<-10.
Syntactic variants of this generalized assignment f(x)<-y include such forms as Set f(x)=y, Set(f(x),y), and Set(f,x,y); "Assign" may occur in place of "Set".
For set- or bag-valued functions it is convenient to define f(x)+=y and f(x)-=y as assigning to f(x) a bag containing one more or one less occurrence of y than the prior value of f(x).
Such updatability of an operation can be established when its behavior is specified, sometimes requiring specification of a procedure to be executed when the update is requested [6][7][9].
Another syntactic form allows the specification of a companion updater operation g when defining a given operation f, essentially declaring Updater(f)<-g. Yet another variant does away with explicit naming, allowing Set(f) to return the companion updater. Set(f)(x,y) would be a syntax analogous to the Updater function mentioned earlier [Section 4].
Some languages use the attribute construct as part of a rigid naming convention that relates an operation to its companion updater. An attribute named f implicitly defines the existence of a pair of operations Get_f and Set_f.
One convention differentiates retrieval syntax for operations and attributes, using Radius(c) if Radius is an operation but Get_Radius(c) or even Get(Radius,c) if Radius is an attribute.
In some models, state is reflected in relationships as well as attributes (we'll explore the distinction between these two shortly). As with attributes, relationships can be described in terms of sets of operations. The difference is that there typically are several different accessor (retrieval) operations for a relationship. For the relationship between students and courses, some or all of the following might be provided in a family of accessors:
Courses(s) returns the set of courses taken by student s,
Students(c) returns the set of students taking course c,
StudCoursePred(s,c) returns True if and only if s is taking c,
StudCourseList() returns all pairs <s,c> such that StudCoursePred(s,c) is true.
Two of these, Courses and Students, have a sense of direction, while the other two reflect the relationship in an undirected way.
Any of the accessors might have a companion updater operation. The essential character of a relationship is that any update which changes the results of an accessor operation changes the results of all accessors in the family. For example, executing any one of the following behaves as though they had all been executed:
Courses(s)+=c,
Students(c)+=s,
StudCoursePred(s,c)<-True,
StudCourseList()+=<s,c>.
An operation such as Register(Student,Course) could equivalently be defined in terms of any one of those.
There are various implementation strategies for keeping such accessors synchronized. One approach is to store them all overlaid in the same place, much like a relational implementation providing shared object state, avoiding redundancy. Another approach is to keep separately stored operations synchronized through some form of replica management. A third approach would store one of these with one of the objects, with the others being defined as queries over that one stored version. As usual, all such implementations should be accessible from the same object interfaces.
How are such operations specified in object definitions? There is no general convention for all operations in such a family. An "inverse" convention is sometimes used for the directed operations:
Interface Student
Courses ->{Course}
...Interface Course
Students -> {Student} inverse of Courses
...
Of course, this is not a true mathematical inverse. If
Courses(s1)={c1,..,cn},
then the mathematical inverse is an operation which takes the set {c1,..,cn} as argument and returns the student s1 as the result. What Students does is take a single course and return a set of students. The notion of inverse here means that s occurs in Students(c) if and only if c occurs in Courses(s).
This approach extends naturally to n-ary relationships [2]. The accessor family for an n-ary relationship could include:
The "inverse" declaration generalizes to an "in family" declaration, e.g.,
f(x,y)=<z,w>,
g(x,w)=<y,z> in family of f(x,y),
meaning that <y,z> occurs in the result of g(x,w) if and only if <z,w> occurs in the result of f(x,y).
But where is "the relationship" in all of this as a single construct? That's a hard question. We may have a single concept in mind, but it is manifest in the object model as a family of operations. Even if we introduce a single named construct to correspond to the relationship itself, such as the family as a whole, there still has to be some mechanism or convention to identify the operations in the family. Alternatively, instead of introducing a new construct, a canonical member of the family could be considered to "represent" the relationship, perhaps either the predicate (StudCoursePred) or the generator (StudCourseList). This is difficult in classical object models [4][8], since these operations do not associate naturally with any single object.
And what exactly is the difference between an attribute and a relationship? It's hard to be exact without exact definitions. In many models, relationships may only associate non-literals. Some models only support binary relationships, others allow n-aries. An attribute is then like a binary relationship, except that
A stable operation returns the same result on successive invocations with the same operand if there are no intervening requests. Any stable operation seems to clearly imply some sort of relationship between the operand and result, or at least an attribute of the operand.
One reason often used to motivate attributes and relationships is that they themselves can have attributes or be involved in relationships. Here we are talking about instances, namely an attribute of a particular object, or a relationship between a particular pair of objects. For example:
Property is a collective term for attributes and relationships. One way to deal with such properties of properties is to develop some notion of property instances to serve as the "subjects" of such properties. For example, a grade could be an attribute of an object representing the relationship between one student and one course. Unfortunately, there are too many candidates for this concept. For the relationship between students and courses, all of the following might be "objects" of interest, with properties of their own:
Some problems:
Single-valued attributes are a relatively simple case, since there is an obvious candidate for the property instance, and there is a natural traversal direction for identifying it. For birthdays, the pair <Sam,Birthday> would suffice to identify a plausible "attribute instance", which might in turn have attributes indicating when it was recorded, or how it was determined.
This notion of attribute instance can be generalized to any operation with a single argument, where the "operation instance" is the operation together with a particular operand, e.g., Sam.Birthday in classical notation. In this sense, an operation instance coincides with the notion of a slot, or an instance variable.
However, this approach doesn't generalize well to multi-valued attributes, or to relationships. This line of development needs further investigation.
Another approach to a slightly different concept is to develop the notion of the extension of a (stable) operation, modeled as a set of (ephemeral) objects uniquely identified by the triplet <operation, argument, result>. These objects could then participate in other attributes or relationships.
Another approach to properties of properties is to "flatten" them to n-ary relationships, so that the date a birthday was recorded becomes a ternary relationship between the person, the birthday, and the recording date. Again, there are too many possible configurations. How the birthday was determined might be another ternary relationship between the person, the birthday, and a source, or it might all be consolidated into one 4-way relationship between person, birthday, recording date, and source. There are also problems of consistency and referential integrity. The underlying birthday attribute still exists in its own right, and the other ternary or quaternary relationships should consistently reflect the same birthday, even if updated. There are also modeling issues: some models only allow relationships among created objects, disallowing relationships involving such things as dates. This line of development also needs further investigation.
State is sometimes characterized in terms of data stored in variables. Variables can be described very nicely as operations. A global variable v is essentially a stable state-sensitive operation with no arguments, whose updater g is a generalized assignment operation:
g(v,,z) => v=z.
g(v,,z) can also be written Assign(v,z) or v<-z.
An expression like f(v) is comparable to composition of operations f(g(c)). The operation evaluator Eval applies to v just as to f(v):
Eval(f(v)) = Eval(f(Eval(v))).
Stable state-sensitive operations of one argument are like instance variables. This is particularly apparent if we revert to classical notation, writing x.foo instead of foo(x). At this point operations, attributes, and variables seem to have much in common.
A procedure variable can behave like multiple variables, having different values and even different declarations in different environments. Programming languages provide various scoping mechanisms, but the general notion is that a new environment is established on entry to a procedure, and the previous environment is restored on exit. Variables explicitly declared in the procedure behave like newly defined variables in the environment. Other variables inherit their definitions from prior environments.
As a first approximation, this behavior can be described by treating the environment as an implicit parameter: evaluating x really evaluates x(E), where E is the current environment. Binding establishes a new value for a given environment: x(E)<-c. Default binding reverts to values in the prior environment: x(E2)<-x(E1).
That scenario doesn't account for a variable having different declarations in different environments. The same variable can be declared an integer in one procedure and an array of character strings in another. This can be modeled in another approach exploiting inheritance and overloaded operators.
A sequence (tree?) of environments can be defined (statically or dynamically) to behave much like an inheritance graph among type interfaces. Some of these environments have an explicit declaration for a given variable, others don't. The declarations come from the procedure associated with the particular environment. Each environment with an explicit declaration for x is, in effect, providing a new definition of the overloaded operation x, with its own type declaration and result value. A reference to a variable is bound in the "nearest" (most recent) environment where it has an explicit definition.
In a loose sense, multiple declarations of a variable correspond to multiple definitions of an operation. Reference to a variable requires binding to the appropriate declaration, much like binding of an overloaded operation [service request, in terms of the other paper]. The main difference is that, with dynamic scoping, each entry to such a procedure effectively provides a new definition.
Interfaces encapsulate objects, hiding their implementations from clients. There are several interface notions in object systems:
Once a client has issued a request to an object system interface, he shouldn't know about or be dependent on how that request is implemented. Designers and developers of objects and object systems may have a need to know, but clients don't. All they care about are the results of the requests, which should be describable in implementation-independent terms.
Object specifications include implementations as well as interfaces, but independently, allowing various and changeable implementations of the same interface.
The operations in a family suggest alternative implementations. One or more of them might be mapped directly to stored data. If several, then there is system-managed redundancy, which is the intent of an "inverse" declaration. Frame- or slot-oriented object models assume that the directed accessors in a family map to stored data. Models resting on relational implementations tend to store the undirected operations (generator or predicate). Of course, none of them needs to be stored: they could all be derived from some other operations.
Various subsets of the family might be made available at client interfaces. Any of them might be updatable, with a corresponding propagation algebra. Some members might be available in different syntaxes, e.g., as queries. With or without syntactic differences, some might be implemented via associative retrieval, i.e., as queries. Different members might perform at different speeds, depending on implementations (queries generally take longer than slot references, but indexing or inverted files could make a difference). The same operation might perform at different speeds at different times, due to changes in implementation.
Some models presume that objects are implemented as disjoint chunks of data, "disjoint" meaning that a data item belongs exclusively to one object and cannot be shared among objects, and "chunk" meaning that all of an object's data occupies one contiguous span of storage space. Disjointness requires, for example, that the registration of a student in a course cannot be recorded in a data item jointly owned by the student and course objects. The data item must be exclusively owned by one or the other; it may even be maintained redundantly, with each object exclusively owning its own copy - but it cannot be shared. Contiguity then requires that all data owned by a given student be bundled together.
There may be good reason to impose such limitations on certain implementations, but they should have no impact on object semantics as perceived by clients across the encapsulation interface. Unfortunately, there often is an impact across this boundary.
Exclusive ownership of data exposes itself in classical object models [4][8] in the form of exclusive ownership of operations by interfaces. That is, an operation is defined as part of one type interface, and cannot be shared among many. An operation which registers a student in a course must be defined as belonging to either the Student interface or the Course interface. The syntax of the classical model reinforces this exclusion, distinguishing the "owner" as being the target of the request. Thus, depending on which interface owns the operation, the client must request the registration of student s in course c either as
s.Register(c)
or
c.Register(s).
Of course, operations having similar effects can be redundantly defined in both interfaces, but the client is then faced with a choice between two operations, rather than a single jointly-owned operation.
Generalized models, in contrast, support joint ownership of operations. The syntax does not distinguish a target operand. The client may write
Register(s,c)
to invoke an operation jointly owned by the Student and Course interfaces.
In principle, one style of interface could be mapped into the other style of implementation. Jointly owned operations could be implemented in exclusively owned data, and vice versa. The inclination seems to be, however, to maintain the same mind set with regard to joint or exclusive ownership on both sides of the interface. (We might observe that implementations of object systems often convert classical requests into generalized form before invoking methods.)
The contiguity assumption exposes itself by constraining change and extensibility. The underlying premise is that all the space needed to store an object's data is allocated in a contiguous chunk when the object is created. This makes it difficult to extend the object's data storage requirements, either by adding new types to the object (making a person an employee) or by adding operations to a type.
The contiguity assumption also confounds certain database implementations. Historically, databases have discovered that they can operate much more efficiently by keeping similar data together, e.g., data about teachers in one place and data about students in another. Having the same object be both a student and a teacher makes it harder to keep all its data in one place.
As discovered in database technology, there is no real need to keep all the data about one object together in one place. The object system has no difficulty in tracking down different facts (or other services) for an object in different places. However, contiguity continues to be an underlying assumption in object models evolving primarily from programming languages.
Objects whose data is all in one contiguous chunk of storage are "coherent"; the others are "dispersed" [5].
Dispersing an object's data among, for example, different files or different tables in a database is dispersion "in the small".
Dispersion is possible on a larger scale as well, on the order of different nodes in a network. This is usually the order of magnitude involved when clients speak of moving objects, or object systems speak of having to "find" an object in order to know where to route a request. Dispersed objects could have their operations and underlying data scattered over multiple locations. The routing of a request would depend not only on the identity of the object, but on the nature of the requested service as well. An unqualified Move operation does not make sense for such objects, since they do not have a singular sense of location. It doesn't make sense to speak of where the object is in the singular.
Different implementations might clump a dispersed object into different coherent sub-units. This may be true of different instances of a given type, or of the same instance if its implementation changes with time. Clients should be impervious to such differences.
Of course, it is sometimes semantically meaningful to clients to know that certain objects are coherent, and it does make sense to expose a class of fully coherent objects. But it is unnecessarily restrictive to assume that all objects are always coherent.
State is not uniquely determined. We know that state and behavior both exist, yet we can't quite tell them apart with a scientist's precision. It's eerily reminiscent of the duality between matter and energy, between light as particles and as waves, in modern physics [3].
From the client's perspective from outside the interfaces of objects, we formulate everything we need to know in terms of operations. While we recognize that some sort of data has to be stored, we can't specify exactly what it is. In fact, many possible configurations will satisfactorily support the same desired behavior. That is very much the concern of the designers and implementers of objects and object systems, but not of object clients.
Object state can be characterized in terms of stable state-sensitive operations (which correspond to the attribute concept), coupled with state- changing operations which alter their future results (corresponding to the update concept). Relationships can be described in terms of families of state-sensitive operations which are updated synchronously with each other.
In general, there is no unique minimal set of state-sensitive operations which define object state. This corresponds to the possibility of multiple implementations.
Languages (models) which expose the structure of stored information in object interfaces are not properly observing the separation of interface an implementation, and are limiting interchangeability and reusability. This includes languages which perpetuate the arbitrary distinction between operations and attributes, as well as database languages which perpetuate the underlying data structure as part of object interface specifications.