http://www.cnr.it/ontology/cnr/individuo/prodotto/ID14355

Computational Properties of Metaquerying Problems (Articolo in rivista)

Type

Label

Computational Properties of Metaquerying Problems (Articolo in rivista) (literal)

Anno

Alternative label

Angiulli Fabrizio, Ben-Eliyahu-Zohary Rachel, Ianni Giovambattista, Palopoli Luigi (2003)
Computational Properties of Metaquerying Problems
in Lecture notes in computer science
(literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori

Angiulli Fabrizio, Ben-Eliyahu-Zohary Rachel, Ianni Giovambattista, Palopoli Luigi (literal)

Pagina inizio

Pagina fine

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume

Rivista

Note

Titolo

Abstract

Metaquerying is a data mining technology by which hidden
dependencies among several database relations can be discovered. This tool has already been successfully applied to several real-world applications, but only preliminary results about the complexity of metaquerying can be found in the literature. In this paper we define several variants of metaquerying that encompass, as far as we know, all the variants that have been 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. Nevertheless, 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, it is within TC^0, but lies within AC^0 in some simpler cases. Finally, we discuss the implementation of metaqueries by providing algorithms that answer them.
(literal)

Prodotto di

Prodotto

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi

data.CNR.it