Enumerating consistent metaquery instantiations
Fabrizio Angiulli · 2005
Metaquerying is a data mining technique by which hidden dependencies among several database relations can be dis-covered in the form of Datalog-like rules, and this tech-nique 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 view-point. The aim of this paper is to illustrate techniques by which metaquerying can be answered as efficiently as possi-ble. 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 complex-ity 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 re-dundant. Redundancy checks are therefore illustrated and ex-ploited below in order to minimize the computational cost to be paid to implement metaquerying. Metaquerying result construction algorithms are then given.