Portal de Periódicos da CAPES

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

2006; Springer Science+Business Media; Linguagem: Inglês

10.1007/11965893_28

1611-3349

Michel Leclère, Marie-Laure Mugnier,

Algorithms and Data Compression

Query containment is a fundamental problem of databases. Given two queries q 1 and q 2, it asks whether the set of answers to q 1 is included in the set of answers to q 2 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 q 2, 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.