Les ontologies sont utilisées pour la représentation et l’interrogation de connaissances d’un domaine précis et peuvent être représentées en partie à l’aide des logiques de description légères. Ces ontologies peuvent être issues de plusieurs sources dont les données sont plus ou moins complétés, ainsi certaines données peuvent être incomplètes ou incohérentes empêchant la déduction d’autres données. L’Answer Set Programming (ASP) est un langage de programmation logique non-monotone à base de règles permettant de représenter des données incomplètes mais il ne permet pas de représenter les logiques de description légères. Les règles existentielles généralisent les logiques de description légères et forment aussi un langage de programmation logique mais ne permettant pas la définition d’exceptions. A partir d’une étude théorique d’ASP et des règles existentielles nous proposons de regrouper en un seul formalisme ces deux langages, nous définissons le formalisme des programmes non-monotones existentiels permettant de traiter un programme provenant d’une ontologie avec exceptions. Cette extension a pour but de généraliser à la fois ASP et les règles existentielles et d’utiliser la puissance des solveurs ASP pour raisonner sur des ontologies avec exceptions. Cette étude propose d’approfondir les travaux sur la décidabilité d’un programme avec l’extension aux programmes non-monotones existentiels. Nous proposons aussi d’améliorer les résultats lies à l’interrogation d’un programme ASP ainsi qu’une implémentation d’une extension du solveur ASPeRiX pour traiter les programmes non-monotones existentiels. / Ontologies are meant to represent or to queryknowledge from a precise domain and can berepresented, in part, by logic formalisms such thatdescription logics. These ontologies can be providedby several sources where knowledge is more or lesscomplete, hence some data can be incomplete orincoherent preventing the deduction of other data.Answer Set Programming (ASP) formalism is anon-monotonic logic programming language based onrules, often used in knowledge representation, whichhas the feature to represent incomplete data.However, it’s impossible to represent lite descriptionlogics in ASP, because of existential variables in rules.Existential rules generalize lite description logics andalso form a programmation logic language that butdoesn’t offer the possibility to represent exceptions.Based on a theoritical study of ASP and existentialrules, we propose to gather both languages in aunique formalism, we define non-monotonic existentialprogram allowing to deal with ontology withexceptions. This extension aims to generalize bothASP and existential rules program and to use theefficiency of ASP solvers to reason on ontologies withexceptions. This thesis propose to deepen worksabout entailment and decidability of a non-monotonicexistential program. Another result from this study isthe improvement of interrogation in ASP and theimplementation of an extension of the ASPeRiX solverto deal with non-monotonic existential programs.

La représentation des connaissances et le raisonnement sur le Web sémantique se sont récemment concentrés, pour des raisons pratiques, sur le sous-ensemble de la logique du premier ordre appelé règles existentielles. Dans cette thèse, nous étudions le raisonnement avec des règles existentielles en présence d'informations contradictoires et introduisons un raisonnement existentiel défaisible. Nous proposons trois résultats principaux: Premièrement, nous montrons que les techniques de raisonnement défaisibles classiques doivent être revisitées pour les règles existentielles et étudions leurs défis théoriques et de mise en œuvre. Deuxièmement, nous fournissons une nouvelle structure combinatoire qui permet de capturer diverses variantes du raisonnement défaisable et étudions son expressivité et sa polyvalence. Troisièmement, nous évaluons notre travail par rapport à l'état de l'art dans le traitement des incohérences et des inconsistances dans les règles existentielles et étudions l'intérêt humain de telles techniques de raisonnement. / Knowledge representation and reasoning on the Semantic Web has recently focused, due to practical rationale, on the subset of first order logic called existential rules. In this thesis we investigate reasoning with existential rules in presence of conflicting information and introduce defeasible existential rule reasoning. We provide three main salient results as follows. First we show that classical defeasible reasoning techniques need to be revisited for existential rules and study their theoretical and implementation related challenges. Second, we provide a new combinatorial structure that allows for diverse variants of defeasible reasoning to be captured together and study its expressivity and versatility. Third we evaluate our work with respect to the state of the art in inconsistency handling in existential rules and investigate the human appeal of such reasoning techniques.

