Introduction

The problem we are concerned with in this paper originated from the observation that the NPD FactPages ontology 4 , used for testing ontology-based data access (OBDA) in industry [13,12], contained covering axioms of the form A B 1 • • • B n . It has been known since Schaerf's paper [18] that answering ontology-mediated queries (OMQs) with a covering axiom can be CONP-hard for data complexity, and so such OMQs are not suitable for OBDA systems in general. In fact, two interesting OMQs with covering can be extracted from [18]: Q 1 = (Cov , q 1 ) and Q 2 = (Cov , q 2 ), where Cov = { F T } and the Boolean conjunctive queries (CQs) q 1 and q 2 are shown below.

q 1 F T S R T T F F P1 P2 N1 N2 R q 2

Schaerf pointed out that answering these queries involves case analysis and showed that Q 2 is CONP-hard for data complexity. It is readily seen that Q 1 is NL-complete. The problem we started attacking in [9] was to find a complete syntactic or semantic classification of OMQs with covering according to their data complexity. The direct attack failed, and connections with other hard classification problems such as boundedness or linearisability of datalog programs (to be discussed in Section 3) indicate that a longer siege is needed. In this paper, we report on our recent findings.

We consider four ontologies with covering: Cov as above, Cov A = {A F T }, Cov ⊥ = { F T, F T ⊥}, Cov ⊥ A = {A F T, F T ⊥}, and we classify connected Boolean CQs q by the number of solitary occurrences of F and T in them, where a solitary F is any F (x) ∈ q with T (x) / ∈ q, and symmetrically for T . We prove a number of new syntactic and semantic sufficient and necessary conditions for such OMQs with at most one solitary F to be in the complexity classes AC 0 and NL, and to be L-, NL-or P-hard. We also give two new examples of very simple CONPcomplete OMQs.

Preliminaries

In this paper, a Boolean conjunctive query (CQ) is any first-order (FO) sentence of the form q = ∃x ϕ(x), where ϕ is a conjunction of unary or binary atoms P (y) with y ⊆ x. We often regard CQs as sets of their atoms, depict them as labelled digraphs, and assume that all of our CQs are connected. By answering an ontology-mediated query (OMQ) Q = (T , q) with a TBox T of the form defined above, we understand the problem of checking, given an ABox A (a finite set of unary or binary ground atoms), whether q holds in every model of T ∪ A, or T , A |= q in symbols. For every Q, this problem is clearly in CONP. It is in the complexity class AC 0 if there is an FO-sentence q , called an FO-rewriting of Q, such that T , A |= q iff A |= q , for any ABox A.

A datalog program, Π, is a finite set of rules ∀x

(γ 0 ← γ 1 ∧ • • • ∧ γ m ),

where each γ i is an atom Q(y) with y ⊆ x. (As usual, we omit ∀x.) The atom γ 0 is the head of the rule, and γ 1 , . . . , γ m its body. All the variables in the head must occur in the body. The predicates in the head of rules are IDB predicates, the rest EDB predicates [1].

A datalog query is a pair (Π, G), where Π is a datalog program and G an 0-ary atom, the goal. The answer to (Π, G) over an ABox A is 'yes' if G holds in the FOstructure obtained by closing A under Π, in which case we write Π, A |= G. A datalog query (Π, G) is a datalog rewriting of an OMQ Q = (T , q) in case T , A |= q iff Π, A |= G, for any ABox A. The answering problem for (Π, G)-i.e., checking, given an ABox A, whether Π, A |= G-is clearly in P. Answering a datalog query with a linear program, whose rules have at most one IDB predicate in the body, can be done in NL. The NL upper bound also holds for datalog queries with a linear-stratified program defined as follows. A stratified program [1] is a sequence Π = (Π 0 , . . . , Π n ) of datalog programs, called the strata of Π, such that each predicate in Π can occur in the head of a rule only in one stratum Π i and can occur in the body of a rule only in strata Π j with j ≥ i. If, additionally, the body of each rule in Π contains at most one occurrence of a head predicate from the same stratum, Π is called linear-stratified. Every linearstratified program can be converted to an equivalent linear datalog program [2].

Connections in High Places

We begin by putting our little problem into the context of more general investigations of (i) boundedness and linearisability of datalog programs and (ii) the data complexity of answering OMQs with expressive ontologies.

