A. Artale, D. Calvanese, R. Kontchakov, and M. Zakharyaschev, The DL-Lite family and relations, Journal of Artifical Intelligence Research, vol.36, pp.1-69, 2009.

F. Baader, M. Bienvenu, C. Lutz, and F. Wolter, Query and predicate emptiness in description logics, Proceedings of the 12th International Conference on Principles of Knowledge Representation and Reasoning (KR), 2010.
URL : https://hal.archives-ouvertes.fr/hal-00624141

F. Baader, S. Brandt, and C. Lutz, Pushing the EL envelope, Proceedings of International Joint Conference on Artificial Intelligence (IJCAI), pp.364-369, 2005.

F. Baader, S. Brandt, and C. Lutz, Pushing the EL envelope further, Proceedings of the Workshop on OWL: Experiences and Directions (OWLED), 2008.

M. Benedikt, W. Fan, and F. Geerts, XPath satisfiability in the presence of DTDs, Journal of the ACM, vol.55, issue.2, pp.1-79, 2008.
DOI : 10.1145/1346330.1346333

M. Bienvenu, P. Hansen, C. Lutz, and F. Wolter, First-order rewritability of conjunctive queries in Horn description logics Forthcoming, 2016.

M. Bienvenu, C. Lutz, and F. Wolter, Query containment in description logics reconsidered, Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning (KR), 2012.
URL : https://hal.archives-ouvertes.fr/hal-00789143

M. Bienvenu, B. Ten-cate, C. Lutz, and F. Wolter, Ontology-based data access: A study through disjunctive datalog, CSP, and MMSNP, ACM Transactions on Database System (TODS), vol.39, issue.4, p.33, 2014.
URL : https://hal.archives-ouvertes.fr/hal-01117583

E. Botoeva, R. Kontchakov, V. Ryzhikov, F. Wolter, and M. Zakharyaschev, Games for query inseparability of description logic knowledge bases, Proceedings of the 14th International Conference in the Principles of Knowledge Representation and Reasoning (KR), 2014.
DOI : 10.1016/j.artint.2016.01.010

E. Botoeva, R. Kontchakov, V. Ryzhikov, F. Wolter, and M. Zakharyaschev, Games for query inseparability of description logic knowledge bases, Artificial Intelligence, vol.234, pp.78-119, 2016.
DOI : 10.1016/j.artint.2016.01.010

P. Bourhis and C. Lutz, Containment in monadic disjunctive datalog, mmsnp, and expressive description logics, Proceedings of the 15th International Conference on Principles of Knowledge Representation and Reasoning (KR), 2016.
URL : https://hal.archives-ouvertes.fr/hal-01413887

D. Calvanese, G. De-giacomo, D. Lembo, M. Lenzerini, A. Poggi et al., Ontologies and Databases: The DL-Lite Approach, Tutorial Lectures of the 5th International Reasoning Web Summer School, pp.255-356, 2009.
DOI : 10.1007/978-3-662-03927-4

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.104, issue.1,2, pp.39-385, 2007.
DOI : 10.1007/s10817-007-9078-x

D. Calvanese, G. De-giacomo, D. Lembo, M. Lenzerini, and R. Rosati, Data complexity of query answering in description logics, Artificial Intelligence, vol.195, pp.335-360, 2013.
DOI : 10.1016/j.artint.2012.10.003

D. Calvanese, G. De-giacomo, and M. Lenzerini, On the decidability of query containment under constraints, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems , PODS '98, pp.149-158, 1998.
DOI : 10.1145/275487.275504

D. Calvanese, M. Ortiz, M. Simkus, and G. Stefanoni, Reasoning about explanations for negative query answers in DL-Lite, Journal of Artificial Intelligence Research, vol.48, pp.635-669, 2013.

A. Chortaras, D. Trivela, and G. B. Stamou, Optimized Query Rewriting for OWL 2 QL, Proceedings of the 23rd International Conference on Automated Deduction (CADE), pp.192-206, 2011.
DOI : 10.1007/978-3-642-04930-9_31

T. Eiter, G. Gottlob, M. Ortiz, and M. Simkus, Query Answering in the Description Logic Horn- $\mathcal{SHIQ}$, Proceedings of the 11th European Conference on Logics in Artificial Intelligence (JELIA), pp.166-179, 2008.
DOI : 10.1007/978-3-540-87803-2_15

