Multi-Faceted Object Systems and Models

William Kent
Database Technology Department
Hewlett-Packard Laboratories
Palo Alto, California

April, 1994


> ***PROLOGUE*** . . . 7
> 1 OBJECTIVES AND STATUS . . . 7
> 2 ORGANIZING PRINCIPLES . . . 7
>> 2.1 Isolation of Object Users From Object Implementation . . . 7
>> 2.2 Behavioral Criteria . . . 8
>> 2.3 Fundamental Concepts . . . 8
>>> 2.3.1 Object Systems . . . 8
>>> 2.3.2 User Perspective . . . 9
>>> 2.3.3 Implementation Perspective . . . 10
> ***OBJECT SYSTEMS*** . . . 10
> 3 COMPUTATIONAL SYSTEMS . . . 10
>> 3.1 Illusion and Metaphor . . . 11
>> 3.2 Interfaces and Symbols . . . 11
>> 3.3 Requests and Expressions . . . 12
>> 3.4 Operator Expressions . . . 13
>> 3.5 What Symbols Mean . . . 14
> 4 INTRODUCTION TO OBJECT SYSTEMS . . . 15
>> 4.1 The Computational Context . . . 15
>>> 4.1.1 Interfaces to a Black Box . . . 15
>>> 4.1.2 Symbols . . . 16
>> 4.1 Object Systems . . . 17
>> 4.3 Object System Interfaces . . . 17
>> 4.4 Facets and Spheres . . . 18
> ***A GENERAL MODEL: USER PERSPECTIVE*** . . . 19
> 5 INTRODUCTION . . . 19
> 6 REQUESTS . . . 20
>> 6.1 Results and Conditions . . . 20
>> 6.2 Expressions . . . 21
>> 6.3 Performers of Requests . . . 22
>> 6.4 Update and State . . . 22
>>> 6.4.1 Updating Variables . . . 23
>>> 6.4.2 Updating Operations . . . 23
>>> 6.4.3 Changeable, Updatable and Recorded Properties, and State . . . 23
> 7 OBJECT EXISTENCE AND IDENTITY . . . 24
>> 7.1 "Exists" vs. "Known" . . . 24
>> 7.2 How Objects Become Known . . . 25
>> 7.3 Equality Axioms . . . 25
>> 7.4 Creating and Initializing Objects . . . 26
> 8 INFORMATION FOR REQUEST PLANNING . . . 26
> 9 TYPES . . . 27
>> 9.1 The Nature and Role of Types . . . 27
>> 9.2 Non-Materialized and Materialized Types . . . 28
>>> 9.2.1 Materialized Types for Numbers . . . 28
>>> 9.2.2 Ideal and Effective Types . . . 29
>>>> 9.2.2.1 Ideal Non-Materialized Numeric Types . . . 30
>>>> 9.2.2.2 Ideal Materialized Numeric Types . . . 30
>>>> 9.2.2.3 Effective Materialized Numeric Types . . . 30
>>>> 9.2.2.4 Effective Non-Materialized Numeric Types . . . 30
> 10 OPERATIONS . . . 32
>> 10.1 Specific and Generic Operations . . . 32
>> 10.2 Specific Operations . . . 32
>>> 10.2.1 Signatures . . . 33
>>> 10.2.2 Behavior Specifications . . . 33
>>>> 10.2.2.1 Behavior vs. Implementation . . . 33
>>>> 10.2.2.2 Update Specifications . . . 34
>> 10.3 Generic Operations and Inheritance . . . 35
>>> 10.3.1 Overview . . . 35
>>> 10.3.2 Inheritance . . . 36
>>> 10.3.3 Default Behavior of Generic Operations . . . 36
>>> 10.3.4 Defined Behaviors . . . 37
>> 10.4 Additional Behaviors . . . 37
>>> 10.4.1 Casting (Substitutability) and Its Uses . . . 38
>>>> 10.4.1.1 Type Casting . . . 38
>>>> 10.4.1.2 Intensional Aggregates . . . 38
>>>> 10.4.1.3 Type Extents . . . 38
>>>> 10.4.1.4 Type Substitutability . . . 38
>>> 10.4.2 Extending Non-Aggregate Operations to Aggregate Operations . . . 38
>> 10.5 The Association Between Types and Operations . . . 39
>> 10.6 Operations Involving Types and Operations . . . 39
>>> 10.6.1 Populating Types: Asserted and Derived Types . . . 39
>>> 10.6.2 Disjoint Types . . . 40
> 11 AGGREGATES . . . 41
>> 11.1 Unstructured Aggregates: Bags and Sets . . . 41
>>> 11.1.1 Instances . . . 41
>>> 11.1.2 Instance Designators . . . 42
>>> 11.1.3 Types and Type Designators . . . 43
>> 11.2 Indexed Aggregates . . . 44
>>> 11.2.1 Instances . . . 44
>>> 11.2.2 Instance Designators . . . 45
>>>> 11.2.2.1 Sequence Designator . . . 45
>>>> 11.2.2.2 Compact Sequence Designator . . . 46
>>> 11.2.3 Types and Type Designators . . . 46
>>>> 11.2.3.1 Sequence and Tuple Types . . . 46
>> 11.3 Empty Aggregates . . . 47
>> 11.4 Type Constraints on Aggregates . . . 47
>> 11.5 Aggregate Subtypes . . . 48
>> 11.6 Arithmetic Semantics of Aggregate Operations . . . 48
>> 11.7 Extensional and Intensional Aggregates . . . 49
> 12 QUERY . . . 50
>> 12.1 Arithmetic Semantics . . . 51
>> 12.2 Basic Form . . . 51
>> 12.3 Group-By . . . 52
>> 12.4 Query Transformations . . . 54
> 13 OTHER INTERESTING OBJECTS . . . 55
>> 13.1 Carriers and Cargos . . . 55
>> 13.2 User-Defined Literals . . . 55
>>> 13.2.1 Subtypes of Basic Literals . . . 56
>> 13.3 Factoids . . . 56
>> 13.4 Objects With Content . . . 57
>> 13.5 Objects With Location . . . 57
>> 13.6 Measured Quantities . . . 57
>>> 13.6.1 Relevance of Non-Materialized and Materialized Types . . . 58
>>> 13.6.2 Use and Mention of Quantity Designators . . . 58
>>> 13.6.3 An Interesting Analogy . . . 59
>>>> 13.6.3.1 Single Designation . . . 59
>>>> 13.6.3.2 Multiple Designations . . . 60
>>>> 13.6.3.3 Conversions . . . 61
>>> 13.6.4 Another Analogy . . . 61
>> 13.7 Geometric Constructs . . . 62
>>> 13.7.1 Geometric Points . . . 62
>>> 13.7.2 Plane Figures . . . 63
> ***A GENERAL MODEL: IMPLEMENTATION PERSPECTIVE*** . . . 63
> 14 INTRODUCTION . . . 63
> 15 CLASSES . . . 63
> 16 CHOOSING PERFORMERS . . . 64
> ***OTHER MODELS*** . . . 65
> 17 MESSAGING MODELS . . . 65
> 18 LINK/INTERACTION MODELS . . . 65
> 19 OSQL . . . 65
>> 19.1 Semantics . . . 65
>>> 19.1.1 Aggregates . . . 65
>>> 19.1.2 Query . . . 66
> 20 BASIC RELATIONAL MODEL . . . 66
>> 20.1 Semantics . . . 66
>>> 20.1.1 Tuple Tables . . . 66
>>> 20.1.2 Update . . . 67
>>> 20.1.3 Query . . . 67
>> 20.2 SQL Syntax . . . 68
> 21 OBJECT-ORIENTED RELATIONAL MODEL . . . 68
>> 21.1 Non-Tuple Tables . . . 69
>> 21.2 Comparison of Tuple- and Non-Tuple Tables . . . 69
>> 21.3 Managing the Extent (Population) of a Type: Table of ALL . . . 70
>> 21.4 SELECT * . . . 70
> ***MODEL DIFFERENCES*** . . . 71
> 22 DIMENSIONS OF DIFFERENCE . . . 71
>> 22.1 Performer and Participant Models . . . 71
>> 22.2 Addressing and Associative Models . . . 74
>>> 22.2.1 Objects in Space . . . 74
>> 22.3 Other Significant Differences . . . 75
> 23 WHY THE DIFFERENCES? . . . 76
> ***MODEL INTEROPERATION*** . . . 77
> 24 REQUIREMENTS . . . 77
>> 24.1 Cascading Interfaces . . . 77
>> 24.2 Dimensions of Interoperation . . . 79
> 25 EQUIVALENT FORMS . . . 80
>> 25.1 Messaging and Functional Syntax . . . 80
>> 25.2 Multiple Arguments vs. Sequences of Arguments . . . 80
>> 25.3 Curried Equivalence . . . 80
>>> 25.3.1 Description . . . 80
>>> 25.3.2 Examples . . . 81
>>>> 25.3.2.1 Typing Operations . . . 81
>>>> 25.3.2.2 Attributes . . . 81
>>>> 25.3.2.3 Units of Measure and Data Types . . . 81
>>>> 25.3.2.4 Schema Mismatch . . . 81
>>>> 25.3.2.5 A Universal Relation and the Apply Operation . . . 81
>> 25.4 (Relational) Operation Families . . . 82
>>> 25.4.1 Description . . . 82
>>> 25.4.2 Uses . . . 82
>> 25.5 Extended Operation Families . . . 83
>> 25.6 Structural Coercions . . . 83
> 26 MULTI-FACETED OBJECT SYSTEMS . . . 83
>> 26.1 Facets, Spheres, and Environments . . . 83
>> 26.2 Interoperation of Diverse Models . . . 84
> ***DETAILS*** . . . 84
> 27 EXPRESSIONS . . . 84
>> 27.1 Variables . . . 84
>>> 27.1.1 Environments and Binding . . . 84
>>> 27.1.2 Declaration vs. Binding . . . 85
>>> 27.1.3 Comparison With Argumentless Operations . . . 85
>> 27.2 Expression Evaluation and Operator Application . . . 86
>>> 27.2.1 Overview . . . 86
>>> 27.2.2 Evaluate . . . 86
>>> 27.2.3 Apply . . . 87
> 28 SOME USEFUL OPERATIONS . . . 87
>> 28.1 Equality and Null . . . 88
>> 28.2 Membership and Inclusion . . . 88
>> 28.3 Profiles and Predicates . . . 88
>> 28.4 Logical Operations . . . 88
>> 28.5 Operation Composition . . . 89
>> 28.6 Quoting . . . 89
>> 28.7 Bag Operations . . . 89
>>> 28.7.1 Duplicate Elimination . . . 90
>>> 28.7.2 Union and Difference . . . 90
>>> 28.7.3 Cross-Products . . . 91
>>> 28.7.4 Bag Processors . . . 91
>> 28.8 Other Relational Operations . . . 93
>>> 28.8.1 Project . . . 93
>>> 28.8.2 Restrict (Select) . . . 93
>>> 28.8.3 Joins . . . 94
> 29 SOME USEFUL OBJECTS . . . 95
>> 29.1 Constants, Values, and Variables . . . 95
>> 29.2 Atomic Objects . . . 95
>> 29.3 Basic (Literal) Data Types . . . 95
>> 29.4 Null . . . 95
>> 29.5 Indexed Aggregates . . . 97
>>> 29.5.1 Compact Aggregate . . . 97
>>> 29.5.2 Sequences/Lists/Tuples . . . 97
>>> 29.5.3 0-Sequence . . . 98
>>> 29.5.4 Record . . . 98
>>> 29.5.5 Array . . . 98
>>> 29.5.6 Regular Bag . . . 98
> 30 SPECIFIED BEHAVIORS FOR GENERIC OPERATIONS . . . 98
>> 30.1 Application to Multidatabase Systems . . . 101
>>> 30.1.1 Operation Merging for Inconsistent Data . . . 101
>>> 30.1.2 Merging Equivalent Objects . . . 103
> 31 REFERENCES . . . 104