The decision problem whether a given datalog program is bounded has been a hot research topic in database theory since the late 1980s. Thus, it was shown that boundedness is undecidable already for linear datalog programs with binary IDB predicates [20] and single rule programs (aka sirups) [15]. On the other hand, deciding boundedness is 2EXPTIME-complete for monadic datalog programs [7,4] and PSPACE-complete for linear monadic programs [7]; for linear sirups, it is even NP-complete [20].

The last two results are relevant for deciding FO-rewritability of OMQs (Cov A , q), where q has a single solitary F and is called a 1-CQ. Indeed, suppose that F (x) and T (y 1 ), . . . , T (y n ) are all the solitary occurrences of F and T in q. Let Π q be a monadic datalog program with three rules G ← F (x), q , P (y 1 ), . . . , P (y n ),

(1) P (x) ← T (x),

(2) P (x) ← A(x), q , P (y 1 ), . . . , P (y n ),

where q = q \ {F (x), T (y 1 ), . . . , T (y n )} and P is a fresh predicate symbol that never occurs in our ABoxes. Then, for any ABox A, we have Cov A , A |= q iff Π q , A |= G. Thus, FO-rewritability of (Cov A , q) is clearly related to boundedness of the sirup (3). The problem of linearising datalog programs, that is, transforming them into equivalent linear datalog programs, which are known to be in NL for data complexity, has also attracted much attention [16,17,21,2] after the Ullman and van Gelder pioneering paper [19].

The success of the OBDA paradigm spurred considerable interest in the data complexity of answering individual OMQs with expressive ontologies. Thus, by establishing a remarkable connection to CSPs, it was shown in [5] that deciding FO-rewritability and datalog rewritability of OMQs with a SHIU ontology and a (Boolean) atomic query is NEXPTIME-complete. This result is obviously applicable to (Cov A , q) with a tree-shaped q. In [8], it was shown that checking rewritability of Boolean monadic disjunctive datalog programs into FO and monadic datalog can be done in, respectively, 2NEXPTIME and 3EXPTIME, which is applicable to all of our OMQs (Cov A , q). An AC 0 /NL/P trichotomy for the data complexity of answering OMQs with an EL ontology and atomic query, which can be checked in EXPTIME, was established in [14]. This result is applicable to OMQs (Cov A , q), in which q is an F -tree having a single solitary F (x) such that the binary atoms in q form a ditree with root x. Indeed, denote by T Q the EL TBox with concept inclusions F C q G , T P and A C q P , where C q is an EL-concept representing q \ {F (x)} with P for T (so for q of the form

F x F T y1 y2 T y3 R1 R2 R3 C q = ∃R 1 .(F P ∃R 2 .∃R 3 .P )). Then, for any ABox A that does not contain G , we have Π Q , A |= G iff T Q , A |= ∃x G (x).

Yet, despite all of these efforts and results (implying, in view of the recent positive solution to the Feder-Vardi conjecture [6,22], that there is a P/CONP dichotomy for OMQs with a SHIU ontology and a (Boolean) atomic query, which is decidable in NEXPTIME), we are still lacking simple and transparent, in particular syntactic, conditions guaranteeing this or that data complexity or type of rewritability. Some results in this direction were obtained in [10,11]. That a transparent classification of monadic sirups according to their data complexity has not been found so far and the close connection to CSPs indicate that this problem is extremely hard in general. Our aim below is to demonstrate that, for the OMQs with covering considered in this paper, syntactic conditions do exist but are difficult to find.

As observed in [9], if an OMQ Q (of the form defined above) is in AC 0 , then q is an FO-rewriting of Q. By a 0-CQ we mean any CQ that does not contain a solitary F . A twin in a CQ q is any pair F (x), T (x) ∈ q. Here is an encouraging syntactic criterion of FO-rewritability for OMQs of the form (Cov ⊥ A , q): Theorem 1. (i) If q is a 0-CQ, then answering both (Cov ⊥ A , q) and (Cov A , q) is in AC 0 , with q being an FO-rewriting of these OMQs.

(ii) If q is not a 0-CQ and does not contain twins, then answering both (Cov ⊥ , q) and (Cov , q) is L-hard.

Proof. (i) follows from [9, Theorem 1]. (ii)

The proof is by reduction to the reachability problem for undirected graphs, which is known to be L-complete; see, e.g., [3]. Denote by q the CQ obtained from q by gluing together all the variables x with F (x) ∈ q and also all the variables y with T (y) ∈ q. Thus, q contains a single Fatom, F (x), and a single T -atom, T (y). Clearly, there is a homomorphism h : q → q . Let q = q \ {F (x), T (y)}.

