Subtypes

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

Nov 1993

SQL3 Change Proposal
ANSI Number: X3H2-93-369r1
Nov. 15, 1993
Title: Subtypes
Author: William Kent


CONTENTS:
> 1 DISCUSSION . . . 2
>> 1.1 Inheritance of components . . . 2
>> 1.2 Rule concerning inheritance of components . . . 2
>> 1.3 Redefinition of components in inheritance . . . 2
>> 1.4 Inheritance of routines . . . 3
>> 1.5 Substitutability does not imply subtype . . . 3
>> 1.6 Component inclusion does not imply subtype . . . 3
>> 1.7 Limitations of substitutability . . . 3
> 2 CHANGE PROPOSALS . . . 3
>> 2.1 Inheritance of components . . . 3
>> 2.2 Rule concerning inheritance of components . . . 4
>> 2.3 Redefinition of components in inheritance . . . 4
>> 2.4 Inheritance of routines . . . 4
>> 2.5 Substitutability does not imply subtype . . . 4
>> 2.6 Component inclusion does not imply subtype . . . 5
>> 2.7 Limitations of substitutability . . . 5


References:

1 X3H2-93-359R/ISO DBL MUN-003, (ISO-ANSI Working Draft) Database Language SQL (SQL3), Jim Melton (ed.), August 1993.

2 X3H2-93-331, "Why SETs and LISTs should not be subtypes of MULTISET", by Linda DeMichiel and Nelson Mattos.

1 DISCUSSION

This paper proposes clarifications of the semantics of subtypes, substitutability, and inheritance. Sections are numbered such that section 1.x motivates the change proposed in 2.x.

1.1 Inheritance of components

This proposal clarifies the conditions under which new specific routines are created in subtypes.

If we define the type Person with an Address function, and then define a subtype Student under Person with another Address function, then there will be two distinct specific functions, which we will denote by the specific names PAddress and SAddress. The existence of distinct specific functions is evident if we assume that either now or in the future it is possible to cause these functions to be explicitly invoked and independently updated, so that PAddress(x) and SAddress(x) might have different non-null values for the same value of x. Due to the late binding semantics of subject routine determination, PAddress(x) might be different from Address(x) if x is a student, since Address(x) will then be interpreted as SAddress(x).

Suppose now that Teacher is also defined as a subtype of Person, without an explicit Address function. It would seem that the user's intent is that the address of a teacher is the address of the person who is the teacher, in the same sense that the birthdate of the teacher is the birthdate of the person who is the teacher. Under this interpretation, the user deliberately avoided re-specifying the Address function because the user did not want a different specific function to be created.

However, Subclause 4.11.2 (Subtypes and supertypes for ADTs) on page 42 of [1] says "Effectively, components of all direct supertype representations are copied to the subtype's representation with same name and data type." Taken literally, this implies that new specific routines are automatically created. This implies an undesirable proliferation of specific routines for every subtype of the type on which the routine is defined, and deprives the user of any option to avoid automatic creation of new specific routines. The proposed change to Subclause 4.11.2 removes the implication that distinct new specific routines are automatically created.

1.2 Rule concerning inheritance of components

A corresponding change should be made to the rules in Subclause 11.46 (<abstract data type body>) on page 488. SR 11 should say that components inherited by a type are not originally-defined components of that type, as defined in SR 5.

1.3 Redefinition of components in inheritance

The rules in Subclause 11.46 do not seem to say that if Address is defined on Person and on Student, then the one defined on Student replaces the one defined on Person in the Student ADT. While SR 15 precludes duplicate names, it does not say which one is retained.

1.4 Inheritance of routines

SR 5 of Subclause 11.46 seems to describe such inheritance only for attribute definitions, not for all members. We propose that this be extended to at least include routine definitions as well. If it should also be extended to other members, we leave that for a future change proposal.

1.5 Substitutability does not imply subtype

Subtypes imply substitutability, as stated in Subclause 4.10: "If Ta is a subtype of Tb, then an instance of Ta can be used wherever an instance of Tb is expected. In particular, an instance of Ta can be assigned to a variable of type Tb, passed as an argument for an input parameter declared as type Tb, and returned from a function whose result type is declared to be Tb."