***PROLOGUE***

1 OBJECTIVES AND STATUS

This document:

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.

2 ORGANIZING PRINCIPLES

This document rests on these organizing principles:

2.1 Isolation of Object Users From Object Implementation

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.

2.2 Behavioral Criteria

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.

2.3 Fundamental Concepts

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.

2.3.1 Object Systems

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.

2.3.2 User Perspective

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:

From the user perspective, it doesn't matter who performs a requested service [Section 6.3].

The essential effect of update is to alter the results of future requests [Section 6.4].

The concept of state is not uniquely defined from the user perspective [Section 6.4.3].

Objects "exist" so long as they are known to an object system [Section 7.1].

If an object system can provide the date on which a certain file was deleted, then that file object still exists as far as the object system is concerned. Certain operations may no longer be supported, such as modifying or displaying the contents of the file, and the file may no longer be present in any directory, but the object system can still respond to requests involving that file.

Similarly, if an object system can provide the date on which a certain building will be completed, as well as its location, height, and blueprints, then the building object exists even if construction has not yet begun.

We try to avoid dealing with "existence" in this document, and speak only of objects being known by an object system. Operations which purport to "create" or "destroy" objects in an object system should really be understood as "introducing" and "erasing" objects, i.e., making them known and unknown to the object system.

The management of object identity depends on how an object becomes known to an object system [Section 7.2].

