M. Bienvenu, S. Kikot, R. Kontchakov, V. V. Podolskii, and M. Zakharyaschev, Recall that stack ?m denotes the word obtained by concatenating the first m symbols of stack

, then we choose Option 1. We remove the tuple from frontier and choose the individual a ? = h(z ? ) for the guess. As a = h(z) (by (37)) and h is a homomorphism, we have (a, a ? ) ? P C T, A , for all P(z, z ? ) ? q, and the call canMap(z ? , a ? , ?) returns true. We add (z ? ? (a ? , 0), z ?? ) to frontier for every child z ??, z ? ) such that h(z ? ) ? ind(A)

, As h is a homomorphism, we have T |= P(x, x), for all P(z, z ? ) ? q, and canMap(z ? , a, top(stack)) returns true. Then, for every child z ?? of z ? in T , we add (z ? ? (a, |stack|), z ?? ) to frontier. Observe that since h(z) = h(z ? ) and (37) holds for z

, Note that in this case, |stack| < 2|T | + |q| since, by (37), h(z) = aw, for w = stack ? |stack| , and, by the choice of homomorphism h, we have |w?| ? 2|T | + |q|. So, we continue and choose ? for the guess. By (37), since h is a homomorphism and h(z ? ) = h(z)?, the call isGenerated(?, a, top(stack)) returns true, T |= ?(x, y) ? P(x, y), for all P(z, z ? ) ? q, and the call canMap(z ? , a, top(stack)) returns true. So, we push ? onto stack and add (z ? ? (a, |stack|), z ?? ) to frontier for every child z ?? of z ? in T

, Since neither Case 1 nor Case 3 applies, |stack| > 0. So, we pop the top symbol ? from stack. Suppose first that deepest ?. By (33), all tuples in deepest share the same individual a. By (37), for every tuple (z ? (a, n), z ? ) ? deepest, we have h(z) = aw?, where w = stack ? |stack| ; moreover, as Case 3 is not applicable, h(z ? ) = aw. Since h is a homomorphism, one can show that T |= ?(x, y) ? P(x, y), for all P(z ? , z) ? q, and canMap(z ? , a, top(stack)) returns true. So, we add to frontier all tuples (z ? ? (a, |stack|), z ?? ), for children z ?? of z ? in T, then we choose Option 3 and remove all elements in deepest = {(z ? (a, n), z ? ) ? frontier | n = |stack|} from frontier

. Finally,

, A, a) that returns true. It follows that the while loop is successfully exited after reaching an empty frontier. Let L be the total number of iterations of the while loop. We inductively define a sequence h 0 , h 1 ,. .. , h L of partial functions from the variables of q to ? C T, A by considering the guesses made during the different iterations of the while loop. The domain of h i will be denoted by dom(h i )

M. Agrawal, E. Allender, R. Impagliazzo, T. Pitassi, and S. Rudich, Reducing the complexity of reductions, Computational Complexity, vol.10, pp.117-138, 2001.

M. Agrawal, E. Allender, and S. Rudich, Reductions in circuit complexity: an isomorphism theorem and a gap theorem, J. Comput. System Sci, vol.57, pp.127-143, 1998.

N. Alon and R. Boppana, The monotone circuit complexity of Boolean functions, Combinatorica, vol.7, pp.1-22, 1987.

S. Arora and B. Barak, Computational Complexity: A Modern Approach, 2009.

A. Artale, D. Calvanese, R. Kontchakov, and M. Zakharyaschev, The DL-Lite family and relations, J. Artif. Intell. Res. (JAIR), pp.1-69, 2009.

B. Aspvall, M. Plass, and R. Tarjan, A linear-time algorithm for testing the truth of certain quantified boolean formulas, Inform. Process. Lett, vol.8, pp.121-123, 1979.

J. Avigad, Eliminating definitions and Skolem functions in first-order logic, ACM Trans. Comput. Logic, vol.4, pp.402-415, 2003.

J. Baget, M. Leclère, M. Mugnier, and E. Salvat, On rules with existential variables: walking the decidability line, Artif. Intell, vol.175, pp.1620-1654, 2011.
URL : https://hal.archives-ouvertes.fr/lirmm-00587012

M. Bienvenu, S. Kikot, R. Kontchakov, V. V. Podolskii, V. Ryzhikov et al., The complexity of ontology-based data access with OWL 2 QL and bounded treewidth queries, Proc. of the 36th ACM SIGMOD-SIGACTSIGAI Symp. on Principles of Database Systems, pp.201-216, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01632638