Suppose we are given an undirected graph G = (V, E) and two vertices s, t ∈ V . We regard G as a directed graph such that (u, v) ∈ E iff (v, u) ∈ E, for any u, v ∈ V . Now, we encode G by means of an ABox A G that is obtained from G as follows. For every edge e = (u, v) ∈ E, let q e be the set of atoms in q with x renamed to u, y to v and all other variables z to z e . Then A G comprises all such q e , for e ∈ E, as well as F (s) and T (t). We show that s

→ G t iff Cov , A G |= q.

Suppose that s → G t, i.e., there exists a path s = v 0 , . . . , v n = t in G with e i = (v i , v i+1 ) ∈ E, for i < n. Consider an arbitrary model I of Cov and A G . Since I |= Cov , and F (s) and T (t) are in A G , we can find some i < n such that I |= F (v i ) and I |= T (v i+1 ). As q ei is an isomorphic copy of q , we obtain I |= q , and so I |= q. Conversely, suppose s → G t. Define an interpretation I, extending the ABox A G , by setting F I to be the set of objects in A G that are reachable from s and T I its complement. Clearly, I is a model of Cov . By the construction, the elements of the connected component of I containing s cannot be instances of T , while the remaining elements of I are not be instances of F . Since q is connected, it follows that I |= q.

Corollary 1. An OMQ (Cov ⊥

A , q) is in AC 0 iff q is a 0-CQ, which can be decided in linear time.

If twins can occur in CQs (that is, F and T are not necessarily disjoint), the picture becomes more complex. On one hand, we have the following criterion for OMQs (Cov A , q) with a path CQ q whose variables x 0 , . . . , x n in q are ordered so that the binary atoms in q form a chain R 1 (x 0 , x 1 ), . . . , R n (x n−1 , x n ).

Theorem 2 ([9]

). An OMQ (Cov A , q) with a path CQ q is in AC 0 iff q is a 0-CQ. If q contains both solitary F and T , then (Cov A , q) is NL-hard.

On the other hand, this AC 0 /NL criterion collapses for path CQs with loops:

Proposition 1. The OMQ (Cov A , q), where q is shown below, is in AC 0 . F T R T F F T S R R S S

Proof. Follows from the sufficient condition of Theorem 4 (i).

Note that the CQ q above is minimal (not equivalent to any of its proper sub-CQs). Note also that, if a minimal 1-CQ q contains both a solitary F and a solitary T , then FO-rewritability of (Cov A , q) implies that q contains at least one twin (F T ) and at least one y with T (y) / ∈ q and F (y) / ∈ q (which can be shown using Theorem 4 (i)).

1-CQs

1-CQs have exactly one solitary F . As observed in Section 3, we have the following:

Theorem 3. (i) Answering any OMQ (Cov A , q) with a 1-CQ q can be done in P.

(ii) Answering any OMQ (Cov A , q) with an F -tree q is either in AC 0 or NLcomplete or P-complete. The trichotomy can be decided in EXPTIME.

Theorem 3 (ii) was proved by a reduction to the AC 0 /NL/P-trichotomy of [14]. It is to be noted, however, that applying the algorithm from [14] in our case is tricky because the input ontology T Q must first be converted to a normal form. As a result, we do not obtain transparent syntactic criteria on the shape of q that would guarantee that the OMQ (Cov A , q) belongs to the desired complexity class (see examples below).

We now give a semantic sufficient condition for an OMQ with a 1-CQ to lie in NL. This condition uses ideas and constructions from [7,14]. Let Q = (Cov A , q) be an OMQ with a 1-CQ q having a solitary F (x). Define by induction a class K Q of ABoxes that will be called cactuses for Q. We start by setting K Q := {q}, regarding q as an ABox, and then recursively apply to K Q the following two rules:

(bud) if T (y) ∈ A ∈ K Q with solitary T (y), then we add to K Q the ABox obtained by replacing T (y) in A with (q \ F (x)) ∪ {A(x)}, in which x is renamed to y and all of the other variables are given fresh names; (prune) if Cov A , A |= Q, where A = A \ {T (y)} and T (y) is solitary, we add to K Q the ABox obtained by removing T (y) from A ∈ K Q .

