Database Reference
In-Depth Information
2
Theoretical background
The goal of this chapter is to introduce some of the basic concepts that will be used through-
out the topic. We describe the relational data model, including languages and integrity con-
straints for relational databases, as well as the fundamental concepts related to handling of
incomplete information. We also talk about ways of measuring the complexity of various
computational tasks that occur in the database context. Finally, we recall some basic facts
about finite automata; these will be used extensively in connection with XML data.
2.1 Relational database model
In the relational database model, data is organized in relations, and is described by means
of a
relational schema
. Informally, we have seen such schemas already in the examples of
the previous chapter. Formally, a relational schema R is a finite sequence
of
relation symbols, with each
U
i
having a fixed arity
n
i
>
0. For example, the target relational
schema considered in the introduction has three relations:
ROUTES
of arity 3,
INFO FLIGHT
of arity 4, and
SERVES
, also of arity 4.
An instance of a schema contains a relation, or a table, for each relation symbol. For
example, the following is a possible relation for
ROUTES
:
U
1
,...,
U
m
flight#
source
destination
AF406
Paris
Santiago
KLM1276
Edinburgh
Amsterdam
KLM1365
Amsterdam
Warsaw
AF5148
Paris
Edinburgh
Formally, we assume a domain of possible values
D
(such as
AF406
or
Pa ris
). Recall
that a
k
-ary relation over
D
is a subset of
D
k
=
D
×···×
D
, the product of
k
copies of
