, 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
Foundations of Databases, 1994. ,
The theory of joins in relational databases, ACM Trans. Database Syst, vol.4, issue.3, pp.297-314, 1979. ,
Modal Languages and Bounded Fragments of Predicate Logic, J. of Philosophical Logic, vol.27, pp.217-274, 1998. ,
Modal languages and bounded fragments of FOL, 1996. ,
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. ,
, The Description Logic Handbook: Theory, Implementation, and Applications, 2007.
An overview of tableau algorithms for description logics, Studia Logica, vol.69, issue.1, pp.5-40, 2001. ,
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
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
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
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
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
The implication problem for data dependencies, Proceedings of Automata, Languages and Programming, vol.115, pp.73-85, 1981. ,
A Proof Procedure for Data Dependencies, Journal of the ACM, vol.31, issue.4, pp.718-741, 1984. ,
Mededelingen van de Koninklijke Nederlandse Akademie van Wetenschappen, Afdeling Letterkunde, vol.18, issue.13, pp.309-342, 1955. ,
of Studies in Logic and Practical Reasoning, Handbook of Modal Logic, vol.3, 2006. ,
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. ,
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. ,
Taming the infinite chase: Query answering under expressive relational constraints, J. Artif. Intell. Res. (JAIR), vol.48, pp.115-174, 2013. ,
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. ,
Taming the infinite chase: Query answering under expressive relational constraints, J. Artif. Intell. Res. (JAIR), vol.48, pp.115-174, 2013. ,
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. ,
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. ,
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. ,
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. ,
Embedded implicational dependencies and their inference problem, Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing (STOC 1981), pp.342-354, 1981. ,
, Alternation. Journal of the ACM, vol.28, issue.1, pp.114-133, 1981.
, , 2009.
, Graph-based Knowledge Representation and Reasoning-Computational Foundations of Conceptual Graphs. Advanced Information and Knowledge Processing
The Monadic Second-Order Logic of Graphs: I. Recognizable Sets of Finite Graphs, Inf. Comput, vol.85, issue.1, pp.12-75, 1990. ,
The chase revisited, Proceedings of the Twenty-Seventh ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2008, pp.149-158, 2008. ,
Data Exchange: Semantics and Query Answering, Theor. Comput. Sci, vol.336, issue.1, pp.89-124, 2005. ,
Query rewriting and optimization for ontological databases, ACM Trans. Database Syst, vol.39, issue.3, p.25, 2014. ,
Stable model semantics for guarded existential rules and description logics, Principles of Knowledge Representation and Reasoning: Proceedings of the Fourteenth International Conference, 2014. ,
Combining decidability paradigms for existential rules. Theory and Practice of Logic Programming, vol.13, pp.877-892, 2013. ,
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. ,
A tableau decision procedure for SHOIQ, J. Autom. Reasoning, vol.39, issue.3, pp.249-276, 2007. ,
Data complexity of reasoning in very expressive description logics, Proc. 19th Int. Joint Conf. on Artificial Intelligence (IJCAI'05), pp.466-471, 2005. ,
Testing containment of conjunctive queries under functional and inclusion dependencies, J. Comput. Syst. Sci, vol.28, issue.1, pp.167-189, 1984. ,
Consequence-driven reasoning for horn-SHIQ ontologies, IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, pp.2040-2045, 2009. ,
Saying it with Pictures: a logical landscape of conceptual graphs, 2001. ,
Sound, complete and minimal ucq-rewriting for existential rules, 2014. ,
The combined approach to query answering in DL-lite, Principles of Knowledge Representation and Reasoning: Proceedings of the Twelfth International Conference, 2010. ,
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. ,
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. ,
Nominal schemas in description logics: Complexities clarified, Principles of Knowledge Representation and Reasoning: Proceedings of the Fourteenth International Conference, 2014. ,
Complexity Boundaries for Horn Description Logics, Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence, pp.452-457, 2007. ,
Complexities of Horn description logics, ACM Trans. Comput. Logic, vol.14, issue.1, p.36, 2013. ,
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. ,
Inverse roles make conjunctive queries hard, Proceedings of the 2007 International Workshop on Description Logics (DL2007), pp.CEUR-WS, 2007. ,
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. ,
The Theory of Relational Databases, 1983. ,
Testing implications of data dependencies, ACM Trans. Database Syst, vol.4, issue.4, pp.455-469, 1979. ,
, OWL 2 Web Ontology Language: Profiles. W3C Recommendation. Available at, 2009.
Representing ontologies using description logics, description graphs, and rules, Artif. Intell, vol.173, issue.14, pp.1275-1309, 2009. ,
Query answering for OWL DL with rules, Journal of Web Semantics, vol.3, issue.1, pp.41-60, 2005. ,
Worst-case optimal reasoning for the Horn-DL fragments of OWL 1 and 2, 2010. ,
Query answering in the Horn fragments of the description logics SHOIQ and SROIQ, IJCAI, pp.1039-1044, 2011. ,
Linking data to ontologies, J. Data Semantics, vol.10, pp.133-173, 2008. ,
Complexity of the two-variable fragment with counting quantifiers, Journal of Logic, Language and Information, vol.14, pp.369-395, 2005. ,
Foundations of description logics, Reasoning Web, vol.6848, pp.76-136, 2011. ,
The two views on ontological query answering, Proceedings of the 8th Alberto Mendelzon Workshop on Foundations of Data Management, vol.1189, 2014. ,
Nominals, inverses, counting, and conjunctive queries or: Why infinity is your friend!, Journal of Artificial Intelligence Research, vol.39, pp.429-481, 2010. ,
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. ,
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. ,
First-order logic. Dover books on mathematics, 1968. ,
Conjunctive Query Answering Under Existential Rules-Decidability, Complexity, and Algorithms, 2013. ,
URL : https://hal.archives-ouvertes.fr/tel-00925722
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
OWL 2 Web Ontology Language: Document Overview. W3C Recommendation, 2009. ,