T. Eiter, M. Ortiz, M. Simkus, T. Tran, and G. Xiao, Query rewriting for Horn-SHIQ plus rules, Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI), 2012.

D. Gabbay, A. Kurucz, F. Wolter, and M. Zakharyaschev, Many-Dimensional Modal Logics: Theory and Applications, 2003.

W. Gatens, B. Konev, and F. Wolter, Lower and upper approximations for depleting modules of description logic ontologies, Proceedings of the 21st European Conference on Artificial Intelligence (ECAI), pp.345-350, 2014.

B. Glimm, C. Lutz, I. Horrocks, and U. Sattler, Answering conjunctive queries in the SHIQ description logic, Journal of Artificial Intelligence Research, pp.31-150, 2008.

J. Golbeck, G. Fragoso, F. Hartel, J. Hendler, J. Oberthaler et al., The National Cancer Institute???s Th??saurus and Ontology, Web Semantics: Science, Services and Agents on the World Wide Web, vol.1, issue.1, pp.75-80, 2003.
DOI : 10.1016/j.websem.2003.07.007

B. C. Grau, I. Horrocks, Y. Kazakov, and U. Sattler, Modular reuse of ontologies: Theory and practice, Journal of Artifical Intelligence Research, pp.31-273, 2008.

C. Haase, Complexity of subsumption in extensions of EL, 2007.

I. Horrocks, O. Kutz, and U. Sattler, The even more irresistible SROIQ, Proceedings of the 10th International Conference on Principles of Knowledge Representation and Reasoning (KR), pp.57-67, 2006.

U. Hustadt, B. Motik, and U. Sattler, A Decomposition Rule for Decision Procedures by Resolution-Based Calculi, Proceedings of the 11th International Conference on Logic for Programming Artificial Intelligence and Reasoning (LPAR), pp.21-35, 2004.
DOI : 10.1007/978-3-540-32275-7_2

U. Hustadt, B. Motik, and U. Sattler, Reasoning in Description Logics by a Reduction to Disjunctive Datalog, Journal of Automated Reasoning, vol.2, issue.3, pp.351-384, 2007.
DOI : 10.1007/s10817-007-9080-3

M. Kaminski, T. Schneider, and G. Smolka, Correctness and worst-case optimality of Prattstyle decision procedures for modal and hybrid logics, Proceedings of the 20th International Conference on Automated Reasoning with Analytic Tableaux and Related Methods (TABLEAUX), pp.196-210, 2011.

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

Y. Kazakov, An Extension of Complex Role Inclusion Axioms in the Description Logic $\mathcal{SROIQ}$, Proceedings of the 5th International Joint Conference on Automated Reasoning (IJCAR), pp.472-486, 2010.
DOI : 10.1007/978-3-642-14203-1_40

B. Konev, M. Ludwig, D. Walther, and F. Wolter, The logical difference for the lightweight description logic EL, Journal of Artificial Intelligence Research, vol.44, pp.633-708, 2012.

B. Konev, C. Lutz, D. Walther, and F. Wolter, Model-theoretic inseparability and modularity of description logic ontologies, Artificial Intelligence, vol.203, pp.66-103, 2013.
DOI : 10.1016/j.artint.2013.07.004

R. Kontchakov, M. Rodriguez-muro, and M. Zakharyaschev, Ontology-Based Data Access with Databases: A Short Course, Proceedings of the International Reasoning Web Summer School, pp.194-229, 2013.
DOI : 10.1002/j.1538-7305.1949.tb03624.x

R. Kontchakov, F. Wolter, and M. Zakharyaschev, Logic-based ontology comparison and module extraction, with an application to DL-Lite, Artificial Intelligence, vol.174, issue.15, pp.1093-1141, 2010.
DOI : 10.1016/j.artint.2010.06.003

M. Krötzsch, OWL 2 Profiles: An Introduction to Lightweight Ontology Languages, Tutorial Lectures of the 8th International Reasoning Web Summer School, pp.112-183, 2012.
DOI : 10.1007/978-3-642-04930-9_43

M. Krötzsch, S. Rudolph, and P. Hitzler, Complexity boundaries for Horn description logics, Proceedings of the 22nd AAAI Conference on Artificial Intelligence (AAAI), pp.452-457, 2007.

