. References, . Abiteboul, V. Hull, S. Abiteboul, R. Hull et al., Foundations of Databases, 1994.

C. Afrati, F. N. Afrati, S. S. Cosmadakis, and M. Yannakakis, On Datalog vs Polynomial Time, Journal of Computer and System Sciences, vol.51, issue.2, pp.177-196, 1995.
DOI : 10.1006/jcss.1995.1060

M. Krötzsch, R. , and S. , How to best nest regular path queries, 2014.

M. Krötzsch, R. , and S. , Reasonable highly expressive query languages, Proc. 24th International Joint Conference on Artificial Intelligence (IJCAI'15), pp.2826-2832, 2015.

C. Chandra, A. K. Harel, and D. , Computable queries for relational data bases, Journal of Computer and System Sciences, vol.21, issue.2, pp.156-178, 1980.
DOI : 10.1016/0022-0000(80)90032-X

C. , K. Chang, C. C. Keisler, and H. J. , Model Theory, 1989.

[. Grau, Computing Datalog rewritings beyond Horn ontologies, Proc. 23rd International Joint Conference on Artificial Intelligence (IJCAI'13). IJCAI/AAAI, 2013.

K. Dawar, A. Dawar, and S. Kreutzer, On datalog vs, LFP. In Aceto, L, 2008.

J. Edmonds, Paths, trees and flowers . Canad, J. Math, vol.17, pp.449-467, 1965.

G. Gottlob and T. Schwentick, Rewriting ontological queries into small nonrecursive Datalog programs, Proc. 13th International Conference on Principles of Knowledge Representation and Reasoning (KR'12, 2012.

S. Rudolph and M. Simkus, Expressiveness of guarded existential rule languages, Proc. 33rd Symposium on Principles of Database Systems (PODS'14), pp.27-38, 2014.

N. Immerman, . Kaminski, C. Nenov, . Grau, M. Kaminski et al., Descriptive complexity . Graduate texts in computer science Datalog rewritability of disjunctive Datalog programs and its applications to ontology reasoning, Proc. 28th AAAI Conference on Artificial Intelligence (AAAI'14), pp.1077-1083, 1999.

R. Ortiz, S. Rudolph, S. Simkus, and M. , Worst-case optimal reasoning for the Horn-DL fragments of OWL 1 and 2, Proc. 12th International Conference on Principles of Knowledge Representation and Reasoning (KR'10, 2010.

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

T. Rudolph, S. Rudolph, and M. Thomazo, Characterization of the expressivity of existential rule queries, Proc. 24th International Joint Conference on Artificial Intelligence (IJCAI'15, 2015.