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.
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 } { 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
Search WWH ::

Custom Search