Improving efficiency of frequent query discovery by eliminating non-relevant candidates

This paper presents, for Frequent Query Discovery (FQD), an algorithm which employs a novel relation of equivalence in order to remove redundant queries in the output. An FQD algorithm returns a set of frequent queries from a data base of query transactions in DATALOG formalism. A DATALOG data base can represent complex structures, such as hyper graphs, and allows the use of background knowledge. Thus, it is useful in complex domains such as chemistry and bio-informatics. A conventional FQD algorithm, such as WARMR, checks the redundancy of the queries with a relation of equivalence based on the θ-subsumption, which results in discovering a large set of frequent queries. In this work, we reduce the set of frequent queries using another relation of equivalence based on relevance of a query with respect to a data base. The experiments with both real and artificial data sets show that our algorithm is faster than WARMR and the test of relevance can remove up to 92% of the frequent queries.