Database Reference
In-Depth Information
Properties of homomorphisms
Using homomorphisms is essential for establishing proper-
ties of conjunctive queries. We have already seen that containment of conjunctive queries
can be formulated in terms of the existence of homomorphisms between their tableaux.
Notice that tableaux are nothing but naıve tables with some distinguished variables.
Another important property concerns the interaction of homomorphisms with certain
answers. Suppose we have two instances
S
and
S
of the same schema, a homomorphism
h
:
S
S
, and a conjunctive query
Q
.Then
→
certain
(
Q
,
S
)
.
certain
(
Q
,
S
)
⊆
The reason for this is that conjunctive queries are
preserved
under homomorphisms. That
is, if
a
is a tuple of constants and
a
is in
Q
(
S
),then
a
also belongs to
Q
(
S
). Indeed, if
Q
is of the form
(
a
,
b
) is true in
S
for some tuple
b
that may contain both constants and nulls. But then by the definition of homomorphisms,
α
∃
y
α
(
x
,
y
),and
a
∈
Q
(
S
), it means that
α
(
a
,
h
(
b
)) is true in
Q
(
S
), implying
a
Q
(
S
).
This preservation property applies to unions of conjunctive queries as well, and will be
used in designing algorithms for query answering in data exchange.
∈
2.4 Complexity classes
For most computational tasks we encounter in the topic, we need to establish whether
they are solvable algorithmically and, if the answer is positive, what type of computa-
tional resources are required. The former, of course, is the
decidability
question for a given
problem; the latter is the question of its
computational complexity
. Complexity is typically
measured in terms of the membership of a problem in a complexity class, and, ideally,
completeness
for a complexity class. Completeness means that the problem is as hard as
any problem in a given class, which tells us that resources demanded by problems in that
class are really needed to solve the problem at hand.
Membership of a problem in a complexity class is established by providing an algorithm
that uses resources allowed by the complexity class. Resources are measured in terms
of either
time
or
space
required by the computation, as well as the type of computation
(deterministic or nondeterministic). Completeness (or undecidability) is established by
reducing from problems already known to be complete for the class.
We now provide basic information about the complexity classes we use, as well as the
prototypical complete problems to be used in reductions.
Definitions of complexity classes
The classes we consider are defined in terms of:
•
time or space requirements; that is, problems requiring
O
(
f
(
n
)) time or space, for a class
of functions
f
,and
•
deterministic or nondeterministic mode of computation.
