Database Reference
In-Depth Information
Remark
First of all, we will use the FOL extended by a number of binary
built-in
predicates
, necessary for composition of queries, as
.
=
=
,<
, etc., that can be used
for compositions of database queries, without using logical negation operator
,
¬
.
.
=
.
=
For example,
¬
(x
y)
will be expressed by
x
=
y
,
x
≤
y
by
(x < y)
∨
(x
y)
,
.
=
¬
y)
by
x>y
, etc. These built-in predicates
have the equal prefixed extension for a given FOL domain
(x > y)
by
(x < y)
∨
(x
y)
,
¬
(x
≤
U
, so do not depend on a
particular Tarski's interpretation
I
T
in Definition
1
.
.
=
formally for FOL formulae, while infor-
mally we will use the common symbol for equality
Notice that we will use the symbol
=
in all other metalanguage
cases.
First-order logic (FOL) corresponds to relational calculus, existential second-
order logic (
SOL: they start with existential second-order quantifiers, followed by a
first-order formula) to the complexity class NP [
18
] (existential second-order quan-
tifiers correspond to the guessing stage of an NP algorithm, and the remaining first-
order formula corresponds to the polynomial time verification of an NP algorithm),
and second-order logic with quantifiers ranging over sets (of positions) describes
regular languages, as
(aa)
∃
∗
, for example. It can be shown that the transitive closure
in the database theory is not expressible in FOL. Such inexpressibility results have
traditionally been a core theme of the finite model theory [
17
,
28
,
76
].
Let us consider the reachability query: can we get from
x
to
y
for a given binary
relation
r
, by considering the following list of queries:
z
r(x,z
1
)
r(z
1
,y)
,
q
0
(x,y)
=
r(x,y), q
1
(x,y)
=∃
∧
...
z
1
...z
n
r(x,z
1
)
r(z
n
,y)
,
q
n
(x,y)
=∃
∧
r(z
1
,z
2
)
∧···∧
that is, one wants to compute the transitive closure of
R
. The problem with this is
that we do not know in advance what
n
is supposed to be. So the query that we need
to write is
q
n
n
∈
N
where
is the set of natural numbers. But it is not an FOL formula. The inability
of FOL to express some important queries motivated a lot of research on extensions
of FOL that can do queries such as transitive closure or cardinality comparisons (as
in SQL that can count). Such extensions, for example,
•
N
Fixed point logics
(fragment of second-order logic). We can extend FOL to
express properties that algorithmically require recursion. Such extensions have
fixed point operators as the least, inflationary, and partial fixed point operators.
The resulting fixed point logics, in the presence of a linear order, capture
complexity classes PTIME (for least and inflationary fixed points) and PSPACE
(for partial fixed points). A well-known database query language that adds fixed
points in FOL is DATALOG. By adding the transitive closure to FOL, over order
structures, it captures nondeterministic logarithmic space.