It is readily seen that, for any ABox A , we have

Cov A , A |= Q iff there exist A ∈ K Q and a homomorphism h : A → A . Denote by K † Q the set of minimal cactuses in K Q (that have no proper sub-cactuses in K Q ).

For a cactus C ∈ K Q , we refer to the copies of (maximal subsets of) q that comprise C as segments. The skeleton C s of C is the ditree whose nodes are the segments s of C and edges (s, s ) mean that s was attached to s by budding. The atoms T (y) ∈ s are called the buds of s. The rank r(s) of s is defined by induction: if s is a leaf, then r(s) = 0; for non-leaf s, we compute the maximal rank m of its children and then set

r(s) = m + 1, if s has ≥ 2 children of rank m; m, otherwise.

The width of C and C s is the rank of the root in C s . We say that K † Q is of width k if it contains a cactus of width k but no cactus of greater width. The depth of C and C s is the number of edges in the longest branch in C s .

We illustrate the definition by an example. Denote by q T nT , for n ≥ 0, the 1-CQ shown below, where all the binary predicates are R and the n variables without labels do not occur in F -or T -atoms:

F T T n . . . Example 1. Let Q = (Cov , q T 1T ).

In the picture below, we show a cactus C obtained by applying (bud) twice to q T 1T (with A = omitted):

F T z T T T

One can check that Cov , C \ {T (z)} |= q T 1T , and so an application of (prune) will remove T (z) from C. Using this observation, one can show that K † Q is of width 1. On the other hand, if Q = (Cov A , q T 1T ) then K † Q is of unbounded width as follows from Theorem 6 below. Theorem 4. Let Q = (Cov A , q) be an OMQ with a 1-CQ q. Then (i) Q is in AC 0 iff for every C ∈ K † Q , there is a homomorphism h : q → C; (ii) Q is rewritable in linear datalog, and so is in

NL, if K † Q is of bounded width.

Proof. The proof of (i) is straightforward. To prove (ii), we represent the ABoxes in K Q as words in a tree alphabet and construct a non-deterministic finite tree automaton

A Q such that K † Q ⊆ L(A Q ) ⊆ K Q .

Then we show that, for K † Q of finite width, the automaton A Q can be transformed into a monadic linear-stratified datalog rewriting of Q. It can further be converted into a linear datalog rewriting at the expense of increasing the arity if IDBs in the program [2].

It is worth noting that, for Q = (Cov , q) with q from Proposition 1, K † Q consists of q and the cactus of depth 1, in which the only solitary T is removed by (prune). Clearly, there is a homomorphism from q into this cactus, and so Q is FO-rewritable. However, for the 1-CQ q in the picture below (where all edges are bidirectional), (Cov , q) is not FO-rewritable, but there is a homomorphism from q to both cactuses of depth 1. We do not know whether, in general, there is an upper bound N q such that the existence of homomorphisms h : q → C, for all C ∈ K Q of depth N q , would ensure FO-rewritability of (Cov A , q). For 1-CQs q with a single solitary T , one can take N q = |q| + 1. Neither do we know the exact complexity of deciding FO-rewritability of OMQs with 1-CQs.

As mentioned in Section 3, this problem is reducible to the boundedness problem for monadic datalog programs, which is known to be in 2EXPTIME.

T F T F T T F T F T F S S S R Q R Q S R, Q R, Q S S R Q R Q R S R, Q R, Q S

Theorem 4 (ii) allows us to obtain a sufficient condition for linear-datalog rewritability of OMQs (Cov A , q) with an F -path CQ q, that is, a path CQ with a single solitary F at its root. We represent such a q as shown in the picture below, which indicates all the solitary occurrences of F and T :

q = F x T y 1 T y i T y m y m+1 . . . . . . . . . . . .

We require the following sub-CQs of q:

q i is the suffix of q that starts at y i , but without T (y i ), for 1 ≤ i ≤ m; -q * i is the prefix of q that ends at y i , but without F (x) and T (y i ), for

1 ≤ i ≤ m; -q * m+1 is q without F (x),

and write f i : q i q if f i is a homomorphism from q i into q with f i (y i ) = x.

Theorem 5. If for each 1 ≤ i ≤ m there exist f i : q i q, then (Cov A , q) is rewritable into a linear datalog program, and so is NL-complete.

