Introduction The OWL 2 QL ontology language [11], based upon the description logic DL-LiteR, is considered particularly well suited for applications involving large amounts of data. While the data complexity of querying OWL 2 QL knowledge bases is well understood, far less is known about combined complexity of conjunctive query (CQ) answering for restricted classes of conjunctive queries. By contrast, the combined complexity of CQ answering in the relational setting has been thoroughly investigated. In relational databases, it is well known that CQ answering is NP-complete in the general case. A seminal result by Yannakakis established the tractability of answering tree-shaped (aka acyclic) CQs [14], and this result was later extended to wider classes of queries, most notably to bounded treewidth CQs [5]. Gottlob et al. [6] pinpointed the precise complexity of answering tree-shaped and bounded treewidth CQs, showing both problems to be complete for the class LOGCFL of all languages logspace-reducible to context-free languages [13]. In the presence of arbitrary OWL 2 QL ontologies, the NP upper bound for arbitrary CQs continues to hold [4], but answering tree-shaped queries becomes NP-hard [8]. Interestingly, the latter problem was recently proven tractable in [3] for DL-Litecore (a slightly less expressive logic than OWL 2 QL), raising the hope that other restrictions might also yield tractability. This extended abstract summarizes our investigation [2] into the combined complexity of conjunctive query answering in OWL 2 QL for tree-shaped queries, their restriction to linear and bounded leaf queries and their generalization to bounded treewidth queries. Our complexity analysis reveals that all query-ontology combinations that have not already been shown NP-hard are in fact tractable. Specifically, in the case of bounded depth ontologies, we prove membership in LOGCFL for bounded treewidth queries (generalizing the result in [6]) and membership in NL for bounded leaf queries. We also show LOGCFL-completeness for linear and bounded leaf queries in the presence of arbitrary OWL 2 QL ontologies. This last result is the most interesting technically, as the upper and lower bounds rely on two different characterizations of the class LOGCFL. Preliminaries We assume the reader familiar is OWL 2 QL (or DL-LiteR) knowledge bases (KBs), composed of a TBox T and ABox A built from countably infinite, mutually disjoint sets NC, NR, and NI of concept names, role names, and individual names. Roles R and basic concepts B are defined in a standard way, cf. [4]. We use NR to refer to the set of all roles. We recall that every consistent OWL 2 QL KB (T ; A) possesses a canonical model CT ;A with the property that T ; A j= q(a) iff CT ;A j= q(a) for every CQ q and tuple a inds(A). Thus, CQ answering in OWL 2 QL corresponds to deciding the existence of a homomorphism of the query into the canonical model. Informally,
CT ;A is obtained from A by repeatedly applying the axioms in T , introducing fresh
elements as needed to serve as witnesses for the existential quantifiers. According to the
standard construction (cf. [
Proof sketch. We exploit the fact that CQ answering over a KB (T ; A) corresponds
to evaluating the query over the canonical model CT ;A viewed as a database. If T
has depth k (with k a fixed constant), then CT ;A can be computed by a
deterministic logspace Turing machine (TM) with access to an NL oracle. Indeed, the depth
bound k implies the finiteness of CT ;A and that all domain elements can be described
using logarithmically many bits. To complete the argument, we use the fact that
answering bounded treewidth queries over databases is in LOGCFL [
Theorem 2. CQ answering is NL-complete for bounded leaf queries and bounded depth ontologies.
Proof sketch. The lower bound is an immediate consequence of the NL-hardness of answering atomic queries in OWL 2 QL. To prove the upper bound, we apply a straightforward non-deterministic procedure for deciding (T ; A) j= q : 1. Fix a directed tree T compatible with q. Let v0 be the root variable. 2. Guess u0 2 CT ;A . Return no if v0 cannot be mapped to u0. 3. Initialize Frontier to f(v0; u0)g. 4. While Frontier 6= ; (a) Remove (v1; u1) from Frontier. (b) For every child v2 of v1 i. Guess an element u2 from CT ;A . ii. Return no if (v1; v2) cannot be mapped to (u1; u2).
iii. Add (v2; u2) to Frontier.
5. Return yes.
tu
tu
Proof sketch. Concerning the upper bound, it is easy to adapt the previous algorithm
to handle arbitrary TBoxes: we simply replace CT ;A by faw 2 CT ;A j jwj
2jT j + jqjg. The modified algorithm gives the correct answers, but it does not have the
required complexity, because it might need more than logarithmically many bits to store
guessed elements aw. To show LOGCFL membership, we further modify the
procedure so that it can be implemented by a non-deterministic polytime logspace-bounded
Turing machine augmented with a stack (such TMs are known to capture LOGCFL
computation [
The lower bound is by reduction from the problem of deciding whether an input of
length l is accepted by the lth circuit of a logspace-uniform family of SAC1 circuits
(proven LOGCFL-hard in [
N -cL .3
m FLCGO :hT; arb NL=poly NP=poly: no polysize PE or NDL
[
SAC1: no poly PE but poly NDL
[
: DBs : [
: [
: [
: : : ONTOLOGY DEPTH d arb 1 2 3
: : :
ONTOLOGY DEPTH
d
Observe that for our newly identified tractable classes, polynomial-size non-recursive
datalog (NDL) rewritings are guaranteed to exist, whereas this is not the case for the
positive existential (PE) rewritings more typically considered. In future work, we plan to
marry these positive succinctness and complexity results by developing concrete
NDLrewriting algorithms for OWL 2 QL for which both the rewriting and evaluation phases
run in polynomial time (as was done in [
Acknowledgments. Partial support was provided by ANR grant 12-JS02-007-01, Russian Foundation for Basic Research and the programme “Leading Scientific Schools”.