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.
Type de document :
Thèse
Artificial Intelligence [cs.AI]. Université de Montpellier, 2016. English
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/tel-01483770
Contributeur : Swan Rocher <>
Soumis le : lundi 6 mars 2017 - 14:22:34
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : mercredi 7 juin 2017 - 14:01:43

Fichier

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

482

Téléchargements de fichiers

288