least specific type (tuple types) See least specific type.

least upper bound Let s be a set; let a partial ordering be defined on s; and let s′ be a subset of s. Then x is an upper bound for s′ if and only if x ∊ s and x is greater than or equal to every element of s′ with respect to the specified ordering. Moreover, if there do exist any such x’s, it’s easy to show there must be a smallest one, and that smallest x is the least upper bound (LUB) for s′ with respect to the specified ordering. (Note that the LUB for s′ might or might not itself be contained within s′.) See also lattice.

Examples: See the examples under type lattice.

Liskov Substitution Principle A principle frequently claimed as the origin of the notion of substitutability, q.v. Unfortunately the paper usually cited as the source for this principle—Barbara Liskov and Jeannette Wing, “A Behavioral Notion of Subtyping,” ACM Transactions on Programming Languages and Systems 16, No. 6, November 1994—appears not to contain any precise statement of the principle as such. The closest it gets seems to be as follows:

[Objects] of the subtype ought to behave the same as those of the supertype as far as anyone or any program using supertype objects can tell.

The term objects here refers to objects in the OO sense, of course; note, therefore, that the definition, if definition it is, fails to distinguish adequately between value and variable substitutability (see Principle of Value Substitutability; Principle of Variable Substitutability). Unfortunately, the same appears to be true of OO writings in general.

LSP Liskov Substitution Principle.

LUB Least upper bound.

Manifesto model Term used in this part of the dictionary to refer to the model of type inheritance described in the book Databases, Types, and the Relational Model: The Third Manifesto (3rd edition), by C. J. Date and Hugh Darwen (Addison-Wesley, 2007), as revised and extended in the book Database Explorations: Essays on The Third Manifesto and Related Topics, by C. J. Date and Hugh Darwen (Trafford, 2010). See the Manifesto website www.thethirdmanifesto.com. Perhaps the most salient feature of the model in question—in sharp contrast to other approaches to inheritance described in the literature—is that, in that model, value v is of type T if and only if v satisfies the type constraint for T. In particular, therefore, absurdities such as circular noncircles (q.v.) and noncircular circles (q.v.) can’t occur. Note: The type constraint for type T defines the set of values that make up that type T (see Part I of this dictionary). For further discussion, see CONSTRAINT; IS; specialization constraint.

maximal supertype (SQL) SQL term for a root type. (Oddly enough, the SQL term for a leaf type isn’t “minimal subtype” but “leaf type.”) Note that the concepts of maximal type and minimal type as defined elsewhere in this part of the dictionary are absent from SQL.

maximal type A type with no immediate supertype. Every type lattice (q.v.) has exactly one maximal type. For scalar types, the unique maximal type is alpha; for tuple and relation types, see maximal type (tuple types) and maximal type (relation types), respectively.

maximal type (relation types) Let T be a relation type with heading {<A1,T1>, <A2,T2>, ..., <An,Tn>} (n ≥ 0). Then type T_alpha = RELATION {<A1,T1_alpha>, <A2,T2_alpha>, ..., <An,Tn_alpha>} is the maximal type with respect to relation type T (in fact, it’s the maximal type with respect to the pertinent type lattice, q.v.) if and only if, for all i (i = 1, 2, ..., n), type Ti_alpha is the maximal type with respect to type Ti.

Examples: 1. For the relation types shown in Fig. 5, the maximal type is RELATION {E alpha, R alpha}. 2. Let T be the relation type RELATION { }. Then the maximal type with respect to T is T itself (the only type in the pertinent type lattice), and it contains exactly two values: namely, TABLE_DUM and TABLE_DEE.

maximal type (tuple types) Let T be a tuple type with heading {<A1,T1>, <A2,T2>, ..., <An,Tn>} (n ≥ 0). Then type T_alpha = TUPLE {<A1,T1_alpha>, <A2,T2_alpha>, ..., <An,Tn_alpha>} is the maximal type with respect to tuple type T (in fact, it’s the maximal type with respect to the pertinent type lattice, q.v.) if and only if, for all i (i = 1, 2, ..., n), type Ti_alpha is the maximal type with respect to type Ti.

Examples: 1. For the tuple types shown in Fig. 5, the maximal type is TUPLE {E alpha, R alpha}. 2. Let T be the tuple type TUPLE { }. Then the maximal type with respect to T is T itself (the only type in the pertinent type lattice), and it contains exactly one value: namely, the 0-tuple.

minimal subtype (SQL) See maximal supertype (SQL).

minimal type A type with no proper subtype. Every type lattice (q.v.) has exactly one minimal type. For scalar types, the unique minimal type is omega; for tuple and relation types, see minimal type (tuple types) and minimal type (relation types), respectively.

minimal type (relation types) Let T be a relation type with heading {<A1,T1>, <A2,T2>, ..., <An,Tn>} (n ≥ 0). Then type T_omega = RELATION {<A1,T1_omega>, <A2,T2_omega>, ..., <An,Tn_omega>} is the minimal type with respect to relation type T (in fact, it’s the minimal type with respect to the pertinent type lattice, q.v.) if and only if, for all i (i = 1, 2, ..., n), type Ti_omega is the minimal type with respect to type Ti.

Examples: 1. For the relation types shown in Fig. 5, the minimal type is RELATION {E omega, R omega}. Note that this type contains exactly exactly one value: namely, the empty relation of that type. 2. Let T be the relation type RELATION { }. Then the minimal type with respect to T is T itself (the only type in the pertinent type lattice), and it contains exactly two values: namely, TABLE_DUM and TABLE_DEE.

minimal type (tuple types) Let T be a tuple type with heading {<A1,T1>, <A2,T2>, ..., <An,Tn>} (n ≥ 0). Then type T_omega = TUPLE {<A1,T1_omega>, <A2,T2_omega>, ..., <An,Tn_omega>} is the minimal type with respect to tuple type T (in fact, it’s the minimal type with respect to the pertinent type lattice, q.v.) if and only if, for all i (i = 1, 2, ..., n), type Ti_omega is the minimal type with respect to type Ti.

Examples: For the tuple types shown in Fig. 5, the minimal type is TUPLE {E omega, R omega}; note that this type is empty (there are no tuples of this type). However, minimal tuple types aren’t necessarily empty. For example, let T be the tuple type TUPLE { }. Then the minimal type with respect to T is T itself (the only type in the pertinent type lattice), and it contains exactly one value: namely, the 0-tuple.

model of a relation variable Let relation variable (relvar) V be of declared type T, and let it have attributes A1, A2, ..., An (n ≥ 0). Because of value substitutability, q.v., the value v assigned to V at any given time can have any subtype T′ of type T as its most specific type. V can therefore be modeled as a named set, containing n named ordered triples of the form <DTi,MSTi,vi> (i = 1, 2, ..., n), where:

• The name of the set is the name of the relvar, V.

• The name of each triple is the name of the corresponding attribute.

• DTi is the name of the declared type of attribute Ai.

• MSTi is the name of the most specific type for, or of, attribute Ai. That most specific type is the most specific common supertype of the most specific types of the values in vi—see the explanation of vi in the next bullet item below. (Actually MSTi is uniquely determined by vi and so could be omitted from the model, but it’s convenient to include it.)

• Let the body of the current value of V consist of m tuples (m ≥ 0); label those tuples (in some arbitrary sequence) “tuple 1,” “tuple 2,” ..., “tuple m”; then vi is a sequence of m values (not necessarily all distinct), being the Ai values from tuple 1, tuple 2, ..., tuple m (in that order). Note that those Ai values are all of type MSTi.

Note: The notation DT(Ai), MST(Ai), v(Ai) is used elsewhere in this dictionary to refer to the DTi, MSTi, vi components, respectively, of the Ai component of this model of relvar V. Also, the notation DT(V), MST(V), v(V) is used to refer to the overall declared type, overall most specific type, and overall current value components, respectively, of this model of relvar V.

model of a relational expression Let exp be a relational expression. Then the notation DTi(V), MSTi(V), vi(V) introduced under model of a relation variable can be extended in an obvious way to allow DTi(exp), MSTi(exp), vi(exp) to be used to refer to the DTi, MSTi, vi components, respectively, of the Ai component of the model of the relation denoted by the expression exp. Similarly, the notation DT(V), MST(V), v(V) introduced under model of a relation variable can be extended in an obvious way to allow DT(exp), MST(exp), v(exp) to be used to refer to the overall DT, MST, v components of the model of the relation denoted by the expression exp.

model of a scalar expression Let exp be a scalar expression. Then the notation DT(V), MST(V), v(V) introduced under model of a scalar variable can be extended in an obvious way to allow DT(exp), MST(exp), v(exp) to be used to refer to the DT, MST, v components of the model of the scalar value denoted by the expression exp.

model of a scalar variable Let scalar variable V be of declared type T. Because of value substitutability, q.v., the value v assigned to V at any given time can have any nonempty subtype T′ of type T as its most specific type. V can therefore be modeled as a named ordered triple of the form <DT,MST,v>, where:

• The name of the triple is the name of the variable, V.

• DT is the name of the declared type for variable V.

• MST is the name of the most specific type for, or of, variable V. (Actually MST is uniquely determined by v—see most specific type—and so the MST component of V could be omitted from the model, but it’s convenient to include it.)

• v is a value of most specific type MST—the current value for, or of, variable V.

Note: The notation DT(V), MST(V), v(V) is used elsewhere in this dictionary to refer to the DT, MST, v components, respectively, of this model of scalar variable V.

model of a tuple expression Let exp be a tuple expression. Then the notation DTi(V), MSTi(V), vi(V) introduced under model of a tuple variable can be extended in an obvious way to allow DTi(exp), MSTi(exp), vi(exp) to be used to refer to the DTi, MSTi, vi components, respectively, of the Ai component of the model of the tuple denoted by the expression exp. Similarly, the notation DT(V), MST(V), v(V) introduced under model of a tuple variable can be extended in an obvious way to allow DT(exp), MST(exp), v(exp) to be used to refer to the overall DT, MST, v components of the model of the tuple denoted by the expression exp.

model of a tuple variable Let tuple variable (tuplevar) V be of declared type T, and let the heading of T have attributes A1, A2, ..., An (n ≥ 0). Because of value substitutability, q.v., the value v assigned to V at any given time can have any nonempty subtype T′ of type T as its most specific type. V can therefore be modeled as a named set of named ordered triples of the form <DTi,MSTi,vi> (i = 1, 2, ..., n), where:

• The name of the set is the name of the tuplevar, V.

• The name of each triple is the name of the corresponding attribute.

• DTi is the name of the declared type of attribute Ai.

• MSTi is the name of the most specific type for, or of, attribute Ai. (Actually MSTi is uniquely determined by vi—see below—and so could be omitted from the model, but it’s convenient to include it.)

• vi is a value of most specific type MSTi—the current value for, or of, attribute Ai.

Note: The notation DT(Ai), MST(Ai), v(Ai) is used elsewhere in this dictionary to refer to the DTi, MSTi, vi components, respectively, of the Ai component of this model of tuplevar V. Also, the notation DT(V), MST(V), v(V) is used to refer to the overall declared type, overall most specific type, and overall current value components, respectively, of this model of tuplevar V.

model of a variable See model of a relation variable; model of a scalar variable; model of a tuple variable.

model of an expression See model of a relational expression; model of a scalar expression; model of a tuple expression.

most specific common subtype Let T1, T2, ..., Tm (m ≥ 0) be types from the same type lattice, q.v. Then type T′ is the most specific common subtype for types T1, T2, ..., Tm if and only if it’s the minimal type with respect to the type lattice in question. Note: Informally, most specific common subtypes are sometimes defined to exclude the pertinent minimal type, in which case the term is taken to apply to the pertinent leaf type (but only if every type in the given set of types T1, T2, ..., Tm overlaps every other—for otherwise no such leaf type exists). With reference to Fig. 4, for example, the most specific common subtype for types KITE and CYCLIC QUADRILATERAL is either type omega, q.v., or (if minimal types are excluded) type SQUARE. (Note that RIGHT KITE is also a common subtype in this example, but it’s not the most specific one.) By contrast, with reference to Fig. 2, the most specific common subtype for types ELLIPSE and RECTANGLE either is type omega or (if minimal types are excluded) doesn’t exist. Contrast least specific common subtype; least specific common supertype; most specific common supertype.

most specific common subtype (relation types) See most specific common subtype.

most specific common subtype (tuple types) See most specific common subtype.

most specific common supertype Let T1, T2, ..., Tm (m ≥ 0) be types from the same type lattice, q.v. Then type T is the most specific common supertype for types T1, T2, ..., Tm if and only if it’s a common supertype (q.v.) for those types and no proper subtype of T is also a common supertype for those types. Note: It can be shown—see the Manifesto book—that, given types T1, T2, ..., Tm, the corresponding most specific common supertype T always exists and is unique (though it might be one of those specified types T1, T2, ..., Tm, or even the pertinent maximal type, q.v.); in fact, it’s the least upper bound, q.v., of types T1, T2, ..., Tm. Note too that (a) if m = 1, then the set of types T1, T2, ..., Tm reduces to just T1, and T1 itself is the most specific common supertype for that set; (b) if m = 0, then the set of types T1, T2, ..., Tm is empty, and the most specific common supertype is the pertinent minimal type. Contrast least specific common subtype; least specific common supertype; most specific common subtype.

Examples: 1. With reference to Fig. 2, the most specific common supertype for types SQUARE and POLYGON is POLYGON, and the most specific common supertype for ELLIPSE and SQUARE is PLANE_FIGURE. 2. With reference to Fig. 3, the most specific common supertype for types RECTANGLE and RHOMBUS is PARALLELOGRAM. 3. With reference to Fig. 4, the most specific common supertype for types RIGHT KITE and RHOMBUS is KITE. Note that QUADRILATERAL is also a common supertype in this example, but it’s not the most specific one.