A. Levy, Irrelevance Reasoning in Knowledge Based Systems, 1993.

L. Lubyte and S. Tessaris, Supporting the design of ontologies for data access, Proceedings of the 21st International Description Logic Workshop (DL), 2008.

C. Lutz, The complexity of CQ answering in expressive description logics, Proceedings of the 4th International Joint Conference on Automated Reasoning (IJCAR), pp.179-193, 2008.

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

C. Lutz and F. Wolter, Deciding inseparability and conservative extensions in the description logic <mml:math altimg="si1.gif" display="inline" overflow="scroll" xmlns:xocs="http://www.elsevier.com/xml/xocs/dtd" xmlns:xs="http://www.w3.org/2001/XMLSchema" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns="http://www.elsevier.com/xml/ja/dtd" xmlns:ja="http://www.elsevier.com/xml/ja/dtd" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:tb="http://www.elsevier.com/xml/common/table/dtd" xmlns:sb="http://www.elsevier.com/xml/common/struct-bib/dtd" xmlns:ce="http://www.elsevier.com/xml/common/dtd" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:cals="http://www.elsevier.com/xml/common/cals/dtd"><mml:mi mathvariant="script">E</mml:mi><mml:mi mathvariant="script">L</mml:mi></mml:math>, Journal of Symbolic Computation, vol.45, issue.2, pp.194-228, 2010.
DOI : 10.1016/j.jsc.2008.10.007

C. Lutz and F. Wolter, Non-uniform data complexity of query answering in description logics, Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning (KR), 2012.

B. Motik, B. C. Grau, I. Horrocks, Z. Wu, A. Fokoue et al., OWL 2 Web Ontology Language: Profiles. W3C Recommendation, 2009.

M. Ortiz, D. Calvanese, and T. Eiter, Data Complexity of Query Answering in Expressive Description Logics via Tableaux, Journal of Automated Reasoning, vol.12, issue.2, pp.61-98, 2008.
DOI : 10.1007/s10817-008-9102-9

M. Ortiz and M. Simkus, Reasoning and Query Answering in Description Logics, Proceedings of the 8th International Reasoning Web Summer School, pp.1-53, 2012.
DOI : 10.1016/0022-0000(86)90026-7

M. Ortiz, M. Simkus, and T. Eiter, Worst-case optimal conjunctive query answering for an expressive description logic without inverses, Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI), pp.504-510, 2008.

C. Patel, J. J. Cimino, J. Dolby, A. Fokoue, A. Kalyanpur et al., Matching Patient Records to Clinical Trials Using Ontologies, Proceedings of the 6th International Semantic Web Conference (ISWC), pp.816-829, 2007.
DOI : 10.1007/978-3-540-76298-0_59

H. Pérez-urbina, B. Motik, and I. Horrocks, A comparison of query rewriting techniques for dl-lite, Proceedings of the 22nd International Description Logic Workshop (DL), 2009.

A. Poggi, D. Lembo, D. Calvanese, G. De-giacomo, M. Lenzerini et al., Linking Data to Ontologies, Journal of Data Semantics, vol.10, pp.133-173, 2008.
DOI : 10.1007/978-3-540-77688-8_5

V. R. Pratt, Models of program logics, 20th Annual Symposium on Foundations of Computer Science (sfcs 1979), pp.115-122, 1979.
DOI : 10.1109/SFCS.1979.24

A. A. Romero, M. Kaminski, B. C. Grau, and I. Horrocks, Ontology module extraction via datalog reasoning, Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI), pp.1410-1416, 2015.

S. Tobies, Complexity Results and Practical Algorithms for Logics in Knowledge Representation, 2001.

M. Y. Vardi, Automata theory for database theoreticans, Proceedings of the 7th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), pp.83-92, 1989.

M. Y. Vardi, Reasoning about the past with two-way automata, Proceedings of the 25th International Colloquium on Automata, Languages and Programming (ICALP), pp.628-641, 1998.
DOI : 10.1007/BFb0055090

B. Assume, >(x) is in I i+1 because of an application of Rule 3 involving A v 9r.E 2 T (E 6 = >), that is, there is some y 2 I i such that y 2 A I i and (y, x) 2 r I i+1 \ r I i