We thus have eternal, mortal, and ephemeral objects.

The management of object identity should be consistent with the axioms of equality [Section 7.3].

Schema constructs such as types, operation definitions, and inheritance are provided for planning purposes, so that users can choose the appropriate requests to achieve their intended results [Section 8].

The operation referenced in a request may be either specific or generic [Section 10.1].

There are no inheritance issues or problems for specific operations. The complexities of inheritance and overloading arise only with generic operations.

Behavior specifications are distinct from implementation specifications [Section 10.2.2.1].

An operation might be exclusively or jointly owned [Section 10.5].

Aggregates can be described in terms of content and form [Section 11].

There's a difference between extensional and intensional aggregates [Section 11.7].

The semantics of queries should be defined in terms which do not depend on any particular internal model of query execution [Section 12.1].

Some objects have an implicit notion of "content" [Section 13.4].

But not all. For these objects, operations such as Move, Copy, and Display are meaningful.

Some objects have a location property [Section 13.5].

But not all. For these objects, operations such as Locate and Move are meaningful.

Null signifies nothing [Section 29.4].

2.3.3 Implementation Perspective

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

***OBJECT SYSTEMS***

3 COMPUTATIONAL SYSTEMS

(This section is not integrated smoothly with the subsequent material.)

3.1 Illusion and Metaphor

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.