For F -path CQs q without twins, we extend Theorem 5 to a NL/P dichotomy (provided that NL = P). Given such a CQ q, we denote by N q the set of the numbers indicating the length of the path from x to each of the y i , i = 1, . . . , m + 1. Theorem 6. Let Q = (Cov A , q) be an OMQ where q is an F -path CQ without twins having a single binary relation. The following are equivalent unless NL = P:

(i) Q is NL-complete;

(ii) {0} ∪ N q is an arithmetic progression; (iii) there exist f i : q i q for every i = 1, . . . , m.

If these conditions do not hold, then Q is P-complete.

Proof. It is readily seen, using Theorem 5, that (ii) ⇒ (iii) ⇒ (i). We prove the implication (i) ⇒ (ii). Suppose {0} ∪ N q is not an arithmetic progression. We show that Q is P-hard by reduction of the monotone circuit evaluation problem. Let X be the sub-CQ of q between F (x) and the first T but without the

∧-gate for |Y | > |X| c A A a T T a A T A b T T b A X X X Y Z X X Y Z X Y Z ∧-gate for |X| > |Y | A c T A b A a X X Y Z ∨-gate c T T a A T T b A X X Y Z X X Y Z

Given any monotone Boolean circuit C and its input α, we construct an ABox A C,α by replacing ∧and ∨-gates with the inputs a and b and output c by the gadgets above, placing T on the input gates evaluated to 1 under α and F on the output gate. We claim that Cov

A , A C,α |= q iff C(α) = 1.

(⇐) It is not hard to show by induction that whenever a non-input gate g in C outputs 1 under α, then the sub-ABox of A C,α generated by g and with F placed on g validates Q. For example, suppose T (a), T (b) and F (c) hold in the left-hand side gadget. Then either F (b ) or T (b ). In the former case, q is satisfied; so assume T (b ). We have either F (a ) or T (a ). Now, in either case, q is satisfied, as required.

(⇒) Suppose C(α) = 0. We construct a model I of Cov A based on A C,α by placing T or F to g and g (if available) depending on the value of g in C under α. It can be checked that I |= q. In particular, if |Y | > |X|, c is the conjunction of b and a, c = b = 0 and a = 1, then if x 0 goes to c, x 1 goes to a , then x 2 must go to the point below a , and so x 3 must go somewhere between a and the point above a, which is impossible. If a = 0, b = 1 and x 0 goes to a and x 1 goes to the central T , then x 2 must go somewhere between the central T and b , which is also impossible.

If |Y | < |X|, c = b ∧ a, b = d ∨ e, a = c = 0, b = 1, then if x 0 goes to c, x2

goes to b, then x 3 cannot go to a as a = 0, and so it must go into some X-segment of the gate b = d ∨ e going out of b, which is again impossible.

Note that the proof of P-hardness in Theorem 6 does not go through for A = . Thus, for (Cov , q T 1T ), we are in the framework of Example 1 and, by Theorem 4 (ii), this OMQ is in NL. In fact, we have the following NL/P dichotomy for the OMQs of the form (Cov , q T nT ).

Theorem 7. (i) The OMQ (Cov , q T 1T ) is NL-complete (whereas (Cov A , q T 1T ) is P-complete).

(ii) The OMQs (Cov , q T nT ) (and (Cov A , q T nT )), for n ≥ 2, are P-complete.

Proof. The proof is similar to that of P-hardness in Theorem 6.

We now apply Theorem 4 (ii) to the class of T F -path CQs of the form q T F = where the T (y i ) and F (x) are all the solitary occurrences of T and F in q T F . We represent this CQ as q T F = {T (y 0 )} ∪ q 0 ∪ q, where q 0 is the sub-CQ of q T F between y 0 and x with T (y 0 ) removed and q is the same as in Theorem 5 (and q * m+1 is q without F (x)).

Theorem 8. If q satisfies the condition of Theorem 5 and there is a homomorphism h : q * m+1 → q 0 such that h(x) = y 0 , then answering (Cov A , q T F ) is NL-complete.

For example, the OMQ (Cov A , q) with q shown below is NL-complete:

T F T F T

On the other hand, as shown in [9], (Cov A , q) with q of the form T F T is P-complete; in fact, it follows from the proof that (Cov , q) is P-complete, too.

2-CQs

A 2-CQ has at least two solitary F and at least two solitary T . For example, as shown in [9], answering (Cov A , q) with the following CQ q is CONP-complete:

T T F F

