We consider the problem of checking equivalence of conjunctive queries with inequalities under bag (multiset) semantics. The problem is known to be decidable in pspace and as hard as graph isomorphism, but its exact complexity remains open. We introduce a natural restriction based on what we call the symmetry degree of queries, and show that when the symmetry degree is bounded by a fixed polynomial in the size of the query, the equivalence problem is in Π2p. We also show that for asymmetric queries (those of symmetry degree 1), checking bag-equivalence is polynomial-time Turing equivalent to the graph automorphism problem. These results can be interpreted as first steps in a more general program of finding “islands of tractability” for testing equivalence of conjunctive queries with inequalities under bag (rather than set) semantics.
We study the problem of checking equivalence of conjunctive queries (CQs) with
built-in inequality predicates over a densely-ordered domain under bag (multiset)
semantics. This problem is well-understood assuming the classical set semantics,
where it is known that the complexity jumps from NP-complete for ordinary
CQs [
In this paper, we introduce a natural restriction on the structure of CQs called
bounded symmetry degree (a bound on the number of query automorphisms)
and use this notion to study the complexity of the bag equivalence problem.
The notion is adapted from the well-known concept of graph symmetry studied
extensively in the graph theory literature [
Outline. Section 2 contains preliminaries and a discussion of related work. Section 3 defines the notion of bounded symmetry degree, establishes some basic results, and compares it with bounded hypertree width. Section 4 presents the main results on equivalence, for bag and bag-set semantics. We conclude in Section 5. The Appendix contains formal proofs of our results. 2
Conjunctive queries with inequalities. Following the standard terminology [
Semantics of queries. We fix a densely-ordered domain of constants which, for concreteness, we will assume is that of the rationals Q. A set relation of arity k is a finite set R of tuples from Qk. A bag (multiset) relation of arity k is a mapping R : Qk → N of tuples to their associated multiplicities, where the mapping is non-zero on only finitely many tuples. A set (resp., bag) database instance I is an assignment of set (resp., bag) relations RI to predicate names R.
The semantics of CQ<s on set and bag relations is based on the notion of valuations. A valuation is mapping ν of variables to constants, extended to map constants to themselves. Valuations operate pointwise on lists/tuples and atoms in the expected way. Let Q be a CQ Q(t¯) :– R1(t¯1), . . . , Rn(t¯n), C and let I be a set instance. The result of evaluating Q on I under set semantics is the set relation JQKI defined
JQKI = {ν(t¯) | ν |= C and ν(t¯1) ∈ R1I ∧ · · · ∧ ν(t¯n) ∈ RnI} Now suppose I is a bag instance. The result of evaluating Q on I under bag semantics is the bag relation JQKbI defined
JQKbI (a¯) = X(R1I(ν(t¯1)) × · · · × RnI(ν(t¯n)))
ν where the sum is over all valuations ν such that ν(t¯) = a¯ and ν |= C. Finally, suppose I is a set instance. The result of evaluating Q on I under bag-set semantics is the bag relation JQKbIs obtained by viewing I as a (duplicate-free) bag relation, and evaluating Q on I under bag semantics.
A CQ< Q is satisfiable (or consistent [
An endomorphism (resp., automorphism) is a homomorphism (resp., isomorphism) from a CQ< to itself. For a CQ< Q, the set of automorphisms of QR, denoted by Aut(QR), forms a subgroup of the symmetric group on V (Q). The identity element in this group is the identity mapping. Similarly, the set of endomorphisms of QR, denoted by End(QR), forms a monoid.
Linearizations and linear expansions. We use the notions of linearizations and
linear expansions of CQ<s due to Nutt et al. [
If L is a linearization of C, and C is the condition of a CQ< Q, then we denote QL the CQ< obtained from Q by replacing C with L, and we say that QL is a linearization of Q. By default, we do not eliminate equalities in linearizations unless explicitly pointed out. (Thus, the condition for a linearization is a conjunction of inequalities of the form x θ t, θ ∈ {<, =}.) The linear expansion of Q is the bag lin(Q) of all linearizations of Q (it can be viewed as a union of CQ<s). We say that linear expansions lin(Q) and lin(Q′ ) are isomorphic if there is a bijection f : lin(Q) → lin(Q′ ) such that QL is isomorphic to f (QL) for every QL ∈ lin(Q).
Known results on equivalence. The equivalence problem for conjunctive queries
with or without inequalities under set semantics, bag semantics, bag-set
semantics have been studied extensively, beginning with the seminal paper by
Chandra and Merlin [
The papers by Chaudhuri and Vardi [
Checking bag-set equivalence of CQ<s was shown to be decidable by Nutt et
al. [
The following simple variation on an example given in [
Q() :– ϕ(x, y, z), x < z, y < z, x 6= y Q′ () :– ϕ(x, y, z), x < y, x < z, y 6= z The linear expansions of Q and Q′ are
Q1() :– ϕ(x, y, z), x < z, y < z, x > y Q2() :– ϕ(x, y, z), x < z, y < z, x < y Q′1() :– ϕ(x, y, z), x < y, x < z, y > z
Q′2() :– ϕ(x, y, z), x < y, x < z, y < z Observe that Q1 is isomorphic to Q′1 and Q2 is isomorphic to Q′2. By Theorem 1, Q and Q′ are bag-equivalent since they have isomorphic linear expansions. However, Q and Q′ are not isomorphic. 3 3.1
A CQ< is linear [
In this section, we introduce a generalization of this restriction based on
what we term the symmetry degree of a query. This is a natural idea derived
from the well-studied notion of the symmetry degree of a graph (see, e.g., [
Q1() :– P (x1, x2), P (x2, x3), . . . , P (xn−1, xn) Q2() :– S(u, v), S(u, w)
Q3() :– R(y1), . . . , R(yn) Q1 has symmetry degree 1 (the variables must all stay put), Q2 has symmetry degree 2 (v and w can be swapped), and Q3 has symmetry degree n! (any permutation of the variables is an automorphism).
We will examine the complexity of computing sym(Q) in Section 3.2. In the meantime, we derive an easy bound based on counting self-joins. Proposition 1. Suppose predicates p1, . . . , pk each occur n1, . . . , nk times, respectively, in the body of a CQ Q. Define the number of self-joins of Q to be n = n1 + · · · + nk − k. Then
k sym(Q) ≤ Y(ni!) ≤ (n + 1)!.
i=1 In particular, the proposition implies that linear queries have symmetry degree one. On the other hand, queries may have low symmetry degree but many selfjoins, e.g., Q1 in Example 2.
We introduce some additional terminology to use in the remainder of the paper. Q is called symmetric if Aut(QR) is a non-trivial subgroup of the symmetric group on V(Q), i.e. sym(Q) > 1. Q is called asymmetric if Aut(QR) is trivial, which only contains the identity, i.e. sym(Q) = 1. Q is called rigid if End(QR) is trivial.
Incidence graphs. A CQ has a natural interpretation as an edge-labeled directed
hypergraph. However, to apply results of interest from graph theory, we may
need to transform this hypergraph into an ordinary directed graph. Given a
CQ Q, we construct its incidence graph [
We next turn to the question of computing the symmetry degree of a CQ, starting with the simpler problem of deciding whether a query is symmetric. Not surprisingly, the latter problem reduces easily to the graph automorphism problem (GA), which is the problem of checking whether a given graph has a non-trivial automorphism.2 1 The automorphism group of a labeled directed graph G = (V, E, λ) is the subgroup of the automorphism group of G′ = (V, E) which respects the labeling λ. 2 As with GI, GA is in NP but not known or believed to be either NP-complete or in ptime. It is no harder than GI in the sense that the problem is polynomial-time many-one reducible to GI; however the converse relationship is at present unknown. Proposition 3. Checking whether a CQ< (CQ) is symmetric is polynomialtime many-one equivalent to the graph automorphism problem.
This leads, using results in [
Corollary 2 (of Theorem 15 in [
Finally, we consider testing for rigidity. Again our strategy is to reduce the
problem on CQ< queries to the analogous problem on graphs, where a result of
Goralcik et al. [
Gottlob et al. [
Symmetry degree and hypertree width seem to be essentially orthogonal concepts: intuitively, hypertree width is in some sense a measure of cyclicity, rather than symmetry. Moreover, a query with high symmetry degree may have small hypertree width, such as the following CQ that computes a “star self-join” on the first column of a relation R:
Q1() :– R(x, y1), R(x, y2), . . . , R(x, yk) Q1 has symmetry degree k! but is acyclic hence has hypertree width 1. At the same time, a query with a high hypertree width may have a small symmetry degree, such as the CQ below:
k k Q2() :– ^ ^ i=1 j=1,j6=i
Rik−k+j (xi, xj) (Q2 intuitively corresponds to a complete directed graph without self-loops on k vertices where each edge is labeled with a distinct predicate name.) Q2 has symmetry degree 1, but we can show that it has hypertree width ⌈ k/2⌉ .
We are not aware of any work studying the interaction of hypertree width and bag equivalence of queries. We also do not know of any work studying whether bounded hypertree width leads to tractable query containment or equivalence checks for CQ<s under the classical set semantics.
A recent paper by Pichler et al. [
We are now ready to present our results on the complexity of bag equivalence of CQ<s having bounded symmetry degree (Section 4.1). We also discuss how these bounds transfer to bag-set semantics (Section 4.2), and present an initial result that applies these ideas to the query equivalence problem under classical set semantics (Section 4.3). 4.1
As already mentioned, Nutt et al. [
Theorem 2. Checking bag equivalence of CQ<s of polynomially bounded symp metry degree is in coNPGI , hence in Π2 .
The proof of the theorem relies on the following technical lemma: Lemma 1. Let Q be a CQ< of polynomially bounded symmetry degree, and let QL be one of its linearizations. Then the number of linearizations in lin(Q) that are isomorphic to QL can be computed in polynomial time with access to a GI oracle.
Proof. The basic idea of the proof is as follows: first, we use the GI oracle to compute Aut(QR); second, we use Aut(QR) to compute the number of linearizations in lin(Q) that are isomorphic to QL.
To compute Aut(QR), we first compute the generating set of Aut(QR). This
can be done in polynomial time using the GI oracle, since it is well-known that
the problem of computing the generating set of the automorphism group of a
labeled graph is polynomial-time Turing equivalent to GI [
Next, let S denote the set of all linearizations in lin(Q) that are isomorphic to QL. Our goal is to compute |S|. We observe that a linearization QL′ ∈ S iff h(L) = L′ for some h ∈ Aut(QR) and L′ |= C, where C denotes the condition part of Q. In other words, S = {h(QL) | h ∈ Aut(QR) and h(L) |= C}. Since we have already computed Aut(QR), we can therefore use it to compute S in polynomial time, and return |S| as the final answer. ⊔ ⊓
Proof. By Lemma 1, given a GI oracle and a linearization QL of Q, we can compute in polynomial time the numbers of linearizations of Q and Q′ , respectively, which are isomorphic to QL. If these two numbers are different, then it follows by Theorem 1 that Q and Q′ are not bag-equivalent. Thus we can guess a nonmembership witness and verify it in polynomial time given a GI oracle, which means this problem is in coNPGI. Since GI≤pT NP, it follows that the problem is also in Π2p. ⊔ ⊓
We note that the pre-condition of Theorem 2 can certainly be checked in Π2p, by Corollary 1. Also, we note that it is not hard to show that Lemma 1 and Theorem 2 can be generalized to show a Π2p upper bound for checking bag equivalence of unions of CQ<s (UCQ<s). In Section 4.2, we will also generalize it to apply to bag-set equivalence.
Next we show some other (relatively) tractable subcases of checking bag equivalence of CQ<s. Here, we show that if the number of self-joins is bounded by some constant, we can push the upper bound down to coNP. Theorem 3. If the numbers of self-joins in CQ< Q, Q′ are bounded by some constant k, then the problem of checking whether Q and Q′ are bag equivalent is in coNP.
Proof. Here wlog we assume that Q and Q′ have the same relational part, since their relational parts are isomorphic by Theorem 1. As stated in Proposition 1, the symmetry degree is bounded by (k + 1)! and we can enumerate the automorphism group in constant time. For checking bag equivalence of Q and Q′ , we can guess a linearization QL. Initialize two sets SQ and SQ′ to be empty. By applying the automorphism to QL one by one and see if the comparison part is compatible with the comparison parts of Q and Q′ respectively and if yes add it to the corresponding SQ or SQ′ . This can be done in polynomial time. If the orders of these two sets are different, then Q and Q′ are not bag-equivalent, since they have different numbers of linearizations that are isomorphic to QL. In other words, we can guess a non-member witness and verify it in polynomial time. Hence, this problem is in coNP. ⊔ ⊓
By imposing various restrictions on the symmetry degree of queries, we can establish other upper bounds on the complexity of the problem. The following result is one example.
Theorem 4. Asymmetric CQ<s Q and Q′ are bag equivalent iff there is an
isomorphism h from Q′ R to QR such that h(C′ ) |==| C. Moreover, bag equivalence
of asymmetric CQ< queries is polynomial-time Turing equivalent to the graph
automorphism problem.
Proof. By Theorem 1, Q, Q′ have isomorphic linear expansions. In other words,
there is a bijective mapping ψ : lin(Q) 7→ lin(Q′ ) such that QL is isomorphic to
ψ(QL) for all QL ∈ lin(Q). Denote by ϕi the isomorphism mapping from QLi
to ψ(QLi). Since Q, Q′ are asymmetric, there is only one isomorphism mapping
from QR to Q′ R (Suppose there are two ϕ1, ϕ2, then ϕ1 ◦ ϕ−1 is a nontrivial
2
automorphism of QR, which is a contradiction). So, ϕi are all the same for any
QLi ∈ lin(Q). The isomorphism of Q and Q′ follows. The only problem is to
find out this only isomorphism mapping of their relational parts and check if
their comparisons are equivalent under this isomorphism. By [
Next we examine bag-set equivalence of CQ<s. Theorem 4 holds not just for bag semantics, but also for bag-set semantics. Let us now look at extending Theorem 2 as well.
We have the following lemma which is analogous to Lemma 1, but uses an NP (rather than GI) oracle. Intuitively, we use this extra power to deal with the fact that for bag-set semantics, when manipulating linearizations, we are forced to reduce equalities (since this can have the effect revealing that an atom in the body is actually a duplicate copy and should be removed).
Lemma 2. Let Q be a CQ< of polynomially bounded symmetry degree, and let QL be one of its linearizations (with equalities reduced). The number of the linearizations in lin(Q) that are isomorphic to QL can be computed in polynomial time with access to a NP oracle.
Using this lemma, we can establish the analog of Theorem 2 for bag-set semantics.
Theorem 5. Checking bag-set equivalence of CQ<s of polynomially bounded symmetry degree is in coNPNP = Π2p. 4.3
We have already seen in the preceding sections that bounded symmetry degree
makes bag (bag-set) equivalence problem of CQ< easier to tackle. We show in this
section a preliminary application of bounded symmetry to checking equivalence
under the classical set semantics. As mentioned earlier, Klug [
Theorem 6. Checking set equivalence of rigid CQ<s is polynomial-time Turing reducible to the graph automorphism problem.
We note that the equivalence results on bag semantics of CQ<s presented here
have wider applicability to any semantics in which CQ< equivalence is
characterized by isomorphism of linearizations. This includes, for example, equivalence of
CQ< on databases annotated with certain kinds of provenance information [
We conjecture that if only <, ≤ are allowed as inequalities, two CQ<s Q, Q′ are bag equivalent if and only if there is an isomorphism from Q′ R to QR under which the condition of Q′ is equivalent to that of Q.
One possible future direction involves applying bounded symmetry degree to
study query containment. Although the decidability of bag containment of CQs
remains a longstanding open problem (Chaudhuri and Vardi [
Finally, we would like to pin down the exact complexity of the general case of bag equivalence of CQ< queries, which seems stubborn to resolve. The problem is reminiscent to another open issue in the area, that of identifying the exact complexity of checking bag equivalence of positive relational algebra queries with inequalities. This class of queries is expressively equivalence to UCQ<, but exponentially more concise, and here again the known lower and upper bounds on the complexity are GI and pspace, respectively.
Acknowledgements. We thank the anonymous reviewers for their helpful comments. This work was supported by NSF CAREER award IIS-1055107.
Consider a satisfiable set C of inequalities, and denote by V (C) the set of variables and constants occurring in C. The transitive closure of C, denoted by C∗, is the conjunction of all inequalities over V (C) entailed by C. For example, if C = {x < y, y ≤ 2}, its transitive closure C∗ = {x < y, y ≤ 2, x < 2, x ≤ y, x ≤ 2, x 6= y, y 6= 2, x 6= 2}. (Notice that C |= x < 3, but x < 3 is not contained in C∗ since 3 does not occur in C.) The transitive closure of a set of inequalities can be computed in polynomial time.
Proposition 5. For sets C1 and C2 of inequalities, the following are equivalent: 1. C1 |==| C2, i.e. C1 |= C2 and C2 |= C1. 2. C1 and C2 have the same sets of linearizations. 3. C1 and C2 have the same transitive closures.
B
Proof. (of Proposition 3) One direction is clear as the graph automorphism
problem can be trivially reduced to the problem of checking symmetry of a Boolean
CQ Q with a single binary relation E such that E(x, y) and E(y, x) are both
subgoals in Q if vertices x and y are adjacent in graph G. In the other direction,
given a CQ Q, we construct its incidence graph G(Q). By Proposition 2, Q is
symmetric iff G(Q) is symmetric. G(Q) is a labeled graph, but it is easy to
verify that labeled graph automorphism is many-one reducible to (ordinary) graph
automorphism, which completes the proof. ⊔ ⊓
Proof. (of Corollary 1) The reductions used in Proposition 3 are parsimonious, so
computing the symmetry degree of a CQ< is polynomial-time many-one
equivalent to #GA3. By results in [
Proof. (of Lemma 2) We can find a homomorphism h from QR to QLR by using
this NP oracle. We can also enumerate all the automorphisms of Q by this NP
oracle in polynomial time since it has polynomial symmetry degree. Using similar
argument as in Lemma 1, by composing h by the elements in Aut(QR) one by
one and applying to L and then see if it is compatible with C, we can get the
number of the linearizations in lin(Q) that are isomorphic to QL. ⊔ ⊓
Proof. (of Theorem 5) Use the same argument as in Theorem 2, but instead of a
p
GI oracle, we use an NP oracle as Lemma 2 suggests. This yields a coNPNP = Π2
upper bound. ⊔ ⊓
Proof. (of Theorem 6) Assuming that two rigid queries Q and Q′ are set
equivalent, then there is only one homomorphism mapping ψ from Q′ R to QR and
only one homomorphism mapping ϕ from QR to Q′ R, i.e. QR and Q′ R are
homomorphically equivalent. But Q and Q′ are rigid, hence cores, and if two cores
are homomorphically equivalent then they are isomorphic. Since Q′ R and QR
are cores, ψ is a unique isomorphism from Q′ R to QR. Now the only problem
is to find out this unique isomorphism mapping, and check the conditions of
these queries are compatible under this mapping which is in polynomial time.
By [