Note: As mentioned under intersection type, whereas least specific common subtypes are always intersection types, most specific common supertypes aren’t necessarily union types, because there might reasonably be cases in which the most specific common supertype contains values that aren’t values of any of its immediate subtypes. In Fig. 3, for example, the most specific common supertype for types RECTANGLE and RHOMBUS is PARALLELOGRAM, yet there certainly exist parallelograms that are neither rectangles nor rhombuses (rhombi, if you prefer).

most specific common supertype (relation types) Let T1, T2, ..., Tm (m ≥ 0) be relation types from the same type lattice, q.v.; by definition, then, those types all have the same attribute names, say A1, A2, ..., An (n ≥ 0). Let the type of attribute Aj (j = 1, 2, ..., n) within type Ti (i = 1, 2, ..., m) be Tij. Then type T = RELATION {<A1,T01>,<A2,T02>, ...,<An,T0n>} is the most specific common supertype for types T1, T2, ..., Tm if and only if, for all j (j = 1, 2, ..., n), type T0j is the most specific common supertype for types T1j, T2j, ..., Tmj. See also most specific common supertype; contrast least specific common subtype (relation types); least specific common supertype (relation types); most specific common supertype (tuple types).

Example: With reference to Fig. 5, the most specific common supertype for (e.g.) relation types CR and ES is relation type ER.

most specific common supertype (tuple types) Let T1, T2, ..., Tm (m ≥ 0) be tuple types from the same type lattice, q.v.; by definition, then, those types all have the same attribute names, say A1, A2, ..., An (n ≥ 0). Let the type of attribute Aj (j = 1, 2, ..., n) within type Ti (i = 1, 2, ..., m) be Tij. Then type T = TUPLE {<A1,T01>,<A2,T02>,...,<An,T0n>} is the most specific common supertype for types T1, T2, ..., Tm if and only if, for all j (j = 1, 2, ..., n), type T0j is the most specific common supertype for types T1j, T2j, ..., Tmj. See also most specific common supertype; contrast least specific common subtype (tuple types); least specific common supertype (tuple types); most specific common supertype (relation types).

Example: With reference to Fig. 5, the most specific common supertype for (e.g.) tuple types ER and ES is tuple type ER.

most specific type Let value x be of type T and not of any proper subtype of T; then T is the most specific type of x (and the set of types possessed by x is, precisely, the set of all supertypes of T). Note that T isn’t necessarily a minimal type, nor even a leaf type. For scalar types, in fact, it can’t possibly be the sole minimal type, which is type omega; for tuple types, it might be the corresponding minimal type, but only if that type is nonempty, which it usually won’t be; for relation types, it’ll be the corresponding minimal type if and only if x is an empty relation. See most specific type (relation types); most specific type (tuple types).

Further, let exp be an expression. Then exp has the same most specific type as the value it denotes. Observe that most specific types are (a) unique; (b) not known until run time (in general). Contrast least specific type.

Example: With reference to Fig. 3, if x is of type SQUARE and not of any proper subtype of SQUARE (in fact, of course, SQUARE doesn’t have any proper subtypes in the case at hand), then the most specific type of x is SQUARE, and the set of types possessed by x is SQUARE, RECTANGLE, RHOMBUS, PARALLELOGRAM, and alpha.

Note: Elsewhere in this dictionary, the most specific type of x is denoted MST(x); likewise, the most specific type of exp is denoted MST(exp). Note further that an important special case occurs when the expression exp consists of a simple variable reference, V; in this case, it’s usual to refer to MST(V) as the most specific type of the variable V as such, as well as of the expression consisting of a reference to that variable.

most specific type (relation types) Let relation x be of type T and not of any proper subtype of T; then T is the most specific type of x (and the set of types possessed by x is, precisely, the set of all supertypes of T). Note that T isn’t necessarily a minimal type, nor even a leaf type. Further, let exp be a relational expression. Then exp has the same most specific type as the relation it denotes. Observe that most specific relation types are (a) unique; (b) not known until run time (in general). See also most specific type; contrast least specific type (relation types).

Note: It follows from the foregoing definitions that if T is the most specific type for some relation x and A is some attribute within T, then the type of A within T is the most specific common supertype of the most specific types of all of the A values in x. By way of example, let relation x be as follows:

┌──────────────┬────────────────┐
│ E  : ELLIPSE │ R  : RECTANGLE │
├══════════════╪════════════════┤
│ e1 : circle  │ r1 : rectangle │
│ e2 : ellipse │ r2 : square    │
│ e3 : circle  │ r3 : square    │
└──────────────┴────────────────┘

(Most specific types are shown in lowercase italics.) The most specific type of this relation is RELATION {E ELLIPSE, R RECTANGLE}—not, as might intuitively have been thought, RELATION {E CIRCLE, R SQUARE}. For if we were to define this latter to be the most specific type of x, then certain tuples in x would have attribute values “of the wrong type”; for example, the <e2,r2> tuple would contain an E value of type ELLIPSE and not CIRCLE, and we would have a “noncircular circle” (q.v.) on our hands.

Two further examples: The most specific type of the empty relation of type RELATION {E ELLIPSE, R RECTANGLE} is RELATION {E omega, R omega}; the most specific type of any relation—necessarily either TABLE_DUM or TABLE_DEE—of type RELATION { } is RELATION { } itself.

Note: Elsewhere in this dictionary, the most specific type of relation x is denoted MST(x); likewise, the most specific type of the relational expression exp is denoted MST(exp), and the most specific type of attribute A of relation x is denoted MST(A). Note further that an important special case occurs when the expression exp consists of a simple relation variable (relvar) reference, V; in this case, it’s usual to refer to MST(V) as the most specific type of the relvar V as such, as well as of the expression consisting of a reference to that relvar.

most specific type (tuple types) Let tuple x be of type T and not of any proper subtype of T; then T is the most specific type of x (and the set of types possessed by x is, precisely, the set of all supertypes of T). Note that T isn’t necessarily a minimal type (in fact it can’t be, unless that minimal type is nonempty), nor even a leaf type. Further, let exp be a tuple expression. Then exp has the same most specific type as the tuple it denotes. Observe that most specific tuple types are (a) unique; (b) not known until run time (in general). See also most specific type; contrast least specific type (tuple types).

Note: It follows from the foregoing definitions that if T is the most specific type for some tuple x and A is some attribute within T, then the type of A within T is just the type of the A value in x. By way of example, let tuple x be as follows:

┌──────────────┬────────────────┐
│ E  : CIRCLE  │ R  : SQUARE    │
├──────────────┼────────────────┤
│ e3 : circle  │ r3 : square    │
└──────────────┴────────────────┘

(Attribute value most specific types are shown in lowercase italics.) As the heading indicates, the most specific type of this tuple is TUPLE {E CIRCLE, R SQUARE}.

By way of another example, the most specific type of the sole tuple of type TUPLE { }—viz., the 0-tuple—is TUPLE { } itself.

Note: Elsewhere in this dictionary, the most specific type of tuple x is denoted MST(x); likewise, the most specific type of the tuple expression exp is denoted MST(exp), and the most specific type of attribute A of tuple x is denoted MST(A). Note further that an important special case occurs when the expression exp consists of a simple tuple variable reference, V; in this case, it’s usual to refer to MST(V) as the most specific type of the tuple variable V as such, as well as of the expression consisting of a reference to that variable.

MST (...) Most specific type of. See model of a variable; model of an expression; most specific type.

multiple inheritance A form of inheritance in which a proper subtype can have any number, n say, of immediate supertypes (n > 1). Contrast single inheritance (but single inheritance is, of course, just that degenerate case of multiple inheritance for which the condition n > 1 is relaxed). Note that tuple inheritance and relation inheritance are necessarily multiple, and scalar inheritance is too if type omega is taken into account (since type omega is a subtype of every scalar type).

Examples: See Figs. 3, 4, and 5.

noncircular circle A contradiction in terms, typical of the logical absurdities that can and do occur if S by C, q.v., and G by C, q.v., aren’t supported, and used as a convenient shorthand to refer to such absurdities in general. To spell out the details of this particular solecism: Consider the type hierarchy of Fig. 2; however, let’s agree for simplicity to ignore all of the types in that figure apart from types ELLIPSE and CIRCLE. Then a noncircular circle is something the system thinks is a circle but actually isn’t—i.e., it’s a value whose most specific type as far as the system is concerned is CIRCLE and yet has different semiaxis lengths, and thus logically ought to have most specific type ELLIPSE. Note: Noncircular circles and suchlike solecisms can’t occur in the Manifesto model. See also circular noncircle.

nondummy type A regular type (the term nondummy type is sometimes used for emphasis).

noninstantiable type Term sometimes used in OO contexts to mean a union type. The name presumably derives from the fact that such a type has no “instances,” where the term “instances” presumably means—at least in this context—values whose most specific type is the type in question (it has nothing to do with instance variables, q.v., nor with instantiation in the sense of logic). Note, however, that elsewhere in those same OO contexts that same term instance is certainly taken to include variables, etc., as well as values as such; in fact, it’s often used a synonym for object. Contrast instantiable type.

nonunion type A regular type that isn’t a union type; equivalently, a scalar type such that there exists at least one value with most specific type the type in question. The term nonunion type is sometimes used for emphasis.

Examples: See the examples under union type.

omega The minimal scalar type. Type omega (a) contains no values at all, (b) has no immediate subtype, and (c) is an immediate subtype for every scalar leaf type (with respect to the set of available types, q.v., in the case of property (c)). No scalar type other than type omega possesses any of properties (a), (b), or (c). Note that, by definition, type omega is system defined; unique; primarily conceptual in nature; a dummy type, q.v. (and in fact a union type, q.v., albeit vacuously so); and not a leaf type, q.v. Note further that the type constraint for omega is simply FALSE; the expression IS_omega (exp), where exp is a scalar expression, always evaluates to FALSE; and the expression TREAT_AS_omega (exp), where exp is a scalar expression always fails (or would always fail, rather, since the expression is clearly a contradiction in terms and might well not be recognized as legitimate). See also T_omega.

It’s worth pointing out that type omega inherits every read-only operator that applies to scalar values, but vacuously so (since those operators can never be invoked on any value of the type). A similar remark applies to type constraints also.

operator inheritance See type inheritance.

operator version Same as implementation version.

overlapping types Types T1 and T2 overlap if and only if there exists at least one value that’s common to both. (Observe in particular, therefore, that an empty type doesn’t overlap with anything, not even itself). Note that the foregoing definition is equivalent to saying T1 and T2 have a nonempty common subtype—and if they do have a nonempty common subtype, they necessarily have a nonempty common supertype also, though the converse is false. Note too that types can’t possibly overlap if they’re not from the same type lattice, q.v. Contrast disjoint types.

overloading (With inheritance) In an inheritance context, the term overloading is sometimes used to mean inclusion polymorphism, q.v. This particular usage is strongly deprecated, however, because there’s an important logical difference between the two concepts, a difference that can be characterized as follows:

• Inclusion polymorphism means there’s just one operator, with several distinct implementation versions under the covers, but the user doesn’t need to know the versions in question are in fact distinct—as far as the user is concerned, there’s just the one operator.

• Overloading polymorphism means there are several distinct operators with the same name, and the user does need to know the operators in question are in fact distinct.

overriding (With inheritance) In an inheritance context, overriding is often confused with either overloading or inclusion polymorphism or both, though it shouldn’t be. For example (from Douglas K. Barry, The Object Database Handbook: How to Select, Implement, and Use Object-Oriented Databases, Wiley Publishing, 1996—italics in the original):

The object model allows ... multiple use of the same method, which is called overloading. The overloaded definition of Display in the [subclass] overrides the definition of Display in the [superclass] because it is lower in the class hierarchy.

And elsewhere in the same book:

Overriding: Where a method for a subclass adds to or replaces a method of its superclass.

Incidentally, these quotes seem to embrace the idea that changing semantics, q.v., is a virtue. They also seem to be confused over the difference between a model and its implementation, though in fact this latter is a criticism that can be leveled at OO writings in general.

parent type Term occasionally used to mean an immediate supertype.

possrep inheritance Let scalar type T be an immediate supertype of scalar type T′. Then every possrep for values of type T is necessarily, albeit implicitly, a possrep for values of type T′ as well. (With reference to Fig. 2, for example, circles are ellipses and so, by definition, “possibly representable”—like ellipses in general—in terms of their major and minor semiaxis lengths and their center.) Thus, possreps might be regarded as further “properties” that are inherited by subtypes from supertypes in general. However, such an inherited possrep isn’t regarded as an explicitly declared one in the sense explained under possible representation in Part I of this dictionary, because to regard it as such would lead to a contradiction concerning inheritance of update operators (inheritance of THE_ pseudovariables, to be specific—again, see Part I of this dictionary). Thus, to say that type T′ inherits a possrep from type T is only a manner of speaking—it doesn’t carry any formal weight. Contrast derived possrep.

Example: With reference to Fig. 2 again, type CIRCLE inherits a possrep with components A, B, and CTR from its immediate supertype ELLIPSE. Now, if that possrep were a declared one, an assignment such as this one to a variable C of declared type CIRCLE—

THE_A ( C ) := LENGTH ( 5.0 ) ;

—would have to be legal. But assignments like this one, if permitted, are exactly what give rise to noncircular circles (q.v.) and the like, which is why they’re prohibited (at least in the Manifesto model). It follows that inherited possreps can’t be considered declared ones.