The proof can be generalised to the class of 2-2-CQs, which are path 2-CQs where all the F are located after all the T , and every occurrence of T or F is solitary. We represent any given 2-2-CQ q as shown below

T x T y F z F w p r s u v

where p, r, u and v do not contain F and T , while s may contain solitary occurrences of both T and F (in other words, the T shown in the picture are the first two occurrences of T in q and the F are the last two occurrences of F in q). Denote by q r the suffix of q that starts from x but without T (x); similarly, q u is the suffix of q starting from z but without F (z). Denote by q − r the prefix of q that ends at y but without T (y); similarly, q − u is the prefix of q ending at w but without F (w). Using the construction from [9], one can show the following: Theorem 9. Any OMQ (Cov A , q) with a 2-2-CQ q is CONP-complete provided the following conditions are satisfied: (i) there is no homomorphism h 1 : q u → q r with h 1 (z) = x, and (ii) there is no homomorphism h 2 : q − r → q − u with h 2 (y) = w. Unfortunately, the proof does not generalise to the other two path 2-CQs with four variables, whose complexity has so far been open:

q 1 T F T F q 2 T F F T Theorem 10. The OMQs Q 1 = (Cov A , q 1 ) and Q 2 = (Cov A , q 2 ) are CONP-complete.

Proof. We prove CONP-hardness of Q 1 by reduction of the NP-complete 3SAT. Given a 3CNF ψ, we construct an ABox A ψ as follows. First, for every variable p occurring in ψ, we take the following p-gadget, where n is the number of clauses in ψ: The key property of the p-gadget is that, for any model I of Cov A based on this gadget, if I |= q 1 then either the A-points on left-hand side of the gadget are all in T I and the A-points on the right-hand side are all in F I , or the other way round. We refer to the a i and b i as p ↑and ¬p ↑ -contacts, and to the c i and d i as p ↓and ¬p ↓ -contacts, respectively. Now, for every clause c = (l 1 ∨ l 2 ∨ l 3 ) in ψ, we add to the constructed gadgets for the variables in ψ the atoms R

(u c ¬l1 , v c l2 ), R(v c l2 , c), T (c), R(c, w c l3 ), where c is a new individual, u c ¬l1 a fresh ¬l ↑ 1 -contact, v c l2 a fresh l ↓2

-contact, and w c l3 a fresh l ↓ 3 -contact. For example, for the clause c = (p ∨ q ∨ ¬r), we obtain the fragment below:

A bi A cj T c A dk A A A A A A ¬p q ¬r The resulting ABox A ψ is such that ψ is satisfiable iff Cov A , A ψ |= q 1 .

For the OMQ Q 2 , we use (simplified) p-gadgets presented in Theorem 11 and connect them similarly to the picture above with T replaced by F at c.

We now sketch two generalisation of Theorem 10.

In Theorem 11 and 12, we assume that p and v do not contain F and T , while r and u may only contain solitary occurrences of T (F ∈ r, u), and s only solitary occurrences of F (T ∈ s).

Theorem 11. Any OMQ (Cov A , q) with q of the form is CONP-complete provided the following conditions are satisfied: (i) there is no homomorphism h 1 : r t → u with h 1 (y) = w, and (ii) there is no homomorphism h 2 : u t → r with h 2 (z) = x, where r is the sub-CQ of q between x and y without T (x), F (y), and similarly for u, r t is r with T (x) and u t is u with T (w).

The proof uses the following p-gadget: In Theorem 12, we use r ext = r(x, y) ∧ T (y) ∧ s 1 (y, y 1 ) ∧ F (y 1 ), where s 1 is the part of s such that s(y, z) = s 1 (y, y 1 ) ∧ F (y 1 ) ∧ s 2 (y 1 , z) and s 1 (y, y 1 ) does not contain any occurrences of F . In other words, the variable y 1 corresponds to the first appearance of F in s, where s is the sub-CQ of q between y and z without F (y), T (z).

Theorem 12. Any OMQ (Cov A , q) with q of the form is CONP-complete provided the following conditions hold: (i) there is no homomorphism g 1 : r t → u with g 1 (y) = w, and (ii) there is no homomorphism g 2 : u → r ext with g 2 (z) = x and g 2 (w) = y 1 .

The CQ below does not satisfy (ii), and its complexity is unknown:

T x T F y F F T z T T F w

It is also unknown whether there are OMQs with 2CQs in P.