Dans cette thèse, nous nous intéressons au problème d'interrogation de bases de connaissances composées de données et d'une ontologie, qui représente des connaissances générales sur le domaine d'application. Parmi les différents formalismes permettant de représenter les connaissances ontologiques, nous considérons ici un fragment de la logique du premier ordre appelé règles existentielles (aussi connues sous le nom de ``tuple generating dependencies'' et Datalog+/-). Le problème fondamental de conséquence logique au cœur de cette thèse demande si une requête conjonctive est conséquence d'une base de connaissances. Les règles existentielles étant très expressives, ce problème est indécidable. Toutefois, différentes restrictions sur les ensembles de règles ont été proposées afin d'obtenir sa décidabilité.La contribution de cette thèse est double. Premièrement, nous proposons un outil qui nous permet d'unifier puis d'étendre la plupart des classes de règles connues reposant sur des notions d'acyclicité assurant la finitude du chaînage avant. Deuxièmement, nous étudions la compatibilité des classes décidables de règles existentielles connues avec un type de connaissance souvent nécessaire dans les ontologies: la transitivité de relations binaires. Nous aidons à clarifier le paysage des résultats positifs et négatifs liés à cette question et fournissons une approche permettant de combiner la transitivité avec les règles existentielles linéaires. / In this thesis we investigate the issue of querying knowledge bases composed of data and general background knowledge, called an ontology. Ontological knowledge can be represented under different formalisms and we consider here a fragment of first-order logic called existential rules (also known as tuple-generating dependencies and Datalog+/-).The fundamental entailment problem at the core of this thesis asks if a conjunctive query is entailed by an existential rule knowledge base. General existential rules are highly expressive, however at the cost of undecidability. Various restrictions on sets of rules have been proposed to regain the decidability of the entailment problem.Our specific contribution is two-fold. First, we propose a new tool that allows to unify and extend most of the known existential rule classes that rely on acyclicity conditions to tame infinite forward chaining, without increasing the complexity of the acyclicity recognition. Second, we study the compatibility of known decidable rule classes with a frequently required modeling construct, namely transitivity of binary relations. We help clarifying the picture of negative and positive results on this question, and provide a technique to safely combine transitivity with one of the simplest, yet useful, decidable rule classes, namely linear rules.

L'objectif du problème appelé "Ontology-based data access" (OBDA) est d'améliorer la réponse à des requêtes en prenant en compte des connaissances d'ordre général durant l'évaluation des requêtes. Ces connaissances générales sont représentées à l'aide d'une ontologie, qui est exprimée dans cette thèse grâce à des formules logiques du premier ordre, appelées règles existentielles, et aussi connues sous le nom de "tuple-generating dependencies" et Datalog+/-. L'expressivité des formules utilisées est telle que l'évaluation de requêtes devient un problème indécidable, et cela a conduit la communauté à définir de nombreux cas décidables, c'est-à-dire des restrictions sur les ensembles de règles existentielles considérés. La contribution de cette thèse est double : tout d'abord, nous proposons une vue unifiée sur une grande fraction des cas décidables connus, et fournissons par là même une analyse de complexité et un algorithme optimal dans le pire des cas. Nous considérons également l'approche couramment utilisée de réécriture de requêtes, et proposons un algorithme générique qui permet de surmonter certaines causes évidentes d'explosion combinatoire qui rendent les approches classiques pratiquement inapplicables. / Ontology-based data access (OBDA) aims at enriching query answering by taking general background knowledge into account when evaluating queries. This background knowledge is represented by means of an ontology, that is expressed in this thesis by a very expressive class of first-order formulas, called existential rules (sometimes also tuple-generating dependencies and Datalog+/-). The high expressivity of the used formalism results in the undecidability of query answering, and numerous decidable classes (that is, restrictions on the sets of existential rules) have been proposed in the literature. The contribution of this thesis is two-fold: first, we propose a unified view of a large part of these classes, together with a complexity analysis and a worst-case optimal algorithm for the introduced generic class. Second, we consider the popular approach of query rewriting, and propose a generic algorithm that overcomes trivial causes of combinatorial explosion that make classical approaches inapplicable.

Ontological database management systems are a powerful tool that combine traditional database techniques with ontological reasoning methods. In this setting, a classical extensional database is enriched with an ontology, or a set of logical assertions, that describe how new, intensional knowledge can be derived from the extensional data. Conjunctive queries are therefore answered against this combined knowledge base of extensional and intensional data. Many languages that represent ontologies have been introduced in the literature. In this thesis we will focus on existential rules (also called tuple-generating dependencies or Datalog^± rules), and three established languages in this area, namely guarded-based rules, sticky rules and weakly-acyclic rules. The main goal of the thesis is to enrich these languages with non-deterministic constructs (i.e. disjunctions) and investigate the complexity of the answering conjunctive queries under these extended languages. As is common in the literature, we will distinguish between combined complexity, where the database, the ontology and the query are considered as input, and data complexity, where only the database is considered as input. The latter case is relevant in practice, as usually the ontology and the query can be considered as fixed, and are usually much smaller than the database itself. After giving appropriate definitions to extend the considered languages to disjunctive existential rules, we establish a series of complexity results, completing the complexity picture for each of the above languages, and four different query languages: arbitrary conjunctive queries, bounded (hyper-)treewidth queries, acyclic queries and atomic queries. For the guarded-based languages, we show a strong 2EXPTIME lower bound for general queries that holds even for fixed ontologies, and establishes 2EXPTIME-completeness of the query answering problem in this case. For acyclic queries, the complexity can be reduced to EXPTIME, if the predicate arity is bounded, and the problem even becomes tractable for certain restricted languages, if only atomic queries are used. For ontologies represented by sticky disjunctive rules, we show that the problem becomes undecidable, even in the case of data complexity and atomic queries. Finally, for weakly-acyclic rules, we show that the complexity increases from 2EXPTIME to coN2EXPTIME in general, and from tractable to coNP in case of the data complexity, independent of which query language is used. After answering the open complexity questions, we investigate applications and relevant consequences of our results for description logics and give two generic complexity statements, respectively, for acyclic and general conjunctive query answering over description logic knowledge bases. These generic results allow for an easy determination of the complexity of this reasoning task, based on the expressivity of the considered description logic.