This dictionary contains more than 600 entries dealing with issues, terms, and concepts
involved in, or arising from use of, the relational model of data. Many of the entries
include not only definitions but also one or more illustrative examples. I've done
my best to make the definitions as clear, precise, and accurate as possible; they're
based on my own best understanding of the material, an understanding I've been honing
gradually over some 35 years of involvement in this field.
I'd like to stress the point that the dictionary is, as advertised, relational.
To that end, I've deliberately omitted terms and concepts that are only tangentially
connected to relational matters (e.g., almost all details of the supporting type
theory, including type inheritance details in particular). I've also omitted various
topics that are part of database technology in general and aren't particular to
relational databases (e.g., security issues, the log, recovery and concurrency control,
and so forth). What's more, I've also omitted certain SQL terms and concepts thatthe
fact that SQL is supposed to be a relational language notwithstandingaren't really
relational at all (outer join, UNION ALL, and updating through a cursor are examples).
That said, I should add that I have deliberately included a few nonrelational terms
in order to make it clear that, contrary to popular opinion, the concepts in question
are indeed not relational (index is a case in point
here).
I must explain too that this is a dictionary with an attitude. It's my very firm
belief that the relational model is the right and proper foundation for database
technology and will remain so for as far out as anyone can see, and many of the
definitions in what follows reflect this belief. As I said in my book
Database in Depth: Relational Theory for Practitioners (O'Reilly):
In addition, I haven't hesitated to mark some term or concept as deprecated if I
believe there are good reasons to avoid it, even if the term or concept in question
is in widespread use at the time of writing. Materialized
view is a case in point here.
The examples that illustrate the definitions are based for the most part on the
familiarnot to say hackneyedsuppliers-and-parts database. I apologize for dragging
out this old warhorse yet one more time, but I believe that using the same example
in a variety of different publications can be a help, not a hindrance, to learning.
Here are the relvar definitions (and if you aren't familiar with the term
relvar, then please check the corresponding dictionary entry!):
The following list summarizes key technical issues underlying the presentation of
terms, concepts, and examples in the dictionary:
A
A relationally complete, "reduced instruction set" version of relational algebra
with only two operatorsREMOVE (essentially projection over all attributes but one)
and an algebraic analog of either NAND or NOR, q.v. The name is a doubly recursive
acronym: it stands for ALGEBRA, which in turn stands
for A Logical Genesis Explains Basic Relational Algebra.
As this expanded name suggests, it is designed in such a way as to emphasize its
close relationship to, and solid foundation in, the discipline of predicate logic,
q.v.
ad hoc polymorphism
Overloading.
aggregate operator
A read-only operator that derives a single value (typically but not necessarily
scalar) from the set or bag of values appearing as values of some attribute of some
relation. Contrast summary. Note: If (a) the argument to some aggregate operator
invocation is empty, and (b) that aggregate operator is essentially just shorthand
for repeated invocation of some scalar operator (e.g., the scalar operator is "+"
in the case of the aggregate operator SUM), and (c) an identity value exists for
that scalar operator (the identity value is 0 in the case of "+"), then the result
of that invocation is that identity value.
Example: Let ST be a variable of type INTEGER.
Then the following statement assigns to ST the sum of the status values for suppliers
in London:
ST := SUM ( S WHERE CITY = 'London', STATUS ) ;
ALGEBRA
See A.
algebra
1. Generically, a formal system consisting of a set of objects and a set of operators
that together satisfy certain laws and properties (certainly closure, probably commutativity
and associativity, and so on). The word algebra itself derives from Arabic al-jebr, meaning a resetting (of something broken)
or a combination. 2. Relational algebra specifically (if the context demands).
alias
Deprecated term used in some SQL products to mean either a tuple calculus range
variable or the name of such a variable. The term table alias
(also deprecated) is also sometimes used with the same meaning.
ALL BUT
See projection.
ALPHA
A proposal, due to Codd, for a concrete relational language based on tuple calculus;
also known as Data Sublanguage ALPHA. ALPHA was never implemented, but its ideas
were influential on the design of QUEL and (to a much lesser extent) SQL.
alternate key
Loosely, a candidate key that isn't the primary key. More precisely, let relvar
R have primary key PK;
then AK is an alternate key for
R if and only if AK is a candidate key
for R that isn't PK.
The term isn't much used.
AND
See conjunction.
appearance
(Of a value) An occurrence of a value (in some
context). Observe that there's a logical difference between a value as such and
an appearance of that valuefor example, an appearance as the current value of some
variable or as some attribute value within the current value of some tuplevar or
relvar. Each such appearance consists internally of some physical representation
of the value in question (and distinct appearances of the same value might have
distinct physical representations). Thus, there's also a logical difference between
an appearance of a value, on the one hand, and the physical representation of that
appearance, on the other; there might even be a logical difference between the physical
representations used for distinct appearances of the same value. All of that said,
however, it's common to abbreviate physical representation
of an appearance of a value to just appearance of a
value, or (more often) simply value,
as long as there's no risk of ambiguity in doing so. Note that
appearance of a value is a model concept, whereas physical
representation of an appearance is an implementation conceptusers
certainly might need to know whether two variables contain appearances of the same
value, but they don't need to know whether those appearances use the same physical
representation.
Example: Let N1 and N2 be variables of type INTEGER.
After the following assignments, then, N1 and N2 both contain an appearance of the
integer value 3. The corresponding physical representations might or might not be
the same (for example, N1 might use a binary representation and N2 a packed decimal
representation), but it's of no concern to the user either way.
N1 := 3 ;
N2 := 3 ;
argument
An actual operand that replaces some parameter of some operator when that operator
is invoked. The operand is either a value (denoted by some expressionpossibly just
a variable reference) or, if and only if the parameter in question is subject to
update, a variable (denoted by some variable reference). Contrast
parameter.
Examples: Let operator DOUBLE be defined as follows:
OPERATOR DOUBLE ( X INTEGER ) RETURNS INTEGER ;
RETURN ( 2 * X ) ;
END OPERATOR ;
Here, X is a parameter of declared type INTEGER. Let N be a variable of type INTEGER.
Then, for example, DOUBLE(N+1) is an invocation of DOUBLE, and the value of the
expression N+1 at the time of that invocation is an argument to that invocation.
That invocation is itself an expression in turn, and it can appear wherever an integer
literal can appear (because operator DOUBLE is defined to return a value of type
INTEGER).
Now suppose DOUBLE is defined as an update operator instead of a read-only one:
OPERATOR DOUBLE ( X INTEGER ) UPDATES { X } ;
X := 2 * X ;
END OPERATOR ;
Now the parameter X is subject to update, and any argument corresponding to X must
be a variable. Thus, e.g., DOUBLE(N) is a valid invocation of DOUBLE, and the variable
Nnot the value of that variableis the argument to that invocation. (Note that, for
example, DOUBLE(N+1) would be a syntax error, because N+1 isn't a variable reference.)
However, that invocation DOUBLE(N) isn't an expression, and it can't appear "wherever
an integer literal can appear"; instead, it can appear only in an explicit CALL
statement (or equivalent), as here:
CALL DOUBLE ( N ) ;
arity
Degree. The term isn't used much.
Armstrong's inference rules
(For FDs) Let A, B,
and C be arbitrary subsets of the heading of some
given relvar. Let AC denote the set theory union
of A and B, and
likewise for BC. Then Arm-strong's rules (also
known as Armstrong's axioms) state that (a) if A
is a superset of B, then
A
B (the reflexivity rule); (b) if A
B, then AC
BC (the augmentation rule); and (c) if A
B and B
C, then A
C (the transitivity rule). These rules are both sound
and complete (see completeness; soundness).
Examples: Let s be a set of FDs and let s include
the FD A
BC. Then the FD A
B is implied by s and can easily
be derived using Armstrong's rules as follows: (a) A
BC (given); (b) BC
B (reflexivity); hence (c) A
B (transitivity).
By way of a second example, if the set s includes the FDs
A
B and C
D, then the FD AX
BD (where X is the set theory
difference between C and
B, in that order) is implied by s. Note:
This example, which is due to Darwen, can be regarded as another inference rule.
It has the interesting property that the augmentation and transitivity rules, as
well as several other rules that are not discussed in detail here, are all special
cases.
arrow
See functional dependency.
assignment
An operator that assigns a value (denoted by an expression) to a variable (denoted
by a variable reference). The value and the variable must be of the same type. Note: Every update operator invocation is semantically
equivalent to some assignment (possibly a multiple assignment, q.v.).
Assignment Principle, The
After assignment of value v to variable
V, the comparison v = V is required
to evaluate to TRUE.
associative
Let Op be a dyadic operator, and assume for definiteness
that Op is expressed in infix style. Then Op is associative if and only if, for all
x, y, and z, x Op (y Op z) = (x Op y) Op z.
Examples: In ordinary arithmetic, addition ("+")
is associative, because
x + ( y + z ) = ( x + y ) + z
for all numbers x, y, and
z. Likewise, "||" (string concatenation) is associative, because
x || ( y || z ) = ( x || y ) || z
for all strings x, y, and z. (We remark in passing
that "+" is also commutative, q.v., but "||" is not.) In the same kind of way, UNION
and JOIN are associative in relational algebra (by contrast, MINUS is not). Likewise,
AND, OR, and EQUIV are associative in logic (by contrast, IMPLIES is not).
associative addressing
Addressing by value instead of position. All addressing is associative in the relational
model, implying among other things that pointers (as that term is usually understood)
are explicitly rejected.
atomic predicate
A simple predicate.
atomic proposition
A simple proposition.
atomic statement
(Programming languages) Syntactically, a statement
that contains no other statements nested inside itself (contrast
compound statement); semantically, a statement that is guaranteed
either to execute in its entirety or to have no effect, except possibly for returning
a status code. All syntactically atomic statements are semantically atomic in the
relational model. (The converse isn't true, incidentally; to be specific, multiple
assignment, q.v., is semantically but not syntactically atomic.)
atomic value
Old-fashioned and somewhat deprecated term for a scalar value.
attribute
Loosely, a column; more precisely, an <attribute name, type name> pair, though
it's common to refer informally to a given attribute by its attribute name alone.
(This simplified form is acceptable because the relational model requires attribute
names to be unique within the pertinent heading, and those names thus effectively
imply the corresponding type names.)
Examples: In the suppliers-and-parts database,
(a) the pair <SNAME,NAME> is an attribute of relvar S; (b) the pair <S#,S#>
is an attribute of both relvar S and relvar SP. We might also say, more simply but
less formally, that (a) SNAME is an attribute of relvar S, and (b) S# is an attribute
of both relvar S and relvar SP. These two attributes are of types NAME and S#, respectively.
attribute constraint
An integrity constraint to the effect that a given attribute of a given relvar is
declared to be of a given type.
Example: Attribute SNAME of relvar S is declared
to be of type NAMEi.e., it's constrained to contain values of type NAME.
attribute extractor
An operator for extracting the value of a specified attribute from a specified tuple.
Example: Let t
denote the supplier tuple from Figure
1 for supplier S1. Then the following expression extracts the status value
from that tuple:
STATUS FROM t
attribute FROM
Tutorial D syntax for an attribute extractor
(q.v.).
attribute renaming
See renaming.
attribute type
See attribute.
attribute value
See tuple value.
augmentation
See Armstrong's inference rules.
axiom
Something assumed to be true, available for use in the derivation of further truths
(i.e., theorems, q.v.). In a database, the tuples in the base relations can be regarded
as axioms, because they represent propositions that are assumed to be true. An axiom
is a special case of a theorem.
Example: The tuple <S1,Smith,20,London> in
the relation that's the current value of base relvar S represents the (presumably
true) proposition "Supplier S1 is under contract, is named Smith, has status 20,
and is located in London."
bag
Very loosely, a "set" that permits duplicates; more precisely, a collection of objects,
called elements, in which the same element can appear any number of times.
Example: The collection (b,b,a,c,b,c);
equivalently, the collection (a,b,b,b,c,c).
base relation
The value of a given base relvar at a given time. Contrast
derived relation.
Examples: The relations that are the values of
relvars S, P, and SP at any given time.
base relvar
A relvar that is not defined in terms of others; i.e., an independent relvar. Contrast derived relvar. Note: It's
a popular misconception that base relvars are physically stored, in the sense that
they're represented in storage by physical files, and their tuples and attributes
are represented in storage by records and fields within those files (see
direct image). But the relational model deliberately has nothing
to say about physical storage; in particular, it categorically doesn't say that
base relvars, as such, are physically stored (neither in the foregoing sense, nor
in any other). The only requirement is that there must be some defined correspondence
between what's physically stored and what's perceived by the user (i.e., base relvars
or derived relvars or a mixture of both).
Examples: Relvars S, P, and SP.
base table
SQL analog of either a base relation or a base relvar, as the context demands. See also table.
BCNF
Boyce/Codd normal form.
BI-IMPLIES
Same as EQUIV.
bijection
A mapping, or function, from set s1 to set s2 such that each element of s2
is the image of exactly one element of s1; equivalently,
a mapping that is both an injection and a surjection (in other words, a one-to-one
correspondence, in the strict sense of that term, from s1
to s2). Also known as a bijective or "one-to-one
onto" mapping. Note that if a given mapping is bijective, then it has an inverse
mapping that's bijective as well.
Example: The mapping from integers
x to their successors x+1 is a bijection
from the set of all integers to itself, and so is the inverse mapping from integers
x to their predecessors x-1.
binary
Of degree two.
body
A set of tuples that are all of the same type; more specifically, the set of tuples
appearing in a given relation, or in a given relvar at a given time. Every subset
of a body is itself a body.
Examples: The set of tuples appearing in relvar
S at any given time; any subset of that set.
BOOLEAN
A scalar data type (the only one required by the relational model) that contains
just the two truth values TRUE and FALSE.
boolean expression
An expression denoting a truth value.
boolean value
TRUE or FALSE.
bound variable
In logic, a variablemore precisely, an occurrence within a predicate of a variable
referencethat either (a) appears within the scope of a quantifier that explicitly
specifies that variable, or (b) is that explicit specification itself. (The term
variable is used here in the sense of logic, not
in the programming language sense.) Contrast
free variable.
Examples: Let the symbols
x and y denote integers. Then the following
expressions are both predicates, and x appears
as a bound variable, twice, in each of them:
EXISTS x ( x > 3 )
EXISTS x ( x > 3 ) AND y < 7
The first of these predicates is in fact a proposition, and its meaning is: "There
exists an integer x such that
x is greater than three" (a proposition that evaluates to TRUE, of course).
By contrast, the second predicate is not a proposition, because it involves a free
variable (namely, y) as well as the two bound ones;
thus, it has no truth value.
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,
q.v.:
S WHERE EXISTS SP ( SP.S# = S.S# )
The expression following the keyword WHERE here is a predicate, and the references
to SP in that predicate are bound (by contrast, the reference to S is free). 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
sensebut that's because we've indulged in a certain sleight of hand, as it were.
Here's an extended version of the same example that should help to clarify matters:
SX RANGES OVER { S } ;
SPX RANGES OVER { SP } ;
SX WHERE EXISTS SPX ( SPX.S# = SX.S# )
Here SX and SPX have been explicitly declared as variables in the sense of logic,
ranging over (the current values of) relvars S and SP, respectively. Now it's the
references to SPX that are bound and the reference to SX that's free. 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. We remark that SQL includes a rule of exactly this kind.
Boyce/Codd normal form
Relvar R is in Boyce/Codd normal form (BCNF) if
and only if for every nontrivial FD A
B satisfied by R, A is a superkey for
R; equivalently, if and only if every nontrivial
FD satisfied by R is implied by some superkey of
R. Every BCNF relvar is in 3NF.
Note: BCNF is "the" normal form with respect to FDs. Also, although being
in BCNF clearly doesn't preclude being in the next higher normal form (4NF) as well,
the term BCNF is often used loosely to refer to
a relvar that's in BCNF and not in 4NF.
Example: With the normal forms, it's often more
instructive to show a counterexample rather than an example per se. Suppose, therefore,
that relvar SP has an additional attribute SNAME, representing the name of the applicable
supplier; suppose also that supplier names are necessarily unique (i.e., no two
suppliers ever have the same name at the same time). This revised version of SP
has two keys, {S#,P#} and {SNAME,P#}, and every subset of the heading{QTY} in particularis,
of course, functionally dependent on both of them. However, the relvar also satisfies
the FDs {S#}
{SNAME} and {SNAME}
{S#}; these FDs are certainly not trivial, nor are they "arrows out of superkeys,"
so the relvar isn't in BCNF (though it is in 3NF).
business rule
See relvar predicate.
calculus
1. Generically, a system of formal computation. (The Latin word
calculus means a pebble, perhaps used in counting or some other form
of reckoning.) 2. Relational calculus specifically (if the context demands).
candidate key
Loosely, a unique identifier. More precisely, let K
be a subset of the heading of relvar R; then K is a candidate key (key for short) for
R if and only if (a) no possible value for R
contains two distinct tuples with the same value for K
(the uniqueness property), while (b) the same can't be said for any proper subset
of K (the irreducibility property). Note that every
relvar, base or derived, has at least one key. Note too that, by definition, keys
are sets of attributes; however, if the set of
attributes constituting some key K contains just
one attribute A, then it's common (though strictly
incorrect) to speak informally of that attribute A
per se as being that key.
Examples: In the suppliers-and-parts database,
{S#}, {P#}, and {S#,P#} are the sole keys for relvars S, P, and SP, respectively.
Note that {SNAME} isn't a key for S, because values of {SNAME} aren't necessarily
unique (though the values shown in
Figure 1 do happen to be unique). Note too that, for example, {S#,CITY}
isn't a key for S either, because although its values are necessarily unique, it
isn't irreducible (we could discard the CITY attribute, and what remained would
still satisfy the uniqueness property).
canonical form
Given a set s1, together with a notion of equivalence
among the elements of that set, subset s2 of s1 is a set of canonical forms for
s1 if and only if every element x1
in s1 is equivalent to just one element
x2 in s2 (and that element
x2 is the canonical form for the element x1).
Various "interesting" properties that apply to x1
also apply to x2; thus, we can study just the small
set s2, not the large set
s1, in order to prove a variety of "interesting" theorems or results.
Example: Let s1
be the set of nonnegative integers and let any two such integers be equivalent if
and only if they leave the same remainder on division by five. Then we can define
s2 to be the set {0,1,2,3,4}. As an example of an "interesting" theorem that applies
here, let x1, y1, and z1
be any three elements of s1, and let their canonical
forms in s2 be x2, y2,
and z2, respectively; then the product
y1 * z1 is equivalent to x1 if and only
if the product y2 * z2 is equivalent to
x2.
cardinality
The number of elements in a bag or (especially) set; hence, of a relation, the number
of tuples in that relation. Also used (a) of a relvar, to mean the number of tuples
in the relation that's the value of that relvar at a given time; (b) of an attribute
of a relation or relvar, to mean the cardinality of the set of distinct values of
that attribute appearing in that relation or relvarat a given time, in the case
of a relvar. (Of course, the cardinality of attribute A
of relation r is the same as the cardinality of
the projection r{A} of that relation over that
attribute; definition (b) here is thus strictly redundant.)
Examples: In
Figure 1, (a) the cardinality of the relation that's the current value of
relvar SP is 12 (and the cardinality of relvar SP is thus currently 12 also); (b)
the cardinality of attribute S# in that relation is 4 (and the cardinality of that
attribute in relvar SP is thus currently 4 also).
cartesian product
1. (Dyadic case) The cartesian product of two relations
r1 and r2, r1
TIMES r2, where r1
and r2 have no attribute names in common, is a
relation with heading the set theory union of the headings of
r1 and r2 and with 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) The cartesian
product of n relations r1,
r2, …, rn (n
0),
TIMES {r1,r2,…,rn}, where no two of r1, r2, …, rn have any attribute names in common,
is a relation with heading the set theory union of the headings of
r1, r2, … , rn and with body the set of all tuples
t such that t is the set theory
union of a tuple from r1, a tuple from
r2, …, and a tuple from rn. Note:
The relational cartesian product operator differs in several respects from the mathematical
operator of the same name (and is sometimes explicitly said to be an expanded, or
extended, cartesian product for that reason). In fact, it's a special case of join,
q.v.
Example: Let r1
and r2 be the projections S{S#} and P{P#}, respectively.
Then the cartesian product r1 TIMES
r2 contains all possible tuples of the form <s#,p#>,
where s# is an S#
value currently appearing in relvar S and p# is a P# value
currently appearing in relvar P, and no other tuples. (Given the values in Figure 1, the result has cardinality 30.)
Note that the expression (S{S#}) TIMES (P{P#}) is semantically equivalent to the
expression (S{S#}) JOIN (P{P#}).
catalog
Within a given database, a set of relvars that describe that database (including
the catalog relvars themselvesi.e., the catalog is self-describing). Such relvars
are sometimes said to contain metadata, q.v. Catalog relvars are usually updated
not by explicit assignment operations but rather by more user-friendly data definition
operators, q.v. (which are nevertheless essentially just shorthand for certain relational
assignments).
closed WFF
A WFF that denotes a proposition.
Closed World Assumption, The
The assumption that (a) if a given tuple appears in a given relvar at a given time,
then the proposition represented by that tuple is true at that time, and (b) if
a given tuple could appear in that relvar at that time but doesn't, then the proposition
represented by that tuple is false at that time. At any given time, in other words,
the relvar contains all and only those tuples that correspond to true propositionsthat
is, invocations, or instantiations, of the relvar predicate that evaluate to TRUEat
that time. Note: The foregoing definition is phrased
in terms of a relvar specifically. However, a precisely analogous definition applies
to relations also.
Examples: The tuple <S1,P1,300> currently
appears in relvar SP; we can therefore assume that it currently is the case that
supplier S1 supplies part P1 in quantity 300. By contrast, the tuple <S5,P6,250>
doesn't currently appear, though presumably it could; we can therefore assume that
it's not currently the case that supplier S5 supplies part P6 in quantity 250.
closure
1. (Of a set of attributes) The set of all attributes
A such that the set {A}
is functionally dependent on the given set. 2. (Of a set of
FDs) The set of all FDs implied by the given set. 3.
(Of relational algebra) The property that the result of every algebraic
operation is a relation.
closure, transitive
See transitive closure.
CNF
Conjunctive normal form.
Codd, E. F
The inventor of the relational model. See especially his papers (a) "Derivability,
Redundancy, and Consistency of Relations Stored in Large Data Banks," IBM Research
Report RJ599, August 19th, 1969 (the very first publication on the relational model);
(b) "A Relational Model of Data for Large Shared Data Banks,"
CACM 13, No. 6, June 1970 (a revised and extended version of that first
paper); and (c) "Relational Completeness of Data Base Sublanguages," in Randall
Rustin (ed.), Data Base Systems: Courant Computer
Science Symposia 6, Prentice Hall (1972). The last of these papers in particular
contains formal definitions of tuple calculus and Codd's original relational algebra,
also of Codd's reduction algorithm, q.v.
Codd's reduction algorithm
An algorithm for reducing an arbitrary tuple calculus expression to a semantically
equivalent relational algebra expression. Among other things, the algorithm relies
on the fact that the operators projection and division are algebraic counterparts
to the existential quantifier and the universal quantifier, respectively, of tuple
calculus.
codomain
See function
coercion
Implicit type conversion (usually best avoided).
column
1. SQL analog of (a) an attribute of some relvar, or (b) an attribute of some relation,
or (c) the bag of values of some attribute of some relation, or sometimes even (d)
an attribute of some tuple, or (e) the value of some attribute of some tuple (as
the context demands). 2. More generally, a picture of an attribute (on paper, for
example). See also table.
commutative
Let Op be a dyadic operator, and assume for definiteness
that Op is expressed in infix style. Then Op is commutative if and only if, for all
x and y, x Op y = y Op x.
Examples: In ordinary arithmetic, addition ("+")
is commutative, because
x + y = y + x
for all x and y.
In the same kind of way, UNION and JOIN are commutative in relational algebra (by
contrast, MINUS is not). Likewise, AND, OR, and EQUIV are commutative in logic (by
contrast, IMPLIES is not). Note: It so happens
that all of the operators just mentioned are not only commutative but associative.
An example of an operator that's commutative but not associative is NOR, q.v.
comparison
A boolean expression of the form (exp1) theta (exp2), where exp1
and exp2 are expressions of the same type T and theta is any
comparison operator that makes sense for values of type T
(certainly "=" or "
",
perhaps ">" also, and so on). Note: The parentheses
enclosing exp1 and exp2
in the comparison might not be needed in practice.
complement
(Of a relation) Let r be a relation with heading
{H} and body {b}.
Then the complement of r is the unique relation
with heading {H} and body consisting of all tuples
with heading {H} that don't appear in {b}.
complement (set theory)
The set of all elements not appearing in a given set.
completeness
(Not to be confused with relational completeness, q.v.)
The property of a formal system according to which, given a set s of sentences of
the system, all sentences implied by those in s can be derived using the rules of
inference of that system (i.e., all tautologies are theorems).
Contrast soundness.
component
(Of a tuple) See tuple component.
composite attribute
Deprecated term for a combination of two or more attributes. The term is deprecated
because a "composite attribute" isn't actually an attribute at all.
composition
The composition of relations r1 and
r2, r1 COMPOSE r2, is the join of
r1 and r2, projected over all attributes
not common to r1 and r2.
See also tuple composition.
Example: Consider the expression S COMPOSE SP.
If the current values of relvars S and SP are s
and sp, respectively, this expression yields a
relation of type RELATION {SNAME NAME, STATUS INTEGER, CITY CHAR, P# P#, QTY QTY},
with body consisting of all tuples of the form <n,st,c,p#,q>
such that there exists some supplier number s#
such that the tuple <s#,n,st,c> appears in
s and the tuple <s#,p#,q>
appears in sp.
compound predicate
A predicate that involves at least one connective.
compound proposition
A proposition that involves at least one connective.
compound statement
Syntactically, a statement that isn't atomic; i.e., a statement that contains other
statements nested inside itself.
Examples: Conventional IF, DO, WHILE, and CASE
statements; BEGIN … END … statement blocks; and many others.
conditional expression
A boolean expression.
conjunct
A predicate that's ANDed with zero or more others.
conjunction
If p and q are
predicates, their conjunction (p) AND (q)
is a predicate also. Let (pi) AND (qi)
be an invocation of that predicate (where pi and
qi are invocations of p
and q, respectively). Then that invocation (pi) AND (qi) evaluates
to TRUE if and only if pi and qi both evaluate to TRUE. Note:
The parentheses enclosing p and
q in the conjunction might not be needed in practice.
conjunctive normal form
A predicate is in conjunctive normal form, CNF, if and only if it's of the form
(p1) AND (p2)
AND … AND (pn), where none of the conjuncts
(p1), (p2), …, (pn) involves any ANDs.
connective
A monadic or dyadic logical operator. There are exactly 20 connectives in two-valued
logic, 4 monadic and 16 dyadic. The most commonly encountered ones are NOT (negation),
AND (conjunction), OR (disjunction), IMPLIES (implication), and EQUIV (equivalence);
others include NAND, NOR, and XOR, q.v. Note: A
variety of other symbols and keywords are also used to denote these connectives.
consistency
Integrity. Contrast correctness.
consistent
(Of a database) Satisfying all defined integrity
constraints.
constraint
An integrity constraint.
contradiction
A predicate whose every possible invocation is guaranteed to yield FALSE, regardless
of what arguments are substituted for its parameters. Contrast
tautology.
Examples: Let p1
be the predicate (actually a proposition) 2+2 = 5; let p2
be the predicate x > x,
where x is an arbitrary integer; and let p3 be
the predicate (p) AND (NOT(p)),
where p is an arbitrary predicate. Then
p1, p2, and p3 are all contradictions.
controlled redundancy
Redundancy (q.v.) is controlled if it does exist (and the user is aware of it),
but the task of "propagating updates" to ensure that it never leads to any inconsistencies
is managed by the DBMS, not the user. Uncontrolled redundancy can be a problem,
but controlled redundancy shouldn't be. As a general rule, databases shouldn't include
any uncontrolled redundancy.
correct
See correctness.
correctness
(Of a database) The property of truly reflecting
the state of affairs that exists in the real world. Contrast
consistency.
correlation name
SQL term for either a tuple calculus range variable or the name of such a variable.
cover
(Of a set of FDs) If s1
and s2 are sets of FDs, then
s2 is a cover for s1 if and only if
every FD implied by s1 is implied by
s2. Note: Some writers use the term cover
in a stronger sense, to mean a set of FDs that's equivalent to some given set. See equivalence.
cross join / cross product
Cartesian product.
CWA
The Closed World Assumption.
D_UNION
See disjoint union.
data definition operator
An operator that either (a) defines some database object, such as a base relvar
or a view or a snapshot or a constraint, or (b) deletes or updates such a definition;
in other words, an operator that updates the catalog.
Examples: See the definitions of relvars S, P,
and SP. Other examples could be (a) an operation to add an attribute to one of those
relvars, or (b) an operation to define a constraint on those relvars, or (c) an
operation to drop one of those relvars or a constraint entirely.
data independence
1. (Physical) The ability to change the physical
design of a database without having to make corresponding changes in the way the
database is perceived by users. 2. (Logical) The
ability to change the logical design of a database without having to make corresponding
changes in the way the database is perceived by users.
data manipulation operator
Loosely, an operator that isn't a data definition operator. However, the distinction
isn't hard and fast; in fact, it's difficult to find an operator that doesn't, in
the final analysis, "manipulate" data of some kind (unless it's a read-only operator,
possibly; some authorities might argue that only update operators "manipulate" data).
The term is probably best avoided.
data model
1. An abstract, self-contained, logical definition of the data structures, data
operators, and so forth, that together make up the abstract machine with which users
interact (contrast implementation).
2. A model of the persistent data of some particular enterprise (i.e., a logical
database design).
Examples: The most obvious example of the first
definition is the relational model. Note that we can sum up the distinction between
a data model in this first sense and an implementation of that model by saying that
the model is what the user has to know, while the implementation is what the user
doesn't have to know. As for the second definition, any logical database design
will suffice as an example.
data sublanguage
A language that provides database support for one or more distinct host languages
(q.v.) in which it can be embedded or from which it can be invoked.
Data Sublanguage ALPHA
See ALPHA.
data type
Type.
database
Strictly, a database value, q.v.; more commonly used, in this dictionary in particular,
to refer to what would more accurately be called a database variable, q.v. We assume
throughout this dictionary that databases are always relational, barring explicit
statements to the contrary. Note: The term database is also used in nonrelational contexts to
mean a variety of other things: for example, a collection of physically stored data.
It's also used, all too frequently, to mean a DBMS, but this particular usage is
strongly deprecated. (If we call the DBMS a database, what do we call the database?)
database constraint
1. ("A" database constraint) An integrity constraint
that isn't a type constraint; informally, an integrity constraint that refers to
two or more distinct relvars. 2. ("The" database constraint)
The logical AND of all integrity constraints, apart from type constraints, that
apply to a given database (the database constraintsometimes
called the total database constraintfor the database
in question).
Examples: First, the key and foreign key constraints
specified in the definition of the suppliers-and-parts database are all database
constraints. Second, here are some more database constraints that might apply to
that database:
CONSTRAINT C1 IS_EMPTY
( S WHERE STATUS < 1 OR STATUS > 100 ) ;
/* status values must be in the */
/* range 1 to 100 inclusive */
CONSTRAINT C2 IS_EMPTY
( P WHERE CITY = 'London' AND COLOR
'Red' ) ;
/* parts in London must be red */
CONSTRAINT C3 IS_EMPTY
( ( S JOIN SP )
WHERE STATUS < 20 AND P# = P#('P6') ) ;
/* no supplier with status less */
/* than 20 can supply part P6 */
Finally, suppose for the sake of the example that the specified key and foreign
key constraints, together with constraints C1-C3, are the only database constraints
that apply to the suppliers-and-parts database. Then the logical AND of all of them
is "the" (total) database constraint for that database.
database design
See logical database design; physical database
design.
database management system
The software system (the DBMS) that controls all access to some database or collection
of databases. Contrast database.
database programming language
A programming language that includes fully integrated ("native") database support.
Contrast data sublanguage; host language.
database value
A possible "state" for some database; i.e., a collection of relations, those relations
being possible values for the applicable relvars. Conceptually, therefore, a database
value can be thought of as a set of propositions, those propositions corresponding
to the tuples in the applicable relations. Contrast
database variable.
Example: The relations (i.e., relation values)
shown in Figure 1 constitute
the "state" of the suppliers-and-parts database that happens to be current at some
particular time. But if we were to look at that database at some different time,
we would probably see a different state. In other words, the database is really
a variablea database variable, to be precise, meaning a variable whose values are
database values. Moreover, the tuples in the relations that are the values of relvars
S, P, and SP at any given time represent propositionspropositions that are assumed
by convention to be true at that time, so the database at the time in question can
be thought of as a set of true propositions.
database variable
Loosely, a container for relvars; more accurately, a variable whose value at any
given time is a database value. Strictly speaking, there's a logical difference,
precisely analogous to that between relation values and relation variables, between
database values and database variables. To be specific, what we usually call a database
is really a variable (typically a rather large one), and updating that database
has the effect of replacing one value of that variable by anotherwhere the values
in question are database values and the variable is a database variable. More precisely
still, a database is a tuple variable, with one attribute (relation-valued) for
each relvar in the database in question. Note, therefore, that a database variable
isn't really a set of relation variables, even though we often think of it that
way informally. All of that said, however, we bow to traditional usage elsewhere
in this dictionary and use the term database to
refer to both database values and database variables, relying on context to make
it clear which is intended.
Example: See database value. As
for the matter of a database really being a tuple variable, the suppliers-and-parts
database in particular can be thought of as a tuple variable of the following tuple
type:
TUPLE { S RELATION { S# S#, SNAME NAME,
STATUS INTEGER, CITY CHAR },
P RELATION { P# P#, PNAME NAME, COLOR COLOR,
WEIGHT WEIGHT, CITY CHAR },
SP RELATION { S# S#, P# P#, QTY QTY } }
DBMS
Database Management System; plural DBMSs.
dbvar
A database variable.
DCO
Domain check override.
De Morgan's Laws
1. (Logic) The negation of the disjunction of predicates
p and q is equivalent
to the conjunction of the negations of p and q; the negation of the conjunction of predicates
p and q is equivalent
to the disjunction of the negations of p and q. 2. (Set theory)
The complement of the union of sets s1 and s2 is equal to the intersection of the complements
of s1 and s2;
the complement of the intersection of sets s1 and
s2 is equal to the union of the complements of
s1 and s2.
decidability
The property of a formal system according to which, given an arbitrary sentence
s, it can be determined whether or not s is a sentence of the system.
Note: Propositional calculus is decidable; predicate calculus is not.
declared type
1. (Of a value) The type of the value in question.
2. (Of a variable or an attribute) The type specified
when the variable or attribute in question is defined. 3.
(Of an expression) The type of the value denoted by the expression in
question. Note: The term
declared type can safely be reduced to type
if inheritance is not supported.
decomposition
Nonloss decomposition (unless the context demands otherwise).
DEE
TABLE_DEE.
deferred checking
Checking an integrity constraint at some time (typically commit time) later than
the time at which an update is performed that might cause it to be violated. The
relational model rejects deferred checking as logically flawed.
Contrast immediate checking.
deferred constraint
A constraint for which the checking is deferred (see
deferred checking). The relational model rejects deferred constraints
as logically flawed. Contrast immediate constraint.
degree
The number n of attributes in a given heading,
key, tuple, tuplevar, relation, or relvar (n
0).
Examples: The degrees of relvars S, P, and SP are
four, five, and three, respectively; the degrees of the corresponding keys are one,
one, and two, respectively.
DELETE
Loosely, an operator that removes a given set of tuples from a given relvar. It's
shorthand for a certain relational assignment.
Example: The DELETE statement
DELETE S WHERE CITY = 'Athens' ;
is shorthand for the following relational assignment:
S := S WHERE NOT ( CITY = 'Athens' ) ;
DELETE rule
A specific kind of foreign key rule, q.v.
denormalization
Replacing a set of relvars R1, R2, … , Rn
by their join R, such that for all
i the projection of R over the attributes
of Ri is guaranteed to be equal to
Ri (i =1,2, … , n). Note: Denormalization (at least to a level
below 5NF) is always contraindicated from a logical point of view. Sometimes it
can't be avoided, however, given the level of technology found in today's commercial
products.
Example: A denormalization that might be applied
to the suppliers-and-parts database would be to replace relvars S and SP by their
join (SSP, say). Relvars S and SP could then be derived by projecting relvar SSP
over the attributes of S and the attributes of SP, respectively.
dependency
An IND or JD or MVD or (especially) FD.
dependency theory
A body of theory, built on top of the relational model, that can be used to help
with logical database design (though it's not limited to that purpose alone).
dependent
In an FD, the set of attributes on the right-hand side. Contrast
determinant.
Example: In the FD {S#,P#}
{QTY}, which is satisfied by relvar SP, {QTY} is the dependent and {S#,P#} is the
determinant.
dereferencing
See referencing.
derived relation
Loosely, a relation defined in terms of others. More precisely, let
s be a set of relations. Then relation r
is derived from those in s if and only if it doesn't
itself appear in s but can be obtained (by means
of some nonempty sequence of relational operations) from those that do. For the
purposes of this definition, (a) the only permitted operations are restriction,
projection, join, union, and difference; (b) the only permitted operands are relations
in s or relations derived from those in
s. Contrast base relation.
Example: Consider the expression S JOIN SP. If
the current values of relvars S and SP are s and
sp, respectively, this expression defines the derived
relation that is the join of s and
sp.
derived relvar
A relvar defined in terms of others (in particular, a view or snapshot, q.v.). Contrast base relvar.
determinant
In an FD, the set of attributes on the left-hand side. Contrast
dependent.
difference
The difference between two relations r1 and r2 (in that order), r1
MINUS r2, where r1
and r2 are of the same type
T, is a relation of type T with body
the set of all tuples t such that
t appears in r1 and not
r2. Note: The relational difference operator is a special case of
semidifference, q.v.
Example: The expression (S{CITY}) MINUS (P{CITY})
denotes the difference between the projections on CITY of the relations that are
the current values of relvars S and P (in that order). That difference is a relation
of type RELATION {CITY CHAR}. Moreover, if the current values of relvars S and P
are s and p, respectively,
the body of that relation consists of all tuples of the form <c>
that appear in s{CITY} and not
p{CITY}meaning c is a current supplier
city that isn't also a current part city. Note that the expression (S{CITY}) MINUS
(P{CITY}) is semantically equivalent to the expression (S{CITY}) NOT MATCHING (P{CITY})or
the simpler expression (S{CITY}) NOT MATCHING P, for that matter.
difference (set theory)
The set of all elements appearing in one given set and not in another.
Contrast symmetric difference.
direct image
A somewhat unsophisticated implementation style, found in most if not all of today's
mainstream database products, in which what's physically stored is effectively just
a direct image of what the user logically sees (i.e., relvars are stored as physical
files, and tuples and attributes are stored as records and fields within those files).
directed relationship
A (binary) relationship, in the sense of the third definition of that term.
disjoint
Sets s1 and s2
are disjoint if and only if they have no elements in common.
disjoint union
A version of the relational union operator for which the operand relations are required
to be disjoint, meaning they have no tuples in common. (This operation could obviously
be generalized to apply to sets in general as well as relations in particular.)
Example: Consider the expression (S{CITY}) D_UNION
(P{CITY}). If the current values of relvars S and P are as shown in Figure 1, this expression causes a run-time
error, because the operands aren't disjoint. If they were, however, the expression
would then be semantically equivalent to (S{CITY}) UNION (P{CITY}).
disjunct
A predicate that's ORed with zero or more others.
disjunction
If p and q are
predicates, their disjunction (p)OR(q)is
a predicate also. Let (pi)OR(qi)
be an invocation of that predicate (where pi and
qi are invocations of p
and q, respectively). Then that invocation (pi)OR(qi) evaluates
to TRUE if and only if at least one of pi and qi evaluates to TRUE. Note:
The parentheses enclosing p and
q in the disjunction might not be needed in practice.
disjunctive normal form
A predicate is in disjunctive normal form, DNF, if and only if it's of the form
(p1)OR(p2)OR …
OR (pn), where none of the disjuncts (p1),
(p2), …, (pn) involves any ORs.
distributive
1. Let operators OpM and
OpD be monadic and dyadic, respectively, and assume for definiteness
that OpD is expressed in infix style. Then OpM distributes over OpD
if and only if, for all x and
y, OpM(x OpD y) = (OpM(x)) OpD (OpM(y)). 2. Let operators
OpC and OpD both be dyadic, and
assume for definiteness that they're expressed in infix style. Then
OpC distributes over OpD if and only
if, for all x, y, and z,
x OpC (y OpD z) = (x OpC y) OpD (x OpC z).
Examples: In ordinary arithmetic, nonnegative square
root ("
") distributes
over multiplication ("*"), because
( x * y ) = ( x ) * ( y )
for all x and y;
also, multiplication distributes over addition ("+"), because
x * ( y + z ) = ( x * y ) + ( x * z )
for all x, y, and z.
In the same kind of way, restriction distributes over UNION, INTERSECT, and MINUS,
and INTERSECT distributes over UNION, in relational algebra.
DIVIDEBY
See division.
division
Let relations r1, r2, and
r3 be such that (a) the set {X}is the common attributes of
r1 and r3; (b) the set {Y}
is the common attributes of r2 and
r3; and (c) the sets {X} and {Y}
are disjoint. Then the division r1 DIVIDEBY r2 PER (r3)where
r1 is the dividend, r2
is the divisor, and r3 is the "mediator"is a relation
with the same heading as r1 and with body defined
as follows: tuple t appears in that body if and
only if it appears in r1, and a tuple <x,y> with x equal
to the X value in t appears in
r3{X,Y} for all tuples <y> appearing
in r2{Y}. Equivalently, the division
r1 DIVIDEBY r2 PER (r3)
is shorthand for the expression r1 WHERE r2{Y}
((r3 RENAME (X
AS Z)) WHERE Z = X){Y}. (The expression Z = X
here is a tuple comparison; the expression r2{Y}
(…){Y} is a relation comparison.)
Note: The division operator as just defined is sometimes known as the
Small Divide. A Great Divide can also be defined, but the details are beyond the
scope of this dictionary.
Example: The expression S DIVIDEBY P PER (SP) yields
a relation of the same type as relvar S, with body consisting of supplier tuples
for suppliers who supply all parts mentioned in relvar P. (Given the sample values
of Figure 1, the result
contains just the tuple for supplier S1.)
DK/NF
Domain-key normal form.
DNF
Disjunctive normal form.
domain
1. (Relational model) Type. Earlier relational
writings favored the term domain; more recent ones
favor the term type instead. 2.
(Mathematics) See function.
domain calculus
A version of relational calculus, semantically equivalent to tuple calculus (q.v.),
in which the range variables range over domains (types) instead of relations and
thus denote values from those domains.
Example: Here's a domain calculus formulation of
the query "Get supplier names for suppliers who supply at least one part" (see tuple calculus for a tuple calculus
analog):
NX RANGES OVER { NAME } ;
SX RANGES OVER { S# } ;
PX RANGES OVER { P# } ;
NX WHERE
EXISTS SX ( EXISTS PX ( S { S# SX, SNAME NX } AND
SP { S# SX, P# PX } ) )
In stilted English: "Get names NX where there exists a supplier number SX and there
exists a part number PX such that a tuple with supplier number SX and supplier name
NX appears in relvar S and a tuple with the same supplier number SX and part number
PX appears in relvar SP." As you can see, this particular example is somewhat clumsier
than its tuple calculus counterpart (see tuple
calculus), but there are also cases where the reverse is true.
domain check override
An ad hoc, flawed, and therefore deprecated mechanism for performing comparisons
between values of different types.
domain-key normal form
Relvar R is in domain-key normal form, DK/NF, if
and only if every constraint that applies to R
is implied by the attribute and key constraints that apply to
R.
Note: Attribute-key normal form would be a better
name. In any case, the concept is mainly of academic interest, because relvars can
easily fail to be in DK/NF and yet be fully normalized (i.e., in 5NF or even 6NF).
Example: As noted under Boyce/Codd normal form,
with the normal forms it's often more instructive to show a counterexample rather
than an example per se. Suppose, therefore, that shipments satisfy a constraint
to the effect that odd-numbered parts can be supplied only by odd-numbered suppliers
and even-numbered parts only by even-numbered suppliers (the example is very contrived,
of course, but it suffices for the purpose at hand). Then this constraint is clearly
not implied by the attribute and key constraints that apply to relvar SP, so SP
isn't in DK/NF; yet it's certainly in 6NF.
domain relational calculus
Domain calculus.
dot qualification
In tuple calculus, a dot-qualified name is an expression of the form
rx.A, where rx is the name of a range
variable and A is the name of an attribute of the
relation r over which rx
ranges. Such an expression serves as an attribute reference; it denotes the value
of attribute A in the particular tuple of r to which rx currently
refers. Dot qualification is used for disambiguation purposes in tuple calculusalso
in SQLbut not in domain calculus or relational algebra (these latter use attribute
(re)naming and name scoping to achieve the same purpose).
Example: The following tuple calculus formulation
of the query "Get suppliers who supply at least one part" makes use of two dot-qualified
names, SPX.S# and SX.S#:
SX RANGES OVER { S } ;
SPX RANGES OVER { SP } ;
SX WHERE EXISTS SPX ( SPX.S# = SX.S# )
For comparison, here is a relational algebra formulation of the same query:
S MATCHING SP
The "matching" here is based on the attribute name "S#", that attribute being the
only one common to relvars S and SP.
double arrow
See multivalued dependency.
double underlining
A convention, illustrated in Figure
1, for marking attributes that participate in primary keys.
dual mode principle
The principle that any relational operation that can be invoked interactively can
also be invoked from an application program.
DRC
Domain relational calculus.
DUM
TABLE_DUM.
duplicate
Let a1 and a2
be appearances (q.v.) in some context of values v1
and v2, respectively. Then
a1 and a2 are duplicates of each other
if and only if v1 and v2
are equal (in other words, if and only if v1 and
v2 are the very same value).
Note: It should be clear from this definition that the well-known dictum
to the effect that relations never contain duplicate tuples really means that no
relation ever contains duplicate appearances of
the same tuplethough we tend to stay with the less
precise formulation in this dictionary for reasons of familiarity. Observe that
because (a) relations never contain duplicate tuples and (b) every relational operation
yields a relation, it follows that duplicates are eliminated, if necessary, whenever
a relational operation is performed (meaning, more precisely, that redundant duplicate
tuple appearances are eliminated).
Examples (duplicate elimination): Given the sample
values shown in Figure 1,
the projection over CITY of the current value of relvar S has cardinality 3, not
5; similarly, the union of the projections over CITY of the current values of relvars
S and P has cardinality 4, not 11. (Note that, of the most familiar relational operators,
projection and union are the only ones for which duplicate elimination is a concern.
For the othersrestriction, join, and so onit's effectively a no op.)
duplicate elimination
See duplicate.
dyadic
(Of an operator) Having exactly two operands; i.e.,
being defined in terms of exactly two parameters.
E/R
Entity/relationship.
E/R diagram
See entity/relationship diagram.
E/R model
See entity/relationship model.
E/R modeling
See entity/relationship modeling.
element
See bag; set.
empty
(Of a bag or set) Having no elements.
empty foreign key
A foreign key of degree zero. Note: The matching
candidate key in the referenced relvar will necessarily also be of degree zero,
and the referential constraint will therefore be satisfied if and only if either
(a) the referenced relvar is non-empty, or (b) the referencing relvar is empty (or
both).
empty heading
The heading of degree zero (note that there's exactly one such).
empty key
A key of degree zero. Note that a relvar with an empty key can't have any other
keys in addition to the empty one, because of the irreducibility requirement on
keys (see candidate key). Note
too that such a relvar can't contain more than one tuple, because otherwise the
key constraint would be violated. Declaring relvar R
to have an empty key is thus a convenient way of imposing the constraint that R never has cardinality greater than one.
empty relation
A relation of cardinality zero (note that there's exactly one such for each possible
relation type).
Example: Suppose relvars S and P are both currently
empty; that is, their current values s and p are both empty relations. Then
s and p aren't equal, even though
their bodies are equal, precisely because they're of different types (equivalently,
because their headings aren't equal).
empty relvar
A relvar whose current value is an empty relation.
empty restriction
A restriction of a given relation r that contains
no tuples (i.e., is equal to r WHERE FALSE); in particular, a restriction of the
form r WHERE c,
where c is a contradiction (q.v.).
Examples: The expressions S WHERE STATUS = 25 and
S WHERE STATUS > STATUS are both empty restrictions (the second necessarily so,
because STATUS > STATUS is a contradiction).
empty set
The set with no elements (note that there's exactly one such). All theorems, properties,
definitions, etc., that apply to sets in general apply to the empty set in particular.
For example, relation headings and bodies are both defined as sets (of attributes
and tuples, respectively), so they are each allowed to be the empty set in particular.
empty tuple
The tuple of degree zero (note that there's exactly one such).
empty type
A type with no values. This concept is of crucial importance if inheritance is supported
but is perhaps of little use otherwise.
encapsulated
Scalar. Note: The term is also used, especially
in OO contexts, to refer to the physical bundling, or packaging, of code and data
(or operator definitions and data representation definitions, to be more precise).
But to use the term in this way is to mix model and implementation considerations;
the user shouldn't care, and shouldn't need to care, whether or not code and data
are physically bundled together.
entity
A thing. Note: It's frequently suggested that there
should be a one-to-one correspondence between "entities of interest" and tuples
in base relvars. The suggestion is hard to sustain, however, given that the term
entities of interest has no precise definition.
(Of course, the same is true of the term entity
itself, for that matter.)
entity integrity
The rule that attributes of primary keys in base relvars don't allow nulls. However,
since (a) relvars, base or otherwise, don't necessarily have to have primary keys
(see primary key), and (b) 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),
the entity integrity rule could be, and in fact has been, dropped without serious
loss. We mention it here mainly for historical reasons. In any case, it refers to
nulls, which aren't part of the relational model; it would thus require major revision
anyway before any suggestion that it be kept could be seriously entertained.
entity/relationship diagram
A picture intended to explicate the logical design of a given database at a level
of abstraction in which many detailsin particular, details of the underlying types
and almost all integrity constraintsare omitted.
entity/relationship model
A set of conventions for drawing entity/relationship diagrams, q.v.
entity/relationship modeling
The process of using the conventions of the entity/relationship model, q.v., as
a tool for assisting in the logical database design process.
equality
Two values are equal if and only if they're the very same value. For example, the
integer 3 is equal to the integer 3 and not to the integer 4, nor to any other integer
(nor to anything else, either). More precisely, let T
be a type; then the equality operator "=" for values of type
T is defined as follows. Let v1 and
v2 be two such values, and let
Op be an operator with a parameter x
of type T. Then v1
and v2 are equal (i.e., v1
= v2 evaluates to TRUE) if and only if, for all such operators
Op, two successful invocations of Op
that are identical in all respects except that the argument corresponding to x is v1 in one invocation
and v2 in the other are indistinguishable in their
effect. Note: The equality operator isin fact,
must bedefined for every type. See duplicate;
overloading; set; set membership; relation equality; tuple equality.
equijoin
A theta join in which theta is "=".
EQUIV
See equivalence.
equivalence
1. (Of sets of FDs) Two sets of FDs are equivalent
if and only if each is a cover for the other. Note:
Any given set of FDs always has an equivalent set that's irreducible (see
irreducible). 2. (Logic) If p and q are predicates,
the equivalence (p) EQUIV (q)
is a predicate also. Let (pi) EQUIV (qi)
be an invocation of that predicate (where pi and
qi are invocations of p
and q, respectively). Then that invocation (pi) EQUIV (qi) evaluates
to TRUE if and only if pi and
qi both evaluate to TRUE or both evaluate to FALSE. (In other words,
(p) EQUIV (q)is
equivalent to ((p) IMPLIES (q))
AND ((q) IMPLIES (p)).)
Note: The parentheses enclosing p and
q in the expression (p) EQUIV (q)
might not be needed in practice.
essentiality
A data structure is essential to a given data model (in the sense of the first definition
of that term) if its removal would make some information impossible to represent
using that model.
-
Example: The relational model includes only one
data structure, the relation itself; that data structure is clearly essential because
if it were removed, the relational model would be incapable of representing anything
at all. However, because the relational model is, in fact, capable of representing
absolutely any data whatsoever, any data model that supports relations in some shape
or form as well as some additional data structure DS
must be such that either relations are inessential or DS
is. But if relations are inessential, then DS must
be logically equivalent to relations!in which case, it could be argued that it's
really DS that's inessential anyway, not relations.
What's more, a data model that doesn't "support relations in some shape or form"
is unlikely in the extreme (even SQL could be said to support relations if various
SQL featuresnulls, duplicate rows, etc.are avoided). Thus, for example, pointers
(object IDs), bags, lists, and arrays could all be removed from the so-called object
model without any loss of representational power. (Indeed, the fact that they're
not removed is prima facie evidence that "the object model" fails to distinguish
properly between model and implementation issues.)
EXCEPT
Same as MINUS.
exclusive OR
If p and q are
predicates, their exclusive OR (p) XOR (q)
is a predicate also. Let (pi) XOR (qi)
be an invocation of that predicate (where pi and
qi are invocations of p
and q, respectively). Then that invocation (pi) XOR (qi) evaluates
to TRUE if and only if exactly one of pi and qi evaluates to TRUE. (In other words, (p)
XOR (q) is equivalent to NOT((p)
EQUIV (q)).) Note: The parentheses enclosing p and q in the expression
(p) XOR (q) might
not be needed in practice.
existential quantifier
Let p(x) be a predicate with a parameter
x; then EXISTS x (p(x)) is a predicate,
and it means "There exists at least one argument value v
that can replace the parameter x such that p(v) is true." In this example, EXISTS
x is an existential quantifier, and x
is an existentially quantified bound variable (q.v.). Note:
Some writers refer to EXISTS by itself as the quantifier; the literature is not
consistent on this point. More important, note that if v1,
v2,…, vn are all of the possible
argument values in the foregoing example, then EXISTS x (p(x))
is equivalent to (p(v1)) OR
(p(v2)) OR…OR (p(vn)) OR FALSE.
Observe in particular that this expression evaluates to FALSE if
n = 0 (i.e., if the bound variable x
ranges over an empty set).
Examples: See bound variable; domain calculus;
free variable;tuple calculus; and elsewhere.
EXISTS
See existential quantifier. In
the literature, EXISTS is often represented by a backward E, thus:
.
expanded cartesian product
See cartesian product.
expressible relation
Any relation that, given a particular set of relations, is either included in that
set or can be derived from those that are (see
derived relation).
expression
In a programming language, a construct that denotes a value; i.e., a rule for computing
or determining the value in question. Every expression is of some type: namely,
the type of the value it denotes. Contrast statement.
Example: X+Y is an expression; it denotes the value
that's the sum of the current values of the variables X
and Y. By contrast,
Z := X + Y ;
is a statement; it assigns the value denoted by the expression X+Y on the right-hand
side to the variable Z referenced on the left-hand side.
expression transformation
The process of transforming one expression into another, semantically equivalent
expression; applies to relational expressions in particular, where it's sometimes
called query rewrite. Query rewrite is typically
done for performance reasons; it can be done either by the user or, much more importantly,
by the system (see optimizer).
Example: The relational expression (r
WHERE br) JOIN (s
WHERE bs) is semantically equivalent to the relational
expression (r JOIN s)
WHERE (br) AND (bs);
therefore, either expression can be transformed into the other. Transforming the
second into the first is likely to be advantageous from a performance standpoint,
because the first means doing the restrictions before the join; thus, it's likely
that the input relations to the join will be smaller and the output will be smaller
too. In fact, this transformation could make the difference between keeping the
JOIN result in memory and having to spill it out onto the disk.
EXTEND
See extension.
extended cartesian product
See cartesian product.
Extensible Markup Language
See XML.
extension
1. (Relational algebra) Let
r be a relation. Then the extension EXTEND r
ADD (exp AS X)
is a relation with (a) heading the heading of r
extended with attribute X, and (b) body consisting
of all tuples t such that
t is a tuple of r extended with a value
for attribute X that is computed by evaluating
the expression exp on that tuple of
r. Relation r must not have an attribute
called X, and exp
must not refer to X. See
also tuple extension. 2. (Predicate)
Let p be a predicate; then the extension of p consists of all instantiations of
p (i.e., all propositions that can be obtained from
p) that evaluate to TRUE. 3. (Relation)
Following on from the previous definition, let r be a relation. Then the heading
of r can be regarded as representing a predicate (see
relation predicate), and the body of r can be regarded as representing
the extension of that predicate. Hence, the term
extension is also sometimes used to refer to the body of a relation.
Contrast intension.
Example (first definition only): The following
expression denotes an extension of the relation that's the current value of relvar
P:
EXTEND P ADD ( WEIGHT * 454 AS GMWT )
That extension is a relation just like the current value of relvar P, except that
it has an additional attribute GMWT ("gram weight"), whose value in any given tuple
is 454 times the WEIGHT value in that same tuple. Note that relvar P per se remains
unaltered in the databaseEXTEND isn't like ALTER TABLE in SQL; it's simply a read-only
operator that (like restrict, for example) takes a certain relation as input and
returns another as output.
external predicate
The relvar predicate for a given relvar. Contrast
internal predicate. Note: Since
this latter term is deprecated, the term external predicate
is deprecated (somewhat) as well.
FALSE
See boolean value.
FD
Functional dependency.
FD implied by a superkey
The FD A
B is implied by a superkey if and only if A is a superkey for the pertinent relvar.
FD preservation
Decomposing a relvar R into its projections R1, R2,…, Rn in such a way that every FD in
r is implied by those in
R1, R2,…, Rn. Note: R1, R2,…, Rn here are said to be independent
projections.
Example: Suppose relvar S
satisfies the additional FD {CITY}
{STATUS}; i.e., the status for a given supplier is a function of that supplier's
location. Then replacing S by its projections on
{S#,SNAME,CITY} and {CITY,STATUS} preserves FDs, because every FD satisfied by S is either satisfied by one of the two projections
or is implied by those that are. By contrast, suppose S
is replaced by its projections on {S#,SNAME,CITY} and {S#,STATUS} instead. Now the
FD {CITY}
{STATUS} isn't implied by the FDs satisfied by those projections (even though the
decomposition is nonloss). One practical consequence is that updates to either of
the two projections must now be monitored (either by the DBMS or, more likely in
practice, by some application) to ensure that the FD {CITY}
{STATUS} is satisfied; for example, consider what's involved in moving supplier
S1 from London to Paris. In other words, the two projections aren't independent
in the latter decomposition. Given the level of technology found in today's commercial
products, therefore, it's generally preferable to perform decomposition in such
a way as to preserve FDsi.e., to decompose into independent projectionswhenever
possible.
fifth normal form
Relvar R is in fifth normal form, 5NF, if and only
if every nontrivial JD satisfied by R is implied
by the superkeys of r. Every 5NF relvar is in 4NF.
Note: 5NF is "the" normal form with respect to
JDs. Also, although being in 5NF clearly doesn't
preclude being in 6NF as well, the term 5NF is often used loosely to refer to a
relvar that's in 5NF and not in 6NF.
Example: As noted under Boyce/Codd normal form,
it's often more instructive with the normal forms to show a counterexample rather
than an example per se. Consider, therefore, relvar SPJ, with attributes S# (supplier
number), P# (part number), and J# (project number), and predicate "Supplier S# supplies
part P# to project J#." Let that relvar be all key (i.e., subject to the key constraint
KEY{S#,P#,J#}). Let it also be subject to the constraint that if (a) supplier Sx supplies part Py,
and (b) part Py is supplied to project
Jz, and (c) project Jz is supplied by
supplier Sx, then (d) supplier
Sx supplies part Py to project
Jz. Then SPJ is equal to the join of its projections on {S#,P#},
{P#,J#}, and {J#,S#}i.e., it satisfies the JD *{{S#,P#}, {P#,J#},{J#,S#}}and so
it can be nonloss decomposed into those three projections. Because that JD is neither
trivial nor implied by the sole superkey (viz., the entire heading), relvar SPJ
isn't in 5NF, though it is in 4NF.
first normal form
Normalized. By definition, relvars are always in first normal form, 1NF (see
relation variable). It follows that a "table" in a language such
as SQL is in 1NF if and only if it's a direct and faithful
representation of some relvar, where direct and faithful means, among other things,
that every row-and-column intersection in that table contains exactly one value
of the applicable type, nothing more and nothing less. (The value in question can
be arbitrarily complexit can even be a tablebut, to repeat, there must be exactly
one, and it must be of the applicable type.) In particular, therefore, a table isn't
in first normal form if it includes any repeating groups, q.v. This fact accounts
for the usual informal characterization of first normal form as meaning simply no repeating groups. Note: Although being in
1NF clearly doesn't preclude being in 2NF as well, the term 1NF is
often used loosely to refer to a relvar that's in 1NF only and not in any higher
normal form.
first order logic
A form of predicate logic in which the sets over which variables range are not allowed
to contain predicates. Contrast second order
logic. Note: Propositional logic,
q.v., might be regarded as a "zeroth order" logic, because it has no variables (and
its variables thus certainly don't range over anything at all).
flat relation
The idea that "relations are flat" is a popular misconception.
See table.
FORALL
See universal quantifier. In the
literature, FORALL is often represented by an upside-down A, thus:
.
foreign key
Let R1 and R2
be relvars, not necessarily distinct, and let K
be a key for R1. Let FK
be a subset of the heading of R2 such that there
exists a possibly empty sequence of attribute renamings that maps
K into K' (say), where
K' and FK contain exactly the same
attributes. Then FK is a foreign key if and only
if, at all times, every tuple in R2 is constrained
to have an FK value that's the
K' value for some (necessarily unique) tuple in R1
at the time in question. R1 and
R2 here are the referenced relvar and the referencing relvar, respectively,
and the constraint between them is a referential constraint.
Examples: In relvar SP, {S#} and {P#} are foreign
keys corresponding to the keys {S#} and {P#} in relvars S
and P, respectively. Note that the key in the referenced relvar that corresponds
to a given foreign key is not required to be a primary key specifically.
foreign key constraint
A referential constraint.
foreign key rule
A rule to the effect that certain updates should trigger certain compensating actions,
such as cascading a delete operation, with the aim of avoiding some referential
integrity violation that might otherwise occur.
formal system
A logical system.
formula
Same as well-formed formula, q.v.
fourth normal form
Relvar R is in fourth normal form, 4NF, if and
only if every nontrivial MVD satisfied by R is
implied by some superkey of r. Every 4NF relvar
is in BCNF. Note: 4NF is "the" normal form with
respect to MVDs. Also, although being in 4NF clearly doesn't preclude being in the
next higher normal form (5NF) as well, the term 4NF
is often used loosely to refer to a relvar that's in 4NF and not in 5NF. In any
case, fourth normal form as such is no longer very important (BCNF, 5NF, and 6NF
being the normal forms of most practical significance); we mention it here mainly
for historical reasons.
Example: As noted under Boyce/Codd normal form,
it's often more instructive with the normal forms to show a counterexample rather
than an example per se. Consider, therefore, relvar CTX, with attributes C (course),
T (teacher), and X (text), and predicate "Course
C can be taught by teacher T and uses text X as
a textbook." Let that relvar be all key (i.e., subject to the key constraint KEY{C,T,X}).
Let it also be such that for a given course, the set of teachers and the set of
texts are quite independent of each other. Then CTX is equal to the join of its
projections on {C,T} and {C,X}i.e., it satisfies the MVDs {C}
{T} and {C}
{X}and so it can be nonloss decomposed into those two projections. Because those
MVDs are neither trivial nor implied by the sole superkey (viz., the entire heading),
relvar CTX isn't in 4NF, though it is in BCNF.
free variable
In logic, a variable (more precisely, an occurrence within a predicate of a variable
reference) that isn't boundin other words, a parameter. (The term
variable is used here in the sense of logic, not in the programming language
sense.) Contrast bound variable.
Examples: Let the symbols
x and y denote integers. Then the following
expressions are both predicates, and x appears
as a free variable in each of them:
x < 7
EXISTS y ( y > 3 ) AND x < 7
The first predicate 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.S# = S.S# )
The text 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 sensebut that's
because we've indulged in a certain sleight of hand, as it were. Here's an extended
version of the same example that should help to clarify matters:
SX RANGES OVER { S } ;
SPX RANGES OVER { SP } ;
SX WHERE EXISTS SPX ( SPX.S# = SX.S# )
Here, SX and SPX have been explicitly declared as 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. Note: Let
VR be a variable reference that occurs prior to the WHERE clause in some
tuple calculus expression. If VR also occurs in
the predicate in that WHERE clause (which it often but not invariably will), then
it must be free, not bound, in that boolean expression.
full FD
Old-fashioned and somewhat deprecated term for a left-irreducible FD.
fully dependent
Old-fashioned and somewhat deprecated term for irreducibly dependent.
fully normalized
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).
function
1. (Mathematics) Given two sets (not necessarily
distinct), a rulealso known as a mappingpairing each element of the first set (the
domain) with exactly one element of the second set (the codomain); equivalently,
that pairing itself. 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 (often a proper subset) of the codomain, and the function can be regarded
as a directed relationshipin fact, a many-to-one correspondence, in the strict sense
of that termfrom the domain to the range. 2. (Programming
languages) A read-only operator (sometimes more specifically one denoted
by an identifier such as SUM 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 only 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 (and similarly
for the codomain).
Example: Let f
be the rule that maps nonnegative integers x to
their squares x2. Then we can say that
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.
functional dependency
Let A and B be
subsets of the heading of relvar r. Then relvar
R satisfies the functional dependency (FD) A
B if and only if, in every relation that's a legal
value for r, whenever two tuples have the same
value for A, they also have the same value for
B (A here is called
the determinant and B is called the dependent).
Note: Functional dependency is also known as functional
dependence. The FD A
B is read as "B is functionally dependent on A,"
or "A functionally determines B," or, more simply, just "A arrow B." Note too that
A and B are, specifically,
sets of attributes. Informally, however, it's common, though strictly incorrect,
to speak of the attributes in B as if those attributes
per se (instead of the set B that contains those
attributes) were functionally dependent on A; likewise, it's common, though strictly
incorrect, to speak of the attributes in A as if
B were functionally dependent on those attributes
per se (instead of on the set A that contains those
attributes).
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 satisfies the FD {S#}
{CITY}. Note in particular in this example that the determinant isn't a key of the
relvar concerned. (By definition, every relvar R
always satisfies all possible FDs of the form K
X, where K is
a keyor, more generally, a super-keyfor 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, in a sense, the interesting
ones.)
functionally dependent
See functional dependency.
functionally determines
See functional dependency.
generated type
See type generator.
Golden Rule, The
The rule 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. (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.)
greater-than join
A theta join in which theta is ">".
GROUP
See grouping.
grouping
Let r be a relation and let the heading of r be partitioned into subsets {X}
and {Y}. Let the
attributes of {Y}
be Y1, Y2,…, Yn; also, let {X}
not contain any attribute called YR. Then the grouping
r GROUP ({Y}AS
YR) is another relation s.
The heading of s consists of {X}
extended with an attribute YR of type RELATION
{Y}. The body of s
is defined as follows: first, let z be the result
of r WRAP ({Y}AS
YT). Second, for each distinct
X value x in z,
(a) let yr be the relation whose tuples are all
and only those YT values from tuples in
z in which the X value is
x; (b) let t be a tuple with
X value x and YR
value yr (and no other attributes); then, and only
then, t is a tuple of s.
Note: Given a relation r and some grouping
of r, there's always an inverse ungrouping that
will yield r again; however, the converse is not
necessarily true. See ungrouping.
Example: The following expression denotes a grouping
of the relation that's the current value of relvar SP:
SP GROUP ( { P#, QTY } AS PQ_REL )
That grouping is a relation spq of type RELATION
{S# S#, PQ_REL RELATION {P# P#, QTY QTY}}. Relation spq
contains one tuple for each distinct S# value currently appearing in relvar SP,
and no other tuples. Given the sample values in
Figure 1, for example, the spq tuple for
supplier S2 has S# value S2 and a PQ_REL value that is a relation whose body contains
just the tuples <P1,300> and <P2,400>.
hash
An implementation construct.
heading
A set of attributes, in which (by definition) each attribute is of the form <A,T>, where A
is an attribute name and T is the type name for
attribute A. 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). Every subset
of a heading is itself a heading. Note: Given that
it's common to refer informally to an attribute by its attribute name alone, it's
also common to regard a given heading informally as a set of attribute names alone.
Examples: The heading of relvar S is
{ <S#,S#>, <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 as:
{ S#, SNAME, STATUS, CITY }
{ CITY, SNAME }
In Tutorial D they would be represented as follows:
{ S# S#, SNAME NAME, STATUS INTEGER, CITY CHAR }
{ CITY CHAR, SNAME NAME }
Heath's theorem
Let A, B, and C
be subsets of the heading of relvar r, such that
the set theory union of A, B, and
C is equal to that heading. Let AB denote
the set theory union of A and
B, and similarly for AC. If
R satisfies the FD A
B, then R is equal
to the join of its projections on AB and
AC.
Example: Relvar S satisfies the FD {S#}
{SNAME,CITY}, so it's equal to the join of (and can be nonloss decomposed into)
its projections on {S#,SNAME,CITY} and {S#,STATUS}.
host language
A programming language that relies on some data sublanguage (q.v.) for its database
support. Contrast database programming language.
idempotent
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.
Examples: In logic, AND and OR are both idempotent,
because
x AND x = x and x OR x = x
for all x. It follows as a direct consequence that
JOIN and UNION, respectively, are idempotent in relational algebra.
identity
1. (General) That which distinguishes a given entity
from all others. 2. (Operator) Equality. 3. (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 might not be needed in practice. 4. (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 iOpv and vOpi
are both equal to v for all possible argument values
v, then i is the
identity, or identity value, with respect to Op.
Examples (fourth definition only): The dyadic operators
"+", "*", AND, OR, and JOIN have identity values 0, 1, 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 numbers is zero (see aggregate operator),
so the join of no relations is TABLE_DEE (see
natural join).
identity projection
The projection of a given relation r over all of
its attributes (i.e., r{H}, where {H}
is the heading of r). Such a projection is guaranteed
to be equal to r.
Example: The expression SP{S#,QTY,P#} is an identity
projection.
identity restriction
A restriction of a given relation r that's equal
to r (i.e., is equal to r
WHERE TRUE); in particular, a restriction of the form r
WHERE t, where t
is a tautology (q.v.).
Examples: The expressions S WHERE STATUS
25 and S WHERE STATUS = STATUS are both 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.
IFF
Same as EQUIV.
image
See function.
immediate checking
Checking an integrity constraint whenever an update is performed that might cause
it to be violated. All constraint checking is immediate in the relational model.
Contrast deferred checking.
immediate constraint
A constraint for which the checking is immediate (see
immediate checking).
implementation
A physical realization on a real machine of the abstract machine that constitutes
some given data model (in the sense of the first definition of that term). In the
interest of physical data independence, the model and its implementation should
be kept rigidly apart; that is, the model should have nothing to say about any aspect
of implementation.
implication
If p and q are
predicates, the implication (p) IMPLIES (q)
is a predicate also. Let (pi) IMPLIES (qi)
be an invocation of that predicate (where pi and
qi are invocations of p
and q, respectively). Then that invocation (pi)
IMPLIES (qi) evaluates to TRUE if and only if pi evaluates to FALSE or qi
evaluates to TRUE or both. (In other words, (p)
IMPLIES (q) is equivalent to (NOT(p))
OR (q).) Note:
The parentheses enclosing p and
q in the expression (p) IMPLIES (q)
might not be needed in practice.
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 inference
rules, q.v.
implied by superkey(s)
See FD implied by a superkey; JD implied by
super-keys; MVD implied by a superkey.
IMPLIES
See implication.
inclusion
See set inclusion.
inclusion dependency
A constraint to the effect that a given projection of a given relvar
R2 is required to be equal at all times to some subset of a given projection
of a given relvar R1 at the time in question (R1 and R2 are not
necessarily distinct). Foreign key constraints are a special case.
IND
An inclusion dependency.
independent projection
See FD preservation.
index
An implementation construct.
inference rule
A rule for deriving a conclusiona theoremfrom a set of premises (i.e., other theorems,
possibly axioms).
information equivalent
Let s1 and s2
be sets of relations. Then s1 and
s2 are information equivalent if and only if every relation in
s1 is either identical to some relation in s2
or can be derived from the relations in s2 (see derived relation), and every
relation in s2 is either identical to some relation
in s1 or can be derived from the relations in s1.
Information Principle, The
The principle that the only kind of variable allowed in a relational database is
the relation variable specifically. (Equivalently, a relational database contains
relvars, and nothing but relvars.) 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 one and only one waynamely, as relations.
inheritance
Type inheritance.
injection
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 itself.
inner join
Join. The qualification inner is used to distinguish
the join in question from its outer counterpart. (Outer join in turn has to do with
nulls and three-valued logic and is therefore deliberately not discussed further
in this dictionary.)
INSERT
Loosely, an operator that inserts a given set of tuples into a given relvar. It's
shorthand for a certain relational assignment.
Example: The INSERT statement
INSERT SP
RELATION {
TUPLE { S# S#('S3'), P# P#('P1'), QTY QTY(150) },
TUPLE { S# S#('S5'), P# P#('P1'), QTY QTY(500) } } ;
is shorthand for the following relational assignment:
SP := ( SP ) UNION
( RELATION {
TUPLE { S# S#('S3'), P# P#('P1'),
QTY QTY(150) },
TUPLE { S# S#('S5'), P# P#('P1'),
QTY QTY(500) } } ) ;
In this example, the expressions S#('S3') and S#('S5') are selector invocations
for type S#; the expression P#('P1') is a selector invocation for type P#; and the
expressions QTY(150) and QTY(500) are selector invocations for type QTY. Likewise,
the two expressions of the form TUPLE {…} are selector invocations for tuple
type TUPLE {S# S#, P# P#, QTY QTY}, and the sole expression of the form RELATION
{…} is a selector invocation for relation type RELATION {S# S#, P# P#, QTY
QTY}. Note, incidentally, that with INSERT as defined here, it's not an error to
try to insert a tuple that already exists in the target relvar. Replacing UNION
in the expansion by D_UNION would solve this problem (if it is a problem).
instantiation
An invocation of a predicate. Note: Actually, the
logical notion of instantiation is more general than the familiar programming language
notion of function invocation. Further details are beyond the scope of this dictionary.
integrity
A database is in a state of integrity if and only if it violates no defined integrity
constraints (i.e., if and only if it's consistent). Integrity is necessary but not
sufficient for correctness. The relational model requires databases to be in a state
of integrity at all times, where "at all times" really means at statement boundaries
(except as noted under type constraint).
integrity constraint
A named boolean expression that must be satisfied (i.e., is required to evaluate
to TRUE) at all times, where "at all times" really means at statement boundaries
(except as noted under type constraint). There are two basic kinds,
database constraints and type constraints (q.v.). The DBMS should reject any update
that, if accepted, would cause some integrity constraint to be violated (i.e., to
evaluate to FALSE). Note: Because database constraints
in particular affect updates, and updates apply by definition to variables specifically,
it follows that such constraints apply to variables specifically tooi.e., anything
thus constrained must be a variable, by definition.
intelligent key
A single-attribute key that, in addition to its main purpose of identifying some
entity, carries some kind of encoded information embedded within it.
Contrast surrogate key.
Example: Let parts purchased from domestic suppliers
be assigned part numbers in the range 04999, and parts purchased elsewhere be assigned
part numbers in the range 50009999. Now assume the 5001st 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 5000 will therefore fail. As
this example suggests, intelligent keys should be used with caution. (Actually,
a similar remark applies to the encoding of information within any attribute, not
just key attributes specifically, but key attributes seem to be particularly prone
to this kind of abuse.)
intended interpretation
The informal, user-understood meaning (i.e., the relvar predicate, q.v.) for a given
relvar. Also referred to as interpretation, unqualified.
intension
For a given relation or relvar, the intended interpretation, or sometimes the heading.
Contrast extension (third definition).
Interchangeability Principle, The
(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 as far
as users are concerned.
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 really propositions).
INTERSECT
See intersection.
intersection
1. (Dyadic case) The intersection of two relations
r1 and r2, r1
INTERSECT r2, where r1
and r2 are of the same type
T, is a relation of type T with body
the set of all tuples t such that
t appears in both r1 and
r2. 2. (N-adic case) The intersection
of n relations r1, r2,…,
rn (n
0),
INTERSECT {r1,r2,…,rn}, where
r1, r2,…, rn are all of the same type T,
is a relation of type T, with body the set of all
tuples t such that t
appears in each of r1, r2,…, rn (unless n = 0, in which case (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: The relational intersection operator is a special case of join,
q.v.
Example: The expression (S{CITY}) INTERSECT (P{CITY})
denotes the intersection of the projections on CITY of the relations that are the
current values of relvars S and P. That intersection
is a relation of type RELATION {CITY CHAR}. Moreover, if the current values of relvars
S and P are s and p,
respectively, the body of that relation 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 semantically equivalent to the expression (S{CITY})
JOIN (P{CITY}).
intersection (set theory)
The set of all elements appearing in both of two given sets. (This definition can
obviously be extended to apply to any number of sets.)
irreducible
1. (Of a key) See candidate key.
2. (Of a relvar) Sixth normal form. 3. (Of
an FD) Left-irreducible. 4. (Of a set of FDs)
The set s of FDs is irreducible if and only if
(a) the dependent in every FD in s contains only
one attribute, (b) every FD in
s is left-irreducible, and (c) no FD
can be discarded from s without changing the closure
of s.
irreducibly dependent
(Of a dependent in an FD) Let
A and B be subsets of the heading of
some relvar r. Then B
is irreducibly dependent on A if and only if it's
functionally dependent on A and not on any proper
subset of A.
Example: In relvar SP, {QTY} is irreducibly dependent
on {S#,P#}. It's also dependent on {S#,P#,QTY}, but not irreducibly so.
irreducibly equivalent
(Of a set of FDs) Let s1
and s2 be sets of FDs. Then
s1 is an irreducible equivalent of s2
if it's equivalent to s2 and irreducible.
IS_EMPTY
A Tutorial D operator that returns TRUE or FALSE
according as a specified relation is empty or not.
isomorphism
Let s1 and s2
be sets (not necessarily distinct), and let f be
a bijective mapping from s1 to
s2. Let OpX be an operator that takes
elements of s1 as its operands and yields an element
of s1 as its result. Then
f is an isomorphism if and only if, for all such operators OpX, there
exists an analogous operator OpY that takes elements
of s2 as its operands and yields an element of
s2 as its result such that, whenever
OpX applied to x1, x2,…, xn yields
x, then OpY applied
to y1, y2,…, yn yields
y, where y1, y2,…, yn, and
y are the images of x1, x2,…, xn,
and x, respectively, under
f. In other words, a bijective mapping is an isomorphism if and only
if it preserves the algebraic structure of the domain s1
in the codomain s2. Note:
If the bijective mapping f is an isomorphism, then
its inverse is an isomorphism as well.
Example: Let s1
be the set {EVEN,ODD} and let operators "+" and "*" be defined as follows:
Table 1-2.
|
+
|
EVEN
|
ODD
|
*
|
EVEN
|
ODD
|
|
EVEN
|
EVEN
|
ODD
|
EVEN
|
EVEN
|
EVEN
|
|
ODD
|
ODD
|
EVEN
|
ODD
|
EVEN
|
ODD
|
Now let s2 be the set {TRUE,FALSE} and let f be a bijection from s1
to s2 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 s1 (with its operators "+" and "*") to s2 (with its operators EQUIV and OR).
JD
Join dependency.
JD implied by superkeys
The JD *{A1,A2,…,An} is implied by super-keys
if and only if each of A1, A2,…, An is a
superkey for the pertinent relvar R.
JOIN
See natural join.
join
Natural join (unless the context demands otherwise).
join dependency
A generalization of the concept of multivalued dependency (every MVD is a JD, but
some JDs aren't MVDs). Let A1, A2,…, An be
subsets of the heading of relvar r. Then
r satisfies the join dependency (JD) *{A1,A2,…,An}
if and only if every relation that's a legal value for R
is equal to the join of its projections on A1, A2,…,
An. Note: The JD *{A1,A2,…,An}
is read as "star A1, A2,…, An."
Example: Relvar S satisfies the JD
* { { S#, SNAME }, { S#, STATUS }, { S#, CITY } }
because every relation that's a legal value for S
is equal to the join of its projections on {S#,SNAME}, {S#,STATUS}, and {S#,CITY};
i.e., relvar S could be nonloss decomposed into
those three projections. (Of course, there's no requirement that this decomposition
actually be performedwhether it should or not depends on whether there's any advantage
to be gained by doing so.)
key
A candidate key (unless the context demands otherwise).
key constraint
A constraint to the effect that a given subset of the heading of a given relvar
is a candidate key for that relvar.
left-irreducible FD
Given a set s of FDs, the FD
f in s is left-irreducible (with respect
to s) if and only if no attribute can be discarded from the determinant of f without changing the closure of
s.
Examples: Let s
be the set of all FDs satisfied by relvar SP. Then the FDs {S#,P#}
{QTY} and {S#,P#,QTY}
{QTY} both appear in s. Of these two FDs, the first
is left-irreducible but the second isn't.
less-than join
A theta join in which theta is "<".
literal
1. (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, must be denotable by means of some literal.
Note: A literal is a special case of a selector invocation (see
selector). 2. (Logic) A simple
proposition or its negation; a simple predicate or its negation (see
simple predicate; simple proposition).
Examples (first definition only): 4 (a literal
of type INTEGER); 'ABC'(a literal of type CHAR); FALSE (a literal of type BOOLEAN);
S#('S1') (a literal of type S#); TUPLE {S# S#('S1'), P# P#('P1'), QTY QTY(300)}
(a literal of type TUPLE {S# S#, P# P#, QTY QTY}); RELATION {TUPLE {S# S#('S1'),
P# P#('P1'), QTY QTY(300)}} (a literal of type RELATION {S# S#, P# P#, QTY QTY});
and so on.
logic
The scientific study of the methods and principles used in valid reasoning.
logic variable
A variable that can appear either bound or free in predicate calculus expressions.
See also range variable.
logical data independence
See data independence.
logical database design
The process (or the result of the process) of deciding, given some body of data
to be represented in some database, what relvars that database should contain, what
attributes they should have, and what constraints they should be subject to. Ideally,
the goal is to produce a design that's independent of all considerations having
to do with either physical implementation or specific applicationsthe latter objective
being desirable for the 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 design
process can be summarized as one of (a) pinning down the relvar predicates (or "business
rules") as carefully as possible, albeit necessarily somewhat informally, and then
(b) mapping those relvar predicates to specific relvars and formal constraints.
logical expression
A boolean expression.
logical implication
Implication.
logical operator
An operator that (a) takes either values or variables (or both) of type BOOLEAN
as operands, and (b) either returns a value, or updates at least one variable, of
type BOOLEAN. The connectives are a special case.
logical system
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 logical system consists of (a) a set of symbols (e.g., NOT, AND, punctuation symbols,
variable names); (b) a set of grammatical rules for forming sentences within the
system; (c) a set of given sentences (the axioms); and (d) a set of rules for inferring
"new" sentences from "old" ones (the rules of inference).
Examples: Propositional logic and predicate logic
are both logical systems.
lossless decomposition
Nonloss decomposition.
lossy decomposition
A decomposition that isn't nonloss.
Example: The decomposition of relvar
S into its projections on {S#,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.
many-to-many correspondence
Strictly, a rule pairing two sets s1 and
s2 (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 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. Then that pairing is a many-to-many
correspondence from s to itself.
many-to-one correspondence
Strictly, a rule pairing two sets s1 and
s2 (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 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 |x|is
a many-to-one correspondence from s1 to
s2.
mapping
A function.
mark
See null.
MATCHING
See semijoin.
material implication
Implication.
materialization
A somewhat unsophisticated technique for implementing operations on views according
to which (a) the relational expression that defines the view is evaluated at the
time the operation is invoked, (b) the view is thereby materialized, and (c) the
operation in question is then executed against the relation so materialized. Note
that this technique can't be used for implementing view updates but is limited to
read-only operations. Contrast materialized
view; substitution (first definition).
materialized view
Deprecated term for a snapshot. Note the difference between (a) materialization
as a technique for implementing operations on views 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 operation on a given view is implemented by materialization).
By contrast, the latter is an issue that concerns the user very much; 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. 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 model is concerned). Worse yet, the unqualified
term view is often taken to mean a materialized
view specifically, and thus we're 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.
meaning
(Of a relvar) See relvar constraint
(second definition); relvar predicate.
member
An element of a bag or set.
merge
A join implementation technique.
metadata
Data about data. See catalog.
minimality
(Of a key or of a set of FDs) Old-fashioned and
somewhat deprecated term for irreducibility.
MINUS
See difference.
missing information
A term often used to refer to information that's either currently unknown or inapplicable.
Note: To say that information that's currently
unknown is missing is possibly reasonable. However, to say that information that's
inapplicable is missing isn't reasonable at all (and the usage is therefore deprecated).
For example, if a given employee is unmarried, spouse information for that employee
isn't missing; rather, it simply doesn't exist.
model
Either a data model in general (usually in the sense of the first definition 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 in the literaturein fact, more meanings
than it can reasonably be expected to bear. Such additional meanings are deliberately
omitted here.
monadic
(Of an operator) Having exactly one operand; i.e.,
being defined in terms of exactly one parameter.
multi-relvar constraint
Informally, an integrity constraint that mentions two or more distinct relvars.
Contrast single-relvar constraint.
Note: The difference between single-and multi-relvar
constraints is more a matter of pragma than logic, thanks to
The Principle of Interchangeability.
Examples: The foreign key constraints from relvar
SP to relvars S and P; also constraint C3 from
the examples under database constraint.
multidependent
See multivalued dependency.
multidetermines
See multivalued dependency.
multiple assignment
An operation that allows several individual assignments all to be performed "simultaneously,"
without any integrity checking being done until all of the individual assignments
have been executed in their entirety.
Example: The following "double DELETE" is, logically,
a multiple assignment operation:
DELETE S WHERE S# = S#('S1') ,
DELETE SP WHERE S# = S#('S1') ;
Note the comma separator after the first DELETE, which indicates syntactically that
the end of the overall statement has not yet been reached.
multiset
A bag.
multivalued dependency
A generalization of the concept of functional dependency (every FD is an MVD, but
some MVDs aren't FDs). Let A, B, and
C be subsets of the heading of relvar R
such that the set theory union of A, B, and C is equal to that heading. Let
AB denote the set theory union of A
and B, and similarly for
AC. Then R satisfies the multivalued
dependencies (MVDs) A
B and A
C if and only if R
satisfies the JD *{AB,AC}.
Note: Multivalued dependency is also known as multivalued dependence.
The MVD A
B is read as "B
is multidependent on A," or "A
multidetermines B," or, more simply, "A
double arrow B." Note that
A and B here are, specifically, sets
of attributes. Informally, however, it's common, though strictly incorrect, to speak
of the attributes in B as if those attributes per
se (instead of the set B that contains those attributes)
were multidependent on A; likewise, it's common,
though strictly incorrect, to speak of the attributes in A
as if B were multidependent on those attributes
per se (instead of on the set A that contains those
attributes). Observe that if relvar r satisfies
the MVDs A
B and A
C, then if it contains the tuples <a,b1,c1>
and <a,b2,c2>, it also contains the tuples
<a,b1,c2> and <a,b2,c1>.
Observe further that it's apparent from the definition that relvar
R can be nonloss decomposed into its projections on
AB and AC if and only if it satisfies
the MVDs A
B and A
C (this theorem, a stronger form of Heath's theorem,
is one of many due to Fagin).
mutator
Term sometimes used (especially in OO contexts) for an update operator.
MVD
Multivalued dependency.
MVD implied by a superkey
The MVD A
B is implied by a superkey if and only if A is a superkey for the pertinent relvar.
n-adic
(Of an operator) Having exactly
n operands; i.e., being defined in terms of exactly
n parameters (n
0).
n-ary
Of degree n (n
0).
n-place
(Of a predicate) n-adic
(n
0).
n-tuple
A tuple of degree n (n
0).
NAND
In logic, a dyadic connective (also known as the Sheffer stroke
and usually written as a vertical bar, "|"); if p
and q are predicates, then (p)|(q) is a predicate also. Let (pi)|(qi)bean invocation of that predicate (where
pi and qi are invocations of
p and q, respectively).
Then that invocation (pi)|(qi)
evaluates to FALSE if and only if pi and
qi 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 expression (p)|(q)
might not be needed in practice.
natural join
1. (Dyadic case) Let relations
r1 and r2 be such that attributes with
the same name are of the same type. Then the natural join of
r1 and r2, r1
JOIN r2, is a relation with heading the set theory
union of the headings of r1 and
r2 and with 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 such that attributes with the same name are of the same type. Then the natural
join JOIN {r1,r2,…,rn} is defined as follows:
if n = 0, the result is TABLE_DEE; if
n = 1, the result is r1; otherwise,
choose any two relations from the set r1, r2,…, rn
and replace them by their (dyadic) natural join and repeat this process until the
set consists of only one relation r, which is the
overall result.
Example: The expression S
JOIN 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 {S# S#, SNAME NAME, STATUS INTEGER, CITY CHAR, P# P#, 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 <s#,n,st,c,p#,q>
such that the tuple <s#,n,st,c> appears in
S and the tuple <s#,p#,q>
appears in sp.
negation
If p is a predicate, its negation NOT(p)
is a predicate also. Let NOT(pi) be an invocation
of that predicate (where pi is an invocation of
p). Then that invocation NOT(pi)
evaluates to TRUE if and only if pi evaluates to
FALSE. Note: The parentheses enclosing
p in the expression NOT(p) might not
be needed in practice.
nested relation
See relation-valued attribute.
NF2
NF squared; short for NFNF ("non first normal form"). An NF2 relvar is, loosely,
a relvar with at least one relation-valued attribute. The term is deprecated, however,
because it's based on a flawed understanding of the concept of first normal form.
Also, the NF2 concept is usually taken to include certain extensions to the conventional
relational operators, extensions that aren't simply shorthand and thus aren't included
(or needed) in the relational model.
niladic
(Of an operator) Having no operands; i.e., being
defined in terms of no parameters. 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 arguments
(such as the system clock). Indeed, niladic operators with such hidden arguments
are the normal case.
Example: Many languages provide a built-in operator
for generating random (or "pseudorandom") numbers. Such operators effectively have
a hidden argumentviz., the random number returned on the previous invocation.
nonloss decomposition
Replacing a relvar R by 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). Note that one "nonloss decomposition" that's always available
for any given relvar R is to "replace"
R by the corresponding identity projection (q.v.).
Example: A nonloss decomposition that might be
applied to the suppliers-and-parts database would be to replace relvar
S by its projections on {S#,SNAME} and {S#,STATUS,CITY}. Relvar
S could then be obtained by joining those two projections back together
again.
nonscalar
Not scalar. The most important nonscalar constructs in the relational model are
tuples and (especially) relations themselves.
nontrivial
(Of an FD, JD, or MVD) Not trivial.
See trivial FD; trivial JD; trivial MVD.
NOR
In logic, a dyadic connective (also known as the Peirce arrow
and usually written as a down arrow, "
"); if p and
q are predicates, then (p)(q)
is a predicate also. Let (pi)(qi) be an
invocation of that predicate (where pi and qi are invocations of p
and q, respectively). Then that invocation (pi)(qi) evaluates to TRUE if and
only if pi and qi
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 expression (p)(q)
might not be needed in practice.
normal form
1. Canonical form. 2. See first normal form;
second normal form; etc. Note: The
most important relational normal forms are BCNF and 5NF (and 6NF); the others are
of mainly historical interest.
normalization
The process of using the principles of nonloss decomposition to replace some given
relvar by certain of its projections, such that the join of those projections is
guaranteed to be equal to the original relvar. Note, 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 objective
of normalization is to reduce redundancy (q.v.) and thereby to eliminate certain
update anomalies (q.v.) that might otherwise occur.
normalized relvar
A relvar. (Relvars are always normalized by definition, in the sense that they're
in at least first normal form. However, the term normalized
is frequently, though somewhat inaccurately, used to refer to some normal form higher
than firstespecially either BCNF or 5NF.)
NOT
See negation.
NOT MATCHING
See semidifference.
null
A construct, used in SQL in particular, for representing missing information (q.v.).
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, and a "relation" that "contains a null" isn't a relation. It follows further
that nulls have no place in the relational model, and this dictionary therefore
has very little to say regarding most null-related concepts.
nullary
Of degree zero. The term is probably best avoided because of the potential confusion
with null, q.v.
nullary foreign key
A foreign key of degree zero.
nullary heading
The heading of degree zero.
nullary key
A key of degree zero.
nullary projection
The projection of a given relation r over no attributes
(i.e., r{}). The result is TABLE_DUM if
r is empty and TABLE_DEE otherwise.
nullary relation
A relation of degree zero. There are exactly two such, TABLE_DEE and TABLE_DUM.
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.
object
A thing.
object ID
A pointer.
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 commercial DBMSs that claim to provide object/relational support
and those that don't 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 support
can hardly 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, dreamt up to conceal the fact that early
"relational" products weren't very relational at all. Hence the present definition,
to the effect that "object/relational" simply means relational.
observer
Term sometimes used (especially in OO contexts) for a read-only operator.
one-to-many correspondence
Strictly, a rule pairing two sets s1 and
s2 (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 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 square roots ±x is a one-to-many correspondence from
s1 to s2.
one-to-one correspondence
Strictly, a rule pairing two sets s1 and
s2 (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 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
is the pairing of elements x with their predecessors
x-1.
OO
Object-oriented or object orientation, as the context demands.
open WFF
A WFF that isn't closed; i.e., a WFF that denotes a predicate that isn't a proposition.
Open World Assumption, The
The assumptionusually rejected in favor of The Closed World Assumption, q.v.that
(a) if a given tuple appears in a given relvar at a given time, then the proposition
represented by that tuple is true at that time, and (b) if a given tuple could appear
in that relvar at that time but doesn't, then the proposition represented by that
tuple might or might not be true at that time.
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 to mean a read-only operator that's denoted
by some special symbol such as "+" instead of an identifier such as SUM, in which
case other read-only operators (i.e., those denoted by identifiers) are typically
referred to as functions.
optimizer
The part of the DBMS responsible for mapping user requests (i.e., queries and updates)
to the "best possible" executable code, where "best possible" basically means best performing.
OR
See disjunction.
ordering
The process, or the result of the process, of imposing a left-to-right sequence
on the attributesand, more especially, a top-to-bottom sequence on the tuplesof
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 orderings.
Operators that request such orderings are of major pragmatic importance, but they
aren't relational operators because their result isn't a relation.
Example: The SQL operators that provide this functionality
are SELECT (for left-to-right column sequence) and ORDER BY (for top-to-bottom row
sequence).
ordinal type
A type with the property that the operator ">" is defined for every pair of values
of the type in question. If v1 and
v2 are two such values and are distinct, then exactly one of the expressions
v1 > v2 and
v2 > v1 evaluates
to TRUE and the other to FALSE. Note that, since the "=" operator applies to values
of every type, and given also the availability of the NOT connective, it follows
that all of the usual comparison operators"=", "", ">", "", "<", and "
"are available for all pairs of values
of an ordinal type.
Examples: Type INTEGER is an ordinal type. By contrast,
suppose the system also supports a type POINT, perhaps user-defined, representing
geometric points in two-dimensional space. Then type POINT wouldn't be an ordinal
type, because the notion of one point being somehow greater than another makes no
sense.
orthogonal
Independent.
orthogonal decomposition
A decomposition of some given relvar into restrictions, such that the restrictions
in question satisfy The Principle of Orthogonal Design.
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 to both LP and HP.
Orthogonal Design Principle, The
Loosely, the principle that no two relvars in a given database should have overlapping
meanings. More precisely, let A and
B be distinct relvars. Replace A and
B by nonloss decompositions into projections A1, A2,…, Am and B1, B2,…,
Bn, respectively, such that every Ai (i = 1, 2,…,
m) and every Bj (j = 1, 2,…, n)
is in 6NF. Let some i and
j be such that there exists a sequence of zero or more attribute renamings
with the property that (a) when applied to Ai,
it produces Ak, and (b) Ak
and Bj are of the same type. Then there must not
exist a constraint to the effect that, at all times, Ak' =
Bj' (where Ak' and
Bj' are specified restrictions of Ak
and Bjsay Ak WHERE
a and Bj WHERE
b, respectivelysuch that neither
a nor b is a contradiction, q.v.).
overloading
Using the same name for two or more different operators. The operators in question
should preferably have similar semantics. Note:
Overloading is also referred to more specifically as overloading polymorphism; it's
also known as ad hoc polymorphism. In an inheritance context, the term is also sometimes
used to refer to what is much better called inclusion polymorphism; this particular
usage is deprecated, however, because it's based on a flawed perception of the nature
of subtypes and supertypes. Further details are beyond the scope of this dictionary.
Examples: UNION is overloaded, because it (i.e.,
the name) is used for both relational and tuple union. 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 {S# S#, P#
P#, QTY QTY}, and so on).
OWA
The Open World Assumption.
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. Every parameter is declared to
be of some type; any argument corresponding to a given parameter must be of the
same type as that parameter.
Peirce arrow
See NOR.
persistence
The property according to which data, once inserted into the database, remains there
("persists") until explicitly deleted.
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 structures 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.
PJ/NF
Projection-join normal form.
placeholder
A free variable or parameter.
pointer
An implementation construct. As is well known, pointers are excluded from the relational
model. In fact, mixing pointers and relationsthat is, allowing a "relation" to have
an "attribute" whose values are pointers to "tuples" in some other "relation" (a
state of affairs supported by several SQL products as well as by the SQL standard,
despite the fact that it violates, among other things, The
Information Principle)has been described as The Second Great Blunder.
(For the first, see type.) See also referencing.
polymorphism
Loosely, the idea that an operator might permit its arguments to be of different
types on different invocations. See overloading.
power set
The set of all subsets of a given set. If the given set has cardinality
n, the power set has cardinality 2n.
predicate
A truth-valued function. If and only if the corresponding set of parameters is empty,
the predicate is a proposition.
predicate calculus
A sound and complete formal system having to do with predicates and connectives
and the inferences that can be made using them. Note:
The principal difference between predicate calculus and propositional calculus,
q.v., is that predicates, unlike propositions, are allowed to contain variables
and quantifiers, which makes predicate calculus more powerful and more widely applicable.
predicate logic
Predicate calculus.
prenex normal form
A predicate is in prenex normal form if and only if all of the quantifiers appear
at the beginning.
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 = 'Red' AND
EXISTS SPX ( SPX.S# = SX.S# AND
SPX.P# = PX.P# ) )
The predicate in the WHERE clause here is not in prenex normal form. Here, however,
is a semantically equivalent formulation of the query in which the predicate is
in prenex normal form:
SX WHERE
EXISTS PX ( EXISTS SPX ( PX.COLOR = 'Red' AND
SPX.S# = SX.S# AND
SPX.P# = PX.P# ) )
primary key
A candidate key that has been singled out for special syntactic treatment for some
reason. While a given relvar can have any number of candidate keys, 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, outside the purview of the relational model. Note:
The relational model originally insisted that base relvars, at least, should always
have a primary key. It also insisted that foreign keys refer to primary keys specifically.
However, there were never any good logical reasons for these rules, and rules that
apply to base relvars but not to other kinds are more than a little suspect in any
case (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.
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 anymore. 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.
Example: For relational algebra, a primitive set
of operators will definitely include projection and almost certainly join, but not
semijoin (because semijoin can be defined in terms of projection and join).
Principle of Identity of Indiscernibles, The
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 identities are represented in the same way as everything elsenamely, by means
of attribute values (see Information Principle,
The)and numerous benefits accrue from this fact. Note too that there's
a logical difference between indiscernibility and interchangeabilitytwo objects
might be interchangeable and yet distinguishable (think of two pennies, for example).
Note finally that the term object here is not being
used in its object-oriented sense.
Principle of Interchangeability, The
See Interchangeability Principle, The.
Principle of Orthogonal Design, The
See Orthogonal Design Principle, The.
product
Cartesian product (unless the context demands otherwise).
projection
Let r be a relation and let {X}
be a subset of the heading of r. Then the projection
r{X} is a relation with heading {X}
and body consisting of all tuples x such that there
exists some tuple t in r
with X value x.
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,c>
(and no other tuples) such that there exists some supplier number s# and some name
n such that the tuple <s#,n,st,c>
appears in the current value of relvar S. Given
the sample values of Figure 1,
the result has cardinality four. Note: For reasons
of user friendliness, Tutorial D allows projections
to be expressed in terms of the attributes to be discarded instead of those to be
retained; thus, for example, the projection S{STATUS,CITY} can equivalently be expressed
as S{ALL BUT S#,SNAME}. A similar remark applies to several other relational (and
tuple) operations also.
projection-join normal form
Fifth normal form. The alternative (and original) name derives from the fact that
5NF is "the" normal form with respect to projection and join (as those operators
are classically understood).
proper inclusion
Set s2 is properly included in set
s1 if and only if it is a proper subset of s1.
proper subset
Set s2 is a proper subset of set
s1 if and only if it is a subset of s1
and s1 and s2
are distinct.
proper superkey
A superkey that does not have the irreducibility property; i.e., a proper superset
of a key.
proper superset
Set s1 is a proper superset of set
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 "properties
of interest" and attributes in base relvars. The suggestion is hard to sustain,
however, given that the term properties of interest
has no precise definition. (Of course, the same is true of the term
property itself, for that matter.)
proposition
A predicate with no parameters (i.e., no free variables); in other words, something
that evaluates unequivocally to either TRUE or FALSE. Given an arbitrary predicate,
substituting arguments for the parameters of that predicate yields a proposition.
Examples: 1. The sun is a star. 2. Neptune is a
star. 3. Supplier s1 is under contract, is named
Smith, has status 20, and is located in Paris. 4. There exists a city
c such that there exists a supplier number s#
such that the supplier with supplier number s#
is located in city c. Notice that there are two
variables, s# and c,
in this last example; however, the variables in question are bound, not free, and
the example overall still evaluates unequivocally to either TRUE or FALSE (it's
either the case or not the case that at least one supplier is located in at least
one city).
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 logic
Propositional calculus.
pseudovariable reference
The use of an operational expression instead of a simple variable reference to denote
a target for some update operation. Note: It's
convenient for definitional purposes to regard pseudovariable references as if they
were regular variable references (and we do so in this dictionary); in other words,
pseudovariables are variables, loosely speaking.
Examples: Let CS be a variable of type CHAR with
a current value of the string 'Middle', and consider the following assignment:
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 is a pseudovariable reference.
For a second example, let LSV be a view, defined as the restriction of relvar S to just suppliers in London, and consider the following
DELETE statement:
DELETE LSV WHERE STATUS > 15 ;
Logically speaking, this DELETE is equivalent to the following:
DELETE ( S WHERE CITY = 'London' ) WHERE STATUS > 15 ;
In this expanded form, the target of the DELETE is specified as an operational expression
(i.e., 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).
QBE
A relational language based on domain calculus. The name is an abbreviation for
Query-By-Example.
quantifier
See existential quantifier; universal quantifier.
(Others are possiblefor example, there exists exactly one of; for all but one of;
there exists an odd number of; and so onbut EXISTS and FORALL are easily the ones
encountered most frequently in practice.)
QUEL
A relational language based on tuple calculus that at one time was a serious competitor
to SQL.
query
A retrieval request (i.e., a relational expression). Sometimes used, loosely, to
refer to update requests also.
query rewrite
See expression transformation.
quota query
A query that imposes a desired limit, or quota, on the cardinality of the result
(though the actual result might have cardinality either less than or greater than
the specified quota).
Example: Here's a possible formulation of the quota
query "Get the three heaviest parts" (the quota here is three):
WITH ( P RENAME ( WEIGHT AS WT ) ) AS t1 ,
( EXTEND P ADD ( COUNT ( t1 WHERE WT > WEIGHT )
AS #_HEAVIER ) AS t2 ,
( t2 WHERE #_HEAVIER < 3 ) AS t3 :
t3 { P#, PNAME, WEIGHT, COLOR, CITY }
Using the RANK shorthand (q.v.), we can express this query a little more succinctly
as:
( ( RANK P BY ( DESC WEIGHT AS W ) ) WHERE W
3 )
{ P#, PNAME, WEIGHT, COLOR, CITY }
range
1. See function. 2.
See range variable.
range variable
Relational calculus analog of a logic variable; in other words, a variable that
"ranges over" some specified set of values (either the set of tuples in some relation
or the set of values of some type) and can appear either bound or free in relational
calculus expressions.
RANK
See ranking.
ranking
Let r be a relation with no attribute called X. Then the ranking RANK r
BY (item,…,item AS
X), where each "item" consists of either ASC (ascending) or DESC (descending)
followed by the name of an attribute of r (and
the overall sequence of items in the commalist specifies major-to-minor ordering
in the usual way), is a relation identical to r
except that (a) it has an additional attribute X,
and (b) the X value in any given tuple of that
result shows that tuple's ranking position with respect to the specified ordering.
Example: See
quota query.
read-only operator
A function; i.e., an operator that, when invoked, updates nothing (except possibly
variables local to the implementation of the operator in question) but returns a
value, of a type declared when the operator in question is defined. A read-only
operator invocation thus denotes a value; i.e., it's an expression, and it can appear
wherever a literal of the appropriate type is allowed. In particular, it can be
nested inside other expressions.
real relvar
A base relvar or a snapshot (contrast
virtual relvar).
recursive query
A relational expressionwhich by definition can be thought of as the invocation of
some relation-valued function fwhose evaluation
involves further invocations of that same function f.
Example: Here's a recursive definition of an operator
to compute the transitive closure, q.v., of a binary relation with attributes A
and B, both of type P# (the code isn't very efficient, but it can obviously be improved
in a variety of ways):
OPERATOR TRANCLO ( AB RELATION { A P#, B P# } )
RETURNS RELATION { A P#, B P# } ;
RETURN
( WITH ( AB UNION
( ( ( AB JOIN
( ( AB RENAME ( B AS C ) )
RENAME ( A AS B ) ) ) { A, C })
RENAME ( C AS B ) ) ) AS ttt :
IF ttt = AB THEN ttt ELSE TRANCLO ( ttt )
END IF ) ;
END OPERATOR ;
Now the invocation TRANCLO(r), where
r is a relation of the appropriate type, can be thought of as a recursive
query, because it implicitly involves further invocations of TRANCLO itself.
redundancy
A given database displays redundancy if and only if it includes two or more distinct
representations, either direct or indirect, of the same proposition.
See also controlled redundancy.
referenced relvar
See foreign key.
referencing
The relational meaning of this term is described under foreign key;
it should not be confused with the operator of the same name (found in systems that
support pointers but not in relational systems) that, given a variable
V, returns a pointer to V. Note: Systems
that support pointers typically support an operator called
dereferencing as well, which, given a pointer p,
returns the variable that p points to.
referencing relvar
See foreign key.
referential action
The action specification portion of a foreign key rule (e.g., "cascade," in a DELETE
rule).
referential constraint
See foreign key
referential integrity
Loosely, the rule that no database is allowed to contain any unmatched foreign key
values. More precisely, let FK be some foreign
key in some referencing relvar R2; let
K be the corresponding key in the corresponding referenced relvar
R1; and let K' be obtained from
K as explained in the entry for foreign key.
Then referential integrity requires that there never be a time at which an FK value exists in R2
that doesn't simultaneously exist as the K' value
for some (necessarily unique) tuple in R1.
reflexive
1. (Of a truth-valued operator) Let
Op be a dyadic truth-valued operator, and assume for definiteness that
Op is expressed in infix style. Then
Op is reflexive if and only if, for all x, x Op x
is true. 2. (Of a relation) Let
r be a binary relation. Then r is reflexive
if and only if, for all x, the tuple <x,x>
appears in r. 3. (Of FDs)
See Armstrong's inference rules.
Examples (first definition only): The logical operator
EQUIV; the "less than or equals" operator "".
refresh
See snapshot.
relation
A relation value. Note: As is well known, the term
is also commonly used to refer to a relation variable, but this usage is deprecated
as the source of much confusion.
relation assignment
Relational assignment.
relation comparison
Relational comparison.
relation constant
A named relation.
Examples: TABLE_DEE and TABLE_DUM.
Note: These two relation constants are probably built-in (i.e., system-defined)assuming
they're supported at all, that is, which in today's products they probably aren't.
Here, by contrast, is one that's user-defined:
CONST STATES
RELATION { TUPLE { STATE NAME('Alabama') } ,
TUPLE { STATE NAME('Alaska' ) } ,
.............
TUPLE { STATE NAME('Wyoming') } } ;
relation equality
Equality of relations; relations r1 and
r2 are equal (i.e., the relational comparison r1 =
r2 evaluates to TRUE) if and only if r1
and r2 are the very same relation.
relation expression
Relational expression.
relation predicate
Let r be a relation. Then the relation predicate
for r is the predicate that represents the user-understood
meaning of r in some particular context. If r is of degree n,
that predicate will be n-adic (it will have a parameter
for each attribute of r). In accordance with The
Closed World Assumption, moreover, the body of r
will contain all and only those tuples that correspond to invocations of that predicate
that evaluate to TRUE.
Examples: 1. Let r
be the projection of the current value of relvar S over S# and CITY. Then the predicate
for r is "There exists a name
n and a status st such that supplier
S# is under contract, is named n, has status st, and is located in CITY." Note that this predicate
is dyadic, as is to be expected for a binary relation. 2. Consider the relations
r1 and r2, where
r1 is the projection S{CITY} and
r2 is the projection P{CITY}. Then it's certainly possible for
r1 and r2 to be equal; nevertheless,
they have different predicates, corresponding to their two different contexts (loosely
speaking, the predicates are "There exists a supplier located in CITY" and "There
exists a part stored in CITY," respectively).
relation type
Let {H} be a heading; then RELATION {H}
is a relation type with the same degree and attributes as {H}.
Examples: The type of relvar S is
RELATION { S# S#, SNAME NAME,
STATUS INTEGER, CITY CHAR }
The following (corresponding to a certain projection of relvar S) is also a relation
type:
RELATION { CITY CHAR, SNAME NAME }
relation type generator
See type generator.
relation type inference
The process of determining the type of the value denoted by a given relational expression.
Note that this process is completely specified by the rules defining the types of
the results of the various relational operations, q.v.
relation value
Loosely, a table (value). More precisely, let RELATION {H}
be a relation type, and let {b} be a set of tuples
of type TUPLE {H}. Let r
be the pair <{H},{b}>.
Then r is a relation value (relation for short)
of type RELATION {H}, with heading {H}
and body {b}, and the same degree and attributes
as {H} and the same cardinality as {b}.
Contrast relation variable; relvar.
Note: Relations as defined in the relational model
differ in certain respects from the mathematical construct of the same name. In
particular, relations in mathematics typically don't have named attributes; instead,
their attributes are identified by their ordinal position, left to right.
relation-valued attribute
An attribute whose type is some relation type. Values of such an attribute are relations
of the specified type (sometimes called nested relations, since they're "nested"
inside tuplesespecially tuples in some other relation). Note:
If a relvar has a relation-valued attribute, that fact in and of itself doesn't
constitute a violation of any particular level of normalization (not even first);
however, such attributes are usually contraindicated in database design, at least
in base relvars, because they necessarily imply some structural asymmetry and thereby
give rise to asymmetry (and complexity) in queries and updates also.
See also grouping; ungrouping.
relation variable
Loosely, a table (variable); more precisely, a variable whose type is some relation
type. Let relation variable R be of type RELATION
{H}; then R has
the same heading (and therefore attributes) and degree as that type does. Let the
value of R at some given time be
r; then R has the same body and cardinality
at that time as r does. Note that a relation variable
is not the same thing as a set of tuple variables
(not even a set of tuple variables all of the same type).
Contrast relation; relation value.
relational algebra
An open-ended collection of read-only operators on relations, each of which takes
one or more relations as operands and produces a relation as a result. Exactly which
operators are included is somewhat arbitrary, but the collection is required to
be at least as powerful as relational calculus, in the sense that every relational
calculus expression is semantically equivalent to some relational algebra expression.
Also, the operators are generic, in the sense that they apply to all possible relations
(loosely speaking). Note: Relational assignment
is a relational operator too, but it isn't a relational algebra operator because
it isn't read-only.
relational assignment
An operation that assigns a relation value to a relation variable (of the same type).
relational calculus
An applied form of predicate calculus, tailored to operating on relations, with
the property that every relational calculus expression is semantically equivalent
to some relational algebra expression. See also
domain calculus; tuple calculus.
relational comparison
A boolean expression of the form (exp1) theta (exp2),
where exp1 and exp2
are relational expressions of the same type T and
theta is any comparison operator that makes sense
for relations of type T (e.g., "=", "", "", etc.). Note:
The parentheses surrounding exp1 and
exp2 in the comparison might not be needed in practice.
relational completeness
A measure of the expressive power of a language. Essentially, a language is relationally
complete if and only if it's at least as powerful as relational calculusmeaning
that any relation that is definable by some relational calculus expression is also
definable by some expression of the language in question.
Examples: Relational algebra is relationally complete,
because every relational calculus expression is semantically equivalent to some
relational algebra expression. It follows that in order to prove that a given language
L is relationally complete, it suffices to prove
that every relational algebra expression is semantically equivalent to some expression
in L (which is often easier than proving that every
relational calculus expression is semantically equivalent to some expression in
L). SQL, for example, can easily be shown to be
relationally complete in this way. Note: In fact,
SQL is "more than" relationally complete, in that its expressions permit the definition
of many objects that aren't relations at all.
relational database
A database that abides by The Information Principle.
We assume throughout this dictionary that databases are always relational, barring
explicit statements to the contrary.
relational DBMS
A DBMS that manages relational databases (and no others); equivalently, a DBMS that
implements the relational model.
relational expression
An expression denoting a relation. Relation literals, relation selector invocations,
relcon and relvar references (i.e., relcon and relvar names, syntactically speaking),
and relational algebra operator invocations are all special cases.
relational model
The formal theory or foundation on which relational databases in particular and
relational technology in general are based. The relational model is often loosely
characterized as having three aspects: a structural aspect, which has to do with
relations as such; an integrity aspect, which has to do with candidate and foreign
keys; and a manipulative aspect, which has to do with operators such as join. More
precisely, the relational model consists of the following components: (a) an open-ended
collection of scalar types, including in particular type BOOLEAN; (b) a relation
type generator and an intended interpretation for relations of types generated thereby;
(c) facilities for defining relation variables of such generated relation types;
(d) a relational assignment operator; and (e) an open-ended collection of generic
read-only operators (i.e., relational algebra or relational calculus) for deriving
relations from relations. Notice part (e) in particular; it's a far too common error
to regard the relational model as consisting of structure only and to overlook the
operators, and yet (as Codd once said) structure without operators is rather like
anatomy without physiology. Note, moreover, that those operators aren't just meant
for writing queries, as many seem to think; rather, they're for writing expressions,
expressions that serve many purposes (including query but not limited to it alone).
One particularly important purpose is the formulation of constraints (though in
this case, the relational expression will be just a subexpression of some boolean
expression, frequently though not invariably an invocation of IS_EMPTY, q.v.). Note: In the interest of physical data independence,
the relational model is deliberately silent on everything to do with performance.
relational operator
An operator that (a) takes either relations or relvars (or both) as operands and
(b) either returns a relation or updates at least one relvar.
relationship
1. A term used briefly in Codd's early papers (later discarded) to mean what we
would now call either a relation or a relvar, as the context demands. 2. In E/R
modeling, "an association among entities" (definition taken from the original E/R
paper). 3. More generally, given two sets (not necessarily distinct), a rule pairing
elements of the first set with elements of the second set; equivalently, that pairing
itself. This definition can easily be extended to three, four, … , or any
number of given sets; i.e., relationships aren't necessarily binary (consider, for
example, the ternary relationship involving suppliers, parts, and projects mentioned
in the example under fifth normal form).
relcon
A relation constant.
relvar
A relation variable. Note: For simplicity, we assume
in this dictionary that all relvars are part of some database. However, there's
no good reason why application-local relvars shouldn't be supported as well.
relvar constraint
1. ("A" relvar constraint) An integrity constraint
that refers to the relvar in question, as well as possibly others; informally, a
single-relvar constraint. 2. ("The" relvar constraint)
The logical AND of all integrity constraints, apart from type constraints, that
apply to a given relvar (the relvar con-straintsometimes
called the total relvar constraintfor the relvar
in question); in other words, the formal, system-under-stood "meaning" for the relvar
in question. Note: All relvar constraints, in either
sense, are also database constraints (q.v.).
Examples: First, the key constraint specified in
the definition of relvar S is a relvar constraint on that relvar. Second, the foreign
key constraint from SP to S is a relvar constraint on both relvar S and relvar SP.
Third, here are some more relvar constraints that might apply to relvar S:
CONSTRAINT C1 IS_EMPTY
( S WHERE STATUS < 1 OR STATUS > 100 ) ;
/* status values must be in the */
/* range 1 to 100 inclusive */
CONSTRAINT C3 IS_EMPTY
( ( S JOIN SP )
WHERE STATUS < 20 AND P# = P#('P6') ) ;
/* no supplier with status less */
/* than 20 can supply part P6 */
(Constraint C3 is also a relvar constraint for relvar SP.)
Finally, suppose for the sake of the example that the foregoing constraints (the
key constraint on relvar S, the foreign key constraint from relvar SP to relvar
S, and constraints C1 and C3) are the only ones that apply to relvar S. Then the
logical AND of all of them is "the" (total) relvar constraint for that relvar.
relvar predicate
Let R be a relvar (real or virtual). Then the relvar
predicate for R is the predicate that represents
the user-under-stood meaning of R. If
R is of degree n, that predicate will
be n-adic (it will have a parameter for each attribute
of R). In accordance with The Closed World Assumption,
moreover, at any given time the body of R will
contain all and only those tuples that correspond to invocations of that predicate
that evaluate to TRUE at that time. Contrast
relvar constraint (second definition); this latter is a formal construct,
but relvar predicates are necessarily somewhat informal. Note:
Relvar predicates are sometimes called business rules
(though some writers use this term to include other constructs in addition to relvar
predicates).
Example: The relvar predicate for relvar S is "Supplier
S# is under contract, is named SNAME, has status STATUS, and is located in CITY."
renaming
Let r be a relation, let
A be an attribute of r, and let
r not have an attribute named B.
Then the renaming r RENAME (A
AS B) is a relation with (a) heading identical
to that of r except that attribute
A in that heading is renamed B, and
(b) body identical to that of r except that all
references to A in that body are replaced by references
to B. See also tuple renaming.
Example: The expression
P RENAME ( WEIGHT AS WT )
yields a relation identical to the current value of relvar P, except that attribute
WEIGHT is renamed WT. Note that relvar P per se remains unaltered in the databaseRENAME
is not like ALTER TABLE in SQL, it's simply a read-only operator that (like restrict,
for example) takes a certain relation as input and returns another as output. Note: For reasons of user friendliness,
Tutorial D allows two or more consecutive renamings to be expressed
by means of a single RENAME invocation. Thus, for example, the expression (P RENAME
(WEIGHT AS WT)) RENAME (COLOR AS COL) can be abbreviated to P RENAME (WEIGHT AS
WT, COLOR AS COL). A similar remark applies to several other relational (and tuple)
operations alsofor example, EXTEND, SUMMARIZE, and so on.
repeating group
Let some table have a column C of type
T. Then C is a repeating group column
if and only if the values appearing within C aren't
values of type T but are, rather, sets (or lists
or arrays or …) of values of type T. Repeating
groups are outlawed in the relational model (which is why this definition is phrased
in terms of tables and columns instead of relations and attributes); in fact, a
"relation" with a repeating group "attribute" is a contradiction in terms.
restriction
Let bx be a boolean expression in which all of
the attributes mentioned are attributes of the same relation r. Then the restriction
r WHERE bx is
a relation with heading the same as that of r and
body consisting of all tuples of r for which bx evaluates to TRUE. Note:
Restriction is sometimes known as selection, but it shouldn't be confused with the
SELECT operation of SQL. The SQL SELECT operationmeaning, more specifically, just
the SELECT portion of an SQL SELECT -FROM -WHERE expressioncan be loosely characterized
as a combination of EXTEND, RENAME, and "project" ("project" in quotes because it
doesn't eliminate duplicates, in general, unless explicitly requested to do so via
DISTINCT).
Example: The following expression denotes a restriction
of the relation that's the current value of relvar P:
P WHERE WEIGHT < WEIGHT ( 17.5 ) AND CITY = 'Paris'
reversible decomposition
Replacing a relvar R by a set of relvars
R1, R2, … , Rn in such a way that it's guaranteed that
R can be obtained from R1, R2, …, Rn.
Nonloss decomposition, q.v., is an important special case.
RM/T
An extended form of the relational model, due to Codd, with the explicit goal of
capturing more meaning than the relational model per se is capable of. The name
is an abbreviation for Relational Model / Tasmania (so called because Codd first
described it at a conference in Tasmania). RM/T includes a variety of "semantic"
constructs (e.g., E-and P-relations, which are meant to represent entities and properties,
respectively, together with operators for operating on such relations). RM/T has
never been implemented in a commercial product (in fact it couldn't be, since the
sole formal paper on the topic"Extending the Database Relational Model to Capture
More Meaning," ACM TODS 4, No. 4fails to specify
it adequately), but its ideas can be useful as an aid in conventional database design.
RM/V1
See RM/V2.
RM/V2
Codd spent much of the late 1980s revising and extending the original relational
model, which he referred to as "the relational model Version 1" or RM/V1, to produce
"the relational model Version 2" or RM/V2. As noted in the introduction, however,
definitions in this dictionary are intended to conform to the relational model as
defined by The Third Manifesto; as a consequence,
they don't always agree with Codd's RM/V1 or RM/V2 definitions. For details of these
latter, see Codd's book The Relational Model for Database
Management Version 2 (Addison-Wesley).
row
1. SQL analog of either a tuple value or a tuple variable, as the context demands.
2. More generally, a picture of a tuple (on paper, for example).
See also table.
row ID
An implementation construct (typically, though not necessarily, some kind of pointer,
q.v.). In some commercial products, however, such IDs are exposed to the userusually,
and unfortunately, in such a way as to violate either The
Information Principle or The Principle of Interchangeability
or both. Sometimes called a tuple ID.
RVA
Relation-valued attribute.
scalar
1. (Of a type, attribute, value, or variable) Having
no user-visible component parts. The term is also often used as an abbreviation
for scalar value specifically. 2.
(Of an operator) Returning a scalar result. Note:
Scalar types and scalar values are required in the relational model; scalar variables
aren't, but they're almost certainly needed in the external environment in order
to support, for example, retrieval of the value of some scalar attribute from some
tuple of some relation. Note too that there's no such thing as "absolute scalarness"the
concept is necessarily somewhat relative. For example, a phone number might be perceived
equally well as an indivisible scalar value or as a tuple value consisting of country
code, area code, and local number (and a database design involving phone numbers
ought to support both perceptions). Consider also the case of TABLE_DUM, which is
clearly a relation and yet (like a scalar) has no user-visible component parts.
second normal form
Relvar R is in second normal form, 2NF, if and
only if every attribute A of
R not contained in any key of R is such
that the set {A} is irreducibly dependent on every
key of R. Every 2NF relvar is in 1NF (as is every
relvar, in fact). Note: Although being in 2NF clearly doesn't preclude being in the next higher
normal form (3NF) as well, the term 2NF is often used loosely to refer to a relvar
that's in 2NF and not in 3NF. Also, second normal form as such is no longer very
important (BCNF, 5NF, and 6NF being the normal forms of most practical significance);
we mention it here mainly for historical reasons.
Example: As noted under Boyce/Codd normal form,
it's often more instructive with the normal forms to show a counterexample rather
than an example per se. Suppose for the sake of the example, therefore, that relvar
SP has an additional attribute CITY, representing the city of the applicable supplier.
This revised version of SP satisfies the FD {S#}
{CITY}, and is therefore not in 2NF (because CITY isn't contained in any key and
{CITY} isn't irreducibly dependent on the key {S#,P#}).
second order logic
A form of predicate logic in which the sets over which variables range are allowed
to contain predicates. Contrast first order
logic.
Example: Consider the well-known principle of mathematical
induction, limited here for simplicity to its application to monadic predicates
p whose sole parameter is of type "nonnegative integer." That principle can be stated
(in somewhat stilted English) as follows: for all such predicates
p, if (a) p(0) is true and if (b) for
all i, if p(i)
is true then p(i+1) is true, then (c)
p(n) is true for all n. In symbols:
FORALL p ( ( p(0) AND
FORALL i ( p(i) IMPLIES p(i+1) ) )
IMPLIES FORALL n ( p(n) ) )
In this example, the variables i and
n range over nonnegative integers but the variable
p ranges over predicates (specifically, monadic predicates whose
sole parameter is of type "nonnegative integer"). The overall expression is thus
second order.
selection
See restriction.
selector
An operator for selecting, or specifying, an arbitrary value of a given type; not
to be confused with the SELECT operation of SQL (for a loose characterization of
this latter, see restriction).
Every type, tuple and relation types included, has at least one associated selector.
Note: Ultimately, the only way any expression can
ever yield a value of type T is via invocation
of some selector for that type T. In fact, the
selector notion is essentially a generalization of the familiar concept of a literal;
that is, all literals are selector invocations, but some selector invocations aren't
literals. (To be specific, a selector invocation is a literal if and only if all
of its arguments are literals in turn.)
Examples: Several selector invocations appear in
the example under INSERT; however, those examples are all literals,
since their arguments are all literals in turn. By contrast, here are some selector
invocations that aren't literals. Let SX, PX, and QX be variables of types CHAR,
CHAR, and INTEGER, respectively. Then (a) the expressions S#(SX), P#(PX), and QTY(QX)
are selector invocations for types S#, P#, and QTY, respectively; (b) the expression
TUPLE {S# S#(SX), P# P#(PX), QTY QTY(150)} is a selector invocation for tuple type
TUPLE {S# S#, P# P#, QTY QTY}; and (c) the expression RELATION {ts},
where ts is the tuple selector invocation just
shown, is a selector invocation for relation type RELATION {S# S#, P# P#, QTY QTY}.
self-referencing relvar
A relvar R with a foreign key matching some key
of R itself. Database designs involving such relvars
are usually contraindicated.
semantic optimization
Using integrity constraints to help in the process of transforming relational expressions,
usually for performance purposes. See expression
transformation; optimizer.
Examples: Consider the query
P WHERE CITY = 'London' AND COLOR = 'Red'
Suppose relvar P is subject to the constraint that parts in London must be red.
Then the query can clearly be transformed into the following simpler one:
P WHERE CITY = 'London'
Moreover, if the original query had requested blue parts instead of red ones, the
optimizer might be able to determine that the result must be empty without actually
having to execute the query at all.
semidifference
Let r1 and r2
be relations. Then the semidifference between r1
and r2 (in that order), r1
NOT MATCHING r2, is shorthand for
r1 MINUS (r1 MATCHING
r2).
Example: The expression
S NOT MATCHING SP
yields suppliers who currently supply no parts at all.
SEMIJOIN
Same as MATCHING.
semijoin
Let r1 and r2
be relations. Then the semijoin of r1 with r2 (in that order), r1
MATCHING r2, is shorthand for (r1
JOIN r2){X}, where
{X} is the heading of r1.
Note that, in general, r1 MATCHING
r2 and r2 MATCHING
r1 aren't equivalent.
Example: The expression
S MATCHING SP
yields suppliers who currently supply at least one part.
SEMIMINUS
Same as NOT MATCHING.
sentence
See logical system.
SEQUEL
Original name for SQL.
set
A collection of objects, called elements, with the property that given an arbitrary
object x, one can determine whether
x appears in the collection (see set
membership). Sets have no ordering to their elements, nor do they
contain any duplicate elements. Note: There's a
logical difference (actually a difference in type) between an element
x and the set {x} that contains only
that element x. Thus, a relational language needs
to provide both (a) an operator for extracting the single tuple from a relation
of cardinality one, and (b) an operator for extracting the single attribute value
from a tuple of degree one (see attribute extractor;
tuple extractor). Note too that the inverse functionalityin effect,
building up a tuple from specified attribute values and building up a relation from
specified tuple valuesis provided by the appropriate tuple and relation selectors
(see selector).
set function
Deprecated (because inappropriate) term for an aggregate operator.
set inclusion
Set s2 is included in set
s1 if and only if it is a subset of s1.
Note that every set is included in itself, also that every set includes the empty
set.
set level
The operators of the relational model are all set level, in the sense that they
take entire relations or relvars (or both) as operands and either produce entire
relations as results or update entire relvars. (Relation level
would be a better term.) Contrast tuple level.
set membership
(Of an element) The property of appearing in some
given set; the operation of testing for that property. Set membership is usually
denoted by the symbol "
";
thus, for example, the boolean expression x
s (which is semantically equivalent to the expression
{x}
s) returns TRUE if and only if element x does in fact appear in set
s.
set theory
A branch of mathematics, closely related to logic, that deals with the nature of
sets; it formalizes the concept of a set in terms of certain axioms, such as the
axiom of extension ("Sets s1 and
s2 are equal if and only if they have the same elements").
Sheffer stroke
See NAND.
simple attribute
An attribute. Contrast composite attribute.
simple predicate
A predicate that involves no connectives.
simple proposition
A proposition that involves no connectives.
single-relvar constraint
Informally, an integrity constraint that mentions exactly one relvar.
Contrast multi-relvar constraint. Note:
The difference between single-and multi-relvar constraints is more a matter of pragma
than logic, thanks to The Principle of Interchangeability.
Examples: The key constraints for relvars S, SP,
and P; also constraints C1 and C2 from the examples under database constraint.
sixth normal form
Relvar R is in sixth normal form, 6NF, if and only
if it can't be nonloss decomposed at all (other than into the identity projection
of R). Observe, therefore, that 6NF is the ultimate
normal form with respect to normalization as conventionally understood; in particular,
every 6NF relvar is in 5NF. Note: The concept of
6NF is given an extended definition in a temporal database context, where it enjoys
certain advantages over 5NFadvantages that don't necessarily apply in a conventional
(nontemporal) database. The details are beyond the scope of this dictionary.
Example: Relvars S and P aren't in 6NF, because
they can both be nonloss decomposed into several binary projections. By contrast,
relvar SP is in 6NF.
snapshot
A derived relvar that's real, not virtual (contrast
view). The value of a given snapshot at a given time is the result
of evaluating a certain relational expression (the snapshot-defining expression,
specified when the snapshot per se is defined) at some time prior to the time in
question. The snapshot is "refreshed" (meaning the snapshot-defining expression
is reevaluated and the result assigned as the new current value of the snapshot)
on demand or, more usually, when some specific event occurs, such as the passing
of a certain interval of time. Note: The snapshot-defining
expression must mention at least one relvar, for otherwise the snapshot wouldn't
be, specifically, a relation variable.
Example: The following statement defines a snapshot
called LSS:
VAR LSS SNAPSHOT ( S WHERE CITY = 'London' )
REFRESH EVERY DAY ;
The relation that's the current value of snapshot LSS at any given time is equal
to the value of the snapshot-defining expression S WHERE CITY = 'London' as it was
at most 24 hours prior to the time in question.
sort/merge
A join implementation technique.
soundness
The property of a formal system according to which, given a set
s of sentences of the system, no sentence not implied by those in
s can be derived using the rules of inference of that system (i.e.,
all theorems are tautologies). Contrast completeness.
SQL
The best-known attempt (unfortunately a seriously flawed one) to realize the abstract
ideas of the relational model in concrete syntactic form. The name SQLthe official
pronunciation is "ess cue ell," though it's often pronounced "sequel"was originally
an abbreviation for Structured Query Language.
In its standard incarnation, however, the name is just a name and isn't considered
to be an abbreviation for anything at all. The version of the SQL standard current
at the time of this writing is SQL:2003 (so called because it was ratified in 2003);
the next version is scheduled for ratification in 2007.
star join
A join implementation technique.
state constraint
A database constraint that is not a transition constraint.
statement
1. (Logic) A proposition. 2.
(Programming languages) A construct that causes some action to occur,
such as defining or updating a variable or changing the flow of control.
Contrast expression.
subexpression
An expression nested inside another expression.
subquery
Loosely, a subexpression of a relational expression; in SQL, a SELECT -FROM -WHERE
expression nested inside another such.
subject to update
Let Op be an update operator that, when invoked,
updates the argument corresponding to parameter x.
Then parameter x is said to be subject to update
(and any argument corresponding to x must be a
variable specifically).
Example: See the second version of operator DOUBLE
in the examples under argument.
subset
Set s2 is a subset of set
s1 if and only if every element of s2
is also an element of s1. Observe that every set
is a subset of itself, also that the empty set is a subset of every set.
Contrast proper subset.
substitution
1. (View implementation) A technique for implementing
operations on views, according to which references to view
V are replaced by the view-defining expression for
V (contrast materialization).
2. (Operator invocation) The process of replacing
a parameter by an argument.
Example (view implementation): See the second example
under pseudovariable reference.
subtables and supertables
A scheme according to which some table T1 is specified
to have all of the columns of some other table T2,
together with certain additional columns of its own (see
table). One of the numerous reasons for deprecating any such scheme
is that which of T1 and T2 is regarded as the subtable and which the supertable
can depend on the system in question.
subtuple
A subset of a tuple; hence, a tuple.
subtype
See type inheritance.
summarization
Let r1 and r2
be relations such that r2 is of the same type as
some projection of r1, and let the attributes of
r2 be A1, A2, … , An.
Then the summarization SUMMARIZE r1 PER (r2)
ADD (summary AS X) is a relation with (a) heading
the heading of r2 extended with attribute X, and (b) body consisting of all tuples
t such that t is a tuple of
r2 extended with a value x for
attribute X. That value x is computed by evaluating
summary over all tuples of
r1 that have the same value for attributes A1, A2,
… , An as tuple t does. Relation
r2 must not have an attribute called
X, and summary must not refer to
X. Note: If r2 is not just of the
same type as some projection of r1 but actually
is such a projection, the PER clause can be replaced by a BY clause, as shown in
the third of the following examples.
Example: The following expression denotes a summarization
of the relation that's the current value of relvar SP:
SUMMARIZE SP PER ( S { S# } ) ADD ( COUNT ( ) AS CT )
That summarization is a relation of type RELATION {S# S#, CT INTEGER}, containing
one tuple for each distinct S# value currently appearing in relvar S (not SP!note
the PER specification), and no other tuples. Given the sample values in Figure 1, for example, the tuple for supplier
S2 in the result has S# value S2 and CT value two, and the tuple for supplier S5
has S# value S5 and CT value zero. By contrast, the expression
SUMMARIZE SP PER ( SP { S# } ) ADD ( COUNT ( ) AS CT )
yields a relation of type RELATION {S# S#, CT INTEGER} with one tuple for each distinct
S# value currently appearing in relvar SP. Given the sample values in Figure 1, for example, the result contains
no tuple for supplier S5. Note: This second SUMMARIZE
example can be simplified slightly thus:
SUMMARIZE SP BY { S# } ADD ( COUNT ( ) AS CT )
SUMMARIZE
See summarization.
summary
A SUMMARIZE operand (see summarization).
Note carefully that summaries aren't aggregate operator invocations, though they
might look rather like them. An aggregate operator invocation is an expression,
and it can appear wherever a literal of the appropriate type can appear. A summary,
by contrast, is merely an operand to SUMMARIZE; it isn't an expression, it has no
meaning outside the context of SUMMARIZE, and in fact can't appear outside that
context.
superkey
Loosely, a superset of a key; it has the uniqueness property but not necessarily
the irreducibility property. More precisely, let K
be a subset of the heading of relvar R; then K is a superkey for R
if and only if no possible value for R contains
two distinct tuples with the same value for K.
Examples: For relvar S, {S#} and {S#,CITY} are
both super-keys. Note that the heading of any given relvar
R is necessarily a superkey for R.
superset
Set s1 is a superset of set
s2 if and only if every element of s2
is also an element of s1. Note that every set is
a superset of itself, also that every set is a superset of the empty set.
Contrast proper superset.
supertype
See type inheritance.
surjection
A mapping, or function, from set s1 to set s2 such that each element of s2
is the image of at least one element of s1 (in
other words, a many-to-one correspondence, in the strict sense of that term). Also
known as a surjective or "many-to-one onto" mapping.
Example: Let s1
and s2 be the set of all integers and the set of
all nonnegative integers, respectively. Then the mapping from integers
x to their absolute values |x| is a
surjection from s1 to s2.
surrogate key
A single-attribute key with the property that its values serve solely as surrogateshence
the namefor the entities they stand for (in other words, they serve merely to represent
the fact that the corresponding entities exist, and they carry absolutely no additional
information or meaning). Contrast intelligent
key.
symmetric
1. (Of a truth-valued operator) Let
Op be a dyadic truth-valued operator, and assume for definiteness that
Op is expressed in infix style. Then
Op is symmetric if and only if, for all x
and y, if x Op y
is true, then so is y O px (i.e.,
Op is symmetric if and only if it's commutative). 2.
(Of a relation) Let r be a binary
relation. Then r is symmetric if and only if, for
all x and y, if
the tuple <x,y> appears in
r, then so does the tuple <y,x>.
Examples (first definition only): The logical operator
EQUIV; the equality operator "=".
symmetric difference (set theory)
The set of all elements appearing in either but not both of two given sets.
table
1. SQL analog of either a relation or a relvar, as the context demands. Here are
some of the major differences between tables in SQL and their relational counterparts:
(a) SQL tables can contain duplicate rows; (b) SQL tables can contain nulls; (c)
SQL tables have a left-to-right column sequence; (d) SQL tables can have two or
more columns with the same name; (e) SQL tables can have what are, in effect, columns
with no name at all. 2. More generally, a picture of a relation (on paper, for example).
Note: A confusion between relations and such tabular
pictures probably accounts for the popular misconception that "relations are flat,"
or two-dimensional. While it's obviously true that those pictures are two-dimensional,
relations in general aren't; rather, a relation of degree
n is n-dimensional, in the sense that
its tuples correspond to points in some n-dimensional
space (one dimension for each attribute of the relation in question). One specific
consequence of such considerations is that (again contrary to popular opinion) relations
are perfectly capable of representing so-called multidimensional data and thereby
supporting so-called online analytical processing (OLAP).
table alias
See alias.
TABLE_DEE and TABLE_DUM
Two preferably built-in relation constants. TABLE_DEE is the unique relation with
no attributes and exactly one tuple (necessarily the empty tuple); TABLE_DUM is
the unique relation with no attributes and no tuples at all.
Note: The names are perhaps not very well chosen, because these two relations
are precisely the ones that are most difficult to picture as tables.
tables and views / tables or views
Phrases that often appear in SQL contexts and strongly suggest that views are somehow
different from tables. But the whole point about views is that (in SQL terms) they
are tablesjust as, in mathematics, the whole point
about a set that's (e.g.) the union or intersection of two other sets is that it
is itself a set. Views should "look and feel" just like base tables to the user
(The Principle of Interchangeability translated
into SQL terms).
tautology
A predicate whose every possible invocation is guaranteed to yield TRUE, regardless
of what arguments are substituted for its parameters. Contrast
contradiction.
Examples: Let p1
be the predicate (actually a proposition) 2+2 = 4; let p2
be the predicate x = x,
where x is an arbitrary integer; and let
p3 be the predicate (p) OR (NOT(p)),
where p is an arbitrary predicate. Then
p1, p2, and p3 are all tautologies.
TCLOSE
See transitive closure.
temporal database
A database in which at least one of the relvars is temporal (where a temporal relvar
is one whose heading includes at least one attribute of some timestamp type, implying
that the corresponding relvar predicate has at least one parameter of some timestamp
type). A variety of special operators can be defined to help with the management
of such data-basessee the book Temporal Data and the Relational
Model, by C. J. Date, Hugh Darwen, and Nikos A. Lorentzos (Morgan Kaufmann,
2003)but all of those operators are, in the final analysis, shorthand for something
that can already be expressed in the classical relational algebra. Further details
are beyond the scope of this dictionary.
theorem
Something that follows from given axioms according to given rules of inference (and
is therefore true if the axioms are true and the inference rules are valid). In
a database, tuples in derived relations can be regarded as theorems, because they
represent propositions derived from the ones represented by tuples in the base relations.
Theorems include axioms (q.v.) as a degenerate special case.
theta join
A relational operation, equivalent to an expression of the form (r1
TIMES r2) WHERE A1
theta A2, where (a) A1
and A2 are attributes (of the same type
T)of r1 and r2,
respectively, and (b) theta is any comparison operator
that makes sense for values of type T (e.g., "=", ">", etc.).
Examples: The following expression represents the
greater-than join (i.e., theta here is ">") of suppliers and parts over cities:
( ( S RENAME ( CITY AS SC ) ) TIMES
( P RENAME ( CITY AS PC ) ) ) WHERE SC > PC
We assume here that CHARthe type of attribute CITYis an ordinal type (">" presumably
means "greater in alphabetic ordering"). Note that we could replace TIMES by JOIN
in the foregoing expression without changing the meaning. Also, replacing ">"
by "<" would yield a less-than join; replacing it by "=" would yield an equijoin.
third normal form
Relvar R is in third normal form, 3NF, if and only
if for every nontrivial FD A
B satisfied by R, either
A is a superkey for R or
B is a subset of some key of R
(or both). Every 3NF relvar is in 2NF. Note: Many
of the definitions of "3NF" in the literature are actually definitions of BCNF;
caveat lector. Also, although being in
3NF clearly doesn't preclude being in the next higher normal form (BCNF)
as well, the term 3NF is often used loosely to refer to a relvar that's in 3NF and
not in BCNF. In any case, third normal form as such is no longer very important
(BCNF, 5NF, and 6NF being the normal forms of most practical significance); we mention
it here mainly for historical reasons.
Example: As noted under Boyce/Codd normal form,
it's often more instructive with the normal forms to show a counterexample rather
than an example per se. Suppose, therefore, that relvar S satisfies the additional
FD {CITY}
{STATUS}; i.e., the status for a given supplier is a function of that supplier's
location. Because {CITY} isn't a superkey and {STATUS} isn't a subset of any key,
this version of relvar S isn't in 3NF (though it is in 2NF).
three-valued logic
A logic, abbreviated 3VL, in which there are three truth values: TRUE, FALSE, and
an intermediate value usually called UNKNOWN. SQL is based on such a logic.
(The relational model, by contrast, is based on two-valued logic, q.v.) In particular,
SQL's support for nulls, q.v., is based on a three-valued logic, though in fact
that support is logically flawed; for example, SQL treats the UNKNOWN truth value
and null as identical, even though there's a logical difference between the twoUNKNOWN
is a value, while null isn't a value at all but a "mark." (This is just one of many
logical errors in SQL's 3VL support.) Note: Tautologies
in 2VL aren't necessarily tautologies in 3VL; likewise, contradictions in 2VL aren't
necessarily contradictions in 3VL. As a result, theorems that hold in 2VL don't
necessarily hold in 3VL, and expression transformations that are valid in 2VL aren't
necessarily valid in 3VL.
time-varying relation
Codd's original term for a relvar; the term is deprecated because relations are
values and therefore don't vary over time.
TIMES
See cartesian product.
total database constraint
See database constraint.
total relvar constraint
See relvar constraint.
transaction
A unit of recovery and concurrency; loosely, a unit of work. Transactions are all
or nothing, in the sense that they either execute in their entirety or have no effect.
Note: Transactions are often said to be a unit
of integrity also. Because the relational model requires all integrity checking
to be immediate, however, the unit of integrity as far as the relational model is
concerned is the statement, not the transaction. See
atomic statement; immediate checking.
transition constraint
A database constraint that limits the transitions that a given database can validly
make from one state to another. Contrast state
constraint.
Example ("No supplier's status must ever decrease"):
CONSTRAINT TRC1 IS_EMPTY (
( ( S' { S#, STATUS } RENAME ( STATUS AS STATUS' ) )
JOIN
( S { S#, STATUS } ) )
WHERE STATUS' > STATUS ) ;
This formulation relies on the convention that a primed relvar name such as S' refers
to the corresponding relvar as it was prior to the update under consideration.
transitive
1. (Of a truth-valued operator) Let
Op be a dyadic truth-valued operator, and assume for definiteness that
Op is expressed in infix style. Then
Op is transitive if and only if, for all x, y,
and z, if x Op y
and y Op z are both true, then so is
x Op z. 2. (Of a relation) Let
r be a binary relation. Then r is
transitive if and only if, for all x, y, and z, if the tuples <x,y>
and <y,z> both appear in
r, then so does the tuple <x,z>.
3. (Of FDs) See Armstrong's inference rules.
Examples (first definition only): The logical operator
IMPLIES; the "less than" operator "<".
transitive closure
Let r be a binary relation with attributes A and B, both of
type T. Then the transitive closure of
r, TCLOSE r, is a relation
r+ defined as follows: the tuple <a,b>
appears in r+ if and only if it appears in r or there exists a value c
of type T such that the tuple <a,c>
appears in r and the tuple <c,b>
appears in r+ (note that this is a recursive definition).
As the following pseudocode algorithm suggests, computing TCLOSE
r conceptually involves iterative formation of the union of some intermediate
result (computed on the previous iteration) and a new partial result (computed on
the current iteration), until that union ceases to growin other words, until it
reaches a fixed point or "fixpoint."
r+ := r ;
do until r+ ceases to grow ;
r+ := WITH ( r+ RENAME ( B AS C ) ) AS t1 ,
( r RENAME ( A AS C ) ) AS t2 :
r+ UNION ( ( t1 JOIN t2 ) { A, B } ) ;
end do;
transitive FD
Let relvar R satisfy the FDs
A
B and B
C; then R also satisfies the transitive
FD A
C.
TransRelational™ Model
A proprietary DBMS implementation technology, not based on conventional direct image
techniques.
TRC
Tuple relational calculus.
triggered procedure
Strictly, an action (the "triggered action") to be performed if a specified event
(the "triggering event") occurs, though the term is often used loosely to include
the triggering event as well. No triggered procedures are prescribed by the relational
model, but they aren't necessarily proscribed either (though they would be if they
could lead to a violation of The Assignment Principle,
q.v., which they very well might in practice). Foreign key rules provide a pragmatically
important example (in which, as it happens, the "procedure" is specified declaratively).
Note: The combination of a triggering event and the corresponding triggered action
is often known simply as a trigger.
trivial FD
An FD that can't possibly be violated. The FD A
B is trivial if and only if A is a superset
of B.
trivial JD
A JD that can't possibly be violated. The JD *{A1,A2,…,
An} is trivial if and only if at least one of A1, A2,
… , An is the entire heading of the pertinent relvar
R.
trivial MVD
An MVD that can't possibly be violated. The MVD A
B is trivial if and only if either A
is a superset of B or the set theory union of A and B is the heading
of the pertinent relvar R (or both).
TRUE
See boolean value.
truth value
In two-valued logic, either TRUE or FALSE; in other words, a boolean value.
truth-valued expression
A boolean expression.
tuple
A tuple value. Every subset of a tuple (i.e., every subtuple of the tuple in question)
is itself a tuple.
tuple assignment
An operation that assigns a tuple value to a tuple variable (of the same type).
tuple calculus
A version of relational calculus, semantically equivalent to domain calculus (q.v.),
in which the range variables range over relations and thus denote tuples from those
relations.
Example: Here's a tuple calculus formulation of
the query "get supplier names for suppliers who supply at least one part" (see domain calculus for a domain
calculus analog):
SX RANGES OVER { S } ;
SPX RANGES OVER { SP } ;
SX.SNAME WHERE EXISTS SPX ( SPX.S# = SX.S# )
In stilted English: "get names of suppliers SX where there exists a shipment SPX
with the same supplier number as SX."
tuple comparison
A boolean expression of the form (exp1) theta (exp2), where exp1
and exp2 are tuple expressions of the same type
and theta is either "=" or "" (note that the operators "<" and ">" are explicitly not
defined for tuples). Note: The parentheses enclosing
exp1 and exp2
in the comparison might not be needed in practice.
tuple component
An <attribute, attribute value> pair appearing in the tuple in question. Note
that attributes in turn are defined to be <attribute name, type name> pairs.
Examples: The pairs <<S#,S#>,S1> and
<<SNAME,NAME>, Smith> are both components of the supplier tuple for
supplier S1 in Figure 1
Note: In Tutorial D,
tuple components are specified more simply as <attribute name, attribute value>
pairs (not meant to be exact Tutorial D syntax).
This simplified form is acceptable because the relational model requires attribute
names to be unique within the pertinent heading, and those names thus effectively
imply the corresponding type names.
tuple difference
See tuple union.
tuple composition
The tuple composition of tuples t1 and
t2, t1 COMPOSE t2, is the tuple union
of t1 and t2,
projected over all attributes not common to t1
and t2.
tuple equality
Equality of tuples; tuples t1 and
t2 are equal (i.e., the tuple comparison t1 = t2
evaluates to TRUE) if and only if t1 and
t2 are the very same tuple. More specifically, tuples
t1 and t2 are equal if and only
if they have the same attributes A1, A2, … , Anin
other words, they're of the same typeand, for all i
(i =1,2, … , n),
the value v1 of Ai
in t1 is equal to the value
v2 of Ai in t2.
Note: The importance of this concept can hardly
be overstated, because so much in the relational model depends on it. For example,
candidate keys, foreign keys, and mostif not allof the operators of relational algebra
are defined in terms of it. Note in particular too that (speaking rather loosely)
all 0-tuples are equal to one another, since in fact there's only one such tuple.
tuple expression
An expression denoting a tuple.
tuple extension
Let t be a tuple. Then the tuple extension EXTEND
t ADD (exp AS
X) is a tuple identical to
t except that it has an additional attribute called
X, with value as specified by exp.
Tuple t must not have an attribute called X, and exp must
not refer to X.
Example: Let t
be some tuple from relvar P. Then the expression
EXTEND t ADD ( WEIGHT * 454 AS GMWT )
yields a tuple just like t, except that it has
an additional attribute GMWT ("gram weight") whose value is 454 times the WEIGHT
value in that same tuple.
tuple extractor
An operator for extracting the single tuple from a specified relation of cardinality
one.
Example: The following expression extracts the
supplier tuple for supplier S1 from the current value of relvar S:
TUPLE FROM ( S WHERE S# = S#('S1') )
A runtime error will occur if the TUPLE FROM argument has cardinality either zero
or two or more.
TUPLE FROM
Tutorial D syntax for a tuple extractor (q.v.).
tuple ID
See row ID.
tuple intersection
See tuple union.
tuple join
See tuple union.
tuple level
An operator is tuple level if it takes individual tuples or tuplevars (or both)
as operands and either produces a tuple as a result or updates a tuple variable.
Note: There are no tuple level operations in the
relational model as such, but such operations are likely to be needed in the external
environment in order to support, for example, extraction of some tuple from some
relation.
tuple projection
Let t be a tuple and let {X} be a subset of the
heading of t. Then the tuple projection
t{X} is a tuple obtained from t by discarding
all components not corresponding to attributes in {X}.
Example: Let t
be some tuple from relvar S. Then the expression t{STATUS,CITY}
yields a tuple of type TUPLE {STATUS INTEGER, CITY CHAR}, containing just the STATUS
and CITY components from that tuple t.
tuple relational calculus
Tuple calculus.
tuple renaming
Let t be a tuple, let A
be an attribute of t, and let
t not have an attribute named B. Then
the tuple renaming t RENAME (A
AS B) is a tuple identical to
t except that attribute A in that tuple
is renamed B.
Example: Let t
be some tuple from relvar P. Then the expression
t RENAME ( WEIGHT AS WT )
yields a tuple just like t, except that attribute
WEIGHT is renamed WT.
tuple type
Let {H} be a heading; then TUPLE {H}
is a tuple type with the same degree and attributes as {H}.
Examples: The type of the tuples in relvar S is
TUPLE { S# S#, SNAME NAME, STATUS INTEGER, CITY CHAR }
The following (corresponding to a certain projection of a supplier tuple) is also
a tuple type:
TUPLE { CITY CHAR, SNAME NAME }
tuple type generator
See type generator.
tuple type inference
The process of determining the type of the value denoted by a given tuple expression.
Note that this process is completely specified by the rules defining the types of
the results of the various tuple operations, q.v.
tuple union
The tuple union of two tuples t1 and
t2, t1 UNION t2 (where if
t1 and t2 have any attributes in
common, then the corresponding attribute values must be the same), is the set theory
union of t1 and t2.
(This operation could obviously be generalized to apply to any number of tuples.)
Note: Tuple union might reasonably be called tuple
join. Also, it would clearly be possible to define tuple intersection and tuple
difference operators if desired.
Example: Let t1
be a tuple from relvar S and t2 a tuple from relvar
SP, and let t1 and t2
have the same S# component (the same S# value in particular). Then the expression
t1 UNION t2 yields
a tuple of type TUPLE {S# S#, SNAME NAME, STATUS INTEGER, CITY CHAR, P# P#, QTY
QTY}, with components as in t1 or
t2 or both, as applicable.
tuple unwrapping
Let s be a tuple with an attribute
YT of type TUPLE {Y}, and let {X}
be the set of all attributes of s except
YT. Let {Y} have attributes
Y1, Y2, …, Yn; also, let {X}
not contain any attribute with the same name as any of Y1,
Y2, …, Yn. Then the tuple unwrapping s
UNWRAP (YT) is another tuple
t. The heading of t consists of the set theory union of {X}
and {Y}. Let tuple s
have X value x
and YT value a tuple with
Y1 value y1, Y2 value
y2, …, and Yn value
yn; then tuple t has
X value x, Y1 value
y1, Y2 value y2, …
, and Yn value yn.
Example: Let t be a tuple from relvar SP, and let
tw be the tuple resulting from the expression
t WRAP ( { P#, QTY } AS PQ_TUP )
(see tuple wrapping). Then the
expression
tw UNWRAP ( PQ_TUP )
yields t.
tuple value
Loosely, a row (value). More precisely, let TUPLE {H}
be a tuple type, and let t be a set of pairs <<A,T>,v>, called components, obtained from {H}
by attaching to each attribute <A,T> in {H} some value v
of type T, called the attribute value in
t for attribute A. Then
t is a tuple value (tuple for short) of type TUPLE {H},
with heading {H} and the same degree and attributes
as {H}. Note:
Tuples as defined in the relational model differ in certain respects from the mathematical
construct of the same name. In particular, tuples in mathematics typically don't
have named attributes; instead, their attributes are identified by their ordinal
position, left to right.
tuple variable
Loosely, a row (variable); more precisely, a variable whose type is some tuple type.
Let tuple variable T be of type TUPLE {H};
then T has the same heading (and therefore attributes)
and degree as that type does. Note: Tuple variables
aren't required by the relational model as such, but they're likely to be needed
in the external environment in order to support, for example, extraction of some
tuple from some relation.
tuple wrapping
Let t be a tuple and let the heading of
t be partitioned into subsets {X} and
{Y}. Let the attributes of {Y}
be Y1, Y2, …, Yn; also, let {X}
not contain any attribute called YT. Then the tuple
wrapping t WRAP ({Y}AS
YT) is another tuple s.
The heading of s consists of {X}
extended with an attribute YT of type TUPLE {Y}. Let tuple t
have X value x, Y1
value y1, Y2 value y2,
…, and Yn value yn;
then tuple s has X
value x and YT
value a tuple with Y1 value
y1, Y2 value y2, …, and
Yn value yn.
Example: Let t
be the tuple for supplier S1 and part P1 from relvar SP. Then the expression
t WRAP ( { P#, QTY } AS PQ_TUP )
yields a tuple tw of type TUPLE {S# S#, PQ_TUP
TUPLE {P# P#, QTY QTY}}, with S# value S1 and PQ_TUP value a tuple with P# value
P1 and QTY value 300.
tuplevar
A tuple variable.
two-valued logic
Conventional logic, abbreviated 2VL, in which there are just two truth values, TRUE
and FALSE.
type
A named, finite set of values (not to be confused with the internal representation
of the values in question, which is an implementation issue). Types can be either
scalar or nonscalar (in particular, they can be tuple or relation types); consequently,
attributes of relations can also be either scalar or non-scalar. Types can also
be either system-defined (i.e., built-in) or user-defined. They can also be generated
(see type generator).
Note: A type isn't a value, nor is it a variable; in particular, relation
values and relation variables aren't types. Equating types and either relation values
or relation variablesa position that has been advocated in the literaturehas been
described as The First Great Blunder. (For the
second, see pointer.)
Example: Here's a sample type definition:
TYPE POINT …
{ … CONSTRAINT ( X ** 2 + Y ** 2 )
10000 } ;
POINT here is a user-defined type, denoting geometric points in two-dimensional
space. It's subject to a type constraint that says, in effect, that the only points
of interest are those that lie on or inside a circle with center the origin and
radius 100.
Note: The (necessary) definition of the representation
of POINT values in terms of the cartesian coordinates X and Y is deliberately omitted
from the example, because a detailed discussion of that definition would take us
too far afield. Other irrelevant details are also omitted for similar reasons.
type constraint
A definition of the set of values that make up a given type. The type constraint
for type T is checked when some selector is invoked
for that type T; in other words, a type constraint
error occurs if and only if some selector is invoked with arguments that violate
the applicable type constraint. Contrast type
error.
Example: See the POINT example under type.
type error
The error that occurs if some operator is invoked with an argument that's not of
the type of the corresponding parameter. Unlike integrity violations, such errors
should be detectable at compile time (unless type inheritance is supported, in which
case certain type errorsnot all, by any meansmight not be detectable until runtime).
type generator
An operator that's invoked at compile time instead of run time and returns a type
instead of a value. For example, conventional programming languages typically support
an array type generator, which lets users define a variety of specific array types.
In the relational model, the tuple and (especially) relation type generators are
the most important ones; they allow users to define a variety of specific tuple
and relation types. See relation type; tuple
type.
Example: Consider the suppliers relvar definition:
VAR S BASE RELATION
{ S# S#, SNAME NAME, STATUS INTEGER, CITY CHAR }
KEY { S# } ;
This definition includes an invocation of the RELATION type generator (syntactically,
everything from the keyword RELATION to the closing brace following the keyword
CHAR, inclusive). That invocation returns a specific relation typeviz., the type
RELATION
{ S# S#, SNAME NAME, STATUS INTEGER, CITY CHAR }
So this type is in fact a generated typeas indeed are all relation types, and all
tuple types as well.
type inheritance
An organizing principle according to which one type can be defined as a subtype
of one or more other types, called supertypes (of the type in question). If T2 is a subtype of supertype T1,
then all values of type T2 are also of type T1, and read-only operators and type constraints
that apply to values of type T1 are inherited by
values of type T2. However, values of type T2 will have read-only operators and type constraints
of their own that don't apply to values that are only of type
T1 and not T2.
unary
Of degree one.
UNGROUP
See ungrouping.
ungrouping
Let s be a relation with an attribute
YR of type RELATION {Y}, and let {X}
be the set of all attributes of s except
YR. Let {Y} have attributes
Y1, Y2, … ,Yn; also, let {X}
not contain any attribute with the same name as any of Y1,
Y2, … , Yn. Then the ungrouping s
UNGROUP (YR) is another relation
r. The heading of r consists of the
set theory union of {X} and {Y}.
As for the body, let z be a relation with heading
consisting of {X} extended with an attribute YT, of type TUPLE {Y},
and body defined as follows: for each tuple of s, z
contains a set of tuples, one (t, say) for each
tuple in the YR value in that
s tuple; each such tuple t contains
an X value (x,
say) equal to the X value from the
s tuple in question and a tuple value (yt,
say) equal to some tuple from the YR value in the
s tuple in question. Let
z contain no other tuples. Then r is
the result of z UNWRAP (YT).
Example: Let spq
be the relation resulting from the expression
SP GROUP ( { P#, QTY } AS PQ_REL )
(see grouping). Then the expression
spq UNGROUP ( PQ_REL )
denotes an ungrouping of spq. That ungrouping is
a relation of type RELATION {S# S#, P# P#, QTY QTY}, and if
spq is obtained from the relation sp
that is shown as the value of relvar SP in
Figure 1, then the result of ungrouping spq
is just sp. Suppose, however, that
spq additionally includes a tuple, say for supplier S5, in which the
PQ_REL value is an empty relation; the result of the foregoing UNGROUP won't contain
a tuple for supplier S5 (in fact, the result will still be, exactly, relation sp). In general, therefore, ungrouping a relation
r and then grouping it again in what might look
like an inverse way isn't guaranteed to take us back to r
(contrast grouping).
UNION
See union.
union
1. (Dyadic case) The union of two relations r1 and r2, r1 UNION
r2, where r1 and
r2 are of the same type T,
is a relation of type T with body the set of all
tuples t such that t
appears in either or both of r1 and r2. 2. (N-adic case) The union of n relations
r1, r2, … , rn (n
0),
UNION {r1,r2, … , rn}, where
r1, r2, … , rn are all of the same type T,
is a relation of type T with body the set of all
tuples t such that t appears in at least one of r1, r2, …
, rn. Note: If n
= 0, (a) some syntactic mechanism, not shown here, is needed to specify the pertinent
type T, and (b) the result is the empty relation
of that type. See also disjoint union; tuple
union.
Example: The expression (S{CITY}) UNION (P{CITY})
denotes the union of the projections on CITY of the relations that are the current
values of relvars S and P. That union is a relation of type RELATION {CITY CHAR}.
Moreover, if the current values of relvars S and P are s
and p, respectively, the body of that relation
consists of all tuples of the form <c> that
appear in s{CITY} or p{CITY},
or bothmeaning that c is a current supplier city
or a current part city, or both.
union compatibility
(Of relations) Of the same type. The term is deprecated
for many reasons, of which inappropriateness is one.
union (set theory)
The set of all elements appearing in either or both of two given sets. (This definition
can obviously be extended to apply to any number of sets.)
unique index
An implementation construct; not to be confused with a candidate key, q.v., even
though such an index might be used to implement some key constraint (i.e., to enforce
uniqueness of some candidate key).
universal quantifier
Let p(x) be a predicate with a parameter
x; then FORALL x (p(x)) is a predicate,
and it means "For all argument values v that can
replace the parameter x, p(v) is true." In this
example, FORALL x is a universal quantifier, and
x is a universally quantified bound variable (q.v.).
Note: Some writers refer to FORALL by itself as
the quantifier; the literature is not consistent on this point. More important,
note that if v1, v2, … , vn are all of the
possible argument values in the foregoing example, then FORALL
x (p(x)) is equivalent to (p(v1)) AND
(p(v2)) AND … AND (p(vn))
AND TRUE. Note in particular that this expression evaluates to TRUE if
n = 0 (i.e., if the bound variable x
ranges over an empty set).
Example: Here's a tuple calculus query that makes
use of the universal quantifier as well as the existential quantifier ("Get suppliers
who supply all parts"):
SX RANGES OVER { S } ;
SPX RANGES OVER { SP } ;
PX RANGES OVER { P } ;
SX WHERE
FORALL PX ( EXISTS SPX ( SPX.S# = SX.S# AND
SPX.P# = PX.P# ) )
This latter expression can be read as "Suppliers SX where, for all parts PX, there
exists a shipment SPX with the same supplier number as SX and the same part number
as PX."
universal relation
Given a relation type RELATION {H}, the relation
of that type that contains all possible tuples of type TUPLE {H}.
universal relvar
The join of all relvars in a given set of relvars. The normalization procedure of
nonloss decomposition, if viewed in isolation (i.e., ignoring other possible aids
to database design), tacitly assumes that it's possible to define an initial universal
relvar that has all of the attributes relevant to the database under consideration,
and then shows how that relvar can be replaced by successively "smaller" projections
until a "good" design is reached. For a variety of reasons, however, that assumption
is not very realistic.
UNWRAP
See unwrapping.
unwrapping
Let s be a relation with an attribute
YT of type TUPLE {Y}, and {X}
be the set of all attributes of s except
YT. Let {Y} have attributes
Y1, Y2, … , Yn; also, let {X}
not contain any attribute with the same name as any of Y1,
Y2, … , Yn. Then the unwrapping s
UNWRAP (YT) is another relation
r. The heading of r consists of the
set theory union of {X} and {Y}.
The body of r contains one tuple for each tuple
in s, and no other tuples. Let tuple
t of s have X
value x and YT
value a tuple with Y1 value
y1, Y2 value y2, …, and
Yn value yn; then the corresponding
tuple of r has X
value x, Y1 value y1, Y2
value y2, … , and Yn
value yn. See also
tuple unwrapping.
Example: Let spw
be the relation resulting from the expression
SP WRAP ( { P#, QTY } AS PQ_REL )
(see wrapping). Then the following
expression denotes an unwrapping of spw:
spw UNWRAP ( PQ_REL )
That unwrapping is a relation of type RELATION {S# S#, P# P#, QTY QTY}. If spw is obtained by wrapping the relation
sp that is shown as the value of relvar SP in
Figure 1, then the result of unwrapping spw
is just sp.
UPDATE
1. (Read-only operator) See what if.
2. (Update operator) Very loosely, an operator
that modifies a given set of attributes in a given set of tuples in a given relvar;
somewhat less loosely, an operator that replaces a given set of tuples in a given
relvar by another such set. It's shorthand for a certain relational assignment.
Example (second definition only): The UPDATE statement
UPDATE P WHERE CITY = 'London'
( WEIGHT := 2 * WEIGHT , CITY := 'Oslo' ) ;
is shorthand for the following relational assignment:
P := WITH ( P WHERE CITY = 'London' ) AS t1 ,
( EXTEND t1 ADD
( 2 * WEIGHT AS NW ) ) AS t2 ,
( EXTEND t2 ADD
( 'Oslo' AS NC ) ) AS t3 ,
( t3 { P#, PNAME, COLOR, NW, NC } ) AS t4 ,
( t4 RENAME ( NW AS WEIGHT ) ) AS t5 ,
( t5 RENAME ( NC AS CITY ) AS t6 ,
( P MINUS t1 ) AS t7 :
t7 UNION t6 ;
In this example, we might say, loosely, that attributes WEIGHT and CITY are being
modified in the tuples for London parts; we might also say, still loosely but a
little less so, that the tuples for London parts are being replaced; but what is
really happening is that a certain relation value is being assigned to a certain
relation variable.
UPDATE rule
A specific kind of foreign key rule, q.v.
update
A relational assignment (especially an INSERT, DELETE, or UPDATE operation).
update anomaly
A somewhat old-fashioned term, never very precisely defined, for the kind of thing
that can go wrong in a less than fully normalized database.
update operator
An operator that, when invoked, returns no value but updates at least one variable
(usually an argument) that's not local to the implementation of the operator in
question. An update operator invocation thus has no valueit's not an expression,
and it can't appear wherever an expression is required. In particular, it can't
be nested inside expressions. Every update operator invocation is semantically equivalent
to some assignment (possibly a multiple assignment, q.v.).
update propagation
See controlled redundancy.
user
Either an end user or an application programmer or both, as the context demands.
value
An "individual constant," such as the integer value 3. Values can be of arbitrary
complexity (they can be scalar or non-scalar; note in particular that tuples and
relations are both values). Values have no location in time or space; however, they
can be represented in memory by means of some encoding, and those representations
do have locations in time and spaceindeed, distinct representations of the same
value can appear at any number of distinct locations in time and space, meaning,
loosely, that the same value can appear as the current value of any number of distinct
variables, and/or as any number of attribute values within the current value of
any number of distinct tuplevars or relvars, at the same time or different times.
Note that, by definition, a value can't be updated; for if it could, then after
such an update it would no longer be that value. Note too that every value is of
some type (in fact, of exactly one type, except possibly if type inheritance is
supported). Note further that a value isn't a type, nor is it a variable.
Contrast appearance.
VAR
The Tutorial D operator for defining variables
(relation variables in particular).
variable
1. (Logic) See logic variable.
2. (Programming languages) A holder for a representation
of a value. Unlike values, variables (a) do have location in time and space and
(b) can be updated (that is, the current value of the variable can be replaced by
another value). Indeed, to be a variable is to be updatable; equivalently, to be
a variable is to be assignable to (and to be assignable to is to be a variable).
Note that every variable is declared to be of some type. Note further that a variable
isn't a type, nor is it a value.
variable reference
1. (Logic) See bound variable; free variable.
2. (Programming languages) Syntactically, a variable
name, used to denote either the variable as such or the value of that variable,
as the context demands. Note in particular that such a reference certainly denotes
the variable as such if it's used to specify a target for some update operationin
particular, if it appears on the left-hand side of an assignment. If on the other
hand it denotes the value of the variable, then it's a special case of an expression,
and it can appear wherever a literal (of the appropriate type) can appear.
view
A derived relvar that's virtual, not real (contrast
snapshot). The value of a given view at a given time is the result
of evaluating a certain relational expression (the view-defining expression, specified
when the view per se is defined) at the time in question.
Note: The view-defining expression must mention at least one relvar,
for otherwise the view wouldn't be, specifically, a relation variable. Note too
that the view must be updatable for the same reason.
Example: The following statement defines a view
called LSV:
VAR LSV VIRTUAL ( S WHERE CITY = 'London' ) ;
The relation that's the current value of view LSV at any given time is equal to
the value of the view-defining expression S WHERE CITY = 'London' at that time.
view updating
Either the theory or the process of updating views, as the context demands. View
updating is still a somewhat controversial topic, but there are those who believe
thatcontrary to popular opinionall views are at least theoretically updatable. The
details are beyond the scope of this dictionary.
virtual relvar
A view (contrast real relvar).
well-formed formula
In logic, a formal expression denoting a predicate.
what if
A read-only relational operator that returns the relation that would result if a
given update were performed on a given relvar (at the time of invocation), without
actually performing that update.
Example: Consider the following expression:
UPDATE S WHERE CITY = 'Paris'
( STATUS := 2 * STATUS , CITY := 'Nice' )
Observe that, even though it uses the keyword UPDATE, this expression is indeed
an expression and not a statement (it has no terminating semicolon), and it has
no effect on relvar S. What it does do is return a relation containing exactly one
tuple t for each tuple s
in relvar S for which the city is Parisexcept that, in that tuple
t, the status is double that in tuple s
and the city is Nice, not Paris.
WITH
A Tutorial D syntactic construct for introducing
names for the results of subexpressions. The introduced names can then be used subsequently
(within the overall expression of which the WITH clause forms a part) to denote
those results.
Example: The following is a formulation of the
query "Get pairs of supplier numbers, Sx and Sy say, such that Sx
and Sy each supply exactly the same set of parts":
WITH ( S RENAME ( S# AS SX ) ) { SX } AS tx ,
( S RENAME ( S# AS SY ) ) { SY } AS ty :
( tx JOIN ty ) WHERE ( SP WHERE S# = SX ) { P# } =
( SP WHERE S# = SY ) { P# }
WFF
A well-formed formula. The abbreviation is variously pronounced "weff," "wiff,"
or "woof." See also closed WFF; open WFF.
WRAP
See wrapping.
wrapping
Let r be a relation and let the heading of r be partitioned into subsets {X}
and {Y}. Let the attributes of {Y}
be Y1, Y2, …, Yn; also, let {X}
not contain any attribute called YT. Then the wrapping
r WRAP ({Y}AS
YT) is another relation s.
The heading of s consists of {X}
extended with an attribute YT of type TUPLE {Y}. The body of s
contains one tuple for each tuple in r, and no
other tuples. Let tuple t of
r have X value x,
Y1 value y1, Y2 value
y2, … , and Yn value
yn; then the corresponding tuple of s
has X value x
and YT value a tuple with
Y1 value y1, Y2 value
y2, … , and Yn value
yn. See also tuple wrapping.
Example: The following expression denotes a wrapping
of the relation that's the current value of relvar SP:
SP WRAP ( { P#, QTY } AS PQ_TUP )
That wrapping is a relation spw of type RELATION {S# S#, PQ_TUP TUPLE {P# P#, QTY
QTY}}; it contains one tuple for each tuple currently appearing in relvar SP, and
no other tuples. Given the sample values in
Figure 1, for example, the spw tuple for
supplier S1 and part P1 has S# value S1 and a PQ_TUP value that is a tuple with
P# value P1 and QTY value 300.
XML
Extensible Markup Language; from a database point of view, best regarded as "just
another data type" (albeit one of considerable pragmatic importance at the time
of writing)meaning, among other things, that relations should be allowed to have
attributes of the type in question, and tuples in such relations should thus be
allowed to include attribute values that are XML documents.
XOR
Seeexclusive OR.