Extensional Query Evaluation - Probabilistic Databases - page 74

4. EXTENSIONAL QUERY EVALUATION
Conversely, if the condition above holds, then we can transform Q into a hierarchical ex-
pression by “pushing existential quantifiers” down, for example, rewriting ∃ x. ∃ y.R(x) ∧ S(x,y)

to y.S(x,y) . Notice that the hierarchy-condition is a syntactic condition, i.e., it de-

pends on the query expression. Given an arbitrary conjunctive query Q ,if Q is hierarchical then,
by definition, there exists an equivalent expression Q that is hierarchical. Minimize Q : this means
remove redundant atoms, until one obtains an equivalent query expression Q where no atom can
be further removed. Q also satisfies the hierarchy condition because it consists of a subset of the
atoms of Q , which satisfied the hierarchy condition. This observation gives us a simple syntactic test
for checking whether Q is hierarchical: minimize it first, then check the hierarchy condition. For
example, consider H 0 =

∃ x.R(x) ∧∃

R(x),S(x,y),T(y) . It is already minimized, and the hierarchy condition
fails because at (x) ={ R, S }

, at (y) ={ S,T } ; thus, H 0 is not hierarchical. For another example,

consider Q R(x),S(x,y),S(z,y) . The expression is not hierarchical, but the query minimizes to

R(x),S(x,y) , which is hierarchical.
Therefore, unlike general relational queries, for conjunctive queries, we have:

=

Lemma 4.28 CQ H,NR CQ H CQ NR = ∩

The proof follows immediately from the observation that both properties H and NR are
preserved under query minimization, and the minimal expression is unique up to isomorphism.

CQ NR . Let Q be a non-repeating conjunctive query, Q ∈

Theorem 4.29

[ Dalvi and Suciu , 2004 ]

Then one of the following holds:

￿If Q is hierarchical, then it is tractable and can be evaluated using two rules: independent-join,
and independent-project.

￿If Q is not hierarchical, then its data complexity is hard for # P .

CQ H,NR and therefore is tractable by Proposition 4.27 .If
Q is not hierarchical, then we prove hardness by reduction from H 0 , whose hardness we proved in
Theorem 3.2 . Consider a minimal expression for Q , and let R 1 ∈

Proof. If Q is hierarchical, then Q ∈

at (y) ,
T 1 ∈ at (y) − at (x) . Thus, the three atoms look like this: R 1 (...,x,...) , S 1 (...,x,...,y,...) , and
T 1 (...,y,...) . Consider any tuple-independent probabilistic database instance D for the query
H 0 = R(x),S(x,y),T(y) . Define the following tuple-independent probabilistic database instance
D 1 for Q . Each tuple R 1 (...,x,...) is derived from a tuple in R(x) by padding all extra attributes
with a fixed constant a ; similarly, each tuple S 1 (...,x,...,y,...) is derived from a tuple S(x,y) ,
and each tuple T 1 (...,y,...) is derived from T(y) : padding is always done with the same constant
a . The probabilities of the tuples in R 1 ,S 1 ,T 1 are the same as those in R, S, T . All relations other
than R 1 ,S 1 ,T 1 are filled with all possible tuples from the active domain of R 1 ,S 1 ,T 1 , and their
probabilities are 1 . 0. It is easy to see that the probability of Q on D 1 is equal to the probability of
H 0 on D .

at (x) − at (y) , S 1 ∈ at (x) ∩