S. Abiteboul, R. Hull, and V. Vianu, Foundations of Databases, 1995.

J. Baget, M. Lecì-ere, M. Mugnier, and E. Salvat, On rules with existential variables: Walking the decidability line, Artificial Intelligence, vol.175, issue.9-10, pp.9-10, 2011.
DOI : 10.1016/j.artint.2011.03.002

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, Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems , PODS '17, 2017.
DOI : 10.1016/0022-0000(91)90020-6

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, 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science, pp.317-328, 2015.
DOI : 10.1109/LICS.2015.38

URL : http://www.dcs.bbk.ac.uk/%7Ekikot/papers/lics15_main.pdf

I. Boguslavsky, V. Dikonov, L. Iomdin, A. Lazursky, V. Sizov et al., Semantic analysis and question answering: a system under development, Computational Linguistics and Intellectual Technologies. Papers from the Annual International Conference Dialogue, p.21, 2015.

A. Caì-i, G. Gottlob, and T. Lukasiewicz, A general datalog-based framework for tractable query answering over ontologies, Journal of Web Semantics, vol.14, pp.57-83, 2012.

S. A. Cook, Characterizations of Pushdown Machines in Terms of Time-Bounded Computers, Journal of the ACM, vol.18, issue.1, pp.4-18, 1971.
DOI : 10.1145/321623.321625

C. Grau, B. Horrocks, I. Krötzsch, M. Kupke, C. Magka et al., Acyclicity notions for existential rules and their application to query answering in ontologies, Journal of Artificial Intelligence Research, vol.47, pp.741-808, 2013.

G. Gottlob, G. Greco, N. Leone, and F. Scarcello, Hypertree Decompositions, Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS '16, 2016.
DOI : 10.1145/79173.79181

G. Gottlob, N. Leone, and F. Scarcello, Hypertree Decompositions and Tractable Queries, Journal of Computer and System Sciences, vol.64, issue.3, pp.579-627, 2002.
DOI : 10.1006/jcss.2001.1809

URL : https://doi.org/10.1006/jcss.2001.1809

G. Gottlob, G. Orsi, and A. Pieris, Query Rewriting and Optimization for Ontological Databases, ACM Transactions on Database Systems, vol.39, issue.3, pp.1-2546, 2014.
DOI : 10.1007/s13740-012-0017-6

S. Kikot, R. Kontchakov, V. Podolskii, and M. Zakharyaschev, On the succinctness of query rewriting over shallow ontologies, Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), CSL-LICS '14, pp.1-5710, 2014.
DOI : 10.1145/2603088.2603131

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 and Reasoning, pp.275-285, 2012.

M. König, M. Lecì-ere, M. Mugnier, and M. Thomazo, Sound, complete and minimal UCQ-rewriting for existential rules, Semantic Web, vol.3, issue.1, pp.451-475, 2015.
DOI : 10.1007/s13740-012-0017-6

M. König, M. Leclere, and M. Mugnier, Query rewriting for existential rules with compiled preorder, Proc. of the 24th Int. Joint Conf. on Artificial Intelligence, 2015.

I. H. Sudborough, On the Tape Complexity of Deterministic Context-Free Languages, Journal of the ACM, vol.25, issue.3, pp.405-414, 1978.
DOI : 10.1145/322077.322083

M. Thomazo, Compact rewriting for existential rules, Proc. of the 23rd Int. Joint Conf. on Artificial Intelligence, 2013.
URL : https://hal.archives-ouvertes.fr/lirmm-00839422

H. Venkateswaran, Properties that characterize LOGCFL, Journal of Computer and System Sciences, vol.43, issue.2, pp.380-404, 1991.
DOI : 10.1016/0022-0000(91)90020-6

URL : https://doi.org/10.1016/0022-0000(91)90020-6