Examples: Let the symbols x and y denote integers. Then the following expressions are both predicates, and x appears as a free variable in both of them:
x < 7
EXISTS y ( y > 3 ) AND x < 7
The first of these examples is self-explanatory. The second is a little more complicated, because it involves a quantified subexpression (in which y appears, twice, as a bound variable) as well as the free variable x.
Turning to a database example, the following is a query (“Get suppliers who supply at least one part”) on the suppliers-and-parts database, expressed in tuple calculus:
{ S } WHERE EXISTS SP ( SP.SNO = S.SNO )
The boolean expression following the keyword WHERE here is a predicate, and the reference to S in that predicate is free (by contrast, the references to SP are bound). Note, however, that in this particular example the symbols S and SP denote not only variables in the sense of logic but also variables in the conventional programming language sense—but that’s because we’ve indulged in a certain sleight of hand, as it were. Here’s an expanded version of the same example that should help clarify matters:
SX RANGES OVER { S } ;
SPX RANGES OVER { SP } ;
{ SX } WHERE EXISTS SPX ( SPX.SNO = SX.SNO )
Here SX and SPX have been explicitly declared to be range variables (q.v.)—in other words, they’re variables in the sense of logic—ranging over (the current values of) relvars S and SP, respectively. Now it’s the reference to SX that’s free and the references to SPX that are bound (in the predicate following the keyword WHERE in both cases). In effect, what happened in the first version of the example was that we were appealing to a syntax rule that allowed a relvar name to be used to denote an implicitly defined range variable that ranges over (the current value of) the relvar with the same name. Note that SQL includes a syntax rule of exactly this kind.
Note: Let R be a range variable reference that occurs prior to the WHERE clause—i.e., within the proto tuple, q.v.—in some tuple calculus expression. If R also occurs in the predicate in that WHERE clause (which it usually but not invariably will), then it must be free, not bound, in that predicate. Observe that these remarks apply in particular to the references to the range variable SX in the example shown above.
friendship An ad hoc and thus somewhat deprecated OO mechanism that allows the code that implements some operator for values and/or variables of some type T1 to have access—access, that is, that it wouldn’t otherwise have—to the physical representation of values and/or variables of some other type T2. The operator in question is “associated with” type T1 but is “a friend of” type T2.
full FD Old fashioned and somewhat deprecated (because slightly inappropriate) term for an irreducible FD.
full instantiation See instantiation.
fully connected (Of a database) See database variable.
fully dependent Old fashioned and somewhat deprecated (because slightly inappropriate) term for irreducibly dependent.
fully normalized A slightly fuzzy term whose meaning varies somewhat, depending on context. Loosely, however, we can say a database is fully normalized if and only if every relvar it contains is in at least 5NF (i.e., if and only if every such relvar is fully normalized in turn). Note, however, that the concept of normalization as such really applies to relvars, not databases.
fully redundant Tuple t is fully redundant in relation r if and only if it’s forced to appear in r by virtue of the fact that certain other tuples t1, t2, …, tn, all distinct from t, also appear in r (see tuple forcing JD). Note that a tuple can be fully redundant without being partly redundant (see partly redundant). Note too that a relvar can contain a fully redundant tuple only if that relvar isn’t in ETNF, q.v; thus, normalizing to (at least) ETNF is guaranteed to eliminate the possibility of fully redundant tuples.
function 1. (Mathematics) Given two sets, not necessarily distinct, a rule—also known as a map or mapping—pairing each element of the first set (the domain) with exactly one element of the second set (the codomain); equivalently, the set of ordered pairs <x,y> that constitutes that pairing. The unique element y of the codomain corresponding to element x of the domain is the image of x under the specified function, and the set of all such images is the range of that function. Note that the range is a subset (in general, a proper subset) of the codomain, and the function can be regarded as a directed relationship—in fact, a many to one correspondence, q.v., in the strict sense of that term—from the domain to the range. Note too that a function is a special case of a binary relation. See also partial function; total function. 2. (Programming languages) A read-only operator (sometimes more specifically one denoted by an identifier such as PLUS instead of a special symbol such as “+”). Note, however, that the programming language construct denoted by this term is precisely a function in the mathematical sense; thus, there’s really just one concept here, not two. Note also that nothing in the definition requires the domain and codomain to be sets of scalars; thus, a read-only operator could be defined in terms of, say, three parameters, in which case the domain would consist of a set of triples. A similar remark applies to the codomain.
Example: Let f be the rule that maps nonnegative integers x to their squares x². Then f is a function with (a) domain and codomain both the set of all nonnegative integers and (b) range that subset of the codomain consisting only of perfect squares. Observe in particular that—to spell the point out—f here, like all functions, has the property that the output value (i.e., the image) for any given input value is well defined and unique. Contrast possibly nondeterministic; ZO.
functional dependency Let H be a heading; then a functional dependency (FD) with respect to H is an expression of the form X → Y, where X (the determinant) and Y (the dependant) are both subsets of H. (The qualifying phrase “with respect to H” can be omitted if H is understood.) The expression X → Y is read as “Y is functionally dependent on X,” or “X functionally determines Y,” or, more simply, just “X arrow Y.”
Let relation r have heading H, and let X → Y be an FD, F say, with respect to H. If all pairs of tuples t1 and t2 of r are such that whenever (a) the projections of t1 and t2 on X are equal then (b) the projections of t1 and t2 on Y are also equal, then (c) r satisfies F; otherwise r violates F. (Note the appeal in this definition to the operation of tuple projection, q.v.) Now let relvar R have heading H. Then R is subject to the FD F—equivalently, the FD F holds in R—if and only if every relation r that can ever be assigned to R satisfies that FD F. The FDs that hold in relvar R are the FDs of R, and they serve as constraints (q.v.) on R.
Note that FDs are defined with respect to some heading, not with respect to some relation or some relvar. Note too that from a formal point of view, an FD is just an expression: an expression that, when interpreted with respect to some specific relation, becomes a proposition that, by definition, evaluates to either TRUE or FALSE. Now, it’s common informally to define X → Y to be an FD only if it actually holds in the pertinent relvar—but that definition leaves no way of saying a given FD fails to hold in some relvar, because, by that definition, an FD that fails to hold isn’t an FD in the first place.
Example: Suppose for the sake of the example that relvar SP has an additional attribute CITY, representing the city of the applicable supplier. Then that revised version of SP is subject to the FD {SNO} → {CITY}. (Note in particular in this example that the determinant isn’t a key of the relvar concerned. By definition, every relvar R is always subject to all possible FDs of the form K → X, where K is a key—or, more generally, a superkey—for R and X is an arbitrary subset of the heading of R. In other words, there are always “arrows out of superkeys,” and it’s “arrows not out of superkeys” that are the interesting ones, in a sense.)
Note finally that X and Y in the FD X → Y are, specifically, sets of attributes; informally, however, it’s common (though strictly incorrect) to speak of the attributes in X as if Y were functionally dependent on those attributes per se, instead of on the set X that contains those attributes. Likewise, it’s common (though strictly incorrect) to speak of the attributes in Y as if those attributes per se, instead of the set Y that contains those attributes, were functionally dependent on X. Note: The foregoing remarks apply with especial force to the common special case in which either X or Y is a singleton set.
functionally dependent See functional dependency.
functionally determines See functional dependency.
further normalization A slightly more accurate, or more descriptive, term for what is more conventionally referred to simply as normalization, q.v.
generalized dependency Somewhat inappropriate term used to refer to a specific kind of constraint—viz., a constraint that’s either an equality generating dependency, q.v., or a tuple generating dependency, q.v.
generated type See type generator.
generic constraint A constraint that’s automatically enforced in connection with every type that can be produced by invocation of some given type generator, q.v. For example, given an array type generator, there might be a generic constraint to the effect that no array of any type that can be produced by invocation of that generator can have a dimension for which the lower bound is greater than the upper bound.
generic operator An operator that’s available in connection with every type that can be produced by invocation of some given type generator, q.v. For example, the operators of the relational algebra are generic: They’re available for relations of every type that can be produced by invocation of the relation type generator—in other words, for relations of all possible types, and hence for all possible relations.
generic polymorphism The kind of polymorphism exhibited by a generic operator, q.v.
generic type Term sometimes used as a synonym for type generator. The term is inappropriate because a type generator isn’t a type.
GET_ operator An OO operator (an “observer,” q.v.) that retrieves the value of 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_ operator, except that THE_ operators are defined in terms of possrep components, not “object properties.” Contrast SET_ operator.
Golden Rule The rule—its name is set in all boldface because of its fundamental importance—that no database is ever allowed to violate its own total database constraint. It follows that no relvar is ever allowed to violate its own total relvar constraint either, a fortiori. Note: This latter, weaker requirement is often referred to as The Golden Rule as well, though strictly speaking it’s merely a logical consequence of The Golden Rule proper.
Great Blunder A somewhat contentious term that has been used in connection with certain egregious violations of fundamental relational principles. See First Great Blunder; Second Great Blunder.
Great Divide One of the many relational division operators that have been defined over the years (see division). Let relations r1, r2, r3, and r4 be such that (a) r1 and r3 are joinable, q.v., and so are r3 and r4, and so are r4 and r2; (b) the common attributes of r1 and r3 are called A1, A2, ..., Am (m ≥ 0); (c) the common attributes of r3 and r4 are called B1, B2, ..., Bn (n ≥ 0); (d) the common attributes of r4 and r2 are called C1, C2, ..., Cp (p ≥ 0); and finally (e) no Ai has the same name as any Bj, and no Bj has the same name as any Ck (1 ≤ i ≤ m, 1 ≤ j ≤ n, 1 ≤ k ≤ p). Then (and only then) the expression r1 DIVIDEBY r2 PER (r3,r4)—where r1 is the dividend, r2 is the divisor, and r3 and r4 are the “mediators”—denotes the division of r1 by r2 according to r3 and r4, and it returns the relation denoted by the expression (r1 JOIN r2) NOT MATCHING ((r1{A1,A2,...,Am} JOIN r4{B1,B2,...,Bn,C1,C2,...,Cp}) NOT MATCHING r3). In other words, relation r has heading the set theory union of the headings of r1 and r2 and body defined as follows: Tuple t appears in that body if and only if it appears in r1 JOIN r2 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,c1,c2,...,cp> appearing in r4{B1,B2,...,Bn,C1,C2,...,Cp} with c1 equal to the C1 value in t, c2 equal to the C2 value in t, ..., and cp equal to the Cp value in t. Contrast Small Divide.
Examples: Suppose we’re given a revised version of the suppliers-and-parts database, a version that’s both extended and simplified compared to our usual running example and looks like this:
S { SNO }
SP { SNO , PNO }
PJ { PNO , JNO }
J { JNO }
Relvar J here represents projects (JNO stands for project number), and relvar PJ indicates which parts are used in which projects. Then the expression S DIVIDEBY J PER (SP,PJ) yields a relation with heading {SNO,JNO} and body consisting of all possible tuples of the form <sno,jno>—where sno is an SNO value currently appearing in relvar S, jno is a JNO value currently appearing in relvar J, and supplier sno supplies all parts used in project jno—and no other tuples. The expression is logically equivalent to this one:
( S JOIN J ) NOT MATCHING ( ( S JOIN PJ ) NOT MATCHING SP )
An equivalent tuple calculus formulation is:
SX RANGES OVER { S } ;
SPX RANGES OVER { SP } ;
PJX RANGES OVER { PJ } ;
JX RANGES OVER { J } ;
{ SX , JX } WHERE FORALL PJX ( EXISTS SPX ( SX.SNO = SPX.SNO AND
SPX.PNO = PJX.PNO AND
PJX.JNO = JX.JNO ) )
An equivalent Tutorial D formulation is:
( S JOIN J ) WHERE !!PJ ⊆ !!SP
(The expressions !!PJ and !!SP here are image relation references, q.v.)
Incidentally, observe what happens if the operands to the foregoing division are switched around, thus: J DIVIDEBY S PER (PJ,SP). This expression yields a relation with heading {JNO,SNO} and body consisting of all possible tuples of the form <jno,sno>—where jno is a JNO value currently appearing in relvar J, sno is an SNO value currently appearing in relvar S, and project jno uses all parts supplied by supplier sno—and no other tuples. An equivalent tuple calculus formulation (using the same range variables as before) is:
{ JX , SX } WHERE FORALL SPX ( EXISTS PJX ( JX.JSNO = PJX.JNO AND
PJX.PNO = SPX.PNO AND
SPX.SNO = SX.SNO ) )
(The only difference is in the quantifiers.) An equivalent Tutorial D formulation is:
( J JOIN S ) WHERE !!SP ⊆ !!PJ
greater-than join A theta join, q.v., in which theta is “>”.
GROUP See grouping.
group Term sometimes used in connection with the grouping operator, q.v. Let r be a relation, let X be a subset of the heading of r, and let the projection of r on X have cardinality n (n ≥ 0). Then r can be partitioned into exactly n groups, where each such group g is a restriction of r (and hence a relation) with the property that (a) every tuple in g has the same value for X—i.e., for all pairs of tuples t1 and t2 in g, the (tuple) projections on X of t1 and t2 are equal—and (b) no tuple of r not in g has that same value for X. (In fact, each such group g is an equivalence class, q.v.)
Example: See the example under grouping.
group (mathematics) A formal system that obeys all of The Laws of Algebra, q.v., except that (a) multiplication (“*”) isn’t necessarily defined and (b) addition (“+”) isn’t necessarily commutative (if it is, then the group is a commutative or abelian group, otherwise it’s a noncommutative or nonabelian group).
grouping Let relation r have attributes called A1, A2, ..., Am, B1, B2, ..., Bn (and no others), and let BR be an attribute name that’s distinct from that of every attribute Ai (1 ≤ i ≤ m). Then (and only then) the expression r GROUP {B1,B2,...,Bn} AS BR denotes the grouping of r on {B1,B2,...,Bn}, and it returns the relation denoted by the expression EXTEND r {A1,A2,...,Am} : {BR := !!r}. Note: The subexpression !!r here is an image relation reference, q.v.
Example: The following expression denotes a grouping of the relation that’s the current value of relvar SP:
SP GROUP { PNO , QTY } AS PQ_REL
That grouping is a relation spq of type RELATION {SNO SNO, PQ_REL RELATION {PNO PNO, QTY QTY}}. Relation spq contains one tuple for each distinct SNO value currently appearing in relvar SP, and no other tuples. Given the sample values in Fig. 1, for example, the spq tuple for supplier S2 has SNO value S2 and PQ_REL value a relation whose body contains just the tuples <P1,300> and <P2,400>. (Attribute PQ_REL here is a relation valued attribute, q.v.)
Note: Given a relation r and some grouping of r, there’s always an inverse ungrouping that will yield r again; however, the converse isn’t necessarily so (see ungrouping).
hand optimization See optimization.
hash A specific kind of physical access path; hence, an implementation construct.
hash join A join implementation technique.
heading A set of attributes, in which (by definition) each attribute is a pair of the form <A,T>, where A is an attribute name and T is the name of the type of attribute A; especially, the set of attributes for a given relation or given relvar. Every subset of a heading is itself a heading. Within any given heading, (a) distinct attributes are allowed to have the same type name but not the same attribute name; (b) the number of attributes is the degree (of the heading in question). Note: Given that it’s common to refer to an attribute, informally, by its attribute name alone, it’s also common to regard a heading, informally, as a set of attribute names alone.
Examples: The heading of relvar S is
{ <SNO , SNO> , <SNAME , NAME> , <STATUS , INTEGER> , <CITY , CHAR> }
The following (corresponding to a certain projection of relvar S) is also a heading:
{ <CITY , CHAR> , <SNAME , NAME> }
These two headings might be represented less formally thus:
{ SNO , SNAME , STATUS , CITY }
{ CITY , SNAME }
In Tutorial D they could be represented as follows:
{ SNO SNO , SNAME NAME , STATUS INTEGER , CITY CHAR }
{ CITY CHAR , SNAME NAME }
(In other words, Tutorial D uses spaces instead of commas or other separators to separate attribute names from their corresponding type names.)
Heath’s Theorem Let X, Y, and Z be subsets of the heading H of relvar R, such that the set theory union of X, Y, and Z is equal to H. Let XY denote the set theory union of X and Y, and similarly for XZ. Finally, let R be subject to the FD X → Y. Then R is equal to the join of its projections on XY and XZ (and so can be nonloss decomposed into those projections). This theorem is often used as a guide in the process of normalization, q.v. Note that the converse of the theorem is false; that is, just because R is equal to the join of its projections on XY and XZ, it doesn’t follow that R is subject to the FD X → Y. However, if we replace the FD X → Y by the MVD X →→ Y throughout, then the resulting statement is true in both directions; that is, R is equal to the join of its projections on XY and XZ if and only if it’s subject to the MVD X →→ Y. See Fagin’s Theorem; multivalued dependency; see also Heath’s Theorem (extended version). Note: Heath’s Theorem was originally formulated in terms of relations, not relvars; however, the reason for this state of affairs (at least in part) was simply that the term relvar wasn’t in use at the time when Heath proved his theorem, back in 1971.
Example: Relvar S is subject to the FD {SNO} → {SNAME,CITY}, and so it’s equal to the join of its projections on {SNO,SNAME,CITY} and {SNO,STATUS}.
Heath’s Theorem (extended version) Let X, Y, and Z be subsets of the heading H of relvar R, such that the set theory union of X, Y, and Z is equal to H. Let XY denote the set theory union of X and Y, and similarly for XZ. If R is subject to the FD X → Y, then (a) R is equal to the join of its projections on XY and XZ and (b) XZ is a superkey for R; conversely, if (a) R is equal to the join of its projections on XY and XZ and (b) XZ is a superkey for R, then R is subject to the FD X → Y.
Example: Relvar S is subject to the FD {SNO} → {SNAME,CITY}, and so (a) it’s equal to the join of its projections on {SNO,SNAME,CITY} and {SNO,STATUS} and (b) {SNO,STATUS} is a superkey for S; conversely, (a) relvar S is equal to the join of its projections on {SNO,SNAME,CITY} and {SNO,STATUS} and (b) {SNO,STATUS} is a superkey for S, and so the FD {SNO} → {SNAME,CITY} holds in S.
hold Constraint C holds for variable V—equivalently, variable V is subject to constraint C—if and only if every value v that can ever be assigned to V satisfies C. Contrast satisfy (first meaning).
horizontal decomposition Informal term for decomposition into restrictions (see also orthogonal decomposition). Be aware, however, that the term is given an additional, or extended, meaning in the temporal data context—see Part III of this dictionary—and possibly in other contexts also.
Note: The physical database design technique known informally as “sharding” consists essentially of (a) performing horizontal decomposition as just defined on each of a set of hierarchically related base relvars based on values of a common attribute, that attribute being a key attribute for the relvar at the root of the hierarchy; (b) grouping together those restrictions with common values for that key attribute into a “shard”; and then (c) physically storing “direct images” (q.v.) of distinct shards at distinct sites. In the case of the suppliers-and-parts database, for example, tuples of relvars S and SP having SNO value either S1 or S2 might constitute one such shard and tuples of those same two relvars having SNO value S3, S4, or S5 might constitute another.
host language A programming language that relies on some data sublanguage, q.v., for its database support. Contrast database programming language.
I_DELETE See included DELETE.
I_MINUS See included difference.
idempotence 1. (Monadic) Let Op be a monadic operator, and assume for definiteness that Op is expressed in prefix style. Then Op is idempotent if and only if, for all x, Op(Op(x)) = Op(x). 2. (Dyadic) Let Op be a dyadic operator, and assume for definiteness that Op is expressed in infix style. Then Op is idempotent if and only if, for all x, x Op x = x. Note: Mathematics textbooks typically define idempotence as a concept that applies to just one of these two cases. However, some define it for the monadic case only and others for the dyadic case only. But both cases clearly make sense; hence the foregoing definition.
Examples: 1. (Monadic case) Let x be a real number, and define the monadic operator CEIL(x) to return the least integer greater than or equal to x. Then CEIL is idempotent, because CEIL(CEIL(x)) = CEIL(x) for all x. (By contrast, the monadic operator HALF—“return half of”—is certainly not idempotent.) 2. (Dyadic case) In logic, the dyadic operators OR and AND are both idempotent, because
x OR x = x
and
x AND x = x
for all x (by contrast, the dyadic operator XOR is not idempotent). Note: It follows as a direct consequence that UNION and JOIN, respectively, are idempotent (and XUNION is not) in relational algebra.
identity 1. (General) That which distinguishes a given entity from all others. 2. (Operator) Equality. 3. (Logic) Equality; also, a tautology of the form (p) ≡ (q) (the parentheses enclosing p and q here might not be needed in practice). 4. (Comparison) A boolean expression of the form (exp1) = (exp2), where exp1 and exp2 are expressions of the same type, that’s guaranteed to evaluate to TRUE regardless of the values of any variables involved. The parentheses enclosing exp1 and exp2 in the comparison might not be needed in practice. 5. (Identity value) Let Op be a commutative dyadic operator, and assume for definiteness that Op is expressed in infix style. If there exists a value i such that i Op v and v Op i are both equal to v for all possible values v, then i is the identity, or identity value, with respect to Op (see Laws of Algebra; see also left identity; right identity). Note: Identity values are also known variously as identity elements; neutral elements; unit elements; or sometimes just as units.
Examples (fifth definition only): The dyadic operators “+”, “*”, OR, AND, EQUIV, XOR, and JOIN have identity values 0, 1, FALSE, TRUE, TRUE, FALSE, and TABLE_DEE, respectively. Note the last of these in particular; it means, to spell the point out, that r JOIN TABLE_DEE = TABLE_DEE JOIN r = r for all possible relations r. It also means that, just as the sum of no integers is zero (see aggregate operator), so the join—and hence, as a special case, the cartesian product—of no relations is TABLE_DEE (see natural join).
Continuing with the examples, the dyadic set theory union, exclusive union, and intersection operators have identity values the empty set, the empty set, and the universal set, respectively. As for the relational counterparts to these set theory operators, there’s one such identity value, in effect, for each possible relation type; thus, if the type in question is T, the identity value for both union and exclusive union is the empty relation of type T, and the identity value for intersection is the universal relation of type T.
identity projection The projection of a relation on all of its attributes. Let relation r have attributes called A1, A2, ..., An (and no others). Then the expression r{A1,A2,...,An} denotes the identity projection of r, and it returns r itself. Note: The term is also used of a relvar; for example, the expression SP{SNO,QTY,PNO} denotes the identity projection of relvar SP (and its value at any given time is the identity projection of the relation that’s the value of relvar SP at the time in question). See also nonloss decomposition.
identity restriction A restriction of a relation r that’s equal to r itself (i.e., is equal to r WHERE TRUE); especially, a restriction of the form r WHERE t, where t is a tautology, q.v. Note: The term is also used of a relvar (see the examples immediately following).
Examples: Given the sample values in Fig. 1, the expressions S WHERE STATUS ≠ 25 and S WHERE STATUS = STATUS both denote identity restrictions (the second necessarily so, because STATUS = STATUS is a tautology).
identity value See identity.
IF AND ONLY IF Same as EQUIV.
IF ... THEN ... Same as IMPLIES (more precisely, IF (p) THEN (q) is the same as, or is equivalent to, (p) IMPLIES (q)).
IFF Short for “if and only if”; hence, same as EQUIV.
image See function.
image relation In Tutorial D, the value (a relation) denoted by an image relation reference, where an image relation reference is an open expression, q.v., of the form !!r (where r in turn is a relational expression). Such an expression can appear in a WHERE clause or in the expression denoting the source for an attribute assignment within an EXTEND, SUMMARIZE, or UPDATE invocation (in each case, wherever a relational expression can appear). For definiteness, suppose the expression !!r2 appears in the boolean expression component bx of the relational expression r1 WHERE bx (other uses of image relation references are defined analogously). Relations r1 and r2 here must be joinable, q.v. Let their common attributes be called A1, A2, ..., An (n ≥ 0). In this context, then, the expression !!r2 is logically equivalent to the expression ((r2) MATCHING RELATION {TUPLE {A1 A1, A2 A2, ..., An An}}) {ALL BUT A1,A2,...,An}. In this latter expression, (a) the subexpression TUPLE {A1 A1, A2 A2, ..., An An} is a tuple selector invocation; (b) each pair within that tuple selector invocation is of the form Ai Ai (i = 1, 2, ..., n), where the first Ai is an attribute name and the second is an attribute reference, being a reference to the attribute of that name within r1; (c) that attribute reference Ai denotes the value of attribute Ai within “the current tuple” of r1; (d) “the current tuple” of r1 is the tuple of r1 that’s currently being processed. For further explanation, see the example below.
Note: In mathematics the expression “n!” (n factorial) is often pronounced “n bang” (see factorial); hence the symbol “!!” might reasonably be pronounced “bang bang” or “double bang.” Alternatively, the expression “!!r” might be pronounced “image in r [of the current tuple].”
Example: The expression
S WHERE ( !!SP ) { PNO } = P { PNO }
yields a relation with heading the same as that of relvar S and body consisting of all possible tuples <sno,sn,st,sc> from the current value of relvar S such that supplier sno supplies all parts mentioned in the current vaue of relvar P. (Given the sample values of Fig. 1, the result contains just the tuple for supplier S1.) The expression overall is logically equivalent to this one:
S WHERE ( ( SP MATCHING RELATION { TUPLE { SNO SNO } } )
{ ALL BUT SNO } ) { PNO } = P { PNO }
To elaborate: Let s and sp be the current values of relvars S and SP, respectively. For a given tuple t in s, then, the expression—actually a relation selector invocation—RELATION {TUPLE {SNO SNO}} evaluates to a relation with just one attribute, SNO, and just one tuple, and that tuple contains just the SNO value from t. So the corresponding image relation within SP—i.e., the one corresponding to tuple t, denoted by the expression !!SP—contains just those tuples of SP that match that tuple t, projected on {PNO,QTY} (equivalently, projected on {ALL BUT SNO}). The projection (!!SP){PNO} thus evaluates to a relation ps, say, with just one attribute, PNO, giving part numbers for all parts supplied by the supplier corresponding to tuple t. For that supplier, the boolean expression (!!SP){PNO} = P{PNO} then tests the corresponding relation ps to see if it’s equal to the projection of the current value of P on {PNO}. That test will give TRUE if and only if the supplier corresponding to tuple t currently supplies all parts currently mentioned in P.
Here now is an example of the use of an image relation with EXTEND:
EXTEND S { SNO } : { CT := COUNT ( !!SP ) }
This expression denotes a certain summarization (q.v.); it yields 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 one such supplier number, together with a count of the number of times the supplier number in question currently appears in relvar SP (the expression !!SP is, again, shorthand for the expression (SP MATCHING RELATION {TUPLE {SNO SNO}}) {ALL BUT SNO}). 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.
image relation reference An open relational expression of the form !!r, where r in turn is a relational expression (and the symbol “!!” is usually pronounced “bang bang” or “double bang”). Since it’s an open expression, an image relation reference can appear only in certain limited contexts. See image relation.
immediate checking Checking a database constraint whenever an update is performed that might cause it to be violated. All database constraint checking is immediate in the relational model. Contrast deferred checking.
immediate constraint A database constraint for which the checking is immediate (see immediate checking). All database constraints are immediate in the relational model. Contrast deferred constraint.
immutable object OO term for a value (contrast mutable object).
impedance mismatch Term sometimes used, especially in OO contexts, to refer to—among quite a number of other things—the problems that can arise if the types used inside the database differ from those available outside.
implementation A physical realization on a physical computer system of the abstract machine that constitutes some given data model (in the first sense of that term, q.v.). In the interest of physical data independence, the model and its implementation should be kept rigidly apart; that is, the model should have nothing whatsoever to say about any aspect of implementation.
implementation defined Term used, in the SQL standard in particular, to refer to a feature whose specifics can vary from one implementation to another but do at least have to be defined for any individual implementation. In other words, the implementation is free to decide how it will implement the feature in question, but the result of that decision does have to be documented. An SQL example is the maximum length of a character string.
implementation dependent Term used, in the SQL standard in particular, to refer to a feature whose specifics can vary from one implementation to another and don’t even have to be defined for any individual implementation. In other words, the term effectively means “undefined”; the implementation is free to decide how it will implement the feature in question, and the result of that decision doesn’t even have to be documented (it might vary from release to release, or possibly more frequently still). An SQL example is the full effect of an ORDER BY clause, if the specifications in that clause fail to specify a total ordering, q.v.
implication If and only if p and q are predicates, the implication (p) IMPLIES (q) is a predicate also. Let (ip) IMPLIES (iq) be an invocation of that predicate, where ip and iq are invocations of p and q, respectively. Then that invocation (ip) IMPLIES (iq) evaluates to TRUE if and only if ip evaluates to FALSE or iq evaluates to TRUE or both. (In other words, (p) IMPLIES (q) is logically equivalent to (NOT(p)) OR (q).) Note: In the predicate (p) IMPLIES (q), p and q are the antecedent and the consequent, respectively; likewise, in the invocation (ip) IMPLIES (iq), ip and iq are the antecedent and the consequent, respectively. The parentheses enclosing p and q in the predicate, and ip and iq in the invocation, might not be needed in practice.
Examples: For people with no training in formal logic, implication can be notoriously difficult to come to grips with. Consider, e.g., the proposition
( 2 + 2 = 4 ) IMPLIES ( the sun is a star )
or, in more user friendly terms,
IF ( 2 + 2 = 4 ) THEN ( the sun is a star )
This proposition evaluates to TRUE, because the antecedent and the consequent are both true; yet whether the sun is a star clearly has nothing to do with whether 2+2 = 4, so what does the implication really “mean”? The following observations might help. Of the 16 available dyadic connectives (see connective), some but not all are given common names such as AND and OR. But those names are really nothing more than a mnemonic device—they don’t have any intrinsic meaning, they’re chosen simply because the connectives so named have behavior that’s similar to (not necessarily the same as) that of their natural language counterparts. In particular, the connective called IMPLIES has, of those 16 connectives, behavior that most closely resembles that of implication as usually understood in natural language. But nobody would or should claim that the two are the same thing. In fact, of course, the connectives are defined purely formally—that is, they’re defined purely in terms of the truth values, not the meanings, of their arguments (viz., the antecedent and consequent, in the case of IMPLIES)—whereas the same obviously can’t be said of their natural language counterparts.
By way of another example, the proposition
IF ( 2 + 2 = 5 ) THEN ( Elvis lives )
also—perhaps even more counterintuitively—evaluates to TRUE, because the antecedent is false; yet whether Elvis is alive clearly has nothing to do with whether 2+2 = 5. Again, part of the justification (for the fact that the implication evaluates to TRUE, that is) is just that IMPLIES is formally defined. In this case, however, there’s another argument that might be a little more satisfying in the database context specifically. Suppose the suppliers-and-parts database is subject to the constraint that all red parts must be stored in London (constraint C2 from the examples under database constraint). Formally, that constraint is a logical implication:
IF ( COLOR = COLOR('Red') ) THEN ( CITY = 'London' )
Obviously we don’t want this constraint to be violated by a part that isn’t red. It follows that we want the expression overall—which, as previously stated, is a logical implication—to evaluate to TRUE if the antecedent evaluates to FALSE.
implicit dependency A dependency—e.g., an FD or JD, or some more general constraint—that isn’t explicitly declared for some relvar but is implied by those that are (and therefore holds in that relvar, implicitly). Contrast explicit dependency.
implied by FDs Given a set s of FDs, a given FD is implied by s if and only if it’s a logical consequence of the FDs in s according to Armstrong’s axioms, q.v.
implied by key(s) Same as implied by superkey(s).
implied by superkey(s) See FD implied by a superkey; JD implied by superkeys; MVD implied by a superkey.
IMPLIES A connective, q.v. (see implication).
improper inclusion Set s1 improperly includes set s2, and set s2 is improperly included in set s1, if and only if s1 and s2 are the same set.
improper subkey A subkey that’s not a proper subkey; in other words, a key.
improper subset Set s2 is an improper subset of set s1 if and only if s2 and s1 are the same set.
improper superkey A superkey that’s not a proper superkey; in other words, a key.
improper superset Set s1 is an improper superset of set s2 if and only if s1 and s2 are the same set.
included DELETE Loosely, an operator, I_DELETE (shorthand for a certain relational assignment), that deletes specified tuples from a specified relvar, just so long as the tuples in question do currently appear in that relvar. The syntax is:
I_DELETE R rx
Here R is a relvar reference (syntactically, just a relvar name) and rx is a relational expression (denoting some relation r of the same type as R), and the effect is to delete the tuples of r from R, just so long as those tuples do currently appear in R. In other words, the DELETE invocation just shown is shorthand for the following explicit assignment:
R := R I_MINUS rx
It follows that an attempt via I_DELETE to delete a tuple that’s not present in the first place is an error (contrast DELETE).
Example: The statement
I_DELETE SP RELATION
{ TUPLE { SNO SNO('S3') , PNO PNO('P2') , QTY QTY(200) } ,
TUPLE { SNO SNO('S1') , PNO PNO('P1') , QTY QTY(400) } } ;
is shorthand for the following relational assignment statement:
SP := SP I_MINUS RELATION
{ TUPLE { SNO SNO('S3') , PNO PNO('P2') , QTY QTY(200) } ,
TUPLE { SNO SNO('S1') , PNO PNO('P1') , QTY QTY(400) } } ;
Given the sample values shown in Fig. 1, this assignment will fail—more precisely, the implicit I_MINUS invocation will fail—and no updating will be done, because the tuple <S1,P1,400> doesn’t currently appear in relvar SP.
included difference A variant on the relational difference operator, q.v., for which the second operand relation is required to be included in the first, meaning that every tuple appearing in the second relation also appears in the first. In other words, if (a) relations r1 and r2 are of the same type T, and (b) no tuple appears in r2 and not in r1, then (and only then) the expression r1 I_MINUS r2 denotes the included difference between r1 and r2 (in that order), and it reduces to r1 MINUS r2. Note: A version of this operator could also be defined to apply to sets in general as well as relations in particular.
Example: Consider the expression S{CITY} I_MINUS P{CITY}. If the current values of relvars S and P are as shown in Fig. 1, this expression will raise a run-time error, because not every part city is also a supplier city. If such were not the case, however, the expression would then be logically equivalent to S{CITY} MINUS P{CITY}.
included MINUS See included difference.
inclusion See bag; relational inclusion; set inclusion.
inclusion dependency An expression of the form rx ⊆ ry, where rx and ry are relational expressions of the same type; it can be read as “The relation denoted by rx must be included in the relation denoted by ry.” Note that foreign key constraints (q.v.) and equality dependencies (q.v.) are both special cases.
Example: Suppose the suppliers-and-parts database is subject to a constraint to the effect that no part can be stored in a city unless there’s at least one supplier in that city:
CONSTRAINT INDX P { CITY } ⊆ S { CITY } ;
/* every part city must also be a supplier city */
This constraint is an inclusion dependency (IND for short). Note, however, that it’s not satisfied by the sample values shown in Fig. 1.
Note: Actually, constraint INDX here is an example of an important special case of INDs in general. That special case can be defined as follows. Let R1 and R2 be relvars, not necessarily distinct. Let X1 and X2 be a subset of the heading of R1 and a subset of the heading of R2, respectively, such that there exists a possibly empty set of attribute renamings on R1 that maps X1 into X1′, say, where X1′ and X2 contain exactly the same attributes (in other words, X1′ and X2 are in fact one and the same). Further, let R1 and R2 be subject to the constraint that, at all times, every tuple t2 in R2 has an X2 value that’s the X1′ value for at least one tuple t1 in R1 at the time in question. Then that constraint is an IND “on” R1 and R2, and R2 and R1 are the source relvar and corresponding target relvar, respectively, for that IND.
inclusive OR Term sometimes used as a synonym for OR, used primarily to distinguish it from exclusive OR, q.v.
inclusive union Term sometimes used as a synonym for union, used primarily to distinguish it from exclusive union, q.v.
Incoherent Principle See Principle of Incoherence.
inconsistency See consistency.
inconsistent Not consistent, q.v.
IND Inclusion dependency.
independent projection See FD preservation.
index A specific kind of physical access path; hence, an implementation construct.
indirect proof See proof.
indirect reasoning See modus tollens.
indiscernibility Lack of discernibility; not to be confused with interchangeability. See Principle of Identity of Indiscernibles; Principle of Interchangeability.
individual constant (Logic) A symbol denoting a value (in effect, a literal in the programming language sense, q.v.); loosely, a value. Intuitively, we might say the individual constants available in a given formal system are what that system is “about.” For example, we might say that ordinary arithmetic is “about” the individual constants 0, 1, 2, etc.
inference rule A rule for deriving a conclusion (i.e., a theorem) from a set of premises (i.e., other theorems, possibly axioms). The derivation process is known as inference. See also Armstrong’s axioms; constraint inference; key inference; logical system; relation type inference; tuple type inference; type inference.
inferential equivalence Same as logical equivalence.
information equivalence Let DB1 be a set of relvars and let TC1 be the logical AND of all constraints that apply to the relvars in DB1, and let DB2 and TC2 be defined analogously. Then DB1 and DB2 are information equivalent if and only if TC1 and TC2 are such that the set of propositions represented (explicitly or implicitly) by DB1 and the set of propositions represented (explicitly or implicitly) by DB2 are one and the same—i.e., every proposition represented by DB1 is represented by DB2 and vice versa.
Example: Let DB1 and DB2 be, respectively, the set of relvars consisting of just the suppliers relvar S considered in isolation and the set of relvars consisting of relvars LS and NLS considered together, where at any given time relvar LS is equal to that restriction of S where the city is London and relvar NLS is equal to that restriction of S where the city is something other than London. Then it’s intuitively obvious that DB1 and DB2 are information equivalent.
Now let DB1 and DB2 be information equivalent sets of relvars, and let the current values of DB1 and DB2 be db1 and db2, respectively. Then:
Those values db1 and db can be said to be information equivalent in turn (certainly it’s true that every proposition represented by db1 is represented by db2 and vice versa). In other words, the notion of information equivalence can be extended to apply to sets of relations as well as to sets of relvars.
If db1 and db2 are information equivalent, then there must exist mappings that transform db1 into db2 and db2 into db1, respectively, where the mappings in question can be expressed in terms of operations of the relational algebra. Conversely, if such mappings exist, then db1 and db2 are information equivalent. Note moreover that to say that DB1 and DB2 per se are information equivalent is to say that (a) such mappings exist for all possible pairs of current values db1 and db2 of DB1 and DB2, respectively, and hence that (b) such a mapping also exists, in effect, between DB1 and DB2 as such.
For every query Q1 on db1, there must exist a query Q2 on db2 that yields the same result.
Let U1 be an update on DB1 that yields a “new” value db1′ of DB1; then there must exist an update U2 on DB2 that yields a “new” value db2′ of DB2, such that db1′ and db2′ are information equivalent. Note in particular that this observation applies to the important special case in which DB1 consists of base relvars only and DB2 consists only of views of the relvars in DB1.
Conversely, let db1 and db2 (and hence DB1 and DB2, a fortiori) not be information equivalent. Then (a) there must exist a query on db1 with no counterpart on db2 (or vice versa), and (b) there must exist an update on DB1 with no counterpart on DB2 (or vice versa). Again note in particular that these observation apply to the important special case in which DB1 consists of base relvars only and DB2 consists only of views of the relvars in DB1.
Finally, note that the definition of what it means for two sets of relvars to be information equivalent relies on an understanding of what it means for two propositions to be “the same”—or (perhaps better) what it means for two propositions to be information equivalent in turn. This state of affairs is the motivation for the following definition (which, be it noted, is tailored somewhat to the specific purpose at hand):
Two propositions are information equivalent if and only if the predicates of which they are instantiations (a) are logically equivalent, q.v., and (b) reference the same relvars.
Information Principle The principle that the only kind of variable allowed in a relational database is the relation variable—i.e., the relvar—specifically. Equivalently, a relational database contains relvars, and nothing but relvars. Yet another equivalent formulation is: At any given time, the entire information content of the database is represented in one and only one way: namely, as relations (see essentiality). Note: It has to be said that this principle isn’t very well named. It might more accurately be called The Principle of Uniform Representation, or even The Principle of Uniformity of Representation, since the crucial point about it is that it implies that all information in a relational database is represented in the same way: namely, as relations.
inheritance Type inheritance (see Part II of this dictionary), unless the context demands otherwise.
INIT See example value.
initialization Assigning an initial value to a variable—typically but not necessarily at the time the variable in question is defined—before any reference to that variable (i.e., within some expression) needs to be evaluated in order to provide a value to be used for some purpose. Note: The Third Manifesto requires all variables, relational or otherwise, to be initialized at the time they’re defined (see variable); in fact, in the case of base relvars in particular, it requires them to be initialized either (a) to a value specified explicitly as part of the operation that defines that relvar or (b) to the empty relation of the pertinent type, if no such explicit value is specified.
injection / injective 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 most one element of s1. Also known as a nonloss, injective, or “one to one into” mapping (though one to one here isn’t being used in its strict sense, q.v.).
Example: The mapping from nonnegative integers x to their squares x2 is an injection from the set of all nonnegative integers to (or into) itself.
inner join Same as join. The qualification inner is used when it’s necessary to distinguish the join in question from its outer counterpart. Outer join in turn—at least as usually understood—has to do with nulls and three-valued logic and is therefore deliberately not discussed further in this dictionary (though in fact it would be possible to define a slightly more “respectable” form of outer join that didn’t involve nulls at all).
INSERT Loosely, an operator—shorthand for a certain relational assignment—that inserts specified tuples into a specified relvar. The syntax is:
INSERT R rx
Here R is a relvar reference (syntactically, just a relvar name) and rx is a relational expression (denoting some relation r of the same type as R), and the effect is to insert the tuples of r into R. In other words, the INSERT invocation just shown is shorthand for the following explicit assignment:
R := R UNION rx
It follows that an attempt via INSERT to insert a tuple that’s already present is not considered an error (contrast disjoint INSERT).
Example: The statement
INSERT SP RELATION
{ TUPLE { SNO SNO('S3') , PNO PNO('P1') , QTY QTY(150) } ,
TUPLE { SNO SNO('S4') , PNO PNO('P5') , QTY QTY(400) } } ;
is shorthand for the following relational assignment statement:
SP := SP UNION RELATION
{ TUPLE { SNO SNO('S3') , PNO PNO('P1') , QTY QTY(150) } ,
TUPLE { SNO SNO('S4') , PNO PNO('P5') , QTY QTY(400) } } ;
Given the sample values shown in Fig. 1, however, this assignment will insert just one tuple, not two (speaking a trifle loosely), because the tuple <S4,P5,400> already appears in relvar SP.
INSERT anomaly Same as insertion anomaly.
INSERT rule A rule specifying the action to be taken automatically—typically but not necessarily a compensatory action, q.v.—to ensure that INSERT operations on a given relvar don’t violate any associated multivariable constraint, q.v. Note, however, that such automatic actions should occur, if and when logically required, regardless of the concrete syntactic form in which the original INSERT request is expressed. For example, an INSERT request expressed as a pure relational assignment (using “:=”), q.v., should nevertheless cause the action specified by the pertinent INSERT rule to be performed—assuming, of course, that such a rule has been defined in the first place.
insert set See relational assignment.
insertion anomaly Term originally used (though never very precisely defined) to refer to the fact that certain information can’t even be represented in a relvar that’s subject to FD redundancy, q.v. E.g., suppose for the sake of the example that relvar S is subject to the FD {CITY} → {STATUS}. 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 (though actually it has no effect on the specific anomaly to be discussed). Here then is an insertion anomaly: We can’t insert a tuple to say the status for Rome is 10 until we have a supplier in Rome (in other words, the design violates the goal of expressive completeness, q.v.). Note: A relvar that’s in BCNF, q.v., is guaranteed to be free of insertion anomalies in this “FD redundancy” sense.
The term insertion anomaly is also used in connection with relvars that are subject to JD redundancy, q.v.; in this case, however, the concept is more precisely defined. To be specific, let the JD J hold in relvar R; then R suffers from an insertion anomaly with respect to J if and only if there exist a relation r and a tuple t, each with the same heading as R, such that (a) r satisfies J, and (b) the relation r′ whose body is obtained from that of r by adding t satisfies R’s key constraints but violates J. Note: A relvar that’s in ETNF (q.v.) is guaranteed to be free of insertion anomalies in this “JD redundancy” sense.
Finally, this latter definition can be generalized, as follows: Relvar R suffers from an insertion anomaly if and only if (a) there exists a single-relvar constraint C on R and (b) there exist a relation r and a tuple t, each with the same heading as R, such that r satisfies C and the relation r′ whose body is obtained from that of r by adding t satisfies R’s key constraints but violates C. Note: A relvar that’s in DK/NF, q.v., is guaranteed to be free of insertion anomalies in this generalized sense.
instance 1. Term sometimes used, especially in OO contexts, as a synonym for occurrence or appearance of a value, q.v.—or possibly of a variable (?). Note: The latter possibility arises because at least some objects in at least some OO systems are really what are known in more conventional programming systems (perhaps not very appropriately) as “explicit dynamic variables.” The storage for such objects is allocated at run time by explicit program action (see constructor function). As a consequence, (a) there can be any number of “instances” of such objects in existence simultaneously at run time; (b) those “instances” have (and can have) no distinguishing name in the conventional sense; and therefore (c) those “instances” can be referenced only by their address or object ID, q.v. (which is essentially why OO systems require support for object IDs in the first place). See mutable object for further explanation. 2. An instance of a relation schema (q.v.) is any relation that conforms to the schema in question; in other words, it’s just a value (a relation) of the type represented by that schema. This usage is deprecated, however, if only because the term instance has also been used on occasion—most inappropriately!—to refer to an individual tuple within some relation.
instance variable The physical representation, q.v., of an object in OO contexts is usually assumed to consist of a set of named instance variables (also known among other things as state variables, attributes, or members), whose values at any given time together represent the overall value of the object in question at that time. Ideally, such instance variables should be visible only to implementation code (i.e., the code that implements the operators that apply to the object in question); in particular, they should be invisible to users. In practice, however, various compromises are typically made in this connection. To be more specific, instance variables are typically divided into two categories: public ones, which are visible to users (as well as, of course, to implementation code of all kinds), and private ones, which are visible only to implementation code that applies to objects of the type of the object in question (but see friendship).
Examples: Let BEGIN and END be public instance variables, both of type POINT, for type LINE_SEG (“line segments”); then the system will typically allow the user to write expressions of the form (e.g.) LS.BEGIN and LS.END to “get” the BEGIN and END points for a given line segment LS.
Of course, the problem with public instance variables is that they effectively expose physical representations. (Note that, by definition, access to such variables must be via some special syntax—typically dot qualification, as the previous paragraph suggests—for otherwise there’s no point in distinguishing between public and private variables in the first place. See further discussion below.) So if the physical representation changes—say to the combination of MIDPOINT, LENGTH, and SLOPE, in the case of line segments—then any program that includes expressions such as LS.BEGIN and LS.END will now fail. In other words, physical data independence is lost.
But public instance variables are logically unnecessary anyway. Suppose operators GET_BEGIN, GET_END, GET_MIDPOINT, GET_LENGTH, and GET_SLOPE are defined for line segments (see GET_ operator). Then the user can “get” the begin point, the end point, the midpoint, and so on, for line segment LS by means of appropriate operator invocations: GET_BEGIN (LS), GET_END (LS), GET_MIDPOINT (LS), and so on. And now it makes no difference what the physical representation of line segments is—just so long as the various GET_ operators are implemented appropriately, and reimplemented appropriately if that physical representation changes. In other words, physical data independence is preserved.
instantiation 1. Loosely, an invocation of a predicate, q.v., in which (by definition) each parameter is replaced by some argument. The result of such instantiation is a proposition, q.v. Note: Actually, the logical notion of instantiation is more general than the familiar programming language notion of operator invocation. To be specific, we can instantiate an n-place predicate by substituting arguments for just m of its parameters (m ≤ n), thereby obtaining a k-place predicate, where k = n − m. If m = n, the instantiation is said to be full (and the term instantiation, unqualified, is usually taken to mean full instantiation specifically, unless the context demands otherwise); otherwise it’s said to be partial. 2. In OO contexts, the term instantiation is sometimes used to refer to the creation of a new mutable object. See constructor function.
integrity A database is in a state of integrity if and only if it satisfies all defined integrity constraints. Of course, a properly implemented DBMS can’t possibly allow the database ever to violate any defined integrity constraint, and so databases really ought to be in a state of integrity at all times (this is one possible formulation of The Golden Rule, q.v.). Note, however, that—in the relational model, at least—“at all times” effectively means at statement boundaries (or, loosely, “at semicolons”), not merely at transaction boundaries. In other words, all integrity checking is immediate in the relational model. See also consistency.
integrity constraint A named boolean expression, or something equivalent to such an expression, that’s required to be satisfied—i.e., to evaluate to TRUE—at all times, where “at all times” effectively means at statement boundaries (or, loosely, “at semicolons”), not merely at transaction boundaries. There are two basic kinds, database constraints and type constraints, q.v. (but see attribute constraint; relvar constraint; tuple constraint); however, the term is usually taken to mean a database constraint specifically, unless the context demands otherwise. The DBMS will reject any attempt to perform an update that would otherwise cause some integrity constraint to be violated (i.e., to evaluate to FALSE). Note: Type constraints effectively constrain selector invocations (see selector). By contrast, database constraints effectively constrain database update operations—and since database update operations apply, by definition, to relvars specifically (i.e., not to relations as such), it follows that such constraints can be thought of as applying to relvars specifically too (i.e., anything constrained by a database integrity constraint must be a relvar, not a relation, by definition).
intelligent key A single-attribute key whose values, in addition to their main purpose of serving as unique identifiers (typically for certain real world “entities,” q.v.), carry some kind of encoded information embedded within themselves. Contrast surrogate key.
Example: Let parts purchased from domestic suppliers be assigned part numbers in the range 0-499 and parts purchased elsewhere be assigned part numbers in the range 500-999. Now assume the 501st different kind of part is purchased from a domestic supplier. Clearly, the part numbering scheme will now have to be revised, and any application that previously relied on the fact that parts purchased domestically have numbers less than 500 will now fail. As this example suggests, intelligent keys should be used with caution. (It’s tempting to suggest, therefore, that “intelligent keys” might better be referred to as “unintelligent keys.”) Note: Actually, similar remarks apply to the encoding of information within values of any attribute, not just “entity identifying” attributes specifically, but “entity identifying” attributes do seem to be particularly prone to this kind of abuse.
intended interpretation For a given relvar, the informal, user understood meaning; in other words, the relvar predicate, q.v. Also referred to as interpretation, unqualified. Contrast relvar constraint (second definition).
intension For a given relation or relvar, the intended interpretation, or sometimes the heading. Note the spelling! Contrast extension (fourth definition).
Interchangeability Principle (Of base and virtual relvars) The principle that there should be no arbitrary and unnecessary distinctions between base and virtual relvars; i.e., virtual relvars should “look and feel” just like base ones so far as users are concerned. See also information equivalence; view updating.
interdependent projections See FD preservation.
interface (Without inheritance) A shared boundary between two systems. Often used more specifically to refer to the specification signature, q.v., for some operator; sometimes also used, especially in OO contexts, to refer to the complete set of operators supported by values and variables of some particular type. (As indicated, this latter use of the term occurs in connection with OO systems in particular. Note, however, that some OO systems also use it to mean something else entirely. See Part II of this dictionary.)
internal predicate The total relvar constraint for a given relvar. The term is deprecated because it’s at least arguably misleading (since relvar constraints are in fact not general predicates but, more specifically, propositions).
interpretation Same as intended interpretation.
INTERSECT See intersection.
intersection (Without inheritance) 1. (Dyadic case) Let relations r1 and r2 be of the same type T. Then (and only then) the expression r1 INTERSECT r2 denotes the intersection 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 each 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 INTERSECT {r1,r2,...,rn}denotes the intersection 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 each 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 universal relation, q.v., of that type. Note too that the relational intersection operator differs in certain respects from the mathematical or set theory operator of the same name, q.v.; in fact, it’s a special case of join, q.v. Note finally that INTERSECT can also be used as an aggregate operator, q.v.
Example: The expression S{CITY} INTERSECT P{CITY} denotes the intersection 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 intersection 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 both s{CITY} and p{CITY}—meaning c is a current supplier city that’s also a current part city. Note that the expression S{CITY} INTERSECT P{CITY} is logically equivalent to the expression S{CITY} JOIN P{CITY}.
intersection (bag theory) See bag.
intersection (set theory) The intersection of two sets s1 and s2, s1 ∩ s2 (where the symbol “∩” can conveniently be pronounced “cap”), is the set of all elements x such that x is an element of s1 and an element of s2. Note: This definition can obviously be extended to apply to any number of sets.
intersection star See bag.
into (Of a function; preposition used as an adjective) Having range equal to some proper subset of the codomain (contrast onto). See injection.
inverse See Laws of Algebra.
Examples: 1. In ordinary arithmetic, the identities for “+” and “*” are 0 and 1, respectively (see identity). As a consequence, (a) for “+”, the inverse of x is −x; (b) for “*”, the inverse of x is 1/x (unless x is 0, the only number that has no multiplicative inverse). 2. In two-valued logic, the identities for OR and AND are FALSE and TRUE, respectively (again, see identity). As a consequence, (a) for OR, FALSE is its own inverse but TRUE has no inverse (there’s no truth value v such that TRUE OR v yields FALSE); (b) for AND, TRUE is its own inverse but FALSE has no inverse (there’s no truth value v such that FALSE AND v yields TRUE). 3. Also in two-valued logic, the identities for EQUIV and XOR are TRUE and FALSE, respectively (again, see identity). As a consequence, for both operators, each of TRUE and FALSE is its own inverse. (To spell out the details: TRUE EQUIV TRUE and FALSE EQUIV FALSE both yield TRUE, while TRUE XOR TRUE and FALSE XOR FALSE both yield FALSE.)
invocation 1. (Operator) See read-only operator; update operator. 2. (Predicate) See instantiation.
invocation signature See RETURNS.
involution 1. (Logic) If v is a truth value, then the negation of the negation of v is equal to v. (It follows that, in logic, adjacent NOTs “cancel out”—that is, the predicate NOT(NOT(p)) can be simplified to just (p).) 2. (Set theory) If s is a set, then the complement of the complement of s is equal to s.
irrational number A real number (q.v.) that can’t be expressed as the ratio of two integers. Examples include π and 
. Irrational numbers have the property that, in decimal notation, the fractional part of such a number consists of an infinite, nonrepeating sequence of decimal digits (e.g., π = 3.14159..., = 1.41421...). Contrast rational number.
irreducible 1. (Of a key) See candidate key. 2. (Of a relvar) Sixth normal form. 3. (Of an FD) See irreducible FD. 4. (Of a set of FDs) See irreducible cover. 5. (Of a JD) See irreducible JD. 6. (Of an MVD) See irreducible MVD.
irreducible cover Let s1 and s2 be sets of FDs. Then s2 is an irreducible cover for s1 if and only if it’s a cover for s1 (q.v.) and, for every FD in s2, (a) the dependant consists of a single attribute; (b) no attribute can be discarded from the determinant without losing the property that s2 is a cover for s1; and (c) the FD can’t be discarded from s2 without losing the property that s2 is a cover for s1.
irreducible FD The FD X → Y is irreducible with respect to relvar R (or just irreducible, if R is understood) if and only if it holds in R and X′ → Y doesn’t hold in R for any proper subset X′ of X.
Examples: Of the FDs {SNO} → {CITY} and {SNO,STATUS} → {CITY}, both of which hold in relvar S, the first is irreducible and the second isn’t. Likewise, of the FDs {SNO,PNO} → {QTY} and {SNO,PNO,QTY} → {QTY}, both of which hold in relvar SP, the first is irreducible and the second isn’t.
irreducible JD Let 
{X1,X2,...,Xn} be a JD, J say, that holds in relvar R, and let there be no proper subset {Y1,Y2,...,Ym} of {X1,X2,...,Xn} such that the JD {Y1,Y2,...,Ym} also holds in R; then J is irreducible with respect to R (or just irreducible, if R is understood). Note: If some component Xi is irrelevant (q.v.) in J, then J is certainly reducible with respect to every relvar in which it holds; however, J can still be reducible with respect to some relvar even if all components are relevant (see the examples immediately following).
Examples: The following JD, which holds in relvar S, is reducible, because the {CITY,STATUS} component can be dropped without significant loss:
{ { SNO , SNAME , STATUS } , { SNO , CITY } , { CITY , STATUS } }
By contrast, the followingJD—i.e., the JD that results when the {CITY,STATUS} component is dropped from the JD just shown—(a) still holds in relvar S but (b) is irreducible:
{ { SNO , SNAME , STATUS } , { SNO , CITY } }
irreducible MVD Since—to speak a trifle loosely—(a) an MVD is basically just a JD with exactly two components and (b) a JD is reducible if and only if one or more of its components can be dropped without loss, (c) the notion of reducibility doesn’t seem to make much sense in connection with MVDs, and hence (d) the notion of irreducibility doesn’t seem to make much sense either.
irreducibly dependent (Of a dependant in an FD) Let X and Y be subsets of the heading of some relvar R. Then Y is irreducibly dependent on X with respect to R if and only if the FD X → Y is irreducible with respect to R.
Examples: In relvar S, {STATUS} is irreducibly dependent on {SNO}; it’s also dependent on {SNO,CITY}, but not irreducibly so. Similarly, in relvar SP, {QTY} is irreducibly dependent on {SNO,PNO}; it’s also dependent on {SNO,PNO,QTY}, but not irreducibly so.
irreducibly equivalent (Of sets of FDs) Let s1 and s2 be sets of FDs. Then s1 and s2 are irreducibly equivalent if and only if each is an irreducible cover for the other.
irrelevant component (Of a JD) Let {X1,X2,..., Xn} be a JD, J say; then Xi is irrelevant in J if and only if (a) there exists some Xj in J such that Xi is a proper subset of Xj or (b) there exists some Xj in J (i > j) such that Xi = Xj. Note: If we assume (as we normally do in practice) that the commalist of components X1, X2, ..., Xn of J contains no duplicates, we can drop part (b) of this definition. See also irreducible JD.
IS_EMPTY A Tutorial D operator that returns TRUE or FALSE according as its argument relation is empty or not.
Examples: See the examples under database constraint and elsewhere.
IS_NOT_EMPTY A Tutorial D operator that returns FALSE or TRUE according as its argument relation is empty or not. In other words, the expression IS_NOT_EMPTY(rx), where rx is a relational expression, is logically equivalent to the expression NOT (IS_EMPTY(rx)). Note: SQL supports the IS_NOT_EMPTY operator fairly directly, but it calls it EXISTS.
isomorphism Let X and Y be sets, not necessarily distinct, and let f be a bijective mapping from X to Y. Let OpX be an operator that takes elements of X as its operands and returns an element of X as its result. Then the mapping f is an isomorphism if and only if, for all such operators OpX, there exists an analogous operator OpY that takes elements of Y as its operands and returns an element of Y as its result such that, whenever (a) OpX applied to x1, x2, ..., xn returns x, then (b) OpY applied to y1, y2, ..., yn returns y, where (c) y1, y2, ..., yn, and y are the images of x1, x2, ..., xn, and x, respectively, under f. In other words, an isomorphism is a bijective mapping that preserves the algebraic structure of the domain X in the codomain Y. Note: If the bijective mapping f is an isomorphism, its inverse is an isomorphism also.
Example: Let X be the set {EVEN,ODD}—the names are meant to be suggestive—and let operators “+” and “*” be defined as follows:
+ │ EVEN ODD * │ EVEN ODD
─────┼─────────── ─────┼────────────
EVEN │ EVEN ODD EVEN │ EVEN EVEN
ODD │ ODD EVEN ODD │ EVEN ODD
Now let Y be the set {TRUE,FALSE} and let f be a bijection from X to Y that maps EVEN and ODD to TRUE and FALSE, respectively. Further, let the logical operators EQUIV and OR correspond to “+” and “*”, respectively. Then f is an isomorphism from X, with its operators “+” and “*”, to Y with its operators EQUIV and OR.
JD Join dependency.
JD implied by keys See JD implied by superkeys.
JD implied by superkeys Let relvar R have heading H and let {X1,X2,...,Xn} be a JD, J say, with respect to H. Then J is implied by the superkeys of R if and only if every relation r that satisfies R’s superkey constraints also satisfies J—equivalently, if and only if the following membership algorithm succeeds. Let S be the set {X1,X2,...,Xn}. If two distinct members of S both include the same superkey of R, replace them in S by their union, and repeat this process until no further such replacements are possible. Then the algorithm succeeds (and J is therefore implied by superkeys of R) if and only if S now contains H as a member. See fifth normal form. Note: The term superkey could be replaced by the term key throughout the foregoing definition without making any substantive difference. Note too that the membership algorithm succeeds trivially if J itself is trivial.
Examples: Let relvar R have attributes A, B, C, D, E, and F (and no others); let AB denote the set of attributes {A,B}, and similarly for other attribute name combinations (also, let single attribute names denote the corresponding singleton sets—e.g., let A denote the set {A}); finally, let R have keys A, B, and CD (and no others). Then the following are all JDs that are implied by the superkeys of R (and they all hold in R, necessarily):
{ AB , ACDE , BF } { ABC , ACD , BEF , EF } { AB , AC , ADEF }
Observe in the second of these examples that the component EF is irrelevant, q.v., and could thus be dropped from the JD without significant loss.
Here by contrast are some JDs that aren’t implied by the superkeys of R:
{ ABC , CDEF } { ABD , ACDE , DF }
Note that the first of these two JDs necessarily fails to hold in relvar R, because C isn’t a key. The second might or might not hold. If it does, then R isn’t in 5NF; conversely, if R is in 5NF, then that JD can’t possibly hold.
Note: It’s worth elaborating on the intuition behind the foregoing. Using notation as in the formal definition, and using J to denote the JD {X1,X2,...,Xn}, the basic idea is as follows. Let the current value of relvar R be relation r, and for some i and j (i ≠ j) let ri and rj be the projections of r on Xi and Xj, respectively. If Xi and Xj both include the same superkey of R, then the join rk of ri and rj—whose heading Xk will be the set theory union of Xi and Xj—will be strictly one to one, and so ri and rj can be replaced by rk without loss of information. (At the same time, Xi and Xj can be replaced in J by Xk.) Since the original version of J was implied by the superkeys of R, performing such replacements repeatedly will, by definition, eventually yield a relation (a) that’s equal to the original relation r (because no information will be lost at any step in the process), and in particular (b) will therefore have a heading equal to the entire heading H of r.
The foregoing argument shows that every relation satisfies every JD that’s implied by the pertinent superkeys, and this fact is appealed to in the definition of 5NF (q.v.): Essentially, a relation conforms to the requirements for 5NF if and only if it fails to satisfy any additional JDs, over and above those implied by the pertinent superkeys. Note, however, that the concept of 5NF applies to relvars, while the foregoing intuitive explanation is expressed in terms of relations, not relvars.
JD redundancy Relvar R is subject to JD redundancy if and only if some tuple forcing JD (q.v.) holds in R.
JOIN See natural join.
join Natural join, q.v. (unless the context demands otherwise).
join dependency Let H be a heading; then a join dependency (JD) with respect to H is an expression of the form {X1,X2,...,Xn}, such that the set theory union of X1, X2, ..., Xn is equal to H. (The qualifying phrase “with respect to H” can be omitted if H is understood.) The expression overall can be read as “star X1, X2, ..., Xn.” Note: The concept of join dependency is a generalization of the concept of multivalued dependency (MVD); that is, every MVD is a JD, but some JDs aren’t MVDs. (To be specific, an MVD is a JD with exactly two components, thus: {X1,X2}.) Informally, however, it’s common to use the term JD to mean a JD that isn’t an MVD.
Note: Different writers use different symbols to denote a JD; in this dictionary we use a special kind of star (“”), but the “bow tie” symbol “⋈” is more often encountered in recent research literature (see natural join).
Let relation r have heading H and let {X1,X2,...,Xn} be a JD, J say, with respect to H. If r is equal to the join of its projections on X1, X2, …, Xn, then r satisfies J; otherwise r violates J. Now let relvar R have heading H. Then R is subject to the JD J—equivalently, the JD J holds in R—if and only if every relation r that can ever be assigned to R satisfies that JD J. The JDs that hold in relvar R are the JDs of R, and they serve as constraints (q.v.) on R.
Note that JDs are defined with respect to some heading, not with respect to some relation or some relvar. Note too that from a formal point of view, a JD is just an expression: an expression that, when interpreted with respect to some specific relation, becomes a proposition that, by definition, evaluates to either TRUE or FALSE. Now, it’s common informally to define {X1,X2,...,Xn} to be a JD only if it actually holds in the pertinent relvar—but that definition leaves no way of saying a given JD fails to hold in some relvar, because, by that definition, a JD that fails to hold isn’t a JD in the first place. Note finally that it’s immediate from the definition that relvar R can be nonloss decomposed into its projections on X1, X2, ..., and Xn if and only if the JD {X1,X2,...,Xn} holds in R.
Examples: The suppliers relvar S is subject to the JD
{ { SNO , SNAME } , { SNO , STATUS } , { SNO , CITY } }
because every relation that’s a legal value for S is equal to the join of its projections on {SNO,SNAME}, {SNO,STATUS}, and {SNO,CITY}; thus, relvar S could be nonloss decomposed into those three projections. Of course, there’s no requirement that this decomposition actually be performed—whether it should or not depends on whether there’s any advantage to be gained by doing so.
By way of a second example, observe that, thanks to Heath’s Theorem (q.v.), if a certain FD holds in a given relvar, then a certain JD holds in that relvar as well. (In other words, every FD implies some JD.) For example, the FD {SNO} → {STATUS} holds in relvar S, and hence the following JD holds as well:
{ { SNO , STATUS } , { SNO , SNAME , CITY } }
So too do both of these JDs, incidentally:
{ { SNO , STATUS } , { SNO , STATUS } , { SNO , SNAME , CITY } } { { SNO , STATUS } , { STATUS } , { SNO , SNAME , CITY } }
In each of these latter JDs, however, one of the components can obviously be dropped; in other words, these JDs aren’t irreducible, q.v.
join trap See connection trap.
joinable (Without inheritance) 1. (Dyadic case) Relations r1 and r2 are joinable if and only if attributes with the same name are of the same type—equivalently, if and only if the set theory union of their headings is a legal heading. Note that dyadic joinability isn’t transitive (q.v.); that is, just because (a) r1 and r2 are joinable and (b) r2 and r3 are joinable, it doesn’t necessarily follow that (c) r1 and r3 are joinable. 2. (N-adic case) Relations r1, r2, ..., rn (n ≥ 0) are joinable—sometimes n-way joinable, for emphasis—if and only if for all i and j, relations ri and rj are joinable (1 ≤ i ≤ n, 1 ≤ j ≤ n).
Examples: Let relation r1 have attributes called A and B (and no others), let relation r2 have attributes called B and C (and no others), and let relation r3 have attributes called C and A (and no others). Further, let attribute B in r1 and attribute B in r2 be of the same type—in other words, let them be, formally, the very same attribute—and likewise for attribute C in r2 and attribute C in r3; but let attribute A in r1 and attribute A in r3 be of different types. Then r1 and r2 are joinable, and so are r2 and r3, but r1 and r3 aren’t. (It follows that r1, r2, and r3 aren’t 3-way joinable.)
KCNF Key complete normal form.
KEY See key constraint.
key A candidate key, q.v. (unless the context demands otherwise).
key attribute An attribute of a given relvar that’s part of at least one key of that relvar. See also primary key attribute; subkey.
key complete normal form Same as redundancy free normal form.
key constraint A constraint to the effect that a given subset of the heading of a given relvar is a key (more precisely, a candidate key) for that relvar. In Tutorial D, such a constraint is defined by means of a KEY specification within the pertinent relvar definition (e.g., see the definitions for relvars S, P, and SP in the introduction to this dictionary). Note, however, that while the system certainly can and will enforce the uniqueness constraint implied by such a specification—see candidate key—it can’t in general enforce the corresponding irreducibility constraint as well; in other words, specifying KEY{K} as part of the definition of relvar R means that {K} is certainly a superkey, q.v., but not necessarily a key as such, for relvar R.
Example: Suppose we were to specify KEY{SNO,CITY} instead of KEY{SNO} in the definition of relvar S. Then the system obviously wouldn’t be able to enforce the constraint that supplier numbers as such, as opposed to supplier-number / city combinations, are unique. (On the other hand, if we were to specify both KEY{SNO,CITY} and KEY{SNO}, the system should at least be able to recognize that {SNO,CITY} is a proper superset of {SNO} and so reject the specification KEY{SNO,CITY}.)
Note: Tutorial D allows key constraints to be specified not just for relvars as such, but in fact for arbitrary relational expressions. For example, the statement
CONSTRAINT KX ( S JOIN SP ) KEY { PNO , CITY } ;
defines a constraint corresponding to the following business rule: If suppliers sx and sy (sx ≠ sy) supply the same part, then they must be in different cities. In other words, this CONSTRAINT statement can be understood as saying that if a view were to be defined with S JOIN SP as its defining expression, then the attribute combination {PNO,CITY} would be a key for that hypothetical view.
key inference The process of determining the key constraints that hold in a given derived relvar or are satisfied by a given derived relation. Key inference is a special case of constraint inference, q.v.
LAST See ordinal type.
Laws of Algebra Let A be a formal system consisting of a set s of elements x, y, z, ..., together with two distinct dyadic operators “+” and “*” (usually called addition and multiplication, respectively, though they aren’t necessarily the operators known by those names in conventional arithmetic). Then A is certainly an algebra if it abides by the following laws:
Closure laws: The set s is closed under both “+” and “*”; that is, for all x and y in s, each of the expressions x+y and x*y yields an element of s.
Commutative laws: For all x and y in s, x+y = y+x and x*y = y*x.
Associative laws: For all x, y, and z in s, x+(y+z) = (x+y)+z and x*(y*z) = (x*y)*z.
Identity laws: There exist elements 0 and 1 in s such that for all x in s, 0+x = x+0 = x and 1*x = x*1 = x. Those elements 0 and 1 are the additive identity and the multiplicative identity, respectively.
Inverse laws: For all x in s, there exist elements −x and (unless x = 0) 1/x in s such that x+(−x) = 0 and x*(1/x) = 1. Those elements −x and 1/x are the additive inverse and the multiplicative inverse, respectively (of x in each case). Note: The expressions x+(−y) and x*(1/y) are usually abbreviated x−y and x/y, respectively.
Distributive law (of “*” over “+”): For all x, y, and z in s, x*(y+z) = (x*y)+(x*z).
However, not all algebras abide by all of these laws. In the algebra of sets, for example, the “+” and “*” operators are union and intersection, respectively, and the corresponding identities are the empty set and the universal set, respectively; however, the inverse laws don’t hold (i.e., given an arbitrary set s1, in general there’s no set s2 such that the union of s1 and s2 is the empty set or the intersection of s1 and s2 is the universal set). Relational algebra likewise fails to obey the inverse laws, a fortiori.
left associativity Let Op be a dyadic operator, and assume for definiteness that Op is expressed in infix style. Then Op is left associative if and only if, for all x, y, and z, x Op y Op z can be correctly evaluated left to right (i.e., as (x Op y) Op z); similarly, it’s right associative if and only if, for all x, y, and z, it can be correctly evaluated right to left (i.e., as x Op (y Op z)). Note: In mathematics and logic, left and right associativity both reduce to just associativity, q.v., as normally understood. However, such is not necessarily the case in computing. For example, let x, y, and z be floating point numbers and let Op be “+”. In the computing context, then, it might well be the case that (x+y)+z and x+(y+z) produce different results; it might even be the case that one of these expressions raises an exception (e.g., overflow) and the other doesn’t.
left 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 i Op v is equal to v for all possible values v, then i is the left identity, or left identity value, with respect to Op. See also identity (fifth definition); right identity.
Examples: Every identity, q.v., is necessarily a left identity in particular (and also a right identity, q.v., of course). As for an example of a left identity that’s not a right identity, let the operator “” be defined in such a way that the invocation mn returns the result of dividing the integer m into the integer n; then, since 1v is equal to v for all numbers v whereas v1is not, 1 is a left identity but not a right identity with respect to “”.
left irreducible FD Same as irreducible FD. (The qualifier “left” derives from the fact that it’s the left side—i.e., the determinant—that can’t be reduced in an irreducible FD.)
less-than join A theta join, q.v., in which theta is “<”.
lexical (Of a language, sentence, etc.) Pertaining to individual words and other basic symbols (punctuation, etc.). Contrast semantic; syntactic.
linear ordering Same as total ordering. Contrast cyclic ordering.
literal 1. (Logic) A simple proposition, q.v., or its negation; a simple predicate, q.v., or its negation. Note that, by definition, a literal in this sense is in both conjunctive normal form, q.v., and disjunctive normal form, q.v. 2. (Programming languages) Loosely, a self-defining symbol; a symbol that denotes a value that can be determined at compile time. More precisely, a literal is a symbol that denotes a value that’s fixed and determined by the symbol in question (and the type of that value is therefore also fixed and determined by the symbol in question). Every value of every type, tuple and relation types included, is—in fact, must be—denotable by means of some literal. Note: A literal in the programming language sense is a special case of a selector invocation (see selector); to be precise, a literal is a selector invocation if and only if all of the argument expressions in that selector invocation are literals in turn. Note too that there’s a logical difference between a literal as such and the value it denotes (see constant, second definition). Be aware, however, that some systems, including certain OO systems in particular, do use the term literal to mean a value as such. Caveat lector.
Examples (second definition only):
4 /* a literal of type INTEGER */
'ABC' /* a literal of type CHAR */
FALSE /* a literal of type BOOLEAN */
SNO('S1') /* a literal of type SNO */
TUPLE { SNO SNO('S1') , PNO PNO('P1') , QTY QTY(300) }
/* a literal of type TUPLE {SNO SNO, PNO PNO, QTY QTY}) */
RELATION { TUPLE { SNO SNO('S1') , PNO PNO('P1') , QTY QTY(300) } ,
{ TUPLE { SNO SNO('S5') , PNO PNO('P6') , QTY QTY(100) } }
/* a literal of type RELATION {SNO SNO, PNO PNO, QTY QTY}*/
log A record in persistent storage of all of the updates that have been made to the database since some prescribed time (possibly the time when the system was first installed), showing for each update in question (a) the value of the updated object before and after that update was done, (b) the time when that update was done, (c) the user and transaction responsible for that update, and (d) almost certainly other things besides. The log is used as a basis (a) for undoing updates if some transaction fails to reach a successful conclusion, and also (b) for redoing updates if a system failure causes the updates in question to be lost. See also audit trail.
logic The science or scientific study of the methods and principles used in valid reasoning.
logic system / logical system / system of logic Terms used interchangeably to mean, loosely, a system consisting of axioms and inference rules, together with a set of theorems that can be derived from the former by means of the latter. More precisely, a logic system consists of (a) a set of symbols (connectives, punctuation symbols, variable names, “individual constants,” etc.); (b) a set of grammatical rules for forming “sentences” of the system; (c) a set of given sentences (the axioms); and (d) a set of rules for inferring “new” sentences from “old” ones. See also connective; individual constant; inference rule; truth functional completeness; and elsewhere.
Examples: Propositional logic and predicate logic are both systems of logic, in which the legal sentences are propositions and predicates, respectively. The relational model is another example, in which the legal “sentences” are relational algebra or relational calculus expressions.
logic variable A variable that can appear either bound or free in expressions of predicate logic (see bound variable; free variable); not to be confused with a logical variable, q.v. See also range variable.
logical access path See access path.
logical data independence See data independence.
logical database design The process, or the result of the process, of deciding what relvars some database should contain, what attributes they should have, and what constraints they should be subject to. Ideally, the goal of the logical design process is to produce a design that’s independent of all considerations having to do either with physical implementation or with specific applications—the latter objective being desirable for the very good reason that it’s generally not the case that all uses to which the database will be put are known at design time. Overall, the logical design process can be summed up as one of (a) pinning down the relvar predicates and other business rules (q.v.) as carefully as possible, albeit necessarily somewhat informally, and then (b) mapping those informal predicates and rules to specific relvars and formal constraints—preferably in such a way as to ensure the result involves no uncontrolled redundancy, q.v.
logical design Same as logical database design (if the context demands).
logical difference A difference that’s logical, not (e.g.) merely psychological, in nature. The term derives from a maxim of Wittgenstein’s: All logical differences are big differences. The relevance of this maxim for database systems in particular, and in fact for computing systems in general, can be explained as follows: The relational model is a formal system (just as a DBMS is, or an operating system, or indeed any computer program). Formal systems are what computers are—or can be made to be—good at. And since the basis of any formal system is logic, it follows that in such contexts differences that are logical in nature are very important ones, and we need to pay careful attention to them. In those same contexts, by contrast, differences that aren’t logical in nature are comparatively unimportant; in programming languages, for example, semantic differences are very significant, while mere syntactic differences are much less so.
Example: In Tutorial D, there’s a syntactic difference, but no semantic or logical difference, between the expressions S{SNO} MINUS SP{SNO} and S{SNO} NOT MATCHING SP. Note: Many further illustrations of, and references to, the notion of logical difference can be found elsewhere in this dictionary.
logical equivalence Two expressions are logically equivalent if and only if each is derivable from the other in accordance with the rules of the particular system of logic in effect. In conventional 2VL, for example, the expressions NOT((p) AND (q)) and (NOT (p)) OR (NOT (q)) are logically equivalent. (This equivalence—which is in fact one of De Morgan’s Laws, q.v.—can easily be shown by means of truth tables, q.v.) And in the relational algebra, the expressions A INTERSECT B and A MINUS (A MINUS B) are logically equivalent, and so are the expressions A and A INTERSECT (A UNION B). Observe in particular in this latter example that one of the expressions mentions a variable, B, that the other one doesn’t. Contrast information equivalence; truth functional equivalence.
logical expression An expression denoting a truth value.
logical implication Implication, q.v.
logical operator An operator that takes values or variables or both of type BOOLEAN as operands and either returns a value, or updates a variable, of type BOOLEAN. The connectives are an important special case.
logical variable (Programming languages) A variable of type BOOLEAN. The term is probably best avoided because of possible confusion with the term logic variable, q.v.
lossless decomposition Nonloss decomposition, q.v.
lossless join Nonloss join, q.v. The term is probably best avoided, just as the term nonloss join (q.v.) is, and for essentially the same reasons.
lossy decomposition A decomposition that isn’t nonloss.
Example: The decomposition of relvar S into its projections on {SNO,SNAME} and {SNAME,STATUS,CITY} is lossy because it isn’t guaranteed that, at all times, S is equal to the join of those projections.
lossy join A join that isn’t a nonloss join, q.v., in either sense of that term. The term is probably best avoided, just as the term nonloss join (q.v.) is, and for essentially similar reasons.
managed redundancy Same as controlled redundancy.
mandatory participation See cardinality constraint.
manual optimization See optimization.
many to many correspondence Strictly, a rule pairing two sets s1 and s2 (not necessarily distinct) such that each element of s1 corresponds to at least one element of s2 and each element of s2 corresponds to at least one element of s1; equivalently, that pairing itself. Often used loosely, however, to mean a pairing such that either (a) each element of s1 corresponds to any number of elements of s2 (possibly none at all) and each element of s2 corresponds to at least one element of s1, or (b) each element of s1 corresponds to at least one element of s2 and each element of s2 corresponds to any number of elements of s1 (possibly none at all), or (c) each element of s1 corresponds to any number of elements of s2 (possibly none at all) and each element of s2 corresponds to any number of elements of s1 (possibly none at all). The term is probably best avoided unless the intended meaning is clear.
Example (strict sense only): Let s be the set of all positive integers. Consider the pairing of positive integers x and y defined as follows: Positive integers x and y are paired if and only if they have the same number of digits in conventional decimal notation (no leading zeros). Then that pairing is a many to many correspondence from s to itself.
many to many join Let relations r1 and r2 be joinable, q.v. Then the join of r1 and r2 is said—somewhat loosely—to be many to many if and only if the pairing of tuples from r1 and r2 under the join is a many to many correspondence, q.v., in any of the senses of this latter term. Note: The foregoing definition is expressed in terms of relations, but the phrase many to many join is often applied to relvars instead of relations.
Example: The join of suppliers and parts, S JOIN P, would typically be said to be many to many, even though there might be some tuples in S that join to no tuple in P and vice versa.
many to one correspondence Strictly, a rule pairing two sets s1 and s2 (not necessarily distinct) such that each element of s1 corresponds to exactly one element of s2 and each element of s2 corresponds to at least one element of s1 (in other words, a surjection, q.v.); equivalently, that pairing itself. Often used loosely, however, to mean a pairing such that (a) each element of s1 corresponds to at most one element of s2 and each element of s2 corresponds to at least one element of s1, or (b) each element of s1 corresponds to exactly one element of s2 and each element of s2 corresponds to any number of elements of s1 (possibly none at all), or (c) each element of s1 corresponds to at most one element of s2 and each element of s2 corresponds to any number of elements of s1 (possibly none at all). The term is probably best avoided unless the intended meaning is clear.
Example (strict sense only): Let s1 and s2 be the set of all integers and the set of all nonnegative integers, respectively. Then the pairing of integers x with their absolute values ABS(x) is a many to one correspondence from s1 to s2.
many to one join Let relations r1 and r2 be joinable, q.v. Then the join of r1 and r2 is said—somewhat loosely—to be many to one if and only if the pairing of tuples from r1 and r2 under the join is a many to one correspondence, q.v., in any of the senses of this latter term. Note: The foregoing definition is expressed in terms of relations, but the phrase many to one join is often applied to relvars instead of relations.
Example: The join of shipments and suppliers, SP JOIN S, would typically be said to be many to one from SP to S, even though there might be some tuples in S that join to no tuple in SP.
many-valued logic Same as nVL, q.v., for some n > 2.
map / mapping Terms used interchangeably to mean a function, q.v. Often used—in this dictionary in particular, on occasion—to mean a function that’s a bijection (q.v.) specifically, together with its inverse.
mark See null.
MATCHING Tutorial D keyword denoting semijoin, q.v.
material equivalence Logical equivalence, q.v.
material implication Logical implication, q.v.
materialization 1. A technique for evaluating relational expressions in which intermediate result relations are produced in their entirety before being passed on as input to another operation. Contrast pipelining. 2. View materialization, q.v.
materialized view Deprecated term for a snapshot. Note the difference between (a) materialization as a technique for implementing read-only operations on views (see view materialization) and (b) a “materialized view”—i.e., a snapshot—as such. The former is an implementation technique and should have no logical consequences for the user at all (i.e., users shouldn’t need to know whether a given read-only operation on a given view is implemented by materialization). By contrast, the latter is an issue that certainly does concern the user; i.e., the user certainly does need to know whether a given relvar is a snapshot, because whether it is or not affects the semantics of the relvar in question (as well as dictating whether update operations are allowed on that relvar). The problem is, however, that—as the definition indicates—snapshots have come to be known, at least in some circles, not as snapshots at all but as materialized views. But snapshots aren’t views; views are virtual and snapshots aren’t, and materialized view is a contradiction in terms, at least as far as the relational model is concerned. Worse yet, the unqualified term view is now often taken to mean a materialized view specifically, and we’re thus in danger of no longer having a good term for a view in the original sense. This dictionary does use view in its original sense, but be warned that the term doesn’t always have that meaning elsewhere. Caveat lector.
MAX (Aggregate operator, dyadic version) Let v1 and v2 be values of the same ordered type. Then the expression MAX{v1,v2} returns v1 if v1 > v2 is true and v2 otherwise. In other words, MAX{v1,v2} is shorthand for:
IF v1 > v2 THEN v1 ELSE v2 END IF
Note: This operator is really just that special case of the n-adic version of MAX (see aggregate operator) in which the commalist of argument expressions contains exactly two such expressions (equivalently, it’s the MAX2 operator also defined under aggregate operator). The definition is included here primarily because it’s appealed to elsewhere in this dictionary (in Part III in particular).
meaning (Of a relvar) See intended interpretation; intension; relvar constraint (second definition); relvar predicate.
mediator See Great Divide; Small Divide.
member An element of a bag or (especially) set. Note: The term is also used in OO systems to mean an instance variable (q.v.), but this usage is best avoided because of possible conflict with the mathematical sense of the term.
membership See bag membership; set membership; contrast containment.
membership algorithm See JD implied by superkeys.
merge join A join implementation technique.
message Term used in OO contexts to mean an operator invocation. However, messages are usually considered as being “sent” to a specific object: viz., the object that’s the argument that corresponds, in the invocation in question, to the “distinguished parameter”—see Part II of this dictionary—to the operator in question (hence the message terminology). See selfish method (also in Part II of this dictionary).
metadata Data about data. See catalog; see also database statistics.
method Term used in OO contexts to mean either an operator per se, which is a model concept, or an implementation version of some operator, which is an implementation concept (see Part II of this dictionary). Unfortunately it’s not uncommon to find the term used with both meanings in the same text, or even in the same sentence. For example: “The attributes [i.e., the instance variables, q.v.] associated with an object are private, and only an object’s methods may examine or update these data; the methods are public” (from R. G. G. Cattell, Object Data Management: Object-Oriented and Extended Relational Database Systems, revised edition, Addison-Wesley, 1994).
MIN (Aggregate operator, dyadic version) Let v1 and v2 be values of the same ordered type. Then the expression MIN {v1,v2} returns v1 if v1 < v2 is true and v2 otherwise. In other words, MIN {v1,v2} is shorthand for:
IF v1 < v2 THEN v1 ELSE v2 END IF
Note: This operator is really just that special case of the n-adic version of MIN (see aggregate operator) in which the commalist of argument expressions contains exactly two such expressions. The definition is included here primarily because it’s appealed to elsewhere in this dictionary (in Part III in particular).
minimality (Of a key or FD, and possibly other things besides) Old fashioned and somewhat deprecated (because inaccurate) term for irreducibility.
MINUS See difference.
missing information Term often used to refer to information that’s either currently unknown or not applicable. Note: To describe information that’s currently unknown as missing is possibly reasonable; for example, if some person has failed to provide their date of birth (e.g., in filling out some form), it’s reasonable to say the date of birth for that person is missing. However, to describe information that’s not applicable as missing isn’t reasonable at all (and the usage is therefore deprecated). For example, if some person doesn’t have an email address, the email address for that person isn’t missing—rather, it simply doesn’t exist.
model In the database world, either a data model in general (in either sense of that term) or the relational model specifically, as the context demands. Note: Actually, the term model has been given a great number of additional meanings as well, both in the computing literature as such and also in the literature of logic and related disciplines—more meanings, in fact, than it can reasonably be expected to bear. Such additional meanings are deliberately ignored here.
modification anomaly Term originally used (though never very precisely defined) to refer to the fact that UPDATE operations on a relvar that’s subject to FD redundancy, q.v., can lead to inconsistency. Note: A relvar that’s in BCNF, q.v., is guaranteed to be free of modification anomalies in this “FD redundancy” sense.
Example: Suppose relvar SP is subject to the FD {CITY} → {STATUS}, meaning that whenever two tuples agree on CITY, they must also agree on STATUS. (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.) Then it’s possible—though only if a less than perfect job is being done on defining and enforcing integrity constraints—that after an UPDATE, two tuples might agree on CITY and not on STATUS.
Note: In general, of course, redundancy of any kind—at least if it’s uncontrolled, q.v.—can always lead to inconsistency, because redundancy means, loosely, that some piece of information is represented twice, and so there’s always the possibility that the two representations don’t agree: namely, when one has been updated and the other hasn’t. (Of course, these remarks do tacitly assume that the kind of consistency under discussion is merely what this dictionary elsewhere—see consistency—calls informal or “eventual” consistency. Formal consistency can be violated only if, to say it again, a less than perfect job is being done on integrity constraint definition and enforcement.)
modus ponens Loosely, proof by affirmation; more precisely, a rule of inference to the effect that if we know that (p) IMPLIES (q) is true and we also know that p is true, we can infer that q must be true. Also known as direct reasoning.
modus tollens Loosely, proof by denial; more precisely, a rule of inference to the effect that if we know that (p) IMPLIES (q) is true but we also know that q is false, we can infer that p must be false. Also known as indirect reasoning. Note: In the database context, modus tollens is relevant to the process of integrity constraint checking. In effect, when some given update is requested, the proposed new database value is checked against all applicable constraints; if the proposition expressed by some such constraint evaluates to FALSE, the new database value must also represent falsehood—in other words, it must be incorrect (see correctness)—and so the update must be rejected.
monadic Of an operator, having exactly one operand; of a predicate, being defined in terms of exactly one parameter. Contrast unary.
multidependent See multivalued dependency.
multidetermines See multivalued dependency.
multiple assignment An operation that allows several individual assignments all to be performed in parallel (in effect, simultaneously). In the important special case in which the target(s) for some or all of the individual assignments are database relvars, no database constraint checking is done until all of those individual assignments have been executed in their entirety. Note that multiple assignments, relational or otherwise, are involved implicitly in a variety of other operations—for example, updating some join or union view, or updating some relvar in such a way as to cause a cascade delete or other compensatory action (q.v.) to be performed.
Example: The following “double DELETE” is, logically, a multiple assignment operation:
DELETE S WHERE SNO = SNO('S1') ,
DELETE SP WHERE SNO = SNO('S1') ;
Note the comma separator after the first DELETE, which indicates syntactically that the end of the overall statement hasn’t yet been reached. Here’s the corresponding expanded form, using explicit assignment:
S := S WHERE NOT ( SNO = SNO('S1') ) ,
SP := SP WHERE NOT ( SNO = SNO('S1') ) ;
In general, the semantics of multiple assignment are as follows: First, all of the source expressions in the individual assignments are evaluated; then all of those individual assignments are executed in parallel. Note: This explanation requires some slight refinement in the case where two or more of the individual assignments specify the same target (see below). Ignoring that refinement for the moment, however, we can say that since the source expressions are all evaluated before any of the individual assignments are done, none of those individual assignments can depend on the result of any other (and so “executing them in parallel” is really just a manner of speaking). In the example, the effect on the database would be exactly the same if the two individual DELETEs were specified in reverse order.
Observe now that a multiple assignment in which the target variables are all relvars in the same database is actually just a syntactic device that allows us to formulate what is logically a database assignment (q.v.) as a collection of individual relational assignments. (And a “single” relational assignment—i.e., a “multiple” relational assignment consisting of just one individual assignment, to one individual database relvar—is just a special case, of course.) In other words, database relvars aren’t really variables, as such, at all; instead, they’re pseudovariables, q.v., and they act as a convenient fiction that gives the illusion that the database can be updated in a piecemeal fashion, individual relvar by individual relvar.
As for repeated targets: If two or more of the individual assignments involved in a given multiple assignment specify the same target variable, then those particular individual assignments are effectively executed in sequence as written (thereby effectively reducing to a single assignment to that target variable). For example, the double assignment
S := S MINUS ( S WHERE SNO = SNO('S1') ) ,
S := S MINUS ( S WHERE SNO = SNO('S2') ) ;
is logically equivalent to the following single assignment:
S := WITH ( S := S MINUS ( S WHERE SNO = SNO('S1') ) ) :
S MINUS ( S WHERE SNO = SNO('S2') ) ;
An important special case of the foregoing arises in connection with assignment via two or more THE_ pseudovariables to the same target variable. For example, the multiple assignment
THE_A ( E ) := LENGTH ( 5.0 ) ,
THE_B ( E ) := LENGTH ( 4.0 ) ;
(where E is a variable of declared type ELLIPSE—see the example under CONSTRAINT) is semantically equivalent to the following single assignment:
E :=
WITH ( E := ELLIPSE ( LENGTH ( 5.0 ) , THE_B ( E ) , THE_CTR ( E ) ) ) :
ELLIPSE ( THE_A ( E ) , LENGTH ( 4.0 ) , THE_CTR ( E ) ) ;
Note: Actually the foregoing explanation—i.e., of multiple assignments of the form illustrated by this particular example—is still slightly oversimplified, inasmuch as special precautions need to be taken in order to ensure that selector invocations in the WITH specification don’t cause any type constraints to be violated. Further details are byond the scope of this dictionary.
multiple EXTEND See extension; tuple extension.
multiple RENAME See renaming; tuple renaming.
multiple SUMMARIZE See summarization.
multiplicative identity See Laws of Algebra.
multiplicative inverse See Laws of Algebra.
multiplicity Strictly, the state of being manifold; loosely, a large number. In bag theory, however, the term is given a rather special meaning (see bag).
multirelvar constraint Term sometimes used for a database constraint that references two or more distinct relvars. Contrast multivariable constraint; single-relvar constraint. Note: Actually the difference between single-relvar and multirelvar constraints is more a matter of pragma than logic, thanks to The Principle of Interchangeability among other things. For example, the constraint on suppliers to the effect that supplier numbers are unique is a single-relvar constraint if all suppliers are represented in a single relvar as in Fig. 1, but would become a multirelvar constraint if that relvar were decomposed “horizontally” into a set of restrictions (one for each supplier city, say).
Examples: The foreign key constraints from relvar SP to relvars S and P are multirelvar constraints; so is constraint C3 from the examples under database constraint.
multiset Same as bag.
multituple constraint Term occasionally used for a relvar or database constraint that isn’t a single-tuple constraint, q.v.
Examples: Constraint C3 from the examples under database constraint might be regarded as a multituple constraint; so might the key constraints for relvars S, P, and SP.
multivalued attribute Extremely inappropriate term—because, by definition, a “multivalued attribute” isn’t an attribute at all—sometimes used to mean a repeating field or repeating group, q.v.
multivalued dependency A join dependency, q.v., with exactly two components (but typically expressed, not in conventional JD notation, but rather in a notation specific to multivalued dependencies as such). To elaborate: Let H be a heading; then a multivalued dependency (MVD) with respect to H is an expression of the form X →→ Y, where X (the determinant) and Y (the dependant) are both subsets of H. (The qualifying phrase “with respect to H” can be omitted if H is understood.) The expression X →→ Y is read as “Y is multidependent on X,” or “X multidetermines Y,” or, more simply, just “X double arrow Y.”
Let relation r have heading H; let X, Y, and Z be such their set theory union is equal to H; and let M be the MVD X →→ Y. If r satisfies the JD {{X,Y},{X,Z}}, then r satisfies M; otherwise r violates M. Now let relvar R have heading H. Then R is subject to the MVD M—equivalently, the MVD M holds in R—if and only if every relation r that can ever be assigned to R satisfies that MVD M. The MVDs that hold in relvar R are the MVDs of R, and they serve as constraints (q.v.) on R.
Note that it follows from the previous paragraph that the expression X →→ Y—or, a little more precisely, the expression X →→ Y | Z (see below)—is indeed, as claimed above, logically equivalent to a certain JD with exactly two components: viz., the JD {{X,Y},{X,Z}}. Note too that MVDs are defined with respect to some heading, not with respect to some relation or some relvar. Note also that from a formal point of view, an MVD is just an expression: an expression that, when interpreted with respect to some specific relation, becomes a proposition that, by definition, evaluates to either TRUE or FALSE. Now, it’s common informally to define X →→ Y to be an MVD only if it actually holds in the pertinent relvar—but that definition leaves no way of saying a given MVD fails to hold in some relvar because, by that definition, an MVD that fails to hold isn’t an MVD in the first place.
Example: As in the example under fourth normal form, let relvar CTX have attributes C (course), T (teacher), and X (textbook), and predicate Course C can be taught by teacher T and uses textbook X. Let that relvar be all key (i.e., let no proper subset of the heading be a key). Assume also that for a given course, the set of teachers and the set of texts are quite independent of each other. Then the MVDs {C} →→ {T} and {C} →→ {X} hold in that relvar (equivalently, the JD {{C,T},{C,X}} holds in that relvar).
Note that X and Y in the MVD X →→ Y are, specifically, sets of attributes. Informally, however, it’s common (though strictly incorrect) to speak of the attributes in X as if Y were multidependent on those attributes per se, instead of on the set X that contains those attributes. Likewise, it’s common (though strictly incorrect) to speak of the attributes in Y as if those attributes per se, instead of the set Y that contains those attributes, were multidependent on X. (The foregoing remarks apply with especial force to the common special case in which either X or Y is a singleton set.) Note too that, given X, Y, and Z as defined above, relvar R is subject to the MVD X →→ Y if and only if it’s subject to the MVD X →→ Z (MVDs always come in pairs in this way); for this reason, it’s usual to write them as a “one liner,” thus: X →→ Y | Z. Note finally that it follows from the definition that if R is subject to the MVDs X →→ Y | Z, then if it contains the tuples <x,y1,z1> and <x,y2,z2>, it also contains the tuple <x,y1,z2> (and hence, as can immediately be seen by interchanging the given tuples, the tuple <x,y2,z1> as well).
multivariable constraint Term sometimes used to mean a database constraint that involves at least two distinct range variables if expressed in tuple calculus form. Contrast multirelvar constraint; single-variable constraint.
Examples: Constraint C3 from the examples under database constraint is both a multirelvar constraint and a multivariable constraint. Note that a multirelvar constraint is necessarily a multivariable constraint as well; however, the converse is false, because the two or more range variables involved in a given multivariable constraint might all range over (the current value of) the same relvar. Key constraints are a case in point; by definition, such a constraint applies to a single relvar, but it’s also a multivariable constraint, necessarily. For example, here’s a relational calculus formulation of the key constraint for relvar S:
CONSTRAINT CSK FORALL SX ( UNIQUE SY ( SX.SNO = SY.SNO ) ) ;
(See FORALL; UNIQUE. The range variables SX and SY here are both defined to range over the relation that’s the value of relvar S at the time the constraint is checked.)
mutable object OO term for a variable (contrast immutable object). Note, however, that (a) the unqualified term variable is typically used in OO contexts to mean not an object at all but, rather, either a local variable or an instance variable, q.v. (meaning in both cases, typically but not necessarily, one that holds an object ID, q.v.); (b) the term mutable object is very frequently abbreviated in OO contexts to just object, unqualified. (In fact, some OO languages and systems actually define the term object to mean a mutable object specifically, and use some quite different term—typically literal, q.v.—to refer to an immutable object.)
Example: As suggested under instance, an illuminating analogy can be drawn between mutable objects as such and the “explicit dynamic variables” supported by certain conventional programming languages (PL/I’s based variables are a case in point). Like mutable objects of a given class, there can be any number of explicit dynamic variables of a given type, the storage for which is allocated at run time by explicit program action. Furthermore, those variables, again like mutable objects, are unnamed and must therefore be addressed via pointers. For example, consider the following PL/I code fragment:
DECLARE 1 ABOBJ BASED ,
2 A INTEGER ,
2 B FLOAT ;
DECLARE P POINTER ;
ALLOCATE ABOBJ SET ( P ) ;
P -> ABOBJ.A = 3 ;
Now observe the parallels between this PL/I code and conventional OO code:
The declaration of the based variable ABOBJ is akin to creating a new object class. Any number of individual objects (or variables) of that class can now be created in turn.
Individual objects (or variables) of that class have two “public instance variables” A and B, of types INTEGER and FLOAT, respectively. Note: In the OO context, A and B would probably contain pointers (i.e., “object IDs,” in effect) rather than numbers.
P is a program variable whose values are pointers (i.e., “object IDs,” in effect).
The ALLOCATE statement is akin to an OO constructor function invocation (q.v.): It creates a new object (or variable) of class ABOBJ, allocating storage for that object, and setting P to point to it. Observe that this new object has no distinguishing name apart from its address—which is precisely why object IDs are necessary, in the OO world.
The assignment statement “mutates” the object that P points to by assigning the value three to its A instance variable.
And so on.
mutation Term sometimes used (especially in OO contexts) to mean updating.
mutator Term sometimes used (especially in OO contexts) to mean an update operator. To quote Stanley B. Zdonik and David Maier, “Fundamentals of Object-Oriented Databases,” in Readings in Object-Oriented Database Systems (Zdonik and Maier, eds.; Morgan Kaufmann, 1990): “[If] m is ... a mutator, it must be possible to observe its effect on some object.” Contrast observer. Note: SQL’s use of the term is unorthodox, in that its mutators are read-only.
MVD Multivalued dependency.
MVD implied by a key See MVD implied by a superkey.
MVD implied by a superkey Let relvar R have heading H and let X →→ Y be an MVD, M say, with respect to H. Then M is implied by a superkey of R if and only if every relation r that satisfies R’s superkey constraints also satisfies M—equivalently, if and only if either M is trivial or X is a superkey for R or both. (Actually, if X is a superkey for R, then the MVD X →→ Y effectively degenerates to the FD X → Y.) See fourth normal form. Note: The term superkey could be replaced by the term key throughout the foregoing definition without making any substantive difference.
n-adic Of an operator, having exactly n operands (n ≥ 0); of a predicate, being defined in terms of exactly n parameters (n ≥ 0). Contrast n-ary. Note: Many operators that are conventionally regarded as dyadic can readily be—and often are, in this dictionary—extended to n-adic versions for arbitrary nonnegative n. Such extended versions are certainly legitimate so long as the dyadic operator in question is associative (q.v.) and commutative (q.v.) and has an identity value (q.v.). Examples of such operators include (a) the logical operators AND, EQUIV, OR, and XOR, and (b) the relational operators union and join and their variants (disjoint union, cartesian product, etc.). Note that some of these operators are idempotent, q.v., and some not. Note too that even if a given dyadic operator isn’t associative, it might still be possible to define an n-adic counterpart to it, but that counterpart will necessarily be a logically different operator (though it might, and ideally should, reduce to the dyadic case if n = 2). For an example and further discussion, see composition; see also the discussion of alternative definitions for n-adic versions of EQUIV (under equivalence) and XOR (under exclusive OR).
n-adic aggregate operator See aggregate operator.
n-ary (Of a heading, key, tuple, relation, etc.) Of degree n (n ≥ 0). Contrast n-adic.
n-dimensional (Of a relation or relvar) Of degree n (n ≥ 0). Observe, therefore, that relations and relvars are not, as many people seem to think, “flat” or two-dimensional (unless they happen to be binary, of course); rather, a relation or relvar of degree n is n-dimensional, in the sense that its tuples represent points in a certain n-dimensional space. One consequence of this state of affairs is that, contrary to popular opinion, relations are perfectly capable of representing “multidimensional data” and thereby supporting “online analytical processing” (OLAP).
Example: Each tuple in the suppliers relvar S represents a certain 4-point—a point, that is, in a certain four-dimensional space (where the dimensions in question are, of course, supplier number, name, status, and city, represented by the four attributes of the relvar)—and the relvar overall can thus be said to be four-dimensional.
n-place (Of a predicate) Same as n-adic (n ≥ 0).
n-tuple A tuple of degree n (n ≥ 0). Hence the special case terms 0-tuple, 1-tuple, 2-tuple, 3-tuple, etc. Note: The familiar relational term tuple itself is simply an abbreviation of the term n-tuple.
n-way joinable See joinable.
named constant A value that can be referenced by means of a name that’s not just a simple literal representation of the value in question. A named constant differs from a variable in two obvious ways—first, it can never serve as the target for an assignment operation; second, every reference to the name in question always denotes the same value. See constant; contrast variable.
naming of types See type naming.
Naming Principle The principle that everything we need to talk about needs to have a name (including The Naming Principle itself, of course!). It’s very difficult to talk about things that have no name, and yet examples where The Naming Principle is violated abound. For example, the SQL standard defines a construct it calls an exception handler. But such handlers have no name in SQL, and so the standard’s explanation of them begins by saying, in effect, “Let H be a handler”; in other words, it introduces a name for the otherwise anonymous construct. Other examples of constructs that at least potentially have no name include (a) columns in SQL tables, (b) databases in Tutorial D, and (c) objects, methods, and parameters in OO systems.
NAND In logic, a dyadic connective (also known as the Sheffer stroke and usually written as a vertical bar, “|”, though this symbol is used for many other purposes as well); if and only if p and q are predicates, then (p)|(q) is a predicate also. Let (ip)|(iq) be an invocation of that predicate, where ip and iq are invocations of p and q, respectively. Then that invocation (ip)|(iq) evaluates to FALSE if and only if ip and iq both evaluate to TRUE. (In other words, (p)|(q) is equivalent to NOT ((p) AND (q)).) Note: The parentheses enclosing p and q in the predicate, and ip and iq in the invocation, might not be needed in practice. Also, NAND as just defined is a logical operator; however, the algebra A, q.v., includes an operator called NAND that—by definition—is an algebraic operator instead (it’s basically “complement of join”).
native key Same as natural key.
natural join (Without inheritance) 1. (Dyadic case) Let relations r1 and r2 be joinable, q.v. Then (and only then) the expression r1 JOIN r2 denotes the natural join of r1 and r2, and it returns the relation with heading the set theory union of the headings of r1 and r2 and body the set of all tuples t such that t is the set theory union of a tuple from r1 and a tuple from r2. 2. (N-adic case) Let relations r1, r2, ..., rn (n ≥ 0) be n-way joinable, q.v. Then (and only then) the expression JOIN {r1,r2,...,rn} denotes the natural join of r1, r2, ..., rn, and it returns a relation r defined as follows: If n = 0, r is TABLE_DEE; if n = 1, r is r1; otherwise, choose any two distinct relations from the set r1, r2, ..., rn and replace them by their (dyadic) natural join, and repeat this process until the set consists of just one relation r, which is the final result.
Note: Although there are various kinds of join (or so it might be argued, at any rate), natural join is far and away the most important kind, which is why this dictionary uses the unqualified term join and the keyword JOIN to refer to the natural join specifically. (By contrast, in the research literature—at least, the recent research literature—natural join is often represented not by a keyword at all but by the “bow tie” symbol ⋈.)
Examples: The expression S JOIN SP—which could equally well be written JOIN {S,SP}—denotes the natural join of the relations that are the current values of relvars S and SP. That join is a relation of type RELATION {SNO SNO, SNAME NAME, STATUS INTEGER, CITY CHAR, PNO PNO, QTY QTY}. Moreover, if the current values of relvars S and SP are s and sp, respectively, the body of that relation consists of all tuples of the form <sno,sn,t,c,pno,q,> such that the tuple <sno,sn,t,c> appears in s and the tuple <sno,pno,q> appears in sp.
By way of another example, the expression S JOIN SP JOIN P—which could equally well be written JOIN {S,SP,P}—denotes the natural join of the relations that are the current values of relvars S, SP, and P (note that S, SP, and P are indeed 3-way joinable, as required). That join is a relation of type RELATION {SNO SNO, SNAME NAME, STATUS INTEGER, CITY CHAR, PNO PNO, QTY QTY, PNAME NAME, COLOR COLOR, WEIGHT WEIGHT}. Moreover, if the current values of relvars S, SP, and P are s, sp, and p, respectively, the body of that relation consists of all tuples of the form <sno,sn,t,c,pno,q,pn,l,w> such that the tuple <sno,sn,t,c> appears in s, the tuple <sno,pno,q> appears in sp, and the tuple <pno,pn,l,w,c> appears in p.
natural key Term sometimes used to refer to a key that’s not a surrogate key, q.v.
natural numbers The positive integers 1, 2, 3, etc. Note: Some writers additionally consider zero to be a natural number; the literature is not consistent on this point, but the majority of writers, and indeed common usage, do exclude the zero case.
negation If and only if p is a predicate, its negation NOT (p) is a predicate also. Let NOT (ip) be an invocation of that predicate, where ip is an invocation of p. Then that invocation NOT (ip) evaluates to TRUE if and only if ip evaluates to FALSE. Note: The parentheses enclosing p in the predicate, and ip in the invocation, might not be needed in practice.
negation as failure A concept closely related to The Closed World Assumption, q.v.; it means, loosely, that if a given tuple has the same heading as the result of a given query and hence could appear in that result (at least in principle) but doesn’t, then the proposition represented by that tuple is false.
negative Strictly less than zero. Note: The expression −0 is legal, of course, but it doesn’t denote a negative value; rather, it denotes the nonnegative value 0.
negative remainder Let p = n*q + r, where p, q, r, and n are integers, q is nonzero, r is nonnegative, and r < q. Then the negative remainder after dividing p by q is r − q (unless r is zero, in which case no negative remainder exists).
Example: Let p = −17 and q = 7. Then the nonnegative remainder r (q.v.) after dividing p by q is 4, and so the negative remainder is −3. Observe that −17 = (−2)*7 + (−3).
nested loops join See brute force join.
nested relation See relation valued attribute.
nesting and unnesting For relations, see grouping and ungrouping, respectively; for tuples, see wrapping and unwrapping, respectively
NEXT See ordinal type.
NF² NF squared; short for NFNF (“non first normal form”). An NF² relvar is, loosely, a relvar with at least one relation valued attribute. The term is very strongly deprecated, however, because it’s based on a flawed understanding of the concept of first normal form (note that all relvars are in 1NF—very likely in some higher normal form as well—even if they do have relation valued attributes). Also, the NF² concept is usually taken to include certain extensions to the conventional relational operators, extensions that aren’t just shorthand and are therefore not included (nor are they needed) in the relational model. For example, some writers have proposed an extended form of dyadic union that (a) recursively and/or repeatedly ungroups both operands until they involve no relation valued attributes at all, either directly or indirectly, then (b) performs a regular union on those ungrouped operands, and then (c) recursively and/or repeatedly (re)groups the result again. And it’s that recursion and/or repetition that makes the operator an “extended” one; that is, while any specific extended union invocation is shorthand for some specific combination of regular relational ungroup and union and (re)group operator invocations, nothing analogous applies to the extended union operator in general.
niladic Of an operator, having no operands; of a predicate, being defined in terms of no parameters. Contrast nullary. Note: An operator might appear to be niladic syntactically and yet not be limited to having the same effect on every invocation, owing to its use of what might be called hidden operands, such as the current reading of the system clock. Indeed, such operators—which are, of course, not truly niladic anyway—are the normal case.
Example: Many languages provide an operator of the form RANDOM ( ) for generating random (or, rather, pseudorandom) numbers. Such operators effectively have a hidden operand—e.g., the random number returned on the previous invocation, or perhaps the current reading of the system clock.
noncommutative group See group (mathematics).
nongenerated type A type not produced by invocation of any type generator, q.v. Note that nongenerated types are always scalar (by contrast, generated types might be scalar or nonscalar). For examples, see system defined type; user defined type.
nonkey attribute An attribute of a given relvar that isn’t part of any key of that relvar.
nonloss decomposition Replacing a relvar R by certain of its projections R1, R2, ..., Rn, such that (a) the join of R1, R2, ..., Rn is guaranteed to be equal to R, and usually also such that (b) each of R1, R2, ..., Rn is needed in order to provide that guarantee (i.e., none of those projections is redundant in the join), and usually also such that (c) at least one of R1, R2, ..., Rn is at a higher level of normalization than R is. In other words, nonloss decomposition is essentially just normalization, q.v., as this latter term is usually understood. (It would be possible to define the concept more generally to encompass more than just conventional normalization, but this dictionary doesn’t do so.) Note, incidentally, that one “nonloss decomposition” that’s always available for any given relvar R is to “replace” R by its identity projection, q.v.
Example: A nonloss decomposition that might be applied to the suppliers-and-parts database would involve the replacement of relvar S by its projections on {SNO,SNAME} and {SNO,STATUS,CITY}. Relvar S could then be reconstructed by joining those two projections back together again.
nonloss join 1. The join of relations r1 and r2 is nonloss with respect to r1 if and only if (r1 MATCHING r2) = r1; nonloss with respect to r2 if and only if (r2 MATCHING r1) = r2; and nonloss unconditionally (or simply nonloss, unqualified, for short) if and only if it’s nonloss with respect to both r1 and r2. 2. Let X and Y be subsets of the heading H of relation r, such that the set theory union of X and Y is equal to H. Then the join of r{X} and r{Y} is nonloss with respect to r if and only if it’s equal to r. Note: These two meanings are related and easily confused, but they’re not the same, and the term is probably best avoided for that reason. (Observe in particular in the second case that the join of r{X} and r{Y} is certainly nonloss in the first sense with respect to each of r{X} and r{Y}.) Be that as it may, the concepts apply to, and are used in connection with, relvars as well as relations.
nonnegative Greater than or equal to zero. Contrast positive.
nonnegative remainder Let p = n*q + r, where p, q, r, and n are integers, q is nonzero, r is nonnegative, and r < q. Then r is the nonnegative remainder after dividing p by q.
Example: Let p = −17 and q = 7. Then the nonnegative remainder after dividing p by q is 4, because −17 = (−3)*7 + 4.
nonscalar Not scalar; i.e., having user visible component parts. The most important nonscalar constructs in the relational model are tuples and (especially) relations themselves, where the “user visible component parts” are, of course, the pertinent attributes (and arguably the pertinent tuples as well, in the case of a relation). For further discussion, see scalar.
nonscalar type See type.
nontrivial (Of an EQD, FD, IND, JD, or MVD) Not trivial. See trivial EQD; trivial FD; trivial IND; trivial JD; trivial MVD. See also trivial decomposition.
NOR In logic, a dyadic connective (also known as the Peirce arrow and usually written as a down arrow, “↓”); if and only if p and q are predicates, then (p)↓(q) is a predicate also. Let (ip)↓(iq) be an invocation of that predicate, where ip and iq are invocations of p and q, respectively. Then that invocation (ip)↓(iq) evaluates to TRUE if and only if ip and iq both evaluate to FALSE. (In other words, (p)↓(q) is equivalent to NOT ((p) OR (q)).) Note: The parentheses enclosing p and q in the predicate, and ip and iq in the invocation, might not be needed in practice. Also, NOR as just defined is a logical operator; however, the algebra A, q.v., includes an operator called NOR that—by definition—is an algebraic operator instead (it’s basically “complement of union,” though “union” here refers not to the relational operator of that name but to a generalized form of that operator).
normal form 1. (General) Canonical form, q.v. 2. (Of a relvar) See first normal form; second normal form; etc. The most important relational normal forms are BCNF and 5NF—or perhaps ETNF—and 6NF; the others are mainly of historical interest. See also normal form hierarchy. Note: Other normal forms mentioned in this dictionary—viz., CNF (q.v.), DNF (q.v.), and PNF (q.v.)—have nothing to do with relvars per se.
normal form hierarchy Term sometimes used to refer to the sequence, or progression, 1NF − 2NF − 3NF − EKNF − BCNF − 4NF − ETNF − RFNF − SKNF − 5NF − 6NF. Note that 6NF implies 5NF, but the reverse implication does not hold; that is, if a given relvar is in 6NF, then it’s certainly in 5NF, but a relvar can be in 5NF without being in 6NF. Similarly, 5NF implies SKNF; SKNF implies RFNF; RFNF implies ETNF; ETNF implies 4NF; 4NF implies BCNF; BCNF implies EKNF; EKNF implies 3NF; 3NF implies 2NF; 2NF implies 1NF; and in none of these cases does the reverse implication hold. Note: It’s also true that DK/NF (q.v.) implies 5NF, while the reverse implication does not hold; however, DK/NF doesn’t imply 6NF, nor does 6NF imply DK/NF, which is why DK/NF fails to appear in the normal form hierarchy as here defined.
normalization Replacing a relvar R by certain of its projections R1, R2, ..., Rn, such that (a) the join of R1, R2, ..., Rn is guaranteed to be equal to R, and usually also such that (b) each of R1, R2, ..., Rn is needed in order to provide that guarantee (i.e., none of those projections is redundant in the join), and usually also such that (c) at least one of R1, R2, ..., Rn is at a higher level of normalization than R is (see nonloss decomposition). Observe, therefore, that projection is the decomposition operator, and join the recomposition operator, with respect to the normalization process (as this latter term is usually understood). The usual objective of normalization is to reduce redundancy, q.v., and thereby to eliminate certain update anomalies, q.v., that might otherwise occur (but see the note following the example below).
Example: Suppose 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.) Then relvar S involves some redundancy, because it states n times, for any city it mentions, that the city in question has a given status (where n is always greater than zero and generally greater than one). Replacing S by its projections on {SNO,SNAME,CITY} and {CITY,STATUS} will eliminate that redundancy.
Note: Following on from the foregoing example, suppose we want to be able to record the status for some city even if there are currently no suppliers located in that city. Then the design consisting of just relvar S is simply wrong (because it isn’t capable of representing such a city at all), and the design consisting of the “projections” of S on {SNO,SNAME,CITY} and {CITY,STATUS} is better (because it is so capable). Note, however, that the “projection” on {CITY,STATUS} here isn’t truly a projection of relvar S (hence the quotation marks), precisely because it might contain a tuple that has no counterpart in relvar S (and such a tuple is obviously not derived from any tuple in S). In such a situation, therefore, replacing S by its “projections” on {SNO,SNAME,CITY} and {CITY,STATUS} might be described—indeed, it usually is—as a process of normalization, but it really isn’t: not according to the foregoing definition, at any rate. Note in particular that the aim of such a “normalization” isn’t so much to reduce redundancy as it is to replace a logically incorrect design by a correct one.
One final point on the foregoing example: If indeed we do want to be able to record the status for some city even if there are currently no suppliers located in that city, then the formal reason why the design consisting of just relvar S is wrong is that it’s not expressively complete. See expressive completeness for another example and further discussion.
normalization principles A set of principles used to guide the practical process of normalization. The principles in question are as follows: (a) A relvar not in ETNF should be decomposed into a set of projections that are in ETNF (and possibly some higher normal form, such as 5NF or 6NF); (b) the original relvar should be reconstructable by joining those projections back together again; (c) the decomposition process should preserve dependencies; (d) every projection should be needed in the reconstruction process.
normalized That property of relations, and hence of relvars, according to which every tuple in the relation or relvar in question contains exactly one value, of the appropriate type, for each of its attributes. (Actually, a “tuple” that didn’t contain exactly one value of the appropriate type for each of its attributes wouldn’t be a tuple in the first place. It follows that a “relation” that contained such a “tuple” wouldn’t be a relation, and a “relvar” whose value was such a “relation” wouldn’t be a relvar, either. In other words, it’s immediate from the definition of what a tuple is that all relations, and hence all relvars, are normalized in the foregoing sense.) Contrast unnormalized. Note: Relvars in particular are equivalently said to be in first normal form, 1NF (q.v.); i.e., a normalized relvar is just a relvar that’s in 1NF, which is to say it’s just a relvar. However, the term normalized is frequently, though inaccurately, used to refer to some normal form higher than just first (typically at least BCNF).
normalized relvar A relvar. (Relvars are always normalized by definition, in the sense that they’re in at least first normal form. See normalized.)
NOT A connective, q.v. (see negation). Note: As just indicated, NOT as conventionally understood is a logical operator; however, the algebra A, q.v., includes an operator it calls NOT that—by definition—is an algebraic operator (in fact, it’s basically “complement”).
NOT MATCHING Tutorial D keywords denoting semidifference, q.v.
null A construct, used in SQL in particular, for representing “missing information”—or, rather, for representing the fact that some piece of information is unavailable for some reason (see missing information). Note: By definition, nulls aren’t values (they’re sometimes said to be marks); it follows that a “type” that “contains a null” isn’t a type, a “tuple” that “contains a null” isn’t a tuple, a “relation” that “contains a null” isn’t a relation, and a “relvar” that “contains a null” isn’t a relvar. It further follows that the concept of nulls as usually understood does serious violence to the relational model, and this dictionary therefore has very little further to say regarding that concept or matters related to it.
null set Deprecated term sometimes used (most unfortunately!) to mean the empty set.
nullary (Of a heading, key, tuple, relation, etc.) Of degree zero. The term is probably best avoided because of the potential confusion with null, q.v. Contrast niladic.
nullary foreign key An empty foreign key; i.e., a foreign key of degree zero.
nullary heading The empty heading; i.e., the heading of degree zero.
nullary key An empty key; i.e., a key of degree zero.
nullary projection 1. (Of a relation) The projection of a given relation r on no attributes (i.e., r{ }); the result is TABLE_DUM if r is empty and TABLE_DEE otherwise. 2. (Of a tuple) The projection of a given tuple t on no attributes (i.e., t{ }); the result is always the empty tuple.
nullary relation A relation of degree zero. There are exactly two such, TABLE_DEE and TABLE_DUM, q.v.
nullary tuple The empty tuple; i.e., the tuple of degree zero.
nullology The study of the empty set. The term has nothing to do with null, q.v.
Examples: Sets as such crop up all over the relational world, and in every case nullology requires us to consider what the implications might be if the set in question happens to be empty. Note that all of the following are sets of one kind or another, and they can all legitimately be empty in a relational context: a body; a heading; a tuple; a key or foreign key; the dependant or determinant in an FD or MVD; a component in a JD; a type; and various other things besides.
nVL A logic with n “truth values”; in other words, n-valued logic for some n ≥ 2. See also truth functional completeness. Note: If n = 2, those “truth values” really are truth values in the conventional sense of that term, and we can drop the quotation marks. In general, however, the number of monadic connectives for nVL is n² and the number of dyadic connectives is n to the power n². Thus, 2VL has 4 monadic connectives and 16 dyadic connectives; 3VL has 27 monadic connectives and 19,683 dyadic connectives; 4VL has 256 monadic connectives and 4,294,967,296 dyadic connectives; and so on.
O/R Object/relational.
object A thing.
object class See class (second definition).
object ID A unique identifier for an object, distinct from the object as such but usable (and used) as a reference to the object in question; in other words, an address or pointer. Note: There’s a logical difference between object IDs and keys in the relational model; to be specific, the former really are just pointers (or, at best, a tiny abstraction of the pointer concept), which keys in the relational model most certainly aren’t. See “Object Identifiers vs. Relational Keys,” in C. J. Date, Relational Database Writings 1994-1997 (Addison-Wesley, 1998) for further discussion.
object modeling See semantic modeling.
object oriented / object orientation Leaning toward things.
object/relational database A relational database (see object/relational DBMS).
object/relational DBMS A relational DBMS. Note: In practice, the major distinction between DBMSs that provide “object/relational” functionality and those that provide only “relational” functionality (at least from the user’s perspective) is simply that the former allow users to define their own types. But a true relational DBMS does so too, and a DBMS that doesn’t provide such functionality thus can’t reasonably claim to be fully relational, even if it supports other aspects of the relational model. The fact is, the term “object/relational” is little more than a marketing label, dreamed up to conceal the fact that early so called “relational” products weren’t very relational at all (not that most modern ones are either, at least at the time of writing).
observer Term sometimes used (especially in OO contexts) to mean a read-only operator. To quote Stanley B. Zdonik and David Maier, “Fundamentals of Object-Oriented Databases,” in Readings in Object-Oriented Database Systems (Zdonik and Maier, eds.; Morgan Kaufmann, 1990): “We call the operations that report on an object’s state observers or reporters.” Contrast mutator.
one to many correspondence Strictly, a rule pairing two sets s1 and s2 (not necessarily distinct) such that each element of s1 corresponds to at least one element of s2 and each element of s2 corresponds to exactly one element of s1; equivalently, that pairing itself. Often used loosely, however, to mean a pairing such that either (a) each element of s1 corresponds to any number of elements of s2 (possibly none at all) and each element of s2 corresponds to exactly one element of s1, or (b) each element of s1 corresponds to at least one element of s2 and each element of s2 corresponds to at most one element of s1, or (c) each element of s1 corresponds to any number of elements of s2 (possibly none at all) and each element of s2 corresponds to at most one element of s1. The term is probably best avoided unless the intended meaning is clear.
Example (strict sense only): Let s1 and s2 be the set of all nonnegative numbers and the set of all numbers, respectively. Then the pairing of nonnegative numbers x with their positive and negative square roots ±√x is a one to many correspondence from s1 to s2.
one to many join Let relations r1 and r2 be joinable, q.v. Then the join of r1 and r2 is said—somewhat loosely—to be one to many if and only if the pairing of tuples from r1 and r2 under the join is a one to many correspondence, q.v., in any of the senses of this latter term. Note: The foregoing definition is expressed in terms of relations, but the phrase one to many join is often applied to relvars instead of relations.
Example: The join of suppliers and shipments, S JOIN SP, would typically be said to be one to many from S to SP, even though there might be some tuples in S that join to no tuple in SP.
one to one correspondence Strictly, a rule pairing two sets s1 and s2 (not necessarily distinct) such that each element of s1 corresponds to exactly one element of s2 and each element of s2 corresponds to exactly one element of s1 (in other words, a bijection, q.v.); equivalently, that pairing itself. Often used loosely, however, to mean a pairing such that (a) each element of s1 corresponds to at most one element of s2 and each element of s2 corresponds to exactly one element of s1, or (b) each element of s1 corresponds to exactly one element of s2 and each element of s2 corresponds to at most one element of s1, or (c) each element of s1 corresponds to at most one element of s2 and each element of s2 corresponds to at most one element of s1. The term is probably best avoided unless the intended meaning is clear.
Example (strict sense only): Let s be the set of all integers. Then the pairing of elements x with their successors x+1 is a one to one correspondence from s to itself; so too is the pairing of elements x with their predecessors x−1.
one to one join Let relations r1 and r2 be joinable, q.v. Then the join of r1 and r2 is said—somewhat loosely—to be one to one if and only if the pairing of tuples from r1 and r2 under the join is a one to one correspondence, q.v., in any of the senses of this latter term. Note: The foregoing definition is expressed in terms of relations, but the phrase one to one join is often applied to relvars instead of relations.
Example: Let R1 and R2 be, respectively, the projection of the suppliers relvar S on {SNO,STATUS} and the projection of that same relvar on {SNO,CITY}. Then the join of R1 and R2 would typically be said to be one to one (and in fact is so in the strictest sense, given that every supplier has exactly one status and exactly one city).
onto (Of a function; preposition used as an adjective) Having range equal to the codomain (contrast into). See bijection; surjection.
OO Object oriented or object orientation, as the context demands.
open expression Expressions in general are of two kinds, open and closed. A closed expression is one that isn’t open, and it can appear wherever expressions in general are allowed. By contrast, an open expression is one that can appear only in certain limited contexts, because it contains references—typically but not necessarily attribute references, in the relational context—whose meaning depends on the context in question. (Image relation references, q.v., are an important special case of open expressions in general.) Simplifying slightly, an open expression can appear in a relational context (a) as the boolean expression in a WHERE clause; (b) as the expression denoting the source for an attribute assignment in an EXTEND, SUMMARIZE, or UPDATE invocation; or (c) as the expression whose values are to be aggregated within an aggregate operator invocation. Note: The unqualified term expression is usually taken to mean a closed expression specifically, unless the context demands otherwise. Also, it’s sometimes convenient to regard a closed expression as a degenerate special case of an open expression.
Example: Consider the following expression:
S WHERE STATUS > 10
This expression overall is closed, but it contains an open subexpression: namely, the boolean expression STATUS > 10. That subexpression is open because it contains an attribute reference (viz., STATUS), and can therefore be evaluated only in contexts in which that attribute reference has a well defined meaning. (In the example, that attribute reference effectively denotes the STATUS value from each tuple in turn within the current value of relvar S.)
open WFF A WFF, q.v., that isn’t closed; i.e., a WFF that denotes a predicate that isn’t a proposition.
Open World Assumption Loosely, the assumption—strongly contraindicated, because it appears to lead directly to a need to support three-valued logic, q.v.—that everything stated or implied by the database is true and everything else is unknown (i.e., it might be true and it might not). More precisely, let relvar R have predicate P (see relvar predicate). Then The Open World Assumption (OWA) says (a) if tuple t appears in R at time T, then the instantiation p of P corresponding to t is assumed to be true at time T; conversely, (b) if tuple t has the same heading as R but doesn’t appear in R at time T, then the instantiation p of P corresponding to t is not assumed to be true at time T (to repeat, it might be true and it might not). Loosely speaking, in other words, tuple t appears in relvar R at a given time only if—not if and only if—it satisfies the predicate for R at that time. However, it does at least follow that if proposition p corresponds to a tuple that appears in some relation that can be derived from the relations that are the values of the database relvars at time T—see derived relation—then proposition p is true at time T (which is why the phrase “or implied” appears in the original loose characterization). Contrast Closed World Assumption. Caveat: Be aware that very different interpretations of the term “open world” can be found in the general computing literature—even in the database literature specifically, sometimes.
operand Something on which an operation is performed. See also argument; parameter.
operation An operator; sometimes, the process performed when an operator is invoked.
operator Either a read-only operator or an update operator. Note: The term is often used, more specifically but a trifle loosely, to mean a read-only operator in particular. It’s also often used even more specifically to mean a read-only operator that’s denoted by some special symbol such as “+” instead of by an identifier such as PLUS, in which case other read-only operators (i.e., those denoted by identifiers) are typically referred to as functions. However, this latter usage is misleading, and hence deprecated, because all read-only operators are functions, strictly speaking. (At least, they should be! SQL, however, supports numerous read-only operators—including its well known SELECT operator in particular—that are explicitly defined in certain circumstances to be “possibly nondeterministic,” q.v., meaning their results given certain specific inputs aren’t fully predictable. See also ZO.)
operator invocation Given an operator Op, an expression (if Op is read-only) or statement (otherwise) that causes that operator Op to be invoked; also used, though mostly not so in this dictionary, to refer to the process performed when that expression is evaluated or that statement is executed. Note that there’s a logical difference between an operator as such and an invocation of that operator. See also argument; instantiation.
operator overloading See overloading.
operator overriding See overriding.
operator signature Same as signature, q.v., in any of the senses of that term. See Part II of this dictionary for further discussion.
optimization In the relational context, the process of converting a relational expression—in effect, a query or an update or a constraint, loosely speaking—into the “best possible” executable code, where “best possible” basically means best performing. The term represents somewhat of an overclaim, however, since it can rarely be guaranteed that the executable code produced is truly optimal in any very precise sense. Note: The term optimization, unqualified, is best reserved for “automatic” optimization—i.e., optimization done by the DBMS (see optimizer). Unfortunately, however, it has become increasingly common in recent years to find it applied to what might better be called hand or manual optimization, or in other words optimization—or would-be optimization—that’s carried out by some user instead of the system (i.e., by choosing, or attempting to choose, the “best” way to formulate some query or other database request in concrete syntax). Caveat lector. See also database statistics; expression transformation; semantic optimization.
optimizer The DBMS component responsible for optimization, q.v.
optional participation See cardinality constraint.
OR 1. A connective, q.v. (see disjunction). 2. An aggregate operator, q.v. Note: OR as conventionally understood is a logical operator (and this observation applies to both of the foregoing definitions); however, the algebra A, q.v., includes an operator it calls OR that—by definition—is an algebraic operator (in fact, it’s a generalized form of union). Note also that OR is sometimes known explicitly as inclusive OR, in order to distinguish it from exclusive OR, q.v.
ORDER BY See ordering.
ordered n-tuple Loosely, a combination, denoted <x1,x2,…,xn>, of exactly n elements x1, x2, …, xn (n ≥ 0) such that xi is the ith element of the ordered n-tuple in question (1 ≤ i ≤ n). More precisely, the ordered n-tuple <x1,x2,…,xn> is recursively defined in terms of the concept of an ordered pair (q.v.) as follows: If n = 0, the corresponding ordered n-tuple, written <>, is empty (and is unique); if n = 1, the corresponding ordered n-tuple is the 1-tuple <x1>; if n = 2, the corresponding ordered n-tuple is the ordered pair <x1,x2>; if n > 2, the corresponding ordered n-tuple is the ordered pair <<x1,x2,…,xm>,xn>, where m = n −1. Note that an ordered n-tuple is not a tuple in the relational model sense—tuples in the relational model have no ordering to their components (which is why tuples in the relational model have a heading, which ordered n-tuples typically don’t). Of course, the concept of ordering is irrelevant anyway if n ≤ 1.
ordered pair A combination, usually denoted <x,y> (though other notations are also used), of exactly two elements x and y such that x is the first element of the pair and y the second. The ordered pairs <x1,y1> and <x2,y2> are equal if and only if x1 = x2 and y1 = y2 (thus <x,y> ≠ <y,x>, in general). Formally, the ordered pair <x,y> is defined to be shorthand for the set {{x},{x,y}}; observe that one of the elements in this set determines the elements that constitute the ordered pair and the other determines which of those elements comes first.
Note: The foregoing definition might be thought to break down in the case where the elements x and y are equal, since the expression {{x},{x,y}} then reduces to just {{x}}. However, such is not the case—or at least it can be argued, somewhat tortuously, not to be the case. The argument in question goes like this. Let p be an ordered pair and let P be the set p is defined to be shorthand for. Then (a) the value x is defined to be the first element of p if and only if, for all sets s in P, x is an element of s, and (b) the value y is defined to be the second element of p if and only if y is an element of some set s in P and for all sets s1 and s2 in P, if s1 ≠ s2, then either y is not an element of s1 or y is not an element of s2.
ordered set Strictly speaking, a contradiction in terms, since sets are unordered by definition. However, the term is often used informally to refer to the combination of a given set and a total ordering (q.v.) imposed on the elements of that set.
ordered tuple Same as ordered n-tuple.
ordered type A type for which a total ordering (q.v.) is defined. Let T be such a type and let v1 and v2 be values of that type. With respect to that ordering, then, exactly one of the following comparisons will return TRUE and the other two will return FALSE:
v1 < v2 v1 = v2 v1 > v2
Contrast ordinal type.
Examples: Type INTEGER is an obvious example of an ordered type; however, that type is in fact an ordinal type, q.v., and is thus something of a special case. For an example of a type that’s ordered but not ordinal, see the examples under ordinal type. For an example of a type that’s not ordered at all (i.e., one that’s not ordered and hence definitely not ordinal either, a fortiori), consider the case of a user defined type POINT, representing geometric points in two-dimensional space. Type POINT wouldn’t be an ordered type, because the notion of one point being somehow less than another makes no sense. Note: It’s worth mentioning in passing that even if a type isn’t ordered at all, it might still be possible to impose an artificial ordering on it for implementation purposes, based perhaps on the internal (i.e., physical) representation for values of the type in question as patterns of bits.
ordering In the relational world, the process, or the result of the process, of imposing a left to right sequence on the attributes, and more particularly a top to bottom sequence on the tuples, of a relation, so that the data in the relation in question can be transferred out of the relational context and into an environment that relies on such sequences—for example, an environment in which results are displayed visually. Operators that request such sequencing, or ordering, are of major pragmatic importance, but they aren’t relational operators as such because their result isn’t a relation. In particular, therefore, it makes no sense to allow such operators to appear within a relational expression (unless, perhaps, they’re treated in that context merely as operators that just return their input). Note: A convenient way to think of such operators informally is as ones that convert a relation into a table (given that, unlike relations as such, tables—i.e., tabular pictures of relations—do have a left to right ordering to their columns and a top to bottom ordering to their rows).
Example: The SQL operators that provide the foregoing functionality are SELECT (for left to right column sequence) and ORDER BY (for top to bottom row sequence). In the case of ORDER BY, every column mentioned must be of some ordered type. Incidentally, it’s worth pointing out in passing that ORDER BY isn’t a function—meaning, more specifically, that the result of a given ORDER BY invocation is indeterminate, in general (consider, e.g., the effect of ORDER BY CITY on the relation that’s the current value of relvar S as shown in Fig. 1). By contrast, the operators of the relational algebra are indeed all functions (but see ZO). The same can’t always be said of the SQL analogs of those operators, incidentally, owing to the fact that certain SQL expressions are explicitly defined to be “possibly nondeterministic,” q.v.
Note: Actually ORDER BY is unusual in another respect also. To be specific, it produces a sequence of tuples as its result, and yet the operators “<” and “>” are explicitly not defined for tuples (see tuple comparison).
ordering (mathematics) See partial ordering; total ordering.
ordinal type An ordered type (q.v.), T, for which the following operators are available: (a) niladic FIRST and LAST operators, which return the first and last value, respectively, of type T with respect to the applicable total ordering; (b) monadic NEXT and PRIOR operators, which, given a value v of type T, return the value of type T immediately succeeding v and the value of type T immediately preceding v, respectively, again with respect to the applicable total ordering. Note: In practice, these four operators will generally (if not universally) need a qualifier to be included in their name in order to specify the pertinent type T, thus: FIRST_T, LAST_T, NEXT_T, PRIOR_T. See Part III of this dictionary for further discussion.
Examples: Type INTEGER is an obvious example of an ordinal type—the NEXT and PRIOR operators are basically just “add one” and “subtract one,” respectively, and the FIRST and LAST operators are operators that return the minimum and maximum integers, respectively. By contrast, let T be the type “rational numbers” (type RATIONAL, in Tutorial D). Then T is an ordered type but not an ordinal one—because if p/q is a rational number, then (in mathematics at least, if not in computer arithmetic) no rational number can be said to be the “next” one, immediately following p/q.
orthogonal At right angles; independent.
orthogonal decomposition A decomposition of some given relvar into restrictions, such that the restrictions in question abide by The Principle of Orthogonal Design, q.v. See also horizontal decomposition.
Examples: Suppose we were to replace relvar P by two relvars LP and HP, LP containing tuples for parts with weight less than or equal to 17.0 and HP containing tuples for parts with weight greater than 17.0; then that decomposition would be orthogonal. By contrast, suppose relvar HP were defined to contain tuples for parts with weight greater than or equal to 17.0; then the decomposition wouldn’t be orthogonal, because tuples for parts with weight equal to 17.0 would logically belong in, and should therefore appear in, both LP and HP.
Orthogonal Design Principle See Principle of Orthogonal Design.
orthogonality The property of being orthogonal, q.v. Sometimes used to refer specifically, albeit loosely, to The Principle of Orthogonal Design, q.v. Also used as a principle of good programming language design (“if features A and B should logically be unrelated, make sure they stay unrelated”).
overlapping 1. (Of bags or sets) Either having at least one element in common or all being empty. Note, therefore, that empty bags or sets are considered as overlapping, as well as being disjoint. Of course, if they’re empty, they’re really all the same bag or set anyway. 2. (Of relations all of the same type) Either having at least one tuple in common or all being empty. Note, therefore, that empty relations of the same type overlap, as well as being disjoint. Of course, if they’re empty, they’re really all the same relation anyway. 3. (Of scalar types) Either having at least one value in common or all being empty. Of course, if they’re empty, they’re really all the same type anyway. 4. (Of tuple types) See Part II of this dictionary. 5. (Of relation types) Again, see Part II of this dictionary.
Note: Distinct types never overlap, except possibly if inheritance is supported (once again, see Part II of this dictionary). Contrast disjoint.
overloading (Without inheritance) Using the same name for two or more different operators. Notice, therefore, that it’s really the name, not some operator as such, that’s overloaded; despite this fact, however, overloading polymorphism—overloading for short—is often referred to more specifically as operator overloading. The operators in question must have different specification signatures (q.v.) but should preferably have similar semantics. Contrast overriding. Note: Overloading is also referred to more specifically as overloading polymorphism. It’s also known as ad hoc polymorphism.
Examples: UNION is overloaded, because it—i.e., the operator name—is used to denote both relational union and tuple union, as well as a certain aggregate operator (and in SQL it’s also used to denote the “union plus” operator, q.v., though oddly enough not (a) the true bag union operator per se—which SQL doesn’t support at all—and not (b) SQL’s approximation to the UNION aggregate operator, which SQL does support but calls FUSION). Likewise, “=” is overloaded, because it applies to values of every type (i.e., there’s an “=” operator for integers, another for supplier numbers, another for relations of type RELATION {SNO SNO, PNO PNO, QTY QTY}, and so on). Similar remarks apply to “:=” also.
Note: The definition above suggests that the operators in question “should preferably have similar semantics.” An example of where this recommendation is flouted is provided by those languages—C++ is a case in point—that use the symbol “+” to denote string concatenation as well as numeric addition. Precisely because they’re used to the fact that numeric addition is commutative, users of such languages might be tempted to fall into the trap of thinking string concatenation is commutative too, which of course it isn’t.
overloading polymorphism See overloading.
overriding (Without inheritance) Replacing an operator by another with the same specification signature, q.v., but different semantics. (It has nothing to do with domain check override, q.v.) Contrast overloading.
Example: Suppose there exists an operator called LOG (possibly built in) that returns natural logarithms. Then it might be possible to override that operator by one that returns logarithms to base ten instead.
OWA The Open World Assumption.
P-relation / P-relvar See RM/T.
pair Either a set of cardinality two or, more usually, an ordered pair (q.v.), as the context demands.
parameter A formal operand in terms of which some operator is defined, to be replaced by some argument when the operator in question is invoked. Simplifying slightly (see polymorphism), every parameter is declared to be of some type, and any argument corresponding to a given parameter is required to be of the same type as that parameter. Contrast argument.
parameterized type Term sometimes used as a synonym for type generator. The term is inappropriate because a type generator isn’t a type.
parent / parent table Deprecated, because inappropriate, terms sometimes used in SQL contexts to mean (the SQL analog of) a referenced relvar, q.v.
partial function Let f be a function with domain d and let dd ⊇ d; then f can be regarded as a partial function with domain dd. Loosely speaking, in other words, a partial function is a function, q.v., except that there can exist elements of the “domain”—“domain” in quotes because it isn’t actually the domain as defined under function elsewhere in this dictionary—that have no image in the codomain. Contrast total function.
Example: Let s be the set of real numbers. Then “reciprocal of” is a partial function with “domain” and codomain both s (it’s partial because there’s one element of the “domain,” namely 0, that has no reciprocal).
partial instantiation See instantiation.
partial ordering Let s be a set. Then a partial ordering on s is a dyadic truth valued operator, usually denoted “≤”, such that for all x, y, and z in s, (a) x ≤ y or y ≤ x or both, or possibly neither; (b) x ≤ x (reflexivity); (c) if x ≤ y and y ≤ z, then x ≤ z (transitivity); and (d) if x ≤ y and y ≤ x, then x = y (antisymmetry). Contrast total ordering.
Example: Let s be an arbitrary set, let P(s) be the power set (q.v.) of s, and let “≤” denote the set inclusion operator (more usually written “⊆”). Then “≤” is a partial ordering on P(s). Moreover, it’s a partial ordering that isn’t a total ordering (except for the degenerate cases in which the cardinality of s is either zero or one). For example, let s, x, and y be the sets {1,2,3}, {1,2}, and {2,3}, respectively. Then x and y, which are distinct elements of P(s), are such that x ≤ y and y ≤ x are both false.
partition See partitioning.
partitioning Let s be a set. Then a partitioning of s is a set of subsets (“partitions”) of s such that every element of s is an element of exactly one such subset. Note that (a) partitions are pairwise disjoint; (b) their union (necessarily a disjoint union) is equal to s. Note too that if s is empty, then it has exactly one partitioning, consisting of an empty set of partitions. See also equivalence class.
partly redundant Tuple t is partly redundant in relation r if and only if it has a projection t{X} that’s forced, by virtue of the fact that r satisfies some FD, to be equal to the projection t′{X} of some distinct tuple t′ in r. Note that t and t′ are interchangeable in this definition; that is, if t is partly redundant because t′ exists, then t′ is partly redundant because t exists. Note too that a relvar can contain a partly redundant tuple only if it—i.e., the relvar—isn’t in BCNF, q.v.; thus, normalizing to (at least) BCNF is guaranteed to eliminate the possibility of partly redundant tuples. Note finally that a tuple can be partly redundant without being fully redundant (see fully redundant).
Peirce arrow See NOR.
persistence That property according to which data, once entered into the database, remains there (“persists”) until it’s removed—possibly in accordance with some compensatory action, q.v.—in response to some explicit user request. Data in database relvars is persistent in this sense (and in a relational database, nothing else is).
physical access path An implementation construct, intended to improve the speed of access to data as physically stored. Typical examples include hashes, indexes, and pointer chains. Note: By definition, there aren’t any physical access paths in the relational model, since that model is concerned only with the logical level of the system. In other words, all access to data as far as the relational model is concerned is via associative addressing, q.v.
physical data independence See data independence.
physical database design The process, or the result of the process, of deciding, given some logical database design, how that logical design should map to whatever physical constructs (including physical access paths in particular) the target DBMS happens to support. Note, therefore, that the physical design should be derived from the logical design and not the other way around; ideally, in fact, it should be derived automatically.
physical design Same as physical database design (if the context demands).
physical representation Internal representation of data in physical storage. Physical representations are an implementation concern, not a model concern, and thus are—or should be—of no interest to the user. Contrast possible representation; see also appearance.
picture (Of a relation, attribute, or tuple) See table, column, and row, respectively; see also cell. Note: Of course, there’s a logical difference between a picture as such and the thing that picture depicts; in the case of relations, attributes, and tuples, however, that difference seems not to be very well understood, at least if today’s DBMS products are anything to go by. This failing is unfortunate, given that the pictures in question often suggest things that aren’t true. For example, pictures of relations as tables (as in Fig. 1) strongly suggest that relations have a top to bottom ordering to their tuples and a left to right ordering to their attributes, neither of which is the case. See also flat relation.
pipelining A technique for evaluating relational expressions in which tuples of intermediate result relations are produced and passed on as input to another operation one at a time instead of en bloc. Contrast materialization (first definition).
PJ/NF Projection-join normal form, q.v.
placeholder A free variable (i.e., a parameter).
PNF Prenex normal form.
pointer An implementation construct. As is well known, pointers are excluded from the relational model. In fact, mixing pointers and relations—that is, allowing a relation (or would-be relation) in the database to have an attribute whose values are supposed to be pointers to tuples somewhere else in the database—has been described as The Second Great Blunder. (For the first, see First Great Blunder; see also referencing.) Indeed, such mixing clearly violates The Information Principle, q.v., among other things (see further discussion below). And yet such a state of affairs is explicitly supported by several SQL products, and is in fact required by the SQL standard (see REF type)—strong prima facie evidence that SQL and the relational model are very far from being the same thing.
Note: Some writers reserve the term pointer to mean, specifically, one whose value is some kind of physical address, and use the term reference (or some such term) for other kinds of pointers. This distinction might be useful in certain contexts but is irrelevant to the relational model—although of course it’s true that the relational model does make use of the term reference in another sense, in connection with foreign keys. But there are numerous logical differences between foreign key values and pointers, of which the most fundamental is that foreign key values identify tuples, which are values, whereas pointer values are addresses and therefore, by definition, identify variables. Indeed, it’s precisely this fact—the fact, that is, that pointers point specifically to variables—that justifies the claim made above to the effect that allowing database relations to contain pointers that “point to tuples somewhere else in the database” leads directly to a violation of The Information Principle. For further explanation, see “Don’t Mix Pointers and Relations!” and “Don’t Mix Pointers and Relations—Please!” (both in C. J. Date, Relational Database Writings 1994-1997, Addison-Wesley, 1998).
polymorphic operator See polymorphism.
polymorphic type Term sometimes used as a synonym for type generator. The term is inappropriate on at least two counts, because (a) a type generator isn’t a type and (b) generic polymorphism (which is the kind of polymorphism associated with type generators) isn’t the only kind of polymorphism.
polymorphism Loosely, the idea that an operator might permit its arguments to be of different types on different invocations. See generic polymorphism; inclusion polymorphism (in Part II of this dictionary); overloading polymorphism.
positive Strictly greater than zero. Contrast nonnegative.
possible representation Let T be a scalar type, and let v be an appearance, q.v., of some value of type T. By definition, v has exactly one physical representation and one or more possible representations (at least one, because there’s obviously always one that’s the same as the physical representation). If T is user defined, then at least one possible representation (“possrep” for short) for values of type T must be explicitly declared; if T is system defined, one or more possreps for values of type T can optionally be declared. Each possrep consists of zero or more components, where each such component consists in turn of a name and a corresponding declared type. Note: Elsewhere in this dictionary, the unqualified term possible representation, or the abbreviated form possrep, refers to a declared possrep specifically, unless the context demands otherwise. Note too that unlike physical representations, possreps are explicitly (if slightly indirectly) exposed to the user, via an associated selector, q.v., and associated set of THE_ operators, q.v. Also, possreps are always named; by default, however, the possrep name is the same as that of the corresponding type, and almost all of the examples elsewhere in this dictionary make use of this default option. Note finally that there’s no requirement, or even suggestion, that any declared possrep be the same as any underlying physical representation; however, there’s certainly a requirement that if PR1 and PR2 are distinct possreps for the same type T, then every value representable via PR1 must be representable via PR2 and vice versa. See also selector; THE_ operator.
Examples: Here in outline is a Tutorial D definition for the user defined type QTY (“quantities”):
TYPE QTY POSSREP QPR ( Q INTEGER ) ;
Observe in particular that the sole possrep here is called QPR (“QTY possible representation”). But specifying an explicit possrep name is optional. Here’s another possible definition for type QTY:
TYPE QTY POSSREP ( Q INTEGER ) ;
This definition is shorthand for the following:
TYPE QTY POSSREP QTY ( Q INTEGER ) ;
By way of an example where specifying more than one possrep makes obvious sense, consider a user defined type POINT, representing geometric points in two-dimensional space:
TYPE POINT
POSSREP CARTESIAN { X RATIONAL , Y RATIONAL ... }
POSSREP POLAR { RHO RATIONAL , THETA RATIONAL ... } ;
Type POINT has two distinct possreps, CARTESIAN and POLAR, reflecting the fact that points in two-dimensional space can indeed possibly be represented by either cartesian or polar coordinates.
possibly nondeterministic An SQL term, deriving from the fact that SQL’s support for the equality operator “=” is seriously defective. To be more specific, SQL allows certain comparisons of the form v1 = v2 to return TRUE even if v1 and v2 aren’t the same value, or even of the same type (this isn’t the only defect in SQL’s support for “=”, but it’s certainly one of the most egregious). As a direct consequence, certain SQL expressions are explicitly defined to be “possibly nondeterministic,” meaning their results aren’t fully predictable. Such expressions are explicitly prohibited from appearing in integrity constraints. Oddly enough, however, they are allowed to appear in queries and updates, where they can surely do just as much harm (?).
Example: Suppose the CITY values for suppliers S2 and S3 are given as 'Paris' and 'Paris ', respectively (note the trailing blank in the S3 value here, and note the logical difference between the two values; for example, if CHAR_LENGTH is a scalar operator with the intuitively obvious semantics, then CHAR_LENGTH applied to 'Paris' returns the value 5, while CHAR_LENGTH applied to 'Paris ' returns the value 6). Then the result of the SQL expression SELECT DISTINCT CITY FROM S will include either 'Paris' or 'Paris ' or both, but which of these three possibilities applies in any given situation is, in general, undefined.
POSSREP The Tutorial D construct that defines a possible representation, q.v.
Example: See the examples under possible representation and elsewhere.
possrep Shorthand for possible representation.
possrep component See possible representation; selector; THE_ operator.
power set The set of all subsets of a given set. If the given set s has cardinality n, the corresponding power set P(s) has cardinality 2n (this count includes both the empty set and the set that’s identical to the original set, both of which are indeed subsets of the original set). Note, therefore, that the cardinality of P(s) is always strictly greater than that of s. (In particular, 20 = 1; thus, if s is the empty set { }, which has cardinality zero, the corresponding power set P(s) is the set {{ }}, which has cardinality one.)
precision (Of a numeric type) The maximum number of significant digits in a value of the type in question. For example, consider the SQL type NUMERIC(5,2). Values of that type are decimal numbers with precision five and scale factor (q.v.) two. In other words, values of that type are precisely the following:
-999.99 , -999.98 , ... , -000.01 , 000.00 , 000.01 , ... , 999.99
In general, the precision for a given numeric type specifies the total number of digits, and the scale factor specifies the position of the assumed radix point, in the string of digits denoting any given value of the type in question. Observe that the precision and scale factor between them serve as an a priori constraint on values of the type; in effect, they constitute the applicable type constraint.
Note: Actually there’s some confusion in the literature over the term precision. To be specific, some writers and some languages use it to mean either the scale, q.v., or the scale factor, q.v. (at least as these latter terms are defined in this dictionary). Caveat lector.
predicate Loosely, a truth valued function. Given an arbitrary predicate, invoking, or instantiating, that predicate—i.e., substituting arguments for the parameters of that predicate—yields a proposition, which by definition evaluates unequivocally to either TRUE or FALSE. Thus, another way of thinking about a predicate is as a parameterized or generalized proposition. And if and only if the set of parameters is empty, the predicate degenerates to a proposition per se; in other words, all propositions are predicates, but “most” predicates aren’t propositions. Note: Strictly speaking, if P is a truth valued function, the corresponding predicate isn’t really P as such—rather, it’s the meaning of P, or in other words what P denotes. Consider the following examples (both of which are deliberately written in a kind of functional style): is_a_star(x) and est_une_étoile(x). Clearly there are two different functions here, even though, equally clearly, they both denote the same predicate. However, it’s usual to ignore this distinction—the distinction, that is, between the truth valued function as such and what that function denotes—in informal contexts (and indeed in more formal contexts as well, sometimes). See also proposition; relvar predicate.
Examples: 1. X is a star. 2. Neptune is a star. (This particular example is actually a proposition, of course—a false one, as it happens.) 3. Politician p is corrupt. 4. Supplier SNO is under contract, is named SNAME, has status STATUS, and is located in city CITY. 5. Supplier SNO supplies part PNO in some quantity (or, in more stilted English, There exists a quantity QTY such that supplier SNO supplies part PNO in quantity QTY). Note that this example is a 2-place predicate, not a 3-place one (QTY here isn’t a parameter but a bound variable, q.v., thanks to the quantifier There exists a quantity QTY such that).
predicate calculus A sound and complete formal system having to do with predicates and connectives and the inferences that can be made using such predicates and connectives. Note: The principal difference between predicate calculus and propositional calculus, q.v.—the former of which subsumes the latter—is that predicates, unlike propositions, are allowed to contain logic variables (both free and bound), which makes predicate calculus more expressively powerful and hence more widely applicable.
predicate constant Same as predicate.
predicate expression An expression denoting a predicate; i.e., an expression involving predicate constants, predicate variables, connectives, and parentheses. Note: Few logic texts if any actually use this term; in fact, logic texts in general don’t seem to have a term for the construct at all other than predicate itself (not even those that use propositional form, q.v., for a propositional expression, which might be expected to use the surely obvious predicate form for a predicate expression).
Examples: If p and q are predicate variables, then p, q, the conjunction (p) AND (q), the disjunction (p) OR (q), and the negation NOT(p) are all predicate expressions.
predicate form See predicate expression.
predicate logic Same as predicate calculus.
predicate variable A variable whose value is a predicate. Note: Some writers use this term to mean a free variable, but this usage is deprecated; surely a predicate variable should be to a predicate just what an integer variable is to an integer, or a relation variable is to a relation (etc.).
premise / premiss In logic, something assumed to be true for the purposes of a proof or attempted proof. See in particular equality generating dependency; tuple generating dependency.
prenex normal form Loosely speaking, a predicate is in prenex normal form, PNF, if and only if the quantifiers all appear at the beginning. More precisely, a predicate is in PNF if and only if (a) it’s quantifier free or (b) it’s of the form Q x (p), where Q x is a quantifier and p in turn is in PNF. Thus, a PNF predicate takes the form
Q1 x1 ( Q2 x2 ( ... ( Qn xn ( q ) ) ... ) )
where (a) n ≥ 0; (b) each of Q1, Q2, ..., Qn is, typically, either EXISTS or FORALL; and (c) the predicate q—which is sometimes called the matrix—is quantifier free.
Example: Consider the following tuple calculus query (“Get suppliers who supply at least one red part”):
SX RANGES OVER { S } ;
SPX RANGES OVER { SP } ;
PX RANGES OVER { P } ;
{ SX } WHERE EXISTS PX ( PX.COLOR = COLOR('Red') AND
EXISTS SPX ( SPX.SNO = SX.SNO AND
SPX.PNO = PX.PNO ) )
The predicate in the WHERE clause here is not in prenex normal form. Here, however, is a logically equivalent formulation of the query in which the predicate is in prenex normal form:
{ SX } WHERE EXISTS PX ( EXISTS SPX ( PX.COLOR = COLOR('Red') AND
SPX.SNO = SX.SNO AND
SPX.PNO = PX.PNO ) )
Prenex normal form is no more logically correct than any other, but with a little practice it does tend to become the easiest to write. Note, however, that it isn’t always achievable. For example, here’s another query on the suppliers-and-parts database (“Get suppliers who either are located in Athens or supply at least one part or both”):
{ SX } WHERE SX.CITY = 'Athens' OR EXISTS SPX ( SPX.SNO = SX.SNO )
The predicate in the WHERE clause here is not in prenex normal form, nor does it have a prenex normal form equivalent.
preserving dependencies See FD preservation.
primary domain Let R be a base relvar; let R have a primary key K; let K be simple (see simple key); and let K be defined on domain (i.e., type) D. Then, and only then, D is a primary domain. Note: Since (a) it clearly violates The Principle of Interchangeability and (b) it relies on a concept, primary key, that’s hard to justify from a logical point of view (see primary key), the primary domain concept is rather strongly deprecated. In any case, the term—perhaps fortunately—isn’t much used; we mention it here mainly for historical reasons.
Examples: Assume the declared keys for the suppliers-and-parts database are in fact primary keys. Then the sole primary domains with respect to that database are the domains (types) SNO and PNO.
primary key A candidate key that has been singled out for special treatment (certainly special syntactic treatment, possibly special semantic treatment also) for some reason. While a given relvar can have any number n of candidate keys (n > 0), it can have at most one primary key. For a given relvar, however, whether some candidate key is to be chosen as primary, and if so which one, are essentially psychological issues, beyond the purview of the relational model as such. Note: The relational model as originally formulated did in fact insist that base relvars, at least, should always have a primary key. It also insisted that foreign keys reference primary keys specifically (partly because it also insisted that foreign keys reference base relvars specifically, as well as being attached to base relvars specifically). However, there were never any good logical reasons for these rules, and in any case rules that apply to base relvars but not to other kinds are more than a little suspect anyway (because they violate The Principle of Interchangeability); thus, the primary key notion could be dropped without serious loss. We mention it here mainly for historical reasons. Tutorial D in particular makes no distinction between primary keys and alternate keys (q.v.), referring to them all just as keys.
primary key attribute An attribute of a given relvar that participates in the primary key (if any) for that relvar. Contrast key attribute.
prime attribute Old fashioned and somewhat deprecated term for a key attribute (not necessarily a primary key attribute).
primitive operator Loosely, an operator not defined in terms of others. More precisely, let s be a set of operators. Let Op be an operator in s that can be defined in terms of other operators in s; remove Op from s, and repeat this step until it can’t be repeated any more. What remains is a set of operators that are primitive with respect to s. Note that the set of primitive operators with respect to a given set s is not necessarily unique.
Examples: 1. For relational algebra, a primitive set of operators (a) will definitely include projection, (b) will probably include join (but see A), but (c) will probably not include semijoin (because semijoin can be defined in terms of projection and join). 2. For the relational operators supported by Tutorial D (not counting relational inclusion), the following set of operators is primitive: {UNION, NOT MATCHING, JOIN, restriction, projection, EXTEND}. 3. For two-valued logic, any of the following sets of operators can be taken as primitive: {NOT,OR}; {NOT,AND}; {NOR}; {NAND}.
primitive type Term sometimes used to mean a system defined type—necessarily scalar—with no declared possrep (the term primitive derives from the fact that all of the types available in any given context are ultimately defined in terms of such types). Typical examples include INTEGER and BOOLEAN. (Of course, type BOOLEAN in particular is required by the prescriptions of the relational model.)
Principle of Cautious Design A guiding principle in the design of formal systems (including databases, DBMSs, database languages, and many other such systems). It can be stated thus: Given a design choice between options A and B, where A is upward compatible with B and the full consequences of going with B aren’t yet known, the cautious decision is to go with A. Going with A permits subsequent “opening up” of the design to B if such opening up becomes desirable. By contrast, going with B prohibits subsequent “closing down” of the design to A, even if such closing down turns out to be desirable (i.e., if it becomes clear that B was a bad choice in the first place).
Example: The designers of SQL had a choice between prohibiting duplicate rows (Option A) and permitting them (Option B). The cautious decision would have been to prohibit them (Option A); they could then have been supported in the future, if a clear need for such support were ever demonstrated. Unfortunately, the designers chose to permit them (Option B). Of course, this decision turned out to be a very bad one, but now there’s no compatible way for SQL to go back to Option A. Note: As this example suggests, The Principle of Cautious Design can help avoid situations in which the language (or the DBMS, or the database, or whatever else it is that’s being designed) provides certain options that users have to be explicitly told not to exercise.
Principle of Database Relativity Consider a database (“the real database”) in which all of the relvars are base ones. In general, a typical user will interact not with that real database as such, but rather with what might be called an “expressible” database that consists of some mixture of base relvars and views. Now, we can assume that none of the relvars in that expressible database can be derived from the rest, because such a relvar could be dropped without loss of information. From the user’s point of view, therefore, the relvars in that expressible database are effectively all base relvars. And likewise for the database itself—i.e., the choice of which database is the “real” one is arbitrary too, just so long as the choices are all information equivalent, q.v. Which is essentially what The Principle of Database Relativity says: Any given body of data can, in general, be represented by means of several distinct but information equivalent database designs. See also information equivalence; Interchangeability Principle.
Principle of Identity of Indiscernibles The principle that if there’s no way whatsoever of distinguishing between two objects, then there aren’t two objects but only one. Or equivalently: Every object has its own unique identity. Note: In the relational model, such unique identities are represented in the same way as everything else—namely, by means of attribute values (see Information Principle)—and numerous benefits accrue from this fact. Note too that there’s a logical difference between indiscernibility and interchangeability—two objects might be distinguishable but interchangeable (think of two pennies, for example); in other words, the concepts of interchangeability and indiscernibility are themselves not interchangeable. (Confusion over this particular logical difference might help explain why some people seem to think SQL’s support for duplicate rows is a good idea.) Note finally that the term object here is intended to be generic—it’s not being used in its special OO sense.
Principle of Incoherence A principle, sometimes invoked in defense of an attempt (successful or otherwise) at criticizing some technical proposal or position, to the effect that it’s hard to criticize something coherently if what’s being criticized is itself not very coherent in the first place—a state of affairs that goes some way toward explaining why such criticisms can often be longer (sometimes much longer) than what’s being criticized. Occasionally referred to, a little unkindly, as The Incoherent Principle.
Example: Here’s a piece of text that, because it’s so badly written, is hard to criticize coherently (it’s quoted verbatim from the SQL reference manual for a certain well known mainstream SQL product):
A table check constraint is a rule that specifies the values allowed in one or more columns of every row of a table. They are optional and can be defined using the SQL statements CREATE TABLE and ALTER TABLE. The specification of table check constraints is a restricted form of a search condition. One of the restrictions is that a column name in a table check constraint on table T must identify a column of T ... The check-condition “IS NOT NULL” can be specified, however it is recommended that nullability be enforced directly using the NOT NULL attribute of a column. For example, CHECK (salary + bonus > 30000) is accepted if salary is set to NULL, because CHECK constraints must be either satisfied or unknown and in this case salary is unknown. However, CHECK (salary IS NOT NULL) would be considered false and a violation of the constraint if salary is set to NULL.
Principle of Interchangeability See Interchangeability Principle.
Principle of Orthogonal Design Loosely, the principle that no two relvars in a given database should have overlapping meanings. More precisely, let R1 and R2 be relvars (not necessarily distinct), and let the JD {X1,X2,...,Xn} be irreducible with respect to R1. Let there exist some Xi (1 ≤ i ≤ n) and some possibly empty set of attribute renamings on the projection, R1X say, of R1 on Xi that maps R1X into R1Y, say, where R1Y has the same heading as some subset Y (distinct from Xi, if R1 and R2 are one and the same) of the heading of R2. Further, let the projection of R2 on Y be R2Y. Then The Principle of Orthogonal Design is violated by R1 and R2 if and only if there exist restriction conditions c1 and c2, nether of which is a contradiction (q.v.), such that the equality dependency (R1X WHERE c1) = (R2Y WHERE c2) holds.
Examples: See the examples under orthogonal decomposition. Note: The equality dependency that holds in the second of those examples is:
( LP WHERE WEIGHT = WEIGHT(17.0) ) = ( HP WHERE WEIGHT = WEIGHT(17.0) )
Principle of Uniform Representation See Information Principle.
Principle of Uniformity of Representation See Information Principle.
principles of normalization See normalization principles.
PRIOR See ordinal type.
private instance variable See instance variable.
privileged operator An operator whose implementation code has access at run time to the physical representation of its argument(s), or indeed to the physical representation of anything at all. Note: As a matter of good practice, the only privileged operators should be selectors and THE_ operators (also IS_T operators, defined in Part II of this dictionary).
product Cartesian product, q.v. (unless the context demands otherwise).
product (bag theory) See bag.
product (set theory) See cartesian product (set theory).
projection Let relation r have attributes called A1, A2, ..., An (and possibly others). Then (and only then) the expression r{A1,A2,...,An} denotes the projection of r on {A1, A2, ..., An}, and it returns the relation with heading {A1,A2,...,An} and body consisting of all tuples t such that there exists a tuple in r that has the same value for attributes A1, A2, ..., An as t does. See also tuple projection.
Example: The expression S{STATUS,CITY} denotes a projection of the relation that’s the current value of relvar S. That projection is a relation of type RELATION {STATUS INTEGER, CITY CHAR}, containing all possible tuples of the form <st,sc> (and no other tuples) such that there exists some supplier number sno and some name sn such that the tuple <sno,sn,st,sc> appears in the current value of relvar S. Given the sample values shown in Fig. 1, the result has cardinality four. Note: For psychological reasons, Tutorial D allows projections to be expressed in terms of the attributes to be removed instead of those to be retained; thus, for example, the projection S{STATUS,CITY} can alternatively, but equivalently, be expressed as S{ALL BUT SNO, SNAME}. Analogous remarks apply to several other Tutorial D constructs also—KEY, GROUP, WRAP, and so on (wherever ALL BUT makes sense, in fact).
projection-join normal form The original name for fifth normal form, 5NF. The name derives from the fact that 5NF is “the” normal form with respect to projection and join, as those operators are classically understood (but see essential tuple normal form; sixth normal form).
pronunciation (SQL) See SQL.
pronunciation (tuple) See tuple.
proof (Logic) In general, a sequence of sentences in some logical system that together establish some sentence as a logical consequence of certain given sentences; if the given sentences are true, then the consequential sentence is also true. A direct proof is such a sequence in which each sentence either (a) is an axiom or (b) is a previously proved theorem or (c) can be deduced from previous sentences in the sequence by means of the rules of inference of the system; the final sentence is a theorem. An axiom is a theorem with a single-sentence direct proof. An indirect proof, also known as a reductio ad absurdum proof (q.v.), is a sequence of sentences that together establish some sentence as a theorem by adopting its negation as a premise and then showing that such adoption leads to a contradiction.
propagating updates See controlled redundancy.
proper inclusion Set s1 properly includes set s2 (“s1 ⊃ s2”) if and only if it is a proper superset of s2; set s2 is properly included in set s1 (“s2 ⊂ s1”) if and only if it is a proper subset of s1.
proper subkey A subkey that isn’t a key (i.e., a proper subset of a key).
proper subset Set s2 is a proper subset of set s1 (“s2 ⊂ s1”) if and only if it is a subset of s1 and s1 and s2 are distinct.
proper superkey A superkey that isn’t a key (i.e., a superkey that doesn’t have the irreducibility property); loosely, a proper superset of a key.
proper superset Set s1 is a proper superset of set s2 (“s1 ⊃ s2”) if and only if it is a superset of s2 and s1 and s2 are distinct.
property A thing belonging to another thing. Note: It’s frequently suggested that there should be a one to one correspondence between the properties of a given entity type and the attributes in some base relvar. The suggestion is hard to sustain, however, given that the term properties of a given entity type has no precise definition. (Of course, the same is true of the term entity type. In fact, it’s true of the term property as well, come to that.)
proposition A 0-place predicate; a predicate with no parameters (i.e., no free variables); a declarative statement (in the sense of logic, not the programming language sense); hence, something that evaluates unequivocally to either TRUE or FALSE. Note: Strictly speaking, if P is a declarative statement, the corresponding proposition isn’t really P as such—rather, it’s the assertion made by P. For example, consider the statements The sun is a star and Le soleil est une étoile. Clearly there are two different statements here. Equally clearly, however, they both denote the same proposition. Be aware, therefore, that it’s usual to ignore the foregoing distinction—i.e., between the statement as such and what that statement denotes—in informal contexts (and indeed in more formal contexts as well, sometimes).
Examples: 1. The sun is a star. 2. Neptune is a star. 3. All politicians are corrupt. 4. Supplier S1 is under contract, is named Smith, has status 20, and is located in city Paris. 5. There exists a city CITY such that there exists a supplier number SNO such that the supplier with supplier number SNO is located in city CITY. Notice that there are two variables, SNO and CITY, in this example (variables in the sense of logic, that is, not variables in the programming language sense); however, the variables in question are bound, not free, and the example overall still evaluates unequivocally to either TRUE or FALSE (i.e., it’s either the case or not the case that at least one supplier is located in at least one city). 6. Let p be an arbitrary predicate. If every parameter of p is either subjected to quantification or replaced by some argument (not both!), then what results is a proposition. For example, given the predicate The supplier with supplier number SNO is under contract, is named SNAME, has status STATUS, and is located in city CITY, the statement There exists a city CITY such that there exists a supplier number SNO such that the supplier with supplier number SNO is under contract, is named Smith, has status 20, and is located in city CITY is a proposition. 7. By way of a counterexample, the expression x > 0 OR TRUE is not a proposition (because it involves a parameter, x), even though it does evaluate unequivocally to TRUE. In other words, although propositions always evaluate unequivocally to either TRUE or FALSE, not everything that evaluates unequivocally to either TRUE or FALSE is a proposition. Note: A useful though not infallible informal test for checking whether some statement S is a proposition is the following: P is a proposition if and only if “Is it the case that P?” is a well formed question in natural language.
propositional calculus A sound, complete, and decidable formal system having to do with propositions and connectives and the inferences that can be made using such propositions and connectives. Contrast predicate calculus.
propositional constant Same as proposition.
propositional expression An expression denoting a proposition; i.e., an expression involving propositional constants, propositional variables, connectives, and parentheses. Note: Logic texts don’t use this term much, typically preferring the term propositional form, q.v. (if they use any term for the concept at all, that is).
Examples: If p and q are propositional variables, then p, q, the conjunction (p) AND (q), the disjunction (p) OR (q), and the negation NOT(p) are all propositional expressions.
propositional form See propositional expression.
propositional function Same as predicate.
propositional logic Same as propositional calculus.
propositional variable A variable whose value is a proposition and thus effectively denotes either TRUE or FALSE. Note: Some writers use the term to mean a free variable, but this usage is deprecated; surely a propositional variable should be to a proposition just what an integer variable is to an integer, or a relation variable is to a relation (etc.).
proto tuple Loosely, the portion of a relational calculus expression that precedes the WHERE clause. The term is shorthand for “prototype tuple”; it’s useful but nonstandard.
Example: Here’s a tuple calculus formulation of the query “Get supplier number and city for suppliers who supply at least one part”:
SX RANGES OVER { S } ;
SPX RANGES OVER { SP } ;
{ SX.SNO , SX.CITY } WHERE EXISTS SPX ( SPX.SNO = SX.SNO )
In this example, the proto tuple is {SX.SNO,SX.CITY}. Note: A proto tuple consisting of just a range variable reference R enclosed in braces is shorthand for one of the form
{ R.A1 , R.A2 , ..., R.An }
where A1, A2, ..., An are all of the attributes of the relation r over which R ranges, in some arbitrary order. For example, given range variable definitions as above, the proto tuple {SX} is shorthand for the proto tuple {SX.SNO,SX.SNAME,SX.STATUS,SX.CITY}.
pseudovariable See pseudovariable reference.
pseudovariable reference The use of an operational expression instead of a simple variable reference to denote the target for some assignment (“:=”) or other update operation (in particular, see THE_ pseudovariable). Note: It’s convenient for definitional purposes to regard pseudovariable references as if they were regular variable references (and this dictionary does so); in other words, pseudovariables are variables, loosely speaking.
Examples: Let CS be a variable of declared type CHAR, with current value the string 'Middle', and consider the following assignment statement:
SUBSTR ( CS , 2 , 1 ) := 'u' ;
SUBSTR here is the substring operator, and the effect of the assignment is to “zap” the second character position within CS, replacing the 'i' by a 'u' (after the update, therefore, the current value of CS is the string 'Muddle'). The expression on the left side of the assignment symbol “:=” is a pseudovariable reference.
For a second example, let LS be a view, defined as the restriction of relvar S to just suppliers in London, and consider the following DELETE statement:
DELETE LS WHERE STATUS > 15 ;
Logically speaking, this DELETE is equivalent to the following:
DELETE ( S WHERE CITY = 'London' ) WHERE STATUS > 15 ;
In this expanded form (which isn’t, nor is it meant to be, valid Tutorial D syntax), the target of the DELETE is specified as an operational expression, or in other words a pseudovariable reference. As the example suggests, therefore, updating a view is logically equivalent to updating a certain pseudovariable (thus, views are pseudovariables, loosely speaking). Here’s the expanded form (again not valid Tutorial D syntax):
( S WHERE CITY = 'London' ) :=
( S WHERE CITY = 'London' ) WHERE NOT ( STATUS > 15 ) ;
And this latter simplifies in turn to the following (which is valid Tutorial D syntax):
S := S WHERE NOT ( CITY = 'London' AND STATUS > 15 ) ;
For a third example, showing that even updating a base relvar is in fact logically equivalent to updating a certain pseudovariable (and hence that base relvars too are really pseudovariables, logically speaking), see the examples under database variable.
public instance variable See instance variable.
QBE A relational language based on domain calculus. (Actually QBE incorporates aspects of both domain and tuple calculus, but the emphasis is on the former.) The name is an abbreviation for Query-By-Example. Unlike QUEL (q.v.), Tutorial D, and most other relational or would-be relational languages, QBE is explicitly designed for use with a display screen interface. To be more specific, it’s based on the idea of making entries in blank tables on the screen.
Example: A QBE formulation of the query “Get supplier names for suppliers who supply at least one part supplied by supplier S2” might look like this:
S │ SNO │ SNAME │ SP │ SNO │ PNO │
───┼─────┼───────┤ ───┼─────┼─────┤
│ _SX │ P._NX │ │ _SX │ _PX │
│ _S2 │ _PX │
To elaborate: The user here has asked the system to display two blank tables on the screen, one for suppliers and one for shipments, and has made entries in them as shown. Entries beginning with a leading underscore are “example elements” (in other words, domain calculus range variables); “S2” is a literal. (For simplicity, we ignore here the fact that supplier numbers are supposed to be of a user defined type, called SNO.) Thus, the user is asking the system to “print” or “present” (“P.”) supplier names _NX such that, if the supplier with supplier number _SX has that name_NX, then that supplier _SX supplies some part _PX, and that part _PX in turn is supplied by supplier S2. Note the implicit existential quantifications involved in this example. Here for comparison purposes is the same query expressed in pure domain calculus:
NX RANGES OVER { NAME } ;
SX RANGES OVER { SNO } ;
PX RANGES OVER { PNO } ;
{ NX } WHERE EXISTS SX ( EXISTS PX ( S { SNO SX , SNAME NX } AND
SP { SNO SX , PNO PX } ) AND
SP { SNO 'S2' , PNO PX } )
quantification Applying a quantifier (q.v.) to a free variable, thereby converting that free variable into a bound variable (see binding), and hence converting the predicate containing that free variable into a different predicate, logically distinct from the original. If the original predicate has n free variables and we quantify just m of them (m ≤ n), we obtain a k-place predicate, where k = n−m. Note: If m = n (i.e., if every free variable in the original predicate is quantified in this way), what results is a proposition.
quantifier See existential quantifier; universal quantifier. Note: Other quantifiers are possible—for example, “there exists exactly one of” (see UNIQUE); “for all but one of”; “there exists an odd number of”; and so on—but EXISTS and FORALL are far and away the ones most frequently encountered in practice.
Note: As explained under existential quantifier and universal quantifier, each of EXISTS and FORALL can be defined in terms of the other. It follows that either one could be dropped without any loss of functionality. But it’s desirable for psychological reasons to support both, because some problems are “more naturally” formulated in terms of EXISTS and others are “more naturally” formulated in terms of FORALL. Note, however, that SQL doesn’t really support either of these two quantifiers! It does support an operator it calls EXISTS, but that operator is indeed an operator and not a quantifier. In fact, it’s essentially the operator that Tutorial D calls IS_NOT_EMPTY, q.v.
QUEL A relational language, based on tuple calculus, that was at one time a serious competitor to SQL.
Example: Here’s a QUEL formulation of the query “Get supplier numbers for suppliers who supply at least one London part” (note the implicit existential quantification on shipments in particular):
RETRIEVE S.SNO
WHERE S.SNO = SP.SNO
AND SP.PNO = P.PNO
AND P.CITY = "London"
Here for comparison purposes is the same query expressed in pure tuple calculus:
SX RANGES OVER { S } ;
SPX RANGES OVER { SP } ;
PX RANGES OVER { P } ;
{ SX.SNO } WHERE EXISTS SPX ( EXISTS PX
( SX.SNO = SPX.SNO AND
SPX.PNO = PX.PNO AND
PX.CITY = 'London' ) )
query A retrieval request (i.e., a relational expression, or a statement that asks for the evaluation of such an expression). Sometimes used, loosely, to refer to update requests also; also used to refer to the informal natural language counterpart to some retrieval or update request.
Query-By-Example See QBE.
query decomposition A divide and conquer technique for evaluating relational expressions by recursively dividing them into subexpressions.
query rewrite See expression transformation.
quota query A query that imposes a desired limit, or quota, on the cardinality of the result.
Example: Here’s a possible, though perhaps a little tricky, formulation of the quota query “Get the three heaviest parts” (the quota here is three):
WITH ( q := 3 /* quota */ ,
t1 := P RENAME { WEIGHT AS WT } ,
t2 := EXTEND P : { N1 := COUNT ( t1 WHERE WT > WEIGHT ) } ,
t3 := t2 WHERE N1 < q ) :
t3 { ALL BUT N1 }
Note: Using the RANK shorthand, q.v., we could express this query more succinctly thus:
WITH ( q := 3 ) :
( ( RANK P BY ( DESC WEIGHT AS N2 ) ) WHERE N2 ≤ q ) { ALL BUT N2 }