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.