Principle of Read-Only Operator Inheritance Let Op be a read-only operator, let P be a parameter to Op, and let T be the declared type of P. Then the declared type of the argument expression, and hence the most specific type of the argument as such, corresponding to P in an invocation of Op can be any nonempty subtype T′ of T. In other words, the operator Op applies to values of type T and therefore, necessarily, to values of type T′—The Principle of Read-Only Operator Inheritance. It follows that such operators are polymorphic, since they apply to values of several different types—The Principle of Read-Only Operator Polymorphism (where the kind of polymorphism involved is, specifically, inclusion polymorphism, q.v.). It further follows that wherever a value of type T is permitted, a value of any subtype of T is also permitted—The Principle of Value Substitutability. Note: If Op is an update operator and P is a parameter to Op that isn’t subject to update, then Op behaves as if it were a read-only operator as far as P is concerned, and all relevant aspects of this definition therefore apply directly, mutatis mutandis.

Example: See the example under argument involving the read-only version of the MOVE operator.

Principle of Read-Only Operator Polymorphism See Principle of Read-Only Operator Inheritance.

Principle of Update Operator Inheritance Let Op be an update operator, let P be a parameter to Op that’s subject to update, and let T be the declared type of P. Then it might or might not be the case that the declared type of the argument expression (which must in fact be a variable reference specifically), and hence the most specific type of the argument (a variable) as such, corresponding to P in an invocation of Op can be some nonempty proper subtype T′ of type T. It follows that for each such update operator Op and for each parameter P to Op that’s subject to update, it’s necessary to state explicitly for which proper subtypes T′ of the declared type T of parameter P operator Op is inherited—The Principle of Update Operator Inheritance. (And if update operator Op isn’t inherited in this way by type T′, it isn’t inherited by any proper subtype of type T′ either. See signature for further discussion.) Update operators are thus only conditionally polymorphic—The Principle of Update Operator Polymorphism. Thus, if Op is an update operator and P is a parameter to Op that’s subject to update and T′ is a proper subtype of the declared type T of P for which Op is inherited, then by definition it’s possible to invoke Op with an argument expression (actually a variable reference) corresponding to parameter P that’s of declared type T′—The Principle of Variable Substitutability.

Examples: To see why it makes no sense for update operators to be inherited unconditionally, let variables R and S be of declared types RECTANGLE and SQUARE, respectively (see Fig. 2). Clearly, then, it’s possible—speaking rather loosely—to change the height of R without changing its width; more precisely, it’s possible to update R in such a way as to replace the current rectangle value r1 by a new rectangle value r2 that has the same width as r1 but a different height. Equally clearly, it’s not possible to do the same thing to S, because squares must always have equal height and width. In other words, a certain update operator (“change the height but not the width”) is effectively defined for type RECTANGLE but not for type SQUARE.

So update operator inheritance has to be conditional; in other words, which update operators are inherited by which subtypes must be specified explicitly (see signature). For example, with reference to Fig. 2 once again, we might reasonably specify the following:

• The update operators that apply to variables of declared type ELLIPSE are (a) assignment to THE_A, THE_B, and THE_CTR and (b) the update form of MOVE (see the examples under signature).

• The update operators that apply to variables of declared type CIRCLE are (a) assignment to THE_CTR and THE_R and (b) the update form of MOVE.

And if we were to define, as we did in the examples under argument, type CIRCLE to have a proper subtype O_CIRCLE (where an “O-circle” is a circle with center the origin), then:

• The only update operator that applies to variables of declared type O_CIRCLE is assignment to THE_R.

Of course, the operators referred to above as assignments to some THE_ operator are all defined automatically anyway, by virtue of the fact that corresponding possreps have been explicitly declared for the pertinent types. See automatic definition.

Note: Despite the foregoing, some writers still argue that update operators, like read-only operators, should be inherited unconditionally, and some languages and systems do indeed behave that way. But it’s precisely such behavior that leads to logical absurdities such as circular noncircles, q.v., and noncircular circles, q.v. (not to mention the almost total lack of type constraint support found in SQL in particular!). For further discussion, see the Manifesto book.

Principle of Update Operator Polymorphism See Principle of Update Operator Inheritance.

Principle of Value Substitutability The principle that wherever a value of type T is permitted, a value of any subtype of T can be substituted. See Principle of Read-Only Operator Inheritance.

Principle of Variable Substitutability The principle that wherever a variable of declared type T is permitted, a variable of declared type some nonempty subtype of T can be substituted—but only if such substitution makes sense. See Principle of Update Operator Inheritance.

proper subtype Type T′ is a proper subtype of type T if and only if (a) it’s a subtype of T and (b) T and T′ are distinct. See also immediate subtype; proper supertype. Note: If T and T′ are scalar types, then there must be at least one value of type T that’s not a value of type T′ (see example value, second definition). As for tuple and relation types, the same will be true so long as none of type T’s attributes is of some empty type.

Examples: 1. With reference to Fig. 2, type SQUARE is a proper subtype of type POLYGON. Note in particular that there do exist polygons (i.e., values of type POLYGON) that aren’t squares (i.e., values of type SQUARE). 2. Here by contrast is an example involving two relation types, one a proper subtype of the other, such that the proper subtype isn’t a proper subset:

RELATION { E omega , R RECTANGLE }

RELATION { E omega , R omega }

Neither of these types is empty, despite the fact that they both have at least one attribute of an empty type; in fact, they both contain exactly one value, viz., the empty relation of most specific type RELATION {E omega, R omega}. 3. Similarly, given the following tuple types—

TUPLE { E omega , R RECTANGLE }

TUPLE { E omega , R omega }

—again one type is a proper subtype, but not a proper subset, of the other; in this case, however, both types are empty.

proper supertype Type T is a proper supertype of type T′ if and only if (a) it’s a supertype of T′ and (b) T and T′ are distinct. See also immediate supertype; proper subtype. Note: If T and T′ are scalar types, then there must be at least one value of type T that’s not a value of type T′ (see example value, second definition). As for tuple and relation types, the same will be true so long as none of type T’s attributes is of some empty type.

Examples: See the examples under proper subtype (note that T is a proper supertype of T′ if and only if T′ is a proper subtype of T).

properties Term used informally and generically to refer to the type constraints and read-only operators (sometimes update operators as well, depending on context) that apply to some given type T—in other words, anything that will or might be inherited by an immediate subtype T′ of the given type T. Note: The term properties is sometimes used, even more informally, to include possreps (q.v.) as well, since any possrep that applies to type T necessarily applies to type T′ as well and so can be thought of—but only informally—as also being inherited by T′ from T (see possrep inheritance).

R : IS_SAME_TYPE_AS See R : IS_T.

R : IS_T Let R be a relational expression, let A be a scalar attribute of the relation r denoted by R, let T be a scalar type, and let DT(A) and T overlap (this is a compile time check). Then the expression R : IS_T (A)—or some logical equivalent to that expression—returns a relation with (a) heading the same as that of r, except that DT(A) in that heading is T, and (b) body consisting of those tuples of r in which v(A) is of type T, except that DT(A) in each of those tuples is T. Note: Tutorial D also supports a generalized version of this operator of the form R : IS_SAME_TYPE_AS (exp,A), where DT(exp) and DT(A) aren’t limited to being scalar. This generalized version is effectively equivalent to R : IS_T (A), where T is DT(exp)—assuming for definitional purposes here that the expression R : IS_T (A) is syntactically valid.

Examples: Let relvar R have an attribute E of declared type ELLIPSE. Then (assuming the obvious operator precedence) the expression

R : IS_CIRCLE ( E ) WHERE THE_R ( E ) > LENGTH ( 2.0 )

returns a relation with (a) heading the same as that of R, except that the type of attribute E in that result is CIRCLE instead of ELLIPSE, and (b) body consisting of just those tuples from R in which the E value is of type CIRCLE and the radius for the circle in question has length greater than two. Note that, by contrast, the expression

R WHERE THE_R ( E ) > LENGTH ( 2.0 )

is invalid (it fails on a compile time type error), since THE_R is not defined for values of type ELLIPSE. Note too that the valid version—R : IS_CIRCLE (E) WHERE ... — is almost but not quite equivalent to the following:

R WHERE CASE
           WHEN IS_CIRCLE ( E ) THEN
                THE_R ( TREAT_AS_CIRCLE ( E ) ) > LENGTH ( 2.0 )
           WHEN NOT ( IS_CIRCLE ( E ) ) THEN FALSE
        END CASE

The difference is that this latter expression yields a relation with the same heading as R, rather than one in which the type of attribute E is CIRCLE. More generally, however, the expression

R : IS_T ( A )

is equivalent to, and is therefore shorthand for, the following:

( R WHERE IS_T ( A ) ) : TREAT_AS_T ( A )

Moreover, this latter expression is shorthand too (see R : TREAT_AS_T).

By way of another example, consider the relation types shown in Fig. 5. Let relvar R have an attribute X of declared type ER and let ESV be a variable of declared type and current most specific type both ES; then the expression

R : IS_SAME_TYPE_AS ( ESV , X )

returns a relation with (a) heading the same as that of R, except that the type of attribute X in that result is ES instead of ER, and (b) body consisting of just those tuples from R in which the X value is of type ES.

R : TREAT_AS_T Let R be a relational expression, let A be a scalar attribute of the relation r denoted by R, let T be a scalar type, and let DT(A) and T overlap (this is a compile time check). Then the expression R : TREAT_AS_T (A)—or some logical equivalent to that expression—either raises a run time type error (if MST(A) isn’t some subtype of type T) or returns a relation identical to r except that the type of attribute A in that relation is T (otherwise). Note: Tutorial D supports a generalized form of this operator, R : TREAT_AS_SAME_TYPE_AS (exp,A), where DT(exp) and DT(A) aren’t limited to being scalar. This generalized form is effectively equivalent to R : TREAT_AS_T (A), where T is DT(exp)—assuming for definitional purposes here that the expression R : TREAT_AS_T (A) is syntactically valid.

Examples: Let relvar R have an attribute E of declared type ELLIPSE. Then the expression

R : TREAT_AS_CIRCLE ( E )

either raises a run time type error (if any tuple in R has an E value of most specific type some proper supertype of CIRCLE), or returns a relation identical to the current value of R (otherwise), except that the type of attribute E in that result is CIRCLE instead of ELLIPSE. In other words, the expression shown is shorthand for the following:

EXTEND R : { E := TREAT_AS_CIRCLE ( E ) }

By way of another example, consider the relation types shown in Fig. 5. Let relvar R have an attribute X of declared type ER and let ESV be a variable of declared type and current most specific type both ES; then the expression

R : TREAT_AS_SAME_TYPE_AS ( ESV , X )

either raises a run time type error (if any tuple in R has an X value of most specific type some supertype of ES), or returns a relation identical to the current value of R (otherwise), except that the type of attribute X in that result is ES instead of ER. In other words, the expression shown is shorthand for the following:

EXTEND R : { X := TREAT_AS_SAME_TYPE_AS ( ESV , X ) }

receiver parameter See selfish method.

recursively defined type (With inheritance) A type defined in terms of itself. Let T be a scalar type, and let S(1), S(2), ... be a sequence of sets defined as follows:

S(1) = { t : t is the declared type of some scalar component, or of some attribute of some tuple valued or relation valued component, of some possrep for T }

S(i) = { t : t is the declared type of some scalar component, or of some attribute of some tuple valued or relation valued component, of some possrep for some type in S(i−1) }

          (i > 1)

If there exists some n (n > 0) such that some subtype or supertype of T is a member of S(n), then T is recursively defined.

As for tuple and relation types: Let H be a heading, and let S(1), S(2), ... be a sequence of sets defined as follows:

S(1) = { t : t is the declared type of some attribute in H }

S(i) = { t : t is the declared type of some component of some possrep for some scalar type, or of some attribute of some tuple or relation type, in S(i−1) }

          (i > 1)

If there exists some n (n > 0) such that some subtype or supertype of either TUPLE H or RELATION H is a member of S(n), then the heading H is recursively defined (and any tuple or relation type with heading H is therefore recursively defined as well).

The relational model currently prohibits recursively defined types.

regular root type A type that’s both (a) a regular (and hence necessarily scalar) type and (b) a root type.

regular type A scalar type that’s not a dummy type. Note that the concept of dummy vs. regular types doesn’t really apply to nonscalar types. For further discussion, see dummy type.

relation assignment See relational assignment.

relation comparison See relational comparison.

relation equality See relational equality.

relation subtype See subtype (relation types).

relation supertype See supertype (relation types).

relation type inheritance A form of inheritance in which the types are relation types specifically. Note that relation type inheritance is necessarily multiple; note too that it has nothing to do with subtables and supertables, q.v.

Example: See Fig. 5.

relational assignment (With inheritance) Let R and r be a relvar and a relation, respectively, such that the most specific type MST(r) of r is some subtype of the declared type DT(R) of R. Then (and only then) r can be assigned to R; the assignment has the effect of setting v(R) equal to r and MST(R) equal to MST(r). Note: In order for the assignment to be syntactically valid, the declared type DT(rx) of the expression rx used to denote relation r must be some subtype of the declared type DT(R) of relvar R (this condition is implied by the fact that MST(r) is required to be some subtype of DT(R), and is a compile time check).

Examples: Let relvars RE and RC be of declared types RELATION {E ELLIPSE} and RELATION {E CIRCLE}, respectively, and consider the following assignment:

RE := RC ;

In this example, compile time type checking succeeds (DT(RC) is a subtype of DT(RE)), and at run time v(RE) and MST(RE) are set equal to v(RC) and MST(RC), respectively.

Now consider this assignment:

RC := RE ;

This example raises a compile time type error, because DT(RE) isn’t a subtype of DT(RC). By contrast, if the expression RE in this example were to be replaced by the expression TREAT_AS_SAME_TYPE_AS (RC,RE), then compile time type checking would succeed; however, this latter expression will raise a type error—a run time type error, of course—if MST(RE) isn’t some subtype of RELATION {E CIRCLE} at run time (see TREAT).

