, typeC r (z 1 , z 2 ) ? r(x, y) ? in(y, z 1 ) ? in(x

, typeD r (z 1 , z 2 ) ? in(x, z 1 ) ? r(x, y) ? in(y

, typeE r (z 1 , z 2 ) ? in(x, z 1 ) ? r(x, y) ? in(y

, ) for any R = p 1 (x)?p 2 (x) from T , 2. typeB (c p 1 , c p 2 , c p 3 ) for any R = p 1 (x)?p 2 (x)?p 3 (x) from T , 3. typeC r (c p 1 , c p 2 ) for any R = r(x, y)?p 1 (y)?p 2 (x) from T , 4. typeD r (c p 1 , c p 2 ) for any R = p 1 (x)?r(x, y)?p 2 (y) from T , and 5. typeE r

, ? Pr 1 , we let F p 1 p 2 = {test(a), sub(c p 1 ), super (c p 2 )} The following property now lists two straightforward observations

, Property 31. R fix is a wgfr1 rule set. F T can be computed in polynomial time and is of polynomial size with respect to T . The next lemma establishes that subsumption in Horn-ALC

, Pr 2 ] terminology and let p 1 , p 2 ? Pr 1 . Then T |= ?x(p 1 (x) ? p 2 (x)) if and only if F T ? F p 1 p 2 , R fix |= match, Lemma 32. Let T be a reduced normalized Horn-ALC

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

A. V. Aho, C. Beeri, and J. D. Ullman, The theory of joins in relational databases, ACM Trans. Database Syst, vol.4, issue.3, pp.297-314, 1979.

H. Andréka, I. Németi, and J. Van-benthem, Modal Languages and Bounded Fragments of Predicate Logic, J. of Philosophical Logic, vol.27, pp.217-274, 1998.

H. Andréka, J. Van-benthem, and I. Németi, Modal languages and bounded fragments of FOL, 1996.

F. Baader, Least common subsumers and most specific concepts in a description logic with existential restrictions and terminological cycles, Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI'03), pp.325-330, 2003.

F. Baader, D. Calvanese, D. Mcguinness, and D. Nardi, The Description Logic Handbook: Theory, Implementation, and Applications, 2007.

F. Baader and U. Sattler, An overview of tableau algorithms for description logics, Studia Logica, vol.69, issue.1, pp.5-40, 2001.

J. Baget, M. Leclère, and M. Mugnier, Walking the Decidability Line for Rules with Existential Variables, Principles of Knowledge Representation and Reasoning: Proceedings of the Twelfth International Conference, 2010.
URL : https://hal.archives-ouvertes.fr/lirmm-00535780

J. Baget, M. Leclère, M. Mugnier, and E. Salvat, Extending Decidable Cases for Rules with Existential Variables, IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, pp.677-682, 2009.
URL : https://hal.archives-ouvertes.fr/lirmm-00410130

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

J. Baget and M. Mugnier, The Complexity of Rules and Constraints, J. Artif. Intell. Res. (JAIR), vol.16, pp.425-465, 2002.
URL : https://hal.archives-ouvertes.fr/lirmm-00268460

J. Baget, M. Mugnier, S. Rudolph, and M. Thomazo, Walking the Complexity Lines for Generalized Guarded Existential Rules, IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, pp.712-717, 2011.
URL : https://hal.archives-ouvertes.fr/lirmm-00618081

C. Beeri and M. Vardi, The implication problem for data dependencies, Proceedings of Automata, Languages and Programming, vol.115, pp.73-85, 1981.

C. Beeri and M. Vardi, A Proof Procedure for Data Dependencies, Journal of the ACM, vol.31, issue.4, pp.718-741, 1984.

E. W. Beth, Mededelingen van de Koninklijke Nederlandse Akademie van Wetenschappen, Afdeling Letterkunde, vol.18, issue.13, pp.309-342, 1955.

P. Blackburn and . Van-benthem, of Studies in Logic and Practical Reasoning, Handbook of Modal Logic, vol.3, 2006.

P. Bourhis, M. Morak, and A. Pieris, The impact of disjunction on query answering under guarded-based existential rules, IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence, 2013.

A. Calì, G. Gottlob, and M. Kifer, Taming the Infinite Chase: Query Answering under Expressive Relational Constraints, Principles of Knowledge Representation and Reasoning: Proceedings of the Eleventh International Conference, pp.70-80, 2008.

A. Calì, G. Gottlob, and M. Kifer, Taming the infinite chase: Query answering under expressive relational constraints, J. Artif. Intell. Res. (JAIR), vol.48, pp.115-174, 2013.

A. Calì, G. Gottlob, T. Lukasiewicz, B. Marnette, and A. Pieris, Datalog+/-: A family of logical knowledge representation and query languages for new applications, Proceedings of the 25th Annual IEEE Symposium on Logic in Computer Science, LICS 2010, pp.228-242, 2010.

A. Calì, G. Gottlob, and M. Kifer, Taming the infinite chase: Query answering under expressive relational constraints, J. Artif. Intell. Res. (JAIR), vol.48, pp.115-174, 2013.

A. Calì, G. Gottlob, and T. Lukasiewicz, A General Datalog-Based Framework for Tractable Query Answering over Ontologies, Proceedings of the Twenty-Eigth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pp.77-86, 2009.

A. Calì, D. Lembo, and R. Rosati, On the decidability and complexity of query answering over inconsistent and incomplete databases, Proceedings of the Twenty-Second ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp.260-271, 2003.

D. Calvanese, G. De-giacomo, and M. Lenzerini, On the decidability of query containment under constraints, Proceedings of the 17th ACM SIGACT SIGMOD Symposium on Principles of Database Systems (PODS 1998), pp.149-158, 1998.

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, Journal of Automated Reasoning, vol.39, issue.3, pp.385-429, 2007.

A. K. Chandra, H. R. Lewis, and J. A. Makowsky, Embedded implicational dependencies and their inference problem, Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing (STOC 1981), pp.342-354, 1981.

A. K. Chandra, D. C. Kozen, and L. J. Stockmeyer, Alternation. Journal of the ACM, vol.28, issue.1, pp.114-133, 1981.

M. Chein and M. Mugnier, , 2009.

, Graph-based Knowledge Representation and Reasoning-Computational Foundations of Conceptual Graphs. Advanced Information and Knowledge Processing

B. Courcelle, The Monadic Second-Order Logic of Graphs: I. Recognizable Sets of Finite Graphs, Inf. Comput, vol.85, issue.1, pp.12-75, 1990.

A. Deutsch, A. Nash, and J. Remmel, The chase revisited, Proceedings of the Twenty-Seventh ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2008, pp.149-158, 2008.

R. Fagin, P. G. Kolaitis, R. J. Miller, and L. Popa, Data Exchange: Semantics and Query Answering, Theor. Comput. Sci, vol.336, issue.1, pp.89-124, 2005.

G. Gottlob, G. Orsi, and A. Pieris, Query rewriting and optimization for ontological databases, ACM Trans. Database Syst, vol.39, issue.3, p.25, 2014.

G. Gottlob, A. Hernich, C. Kupke, and T. Lukasiewicz, Stable model semantics for guarded existential rules and description logics, Principles of Knowledge Representation and Reasoning: Proceedings of the Fourteenth International Conference, 2014.

G. Gottlob, M. Manna, and A. Pieris, Combining decidability paradigms for existential rules. Theory and Practice of Logic Programming, vol.13, pp.877-892, 2013.

G. Gottlob, S. Rudolph, and M. Simkus, Expressiveness of guarded existential rule languages, Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS'14, pp.27-38, 2014.

I. Horrocks and U. Sattler, A tableau decision procedure for SHOIQ, J. Autom. Reasoning, vol.39, issue.3, pp.249-276, 2007.

U. Hustadt, B. Motik, and U. Sattler, Data complexity of reasoning in very expressive description logics, Proc. 19th Int. Joint Conf. on Artificial Intelligence (IJCAI'05), pp.466-471, 2005.

D. Johnson and A. Klug, Testing containment of conjunctive queries under functional and inclusion dependencies, J. Comput. Syst. Sci, vol.28, issue.1, pp.167-189, 1984.

Y. Kazakov, Consequence-driven reasoning for horn-SHIQ ontologies, IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, pp.2040-2045, 2009.

G. Kerdiles, Saying it with Pictures: a logical landscape of conceptual graphs, 2001.

M. König, M. Leclère, M. Mugnier, and M. Thomazo, Sound, complete and minimal ucq-rewriting for existential rules, 2014.

R. Kontchakov, C. Lutz, D. Toman, F. Wolter, and M. Zakharyaschev, The combined approach to query answering in DL-lite, Principles of Knowledge Representation and Reasoning: Proceedings of the Twelfth International Conference, 2010.

M. Krötzsch and S. Rudolph, Extending Decidable Existential Rules by Joining Acyclicity and Guardedness, IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, pp.963-968, 2011.

M. Krötzsch, F. Maier, A. Krisnadhi, P. Hitzler, S. Srinivasan et al., A better uncle for owl: nominal schemas for integrating rules and ontologies, Proceedings of the 20th International Conference on World Wide Web, pp.645-654, 2011.

M. Krötzsch and S. Rudolph, Nominal schemas in description logics: Complexities clarified, Principles of Knowledge Representation and Reasoning: Proceedings of the Fourteenth International Conference, 2014.

M. Krötzsch, S. Rudolph, and P. Hitzler, Complexity Boundaries for Horn Description Logics, Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence, pp.452-457, 2007.

M. Krötzsch, S. Rudolph, and P. Hitzler, Complexities of Horn description logics, ACM Trans. Comput. Logic, vol.14, issue.1, p.36, 2013.

A. Y. Levy and M. Rousset, CARIN: A representation language combining Horn rules and description logics, Proceedings of the 12th European Conference on Artificial Intelligence (ECAI 1996), pp.323-327, 1996.

C. Lutz, Inverse roles make conjunctive queries hard, Proceedings of the 2007 International Workshop on Description Logics (DL2007), pp.CEUR-WS, 2007.

C. Lutz, D. Toman, and F. Wolter, Conjunctive Query Answering in the Description Logic EL Using a Relational Database System, IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, pp.2070-2075, 2009.

D. Maier, The Theory of Relational Databases, 1983.

D. Maier, A. O. Mendelzon, and Y. Sagiv, Testing implications of data dependencies, ACM Trans. Database Syst, vol.4, issue.4, pp.455-469, 1979.

B. Motik, B. Cuenca-grau, I. Horrocks, Z. Wu, A. Fokoue et al., OWL 2 Web Ontology Language: Profiles. W3C Recommendation. Available at, 2009.

B. Motik, B. C. Grau, I. Horrocks, and U. Sattler, Representing ontologies using description logics, description graphs, and rules, Artif. Intell, vol.173, issue.14, pp.1275-1309, 2009.

B. Motik, U. Sattler, and R. Studer, Query answering for OWL DL with rules, Journal of Web Semantics, vol.3, issue.1, pp.41-60, 2005.

M. Ortiz, S. Rudolph, and M. Simkus, Worst-case optimal reasoning for the Horn-DL fragments of OWL 1 and 2, 2010.

M. Ortiz, S. Rudolph, and M. Simkus, Query answering in the Horn fragments of the description logics SHOIQ and SROIQ, IJCAI, pp.1039-1044, 2011.

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

I. Pratt-hartmann, Complexity of the two-variable fragment with counting quantifiers, Journal of Logic, Language and Information, vol.14, pp.369-395, 2005.

S. Rudolph, A. Polleres, C. Amato, M. Arenas, S. Handschuh et al., Foundations of description logics, Reasoning Web, vol.6848, pp.76-136, 2011.

S. Rudolph, The two views on ontological query answering, Proceedings of the 8th Alberto Mendelzon Workshop on Foundations of Data Management, vol.1189, 2014.

S. Rudolph and B. Glimm, Nominals, inverses, counting, and conjunctive queries or: Why infinity is your friend!, Journal of Artificial Intelligence Research, vol.39, pp.429-481, 2010.

S. Rudolph, M. Krötzsch, and P. Hitzler, Type-elimination-based reasoning for the description logic SHIQb s using decision diagrams and disjunctive datalog, Logical Methods in Computer Science, vol.8, issue.1, 2012.

E. Salvat and M. Mugnier, Sound and Complete Forward and Backward Chainings of Graph Rules, Conceptual Structures: Knowledge Representation as Interlingua, 4th International Conference on Conceptual Structures, ICCS '96, vol.1115, pp.248-262, 1996.

R. M. Smullyan, First-order logic. Dover books on mathematics, 1968.

M. Thomazo, Conjunctive Query Answering Under Existential Rules-Decidability, Complexity, and Algorithms, 2013.
URL : https://hal.archives-ouvertes.fr/tel-00925722

M. Thomazo, J. Baget, M. Mugnier, and S. Rudolph, A generic querying algorithm for greedy sets of existential rules, Principles of Knowledge Representation and Reasoning: Proceedings of the Thirteenth International Conference, 2012.
URL : https://hal.archives-ouvertes.fr/lirmm-00763518

. W3c-owl-working and . Group, OWL 2 Web Ontology Language: Document Overview. W3C Recommendation, 2009.