3.2 Interfaces and Symbols

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:

3.3 Requests and Expressions

Everything that happens in the computational system is the result of a request, which causes a symbol to be evaluated. What does evaluation do? What can be evaluated? How do requests happen?

Evaluation might do one or more of the following:

An error-free evaluation is one which does not yield an error condition.

In a broad sense, any symbol (external, opaque, or a mixture) can be evaluated, though in extreme cases evaluation might yield an error condition, or it might simply return the original symbol unchanged. Evaluation of symbols which can be recognized as operator expressions (containing operator parts and operand parts) is quite complex, and will be discussed shortly. Other symbols can be characterized by the results of their error-free evaluation:

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:

(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.)

3.4 Operator Expressions

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:

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.

3.5 What Symbols Mean

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.

4 INTRODUCTION TO OBJECT SYSTEMS

This section briefly introduces the basic notion of object systems. We will later return to discuss multi-faceted object systems [Section 26].

4.1 The Computational Context

A computational system is a symbol processor with interfaces.

4.1.1 Interfaces to a Black Box

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:

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.

4.1.2 Symbols

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:

4.2 Object Systems

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.

4.3 Object System Interfaces

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.

4.4 Facets and Spheres

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.

***A GENERAL MODEL: USER PERSPECTIVE***

5 INTRODUCTION

This section describes a particular model which, in the terms introduced in Section 22, can be characterized as a participant and associative model.

(This could be FOQL - Functional Object Query Language - abusing the word "query" to include all DDL and DML, just as in SQL and OSQL.)

By and large, this is an aggregation of familiar material, such as the functional Evaluate/Apply paradigm and some usual notions of types, operations, overloading, etc. However, there are a number of small but powerful refinements:

Most real systems and languages support only a subset of the features described here. This model is intended to be a superset of the model supported by most real systems and languages.

The model is developed top-down, developing the natural consequences of the fundamental concepts.

6 REQUESTS

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.

6.1 Results and Conditions

Evaluation of a request yields one or more of the following:

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:

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.

6.2 Expressions

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.

6.3 Performers of Requests

From the user perspective, it doesn't matter who performs a requested service.

Notes:

6.4 Update and State

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.

6.4.1 Updating Variables

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.

6.4.2 Updating Operations

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.

6.4.3 Changeable, Updatable and Recorded Properties, and State

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.