relational comparison (With inheritance) A boolean expression of the form (rx1) theta (rx2), where (a) rx1 and rx2 are relational expressions and (b) theta is any comparison operator that makes sense for relations (“=”, “≠”, “⊆”, etc.). Note: If theta is “=” or “≠”, then, in order for the comparison to be syntactically valid, the declared types DT(rx1) and DT(rx2) must overlap (this is a compile time check). Also, the parentheses enclosing rx1 and rx2 in the comparison might not be needed in practice.

relational equality (With inheritance) Let r1 and r2 be relations such that the most specific types MST(r1) and MST(r2) overlap. Then r1 and r2 can be compared for equality; the comparison returns TRUE if and only if r1 is equal to r2 (in which case MST(r1) is equal to MST(r2) also). Note: In order for the comparison to be syntactically valid, the declared types DT(rx1) and DT(rx2) of the expressions rx1 and rx2 used to denote r1 and r2, respectively, must overlap (this condition is implied by the fact that MST(rx1) and MST(rx2) are required to overlap, and is a compile time check).

result covariance Let Op be a read-only operator and let T be the declared type of the result as specified in some invocation signature for Op (see signature). Then an invocation of Op whose arguments are of types as specified in that invocation signature can return a result whose most specific type is any nonempty subtype of T. Contrast argument contravariance.

Examples: First, observe that result covariance as just defined is essentially just a consequence of The Principle of Value Substitutability; that is, just as a reference to a variable of declared type T can denote a value of any nonempty subtype of T (in general), so also an invocation of an operator with declared type T can denote a value of any nonempty subtype of T (in general). But, although the definition given above does capture the essence of the concept, there’s quite a lot more to be said on the subject of result covariance in general. First, here for interest is a definition from the OO literature (it’s taken from Elisa Bertino and Lorenzo Martino, Object-Oriented Database Systems: Concepts and Architectures, Addison-Wesley, 1993, but is somewhat paraphrased here):

A type T′ is a subtype of a type T if ... for each method M of T there is a corresponding method M′ of T′ such that ... if there is a result, then the type of the result of M′ is a subtype of the type of the result of M (rule of covariance in results).

Now, this definition can be criticized on a number of grounds. First of all, as pointed out in connection with some related text under argument contravariance, it seems to be circular—it defines what it means for some type to be a subtype of another in terms of the concept of some type being a subtype of another. Second, it seems to be insisting—though it’s hard to be sure—that the result of M′, if there is one, must be of some (apparently proper) subtype of the type of the result of M: surely an undesirable state of affairs in practice. Third, it seems to be saying that T′ is a subtype of T if substitutability applies, whereas the Manifesto model says that substitutability applies if T′ is a subtype of T.

Be that as it may, consider by way of a simple example the type hierarchy of Fig. 2 and the following operator definition:

OPERATOR COPY ( E ELLIPSE ) RETURNS ELLIPSE ;
   RETURN E ;
END OPERATOR ;

An invocation of this operator will return either a circle or just an ellipse, depending on whether its argument is a circle or just an ellipse. In this example, then, the type—the most specific type, that is—of the result clearly “covaries” with the type of the sole argument (whence the term result covariance, presumably). So far, so good. But what about the following example?

OPERATOR EORC ( B BOOLEAN ) RETURNS ELLIPSE ;
   RETURN ( IF B THEN ELLIPSE ( ... )
                 ELSE CIRCLE  ( ... ) END IF ) ;
END OPERATOR ;

An invocation of this operator will return either a circle or just an ellipse, depending on the value, not the type, of its argument. In this example, then, we obviously can’t say the type of the result covaries with the type, as such, of the argument. What’s more, it would surely be a little odd to think of it as covarying with the value of the argument, since the mapping between argument values and result types could in principle be arbitrarily complex—much more complex, surely, than the simple term “covarying” could reasonably be expected to signify.

For a third example, consider the operator MOVE (read-only version), with invocation signatures as follows (see signature):

( ELLIPSE , RECTANGLE ) RETURNS ELLIPSE
( ELLIPSE , SQUARE    ) RETURNS ELLIPSE
( CIRCLE  , RECTANGLE ) RETURNS CIRCLE
( CIRCLE  , SQUARE    ) RETURNS CIRCLE

Here the result type does covary with the type of the first argument but not with that of the second.

The net of the foregoing discussion is that—unlike the concept of argument contravariance, q.v.—the concept of result covariance is both necessary and desirable; in fact, it’s a logical consequence of The Principle of Value Substitutability, q.v. However, the term result covariance as such is inappropriate, and logically unnecessary, and in some ways quite misleading.

RETURNS (With inheritance) See signature.

reuse See code reuse.

root Abbreviation for root type.

root type A type with no immediate supertype other than the pertinent maximal type, q.v. Distinct root types are disjoint.

Examples: In Fig. 2, PLANE_FIGURE is the only root type; in Fig. 3, PARALLELOGRAM is the only root type; in Fig. 4, QUADRILATERAL is the only root type; in Fig. 5, ER is the only root type. No two of these root types overlap.

run time binding As noted under binding, the term binding is used in the inheritance context to refer to the process of determining which implementation version of a given operator is to be executed in response to a given invocation of the operator in question. Such binding can be done at compile time or run time or both. Run time binding in particular (at least as that term is understood in the Manifesto model) can be defined thus: Given some invocation of some operator Op, it’s the process of finding, at run time, the unique invocation signature for Op—see signature—for which the declared types of the parameters exactly match the most specific types of the corresponding arguments to that invocation, thereby causing the unique corresponding implementation version, q.v., of Op to be invoked. Note: In principle, binding can always be done at compile time—run time binding is logically unnecessary (though it might lead to better performance). See implementation version for further discussion; see also compile time binding.

run time type checking Checking at run time that the types of the arguments to an invocation of some operator conform to that operator’s parameter type requirements, as specified by that operator’s specification signature. Note: In the Manifesto model, such checking reduces to a single special case (all other type checking can be done at compile time): namely, checking at run time that the most specific type of the argument to a TREAT invocation is some subtype of the specified target type. Contrast compile time type checking.

Examples: See the examples under TREAT.

run time type error The error that occurs if run time type checking (q.v.) fails. In the Manifesto model, such errors can occur only in the context of TREAT, q.v.

S by C Specialization by constraint.

scalar subtype See subtype.

scalar supertype See supertype.

SELF See selfish method.

selfish method A method in the OO sense for which one parameter—the distinguished, receiver, or target parameter—is singled out for special semantic treatment (and special syntactic treatment also, necessarily), instead of all parameters being treated equally. The special treatment in question consists in using the argument corresponding to the distinguished parameter, and no other arguments, to control the binding process—i.e., to determine the implementation version, q.v., to be invoked. The term selfish method derives from the fact that the distinguished parameter is typically unnamed and thus has to be referenced within the method’s implementation code in some ad hoc way, typically by means of the keyword SELF.

Note: In practice, OO methods are usually assumed to be selfish in the foregoing sense. For example, here’s a quote from Douglas K. Barry, The Object Database Handbook: How to Select, Implement, and Use Object-Oriented Databases (Wiley Publishing, 1996):

[Polymorphism is a] mechanism that selects a method based on the type of the target operand.

(Note the last eight words in particular.) And it’s worth pointing out that selfish methods do make the binding process simpler than it would otherwise be (simpler, that is, than the binding process as defined elsewhere in this part of the dictionary). But “simpler” here really means simpler for the system, whose job it is to perform the actual binding; unfortunately, it’s easy to see by contrast that it can have the effect of making matters much more complicated for the person whose job it is to write the code for the various implementation versions of the operator in question. See the Manifesto book for detailed arguments in support of this position.

set of available types See available types.

signature (With inheritance) Let Op be a read-only operator, with parameters P1, P2, ..., Pn (and no others). Also, let parameter Pi have declared type DTi (i = 1, 2, ..., n)—but note immediately that a large part of the point of the discussion that follows is to make this remark, concerning parameter declared types, much more precise. In an invocation of Op, then, the argument Ai corresponding to parameter Pi can have as its most specific type MSTi any nonempty subtype of DTi. (It follows a fortiori that the expression Xi denoting argument Ai can have as its declared type any type that’s simultaneously a subtype of DTi and a supertype of MSTi.) Conceptually, therefore, Op has a specification signature, denoting that operator as perceived by the user, and a set of invocation signatures, where:

• The specification signature consists of the operator name, the parameter declared types PDT1, PDT2, ..., PDTn, and the result declared type RDT.

• Each invocation signature consists of one possible combination of argument expression declared types ADT1, ADT2, ..., ADTn, together with the declared type IRDT of the result—necessarily a subtype of RDT—produced by an invocation of Op with arguments of most specific types equal to the declared types ADT1, ADT2, ..., ADTn, respectively, specified in the invocation signature in question.

Note: Under the covers, each distinct invocation signature will be associated with exactly one implementation version of Op, though a given implementation version might be associated with any number of distinct invocation signatures. See binding; implementation version.

Note, therefore, that (to repeat) Op has exactly one specification signature, plus exactly one invocation signature for each possible combination of argument expression declared types. (At least, that’s what the model says, though certain obvious shorthands are likely to be available in concrete syntax—see further discussion below.)

Example: Consider the read-only version of the operator MOVE (mentioned in the examples under argument and elsewhere), which moves a specified ellipse such that it becomes centered on the center of a specified rectangle. Abstractly, that operator might have a specification signature that looks like this:

MOVE ( ELLIPSE , RECTANGLE ) RETURNS ELLIPSE

As far as the user is concerned, in other words, MOVE is an operator that takes an ellipse and a rectangle as arguments and returns an ellipse as result—and the following implementation code, repeated from the examples under argument, supports that understanding (CTR here is a read-only operator that returns the center of its rectangle argument):

OPERATOR MOVE ( E ELLIPSE , R RECTANGLE ) RETURNS ELLIPSE ;
   RETURN ELLIPSE ( THE_A ( E ) , THE_B ( E ) , CTR ( R ) ) ;
END OPERATOR ;

Because of value substitutability, however (q.v.), a given MOVE invocation can have a value of any nonempty subtype of ELLIPSE as its first argument and a value of any nonempty subtype of RECTANGLE as its second argument. Thus, we see from Fig. 2 that the first argument can have most specific type either ELLIPSE or CIRCLE, and the second argument can have most specific type either RECTANGLE or SQUARE. Moreover, if the first argument is in fact a circle and not just an ellipse, the result will clearly be a circle too. At least abstractly, then, MOVE will have four distinct invocation signatures that might look like this:

( ELLIPSE , RECTANGLE ) RETURNS ELLIPSE
( ELLIPSE , SQUARE    ) RETURNS ELLIPSE
( CIRCLE  , RECTANGLE ) RETURNS CIRCLE
( CIRCLE  , SQUARE    ) RETURNS CIRCLE

Thus, e.g., if C and R are variables of declared types CIRCLE and RECTANGLE, respectively, then the declared type of the expression MOVE (C,R) is CIRCLE.

In Tutorial D, invocation signatures are defined by means of the RETURNS clause, q.v. For example, here again is the definition of MOVE as a read-only operator, now shown complete:

OPERATOR MOVE ( E ELLIPSE , R RECTANGLE )
         RETURNS
            CASE
               WHEN IS_ELLIPSE ( E ) AND IS_RECTANGLE ( R ) THEN ELLIPSE
               WHEN IS_ELLIPSE ( E ) AND IS_SQUARE    ( R ) THEN ELLIPSE
               WHEN IS_CIRCLE  ( E ) AND IS_RECTANGLE ( R ) THEN CIRCLE
               WHEN IS_CIRCLE  ( E ) AND IS_SQUARE    ( R ) THEN CIRCLE
            END CASE ;
   RETURN ELLIPSE ( THE_A ( E ) , THE_B ( E ) , CTR ( R ) ) ;
END OPERATOR ;

Observe that the specification signature as such is now effectively defined by means of the combination of the operator name, the parameter declared types, and that particular one of the invocation signatures that has argument declared types all equal to the corresponding parameter declared types—in other words, the first of the invocation signatures shown, in the case at hand. However, observe further that (a) the CASE expression in the RETURNS specification is evaluated at compile time, not run time (to be specific, it’s evaluated whenever the compiler processes a MOVE invocation); hence, (b) the various “IS_” operator invocations in that CASE expression are also evaluated at compile time, and (c) those “IS_” operator invocations therefore return TRUE if and only if the corresponding declared types are as indicated. In other words, those “IS_” operators aren’t the usual operators of those names, which return TRUE if and only if their operands have the indicated types at run time. If this state of affairs is considered undesirable, it could perhaps be avoided by insisting that the various WHEN clauses appear in an appropriate sequence, as here:

OPERATOR MOVE ( E ELLIPSE , R RECTANGLE )
         RETURNS
            CASE
               WHEN IS_CIRCLE  ( E ) AND IS_SQUARE    ( R ) THEN CIRCLE
               WHEN IS_CIRCLE  ( E ) AND IS_RECTANGLE ( R ) THEN CIRCLE
               WHEN IS_ELLIPSE ( E ) AND IS_SQUARE    ( R ) THEN ELLIPSE
               WHEN IS_ELLIPSE ( E ) AND IS_RECTANGLE ( R ) THEN ELLIPSE
             END CASE ;
   RETURN ELLIPSE ( THE_A ( E ) , THE_B ( E ) , CTR   ( R ) ) ;
END OPERATOR ;

With this revised sequence, it will still be the case that the “IS_” operator invocations are evaluated at compile time and so are interpreted in terms of declared types, but the results they return will be the same as if they were interpreted in terms of most specific types at run time.

