Database Reference
In-Depth Information
In these first two rules, one of the
t
i
's could be a constant
c
. In that case, we make the
assumption that
(
c
)=
c
.
The remaining rules are as follows:
σ
•
(
S
,
σ
)
|
=
ϕ
∨
ψ
iff (
S
,
σ
)
|
=
ϕ
or (
S
,
σ
)
|
=
ψ
.
•
(
S
,
σ
)
|
=
ϕ
∧
ψ
iff (
S
,
σ
)
|
=
ϕ
and (
S
,
σ
)
|
=
ψ
.
•
(
S
,
σ
)
|
=
¬
ϕ
iff (
S
,
σ
)
|
=
ϕ
is false.
•
(
S
,
σ
)
|
=
∃
x
ϕ
iff (
S
,
σ
[
c
/
x
])
|
=
ϕ
for some
c
∈
D
OM
(
S
).Here
σ
[
c
/
x
] coincides with
σ
on all variables except
x
, on which its value is defined to be
c
.
•
(
S
,
σ
)
|
=
∀
x
ϕ
iff (
S
,
σ
[
c
/
x
])
|
=
ϕ
for all
c
∈
D
OM
(
S
).
In general, not all of the connectives are required. Due to the standard equivalences:
ϕ
∨
ψ
↔¬
(
¬
ϕ
∧¬
ψ
)
∀
x
ϕ
↔¬∃
x
¬
ϕ
conjunction, negation, and existential quantification are sufficient to express all relational
calculus queries.
As an example, consider a query
ϕ
(
x
) below:
z
ROUTES
(
y
,
x
,
z
)
∧
ROUTES
(
y
,
z
,
x
)
,
y
∃
∃
y
∃
z
∃
(2.1)
asking for cities that appear as both a source and a destination in table
ROUTES
.Inthe
example shown earlier, the answer to this query will include Edinburgh and Amsterdam.
A note on Boolean queries
We shall sometimes deal with Boolean queries, or queries
returning
true
or
false
. Normally we assume that the output of any relational query is
a relation, and the same must hold for Boolean queries. We represent the Boolean values
true
and
false
by means of relations of arity 0, i.e., containing tuples with no attributes.
There is only one such tuple, namely the empty tuple, which we denote by (). Hence, there
are only two possible relations of arity zero:
/0and
{
()
}
;
that is, the empty set, and the set containing the empty tuple. We shall associate the empty
set with
false
, and the set containing the empty tuple with
true
.
Relational algebra
Although we mainly deal with logical formalisms in this topic, we now briefly review rela-
tional algebra - the standard procedural counterpart of relational calculus. Each expression
of relational algebra, when applied to a database instance, produces a relation of some arity
n
≥
0. In general, we assume that attributes of an
n
-ary relation are named as 1
,...,
n
.
Relational algebra has the following five operations.
