Database Reference
In-Depth Information
Fixed point logics can be embedded into a logic which uses infinitary connec-
tives but has a restriction that every formula mentions finitely many variables.
•
Counting logics
that are important for database theory. For example [
41
], in SQL
one can write a query that finds all pairs of managers
x
and
y
whohavethe
same number of people reporting to them (Reports_To relation stores pairs
(x,y)
where
x
is an employee and
y
is his/her immediate manager):
Select
R
1
.manager,
R
2
.manager
from Reports_To
R
1
, Reports_To
R
2
where (select count (Reports_To.employee)
from Reports_To
where Reports_To.manager
=
R
1
.manager)
=
(select count (Reports_To.employee)
from Reports_To
where Reports_To.manager
=
R
2
.manager)
In general, we add mechanisms for counting, such as counting terms, counting
quantifiers, or certain generalized quantifiers. Usually with this counting power,
these extended languages remain local, as FOL. We can apply these results in
the database setting, by considering a standard feature of many query-languages,
namely aggregate functions.
Interesting extensions of FOL by a number of second-order features are
monadic
second-order quantifiers (MSO). Such quantifiers can range over particular
subsets
of the universe (in monadic extensions, we can use the quantification
∃
X
where
X
is a subset of the universe, differently from FOL where
X
is an element of the
universe). We can consider two particular restrictions:
1. An
∃
MSO formula starts with a sequence of existential second-order quantifiers,
which is followed by an FOL formula.
2. An
MSO formula starts with a sequence of universal second-order quantifiers,
which is followed by an FOL formula.
For example,
∀
∃
MSO and
∀
MSO are different for graphs. For strings MSO collapses
to
MSO and captures exactly the
regular languages
[
6
]. If we restrict attention to
FOL over strings then it captures exactly the star-free languages.
MSO can be used over
trees
(if we view the XML documents as trees, such
queries choose certain nodes from trees) and tree automata, for example, for
monadic DATALOG. Furthermore, monadic DATALOG can be evaluated in time
linear both in the size of the program and the size of the string [
27
].
∃
1.4
Basic Database Concepts
The database mappings, for a given logical language (we assume the FOL language
in Definition
1
), are usually defined at a schema level as follows:
•
A
database schema
is a pair
(S
A
,Σ
A
)
where
S
A
is a countable set of
relational symbols (predicates in FOL)
r
A
=
∈ R
with finite arity
n
=
ar(r)
≥
1
(
ar
:R→
N
), disjoint from a countable infinite set
att
of attributes (a domain
of
a
∈
att
is a nonempty finite subset
dom(a)
of a countable set of individual
symbols
dom
, with
U
=
dom
∪
SK
). For any
r
∈R
, the sort of
r
, denoted by tu-
