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

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

knownby 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:

- Produce a symbol (possibly opaque) which is the
*result*of the evaluation, said to be*returned*by the evaluation. (And sometimes called the*value*of the evaluated symbol.) For example, evaluation of a variable might return the symbolic representation of a number. The symbol might be visible or opaque, and it might be the originally evaluated symbol itself.(Note that an evaluation result in not automatically displayed, or returned across the interface; it might be an opaque symbol.)

- Alter something within the computational system in a way that affects the behavior of future requests. For example, a request to increment some counter alters the results of future requests to display the counter.
- Produce information about one or more
*conditions*encountered during processing of the request. Some conditions signify errors, while others might simply indicate that request processing has been completed, or that is has been completed without producing any result.- An
*invalid expression*error condition arises when the computational system does not recognize the symbol, i.e., the system has no instructions on how to evaluate the symbol. - The
*null*condition arises when there is no result to be returned. - The
*completion*condition is raised simply to indicate that evaluation is finished. It might only need to be returned in the absence of other conditions.

- An

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:

- Clarification of various modes by which objects come into existence [Section 7.2].
- Well-defined semantics for equality [Section 7.3].
- Treatment of null as a condition rather than a value [Section
6.1]. Null is represented by
*Nullcon*, an object which is a constant (non-updatable variable) whose evaluation yields the null condition [Section 29.1]. - Variables are objects themselves [Section 29.1].
- Types are predicates [Section 9], bags are profiles [Section 11.1.1].
- Distinction between behavior and implementation [Section 10.2].
- User-defined behavior for generic operations [Section 10.3].
- Distinction between types and classes [Section 15].
- Casting [Section 10.4.1].
- Generalized model of aggregates in terms of index sets [Section 11.2].
- Distinction between literal and surrogate aggregates [Section 11.7].
- Carriers and cargos [Section 13.1].
- Semantics of queries (including duplicates and group-by) and some other operations defined in terms of arithmetic [Section 20], [Section 28].
- Extracting elements of sequences (tuples) by applying integers as operations [Section 29.5].
- Convenient equivalences between various constructs [Section 25].

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.

- Pre-conditions are constraints which must be satisfied to insure error-free application
of the operation.

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.
- For internal operations, we can use UWC directly, e.g.,
If UWC=CEO then...

- To display the current UWC, we would use something like:
Display(Enum(UWC))

Display(Ssn(UWC)) - To designate an employee by employee number or social security number, we would use
something like:
UWC<-EmpWithEnum(123)

UWC<-EmpWithSsn(123)

- For internal operations, we can use UWC directly, e.g.,

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>) =

Pii(x[i] IN bi),

i.e.,

Xprod(<b1...bn>)(x) =

Piibi(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) =

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