M. Bienvenu, S. Kikot, and V. V. Podolskii, Tree-like queries in OWL 2 QL: succinctness and complexity results, Proc. of the 30th Annual ACM/IEEE Symp. on Logic in Computer Science, LICS 2015, pp.317-328, 2015.

M. Bienvenu, C. Lutz, and F. Wolter, First-order rewritability of atomic queries in Horn description logics, Proc. of the 23nd Int. Joint Conf. on Artificial Intelligence, IJCAI 2013. IJCAI/AAAI, pp.754-760, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00947535

M. Bienvenu, M. Ortiz, and M. Simkus, Regular path queries in lightweight description logics: complexity and algorithms, J. Artif. Intell. Res. (JAIR), pp.315-374, 2015.

M. Bienvenu, M. Ortiz, M. Simkus, and G. Xiao, Tractable queries for lightweight description logics, Proc. of the 23nd Int. Joint Conf. on Artificial Intelligence, IJCAI 2013. IJCAI/AAAI, pp.768-774, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00947533

M. Bienvenu and R. Rosati, Query-based comparison of OBDA specifications, Proc. of the 28th Int. Workshop on Description Logics, DL 2015 (CEUR), vol.1350, pp.55-66, 2015.

M. Bienvenu, B. Cate, C. Lutz, and F. Wolter, Ontology-based data access: a study through disjunctive Datalog, CSP, and MMSNP. ACM Trans. Database Syst, vol.39, pp.1-44, 2014.
URL : https://hal.archives-ouvertes.fr/hal-01117583

E. Botoeva, D. Calvanese, V. Santarelli, D. F. Savo, A. Solimando et al., Beyond OWL 2 QL in OBDA: rewritings and approximations, Proc. of the AAAI Conf. on Artificial Intelligence, vol.2016, 2016.

A. Brandstädt, V. B. Le, and J. P. Spinrad, Graph Classes: A Survey, 1999.

A. Bretto, Hypergraph Theory: An Introduction, 2013.
URL : https://hal.archives-ouvertes.fr/hal-01024351

A. Calì, G. Gottlob, and T. Lukasiewicz, A general Datalog-based framework for tractable query answering over ontologies, J. Web Semantics, vol.14, pp.57-83, 2012.

A. Calì, G. Gottlob, and A. Pieris, Towards more expressive ontology languages: The query answering problem, Journal of the ACM, vol.193, issue.1, p.68, 2012.

M. Bienvenu, S. Kikot, R. Kontchakov, V. V. Podolskii, and M. Zakharyaschev,

D. Calvanese, G. De-giacomo, D. Lembo, M. Lenzerini, A. Poggi et al., The MASTRO system for ontology-based data access, Semantic Web, vol.2, pp.43-53, 2011.

D. Calvanese, G. De-giacomo, D. Lembo, M. Lenzerini, and R. Rosati, Tractable reasoning and efficient query answering in description logics: the DL-Lite family, J. of Autom. Reasoning, vol.39, pp.385-429, 2007.

A. Chandra and P. Merlin, Optimal implementation of conjunctive queries in relational data bases, Conf. Record of the 9th Annual ACM Symp. on Theory of Computing, STOC'77, pp.77-90, 1977.

C. Chekuri and A. Rajaraman, Conjunctive query containment revisited, Theoretical Computer Science, vol.239, pp.211-229, 2000.
DOI : 10.1007/3-540-62222-5_36

A. Chortaras, D. Trivela, and G. Stamou, Optimized query rewriting for OWL 2 QL, Proc. of the 23rd Int. Conf. on Automated Deduction, CADE-23, vol.6803, pp.192-206, 2011.
DOI : 10.1007/978-3-642-22438-6_16
URL : http://www.image.ece.ntua.gr/papers/684.pdf

C. Civili and R. Rosati, A broad class of first-order rewritable tuple-generating dependencies, Proc. of the 2nd Int. Datalog 2.0 Workshop, vol.7494, pp.68-80, 2012.

M. Console, J. Mora, R. Rosati, V. Santarelli, and D. F. Savo, Effective computation of maximal sound approximations of description logic ontologies, Proc. of the 13th Int. Semantic Web Conf., ISWC 2014, Part II, vol.8797, pp.164-179, 2014.

S. A. Cook, Characterizations of pushdown machines in terms of time-bounded computers, J. ACM, vol.18, pp.4-18, 1971.

T. Eiter, M. Ortiz, M. ?imkus, T. Tran, and G. Xiao, Query rewriting for Horn-SHIQ plus rules, Proc. of the 26th AAAI Conf. on Artificial Intelligence, AAAI 2012. AAAI, pp.726-733, 2012.