7 OBJECT EXISTENCE AND IDENTITY

7.1 "Exists" vs. "Known"

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.

7.2 How Objects Become Known

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:

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

7.3 Equality Axioms

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

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.

7.4 Creating and Initializing Objects

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.

8 INFORMATION FOR REQUEST PLANNING

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.

9 TYPES

The following topics need to be developed:

9.1 The Nature and Role of Types

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

(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).

9.2 Non-Materialized and Materialized Types

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.

9.2.1 Materialized Types for Numbers

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:

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.

9.2.2 Ideal and Effective Types

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:

Languages typically take one of the following approaches:

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:

9.2.2.1 Ideal Non-Materialized Numeric Types

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.

9.2.2.2 Ideal Materialized Numeric Types

These are the ones described above in Section 9.2.1, with infinite symbol sets.

9.2.2.3 Effective Materialized Numeric Types

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.

9.2.2.4 Effective Non-Materialized Numeric Types

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:

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

10 OPERATIONS

10.1 Specific and Generic Operations

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.

10.2 Specific 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:

10.2.1 Signatures

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.

10.2.2 Behavior Specifications

10.2.2.1 Behavior vs. Implementation

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:

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:

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 operation may have several sets of implementation specifications, each associated with a different class [Section 15].

10.2.2.2 Update Specifications

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.

10.3 Generic Operations and Inheritance

10.3.1 Overview

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:

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:

10.3.2 Inheritance

Inheritance behaves as follows (this is inheritance of interfaces, not implementations):

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

10.3.3 Default Behavior of Generic Operations

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:

Without item 4a, f(x) would be considered ambiguous when there are several eligible operations even if they all have the same value.

10.3.4 Defined Behaviors

The following behaviors may be explicitly defined for a generic operation with respect to a set of argument types:

Details are described in Section 30.

10.4 Additional Behaviors

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.

10.4.1 Casting (Substitutability) and Its Uses

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:

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.

10.4.1.1 Type Casting

Automatic casting between basic data types is often defined for some languages.

10.4.1.2 Intensional Aggregates

The Cargo operation is the casting operation for intensional aggregates [Section 11.7].

10.4.1.3 Type Extents

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

10.4.1.4 Type Substitutability

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.

10.4.2 Extending Non-Aggregate Operations to Aggregate Operations

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

10.5 The Association Between Types and Operations

An operation might be exclusively or jointly owned.

10.6 Operations Involving Types and Operations

Topics:

10.6.1 Populating Types: Asserted and Derived 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:

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.

10.6.2 Disjoint Types

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:

We summarize the rules governing overlap and disjointness:

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.

11 AGGREGATES

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

11.1 Unstructured Aggregates: Bags and Sets

11.1.1 Instances

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.

11.1.2 Instance Designators

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.

11.1.3 Types and Type Designators

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:].

11.2 Indexed Aggregates

Indexed aggregates provide a general way to describe things like sequences, arrays, and records.

11.2.1 Instances

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.

11.2.2 Instance Designators

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.

11.2.2.1 Sequence Designator

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.

11.2.2.2 Compact Sequence Designator

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

11.2.3 Types and Type Designators

11.2.3.1 Sequence and Tuple Types

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.

11.3 Empty Aggregates

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.

11.4 Type Constraints on Aggregates

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

11.5 Aggregate Subtypes

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.

11.6 Arithmetic Semantics of Aggregate Operations

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:

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

11.7 Extensional and Intensional Aggregates

There's a difference between extensional and intensional aggregates.

We have six terms for two concepts:

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.

12 QUERY

"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.

12.1 Arithmetic Semantics

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.

12.2 Basic Form

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:

This definition of the Query operation imposes minimal requirements on the expressions b, w(x), and r(x):

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.

12.3 Group-By

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:

  1. The initial bag is obtained by evaluating b.
  2. 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).
  3. 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.

  4. The second (outer) BagFilter applies the having-clause h(u) to bg, yielding the bag bg2 such that bg2(u)=bg(u)*h(u).
  5. 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

  1. b = Extent(Employee).
  2. w(x) = Age(x)>30.
  3. g(x) = Salary(x).
  4. h(u) = Count(u)>2 AND Salary(u)>50000.
  5. r(u) = Salary(u).

12.4 Query Transformations

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.

