Databases Reference

In-Depth Information

such that
A
appears in
X
.
1
Note:
Here I'm defining a version of the usual relational projection operator that

applies to individual tuples (see Exercise 2.11). Observe that every projection of a tuple is itself a tuple.

Definition:
A
relation
r
is an ordered pair <
H
,
h
>, where
h
is a set of tuples (the
body
of
r
) all having

heading
H
.
H
is the
heading
of
r
and the attributes of
H
are the
attributes
of
r
. The tuples of
h
are the

tuples
of
r
.

Definition:
Let
r
be the relation <
H
,
h
> and let
X
be a subset of
H
. Then the (relational)
projection
r
{
X
} of

r
on the attributes of
X
is the relation <
X
,
x
>, where
x
is the set of all tuples
t
{
X
} such that
t
is a tuple of
h
.

Definition:
Let relations
r1
, ...,
rn
(
n
≥ 0) be
joinable
—i.e., let them be such that attributes with the same

name are of the same type. Then the
join
of
r1
, ...,
rn
, JOIN {
r1
,...,
rn
}, is a relation with (a) heading the

union of the headings of
r1
, ...,
rn
and (b) body the set of all tuples
t
such that
t
is the union of a tuple from

r1
, ..., and a tuple from
rn
.
Note:
This version of join is what's sometimes called, more explicitly, the

natural
join. Note that it's an
n-
adic operator, not a dyadic operator merely (
n
= 2 is just a common special

case; as for
n
< 2, see Exercise 3.1). Note also that join degenerates to cartesian product in the important

special case in which the operand relations
r1
, ...,
rn
have no attributes with the same name.

Definition:
A
relation variable
or
relvar
with heading
H
is a variable
R
such that a value
r
can be assigned

to that variable only if that value
r
is a relation with heading
H
. The attributes of
H
are the
attributes
of
R
.

Also, if relation
r
is assigned to
R
, then the body and tuples of
r
are the
body
and
tuples
of
R
, respectively,

under that assignment.
Note:
As the definition says, relation
r
can be assigned to relvar
R
only
if (emphasis

added) it has the same heading as
R
. In fact, relation
r
can be assigned to relvar
R
if and only if
(a) it has the

same heading as
R
and(b) it satisfies all of the constraints that apply to
R
—where “all of the constraints that

apply to
R
” includes FDs that hold in
R
but (in general) isn't limited to such FDs alone.

FUNCTIONAL DEPENDENCIES

Now I'm in a position to deal properly with the concept of functional dependencies. Again I'll be presenting precise

definitions—but in this section I'll have rather more to say about those definitions and some of their implications.

Definition:
Let
H
be a heading; then a
functional dependency
(FD)
with respect to
H
is an expression of

the form
X
→
Y
, where
X
(the
determinant
) and
Y
(the
dependant
) are both subsets of
H
.
Note:
The phrase

FD with respect to H
can be abbreviated to just
FD
, if
H
is understood.

Here are a couple of examples:

{ CITY }
→
{ STATUS }

{ CITY }
→
{ SNO }

1
There's a tiny notational complication here. If
X
is a subset of
H
, then
X
is a set of attribute names, {
A1
,...,
An
} say, and the projection
t
{
X
}of
t

on
X
would thus apparently have to be written with double braces, like this:
t
{{
A1
,...,
An
}}. Of course we don't do this, and I'm going to ignore

this complication throughout the remainder of the topic. However, I should at least explain why it arises. Basically, it does so because we're

conflating two distinct interpretations of the symbol
X
. On the one hand, we're using that symbol to mean
the set as such
─i.e., the set whose

elements are
A1
, ...,
An
; on the other hand, we're using it to mean the
commalist of attribute names A1, ... An as physically written
that represents

those elements (on paper, say). The former is what the symbol
X
actually denotes; the latter is the way we express that denotation in concrete

syntax.