Nous considérons le problème de déduction dans le frag- ment existentiel conjonctif muni de la négation atomique en logique du premier ordre. Ce problème peut être reformulé en termes d'autres problèmes en bases de données et en in- telligence artificielle : l'inclusion de requêtes, l'implication de clauses et la déduction dans un fragment des graphes conceptuels. Partant des résultats de Leclère et Mugnier (ICDT 07), nous raffinons leur schéma d'algorithme et tes- tons expérimentalement différentes heuristiques. L'article décrit notre démarche et présente les résultats expérimen- taux obtenus.