C. Flament, Hypergraphes arborés, Discrete Mathematics, vol.21, pp.223-227, 1978.
DOI : 10.1016/0012-365x(78)90154-1
URL : https://doi.org/10.1016/0012-365x(78)90154-1

J. Flum and M. Grohe, Parameterized Complexity Theory, 2006.

M. Giese, A. Soylu, G. Vega-gorgojo, A. Waaler, P. Haase et al., Optique: Zooming in on Big Data, IEEE Computer, vol.48, pp.60-67, 2015.
DOI : 10.1109/mc.2015.82

G. Gottlob, S. Kikot, R. Kontchakov, V. V. Podolskii, T. Schwentick et al., The price of query rewriting in ontology-based data access, Artif. Intell, vol.213, pp.42-59, 2014.

G. Gottlob, N. Leone, and F. Scarcello, Computing LOGCFL certificates, Proc. of the 26th Int. Colloquium on Automata, Languages & Programming, ICALP-99, vol.1644, pp.361-371, 1999.
DOI : 10.1016/s0304-3975(01)00108-6
URL : https://doi.org/10.1016/s0304-3975(01)00108-6

G. Gottlob, N. Leone, and F. Scarcello, The complexity of acyclic conjunctive queries, J. ACM, vol.48, pp.431-498, 2001.
DOI : 10.1109/sfcs.1998.743521

G. Gottlob, M. Manna, and A. Pieris, Polynomial rewritings for linear existential rules, Proc. of the 24th Int. Joint Conf. on Artificial Intelligence, IJCAI 2015. AAAI, pp.2992-2998, 2015.

G. Gottlob, G. Orsi, and A. Pieris, Ontological queries: rewriting and optimization, Proc. of the 27th Int. Conf. on Data Engineering, pp.2-13, 2011.
DOI : 10.1109/icde.2011.5767965

G. Gottlob and T. Schwentick, Rewriting ontological queries into small nonrecursive Datalog programs, Proc. of the 13th Int. Conf. on Principles of Knowledge Representation & Reasoning, KR 2012. AAAI, pp.254-263, 2012.

S. A. Greibach, The Hardest Context-Free Language, SIAM J. Comput, vol.2, pp.304-310, 1973.
DOI : 10.1137/0202025

M. Grigni and M. Sipser, Monotone complexity, Proc. of the London Mathematical Society Symp. on Boolean Function Complexity, pp.57-75, 1992.
DOI : 10.1017/cbo9780511526633.006

M. Grohe, T. Schwentick, and L. Segoufin, When is the evaluation of conjunctive queries tractable, Proc. of the 33rd Annual ACM Symp. on Theory of Computing, STOC, pp.657-666, 2001.

V. Gutiérrez-basulto, Y. Ibáñez-garcía, R. Kontchakov, and E. V. Kostylev, Queries with negation and inequalities over lightweight ontologies, J. Web Semantics, vol.35, pp.184-202, 2015.

P. Hansen, C. Lutz, I. Seylan, and F. Wolter, Efficient query rewriting in the description logic EL and beyond, Proc. of the 24th Int. Joint Conf. on Artificial Intelligence, IJCAI 2015. AAAI, pp.3034-3040, 2015.

D. A. Huffman, A method for the construction of minimum-redundancy codes, Proceedings of the Institute of Radio Engineers, vol.40, pp.1098-1101, 1952.

N. Immerman, Nondeterministic space is closed under complementation, SIAM J. Comput, vol.17, pp.935-938, 1988.
DOI : 10.1109/sct.1988.5270

D. S. Johnson, A Catalog of Complexity Classes, In Handbook of Theoretical Computer Science, vol.A, pp.67-161, 1990.

D. S. Johnson and A. C. Klug, Testing containment of conjunctive queries under functional and inclusion dependencies, Proc. of the ACM Symp. on Principles of Database Systems, PODS. ACM, pp.164-169, 1982.
DOI : 10.1145/588111.588138

S. Jukna, Boolean Function Complexity-Advances and Frontiers, Algorithms and combinatorics, vol.27, 2012.
DOI : 10.1007/978-3-642-24508-4

M. Kaminski, Y. Nenov, and B. C. Grau, Datalog rewritability of disjunctive Datalog programs and its applications to ontology reasoning, Proc. of the 28th AAAI Conference on Artificial Intelligence, AAAI 2014. AAAI, pp.1077-1083, 2014.
DOI : 10.1016/j.artint.2016.03.006

