Figure 3a shows how these queries relate with respect to
parallel-correctness transfer. As an example, . Figure
3b illustrates that these relationships are completely orthogonal to query containment. Indeed, there are examples
where parallel-correctness transfer and query containment
coincide (Q3 vs. Q4), where they hold in opposite directions
(Q4 vs. Q2) and where one but not the other holds (Q3 vs. Q2
and Q1 vs. Q4, respectively).
Proposition 6. 4 allows us to pinpoint the complexity of
parallel-correctness transferability. For a formal statement
we define the following algorithmic problem:
When the defining condition of “covers” is spelled out by
rewriting “minimal valuations” one gets a characterization
with a Π3-structure. Again, it can be shown that this is essen-
tially optimal.
Theorem 6. 6. Problem pc-trans(CQ) is Πp 3-complete.
The upper bounds follow directly from the characterization in Proposition 6. 4. We note that the same complexity
bounds continue to hold in the presence of inequalities and
for unions of conjunctive queries.
2
The complexity of transferability is considerably better for
a restricted class of conjunctive queries that we call strongly
minimal.
Definition 6. 7. A CQ query is strongly minimal if all its
valuations are minimal.
Strong minimality generalizes two particularly simple
classes of queries:
Lemma 6. 8. A CQ Q is strongly minimal
• if it is a full query;
• if it contains no self-joins (every relation name occurs at
most once).
Theorem 6. 9. pc-trans(CQ) restricted to inputs (Q, Q′), where
Q is strongly minimal, is NP-complete.
7. CONCLUSION
Parallel-correctness serves as a framework for studying correctness and implications of data partitioning in the context
of one-round query evaluation algorithms. A main insight of
the work up to now is that testing for parallel-correctness as
pc-trans (CQ)
Input: Queries Q and Q′ from CQ
Question: Does parallel-correctness transfer from
Q to Q′?
R(x, y), T(y)
R(x,x),T(x) S(x),R(x,y),T(y)
S(x), R(x, x), T(x)
pc
pc
pc
pc
pc
(a)
(b)
R(x, y), T(y)
R(x,x),T(x) S(x),R(x,y),T(y)
S(x), R(x, x), T(x)
⊆
⊆
⊆
⊆
⊆
Figure 3. Relationship between the queries of Example 6. 5 with respect
to (a) parallel-correctness transfer (pc) and (b) query containment (⊆).
Figure 2. Global instances I = {R( 1, 1), R( 1, 3), R( 3, 1)} (left and middle) and I′ = {R( 1, 3), R( 3, 1)} (right) are represented by graphs. Solid edges
(facts) are located at node κ1, dashed edges at node κ2; colored edges are required by the valuation under concern. Instance I has globally and
locally satisfying valuations for query Q, subinstance I′ ⊆ I has a globally satisfying valuation but no locally satisfying one—under the same
distribution policy. There is thus a policy under which Q is parallel-correct but Q′ is not, and therefore parallel-correctness does not transfer
from Q to Q′. (a) Valuation V satisfies Q globally on I but not locally. It is not minimal for Q. (b) Valuation V satisfies Q globally on I and locally
on κ1. It is minimal for Q and derives the same fact as V. (c) Valuation V satisfies Q′ globally on I′ but not locally. It is minimal for Q′. It does not
satisfy Q.
V = {d1 ;
1,d2 ;
1,d3 ;
3}
1
3 R(d1, d2)
R(d1, d3)
R(d3, d2)
(a)
V = {d1;
1, d2;
1, d3;
1}
13
R(d1, d3)
R(d1, d2)
R(d3, d2)
(b)
V = {d1 ;
1, d2 ;
1, d3 ;
3}
13
R(d1, d3)
R(d3, d2)
(c)
