Skip to Main content Skip to Navigation
Theses

Querying Existential Rule Knowledge Bases: Decidability and Complexity

Swan Rocher 1
1 GRAPHIK - Graphs for Inferences on Knowledge
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier, CRISAM - Inria Sophia Antipolis - Méditerranée
Résumé : 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 coeur 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.
Document type :
Theses
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/tel-01483770
Contributor : Swan Rocher <>
Submitted on : Monday, March 6, 2017 - 2:22:34 PM
Last modification on : Friday, May 17, 2019 - 11:41:28 AM
Document(s) archivé(s) le : Wednesday, June 7, 2017 - 2:01:43 PM

Identifiers

  • HAL Id : tel-01483770, version 1

Collections

Citation

Swan Rocher. Querying Existential Rule Knowledge Bases: Decidability and Complexity. Artificial Intelligence [cs.AI]. Université de Montpellier, 2016. English. ⟨tel-01483770⟩

Share

Metrics

Record views

646

Files downloads

545