Database Reference
In-Depth Information
2. DATA AND QUERY MODEL
We denote by
ADom(
D
)
the active domain of the database instance, i.e., the set of all constants
occurring in
D
.
Let
Q
be a (non-Boolean) query in the Relational Calculus, with head variables
x
. For each
¯
a
, its lineage is defined as the lineage of the Boolean query
Q
[
a/x
]
possible answer
.
The lineage
Q
is defined by induction on the query expression
Q
given by
Eq. (2.1)
. Notice
that
Q
is always a Boolean query
Q
. Thus, if the query is an equality predicate
u
=
v
, then
u
and
v
must be two constants: if they are the same constant, then query is
a
=
a
, and the lineage is defined
as
true
; if they are different constants, then the query is
a
=
b
and then the lineage is defined as
false
. If the query is
R(x)
, then all terms in
x
are constants; hence, the query is a ground tuple
t
: the
lineage is defined as
t
. Finally, if the query is one of the other expressions in
Eq. (2.1)
, then the
lineage is defined accordingly; this should be clear from
Eq. (2.4)
.
For a simple illustration of the lineage expression, consider the Boolean query
Q
=
Example 2.9
∃
x.
∃
y.R(x)
∧
S(x,y)
, and consider the following database instance with relations
R
and
S
:
S
AB
a
1
R
A
a
1
b
1
Y
1
X
1
a
1
b
2
Y
2
a
2
X
2
a
2
b
1
Y
3
We have associated a distinct Boolean variable with each tuple, in effect transforming standard
relations
R
and
S
into two c-tables.Then the lineage of
Q
is
Q
=
X
2
Y
3
. Intuitively,
the lineage says when
Q
is true on a subset of the database: namely,
Q
is true if either both tuples
X
1
and
Y
1
are present, when both tuples
X
1
and
Y
2
are present, or when both tuples
X
2
and
Y
3
are
present.
X
1
Y
1
∨
X
1
Y
2
∨
The lineage allows us to reduce the query evaluation problem to the problem of evaluating
the probability of a propositional formula. More precisely:
Proposition 2.10
Let Q( x) be a query with head variables
x, and let
D
be a pc-database. Then the
probability of a possible answer
a to Q is equal to the probability of the lineage formula:
P(a
∈
Q)
=
P(
Q
[
a/x
]
)