Database Reference
In-Depth Information
2.2 Query languages
We now give a brief overview of the standard relational query languages such as relational
calculus, relational algebra, and their fragments.
Relational calculus
This is another name for first-order predicate logic, abbreviated as FO. Its formulae, over a
schema R with relation names
, are built inductively, using the rules presented
below. We assume a (countably infinite) set of variables, typically denoted by lowercase
letters such as
x
,
y
,
z
,...
, sometimes with subscripts and superscripts. We now define both
formulae of relational calculus, and their
free variables
.
U
1
,...,
U
m
If
U
i
is a relation in the schema, and
t
=(
t
1
,...,
t
n
i
) is a tuple of the same length as the
arity of
U
i
so that each
t
j
is either a variable, or a constant from the domain, then
U
i
(
t
)
is a formula.
Its free variables are exactly the variables present in
t
.
•
•
If each of
t
1
,
t
2
is either a variable, or a constant from the domain, then
t
1
=
t
2
is a
formula. Its free variables are exactly the variables among
t
1
and
t
2
. For example,
x
= 5
is a formula with free variable
x
, while
x
=
y
is a formula with free variables
x
and
y
.
Formulae of the two kinds described above are called
atomic formulae
.
•
If
ϕ
and
ψ
are formulae, then both
ϕ
∨
ψ
and
ϕ
∧
ψ
are formulae. Their free variables
include all the free variables of
ϕ
and
ψ
.
•
If
ϕ
is a formula, then
¬
ϕ
is a formula. Its free variables coincide with the free variables
of
ϕ
.
•
If
ϕ
is a formula and
x
is a variable, then both
∃
x
ϕ
and
∀
x
ϕ
are formulae. Their free
variables include all the free variables of
ϕ
except the variable
x
.
If we have a formula
ϕ
whose free variables are
x
=(
x
1
,...,
x
n
), we shall write
ϕ
(
x
) or
ϕ
(
x
1
,...,
x
n
).
We next define the semantics of relational calculus queries. Assume that we have an
instance
S
, in which each predicate
U
i
of arity
n
i
is interpreted as an
n
i
-ary relation
U
i
.For
each formula
ϕ
(
x
1
,...,
x
n
) and a mapping
σ
from a set of variables including
x
1
,...,
x
n
to
D
OM
(
S
) we define the notion of
(
S
,
σ
)
|
=
ϕ
(
x
)
,
saying that
ϕ
(
x
) is true when variables
x
1
,...,
x
n
are interpreted as
σ
(
x
1
)
,...,
σ
(
x
n
)
∈
D
OM
(
S
). Then the output of a query
ϕ
(
x
1
,...,
x
n
) on the instance
S
is
(
S
)=
σ
(
x
n
)
|
(
x
)
.
ϕ
(
x
1
)
,...,
σ
(
S
,
σ
)
|
=
ϕ
We now define (
S
,
σ
)
|
=
ϕ
(
x
) inductively. For atomic formulae, we have:
•
(
S
,
σ
)
|
=(
t
1
=
t
2
) iff
σ
(
t
1
)=
σ
(
t
2
).
=
U
i
(
t
1
,...,
t
n
i
) iff
σ
(
t
n
i
)
∈
U
i
.
•
(
S
,
σ
)
|
(
t
1
)
,...,
σ
