Computational Properties of Metaquerying Problems Fabrizio Angiulli, Rachel Ben-Eliyahu-Zohary, Giovambattista Ianni, and Luigi Palopoli   View Paper (PDF)   Return to Data Mining / Information Dependencies Abstract 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 very 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), but we are able to single out some tractable interesting metaquerying cases (whose combined complexity is LOGCFL-complete). As for the data complexity of metaquerying, we prove that, in general, this is in P, but lies within AC0 in some interesting cases. Finally, we discuss the issue of equivalence between metaqueries, which is useful for optimization purposes. References Note: References link to DBLP on the Web. [1] Rakesh Agrawal , Tomasz Imielinski , Arun N. Swami : Mining Association Rules between Sets of Items in Large Databases. SIGMOD Conference 1993 : 207-216 [2] Serge Abiteboul , Richard Hull , Victor Vianu : Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0 Contents [3] David A. Mix Barrington , Neil Immerman , Howard Straubing : On Uniformity within NC¹. JCSS 41(3) : 274-306(1990) [4] Catriel Beeri , Ronald Fagin , David Maier , Mihalis Yannakakis : On the Desirability of Acyclic Database Schemes. JACM 30(3) : 479-513(1983) [5] Rachel Ben-Eliyahu-Zohary , Ehud Gudes : Towards Efficient Metaquerying. IJCAI 1999 : 800-805 [6] Ashok K. Chandra , Philip M. Merlin : Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977 : 77-90 [7] Carmel Domshlak , D. Gershkovich , Ehud Gudes , N. Liusternik , Amnon Meisels , T. Rosen , Solomon Eyal Shimony : FlexiMine - A Flexible Platform for KDD Research and Application Construction. KDD 1998 : 184-188 [8] Usama M. Fayyad , Gregory Piatetsky-Shapiro , Padhraic Smyth , Ramasamy Uthurusamy (Eds.): Advances in Knowledge Discovery and Data Mining. AAAI/MIT Press 1996, ISBN 0-262-56097-6 Contents [9] ... [10] Yongjian Fu , Jiawei Han : Meta-Rule-Guided Mining of Association Rules in Relational Databases. KDOOD/TDOOD 1995 : 39-46 [11] M. R. Garey , David S. Johnson : Computer and Intractability: A Guide to NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7 [12] Georg Gottlob , Nicola Leone , Francesco Scarcello : The Complexity of Acyclic Conjunctive Queries. FOCS 1998 : 706-715 [13] Bob Kero , Lucian Russell , Shalom Tsur , Wei-Min Shen : An Overview of Database Mining Techniques. KDOOD/TDOOD 1995 : 1-8 [14] Wei-Min Shen , KayLiang Ong , Bharat G. Mitbander , Carlo Zaniolo : Metaqueries for Data Mining. Advances in Knowledge Discovery and Data Mining 1996 : 375-398 [15] Walter L. Ruzzo : On Uniform Circuit Complexity. JCSS 22(3) : 365-383(1981) [16] ... [17] Wei-Min Shen , Bing Leng : A Metapattern-Based Automated Discovery Loop for Integrated Data Mining - Unsupervised Learning of Relational Patterns. TKDE 8(6) : 898-910(1996) [18] Larry J. Stockmeyer : The Polynomial-Time Hierarchy. TCS 3(1) : 1-22(1976) [19] Moshe Y. Vardi : The Complexity of Relational Query Languages (Extended Abstract). STOC 1982 : 137-146 BIBTEX @inproceedings{DBLP:conf/pods/AngiulliBIP00,   author    = {Fabrizio Angiulli and                 Rachel Ben-Eliyahu-Zohary and                 Giovambattista Ianni and                 Luigi Palopoli},    title     = {Computational Properties of Metaquerying Problems},    booktitle = {Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium                 on Principles of Database Systems, May 15-17, 2000, Dallas, Texas,                 USA},    publisher = {ACM},    year      = {2000},    isbn      = {1-58113-214-X},    pages     = {237-244},    crossref  = {DBLP:conf/pods/00},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, DiSC'01 Copyright ©2002 ACM Inc.