13 OTHER INTERESTING OBJECTS

13.1 Carriers and Cargos

(Refer to other documents.)

13.2 User-Defined Literals

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

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.

13.2.1 Subtypes of Basic Literals

(E.g., even numbers, primes, "small" numbers, state and country names, etc.)

13.3 Factoids

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:

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.

13.4 Objects With Content

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.

13.5 Objects With Location

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.

13.6 Measured Quantities

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:

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

13.6.1 Relevance of Non-Materialized and Materialized Types

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.

13.6.2 Use and Mention of Quantity Designators

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.

13.6.3 An Interesting Analogy

We can make an interesting analogy between employees and distances if we assume that oid's cannot be exposed.

13.6.3.1 Single Designation

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.

13.6.3.2 Multiple Designations

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:

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

13.6.3.3 Conversions

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.

13.6.4 Another Analogy

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

13.7 Geometric Constructs

13.7.1 Geometric Points

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

13.7.2 Plane Figures

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

***A GENERAL MODEL: IMPLEMENTATION PERSPECTIVE***

14 INTRODUCTION

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.

15 CLASSES

An operation may have several sets of retrieval and update execution specifications, each associated with a different class. Notes:

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.

16 CHOOSING PERFORMERS

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.

***OTHER MODELS***

17 MESSAGING MODELS

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.

18 LINK/INTERACTION MODELS

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.

19 OSQL

19.1 Semantics

19.1.1 Aggregates

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

19.1.2 Query

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.

20 BASIC RELATIONAL MODEL

This section covers the basic relational model, i.e., without object orientation. Goals:

20.1 Semantics

20.1.1 Tuple Tables

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.

20.1.2 Update

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].

20.1.3 Query

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.

20.2 SQL Syntax

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.

21 OBJECT-ORIENTED RELATIONAL MODEL

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:

There are two possible essential extensions:

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:

21.1 Non-Tuple Tables

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 */

21.2 Comparison of Tuple- and Non-Tuple Tables

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.

21.3 Managing the Extent (Population) of a Type: Table of ALL

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

21.4 SELECT *

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

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.

***MODEL DIFFERENCES***

22 DIMENSIONS OF DIFFERENCE

22.1 Performer and Participant Models

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.

22.2 Addressing and Associative Models

Addressing includes concepts of location as

22.2.1 Objects in Space

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.

22.3 Other Significant Differences

The following is a sampling of some other significant differences:

23 WHY THE DIFFERENCES?

Object models differ for a variety of reasons. Perhaps the most important is that different goals are being pursued by various object-oriented facilities:

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.

***MODEL INTEROPERATION***

24 REQUIREMENTS

24.1 Cascading Interfaces

The following scenario illustrates a variety of requirements on object models. Key points to keep in mind:

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:

In summary, at any given interface there are:

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.

24.2 Dimensions of Interoperation

Applications can interoperate along the following dimensions:

25 EQUIVALENT FORMS

Equivalent forms provide different ways to express the same, or nearly the same, concept. They have the following uses:

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

25.1 Messaging and Functional Syntax

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.

25.2 Multiple Arguments vs. Sequences of Arguments

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.

25.3 Curried Equivalence

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.

25.3.1 Description

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.

25.3.2 Examples

25.3.2.1 Typing Operations

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.

25.3.2.2 Attributes

Height(x), Weight(x) vs. Get(Height,x), Get(Weight,x).

25.3.2.3 Units of Measure and Data Types

Inches(x), Feet(x) vs. Measure(Inches,x), Measure(Feet,x).

Decimal(x), Octal(x) vs. Represent(Decimal,x), Represent(Octal,x).

25.3.2.4 Schema Mismatch

Develop examples with stock prices, sports schedules, etc. Also parameterized data.

25.3.2.5 A Universal Relation and the Apply Operation

Currying the operation invocation concept:

f(x), g(x) vs. Apply(f,x), Apply(g,x).

25.4 (Relational) Operation Families

25.4.1 Description

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.

25.4.2 Uses

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:

Curried equivalences also apply here. For either sort of generator:

25.5 Extended Operation Families

Permutations within arguments and within results.

Projections (one-way implications, not equivalences).

Structural coercions.

25.6 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.

26 MULTI-FACETED OBJECT SYSTEMS

26.1 Facets, Spheres, and Environments

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

