Processing of Conjunctive Queries with Negation: Algorithms and Experiments
| Autor: | Ben Mohamed, Khalil |
|---|---|
| Přispěvatelé: | Graphs for Inferences on Knowledge (GRAPHIK), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université Montpellier II - Sciences et Techniques du Languedoc, Marie-Laure Mugnier(mugnier@lirmm.fr), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Inria Sophia Antipolis - Méditerranée (CRISAM) |
| Jazyk: | francouzština |
| Rok vydání: | 2010 |
| Předmět: |
Knowledge bases
Bases de connaissances Conjunctive Queries with Negation [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH] Bases de données Déduction Algorithme Expérimentations Algorithm Heuristiques Databases Graphes Requêtes conjonctives avec négation Homomorphisme Homomorphism Heuristics Négation Experiments Graphs |
| Zdroj: | Autre [cs.OH]. Université Montpellier II-Sciences et Techniques du Languedoc, 2010. Français Autre [cs.OH]. Université Montpellier II-Sciences et Techniques du Languedoc, 2010. Français. ⟨NNT : ⟩ |
| Popis: | In this thesis, we consider problems at the intersection of two areas: databases and knowledge bases. We focus on two equivalent problems on conjunctive queries with negation: query containment and query answering with boolean queries while making the open-world assumption. We reformulate these problems as a deduction problem in a first-order logic fragment. Then we refine existing algorithm schemes and propose new algorithms. To study and compare them experimentally, we propose a random generator and we analyze the influence of parameters on problem instances difficulty. Finally, we analyze the improvements brought out by our refinements and we compare experimentally the algorithms.; 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|