Some Algorithmic Improvments for the Containment Problem of Conjunctive Queries with Negation

Michel Leclère 1 Marie-Laure Mugnier 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
Abstract : Query containment is a fundamental problem of databases. Given two queries q1 and q2, it asks whether the set of answers to q1 is included in the set of answers to q2 for any database. In this paper, we investigate this problem for conjunctive queries with negated subgoals. We use graph homomorphism as the core notion, which leads us to extend the results presented in [Ull97] and [WL03]. First, we exhibit sufficient (but not necessary) conditions for query containment based on special subgraphs of q2, which generalize that proposed in [WL03]. As a corollary, we obtain a case where the time complexity of the problem decreases. From a practical viewpoint, these properties can be exploited in algorithms, as shown in the paper. Second, we propose an algorithm based on the exploration of a space of graphs, which improves existing algorithms.
Keywords : Query Containment
Type de document :
Communication dans un congrès
ICDT: International Conference on Database Theory, Jan 2007, Barcelona, Spain. Springer, 11th International Conference on Database Theory, LNCS (4353), pp.404-418, 2007, Database Theory – ICDT 2007. 〈10.1007/11965893_28〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00135448
Contributeur : Michel Leclère <>
Soumis le : mercredi 7 mars 2007 - 16:41:19
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Lien texte intégral

Identifiants

Collections

Citation

Michel Leclère, Marie-Laure Mugnier. Some Algorithmic Improvments for the Containment Problem of Conjunctive Queries with Negation. ICDT: International Conference on Database Theory, Jan 2007, Barcelona, Spain. Springer, 11th International Conference on Database Theory, LNCS (4353), pp.404-418, 2007, Database Theory – ICDT 2007. 〈10.1007/11965893_28〉. 〈lirmm-00135448〉

Partager

Métriques

Consultations de la notice

124