Caractérisation de l'anti-monotonie du support des requêtes projection-sélection sur une table relationnelle en présence de dépendances fonctionnelles
Résumé
In this paper we study the problem of mining all frequent queries in a relational table, a problem known to be intractable even for conjunctive queries. We restrict our attention to projection-selection queries and we assume that the table to be mined satis- es a set of functional dependencies. Under these assumptions we dene two preorderings with respect to which the support measure is shown to be anti-monotonic. Moreover, each of these pre-orderings induces an equivalence relation for which all queries of the same equivalence class have the same support. The goal of this paper is not to provide algorithms for the computation of frequent queries, but rather to characterize the preorderings and their associated equivalence relations. Basic computational implications of these characterizations are discussed in the paper, based on our previous work.