Global ETD Search

1	Traitement de requêtes conjonctives avec négation : algorithmes et expérimentations Ben Mohamed, Khalil 08 December 2010 (has links) (PDF) Dans cette thèse, nous nous intéressons à des problèmes à la croisée de deux domaines, les bases de données et les bases de connaissances. Nous considérons deux problèmes équivalents concernant les requêtes conjonctives avec négation : l'inclusion de requêtes et l'évaluation d'une requête booléenne sous l'hypothèse du monde ouvert. Nous reformulons ces problèmes sous la forme d'un problème de déduction dans un fragment de la logique du premier ordre. Puis nous raffinons des schémas d'algorithmes déjà existants et proposons de nouveaux algorithmes. Pour les étudier et les comparer expérimentalement, nous proposons un générateur aléatoire et analysons l'influence des différents paramètres sur la difficulté des instances du problème étudié. Finalement, à l'aide de cette méthodologie expérimentale, nous comparons les apports des différents raffinements et les algorithmes entre eux. [INFO:INFO_OH] Computer Science/Other [INFO:INFO_OH] Informatique/Autre Bases de données Bases de connaissances Déduction Négation Requêtes conjonctives avec négation Graphes Homomorphisme Algorithme Heuristiques Expérimentations