Database Reference
In-Depth Information
D
.An
instance S
of schema R =
U
1
,...,
U
m
assigns to each relation symbol
U
i
,where
m
, a finite
n
i
-ary relation
U
i
. Recall that
n
i
is the arity of
U
i
.
The
domain
of instance
S
, denoted by D
OM
(
S
), is the set of all elements that oc-
cur in the relations
U
i
. It is often convenient to define instances by simply listing
the tuples attached to the corresponding relation symbols. Further, sometimes we use
the notation
U
(
t
)
1
≤
i
≤
U
S
, and call
U
(
t
) a
fact
of
S
. For instance,
FLIGHT
(
Paris, Santiago, AirFrance
, 2320) is an example of a fact.
Given instances
S
and
S
of R, we write
S
S
instead of
t
∈
∈
S
if instance
S
is contained in instance
S
;
⊆
U
S
i
that is, if
U
i
⊆
for every
i
∈{
1
,...,
m
}
.
. It is measured as the sum of the sizes of all
relations in
S
. The size of each relation is the total number of values stored in that relation;
that is, the product of the number of tuples and the arity of the relation. In the example of
a relation above, we measure its size as 12, since it has four tuples, and has arity 3.
The size of instance
S
is denoted by
S
Integrity constraints
We often consider relational schemas with
integrity constraints
,
which are conditions that instances of such schemas must satisfy. The most commonly
used constraints in databases are functional dependencies (and a special case of those:
keys), and inclusion dependencies (and a special case of functional and inclusion depen-
dencies: foreign keys). Schema mappings, as we saw, are given by constraints that relate
instances of two schemas. These will be studied in detail in the topic; for now we review
the most common database constraints.
A
functional dependency
states that a set of attributes
X
uniquely determines another
set of attributes
Y
; a key states that a set of attributes uniquely determines the tuple. For
example, it is reasonable to assume that
flight#
is a key of
ROUTES
, which one may write
as a logical sentence
∀
f
∀
s
∀
d
∀
s
∀
d
ROUTES
(
f
,
s
,
d
)
∧
ROUTES
(
f
,
s
,
d
)
→
(
s
=
s
)
∧
(
d
=
d
)
.
An inclusion dependency states that a value of an attribute (or values of a set of attributes)
occurring in one relation must occur in another relation as well. For example, we may
expect each flight number appearing in
INFO FLIGHT
to appear in
ROUTES
as well: this is
expressed as a logical sentence
∀
f
∀
d
∀
a
∀
a
INFO FLIGHT
(
f
,
d
,
a
,
a
)
→∃
s
∃
d
ROUTES
(
f
,
s
,
d
)
.
Foreign keys are simply a combination of an inclusion dependency and a key con-
straint: by combining the above inclusion dependency with the constraint that
flight#
is a key for
ROUTES
, we get a foreign key constraint
INFO FLIGHT[flight#]
⊆
FK
ROUTES[flight#]
, stating that each value of flight number in
INFO FLIGHT
occurs in
ROUTES
, and that this value is an identifier for the tuple in
ROUTES
.
