Multi-Faceted Object Systems and Models
William Kent
Database Technology Department
Hewlett-Packard Laboratories
Palo Alto, California
April, 1994
> ***PROLOGUE*** . . . 7
> 1 OBJECTIVES AND STATUS . . . 7
> 2 ORGANIZING PRINCIPLES . . . 7
>> 2.1 Isolation of Object Users From Object
Implementation . . . 7
>> 2.2 Behavioral Criteria . . . 8
>> 2.3 Fundamental Concepts . . . 8
>>> 2.3.1 Object Systems . . . 8
>>> 2.3.2 User Perspective . . . 9
>>> 2.3.3 Implementation Perspective . . . 10
> ***OBJECT SYSTEMS*** . . . 10
> 3 COMPUTATIONAL SYSTEMS . . . 10
>> 3.1 Illusion and Metaphor . . . 11
>> 3.2 Interfaces and Symbols . . . 11
>> 3.3 Requests and Expressions . . . 12
>> 3.4 Operator Expressions . . . 13
>> 3.5 What Symbols Mean . . . 14
> 4 INTRODUCTION TO OBJECT SYSTEMS . . . 15
>> 4.1 The Computational Context . . . 15
>>> 4.1.1 Interfaces to a Black Box . . . 15
>>> 4.1.2 Symbols . . . 16
>> 4.1 Object Systems . . . 17
>> 4.3 Object System Interfaces . . . 17
>> 4.4 Facets and Spheres . . . 18
> ***A GENERAL MODEL: USER PERSPECTIVE*** . . . 19
> 5 INTRODUCTION . . . 19
> 6 REQUESTS . . . 20
>> 6.1 Results and Conditions . . . 20
>> 6.2 Expressions . . . 21
>> 6.3 Performers of Requests . . . 22
>> 6.4 Update and State . . . 22
>>> 6.4.1 Updating Variables . . . 23
>>> 6.4.2 Updating Operations . . . 23
>>> 6.4.3 Changeable, Updatable and Recorded
Properties, and State . . . 23
> 7 OBJECT EXISTENCE AND IDENTITY . . . 24
>> 7.1 "Exists" vs. "Known" .
. . 24
>> 7.2 How Objects Become Known . . . 25
>> 7.3 Equality Axioms . . . 25
>> 7.4 Creating and Initializing Objects . . . 26
> 8 INFORMATION FOR REQUEST PLANNING . . . 26
> 9 TYPES . . . 27
>> 9.1 The Nature and Role of Types . . . 27
>> 9.2 Non-Materialized and Materialized Types . .
. 28
>>> 9.2.1 Materialized Types for Numbers . .
. 28
>>> 9.2.2 Ideal and Effective Types . . . 29
>>>> 9.2.2.1 Ideal Non-Materialized
Numeric Types . . . 30
>>>> 9.2.2.2 Ideal Materialized Numeric
Types . . . 30
>>>> 9.2.2.3 Effective Materialized
Numeric Types . . . 30
>>>> 9.2.2.4 Effective Non-Materialized
Numeric Types . . . 30
> 10 OPERATIONS . . . 32
>> 10.1 Specific and Generic Operations . . . 32
>> 10.2 Specific Operations . . . 32
>>> 10.2.1 Signatures . . . 33
>>> 10.2.2 Behavior Specifications . . . 33
>>>> 10.2.2.1 Behavior vs.
Implementation . . . 33
>>>> 10.2.2.2 Update Specifications . .
. 34
>> 10.3 Generic Operations and Inheritance . . .
35
>>> 10.3.1 Overview . . . 35
>>> 10.3.2 Inheritance . . . 36
>>> 10.3.3 Default Behavior of Generic
Operations . . . 36
>>> 10.3.4 Defined Behaviors . . . 37
>> 10.4 Additional Behaviors . . . 37
>>> 10.4.1 Casting (Substitutability) and
Its Uses . . . 38
>>>> 10.4.1.1 Type Casting . . . 38
>>>> 10.4.1.2 Intensional Aggregates .
. . 38
>>>> 10.4.1.3 Type Extents . . . 38
>>>> 10.4.1.4 Type Substitutability . .
. 38
>>> 10.4.2 Extending Non-Aggregate
Operations to Aggregate Operations . . . 38
>> 10.5 The Association Between Types and
Operations . . . 39
>> 10.6 Operations Involving Types and Operations
. . . 39
>>> 10.6.1 Populating Types: Asserted and
Derived Types . . . 39
>>> 10.6.2 Disjoint Types . . . 40
> 11 AGGREGATES . . . 41
>> 11.1 Unstructured Aggregates: Bags and Sets .
. . 41
>>> 11.1.1 Instances . . . 41
>>> 11.1.2 Instance Designators . . . 42
>>> 11.1.3 Types and Type Designators . . .
43
>> 11.2 Indexed Aggregates . . . 44
>>> 11.2.1 Instances . . . 44
>>> 11.2.2 Instance Designators . . . 45
>>>> 11.2.2.1 Sequence Designator . . .
45
>>>> 11.2.2.2 Compact Sequence
Designator . . . 46
>>> 11.2.3 Types and Type Designators . . .
46
>>>> 11.2.3.1 Sequence and Tuple Types
. . . 46
>> 11.3 Empty Aggregates . . . 47
>> 11.4 Type Constraints on Aggregates . . . 47
>> 11.5 Aggregate Subtypes . . . 48
>> 11.6 Arithmetic Semantics of Aggregate
Operations . . . 48
>> 11.7 Extensional and Intensional Aggregates .
. . 49
> 12 QUERY . . . 50
>> 12.1 Arithmetic Semantics . . . 51
>> 12.2 Basic Form . . . 51
>> 12.3 Group-By . . . 52
>> 12.4 Query Transformations . . . 54
> 13 OTHER INTERESTING OBJECTS . . . 55
>> 13.1 Carriers and Cargos . . . 55
>> 13.2 User-Defined Literals . . . 55
>>> 13.2.1 Subtypes of Basic Literals . . .
56
>> 13.3 Factoids . . . 56
>> 13.4 Objects With Content . . . 57
>> 13.5 Objects With Location . . . 57
>> 13.6 Measured Quantities . . . 57
>>> 13.6.1 Relevance of Non-Materialized and
Materialized Types . . . 58
>>> 13.6.2 Use and Mention of Quantity
Designators . . . 58
>>> 13.6.3 An Interesting Analogy . . . 59
>>>> 13.6.3.1 Single Designation . . .
59
>>>> 13.6.3.2 Multiple Designations . .
. 60
>>>> 13.6.3.3 Conversions . . . 61
>>> 13.6.4 Another Analogy . . . 61
>> 13.7 Geometric Constructs . . . 62
>>> 13.7.1 Geometric Points . . . 62
>>> 13.7.2 Plane Figures . . . 63
> ***A GENERAL MODEL: IMPLEMENTATION PERSPECTIVE*** . .
. 63
> 14 INTRODUCTION . . . 63
> 15 CLASSES . . . 63
> 16 CHOOSING PERFORMERS . . . 64
> ***OTHER MODELS*** . . . 65
> 17 MESSAGING MODELS . . . 65
> 18 LINK/INTERACTION MODELS . . . 65
> 19 OSQL . . . 65
>> 19.1 Semantics . . . 65
>>> 19.1.1 Aggregates . . . 65
>>> 19.1.2 Query . . . 66
> 20 BASIC RELATIONAL MODEL . . . 66
>> 20.1 Semantics . . . 66
>>> 20.1.1 Tuple Tables . . . 66
>>> 20.1.2 Update . . . 67
>>> 20.1.3 Query . . . 67
>> 20.2 SQL Syntax . . . 68
> 21 OBJECT-ORIENTED RELATIONAL MODEL . . . 68
>> 21.1 Non-Tuple Tables . . . 69
>> 21.2 Comparison of Tuple- and Non-Tuple Tables
. . . 69
>> 21.3 Managing the Extent (Population) of a
Type: Table of ALL . . . 70
>> 21.4 SELECT * . . . 70
> ***MODEL DIFFERENCES*** . . . 71
> 22 DIMENSIONS OF DIFFERENCE . . . 71
>> 22.1 Performer and Participant Models . . . 71
>> 22.2 Addressing and Associative Models . . .
74
>>> 22.2.1 Objects in Space . . . 74
>> 22.3 Other Significant Differences . . . 75
> 23 WHY THE DIFFERENCES? . . . 76
> ***MODEL INTEROPERATION*** . . . 77
> 24 REQUIREMENTS . . . 77
>> 24.1 Cascading Interfaces . . . 77
>> 24.2 Dimensions of Interoperation . . . 79
> 25 EQUIVALENT FORMS . . . 80
>> 25.1 Messaging and Functional Syntax . . . 80
>> 25.2 Multiple Arguments vs. Sequences of
Arguments . . . 80
>> 25.3 Curried Equivalence . . . 80
>>> 25.3.1 Description . . . 80
>>> 25.3.2 Examples . . . 81
>>>> 25.3.2.1 Typing Operations . . .
81
>>>> 25.3.2.2 Attributes . . . 81
>>>> 25.3.2.3 Units of Measure and Data
Types . . . 81
>>>> 25.3.2.4 Schema Mismatch . . . 81
>>>> 25.3.2.5 A Universal Relation and
the Apply Operation . . . 81
>> 25.4 (Relational) Operation Families . . . 82
>>> 25.4.1 Description . . . 82
>>> 25.4.2 Uses . . . 82
>> 25.5 Extended Operation Families . . . 83
>> 25.6 Structural Coercions . . . 83
> 26 MULTI-FACETED OBJECT SYSTEMS . . . 83
>> 26.1 Facets, Spheres, and Environments . . .
83
>> 26.2 Interoperation of Diverse Models . . . 84
> ***DETAILS*** . . . 84
> 27 EXPRESSIONS . . . 84
>> 27.1 Variables . . . 84
>>> 27.1.1 Environments and Binding . . . 84
>>> 27.1.2 Declaration vs. Binding . . . 85
>>> 27.1.3 Comparison With Argumentless
Operations . . . 85
>> 27.2 Expression Evaluation and Operator
Application . . . 86
>>> 27.2.1 Overview . . . 86
>>> 27.2.2 Evaluate . . . 86
>>> 27.2.3 Apply . . . 87
> 28 SOME USEFUL OPERATIONS . . . 87
>> 28.1 Equality and Null . . . 88
>> 28.2 Membership and Inclusion . . . 88
>> 28.3 Profiles and Predicates . . . 88
>> 28.4 Logical Operations . . . 88
>> 28.5 Operation Composition . . . 89
>> 28.6 Quoting . . . 89
>> 28.7 Bag Operations . . . 89
>>> 28.7.1 Duplicate Elimination . . . 90
>>> 28.7.2 Union and Difference . . . 90
>>> 28.7.3 Cross-Products . . . 91
>>> 28.7.4 Bag Processors . . . 91
>> 28.8 Other Relational Operations . . . 93
>>> 28.8.1 Project . . . 93
>>> 28.8.2 Restrict (Select) . . . 93
>>> 28.8.3 Joins . . . 94
> 29 SOME USEFUL OBJECTS . . . 95
>> 29.1 Constants, Values, and Variables . . . 95
>> 29.2 Atomic Objects . . . 95
>> 29.3 Basic (Literal) Data Types . . . 95
>> 29.4 Null . . . 95
>> 29.5 Indexed Aggregates . . . 97
>>> 29.5.1 Compact Aggregate . . . 97
>>> 29.5.2 Sequences/Lists/Tuples . . . 97
>>> 29.5.3 0-Sequence . . . 98
>>> 29.5.4 Record . . . 98
>>> 29.5.5 Array . . . 98
>>> 29.5.6 Regular Bag . . . 98
> 30 SPECIFIED BEHAVIORS FOR GENERIC OPERATIONS . . .
98
>> 30.1 Application to Multidatabase Systems . .
. 101
>>> 30.1.1 Operation Merging for
Inconsistent Data . . . 101
>>> 30.1.2 Merging Equivalent Objects . . .
103
> 31 REFERENCES . . . 104
***PROLOGUE***
This document:
- Pursues the Holy Grail of a single unified object model, or at least a single unified
mechanism for describing object models.
- Describes some specific object models in these terms.
- Characterizes differences in object models.
- Describes a framework for model interoperation.
This draft is very much a skeleton of work in progress. Parts of it are fairly
complete, parts are totally missing. Some of the missing material simply needs to be
written, and some still requires a bit of invention and may even remain a speculative
sketch. There are undoubtedly some inconsistencies. Readability still needs to be
substantially improved, perhaps by changing the order of presentation and adding more
motivational and illustrative material. The overall structure is itself negotiable.
The document presents a hopefully coherent set of semantic concepts. Notably absent at
the moment is material on why these ideas are useful, how to realize them in practical
languages and systems, and how they relate to current work. Many of the ideas presented
here are obviously derived from other sources, though not yet so identified. All this work
also remains to be done.
The problem of consistent terminology is worse in object orientation than in most other
fields, and there are efforts under to way to correct this. If consistent terminology
emerges in time, we will adopt it in this document. In the meantime, the best we can do is
define our terms carefully here and try to use them consistently. Most readers will not be
satisfied with all of our terminology. Be patient, and be warned: some terms may not mean
what you think they do. Since nobody wants to read a glossary at the outset (and we
haven't yet extracted a consolidated glossary anyhow), you will probably be surprised by
some of the definitions you encounter after the terms have been used. Sorry about that.
This document rests on these organizing principles:
- Isolation of object users from object implementation.
- Behavioral criteria.
- Top-down development from fundamental concepts.
Perhaps the central organizing principle of object orientation, and this document, is
the isolation of object users from object implementation. Applications which use objects
in this fashion can operate with different and changing implementations, making such
applications more portable and more reusable.
Underlying this is the perception of an object as something which gets used for some
purpose, rather than as an active thing which does things in a system. This latter view
reduces focus on the user perspective, and diminishes the role of the infrastructure. This
difference may in itself account for pervasive differences in object models.
The implementation constructs which are hidden from users behind an object system
interface include program code for executing requests, query processing and optimization,
data structures, data placement and clustering, and pointers.
Much of the work in object orientation focuses on implementation aspects (complex data
structures, messaging and dispatching paradigms, pointer management, garbage collection,
query processing, etc.); it might be instructive for the reader to assess the extent to
which this is so. This also raises an interesting question, couched in terms we won't
define further: if a system appears to be object-oriented on the user side but not on the
implementation side, or vice versa, is the system object-oriented?
The present document, in contrast, focuses primarily on the user side, taking special
care that implementation considerations do not intrude.
Distinctions are made in the model only if they make a difference in the way something
works. Constructs are not included, for example, simply because they reflect the way
people might think about things. Thus, if one construct is different from another, then
there must be some meaningful operation which behaves differently for the two.
The material presented here is developed top-down from a set of fundamental concepts,
which are summarized below and elaborated in the rest of the document.
A computational system is a symbol processor with interfaces [Section 4.1].
Everything can ultimately be explained in terms of symbol processing.
Objects are managed by object systems [Section 4.1].
Object systems provide an infrastructure which provides such services as routing
requests from requestors to performers, returning results, and resolving generic requests.
Models vary in the extent of services provided by this infrastructure.
Object systems provide interfaces which isolate object users from implementations [Section 4.3].
Object model features can thus be partitioned into those relating to users and those
relating to implementation. This document is biased toward a focus on the user side.
From the user perspective, everything that happens in an object system is the
consequence of a request [Section 6].
We take a request-centered approach. Everything that happens in the object system is
the consequence of a user making a request to the object system. The user might be a
person or a program, or some other active agent such as a sensing device. The request
might be initiated spontaneously from outside the object system, it might arise as the
consequence of performing another request, or it might be triggered by other mechanisms
such as a monitor or other event/condition/action mechanism.
Things we therefore have to describe include:
How requests work.
What facilities are provided to allow requests to achieve the user's goals.
How the user figures out what facilities are available so that he can formulate the
appropriate requests. That's what a schema is for, supplementing a basic understanding of
how the system works.
From the user perspective, it doesn't matter who performs a requested service [Section 6.3].
The essential effect of update is to alter the results of future requests [Section 6.4].
The concept of state is not uniquely defined from the user perspective [Section 6.4.3].
Objects "exist" so long as they are known to an object system [Section 7.1].
If an object system can provide the date on which a certain file was deleted, then that
file object still exists as far as the object system is concerned. Certain operations may
no longer be supported, such as modifying or displaying the contents of the file, and the
file may no longer be present in any directory, but the object system can still respond to
requests involving that file.
Similarly, if an object system can provide the date on which a certain building will be
completed, as well as its location, height, and blueprints, then the building object
exists even if construction has not yet begun.
We try to avoid dealing with "existence" in this document, and speak only of
objects being known by an object system. Operations which purport to
"create" or "destroy" objects in an object system should really be
understood as "introducing" and "erasing" objects, i.e., making them
known and unknown to the object system.
The management of object identity depends on how an object becomes known to an
object system [Section 7.2].
We thus have eternal, mortal, and ephemeral objects.
The management of object identity should be consistent with the axioms of equality [Section 7.3].
Schema constructs such as types, operation definitions, and inheritance are provided
for planning purposes, so that users can choose the appropriate requests to achieve their
intended results [Section 8].
The operation referenced in a request may be either specific or generic [Section 10.1].
There are no inheritance issues or problems for specific operations. The complexities
of inheritance and overloading arise only with generic operations.
Behavior specifications are distinct from implementation specifications [Section 10.2.2.1].
An operation might be exclusively or jointly owned [Section
10.5].
Aggregates can be described in terms of content and form [Section 11].
There's a difference between extensional and intensional aggregates [Section 11.7].
The semantics of queries should be defined in terms which do not depend on any
particular internal model of query execution [Section 12.1].
Some objects have an implicit notion of "content" [Section 13.4].
But not all. For these objects, operations such as Move, Copy, and Display are
meaningful.
Some objects have a location property [Section 13.5].
But not all. For these objects, operations such as Locate and Move are meaningful.
Null signifies nothing [Section 29.4].
Different instances of the same type may be implemented with different data
structures or methods [Section 15].
A method might be exclusively or jointly owned.
Exclusively owned methods may be thought of as being "performed" by their
owner (object).
(This section is not integrated smoothly with the subsequent material.)
I see this page on my computer screen. Is this document in the computer? If I break it
open will I find a micro-dot somewhere that I can enlarge with a magnifying glass to see
this very page? Not really. The chains of words and characters are strung out over various
segments of main memory and my hard disk, being assembled with blinding speed for display
on this screen whenever I want to see it.
Well, that's not exactly true, either. There aren't really any words or characters
inside my machine. They are all encoded in these numbingly long and unreadable strings of
ones and zeros like 110111001100111011110011... Some blindingly fast bit of software turns
those into letters and words whenever we want to see things on a screen or a printed page.
Is that the truth? Well, not exactly. There are no ones and zeros in my computer. There
are just these electrons flowing around in bits of silicon and copper, and magnetized
spots on the surface of my disk. On some other disk there are just some minuscule patches
of lightness and darkness. When these little bits of things are intense enough, they get
to be called a "1", otherwise they are a "0".
Have we reached bottom yet? Probably not. A mathematical physicist would probably say
that electrons and magnetism and light are anthropomorphized metaphors expressed in terms
we can relate to. What's "really" there are arcane behaviors of energy that
humans can't really comprehend, but only "describe" in unreadable formulas.
Ultimately what's "really" happening goes on in physical matter and energy.
That's how things are recorded in storage media, that's what flows around and gets
transformed during computation, that's what goes into a computer in terms of pushing keys,
and that's what comes out of a computer in a way that reflects light energy into our eyes
or sends sound energy to our ears so that we can read and hear it.
All our communication and computation facilities build metaphors on top of these...
My word processor behaves in such a way that I can think I am dealing with words on a
page.
A relational database system lets its users think they are dealing with rows and
columns.
A file system...
Sometimes these are piled up one on top of another.
Objects are shaped by the computational systems which manage them. A computational
system is an abstraction which presents a user interface at which users make
requests. Behind this interface lie a hidden internal processor (black
box), as well as storage, communication and networking facilities.
A computational system is a symbol processor. A symbol might be
anything that can pass across the user interface, or it might be something which can only
occur in the internal processor without passing across the user interface. For our present
purposes, it suffices to think of a symbol as a finite sequence of characters from some
underlying character set. Symbols which can pass across the interface might be
called visible, external, or language symbols. Symbols which cannot
might be called internal, hidden, or opaque symbols.
Opaque symbols might include:
- The internal bit-string representations of numbers and character strings.
- The internal representation of complex structures such as sets or arrays.
- The internal representation used to denote an object such as a person or an airplane
(i.e., an "object identifier").
- The internal representation of executable procedures.
Everything that happens in the computational system is the result of a request,
which causes a symbol to be evaluated. What does evaluation do? What can be
evaluated? How do requests happen?
Evaluation might do one or more of the following:
An error-free evaluation is one which does not yield an error condition.
In a broad sense, any symbol (external, opaque, or a mixture) can be evaluated, though
in extreme cases evaluation might yield an error condition, or it might simply return the
original symbol unchanged. Evaluation of symbols which can be recognized as operator
expressions (containing operator parts and operand parts) is quite complex, and will
be discussed shortly. Other symbols can be characterized by the results of their
error-free evaluation:
- Evaluation of a variable returns some other symbol.
- A constant is similar to a variable, except that every evaluation returns the
same symbol.
- Evaluation of a value always returns the value symbol itself. In effect, the
computational system does not "know" that the value symbol denotes anything
else. The value symbol "denotes itself".
Expressions to be evaluated might enter across the user interface in external form, or
they might be internally constructed, perhaps during the course of evaluating other
expressions. It might be useful to assume that all expressions are evaluated in an internalized
form, having the following characteristics:
- It may have been parsed in order to
- Classify symbols as described above;
- Determine it substructure if it is an operator expression (below).
- It may include opaque symbols.
(Such parsing, or internalization, might also do such things as replace constants with
their values, but we will count that as part of the evaluation process.)
The simplest operator expression can be decomposed into a pair of values
serving as the operator part and operand part, often denoted
operator(operand). The dot-notation form operand.operator is also used.
The operator part is said to be applied to the operand part. In the simplest
case, such application consists of finding the body of the operator part and
executing it with the operand part as argument to yield consequences as described above.
Expression evaluation is often more complicated for a number of reasons:
- Either part might itself be an expression, recursively requiring evaluation in its own
right.
- In the simplest of these cases, the operand or operator might be a variable or a
constant. (All languages support this for the operand, and a few allow this for the
operator as well.)
- The operand part might be an operator expression, giving rise to function
composition of the form f(g(x)).
- The operator part might also be an operator expression.
For example, there might be
different tax formulas for different states, such that TaxFormula(state) returned the
formula for the specified state. To compute the tax on a particular item purchased in that
state, one could evaluate the expression TaxFormula(state)(item).
- As a special case of this, the operand might be a complex structure of objects.
And
an important special case of this occurs when the operand is a list, giving the effect of
multiple operands. This is commonly written in the simplified form f(x,y,z).
- The operator might be overloaded (generic), requiring that a specific operation
be chosen based on the nature of the operand.
This typically arises when several
operations have the same name. There might be operations to Fire an employee, Fire a
cannon, or Fire a rule in a rule-based system. The Area formula might be different for
rectangles, squares, triangles, circles, and arbitrary polygons.
This is an extremely important aspect of object-oriented systems, but we will put it
off for a while. For now we make the simplifying assumption that operations are
uniquely named.
The most general form of an operator expression may involve a fairly complex grammar of
possibly parenthesized operators and operands, allowing such things as x+(y-z). These can
often be transformed into simple operator form in several ways, e.g.,
+(x,-(y,z)),
+(-(y,z),x).
While such expressions are important in programming language design and processing,
they don't have any special significance for object systems. We will therefore limit our
attention to the operator-operand form.
In what sense does a computational system "know" what a symbol means?
Ultimately it doesn't, with denotation being in the mind of the observer. It doesn't
"know" that Bill Clinton is the president of the United States, nor what it
means to be president. But when a well-behaved computational system is presented with a
symbol that we think denotes the appropriate question, it will respond with a symbol that
we think denotes the appropriate answer.
However, there are certain operational ways in which we might characterize the
"meaning" of a symbol in a computational system. One is in the results of
evaluating the symbol. Thus if evaluation of a symbol x results in a symbol y, we can say
that x "means" y at the time of evaluation.
Another aspect has to do with the behavior of operators applied to the symbol. The
computational system "knows" what 1 means by virtue of the results returned by
arithmetic operations applied to it.
Equality is a third manifestation, being an operator which has special significance
with regard to the "meaning" of symbols. If the symbol x is "equal" to
the symbol y, then the computational system at least appears to think they mean the same
thing, even if it doesn't understand what they mean. But what determines whether
Equal(x,y) is true? That's another complex topic.
This section briefly introduces the basic notion of object systems. We will later
return to discuss multi-faceted object systems [Section 26].
A computational system is a symbol processor with interfaces.
We should think of a computational system as a black box with interfaces [Figure 1].
The interfaces transfer information back and forth to users (output and input), and also
back and forth to persistent storage or network communication facilities. For our purposes
we distinguish three relevant viewpoints:
- The input/output interface. We often call this the end-user interface, though it is also
relevant to application designers.
- The storage and network interface. We will call people concerned with this interface
"application implementers".
- The inside of the black box, known only to system implementers.
input/output (end user) interface | | | |---------------| |XXXXXXXXXXXXXXX|
|XXXXXXXXXXXXXXX| end users<-->|XXXXXXXXXXXXXXX|<-->storage |XXXXXXXXXXXXXXX| external programs<-->|XXXXXXXXXXXXXXX|<-->network
|XXXXXXXXXXXXXXX| |XXXXXXXXXXXXXXX| |---------------| | | Figure 1.
Depending on what we have in mind as the boundaries of the black box, the input/output
interface is not limited to input/output devices in the usual sense. It may be an
interface to other programming facilities, e.g., external address spaces. Thus, for
example, certain variables may have their values maintained opaquely inside the black box,
while other variables are external. Passing values to or from such external variables
counts as crossing the input/output interface. (For this reason, I am sometimes tempted to
use the terms "import" and "export" rather than "input" and
"output", so that it doesn't necessarily connote an I/O device.) Representations
need to be specified for data maintained in such external variables, but not for variables
maintained in the black box.
Following the object-oriented principle of separating interface (semantics) from
implementation, we focus primarily on the end user's input/output interface. We talk
primarily about the language facilities provided for use at this interface, and how
information appears when it crosses this interface. We also talk about the requirements
and constraints imposed at this interface, without specifying how these are satisfied in
the other viewpoints. Thus we may talk about how information looks on input, and what is
consequently expected on output, without dictating how this appears inside the black box
or in storage. In many cases it might be most expedient to represent things in a form
similar to what was provided on input, but this is not required.
The other viewpoints do need to be considered as well. Somebody does have to decide how
things will look in storage and inside the black box. Our position is that these
specifications should be segregated in such a way that the end-user's understanding of the
system behavior does not require knowledge of these specifications. Furthermore, these
"implementation" specifications should be changeable without altering the
semantic behavior presented to the end user.
The black box is a symbolic system, which means that the only things which pass across
the interfaces are symbols. People and abstract numbers don't pass across these
interfaces; strings and pictures do. Our general definition of "symbol" is
circular, taken to mean whatever can pass across these interfaces. The exact nature
expands with advances in technology, including such things as text sequences, pictures,
sounds, electrical signals, and even actions such as mouse movements or screen touches.
For our purposes, though, it suffices to think of symbols as text sequences.
An important point: although non-symbols can't pass across the interfaces, they can
have opaque representations inside the black box. We can tell the box to create a thing
such as a person and put it into a local variable. What goes into that local variable does
not have to be known externally. Internal operations can be requested without such
knowledge, using the local variable or some other sort of expression. The thing does have
to be provided in a designed symbolic form when it is to be output (exported), either to
some output device or an external variable. There also has to be some convention for
understanding that an input symbol designates this thing. The thing also has to be put
into a designed symbolic form when it goes to storage, but that need not be a concern of
the end user.
Simple examples:
- Suppose that oid formats were not exposed, so that the black box designers were free to
redesign the formats used internally. One could create an instance of Person without being
able to see the oid, or knowing what the oid looks like. To display a person, e.g., as the
result of a query, we would have to establish some other convention for mapping the person
into a symbol, such as a name or a social security number. (See the example in Section 13.6.3.)
- For input and output of numbers, there are conventions which determine whether the
symbols are to be interpreted as decimal, binary, hexadecimal, octal, etc. However, the
numbers may be represented internally in various bit patterns which may or may not be
related to forms in which they were entered.
- Date and time are often supported with a variety of external formats used for input and
output, while the system uses some highly encoded timestamp format. (The fact that the
internal format is sometimes described in the manual is irrelevant; it shouldn't matter to
the end user.)
- By extension, we can imagine any measured quantity as being maintained internally in
some unspecified format. Representation in terms of a particular number and units only
matters to the end user during input and output. It also matters to the application
implementer when specifying how it will be maintained in storage.
Objects are managed by object systems.
Objects are managed in computational systems which we will call object systems.
Object systems are not totally transparent to the operation of objects. They provide an
infrastructure which routes requests from requestors to performers, returns results,
resolves generic requests, and may provide other services as well. Different systems and
languages vary in the services provided by the object system infrastructure.
Object systems provide interfaces which isolate object users from implementations.
Object model features can thus be partitioned into those relating to users and those
relating to implementation.
Object users are those entities which issue requests. They may be humans at an
interactive interface, or they may be programs, possibly implementing services for other
objects. They may also be mechanisms triggered by events and conditions, accounting for
active databases.
The implementation constructs which are hidden from users behind an object system
interface include program code for executing requests, query processing and optimization,
data structures, data placement and clustering, and pointers.
The distinction between services provided by a compiler, by client facilities [18], and
by the object system infrastructure [Figure 2] is a bit fuzzy. An object model might be
defined in terms of the request as constructed by a user, or in terms of the request as
provided either to a client facility or to the object system interface.
|programming language interface | | |"client services" interface | | | |
|"object management" interface | | |
|---------------|----------------------|----------------
|...............|//////////////////////|XXXXXXXXXXXXXXX|
|...............|//////////////////////|XXXXXXXXXXXXXXX| end users<-->|...............|//////////////////////|XXXXXXXXXXXXXXX|
|.. compiler ...|// client facility ///|XXXXXXXXXXXXXXX| external programs<-->|...............|//////////////////////|XXXXXXXXXXXXXXX|
|...............|//////////////////////|XXXXXXXXXXXXXXX|
|...............|//////////////////////|XXXXXXXXXXXXXXX|
|---------------|----------------------|---------------- | | | Figure 2.
The notion of a request being a "message" to a single recipient, where that
recipient is the performer of the request, really seems to be an implementation concept,
not visible to the user. The user doesn't see the difference whether a request to register
a student in a course is a message to the student or to the course, or even if it becomes
a message to a Registrar application or a DBMS which actually performs the service.
Syntactic forms such as Student.Register(Course) or Course.Register(Student) don't have
any real operational significance. (Possible exceptions: inheritance patterns, content
notions.)
This parallels the classical/generalized distinction, augmented with the possibility
that the performer might be none of the objects mentioned in the request.
An object system may provide multiple object system interfaces. One configuration
arises when the performance of a request is executed by making requests to a
"lower-level" interface containing implementation objects [Section 24.1]. Different interfaces might support
different object models, giving rise to a "multi-faceted system" [Section 26].
At a given interface, different users might have access to different sets of objects
for various scoping reasons. Each such scope is called a sphere (suggesting a
"sphere of knowledge") in which a specified set of objects is known. Each
interface has a maximal sphere, being the set of all objects known at that interface by
any users.
These concepts will be elaborated in Section 26. For
now we deal simply with a single interface, operating under a single object model, with
just one (maximal) sphere.
This section describes a particular model which, in the terms introduced in Section 22, can be characterized as a participant and
associative model.
(This could be FOQL - Functional Object Query Language - abusing the word
"query" to include all DDL and DML, just as in SQL and OSQL.)
By and large, this is an aggregation of familiar material, such as the functional
Evaluate/Apply paradigm and some usual notions of types, operations, overloading, etc.
However, there are a number of small but powerful refinements:
Most real systems and languages support only a subset of the features described here.
This model is intended to be a superset of the model supported by most real systems and
languages.
The model is developed top-down, developing the natural consequences of the fundamental
concepts.
From the user perspective, everything that happens in an object system is the
consequence of a request.
This model is essentially a functional object model - operations and functions are the
same thing. A request designating an operation and an argument is issued by a user at an
object system interface. In the simplest case the request explicitly identifies a specific
operation and a simple object. In other cases the operation might be generic [Section 10.1], the argument might be complex [Section 11], and either might be designated by an
expression [Section 6.2] consisting of a composition of
requests.
A request is an event, occurring at a point in time. The same operation/argument pair
might occur in many requests.
Evaluation of a request yields one or more of the following:
- A condition object providing information about the evaluation process. It might
be a composite of several conditions.
- An optional result object (which may be called the value of the
request).
- Possible update [Section 6.4], altering the
results returned by future requests.
- Possible display of a symbol at an interface.
Evaluation always yields some condition object, in order to signal completion of the
evaluation.
Following are some of the conditions which might be returned for an operation f and
argument x:
- Unknown: either f or x is not a known object in the current sphere [Section 7.1].
- Inapplicable: f is a specific operation, but the system has no instructions on
how to apply f to x (i.e., x is not an instance of the argument type of f [Section 9]).
- Undefined: f is a generic operation, and no specific operation named f is
defined for any type to which x belongs, no default value has been provided [Section 10.3.4], and no appropriate casting operation
is available [Section 10.4.1].
- Ambiguous: f is generic, and there is more than one eligible specific operation
remaining after resolution, and no disambiguator has been specified [Section 10.3.4].
- NullArg: f is specific and x is null, where the pre-conditions for f do not
allow null arguments; or f is generic, and no specific operation named f accepts a null
argument.
- Null: there is no result object. An object is said to be null if its evaluation
yields the null condition.
- Completed: simply indicates completion of the evaluation.
Some of these conditions may not be treated as errors, depending on the degree of type
checking in effect. If the condition is not an error, then the result should be considered
null.
An error-free evaluation yields no error conditions.
Other things besides simple requests can be evaluated. Exactly who does this evaluation
may be debatable. This is one point at which we enter the fuzzy domain between the user
(client) environment and the object system. For example, an expression such as
Length(x)+Length(y) might be compiled into two calls to the object system to retrieve the
lengths of two objects, with the subsequent addition being performed locally in the
program's own execution space. Compositions such as Length(Axle(x)) might be similarly
decomposed into two calls to the object system. We will not address these sorts of
decomposition here, simply saying that, from the user perspective, the object system does
all evaluation.
Requests may be more complex than a simple operation/argument pair. Either of these
elements might itself be the result of a request, giving rise to nested requests. At the
other extreme, single objects can themselves be evaluated.
To be precise, an operation is a value object [Section
29.1] which can occur as the first element of some pair whose evaluation is
error-free. The second object in such a pair is playing the role of an argument.
A request form is a pair <f,x> which is intended to be evaluated. Either
element of the pair may itself be a request form. The request form is generally denoted as
f(x) in functional notation, or as x.f in relational dot notation and object-oriented
messaging notation. (In some syntaxes where the argument x is implicitly understood - as
in the current row of a table during a query - f alone can also have the same meaning.) A
request to evaluate an argumentless operation [Section
27.1.3] will be expressed as a pair with a null second element, i.e., f() or
<f,>. The notion of a pair is itself defined in Section
29.5.
We can use the term property to mean an operation which may return a value,
e.g., f is the property in f(x)=y.
It is not clear how to differentiate an expression from other valid objects, although a
language parser might do so. A variable is an expression, though it is not a request form.
The default evaluation for any object is to return itself, i.e., to treat it as a value
object. Thus an expression is any object for our purposes.
Details of expression evaluation are described in Section
27.2.
From the user perspective, it doesn't matter who performs a requested service.
Notes:
- Define "performer" (relative to type or class?). Illustrate with registration
of students in courses. Refer to Section 16 regarding
implementation.
A common paradigm: A performer object has a location property and a set
of exclusively owned methods. A request is executed by sending a message to the performer
object, causing a method to be dispatched.
- Performer view: infrastructure is a transparent medium through which a message flies
like an arrow to a target object which performs the requested service. Other mentioned
objects merely go along for the ride as parameters. Users write requests in a syntax
requiring them to designate the performer object.
Participant view: the requested
service might be performed by any of the mentioned objects, or by something else
altogether. The infrastructure plays a more active role, at least to the extent of helping
to select a performer for the request.
Proposition: the knowledge of who performs the requested service is an implementation
concept. The user doesn't care. It should be possible to have different performers in
different implementations without affecting the user.
- "Reflection" is often described as the ability of an object to tell what type
it is. That's a performer (implementation) perspective. The participant (user) perspective
would merely say that it is possible for a user to ask for the type of an object. The user
doesn't care whether the answer comes directly from the object or from some other system
service.
- Other examples: In the performer view, it might be said that a request to print a book
is performed by the book itself, while a request to identify the authors is performed by
some other object or service which manages attributes of objects, such as a database. In
the participant view, both are requests which can be applied to a book. (We could cut the
distinction even finer and say that a request for the number of chapters is handled by the
book itself by counting, rather than being an attribute.) (Add other similar examples.)
- The notion that an object is an application is essentially a performer viewpoint.
The essential effect of update is to alter the results of future requests.
The traditional notion of update in terms of writing data to storage is not effective
from the user perspective, since storage mechanisms are hidden from the user on the other
side of the object system interface. The only way the user knows that update has occurred
is by observing the results of future requests. If the user requests that the radius of a
circular object be modified, the user will subsequently see different responses to
requests for the radius, diameter, circumference, area, volume, or weight of the object.
The user doesn't know, nor need to know, which or how many of these facts are physically
stored, as opposed to being computed from the others.
When the Assign operation is applied to a pair consisting of a quoted variable
[Section 28.6] and an expression, its effect is to bind
the variable in the current environment [Section 27.1.1]
to the result of the expression (including null).
The request form Assign(<`x,y>) (i.e., <Assign,<<Quote,x>,y>>)
is generally denoted as x<-y. Note that x itself is not evaluated, but y is. The effect
is that a subsequent evaluation of x in the current environment, with no intervening
update of x, will yield y.
When the Assign operation is applied to a triple <f,x,y>, where the first element
is an updatable operation, the effect is to invoke the update component of the operation [Section 10.2.2.2]. The effect of executing the update
component should be that a subsequent invocation of f(x) returns the value of y (including
null).
Assign(<f,x,y>) can be denoted as f(x)<-y; this does not signify that f(x) is
to be evaluated (although x itself is evaluated in this case).
Updates which would violate any constraints (invariants) are not permitted. An attempt
to do so should yield an error condition.
Some languages support a single assignment operation such that Assign(f,x,y) signifies
f(x)<-y (the language might directly support an assignment syntax). Other languages,
via an attribute mechanism, associate with an updatable operation f an updating operation
Updater(f), such that Updater(f)(x,y) signifies f(x)<-y. For example, the updater for
Salary might be Set_Salary, and the updater for Location might be Move. The effect of
Move(x,y) is thus defined as causing Location(x) to be y.
The concept of state is not uniquely defined from the user perspective.
A changeable property is one whose value may change with time, e.g., f(x)=y
now and f(x)=z later. Square root and square are unchangeable properties of integers. A
schema might define social security numbers or part numbers as unchangeable properties of
persons or parts.
An updatable property is one whose value can be changed by direct assignment,
for which we will use the syntactic form f(x)<-z. After such assignment, we have f(x)=z
(ignoring funny situations casting might cause). A schema might define Age to be
non-updatable, yet it is changeable by the passage of time or by the update of someone's
birthday.
Updatable properties need not be stored. Update may be managed by procedures which
update other stored information. For example, either the radius or diameter of a circular
object could be stored. Both might be updatable, with the stored value being updated as
appropriate. Thus, if the radius is stored, then updating the diameter causes half the new
diameter to be stored as the new radius.
A recorded property is one whose value is stored; this is an implementation
concept. This is sometimes equated with the notion of state. Unfortunately, the
necessary set of recorded properties is not uniquely determined by semantics, but is
ultimately an implementation choice. The set of minimal recorded properties is not unique.
For example, while it is clear that either the radius, diameter, circumference, or area of
a circular object must be stored, the choice is a matter of implementation (we might even
choose to store several for efficient retrieval, keeping the various stored values
synchronized).
Thus there is no natural definition of an object's state. Some systems and languages
allow an arbitrary set of properties to be defined as the state of an object. Care should
be taken not to assume that these are recorded properties, as this would expose
implementation to the user. This set of properties is also sometimes taken to define the
"content" of the object [Section 13.4] for
the purposes of such operations as Copy or Display.
The term "mutable" is ambiguous. It is commonly used in the sense that some
objects are mutable while others are not, but the concept really applies to properties of
objects. Certain properties of an object might be mutable while others are not, and it
might be the case that some objects have no mutable properties. In any case, however, it
is not clear in which of the above senses mutability is defined. We avoid the term.
Objects "exist" so long as they are known to an object system.
If an object system can provide the date on which a certain file was deleted, then that
file object still exists as far as the object system is concerned. Certain operations may
no longer be supported, such as modifying or displaying the contents of the file, and the
file may no longer be present in any directory, but the object system can still respond to
requests involving that file.
Similarly, if an object system can provide the date on which a certain building will be
completed, as well as its location, height, and blueprints, then the building object
exists even if construction has not yet begun.
We try to avoid dealing with "existence" in this document, and speak only of
objects being known by an object system. Operations which purport to
"create" or "destroy" objects in an object system should really be
understood as "introducing" and "erasing" objects, i.e., making them
known and unknown to the object system.
An object is considered to exist in an object system if any operation can be
successfully applied to it in the object system. More specifically, an object is known if
it can be mentioned as an argument in some request without causing an unknown
error condition [Section 6.1]. Such existence does not
necessarily imply that storage space has been allocated for maintaining data about the
object, or that certain particular operations can be applied to the object.
Other notions of "existence" can be modeled in terms of the status of known
objects, perhaps in terms of types and subtypes. For example, "ExistingFile"
might be a subtype of "File", such that operations which modify or display the
contents, or manage the file within a directory, are only defined on ExistingFile.
The management of object identity depends on how an object becomes known to an
object system.
The closest we come to dealing with the philosophical question of what
"exists" in an object system is to describe what is known in a sphere. Objects
can become known in a sphere by the following means:
- Eternal objects are always known. This is the case, for example, for elementary
literals such as numbers and character strings. It is also the case for things essential
to the object model, including types such as Function, Type, etc.
- Mortal objects are made known to a sphere by explicit invocation of a New
operation [Section 7.4] at the sphere. The set of mortal
objects known to a sphere is finite, and New increases the size of this set.
- Ephemeral objects become known according to a rule, which may be true or false
at various times for a particular object and a particular sphere. Some examples:
An extensional set is known if and only if its elements are known.
For certain kinds of imported data, an object exists if and only if a certain value
exists in some external data source.
The objects known in one sphere might be defined by selection from the objects known in
another sphere.
The term surrogate refers to mortal objects together with the non-literal
objects essential to the model itself, like the built-in types and operations. (In
implementation terms, surrogates are things typically represented by system-generated
object identifiers.)
The management of object identity should be consistent with the axioms of equality.
Equality in object systems is ultimately described in terms of an arbitrary equality
predicate x=y whose truth may be defined either by users or by the object system. However,
in order to provide expected behavior, the predicate should observe the axioms of equality
and substitution.
The semantics of object identity are described by axioms for an equality operation x=y [Section 28.1], interpreted to mean that the values of the
variables x and y are one and the same object. The operation may yield different results
in different spheres, but is always subject to the following axioms (quantifiers range
over a given sphere):
E1 (reflexivity): FORALL x, x=x.
E2 (symmetry): FORALL x FORALL y, x=y => y=x.
E3 (transitivity): FORALL x FORALL y FORALL z, x=y AND y=z => x=z.
E4 (substitutability): FORALL x FORALL y FORALL f, x=y => f(x)=f(y); also, f(x) and
f(y) cause the same conditions and updates.
E5 (singularity): FORALL x FORALL y, x=y => {x,y}={x}, or equivalently,
Card({x,y})=1.
E5 captures the notion that x and y refer to one object. E5 might not be an independent
axiom, depending on how set construction is defined in terms of equal elements, but it
doesn't hurt to emphasize it here.
Although identity is often implemented in terms of object identifiers (oid's), the
semantics of identity are defined without reference to oid's.
New() is an argumentless operation which returns an object which did not
previously exist.
AddType(x,t) makes x an instance of type t. It can be characterized as
Add(<`Extent(t),x>).
RemoveType(x,t) makes x no longer an instance of type t. It can be
characterized as Remove(<`Extent(t),x>).
The main purpose of the Initialize operation is to allow values of total
operations to be provided at the time an object becomes an instance of their argument
types. It has the form Initialize(<x,<<f1,y1>,...,<fn,yn>>>), and
its effect is equivalent to
f1(x)<-y1,
...
fn(x)<-yn.
The AddType operation should incorporate Initialize in order to satisfy constraints on
total operations. Hence AddType should accept arguments for Initialize (or the two should
be packaged in some other atomic operation). Initialization should account for total
operations defined on supertypes of t as well as on t.
Object creation operations often bundle New and AddType (and hence Initialize),
creating an object as an instance of a type.
Schema constructs such as types, operation definitions, and inheritance are provided
for planning purposes, so that users can choose the appropriate requests to achieve their
intended results.
The following topics need to be developed:
- The nature and role of types.
- How types get created and populated.
- Relationships among types.
- Different notions of subtype.
- Type checking.
- Extent maintenance.
Types are fundamentally a link between objects and operations, establishing whether the
object system has instructions on how to apply an operation to an object. In a nutshell,
if an operation f is defined to accept arguments of type t, and if x is an instance of
type t when f is applied to x, then a request which applies f to x will not cause the inapplicable
condition [Section 6.1]. This enables users to plan to
apply f to x without fear of causing this particular condition.
Types also characterize the results returned by operations. If an operation g is
defined to return results of type t (the argument type of f), then the user may plan to
apply f to the result of g(y) without fear of raising the inapplicable condition
(assuming g is applicable to y).
There are at least the following things associated with the notion of "type":
- A type itself, as a distinct concept in its own right.
- A predicate which tests whether an object is an instance of the type.
- A "type interface" consisting of a set of operations associated with the type [Section 10.5]. There may be several such notions,
differentiating between the type's own operations and inherited operations.
- An extent, i.e., the set of instances.
(The following text is a bit old, and may need to be cleaned up to better reflect these
distinctions. An interesting thought to pursue is whether a single object can play all
these roles. Also deal with the fact that created types are surrogates (mortal) while
parameterized types are ephemeral.)
There is an object named Type. A type t is an object for which t IN Type. Type
IN Type, i.e., Type is a type. If x IN t for a type t, then the value of x is an instance
of the type t. (More precisely, x is an instance of the set which is the extent of the
type t. We could model it that way if we took a little more trouble.)
A type t is also a total predicate, such that t(x)<=>x IN t. (Hence Type SUBSETEQ
Predicate SUBSETEQ Profile SUBSETEQ Operation.)
There is an ArgType operation which, when applied to some operations, yields a type. If
x IN ArgType(f) then evaluating f(x) will not yield an inapplicable condition.
There is a ResultType operation which, when applied to some operations, yields a type.
If ResultType(f) is t and evaluation of f(x) does not yield an error or null condition,
then f(x) IN ResultType(f).
If t1 SUBSETEQ t2 for types t1 and t2, we will say that t1 is a subtype of t2.
A subtype t2 of t1 is an immediate subtype of t1 (and t1 is an immediate
supertype of t2) if no supertype of t2 is a subtype of t1. An instance x of type t is
an immediate instance of t (and t is an immediate type of x) if x is not
an instance of any subtype of t.
Every type has a name. System types have predefined names. Created types are named upon
creation. Generated types are named by a naming convention. Type names are unique over all
types known within any given sphere.
The fact that x is an instance of t can be expressed in a number of equivalent ways
(some of which are curried equivalences [Section 25.3]):
x IN t <=> t(x) <=> TypeInstance(<t,x>) <=> t IN Types(x)
<=> x IN Extent(t).
This is territory where we usually don't want to be bothered with the distinctions,
because we assume some familiar defaulting conventions which gloss over the detail. Thus
we hate to have to say that 10 is to be interpreted as decimal digits, because that's the
normal assumption. Such things only matter when the defaults aren't self-evident. Thus our
overall approach should proceed in stages: first spell out the painful details involved,
then seek ways to ease the pain by restoring appropriate defaults wherever possible.
The general idea is that only materialized types can be exported and imported. Any
other type has to be cast (coerced?) into a materialized type for export, and an inverse
casting mechanism needs to be established for import.
This is closely related to the notion of semantic and presentation objects, taken to an
extreme degree. Here, semantic objects are inside the black box, in opaque form. Anything
else that is input, output, or stored is in a presentation form, including simple strings
of bits, bytes, or characters.
The essential idea: Integer is a non-materialized type, not presuming any symbolic
representation. The corresponding materialized types include Decimal_Integer (the
traditional default), Hexadecimal, Octal, Binary, etc. We might also have Word_Integer,
whose instances include "one", "ten", "one hundred
twenty-one", perhaps with variants for different languages. The check-writer in my
financial software converts numbers to a type similar to this. It may be the case that we
know the internal form used inside the black box, or in storage, but this doesn't really
matter to the end user.
The concept of a materialized numeric type deals with the correspondence
between symbols and abstract numbers, with each such type having an associated:
- Set of symbols.
- Corresponding set of abstract numbers.
- Mapping between these.
The mapping is an important part of the type concept, since the same symbol can occur
in different numeric data types to denote different numbers. Thus 10 means different
things in decimal and binary, and 1E1 means different things in exponential and hex.
For the Hexadecimal type the set of symbols includes all sequences over the alphabet
{0...9,A...F}. (This is the ideal type; corresponding effective types will be limited to
finite sets [Section 9.2.2].)
The mapping is a pair of inverse functions for input and output, establishing
correspondences between abstract numbers and symbols. Thus HexIn(A) applies the HexIn
function to the symbol A, yielding the number ten (in no specific representation).
Similarly, HexOut(OctalIn(10)+BinaryIn(10)) yields the symbol A.
We've actually seen these functions in many languages, though with a different syntax.
HexIn(10) often takes the form x `10'. The forms x`10', o`10', and b`10' each map the
string 10 into a different number. (Those are "designators".) In fact, we can
think of quotation marks in a similar sense: "10" behaves like CharIn(10),
mapping the string 10 to an opaque internal representation of itself.
It's interesting to note that there is no materialized type corresponding to the real
numbers, if we assume that symbol sets are denumerable. A data type called
"Real" is dealing at most with the rational numbers.
This is where we take into account the effect of implementation restrictions on data
types. An ideal type is an abstraction which typically cannot be fully implemented in any
real system. An effective type is the type that's really supported by an implementation.
We want to try to describe these in semantic terms, being minimally contaminated by
"implementation" considerations. Unfortunately, "minimal" is not zero.
The essential problems are these:
- An effective type does not have all the nice characteristics of its corresponding ideal
type. It does not satisfy all the axioms, most notably the closure axioms.
- There are usually many effective types corresponding to one ideal type.
Languages typically take one of the following approaches:
- They only mention the ideal types in the language, and essentially tell the user about
the effective equivalents by referring to "implementation dependencies" hidden
away in some appendix. An ideal type thus might bind to different effective types in
different environments.
- They actually incorporate effective types into the language, introducing such things as
Long and Short, or Integer_16 and Integer_32. However, they sometimes do funny things,
such as not recognizing that an instance of Integer_16 is also an instance of Integer_32.
(The number ten occurs in both.)
Dividing these types into non-materialized and materialized, and also into ideal and
effective, yields four categories. We'll go around the matrix in the following order:
- Ideal non-materialized types contain the infinitely perfect abstract numbers.
- Ideal materialized types contain their representations without length restrictions.
- Effective materialized types contain the representations with length restrictions.
- Effective non-materialized types contain the finite subsets of the abstract numbers
which can be represented.
Ideal non-materialized numeric types are the ones we learned about in school. The
counters (non-negative integers) are a subset of the integers, which are a subset of the
rationals, which are a subset of the reals, which are a subset of the complex numbers if
we want to go that far. By "subset" we mean a naive form of inclusion whereby
the integer ten is itself a rational number, not just "equivalent" to something
else denoted by 10.0.
All these sets are infinite, and they are all closed under addition, subtraction, and
multiplication. All but the integers are closed under division. Comparisons are perfect,
i.e., two numbers either are or are not equal, unambiguously. Equality is a perfect
equivalence relation (symmetric, reflexive and, hardest of all, transitive), and the
orderings perfectly satisfy their axioms. Even assignment works perfectly: x=e always
holds after x<-e.
These are the ones described above in Section 9.2.1,
with infinite symbol sets.
These are the materialized numeric types with length restrictions. There are overall
length restrictions, as well as restrictions on various components, such as the mantissa
and the exponent.
In effect, these are parameterized types, parameterized by different lengths.
The effective non-materialized numeric types are the ones actually supported in
computational systems. They represent places where implementation considerations show
through into language semantics, being impacted by limitations of hardware and
representation.
(Alternative terminology: we might also call these "practical",
"pragmatic", or even "finite" numeric types. Even the term
"real" - as opposed to ideal - comes to mind, but that would get confused with
the real numbers.)
Note that several different effective materialized types might correspond to the same
effective non-materialized type. For example, 4-character hex and 16-bit binary have the
same capacity.
An ideal numeric type can have a large number of overlapping effective numeric
subtypes, corresponding to different internal limitations. The essential characteristic of
the effective types is that they include only a subset (usually finite) of the instances
of the ideal supertype. Thus Integer_16 only contains the integers up to (2**16)-1, while
Integer_32 includes those as well as all other integers up to (2**32)-1. There may be
interior gaps as well as outer bounds. A type restricted to three significant digits can
represent 1230 and 12300, but not 1234; the "successor" to 1230 is 1240.
This incompleteness leads to the central semantic problem of effective types: failure
of closure under arithmetic operations. This is exactly what causes overflow and underflow
errors, as well as truncation and rounding.
Most operations are not closed within an effective type. More generally, trying to
represent an arbitrary abstract number requires an additional fudge step (often
roundoff or truncation) to find an appropriate (not always nearest) abstract number which
is representable in that data type. Similarly, comparisons sometimes take such fudge
factors into account.
So, the course of a computation goes roughly as follows:
- Argument symbols are obtained from cells.
- Interpretation of the argument symbols is governed by data type specifications, which
might be declared in the computational procedure, associated with the source cells, or
embedded in the symbols for self-describing data. These interpretations govern the
abstract number yielded by the computation.
- The abstract number resulting from the computation has to be represented in some target
cell (variable, table entry, etc.). The first step is to fudge the result to the
appropriate number representable in the target data type, and then place the
representation of that number into the target cell.
Such data types correspond to mappings into, rather than onto, a certain kind of number
(e.g., rational or integer). The set of numbers it maps symbols onto are its representable
numbers. The inverse mapping is total on the representable numbers, partial on all the
numbers. Alternatively, the inverse mapping is total but not invertible; an arbitrary
number first gets fudged to a representable number, whose corresponding symbol is then
used. Inverting this yields the representable number, not the original number.
Example: say SmallRational can represent numbers to two decimal places.
SmallRational(2/3)=0.67. Number(SmallRational(2/3)) yields a number equal to 67/100, not
2/3.
We might distinguish between "exact numbers" and "true values". A
symbol exactly denotes a certain number when interpreted within a specified data type. It
might not be the intended "true" number for a variety of reasons. Thus
0.666666666667 very exactly denotes a certain rational number in decimal notation. It may
be "wrong" because it was originally computed as 2/3, or because a ruler had
finite precision, or because somebody entered the wrong number. But it is a very exact
number. This is analogous to saying that 1,000,000 is a very exact number, but it might be
"wrong" because it is only the estimated population of a certain city.
We'd like to relegate this all to the realm of "implementation", quite
unrelated to the semantics of operations performed by users. Unfortunately, we can't.
Users see the consequences in the form of various sorts of errors. Results of certain
computations get too large or too small, and comparisons occasionally behave strangely.
Assigning x/y to z might not yield equality between x/y and z.
Therefore, the user needs to be conscious of "subtypes" of the number kinds.
It is in fact semantically meaningful to differentiate between Integer_16 and Integer_32,
or between Rational(5,5) and Exponential(5,5). Each of these types has a different
population of representable numbers, and assigning anything to cells having such types has
to be understood as implying a fudge step.
On the other hand, we need to be careful whether we have in mind different internal
implementations or different sets of abstract numbers. The difference is illustrated by
whether or not we consider Integer_16 to be a subtype of Integer_32. The integer ten is an
instance of both, and the same can be said of any abstract number representable in
Integer_32. Thus the numbers in the abstract set denoted by Integer_16 is a subset of the
set denoted by Integer_32. On the other hand, a 16-bit field is not a 32-bit field. The
fields declared to be of type Integer_16 are not declared to be of type Integer_32. In
this sense, Integer_16 is not a subtype of Integer_32.
The same sort of argument arises between such types as Integer and Rational (aka Real).
Numerically, one is a subtype of the other, but in terms of representations they are not.
An interesting and possible useful idea is to treat numeric types as parameterized
types, with the "storage" type as a parameter. This would be a useful way of
relating the abstract and stored types. For example, Integer might be a type generator
rather than a single type. Specific types would be given by Integer(32_bit) and
Integer(16_bit). Similarly, rational types might be given by Rational(5,5) and
Rational(5E5).
The operation referenced in a request may be either specific or generic.
A specific operation is explicitly defined with a name, signature, and
behavior specification.
Several specific operations may have the same name. A generic operation
implicitly exists for each set of specific operations having the same name. If a request
identifies an operation by simple name only, this is a reference to the generic operation,
which then has to be resolved to a specific operation appropriate to the argument in the
request.
There are no inheritance issues or problems for specific operations. The complexities
of inheritance and overloading arise only with generic operations.
There is a type named Operation (whose instances are all the operations), partitioned
into the subtypes named SpecificOperation and GenericOperation (the latter are described
in Section 10.3).
A specific operation has the following things:
- A name f (sometimes called its simple or generic name), given by the
operation Name(f). This might not be a unique name, hence it does not "denote"
the operation.
- An optional argument type, given by ArgType(f), as described above. If absent, the
operation is argumentless, i.e., it can only be applied to a null argument. The
argument type may be an aggregate type. In particular, an operation on multiple arguments
is modeled as an operation taking a sequence (tuple) as argument.
- An optional result type, given by ResultType(f), as described above. If absent, this
operation never yields a result object. The result type may also be an aggregate type.
- A specific name, obtained by concatenating the name of its argument type with
its simple name, e.g., T.f. The specific name of an argumentless operation is its simple
name. Specific names are unique over all operations known within any given sphere.
- Behavior specifications.
There are several notions of signature. We define it here as the name,
argument type, and result type of an operation, often denoted as f: t1 -> t2.
Behavior specifications are distinct from implementation specifications.
Behavior specifications describe the consequences a user should expect from applying an
operation. Implementation specifications describe what the object system (including the
objects it manages) has to do to yield such consequences. We reserve the term
"method" for implementation specifications. Many current systems and languages
merge the two concepts, taking methods to be behavior specifications.
The distinction is admittedly fuzzy. A definition of salary as the product of hourly
rate and hours worked could arguably be taken either way. So could the definition of an
operation in terms of a high-level query which is both readable and executable. The
distinction must ultimately be made somewhat arbitrarily by type and class definers, based
on the following guidelines:
- Specifications which should be changeable without affecting the reasoning of
applications which use the defined objects are implementation. A change in implementation
might require recompilation, but not reprogramming.
- It should possible for applications which use the defined objects to function correctly
with several different implementations.
Furthermore, the state of the art in behavior specification is not yet mature.
Nevertheless, we describe the general model in terms of a distinction between behavior and
implementation specifications.
A behavior specification thus defines the intended behavior of an operation when it is
applied. The specification is provided for the user's information, and is also intended to
constrain the implementation specification. It might be provided in various forms, such
as:
- Comments (not effective in constraining the execution specification).
- An executable (or interpretable) language, such as a query language, which is judged to
be "high level" enough to be meaningful to users.
- Logical constraints such as pre- and post-conditions:
- Pre-conditions are constraints which must be satisfied to insure error-free application
of the operation.
The requirement that the argument be an instance of the argument type
is an implicit pre-condition (if strict type checking is enforced - to be discussed).
Whether or not the operation can be applied to a null argument is also a pre-condition.
- Post-conditions are constraints which will be satisfied after error-free application of
the operation.
The fact that a non-null result will be an instance of the result type
is an implicit post-condition.
Totality (i.e., the result will not be null if the argument is an instance of the
argument type) is also a post-condition.
The implementation specification defines what the object system will actually do when
the operation is applied. It might be provided in various forms, such as:
- An algorithm specified in some arbitrary language. It may invoke services at a different
facet of the object system. (This is the usual notion of method.)
- An interpreter for the behavior specification (or a compiled form of it), e.g., a query
interpreter.
- A mapping to an internal data structure (another facet?), implying that the retrieval is
effected simply by retrieving the stored data.
An operation may have several sets of implementation specifications, each associated
with a different class [Section 15].
In a general model which supports direct update [Section
6.4.2], a separate specification is provided for the behavior of the operation when it
is updateds. In effect, this serves as an "update entry point" for the
operation. This specification might simply say that the operation is updatable, i.e.,
assignable [Section 6.4]. It could also define the
intended behavior when this is ambiguous, e.g., it would indicate whether changing an
employee's manager is interpreted as the employee changing departments or the department
changing managers. The update semantics might be inferred by the system, e.g., when the
operation is mapped to stored data, or when the system can determine the inverse of the
retrieval specification.
Specific operations having a given name imply the existence of a generic operation
with that name. A generic operation has a default behavior defined by the computational
system (i.e., the rules for overloading) in terms of specific operations having the same
name as the generic operation. User-specified behaviors can override the default behavior
in order to provide:
- Disambiguation of ambiguous generic calls to overloaded operations.
- Different behaviors of generic operations for different argument types.
- Different result types for overloaded operations with the same name.
- Default values for operations not defined on certain types.
- A limited form of upward inheritance.
- Multi-operation uniqueness and equivalence specifications.
Besides their general utility, these features are particularly useful for multidatabase
systems [Section 30.1].
A behavior may be specified for a generic operation f with respect to a set of relevant
types. Specifications may include a result type, a default result value, a disambiguation
specification, and a uniqueness specification (these terms will be defined shortly).
Different behaviors may be specified for different sets of relevant types. For example,
they may have different result types; any operation named f whose argument type is in a
relevant type set must have the specified result type.
When f(x) is invoked:
- If it is unambiguous, then the appropriate specific operation is invoked, without
involving the generic operation.
- If x is an instance of types in a relevant type set for the generic operation f, but no
specific f is defined on any type of x, then the generic operation can define the default
result.
- If f(x) is ambiguous, and the argument types of all the eligible specific operations are
in a relevant type set for the generic operation f, then the generic operation can provide
the disambiguating behavior.
- When none of these conditions are satisfied, the system default behavior for generic
operations applies.
Inheritance behaves as follows (this is inheritance of interfaces, not
implementations):
- The operation f.ti is known for ti.
- If the operation f.ti is known for tj, then it is known for an immediate subtype tk of
tj if there is no specific operation f.tk.
In particular, both f.t1 and f.t2 are known for t4 in the case shown in Figure 3.
------
| t1 |
f.t1 ------
:
.....................
: :
------ ------
| t2 | | t3 |
f.t2 ------ ------
: :
.....................
:
------
| t4 |
------
Figure 3.
Unless otherwise defined for the generic operation, all specific operations having the
same simple name must have the same result type. (OSQL may allow overloaded operations
defined on literals to have different result types from operations with the same name
defined on surrogates. That's not particularly significant here.)
A request may involve a simple (generic) or specific operation name. If specific, the
call invokes the behavior defined for the specific operation [Section 10.2].
The default behavior for a generic operation call f(x) is defined as follows:
1. The eligible operations are the specific operations f.t which are known for
the immediate types of x.
If x is null, the eligible operations are the specific operations named f whose
pre-conditions allow null arguments, including argumentless operations.
2. If there is exactly one eligible operation, invoke it and exit.
3. If there are no eligible operations:
3a. If there exists exactly one Caster(<t1,t2>) [Section
10.4.1] such that x is an instance of t1 and there exists an f.t2, then invoke
f.t2(Caster(<t1,t2>)(x)) and exit.
3b. Else return an undefined condition and exit.
4. If there is more than one eligible operation:
4a. If all the non-null values are the same, then return that value (or null if all the
values are null) and exit.
4b. Else raise an ambiguous condition and exit.
Without item 4a, f(x) would be considered ambiguous when there are several eligible
operations even if they all have the same value.
The following behaviors may be explicitly defined for a generic operation with respect
to a set of argument types:
- A result type.
- A default result specification.
- A disambiguation specification.
- An optional uniqueness specification.
Details are described in Section 30.
When a specific operation is applied to an argument which is not an instance of the
operation's argument type, there are additional mechanisms which sometimes define
behaviors.
The essential idea of casting is that an object x which is not of an
appropriate type may be replaced by a related object c(x) which is of the appropriate
type. An operation c which plays this role is a casting operation.
For any pair of types t1 and t2, there is at most one casting operation c with
signature c: t1->t2. For such a pair of types, we define a Caster operation
such that Caster(<t1,t2>)=c.
If Caster(<t1,t2>) is not null, and if any operation f.t2 is applied to an
argument x which is an instance of t1 but not t2, then f.t2(x) can be evaluated as
f.t2(Caster(<t1,t2>)(x)), i.e., as f.t2(c(x)).
CastingOperation is a subtype of Operation. An operation might be defined as a casting
operation in several ways:
- Built-in, as with type casting for basic data types.
- Explicitly, by some syntactic means which establishes some operation c with signature c:
t1 -> t2 as the casting operation from t1 to t2. Certain operation names, such as
Content, might be defined to belong to casting operations.
- By default, if there is only one operation from t1 to t2. Language definers can decide
whether or not to support such a default.
Since an instance of a type t is an instance of all supertypes of t, an instance of t
is always acceptable where an instance of a supertype is required. Hence it does not make
sense to allow a casting operation to be defined from a type to any of its supertypes.
Automatic casting between basic data types is often defined for some languages.
The Cargo operation is the casting operation for intensional aggregates [Section 11.7].
As a special case, we will assume that Extent is the casting operation from Type to Bag
(did we say that Bag=BagType(Object)?). Thus, whenever a type t appears where a bag (or
set) is needed, it can be replaced by Extent(t).
The existence of a casting operation from type t1 to type t2 means that an instance of
t1 is acceptable wherever an instance of t2 is required, i.e., t1 is substitutable for t2.
If t1 is a subtype of t2, then t1 is trivially substitutable for t2 without a casting
operation.
If f has signature
f: t1->t2,
where t1 is not a bag type [Section 11.1.3], it is
useful to "overload" f with another definition with signature
f: BagType(t1)->BagType(t2),
whose behavior is defined for a bag b of type BagType(t1) as
f(b) ::= BagReplace(<b, `x, `f.t1(x)>) [Section
28.7.4].
The result is a bag in which each occurrence of x in b is replaced by an occurrence of
f.t1(x).
An operation might be exclusively or jointly owned.
Topics:
- Creating and destroying types and operations (relate to general creation of objects).
- Parameterized types.
- Maintaining type relationships: subtype, disjoint.
- How objects become instances of types.
- Changeable types.
- Multiple immediate types.
A type can be acquire instances by one or more of the following means, corresponding to
various ways in which its Extent operation can be managed:
- By assertion, i.e., via AddType. Its Extent operation is assertable.
- By a rule, which is essentially the script for its scripted Extent operation. This has
several variants:
- Fixed population, which can be thought of as a constant rule. Most (all?) literal types
are like this.
- The rule selects from existing objects. (This is my notion of derived type.)
- The rule produces (materializes) new objects as instances whenever the rule is
satisfied. (This is my notion of producer type, also called imaginary virtual objects in
[1].)
- Via subtypes: t1 SUBSETEQ t2 => (t1(x)=>t2(x))
Maintaining consistency of rules can be difficult. If a rule-based type is also
assertable, or has subtypes, the instances acquired by those means should be consistent
with its defining rule.
Types are disjoint (intensionally) if they may never have any instances in
common. It follows that they may never have any common (non-empty) subtypes, and that
subtypes of disjoint types are themselves disjoint. Types which are not disjoint are said
to overlap, meaning that they could possibly have instances in common.
We can say that two distinct types intersect if they overlap with neither
being a subtype of the other. Exactly one of the following relationships holds between any
pair of types:
- Equal
- Disjoint
- Subtype/supertype
- Intersect
We summarize the rules governing overlap and disjointness:
- Distinct types are disjoint if and only if they do not overlap.
- Disjointness and overlap are each anti-reflexive (a type is neither disjoint nor
overlapped with itself).
- Disjointness and overlap are each symmetric (t1 is disjoint from t2 if and only if t2 is
disjoint from t1, and the same for overlap).
- Neither disjointness nor overlap is transitive (t1 disjoint from t2 and t2 disjoint from
t3 does not imply t1 disjoint from t3; the same for overlap).
- A type overlaps its supertypes. Transitivity of supertypes implies that a type overlaps
all supertypes of its immediate supertypes.
- If t1 is disjoint from t2, then t1 is disjoint from all subtypes of t2. If t1 overlaps
t2, then t1 overlaps all supertypes of t2.
A language may allow explicit specification of disjointness and/or overlap
(intersection), consistent with the above rules. A language may also establish the default
assumption. We will arbitrarily make the default assumption that types overlap.
Aggregates can be described in terms of content and form.
Aggregates have content and form. Bags and sets are the limiting case, having only
content but no form. "Content" does not have connotations of being inside, or
belonging. Doing things to an aggregate doesn't automatically do anything to its members.
Content is ultimately described in terms of an arbitrary "occurs" predicate.
An aggregate is an object in which other objects occur. Formally, we
define
Occurs: <:Object, Aggregate:> -> NonNegativeInteger,
with Occurs(<x,g>) giving the number of times x occurs in g. We use x IN g to
mean the same thing as Occurs(x,g); hence, x NOT IN g means (x IN g)=0.
The cardinality of an aggregate is the sum of all occurrences of all things in
the aggregate:
Card: Aggregate -> NonNegativeInteger,
Card(g) = SUM[x]Occurs(x,g).
A bag is an aggregate which is not an indexed aggregate [Section 11.2]. Alternatively, it can be characterized as
an indexed aggregate whose index set is empty.
A set is a bag which satisfies the constraint FORALL x, x IN g=<0.
There is exactly one empty set g for which Card(g)=0. It is the same thing as
the empty bag.
Bag and set equality:
g1=g2 <=> FORALL x, (x IN g1)=(x IN g2).
That is, g1 and g2 are the same bag (set) if and only if everything which occurs in one
occurs the same number of times in the other.
For any bag g, NullCon IN g is defined to be 0.
We can get more elegant by allowing a bag itself to be a profile operation such that
b(x) = x IN b. The expression defining the membership of b, i.e., the expression for
computing b(x), will be referred to as the "profile" of b. As a trivial example,
the expression b(x)=Prime(x) defines b to be the set of prime numbers. If x is prime, then
Prime(x)=1. In turn, b(x)=1 means that x occurs once in b.
A designator is an expression used as a means of identifying something.
Informal syntax such as {1,2} and {2,1} are examples of designators which identify the
same set (analogous to saying that 1+2 and 2+1 denote the same number). We avoid the
commonly used term "constructor" because of the unintended implication that
something new is being constructed with each use of the expression.
The informal syntax [x,y] is commonly used to designate bags. If x¬=y, then the result
in this case is also a set. {} and [] correspond to two different sorts of designator
operations: {} removes duplicates, while [] does not. Either one can yield a set; {}
always does.
Bag and set designators can be formally defined in terms of sequence designators. If we
let Boolean values be treated as 1 for True and 0 for False, then every sequence s has a
unique corresponding bag b such that b(x) = SUM[i](s[i]=x). This expression means that the
number of occurrences of x in the bag b is equal to the number of distinct integers i for
which x is the i-th element of the sequence s. Let the operation Seq2Bag map a sequence
into this corresponding bag. A Bag instance designator can be defined as
Bag(<e1,...,en>) = Seq2Bag(<e1,...,en>).
It is often denoted [e1,...,en].
Every bag b has a unique corresponding set s such that s(x)=1 <=> b(x)>0
(i.e., s(x)=[b(x)>0]). Thus x occurs once in s if and only if x occurs at least once in
b. Let the Distinct operation map a bag into this corresponding set. A Set
instance designator can be defined as
Set(<e1,...,en>) = Distinct([e1,...,en]).
It is often denoted {e1,...,en}.
Note that a bag instance designator will yield a set if the argument expressions yield
distinct values:
[e1,...,en] = {e1,...,en} when the non-null ei yield distinct values.
Since nulls are nothing, and sets are bags, we have
[] = {} = [NullCon] = {NullCon} = [NullCon,NullCon] = {NullCon,NullCon} etc.
These expressions all yield the same object.
Many relational operations can be described as designators involving regular bags.
An aggregate type is a type whose instances are aggregates whose members
satisfy certain type constraints. Aggregate types are ephemeral, and they exist exactly
whenever the types in their definitions exist. An aggregate type designator is an
operation which returns an existing aggregate type. It does not create anything new.
Details depend on the specific aggregate type designator.
(Type designators are parameterized types.)
(An interesting way to look at this: all imaginable and describable sets of existing
aggregates exist. At any point in time, an aggregate type corresponds to one of these
existing sets. Not all such sets correspond to aggregate types, however.)
Terminology: we will use Bag(...), Set(...), etc. to designate instances. Thus
Bag(<1,2,2>) means [1,2,2], i.e., it designates a particular bag. We will use
BagType(...), SetType(...), etc. to designate types. Thus BagType(Integer) is the type
whose instances are bags of integers. The difference is that [Integer] designates a
specific bag whose only member is the type object named Integer. We will use [:Integer:]
and {:Integer:} to respectively mean BagType(Integer) and SetType(Integer).
(We may not be consistently using that notation in operation signatures at the moment.)
The aggregate type designator BagType maps a type into an aggregate type:
BagType: Type -> AggregateType.
If t is any existing type, then BagType(t) is an existing aggregate type, recursively.
The instances of BagType(t) are all the bags whose members are instances of t:
b IN BagType(t) <=> Occurs(x,b)>0=>x IN t,
i.e.,
b IN [:t:] <=> b(x)>0=>x IN t.
Note that we are saying that b is an instance of that type which is returned
(designated) by BagType(t).
For example, if an operation is constrained to return results of the type
BagType(Integer), then any result returned by the operation will be a bag of integers.
Note that BagType is not a type, but an operation which returns a type. The type whose
instances are all bags is designated as BagType(Object).
We have t1 SUBSETEQ t2 => [:t1:]=>[:t2:]. Thus [:Employee:] SUBSETEQ [:Person:],
since any bag of employees is also a bag of persons.
Bag types may overlap, i.e., have instances in common, even if one is not a subtype of
the other. If @sam refers to a person, then [@sam] might be an instance of [:Employee:],
[:Teacher:], [:Student:], etc. Furthermore, [@sam,@jim] is an instance of [:t:] whenever
Sam and Jim are both instances of t, and it is not an instance if either Sam or Jim is not
an instance of t.
The aggregate type designator SetType is analogous to BagType, except that the
instances of {:t:} are all the sets whose members are instances of t. For any type t,
{:t:} SUBSETEQ [:t:].
Indexed aggregates provide a general way to describe things like sequences, arrays, and
records.
An indexed aggregate x has an index set characterized by the
operations:
IndexSet: IndexedAggregate -> {:Object:},
Extract: <:Object, IndexedAggregate:> -> Object.
({:Object:} means SetType(Object), i.e., the type whose instance is any set; see Section 11.1.3.)
Bags and sets can be considered the limiting case where the index set is empty, i.e.,
there are no accessors.
We use the notation g[i] for Extract(<i,g>). (We could also use the notation
i(g), except when the index set itself happens to consist of operations. We will use this
notation for sequences.)
If i IN IndexSet(g), then g[i] may return something, though it need not. If i NOT IN
IndexSet(g), then g[i] returns nothing, i.e.,
i NOT IN IndexSet(g) => g[i]~NullCon.
The following also holds:
g[i]=x => x IN g>0.
The arity (i.e., "length") of an indexed aggregate is the
cardinality of its index set:
Arity: IndexedAggregate -> NonNegativeInteger,
Arity(g) = Card(IndexSet(g)).
The number of occurrences of an object x in an indexed aggregate g is given by
x IN g = SUM[i IN IndexSet(g)](g[i]=x),
i.e., the number of occurrences of x in the indexed aggregate g is equal to the number
of distinct objects i in IndexSet(g) for which g[i]=x.
Equality of indexed aggregates is defined by
g1=g2 <=> IndexSet(g1)=IndexSet(g2) AND FORALL i, g1[i]~g2[i].
(Some models further differentiate aggregates according to the kind of designator used
in referring to them. In effect, the aggregate type becomes part of the identity of the
aggregate. For example, List(1,2) could be different from Tuple(1,2). It's not clear why
this is useful.)
Specific kinds of indexed aggregates are defined in Section
29.5.
A generalized model of indexed aggregate designation is given by an expression of the
form
Agg(<<i1,e1>,...,<in,en>>),
whose value is the indexed aggregate g with index set i1...in (all distinct) such that
g[ij]=ej and Arity(g)=n.
For a sequence designator the index set is omitted, defaulting to the integers 1...n:
Seq(<e1,...,en>) ::= Agg(<<1,e1>,...,<n,en>>),
which is often abbreviated to the form
<e1,...,en>.
The expression <>, i.e., Sequence(), yields a sequence of arity 0. There is
exactly one such sequence.
Observe that <> ¬= <NullCon> ¬= <NullCon,NullCon> ¬=
<NullCon,NullCon,NullCon> etc. They are all distinct sequences, having arities of 0,
1, 2, 3, etc., and correspondingly different index sets.
The compact sequence designator CompSeq(<e1,...,en>) essentially constructs a
sequence from the non-null expressions in the argument sequence. To define it, we can
first define a RemoveNulls operation on sequences:
RemoveNulls: Sequence -> Sequence.
RemoveNulls(s) is defined recursively:
1. Let i be the least integer 1 =<i=<n=Arity(s) such that s[i]~NullCon.
2. If none, return s.
3. Else return RemoveNulls(<s[1],...,s[i-1],s[i+1],...,s[n]>).
A sequence s is a compact sequence if and only if RemoveNulls(s)=s. Also,
Arity(RemoveNulls(s))=<Arity(s), and RemoveNulls(<NullCon,...,NullCon>)=<>.
The compact sequence designator can then be defined as
CompSeq(<e1,...,en>) = RemoveNulls(<e1,...,en>).
If none of the argument expressions is null, then
CompSeq(<e1,...,en>) = <e1,...,en>.
The instances of sequence types and tuple types are sequences. The instances of the
sequence type denoted by SequenceType(t) are all sequences of any length whose non-null
constituents are all instances of t. The instances of the tuple type denoted by
TupleType(t1,...,tn) are all sequences g of length n such that g[i] IN ti if g[i] is not
null. We use <:t1,...,tn:> to denote TupleType(t1,...,tn). Note that it is not
a sequence type.
We have t1 SUBSETEQ t2 => SequenceType(t1) SUBSETEQ SequenceType(t2).
Also, <@sam,@jim> is an instance of SequenceType(t) whenever Sam and Jim are both
instances of t, and it is not an instance if either Sam or Jim is not an instance of t.
For tuple types, the subtype relationship is
<:t11,...,t1n:> SUBSETEQ <:t21,...,t2m:> <=> n=m AND
0<i=<n=>t1i SUBSETEQ t2i.
The subtype is proper if any of the type pairs has a proper subtype relationship.
Due to the length distinction, there is no single tuple type which is supertype of all
supertypes. The types
<:Object:>, <:Object,Object:>, <:Object,Object,Object:>...
are all distinct types. The type whose instances are all the tuples, i.e., the
supertype of all tuple types, is actually SequenceType(Object).
<:Programmer, Engineer:> is a subtype of SequenceType(Employee). Conversely, the
sequence <@joe,@sam> could be an instance of the tuple type. Every instance of a
tuple type is also an instance of a sequence type. In general,
<:t1,...,tn:> SUBSETEQ SequenceType(t),
where t is any common supertype of t1,...,tn.
Note that we did not define a tuple instance designator different from a sequence
instance designator. Every instance of a tuple type is an instance of some sequence type,
and vice versa.
There are several distinct empty aggregates g for which Card(g)=0.
Associated with each index set is one distinct empty aggregate g for
which g[i]~NullCon is always True. That is, the empty aggregates for different index sets
are different objects. There is exactly one indexed aggregate whose index set is the empty
set and whose Arity is therefore 0. This indexed aggregate is different from the empty
set, which has no index set.
Since every object is an instance of multiple types (including all its supertypes),
every non-empty aggregate always contains objects of different types, yet it always
contains objects of the same type: they are all instances of Object.
Example: assume Dick is a student and Jane is a teacher. Then SET(:Dick,:Jane) is
simultaneously:
- A set of objects of the same type: Person, or Surrogate, or Object.
- A set of objects of different types: Student and Teacher, Man and Woman.
A bag type or a set type does not require that all instances be of the same type. It
requires that they all be instances of some specified type, in addition to whatever other
types they might have.
A given aggregate object is an instance of many aggregate types, corresponding to
combinations of the types to which the members belong. SET(:Dick,:Jane) is an instance of
SETTYPE(Object) and SETTYPE(Person); it also happens to be an instance of BAGTYPE(Object)
and BAGTYPE(Person).
TUPLE(:Dick,:Jane) is an instance of TUPLETYPE(Person,Person), TUPLETYPE(Object,
Student),... in fact, it is an instance of all tuple types of the form TUPLETYPE(T1,T2)
where T1 is any one of Object, Surrogate, Person, Student, Man, and T2 is any one of
Object, Surrogate, Person, Teacher, Woman.
All of the Dick and Jane examples proliferate further if they happen to have other
types as well.
The types to which an aggregate object belongs changes when the types of its elements
change. If Dick becomes a teacher, then SET(:Dick,:Jane) becomes an instance of
SETTYPE(TEACHER).
There are some natural subtype relationship among aggregate types.
SET(T) SUBSET BAG(T) for any type T.
SET(S) SUBSET SET(T) if S SUBSET T.
BAG(S) SUBSET BAG(T) if S SUBSET T.
LIST(S) SUBSET LIST(T) if S SUBSET T.
TUPLE(S1,...,Sn) SUBSET TUPLE(T1,...,Tn) if each Si SUBSETEQ Ti, with at least one Si
SUBSET Ti.
The subtype rule for tuples can be used to reduce overloading of multi-argument
operations to the same rules as defined for single-argument operations.
Note that this actually applies to all aggregates, accounting for content but not form.
The semantics of operations which yield indexed aggregates can be defined in terms of
the form and content of the result, i.e., its index set and the behavior of the Extract
operation [Section 11.2.1]. Thus, for example, the
semantics of sequence concatenation s0=Concat(s1,s2) can be defined by the arithmetic
expressions:
- i IN IndexSet(s0) = (i>0) * (i =< [Length(s1)+Length(s2)]),
i.e., the integer i
is in the index set of s0 if i is greater than 0 and not greater than the combined lengths
of s1 and s2.
- s0[i]=x <=> (i=<Length(s1) * x=s1[i]) + (i-Length(s1))=<Length(s2) *
x=s2[i-Length(s1)])
i.e., the i-th element of s0 is x if
- i=<Length(s1) and x is the i-th element of s1, or
- j=<Length(s2) and x is the j-th element of s2, where j=i-Length(s1).
As mentioned in Section 11.2.1, the number of
occurrences of an object x in an indexed aggregate g is given by
x IN g = SUM[i IN IndexSet(g)](g[i]=x).
For bags and sets, which have no index sets, results of operations can only be
characterized by the contents of the result. This takes the form of a "profile
expression" defining the occurrences of objects in the result in terms of the
occurrences of objects in the operands. As a simple example, the semantics of b0=b1 UNION
b2 is defined as a sum:
x IN b0 = x IN b1 + x IN b2.
or, using more compact notation,
(b1 UNION b2)(x) = b1(x)+b2(x).
- Add motivation and more examples. Say something here about the scopes of summations.
- Refer to detailed operations at end.
- Mention basis for arithmetic semantics of queries.
- While some of the expressions may seem elaborate, they involve nothing more than
addition and multiplication. The reader is urged to be open to the simple notions behind
all the Greek letters.
- Someplace we should also say something characterizing the types of the results.
There's a difference between extensional and intensional aggregates.
We have six terms for two concepts:
- Extensional aggregates are immutable literals. [ephemeral]
- Intensional aggregates are mutable surrogates.
The aggregates we have described so far are immutable. They don't change. Operations
which appear to change them should be viewed as replacing one with another. If we add one
to the second component of <Sam,17>, we haven't altered the tuple. <Sam,17> is
still <Sam,17>. What we have done is to replace <Sam,17> with <Sam,18>.
The immutable aggregates are ephemeral [Section 7.2].
Things like {Sam}, {Sam,1}, [Sam,Sam], <Sam, 1, Sam> are all known to exist exactly
whenever Sam is known to exist. Aggregate designators yield existing immutable aggregates.
The alternative concept of an intensional (mutable) aggregate is illustrated by
something like a team, which is thought of as a set of persons but whose identity is not
determined by the set, since there can be different people on the team at different times.
Furthermore, if the bowling team and the bridge team happened to have the same people,
they still aren't the same team.
Intensional (mutable) aggregates are thus modeled as explicitly created surrogate
objects which serve as carriers having extensional aggregates as their cargos.
Aggregate objects are like literals in that they are not explicitly created or
destroyed, and they are immutable, i.e., we might replace one with another, but we don't
change them. The following analogy might help clarify this:
Here's how literals work. If we assign Distance(AlphaCentauri) to be twenty-five
trillion miles, it doesn't mean we just created that number, even if nobody ever mentioned
that particular number before. We just need to have someplace to store this particular
reference to it. If the distance to another star happens to be the same number, it doesn't
mean we "created" that number again. And if a star moves, so that we change its
distance to be twenty-six trillion miles, we haven't altered the number twenty-five
trillion; we just replaced this occurrence with something else.
There are many expressions which might return (refer to) the same number: 2+2, 7-3,
length('abcd'), Sqrt(16), Successor (3), Age(:Spot), etc. None of these
"creates" the number.
Here's the analogy for aggregates. If we assign Children(:Tom) to be SET(:Dick,:Jane),
it doesn't mean we just created that set, even if nobody every mentioned that particular
set before. We just need to have someplace to store this particular reference to it. If we
assign Owners(:Spot) to also be SET(:Dick,:Jane), it doesn't mean we "created"
that set again. And if we sell the dog, so that Owners(:Spot) becomes SET(:Bob,:Ray), we
haven't altered SET(:Dick,:Jane); we just replaced this occurrence with something else.
There are many expression which might return (refer to) the same set: Children(:Tom),
Owners(:Spot), SET(:Dick,:Jane), SET(:Jane,:Dick), SET(:Jane,:Jane,:Dick),
Union(SET(:Dick), SET(:Jane)), etc. None of these "creates" the set.
"Query" means various things in the database literature. It is sometimes used
in the sense of a query language, meaning either just the retrieval operations or
the entire language (as in the language names "SQL", "OSQL", and even
"FOQL"); it sometimes refers to operations on sets or other aggregates in
general. The term is sometimes used in the narrower sense of a query operation
which selects things from a collection based on some criterion, often in a "select
... from ... where" syntactic form. Here we will use the term in this last sense: a query
is a specific operation which generates a collection of things from some other collection.
By "query semantics" we mean some formal specification of the results produced
by a query operation.
The semantics of queries should be defined in terms which do not depend on any
particular internal model of query execution.
We will describe queries purely in terms of external semantics, without reference to
any style of computing the results such as relational algebra or logical inference, using
only the operations described in Section 28.7. The
semantics of those operations, and hence of queries, is defined by arithmetic. The basic
semantics of query are thus independent of data model; dependence on data model is
principally reflected in the sorts of expressions which may occur within the query.
The basic Query operation is a combination of BagFilter and BagReplace:
Query(<b,'x,'w,'r>) = BagReplace(<BagFilter(<b,'x,'w>),'x,'r>),
which is intended to correspond to the familiar syntactic form
SELECT r(x) FROM b x WHERE w(x).
The following terminology and concepts are relevant:
- The expression b is a from-clause, whose value is the initial bag
which serves as the search domain. Unbound variables in the expression b are
evaluated before evaluating the query.
- The expression w is a where-clause or filter expression. Evaluation of
BagFilter(<b,'x,'w>) yields a secondary bag b2 such that b2(x)=b(x)*w(x).
If w(x)>1, this multiplies the number of occurrences of x.
- The expression r is a select-clause or result generator. The result of
the Query operation is a bag br which contains one occurrence of r(x) for each occurrence
of x in b2, i.e., br(y) = SUM[x](y=r(x) * b2(x)). The summation accounts for the fact that
distinct values of x may have the same value of r(x), hence all such values of x
contribute occurrences of r(x).
This definition of the Query operation imposes minimal requirements on the expressions
b, w(x), and r(x):
- b must return a bag.
- w(x) must return a non-negative integer for each element x occurring in b.
- r(x) must be defined for each element x occurring in b.
It is up to the orthogonal, model-dependent portion of a language specification to
define what constructs are allowed in these expressions and how the expressions evaluate
to the appropriate value. That includes such considerations as nulls, recursion, and the
treatment of logical operations in the presence of duplicates [expand this last point,
referring to Joseph's work]. If the result generator r is a sequence designator, then the
query result could be a bag of tuples.
DISTINCT and ORDER BY are obtained by appropriate applications of Distinct and BagSort.
GROUP-BY can be described as a double application (nesting) of Query, using BagGroup in
place of the inner BagReplace:
GroupQuery(<b,'x,'w,'g,'u,'h>)
= Query(<BagGroup(<BagFilter(<b,'x,'w>),'x,'g>),'u,'h,'r>)
=BagReplace(<BagFilter(<<BagGroup(<BagFilter(<b,'x,'w>),'x,'g>),'u,'h>),'u,'r>).
Figure 4 shows a stepwise representation:
------------------------ | BagFilter() | --------------- v ------------- | BagGroup() |
---------------- v ------------- | BagFilter() | ----------------- v ------------- |
BagReplace() |
---------------------------------------------------------------------------------------------------
Figure 4.
This can be visualized in the syntactic form
SELECT r(u) FROM b x WHERE w(x) GROUP-BY g(x) HAVING h(u),
The expression g is a grouping-clause, and h is a having-clause.
Figure 5 shows a stepwise representation:
------------------------ | FROM b x WHERE w(x) | | BagFilter() | --------------- v
------------- | GROUP-BY g(x) | | BagGroup() | ---------------- v ------------- | HAVING
h(u) | | BagFilter() | ----------------- v ------------- | SELECT r(u) | | BagReplace() |
---------------------------------------------------------------------------------------------------
Figure 5.
The value of GroupQuery is defined by the following steps:
- The initial bag is obtained by evaluating b.
- The first (inner) BagFilter applies the where-clause w(x) to b, yielding the secondary
bag b2 such that b2(x)=b(x)*w(x).
- BagGroup then applies the grouping clause g(x) to yield a bag bg (actually a set) in
which each element is a group uj. Each group uj is a non-empty bag containing all the
occurrences of each x in b2 having the same value of g(x), which is also the value of
g(uj). Subsequent operations have access to the groups uj as well as to the value of
g(uj).
The outer query now has the form Query(<bg,'u,'h,'r>), i.e., SELECT r(u)
FROM bg u WHERE h(u).
The having clause h(u) serves as a where-clause for the outer query. For each
evaluation of h(u), the variable u is bound to a group uj.
- The second (outer) BagFilter applies the having-clause h(u) to bg, yielding the bag bg2
such that bg2(u)=bg(u)*h(u).
- BagReplace then applies the select-clause r(u) to yield the query result br.
Consider the query
SELECT Salary(u) FROM Employee x WHERE Age(x)>30
GROUP-BY Salary(x) u HAVING Count(u)>2 AND Salary(u)>50000
which returns the salaries over 50000 which are earned by more than 2 employees over
the age of 30 [Figure 6]. For simplicity, there is only one
grouping operation g, namely Salary.
The example query will
- b = Extent(Employee).
- w(x) = Age(x)>30.
- g(x) = Salary(x).
- h(u) = Count(u)>2 AND Salary(u)>50000.
- r(u) = Salary(u).
The correctness of query transformations can be proved via arithmetic analysis. Such
analysis might also lead to the discovery of new transformations. To illustrate, we prove
the correctness of the familiar relational query transformation involving projection and
selection [Section 28.8].
Consider the projection
bp = pi [i1,...,in]b
The k-th element of a tuple y occurring in bp is given by y[k], and is equal to x[ik]
for some x in b. If we then select from bp using a selection criterion on this k-th
element, we have
bps = sigma [s(y[k])]bp = sigma [s(y[k])]pi [i1,...,in]b,
where s(y[k]) signifies a selection on y[k]. We are thus selecting on the k-th
component of a projection. The membership profile of bp is
bp(y) = SUM[x](b(x) * y[1]=x[i1] * ... * y[n]=x[in] ).
The membership profile of bps is
bps(y) = bp(y) * s(y[k])
= [ SUM[x]( b(x) * y[1]=x[i1] * ... * y[n]=x[in] ) ] * s(y[k]).
Now let's reverse the order of the operations. Since y[k]=x[ik], we have
s(y[k])=s(x[ik]), and an equivalent selection on b takes the form
bs = sigma [s(x[ik])]b.
Since bs has the same type (and hence the same index set) as b, we can still write the
projection as
bsp = pi [i1...in]bs = pi [i1...in]sigma [s(x[ik])]b.
The membership profile of bs is
bs(x) = b(x) * s(x[ik]).
The membership profile of bsp is
bsp(y) = SUM[x]( bs(x) * y[1]=x[i1] * ... * y[n]=x[in] )
= SUM[x]( b(x) * s(x[ik]) * y[1]=x[i1] * ... * y[n]=x[in] ).
If we simply rearrange terms, and substitute s(y[k])=s(x[ik]), we see that
bps(y) = s(y[k]) * [ SUM[x]( b(x) * y[1]=x[i1] * ... * y[n]=x[in] ) ],
bsp(y) = SUM[x]( s(y[k]) * b(x) * y[1]=x[i1] * ... * y[n]=x[in] ).
From the distributivity of multiplication over addition, we see that these are equal.
QED.
(Refer to other documents.)
(This should probably be correlated with the general concept of parameterized or
generated types.)
(Both the types and the instances are ephemeral. Defining the type designator makes all
the types recognizable, as well as all their instances.)
User-defined literals define the existence of such things as imaginary numbers or
geometric abstractions. The instances have eternal existence (which is why we call them
literals), but a mechanism has to be provided by which the instances can be denoted, i.e.,
designators. If a literal type has more than one designator, then equality between
designator expressions also has to be defined. [Default equality is based on equality of
arguments.]
Internal representations may or may not be specified. (Need to distinguish between
Imaginary(x,y) and Point(x,y). Whether the labels Imaginary or Point are stored is a
matter of implementation. We could think of these things as having oid's generated by some
rule.)
UDLTs are the same as SQL3 Value ADTs. They have the characteristics of literal types
mentioned above.
Essential characteristics:
- The types themselves are user-created surrogate objects.
- They are generally defined in terms of other types.
- Their instances may or may not have an explicit storage representation. (We may
associate storage hints with such types.)
- They may require definition of designator expressions for referring to instances.
- They may require a definition of equality to establish when two designators refer to the
same instance.
- User-defined literal types are generally disjoint from each other, unless otherwise
specified, usually in terms of sub/supertype relationships.
- User-defined literal types are not union-compatible unless they have a common supertype.
They may have several common supertypes.
Thus, for example, Rational(3,4) ¬= Imaginary(3,4) ¬= Rectangle(3,4) ¬= Ellipse(3,4)
¬= Point(3,4) etc. (May need to modify those examples to account for units.)
The following sections illustrate useful sorts of literal types which users might
define.
(E.g., even numbers, primes, "small" numbers, state and country names, etc.)
Factoids are things which can be used to represent instances of attributes or
relationships, in order to model attributes and relationships of attributes and
relationships. They are ephemeral objects, with designators. They come in several
equivalent forms, linked somehow via operation families. There are also some variant forms
of factoids.
A factoid is an ephemeral object which can be characterized by an n-ary predicate and
an n-tuple for which the predicate is true. It can be designated by something like
Factoid(<p,<x1,...,xn>>) (that's an ugly notation), which is null when
p(<x1,...,xn>) is not True.
The general idea is to express a property of an attribute or relationship as an
operation which takes a factoid as an argument and returns the property value. Some
unresolved problems:
- How do we aggregate factoids into types?
- How do we express the signatures of their properties?
- How does the implementation manage referential integrity when there is a stored
operation involving any ephemeral object?
Other notions of factoid correspond to <f,<x,y>> such that y=f(x). That's
not equivalent to the above notion for multi-valued operations. The operation family
equivalent of the above notion is more like <f,<x,y>> where y IN f(x).
Stay tuned.
Some objects have an implicit notion of "content".
But not all. (But in some models, these are the only kind of object.)
For these objects, operations such as Move, Copy, and Display are meaningful.
Some objects have a location property.
But not all. (But in some models, these are the only kind of object.)
For these objects, operations such as Locate and Move are meaningful.
Measured quantities such as distance and weight can be user-defined literal types
(domains?) in their own right, apart from the numbers used to measure them. Thus the
height of a person and the height of a door would be comparable, and union compatible,
regardless of units of measure. On the other hand, a person's height and weight would not
be comparable or union compatible, even if both were stored as integers.
Units of measure would be defined as properties, with equality specifications defining
the units conversions.
Two options are available when specifying types of columns in relational tables:
- Specify a base data type, e.g., Integer. All columns so typed are comparable and union
compatible.
- Specify a UDLT, such as Distance, together with "storage hints" specifying a
unit of measure and base data type, e.g., Distance in Meters as Integer. All columns typed
as Distance are comparable and union compatible, but columns respectively typed Distance
and Weight are not.
A column, property, or variable having a type such as Distance may always be assigned a
distance as its value. If the column, operation, or variable also has an associated unit
of measure and base data type, then it can also be assigned a numeric value, which will be
interpreted appropriately. Thus, if the Height property on Person was only typed as a
Distance, then Height(Tom)<-Height(Dick) is a meaningful assignment, but
Height(Tom)<-6.5 is not. On the other hand, if Height was specified as being a Distance
in Feet as Real, then Height(Tom)<-6.5 is a meaningful assignment.
CREATE LITERAL TYPE Distance d
InchMeasure -> Number;
FootMeasure -> Number;
MileMeasure -> Number;
...;
CONSTRAINTS
d.InchMeasure=12*d.FootMeasure;
d.FootMeasure=5280*d.MileMeasure;
...
DESIGNATORS
Distance_Inches(n Number): d.InchMeasure=n;
Distance_Feet(n Number): d.FootMeasure=n;
...;
EQUAL(Distance_Inches(x),Distance_Inches(y)): x=y;
...;
EQUAL(Distance_Inches(x),Distance_Feet(y)): x=12*y;
...;
(Angles: Similar treatment, with Degrees and Radians as two measurement attributes.)
The intent here is to think of physical quantities in terms of non-materialized types
and quantity designators in terms of materialized types. However, it turns not to be quite
that simple. There seem to be intermediate stages. Mapping a distance into a
distance-designator doesn't yet yield something material until we further specify how to
materialize the number and the units.
We use symbols to mention the things denoted by the symbols. When I
say that I was in Manhattan, you know that I just mentioned an island in New York. If I
asked you how long Manhattan is, you might tell me that it's about twelve miles. But what
if I want to mention - that is, talk about - the name of that island? If I ask you how
many characters there are in Manhattan, you might guess there are about two million.
That's because I'm using the name. If I want to mention the name, the
normal convention is to use a quoted form: How many characters in
"Manhattan"? Now the answer is nine. I use the 11-character sequence
"Manhattan" to mention the nine-character name of the island. I use the
nine-character sequence to mention the island.
It's somewhat analogous to asking whether 2+2 and 1+3 are the same. Yes, if we are
using these expressions to mention numbers; they both mention the same number. No, if we
are mentioning the expressions; they are different expressions.
What has this got to do with units? Watch carefully.
Good old Bill, his height is six feet.
What were the units of that? Feet.
What was that last question about? It wasn't about the distance, it was about the
designator.
Is Bill taller than Bruce? I don't know.
What was that last question about? It was about the distance, not the designator.
At the risk of getting too tedious, let me spell it out again. Designators and
distances are different. Sometimes we're talking about (mentioning) the designator, and
sometimes we're using the designator to talk about (mention) the distance.
How can we manage the distinction, to know which we're talking about when? A crude,
impractical solution is to use something like quotes. We could say that it doesn't make
sense to ask about the units in six feet, but we can sensibly talk about the units in
"six feet".
A more useful approach involves casting. We recognize that designators and distances
are different types of things. We have some operations which are defined on designators
but not on distances, i.e., the ones which return the number, units, or dimension. We also
have some operations which make sense on distances but not really on designators, e.g.,
for comparing or combining. We make such operations applicable to designators by invoking
the casting concept, saying that if a designator appears where a distance is required,
then we cast the designator into the corresponding distance.
This also ties in to the overloading notion, since casting always implies a form of
overloading. Given a casting function c12 from type T1 to type T2, then any function
defined on T2 is effectively also defined on T1. If x is an instance of T1, then f(x) is
defined as f(c12(x)).
So, what's the bottom line? As is often the case, we seem to have traveled a long way
around to come to a simple conclusion, but it's important if we've gotten it right.
Designators and distances are different things, both recognized in our type system.
(Why? Because there is not a one-to-one correspondence between them. There are many
designators for a given distance.) Distances only have opaque internal representations,
and have to be mapped ("measured") into designators before they can be exported.
Functions can be defined to return either distances or designators. Those that return
designators can be used where distances are required by virtue of casting. Those that
return distances can be used where designators are required if a default designator has
been established, or if an explicit mapping ("measurement") is applied.
We can make an interesting analogy between employees and distances if we assume that
oid's cannot be exposed.
A simple case arises when the default symbol for an employee is the employee number. It
can be used on output or input to designate an employee, but this may or may not be the
form in which employees are maintained internally.
Distance would be an analogous case if there was one standard unit for representing
distances, e.g., inches. Then any distance can be designated on input or output simply by
a number.
Now suppose we had more than one possible way to designate an employee, e.g., social
security numbers could also be used. Now we can't simply look at a number and know which
employee it designates. We need to know whether the number is an employee number or a
social security number. There are several general ways to do this:
- By a self describing notation, e.g., <123, Enum>, <123, Ssn>.
- Appropriate functional expressions. Suppose that UWC is a variable containing the
internal representation of an employee who is the current United Way Coordinator.
There is a one-to-one correspondence between <123,Enum> and EmpWithEnum(123).
They both designate a certain employee. However, we may or may not be able to think of
those two constructs as identical, since one is a tuple while the other is an expression.
This distinction might give us trouble.
It might be interesting to bridge the two notations with some functional equivalence.
Roughly, we might like to say that
EmpDesBy(<x,y>) ::= GetFunc(y)(x),
where GetFunc(y) returns the EmpWithEnum function if y=Enum and EmpWithSsn if y=Ssn.
Thus
EmpDesBy(<123,Enum>) = GetFunc(Enum)(123) = EmpWithEnum(123).
(Develop the analogy here with distances in different units. Establish here the idea of
units as functions analogous to Enum and Ssn.)
Given an employee number, we may want to know the corresponding social security number,
and vice versa.
With the functional notation, this involves straightforward composition of functions:
E2S(e) ::= Ssn(EmpWithEnum(e)),
S2E(s) ::= Enum(EmpWithSsn(s)).
This is a two-stage process, always getting the internal representation of the employee
as an intermediate result. However, let's imagine that there is some computational
algorithm e=f(s) which relates employee numbers and social security numbers, e.g., the
company defines employee number to be twice the social security number. (Don't ask me why.
It may not be practical, but it facilitates the analogy.)
Now we can define the conversions as one-step processes, bypassing the internal
representations:
S2E(s) ::= f(s),
E2S(e) ::= f¯¹(e).
However, these are still logically equivalent to the previous forms.
The analogy with units conversion is pretty obvious.
An interesting analogy can also be made with a more abstract notion, namely geometric
points in two dimensions. A measurable quantity such as a particular distance has an
abstract existence in its own right, just as does a point in a two-dimensional space.
These things aren't symbols, or even numbers, so there is no intrinsic way to represent
them in symbols. (They could be represented in a broader set of symbols, if we included
diagrams.)
These things do have various properties, which can be used to represent them uniquely.
Thus a point has an x-coordinate, a y-coordinate, an angle, and a magnitude. [Is that
appropriate terminology for polar coordinates?] There are functions which can be applied
to a point (in some opaque internal representation) to return any of these properties.
Conversely, certain functions map values to points, and can be used to uniquely designate
the points. Thus Rect(x,y) designates a point whose x- and y-coordinates are x and y,
while Polar(x,y) designates a point whose angle and magnitude are x and y. (Generally not
the same point, obviously.)
Similarly, units serve as a set of functions which map a distance into different
numbers. Thus Inches maps a particular distance to a particular number, while Feet maps
the same distance to a different number. The inverses of these functions can be used to
uniquely designate specific distances. Thus InchDistance(12) designates a distance, while
FeetDistance(12) designates a different distance.
If these designators are the only way to uniquely refer to the abstract item, then we
need some criterion to determine whether two designator expressions refer to the same
item. First of all there is a trivial set of rules of the form:
Rect(x1,y1)=Rect(x2,y2) <=> x1=x2 AND y1=y2, etc.
InchDistance(x)=InchDistance(y) <=> x=y, etc.
More interesting are the equivalences of the form
Rect(x,y)=Polar(a,m) <=> tan(a)=y/x AND m=sqrt(x²+y²).
InchDistance(x)=FeetDistance(y) <=> x=12y.
(Be sure there's no confusion about signs and quadrants.)
Consider geometric points in a two-dimensional space. All such points exist, and they
are immutable. They may be referenced (designated) by either rectangular or polar
coordinates. Whether they are represented internally in one form or the other is a matter
of implementation, not specified. (If specified, it should be considered an implementation
hint.) What is required, though, is some definition of when two designators are equal. For
example...
CREATE LITERAL TYPE GeometricPoint p
Xcoord -> Distance;
Ycoord -> Distance;
Magnitude -> Distance;
Angle -> Angle;
CONSTRAINTS /* post-conditions? */
p.Magnitude=Sqrt(p.Xcoord*p.Xcoord + p.Ycoord*p.Ycoord);
p.Ycoord=p.Xcoord * Tan(p.Angle);
DESIGNATORS
RectPoint(x Distance, y Distance): p.Xcoord=x, p.YCoord=y;
PolarPoint(m Distance, a Angle): p.Magnitude=m, p.Angle=a;
EQUAL(RectPoint(x,y),PolarPoint(m,a)): m=Sqrt(x*x+y*y), y=x*Tan(a);
The following are implicit:
EQUAL(RectPoint(x1,y1),RectPoint(x2,y2)): x1=x2, y1=y2;
EQUAL(PolarPoint(m1,a1),PolarPoint(m2,a2)): m1=m2, a1=a2;
Note that such points are different from "movable" points which can have
different locations at different times, and may even occupy the same location. Such points
will be described later as "carrier" objects which have the above sort of
geometric points as the values of their "location" property. (If two circles are
concentric, are their centers the same point? We can say no, they are two distinct movable
points which happen to be located at the same geometric point.)
These are interesting because they introduce subtypes, including overlaps. Develop
examples involving plane figures, convex figures, polygons, regular polygons,
quadrilaterals, parallelograms, trapezoids, rhombuses, rectangles, squares, rounded
figures, ellipses, circles. Complex inheritance patterns.
Also note an interesting equality rule: Rectangle(x,y)=Rectangle(y,x).
The implementation constructs which are hidden from users behind an object system
interface include program code for executing requests, query processing and optimization,
data structures, data placement and clustering, and pointers.
The notion of a request being a "message" to a single recipient, where that
recipient is the performer of the request, really seems to be an implementation concept,
not visible to the user. The user doesn't see the difference whether a request to register
a student in a course is a message to the student or to the course, or even if it becomes
a message to a Registrar application or a DBMS which actually performs the service.
Syntactic forms such as Student.Register(Course) or Course.Register(Student) don't have
any real operational significance. (Possible exceptions: inheritance patterns, content
notions.)
This parallels the classical/generalized distinction, augmented with the possibility
that the performer might be none of the objects mentioned in the request.
An operation may have several sets of retrieval and update execution specifications,
each associated with a different class. Notes:
- Execution specifications and classes should not be exposed to users.
- Objects are grouped into classes as well as types. The grouping mechanism (criterion)
should be transparent to users. Explain possible mechanisms.
- Establish correspondence between classes and types. A type definition owns the
behavioral semantics, while a class provides the executions specifications for (some)
operations owned by a given type.
- Explore the similarity between classes and Pegasus underlying types.
- Clarify correspondences between facets, implementations, types, and classes.
- Talk about how the class is determined for new objects. Use the OMG formulation:
portability etc. are enhanced to the extent that this is transparent to the application.
An experimental example:
The example concerns circles for which the radius and diameter are both defined.
Different implementations might store one or the other, or both.
CREATE TYPE Circle
OPERATIONS (
Center -> Point ASSERTABLE;
Radius -> Number ASSERTABLE;
Diameter -> Number ASSERTABLE;)
CREATE CLASS Circle1 FOR Circle
OPERATIONS (
Center AS STORED (format);)
CREATE CLASS Circle1a SUBCLASS OF Circle1
OPERATIONS (
Radius AS STORED (format);
Diameter(x) AS 2*Radius(x),
ASSERTION x,y: Radius(x)<-y/2;)
CREATE CLASS Circle1b SUBCLASS OF Circle1
OPERATIONS (
Radius(x) AS Diameter(x)/2,
ASSERTION x,y: Diameter(x)<-2*y;
Diameter AS STORED (format);)
Under this schema, all instances of the type Circle use the same implementation for
Center, hence all circles are instances of the class Circle1. Instances of the subclass
Circle1a have their radius stored and diameter computed, while instances of Circle1b have
the opposite implementation. Every instance of the type Circle must also be an instance of
one of the leaf classes Circle1a or Circle1b.
Application logic is sensitive only to the specification of the type Circle, and not to
the specification of any of the classes. The keyword ASSERTABLE tells the application that
new values may be assigned, while remaining neutral as to whether and how the values are
stored.
Notes...
In performer models, the performer object must be explicitly designated in the request.
Choosing the performer object may or may not be a service provided by the object system
infrastructure.
A common paradigm: A performer object has a location property and a set of exclusively
owned methods. A request is executed by sending a message to the performer object, causing
a method to be dispatched.
Whether or not a request is so executed should be transparent to the user perspective.
Choosing and finding a performer to execute a specific operation may be based on the
class of the argument, as well as availability of performers and similar resource
constraints (e.g., a trader concept). If not local, then a message with arguments has to
be shipped to the performer.
Describe C++ and CORBA-style models. Mainly performer/addressing models.
Reason for including it here: it is the main alternative, in most people's minds.
Reason for including it here: it is another significant alternative, in many people's
minds. I'm not even sure what would go here, though I'm pretty sure this category exists.
These models are based on some interaction paradigm other than operation invocation or
messaging. They have notions of "links" between objects over which
communications flow freely, or "interaction points" which have some sort of
gating effect on subsequent activities. (Is "Petri net" a relevant concept?)
Maybe interaction paradigms is another dimension in which to classify models.
An OSQL Tuple is a 0-sequence, and an OSQL List is a compact 0-sequence [Section 29.5.3].
0-sequence designators yield sequences using zero origin, i.e., having index set
0,...,Arity(s)-1. A ShiftLeft operation maps a sequence into the corresponding
0-sequence (essentially by decrementing each integer in the index set), so that
s[i]=ShiftLeft(s)[i-1]. A 0-sequence designator can then be defined as
0Seq(<e1,...,en>) = ShiftLeft(<e1,...,en>).
A compact 0-sequence designator can then be defined as
Comp0Seq(<e1,...,en>) = 0Seq(CompSeq(<e1,...,en>)).
The designators can take zero or more expressions as arguments.
The OSQL Tuple instance designator is a 0-sequence designator, while the OSQL List
instance designator is a compact 0-sequence designator. (It seems to follow that a
tuple with no null elements is a list, and the Tuple designator constructs a list if none
of the arguments are null. Is it true that Tuple(1,2)=List(1,2)?)
The from-clause [Section 12.2] in an OSQL query is
either a single type and variable t x or a list of types and variables t1 x1,...,tn xn.
In the case of a single type, casting [Section
10.4.1.3] allows the single type t to be replaced by Extent(t) to serve as the initial
bag. The variable x can serve as the variable for the where-clause and select-clause.
With the list of types, the initial bag is effectively defined as the cross-product [Section 28.7.3] of the types which, due to casting, is
the cross-product of the extents of the types. To provide a variable for the where-clause
and select-clause, we introduce a new variable x which ranges over the tuples in the
cross-product. The variable x is defined such that i(x)=xi, so that each specified
variable xi corresponds to the element in a tuple which comes from ti. Thus a query of the
form
SELECT FROM T1 x1,...,Tn xn WHERE w(xi,...,xn)
can be interpreted as
SELECT FROM Xprod(<Extent(T1),...,Extent(Tn)>) x
WHERE w(x1,...,xn) AND x1=1(x) AND ... AND xn=n(x).
For a basic query, the result generator is always a sequence generator, so that the
query result is a bag of tuples.
This section covers the basic relational model, i.e., without object orientation.
Goals:
- Describe semantics in terms of FOQL.
- Show SQL language bindings.
- Explore how OSQL might be (or become) a superset of SQL.
A tuple table is a named carrier object whose cargo is a tuplebag [Section 28.8]; hence the CargoType of a table is of the
form BagType(TupleType(t1,...,tn)). Its bag of rows is the value of the Cargo operation;
the Cargo operation could also be called Rows. The type TupleType(t1,...,tn) is
the RowType of the tuple table. Thus, in general, an operation which is defined
on tuplebags can be applied to a table; it will be applied to the cargo of the table.
In a "pure" relational model we would have sets rather than bags, and the
types ti would be restricted to atomic (non-aggregate) types.
We treat a tuple table as having numbered columns. A tuple table has an associated
sequence of distinct character strings which serve as column labels c1,...,cn, with ci
referring to the i-th column of the table. A given label may be used for different columns
in different tables. The operation ColNum(table,column) maps a table and column
label into an integer.
Thus, if x is bound to a row (tuple) in a tuple table t, the element in column c can be
referred to as ColNum(t,c)(x), using the i(s) access notation for elements of sequences [Section 11.2.1], [Section
29.5].
Note that the column labels are not in the index set of the tuples [Section 29.5.2], since tuple identity is not affected
by column labels. Tuples from different tables, with different column labels, can be
equal. Hence tuples are different from records [Section
29.5.4].
To summarize, the type TupleTable is defined with the following properties:
Symbol: Table->Char; /* table name */
RowType: Table->TupleType;
Rows: Table->BagType(RowType); /* the Cargo operation */
Columns: Table->ListType(Char); /* plus a uniqueness constraint */
[TupleType is a subtype of Type whose instances are all the tuple types.]
Note that the definition of Rows stretches our model a bit. RowType is not a specific
type. The definition should be written in the form Rows: Table->BagType(RowType(b)),
where b is the table being defined.
If x is an instance of the RowType of a tuple table b, then insertion and deletion of
the tuple are achieved by Add(<b,x>) (or SetAdd(<b,x>)) and
Remove(<b,x>) [Section 28.7.2].
For queries [Section 12], the initial bag in the
from-clause is given by one or more tuple tables, with repetition allowed. If a single
table, then the initial bag is just its cargo, i.e., a bag of tuples. As the variable x is
bound to each tuple, its elements can be simply referenced as 1(x), 2(x), etc. (The
challenge with SQL syntax is to define the column names as having these numeric values.)
When more than one table is specified, the initial bag is the unflattened cross-product
[Section 28.7.3] of their cargos. If there are two
tables with representative tuples <y1,y2> and <z1,z2>, then a representative
tuple in the initial bag would have the form <<y1,y2>,<z1,z2>>. As the
variable x is bound to each such tuple, an element such as z1 can be referenced as
1(2(x)), i.e., the first element of the second element of x, corresponding to the first
column of the second table. In general an element may be referenced as i(j(x)), where j
refers to the j-th table in the cross product and i refers to the i-th column of this
table.
Notes...
Mainly we need to find ways to map various syntactic constructs into the form i(j(x))
for referring to the i-th column of the j-th table. The main problems: column names in
queries, dot notation, and implicit arguments.
Table names (or correlation variables - is that the right term?) should take in integer
values corresponding to their relative position in the FROM list.
To deal with dot notation and implicit arguments, we can allow c=x.c=c(x).
There might be some ambiguities, which should be considered a problem with the SQL
syntax.
Pay special attention to Select *.
Should also check other aspects of SQL syntax.
Notes...
This section will deal with an object-oriented superset of the relational model,
intended to converge with SQL3 (a moving target which we hope to influence). Goals of this
section:
- Describe semantics.
- Show extended SQL language bindings.
- Show convergence with OSQL.
There are two possible essential extensions:
- Allow elements of tuples to be other than literals, i.e., let them be instances of
arbitrary types.
- Allow rows themselves to be arbitrary objects, i.e., not necessarily tuples.
The first extension seems inevitable. [Is there anything of interest to be said about
it?] The second could be simulated with the first, allowing a table to consist of a single
column, with each row being a tuple containing a single arbitrary object. However, it gets
more difficult to provide uniform treatment of tuples and objects in tables.
Main issues:
- Are non-tuple tables supported?
- What sorts of types may be defined? [Not yet discussed in this document.]
- How are their extents managed?
The row type of a non-tuple table may be a separately defined type t, i.e.,
something other than a tuple type. The cargo type would then be BagType(t).
Specific operations defined on the row type t play a role analogous to column names.
While c(x) refers to the c-th element of the row object x in a tuple table, f(x) refers to
the value of f applied to the row object x in a non-tuple table. Hence non-tuple tables
don't need declared column labels. We could say that such operations appear to be the
columns of the table.
For queries over multiple tables, the form i(j(x)) still applies, with j still being
the j-th table in the cross product. If this is a tuple table, then i is an integer (or
column name) referring to the i-th column; otherwise, i is an operation to be applied to
the row object.
To summarize, the type Table is defined with the following properties:
Symbol: Table->Char; /* table name */
RowType: Table->Type;
Rows: Table->BagType(RowType); /* the Cargo operation */
TupleTable can then be defined as a subtype, with the following added or redefined
properties:
RowType: Table->TupleType;
Columns: Table->ListType(Char); /* plus a uniqueness constraint */
If the type Person is defined with properties Name, Age, and Address, then
CREATE TABLE B1 OF Person
creates a non-tuple table whose RowType is Person and whose columns appear to be
labeled Name, Age, and Address. Note that this is not a table of tuples. However,
for query syntax, it will behave much like one.
In contrast,
CREATE TABLE B2 OF Name Char, Age Interval
is equivalent to
CREATE TABLE B2 of TupleType(Char, Interval) Columns(Name, Age),
creating a tuple table whose columns are labeled Name and Age. Its RowType is
TupleType(Char,Interval). Name and Age are constants equal to 1 and 2 for indexing into
tuples of this table. The terms w.Age, Age(w), w.2 and 2(w) all refer to the second
element of a row w. (In SQL query syntax, a column label standing alone would not be
treated as a constant, but as a reference into a row. Thus Age alone does not mean 2 but
w.Age, i.e. Age(w).)
Although query behavior of the two tables is similar (identical?), there are crucial
differences in update behavior. What can be inserted into table B1 are persons. If w is an
element (row) of table B1, then updating Age(w) updates the age of a certain person,
wherever that person occurs. (One could imagine that the age of persons is maintained in a
table of ALL Persons [Section 21.3], such that the
value of the Age property is inherited from this table and updates of Age propagate back
into this table.)
What can be inserted into table B2 are any tuples of type <Char, Interval>. They
can be the name of a book and the age of a horse, or the text of a memo and the duration
of your last vacation, or <"Spflzk", 9090909>. Even if <Name(p),
Age(p)> is inserted, it has copy (snapshot) semantics. Updating the second element of
this tuple does not change the age of any person.
For any object type T, it is possible to create at most one TABLE OF ALL T, i.e.,
CREATE TABLE B0 OF ALL T;
This table contains the extent of T, i.e., all instances. It is a set. Inserting a new
instance into any other Table of T will insert it into this table if not already there.
Persistence is an orthogonal issue. Some other mechanism is needed to indicate whether
an object is to be treated as transient or persistent. Transient instances of T will be
deleted from every Table of T at the appropriate time, such as end of session.
This provides a model of where the master copies of recorded properties live. A Table
of ALL T contains the recorded properties specifically defined on T for all instances of
T.
Every Initialize (possibly invoked by New) makes an entry, whether the thing is going
into a table or a variable. In some sense, a variable of type T behaves like a table of
type T which can have at most one row, except that it is not a Bag(T). (The Initialize
operation is one that initializes the relevant properties of an object when it becomes an
instance of a type.)
(It might be necessary to provide other tables for relationships, i.e., extensions of
multi-argument operations.)
A SELECT clause of the form SELECT se1...sen yields a collection of elements, where the
elements are of type TupleType(T1...Tn), where Ti is the type of value returned by sei.
When the se1...sen are simply variables, then this is just a projection.
We can choose to treat SELECT * in several ways, depending on what interpretation we
attach to its behavior today.
When selecting from a single tuple table, e.g., SELECT * FROM B2, the result would be
as today: a set of <Char,Interval> tuples.
When selecting from a single object table, e.g., SELECT * FROM B1, the result could be
- A set of Person oid's.
The interpretation here is "select everything" that
B1 contains. What B1 contains is Person oid's. Note that if x is bound to a member of this
query result, one can still get Name(x) and Age(x).
- A set of <Char,Interval> tuples.
The interpretation here is "select all
columns", or "select all properties". These tuples will lose any semantic
association with persons, just being snapshots of some names and ages. For SELECT
DISTINCT, people having the same name and age will be collapsed into a single tuple.
- A set of <Person,Char,Interval> tuples, with the first element being the oid of a
person, and the other two being snapshots of the person's Name and Age.
The motivation
here is to retain the association with persons. However, the last two elements will still
be snapshots.
The first alternative is recommended.
The result of SELECT * when selecting from multiple tables depends in part on the above
choice. If the recommended alternative is adopted, returning the flattened form of the
secondary collection is probably the most consistent.
Perhaps the most fundamental distinction between object models is whether objects are
perceived as performers or participants. Suppose that a student counseling service (human
or automated) wishes to register Sam in the Algebra course. The user might perceive this
as a request for a Register operation in which Sam and Algebra participate,
perhaps written as Register(Sam,Algebra). The requested service might be performed
by an object corresponding to Sam, by an object corresponding to Algebra, by a Registrar
application object, or directly by a DBMS object which records Sam's registration in
Algebra. The requester might not even know that the Registrar or DBMS objects exist.
The "participants" in the user's request are Sam and Algebra. The
"performer" might be Sam, Algebra, the Registrar, or the DBMS. Thus, in general,
the performer may or may not be one of the participants mentioned in the request.
Sometimes the application programming language imposes a "performer-oriented"
syntax, e.g., Sam.Register(Algebra) or Algebra.Register(Sam), but even then the actual
performer might be something else, i.e., the Registrar or the DBMS rather than Sam or
Algebra. Similarly, a user at a graphical interface might drag a document icon to a
trashcan icon (the two participants), causing the service to be performed by a file
manager object.
Some facility in the system may have to transform a user's request of the form
Register(Sam,Algebra) into a performer request such as Registrar.Register(Sam,Algebra) or
DBMS.Register(Sam,Algebra). This may even cascade to another level, which recognizes
different copies of the Registrar application at different sites as being distinct
objects, and selects one copy to service the request. There are thus at least two object
models involved in the registration scenario, requiring a cascading of interfaces [16, 17]
to map between them.
A participant model does not distinguish between performers and participants, while a
performer model does. The distinction is relative to a particular request; a performer for
one request might simply be a participant in another. In a typical performer model, only
certain objects can play the role of performer, and most model facilities are oriented
toward those objects.
There are a number of other distinctions which roughly parallel the
performer/participant distinction [Figure 7]:
--------------------------------------------------------------------------------------
| Performer Models | Participant Models |
|=========================================|==========================================| |
Request | | | ------- | | | Message to one target object | Operation applied to one or
more | | (the performer). | participant objects. | | This is the "classical"
object model. | This is the "generalized" model. |
|-----------------------------------------+------------------------------------------| |
Request Syntax | | | -------------- | | | Performer.Operation(Participants) |
Operation(Participants) |
|-----------------------------------------+------------------------------------------| |
Objects Represent | | | ----------------- | | | System components & resources |
Enterprise entities. | | (applications, clients/servers, | | | chunks of code, chunks of
storage, | | | files, tables, tuples, data "frames"). | |
|-----------------------------------------+------------------------------------------| |
Object Granularity | | | ------------------ | | | Coarse, large. | Fine, small. |
|-----------------------------------------+------------------------------------------| |
Role of Infrastructure | | | ---------------------- | | | Locate performer, deliver
request, | Determine performer, | | manage parameters. | then locate it, etc. |
|-----------------------------------------+------------------------------------------| |
Method Ownership | | | ---------------- | | | Exclusively owned by performer type. |
Jointly owned by participant types [13]. |
|-----------------------------------------+------------------------------------------| |
State | | | ----- | | | Disjointly partitioned between objects. | Could be shared among
objects. |
|-----------------------------------------+------------------------------------------| |
Relationships | | | ------------- | | | Separate constructs. | Could be multi-argument
operations. |
|-----------------------------------------+------------------------------------------| |
Localization | | | ------------ | | | Object is at one node, state is a | Object can be
dispersed, with state and | | contiguous "chunk". | services scattered (not just
replicas). |
--------------------------------------------------------------------------------------
Figure 7.
This is not a strict partitioning. Various object models exhibit these characteristics
in various degrees and combinations.
Note that both performers and participants can have associated behavior.
The role of OODBMS is ambivalent. Some have performer models, some have participant
models.
Addressing includes concepts of location as
- Nodes in a network.
- Storage media and locations within them.
- Abstract address spaces in a computational context.
Objects are not subject to the physical laws governing material things, which would
give them a location in physical space and forbid them from being in more than one place
at a time. In the first place (pun?), we should more precisely think of an object as
something in a computational system which represents something else. Thus we might say
that a person is represented by an object in a computational system, rather than that the
person itself is the object. In the second place, many of the things being represented are
themselves concepts rather than material things, e.g., the United States, the sales
department, the American flag, the Bible, Gone With the Wind, English, SQL, the
color green, and the number seven. None of these is a physical object subject to the
constraints on material things.
However, there is a more pragmatic concern which does motivate a sense of location
within the address space of a computational system. In order to avoid thinking about
problems of replica synchronization, it is useful to assume that there is only one
"master copy" of each recorded property of an object. Thus there should only be
one master copy of the fact that Sam's salary is $50,000. If we imagine it to occur
anywhere else, it is a "view" of this master copy. Any update to Sam's salary
updates this master copy, which is immediately perceived in all views of it (subject to
the appropriate transaction protocols). We also imagine that Sam's salary can be obtained
regardless of how one has obtained Sam's identifier (subject, of course, to authorization
constraints), the request being logically mapped into a reference to this master copy.
Note that it is not the value $50,000 which is to be in only one place, but the fact
that Sam's salary is $50,000, i.e., the association between Sam's identifier and the value
$50,000.
There is a related concern with how one "finds" such properties in a
computational system. A simple addressing model might require all recorded properties of
an object to be maintained in one contiguous region within the address space, which we can
call a "cell". In this case, the address of this cell can serve as the
identifier for the abstract object, i.e., the identifier is a "pointer" to the
object. In order to find Sam's salary, one simply takes Sam's identifier as a pointer to
Sam's cell, which contains his salary value along with his other recorded properties.
At a very abstract level this notion makes sense, but it runs into difficulties as we
try to map it more closely into real addressing in real address spaces. Real address
spaces have to be concerned with the size and formatting of such cells, and with efficient
packing and clustering of cells on various primary and secondary storage devices. The
abstraction of a cell needs to accommodate changing sizes of a property value over time
(some collection-valued properties can be quite huge). A cell needs to accommodate all the
properties of the object, relative to all the types to which the object belongs, and needs
to accommodate addition or removal of properties as the object gains or loses types, or as
the types themselves are redefined. Furthermore, a relationship between two objects might
plausibly be maintained in the intersection of their cells, suggesting complex overlap
among cells.
Thus at some point the correspondence between identifiers and pointers breaks down. We
may still preserve some notion of there being only one master copy of each recorded
property of an abstract object, but we may give up the model of these all being clustered
in a single cell. At this point the identifier no longer serves as a pointer, and other
addressing mechanisms are required. For our purposes these are matters of implementation,
a level below the level at which we define the semantics of our information model. To be
realized, of course, such semantics do have to be mapped into physical address spaces and
accessing strategies.
To illustrate, it is sometimes held that collecting all properties of an object in one
place characterizes object-oriented models, while clustering all salaries in one place
(e.g., a column of a table) characterizes relational or functional models. We are here
trying to define a semantic model at a level which is neutral to such distinctions.
Applications written at this level can be neutral to such implementation alternatives.
The following is a sampling of some other significant differences:
- Which of the following are objects?
Literals, aggregates, tables, applications,
users, icons, types, classes, operations, methods, attributes, relationship, factories,...
- Object introduction:
- Objects are created, made instances of types, and acquire corresponding interfaces by
explicit operations of the object system, or
- Independently existing objects are accessed by the object system, which has to discover
their types and interfaces.
- Identity:
- Based on oid's? Format? Scope of uniqueness?
- Can oid's be held outside the object system, with guaranteed meaning on future use?
- Can objects have several (synonymous) oid's?
- Is x=y testable?
- How do oid's relate to naming systems?
- Data structure:
- Expose more complex data structure, or
- Hide structure behind behavioral abstraction.
- Behavior: is there a distinction between behavior specification and implementation?
Which corresponds to methods?
- Types:
- One level vs. subtyping.
- Single vs. multiple (immediate).
- Changeable?
- Are extents maintained?
- Various definitions of the difference between types and classes.
- Basic data types.
- Various inheritance notions (single/multiple, class/type, blocking, instance vs.
property, delegation, ...)
- Treatment of attributes and relationships.
- Various approaches to containment, aggregates, composite objects.
- Query (yes/no, different query models; is it really an OO issue?).
- Single performer per object?
- All services for a given object are provided by one performer (e.g., a document is
associated with one word processor for all services). All requests involving this object
can be routed to the same performer.
- Services may be provided by different performers (e.g., independent performers for
editing, displaying, and printing a document, possibly at different locations). Choice of
performer may depend on service requested.
Object models differ for a variety of reasons. Perhaps the most important is that
different goals are being pursued by various object-oriented facilities:
- Interoperability.
- Portability.
- Extensibility.
- Code reuse.
- Communication/distribution.
- Complex applications.
- Persistence of program data.
- Enterprise modeling.
- System resource management.
There are also business, political, and cultural reasons. Vendors have vested interests
in their products. Users need to protect their investments in legacy applications,
hardware, software, and programmer training. Researchers become committed to a certain
line of development. People have learned to think in the metaphors of certain languages
(C++, Smalltalk, CLOS, SQL, etc.). Nationalism plays a role. People have different views
of the role of database, e.g., as a repository of structured data vs. an interface through
which users manage information.
The following scenario illustrates a variety of requirements on object models. Key
points to keep in mind:
- Providing a service to a user typically involves the interoperation of a number of
system and application interfaces.
- There may be different objects involved at the different interfaces, with mappings among
them.
- Different features of the object model may be required at the different interfaces.
Requested services are often provided via cascading interfaces, frequently involving
different objects at each interface. Objects may be categorized as "visible'' or
"invisible'' with respect to a particular interface. The visible objects are
identified and manipulated at the interface. The invisible objects are not, even if the
user is aware of their effect on the behavior of the visible objects.
The object model is multi-purpose, designed to be applicable to a variety of areas such
as user interfaces, application interfaces, network management, etc. Different areas may
use different components from the model, and may involve different populations of object
types and instances. This is illustrated in the following scenario:
At a graphical user interface, a user manipulates presentation objects such as icons
and windows. The user may directly create and destroy icons and windows; change their
size, position, and color; convert icons into windows and vice versa; manipulate text and
graphics appearing in the windows; and so on. As much as possible, for the user's
convenience, the GUI tries to maintain the illusion that such activities are manipulating
a real thing, such as a document. Occasionally, however, the user must realize that the
icon is not the document, just as a photograph or TV image is not the real person; you can
draw a mustache on the photograph or turn the TV image green without altering the person.
The user may notice that he has several icons for the same document in different desktops
or folders; several icons can't be the same thing as one document. He knows that editing
the text in a window does not alter the "real'' text hidden under the interface until
he issues a "save'' request; until then, the real text is available to refresh the
window. He is more keenly aware of the difference if he can open several windows on the
same document and edit them differently, seeing two different versions of the document at
the same time -- neither one being the real text.
At the outset the GUI user may identify the underlying document when he requests a
window to be opened on it. He knows that save and restore requests involve that document.
But the document is largely invisible; the objects the user deals with are the icons,
windows, and their contents at the interface. Thus the user is aware that the icons and
windows in the GUI are distinct objects from the documents they represent and map to.
Another interface may define the semantics of an application. It could be neutral to
the user interface, being usable from a variety of command-line or graphic interfaces. A
publishing application may support requests to create or destroy an article, assign
writers to it, specify its subject and planned length, schedule it for a certain issue of
a magazine, sketch its geometric layout - long before any text is written. At this
interface, users don't think that assigning a writer to an article is a message "to''
either the writer or the article. Similarly, scheduling the article for a certain issue is
not a message "to'' either the article or the issue. These users don't have any
notion of "where'' an issue or a writer is, and it doesn't make sense to move them.
The notion of moving an article only makes sense with respect to its position in a
magazine issue, not within the computer system. Thus at these interfaces objects may
appear to jointly own operations and to be dispersed in various ways.
Information might be maintained as a complex combination of data and procedures. For
some articles, the length might be a simple property assigned or altered 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.
Different users have different assumptions about what an article "contains''. When
a writer or copy editor opens the document, he expects to see its text. (But if the
magazine has regional or international editions, there may be different versions of the
text.) When the layout editor opens the document, he expects to see a graphic image of its
shape in the magazine, probably without text. The librarian expects to see a title,
authors, publication data, abstract, and keywords. The reprint manager expects to see an
inventory, price, page count, and order history. Thus the notion of the
"content" of an object may be different for different uses.
All these users are dealing with the same article as an identifiable object. To many of
them, the text of the document is just an incidental property.
Requests at this application interface map into requests at a lower level which deal
with computational resources. A request to edit the text of an article translates to the
invocation of a certain editor with a certain text file. They have to be identified,
found, brought to a common work site, dispatched, and so on. The same happens with a
request to rearrange the layout of the article, or to change the assigned writers, or to
reschedule it to a different issue. Each such request may involve different units of
program and/or data, possibly at different locations. The text file, layout file, editor
program, and graphics package are all different objects from the article itself. The
program and data units are objects involved in providing these services, but they are not
visible to users of the publishing application interface.
The existence of distinct objects at the various levels is illustrated by the various
things a user might intend when he slides an icon around the screen:
- He might simply be rearranging the appearance of his desktop.
- He might be moving an article to another spot in the magazine, perhaps to a different
issue.
- He might be trying to move the text file from one computer to another.
In summary, at any given interface there are:
- Visible objects which are identified and manipulated at the interface.
- Invisible objects whose behavior may affect behavior at the interface, but are not
directly identified or manipulated at the interface.
Different interfaces may support different objects, and even different kinds of objects
with respect to other categorizations. Objects at one interface may be dispersed, being
mapped into coherent objects at a lower interface. Thus there may be different object
models at the different interfaces. Between interfaces there are applications (services)
which map from one level to another. A GUI service maps from user interface actions to
publication manager requests. The publication manager application in turn maps these to a
computational resource interface. This may in turn cascade down through several more
layers of implementation and communication services.
Applications can interoperate along the following dimensions:
- "Horizontal" peer-to-peer sharing of services and information, such as an
editor invoking a spreadsheet processor to embed a spreadsheet in a document.
- "Vertical" cascading through levels of implementation. A student registration
service may use a database service which in turn uses a file manager which uses a device
driver.
- "Time-line" through the life cycle of an application. Enterprise modeling may
be done in terms of one set of constructs which are translated into constructs of the
application programming language which are compiled into constructs of the run-time
environment. Or, a graphical language used to capture a user's conceptual model of a
business domain is translated into a computer-executable simulation language, with the
results of the simulation then being input either to an analysis tool to allow refinement
of the simulation, or to a report generator to produce the final result.
- Others, e.g., the "viewpoints" of the ISO/CCITT Reference Model for Open
Distributed Processing (RM-ODP) [19]:
- Enterprise viewpoint
- Information viewpoint
- Computational viewpoint
- Engineering viewpoint
- Technology viewpoint
Equivalent forms provide different ways to express the same, or nearly the same,
concept. They have the following uses:
- Explaining some differences between models.
- Designing bridging mechanisms between models.
- Supporting alternative forms with a model. Certain things may be easier to express in
one form than another, such as functional dependences.
- Different forms might motivate or explain different implementations.
- Substitution of equivalent forms may help query optimization.
- Some equivalence classes themselves correspond to certain semantic constructs, e.g.,
relationships.
Some of these can be expressed as constraints of the general form p1(x1) <=> ...
<=> pn(xn), such that any correct implementation will insure that pi(xi) is true
(false) whenever pj(xj) is true (false).
The messaging form x0.f(x1,...,xn) is syntactically equivalent to the functional form
f(x0,x1,...,xn) so long as there is some convention as to which argument is so
distinguished as the "controlling" argument.
Models may differ in their treatment of inheritance, giving the controlling argument
different significance than the others.
An operation with multiple arguments f(x1,...,xn) is equivalent to an operation
f(<x1,...,xn>) taking a single sequence as an argument, provided that such sequence
objects and corresponding types are recognized in the model.
Curried equivalence essentially lets certain concepts be expressed either as operations
or as arguments to operations. For example, the price of HP stock on the New York Stock
Exchange might be expressed as Price(HP,NYSE) or as NYSE_Price(HP). In the first case
there is one Price operation, while in the second case there is a set of operations, one
for each stock exchange.
Curried equivalence is a correspondence (f,x)<->fx such that
f(x,y)=fx(y). In effect, a set of operations is equivalent to a set of arguments to a
single operation. The equivalence can be formally defined as follows, where f is an
operation with signature
f:<t,t1,...,tn> -> tr.
There can be a corresponding set of operations F={fi}, one for each xi, with signatures
fi:<t1,...,tn> -> tr.
The 1:1 correspondence between the instances of F and t can be expressed in a pair of
mapping operations t2F and F2t. The basic equivalences is then given by:
f(x,x1,...,xn) = t2F(f)(x1,...,xn),
fx(x1,...,xn) = f(F2t(fx),x1,...,xn).
That is, f(x,x1,...,xn) is equivalent to taking the operation fi in F which corresponds
to x and applying fi to x1,...,xn.
The equivalence can be constructed in the other direction as well, starting with a set
F of operations having similar signatures and generating an equivalent operation f.
Currying can proceed in multiple stages, each dealing with a different argument. This
yields a lattice of operation sets.
We can have a single HasType predicate used as HasType(x,Employee),
HasType(x,Department), etc., or we can have a set of predicates of the form IsEmployee(x),
IsDepartment(x), etc.
Height(x), Weight(x) vs. Get(Height,x), Get(Weight,x).
Inches(x), Feet(x) vs. Measure(Inches,x), Measure(Feet,x).
Decimal(x), Octal(x) vs. Represent(Decimal,x), Represent(Octal,x).
Develop examples with stock prices, sports schedules, etc. Also parameterized data.
Currying the operation invocation concept:
f(x), g(x) vs. Apply(f,x), Apply(g,x).
Let p be a profile operation which maps n-tuples from the types T1,...,Tn into the
non-negative integers (counters):
p: <T1,...,Tn> -> Integer,
so that
p(x1,...,xn)=k.
Let xi1,...,xi2 and xi3,...,xi4 be any of the 2**n partitions of x1,...,xn (ignoring
permutations). There exists a family of 2**n operations with signature
fi: <Ti1,...,Ti2> -> [<Ti3,...,Ti4>]
such that
<xi3,...,xi4> IN fi(<xi1,...,xi2>)=p(x1,...,xn).
I.e.,
<xi3,...,xi4> IN fi(<xi1,...,xi2>)=k <=> <xj3,...,xj4> IN
fj(<xj1,...,xj2>)=k.
Inverses.
Control over traversability.
Model of relationships. Supports directed and undirected variants. Relate to factoids [Section 13.3].
Functional dependencies.
Facts (from semrel92): Another interesting sort of operations are generators,
which generally return sets of sequences which can be interpreted as the extension of an
r-schema. These come in tagged and untagged forms:
- The tagged form yields a set of <R-schema, <x1,...,xn>> pairs. [Those look
like facts!]
- The untagged form yields a set of <x1,...,xn> sequences.
- Either of those cases can be extended to include <x1,...,xn,b> sequences.
Curried equivalences also apply here. For either sort of generator:
- There can be a single Generator operation of the form Generator(r-schema) which takes an
r-schema as argument.
- There can be a generator operation for each r-schema of the form GenerateR(), taking no
arguments.
Permutations within arguments and within results.
Projections (one-way implications, not equivalences).
Structural coercions.
f1(x1,...,xn)=y <=> f2(<x1,...,xn>)=y.
f1(x)=y <=> f2(x)=<y>.
f1(x)=(<x1,...,xn>) <=> f2(x)=([<x1,...,xn>]) AND FORALL x
Card(f2(x))=<1.
Diverse object models can coexist in a "multi-faceted" object system, where
each facet is a "subsystem" that operates under its own object model. Everything
that happens in an object system is initiated by a request, which is an event that causes
an object to be evaluated. Some services requested at one facet might be performed by
requesting other services at other facets, thus providing a bridge to other models.
(The common infrastructure which links facets might be what some people mean by
"object model", but we have a much richer meaning in mind.)
Facets are subdivided into possibly overlapping "spheres", which define the
set of objects and services which are accessible to a given requestor. ("Sphere"
suggests "sphere of knowledge".) There are also "environments" which
provide a binding for the values of variables. A request is thus made with respect to a
particular environment which determines the bindings of variables, a particular sphere
which determines the objects and services available to the requestor, and a facet which
determines the object model under which the request is defined.
Any request (including equality tests, object creation, etc.) occurs within a given
environment, sphere, and facet. The request may only involve operations and arguments
known in the sphere, and it will only return objects known in the sphere. Thus a given
operation may have different results in different spheres (even with the same behavior
specifications).
This area needs more research, since it's not too clear exactly how this fits into the
FOQL model. Some possibilities:
- A specific operation can have an execution specification which sends a message to a
performer.
- The system's operation application paradigm can somehow recognize that the execution
specification is not local, and try to send a message to a performer.
- Other variations?
Some questions:
- Who chooses the specific performer instance?
- Who gets involved in the trader activity?
- Who marshals parameters?
- How does CORBA fit in here? And OpenODB?
An environment is a set of bindings, which are associations between
variables and objects which are their values. A binding may be null.
A declaration is an operation Declare(<`x,t>) which establishes t as the
value type (result type) for x. A declaration may be evaluated at most once in any
environment. Each evaluation establishes an initially null binding for the variable x in
the current environment. When an environment is deleted, all bindings established in that
environment are deleted. The active binding for a given variable corresponds to
the declaration most recently executed in an environment which has not been deleted.
Evaluation and update of the variable apply to the active binding. Updates are constrained
by the value type established by the corresponding declaration.
Declaring a variable must be clearly distinguished from binding it to a value (some
languages do merge the two notions). Declaring a variable of type Person does not cause an
instance of Person to exist, nor does it bind the variable to an instance of Person. The
declaration merely notifies the implementation to prepare the variable to be bound to an
instance of type Person. Furthermore, the variable may be bound to different instances of
Person at different times.
There is a close resemblance between variables and argumentless operations.
Similarities:
- They are named objects.
- They can be evaluated to yield something else.
- They can be updated.
- They have declared result types.
- They have no arguments or argument types.
But there are important differences:
- Operations are often treated as "first class objects" (e.g., given oid's),
while variables rarely are. Operations have system-defined properties such as name,
signature (argument and result types) and behavior specification. Arbitrary operations
might also be defined on them, such as owner, creation date, application domain, etc.
Variables have implicit properties like their names and declared types, but languages
usually don't provide any mechanism for referring to properties of variables.
- The result type and value may depend on the environment for a variable, but not for an
operation.
- An operation is explicitly created by something like the OSQL Create Function statement,
which is not expected to be executed more than once for a given operation. Variables
aren't really created. Each execution of a declaration establishes a distinct binding of a
variable in a new environment, but that doesn't seem equivalent to object creation.
- An operation might have an arbitrary execution specification, while a variable is always
bound to stored data.
(Global variables might in fact be about the same as argumentless operations.)
The following alternatives do not work well:
- Treating a variable as a operation whose implicit argument is the environment. (It can
have different type declarations in different environments.)
- Letting each declaration create a new instance of the variable, with the variable name
being overloaded. (Ordinary overloading is resolved by argument type.)
There's another interesting way to think about the behavior of variables. Suppose there
was no such thing as a variable, but we did have an ordinary function called Value.
Suppose we also had a naming convention so that, for example, "eks" is
understood to be the name of an object (in the same way that "Person" is
understood to be the name of a type object). To what extent would the ordinary behavior of
functions simulate the desired behavior of variables if we used Value(eks) everywhere we
would like to use the variable x? Consider the positive aspect of where it does work, as
well as the negative aspect of where it doesn't work.
- Classify the object being evaluated. It might be a constant, variable, or an
operation/argument pair. In the latter case, the operation and argument portions may
themselves need to be evaluated to determine the operation and argument objects.
- If the operation is generic, it has to be resolved to a specific operation, based on the
type of the argument. This differentiates, for example, between registering a student in a
course, registering a voter in a district, and registering a car in a state. The result is
a specific operation, which might be one of the specific operations named Register, or a
disambiguator [Section 10.3.4].
- If no specific operation is applicable, try to find one via casting [Section 10.4.1].
- Choose and find a performer to execute the specific operation. This may be based on the
class of the argument [Section 15], as well as
availability of performers and similar resource constraints (e.g., a trader concept). If
not local, then a message with arguments has to be shipped to the performer.
- The specific operation (performer) is applied to the arguments, and results returned.
Evaluation is described in terms of an Evaluate specific operation which takes
any object as argument. It always yields a condition object, which could be an aggregate
of one or more condition objects. There is a current environment and sphere. The behavior
of Evaluate applied to a thing e is described as follows:
- If e is not a known object in the current sphere, return an error condition and no
result.
- If e is a variable, return its binding in the current environment [Section 27.1]
- If e is not a pair, return e as a value object.
- Evaluate the first element of the pair. I.e., Evaluate(1(e)).
4a If this returns an
error condition, return the error condition and results of that evaluation.
4b If the result is not an operation, return e as a value object.
4c If the result is a quoting operation [Section
28.6], return the second element of the pair. I.e., Return(2(e)). Note that it is the
second element of the pair which is returned, without evaluation.
- Evaluate the second element. I.e., Evaluate(2(e)).
5a If this returns an error
condition, return the error condition and results of that evaluation.
- If the value f of the first element is generic, use the mechanism described in Section 10.3.
- If x is not an instance of the argument type t of f, and if there exists exactly one
Caster(<t1,t>) [Section 10.4.1] such that x is
an instance of t1, then evaluate f(Caster(<t1,t>)(x)) and exit.
- [Insert a big step here to choose and find a performer. Account for such things as
classes, trading, messaging, etc.]
- Apply the first element to the second element, and return the error condition and
results of that application. I.e., Apply(<1(e),2(e)>).
Operation application is described in terms of an Apply specific
operation, whose argument is a pair whose first element is an operation. The behavior of
Apply for <f,x> is described as follows:
- If x does not satisfy the preconditions for f [Section
10.2], return an appropriate condition and no result. Preconditions include type
restrictions and whether null arguments are allowed.
- Establish a new environment [Section 27.1.1].
- Perform the operation's execution specification [Section
10.2] (appropriate to the argument's class).
- Delete the current environment, restoring the previous one.
- Return the conditions and results of the operation's execution.
A binary operation is an operation which always yields an error condition if
applied to an argument which is not a pair. Certain language constructs written in the
infix form x binop y denote an expression of the form binop(<x,y>).
A total operation never yields the null condition when applied to a non-null
argument.
We will assume common arithmetic operations without further definition. Semantics of
other operations will be defined arithmetically.
Equal denotes a binary operation such that the evaluation of
Equal(<e1,e2>) yields the result True if and only if e1 and e2 evaluate to the same
object. It is null if either expression is null; otherwise it returns False.
Equal(<e1,e2>) is commonly denoted as e1=e2.
The binary operation denoted as e1~e2 yields True if e1=e2 or if e1 and e2 are both
null; otherwise it yields False. We have e1=e2 => e1 IN e2. (The equality axioms [Section 7.3] actually hold for e1~e2 as well.)
The fact that an expression e is null can be written as e~NullCon.
If e2 is an aggregate [Section 11], the binary
operation denoted as e1 IN e2 yields a non-negative integer, intended to signify the
number of occurrences of e1 in e2. If e2 is a set, then the value of e1 IN e2 will be 1 or
0, corresponding to True or False.
If the value of e2 is not an aggregate, then e1 IN e2 = e1~e2. Thus, if e2 is an
aggregate, then e1 IN e2 signifies occurrences of e1 in e2; otherwise it signifies
equality (or nullness) of e1 and e2.
The meaning of the binary operation denoted as e1 SUBSETEQ e2 is given by
e1 SUBSETEQ e2 => ( x IN e1 => x IN e2 ).
This signifies subset for sets and subtype for types.
A profile is an operation whose value when not null is always a non-negative
integer.
A predicate is an operation whose value when not null is True or False (1 or
0). Thus a predicate is a profile. The phrase "the value of p(x) is True" is
often elided simply to "p(x)" in prose.
We define the semantics of logical operations in terms of the arithmetic of
non-negative integers.
Comparisons return 1 or 0 (or possibly null).
An expression p will be considered true if p>0. To force it to always be exactly
True (1) or False (0), evaluate the expression p>0.
For a simple logic based on zero and non-zero, it suffices to treat conjunction
(AND) as multiplication and disjunction (OR) as addition. These can be reduced to
True and False via p>0. When the numeric value of the expression is significant, as in
the treatment of duplicates in queries [Section 12.2],
it is more appropriate to treat AND as maximum and OR as minimum. Plausible arithmetic
treatments of logical operations in the presence of duplicates are examined in [3, 9].
In general, the negation ¬p of p is given by the expression p=0. This returns 1 if p
is 0, and 0 otherwise. Double negation ¬¬p always returns 0 or 1, and not the value of p
if p>1.
The implication p=>q is defined as "not p, or q", i.e., (p=0)+q.
The conditional "if p then q else r" can be expressed as "p and
q, or (not p) and r", i.e.,
p*q + (p=0)*r.
Quantification can also be expressed arithmetically:
- EXISTS x IN X p(x) ::= [SUM[x IN X]p(x)]>0. This is computable when X is finite.
- FORALL x IN X p(x) can be expressed via the usual double use of negation as ¬(FORALL x
IN X ¬p(x)), i.e., [SUM[x IN X](p(x)=0)]=0.
The summation domain X can be incorporated into the expression in the form
[SUM[x]p(x)*X(x)]>0. Negation of the existential quantifier, i.e., "there exist no
x in X such that p(x)", is given by [SUM[x IN X]p(x)]=0.
An alternative treatment of quantification:
- FORALL x IN X p(x) can be defined as X(x)=>p(x), i.e., [X(x)=0]+p(x).
- EXISTS x IN X p(x) is then given by ¬(FORALL x IN X ¬p(x)), i.e., [X(x)=0+p(x)=0]=0.
[That seems wrong. Where's the flaw?]
y IN f(g(x)) is equivalent to EXISTS z IN Z | z=g(x) AND y IN f(z). Here Z is the
intersection of the result type of g and the argument type of f. For operation
composition, these would normally all be the same.
Arithmetically, this becomes
[y IN f(g(x))] = [SUM[z IN Z](z=g(x))*(y IN f(z))].
The operation Quote(x) indicates that the object x itself is not to be
evaluated. Its principal use is to pass expressions as arguments to other operations which
will apply the expressions. We will sometimes use `x to denote Quote(x).
(We are taking a somewhat simplified view of quoting. Sometimes it may be necessary to
pass x unevaluated through several levels of invocation, implying multiple levels of
quoting. Also, if x is an expression, it is sometimes necessary to evaluate some of the
variables before quoting, as in Section 28.7.4. We
ignore such elaborations.)
Many of these operations are used to define queries [Section
12].
Distinct(b) yields a set containing one occurrence of each x in the bag b:
Distinct(b)(x) = [b(x)>0],
i.e.,
x IN Distinct(b) = [x IN b>0],
i.e.,
Occurs(x,Distinct(b)) = [Occurs(x,b)>0].
If b is an instance of BagType(t), then Distinct(b) is an instance of SetType(t).
Union(b1,b2) of bags, denoted as b1 UNION b2, is defined as a sum:
(b1 UNION b2)(x) = b1(x)+b2(x).
If b1 and b2 are instances of BagType(t1) and BagType(t2), respectively, then b1 UNION
b2 is an instance of BagType(t3), where t3 is any common supertype of t1 and t2.
Distinct should be applied to the result if it is to be assigned to a set-valued
variable or operation.
Difference(b1,b2) of bags, denoted as b1--b2, is defined as non-negative
subtraction:
(b1--b2)(x) = if b1(x)<b2(x) then 0, else b1(x)-b2(x).
Add and Remove operations can be defined to update the values of bag-
and set-valued variables (to update operations, write f(x) rather than x):
Add(<`x,y>) ::= x<-x UNION [y];
SetAdd(<`x,y>) ::= x<-Distinct(x UNION [y]);
Remove(<`x,y>) ::= x<-x--[y];
To update operations, write `f(x) rather than `x. Similar updates are defined for
carriers [Section 11.7] of bag- and set-valued cargos:
Add(<c,y>) ::= Cargo(c)<-Cargo(c) UNION [y];
SetAdd(<`x,y>) ::= Cargo(c)<-Distinct(Cargo(c) UNION [y]);
Remove(<`x,y>) ::= Cargo(c)<-Cargo(c)--[y];
Xprod(<b1,...,bn>) yields the cross product of a sequence of bags
b1,...,bn. The result is a bag of sequences of length n. The result contains k occurrences
of <x1,...,xn>, where k is the product of the number of occurrences of xi in bi:
x IN Xprod(<b1...bn>) = Pi i(x[i] IN bi),
i.e.,
Xprod(<b1...bn>)(x) = Pi ibi(x[i]).
If each bi is an instance of BagType(ti), then Xprod(<b1,...,bn>) is an instance
of BagType(TupleType(<t1,...,tn>)), i.e., [:<:t1,...,tn:>:].
A flattened cross-product FXprod can be defined in terms of a concatenation
operation defined as follows:
- If x is not a sequence, then Concat(<x,y>)=Concat(<<x>,y>).
- If y is not a sequence, then Concat(<x,y>)=Concat(<x,<y>>).
- If x=<x1,...,xn> and y=<y1,...,ym>, then
Concat(<x,y>)=<x1,...,xn,y1,...,ym>.
- Concat(<x1,...,xn>) = Concat(<Concat(<x1,...,xn-1>),xn>).
FXprod(<b1,...,bn>) yields a bag of sequences which contains k occurrences of
Concat(<x1,...,xn>), where k is the product of the number of occurrences of xi in
bi:
FXprod(<b1,...,bn>)(y) = Pi i[bi(x[i]) * y=Concat(<x1,...,xn>)].
Bag processors are operations which take as argument a bag and a quoted
expression with a specified free variable. The general form of these is
Op(<b,'x,'e>) in which b is any bag-valued expression that will be evaluated prior
to application of Op, while x and e are an unevaluated variable and expression. The
variable x will be bound to each occurrence in b, and e(x) evaluated. The bag processors
differ in what they do with the results. (To be more precise: unbound variables other than
x in e must be bound and evaluated before invoking Op. What then gets quoted is the
expression e with those other variables replaced with their values.)
BagReplace simply replaces each occurrence of x with e(x). Since distinct
values of x may have the same value of e(x), the profile of the result is given by
summation over values of x having the same value of e(x):
y IN BagReplace(<b,'x,'e>) = SUM[x](x IN b * y=e(x)),
i.e.,
BagReplace(<b,'x,'e>)(y) = SUM[x](b(x) * y=e(x)),
The summation ranges over distinct values of x having non-zero occurrence in b.
BagFilter requires e to be a profile, with e(x) returning a non-negative
integer for each x occurring in b1. The expression e could be a predicate, returning only
1 or 0 (True or False). The resulting bag contains e(x) occurrences of each x occurring in
b1:
BagFilter(<b,'x,'e>)(x) = [b(x) * e(x)].
BagSort(<b,'x,'e>) yields a sequence whose length is the cardinality of
b, in which x1 precedes x2 if e(x1)<e(x2).
BagGroup(<b,'x,e>) generates equivalence classes of elements of b having
the same values of e. The result is a set of non-empty bags uj (we call them groups).
Since the value of e is the same for each x in a group uj, e is in effect overloaded such
that x IN uj => e(uj)=e(x). Each group uj contains all elements of b having the same
values of e. Hence
uj(x) = [b(x) * e(x)=e(uj)].
The cardinality of BagGroup(<b,'x,'e>), i.e., the number of groups in the
resulting set, is the number of distinct values of e(x) corresponding to elements of x in
b.
Grouping by several expressions e1(x),...,en(x) can be achieved by defining e(x) as
<e1(x),...,en(x)>. A group will contain objects having matching values of each ei.
Each such ei is then overloaded such that x IN uj => ei(uj)=ei(x).
(The following alternative form of BagGroup is somewhat cleaner, but it is more awkward
to use in describing queries...)
BagGroup(<b,'x,'e>) essentially generates equivalence classes of
elements of b having the same value of e. The result is a set of pairs <ui,ei> in
which each ei is a value of e(x) for some x in b, and the group ui is a non-empty bag
containing all occurrences of the x values for which e(x)=ei:
x IN ui = [x IN b * e(x)=ei].
The cardinality of BagGroup(<b,'x,'e>), i.e., the number of pairs in the
resulting set, is the number of distinct values of e(x) corresponding to elements of x in
b. Note that e could be a sequence designator, yielding a composition of multiple
properties of x.
By a tuplebag of width n we will mean an instance of some type of the
form BagType(TupleType(t1,...,tn)), i.e., [:<:t1,...,tn:>:]. The term
"relation" is ambiguous, meaning either a table and its bag of tuples [Section 20.1].
Let b be a tuplebag of width n. Let i1,...,ik be any sequence of integers between 1 and
n inclusive, allowing repetition. Project(<b,<i1,...,ik>>), denoted
as pi [i1,...,ik]b, is defined as
pi [i1,...,ik]b = BagReplace(<b,'x,'<x[i1],...,x[ik]>>).
It yields a bag bp of tuples of the form y=<x[i1]...x[ik]> whose membership
profile is
bp(y) = SUM[x](b(x) * y[1]=x[i1] * ... * y[k]=x[ik] ).
[We could be using ik(x) and i(y) in place of x[ik] and y[i] .]
In effect, we index the tuples in the resulting projection by the
"attributes" 1,...,k. For a given tuple y in bp, its k-th element y[k] is the
ik-th element of a tuple x in b. Thus a tuple y will occur in bp if there is a tuple x in
b such that y[1]=x[i1] AND ... AND y[k]=x[ik]. There may be several distinct tuples x in b
which contribute the same y. Each of these contributes b(x) occurrences of y to bp, hence
the summation over such tuples.
The type of the resulting bag bp is [:<:ti1,...,tik:>:].
Restriction (to avoid confusion with "Select" in a query) is easy to
characterize in terms of a selection expression s(x) which yields a Boolean number. Restrict(<b,'x,'s>),
commonly denoted as sigma [s(x)]b, (yes, sigma corresponds to
"select") is the same as BagFilter:
sigma [s(x)]b = BagFilter(<b,'x,'s>).
It yields a tuplebag bs of the same type as b whose membership profile is
bs(x) = b(x) * s(x).
x occurs n times in bs if x occurs n times in b and s(x) is true.
INJ(<b1,b2,'x1,'x2,'p>) yields the inner join of tuplebags b1 and b2 on the join
predicate p(x1,x2). It yields a tuplebag bI whose membership profile is
bI(x) = (x=<x1,x2>) * p(x1,x2) * b1(x1) * b2(x2).
If x=<x1,x2>, and if p(x1,x2) is true, then the number of occurrences of x in bI
is the product of the number of times x1 occurs in b1 and x2 occurs in b2. Otherwise, x
does not occur in bI.
(We can probably also express inner join as a restriction of the cross-product.)
For outer joins, we first define right and left "appendages" R and L relative
to b1 and b2:
R(x) = (x=<x1,>) * b1(x1)>0 * 0=SUM[x2](p(x1,x2) * b2(x2)).
L(x) = (x=<,x2>) * b2(x2)>0 * 0=SUM[x1](p(x1,x2) * b1(x1)).
These appendages contain things from one bag which don't match anything in the other,
padded out with nulls to match the "shape" of the join result. For R, if:
- x=<x1,>,
- x1 occurs in b1 at least once, and
- there are zero elements x2 occurring in b2 for which p(x1,x2) is true (using negation of
existential quantification [Section 28.4]),
then x will occur once in R. Otherwise x will not occur. Similar analysis applies to L.
Let ROJ, LOJ, and SOJ denote the right, left, and symmetric outer joins of b1 and b2 on
p(x1,x2), respectively yielding bR, bL, and bS. These are respectively defined as the
concatenation of bI with R, with L, and with both. Concatenation is expressed as simple
addition. Hence
ROJ(<b1,b2,'x1,'x2,'p>)(x) = bR(x) = bI(x)+R(x),
LOJ(<b1,b2,'x1,'x2,'p>)(x) = bL(x) = bI(x)+L(x),
SOJ(<b1,b2,'x1,'x2,'p>)(x) = bS(x) = bI(x)+R(x)+L(x).
(Note that these joins are not flattened. We could probably introduce flattened
versions if needed by using Concat(<x1,x2>) in place of <x1,x2>.)
Certain kinds of objects can be characterized by the results of their evaluation.
A constant object is any object whose error-free evaluation always yields the
same result. (Bound designator expressions are constant objects.) NullCon is a
constant object whose evaluation is always null.
A value object is a constant object whose error-free evaluation always yields
itself as the result. Literals are value objects. A reasonable default for the evaluation
of any object is to treat it as a value object, i.e., to return itself as the result. (In
terms of quoting [Section 28.6], c='c for a value
object.) (An oid would also be a value object.)
A variable [Section 27.1] is an atomic
object whose error-free evaluation does not yield itself as the result. Its value depends
on the environment of the evaluation.
An atomic object is not an aggregate [Section 11].
We have little to say about these. Integer (and perhaps character string) seem to be
the only ones needed in the core of the model. Others may be added as extensions. Things
to be defined include designators (symbols), equality, subtyping, and casting.
Null signifies nothing.
Let's consider common-sense semantics.
Consider poor Sam: homeless, unemployed, and born on the Fourth of July.
Address(Sam) is empty, vacuous, non-existent. So is Employer(Sam). Is it true that
Address(Sam)=Employer(Sam)? No. But it's also not true that Address(Sam)¬=Employer(Sam).
In order to say that two things are equal, or unequal, we need to have some things to
compare. Address(Sam) and Employer(Sam) aren't anything; there isn't anything there for us
to compare, for us to say they are equal or unequal. In fact, it isn't even true that
Address(Sam)=Address(Sam); we don't have any things to compare.
If we construct the set {Address(Sam)}, we get the empty set: {Address(Sam)}={ }. The
same is true of {Employer(Sam)}. Furthermore, if we construct the set
{Address(Sam), Employer(Sam)},
we still get a set containing nothing, i.e., the empty set. So,
{Address(Sam), Employer(Sam)} = {Address(Sam)} = {Employer(Sam)} = { }.
Is it really true that {Address(Sam)}={Employer(Sam)}? Yes. The empty set is a thing,
which can be compared with other things. If x and y both refer to the empty set, then x=y
is true. So, we also have {Address(Sam)}={Address(Sam)} being true.
If we construct the tuple <Name(x), Address(x), Employer(x), Birthdate(x)> for
Sam, we get
<Sam, , , 7/4/74>.
That's a funny thing. The date 7/4/74 is the fourth thing in the tuple, though the
tuple contains only two things. The second and third things aren't there, though we hold a
place for them.
Is it true that <Sam, , ,7/4/74>=<Sam, , ,7/4/74>? Of course it is. Like
sets, these tuples are existing things which can be compared. Two aggregates have to be
equal if they have the same structure, they are empty in corresponding places, and things
in corresponding non-empty places are equal.
We do need some sort of placeholder in stored data. But the placeholder is not an
address or an employer. If we construct a table of data about people, we might have
something like
-----------------------------------------
| Name | Address | Employer | Birthdate |
|======|=========|==========|===========|
| Sam | | | 7/4/74 |
-----------------------------------------
Figure 8.
Like our tuple above, the row for Sam has four cells, though two of them are empty. The
row contains two things; the date 7/4/74 is in the fourth cell. How long is this row?
Four, even though it contains only two things.
The blank spaces are not addresses or employers. If we allow such blank spaces, then it
is simply untrue to say that everything in the second column is an address, or that
everything in the third column is an employer. The second column is allowed to contain
addresses or blank spaces, and the third column may contain employers or blank spaces.
By the way, things would be the same whether Sam is homeless or we just don't know his
address. Things would also be the same whether Sam is unemployed or we just don't know his
employer. Our data only reflects what we know, not the total truth. Address(Sam) being
empty means precisely that we don't know an address for Sam; we can't tell which case it
means. The same is true for Employer(Sam) being empty.
Following are some examples of the kinds of indexed aggregates which can be defined in
terms of their index sets and other constraints. The terminology is not uniformly
accepted.
Any sort of indexed aggregate has a "compact" form which contains no nulls,
as defined by the additional constraint
i IN IndexSet(g) => ¬g[i]~NullCon.
Any of the indexed aggregates described below can be defined to have a compact variant.
We define these three terms to be equivalent (but the corresponding types are not!).
A sequence is a single object which corresponds to an ordered list of objects
or empty positions. A pair is a sequence of length two.
In order to avoid the circular definition which arises from trying to define a sequence
in terms of an operation which takes a sequence of things as its argument, it is useful in
the abstract to define a sequence to be an operation. There is an empty sequence, which
can be denoted as <>. When <> is applied to an object x1, the resulting object
is a sequence we can denote as <x1>, i.e., <x1> means <>(x1). When that
sequence is in turn applied to an expression x2, the resulting object is a sequence we can
denote as <x1,x2>. In general, <x1,...,xn> can be thought of as denoting the
object resulting from the successive evaluations <>(x1)...(xn). An object is a
sequence if it is <> or it is the value of s(x) for some sequence s and object x.
There is a Length operation which can be applied to sequences.
Length(<>)=0. If the value of s is a sequence, then Length(s(x))=Length(s)+1 (even
if x is null).
Integers may be applied as operations to sequences in order to extract elements. The
expression i(<x1,...,xn>) yields xi, which might be null. This can be defined as
follows:
- i(s)~NullCon for i<1 or i>Length(s) (NullCon is defined in Section 29.1; the ~ operator is defined in Section 28.1).
- i(s(x))~i(s) for 1=<i=<Length(s).
- i(s(x))~x for i=Length(s)+1.
Mnemonically, we can read 1(s) as First(s), 2(s) as Second(s), and so on.
We will eventually establish all of the following as equivalent notation:
i(s) = Extract(<i,s>) = s[i] = s.i.
The index set is an initial subset of the positive integers 1,...,n. Arity=n.
Note carefully that sequences and tuples are the same thing at the instance level,
though the corresponding types aggregate them differently [Section
11.1.3]. For example, the sequence (or tuple) <1,2> is an instance of both
SequenceType(Integer) and TupleType(<Integer,Integer>).
These come in compact and non-compact varieties.
The index set is an initial subset of the non-negative integers 0...n-1. Arity=n. This
is a 0-origin sequence.
These come in compact and non-compact varieties.
The index set is some arbitrary set of objects. The elements of the index set might be
called "attributes" or "accessors". (Strictly speaking, all indexed
aggregates are records. One could make a case for limiting records to be accessed by
character strings, serving as "field names".)
The index set is a set of n-long sequences of integers. The integer n is the dimensionality
of an array. A bounded array also has an associated sequence of n integers i1,...,in
representing maximum values on the index set.
A regular bag has an associated index set, which is not an index set of the
bag itself, but which is the index set for each object occurring in the bag. A regular bag
thus contains uniform aggregates, all having the same index set.
A relation is a regular bag (or regular set).
Behavior of a generic operation may be defined with the following statement (in the
syntactic style of OSQL [7]):
DEFINE GENERIC OPERATION generic-name
[FOR type-list]
[RESULT_TYPE result-type]
[DEFAULT_VALUE [FOR var-1 IS] expr-1]
[DISAMBIGUATE [FOR var-1] USING expr-2 WITH {VALUE_BAG | FUNC_SET} var-2 ]
[UNIQUE];
We will use the operation name f for illustration, with f(x) being a generic request.
The statement may occur before any specific operation named f is created, in order to
provide control over result types.
The relevant types are those in the type-list and their subtypes.
Types which become subtypes of these in the future will automatically be included.
Different behaviors may be defined for different sets of relevant types for the same
generic operation f. A type may not be in more than one relevant type set for a given
generic operation. If type-list is omitted, then the relevant type set contains all types.
Specified behaviors are associated with a particular generic operation and relevant
type set.
If result_type is specified, then any specific operation named f whose argument type is
in the relevant set must have the specified result type. Specific operations named f may
have different result types if their argument types are in different relevant type sets
with associated result-type specifications. Specific operations named f whose argument
types are not in any relevant type set having a result-type specification must all have
the same result type; this is the default result type.
The DEFAULT_VALUE clause has the effect of making an operation f defined for all the
relevant types. If the types of x are in exactly one relevant type set for f having a
DEFAULT_VALUE specification, and there is no specific operation f.t known on any type t of
x, then expr-1 defines the value of f(x). If var-1 is provided, it is bound to the value
of x, and it may be used in expr-1. In the following example, if t0 is in the type-list
but there is no specific operation f.t0, then expr-1 defines the value of f for immediate
instances of t0. This can be considered a limited form of upward inheritance
[Figure 9].
------
| t0 |
------
:
:
------
| t1 |
f.t1 ------
:
.....................
: :
------ ------
| t2 | | t3 |
f.t2 ------ ------
: :
.....................
:
------
| t4 |
------
Figure 9.
The DISAMBIGUATE clause specifies action to be taken when a generic operation call f(x)
is ambiguous, and the argument types of all the eligible operations are in the relevant
type set. The value of expr-2 is returned; it must yield a value whose type is the
specified or default result-type. The variables var-1 and var-2 may be used in expr-2. If
var-1 is provided, it is bound to the value of x. If VALUE_BAG is specified, then var-2 is
bound to the bag of results of the evaluated eligible operations. If FUNC_SET is
specified, then var-2 is bound to the set of unevaluated eligible operations, allowing
expr-2 to reason over these operations and select the ones to be invoked.
The UNIQUE keyword signifies that the generic operation must be unique-valued for all
instances of all its relevant types. It means that f.ti(x)=f.tj(y) => x=y if ti and tj
are relevant types. Thus, for example, if a generic operation named SSN ("social
security number") was defined to be unique, then distinct instances of relevant types
may not have the same value of SSN, even via different specific operations named SSN. In
OSQL, without this extension, uniqueness can only be specified within an individual
specific operation.
Section 30.1 provides other examples.
The processing of a generic request f(x) is now extended as follows:
1. The eligible operations are the specific operations f.t which are known for
the immediate types of x.
If x is null, the eligible operations are the specific operations named f whose
pre-conditions allow null arguments, including argumentless operations.
2. If there is exactly one eligible operation, invoke it and exit.
3. If there are no eligible operations:
3a. If the types of x are in exactly one relevant type set for generic operation f
which has a specified result value, then return that value and exit.
3b. If there exists exactly one Caster(<t1,t2>) [Section
10.4.1] such that x is an instance of t1 and there exists an f.t2, then invoke
f.t2(Caster(<t1,t2>)(x)) and exit.
3c. Else return an undefined condition and exit.
4. If there is more than one eligible operation:
4a. If the argument types of all the eligible operations are in exactly one
relevant type set for generic operation f which has a disambiguation specification, then
use that disambiguation specification and exit.
4b. If all the non-null values are the same, then return that value (or null if all the
values are null) and exit
4c. Else raise an ambiguous condition and exit.
As before, the non-emphasized portions of items 3 and 4 characterize the default
behavior of the generic operation.
Multidatabase systems such as Pegasus and Multibase [2, 6] include the ability to
reconcile inconsistent data from different data sources, and also to treat things imported
from different data sources as the same object. These things can be done with user-defined
generic operation behavior.
The general approach to integration is to import data from different sources as
distinct imported types, and then to provide correlation mechanisms across the imported
types.
A typical situation here is that data from two sources may be inconsistent, e.g.,
Salary(x) in one source differs from Wages(x) in another. If we impose the not
unreasonable requirement that "semantically equivalent" operations should have
the same name, even by renaming if necessary, then the disambiguation behavior of generic
operations can be used to correlate their values.
Suppose we have the following schema after renaming, where t1 and t2 are imported types
[Figure 10]:
------
| t0 |
------
:
.....................
: :
------ ------
| t1 | | t2 |
Salary.t1 ------ ------ Salary.t2
Figure 10.
Then
DEFINE GENERIC OPERATION Salary
FOR t0
RESULT_TYPE Number
DEFAULT_VALUE Return(0)
DISAMBIGUATE USING Average(sal_bag) WITH VALUE_BAG sal_bag;
defines the generic operation behavior for Salary(x) which would be applicable if x is
an instance of t0 or any of its subtypes. Any Salary operation defined on t0 or any of its
subtypes must have result type Number. When Salary(x) is invoked:
- If x is an instance of t1 only or t2 only, then Salary.t1(x) or Salary.t2(x) is invoked
without even involving the generic operation.
- If x is an immediate instance of t0, or an instance of any subtype on which Salary is
not known, then DEFAULT_VALUE defines the value of Salary(x) to be 0.
- If x is an instance of t1 and t2, then the DISAMBIGUATE clause indicates that the
average of the salaries is to be returned. The variable sal_bag will contain the bag of
results of evaluating Salary.t1(x) and Salary.t2(x), which in this case will be passed to
the Average operation.
If the behavior was defined as
DEFINE GENERIC OPERATION Salary
FOR t0
RESULT_TYPE Number
DEFAULT_VALUE Return(0)
DISAMBIGUATE FOR x USING Best_sal(x,funcs) WITH FUNC_SET funcs;
then, if x belongs to both t1 and t2, Salary.t1(x) and Salary.t2(x) will not be
evaluated. The variable funcs will contain the set of unevaluated operations Salary.t1 and
Salary.t2, which in this case will be passed to the Best_sal operation along with x. That
operation might, for example, consider t1 to always be more reliable, and only evaluate
and return Salary.t1(x). It might also do more complex reasoning.
If no disambiguation was defined, then the default behavior in case of ambiguity under
the present proposal would be to return the consistent value if Salary.t1(x)=Salary.t2(x),
and raise an ambiguity error otherwise.
This approach to correlating imported data has several benefits:
- It takes advantage of a general-purpose facility for disambiguating overloaded
operations.
- Nothing has to be specified for the cases where there is no conflict, e.g., x belongs to
only one of the subtypes.
- It is readily extensible. When a new type is imported, it is only necessary to insure
that the Salary operation has that name, and to make the new type a subtype of t0. The
mechanism described here will automatically be applicable.
Accidental conflicts with other unrelated operations which might also be named
"Salary" can be avoided by
- Renaming it to a different name, or
- Making sure its argument type is not a subtype of t0.
Multidatabase systems provide the ability to treat objects imported from different
external data sources as being the same object, based on some criterion such as social
security number. The general mechanism is to provide equivalence specifications across the
imported types [6]. Unique-valued generic operations can simplify their specification.
A simple equivalence specification might take the form
SocSecNum.t1(x)=SSN.t2(y)=> x=y,
implying that x and y are to be treated as the same object if
SocSecNum.t1(x)=SSN.t2(y). Generic operations can become involved if we again adopt the
same-name assumption for semantically equivalent operations. If the operations are all
named SSN, and the generic operation named SSN is defined to be unique for t1 and t2, this
would imply
SSN.t1(x)=SSN.t2(y)=> x=y.
More generally, we would have
SSN.ti(x)=SSN.tj(y)=> x=y
whenever ti and tj were relevant. Thus a single generic operation behavior definition
can imply equivalence specifications between many pairs of types.
The equivalence holds even when ti and tj are the same. Thus if two people in the same
imported type somehow had the same social security number, they would be treated as the
same person. (A more plausible example might arise when courses using the same textbook
are to be treated as the same course.) Of course, the earlier treatment of operation
merging does not work for such intra-type equivalence.
We need to distinguish between two responses to "violations" of uniqueness:
- Rejecting it as an error, e.g., trying to give the same social security number to two
people known to be distinct.
- Treating the offenders as being one and the same object.
This can be distinguished on the basis of a "view" concept:
- If two objects are known to be distinct in the current view, then any attempt to modify
their properties in a way that would violate uniqueness is rejected as an error.
- If one or both of the objects are "imported" from some other view with
matching values of unique properties, then treat them as a single object.
Equivalence based on conjunction of multiple properties, e.g., Nationality and
PassportNumber, can be handled by defining another operation on each of the imported types
as the concatenation of Nationality and PassportNumber, e.g.,
Ident(x) ::= <Nationality(x),PassportNumber(x)>,
and then defining the generic operation Ident to be unique.
Equivalence based on disjunction of multiple properties, e.g., social security number
or passport number, can be handled by defining a unique-valued generic operation for each.
(Cycles of such equivalence specifications can also cause intra-type equivalence. A person
in one type might have a social security number corresponding to one person in another
type and a passport number corresponding to a different person in that type.)
As before, this approach is readily extensible. New imported types can be accommodated
by appropriately naming the operations and making the types relevant to the generic type.
1 Serge Abiteboul and Anthony Bonner, "Objects and Views", Proc. SIGMOD May
29-31, 1991, Denver, Colorado.
2 R. Ahmed, P. DeSmedt, W. Du, W. Kent, M. Ketabchi, W. Litwin, A. Rafii, M.-C. Shan,
"The Pegasus Heterogeneous Multidatabase System", IEEE Computer, December 1991.
3 Joseph Albert, "Algebraic Properties of Bag Data Types", Proc. 17th Intl.
Conf. on Very Large Data Bases, Sept. 3-6, 1991, Barcelona, Spain.
4 Joseph Albert, Rafi Ahmed, Mohammad Ketabchi, William Kent, Ming-Chien Shan,
"Automatic Importation of Relational Schemas in Pegasus", Proc. RIDE-IMS, April
19-20 1993, Vienna, Austria.
5 C. Batini, M. Lenzerini, and S.B. Navathe, "A Comparative Analysis of
Methodologies for Database Schema Integration", ACM Computing Surveys 18(4), Dec.
1986.
6 Umeshwar Dayal and Hai-Yann Hwang, "View Definition and Generalization for
Database Integration in a Multidatabase System", IEEE Trans. on Software Engineering,
SE-10(6), Nov. 1984, pp. 628-645.
7 Dan Fishman, et al, "Overview of the Iris DBMS", Object-Oriented
Concepts, Databases, and Applications, Kim and Lochovsky, eds, Addison-Wesley, 1989.
8 Elizabeth Fong, William Kent, Ken Moore and Craig Thompson (editors), X3/SPARC/DBSSG/OODBTG
Final Report, Sept 17, 1991. Available from NIST.
9 William Kent, "Profile Functions and Bag Theory", HPL-SAL-89-19,
Hewlett-Packard Laboratories, Jan. 10, 1989. [pdf]
10 William Kent, "The Many Forms of a Single Fact", Proc. IEEE COMPCON, Feb.
27-Mar. 3, 1989, San Francisco. [html]
11 William Kent, "A Rigorous Model of Object Reference, Identity, and
Existence", Journal of Object-Oriented Programming 4(3) June 1991 pp. 28-38. [html]
12 William Kent, "The Breakdown of the Information Model in Multi-Database
Systems", SIGMOD Record 20(4) Dec 1991. [html]
13 William Kent, "User Object Models", OOPS Messenger 3(1), Jan 1992. [html]
14 William Kent, "The State of Object Technology", Canadian Information
Processing, July/August 1992. [html]
15 Amit P. Sheth and James A. Larson, "Federated Database Systems for Managing
Distributed, Heterogeneous, and Autonomous Databases", ACM Computing Surveys 22(3),
Sept. 1990.
16 Richard Soley and William Kent, "The OMG Object Model", in Database
Challenges in the 1990s, Won Kim (editor), Addison-Wesley/ACM (in preparation).
17 Object Management Architecture Guide, Second Edition, Object Management
Group, Framingham MA, 1992.
18 "The Common Object Request Broker: Architecture and Specification (Revision
1.1)", Document Number 91.12.1, Object Management Group, Framingham MA, Dec. 1991.
19 "Information Technology - Basic Reference Model of Open Distributed Processing
- Part 2: Descriptive Model", ISO/IEC CD 10746-2.2, 26 April 1993.
20 "Information Technology - Basic Reference Model of Open Distributed Processing
- Part 2: Descriptive Model", ISO/IEC CD 10746-2.2, 26 April 1993.