26.2 Interoperation of Diverse Models

This area needs more research, since it's not too clear exactly how this fits into the FOQL model. Some possibilities:

Some questions:

***DETAILS***

27 EXPRESSIONS

27.1 Variables

27.1.1 Environments and Binding

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.

27.1.2 Declaration vs. Binding

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.

27.1.3 Comparison With Argumentless Operations

There is a close resemblance between variables and argumentless operations. Similarities:

But there are important differences:

(Global variables might in fact be about the same as argumentless operations.)

The following alternatives do not work well:

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.

27.2 Expression Evaluation and Operator Application

27.2.1 Overview

  1. 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.
  2. 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].
  3. If no specific operation is applicable, try to find one via casting [Section 10.4.1].
  4. 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.
  5. The specific operation (performer) is applied to the arguments, and results returned.

27.2.2 Evaluate

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:

  1. If e is not a known object in the current sphere, return an error condition and no result.
  2. If e is a variable, return its binding in the current environment [Section 27.1]
  3. If e is not a pair, return e as a value object.
  4. 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.

  5. 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.

  6. If the value f of the first element is generic, use the mechanism described in Section 10.3.
  7. 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.
  8. [Insert a big step here to choose and find a performer. Account for such things as classes, trading, messaging, etc.]
  9. 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)>).

27.2.3 Apply

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:

  1. 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.
  2. Establish a new environment [Section 27.1.1].
  3. Perform the operation's execution specification [Section 10.2] (appropriate to the argument's class).
  4. Delete the current environment, restoring the previous one.
  5. Return the conditions and results of the operation's execution.

28 SOME USEFUL OPERATIONS

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.

28.1 Equality and Null

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.

28.2 Membership and Inclusion

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.

28.3 Profiles and Predicates

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.

28.4 Logical Operations

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:

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:

28.5 Operation Composition

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))].

28.6 Quoting

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

28.7 Bag Operations

Many of these operations are used to define queries [Section 12].

28.7.1 Duplicate Elimination

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

28.7.2 Union and Difference

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];

28.7.3 Cross-Products

Xprod(<b1,...,bn>) yields the cross product of a sequence of bags b1,...,bn. The result is a bag of sequences of length n. The result contains k occurrences of <x1,...,xn>, where k is the product of the number of occurrences of xi in bi:

x IN Xprod(<b1...bn>) = Pi i(x[i] IN bi),

i.e.,

Xprod(<b1...bn>)(x) = Pi ibi(x[i]).

If each bi is an instance of BagType(ti), then Xprod(<b1,...,bn>) is an instance of BagType(TupleType(<t1,...,tn>)), i.e., [:<:t1,...,tn:>:].

A flattened cross-product FXprod can be defined in terms of a concatenation operation defined as follows:

FXprod(<b1,...,bn>) yields a bag of sequences which contains k occurrences of Concat(<x1,...,xn>), where k is the product of the number of occurrences of xi in bi:

FXprod(<b1,...,bn>)(y) = Pi i[bi(x[i]) * y=Concat(<x1,...,xn>)].

28.7.4 Bag Processors

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.

28.8 Other Relational Operations

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].

28.8.1 Project

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:>:].

28.8.2 Restrict (Select)

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.

28.8.3 Joins

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:

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

29 SOME USEFUL OBJECTS

29.1 Constants, Values, and Variables

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.

29.2 Atomic Objects

An atomic object is not an aggregate [Section 11].

29.3 Basic (Literal) Data Types

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.

29.4 Null

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.

29.5 Indexed Aggregates

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.

29.5.1 Compact Aggregate

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.

29.5.2 Sequences/Lists/Tuples

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:

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.

29.5.3 0-Sequence

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.

29.5.4 Record

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".)

29.5.5 Array

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.

29.5.6 Regular Bag

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

30 SPECIFIED BEHAVIORS FOR GENERIC OPERATIONS

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:

As before, the non-emphasized portions of items 3 and 4 characterize the default behavior of the generic operation.

30.1 Application to Multidatabase Systems

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.

30.1.1 Operation Merging for Inconsistent Data

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

Accidental conflicts with other unrelated operations which might also be named "Salary" can be avoided by

30.1.2 Merging Equivalent Objects

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:

This can be distinguished on the basis of a "view" concept:

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.

31 REFERENCES

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.