s
Chapter 5 Review
471
relational calculus (p. 372)
relational database (p. 366)
relational model (p. 366)
residue of x modulo n (p. 423)
restrict (p. 369)
restriction of a partial ordering
(p. 336)
RSA public key encryption
algorithm (p. 431)
scalar (p. 448)
scalar multiplication (p. 448)
SELECT (p. 372)
simple substitution cipher (p. 429)
SQL (p. 372)
subtraction of matrices (p. 449)
successor in a partial ordering
(p. 336)
surrogate key (p. 368)
symmetric closure (p. 334)
symmetric encryption (p. 431)
symmetric matrix (p. 447)
symmetric relation (p. 332)
topological sorting (p. 359)
total ordering (p. 338)
transitive closure (p. 334)
transitive relation (p. 332)
tuple (p. 366)
UPC-A (Universal Product Code)
(p. 436)
upper triangular matrix (p. 453)
vector (p. 448)
vertex (p. 337)
zero matrix (p. 449)
Self-teSt
Answer the following true-false questions.
section 5.1
1. In a one-to-many binary relation, at least one first
component must appear in two different ordered
pairs.
2. If an antisymmetric binary relation contains (x, y),
then (y, x) will not belong to the relation.
3. A least element of a partially ordered set precedes
all elements except itself.
4. An equivalence relation cannot also be a partial
ordering.
5. A partial ordering on a set determines a partition of
that set.
section 5.2
1. If a task is not on the critical path in a PERT chart,
then that task is optional.
2. A topological sort turns a partially ordered set into
a totally ordered set.
3. If x precedes y after a topological sort on a finite
partially ordered set, then x preceded y in the original partial ordering.
4. The times to complete parallel tasks are added together in determining a critical path in a PERT chart.
5. A given set of data results in a unique topological
sort.
section 5.3
1. A relation in a relational database is a set of n tuples
of attribute values.
2. A primary key in a relation is a minimum subset of
attribute values that will uniquely identify each tuple.
3. The restrict operation can be achieved by doing a
union followed by an intersection.
4. The join operation can be achieved by doing a
Cartesian product followed by a restrict.
5. Deleting a tuple from a relation may result in additional deletions being done in order to satisfy data
integrity.
section 5.4
1. A binary relation on S × T that is not one-to-many
or many-to-many is a function from S to T.
2. To prove that a function is onto, begin with an arbitrary element of the range and show that it has a
preimage.
3. To prove that a function is one-to-one, assume
f (s 1 ) = f (s 2 ) for some s 1 and s 2 in the domain and
show that s 1 = s 2 .
4. The composition of two permutation functions on a
set is a permutation function on the set.
5. Any one-to-one function has an inverse function.
section 5.5
1. If f is Θ(g), then beyond some point the values for
f(x) must fall between
1
2 g(x) and 2g(x).
2. If f = O(g), then either f = Θ(g) or g = o( f ).
3. If f(x) = 3x
2
+ 15x − 2 and g(x) = 5000x
3
∙
(x − 1) then f = Θ(g).
4. An intractable problem is one that only has solution
algorithms of the form Θ(n
c
) where c ≥ 5.
5. In a recurrence relation of the form
S(n) = aS a
n
b
b + n
c
for n ≥ 2
the order of magnitude of the solution, as determined by the master theorem, depends on the ratio
of a to b
c
.
Chapter 5 Review
471
relational calculus (p. 372)
relational database (p. 366)
relational model (p. 366)
residue of x modulo n (p. 423)
restrict (p. 369)
restriction of a partial ordering
(p. 336)
RSA public key encryption
algorithm (p. 431)
scalar (p. 448)
scalar multiplication (p. 448)
SELECT (p. 372)
simple substitution cipher (p. 429)
SQL (p. 372)
subtraction of matrices (p. 449)
successor in a partial ordering
(p. 336)
surrogate key (p. 368)
symmetric closure (p. 334)
symmetric encryption (p. 431)
symmetric matrix (p. 447)
symmetric relation (p. 332)
topological sorting (p. 359)
total ordering (p. 338)
transitive closure (p. 334)
transitive relation (p. 332)
tuple (p. 366)
UPC-A (Universal Product Code)
(p. 436)
upper triangular matrix (p. 453)
vector (p. 448)
vertex (p. 337)
zero matrix (p. 449)
Self-teSt
Answer the following true-false questions.
section 5.1
1. In a one-to-many binary relation, at least one first
component must appear in two different ordered
pairs.
2. If an antisymmetric binary relation contains (x, y),
then (y, x) will not belong to the relation.
3. A least element of a partially ordered set precedes
all elements except itself.
4. An equivalence relation cannot also be a partial
ordering.
5. A partial ordering on a set determines a partition of
that set.
section 5.2
1. If a task is not on the critical path in a PERT chart,
then that task is optional.
2. A topological sort turns a partially ordered set into
a totally ordered set.
3. If x precedes y after a topological sort on a finite
partially ordered set, then x preceded y in the original partial ordering.
4. The times to complete parallel tasks are added together in determining a critical path in a PERT chart.
5. A given set of data results in a unique topological
sort.
section 5.3
1. A relation in a relational database is a set of n tuples
of attribute values.
2. A primary key in a relation is a minimum subset of
attribute values that will uniquely identify each tuple.
3. The restrict operation can be achieved by doing a
union followed by an intersection.
4. The join operation can be achieved by doing a
Cartesian product followed by a restrict.
5. Deleting a tuple from a relation may result in additional deletions being done in order to satisfy data
integrity.
section 5.4
1. A binary relation on S × T that is not one-to-many
or many-to-many is a function from S to T.
2. To prove that a function is onto, begin with an arbitrary element of the range and show that it has a
preimage.
3. To prove that a function is one-to-one, assume
f (s 1 ) = f (s 2 ) for some s 1 and s 2 in the domain and
show that s 1 = s 2 .
4. The composition of two permutation functions on a
set is a permutation function on the set.
5. Any one-to-one function has an inverse function.
section 5.5
1. If f is Θ(g), then beyond some point the values for
f(x) must fall between
1
2 g(x) and 2g(x).
2. If f = O(g), then either f = Θ(g) or g = o( f ).
3. If f(x) = 3x
2
+ 15x − 2 and g(x) = 5000x
3
∙
(x − 1) then f = Θ(g).
4. An intractable problem is one that only has solution
algorithms of the form Θ(n
c
) where c ≥ 5.
5. In a recurrence relation of the form
S(n) = aS a
n
b
b + n
c
for n ≥ 2
the order of magnitude of the solution, as determined by the master theorem, depends on the ratio
of a to b
c
.