Explanation: Given the sample value for relvar P shown in Fig. 1, the RANK invocation returns a relation looking like this—
┌─────┬───────┬───────┬────────┬────────┬────┐
│ PNO │ PNAME │ COLOR │ WEIGHT │ CITY │ N2 │
├═════┼───────┼───────┼────────┼────────┼────┤
│ P6 │ Cog │ Red │ 19.0 │ London │ 1 │
│ P2 │ Bolt │ Green │ 17.0 │ Paris │ 2 │
│ P3 │ Screw │ Blue │ 17.0 │ Oslo │ 2 │
│ P4 │ Screw │ Red │ 14.0 │ London │ 4 │
│ P1 │ Nut │ Red │ 12.0 │ London │ 6 │
│ P5 │ Cam │ Blue │ 12.0 │ Paris │ 6 │
└─────┴───────┴───────┴────────┴────────┴────┘
—and the overall result thus looks like this:
┌─────┬───────┬───────┬────────┬────────┐
│ PNO │ PNAME │ COLOR │ WEIGHT │ CITY │
├═════┼───────┼───────┼────────┼────────┤
│ P6 │ Cog │ Red │ 19.0 │ London │
│ P2 │ Bolt │ Green │ 17.0 │ Paris │
│ P3 │ Screw │ Blue │ 17.0 │ Oslo │
└─────┴───────┴───────┴────────┴────────┘
Note that the cardinality of the result of a given quota query might not be exactly equal to the specified quota; in fact, it might be either less than or greater than that specified quota, depending on the query itself, and depending also on the current values of whatever relvars are involved in that query.
R-table Term used in Codd’s later writings to mean either a relation or a relvar or both, as the context demanded. The “R-” prefix was intended to stress the point that certain properties commonly associated with tables as such (in particular, top to bottom row ordering and left to right column ordering) didn’t apply. However, the term is deprecated because it fails to make the crucial distinction between values and variables.
range 1. See function. 2. See range variable.
range variable Relational calculus analog of a logic variable; in other words, a variable that “ranges over” some specified set of values—either the set of tuples in some relation (in tuple calculus) or the set of values of some type (in domain calculus)—and can appear either bound or free in relational calculus expressions.
Examples: See the examples under domain calculus, tuple calculus, and elsewhere.
RANK See ranking.
ranking Let relation r not have an attribute called A. Then (and only then) the expression RANK r BY (item, ..., item AS A) denotes a ranking of r. Within that overall expression, each item consists of the keyword ASC (ascending) or DESC (descending) followed by an (open) expression exp—typically but not necessarily just an attribute reference identifying an attribute of r—and the left to right sequence of such items specifies major to minor ordering in the usual way, in accordance with values of the specified expressions exp within the specified items. The overall expression returns a relation identical to r except that it has an additional attribute A whose value in any given tuple of that result shows that tuple’s ranking position with respect to the specified ordering.
Example: See the example under quota query.
RATIONAL In Tutorial D, a system defined type whose values are rational numbers (more precisely, rational numbers “of the first kind”). See rational number.
rational number A number that can be expressed as the ratio of two integers p and q (q ≠ 0)—e.g., 3/8, 593/370, −4/3. Such numbers fall into two categories: (a) those whose fractional part can be expressed in decimal notation by means of a finite sequence of digits followed by an infinite sequence of zeros, which can be ignored without loss (e.g., 3/8 = 0.375000...), and (b) those whose fractional part can be expressed in decimal notation by means of a possibly empty finite sequence of digits followed by another finite sequence of digits, the first of which is nonzero, that infinitely repeats (e.g., 593/370 = 1.60270270...). Note: It follows that rational numbers of the second kind can’t be precisely represented on a finite computer system—at least, not using conventional decimal notation. (In fact, of course, the same is true of “most” rational numbers of the first kind as well.) Contrast irrational number; real number.
read operator Same as read-only operator.
read-only operator Generally, a function; i.e., an operator that, when invoked, updates nothing (except possibly variables local to the implementation of the operator in question) but returns a value, of a type declared when the operator in question is defined (see specification signature). A read-only operator invocation thus denotes a value; i.e., it’s an expression—in fact, expression and read-only operator invocation are just two different terms for the very same concept—and it can therefore appear wherever a literal of the appropriate type is allowed. In particular, it can be nested inside other expressions.
Example: See the first example under argument.
Note: As mentioned elsewhere in this dictionary, certain read-only operators in SQL in particular are explicitly defined to be “possibly nondeterministic,” q.v., meaning they’re not functions at all, technically speaking. In truth, they really are functions; however, they’re ones that are deliberately underspecified and thus don’t behave like functions from the user’s point of view. See also ZO.
real database See Principle of Database Relativity.
real number Either a rational or an irrational number. The set of all real numbers forms a continuum called the real number line, q.v.
real number line An infinitely long straight line on which the real numbers are plotted according to their distance in a positive or negative direction from an arbitrarily chosen origin point (corresponding to the real number zero). Every point on the line corresponds to a unique real number and vice versa.
real relation The value of a given real relvar at a given time.
real relvar A base relvar or a snapshot (contrast virtual relvar).
record Term sometimes used to mean a row, in any of the possible senses of that term. All such uses are deprecated, however; the term is better reserved for an operating system or even physical level construct.
recovery log Same as log.
recursive query A relational expression, which by definition can be thought of as the invocation of some relation valued operator Op, whose evaluation involves further invocations of that same operator Op.
Example: Here’s a recursive definition of an operator that computes the transitive closure, q.v., of a binary relation with attributes PA and PB, both of type PNO (the code isn’t very efficient, but it can obviously be improved in a variety of ways):
OPERATOR TRANCLO ( PAB RELATION { PA PNO , PB PNO } )
RETURNS RELATION { PA PNO , PB PNO } ;
RETURN ( WITH ( temp := PAB UNION ( ( PAB RENAME { PB AS PC } )
COMPOSE ( PAB RENAME { PA AS PC } ) ) ) :
IF temp = PAB THEN temp ELSE TRANCLO ( temp ) END IF ) ;
END OPERATOR ;
Now the invocation TRANCLO (rx), where rx is a relational expression denoting a relation of the appropriate type, can be thought of as a “recursive query,” because its evaluation involves further invocations of TRANCLO itself (in general).
recursive relationship A relationship (in the sense of the third definition of that term, q.v.) in which the two sets participating are one and the same. The term isn’t particularly apt, since there’s no recursion, as such, involved (though such relationships do often give rise to recursive processing of some kind).
Example: The well known bill of materials application involves a relationship between parts and their components. That relationship is “recursive” because components are parts in turn and can have further components of their own.
recursive type Shorthand for recursively defined type.
recursively defined type (Without 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 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 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.
reductio ad absurdum “Reduction to absurdity”; a method of proof, q.v., that establishes something as true by showing that assuming its negation leads to a contradiction. Also known as indirect proof.
redundancy In general, something displays redundancy if and only if it “says the same thing twice.” With respect to databases in particular, however, it seems to be quite difficult to pin this notion down completely precisely. The following definition must therefore be regarded as somewhat tentative at this time: Let DB be a database variable (equivalently, a database design); let db be a database value that conforms to DB (i.e., let db consist of a collection of relation values, one for each relvar mentioned in DB); and let p be a proposition not involving any existential quantification. If db contains two or more distinct representations of p (either implicitly or implicitly), then db contains, and DB permits, redundancy. Note, however, that this definition says only that if (not if and only if) a certain condition holds, then there’s redundancy; it would be nice if that if could be strengthened to if and only if, but it’s not yet clear whether it can be (further research is needed). Note carefully too that a database can display redundancy by the foregoing definition even if it fully conforms to The Principle of Orthogonal Design and all normalization principles. For a detailed discussion of such matters, with numerous examples, see the book Database Design and Relational Theory: Normal Forms and All That Jazz, by C. J. Date (O’Reilly Media Inc., 2012).
Here are some further relevant considerations:
A relvar is subject to redundancy that can be eliminated by taking projections if and only if it’s not in ETNF, q.v. To put the point another way, a relvar allows redundant tuples (q.v.) if and only if it’s not in ETNF. Note: In fact, BCNF is sufficient to prohibit partly redundant tuples, q.v.; however, ETNF is necessary to prohibit fully redundant tuples, q.v.
(Attribute level redundancy): The following has been proposed as a definition of what it might mean for redundancy to exist at the level of the appearance, or occurrence, of some individual value of some individual attribute: Let relation r be a value of relvar R; let t be a tuple in r; and let v be an attribute value occurring within t. Then that occurrence of that value v within t is redundant in r, and R is subject to redundancy, if and only if replacing that occurrence of v by an occurrence of some value v′ (v′ ≠ v), while leaving everything else unchanged, leads to some dependency of R being violated. Note very carefully, however, that the term dependency in this definition refers only to dependencies that are FDs or JDs specifically—even embedded JDs are excluded. Be that as it may, a relvar is subject to this kind of redundancy if and only if it’s not in RFNF (q.v.).
Example (attribute level redundancy): Suppose the FD {CITY} → {STATUS} holds in our usual suppliers relvar S. Of course, the sample value shown for that relvar in Fig. 1 doesn’t satisfy this FD; however, it would do so if we changed the status for supplier S2 from 10 to 30, so let’s suppose for the sake of the example that this change has in fact been made. Suppose also that (as in Fig. 1) the tuple for supplier S1 in that relvar has city London and status 20, and the tuple for supplier S4 also has city London. Then this latter tuple must also have status 20, for otherwise the FD {CITY} → {STATUS} would be violated. In a sense, therefore, the occurrence of that status value 20 in the tuple for supplier S4 is redundant, because there’s nothing else it could possibly be—it’s a logical consequence of, and is fully determined by, the values appearing elsewhere in the relation that’s the current value of the relvar at the time in question. Note: The notion of partly redundant tuples—see partly redundant—is motivated by such considerations, in part.
Caveat: This dictionary is of course primarily concerned with the relational or logical level of the system—i.e., with the database as perceived by the user. Now, there will almost certainly be redundancy at the internal level of the system (i.e., redundancy in the data as physically stored: between an index and the data it indexes, for example). But such physical redundancy exists purely for performance, data recovery, and other such pragmatic reasons—it has no effect (or should have no effect) on the data as seen by the user. Thus, the term redundancy must be understood throughout this dictionary as referring to what might more accurately be called logical redundancy, meaning redundancy in the data as perceived by the user (barring explicit statements to the contrary, of course).
redundancy free normal form Relvar R is in redundancy free normal form (RFNF) if and only if it’s not subject to redundancy at the level of the appearance, or occurrence, of some individual value of some individual attribute of the relvar in question (see redundancy)—equivalently, if and only if (a) R is in BCNF and (b) for every JD J that holds in R, the union of those components of J that are superkeys for R is equal to the heading of R. Every RFNF relvar is in ETNF. Note: RFNF is logically equivalent to KCNF, q.v.
Example: As noted under Boyce/Codd normal form, with the normal forms it’s often more instructive to show a counterexample rather than an example per se. Consider, therefore, relvar SPJ, with attributes SNO (supplier number), PNO (part number), and JNO (project number), and predicate Supplier SNO supplies part PNO to project JNO. Let the sole key for that relvar be {SNO,PNO}. Also, let the relvar be subject to the constraint that if (a) supplier sno supplies part pno and (b) part pno is supplied to project jno and (c) project jno is supplied by supplier sno, then (d) supplier sno supplies part pno to project jno. Then SPJ is equal to the join of its projections on {SNO,PNO}, {PNO,JNO}, and {JNO,SNO}—i.e., the JD
{ { SNO , PNO } , { PNO , JNO } , { JNO , SNO } }
holds in SPJ—and so that relvar can be nonloss decomposed into those three projections. However, since the only component of that JD that’s a superkey is {SNO,PNO}, relvar SPJ isn’t in RFNF, though it is in ETNF.
redundant tuple Tuple t is redundant in relation r if and only if it’s either partly redundant, q.v., or fully redundant, q.v., in r. Contrast essential tuple; see also essential tuple normal form.
REF type (SQL) In SQL, defining a structured type (q.v.) causes automatic definition of an associated REF type. If T is the structured type in question, the corresponding REF type is denoted REF(T), and its values are “references”—i.e., pointers—to rows in some “typed table” (see Part II of this dictionary) that’s defined to be “of” type T. Thus, REF is really a type generator, and values of a REF type are SQL’s analog of object IDs; in other words, they’re pointers. Further details are beyond the scope of this dictionary.
reference See referencing.
reference (SQL) Term used in SQL to mean (among several other things) a value of some REF type, q.v.
referenced key See foreign key.
referenced relvar See foreign key.
referenced tuple See foreign key.
referencing The relational meaning of this term is as described under foreign key; it should not be confused with the operator of the same name, found in systems that support pointers (and perhaps more aptly called “address of”), that, given a variable V, returns a pointer to V. Note that this latter operator is rather unusual, inasmuch as (a) it’s certainly read-only and yet (b) as with an update operator, its argument—its sole argument, that is—must be a variable specifically.
Note: Systems that support pointers usually support an operator called dereferencing as well, which, given a pointer p, returns the variable V that p points to; equivalently, given an address p, the operator returns the variable at that address p. (This operator is unusual too, in that, in general, it returns a variable instead of a value. However, the use of the term found in SQL in particular is unorthodox, in that SQL’s dereferencing operator—which exists in two distinct forms, incidentally—returns a value, not a variable: namely, the value of whatever it is that its pointer argument points to. What’s more, SQL doesn’t support a corresponding referencing operator at all!)
referencing relvar See foreign key.
referencing tuple See foreign key.
referential action The action specification portion of a foreign key rule (e.g., “cascade,” in a cascade DELETE rule); also used to refer to the specified action as such.
referential constraint See foreign key.
referential cycle A referential path, q.v., from some relvar R to itself. Database designs involving such cycles are best avoided because they lead to a need for multiple assignment, which today’s DBMS products don’t support. (At least, they don’t support it in the form tacitly being considered here—the form, that is, in which the individual assignments involved in the multiple assignment in question are, specifically, explicit assignments to database relvars.)
referential integrity Loosely, the rule that no referencing tuple is allowed to exist if the corresponding referenced tuple doesn’t also exist. More precisely, let FK be some foreign key in some referencing relvar R2; let K be the corresponding key in the corresponding referenced relvar R1; and let K′ be derived from K in the manner explained under foreign key. Then the referential integrity rule requires there never to be a time at which there exists an FK value in R2 that isn’t the K′ value for some (necessarily unique) tuple in R1. Note: Either or both of R1 and R2 in the foregoing definition might in fact be “hypothetical views,” in the sense of that term explained under, e.g., foreign key constraint. See also foreign key; foreign key rule.
referential path Let relvars Rz, Ry, Rx, ..., Rb, Ra be such that there exists a referential constraint from Rz to Ry, a referential constraint from Ry to Rx, ..., and a referential constraint from Rb to Ra. Then the chain of such constraints from Rz to Ra constitutes a referential path from Rz to Ra (and the number of constraints in the chain is the length of the path). Note: Any or all of Rz, Ry, Rx, ..., Rb, Ra in the foregoing definition might in fact be a “hypothetical view,” in the sense of that term explained under, e.g., foreign key constraint.
reflexivity 1. (Of a dyadic logical operator) The dyadic logical operator Op, which we assume for definiteness is expressed in infix style, is reflexive if and only if, for all x, x Op x is true. 2. (Of a binary relation) The binary relation r is reflexive if and only if, for all x, the tuple <x,x> appears in r. 3. (Of FDs) See Armstrong’s axioms. Note: The first two of these definitions are slightly oversimplified, in that they deliberately fail to specify the range of possible values for x.
Examples (first definition only): The logical operators EQUIV and IMPLIES; the partial ordering operator “≤”; the equality operator “=”.
refresh See snapshot.
RELATION In Tutorial D, the name of the type generator for relation types. Also used in Tutorial D to denote a relation selector.
Examples: For examples showing the RELATION type generator, see the examples under relation type. Here by contrast is an example of a relation selector invocation:
RELATION { TUPLE { SNO SNO('S1') ,
SNAME NAME('Smith') ,
STATUS 20 ,
CITY 'London' } ,
TUPLE { SNO SNO('S5') ,
SNAME NAME('Adams') ,
STATUS 30 ,
CITY 'Athens' } }
relation A relation value, q.v. Note: The term is also commonly used to refer to a relation variable, of course, but that usage is strongly deprecated as the source of much confusion.
relation (mathematics) Given sets s1, s2, ..., sn, not necessarily distinct, r is a relation on those sets if and only if it’s a set of n-tuples each of which has its first element from s1, its second element from s2, and so on. (In other words, r is a subset of the cartesian product s1 × s2 × ... × sn.) Set si is the ith domain of r (i = 1, 2, ..., n).
Note: There are several important logical differences between a relation in mathematics and its relational model counterpart. Here are some of them:
Mathematical relations have a left to right ordering to their attributes.
Actually, mathematical relations have, at best, only a very rudimentary concept of attributes anyway. Certainly their attributes aren’t named, other than by their ordinal position.
As a consequence, mathematical relations don’t really have a heading (nor, a fortiori, a type) in the relational model sense.
Mathematical relations are usually either binary or, just occasionally, unary. By contrast, relations in the relational model are of degree n, where n can be any nonnegative integer (possibly even zero).
Relational operators such as JOIN, EXTEND, and the rest were first defined in the context of the relational model specifically; the mathematical theory of relations includes few such operators.
And so on (the foregoing isn’t an exhaustive list).
relation assignment Same as relational assignment.
relation comparison Same as relational comparison.
relation constant A relation, especially one that’s named; not to be confused with a relation literal, q.v.
Examples: TABLE_DEE and TABLE_DUM. Note: These two relation constants are probably built in (assuming they’re supported at all, that is, which in today’s products they’re probably not). Here by contrast is one that’s user defined:
CONST STATES_OF_THE_USA
RELATION { TUPLE { STATE NAME('Alabama') } ,
TUPLE { STATE NAME('Alaska' ) } ,
..............
TUPLE { STATE NAME('Wyoming') } } ;
relation equality (Without inheritance) Equality of relations; relations r1 and r2 are equal—i.e., the relational comparison r1 = r2 evaluates to TRUE—if and only if r1 and r2 are the very same relation, meaning they have the same heading and the same body (i.e., their headings are equal and their bodies are equal too).
relation expression Same as relational expression.
relation level See set level.
relation literal A literal that denotes a relation; not to be confused with a relation constant, q.v.
Examples: See the examples under literal.
relation inclusion Same as relational inclusion.
relation predicate Let r be a relation. Then the relation predicate for r is the predicate that represents the user understood meaning of r in some particular context. If r is of degree n, that predicate will be n-adic (it will have a parameter for each attribute of r). In accordance with The Closed World Assumption, moreover, the body of r will contain all and only those tuples that correspond to invocations (instantiations) of that predicate that evaluate to TRUE.
Examples: 1. Let r be the projection of the current value of relvar S on {SNO,CITY}. Then the predicate for r is There exists a name sn and a status st such that supplier SNO is under contract, is named sn, has status st, and is located in city CITY. Note that this predicate is dyadic, as is to be expected for a binary relation. 2. Consider the relations r1 and r2, where r1 is the projection of the current value of relvar S on{CITY} and r2 is the projection of the current value of relvar P on{CITY}. Then it’s certainly possible for r1 and r2 to be equal; nevertheless, they have different predicates, corresponding to their two different contexts (loosely speaking, the predicates are There exists a supplier located in city CITY and There exists a part stored in city CITY, respectively).
relation schema / relation scheme Terms much used in the research literature, though very little in commercial practice, to mean a relation heading or (especially) relvar heading—or sometimes such a heading in combination with a relvar name and/or with certain dependencies (e.g., FDs), q.v.
relation selector Let T be a relation type; then the corresponding selector is an operator that allows a relation of type T to be selected, or specified, by supplying a set of tuple values. More precisely, let T be a relation type, and let the corresponding heading be H; then there’s exactly one selector, S say, for that type T, and S is such that (a) the sole argument to any given invocation of S is a set of tuples all with heading H; (b) every relation of type T is producible by means of some invocation of S in which those tuples are all represented by tuple literals; and (c) every successful invocation of S produces a relation of type T. See also selector.
Examples: See the examples under selector and elsewhere. Of course, those examples illustrate, not incidentally, the syntax used for relation selectors in Tutorial D specifically; other syntactic styles might be possible, but they must be logically equivalent to the Tutorial D style.
relation type Let H be a heading; then (and only then) RELATION H denotes a relation type—in fact, the sole relation type—with the same degree and attributes as H. Note: The following lightly edited extract from The Third Manifesto elaborates on the foregoing relation type naming convention:
When we say “the name of [a certain relation type] shall be RELATION H,” we do not mean to prescribe specific syntax. The Manifesto does not prescribe syntax. Rather, what we mean is that the type in question shall have a name that does both of the following, no more and no less: First, it shall specify that the type is indeed a relation type; second, it shall specify the pertinent heading. Syntax of the form “RELATION H” satisfies these requirements, and we therefore use it as a convenient shorthand; however, all appearances of that syntax throughout this Manifesto are to be interpreted in the light of these remarks.
Examples: Consider the Tutorial D definition for relvar S:
VAR S BASE
RELATION { SNO SNO , SNAME NAME , STATUS INTEGER , CITY CHAR }
KEY { SNO } ;
The second line of this definition constitutes an invocation of the RELATION type generator and thereby specifies the declared type of the variable being defined. To be specific, the keyword RELATION shows it’s a relation type, while the rest of the line—a commalist, enclosed in braces, of <attribute name, type name> pairs—defines the pertinent heading. The declared type of relvar S is thus exactly the result of the specified invocation:
RELATION { SNO SNO , SNAME NAME , STATUS INTEGER , CITY CHAR }
By way of a second example, the following (corresponding to a certain projection of relvar S) also denotes a certain relation type:
RELATION { CITY CHAR , SNAME NAME }
Note that Tutorial D provides nothing analogous to a TYPE statement, q.v., for defining relation types. Instead, such types can be defined only by invoking the relation type generator, q.v., as illustrated in the foregoing examples.
relation type generator See RELATION; see also type generator.
relation type inference The process of determining the type of the value denoted by a given relational expression. Note that this process is completely specified by the rules defining the types of the results of the various relational operators, q.v.
relation value Very loosely, a table (value). More precisely, let H be a heading, let B be a body consisting of tuples with heading H, and let r be the pair <H,B>. Then (and only then) r is a relation value (relation for short), with heading H and body B, and the same degree and attributes as H and the same cardinality as B. See also relation predicate; contrast relation variable. Note: It follows from this definition that a relation doesn’t really contain tuples (it contains a body, and that body in turn contains tuples), but it’s usual to talk as if relations contained tuples directly, for simplicity. Note too that relations in the relational model differ in several important respects from the mathematical construct of the same name. In particular, relations in mathematics typically don’t have named attributes; instead, their attributes are identified by ordinal position, left to right. For other differences, see relation (mathematics).
relation valued attribute An attribute whose type is some relation type. Values of such an attribute are relations of the specified type (sometimes called nested relations, since they’re “nested” inside tuples—typically but not necessarily tuples within the relation that’s the current value of some relvar, or tuples within the relation that’s the result of some query). Note: If some relvar has a relation valued attribute, that fact in and of itself doesn’t constitute a violation of any particular level of normalization (not even first); however, such attributes are usually contraindicated in base relvars in particular, because they necessarily imply some structural asymmetry in the database and thereby give rise to asymmetry (and hence complexity) in queries, constraints, and updates as well. See also grouping; ungrouping.
Example: See the example under grouping.
relation variable Very loosely, a table (variable); more precisely, a variable whose type is some relation type. Let relation variable R be of declared type T; then R has the same heading (and therefore the same attributes and degree) as type T does. Let the value of R at some given time be r; then R has the same body and cardinality at that time as r does. Note that a relation variable is not the same thing as a set of tuple variables (not even a set of tuple variables all of the same type). See also relvar predicate; variable; contrast relation value.
relational algebra An open ended collection of read-only operators on relations, each of which takes one or more relations as operands and produces a relation as a result. Exactly which operators are included is somewhat arbitrary, but the collection overall is required to be at least as powerful as relational calculus, meaning that for every relational calculus expression there exists some logically equivalent expression in relational algebra (in other words, the algebra is required to be relationally complete, q.v.). Also, the operators are generic, in the sense that they apply to all possible relations, loosely speaking. See also Codd’s relational algebra.
Note: If we want relational algebra to be regarded as an algebra in the same sense that the algebra of sets, q.v., is so regarded—which presumably we do—then we ought really to require, in addition to the operators that produce a relation as a result, support for the relational inclusion operator (q.v.), which produces a truth value, not a relation, as a result. Note also that relational assignment (q.v.) is also a relational operator, but it isn’t a relational algebra operator as such because it isn’t read-only.
relational assignment (Without inheritance) An operation that assigns a relation value of type T to a relation variable of that same type T. The relational operations INSERT, D_INSERT, DELETE, I_DELETE, and UPDATE are all special cases; in fact, every invocation of one of these operators is logically equivalent to some specific invocation of the explicit relational assignment operation (“:=”) as such. Fundamentally, therefore, relational assignment is the only relational update operator logically required. Conversely, however, any given relational assignment is logically equivalent to a certain DELETE / INSERT combination (more precisely, a certain I_DELETE / D_INSERT combination). To be specific, the relational assignment
R := rx
(where R is a relvar reference and rx is a relational expression of the same type as R) is logically equivalent to an explicit relational assignment of the form
R := ( r MINUS d ) UNION i
where:
r is the “old” value of R
d is the set of tuples to be deleted from R (the “delete set”)
i is the set of tuples to be inserted into R (the “insert set”)
d is a subset of r
i and r are disjoint
d and i are disjoint a fortiori
d and i are unique
In other words, the original assignment R := rx is logically equivalent to the following multiple assignment—in fact, a multiple assignment (q.v.) in which the individual assignments both involve the same target, q.v.:
DELETE R d , INSERT R i
Thus, any given relational assignment to relvar R can always be thought of as a combination of a delete operation on R and an insert operation on R. In fact, given that (a) d is a subset of r and (b) i and r are disjoint, the original assignment is logically equivalent to either of the following:
I_DELETE R d , D_INSERT R i
D_INSERT R i , I_DELETE R d
If d is empty, the assignment is effectively a pure insert operation; if i is empty, it’s effectively a pure delete operation.
relational calculus An applied form of predicate calculus, tailored to operating on relations, with the property that every relational calculus expression is logically equivalent to some relational algebra expression. Note: The converse is true, too—i.e., every relational algebra expression is logically equivalent to some relational calculus expression. In other words, the algebra and the calculus can be regarded as functionally equivalent, and hence interchangeable. In fact, they’re both relationally complete, q.v. (It’s interesting to note, incidentally, that the first version of relational calculus to be defined—see E. F. Codd, “Relational Completeness of Data Base Sublanguages,” in Randall J. Rustin, ed., Data Base Systems, Courant Computer Science Symposia Series 6, Prentice-Hall, 1972—was in fact not as expressive as the relational algebra as defined in that same paper, because it failed to support any calculus counterpart to the algebraic union operator.)
Examples: See the examples under domain calculus and tuple calculus.
relational comparison (Without inheritance) A boolean expression of the form (rx1) theta (rx2), where rx1 and rx2 are relational expressions of the same type T and theta is any comparison operator that makes sense for relations (“=”, “≠”, “⊆”, etc.). Note: The parentheses enclosing rx1 and rx2 in the comparison might not be needed in practice. Note too that all possible relational comparisons can be defined in terms of the relational inclusion operator “⊆”, q.v. Fundamentally, therefore, relational inclusion is the only relational comparison operator logically required.
relational completeness A basic measure of the expressive power of a language. Essentially, a language is relationally complete if and only if it’s at least as expressive as relational calculus, meaning that any relation definable by some relational calculus expression is also definable by some expression of the language in question.
Examples: Relational algebra is relationally complete, because for every relational calculus expression there exists some logically equivalent expression in relational algebra. (In fact, as noted under relational calculus, the converse is true as well; that is, for every relational algebra expression there exists some logically equivalent expression in relational calculus, at least with the algebra and calculus as usually defined.) For example, the relational calculus expression
{ SX.SNAME } WHERE EXISTS SPX ( SPX.SNO = SX.SNO )
(where SX and SPX are range variables, q.v., that range over the current values of S and SP, respectively) is logically equivalent to this relational algebra expression:
( S MATCHING SP ) { SNAME }
It follows that in order to prove some given language L is relationally complete, it suffices to prove that every relational algebra expression is logically equivalent to some expression in L—which is often easier than proving that every relational calculus expression is logically equivalent to some expression in L. SQL, for example, can be shown to be “almost” relationally complete in this way (“almost” because SQL fails to support TABLE_DEE and TABLE_DUM, q.v.). Note: Actually SQL is also “more than” relationally complete, in a sense, in that its expressions permit the definition of many objects that aren’t relations at all. As this example should be sufficient to suggest, being more than relationally complete isn’t necessarily a good thing.
relational database A database that abides by The Information Principle. We assume throughout this dictionary that all databases are relational, barring explicit statements to the contrary. Note: SQL databases must be regarded as only approximately relational at best, since SQL involves so many departures from The Information Principle (including but not limited to the departures identified under table, q.v.).
relational DBMS A DBMS that manages relational databases (and relational databases only); equivalently, a DBMS that implements the relational model. Note: SQL DBMSs must be regarded as only approximately relational at best, since SQL involves so many departures from the relational model (including but not limited to the departures identified under table, q.v.).
relational expression An expression denoting a relation. Relation selector invocations (and hence relation literals), relcon and relvar references, and relational algebra operator invocations are all special cases.
relational inclusion Let relations r1 and r2 be of the same type. Then r1 includes r2 (“r1 ⊇ r2”) if and only if its body is a superset of that of r2, and r2 is included in r1 (“r2 ⊆ r1”) if and only if its body is a subset of that of r1. Relation r1 is equal to relation r2 (“r1 = r2”) if and only if each includes the other. Observe that every relation is included in itself, also that every relation both (a) includes the empty relation of the applicable type and (b) is included in the universal relation of the applicable type. Observe also that the term relational inclusion is usually taken, a trifle arbitrarily, to refer to the operator “⊆” specifically, not the operator “⊇”.
relational model A data model, in the first sense of that term, q.v.; the formal theory or foundation on which relational databases in particular and relational technology in general are based. The relational model is often loosely characterized as having three aspects: a structural aspect, which has to do with relations per se; an integrity aspect, which has to do with keys and foreign keys; and a manipulative aspect, which has to do with operators such as join. A more precise characterization is as follows. The relational model consists of the following five components: (a) an open ended collection of types, including in particular the scalar type BOOLEAN; (b) a relation type generator and an intended interpretation for relations of types generated thereby; (c) facilities for defining relation variables of such generated relation types; (d) a relational assignment operator; and (e) a relationally complete, q.v., but otherwise open ended collection of generic read-only operators (i.e., relational algebra or relational calculus or something logically equivalent) for deriving relations from relations. Note part (e) in particular; it’s a far too common error to regard the relational model as consisting of structure only and to overlook the operators, and yet (as Codd once said) structure without operators is rather like anatomy without physiology. Note too that those operators aren’t just meant for writing queries, as many seem to think; rather, they’re for writing expressions, expressions that serve many different purposes, including query but not limited to query alone. One particularly important purpose is the formulation of constraints (though in this case the relational expression will be just a subexpression of some boolean expression, frequently though not invariably an invocation of IS_EMPTY, q.v.). Note too that, in the interest of physical data independence, q.v., the relational model is deliberately silent on everything to do with performance (including physical storage representations in particular). See also essentiality.
Caveat: The term relational model is often used in the commercial world to mean a data model in the second sense of that term, when the data model in question is specifically a relational one. This second meaning is somewhat deprecated, however, because of the potential confusion with the first (and vastly more important) meaning as defined above.
relational operator An operator that takes relations or relvars or both as operands and either returns a relation or updates a relvar.
relationally complete See relational completeness.
relationship 1. A term used briefly in Codd’s earliest papers (but quickly discarded) to mean what we would now call either a relation or a relvar, as the context demands. It was used to distinguish relations in the relational model sense (which don’t have a left to right ordering to their attributes) from their mathematical counterparts, q.v. (which do). 2. In E/R modeling, “an association among entities” (this extremely imprecise definition is taken from Chen’s original E/R paper, “The Entity-Relationship Model—Toward a Unified View of Data,” ACM TODS 1, No. 1, March 1976). 3. More generally, given two sets (not necessarily distinct), a rule pairing elements of the first set with elements of the second set; equivalently, that pairing itself. Note: This last definition can easily be extended to three, four, ..., or any number of given sets. By way of illustration, consider the relationship involving suppliers, parts, and projects mentioned in the example under essential tuple normal form and elsewhere.
relative complement See complement (set theory).
relcon A relation constant, q.v.
relcon reference Syntactically, a relcon name, used to denote the value of that relcon. See also constant reference.
relvar A relation variable, q.v. Note: For simplicity, we assume in this dictionary that all relvars are part of some database (“database relvars”). However, there’s no good reason why relvars that are local to some application (“application relvars”) shouldn’t be supported as well.
relvar constraint 1. (“A” relvar constraint) Formally, any constraint that refers to the relvar in question, as well as possibly others; informally, a single-relvar constraint, q.v. Note: These definitions aren’t meant to be equivalent in any sense—they refer to two distinct concepts. 2. (“The” relvar constraint) The logical AND of all constraints, apart from type constraints, that refer to a given relvar (the relvar constraint—sometimes called the total relvar constraint, for emphasis—for the relvar in question); in other words, the formal, system understood “meaning” for the relvar in question (contrast relvar predicate). Note that it follows from this definition that one constraint that applies to every relvar is the degenerate (“default”) constraint TRUE. (In fact, of course, every relvar is necessarily subject to at least one key constraint, anyway.) Note too that all relvar constraints, in either sense, are also database constraints, q.v.
Examples: First, the key constraint specified in the definition of relvar S is a relvar constraint on that relvar (and the same would be true for all FDs, MVDs, and JDs—in particular, ones not implied by the keys—that apply to that relvar, if any such had been specified). Second, the foreign key constraint from SP to S is a relvar constraint for both relvar S and relvar SP. Third, here are a couple more relvar constraints (repeated from the examples under database constraint) that might apply to relvar S:
CONSTRAINT C1 IS_EMPTY ( S WHERE STATUS < 1 OR STATUS > 100 ) ;
/* status values must be in the range 1 to 100 inclusive */
CONSTRAINT C3 IS_EMPTY
( ( S JOIN SP ) WHERE STATUS < 20 AND PNO = PNO('P6') ) ;
/* no supplier with status less than 20 can supply part P6 */
(Constraint C3 is also a relvar constraint for relvar SP.)
Finally, suppose for the sake of the example that the foregoing constraints (the key constraint on relvar S, the foreign key constraint from relvar SP to relvar S, and constraints C1 and C3 above) are the only ones that apply to relvar S. Then the logical AND of all of them is “the” (total) relvar constraint for that relvar.
relvar predicate Let R be a relvar. Then the relvar predicate for R is the predicate that represents the user understood meaning of R. If R is of degree n, that predicate will be n-adic (it will have a parameter for each attribute of R). In accordance with The Closed World Assumption, moreover, at any given time the body of R will contain all and only those tuples that correspond to invocations (instantiations) of that predicate that evaluate to TRUE at that time. Contrast relvar constraint (second definition); this latter is a formal construct, but relvar predicates are necessarily somewhat informal. Note: Relvar predicates are sometimes called business rules, q.v.—though most writers take this latter term to include a variety of other constructs in addition to relvar predicates as such, including in particular the informal counterparts to various integrity constraints. (Conversely, some writers regard such additional constructs as part of the relvar predicates. There’s no consensus on such matters.)
Example: The relvar predicate for relvar S is Supplier SNO is under contract, is named SNAME, has status STATUS, and is located in city CITY. At least, this predicate is the one assumed (and indeed stated) elsewhere in this dictionary to be the one for relvar S. However, it would really be more accurate to say the predicate is, rather, We know that—or (perhaps better) We believe that—supplier SNO is under contract, is named SNAME, has status STATUS, and is located in city CITY. The point is, there can’t be any guarantee that the database truly reflects the state of affairs that exists in the real world (see correctness); all it can do is reflect what users tell it, and what users tell it in turn will reflect their beliefs about the real world, not necessarily the real world per se. Note in particular, therefore, that if a certain tuple—say the tuple <S6,Lopez,30,Madrid>—currently fails to appear in relvar S, the accurate interpretation isn’t It’s not the case that supplier S6 is under contract, is named Lopez, has status 30, and is located in city Madrid; rather, it’s It’s not the case that we know that—or, more colloquially and more simply, We don’t know whether—supplier S6 is under contract, is named Lopez, has status 30, and is located in city Madrid. Of course, it’s customary to ignore such considerations in informal contexts, but perhaps it ought not to be. For further discussion, see Appendix C (“A Relational Approach to Missing Information”) in C. J. Date, SQL and Relational Theory: How to Write Accurate SQL Code (3rd edition, O’Reilly Media Inc., 2015).
relvar reference Syntactically, a relvar name, used to denote either the relvar as such or the value of that relvar, as the context demands.
relvar vs. type The logical difference between these two concepts is discussed under First Great Blunder. But the question is sometimes asked: When should a given “entity type” be represented as a relvar and when as a type? A detailed discussion of this issue can be found in the Manifesto book, but here are some relevant observations:
If T is a type, there’s no way to insert new values into or delete existing values from T. By contrast, if R is a relvar, it’s certainly possible to insert new tuples into or delete existing tuples from R. To take a concrete example, if the given entity type is “employees,” representing them as a type would mean there would be no way to hire and fire them.
Tuples in a relvar correspond to propositions and thus assert certain facts—e.g., the fact that “Supplier S1 is under contract, is named Smith, has status 20, and is located in London.” By contrast, values of some type don’t in and of themselves assert anything at all (e.g., what does the integer 3 assert?). For example, if suppliers are represented as a type, with type name S, the following might be a corresponding selector invocation:
S ( SNO('S1') , NAME('Smith') , 20 , CITY 'London' )
But this selector invocation constitutes, in effect, nothing more than a certain rather heavy duty noun—something like “an S1-numbered, Smith-named, status-20, London-located supplier.” To repeat, it doesn’t assert any facts, as such, at all.
REMOVE An operator of the algebra A, q.v., equivalent to “project on all attributes but one” (i.e., the A expression r REMOVE A, where r is a relation and A is an attribute of r, is equivalent to the Tutorial D expression r{ALL BUT A}).
RENAME See renaming.
renaming Let relation r have an attribute called A and no attribute called B. Then (and only then) the expression r RENAME {A AS B} denotes an attribute renaming on r, and it returns the relation with heading identical to that of r except that attribute A in that heading is renamed B, and body identical to that of r except that all references to A in that body—more precisely, in tuples in that body—are replaced by references to B. See also tuple renaming.
Example: The expression
P RENAME { WEIGHT AS WT }
returns a relation identical to the current value of relvar P, except that attribute WEIGHT is renamed WT. Note that relvar P per se remains unaltered in the database—RENAME is not like ALTER TABLE in SQL, it’s just a read-only operator (like restrict, for example) that takes a certain relation as input and returns another as output.
Note: Tutorial D additionally supports a form of RENAME that allows two or more separate renamings to be carried out in parallel (“multiple RENAME”). Here’s an example:
P RENAME { WEIGHT AS WT , COLOR AS COL }
Note in particular that this feature simplifies the process of interchanging attribute names. For example, the multiple renaming
r RENAME { A AS B , B AS A }
is equivalent to, and can be thought of as shorthand for, an expression of the form
( ( r RENAME { B AS C } ) RENAME { A AS B } ) RENAME { C AS A }
for some arbitrary attribute name C that’s distinct from A and B but is otherwise unspecified.
repeating field See repeating group.
repeating group Let some table have a column C of type T. Then C is a repeating group column if and only if the values appearing within C aren’t values of type T but are, rather, collections (i.e., sets or bags or sequences or arrays or ...) of values of type T. Repeating groups are outlawed in the relational model (which is why this definition is phrased in terms of tables and columns instead of relations and attributes); in fact, a “relation” with a repeating group “attribute” is a contradiction in terms. Note: Technically, the foregoing definition might be considered as defining a repeating field rather than a repeating group. A repeating group would then be a repeating field in which the pertinent “field” is actually a combination of two or more columns, considered as a unit. For example, a row in an employee table might contain the employee number and a repeating group of job history information, giving, for each job held by the employee in question, the job title, start date, and end date. However, the distinction in question—i.e., between repeating fields and repeating groups—is unimportant for present purposes. In any case, there’s a great deal of confusion in the literature over the precise meaning of either term; the foregoing definitions are offered in an attempt to clarify the situation, but there’s much more that could be said. In particular, note carefully that—contrary to popular opinion, perhaps—a relation valued attribute, q.v., is quite definitely not a “repeating group column” by the foregoing definition, and any or all suggestions to the contrary should be firmly resisted. (In particular, relation valued attributes are permitted by the relational model, while repeating groups aren’t.)
reporter See observer.
representation Either a physical representation (q.v.) or a possible representation (q.v.), as the context demands.
restriction Let r be a relation and let bx be a restriction condition, q.v., on r (implying in particular that every attribute reference in bx identifies some attribute of r). Then (and only then) the expression r WHERE bx denotes the restriction of r according to bx, and it returns the relation with heading the same as that of r and body consisting of all tuples of r for which bx evaluates to TRUE.
Example: The following expression denotes a restriction of the relation that’s the current value of relvar P:
P WHERE WEIGHT < WEIGHT(17.5)
Note: Restriction is often referred to as selection, but this term is deprecated, slightly, because of the potential confusion with either selector operations or the SELECT operation of SQL or both. Regarding selector operations, see selector. As for the SELECT operation of SQL—meaning, more specifically, just the SELECT portion of an SQL SELECT expression, q.v.—that operation can be loosely characterized as a combination of summarize, extend, rename, and “project” operations (“project” in quotes because SELECT doesn’t eliminate duplicates, in general, unless explicitly requested to do so via DISTINCT). Note in particular, therefore, that “selection” in the sense of restriction is explicitly not one of the operations performed by the SELECT portion of an SQL SELECT expression (!).
restriction condition Let r be a relation; then a restriction condition on r is a boolean expression—typically an open expression, q.v.—in which all attribute references are references to attributes of r and there are no relvar references. See restriction.
Note: WHERE clauses in real languages typically permit boolean expressions that are more general than simple restriction conditions on the pertinent relation. (Certainly this is the case for both SQL and Tutorial D.) Strictly speaking, in fact, a restriction condition isn’t even supposed to contain any connectives; rather, it’s supposed to consist, at its most complex, of a simple comparison, q.v. In practice, however, the following identities let real languages support the connectives in WHERE clauses after all:
r WHERE ( ( p ) AND ( q ) ) ≡ ( r WHERE p ) INTERSECT ( r WHERE q )
r WHERE ( ( p ) OR ( q ) ) ≡ ( r WHERE p ) UNION ( r WHERE q )
r WHERE ( NOT ( p ) ) ≡ r MINUS ( r WHERE p )
Examples: For an example of a WHERE clause in which the boolean expression is just a simple restriction condition on the pertinent relation, see restriction. Here by contrast is an example in which the boolean expression is more general:
S WHERE P { PNO } =
( ( SP RENAME { SNO AS ZNO } ) WHERE ZNO = SNO ) { PNO }
The boolean expression in the (outer) WHERE clause here isn’t just a simple restriction condition on the relation that’s the current value of relvar S, because (a) it contains attribute references that don’t identify attributes of that relation, and (b) it also contains two relvar references. However, the expression overall can be seen as shorthand for something like the following:
WITH ( temp := EXTEND S : { X := P { PNO } , Y := !!SP { PNO } } ) :
temp WHERE X = Y
In this expanded formulation, X and Y are attributes—in fact, relation valued attributes, q.v.—of temp, and the predicate in the WHERE clause in the second line is indeed a restriction condition as formally defined. Note: The expression !!SP in the first line is an image relation reference, q.v.
RETURN Let Op be a read-only operator, and let the implementation code for Op be written in Tutorial D; then that code must contain at least one Tutorial D RETURN statement. The purpose of that statement is (a) to terminate execution of an invocation of Op and (b) to specify the value (the “return value”) to be returned to the invoker by the invocation in question. Note: The foregoing remarks also apply if Op is an update operator, except that (a) there won’t be any return value—so the RETURN statement will consist simply of the keyword RETURN followed by a semicolon—and (b) that RETURN statement need not be specified explicitly, because such a statement will implicitly be placed in the code anyway, immediately prior to the END OPERATOR specification.
Examples: The code fragments shown below constitute two versions, a read-only version and an update version, of an operator called MOVE that moves a specified ellipse such that it becomes centered on the center of a specified rectangle. (CTR is a read-only operator that returns the center of its rectangle argument.) Note the RETURN statement in the first version and the absence of such a statement from the second.
OPERATOR MOVE ( E ELLIPSE , R RECTANGLE ) RETURNS ELLIPSE ;
RETURN ELLIPSE ( THE_A ( E ) , THE_B ( E ) , CTR ( R ) ) ;
END OPERATOR ;
OPERATOR MOVE ( E ELLIPSE , R RECTANGLE ) UPDATES { E } ;
THE_CTR ( E ) := CTR ( R ) ;
END OPERATOR ;
RETURNS (Without inheritance) Let Op be an operator; then Op has an invocation signature, consisting essentially of the specification signature, q.v., minus the operator name. In Tutorial D, therefore, the invocation signature consists of the combination of (a) the declared types (in order) of the parameters to Op, and either (b) the declared type—defined via the RETURNS clause—of the result, if any, of executing Op or (c) an indication of those parameters to Op, if any, that are subject to update. (In case (c), the RETURNS clause is replaced by an UPDATES clause. See UPDATES.)
Example: The invocation signature for the first version of the MOVE operator as defined in the examples under RETURN is:
( ELLIPSE , RECTANGLE ) RETURNS ELLIPSE
reversible decomposition Replacing a relvar R by a set of relvars R1, R2, ..., Rn in such a way that it’s guaranteed that R can be derived from R1, R2, ..., Rn. Nonloss decomposition, q.v., is an important special case.
rewrite rule An identity, q.v., in the sense of the fourth definition of that term. As the name suggests, a rewrite rule of the form x ≡ y allows any expression that contains an occurrence of x to be rewritten, without changing the meaning, as an expression that contains an occurrence of y (parenthesized if necessary) in its place but is otherwise unchanged. See expression transformation; query rewrite; substitution.
RFNF Redundancy free normal form.
right associativity See left associativity.
right identity Let Op be a dyadic operator, and assume for definiteness that it’s expressed in infix style. If there exists a value i such that v Op i is equal to v for all possible values v, then i is the right identity, or right identity value, with respect to Op. See also identity (fifth definition); left identity.
Examples: Every identity, q.v., is necessarily a right identity in particular (and also a left identity, of course). As for an example of a right identity that’s not also a left identity, let Op be the regular arithmetic subtraction operator; then, since v−0 is equal to v for all numbers v whereas 0−v is not, 0 is a right identity but not a left identity with respect to that operator.
ring (mathematics) A formal system that obeys all of The Laws of Algebra, q.v., except that the commutative, identity, and inverse laws don’t necessarily apply to multiplication (“*”). Note: Every ring is a commutative group, q.v., with respect to addition (“+”).
Rissanen’s Theorem Let relvar R, with heading H, have projections R1 and R2, with headings H1 and H2, respectively; further, let H1 and H2 both be proper subsets of H, and let their union be equal to H; then R1 and R2 are independent projections (q.v.) if and only if (a) their common attributes constitute a superkey for at least one of them and (b) every FD that holds in R is a logical consequence (in accordance with Armstrong’s axioms, q.v.) of those that hold in at least one of them.
RM/T An extended form of the relational model, due to Codd, with the explicit goal of capturing more of the meaning of the data than the relational model per se is capable of. The name RM/T is an abbreviation for Relational Model / Tasmania (so called because Codd first described it at a conference in Tasmania). RM/T includes a variety of “semantic” constructs (e.g., E- and P-relations, which are meant to represent entities and properties, respectively, together with operators for operating on such relations). RM/T as such has never been implemented in a commercial product (in fact it couldn’t be, since Codd’s only paper on the topic—“Extending the Database Relational Model to Capture More Meaning,” ACM TODS 4, No. 4—fails to specify it adequately), but its ideas can be useful as an aid in conventional database design. Note: E- and P-relations are better referred to as E- and P-relvars, but the term relvar wasn’t in widespread use in 1979, when Codd first defined RM/T.
RM/V1 See RM/V2.
RM/V2 Codd spent much of the late 1980s revising and extending his original relational model, which he referred to as “the Relational Model Version 1” or RM/V1, to produce “the Relational Model Version 2” or RM/V2. However, definitions in the present dictionary are (as noted in the introduction) intended to conform to the relational model as defined by The Third Manifesto; as a consequence, therefore, they don’t always agree with Codd’s RM/V1 or (especially) RM/V2 definitions. For details of these latter, see Codd’s book The Relational Model for Database Management Version 2 (Addison-Wesley, 1990).
row 1. SQL analog of either a tuple value or a tuple variable, as the context demands. 2. More generally, a picture of a tuple (on paper, for example). See also cell; column; table.
row ID An implementation construct (typically though not necessarily some kind of pointer, q.v.); sometimes rather inappropriately called a tuple ID. Note: In some commercial products, row IDs are exposed to the user—usually, and unfortunately, in such a way as to violate either The Information Principle or The Principle of Interchangeability or both. Also, don’t confuse row IDs with surrogates, q.v. Here are some differences between the two constructs:
First, row IDs identify rows, while surrogates identify entities (note the logical difference here).
Second, row IDs have performance connotations, but surrogates don’t.
Third, row IDs are usually (though not always, as already indicated) hidden from the user, but surrogates mustn’t be, because of The Information Principle.
In a nutshell: Surrogates are a model concept; row IDs are an implementation concept.
row subquery See subquery.
rule of inference See inference rule.
RVA Relation valued attribute.
safe expression A relational expression that would be guaranteed to evaluate to a finite result even if the underlying domains (types) were infinite. In practice, various rules are imposed to ensure that unsafe expressions can never occur. An example of an unsafe expression, if it were permitted, would be one denoting the set of all tuples with heading the same as that of relvar S that don’t currently appear in that relvar (in other words, a request for the complement of the relation that’s the current value of relvar S). Note: As should be obvious, it’s generally desirable for various pragmatic reasons to prohibit unsafe expressions even if all domains are in fact finite (as of course they are in real systems).
satisfy 1. (Integrity constraint) Let C be a constraint that refers to variables V1, V2, ..., Vn (n ≥ 0) and no others. Then values v1, v2, ..., vn (in that order) satisfy C if and only if evaluating C with V1 equal to v1, V2 equal to v2, ..., and Vn equal to vn yields TRUE. Note: An analogous definition applies to business rules also, q.v. Contrast hold; violate. 2. (Predicate) Let P be a predicate, with parameters P1, P2, ..., Pn (n ≥ 0) and no others. Then values v1, v2, ..., vn (in that order) satisfy P if and only if substituting v1 for P1, v2 for P2, ..., and vn for Pn produces a proposition that evaluates to TRUE.
scalar 1. (Of a type, attribute, value, or variable) Having no user visible component parts. The term is often used as a noun as an abbreviation for scalar value specifically. See also encapsulated. 2. (Of a read-only operator) Returning a scalar result. Note that in order to have a type at all—i.e., to be considered either scalar or nonscalar—an operator must be read-only; update operators return nothing, and the concept of scalar vs. nonscalar thus doesn’t apply. Note: Support for the scalar type BOOLEAN is required by the relational model, and support for scalar values and scalar attributes—at least ones of that particular type—is therefore required also. Scalar variables aren’t required by the relational model, but they’ll almost be certainly needed in the external environment; for example, such a variable will certainly be needed to serve as the target for retrieval of the value of some scalar attribute from some tuple of some relation. An analogous remark applies to scalar operators also. Note too that there’s no such thing as “absolute scalarness” (or “absolute atomicity,” as it’s sometimes called)—the concept is necessarily somewhat relative, and indeed somewhat informal to boot. For example, a phone number might be perceived equally well as an “atomic” (i.e., scalar) value or as a tuple value consisting of country code, area code, and local number (and a database design involving phone numbers ought to be capable of supporting both perceptions). Consider also the case of TABLE_DUM, which is clearly a relation and yet (like a scalar, but unlike all other relations) has no user visible component parts. Note finally that because the term is indeed informal, the relational model nowhere depends on the scalar vs. nonscalar distinction in any formal sense.
scalar attribute See scalar.
scalar operator See scalar.
scalar selector See selector.
scalar subquery See subquery.
scalar type A type having no user visible component parts (contrast possible representation; tuple type; relation type). See type for further discussion.
scalar value See scalar; value.
scalar variable See scalar; variable.
scale (Of a numeric type) Loosely, the size of the increment from one value of the type to the next, where “next” means next in sequence according to the natural ordering for the type in question. For example, consider the SQL type NUMERIC(5,2). Values of that type are decimal numbers with precision (q.v.) five and scale factor (q.v.) two, whence the scale as such is 0.01, or in other words one hundredth. Thus, values of that type are precisely the following:
-999.99 , -999.98 , ... , -000.01 , 000.00 , 000.01 , ... , 999.99
See precision and scale factor for further discussion.
By way of another example, let EVEN_INTEGER be a user defined type with the intuitively obvious semantics. The scale for that type is two.
Note: Actually there’s some confusion in the literature over the term scale. To be specific, some writers and some languages use it to mean the scale factor (at least as that term is defined in this dictionary); others use it to refer to the distinction between fixed and floating point; and still others use it as a synonym for base or radix. Finally, note that (a) the term can also sensibly be used (and indeed is used) of certain nonnumeric types, such as dates and times; (b) scales are usually assumed to be linear but don’t have to be (e.g., consider the well known example of the Richter Scale, where the scale is logarithmic to base ten). Caveat lector.
scale factor (Of a numeric type; for reasons of simplicity, however, the following explanation is couched in terms of decimal types only) Consider the SQL type NUMERIC(p,q). Values of that type are decimal numbers with precision (q.v.) p and scale factor q. The scale factor specifies the position of the assumed decimal point in the string of digits denoting any given value of the type in question, as follows: A nonnegative scale factor q means the decimal point is assumed to be q decimal places to the left of the rightmost decimal digit of such a string of digits; a negative scale factor −q means the decimal point is assumed to be q decimal places to the right of the rightmost decimal digit of such a string of digits. In other words, if v is a value of type NUMERIC(p,q), then v can be thought of in terms of a p-digit integer, n say; however, that p-digit integer n must be interpreted as denoting the value v = n * (10-q). The multiplier 10-q is the scale defined by the scale factor q (e.g., for NUMERIC(5,2), the scale is 0.01, or in other words one hundredth). Observe that, by definition, every value of the type is evenly divisible by the scale (i.e., dividing the value in question by the scale always leaves a zero remainder). See precision and scale for further discussion.
schema / scheme 1. Terms sometimes used to mean either the logical design of a database or the collection of data definitions that represents that design. (The term schema, at least, is also frequently used in the context of conceptual design, q.v. See conceptual schema.) 2. Shorthand for a relation schema (or relation scheme) specifically, q.v., if the context demands.
Second Great Blunder Mixing pointers and relations (see pointer). Note that committing The First Great Blunder, q.v., seems to lead inevitably to committing the second as well; however, it’s possible to commit the second without committing the first (witness SQL).
second normal form Relvar R is in second normal form, 2NF, if and only if every nonkey attribute A of R is such that the set {A} is irreducibly dependent on every key of R—equivalently, if and only if, for every nontrivial FD X → Y that holds in R, (a) X is a superkey or (b) Y is a subkey or (c) X isn’t a subkey. Every 2NF relvar is in 1NF (as indeed every relvar is, of course). Note: Although being in 2NF clearly doesn’t preclude being in the next higher normal form (3NF) as well, the term 2NF is often used loosely to refer to a relvar that’s in 2NF and not in 3NF. Also, second normal form as such is no longer very important (BCNF, 5NF—or perhaps ETNF—and 6NF being the normal forms of most practical significance); we mention it here mainly for historical reasons.
Example: As noted under Boyce/Codd normal form, with the normal forms it’s often more instructive to show a counterexample rather than an example per se. Suppose for the sake of the example, therefore, that relvar SP has an additional attribute CITY, representing the city of the applicable supplier. This revised version of SP is subject to the FD {SNO} → {CITY} and is therefore not in 2NF (because CITY is a nonkey attribute, yet {CITY} isn’t irreducibly dependent on the key {SNO,PNO}; equivalently, because {SNO} isn’t a superkey, is a subkey, and {CITY} isn’t a subkey).
second order logic A form of predicate logic in which the sets over which logic variables range are allowed to be sets of predicates. Contrast first order logic.
Example: Consider the well known principle of mathematical induction, limited here for simplicity to its application to monadic predicates p whose sole parameter i is of type nonnegative integer. That principle can be stated in somewhat stilted English as follows: For all such predicates p, if (a) p(0) is true and if also (b) for all i (i ≥ 0), if p(i) is true then p(i+1) is true, then (c) p(n) is true for all n (n ≥ 0). In symbols:
FORALL p ( ( p(0) AND FORALL i ( p(i) IMPLIES p(i+1) ) )
IMPLIES FORALL n ( p(n) ) )
In this example the variables i and n range over nonnegative integers, but the variable p ranges over predicates—specifically, monadic predicates whose sole parameter is of type nonnegative integer—and is thus a predicate variable, q.v. The expression overall is thus second order.
SELECT expression In SQL, the vast majority of table expressions—i.e., expressions that denote a table—involve, in sequence as written, a SELECT clause (with an optional DISTINCT specification), a FROM clause, an optional WHERE clause, an optional GROUP BY clause, and an optional HAVING clause. Such expressions are known generically, and loosely, as SELECT − FROM − WHERE − GROUP BY − HAVING expressions, or more simply as SELECT − FROM − WHERE expressions, or more simply still as just SELECT expressions. Unfortunately, it’s impossible in a dictionary of this nature to give a complete and accurate definition of this SQL construct, owing in part to the complicated interdependencies that exist among the various clauses. For example, the syntax and the semantics of the SELECT clause both depend on whether or not there’s an accompanying GROUP BY clause, among other things. However, the following (extremely loose!) conceptual algorithm gives a rough idea of the overall semantics:
(FROM) Form the cartesian product of the tables specified in the FROM clause.
(WHERE) Discard rows from that product that fail to satisfy the boolean expression in the WHERE clause.
(GROUP BY) Partition the remaining rows into groups in accordance with values of the columns specified in the GROUP BY clause.
(HAVING) Discard groups from that partitioning that fail to satisfy the boolean expression in the HAVING clause.
(SELECT) From each remaining group, derive a row by applying whatever combination of summarize, extend, rename, and “project” operations is specified by the SELECT and GROUP BY clauses taken in combination.
(DISTINCT) Discard redundant duplicate rows from the result of the previous step.
Observe in particular that the clauses aren’t evaluated in the sequence in which they’re written (which is in fact the sequence in which they must be written).
Here are some additional factors that would need to be taken into account in any more precise explanation:
The fact that the various clauses can all contain subqueries, q.v.
The fact that certain subqueries can be “correlated”
The fact that certain correlated subqueries can be “lateral”
The fact that certain fundamental operations, including equality (“=”) in particular, aren’t fully defined (in some cases, in fact, they’re explicitly defined to be what the SQL standard calls “possibly nondeterministic,” q.v., meaning their results aren’t fully predictable)
The fact that there are numerous differences between SQL tables and their relational counterparts (see table for a partial list of such differences)
Further explanation of such matters is beyond the scope of this dictionary.
Note: Let exp1 and exp2 be SELECT expressions. Then SQL permits various unions, intersections, and differences to be formulated in terms of exp1 and exp2. Again, however, the details are beyond the scope of this dictionary.
selection (relational algebra) See restriction.
selector An operator—read-only by definition—for selecting, or specifying, an arbitrary value of a given type; not to be confused with either relational restriction (which is, perhaps rather unfortunately, sometimes called selection), q.v., or the SELECT operation of SQL. (For a loose characterization of this latter, see SELECT expression.) Note that, by definition, the type in question must be nonempty. Every such type, tuple and relation types included, has at least one associated selector (see below for further details). Let T be such a type, and let S be a selector for type T. Then (a) every value of type T is producible by means of some invocation of S in which the argument expressions are all literals, and (b) every successful invocation of S produces a value of type T. To be more specific:
If T is a user defined scalar type, definition of a possrep PR for T causes automatic definition of a corresponding selector operator (with the same name as PR, in Tutorial D), which allows a value of type T to be selected by supplying a value for each component of PR.
If T is a system defined scalar type, one or more possreps might or might not be defined for it. If one is defined (PR, say), then it behaves exactly as if T were user defined and PR were a corresponding possrep. If no possrep is defined, then at least one selector operator for type T must be provided by the system. In this latter case, however, invocations of such a selector will probably be limited to being simple literals (see further discussion of literals below).
If T is a tuple type, the (unique) corresponding selector operator allows a tuple of type T to be selected by supplying a value for each attribute of T.
If T is a relation type, the (unique) corresponding selector operator allows a relation of type T to be selected by specifying a set of tuple expressions, each denoting one tuple of the relation in question. In other words, a relation selector invocation effectively just enumerates the relevant tuples.
Note: If S is a selector for type T, then T is said to be the target type for S. Note further that, ultimately, the only way any expression can ever yield a value of type T is via invocation of some selector for that type T. In fact, the selector notion is essentially a generalization of the familiar concept of a literal (as noted under literal, all literals are selector invocations, but some selector invocations aren’t literals; to be specific, a selector invocation is a literal if and only if all of its argument expressions are literals in turn).
Examples: First some scalar examples. User defined types: The expressions SNO('S3') and SNO('S5') are selector invocations for type SNO; the expression PNO('P1') and PNO('P2') are selector invocations for type PNO; and the expressions QTY(150) and QTY(500) are selector invocations for type QTY. System defined types: The expressions 'S3', 'P1', and 150 are selector invocations for types CHAR, CHAR, and INTEGER, respectively (assumed for the sake of the example to be system defined types).
Here now are a couple of selector invocations for tuple type TUPLE {SNO SNO, PNO PNO, QTY QTY}:
TUPLE { SNO SNO('S3') , PNO PNO('P1') , QTY QTY(150) }
TUPLE { SNO SNO('S5') , PNO PNO('P2') , QTY QTY(500) }
And here’s a selector invocation for relation type RELATION {SNO SNO, PNO PNO, QTY QTY}:
RELATION
{ TUPLE { SNO SNO('S3') , PNO PNO('P1') , QTY QTY(150) ,
TUPLE { SNO SNO('S5') , PNO PNO('P2') , QTY QTY(500) } }
Note: All of the foregoing examples are actually literals, since their argument expressions are all literals in turn. Here by contrast are some selector invocations that aren’t literals. Let X, Y, and Z be variables of declared types CHAR, CHAR, and INTEGER, respectively. Then (a) the expressions SNO(X), PNO(Y), and QTY(Z) are selector invocations for types SNO, PNO, and QTY, respectively; (b) the expression TUPLE {SNO SNO(X), PNO PNO(Y), QTY QTY(Z)} is a selector invocation for tuple type TUPLE {SNO SNO, PNO PNO, QTY QTY}; and (c) the expression RELATION {ts}, where ts is the tuple selector invocation just shown, is a selector invocation for relation type RELATION {SNO SNO, PNO PNO, QTY QTY}.
self-referencing relvar A relvar R with a foreign key that references some key of R itself (hence giving rise to a referential cycle, q.v., of length one). Database designs involving such relvars are best avoided if possible; in fact, as noted under referential cycle, designs involving referential cycles of any length are best avoided if possible.
semantic (Of a language, sentence, etc.) Pertaining to meaning. Contrast lexical; syntactic.
semantic modeling A rather vague term, never very precisely defined, having to do with the representation of meaning within a database design. Other terms used in the same or a related sense include conceptual modeling; data modeling; entity modeling; entity/relationship modeling; and object modeling. See also RM/T.
semantic optimization Using database integrity constraints as a basis for transforming relational expressions, usually with the aim of improving performance. See expression transformation; optimizer.
Example: Consider the query
P WHERE CITY = 'London' AND COLOR = COLOR('Red')
Suppose relvar P is subject to the constraint that all parts in London must be red. Then the query can clearly be transformed—possibly “manually” by the user, preferably automatically by the optimizer, q.v.—into the following simpler one:
P WHERE CITY = 'London'
Moreover, if the original query had requested blue parts instead of red ones, the optimizer might be able to determine that the result is empty without actually having to execute the query at all.
semantic override Same as domain check override.
semantic transformation The kind of expression transformation performed in connection with semantic optimization, q.v.
semantics (Plural noun treated as singular) Meaning; pertaining to meaning. Note: Semantics is often confused with syntax (especially in nontechnical contexts, where for some reason the term is frequently used with pejorative intent). But when we say something, semantics is what we mean, while syntax is merely how we say it. Semantics is more important than syntax, at least from a logical or conceptual point of view.
semidifference Let relations r1 and r2 be joinable, q.v. Then (and only then) the expression r1 NOT MATCHING r2 denotes the semidifference between r1 and r2 (in that order), and it returns the relation denoted by the expression r1 MINUS (r1 MATCHING r2).
Examples: The expression
S NOT MATCHING SP
represents the query “Get suppliers who supply no parts at all,” and the expression
S { CITY } NOT MATCHING P { CITY }
represents the query “Get supplier cities that aren’t also part cities.” Note: As this latter example indicates, r1 NOT MATCHING r2 degenerates to r1 MINUS r2 when r1 and r2 are of the same type. In other words, as noted under difference, regular relational difference is actually just a special case of semidifference.
SEMIJOIN Same as (but in Tutorial D superseded by) MATCHING.
semijoin Let relations r1 and r2 be joinable, q.v., and let r1 have attributes called A1, A2, ..., An (and no others). Then (and only then) the expression r1 MATCHING r2 denotes the semijoin of r1 with r2 (in that order), and it returns the relation denoted by the expression (r1 JOIN r2) {A1,A2, ...,An}. Note that r1 MATCHING r2 and r2 MATCHING r1 aren’t equivalent, in general (i.e., MATCHING is noncommutative).
Example: The expression
S MATCHING SP
represents the query “Get suppliers who supply at least one part.”
SEMIMINUS Same as (but in Tutorial D superseded by) NOT MATCHING.
sentence (Logic) A statement (see logical system).
SEQUEL An acronym for “Structured English Query Language” (the original name for SQL).
set A collection of objects, called elements, with the property that given an arbitrary object x, it can be determined whether or not x appears in the collection (see set membership). An example is the collection {a,b,c}, which can equivalently be written as, e.g., {b,a,c}, since sets have no ordering to their elements (nor do they contain any duplicate elements). Every subset or superset of a set is itself a set. See also class (first definition). Note: There’s a logical difference—actually a difference in type—between an element x and the singleton set {x} that contains just that element x. Thus, a database language needs to provide both (a) an operator for extracting the single tuple from a relation of cardinality one and (b) an operator for extracting the single attribute value from a tuple of degree one (see tuple extractor and attribute extractor, respectively). Note too that the inverse functionality—in effect, building up a tuple from specified attribute values and building up a relation from specified tuple values—is provided by the appropriate tuple and relation selectors, respectively (see tuple selector; relation selector).
SET_ operator An OO operator (a “mutator,” q.v.) that assigns a specified value to a specified property—typically represented by an instance variable, q.v.—of a specified object. It might be thought of, very loosely, as the OO counterpart to a THE_ pseudovariable, except that (a) THE_ pseudovariables are defined in terms of possrep components, not “object properties,” and (b) THE_ operator invocations can be nested, whereas the same might not be true of SET_ operator invocations. Contrast GET_ operator.
set algebra See boolean algebra (second definition).
set function Strictly, a function (i.e., a read-only operator) that takes sets as input and produces a set as output. Unfortunately, the term is mainly used in practice to refer to an aggregate operator (q.v.) or a summary (q.v.) or both; such usage is doubly deprecated, because in both cases (a) the input is typically not a set but a bag and (b) the output is typically not a set but a scalar. Note: SQL in particular uses the term to refer to a summary (but not to an aggregate operator, because—as noted under aggregate operator—SQL doesn’t support aggregate operators, as such, at all).
set inclusion Set s1 includes set s2 (“s1 ⊇ s2”) if and only if it is a superset of s2; set s2 is included in set s1 (“s2 ⊆ s1”) if and only if it is a subset of s1. Set s1 is equal to set s2 (“s1 = s2”) if and only if each includes the other. Observe that every set is included in itself, also that every set includes the empty set. Observe also that the term set inclusion is usually taken, a trifle arbitrarily, to refer to the operator “⊆” specifically, not the operator “⊇”. Note: The term containment is sometimes used as a synonym for inclusion in the present sense, but this usage is generally deprecated—better to say of a set that it contains its elements (see containment) but includes its subsets.
set level The operators of the relational model are all set level, in the sense that they take entire relations or relvars or both as operands and either produce entire relations as results or update entire relvars. (Relation level would be a better term.) One important implication of this state of affairs, for update operators in particular, is that applicable compensatory actions must not be done until all of the explicitly requested updating has been done; another is that database integrity checking must not be done until all of the updating has been done (including applicable compensatory actions, if any). Contrast tuple level.
set membership (Of an element) The property of appearing in some given set; the operation of testing for that property. Set membership is usually denoted by the symbol “∊” (sometimes pronounced epsilon, because it’s a variant form of the lowercase Greek letter epsilon—i.e., “ε”—which is the first letter of the Greek word meaning “is”); thus, the boolean expression x ∊ s—which is logically equivalent to the expression {x} ⊆ s—returns TRUE if and only if element x does in fact appear in set s. Note: The expression x ∊ s is logically equivalent to the expression s ∍ x, where the symbol “∍” denotes containment (the inverse of membership, in effect).
set operator See boolean algebra (second definition); see also difference (set theory), intersection (set theory), set function, and so on; not to be confused with either SET_ operators (q.v.) or the SET operator of SQL, which is basically just assignment (e.g., SET A = B is SQL syntax for the assignment A := B).
set theory A branch of mathematics, closely related to logic, that deals with the nature of sets. Among other things, it formalizes the concept of a set in terms of certain axioms, such as the axiom of extension, q.v.
sharding A physical database design technique (see horizontal decomposition).
Sheffer stroke See NAND.
SI prefixes Part of the International System of Units, the standard for scientific measurements of all kinds (SI is an abbreviation for Système Internationale d’Unités). The following table lists SI prefixes and their abbreviations and meanings:
yotta |
Y |
10 to the power 24 |
zetta |
Z |
10 to the power 21 |
exa |
E |
10 to the power 18 |
peta |
P |
10 to the power 15 |
tera |
T |
10 to the power 12 |
giga |
G |
10 to the power 9 |
mega |
M |
10 to the power 6 |
kilo |
k |
10 to the power 3 |
hecto |
h |
10 to the power 2 |
deca |
da |
10 to the power 1 |
yocto |
z |
10 to the power −24 |
zepto |
z |
10 to the power −21 |
atto |
a |
10 to the power −18 |
femto |
f |
10 to the power −15 |
pico |
p |
10 to the power −12 |
nano |
n |
10 to the power −9 |
micro |
µ |
10 to the power −6 |
milli |
m |
10 to the power −3 |
centi |
c |
10 to the power −2 |
deci |
d |
10 to the power −1 |
Note: In the computing world, the prefixes yotta through kilo are used a little differently. To be specific, they’re usually interpreted in terms of powers of 2, not 10, as indicated here:
yotta |
Y |
2 to the power 80 |
zetta |
Z |
2 to the power 70 |
exa |
E |
2 to the power 60 |
peta |
P |
2 to the power 50 |
tera |
T |
2 to the power 40 |
giga |
G |
2 to the power 30 |
mega |
M |
2 to the power 20 |
kilo |
K |
2 to the power 10 |
For example, one kilobyte (1KB—the prefix kilo is usually abbreviated K, not k, in the computing world) is 1,024 bytes, not 1,000 bytes. Note in particular that a gigabyte is a billion bytes, roughly speaking (the abbreviation BB is sometimes used instead of GB; similarly, the abbreviation XB is sometimes used instead of EB). Note also that—contrary to popular belief—the prefix giga is properly pronounced with a soft initial g (as in gigantic).
signature See invocation signature; specification signature.
simple attribute An attribute, q.v. Contrast composite attribute.
simple key A key that’s not composite.
simple predicate A predicate that involves no connectives. Contrast compound predicate.
simple proposition A proposition that involves no connectives. Contrast compound proposition.
single arrow Same as arrow (see functional dependency). Contrast double arrow.
single assignment See multiple assignment.
single-relvar constraint Term sometimes used to mean a database constraint that mentions exactly one relvar. Contrast multirelvar constraint; single-variable constraint. Note: As noted under multirelvar constraint, the difference between single- and multirelvar constraints is more a matter of pragma than logic, thanks to The Principle of Interchangeability (q.v.) among other things.
Examples: The key constraints for relvars S, SP, and P; also constraints C1 and C2 from the examples under database constraint.
single-tuple constraint Same as tuple constraint.
single-variable constraint Term sometimes used to mean a database constraint that involves exactly one range variable if expressed in tuple calculus form. Contrast multivariable constraint; single-relvar constraint.
Examples: Constraints C1 and C2 from the examples under database constraint are single-relvar constraints that are also single-variable constraints. By contrast, the key constraints for relvars S, SP, and P are single-relvar constraints but not single-variable constraints, because it takes two range variables to express the fact that (e.g.) values of {SNO} within relvar S are unique.
singleton set A set of cardinality one.
sixth normal form Relvar R is in sixth normal form, 6NF, if and only if it can’t be nonloss decomposed at all, other than trivially—i.e., if and only if the only JDs to which it’s subject are trivial ones. Equivalently, relvar R is in 6NF if and only if it’s in 5NF, is of degree n, and has no key of degree less than n−1. Observe, therefore, that (a) 6NF is the ultimate normal form with respect to normalization as conventionally understood; (b) every 6NF relvar is in 5NF; (c) 6NF relvars are irreducible, q.v. Note: Part III of this dictionary gives an extended definition of this particular normal form.
Examples: 1. Relvar SP is in 6NF, since it can’t be nonloss decomposed at all other than trivially. (In other words, SP is irreducible. Observe that it’s certainly in 5NF; it’s of degree three; and it has no key of degree less than two.) By contrast, relvars S and P aren’t in 6NF, because they can each be nonloss decomposed, nontrivially, into two or more projections (in several different ways, in fact). 2. Let relvar PLUS have attributes A, B, and C, all of declared type INTEGER, and let the corresponding relvar predicate be
A + B = C
Then relvar PLUS has three distinct keys: {A,B}, {B,C}, and {C,A}. But PLUS is in 6NF, since it’s certainly in 5NF, it’s of degree three, and it has no key of degree less than two.
SKNF Superkey normal form.
skolem constant By definition, the expression EXISTS x (p(x)) is logically equivalent to the expression p(v) for some unknown value v; that is, the original expression effectively asserts that some such value v exists, even if we don’t know what it is. That value v is a skolem constant. See also skolem function.
skolem function By definition, the expression FORALL y (EXISTS x (q(y,x))) is logically equivalent to the expression FORALL y (q(y,f(y))) for some unknown function f of the universally quantified variable y; that is, the original expression effectively asserts that some such function f exists, even if we don’t know what it is. That function f is a skolem function. Together, skolem constants, q.v., and skolem functions (which are named for the logician T. A. Skolem) provide a basis for systematically eliminating existential quantifiers from an arbitrary logical expression, thereby making that expression more amenable to subsequent formal manipulation. Further details are beyond the scope of this dictionary.
Small Divide One of the many relational division operators that have been defined over the years (see division). Let relations r1, r2, and r3 be such that (a) r1 and r3 are joinable, q.v., and so are r3 and r2; (b) the common attributes of r1 and r3 are called A1, A2, ..., Am (m ≥ 0); (c) the common attributes of r3 and r2 are called B1, B2, ..., Bn (n ≥ 0); and finally (d) no Ai has the same name as any Bj (1 ≤ i ≤ m, 1 ≤ j ≤ n). Then (and only then) the expression r1 DIVIDEBY r2 PER (r3)—where r1 is the dividend, r2 is the divisor, and r3 is the “mediator”—denotes the division of r1 by r2 according to r3, and it returns the relation r denoted by the expression r1 NOT MATCHING ((r1{A1,A2,...,Am} JOIN r2{B1,B2,...,Bn}) NOT MATCHING r3). In other words, relation r has heading the same as that of r1 and body defined as follows: Tuple t appears in that body if and only if it appears in r1 and a tuple <a1,a2,..,am,b1,b2,...,bn>, with a1 equal to the A1 value in t, a2 equal to the A2 value in t, ..., and am equal to the Am value in t appears in r3{A1,A2,...,Am,B1,B2,...,Bn} for all tuples <b1,b2,...,bn> appearing in r2{B1,B2,...,Bn}. Contrast Great Divide.
Example: The expression S DIVIDEBY P PER (SP) yields a relation with heading the same as that of relvar S and body consisting of all possible tuples <sno,sn,st,sc> from relvar S such that supplier sno supplies all parts mentioned in relvar P. (Given the sample values of Fig. 1, the result contains just the tuple for supplier S1.) The expression is logically equivalent to this one:
S NOT MATCHING ( ( S { SNO } JOIN P { PNO } ) NOT MATCHING SP )
An equivalent tuple calculus formulation is:
SX RANGES OVER { S } ;
SPX RANGES OVER { SP } ;
PX RANGES OVER { P } ;
{ SX } WHERE
FORALL PX ( EXISTS SPX ( SPX.SNO = SX.SNO AND SPX.PNO = PX.PNO ) )
An equivalent Tutorial D formulation is:
S WHERE ( !!SP ) { PNO } = P { PNO }
(The expression !!SP here is an image relation reference, q.v.)
snapshot A derived relvar that’s real, not virtual (contrast view). The value of a given snapshot at a given time is the result of evaluating a certain relational expression—the snapshot defining expression, specified when the snapshot itself is defined—at some time prior to the time in question: to be precise, at the most recent “refresh time” (see the explanation immediately following). The snapshot is “refreshed” (i.e., the snapshot defining expression is reevaluated and the result assigned as the new current value of the snapshot) on explicit user request or, more usually, when some prescribed event occurs, such as the passing of a certain interval of time. Note: The snapshot defining expression must mention at least one relvar, for otherwise the snapshot wouldn’t be a variable as such. However, the only kind of update permitted on that variable is the periodic refreshing already described; in other words, snapshots are “almost” read-only.
Example: The following statement is a hypothetical Tutorial D definition for a snapshot called LSS (it’s hypothetical because Tutorial D doesn’t actually support snapshots at the time of writing):
VAR LSS SNAPSHOT ( S WHERE CITY = 'London' )
REFRESH EVERY DAY ;
The relation that’s the value of snapshot LSS at any given time is equal to the value of the snapshot defining expression S WHERE CITY = 'London' as it was at most 24 hours prior to the time in question.
SNF Same as SKNF.
SOME Keyword sometimes used as an alternative spelling for the aggregate operator OR (see aggregate operator).
sort/merge join A join implementation technique.
sorted logic A form of logic—nothing to do with sorting in the usual computing sense—in which the values or “individual constants,” q.v., that are the subject of the logic are divided up into “sorts,” or in other words types. Note: Most logic texts pay little or no attention to the notion of types; instead, they deal with unsorted logic, which effectively means they assume that everything is of the same type (often referred to as the universe, or domain, of discourse).
soundness (Of a formal system) A formal system is sound if and only if, given a set s of sentences of the system, no sentence not implied by those in s can be derived using the rules of inference of that system (i.e., all theorems are tautologies). See also completeness.
source (Assignment) See assignment.
source relvar For the general meaning, see inclusion dependency. In the foreign key context in particular, the term is sometimes used as a synonym for a referencing relvar, q.v.
source tuple Term sometimes used in the foreign key context as a synonym for a referencing tuple, q.v.
specification signature (Without inheritance) Let Op be an operator; then Op has a specification signature, denoting that operator as perceived by the user. The specification signature consists of the combination of (a) the operator name Op, (b) the declared types of the parameters to Op, and either (c) the declared type of the result, if any, of executing Op or (d) an indication of those parameters to Op, if any, that are subject to update. See also invocation signature.
Examples:
Consider the read-only version of the operator DOUBLE from the examples under argument. The specification signature for that operator is:
DOUBLE ( INTEGER ) RETURNS INTEGER
For the read-only version of the operator MOVE (see the first example under RETURN), the specification signature is:
MOVE ( ELLIPSE , RECTANGLE ) RETURNS ELLIPSE
For the update version of the operator MOVE (see the second example under RETURN), the specification signature is the same as in the previous case, except that the specification RETURNS ELLIPSE is replaced by an indication of the fact that the first parameter is subject to update.
Caveat: Some writers give definitions of the term (specification signature, that is) that differ slightly from the one just given; for example, it’s sometimes taken to include parameter names. In fact, most writers fail to distinguish explicitly between specification and invocation signatures (q.v.) anyway, referring to them both as just signatures. (The distinction is important if inheritance is supported but not perhaps otherwise; nevertheless, use of the unqualified term signature is probably best avoided unless there’s no risk of ambiguity.) Note finally that if two operators are distinct but have the same name—see overloading—their specification signatures must differ in either the number or the declared types of their parameters or both (possibly in the declared types of their results as well, if any).
SQL The best known attempt (unfortunately a seriously flawed one) to realize the abstract ideas of the relational model in concrete syntactic form. The name SQL—the official pronunciation, and the one adhered to in this dictionary, is “ess cue ell,” though the pronunciation “sequel” is often heard (see SEQUEL)—was originally an abbreviation for Structured Query Language. In its standard incarnation, however, the name is just a name and isn’t an abbreviation for anything at all. Note: The version of the standard current at the time of writing is SQL:2011 (so called because it was ratified in 2011), and all remarks concerning SQL in this dictionary are intended to apply to that version specifically (see SQL standard). However, every SQL product supports its own SQL dialect, and the remarks in question might thus not apply to all products.
SQL standard The “official” definition of SQL. The full reference is as follows:
International Organization for Standardization (ISO), Database Language SQL, Document ISO/IEC 9075:2011 (2011)
As this citation indicates, the standard is indeed an international or “ISO” standard, not just (as many seem to think) an American or “ANSI” standard (ANSI being an abbreviation for the American National Standards Institute). Note: The SQL standard has been through several versions, or editions, over the years. The first two appeared in 1986 and 1989 and were known as SQL/86 and SQL/89, respectively. The version current at the time of writing is SQL:2011; the previous version was SQL:2003, the one before that was SQL:1999, and the one before that was SQL:1992.
star join A join implementation technique, primarily intended for use in connection with star schemas, q.v.
star schema A database design, or the collection of data definitions representing such a design, intended primarily to support so called online analytical processing (OLAP). Note: In principle, there’s no reason why a star schema should be distinguishable in any way from a conventional and properly normalized relational design. In practice, however, star schemas typically (and deliberately) violate numerous relational design principles, including the principles of normalization in particular. Such violations are deemed necessary, or at least desirable, in order to overcome certain deficiencies in existing SQL product implementations, but they’re to be deplored nevertheless. (Of course, the same goes for the products in question.) Further details are beyond the scope of this dictionary.
state (Of a variable) Slightly deprecated (because logically unnecessary) term used to refer to the actual—i.e., current—or some possible value of the variable in question; frequently used to refer to the current or some possible value of a database variable in particular, q.v.
state constraint A database constraint, q.v., that isn’t a transition constraint, q.v.
state variable See instance variable.
statement 1. (Logic) A proposition (or, perhaps more precisely, the representation of a proposition in some concrete syntactic form). 2. (Programming languages) A construct that causes some action to occur, such as defining or updating a variable or changing the flow of control. Contrast expression. Note: Throughout this dictionary, the term statement should be understood in the programming language sense, unless the context demands otherwise.
Examples (second definition only): See the examples under DELETE, INSERT, and elsewhere. Note that (as in many other languages) statements in Tutorial D terminate in a semicolon.
stored procedure A subroutine, possibly parameterized; in other words, the implementation code for some operator. Note: Like the term encapsulated, q.v., the term stored procedure has unfortunately come to mean something in practice that mixes model and implementation considerations. From the point of view of the model, a stored procedure is basically, as just stated, nothing more than an operator (or the implementation code for such an operator, rather). In practice, however, stored procedures have a number of properties that make them much more important than they would be if they were just operators as such (although the first two of the following properties will probably apply to operators in general, at least if the operators in question are system defined). First, they’re compiled separately and can be shared by distinct applications. Second, their compiled code is, typically, physically stored at the site at which the data itself is physically stored, with obvious performance benefits. Third, they’re often used to provide shared functionality that ought to be provided by the DBMS but isn’t (integrity checking is a good example here, given the state of today’s SQL implementations). See also triggered procedure.
strong typing A programming language is strongly typed if and only if every expression of the language is of a known type and type errors are always detected (preferably though not necessarily at compile time). The relational model explicitly requires strong typing for relational expressions.
structured type (SQL) See user defined type (SQL).
subexpression An expression nested inside another such.
subject to Variable V is subject to constraint C—equivalently, constraint C holds for variable V—if and only if every value v that can ever be assigned to V satisfies C.
subject to update Let Op be an update operator that, when invoked, updates the argument corresponding to parameter P. Then parameter P is said to be subject to update (and any argument corresponding to P must be a variable specifically). See UPDATES.
Example: See the second example under RETURN.
subkey Loosely, a subset of a key. More precisely, let X be a subset of the heading of relvar R; then X is a subkey for, or of, R if and only if there exists some key K for R such that K ⊇ X.
Examples: The subkeys for relvar SP are {SNO,PNO}, {SNO}, {PNO}, and { }. Note that the empty set { } is necessarily a subkey for all possible relvars R.
subquery If a relational expression is regarded as a “query”—slightly deprecated usage—then a relational expression nested inside another such is a “subquery.”
Note: The term subquery is given a rather more specific meaning in SQL, where it refers to an expression that denotes a table—usually but not invariably a SELECT expression specifically, q.v.—enclosed in parentheses. Note, however, that not all parenthesized expressions in SQL that denote an SQL table are subqueries in the SQL sense. Note too that the SQL notion of a subquery is considerably more complex than the foregoing definition might suggest. In particular, if t is the table denoted by SQL subquery sq, then (a) if table t contains just one row r, then sq can be used in certain contexts as if it denoted r as such (in which case sq is acting as a “row subquery”); (b) if table t contains just one row r and just one column C, and therefore contains just a single value v, then sq can be used in certain contexts as if it denoted v as such (in which case sq is acting as a “scalar subquery,” despite the fact that the value v isn’t limited to being a scalar value specifically); and (c) if sq is neither a row subquery nor a scalar subquery, then it’s a “table subquery.” There’s a lot more that could be said here, too, but further details are beyond the scope of this dictionary.
subrelation Let relations r1 and r2 be such that r2 is derived from r1 by eliminating a subset of the attributes (via projection) or eliminating a subset of the tuples (via restriction) or both. Then relation r2 is a subrelation of relation r1. The term isn’t much used.
subschema / subscheme Terms occasionally used to mean either (a) the (possibly restructured) logical design of some subset of a given database as it’s perceived by some given user or (b) the collection of data definitions representing such a design.
subset Set s2 is a subset of set s1 (“s2 ⊆ s1”) if and only if every element of s2 is also an element of s1. Observe that every set is a subset of both itself and the universal set, also that the empty set is a subset of every set. Contrast proper subset.
substitution 1. (Logic) Let x be an expression containing an occurrence of y as a subexpression; let y′ be logically equivalent to y; and let x′ be the expression obtained by substituting y′ (parenthesized if necessary) for the occurrence of y in question in x. Then x and x′ are logically equivalent. 2. (View implementation) A technique for implementing operations on views, according to which references to view V are effectively replaced by the view defining expression for V (contrast view materialization). 3. (Operator invocation) Replacing a parameter by an argument. Note that this last definition applies to predicate instantiation (q.v.) in particular.
Examples: 1. (Logic) See the example under expression transformation. 2. (View implementation) See the second example under pseudovariable reference. 3. (Operator invocation) See the examples under argument.
subtuple A subset of a tuple; hence, a tuple.
summarization Let relations r1 and r2 be such that the heading of r2 is some subset of that of r1. Let r2 have attributes called A1, A2, ..., An and no others (in particular, no attribute called B). Then (and only then) the expression SUMMARIZE r1 PER (r2) : {B := exp} denotes a summarization of r1 according to r2, and it returns the relation with heading {A1,A2,...,An,B} and body the set of all tuples t such that t is a tuple of r2, extended with a value b for attribute B. That value b is computed by evaluating the expression exp over all tuples of r1 that have the same value for attributes A1, A2, ..., An as t does. Note: The construct referred to as exp here will typically be an open expression, q.v.; in particular, it can, and in practice usually will, include at least one summary, q.v. See also WITH.
Examples: The following expression denotes a certain summarization of the current value of relvar SP “per” the current value of relvar S:
SUMMARIZE SP PER ( S { SNO } ) : { CT := COUNT ( ) }
COUNT( ) here is an example of a summary, q.v. Observe that it’s the PER relation, not the SUMMARIZE relation, that drives the operation—the result contains one tuple for each tuple in the PER relation, not one tuple for each tuple in the SUMMARIZE relation. Thus, the expression overall is logically equivalent to the following (arguably much clearer!) EXTEND invocation:
EXTEND S { SNO } : { CT := COUNT ( !!SP ) }
Note in particular that the COUNT summary in the SUMMARIZE invocation has been replaced by an invocation of the COUNT aggregate operator in this revised (i.e., EXTEND) version; note also that the argument expression in that aggregate operator invocation is an image relation reference, q.v. In both cases (i.e., regardless of whether the SUMMARIZE or the EXTEND formulation is used), the result is a relation of type RELATION {SNO SNO, CT INTEGER}, containing one tuple for each distinct SNO value currently appearing in relvar S (and no other tuples). Each such tuple contains the pertinent supplier number and a count of the number of times that supplier number currently appears in relvar SP. Given the sample values in Fig. 1, for example, the tuple for supplier S2 in the result has SNO value S2 and CT value two, and the tuple for supplier S5 has SNO value S5 and CT value zero.
By way of a second example, consider this expression:
SUMMARIZE SP PER ( SP { SNO } ) : { CT := COUNT ( ) }
The only difference between this example and the previous one is that the PER operand is specified as SP{SNO} instead of S{SNO}. The expression thus yields a relation of type RELATION {SNO SNO, CT INTEGER} as before, but with one tuple for each distinct SNO value currently appearing in relvar SP instead of relvar S. Given the sample values in Fig. 1, for example, the result contains no tuple for supplier S5. The expression overall is logically equivalent to the following EXTEND invocation:
EXTEND SP { SNO } : { CT := COUNT ( !!SP ) }
Note: Because the PER relation in the SUMMARIZE version of this second example actually is a projection of the SUMMARIZE relation (instead of merely having the same heading as such a projection), the expression overall can be simplified, slightly, to
SUMMARIZE SP BY { SNO } : { CT := COUNT ( ) }
The simplification consists in replacing the PER specification by a BY specification. More generally, the expression SUMMARIZE r1 BY {Ax,Ay,...,Az} : {B := exp} is logically equivalent to, and is defined to be shorthand for, the expression SUMMARIZE r1 PER (r1{Ax,Ay,...,Az}) : {B := exp}; in other words, the specification BY {Ax,Ay,...,Az} is shorthand for the specification PER (r1{Ax,Ay,...,Az}).
Tutorial D also allows the PER and BY specifications both to be omitted, in which case PER (TABLE_DEE) is assumed by default. Thus, the expression
SUMMARIZE SP : { CT := COUNT ( ) }
evaluates to a relation with heading {CT INTEGER} and body consisting of just one tuple, containing (given our usual sample values) just the value 12. Here’s an EXTEND equivalent:
EXTEND TABLE_DEE : { CT := COUNT ( SP ) }
Incidentally, it’s worth pointing out that any summarization involving COUNT is logically equivalent to one involving SUM instead. For example, the first SUMMARIZE example shown above is logically equivalent to the following:
SUMMARIZE SP PER ( S { SNO } ) : { CT := SUM ( 1 ) }
EXTEND equivalent:
EXTEND S { SNO } : { CT := SUM ( !!SP , 1 ) }
Here’s another example (“For each supplier, get the sum of distinct shipment quantities”):
SUMMARIZE SP { SNO , QTY } PER ( S { SNO } ) : { SDQ := SUM ( QTY ) }
EXTEND equivalent:
EXTEND S { SNO } : { SDQ := SUM ( ( !!SP ) { QTY } ) }
Here for interest is an SQL analog of this last example (note the need for a DISTINCT specification within the SQL SUM invocation, also the need to use SQL’s COALESCE operator in order to prevent the overall result from showing the sum for supplier S5 as null):
SELECT SNO , ( SELECT COALESCE ( SUM ( DISTINCT QTY ) , 0 )
FROM SP
WHERE SP.SNO = S.SNO ) AS SDQ
FROM S
Note the use of a scalar subquery in the SELECT clause here (see subquery).
Note: Tutorial D additionally supports a form of SUMMARIZE that allows two or more summarizations to be performed in parallel (“multiple SUMMARIZE”). Here’s an example:
SUMMARIZE SP BY { SNO } : { SQ := SUM ( QTY ) , AQ := AVG ( QTY ) }
EXTEND equivalent (a “multiple EXTEND”):
EXTEND SP : { SQ := SUM ( !!SP , QTY ) , AQ := AVG ( !!SP , QTY ) }
Alternatively (note the WITH specification within the braces here):
EXTEND SP : { WITH ( temp := !!SP ) :
SQ := SUM ( temp , QTY ) , AQ := AVG ( temp , QTY ) }
Note finally that (as the foregoing examples should be sufficient to suggest) any given SUMMARIZE invocation, multiple or otherwise, is always—in fact, is defined to be—logically equivalent to a certain EXTEND invocation. Partly for this reason, the SUMMARIZE operator per se is in the process of being dropped from Tutorial D. (The current version of the language does still support it, but the main reason it does so is for compatibility with earlier versions.)
SUMMARIZE See summarization.
summary A construct that can appear within an attribute assignment within a SUMMARIZE invocation wherever a literal of the appropriate type is allowed. Note that summaries aren’t aggregate operator invocations, though they might look rather like them (and indeed every aggregate operator does have a summary counterpart). An aggregate operator invocation is an expression (open or closed as the case may be). A summary, by contrast, is merely an operand to SUMMARIZE (speaking a trifle loosely); it has no meaning outside the context of SUMMARIZE, and in fact can’t appear outside that context. See summarization for further explanation.
superkey Loosely, a superset of a key; it has the uniqueness property of keys, but not necessarily the irreducibility property. More precisely, let X be a subset of the heading of relvar R; then X is a superkey for, or of, R if and only if no possible value for R contains two distinct tuples with the same value for X.
Examples: Relvar S has exactly eight superkeys (why?), of which {SNO} and {SNO,CITY} are two. Note that the heading of any given relvar R is necessarily a superkey for R. Note too that if SK is a superkey for relvar R, then the FD SK → X necessarily holds for all subsets X of the heading of R.
superkey constraint A constraint to the effect that a given subset of the heading of a given relvar is a superkey for that relvar. In Tutorial D, such a constraint is defined by means of a KEY specification within the pertinent relvar definition (see key constraint).
superkey normal form Relvar R is in superkey normal form (SKNF) if and only if every component of every irreducible JD that holds in R is a superkey for R. Every SKNF relvar is in RFNF.
Example: As noted under Boyce/Codd normal form, with the normal forms it’s often more instructive to show a counterexample rather than an example per se. Consider, therefore, relvar SPJ, with attributes SNO (supplier number), PNO (part number), and JNO (project number), and predicate Supplier SNO supplies part PNO to project JNO. Let that relvar have just two keys, {SNO,PNO} and {PNO,JNO}. Also, let the relvar be subject to the constraint that if (a) supplier sno supplies part pno and (b) part pno is supplied to project jno and (c) project jno is supplied by supplier sno, then (d) supplier sno supplies part pno to project jno. Then SPJ is equal to the join of its projections on {SNO,PNO}, {PNO,JNO}, and {JNO,SNO}—in other words, the JD
{ { SNO , PNO } , { PNO , JNO } , { JNO , SNO } }
holds in SPJ—and so that relvar can be nonloss decomposed into those three projections. However, since that JD has a component that’s not a superkey, relvar SPJ isn’t in SKNF, though it is in RFNF.
superset Set s1 is a superset of set s2 (“s1 ⊇ s2”) if and only if every element of s2 is also an element of s1. Observe that every set is a superset of both itself and the empty set, also that the universal set is a superset of every set. Contrast proper superset.
surjection / surjective mapping Terms used interchangeably to mean a mapping, or function, from set s1 to set s2 such that each element of s2 is the image of at least one element of s1 (in other words, a many to one correspondence, in the strict sense of that term). Also known as a surjective or “many to one onto” mapping.
Example: Let s1 and s2 be the set of all integers and the set of all nonnegative integers, respectively. Then the mapping from integers x to their absolute values ABS(x) is a surjection from s1 to (or onto) s2.
surrogate Abbreviation for surrogate key or surrogate key value, as the context demands.
surrogate key A single-attribute (i.e., simple) key with the property that its values serve solely as surrogates—hence the name—for the entities they’re supposed to stand for. In other words, those surrogate key values serve merely to represent the fact that the corresponding entities exist, and they carry absolutely no additional information or meaning. Contrast composite key; intelligent key; natural key; row ID.
symmetric difference Same as exclusive union.
symmetry 1. (Of a dyadic logical operator) Commutativity. 2. (Of a binary relation) The binary relation r is symmetric if and only if, for all x and y, if the tuple <x,y> appears in r, then so does the tuple <y,x>.
Examples (first definition only): The logical operator EQUIV (or “≡”); the equality operator “=”.
synonym 1. (Of an operator) An alternative name for an operator. For example, the operator that returns the angle at vertex B of a triangle ABC might reasonably be referred to equally well as either ABC or CBA. Similarly, the operator that returns the length of the side connecting vertices A and B might reasonably be referred to equally well as either AB or BA. 2. (Of a type) See type naming.
syntactic (Of a language, sentence, etc.) Pertaining to grammatical structure. Contrast lexical; semantic.
syntactic substitution A language design principle, according to which new operators are defined purely in terms of ones that already exist in the language in question (thus, invocations of such a new operator are effectively just shorthand for something that can already be expressed, possibly more longwindedly). Advantages of such an approach to language design include teachability, understandability, raising the level of abstraction, and the possibility of improved performance.
Examples: In Tutorial D, the operators MATCHING, q.v., and COMPOSE, q.v., are both defined in terms of join and projection (and nothing else).
syntax See semantics.
system defined See user defined.
system defined type A type defined by the system; i.e., one that’s built in. Contrast user defined type. Note: The system vs. user defined types distinction applies only to nongenerated types, not to types produced via invocation of some type generator. It follows that system defined types are always scalar, by definition.
Examples: Of the scalar types used in the suppliers-and-parts database, types CHAR (the set of all character strings) and INTEGER (the set of all integers) are system defined (or, at least, so we assume for the purposes of this dictionary). See also BOOLEAN.
system of logic See logic system.
table 1. SQL analog of either a relation or a relvar, as the context demands. Here are some of the major differences between tables in SQL and their relational counterparts: (a) SQL tables can contain duplicate rows; (b) SQL tables can contain nulls; (c) SQL tables have a left to right ordering to their columns; (d) SQL tables can have two or more columns with the same name; (e) SQL tables can have what are, in effect, columns with no name at all; (f) SQL tables—even ones in the database—can contain pointers; (g) SQL tables have no types. 2. More generally, a picture of a relation (on paper, for example). See also cell; column; row. Note: A confusion between relations and such tabular pictures probably accounts for the popular misconception that relations are “flat” or two-dimensional (see flat relation). While it’s obviously true that those pictures are two-dimensional, relations in general aren’t; rather, a relation of degree n is n-dimensional (q.v.), in the sense that its tuples correspond to points in some n-dimensional space (one dimension for each attribute of the relation in question).
table alias See alias.
TABLE_DEE and TABLE_DUM Two relation constants, preferably built in. TABLE_DEE is the unique relation with no attributes and exactly one tuple (necessarily the empty tuple); TABLE_DUM is the unique relation with no attributes and no tuples at all. They can be interpreted as TRUE (or yes) and FALSE (or no), respectively. (More precisely, the relation predicate for TABLE_DEE is any 0-place predicate that evaluates to TRUE, and the relation predicate for TABLE_DUM is any 0-place predicate that evaluates to FALSE.) Note: The names are perhaps not very well chosen, since TABLE_DEE and TABLE_DUM are precisely the two relations for which the popular understanding of a relation as a table most obviously breaks down.
table subquery See subquery.
tables and views / tables or views Phrases frequently appearing in SQL contexts that strongly suggest that views are somehow different from tables. But the whole point about views is that, in SQL terms, they are tables—just as, in mathematics, the whole point about a set that’s (e.g.) the union or intersection of two sets is that it is itself a set. In other words, views are supposed to “look and feel” just like base tables to the user (The Principle of Interchangeability, q.v., translated into SQL terms).
target (Assignment) See assignment.
target key See foreign key.
target relvar 1. (IND) For the general meaning, see inclusion dependency. In the foreign key context in particular, the term is sometimes used as a synonym for referenced relvar, q.v. 2. (Assignment) The relvar being updated in a relational assignment operation.
target tuple Term sometimes used in the foreign key context as a synonym for referenced tuple, q.v.
target type (Without inheritance) 1. Let S be a selector for type T; then the target type for an invocation of S is T. 2. In the CAST invocation CAST_AS_T (...), the target type is T.
tautology A predicate whose every possible invocation is guaranteed to yield TRUE, regardless of what arguments are substituted for its parameters. Contrast contradiction.
Examples: Let p1 be the predicate (actually a proposition) 2+2 = 4; let p2 be the predicate x = x, where x denotes an arbitrary integer; and let p3 be the predicate (p) OR (NOT(p)), where p denotes an arbitrary predicate. Then p1, p2, and p3 are all tautologies. Note that a tautology isn’t necessarily a proposition, even though (like some propositions) it does unequivocally evaluate to TRUE. For example, x = x isn’t a proposition; rather, it’s a monadic predicate (i.e., a predicate with exactly one parameter, viz., x).
TCLOSE See transitive closure.
THE_ operator Let T be a scalar type. Then definition of a possrep PR for T causes automatic definition of a set of operators of the form THE_A, THE_B, …, THE_C (Tutorial D syntax), where A, B, ..., C are the names of the components of PR. Let v be a value of type T, and let PR(v) denote the possible representation corresponding to PR for that value v. Then invoking THE_X on v (X = A, B, …, C) returns the value of the X component of PR(v).
Examples: Let type POINT have two distinct possreps called CARTESIAN and POLAR, respectively, with the obvious semantics:
POSSREP CARTESIAN { X RATIONAL , Y RATIONAL }
POSSREP POLAR { R RATIONAL , THETA RATIONAL }
Then the following are valid THE_ operator invocations for type POINT:
THE_X ( P )
/* denotes the X coordinate of the point in */
/* P, where P is a variable of type POINT */
THE_R ( P )
/* denotes the R coordinate of the point in P */
THE_Y ( exp )
/* denotes the Y coordinate of the point denoted */
/* by the expression exp (which is of type POINT) */
THE_ operator invocations can also be used as pseudovariable references (loosely, “THE_ pseudovariables”). For example:
THE_X ( P ) := Z ;
This example is shorthand for the following expanded version:
P := CARTESIAN ( Z , THE_Y ( P ) ) ;
THE_ operator invocations and THE_ pseudovariable references can both be nested. For example, let type LINESEG (“line segments”) be defined as follows (irrelevant details omitted):
TYPE LINESEG POSSREP { BEGIN POINT , END POINT } ;
Also, let LS be a variable of declared type LINESEG. Then the assignment
Z := THE_X ( THE_BEGIN ( LS ) ) ;
“gets” the X coordinate of the begin point of LS, and the assignment
THE_X ( THE_BEGIN ( LS ) ) := Z ;
“sets” the X coordinate of the begin point of LS. Here for interest is the expanded form of this latter assignment:
LS := LINESEG ( CARTESIAN ( Z , THE_Y ( THE_BEGIN ( LS ) ) ) ,
THE_END ( LS ) ) ;
THE_ pseudovariable See THE_ operator.
theorem Something that follows from given axioms according to given rules of inference (and is therefore true if the axioms are true and the inference rules valid). In the database context, tuples in derived relations can be regarded as theorems, because they represent propositions derived from the ones represented by tuples in the base relations. Theorems include axioms, q.v., as a degenerate special case. See proof.
Example: Given the sample values of Fig. 1, the relation denoted by the expression (S JOIN P) {SNO,PNO} contains the tuple <S1,P1> among others. That tuple can be regarded as a theorem; it represents the (true) proposition Supplier S1 and part P1 are in the same city, a “true fact” that can be inferred from the axioms represented by the pertinent tuples in the pertinent base relations.
theta join A relational operator whose invocation is logically equivalent to an expression of the form (r1 TIMES r2) WHERE A1 theta A2, where (a) A1 and A2 denote attributes (of the same type T) of r1 and r2, respectively, and (b) theta is any comparison operator that makes sense for values of type T (e.g., “=”, “>”, etc.). Note that r1 and r2 can’t have any attribute names in common, for otherwise the subexpression r1 TIMES r2 will be undefined. In particular, therefore, the attribute names A1 and A2 must obviously be different.
Example: The following expression represents the greater-than join (i.e., theta here is “>”) of suppliers and parts, in that order, on cities (note the renamings):
( ( S RENAME { CITY AS SC } )
TIMES
( P RENAME { CITY AS PC } ) ) WHERE SC > PC
We assume here that CHAR—the declared type of attribute CITY—is an ordered type (“>” on CHAR values presumably means “greater in alphabetic ordering”). Note that we could replace TIMES by JOIN in the foregoing expression without changing the meaning. Also, replacing “>” by “<” would yield a less-than join, while replacing it by “=” would yield an equijoin.
Note: Theta join was defined in one of Codd’s early papers as part of what is now known as Codd’s relational algebra, q.v. As a consequence, it has rather unfortunately received more attention than it really deserves. For one thing, the operator is, as the definition makes clear, nothing more than shorthand for a certain combination of more primitive operations (and a rather unimportant combination at that). More significant, the idea that many different kinds of join can be defined makes it look as if join as such—meaning natural join specifically—is just one of a family of similar operators; however, the fact is that join as such is a truly important operator (one of the most fundamental operators of all, in fact). Use of the term theta join is thus deprecated, slightly.
Third Manifesto A formal proposal for the future of data and database management systems. Like Codd’s original papers, the Manifesto can be seen as an abstract blueprint for the design of a DBMS and the language interface to such a DBMS. See the introduction to this dictionary for further explanation.
third normal form Relvar R is in third normal form, 3NF, if and only if, for every nontrivial FD X → Y that holds in R, (a) X is a superkey or (b) Y is a subkey. Every 3NF relvar is in 2NF. Note: Many of the “definitions” of 3NF in the literature are actually definitions of BCNF, q.v.; caveat lector. Also, although being in 3NF clearly doesn’t preclude being in some higher normal form as well, the term 3NF is often used loosely to refer to a relvar that’s in 3NF and not in (e.g.) BCNF. In any case, third normal form as such is no longer very important (BCNF, 5NF—or perhaps ETNF—and 6NF being the normal forms of most practical significance); we mention it here mainly for historical reasons.
Example: As noted under Boyce/Codd normal form, with the normal forms it’s often more instructive to show a counterexample rather than an example per se. Suppose, therefore, that relvar S is subject to the additional FD {CITY} → {STATUS}; i.e., the status for a given supplier is a function of that supplier’s location. (Of course, the sample value shown for that relvar in Fig. 1 doesn’t satisfy this FD; however, it would do so if we changed the status for supplier S2 from 10 to 30, so let’s suppose for the sake of the example that this change has in fact been made.) Since {CITY} isn’t a superkey and {STATUS} isn’t a subkey, this version of relvar S isn’t in 3NF (though it is in 2NF).
third truth value See three-valued logic.
three-valued logic A logic in which there’s a “third truth value” (usually called UNKNOWN) in addition to the conventional TRUE and FALSE; abbreviated 3VL. Note that tautologies in two-valued logic (2VL), q.v., aren’t necessarily tautologies in 3VL; likewise, contradictions in 2VL aren’t necessarily contradictions in 3VL. (By way of a simple example, let bx be a boolean expression, and consider the expression bx OR NOT (bx), which is certainly a tautology in 2VL but not in 3VL.) As a result, theorems that hold in 2VL don’t necessarily hold in 3VL, and expression transformations that are valid in 2VL aren’t necessarily valid in 3VL.
Note: As is well known, SQL’s support for nulls, q.v., is based on a three-valued logic (by contrast, the relational model is based on two-valued logic). However, that SQL support is logically flawed. For example, SQL treats UNKNOWN and null as identical, even though there’s a clear logical difference (q.v.) between the two—UNKNOWN is a value, while null isn’t a value at all but a “mark.” (This is just one of many logical errors in SQL’s 3VL support. Perhaps a more serious one is that the 3VL in question isn’t even fully defined! For example, the SQL standard nowhere defines the semantics of implication. Nor does it consider the question of whether SQL’s 3VL is truth functionally complete—that is, does SQL support all 27 monadic and 19,683 dyadic connectives of 3VL?)
time-varying relation Term used in Codd’s early papers to mean what we now call a relvar; the term is deprecated because relations are values and thus simply don’t “vary over time,” by definition (see value).
TIMES See cartesian product.
total database constraint See database constraint.
total function A partial function, q.v., in which every element x in the domain has an image y in the codomain; in other words, a function.
total ordering A special case of partial ordering, q.v. Let s be a set. Then a total ordering on s is a partial ordering, usually denoted “≤”, with the property that for all pairs of elements x and y of s, either x ≤ y or y ≤ x (or both, if and only if x and y are in fact the same element of s). Note: Given that the “=” operator and the NOT connective are both always available, it follows that all of the usual comparison operators “=”, “≠”, “<”, “≤”, “>”, and “≥” are available for all pairs of values in such a set s. Note also that the unqualified term ordering is usually taken to mean a total ordering specifically, unless the context demands otherwise. Contrast cyclic ordering.
Examples: See the examples under ordered type and ordinal type.
total relvar constraint See relvar constraint.
transaction A unit of recovery and concurrency; loosely, a unit of work. Transactions are all or nothing, in the sense that they either execute in their entirety or have no effect (other than returning a status code or equivalent, perhaps). Note: Transactions are often said to be a unit of integrity (or consistency) also. Since the relational model requires all integrity checking to be immediate, however, the unit of integrity as far as the relational model is concerned is the statement, not the transaction. See atomic statement; immediate checking.
transition The change in value of some variable (especially a database variable, q.v.) caused by a single updating statement. Contrast state.
transition constraint A database constraint, q.v., that limits the transitions a given database can validly make, as a consequence of a single updating statement, from one state to another. Contrast state constraint.
Example (“No supplier’s status must ever decrease”):
CONSTRAINT TRC1 IS_EMPTY (
( ( S { SNO , STATUS } ) JOIN
( ( S′ { SNO , STATUS } RENAME { STATUS AS STATUS′ } ) )
WHERE STATUS < STATUS′ ) ;
This formulation relies on a convention to the effect that a primed relvar name such as S′ refers to the value of the corresponding relvar as it was prior to the update under consideration.
Note: It’s worth pointing out that most if not all transition constraints can easily be subverted by performing two or more separate updates in sequence. Stating such constraints declaratively can be helpful in avoiding mistakes, therefore, but it provides little by way of protection against deliberate malicious action.
transitive closure Let r be a binary relation with attributes A and B, both of type T. Then (and only then) the expression TCLOSE (r) denotes the transitive closure of r, and it returns a relation r+ defined as follows: The tuple <a,b> appears in r+ if and only if it appears in r or there exists a value c of type T such that the tuple <a,c> appears in r and the tuple <c,b> appears in r+. (Observe that this is a recursive definition; observe too that r+ is indeed a transitive relation, as the name “transitive closure” suggests. See transitivity, second definition.) As the following pseudocode algorithm indicates, computing TCLOSE (r) conceptually involves repeated formation of the union of an intermediate result (computed on the previous iteration) and a new partial result (computed on the current iteration), until that union ceases to grow—in other words, until it reaches a fixed point or “fixpoint.”
r+ := r ;
do until r+ ceases to grow ;
r+ := WITH ( t1 := r+ RENAME { B AS C } ,
t2 := r RENAME { A AS C } ) :
r+ UNION ( t1 COMPOSE t2 ) ;
end do ;
See also recursive query.
transitive FD The FDs X → Y and Y → Z together imply the transitive FD X → Z (see Armstrong’s axioms); thus, if relvar R is subject to the FDs X → Y and Y → Z, it’s also subject to the transitive FD X → Z.
transitivity 1. (Of a dyadic logical operator) The dyadic logical operator Op, which we assume for definiteness is expressed in infix style, is transitive if and only if, for all x, y, and z, if x Op y and y Op z are both true, then so is x Op z. 2. (Of a binary relation) The binary relation r is transitive if and only if, for all x, y, and z, if the tuples <x,y> and <y,z> both appear in r, then so does the tuple <x,z>. 3. (Of FDs) See Armstrong’s axioms.
Examples (first definition only): The logical operator IMPLIES; the partial ordering operator “≤”. By way of a counterexample, consider the operator “father of”—“x father of y” and “y father of z” most certainly do not together imply “x father of z” (in fact, they imply “x not father of z,” loosely speaking).
TransRelationalTM Model A proprietary DBMS implementation technology, not based on conventional direct image techniques. A brief introduction to this technology can be found in Appendix A of the book An Introduction to Database Systems, by C. J. Date (8th edition, Addison-Wesley, 2004). A much more extensive description can be found in the book Go Faster! The TransRelationalTM Approach to DBMS Implementation, by C. J. Date (Ventus Publishing, 2002, 2011; free download available at bookboon.com).
TRC Tuple relational calculus.
trigger See triggered procedure.
triggered procedure Strictly, an action (the “triggered action”) to be performed if a specified event (the “triggering event”) occurs, though the term is often used loosely to refer to the triggered action and the triggering event taken in combination. (Moreover, that combination is often known more simply just as a trigger.) A triggered procedure can be thought of as a stored procedure, q.v., except that stored procedures must be explicitly invoked, whereas a triggered procedure is invoked automatically whenever the triggering event occurs. Apart from this difference, however, triggered procedures have many of the same properties, and are used for many of the same purposes, as stored procedures. No triggered procedures are prescribed by the relational model, but they aren’t necessarily proscribed either—though they would be if they were to violate either The Assignment Principle (q.v.) or the set level nature of the relational model, both of which in practice they’re quite likely to do.
Note: Triggered procedures, or triggers, shouldn’t be confused with compensatory actions, q.v., though they might be used to simulate such actions if the system provides no direct support for them. Here are some of the differences between the two concepts:
Details of the operation, and possibly even the existence, of triggers are typically concealed from the user. Such is not the case with compensatory actions.
There’s no notion with triggers that the system should be able to determine for itself what actions are to be performed (indeed, if it could, then triggers wouldn’t be necessary in the first place). With compensatory actions, by contrast, the system should be able (at least in some cases) to work out for itself just what actions are required.
Triggers can and usually do involve procedural code; in fact, as already noted, triggers can and often do violate the set level nature of the relational model.
trivial decomposition A nonloss decomposition, q.v., that’s performed on the basis of some trivial FD, JD, or MVD, q.v.
Examples: 1. Consider the suppliers relvar S. Let X, Y, and Z denote the sets of attributes {SNO,SNAME}, { } (the empty set), and {SNO,SNAME,STATUS,CITY}, respectively; then X, Y, and Z satisfy the requirements of Heath’s Theorem—in particular, the FD X → Y holds—and S can thus be nonloss decomposed into its projections on XY and XZ (i.e., on {SNO,SNAME} and {SNO,SNAME,STATUS,CITY}, respectively). However, X → Y here is a trivial FD, and the decomposition is trivial in turn. (Moreover, the projection on {SNO,SNAME} can now be discarded, since it clearly isn’t needed in the associated reconstruction process.)
2. Any relvar can be trivially decomposed into just its identity projection. To elaborate briefly: Let relvar R have heading H; then the trivial FD H → { } certainly holds in R, and so R can be nonloss decomposed into its projection on the entire heading H—i.e., the identity projection—and its projection on no attributes at all. (And this latter projection can now be discarded without loss.)
trivial dependency A dependency d that’s necessarily satisfied by every relation whose heading H is such that d is defined with respect to H; in other words, a dependency that can’t possibly be violated. From a logical point of view, such a dependency is implied by the empty set of constraints, and hence by every superset of that set also. In particular, therefore, we can certainly, and usefully (albeit perhaps a trifle counterintuitively), say that such trivial dependencies are implied by the pertinent keys or superkeys, and hence that such dependencies don’t cause the relvar in question to violate any of the usual normal forms. See trivial EQD; trivial FD; trivial IND; trivial JD; trivial MVD.
Example: The FD {CITY} → {CITY}, which holds in relvar S, is trivial—it can’t possibly be violated—and is therefore implied by the sole key {SNO} of that relvar. (In fact that same FD holds in relvar P as well, of course, as indeed it does in every possible relvar with a CITY attribute.)
trivial EQD An EQD that can’t possibly be violated. The EQD r1{X} = r2{X} is trivial if and only if one of r1 and r2 is a projection of the other (so long as the projection in question preserves all of the attributes of X, of course).
trivial FD An FD that can’t possibly be violated. The FD X → Y is trivial if and only if X ⊇ Y.
trivial IND An IND that can’t possibly be violated. The IND r1{X} ⊆ r2{X} is trivial if and only if one of r1 and r2 is a projection of the other (a projection that preserves all of the attributes of X, of course), in which case the IND is in fact an EQD.
trivial JD A JD that can’t possibly be violated. The JD {X1,X2,...,Xn} is trivial if and only if at least one of X1, X2, ..., Xn is equal to the pertinent heading.
trivial MVD An MVD that can’t possibly be violated. The MVD X →→ Y is trivial if and only if either X ⊇ Y or the set theory union of X and Y is equal to the pertinent heading. Observe that, given the pair of MVDs X →→ Y | Z, the MVD X →→ Y is trivial if and only if the MVD X →→ Z is trivial as well.
TRUE See BOOLEAN.
truth functional completeness A logical system is truth functionally complete if and only if it supports, directly or indirectly, all possible connectives—meaning, more specifically, that all possible connectives either (a) are supported explicitly or (b) can be expressed in terms of the ones that are supported explicitly (see primitive operator). Truth functional completeness is an extremely important property; a logical system without it would be like a system of arithmetic that had no support for certain operations, say the operation of addition. (And a database language based on such an incomplete logic would be one in which certain queries couldn’t be formulated; moreover, it might not even be clear, give such a language, which queries could be formulated and which ones couldn’t.) See also nVL.
truth functional equivalence Two logical expressions are truth functionally equivalent if and only if they evaluate to the same truth value. For example, the propositions “Earth has two moons” and “Venus has two moons” are truth functionally equivalent, since they both evaluate to FALSE. Note that logical equivalence (q.v.) implies truth functional equivalence, but the latter doesn’t imply the former. Note too that the connective EQUIV, q.v., denotes truth functional equivalence specifically.
truth table Let x be a propositional expression. Then the possible truth values of x can be defined by means of a truth table that shows, for each possible combination of truth values for the propositional variables mentioned in x, the truth value of the overall expression.
Example: Let x be the expression (p AND q) OR r, where p, q, and r are propositional variables. Then, using T and F to represent TRUE and FALSE, respectively, the possible truth values of x are defined by the following self-explanatory truth table:
p │ q │ r │ p AND q │ (p AND q) OR r
───┼───┼───┼─────────┼────────────────
T │ T │ T │ T │ T
T │ T │ F │ T │ T
T │ F │ T │ F │ T
T │ F │ F │ F │ F
F │ T │ T │ F │ T
F │ T │ F │ F │ F
F │ F │ T │ F │ T
F │ F │ F │ F │ F
By way of another example, the logical equivalence of the expressions NOT((p) AND (q)) and (NOT (p)) OR (NOT (q))—see De Morgan’s Laws—can readily be demonstrated by showing that the final columns of the respective truth tables are identical.
truth value In two-valued logic (2VL), either TRUE or FALSE; in other words, a boolean value. Note: Many-valued logics, q.v., support additional “truth values” over and above the conventional TRUE and FALSE. For example, three-valued logic (3VL) supports one such additional value, usually called UNKNOWN.
truth value of In logic, an operator (in symbols, “/.../”) that, given a logical expression, returns the truth value of that expression. For example, let the symbols x and y denote integers. Then the expression /x > y/ returns TRUE if the integer denoted by x is greater than that denoted by y and FALSE otherwise. Note that /TRUE/ and /FALSE/ return TRUE and FALSE, respectively. Note too that the logical expression p EQUIV q (or p ≡ q) means the same as /p/ = /q/; for example, the expression (Neptune is a planet) EQUIV (Mars has exactly two moons) means the same as the expression /(Neptune is a planet)/ = /(Mars has exactly two moons)/. Similarly, the logical expression p XOR q means the same as /p/ ≠ /q/. Note further that, in the computing literature at any rate, authors often write p = q when what they really mean is /p/ = /q/ (or p ≡ q); caveat lector.
truth valued expression A logical expression, q.v.
truth valued operator A read-only logical operator, q.v. (especially one of the connectives, q.v.).
TUPLE In Tutorial D, the name of the type generator for tuple types. Also used in Tutorial D to denote a tuple selector.
Examples: For examples showing the TUPLE type generator, see the examples under tuple type. Here by contrast is an example of a tuple selector invocation:
TUPLE { SNO SNO('S1') , SNAME NAME('Smith') , STATUS 20 , CITY 'London' }
tuple A tuple value, q.v. The term is short for n-tuple, q.v., and is usually pronounced to rhyme with “couple.”
tuple (mathematics) Given sets s1, s2, ..., sn, not necessarily distinct, t is an n-tuple (tuple for short) on those sets if and only if it’s an ordered collection of elements, the first of which is from s1, the second from s2, and so on. Set si is the ith domain of t (i = 1, 2, ..., n). Note: There are several important logical differences between a tuple in mathematics and its relational model counterpart. See relation (mathematics); tuple value.
tuple assignment (Without inheritance) An operation that assigns a tuple value of type T to a tuple variable of that same type T. See assignment.
tuple calculus A form of relational calculus in which the range variables range over relations and thus denote tuples from those relations. Tuple calculus and domain calculus, q.v., are logically equivalent, because for every expression of the former there’s a logically equivalent expression of the latter and vice versa (in fact, they’re both relationally complete, q.v.).
Example: Here’s a tuple calculus formulation of the query “Get supplier names for suppliers who supply at least one part” (see domain calculus for a domain calculus analog):
SX RANGES OVER { S } ;
SPX RANGES OVER { SP } ;
{ SX.SNAME } WHERE EXISTS SPX ( SPX.SNO = SX.SNO )
In stilted English: “Get names of suppliers SX where there exists a shipment SPX with the same supplier number as SX.”
tuple comparison (Without inheritance) A boolean expression of the form (tx1) theta (tx2), where tx1 and tx2 are tuple expressions of the same type T and theta is any comparison operator that makes sense for tuples (“=”, “≠”, “⊆”, etc., but definitely not “<” and “>”; tuples are sets and “<” and “>” are therefore explicitly not defined for tuples). Note: The parentheses enclosing tx1 and tx2 in the comparison might not be needed in practice.
tuple component An <attribute, attribute value> pair appearing in the tuple in question. Note that attributes in turn are defined to be <attribute name, type name> pairs, whence it follows that tuple components are of the form <<attribute name, type name>, attribute value>. However, other formalisms are possible; in particular, it would be possible to define a tuple component as an <attribute name, type name, attribute value> triple instead of an <attribute, attribute value> pair. (As a matter of fact, The Third Manifesto does exactly this.) Of course, the two definitions are clearly isomorphic.
Examples: The pairs <<SNO,SNO>,S1> and <<SNAME,NAME>,Smith> are both components of the supplier tuple for supplier S1 in Fig. 1. Note: In Tutorial D, tuple components are specified more simply as <attribute name, attribute value> pairs (not meant to be actual Tutorial D syntax). This simplified form is acceptable because the relational model requires attribute names to be unique within the pertinent heading, and those names thus effectively imply the corresponding type names.
tuple composition Let tuples t1 and t2 be such that attributes with the same name are of the same type and have the same value, and let their common attributes be called A1, A2, ..., An (n ≥ 0). Then (and only then) the expression t1 COMPOSE t2 denotes the tuple composition of t1 and t2, and it returns the tuple denoted by the expression (t1 UNION t2){ALL BUT A1, A2, ..., An}. Note: The operator as defined here is dyadic, but it would clearly be possible to define an n-adic version if desired (see composition).
tuple constant A tuple, especially one that’s named; not to be confused with a tuple literal, q.v.
tuple constant reference Syntactically, a tuple constant name, used to denote the value of that tuple constant. See also constant reference.
tuple constraint Slightly deprecated term sometimes used to refer to a relvar constraint of the form IS_EMPTY (R WHERE bx), where R is a relvar and bx is a restriction condition, q.v., on R (and can therefore be evaluated for an individual tuple, proposed for entry into R, by examining just that tuple in isolation). Note that a tuple constraint is indeed a constraint on a relvar and not on a tuplevar. (There aren’t any tuplevars in a relational database; a fortiori, therefore, there aren’t any “tuplevar constraints” either. See Information Principle.) Contrast multituple constraint.
Example: Constraints C1 and C2 from the examples under database constraint are both tuple constraints; constraint C3 is not.
tuple difference See tuple union.
tuple equality (Without inheritance) Equality of tuples; tuples t1 and t2 are equal—i.e., the tuple comparison t1 = t2 evaluates to TRUE—if and only if t1 and t2 are the very same tuple (implying among other things that t1 and t2 must certainly be of the same type). More specifically, let tuples t1 and t2 be of the same type, and let their attributes be called A1, A2, ..., An. Then t1 and t2 are equal if and only if, for all i (i = 1, 2, ..., n), the value v1 of Ai in t1 is equal to the value v2 of Ai in t2. Note: The importance of this concept can hardly be overstated, since so much in the relational model depends on it. For example, keys, foreign keys, and most if not all of the operators of relational algebra are defined in terms of it. Note in particular too that all 0-tuples are equal to one another, since in fact there’s only one such tuple.
tuple exclusive union See tuple union.
tuple expression An expression denoting a tuple. Tuple selector invocations (and hence tuple literals), tuplecon and tuplevar references, and read-only tuple operator invocations are all special cases.
tuple extension 1. (First form) Let tuple t not have an attribute called A. Then (and only then) the expression EXTEND t : {A := exp} returns a tuple identical to t except that it has an additional attribute called A, with a value that’s computed by evaluating the expression exp on t. 2. (Second form) Let tuple t have an attribute called A. Then (and only then) the expression EXTEND t : {A := exp} returns a tuple identical to t except that the value for attribute A is replaced by a value that’s computed by evaluating the expression exp on t.
Examples: By way of an example to illustrate the first definition, let t be some tuple in the current value of relvar P, and consider the following expression:
EXTEND t : { GMWT := WEIGHT * 454 }
This expression yields a tuple just like t, except that it has an additional attribute GMWT (“gram weight”) whose value is 454 times the WEIGHT value in that same tuple. Note that WEIGHT * 454 in this example is an open expression—it relies on context for its meaning.
Here now is an example to illustrate the second definition:
EXTEND t : { WEIGHT := 2 * WEIGHT }
This expression yields a tuple just like t, except that the WEIGHT value is doubled (note that the subexpression 2 * WEIGHT is an open expression).
Note: Tutorial D additionally supports a form of tuple EXTEND that allows two or more attribute assignments to be carried out in parallel (“multiple tuple EXTEND”). Here’s an example:
EXTEND t : { GMWT := WEIGHT * 454 ,
WEIGHT := 2 * WEIGHT ,
NC := 'Oslo' }
This example illustrates both meanings of the term tuple extension.
Note finally that the second form of tuple EXTEND can be defined in terms of the first. For example, the expression
EXTEND t : { WEIGHT := 2 * WEIGHT }
can be regarded as shorthand for an expression of the following form:
( ( EXTEND t : { temp := 2 * WEIGHT } ) { ALL BUT WEIGHT } )
RENAME { temp AS WEIGHT }
tuple extractor An operator for extracting the single tuple from a specified relation of cardinality one.
Example: The following expression extracts the supplier tuple for supplier S1 from the current value of relvar S:
TUPLE FROM ( S WHERE SNO = SNO('S1') )
A run-time error will occur if the TUPLE FROM argument doesn’t have cardinality exactly one.
Note: SQL has no explicit counterpart to Tutorial D’s TUPLE FROM; instead, it relies on certain coercions to perform the analogous function. For example, consider the following SQL expression:
SELECT SNO
FROM S
WHERE ( CITY , STATUS ) =
( SELECT CITY , STATUS
FROM S
WHERE SNO = SNO('S1') )
Overall, this expression returns supplier numbers for suppliers with the same city and status as supplier S1. Note that it contains a subquery (“SELECT CITY, STATUS ...”). By definition, that subquery evaluates to a table; however, the table in question contains just one row—it’s what SQL calls a “row subquery,” q.v.—and, precisely because it appears in the context of a “row comparison,” that table is then coerced to the single row it contains. For further discussion, refer to the book SQL and Relational Theory: How to Write Accurate SQL Code, by C. J. Date (3rd edition, O’Reilly Media Inc., 2015).
tuple forcing JD Let J be a JD that holds in relvar R. Then J is tuple forcing with respect to R if and only if it requires that if certain tuples t1, t2, ..., tn appear in R at some given time, then some other tuple t, distinct from each of t1, t2, ..., tn, is forced to appear in R as well at that time. Note: Not all JDs are tuple forcing (though they’re all tuple generating, q.v.; that is, all tuple forcing JDs are tuple generating JDs, but the converse is not the case). In fact, a JD is tuple forcing (with respect to the pertinent relvar R) if and only if it’s (a) nontrivial, (b) not implied by any FD of R, and (c) not implied by the keys of R.
TUPLE FROM Tutorial D syntax for a tuple extractor, q.v.
tuple generating dependency An expression of the form {t1,t2,…,tn} / t; it can be read as “If tuples t1, t2, ..., tn appear (in some given relvar at some given time), then tuple t must appear (in that same relvar at that same time).” Tuples t1, t2, …, tn are the premises of the dependency and tuple t is the conclusion. Note: JDs in particular are tuple generating dependencies (not the only possible kind, but the only kind considered in this dictionary). See also tuple forcing JD.
tuple ID See row ID.
tuple intersection See tuple union.
tuple join See tuple union. Note that this dictionary frequently appeals, informally, to the notion of “joining tuples”—see, for example, the example under many to one join.
tuple level An operator is tuple level if it takes individual tuples or tuplevars or both as operands and either produces a tuple as a result or updates a tuple variable. There are no tuple level operators in the relational model as such (except as noted under database variable), but such operators are likely to be needed in the external environment in order to support, e.g., extraction of some tuple from some relation. (By contrast, SQL in particular does support certain tuple level operations—specifically, DELETE and UPDATE operations via some cursor, or in other words so called “positioned” deletes and updates—that aren’t just part of the external environment but are supposed to affect the database directly. The operators in question thus constitute a serious departure from the relational model.) Note: The foregoing is not to say that, e.g., an operator that “updates an individual tuple” couldn’t be defined in a relational language like Tutorial D, but (a) invoking such an operator would have to be understood, logically, as asking for a set of tuples to be updated where the set in question simply happens to have cardinality one, and (b) such an invocation will necessarily fail if certain multivariable constraints, q.v., happen to be in effect.
tuple literal A literal that denotes a tuple.
Examples: See the examples under literal.
tuple operator An operator that takes either tuples or tuplevars or both as operands and either returns a tuple or updates a tuplevar (see tuple level).
tuple product See tuple union.
tuple projection Let tuple t have attributes called A1, A2, ..., An (and possibly others). Then the expression t{A1,A2,...,An} denotes the projection of t on {A1, A2, ..., An}, and it returns the tuple obtained by removing from t all components other than those corresponding to attributes A1, A2, ..., An.
Example: Let t be some tuple in relvar S. Then the expression t{STATUS,CITY} yields a tuple of type TUPLE {STATUS INTEGER, CITY CHAR}, containing just the STATUS and CITY components from that tuple t.
tuple relational calculus Tuple calculus, q.v.
tuple renaming Let tuple t have an attribute called A and no attribute called B. Then (and only then) the expression t RENAME {A AS B} denotes an attribute renaming on t, and it returns the tuple that’s identical to t except that attribute A in that tuple is renamed B.
Example: Let t be some tuple from relvar P. Then the expression
t RENAME { WEIGHT AS WT }
yields a tuple just like t, except that attribute WEIGHT is renamed WT.
Note: Tutorial D additionally supports a form of tuple RENAME that allows two or more separate tuple renamings to be carried out in parallel (“multiple tuple RENAME”). See renaming for further explanation.
tuple selector Let T be a tuple type; then the corresponding selector is an operator that allows a tuple of type T to be selected by supplying a value for each attribute of T. More precisely, let T be a tuple type, and let the corresponding heading be H; then there’s exactly one selector, S say, for that type T, and S is such that (a) the sole argument to any given invocation of S is a set of values, one such value for each attribute in H; (b) every tuple of type T is producible by means of some invocation of S in which those attribute values are all represented by literals; and (c) every successful invocation of S produces a tuple of type T.
Examples: See the examples under selector and elsewhere. Of course, those examples illustrate, not incidentally, the syntax used for tuple selectors in Tutorial D specifically; other syntactic styles might be possible, but they must be logically equivalent to the Tutorial D style.
tuple symmetric difference See tuple union.
tuple type Let H be a heading; then (and only then) TUPLE H denotes a tuple type—in fact, the sole tuple type—with the same degree and same attributes as H. Note: The following lightly edited extract from The Third Manifesto elaborates on the foregoing tuple type naming convention:
When we say “the name of [a certain tuple type] shall be TUPLE H,” we do not mean to prescribe specific syntax. The Manifesto does not prescribe syntax. Rather, what we mean is that the type in question shall have a name that does both of the following, no more and no less: First, it shall specify that the type is indeed a tuple type; second, it shall specify the pertinent heading. Syntax of the form “TUPLE H” satisfies these requirements, and we therefore use it as a convenient shorthand; however, all appearances of that syntax throughout this Manifesto are to be interpreted in the light of these remarks.
Examples: Consider the following Tutorial D definition for a tuplevar called TS:
VAR TS TUPLE { SNO SNO , SNAME NAME , STATUS INTEGER , CITY CHAR } ;
This definition includes an invocation of the TUPLE type generator (syntactically, everything from the keyword TUPLE to the closing brace following the keyword CHAR, inclusive), which specifies the type of the variable being defined. To be specific, the keyword TUPLE shows it’s a tuple type, while the commalist, enclosed in braces, of <attribute name, type name> pairs defines the pertinent heading. Thus, the type of the tuple variable, or tuplevar, TS is exactly as follows (the result of the specified invocation):
TUPLE { SNO SNO , SNAME NAME , STATUS INTEGER , CITY CHAR }
By way of a second example, the following (corresponding to a certain projection of tuplevar TS) also denotes a certain tuple type:
TUPLE { CITY CHAR , SNAME NAME }
Note that Tutorial D provides nothing analogous to a TYPE statement, q.v., for defining tuple types. Instead, such types can be defined only by invoking the tuple type generator, q.v., as illustrated in the foregoing examples.
tuple type generator See TUPLE; see also type generator.
tuple type inference The process of determining the type of the value denoted by a given tuple expression. Note that this process is completely specified by the rules defining the types of the results of the various tuple operators, q.v.
tuple union Let tuples t1 and t2 be such that attributes with the same name are of the same type and have the same value. Then (and only then) the expression t1 UNION t2 denotes the union of t1 and t2, and it returns the tuple that’s the set theory union of t1 and t2. (This operation could obviously be generalized to apply to any number of tuples.) Note: Tuple union might reasonably be called tuple join; analogously, the special case in which the given tuples t1 and t2 have no attribute names in common might reasonably be called tuple product. Also, it would clearly be possible to define tuple intersection, difference, and exclusive union (or symmetric difference) operators if desired.
Example: Let t1 and t2 be a tuple from the current value of relvar S and relvar SP, respectively, and let t1 and t2 have the same SNO component (and hence the same SNO value in particular). Then the expression t1 UNION t2 yields a tuple of type TUPLE {SNO SNO, SNAME NAME, STATUS INTEGER, CITY CHAR, PNO PNO, QTY QTY}, with components as in t1 or t2 or both, as applicable.
tuple unwrapping Let tuple t have attributes called A1, A2, ..., Am, and BT (and no others), and let attribute BT be tuple valued and have attributes called B1, B2, ..., Bn (and no others); further, let no Ai have the same name as any Bj (1 ≤ i ≤ m, 1 ≤ j ≤ n). Then (and only then) the expression t UNWRAP BT denotes the unwrapping of t on BT, and it returns the tuple denoted by the expression (EXTEND t : {B1 := B1 FROM BT, B2 := B2 FROM BT, ..., Bn := Bn FROM BT}){ALL BUT BT}.
Example: Let t be a tuple from the current value of relvar SP, and let tw be the tuple resulting from the expression
t WRAP { PNO , QTY } AS PQ_TUP
(see tuple wrapping). Then the expression
tw UNWRAP PQ_TUP
yields t.
tuple value Very loosely, a row (value). More precisely, let H be a heading, and let t be a set of pairs <<A,T>,v>, called components (q.v.), obtained from H by attaching to each attribute <A,T> in H some value v of type T, called the attribute value in t for attribute A. Then (and only then) t is a tuple value (tuple for short) with heading H and the same degree and attributes as H. Every subset of a tuple value is itself a tuple value. Note: Other formalisms are possible; in particular, it would be possible to define a tuple as a set of <attribute name, type name, attribute value> triples instead of <attribute, attribute value> pairs (as a matter of fact, The Third Manifesto does exactly this). Of course, the two definitions are clearly isomorphic. Either way, tuples as defined in the relational model differ in certain important respects from the mathematical construct of the same name. In particular, tuples in mathematics typically don’t have named attributes; instead, their attributes are identified by ordinal position, left to right. See tuple (mathematics).
tuple valued attribute An attribute whose type is some tuple type. Values of such an attribute are tuples of the specified type. Note: If a relvar has a tuple valued attribute, that fact in and of itself doesn’t constitute a violation of any particular level of normalization (not even first); however, such attributes are usually contraindicated in database design, at least in base relvars, because they necessarily imply some structural asymmetry and thereby give rise to asymmetry (and hence complexity) in queries, constraints, and updates as well. See also tuple unwrapping; tuple wrapping.
Examples: See the examples under wrapping and tuple wrapping.
tuple variable Very loosely, a row (variable); more precisely, a variable whose type is some tuple type. Let tuple variable V be of type T; then V has the same heading (and therefore attributes) and degree as type T does. Note: Tuple variables aren’t required by the relational model as such (except as noted under database variable), but they’re likely to be needed in the external environment (e.g., such a variable will be needed to serve as the target for retrieval of some tuple from some relation). See also variable and (for a discussion of the fact that a database is really a tuple variable) database variable.
tuple wrapping Let tuple t have attributes called A1, A2, ..., Am, B1, B2, ..., Bn (and no others), and let BT be an attribute name that’s distinct from that of every attribute Ai (1 ≤ i ≤ m). Then (and only then) the expression t WRAP {B1,B2,...,Bn} AS BT denotes the wrapping of t on {B1,B2,...,Bn}, and it returns the tuple denoted by the expression (EXTEND t : {BT := TUPLE {B1 B1,B2 B2,...,Bn Bn}}) {A1,A2,...,Am,BT}.
Example: Let t be the tuple for supplier S1 and part P1 from the current value of relvar SP. Then the expression
t WRAP { PNO , QTY } AS PQ_TUP
yields a tuple tw of type TUPLE {SNO SNO, PQ_TUP TUPLE {PNO PNO, QTY QTY}}, with SNO value S1 and PQ_TUP value a tuple with PNO value P1 and QTY value 300. (Attribute PQ_TUP here is an example of a tuple valued attribute.)
tuplecon A tuple constant, q.v.
tuplevar A tuple variable, q.v.
tuplevar reference Syntactically, a tuplevar name, used to denote either the tuplevar as such or the value of that tuplevar, as the context demands.
Tutorial D A particular D, q.v., designed primarily to serve as a teaching vehicle (see the introduction to this dictionary). Note that the name Tutorial D, like the name D, is always set in boldface.
TVA Tuple valued attribute.
two-valued logic Conventional propositional or predicate logic, in which there are just two truth values, TRUE and FALSE; abbreviated 2VL. The relational model is based on 2VL.
TYPE The Tutorial D operator for defining (user defined) scalar types. For example, here’s a sample type definition for a user defined scalar type called POINT (irrelevant details omitted):
TYPE POINT ...
POSSREP CARTESIAN { X RATIONAL , Y RATIONAL
CONSTRAINT ( X↑2 + Y↑2 ) ≤ 10000 } ;
Type POINT denotes geometric points in two-dimensional space. Points have a possible representation called CARTESIAN, with components X and Y (both of declared type RATIONAL); also, they’re subject to a constraint—imposed somewhat arbitrarily, and purely for the sake of the example—that says, in effect, that the only points we’re interested in are those that lie on or inside a circle with center the origin and radius of length 100 (the symbol “↑” denotes exponentiation). See CONSTRAINT for further explanation.
Note: As explained under possible representation, possible representations (“possreps”) are always named; by default, however, the possrep name is the same as that of the corresponding type. Here, for example, is a slightly simpler version of the foregoing definition for type POINT:
TYPE POINT ...
POSSREP { X RATIONAL , Y RATIONAL
CONSTRAINT ( X↑2 + Y↑2 ) ≤ 10000 } ;
Now the possrep is called POINT instead of CARTESIAN. Most of the examples involving user defined types elsewhere in this dictionary make use of this default option.
As for tuple and relation types, there aren’t any explicit “define tuple type” or “define relation type” operators in Tutorial D. Rather, the availability of a given scalar type tacitly implies the availability of an unbounded number of tuple and relation types with names of the form TUPLE H or RELATION H (as applicable)—where (a) TUPLE and RELATION are type generators, q.v.; (b) H is a heading, consisting of a possibly empty commalist of attributes enclosed in braces; and (c) each attribute in turn consists of an attribute name followed by a type name. (This definition is recursive, of course.) Such a tuple or relation type can be specified as the type for (e.g.) some variable by simply specifying the appropriate type name as part of the definition of the variable in question. Here are some examples of such types:
TUPLE { E ELLIPSE , R RECTANGLE }
RELATION { E ELLIPSE , AB TUPLE { A ELLIPSE , B RECTANGLE } }
TUPLE { E ELLIPSE , AB RELATION { A RECTANGLE , B ELLIPSE } }
RELATION { E ELLIPSE , AB RELATION { A RECTANGLE , B ELLIPSE } }
And so on.
type A named (and in practice finite) set of values; not to be confused with the internal or physical representation of the values in question, which is an implementation issue. Every value, every variable, every attribute, every read-only operator, every parameter, and every expression is of some type. Types can be either scalar or nonscalar (in particular, they can be tuple or relation types); as a consequence, attributes of relations in particular can also be either scalar or nonscalar. Types can also be either system defined (i.e., built in) or user defined. They can also be generated (see type generator). See also domain; type naming. Note: A type isn’t a value, nor is it a variable; in particular, relation values and relation variables aren’t types. Equating types and either relation values or relation variables—positions that have been advocated in the literature—has been referred to as The First Great Blunder, q.v. (For the second, see pointer; Second Great Blunder.)
Example: Here’s a sample type definition (basically as shown in the example under TYPE):
TYPE POINT ... { ... CONSTRAINT ( X↑2 + Y↑2 ) ≤ 10000 } ;
POINT here is a user defined type, denoting geometric points in two-dimensional space. It’s subject to a type constraint—imposed somewhat arbitrarily, and purely for the sake of the example—that says, in effect, that the only points of interest are those that lie on or inside a circle with center the origin and radius of length 100. (The symbols X and Y denote the cartesian coordinates of the point in question, and the symbol “↑” denotes exponentiation.)
type checking (Without inheritance) Checking that the types of the arguments to a given operator invocation conform to the type requirements as defined in the applicable invocation signature, q.v. Note that all type checking can be done at compile time, in the absence of support for inheritance.
Example: Let MOVE be an operator with invocation signature as follows:
( ELLIPSE , RECTANGLE ) RETURNS ELLIPSE
Also, let variables E and R be of declared types ELLIPSE and RECTANGLE, respectively. Then the first of the following MOVE invocations will raise a type error (q.v.) but the second won’t:
MOVE ( R , E )
MOVE ( E , R )
type constraint A definition of the set of values that make up a given type. The type constraint for type T is checked, in effect, whenever some selector is invoked for that type T; in other words, a type constraint error occurs if and only if some selector is invoked with arguments that violate the applicable type constraint. See also CONSTRAINT; contrast type error.
Examples: For scalar types, see the examples under CONSTRAINT; TYPE; and elsewhere. For tuple and relation types, no type constraints are defined explicitly (at least as far as The Third Manifesto is concerned); rather, the constraints in question are defined implicitly by the constraints that apply to the scalar types in terms of which the tuple or relation type in question is (ultimately) defined. For example, the type constraint for type RELATION {E ELLIPSE, R RECTANGLE} is simply a constraint to the effect that (a) attribute E is subject to the type constraint that applies to type ELLIPSE and (b) attribute R is subject to the type constraint that applies to type RECTANGLE.
Incidentally, it’s worth noting that the only type constraints that apply to user defined types in SQL—see user defined type (SQL)—are those that follow from the underlying physical representation. For example, suppose type SHOE_SIZE (with the obvious interpretation) is defined to have an INTEGER physical representation. Then the only constraint on shoe sizes is that they must be representable as an integer; thus, e.g., −5000 is apparently a valid shoe size (!).
type constraint error See type constraint.
type constructor Term used in SQL and certain other languages to mean a type generator.
type conversion See CAST_AS_T.
type definition See TYPE.
type error (Without inheritance) The error that occurs if type checking fails (i.e., if some operator is invoked with an argument of some type not equal to the declared type of the corresponding parameter). Such errors should be detectable at compile time, in the absence of support for inheritance.
type generator An operator that’s invoked at compile time instead of run time and returns a type instead of a value. For example, conventional programming languages typically support an array type generator, which lets users specify an unlimited number and variety of individual array types. In the relational model, the tuple and (especially) relation type generators are the important ones; they allow users to specify an unlimited number and variety of individual tuple and relation types. See relation type; tuple type.
Examples: Consider the suppliers relvar definition:
VAR S BASE RELATION
{ SNO SNO , SNAME NAME , STATUS INTEGER , CITY CHAR }
KEY { SNO } ;
This definition includes an invocation of the RELATION type generator (syntactically, everything from the keyword RELATION to the closing brace following the keyword CHAR, inclusive). That invocation returns a specific relation type—namely, the type
RELATION { SNO SNO , SNAME NAME , STATUS INTEGER , CITY CHAR }
So this type is in fact a generated type—as indeed are all relation types, and all tuple types also, at least as far as this dictionary, and indeed Tutorial D and The Third Manifesto, are concerned.
Observe that nongenerated types are always scalar. Generated types are typically nonscalar, but don’t have to be. An example of a scalar generated type is the SQL type CHAR(25); CHAR here is a type generator—not, as commonly supposed, a type as such—and the length specification 25 is the argument to a specific invocation of that generator. Analogous remarks apply to the SQL type NUMERIC(5,2).
type inference The process of determining the type of the value denoted by a given expression. Note that this process is completely specified by the rules defining the types of the results of the various operations involved in the expression in question. (In fact, of course, the type of the value denoted by expression exp is, precisely, the type of the result of the outermost operation involved in exp.)
type inheritance 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′. 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′. See Part II of this dictionary for further explanation.
type naming The Third Manifesto requires every type to have exactly one name and distinct types to have distinct names. In the case of tuple and relation types, however, there might well be more than one way of writing the corresponding name on paper. For example, the following all represent the same relation type name in Tutorial D:
RELATION { SNO SNO , CITY CHAR }
RELATION { CITY CHAR , SNO SNO }
RELATION { SNO SNO , CITY CHAR , SNO SNO }
Note: Although it’s true that every type has just one unique name, for psychological reasons Tutorial D does allow types to have one or more synonyms. For example, CHAR, INT, and BOOL are system defined synonyms for CHARACTER, INTEGER, and BOOLEAN, respectively, in Tutorial D. Thus, e.g., a given variable can be defined to have type either INTEGER or INT, and the definitions in question are regarded as equivalent. As for tuple and relation types, that same synonym mechanism allows the keywords TUPLE and RELATION to be abbreviated to TUP and REL, respectively.
type schema (Without inheritance) Term sometimes used to refer to a collection of type definitions. For example, the collection of type definitions for all of the user defined types (SNO, PNO, NAME, COLOR, WEIGHT, QTY) involved in the suppliers-and-parts database could be regarded as a type schema.
type vs. relvar See relvar vs. type.
types vs. units Some types are such that values of the type in question have to be understood as being expressed in terms of certain units in order to be fully understood. For example, consider type LENGTH. A sample value of that type might be 24, with inches understood; or, equivalently, 2, with feet understood; or 60.96, with centimeters understood; and so on. One approach to this issue would be to design a single LENGTH type with different possreps corresponding to different units of measure: an inches possrep, a feet possrep, a centimeters possrep, and so on. For further discussion of this approach, see the Manifesto book; see also CAST_AS_T.
UDT User defined type.
unary (Of a heading, key, tuple, relation, etc.) Of degree one. Contrast monadic.
uncontrolled redundancy Redundancy, q.v., that has the potential to lead to inconsistency. Database designs should preferably not permit such redundancy. Contrast controlled redundancy; see also consistency.
UNGROUP See ungrouping.
ungrouping Let relation r have attributes called A1, A2, ..., Am, and BR (and no others), and let attribute BR be relation valued and have attributes called B1, B2, ..., Bn (and no others); further, let no Ai have the same name as any Bj (1 ≤ i ≤ m, 1 ≤ j ≤ n). Then (and only then) the expression r UNGROUP BR denotes the ungrouping of r on BR, and it returns the relation denoted by the expression UNION (EXTEND r : { temp := (!!r){ALL BUT BR} TIMES BR}, temp)—an invocation of the UNION aggregate operator, q.v. Note: The subexpression !!r here is an image relation reference, q.v.
Example: Let spq be the relation resulting from the expression
SP GROUP { PNO , QTY } AS PQ_REL
(see grouping). Then the expression
spq UNGROUP PQ_REL
denotes an ungrouping of spq. That ungrouping is a relation of type RELATION {SNO SNO, PNO PNO, QTY QTY}; and if spq is obtained from the relation sp shown as the value of relvar SP in Fig. 1, then the result of ungrouping spq is just sp. Suppose, however, that spq additionally contains a tuple, say for supplier S5, in which the PQ_REL value is an empty relation; then the result of the foregoing UNGROUP won’t contain a tuple for supplier S5 (in fact, the result will still be, exactly, that same relation sp). In general, therefore, ungrouping a relation r and then grouping it again in what might look like an inverse way isn’t guaranteed to take us back to r (contrast grouping).
uniform representation / uniformity of representation See Information Principle.
UNION See union.
union (Without inheritance) 1. (Dyadic case) Let relations r1 and r2 be of the same type T. Then (and only then) the expression r1 UNION r2 denotes the union of r1 and r2, and it returns the relation of type T with body the set of all tuples t such that t appears in at least one of r1 and r2. 2. (N-adic case) Let relations r1, r2, ..., rn (n ≥ 0) all be of the same type T. Then (and only then) the expression UNION {r1,r2,...,rn}denotes the union of r1, r2, ..., rn, and it returns the relation of type T with body the set of all tuples t such that t appears in at least one of r1, r2, ..., rn. Note: If n = 0, (a) some syntactic mechanism, not shown here, is needed to specify the pertinent type T and (b) the result is the empty relation of that type. Note too that the relational union operator differs in certain respects from the mathematical or set theory operator of the same name, q.v.; also, union is sometimes known explicitly as inclusive union in order to distinguish it from exclusive union, q.v. (but the term union, unqualified, is always taken to mean inclusive union specifically, unless the context demands otherwise). Note finally that UNION can also be used as an aggregate operator, q.v. See also disjoint union; tuple union.
Example: The expression S{CITY} UNION P{CITY} denotes the union of (a) the relation that’s the projection on {CITY} of the current value of relvar S and (b) the relation that’s the projection on {CITY} of the current value of relvar P. That union is a relation r of type RELATION {CITY CHAR}. Moreover, if the current values of relvars S and P are s and p, respectively, then the body of that relation r consists of all tuples of the form <c> that appear in s{CITY} or p{CITY} or both—meaning c is a current supplier city or a current part city or both.
union (bag theory) See bag.
union (set theory) The union of two sets s1 and s2, s1 ∪ s2 (where the symbol “∪” can conveniently be pronounced “cup”), is the set of all elements x such that x is an element of s1 or an element of s2. Note: This definition can obviously be extended to apply to any number of sets.
union compatible (Of relations) Of the same type. The term is deprecated for many reasons, of which inappropriateness is one.
union plus See bag.
UNIQUE Keyword sometimes used to denote the quantifier “there exists exactly one of.” In other words, let p(x) be a predicate with a parameter x; then UNIQUE x (p(x)) is a predicate, and it means “There exists exactly one argument value v that can be substituted for the parameter x such that p(v) is true.”
Example: Here’s a tuple calculus formulation of the foreign key constraint “Every shipment has exactly one corresponding supplier”:
SX RANGES OVER { S } ;
SPX RANGES OVER { SP } ;
CONSTRAINT SP_REFERENCES_S
FORALL SPX ( UNIQUE SX ( SX.SNO = SPX.SNO ) ) ;
Note: The expression UNIQUE x (p(x)) is logically equivalent to the expression EXISTS x (p(x) AND NOT EXISTS y (y ≠ x AND p(y))). Observe that this expression evaluates to FALSE if the bound variable x has an empty range.
unique index An index—hence, an implementation construct—on (the stored analog of) some relvar on the basis of some superkey for that relvar; not to be confused with a superkey per se, even though the index might be used to implement the associated superkey constraint. Note: In practice, the superkey in question is usually (or is usually intended to be) a key as such, not a proper superkey.
uniqueness See candidate key; superkey.
units See types vs. units.
universal quantifier Let p(x) be a predicate with a parameter x; then FORALL x (p(x)) is a predicate, and it means “For all argument values v that can be substituted for the parameter x, p(v) is true.” In this example, FORALL x is a universal quantifier, and x is a universally quantified bound variable, q.v. Note: Some writers refer to FORALL by itself as the quantifier; the literature is not consistent on this point. More important, note that if v1, v2, ..., vn are all of the possible argument values in the foregoing example, then FORALL x (p(x)) is equivalent to AND {(p(v1)), (p(v2)),...,(p(vn))} (see conjunction, second definition). Observe in particular that this expression evaluates to TRUE if n = 0 (i.e., if the bound variable x has an empty range), because TRUE is the identity with respect to AND. Observe further that the expression FORALL x (p(x)) is logically equivalent to the expression NOT (EXISTS x (NOT (p(x)))). See also FORALL; contrast existential quantifier.
Example: Here’s a tuple calculus query that makes use of the universal quantifier as well as the existential quantifier (“Get suppliers who supply all parts”):
SX RANGES OVER { S } ;
SPX RANGES OVER { SP } ;
PX RANGES OVER { P } ;
{ SX } WHERE FORALL PX ( EXISTS SPX ( SPX.SNO = SX.SNO AND
SPX.PNO = PX.PNO ) )
The expression in the last two lines here can be read as “Suppliers SX where for all parts PX there exists a shipment SPX with the same supplier number as SX and the same part number as PX.”
universal relation Given a heading H, the relation with heading H that contains all possible tuples with heading H. Note, therefore, that there’s exactly one universal relation for each relation type, and every relation of a given type is a subrelation (q.v.) of the pertinent universal relation. Contrast empty relation. Caveat: The term universal relation is often used in the database literature (e.g., in discussions of normalization) to refer to what would more appropriately be called a universal relvar, q.v.
universal relvar Very loosely, the join of all relvars in a given set of relvars; slightly less loosely, a hypothetical relvar whose heading is the set theory union of the headings of all of the relvars in a given set. The normalization procedure, q.v., if viewed in isolation (i.e., ignoring other possible aids to database design), tacitly assumes it’s possible to define an initial universal relvar—unfortunately more usually referred to in the literature not as a universal relvar as such but rather as a universal relation—that has all of the attributes relevant to the database under consideration, and then shows how that relvar can and/or should be replaced by successively “smaller” (i.e., lower degree) projections until a “good” design is reached. Incidentally, note the implications for attribute naming that underlie the foregoing assumption. To be specific, it implies that (e.g.) the supplier number attributes in relvars S and SP will both have the same name instead of being called, say, SNO in one relvar and SNUM in the other. This attribute naming discipline is strongly recommended anyway, because it has the effect among other things of simplifying the formulation—both formal and informal—of queries, constraints, and so on (as indeed should be clear from a careful study of the definitions in this dictionary of the various relational operators).
universal set The universe of discourse, q.v.; the set that contains all of the elements of interest in some given context. Every set is a subset of the universal set.
universe of discourse See sorted logic.
UNKNOWN See three-valued logic.
unnesting See nesting and unnesting.
unnormalized Not normalized (i.e., not in first normal form, q.v.); not to be confused with denormalized (see denormalization). Note: By definition, relations and relvars are never unnormalized. However, certain data structures—in particular, tables with repeating groups, q.v.—might “look something like” relations or relvars and yet not be normalized (and thus in fact not corresponding directly to relations or relvars, as such, after all).
unsorted logic See sorted logic.
UNWRAP See unwrapping.
unwrapping Let relation r have attributes called A1, A2, ..., Am, and BT (and no others), and let attribute BT be tuple valued and have attributes called B1, B2, ..., Bn (and no others); further, let no Ai have the same name as any Bj (1 ≤ i ≤ m, 1 ≤ j ≤ n). Then (and only then) the expression r UNWRAP BT denotes the unwrapping of r on BT, and it returns the relation denoted by the expression (EXTEND r : {B1 := B1 FROM BT, B2 := B2 FROM BT, ..., Bn := Bn FROM BT}){ALL BUT BT}. See also tuple unwrapping.
Example: Let spw be the relation resulting from the expression
SP WRAP { PNO , QTY } AS PQ_REL
(see wrapping). Then the following expression denotes an unwrapping of spw:
spw UNWRAP PQ_REL
That unwrapping is a relation of type RELATION {SNO SNO, PNO PNO, QTY QTY}. If spw is obtained by wrapping the relation sp shown as the value of relvar SP in Fig. 1, then the result of unwrapping spw is just sp.
UPDATE Very loosely, an operator that updates a given set of attributes in a given set of tuples in a given relvar; slightly less loosely, an operator that replaces a given set of tuples in a given relvar by another such set. It’s shorthand for a certain relational assignment. The syntax is:
UPDATE R [ WHERE bx ] : { attribute assignment commalist }
Here R is a relvar reference (syntactically, just a relvar name), bx is a boolean expression, the target for the attribute assignments are attributes of relvar R, and the invocation just shown is shorthand for the following explicit assignment:
R := ( R WHERE NOT ( bx ) )
UNION
( EXTEND ( R WHERE bx ) : { attribute assignment commalist } )
See also WITH.
Example: The UPDATE statement
UPDATE P WHERE CITY = 'London' :
{ WEIGHT := 2 * WEIGHT , CITY := 'Oslo' } ;
is shorthand for the following relational assignment statement:
P := ( P WHERE NOT ( CITY = 'London' ) )
UNION
( EXTEND ( P WHERE CITY = 'London' ) :
{ WEIGHT := 2 * WEIGHT , CITY := 'Oslo' } ) ;
In this example, we might say, loosely, that attributes WEIGHT and CITY are being updated in the tuples for London parts; we might also say, still loosely but a little less so, that the tuples for London parts are being replaced; but what’s really happening is that a certain relation value is being assigned to a certain relation variable.
Note: In Tutorial D in particular, the UPDATE operator can be used to update scalar and tuple variables as well as relation variables per se (in other words, UPDATE is overloaded).
UPDATE anomaly Same as modification anomaly.
UPDATE rule A rule specifying the action to be taken automatically—typically but not necessarily a compensatory action, q.v.—to ensure that UPDATE operations on a given relvar don’t violate any associated multivariable constraint, q.v. Note: The relational model rejects UPDATE rules as logically flawed (since, unlike DELETE and INSERT rules, q.v., they’re apparently driven by syntax, not semantics). Contrast DELETE rule; INSERT rule.
update An assignment, especially a relational assignment; more especially still, a relational INSERT, D_INSERT, DELETE, I_DELETE, or UPDATE operation, q.v.
update anomaly A deletion anomaly (q.v.), insertion anomaly (q.v.), or modification anomaly (q.v.).
update operator An operator that, when invoked, returns no value but updates a variable (usually an argument) that’s not local to the implementation of the operator in question. An update operator invocation doesn’t denote a value—loosely speaking, it’s a statement (typically a CALL statement of some kind), not an expression—and thus it can’t appear where an expression is required. In particular, it can’t be nested inside an expression. Every update operator invocation is logically equivalent to some assignment (possibly a multiple assignment, q.v.).
Example: See the second example under RETURN.
update propagation See controlled redundancy.
UPDATES Let Op be an update operator; then Op has a set of parameters that are subject to update, q.v., each of which must be identified as such as part of the definition of Op. In Tutorial D, this function is performed by means of the UPDATES clause. Contrast RETURNS.
Example: See the second example under RETURN.
user Either an end user (knowledgeable or otherwise concerning database matters) or an application programmer or both, as the context demands.
user defined Defined by some agency other than the system; i.e., not system defined (not built in). User defined operators and user defined types provide obvious examples. Note: The term “user defined” is sanctioned by usage but really isn’t very good. Consider the case of a user defined type T, for example. To the user who merely makes use of that type—as opposed to the user who actually defines it—type T behaves in all major respects just like a system defined type (indeed, that’s the whole point). In other words, what’s being sought here is not so much a distinction between users and the system as it is a distinction between different roles played by different users (possibly even by the same user) in different contexts.
user defined type See type; user defined. Contrast system defined type. Note: The system vs. user defined types distinction applies only to nongenerated types, not to types produced via invocation of some type generator.
Examples: Of the scalar types used in the suppliers-and-parts database, SNO, PNO, NAME, COLOR, WEIGHT, and QTY are all user defined.
user defined type (SQL) SQL divides user defined types into two kinds, “distinct types” and “structured types.” In essence:
A distinct type D—note that the term distinct is being used here in a highly specialized sense—(a) is defined in terms of just one underlying type T, which is explicitly visible to the user, must be system defined, must be scalar, and is in fact the physical (not just some possible) representation for values of type D; (b) has no type constraint, except for the obvious constraint that values of type D must be representable as values of type T; (c) inherits comparison and assignment operators, but no other operators, from type T; (d) effectively does have selector and THE_ operators, though terminology and syntax both differ from their counterparts as defined in this dictionary; and (e) can’t have proper subtypes.
A structured type S—note that the term structured is being used here in a highly specialized sense—(a) is defined in terms of a construct somewhat akin to a possrep, except that the “possrep” in question is really the physical (not just some possible) representation for values of type S; (b) has no type constraint, except for the obvious constraint that values of type S must be representable in terms of that specified physical representation; (c) has no comparison operators (not even “=”) other than ones explicitly defined by means of a special and separate CREATE ORDERING operator [sic]; (d) effectively does have assignment, selector, and THE_ operators, though terminology and syntax both differ from their counterparts as defined in this dictionary; and (e) can have proper subtypes.
Further details, of both distinct and structured types, are exceedingly complex and are beyond the scope of this dictionary, except for occasional passing references here and there.
value An “individual constant,” q.v. (for example, the individual constant denoted by the integer literal 3). Values can be of arbitrary complexity; in particular, they can be either scalar or nonscalar (note in particular that tuples and relations are both values). Values have no location in time or space; however, they can be represented in memory by means of some encoding, and those representations do have location in time and space—indeed, distinct occurrences of the same value can appear at any number of distinct locations in time and space, meaning, loosely, that the same value can occur as the current value of any number of distinct variables, and/or as any number of attribute values within the current value of any number of distinct tuplevars and/or relvars, at the same time or different times (see appearance). Note that, by definition, a value can’t be updated; for if it could, then after such an update it would no longer be that value. Note too that every value is of some type—in fact, of exactly one type (and types are thus disjoint), except possibly if type inheritance is supported. Note finally that a value isn’t a type, nor is it a variable. Contrast literal.
value set Term sometimes used in E/R contexts to mean a type—almost certainly a scalar type specifically, though the literature isn’t really clear on this point.
VAR The Tutorial D operator for defining variables (relation variables in particular).
Examples: See the introduction to this dictionary and elsewhere.
variable 1. (Logic) See logic variable. 2. (Programming languages) A holder for a representation of a value, q.v. Unlike values, variables (a) do have location in time and space and (b) can be updated (that is, the current value of the variable can be replaced by another value). Indeed, to be a variable is to be updatable, and to be updatable is to be a variable; equivalently, to be a variable is to be assignable to, and to be assignable to is to be a variable. Every variable is declared to be of some type. Note that a variable isn’t a type, nor is it a value. Note too that the language D, q.v., requires variables always to have a value; in particular, therefore, it requires the operation of defining variable V to have the effect, among other things, of initializing V to some value—typically but not necessarily a value explicitly specified as part of that defining operation (but see example value).
variable reference 1. (Logic) See bound variable; free variable. 2. (Programming languages) Syntactically, a variable name, used to denote either the variable as such or the value of that variable, as the context demands. Note that such a reference definitely denotes the variable as such if it’s used to specify a target for some update operation (in particular, if it appears on the left side of an assignment). If on the other hand it denotes the value of the variable, then it can be regarded as an invocation of a read-only operator—and hence as an expression, q.v.—where the read-only operator in question is essentially “Return the current value of the specified variable.” Like all expressions, therefore, it can appear wherever a literal of the appropriate type can appear. See also pseudovariable reference.
vertical decomposition Informal term for decomposition into projections.
view A derived relvar that’s virtual, not real (contrast snapshot). The value of a given view at a given time is the result of evaluating a certain relational expression—the view defining expression, specified when the view itself is defined—at the time in question. Note: The view defining expression must mention at least one relvar, for otherwise the view wouldn’t be, specifically, a variable as such. Note too that the view must be updatable for the same reason.
Example: The following statement defines a view called LS:
VAR LS VIRTUAL ( S WHERE CITY = 'London' ) ;
The relation that’s the value of view LS at any given time is equal to the value of the view defining expression S WHERE CITY = 'London' at that time.
view materialization A somewhat unsophisticated technique for implementing operations on views, according to which (a) the relational expression that defines the view is evaluated at the time the operation on the view is invoked, (b) a relation is thereby materialized, and (c) the operation in question is then executed against the relation so materialized. Observe that operations on views can always be implemented using this technique (albeit perhaps not very efficiently) if the operation in question is a read-only operation but not if it’s an update operation. Contrast substitution (second definition). See also materialized view.
view updating Either the theory or the process of updating views, as the context demands. View updating is still a somewhat controversial topic, but there are those who believe that—contrary to popular opinion, perhaps—all views are at least theoretically updatable. The details are beyond the scope of this dictionary, except to note that (a) a view update can fail on an integrity violation, of course, just as a base relvar update can, and (b) an argument can be made that view updates that are regarded by some writers as “impossible” aren’t intrinsically impossible after all but instead fail on just such a violation. Moreover, if a system does support views but doesn’t support view updating correctly (or at all!), then such a state of affairs would constitute the clearest possible violation of The Principle of Interchangeability. For a detailed discussion of such matters, with numerous examples, see the book View Updating and Relational Theory: Solving the View Update Problem, by C. J. Date (O’Reilly Media Inc., 2013).
violate Let C be a constraint that refers to variables V1, V2, ..., Vn (n ≥ 0) and no others. Then values v1, v2, ..., vn (in that order) violate C if and only if evaluating C with V1 equal to v1, V2 equal to v2, ..., and Vn equal to vn yields FALSE. Note: An analogous definition applies to business rules also, q.v. Contrast satisfy.
virtual relation The value of a given virtual relvar at a given time.
virtual relvar A view, q.v. (contrast real relvar).
void Empty (e.g., the empty set is sometimes referred to as the void set). Not to be confused with null, q.v.
well formed formula In logic, a formal expression denoting a predicate.
WFF A well formed formula. The abbreviation is variously pronounced “weff” or “wiff” or “woof.” See also closed WFF; open WFF.
what if A read-only relational operator that returns the relation that would result if certain changes were made to a specified relation (ignoring the fact that such changes couldn’t in fact be made, because a relation is a value). Note: Tutorial D uses the EXTEND operator to provide this functionality—see extension, second definition. (The keyword EXTEND is perhaps not the best in the circumstances, but it’s hard to find a word that catches the overall sense better and yet is equally succinct.) See also WITH.
Example: The expression
EXTEND ( S WHERE CITY = 'Paris' ) :
{ STATUS := 2 * STATUS , CITY := 'Nice' }
denotes a relation containing exactly one tuple t for each tuple s in the current value of relvar S for which the city is Paris—except that, in that tuple t, the status is double that in tuple s and the city is Nice, not Paris.
WHERE clause A syntactic construct of the form WHERE bx (where bx is a boolean expression, typically an open one) that appears ubiquitously in SQL, Tutorial D, and many other languages. See DELETE; restriction; restriction condition; SELECT expression; UPDATE; and elsewhere.
WITH A syntactic device, supported by Tutorial D in particular, for introducing names for the results of subexpressions. The introduced names are then available for subsequent use (but only within the overall expression or statement of which the WITH specification forms a part) to denote those results.
Examples: 1. The following is a Tutorial D formulation of the query “Get pairs of supplier numbers, Sx and Sy say, such that suppliers Sx and Sy each supply exactly the same set of parts”:
WITH ( tx := ( S RENAME { SNO AS SX } ) { SX } ,
ty := ( S RENAME { SNO AS SY } ) { SY } ) :
( tx JOIN ty ) WHERE ( SP WHERE SNO = SX ) { PNO } =
( SP WHERE SNO = SY ) { PNO }
Note the relational comparison in the WHERE clause here. 2. Tutorial D also allows a WITH specification to appear inside the braces, preceding the commalist of attribute assignments, in an EXTEND, SUMMARIZE, or UPDATE invocation. The following example is repeated from the discussion in the entry for summarization:
EXTEND SP : { WITH ( temp := !!SP ) :
SQ := SUM ( temp , QTY ) , AQ := AVG ( temp , QTY ) }
Note: SQL also supports a WITH construct, with semantics similar but not identical to those of the Tutorial D construct—and, it has to be said, with much less practical utility, owing to the fact that SQL’s support for any given relational operator is, in general, quite hard to disentangle from its support for other such operators. (Simplifying slightly, the problem is that, in SQL, the subexpressions whose results can be named via WITH can’t be anything less than an entire SELECT expression, q.v.)
WRAP See wrapping.
wrapping Let relation r have attributes called A1, A2, ..., Am, B1, B2, ..., Bn (and no others), and let BT be an attribute name that’s distinct from that of every attribute Ai (1 ≤ i ≤ m). Then (and only then) the expression r WRAP {B1,B2,...,Bn} AS BT denotes the wrapping of r on {B1,B2,...,Bn}, and it returns the relation denoted by the expression (EXTEND r : {BT := TUPLE {B1 B1,B2 B2,...,Bn Bn}}) {A1,A2,...,Am,BT}. See also tuple wrapping.
Example: The following expression denotes a wrapping of the relation that’s the current value of relvar SP:
SP WRAP { PNO , QTY } AS PQ_TUP
That wrapping is a relation spw of type RELATION {SNO SNO, PQ_TUP TUPLE {PNO PNO, QTY QTY}}; it contains one tuple for each tuple currently appearing in relvar SP, and no other tuples. Given the sample values in Fig. 1, for example, the spw tuple for supplier S1 and part P1 has SNO value S1 and PQ_TUP value a tuple with PNO value P1 and QTY value 300. (Attribute PQ_TUP here is an example of a tuple valued attribute.)
write operator Same as update operator.
XMINUS If exclusive union (q.v.) is referred to as symmetric difference (q.v.), then XMINUS might be psychologically preferable to XUNION (q.v.) as the corresponding keyword.
XML Extensible Markup Language. Note: From a database point of view, XML—or “XML document,” rather—is best regarded as just another data type, albeit one of considerable pragmatic importance at the time of writing. Values of that type are XML documents. Among other things, therefore, relations should be allowed to have attributes of that type, and tuples in such relations should thus be allowed to contain attribute values that are XML documents.
XOR 1. A connective, q.v. (see exclusive OR). 2. An aggregate operator, q.v. Contrast EQUIV.
XUNION See exclusive union.
ZO A Tutorial D operator that, given a relation r, returns a relation with heading the same as that of r and body either (a) empty if r is empty or (b) consisting of precisely one tuple otherwise, that tuple being some arbitrary tuple from the body of r. The name ZO is shorthand for “zero or one”; it derives from the fact that the cardinality of the result is either zero or one. See also axiom of choice.
Example: Here is a possible formulation of a constraint to the effect that the cardinality of some given relvar R must never exceed two:
CONSTRAINT ZOX WITH ( X := R MINUS ZO ( R ) ) :
IS_EMPTY ( X MINUS ZO ( X ) ) ;
Of course, the same constraint can be more readily expressed thus:
CONSTRAINT ZOX COUNT ( R ) ≤ 2 ;
However, this formulation relies, as the former did not, on the availability of the aggregate operator COUNT.