  Metaquerying is a datamining technology by which hidden dependencies among
several database relations can be discovered. This tool has already been
successfully applied to several real-world applications. Recent papers provide
only preliminary results about the complexity of metaquerying. In this paper we
define several variants of metaquerying that encompass, as far as we know, all
variants defined in the literature. We study both the combined complexity and
the data complexity of these variants. We show that, under the combined
complexity measure, metaquerying is generally intractable (unless P=NP), lying
sometimes quite high in the complexity hierarchies (as high as NP^PP),
depending on the characteristics of the plausibility index. However, we are
able to single out some tractable and interesting metaquerying cases (whose
combined complexity is LOGCFL-complete). As for the data complexity of
metaquerying, we prove that, in general, this is in TC0, but lies within AC0 in
some simpler cases. Finally, we discuss implementation of metaqueries, by
providing algorithms to answer them.
