Adding datatypes to ontology-mediated conjunctive queries (OMQs) often makes query answering hard. This applies, in particular, to datatypes with non-unary predicates. In this paper we propose a new, nonuniform way, of analysing the data-complexity of OMQ answering with datatypes containing higher-arity predicates. We aim at a classi cation of the patterns of datatype atoms in OMQs into those that can occur in nontractable OMQs and those that only occur in tractable OMQs. Our main result is a P/coNP-dichotomy for OMQs over DL-Lite TBoxes and rooted CQs using the datatype (Q; ). The proof employs a recent dichotomy result by Bodirsky and Kara for temporal constraint satisfaction problems.
In recent years, querying data using ontologies has become one of the main
applications of description logics (DLs). The general idea is that an ontology
is used to enrich incomplete and heterogeous data with a semantics and with
background knowledge, thus serving as an interface for querying data and allowing
to derive additional facts. In this area called ontology-based data management
(OBDM) one of the main research problems is to identify ontology languages
and queries for which query answering scales to large amounts of data [
The aim of this paper is to revisit OBDM with expressive datatypes from a new, non-uniform, perspective. Instead of the standard approach that aims at the de nition of DLs L and query languages Q such that for any TBox T in L and any query q in Q, answering q under T is tractable in data-complexity we now aim at describing the complexity of query answering with datatypes at a more ne-grained level by taking into account the way in which datatype atoms can occur in queries. In more detail, an ontology-mediated query (OMQ) Q is a triple Q = (T ; q; D) consisting of a TBox T 1, a CQ q, and a datatype D (that we identify with a relational structure (D; R1; : : :)). The TBox T in Q can refer to the datatype D using existential restrictions 9U where U is an attribute. The CQ q can contain atoms using attributes and relations Ri from D. We aim at a classi cation of the data complexity of query answering with OMQs (T ; q; D) based on the datatype pattern dtype(q) of q that consists of all atoms using the relations in D. To illustrate, the CQ q uses the datatype D = (Q; ) and asks for all rectangles whose width is larger than its height: q(x) rectangle(x) ^ height(x; u) ^ width(x; v) ^ u v: Thus, height and width are attributes and the datatype pattern dtype(q) of q is u v. The following CQ q0 uses (Q; ) as well and asks for all countries having a neigbour to the west that is larger and a neighbour to the east that is smaller: q0(x) country(x) ^ westneighbour(x; y1) ^ eastneighbour(x; y2) ^ area(x; u) ^ area(y1; u1) ^ area(y2; u2) ^ (u u1) ^ (u2
u): Its datatype pattern dtype(q0) is (u u1) ^ (u2 u).
Our main results assume that either the CQ q is a rooted CQ (a CQ in which each variable is connected to an answer variable not in dtype(q)) or that the chase of the TBox under consideration is nite for all ABoxes. Under this assumption, we rst show a close link between the complexity of query evaluation for OMQs with datatype D and the evaluation problem for positive existential sentences in the structure D in which every relation R has been replaced by its complement (thus, D = (Q; >) if D = (Q; )). In more detail, we show that evaluating an OMQ with datatype D and a datatype pattern with at most k atoms is polynomially reducible to the complement of the problem PEk(D) of evaluating positive existential formulas in k-CNF in D. Conversely, PEk(D) is polynomially reducible to the complement of evaluating a single xed OMQ (depending only on k) with datatype D and a datatype pattern with nk atoms, where n is the number of relations in D.
Basic complexity results can be obtained easily from this observation. For example, from the fact that PE1(D) is tractable for D 2 f(Z; <); (Z; ); (Q; <); (Q; )g, we obtain that evaluating OMQs (T ; q; D) in which q is a rooted CQ whose datatype pattern is a singleton is tractable. Conversely, from the fact that PE2(Q; >) is non-tractable we obtain an intractable OMQ (T ; q; D) with datatype D = (Q; ) and a rooted CQ q whose datatype pattern consists of two atoms.
Our main result is a P/coNP-dichotomy for OMQs using the datatype D = (Q; ). Namely, we show that for any datatype pattern q0 over (Q; ) exactly one of the following two conditions holds (unless P=coNP): 1 The results presented in this paper do not depend on the particular tractable DL we extend with datatypes. To prove the lower bounds we require that the TBox is given in a DL containing DL-Litecore; the upper bounds can be proved for all standard Horn-DLs for which CQ evaluation is in PTime. { Evaluating rooted OMQs (T ; q; D) with dtype(q) = q0 is in PTime. { There exists a rooted OMQ (T ; q; D) with dtype(q) = q0 whose evaluation problem is coNP-hard.
The proof uses a recent dichotomy result by Bodirsky and Kara for temporal
constraint satisfaction problems [
Due to space limitations, some proofs had to be deferred to the full version of this paper, which is available on the authors' websites.
Related Work Expressive DLs with datatypes (or concrete domains) have been
introduced in [
A datatype is a tuple D = (D; R1; R2; : : : ), where D is a non-empty set and R1; R2; : : : are relations on D. We call dom(D) := D the domain of D. To simplify the presentation, we will not distinguish between a relation Ri and its name (i.e., we use Ri both as a relation and as the name of the relation Ri). The complement of D, denoted by D, is obtained by replacing each k-ary relation Ri in D by its complement Ri := Dk n Ri. For example, we have (Q; ) = (Q; >).
We assume countably in nite and mutually disjoint sets of concept names, role
names, attribute names, and individual names. Concept names will typically be
denoted by A, role names by P , attribute names by U , and individual names by
a; b; c. The logic DL-Litecore and Horn DLs such as Horn-ALCHIQ are de ned as
usual [
Let D be a datatype. A D-ABox consists of assertions of the form A(a), P (a; b), and U (a; u), where A is a concept name, P is a role name, U is an attribute name, a; b are individual names, and u 2 dom(D). A D-knowledge base (D-KB) is a pair (T ; A) consisting of a TBox T and a D-ABox A.
An interpretation I = ( I ; I ) over a datatype D consists of a non-empty domain I = iInd [dom(D) and an interpretation function I that assigns to each concept name A a set AI iInd, to each role name P a relation P I iInd iInd, and to each attribute name U a relation U I iInd dom(D). The elements in ind are called individuals, whereas the elements in dom(D) are called data values.
I We assume that iInd and dom(D) are disjoint. Throughout this paper, we make the standard name assumption: if I is an interpretation, then we set aI := a for all individual names a. We also set uI := u for each u 2 dom(D), and RI := R for each relation R of D. The interpretation I induces the interpretations CI and SI for each complex concept C and complex role S in the standard way.
We say that I is a model of a KB (T ; A) if aI 2 AI , (aI ; bI ) 2 P I , and (aI ; uI ) 2 U I for all assertions A(a), P (a; b), and U (a; u) in A, and if for every inclusion X v Y in T we have XI Y I . A KB (T ; A) is satis able if it has a model; in this case we say that A is satis able relative to T .
We consider conjunctive queries (CQs) q (over D) of the form q(x) ', where x is the tuple of answer variables of q, and ' is a conjunction of atomic formulas of the form A(y), P (y; z), U (y; u), or R(u1; : : : ; uk), where A, P , U , and R range over concept names, role names, attribute names, and relation names in D, respectively; each y; z is a variable; and each u; u1; : : : ; uk is a variable. As usual, all variables of x must occur in some atom of '. The size jqj of q is the number of atoms in q. The datatype pattern of q, denoted by dtype(q), is the conjunction of all atoms in ' that use a relation in D. The variables that occur in dtype(q) are called data variables. We assume that all data variables occur in some atom U ( ; ) outside of dtype(q). A match of q in an interpretation I is a mapping from the variables of ' to I such that for each atom X(t1; : : : ; tk) of ' we have ( (t1); : : : ; (tk)) 2 XI . A tuple c of individual names and data values is an answer to q in an interpretation I if there is a match of q in I such that (x) = c. We denote this by I j= q(c). Given a KB (T ; A), we write T ; A j= q(c) if c is an answer to q in every model of (T ; A).
The connection graph of a CQ q is the undirected graph with the variables of q as its vertices and an edge between any two distinct variables if they occur together in an atom of q that does not belong to dtype(q). We say that q is rooted if for every variable y of q the connection graph contains a path from y to an answer variable of q.
We consider ontology-mediated queries (OMQs) of the form Q = (T ; q; D), where D is a datatype, T is a TBox, and q is a CQ over D. Given a D-ABox A and a tuple c, we write A j= Q(c) if (T ; A) j= q(c). An OMQ Q = (T ; q; D) is rooted if q is rooted. The query evaluation problem for Q is the problem to decide for given D-ABox A and c whether A j= Q(c). 3
We establish a tight link between the OMQ evaluation problem with datatype D and the satisfaction problem for positive existential sentences over D. To this end we rst introduce a variant of the universal (or canonical) model for standard Horn-DL KBs. In contrast to KBs with Horn-DL TBoxes without datatypes, in general there does not exist a universal model for KBs with datatypes. Example 1. Consider the KB (T ; A) with T = fA v 9U1; A v 9U2g and A = fA(a)g and with datatype (Q; ). Consider the OMQs Qi = (T ; qi; (Q; )), i = 1; 2, where q1(x)
U1(x; u1) ^ U2(x; u2) ^ u1 u2 q2(x)
U1(x; u1) ^ U2(x; u2) ^ u2 u1 Clearly A 6j= Q1(a) since for the interpretation I with U1I = f(a; 2)g and U2I = f(a; 1)g we have I 6j= q1(a). Also, A 6j= Q2(a) since for the interpretation J with U1J = f(a; 1)g and U2J = f(a; 2)g we have J 6j= q2(a). However, there does not exist a model I of T and A such that I 6j= qi(a) for both i = 1 and i = 2. The reason that universal models do not exist is that distinct interpretations of attributes can be required to refute the entailment of CQs. The notion of pre-interpretation formalizes this intuition: it xes the interpretation of concept and roles names but leaves the interpretation of attributes open by adding placeholders for data values (called data nulls) to the set of possible values of attributes. A pre-interpretation J over D is the same as an interpretation over D with the exception that attribute names U are now interpreted as sets U J iJnd (dom(D) [ nJull), where nJull is a set of data nulls disjoint from iJnd [ dom(D). The de nitions of the interpretations CJ of a concept C and SJ of a role S are extended from interpretations to pre-interpretations in the obvious way. A pre-model of a KB is a pre-interpretation that satis es all assertions and inclusions in the KB.
Pre-interpretations J can be completed to interpretations by assigning data values to data nulls. A completion function f for J is a mapping f : nJull ! dom(D). The completion f (J ) of J by f is the interpretation I obtained from J by setting AI = AJ for all concept names A, P I = P J for all role names P , and U I = (U J \ ( iJnd dom(D))) [ f(d; f (v)) j (d; v) 2 U J ; v 2 nJullg for all attribute names U . An interpretation I is called a completion of J if there exists a completion function f for J such that f (J ) = I.
Using a straightforward modi cation of the standard chase procedure for
Horn-DLs (see, e.g., [
f (can(T ; A)) j= q(c) for all completion functions f .
We call can(T ; A) with this property a universal pre-model of T and A. Lemma 1. For every satisfable D-KB (T ; A) there exists a universal pre-model can(T ; A).
Example 2. A universal pre-model can(T ; A) for the KB (T ; A) given in Example 1 is given by setting can(T ;A) = fa; u1; u2g; Acan(T ;A) = fag; U1can(T ;A) = f(a; u1)g; and U can(T ;A) = f(a; u2)g.
2
A completion function f for can(T ; A) maps u1 and u2 to rational numbers and de nes a completion f (can(T ; A)) in which U1 is interpreted as (a; f (u1)) and U2 is interpreted as (a; f (u2)). The universal pre-model can(T ; A) can be in nite. If we are given a rooted OMQ Q = (T ; q; D), then it is su cient to consider the subinterpretation cann(T ; A) of can(T ; A) induced by the set of domain elements that are reachable from ABox elements in at most n = jqj steps. We call cann(T ; A) a n-universal pre-model of T and A. As Q is rooted, it has the following property for any c:
f (cann(T ; A)) j= q(c) for all completion functions f .
A straightforward modi cation of the standard chase shows that an n-universal
pre-model cann(T ; A) can be computed in polynomial time in the size of A [
A positive existential sentence over a datatype D is a rst-order sentence built from atomic formulas over the relations in D by using solely conjunction, disjunction and existential quanti ers. Atomic formulas can use both individual variables and constants from D. is in Conjunctive Normal Form (CNF) if it has the form
m = 9x ^ ci; i=1 where ci = ni _ ci;j for i = 1; : : : m j=1 where ci;j are atomic formulas. If ni = k, for each i, then we say that is in k-CNF. The problem of deciding whether a positive existential sentence in k-CNF is satis ed in D is denoted PEk(D). We now show that we have a polynomial time reduction from evaluating OMQs over D to the complement of the problem PEk(D) and vice versa.
Theorem 1. Let k > 0 and let D = (D; R1; : : : ; Rn) be a datatype.
Let Q = (T ; q; D) be a rooted OMQ and assume that dtype(q) has k atoms. Then evaluating Q is polynomially reducible to the complement of PEk(D).
Conversely, there is a rooted OMQ Q = (T ; q; D) such that dtype(q) has nk atoms and PEk(D) is polynomially reducible to the complement of evaluating Q. Proof. Assume q is given as q(x) '. Let A be an ABox satis able relative to T and let c be a tuple of individual names and data values in A of the same length as x. Remove from ' the datatype pattern of q and denote by the remaining atoms in '. A match of in a pre-interpretation I is a mapping from the variables in to I such that for each atom X(t1; : : : ; tk) in we have ( (t1); : : : ; (tk)) 2 XI . Consider the set X of all matches of with (x) = c in cann(T ; A), where n = jqj. Now assume that dtype(q) = Vik=1 Si(zi) and let := 9u ^ k _ Si( (zi)); 2X i=1 where u is a repetition-free enumeration of all data nulls in the set f (zi) j 2 X; 1 i kg (here we identify data nulls with individual variables in the k-CNF ). It is readily checked that T ; A j= q(c) if, and only if, D 6j= . This establishes the rst part.
Conversely, assume = 9x Vim=1 ci, where ci = Wjk=1 ci;j for 1 i m. We rst assume that is uniform, that is, for each 1 j k there exists a relation Sj (independent from i) such that ci;j is of the form Sj (ti;j ). In this case we can construct the required OMQ (T ; q; D) with jdtype(q)j = k. The TBox T is independent from k and de ned as T = fA v 9U g. Assume that the relations Sj are of arity lj and ci;j = Sj (ti;j ) for all 1 i m. Before de ning the CQ q we de ne an ABox A as follows: { { A uses individuals c and c1; : : : ; cm that are connected by a role name P using the assertions P (c ; ci) for 1 i m; { in addition A uses individuals ci;j which are connected to the individuals ci by role names P1; : : : ; Pk using the assertions Pj (ci; ci;j ) for 1 i m and 1 j k; { in addition A uses individuals dt for each variable and constant t in that are connected to the ci;j using role names N1j ; : : : ; Nljj for 1 j k and the assertions Nrj (ci;j ; dt) if the r-th component of ti;j equals t;
nally A contains A(dt) if t is a variable in and U (dt; t) if t is a constant in .
De ne the query q(x)
, by setting k = P (x; y)^ ^
lj
Pj (y; yj )^ ^ j=1
r=1 It is not di cult to show that D j=
if, and only if, T ; A 6j= q(c ). For 0 = 9x19x2 (R1(1; x1) _ R2(x2; x1)) ^ (R1(x1; x2) _ R2(x2; 2)) the ABox A and query q are shown in Figure 1.
Nrj (yj ; zj;r)^U (zj;r; uj;r) ^Sj (uj;1; : : : ; uj;lj ) c11 d1 1
c1 P1
P2 N11
N21 U
A dx1
P N22 c12 N11 c
P
N21 c21 N12
P1
P2 c2
N12 dx2
c22 N22 U d2 2 z11 u11 y1 N11
P P1 y
N21 z12 u12 R1 x
N12 z21 P2 y2
N22 u21
R2 z22 u22
It remains to consider the case in which is not uniform. We may assume that Ri 6= ; for all 1 i n. We equivalently transform into a uniform sentence in nk-CNF over D. To this end, each conjunct ci of into a conjunct c0i of the form is equivalently transformed We construct R1(ti1;j ) for a xed i and 1 j k. The remaining atoms are constructed in the same way. ci contains between 0 and k disjuncts of the form R1(t). Thus, if ci contains at least one disjunct of this form we take su ciently many copies to obtain R1(ti1;1)_: : : ; _R1(ti1;k) that is equivalent to the disjunction over all atoms of the form R1(t) in ci. If ci does not contain any R1(t), then take c with c 2 R1 and let ti1;1 = = ti1;k = c. Then R1(ti1;1) _ : : : _ R1(ti1;k) is unsatis able, as required.
We illustrate Theorem 1 by transfering some complexity results from temporal CSP over (Q; <) to OMQs. Recall that we are after a complexity classi cation. The following result shows that answering OMQs with datatype (Q; ) can be intractable already for datatype patterns of size two.
Corollary 1. There is a rooted OMQ Q = (T ; q; (Q; )) with T = fA v 9U g and jdtype(q)j = 2 such that evaluating Q is coNP-hard.
Proof. The BETWEENNESS problem in temporal constraints satisfaction is the
problem to decide whether := 9u V(x;y;z)2C (x < y < z _ z < y < x) is
satis able in (Q; <), where C is a set of triples of the form (x; y; z). This problem
is NP-complete [
(x < y _ z < y) ^ (x < y _ y < x) ^ (y < z _ z < y) ^ (y < z _ y < x): 9u
^ (x;y;z)2C The claim now follows from Theorem 1.
This is optimal as shown by the following result.
Corollary 2. Let D 2 f(Z; <); (Z; ); (Q; <); (Q; )g. Then evaluating rooted OMQs Q = (T ; q; D) with jdtype(q)j = 1 is in PTime.
Proof. Follows from Theorem 1 and the observation that satis ability of sentences in 1-CNF in D is decidable in PTime. tu 4
)
In this section, we focus on rooted OMQs that use the datatype (Q; ). We prove
a P/coNP-dichotomy of evaluating such OMQs based on their datatype pattern,
and provide a simple syntactic characterization of the datatype patterns of rooted
OMQs with datatype (Q; ) for which the evaluation problem can be solved
in polynomial time (Theorem 4). These results are based on a recent dichtomy
result by Bodirsky and Kara [
We start by reviewing the temporal constraint satisfaction framework of [
Bodirsky and Kara [
We now translate the evaluation problem for rooted OMQs over (Q; ) into the temporal constraint satisfaction framework. With every datatype pattern q0(z1; : : : ; zn) = Vik=1 zsi zti we associate the temporal constraint language q0 := (Q; <; Rq0 ) where Rq0 := f(c1; : : : ; cn) 2 Qn j (Q; <) j= Wik=1 cti < csi g: Theorem 3. Let q0(z1; : : : ; zn) = Vik=1 zsi zti be a datatype pattern.
If Q = (T ; q; (Q; )) is a rooted OMQ with dtype(q) = q0, then evaluating Q is polynomially reducible to the complement of CSP( q0 ).
Conversely, there is a rooted OMQ Q = (T ; q; (Q; )) with dtype(q) = q0 such that CSP( q0 ) is polynomially reducible to the complement of evaluating Q. Proof (Sketch). We re ne the proof of Theorem 1. For the rst part, we construct the positive existential sentence as in the proof of Theorem 1, and then express each disjunctive clause by a single Rq0 -atom. The result is a primitive positive sentence 0 over q0 . Note that q0 may still contain constants. To obtain a primitive positive sentence without constants, we turn each constant in 0 into an existentially quanti ed variable and add constraints that ensure that the order of the elements assigned to these variables corresponds to the order of the constants. More precisely, let c1 < < cl be the constants in 0. Then, = 9c1 9cl 0 ^ Vli=11 ci < ci+1 : It can be shown that q0 j= i q0 j= 0.
For the second part, we rst translate a given primitive positive sentence over q0 into a positive existential sentence over (Q; >). Atoms using the relation Rq0 are replaced by disjunctive formulas expressing the predicate de ning the relation Rq0 . Atoms using < are expanded into disjunctions with k atoms. The resulting sentence is in k-CNF. The second part of the theorem now follows from the construction in the proof of Theorem 1. tu
Since < is preserved under min, mi , mx , ll and their duals, but not under any constant function, Theorem 2 implies that CSP( q0 ) is in PTime i Rq0 is preserved under min, mi , mx , ll or one of their duals. Together with Theorem 3, we obtain the following corollary.
Corollary 3. Let q0 be a datatype pattern. If Rq0 is preserved under min, mi , mx , ll , or one of their duals, then evaluating rooted OMQs (T ; q; (Q; )) with dtype(q) = q0 is in PTime. Otherwise, there is a rooted OMQ Q = (T ; q; (Q; )) with dtype(q) = q0 such that evaluating Q is coNP-complete.
To illustrate, consider the datatype pattern q0(x; y; z) = x y ^ y z. It is straightforward to verify that Rq0 = f(a; b; c) 2 Q3 j a > b _ b > cg is not preserved under min, mi , mx , ll or their duals, so there are OMQs (T ; q; (Q; )) with dtype(q) = q0 for which the evaluation problem is coNP-complete. On the other hand, if q0 has the form Vin=1 x0 xi or Vin=1 xi x0, then it follows from [8, Proposition 3.5] that Rq0 is preserved under ll or its dual. In particular, evaluation of OMQs (T ; q; (Q; )) with dtype(q) = q0 is in PTime. In fact, we will now show that these two forms of datatype patterns, which we call min-pattern and max-pattern, respectively, essentially characterize all the tractable cases.
The following lemma is the core of the characterization result. It implies that preservation under min, mi , mx or their duals collapses to preservation under ll or its dual for relations that are de nable by normal disjunctive formulas. By a disjunctive formula we mean a disjunction of atoms of the form x < y. A disjunctive formula (x1; : : : ; xn) is normal if the directed graph with vertex set fx1; : : : ; xng and edge set f(xj; xi) j xi < xj 2 g is acyclic.
Lemma 3. Let R Qn be de ned by a normal disjunctive formula (x1; : : : ; xn) over (Q; <). If R is preserved under min, mi , mx , ll , or one of their duals, then has the form Win=1 x0 > xi or Win=1 xi > x0.
In particular, [8, Proposition 3.5] implies that a relation de ned by a formula of the form Wn i=1 xi > x0 is preserved under ll or its dual.
i=1 x0 > xi or Vn
We apply the lemma to relations Rq0 for acyclic datatype patterns q0. A datatype pattern q0 is acyclic if the directed graph with the variables of q0 as vertices and an edge (x; y) for each atom x y of q0 is acyclic. Since a cycle x0 x1 ^ x1 x2 ^ ^ xn x0 tells us that x0; x1; : : : ; xn have to be mapped to the same data value, we can eliminate any cycle by removing all of its atoms, and replacing x1; : : : ; xn by x0. Let q0acyclic be the acyclic datatype pattern obtained from a datatype pattern q0 by eliminating all of its cycles.
Theorem 4. Let q0 be a datatype pattern over (Q; ). If q0acyclic is a min-pattern or a max-pattern, then evaluating rooted OMQs (T ; q; (Q; )) with dtype(q) = q0 is in PTime. Otherwise, there is a rooted OMQ Q = (T ; q; (Q; )) with dtype(q) = q0 such that evaluating Q is coNP-complete.
Proof. To simplify the presentation, we assume without loss of generality that q0 is acyclic. By Corollary 3, it su ces to show that q0 is a min-pattern or a max-pattern i Rq0 is preserved under min, mi , mx , ll , or one of their duals.
If q0 is a min-pattern, then Rq0 is de ned by a formula of the form Wn i=1 x0 > xi. Similarly, if q0 is a max-pattern, then Rq0 is de ned by a formula of the form Wn
i=1 xi > x0. It is known [8, Proposition 3.5] that relations de ned by such formulas are preserved under ll and dual-ll , respectively.
Now suppose that Rq0 is preserved under min, mi , mx , ll , or one of their duals. Let q0(z1; : : : ; zn) = Vik=1 zsi
zti . Then, Rq0 is de ned by (z1; : : : ; zn) = Wik=1 zti < zsi . Clearly, is disjunctive, and since q0 is acyclic it is also normal. Thus, Lemma 3 implies that has the form Win=1 x0 > xi or Win=1 xi > x0. This implies that q0 is a min-pattern or a max-pattern.
Note that the fact that qacyclic is neither a min-pattern nor a max-pattern 0 does not imply that evaluation is hard for all OMQs Q = (T ; q; (Q; )) with dtype(q) = q0. For example, q0acyclic may have several connected components, each a min-pattern or a max-pattern. If no component is connected to another one via a path of existential variables in q one can show that evaluating Q is in PTime. tu 5
We have presented rst promising results for a non-uniform complexity analysis
of ontology-mediated queries with expressive datatypes. Many research questions
arise within this framework, including the following: (1) It remains an interesting
open problem whether our results generalize to non-rooted OMQs. Such OMQs
can \look" arbitrarily deep into a universal pre-model. We suspect that a nite
portion of a universal pre-model su ces, but this is far from obvious. (2) The
TBoxes we consider have very limited expressive power regarding datatypes
and it would be of interest to generalize our method to TBoxes that admit
more constructors using datatypes. (3) In this paper, we have used datatype
patterns within CQs to classify the complexity of OMQs. It would be of interest
to complement and extend this approach with classi cations based on TBoxes,
OMQs, or extended patterns in CQs that take into account additional atoms
not using datatype relations. (4) In addition to the PTime/coNP dichotomy
considered above, it would be of interest to investigate FO-rewritability and
Datalog-rewritability of OMQs as well [