Now, we’ve said that if C and R are variables of declared types CIRCLE and RECTANGLE, respectively, then the declared type of the expression MOVE (C,R) is CIRCLE. Moreover, the RETURNS clause means the compiler is aware of such matters, as just explained. As a consequence, various TREAT invocations that might otherwise have been needed won’t be needed after all. For example, given C and R as above, we can write

C := MOVE ( C , R ) ;

instead of what we would otherwise have had to write:

C := TREAT_AS_CIRCLE ( MOVE ( C , R ) ) ;

Note: As pointed out in Part I of this dictionary, few writers (or languages or systems, come to that) seem to distinguish properly—or at all—between specification and invocation signatures. As the foregoing example suggests, however, languages and systems that fail to make this distinction will probably require more TREAT invocations than ones that do make it.

To return to the question of concrete syntax: As already suggested, certain obvious shorthands are surely possible in practice. For example, the RETURNS clause in the foregoing MOVE example might reasonably be abbreviated to just:

RETURNS IF IS_CIRCLE ( E ) THEN CIRCLE ELSE ELLIPSE END IF

Another possible shorthand is illustrated by the following self-explanatory example:

RETURNS SAME_TYPE_AS ( E )

Now suppose, as we did in the examples under argument, that type CIRCLE has a proper subtype O_CIRCLE (where an “O-circle” is a circle with center the origin):

TYPE O_CIRCLE
     IS { CIRCLE
          CONSTRAINT THE_CTR ( CIRCLE ) = POINT ( 0.0 , 0.0 )
          POSSREP { R = THE_R ( CIRCLE ) } } ;

Conceptually, then, the read-only version of MOVE will now require six invocation signatures, thus (note the last two in particular):

( ELLIPSE  , RECTANGLE ) RETURNS ELLIPSE
( ELLIPSE  , SQUARE    ) RETURNS ELLIPSE
( CIRCLE   , RECTANGLE ) RETURNS CIRCLE
( CIRCLE   , SQUARE    ) RETURNS CIRCLE
( O_CIRCLE , RECTANGLE ) RETURNS CIRCLE
( O_CIRCLE , SQUARE    ) RETURNS CIRCLE

Here’s a possible RETURNS clause shorthand:

RETURNS
   CASE
      WHEN IS_CIRCLE  ( E ) THEN CIRCLE
      WHEN IS_ELLIPSE ( E ) THEN ELLIPSE
   END CASE

Here we’re assuming further that the compile time version of IS_CIRCLE will return TRUE if the declared type of E is any subtype of CIRCLE (including O_CIRCLE in particular). Note: The second of these WHEN specifications might be simplified to just ELSE ELLIPSE—see the paragraph immediately following. (Alternatively, the entire CASE expression might be replaced by IF IS_CIRCLE(E) THEN CIRCLE ELSE ELLIPSE END IF.)

One final example, to illustrate yet another possibility: Suppose (a) read-only operator Op has a specification signature involving two parameters X and Y, both of declared type ELLIPSE; (b) result declared types are defined (via appropriate invocation signatures) corresponding to the argument expression declared type combinations ELLIPSE / ELLIPSE, ELLIPSE / CIRCLE, and CIRCLE / ELLIPSE (only); and (c) Op is invoked with the argument expression declared type combination CIRCLE / CIRCLE. That invocation doesn’t match any of the specified invocation signatures exactly—so what’s its declared type? The simplest solution to this problem (perhaps not the only one) is to allow the CASE expression that specifies the various invocation signatures to include an appropriate ELSE clause, as here:

CASE
   WHEN IS_ELLIPSE ( X ) AND IS_CIRCLE  ( Y ) THEN ...
   WHEN IS_CIRCLE  ( X ) AND IS_ELLIPSE ( Y ) THEN ...
   WHEN IS_ELLIPSE ( X ) AND IS_ELLIPSE ( Y ) THEN ...
   ELSE ...
END CASE

So much for the read-only case; we turn now to the question of signatures for update operators. Here (again repeated from the examples under argument) is MOVE as an update operator:

OPERATOR MOVE ( E ELLIPSE , R RECTANGLE ) UPDATES { E } ;
   THE_CTR ( E ) := CTR ( R ) ;
END OPERATOR ;

Now there’s no question of specifying the declared type of the result of invoking the operator, because update operator invocations don’t have a result. But signatures are still required for purposes of binding, q.v., and type checking, q.v., as well as for defining the user’s perception of the operator. Thus, the specification signature in the example might look like this:

MOVE ( ELLIPSE , RECTANGLE )

And the invocation signatures might look like this:

( ELLIPSE , RECTANGLE )
( ELLIPSE , SQUARE    )
( CIRCLE  , RECTANGLE )
( CIRCLE  , SQUARE    )

Of course, the specification signature, though probably not the invocation signatures, would additionally need to indicate that MOVE invocations update the argument corresponding to their first parameter, but we omit any such indication here for simplicity (see UPDATES in Part I of this dictionary). More to the point, note that even if circles have “O-circles” as a proper subtype, then—as explained under argument—that first argument can’t be of type O_CIRCLE, because the center of an O-circle is always the origin and can’t be changed. Thus, there are now no invocation signatures (not even purely conceptual ones) showing the type of the first parameter as O_CIRCLE. As far as the first parameter is concerned, in other words (the parameter that’s subject to update), the update form of MOVE is defined for type ELLIPSE, is inherited by type CIRCLE, but isn’t inherited by type O_CIRCLE. (As noted under Principle of Update Operator Inheritance, if O_CIRCLE had any nonempty proper subtypes, it wouldn’t inherited by those either, a fortiori.) Some syntactic construct for expressing such a state of affairs is thus necessary—perhaps as illustrated here:

OPERATOR MOVE ( E ELLIPSE , R RECTANGLE ) UPDATES { E }
                                          NOT ( IS_O_CIRCLE ( E ) ) ;
   THE_CTR ( E ) := CTR ( R ) ;
END OPERATOR ;

So let Op be an update operator, with parameters P1, P2, ..., Pn (and no others), and let parameter Pi have declared type PDTi (i = 1, 2, ..., n). If Pi isn’t subject to update, then Op behaves as if it were a read-only operator as far as Pi is concerned, and the previous discussion of the read-only case applies directly, mutatis mutandis. But if Pi is subject to update, then the argument Ai corresponding to Pi in an invocation of Op must be a variable specifically, and it might or might not be allowed to have some given subtype of PDTi as its most specific type (and a fortiori as its declared type, too). Thus, Op has a specification signature, denoting that operator as perceived by the user, and a set of invocation signatures. The specification signature consists of the operator name, the parameter declared types PDT1, PDT2, ..., PDTn, and an indication as to which parameters are subject to update. Each invocation signature consists of one possible combination of argument expression declared types ADT1, ADT2, ..., ADTn.

Note finally that no two distinct operators can have specification signatures with the same operator name and the same sequence of parameter declared types PDT. Moreover, let S be a set of types with a nonempty common subtype. Then no two distinct operators can have specification signatures that differ only in that, for some i, j, ..., k, the declared types of their ith parameters are distinct members of S, the declared types of their jth parameters are distinct members of S, ..., and the declared types of their kth parameters are distinct members of S.

single inheritance A form of inheritance in which each proper subtype has exactly one immediate supertype. Contrast multiple inheritance.

Examples: See Fig. 2.

specialization Let types T′′, T′, and T be such that T′′ is a subtype of T′ and T′ is a subtype of T, and let v′′ be a value of most specific type T′′. Also, let V be a variable of declared type T, and let the current most specific type MST(V) of V be T′. Finally, let the value v′′ be assigned to V. Then the current most specific type of V is now T′′; in other words, MST(V) has been specialized—sometimes further specialized, for emphasis—from T′ to T′′. (Of course, T′ and T′′ might in fact be one and the same, and so might T and T′, but in general they won’t be.) Contrast generalization; specialization by constraint.

Example: With reference to Fig. 2, let variables E and C be of declared types ELLIPSE and CIRCLE, respectively. Moreover, let their current most specific types be ELLIPSE and CIRCLE, respectively, as well. Now consider this assignment:

E := C ;

This assignment has the effect of changing (“specializing”) the most specific type of E—or, loosely, just specializing E—“down” from ELLIPSE to CIRCLE; in other words, MST(E) is now CIRCLE. More precisely, after the assignment, MST(E) is the same as MST(C), which in principle might be some nonempty proper subtype of CIRCLE—though not in the case at hand, because type CIRCLE doesn’t have any proper subtypes apart from type omega, q.v. But if (as in the examples under argument) type CIRCLE has a proper subtype O_CIRCLE (where an “O-circle” is a circle with center the origin), and C currently contains an O-circle, then after the foregoing assignment MST(E) will be O_CIRCLE.

Note: The foregoing definition and example explain how the Manifesto model works, and probably how most other systems work too. (Indeed, if they don’t, then the result will be a circular noncircle, q.v.) For further details, see the discussion under specialization by constraint.

specialization by constraint Let S be a selector of declared type T, and let exp be an expression denoting an invocation of S (so DT(exp) = T). Let v be the value returned by exp (so v(exp) = v). Further, let v satisfy the type constraint for subtype T′ of T (and not for any proper subtype of T′). Then the most specific types MST(v) and MST(exp) of v and exp, respectively, are both T′. (Of course, T and T′ might in fact be one and the same, but in general they won’t be.) Contrast generalization by constraint; specialization; see also specialization constraint; specialization via constraints.

Examples: Assume for simplicity that the only types we have to deal with are ELLIPSE and CIRCLE (see Fig. 2). Here once again are the type definitions for those types:

TYPE ELLIPSE
     IS { PLANE_FIGURE
          POSSREP { A LENGTH , B LENGTH , CTR POINT
                    CONSTRAINT A ≥ B } } ;

TYPE CIRCLE
     IS { ELLIPSE
          CONSTRAINT THE_A ( ELLIPSE ) = THE_B ( ELLIPSE )
          POSSREP { R   = THE_A  ( ELLIPSE ) ,
                    CTR = THE_CTR ( ELLIPSE ) } } ;

Note in particular the CONSTRAINT specification for type CIRCLE, which says among other things (and speaking a trifle loosely) that the semiaxis lengths a and b are supposed to be equal for a circle. But what does it say precisely? Let e be a value of type ELLIPSE, and let a and b be the corresponding semiaxis lengths. Then there are four possibilities:

1. If a = b, then e is of type CIRCLE.

2. If e is of type CIRCLE, then a = b.

3. Neither 1 nor 2.

4. Both 1 and 2.

Clearly, possibility 1 permits—or at least fails to prohibit—“noncircular circles” (i.e., values e of type CIRCLE that don’t have a = b). Likewise, possibility 2 permits “circular noncircles” (i.e., values e of type ELLIPSE and not type CIRCLE that do have a = b), and possibility 3 permits both “noncircular circles” and “circular noncircles,” in which case there doesn’t seem to be any point in specifying the constraint at all. (Note, however, that this latter case is exactly the one “supported” by SQL!—see the further remarks on this point near the end of the present entry.) Thus, possibility 4 appears to be the only sensible option; certainly it’s the only one that corresponds to mathematical reality, which is why it’s the one adopted in the Manifesto model. And it follows immediately that the system must support specialization by constraint. By way of example, consider the following selector invocation:

ELLIPSE ( LENGTH ( 5.0 ) , LENGTH ( 5.0 ) , POINT ( ... ) )

The value denoted by this expression is an ellipse with a = b and is thus a circle, and is therefore—at least in the Manifesto model—of type CIRCLE. Thus, specialization by constraint (S by C for short) implies, as the original definition states, that certain selector invocations will produce results whose most specific type is some proper subtype of the specified target type. Of course, ultimately, the only way any expression can yield a result value of any type is via some selector invocation. It follows that S by C must be implemented as part of the implementation of the pertinent selector (conceptually, at any rate, though various optimizations are possible in practice, as explained in the Manifesto book).

By way of another example, let the current value of variable E be an ellipse with a = 4 and b = 3, and consider the following assignment:

THE_A ( E ) := LENGTH ( 3.0 ) ;

The expanded form of this assignment is:

E := ELLIPSE ( LENGTH ( 3.0 ) , THE_B ( E ) , THE_CTR ( E ) ) ;

Since THE_B(E) = 3.0, the selector invocation on the right side here returns a circle, not “just an ellipse,” and that circle is then assigned to the variable E. Loosely, we can say that the type—meaning, more precisely, the most specific type MST(E)—of variable E has been changed “down,” or specialized, from ELLIPSE to CIRCLE.

Now suppose the foregoing assignment is followed by this one:

THE_B ( E ) := LENGTH ( 2.5 ) ;

Expanded form:

E := ELLIPSE ( THE_A ( E ) , LENGTH ( 2.5 ) , THE_CTR ( E ) ) ;

Since THE_A(E) = 3.0, the selector invocation on the right side here returns “just an ellipse” (i.e., an ellipse that’s not a circle), and that ellipse is then assigned to the variable E. In other words, generalization by constraint (G by C) has occurred, and the most specific type MST(E) of variable E is now ELLIPSE again. Loosely, we can say that the type—meaning, more precisely, the most specific type MST(E)—of variable E has been changed “up,” or generalized, from CIRCLE to ELLIPSE.

So S by C and G by C together support changing types both up and down—and hence “sideways,” too. Suppose type ELLIPSE has another immediate subtype NONCIRCLE, with the obvious semantics (i.e., ELLIPSE is now a union type, q.v., and every ellipse is either a circle or a noncircle and not both). Let the current value of variable E be an ellipse with a = 4 and b = 3, and hence in fact a noncircle. Then the following assignment—