It should be clarified that this is a one-way implication. Substitutability does not itself suffice to imply subtypes. For example, there is a form of substitutability based on casting which does not imply subtypes. Let f be an operation with argument type Tb. If there is a casting function from Ta to Tb, then f(x) will execute successfully if x is an instance of Ta. This is substitutability, since an instance of Ta can be used where an instance of Tb is expected, but this does not make Ta a subtype of Tb.

1.6 Component inclusion does not imply subtype

While subtypes imply component inclusion, in the sense that the components of Person are included in the components of Student, it should be clarified that this too is a one-way implication. The converse does not follow: component inclusion does not in itself imply subtyping. The type Person may be defined with functions Name, Age, and Address, and the type Wine may be defined with functions Name and Age, but that does not suffice to make Person a subtype of Wine.

1.7 Limitations of substitutability

Substitutability may not extend to the target of an update. Suppose Move(p,d) is an operation which moves a person p to an address d, i.e., changes the address of the person. It does not necessarily follow that any person can be moved to any address. Suppose students are required to reside in the United States. If p is an instance of Person, then Move(p,London) would be valid - but not if p is an instance of Student. Thus this instance of Student could not be substituted where an instance of Person is allowed. This addresses a problem described in Section 2.0 (Desirable, but incompatible features) of [2].

2 CHANGE PROPOSALS

Changes are cumulative but independent. Adopted things added to the end of the same material should be added in the order proposed below.

2.1 Inheritance of components

In Subclause 4.11.2 (Subtypes and Supertypes for ADTs):

In the fourth paragraph, replace the sentence

"Effectively, components of all direct supertype representations are copied to the subtype's representation with same name and data type."

with the sentence

"Effectively, components of all direct supertype representations are reused in the subtype's representation, unless replaced by explicit specification of a component with the same name."

2.2 Rule concerning inheritance of components

In Subclause 11.46 (<abstract data type body>):

At the end of SR 11 Case b) "Otherwise, an implicit <member list>...", add the sentence

Components of the inherited representation of STD are not originally-defined components in TUP.

2.3 Redefinition of components in inheritance

In Subclause 11.46 (<abstract data type body>):

Before SR 12 ("Let same component mean..."), add the following new SR appropriately numbered as x:

x) Each component in the inherited representation of STD which has the same name as a component in the explicit <member list> of STD is dropped from TUP.

2.4 Inheritance of routines

In Subclause 11.46 (<abstract data type body>):

In SR 5 ("If <member list> is specified, then"),

2.5 Substitutability does not imply subtype

In Subclause 4.10 (Subtypes and supertypes):

Add the following paragraph at the end:

Although subtypes imply substitutability, the converse does not hold. There is a form of substitutability based on casting which does not imply subtypes. Let f be an operation with argument type Tb. If there is a casting function from Ta to Tb, then f(x) will execute successfully if x is an instance of Ta. This is substitutability, since an instance of Ta can be used where an instance of Tb is expected, but this does not make Ta a subtype of Tb.

2.6 Component inclusion does not imply subtype

In Subclause 4.10 (Subtypes and supertypes):

Add the following paragraph at the end:

Subtypes imply component inclusion, in the sense that if the type PERSON has an Address component then the subtype STUDENT has an Address component. The converse does not follow: component inclusion does not in itself imply subtyping. The type PERSON may be defined with components Name, Age, and Address, and the type WINE may be defined with components Name and Age, but that does not suffice to make PERSON a subtype of WINE.

2.7 Limitations of substitutability

In Subclause 4.10 (Subtypes and supertypes):

Add the following paragraph at the end:

Substitutability may not extend to the target of an update. Suppose Move(p,d) is an operation which moves a person p to an address d, i.e., changes the address of the person. It does not necessarily follow that any person can be moved to any address. Suppose students are required to reside in the United States. If p is an instance of Person, then Move(p,London) would be valid - but not if p is an instance of Student. Thus this instance of Student could not be substituted where an instance of Person is allowed.