M. Karchmer and A. Wigderson, Monotone circuits for connectivity require super-logarithmic depth, Proc. of the 20th Annual ACM Symp. on Theory of Computing, STOC '88, pp.539-550, 1988.
DOI : 10.1145/62212.62265

E. Kharlamov, D. Bilidas, D. Hovland, E. Jiménez-ruiz, D. Lanti et al., Ontology based data access in Statoil, J. Web Semantics, vol.44, pp.3-36, 2017.
DOI : 10.1016/j.websem.2017.05.005
URL : https://brage.bibsys.no/xmlui/bitstream/11250/2467066/2/main-JWS-16-Statoil75767.pdf

E. Kharlamov, T. Mailis, G. Mehdi, C. Neuenstadt, Ö. Özçep et al., Semantic access to streaming and static data at Siemens, J. Web Semantics, vol.44, pp.54-74, 2017.
DOI : 10.2139/ssrn.3199299
URL : https://brage.bibsys.no/xmlui/bitstream/11250/2467073/3/main-JWS-16-Siemens.pdf

S. Kikot, R. Kontchakov, V. V. Podolskii, and M. Zakharyaschev, Exponential lower bounds and separation for query rewriting, Proc. of the 39th Int. Colloquium on Automata, Languages & Programming, ICALP 2012, vol.7392, pp.263-274, 2012.

S. Kikot, R. Kontchakov, V. V. Podolskii, and M. Zakharyaschev, On the succinctness of query rewriting over shallow ontologies, Proc. of the Joint Meeting of the 23rd EACSL Annual Conf. on Computer Science Logic (CSL) and the 29th Annual ACM/IEEE Symp. on Logic in Computer Science (LICS), vol.57, pp.1-57, 2014.

S. Kikot, R. Kontchakov, and M. Zakharyaschev, On (in)tractability of OBDA with OWL 2 QL, Proc. of the 24th Int. Workshop on Description Logics, vol.745, pp.224-234, 2011.

S. Kikot, R. Kontchakov, and M. Zakharyaschev, Conjunctive query Answering with OWL 2 QL, Proc. of the 13th Int. Conf. on Principles of Knowledge Representation & Reasoning, KR 2012. AAAI, pp.275-285, 2012.

M. König, M. Leclère, and M. Mugnier, Query rewriting for existential rules with compiled preorder, Proc. of the 24th Int. Joint Conf. on Artificial Intelligence, IJCAI 2015. AAAI, pp.3106-3112, 2015.

M. König, M. Leclère, M. Mugnier, and M. Thomazo, Sound, complete and minimal UCQ-rewriting for existential rules, Semantic Web, vol.6, pp.451-475, 2015.

R. Kontchakov, C. Lutz, D. Toman, F. Wolter, and M. Zakharyaschev, The combined approach to query answering in DL-Lite, Proc. of the 12th Int. Conf. on Principles of Knowledge Representation & Reasoning, KR 2010. AAAI, pp.247-257, 2010.

R. Kontchakov, M. Rezk, M. Rodriguez-muro, G. Xiao, and M. Zakharyaschev, Answering SPARQL queries over databases under OWL 2 QL entailment regime, Proc. of the 13th Int. Semantic Web Conf., ISWC 2014, Part I (LNCS), vol.8796, pp.552-567, 2014.

E. V. Kostylev, J. L. Reutter, and D. Vrgo?, XPath for DL ontologies, Proc. of the 29th AAAI Conference on Artificial Intelligence, AAAI 2015. AAAI, pp.1525-1531, 2015.

D. Lembo, J. Mora, R. Rosati, D. F. Savo, and E. Thorstensen, Mapping analysis in ontology-based data access: algorithms and complexity, Proc. of the 14th Int. Semantic Web Conf., ISWC 2015, vol.9366, pp.217-234, 2015.

L. Libkin, Elements of Finite Model Theory, 2004.

C. Lutz, The complexity of conjunctive query answering in expressive description logics, Proc. of the 4th Int. Joint Conf. on Automated Reasoning, IJCAR 2008 (LNAI), pp.179-193, 2008.

C. Lutz, R. Piro, and F. Wolter, Description logic TBoxes: model-theoretic characterizations and rewritability, Proc. of the 22nd Int. Joint Conf. on Artificial Intelligence, IJCAI 2011. IJCAI/AAAI, pp.983-988, 2011.

C. Lutz, I. Seylan, D. Toman, and F. Wolter, The combined approach to OBDA: taming role hierarchies using filters, Proc. of the 12th Int. Semantic Web Conf., ISWC 2013, Part I (LNCS), vol.8218, pp.314-330, 2013.