THE_A ( E ) := LENGTH ( 3.0 ) ;

—will assign a circle (of radius length 3) to E, and will thus effectively also change the type—meaning, more precisely, the most specific type MST(E)—of variable E “sideways,” from NONCIRCLE to CIRCLE.

What about S by C for tuple and relation types? Well, if S by C is performed as described above for scalar types, it’ll happen automatically for tuple and relation types too, and nothing more needs to be said about the matter. What’s more, the same goes for G by C too, mutatis mutandis.

Note: Most languages and systems (including SQL systems in particular) that support inheritance at all don’t actually support either S by C or G by C. Thus, SQL in particular does permit “noncircular circles” and “circular noncircles” (in fact, as noted under Principle of Update Operator Inheritance, as well as under type constraint in Part I of this dictionary, SQL doesn’t support much in the way of type constraints at all). It’s also worth mentioning that changing types up, down, or sideways is a much more complex business—it might even be impossible—in systems that fail to support S by C and G by C. Finally, many further advantages also accrue if and only if S by C and G by C are supported; however, further details are beyond the scope of this dictionary (they can be found in the Manifesto book).

specialization constraint Let T be a regular type (and hence, necessarily, a scalar type), and let T′ be a nonempty immediate subtype of T. Then the type constraint for type T′ will specify that, in order for some given value to be of type T′, that value must be of type T and must additionally satisfy some further constraint. That type constraint is the specialization constraint for type T′. For further discussion and examples, see IS. Note: As indicated under proper subtype, in practice there’ll always be at least one value of type T that’s not of type T′. See example value, second definition.

specialization via constraints A term found in the OO literature, possibly related to—but not to be confused with—specialization by constraint, q.v. The following definition is taken from Stanley B. Zdonik and David Maier, “Fundamentals of Object-Oriented Databases,” in Readings in Object-Oriented Database Systems (Zdonik and Maier, eds.; Morgan Kaufmann, 1990):

Specialization via constraints happens whenever the following is permitted:

B subtype_of A and T subtype_of S and
f(...b:T,...) returns r:R in Ops(B) and
f(...b:S,...) returns r:R in Ops(A)

That is, specialization via constraints occurs whenever the operation redefinition on a subtype constrains one of the arguments to be from a smaller value set than the corresponding operation on the supertype.

Note, however, that “operator redefinition on a subtype” apparently means (to use terminology defined elsewhere in this part of the dictionary) definition of a new implementation version, q.v. “Specialization via constraints” thus appears to mean nothing more than—to take a concrete example—that if Op is an operator that’s defined to work on ellipses, and a version of Op is defined to work on ellipses that happen to be circles, then the argument to that version of Op must be a circle specifically and not just an ellipse. It’s not really clear, therefore, that “specialization via constraints” has anything to do with the inheritance model, as such, at all (but see three out of four “rule”).

specification signature (With inheritance) See signature.

static binding Term sometimes used as a synonym for compile time binding, q.v.

static classification Systems and languages (especially OO systems and languages) that use the term class to mean a type—see Part I of this dictionary—sometimes use the term static classification to refer to the process, or the result of the process, of determining at compile time the type(s) possessed by some object.

static dispatching / static despatching Term sometimes used (especially OO systems and languages) as a synonym for compile time binding, q.v.

static type checking Term sometimes used as a synonym for compile time type checking, q.v.

structural inheritance A form of inheritance, supported in some OO systems, according to which if type T′ is a subtype of type T, then T′ inherits all of T’s public instance variables. (It probably inherits T’s private instance variables as well, but this latter is an implementation matter, not part of the model.) Note: The Manifesto model doesn’t support structural inheritance at all (except, arguably, as discussed under inherited possrep). See also extends relationship; contrast behavioral inheritance.

subclass Systems and languages that use the term class—see Part I of this dictionary—typically use the term subclass also, with a similar variety of interpretations.

subject routine determination SQL term for binding.

substitutability Value substitutability (q.v.) or variable substitutability (q.v.) or both, as the context demands. See Principle of Read-Only Operator Inheritance; Principle of Update Operator Inheritance. Note: In many ways, substitutability is the whole point of inheritance. One reason for wanting to support inheritance in the first place is that (for example) a program that works for ellipses might work for circles too, even if it was originally written with no thought for circles at all (see code reuse). And to the degree that such an objective might be attainable, it should be clear that it’s substitutability that makes it so. See also coercion vs. substitutability.

substitutability vs. coercion See coercion vs. substitutability.

subtable See subtables and supertables.

subtables and supertables A scheme—in fact, a specific concrete realization of the “extends relationship” concept, q.v.—according to which some table T′ is defined to have all of the columns of some other table T, together with certain additional columns of its own. Note: We deliberately frame this definition in SQL terms—viz., tables, columns, and rows—instead of relational terms because SQL does at least support the “subtables and supertables” concept and the relational model doesn’t (at least, not explicitly; see the discussion below, however, showing how relational views could be used to achieve comparable functionality).

Example: Consider the following SQL tables (for definiteness, assume them to be base tables specifically):

EMP   /* supertable */
┌─────┬───────┬─────┬────────┐
│ ENO │ ENAME │ DNO │ SALARY │
└═════┴───────┴─────┴────────┘

 PGMR   /* subtable */
┌─────┬───────┬─────┬────────┬──────┐
│ ENO │ ENAME │ DNO │ SALARY │ LANG │
└═════┴───────┴─────┴────────┴──────┘
└──── inherited from EMP ────┘

Observe that table EMP (“employees”) has four columns; by contrast, table PGMR (“programmers”) has just one column of its own, but is conceptually extended with four more columns, shown in the diagram above in italics, that it “inherits” from table EMP. (Note, therefore, that the subtable—a little counterintuitively, perhaps—has a superset of the columns of the supertable.) Column names are meant to be self-explanatory. Nonprogrammers have a row in EMP only, while programmers have a row in both tables (so every row in PGMR has a counterpart in EMP, but the converse is false). Here are some of the implications of this state of affairs for the usual SQL retrieval and update operations:

• SELECT: Retrieval from EMP behaves normally. Retrieval from PGMR behaves as if PGMR does actually contain columns ENO, ENAME, DNO, and SALARY (as well as column LANG, of course).

• INSERT: INSERT into EMP behaves normally. INSERT into PGMR effectively causes new rows to appear in both EMP and PGMR.

• DELETE: DELETE from EMP causes rows to disappear from EMP and (if the rows in question happen to correspond to programmers) from PGMR too. DELETE from PGMR causes rows to disappear from both EMP and PGMR.

• UPDATE: Updating columns ENO or ENAME or DNO or SALARY in EMP causes the same updates to be applied to any corresponding rows in PGMR. Updating those columns in PGMR causes the same updates to be applied to the corresponding rows in EMP. Updating column LANG in PGMR updates PGMR only.

Actually there are at least two further operations of an updating nature that a system supporting subtables and supertables would seem to need—viz., DELETE ONLY, q.v., and INSERT ONLY, q.v.—but no such operators are supported by SQL. What makes this omission a trifle odd is that such operators would be supported, in effect, if the tables were treated just as regular SQL tables instead of being bound together as a subtable / supertable pair. What makes it even odder is that the functionality, such as it is, of subtables and supertables, including the DELETE ONLY and INSERT ONLY functionality, could be achieved in its entirety by means of the conventional view mechanism! To be specific, suppose we define base tables EMP and EMP_LANG as follows (in outline):

EMP      ( ENO , ENAME , DNO , SALARY )

EMP_LANG ( ENO , LANG )

Suppose we also define PGMR as a view of these two base tables, with the following SQL expression as the necessary view defining expression:

EMP NATURAL JOIN EMP_LANG

Then tables EMP, EMP_LANG, and PGMR together not only provide all of the functionality of subtables and supertables, they also get around the lack of support for INSERT ONLY and DELETE ONLY (trivially so, in fact—those operators are simply no longer needed, being replaced by suitable INSERTs and DELETEs on table EMP_LANG).

Note carefully that the “subtables and supertables” scheme has nothing whatsoever to do with relation subtypes and supertypes, q.v. To be specific, let relation headings EH and PH correspond to tables EMP and PGMR in the obvious way; note in particular that EH has four attributes and PH either five or one, depending on your point of view. Whichever it is, type RELATION PH is clearly not a subtype of type RELATION EH in the sense of the Manifesto model, precisely because those two types have different headings. In particular, therefore, a value (a relation) of type RELATION PH isn’t a value of type RELATION EH. Perhaps more to the point, a value (a tuple) of type TUPLE PH isn’t a value of type TUPLE EH, either.

A more extensive description of the foregoing scheme and what’s wrong with it (and why it’s logically unnecessary anyway) can be found in the Manifesto book. Here we note just one further point, which is that, in general, which of tables T and T′ is regarded as the subtable and which the supertable might depend on context. For example, consider an SQL version of the suppliers-and-parts database used as a running example throughout Part I of this dictionary. Suppose for the sake of the example that status information can be “missing” for certain suppliers. Then a good way to design the database, in SQL terms, would be to have two tables S and S′ that look like this:

 S
┌─────┬───────┬────────┬──────┐
│ SNO │ SNAME │ STATUS │ CITY │
└═════┴───────┴────────┴──────┘

 S′
┌─────┬───────┬──────┐
│ SNO │ SNAME │ CITY │
└═════┴───────┴──────┘

Table S corresponds to suppliers with a known status value, while table S′ corresponds to suppliers for whom the status information is missing. And the point about this example—which illustrates, incidentally, a perfectly reasonable basis for dealing with the phenomenon of “missing information”—is that it would be quite natural to refer to S here as the supertable and S′ as the subtable; but now the supertable has a superset of the columns of the subtable, instead of the other way around as in the “employees and programmers” example.

subtype Type T′ is a subtype of type T if and only if every value of type T′ is a value of type T. Note that T and T′ must be from the same type lattice, necessarily. Note: It follows from this definition that (a) every type is a subtype of itself (i.e., the “subtype of” relationship is reflexive), and (b) every subtype of T′ is a subtype of T (i.e., the “subtype of” relationship is transitive). Note too that, by definition, read-only operators and type constraints (“properties”) that apply to values of type T also apply to values of type T′. Note finally that there can’t possibly be more values of type T′ than there are of type T; this apparently trivial observation can be very helpful in pinpointing errors and clearing up confusions. (Indeed, it’s worth stating explicitly, albeit rather loosely, that T′ has a subset of type T’s values but a superset of type T’s properties.) See also supertype; contrast extends relationship.

Examples (scalar types only): See Figs. 2-4.

subtype (relation types) Let T and T′ be relation types from the same type lattice, q.v.; by definition, then, those types have the same attribute names, say A1, A2, ..., An (n ≥ 0). Then type T′ is a subtype of type T if and only if, for all i (i = 1, 2, ..., n), the type Ti′ of attribute Ai within T′ is a subtype of the type Ti of attribute Ai within T. Further, relation r is of some subtype of type T if and only if the heading of r is that of some subtype of T (in which case every tuple t in the body of r necessarily has a heading that’s the heading of some subtype of the type of r). See also supertype (relation types).

Examples: See Fig. 5.

subtype (tuple types) Let T and T′ be tuple types from the same type lattice, q.v.; by definition, then, those types have the same attribute names, say A1, A2, ..., An (n ≥ 0). Then type T′ is a subtype of type T if and only if, for all i (i = 1, 2, ..., n), the type Ti′ of attribute Ai within T′ is a subtype of the type Ti of attribute Ai within T. Further, tuple t is of some subtype of type T if and only if the heading of t is the heading of some subtype of T. See also supertype (tuple types).

Examples: See Fig. 5.

subtyping Term sometimes used as a synonym for inheritance.

superclass Systems and languages that use the term class—see Part I of this dictionary—typically use the term superclass also, with a similar variety of interpretations.

supertable See subtables and supertables.

supertype Type T is a supertype of type T′ if and only if every value of type T′ is a value of type T. Note that T and T′ must be from the same type lattice, necessarily. Note: It follows from this definition that (a) every type is a supertype of itself (i.e., the “supertype of” relationship is reflexive), and (b) every supertype of T is a supertype of T′ (i.e., the “supertype of” relationship is transitive). Note too that, by definition, read-only operators and type constraints (“properties”) that apply to values of type T also apply to values of type T′. (Indeed, it’s worth stating explicitly, albeit rather loosely, that T has a superset of type T′’s values but a subset of type T′’s properties.) See also subtype.

Examples (scalar types only): See Figs. 2-4.

supertype (relation types) Let T and T′ be relation types from the same type lattice, q.v.; by definition, then, those types have the same attribute names, say A1, A2, ..., An (n ≥ 0). Then type T is a supertype of type T′ if and only if, for all i (i = 1, 2, ..., n), the type Ti of attribute Ai within T is a supertype of the type Ti′ of attribute Ai within T′. Further, relation r is of some supertype of type T′ if and only if the heading of r is that of some supertype of T′ (in which case every tuple in the body of r necessarily has a heading that’s both (a) the heading of some supertype of T′ and (b) the heading of some subtype of the type of r). See also subtype (relation types). Examples: See Fig. 5.

supertype (tuple types) Let T and T′ be tuple types from the same type lattice, q.v.; by definition, then, those types have the same attribute names, say A1, A2, ..., An (n ≥ 0). Then type T is a supertype of type T′ if and only if, for all i (i = 1, 2, ..., n), the type Ti of attribute Ai within T is a supertype of the type Ti′ of attribute Ai within T′. Further, tuple t is of some supertype of type T′ if and only if the heading of t is the heading of some supertype of T′. See also subtype (tuple types).

Examples: See Fig. 5.

