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 ] )
 
Search WWH ::




Custom Search