C. Lutz, D. Toman, and F. Wolter, Conjunctive query answering in the description logic EL using a relational database system, Proc. of the 21st Int. Joint Conf. on Artificial Intelligence, IJCAI 2009, pp.2070-2075, 2009.

J. Mora, R. Rosati, and Ó. Corcho, Kyrie2: query rewriting under extensional constraints in ELHIO, Proc. of the 13th Int. Semantic Web Conf., ISWC 2014, vol.8796, pp.568-583, 2014.

H. Pérez-urbina, B. Motik, and I. Horrocks, A comparison of query rewriting techniques for DL-lite, Proc. of the 22nd Int. Workshop on Description Logics, DL 2009 (CEUR), vol.477, 2009.

H. Pérez-urbina, E. Rodríguez-díaz, M. Grove, G. Konstantinidis, and E. Sirin, Evaluation of query rewriting approaches for OWL 2, Proc. of SSWS+HPCSW 2012 (CEUR), vol.943, 2012.

A. Poggi, D. Lembo, D. Calvanese, G. De-giacomo, M. Lenzerini et al., Linking data to ontologies, J. Data Semantics X, pp.133-173, 2008.

R. Raz and A. Wigderson, Monotone circuits for matching require linear depth, J. ACM, vol.39, pp.736-744, 1992.

A. Razborov, Lower bounds for the monotone complexity of some Boolean functions, Dokl. Akad. Nauk SSSR, vol.281, pp.798-801, 1985.

A. A. Razborov, Lower bounds for deterministic and nondeterministic branching programs, Proc. of the 8th Int. Symp. on Fundamentals of Computation Theory, FCT'91, vol.529, pp.47-60, 1991.

M. Rodriguez-muro and D. Calvanese, High performance query answering over DL-Lite ontologies, Proc. of the 13th Int. Conf. on Principles of Knowledge Representation & Reasoning, KR 2012. AAAI, pp.308-318, 2012.

M. Rodriguez-muro, R. Kontchakov, and M. Zakharyaschev, Ontology-based data access: Ontop of databases, Proc. of the 12th Int. Semantic Web Conf., ISWC 2013, vol.8218, pp.558-573, 2013.

R. Rosati, The limits of querying ontologies, Proc. of the 11th Int. Conf. on Database Theory, ICDT 2007, vol.4353, pp.164-178, 2007.

M. Bienvenu, S. Kikot, R. Kontchakov, V. V. Podolskii, and M. Zakharyaschev,

R. Rosati, Prexto: query rewriting under extensional constraints in DL-Lite, Proc. of the 9th Extended Semantic Web Conf, vol.7295, pp.360-374, 2012.

R. Rosati and A. Almatelli, Improving query answering over DL-Lite ontologies, Proc. of the 12th Int. Conf. on Principles of Knowledge Representation & Reasoning, KR 2010. AAAI, pp.290-300, 2010.

J. F. Sequeda, M. Arenas, and D. P. Miranker, OBDA: query rewriting or materialization? In practice, both!, Proc. of the 13th Int. Semantic Web Conf., ISWC 2014, Part I (LNCS), vol.8796, pp.535-551, 2014.

I. H. Sudborough, On the tape complexity of deterministic context-free languages, J. ACM, vol.25, pp.405-414, 1978.

R. Szelepcsényi, The method of forced enumeration for nondeterministic automata, Acta Informatica, vol.26, pp.279-284, 1988.

M. Thomazo, Compact rewritings for existential rules, Proc. of the 23rd Int. Joint Conf. on Artificial Intelligence, IJCAI 2013. IJCAI/AAAI, pp.1125-1131, 2013.

M. Vardi, The complexity of relational query languages (extended abstract), Proc. of the 14th ACM SIGACT Symp. on Theory of Computing, STOC'82, pp.137-146, 1982.

H. Venkateswaran, Properties that characterize LOGCFL, J. Comput. System Sci, vol.43, pp.380-404, 1991.

H. Vollmer, Introduction to Circuit Complexity: A Uniform Approach, 1999.

M. Yannakakis, Algorithms for acyclic database schemes, Proc. of the 7th Int. Conf. on Very Large Data Bases, VLDB'81, pp.82-94, 1981.

Y. Zhou, B. Grau, Y. Nenov, M. Kaminski, and I. Horrocks, PAGOdA: pay-as-you-go ontology query answering using a Datalog reasoner, J. Artif. Intell. Res. (JAIR), vol.54, pp.309-367, 2015.