T_alpha Generic name for the maximal type in the type lattice, q.v., to which some specified type T belongs. Note: If T is scalar, the “T_” prefix can be dropped, since all scalar types belong to the same type lattice and there’s exactly one maximal scalar type, viz., alpha, q.v.

T_omega Generic name for the minimal type in the type lattice, q.v., to which some specified type T belongs. Note: If T is scalar, the “T_” prefix can be dropped, since all scalar types belong to the same type lattice and there’s exactly one minimal scalar type, viz., omega, q.v.

target parameter See selfish method.

target type (With inheritance) 1. Let S be a selector for type T; then the target type for an invocation of S is T. 2. In the TREAT invocation TREAT_AS_T (...), the target type is T. 3. In the CAST invocation CAST_AS_T (...), the target type is T. Note: In all three of these cases, S by C (q.v.) implies that the most specific type of the result might be some nonempty proper subtype of the target type. However, the declared type of the result is the same as the target type in all cases.

three out of four “rule” In “Fundamentals of Object-Oriented Databases,” by Stanley B. Zdonik and David Maier (in Readings in Object-Oriented Database Systems, Zdonik and Maier, eds., Morgan Kaufmann, 1990), the claim is made that at most three of the following four allegedly desirable features can be supported simultaneously: (a) substitutability, (b) compile time type checking, (c) mutability, and (d) “specialization via constraints” (q.v.). By way of illustration, consider the following code fragment (the example that follows is an edited version of one from Zdonik and Maier’s own paper, revised to use Tutorial D syntax and types ELLIPSE and CIRCLE from Fig. 2):

VAR E ELLIPSE ;

E := CIRCLE ( LENGTH ( 2.0 ) , POINT ( ... ) ) ;
THE_A ( E ) := LENGTH ( 3.0 ) ;

The first line here defines E to be a variable of declared type ELLIPSE. The next line attempts to assign a circle to E; compile time type checking succeeds—feature (b)—and the assignment succeeds at run time because of feature (a), substitutability (value substitutability, to be precise). The last line is an illustration of mutability—feature (c)—and it attempts to change the length of the a semiaxis of the ellipse (actually a circle) in E; compile time type checking succeeds, but does the assignment succeed at run time? Zdonik and Maier claim, in effect, that it will fail if the system is aware that circles must have a = b; they therefore claim that, in order for the assignment to succeed, the system mustn’t be told that circles do have a = b. In other words, they appear to be suggesting that it’s better that such a constraint not be declared! (Apparently, they also regard declaring such a constraint as an example of “specialization via constraints”—feature (d)—though it’s hard to see how that perception is consistent with their own definition of this latter concept, q.v. In fact, the constraint in question—the constraint, that is, that a circle is an ellipse with a = b—is basically just the pertinent specialization constraint, q.v.) Of course, if that constraint isn’t declared, the assignment will indeed “succeed,” but the effect will be that variable E now contains a “noncircular circle,” q.v.

Note: In the Manifesto model, the assignment succeeds even though the constraint is declared (necessarily declared, in fact, as part of the definition of type CIRCLE). The point is, of course, that in that model G by C comes into play and the most specific type of the variable E after the assignment is ELLIPSE, not CIRCLE. In other words, the three out of four “rule” isn’t a rule at all, in the Manifesto model (that’s why the word “rule” is set in quotation marks here). Moreover, note also that:

• Feature (a), value substitutability, is logically implied by inheritance and is thus a sine qua non.

• Feature (b), compile time type checking, is highly desirable but can’t be achieved 100 percent (see TREAT).

• Feature (c), mutability, is a sine qua non unless nothing is ever updated.

• Constraints of the kind under discussion—feature (d), apparently—are also a sine qua non if noncircular circles and the like are to be avoided.

See four out of five rule for further discussion.

One last point: It does seem to be the case in practice that most languages that provide inheritance support (including SQL in particular) do fail to support specialization constraints, q.v. The following quote from a paper by James Rumbaugh (“A Matter of Intent: How to Define Subclasses,” Journal of Object-Oriented Programming, September 1996), tends to support this contention:

Is SQUARE a subclass of RECTANGLE? ... Stretching the x dimension of a rectangle is a perfectly reasonable thing to do. But if you do it to a square, then the object is no longer a square. This is not necessarily a bad thing conceptually. When you stretch a square you do get a rectangle ... But ... most object-oriented languages do not want objects to change class ... [This] suggests [a] design principle for classification systems: A subclass should not be defined by constraining a superclass.

And Rumbaugh buttresses his conclusion with the following claim:

It would be computationally infeasible to support a rule-based, intensional definition of class membership, because you would have to check the rules after each operation that affects an object.

(The phrase “rule-based, intensional definition of class membership” refers to S by C and G by C; it means, for example, that a given ellipse is a member of the class of circles if and only if it satisfies the rule that a = b.) But we reject this claim; we believe the computational aspects of S by C and G by C can be handled both simply and efficiently. See the Manifesto book for further discussion.

TREAT Let exp be a scalar expression, let T be a nonempty scalar type, and let DT(exp) and T overlap (this is a compile time check). Then the expression TREAT_AS_T (exp)—or some logical equivalent to that expression—raises a run time type error, if MST(exp) isn’t some subtype of T; otherwise, it returns a result x with DT(x) = T, v(x) = v(exp), and MST(x) = MST(exp). Note: Tutorial D additionally supports a generalized version of this operator of the form TREAT_AS_SAME_TYPE_AS (exp1,exp2), in which the expressions exp1 and exp2 aren’t limited to being scalar. This generalized version is effectively equivalent to the expression TREAT_AS_T1 (exp2), where T1 is DT(exp1)—assuming for definitional purposes that the expression TREAT_AS_T1 (exp2) is syntactically valid.

Examples: First of all, here with reference to Fig. 2 are a couple of examples that illustrate the raison d’être for the TREAT operator. Let variables E and C be of declared types ELLIPSE and CIRCLE, respectively. Then the assignment

C := E ;

will fail on a compile time type error, even if we know that E will contain a circle at run time. Similarly, the expression THE_R (E) (“the radius of E”) will also fail at compile time, even if we know, again, that E will contain a circle at run time. By contrast, consider this assignment:

C := TREAT_AS_CIRCLE ( E ) ;

This assignment won’t fail at compile time, because the declared type of the expression TREAT_AS_CIRCLE (E) is CIRCLE; and if E does contain a circle at run time, the assignment will cause that circle to be assigned to C. (However, the TREAT invocation will raise a run time type error if E contains “just an ellipse” at run time.) Similarly, the expression THE_R (TREAT_AS_CIRCLE (E)) won’t fail at compile time and—again, if E does contain a circle at run time—will return the length of the radius of that circle (but it’ll raise a run time type error otherwise). In the Manifesto model, in fact, an attempt to TREAT a value to a type it doesn’t possess is the only possible way a run time type error can ever occur.

Here are some more examples:

• With reference to Fig. 3, let V be a variable of declared type RECTANGLE and current most specific type SQUARE; then the TREAT invocations TREAT_AS_SQUARE (V), TREAT_AS_RECTANGLE (V), TREAT_AS_RHOMBUS (V), and TREAT_AS_PARALLELOGRAM (V) all succeed at both compile time and run time.

• With reference to Fig. 5, let ERV be a variable of declared type ER and current most specific type CS, and let ESV be a variable of declared type and most specific type both ES; then TREAT_AS_SAME_TYPE_AS (ERV,ESV) succeeds at both compile time and run time.

Note: The Manifesto model currently allows TREAT operator invocations to be used as pseudovariable references, but such “TREAT pseudovariables” don’t actually seem to serve much purpose. For example, let variable E be of declared type ELLIPSE but current most specific type CIRCLE. Then the following assignment—

THE_R ( E ) := LENGTH ( 5.0 ) ;

—will fail at compile time. By contrast, the following assignment will succeed at both compile time and run time:

THE_R ( TREAT_AS_CIRCLE ( E ) ) := LENGTH ( 5.0 ) ;

However, this latter assignment is logically equivalent to this one:

E := CIRCLE ( LENGTH ( 5.0 ) , THE_CTR ( E ) ) ;

Thus, it’s not clear that the TREAT pseudovariable has actually bought us anything in this example.

TREAT_AS_SAME_TYPE_AS See TREAT.

TREAT expression See TREAT.

TREAT pseudovariable See TREAT.

tuple assignment (With inheritance) Let T and t be a tuplevar and a tuple, respectively, such that the most specific type MST(t) of t is some subtype of the declared type DT(T) of T. Then (and only then) t can be assigned to T; the assignment has the effect of setting v(T) equal to t and MST(T) equal to MST(t). Note: In order for the assignment to be syntactically valid, the declared type DT(tx) of the expression tx used to denote tuple t must be some subtype of the declared type DT(T) of tuplevar T (this condition is implied by the fact that MST(t) is required to be some subtype of DT(T), and is a compile time check).

Examples: Let tuplevars TE and TC be of declared types TUPLE {E ELLIPSE} and TUPLE {E CIRCLE}, respectively, and consider the following assignment:

TE := TC ;

In this example, compile time type checking succeeds (DT(TC) is a subtype of DT(TE)), and at run time v(TE) and MST(TE) are set equal to v(TC) and MST(TC), respectively.

Now consider this assignment:

TC := TE ;

This example raises a compile time type error, because DT(TE) isn’t a subtype of DT(TC). By contrast, if the expression TE in this example were to be replaced by the expression TREAT_AS_SAME_TYPE_AS (TC,TE), then compile time type checking would succeed; however, this latter expression will raise a type error (a run time type error, of course) if MST(TE) isn’t some subtype of TUPLE {E CIRCLE} at run time (see TREAT).

tuple comparison (With inheritance) A boolean expression of the form (tx1) theta (tx2), where (a) tx1 and tx2 are tuple expressions whose most specific types MST(tx1) and MST(tx2) overlap and (b) theta is either “=” or “≠”. Note: In order for the comparison to be syntactically valid, the declared types DT(tx1) and DT(tx2) must overlap (this condition is implied by the fact that MST(tx1) and MST(tx2) are required to overlap, and is a compile time check). Also, the parentheses enclosing tx1 and tx2 in the comparison might not be needed in practice.

tuple equality (With inheritance) Let t1 and t2 be relations such that the most specific types MST(t1) and MST(t2) overlap. Then t1 and t2 can be compared for equality; the comparison returns TRUE if and only if t1 is equal to t2 (in which case MST(t1) is equal to MST(t2) also). Note: In order for the comparison to be syntactically valid, the declared types DT(tx1) and DT(tx2) of the expressions tx1 and tx2 used to denote t1 and t2, respectively, must overlap (this condition is implied by the fact that MST(t1) and MST(t2) are required to overlap, and is a compile time check).

tuple subtype See subtype (tuple types).

tuple supertype See supertype (tuple types).

tuple type inheritance A form of inheritance in which the types are tuple types specifically. Note that tuple type inheritance is necessarily multiple. See subtype (tuple types); supertype (tuple types).

Example: See Fig. 5.

type checking (With inheritance) See compile time type checking; run time type checking.

type constraint inheritance See type inheritance.

type error (With inheritance) The error that occurs if type checking fails (see compile time type checking; run time type checking). In the Manifesto model, such errors are detectable at compile time (except, sometimes, in the context of TREAT, q.v.).

type graph A pictorial way of representing supertype / subtype relationships, applicable even when there’s multiple inheritance involved (contrast type hierarchy). A type graph is a directed acyclic graph; more precisely, it’s a graph TG consisting of a finite set N of nodes and a finite set D of directed arcs that together satisfy the following properties:

• TG is empty if and only if N is empty (in which case D is necessarily empty too).

• Each node is given the name of a type.

• No two nodes have the same name. Also, no node is named either T_alpha (q.v.) or T_omega (q.v.) for any possible type T; by convention, the types with these names—which are primarily conceptual in nature anyway—aren’t represented in the graph at all.

• There’s a directed arc from node T to node T′ if and only if type T is an immediate supertype of type T′.

• If there’s a directed arc from node T to node T′, then node T′ isn’t reachable from node T via any other path, where (a) a path from node T to node T′ is a sequence of n directed arcs A1 (from T to T1, say), A2 (from T1 to T2, say), ..., An (from T(n-1), say, to T′), where n ≥ 0, and n = 0 implies T = T′ (i.e., there’s always a path from node T to itself); (b) a node T′ is reachable from a node T if and only if there’s a path from node T to node T′.

• If the graph includes any nodes at all, then—because it’s directed and acyclic—it necessarily contains at least one node that has no immediate supertype node. Such a node is called a root node (and the corresponding type is called a root type).

• If the graph includes any nodes at all, then—again because it’s directed and acyclic—it necessarily contains at least one node that has no immediate subtype node. Such a node is called a leaf node (and the corresponding type is called a leaf type).

• If nodes T1 and T2 are distinct root nodes, then no node is reachable from both T1 and T2.

• If nodes T1, T2, T′, and T′′ are such that there exist paths from both T1 and T2 to both T′ and T′′, then there must exist a node T that’s common to every such path.

It follows from the foregoing definition that any given type graph TG can be divided into a set of disjoint partitions—a nonempty set, unless TG itself is empty—such that (a) each partition in the set has exactly one root node and one or more leaf nodes, and (b) no type in any partition in the set overlaps any type in any other partition in the set. If such a partition has just one leaf node, then that partition forms a lattice; if it has more than one leaf node, it can be converted into a lattice by introducing the pertinent minimal type. Note, however, that the lattices in question aren’t type lattices as such, q.v. (at least, not as this latter term is usually understood), because they don’t contain the pertinent maximal type.

