Database Reference
In-Depth Information
2. DATA AND QUERY MODEL
For a simple illustration, consider the query
Q(x, z)
=∃
y.R(x,y)
∧
S(y,z)
. Given an in-
put instance
D
=
R
D
,S
D
, the query
Q
returns the set of pairs
(a, c)
for which there ex-
R
D
S
D
. This set is denoted by
Q(D)
. To make it concrete,
ists
b
s.t.
(a, b)
∈
and
(b, c)
∈
if
R
D
,
S
D
={
(a
1
,b
1
), (a
2
,b
2
), (a
2
,b
3
)
}
={
(b
2
,c
1
), (b
2
,c
2
), (b
2
,c
3
), (b
3
,c
3
)
}
, then
Q(D)
=
{
.
By convention, we restrict queries to be domain independent [
Abiteboul et al.
,
1995
]. In that
case, the semantics of a query coincides with the following
active domain semantics
.Let
ADom
be
the set of all constants occurring in all relation instances of the database
D
;wecallitthe
active
domain
of the database
D
. Under the active domain semantics, every quantifier
(a
2
,c
1
), (a
2
,c
2
), (a
2
,c
3
)
}
∃
x
in the query
Q
is
interpreted as ranging over the active domain
ADom(D)
, and the set of answers
a
is also restricted
¯
to the active domain.
A
Conjunctive Query
, or CQ, is a query constructed only using the first four production rules
of the grammar given by
Eq. (2.1)
.A
Union of Conjunctive Queries
, UCQ, is a query constructed
only using the first five grammar production rules. It is well known that every UCQ query can
be written equivalently as
Q
1
∨
Q
2
∨
...
where each
Q
i
is a conjunctive query, which justifies the
name
union of conjunctive queries
. Note that UCQ does not include queries with the predicate
u
=
v
:
this can be expressed as
¬
(u
=
v)
, but in UCQ, we do not have negation. Also, we do not consider
interpreted predicates, like
u<v
, as part of the query language: both
u
=
v
and
u<v
can be treated
as an uninterpreted relational predicate
R(u, v)
, in effect, forgetting any special properties that the
interpreted predicate has, but some of the necessary-and-sufficient results in
Chapter 4
no longer
hold in the presence of interpreted predicates.
An alternative syntax for RC is given by a
non-recursive datalog with negation
. In this language,
a query is defined by a sequence of
datalog rules
, each having the form:
S(
x)
¯
:−
L
1
,L
2
,...,L
k
where the atom
S(
x)
is called the
head
,
¯
x
are called the
head variables
, the expression
L
1
,L
2
,...,L
k
¯
is either a positive relational atom
R(x
i
)
or the negation of a
is called the
body
, and each atom
L
i
relational atom
x
i
)
. Each rule must be
domain independent
, meaning that every variable must
occur in at least one non-negated atom. The program is non-recursive if the rules can be ordered
such that each head symbol
S
does not occur in the body of the current rule or the bodies of the
previous rules.
We will freely switch back and forth between the two notations. For example, the query
Q(x, z)
above is written as follows in non-recursive datalog:
¬
R(
¯
Q(x, z)
:−
R(x,y),S(y,z)
