Enumerating Consistent Metaquery Instantiations

Metaquerying is a data mining technique by which hidden dependencies among several database relations can be discovered in the form of Datalog-like rules, and this technique has already been successfully applied to several real-world application domains. Unfortunately, recent papers have shown that performing metaquerying turns out to be in general quite demanding from the computational viewpoint. The aim of this paper is to illustrate techniques by which metaquerying can be answered as efficiently as possible. Therefore, we first provide some new results regarding the computation of the number of substitutions for a given metaquery. In particular, an important source of complexity of implementing metaquerying relies in the exponential number of variable substitutions potentially to be analyzed to compute results, many of which turn out to be actually redundant. Redundancy checks are therefore illustrated and exploited below in order to minimize the computational cost to be paid to implement metaquerying. Metaquerying result construction algorithms are then given.