Note: Type graphs aren’t part of the inheritance model as such—they’re merely an intuitively convenient way of depicting supertype / subtype relationships, which are. (Type graphs play a role in the inheritance model analogous to that played by tables in the relational model: Tables aren’t part of the relational model as such, they’re merely an intuitively convenient way of depicting relations, which are.)

Examples: See Figs. 2-5. (Fig. 2 shows a type hierarchy, of course, which is a degenerate case; Figs. 3-5 show type graphs that aren’t type hierarchies.)

type hierarchy A pictorial way of representing supertype / subtype relationships, applicable so long as there’s no multiple inheritance involved (and hence applicable only to scalar types, and then only because type omega is ignored—see below). A type hierarchy is a directed acyclic graph; more precisely, it’s a graph TH consisting of a finite set N of nodes and a finite set D of directed arcs that together satisfy the following properties:

• TH is empty if and only if N is empty (in which case D is necessarily empty too).

• Each node is given the name of a type.

• No two nodes have the same name. Also, no node is named either alpha or omega; by convention, the types with these names (which are primarily conceptual in nature anyway) aren’t represented in the graph at all.

• Each arc connects exactly two distinct nodes and represents a directed path from one of those two nodes (the parent) to the other (the child). There’s an arc from parent T to child T′ if and only if type T is an immediate supertype of type T′.

• Each parent is connected to one or more children. Each child is connected to exactly one parent.

• Node Y is a descendant of node X if and only if it’s a child of X or a child of a descendant of X. No node is a descendant of itself.

• Node X is an ancestor of node Y if and only if node Y is a descendant of node X. No node is an ancestor of itself.

• A node connected to no parent is a root node (and the corresponding type is called a root type). Note: If TH is nonempty, it has exactly one root node, otherwise it has no root node at all.

• A node connected to no children is a leaf node (and the corresponding type is called a leaf type).

Contrast type graph; see also derived type hierarchy.

Note: Type hierarchies aren’t part of the inheritance model as such—they’re merely an intuitively convenient way of depicting supertype / subtype relationships, which are. (Type hierarchies play a role in the inheritance model analogous to that played by tables in the relational model: Tables aren’t part of the relational model as such, they’re merely an intuitively convenient way of depicting relations, which are.) Note further that type hierarchies are known in the literature by a variety of different names, the following among them:

• Class hierarchies (on the grounds that types are sometimes called classes, especially in an OO context)

• Generalization hierarchies (on the grounds that, e.g., an ellipse is a generalization of a circle)

• Specialization hierarchies (on the grounds that, e.g., a circle is a specialization of an ellipse)

• Inheritance hierarchies (on the grounds that, e.g., circles inherit properties from ellipses)

• “IS A” hierarchies (on the grounds that, e.g., every circle “is a” ellipse)

and so on (this isn’t an exhaustive list).

Example: See Fig. 2.

type inheritance (Expanded definition) An organizing principle according to which one type can be defined as a subtype of one or more other types, called supertypes (of the type in question). If T′ is a subtype of supertype T, then all values of type T′ are also values of type T, and read-only operators and type constraints that apply to values of type T therefore also apply to—i.e., are “inherited by”—values of type T′ (see Principle of Read-Only Operator Inheritance). However, values of type T′ will have read-only operators and type constraints of their own that don’t apply to values that are only of type T and not of type T′. As for variables of declared type T′, they might or might not inherit update operators that apply to variables of type T (see Principle of Update Operator Inheritance). See also possrep inheritance.

Note: The foregoing definition of the term type inheritance is the definition the Manifesto model is based on. However, it has to be said there’s no consensus in the literature on exactly what the term is supposed to mean. For example:

• From “The Object-Oriented Database System Manifesto,” by Malcolm Atkinson, François Bancilhon, David DeWitt, Klaus Dittrich, David Maier, and Stanley Zdonik (Proc. 1st International Conference on Deductive and Object-Oriented Databases, Kyoto, Japan, Elsevier Science, 1990):

  [There] are at least four types of inheritance: substitution inheritance, inclusion inheritance, constraint inheritance, and specialization inheritance ... Various degrees of these four types of inheritance are provided by existing systems and prototypes, and we do not prescribe a specific style of inheritance. (Italics as in the original.)

• From An Introduction to Data Types, by J. Craig Cleaveland (Addison-Wesley, 1986):

  [Inheritance can be] based on [a variety of] different criteria and there is no commonly accepted standard definition.

  The book then goes on to give eight possible interpretations. (Bertrand Meyer, in “The Many Faces of Inheritance: A Taxonomy of Taxonomy,” IEEE Computer 29, No. 5, May 1996, gives twelve.)

• From technical correspondence by Kenneth Baclawski and Bipin Indurkhya in CACM 37, No. 9, September 1994:

  [A language merely] provides a set of [inheritance] mechanisms. While these mechanisms certainly restrict what one can do in that language and what views of inheritance can be implemented [in that language], they do not by themselves validate some view of inheritance or other. [Types,] specializations, generalizations, and inheritance are only concepts, and ... they do not have a universal objective meaning ... This [state of affairs] implies that how inheritance is to be incorporated into a specific system is up to the designers of [that] system, and it constitutes a policy decision that must be implemented with the available mechanisms.

And so on. Caveat lector.

type lattice In general, a lattice, q.v., for which (a) the pertinent set is a set of types and (b) the necessary partial ordering is provided by the “is a subtype of” operator. In particular, the set of available types (q.v.) in any given situation can be considered as constituting a collection of disjoint lattices, as follows:

• The set of all scalar types is a lattice; for any given pair of such types, the least upper bound and the greatest lower bound are, respectively, the most specific common supertype and the least specific common subtype (for that pair in each case). The least upper and greatest lower bounds for the lattice as a whole are the maximal scalar type alpha and the minimal scalar type omega, respectively.

• Let T be a tuple type, with corresponding maximal and minimal types T_alpha and T_omega, respectively. Then the set of all subtypes of T_alpha and supertypes of T_omega is a lattice; for any given pair of such types, the least upper bound and the greatest lower bound are, respectively, the most specific common supertype and the least specific common subtype (for that pair in each case). The least upper and greatest lower bounds for the lattice as a whole are T_alpha and T_omega, respectively. Note that, by definition, all types belonging to the same tuple type lattice have the same attribute names.

• Let T be a relation type, with corresponding maximal and minimal types T_alpha and T_omega, respectively. Then the set of all subtypes of T_alpha and supertypes of T_omega is a lattice; for any given pair of such types, the least upper bound and the greatest lower bound are, respectively, the most specific common supertype and the least specific common subtype (for that pair in each case). The least upper and greatest lower bounds for the lattice as a whole are T_alpha and T_omega, respectively. Note that, by definition, all types belonging to the same relation type lattice have the same attribute names.

The foregoing lattices are pairwise disjoint, in the sense that every type in the set of available types belongs to precisely one of them. Moreover, no type in any of the lattices in question overlaps any type in any other.

Let T be any type. Then the set of all subtypes of T, including both type T itself and type T_omega, can be regarded as a lattice in its own right. Likewise, the set of all supertypes of T, including both type T itself and type T_alpha, can also be regarded as a lattice in its own right. Note: That said, however, the unqualified term type lattice is almost invariably taken—in this dictionary in particular—to refer to one of the lattices described in the three bullet items above, unless the context demands otherwise.

Examples: The types shown in Fig. 4 (even without types alpha and omega), together with “is a subtype of” as the necessary partial ordering, constitute a type lattice. By way of illustration, consider types PARALLELOGRAM and ISOSCELES TRAPEZOID; these two types have their most specific common supertype TRAPEZOID as their least upper bound and their least specific common subtype RECTANGLE as their greatest lower bound. As another example, consider types RECTANGLE and RIGHT KITE; these two types have their most specific common supertype CYCLIC QUADRILATERAL as their least upper bound and their least specific common subtype SQUARE as their greatest lower bound.

type schema (With inheritance) Term sometimes used to refer to a collection of type definitions—especially if the types in question are involved in any subtype / supertype relationships. For example, the collection of type definitions for the set of six types shown in Fig. 2 could be regarded as constituting a type schema.

type testing See IS_T; see also R : IS_T.

typed table An SQL construct, highly intertwined with SQL’s support for subtables and supertables, q.v., and REF types (see Part I of this dictionary), and deprecated for both of those reasons.

Note: The terminology of “typed tables” is quite inappropriate, because (a) all tables, not just “typed” ones, are effectively of some type anyway—though SQL fails to take advantage of, or indeed even recognize, this fact—and (b) if “typed table” TT is defined to be “of type T,” then TT is in fact not of type T, and neither are its rows. (In particular, if the declared type of some parameter to some operator Op is T, no “typed table” TT can be passed as the corresponding argument to an invocation of that operator Op, and neither can any of its rows.) Further details are beyond the scope of this dictionary, but a brief discussion of such matters can be found in the book An Introduction to Database Systems (8th edition), by C. J. Date (Addison-Wesley, 2004).

union (With inheritance) See dyadic relational operators.

union type A scalar type T such that every value v of type T has as its most specific type some proper and necessarily nonunion subtype of type T (i.e., there’s no value v such that MST(v) is T). Dummy types, q.v., are an important special case. Note that—with the obvious exception of the special dummy type omega, q.v.—a union type must have at least two distinct immediate subtypes. Note too that the concept of union vs. nonunion types doesn’t really apply to nonscalar types.

Examples: Consider first the following type schema, q.v. (based on a revised version of Fig. 2):

TYPE ELLIPSE UNION
     IS { PLANE_FIGURE
          POSSREP { A LENGTH , B LENGTH , CTR POINT
          CONSTRAINT A ≥ B } } ;

TYPE CIRCLE
     IS { ELLIPSE
          CONSTRAINT THE_A ( ELLIPSE ) = THE_B ( ELLIPSE )
          POSSREP { R   = THE_A   ( ELLIPSE ) ,
                    CTR = THE_CTR ( ELLIPSE ) } } ;

TYPE NONCIRCLE
     IS { ELLIPSE
          CONSTRAINT THE_A ( ELLIPSE ) > THE_B ( ELLIPSE )
          POSSREP { A   = THE_A   ( ELLIPSE ) ,
                    B   = THE_B   ( ELLIPSE ) ,
                    CTR = THE_CTR ( ELLIPSE ) } } ;

Given these type definitions:

• Type ELLIPSE is a union type and types CIRCLE and NONCIRCLE are nonunion types; what’s more, every ellipse is either a circle or a noncircle (i.e., types CIRCLE and NONCIRCLE are disjoint).

• Type ELLIPSE does have a declared possrep and hence a selector, but invoking that selector will never return a value of most specific type ELLIPSE. It also has THE_ operators, but such operators will never be applied to arguments of most specific type ELLIPSE.

• A variable of declared type ELLIPSE will always have most specific type some proper subtype of ELLIPSE.

• Invocation signatures can be defined having ELLIPSE as the declared type of their result. However, no operator invocation will ever return a value of most specific type ELLIPSE.

• Invocation signatures can also be defined having ELLIPSE as one of their argument types. However, no actual argument will ever have most specific type ELLIPSE.

• Let AREA_OF be an operator that applies to both circles and noncircles. Observe, then, that implementation code can be provided for that operator at the ELLIPSE level that will work for both circles and noncircles:

  OPERATOR AREA_OF VERSION E_AREA ( E ELLIPSE ) RETURNS AREA ;
     RETURN 3.14159 * THE_A ( E ) * THE_B ( E ) ;
  END OPERATOR ;

• The AREA_OF example gives some idea of the purpose of union types: They provide a way of defining operators, together with implementation code for those operators, that apply to values or variables of several different types, all of them proper subtypes of the union type in question.

A union type obviously can’t be a leaf type. However, it would be possible to set up the type schema in such a way that all types except leaf types (and the pertinent minimal type or types) are union types. With reference to Fig. 2, for example, introducing type NONCIRCLE as above, together with types NONRECTANGLE and NONSQUARE (as immediate subtypes of types POLYGON and RECTANGLE, respectively, and with the intuitively obvious semantics) would have such an effect. “All most specific types must be leaf types” might thus be regarded as the extreme form of the idea of union types, and some writers have indeed advocated such a notion. The Manifesto model doesn’t assume such an arrangement, but neither does it prohibit it.

Note that a nonunion type can have a union type (but not a dummy type) as a proper subtype. For example, type SQUARE might be a proper subtype of type RECTANGLE, where (a) RECTANGLE is a nonunion type and (b) SQUARE is divided into “big squares” and “small squares” and is therefore a union type.

Finally, what about tuple and relation union types? For simplicity, let’s focus on tuple types specifically. Loosely speaking, then, a tuple type that includes an attribute of some union type will itself effectively be a union type also (even though, technically, the concept doesn’t apply to tuple types). Similarly for relation types, mutatis mutandis.

v (...) Value of.

value of See model of a variable; model of an expression.

value substitutability Wherever a value of type T is permitted, a value of any subtype of T can be substituted. See Principle of Value Substitutability. Note that the concept of value substitutability is a logical consequence of the very notion of type inheritance. Note: Unfortunately, few writers (or languages or systems, come to that) seem to distinguish properly—or at all—between value substitutability and variable substitutability, q.v. But languages and systems that fail to make this distinction are very likely to permit such absurdities as circular noncircles (q.v.) and noncircular circles (q.v.).

variable substitutability Wherever a variable of declared type T is permitted, a variable of declared type some nonempty subtype of T can be substituted—but only if such substitution makes sense. See Principle of Variable Substitutability. Note: Unfortunately, few writers (or languages or systems, come to that) seem to distinguish properly—or at all—between variable substitutability and value substitutability, q.v. But languages and systems that fail to make this distinction are very likely to permit such absurdities as circular noncircles (q.v.) and noncircular circles (q.v.).

version (operator) Implementation version, q.v.

version signature See implementation version.