Database Reference
In-Depth Information
that is, disjunction, negation, and universal quantification are not allowed. Hence, they are
queries of the form
y
α
1
(
z
1
)
∧
α
m
(
z
m
)
,
ϕ
(
x
)=
∃
∧
...
(2.2)
where:
•
each
α
i
is an atomic relational formula, i.e., a formula of the form
U
(
z
i
),where
U
is a
relation symbol, and
•
z
i
is a tuple of variables and constants, with all the variables coming from
x
and
y
.
For example, the query
(2.1)
is a conjunctive query.
Conjunctive queries can be translated into the fragment of relational algebra that con-
tains only the operations of projection (
). One
sometimes refers to this fragment as select-project-join queries. Conversely, every query in
the
{
π
,
σ
,×}
-fragment of relational algebra is a conjunctive query.
Conjunctive queries also correspond to the basic fragment of SQL, namely to queries
of the form
SELECT-FROM-WHERE
,inwhichthe
WHERE
clause contains a conjunction of
equalities.
A related class we consider consists of
unions of conjunctive queries
. As the name sug-
gests, these are queries of the form
Q
1
∪···∪
Q
m
, where all the
Q
i
's are conjunctive queries.
In other words, they are the queries expressible in the
π
), selection (
σ
), and Cartesian product (
×
-fragment of relational
algebra. Since these are queries without the difference operation, they are also sometimes
referred to as queries in the positive fragment of relational algebra. From the calculus
perspective, they can be expressed in the
{
π
,
σ
,
×
,
∪}
{∃
,
∧
,
∨}
-fragment of FO (i.e., no negation, no
universal quantification).
There are several important properties of conjunctive queries and their unions that we
shall use throughout the topic. One of them is monotonicity. If
Q
is a conjunctive query, or
a union of conjunctive queries, then
S
⇒
Q
(
S
)
.
S
⊆
Q
(
S
)
⊆
Another useful property is that containment and equivalence of conjunctive queries are
decidable. We say that a query
Q
is
contained
in a query
Q
, written as
Q
Q
,if
Q
(
S
)
⊆
⊆
Q
(
S
) for every instance
S
. Queries are equivalent if
Q
(
S
)=
Q
(
S
) for every instance.
To explain why containment is decidable for conjunctive queries, we introduce key no-
tions of
tableaux
and their
homomorphisms
. These notions will be central for us in the
topic.
Suppose we have a conjunctive query of the form
(2.2)
.Its
tableau
is a pair (
T
ϕ
,
x
),
where
T
ϕ
α
i
(
z
i
). For example,
for the conjunctive query in
(2.1)
, the tableau will contain two facts:
ROUTES
(
y
,
x
,
z
) and
ROUTES
(
y
,
z
,
x
).
Given two tableaux (
T
,
x
) and (
T
,
x
),a
homomorphism
between them is a map
h
:
D
OM
(
T
)
is a relational database containing essentially the atoms
D
OM
(
T
) satisfying two conditions:
→
