Computing Supports of Conjunctive Queries on Relational Tables with Functional Dependencies

• Autorzy: Jen T-Y. , Laurent D.
• Języki publikacji: EN

Abstrakty

EN

The problem of mining all frequent queries on a relational table is a problem known to be intractable even for conjunctive queries. In this article, we restrict our attention to conjunctive projection-selection queries and we assume that the table to be mined satisfies a set of functional dependencies. Under these assumptions, we define and characterize two pre-orderings with respect to which the support measure is shown to be anti-monotonic. Each of these pre-orderings induces an equivalence relation for which all queries of the same equivalence class have the same support. The goal of this article is not to provide algorithms for the computation of frequent queries, but rather to provide basic properties of pre-orderings and their associated equivalence relations showing that functional dependencies can be used for an optimized computation of supports of conjunctive queries. In particular, we show that one of the two pre-orderings characterizes anti-monotonicity of the support, while the other one refines the former, but allows to characterize anti-monotonicity with respect to a given table, only. Basic computational implications of these properties are discussed in the article.

Słowa kluczowe

EN

functional dependencies; data mining; level-wise algorithms; frequent queries; equivalent queries

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 99, nr 3
• Strony: 263--292
• Opis fizyczny: Bibliogr. 18 poz.

Twórcy

autor

Jen T-Y.

autor

Laurent D.

• Université Cergy-Pontoise --ETIS - CNRS - F-95000 Cergy-Pontoise, France,

Bibliografia

• [1] R. Agrawal, H. Mannila, R. Srikant, H. Toivonen, and A.I. Verkamo. Fast discovery of association rules. In Advances in Knowledge Discovery and Data Mining, pages 309-328. AAAI-MIT Press, 1996.
• [2] W.W. Armstrong. Dependency structures of data base relationships. In IFIP Congress, pages 580-583.North Holland, 1974.
• [3] C. Beeri, M. Downd, R. Fagin, and R. Statman. On the structure of armstrong relations for functional dependencies. Journal of the ACM, 31(1):30-46, 1984.
• [4] Ph. Bohannon, W. Fan, F. Geerts, X. Jia, and A. Kementsietsidis. Conditional functional dependencies for data cleaning. In ICDE, pages 746-755, 2007.
• [5] L. Dehaspe and L. De Raedt. Mining association rules in multiple relations. In 7th International Workshop on Inductive Logic Programming, volume 1297 of LNCS, pages 125-132. Springer Verlag, 1997.
• [6] C.T. Diop, A. Giacometti, D. Laurent, and N. Spyratos. Composition of mining contexts for efficient extraction of association rules. In EDBT'02, volume 2287 of LNCS, pages 106-123. Springer Verlag, 2002.
• [7] A. Faye, A. Giacometti, D. Laurent, and N. Spyratos. Mining rules in databases with multiple tables: Problems and perspectives. In 3rd International Conference on Computing Anticipatory Systems (CASYS), 1999.
• [8] B. Goethals. Mining queries, (unpublished paper). In Workshop on inductive databases and constraint based mining. Available at http://www.informatik.uni-freiburg.de/˜ml/IDB/talks/Goethals_ slides.pdf, 2004.
• [9] B. Goethals and J. Van den Bussche. Relational association rules: getting warmer. In ESF Exploratory Workshop on Pattern Detection and Discovery in Data Mining, volume 2447 of LNCS, pages 125-139. Springer-Verlag, 2002.
• [10] B. Goethals, E. Hoekx, and J. Van den Bussche. Mining tree queries in a graph. In 11th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pages 61-69, 2005.
• [11] B. Goethals,W. Le Page, and H. Mannila. Mining association rules of simple conjunctive queries. In SIAMSDM, pages 96-107, 2008.
• [12] J. Han, Y. Fu, W. Wang, K. Koperski, and O. Zaiane. Dmql : A data mining query language for relational databases. In SIGMOD-DMKD'96, pages 27-34, 1996.
• [13] T.Y. Jen, D. Laurent, and N. Spyratos. Mining all frequent selection-projection queries from a relational table. In EDBT'08, pages 368-379. ACM Press, 2008.
• [14] T.Y. Jen, D. Laurent, and N. Spyratos. Mining frequent conjunctive queries in star schemas. In International Database Engineering and Applications Symposium (IDEAS), pages 97-108. ACM Press, 2009.
• [15] T.Y. Jen, D. Laurent, N. Spyratos, and O. Sy. Towards mining frequent queries in star schemes. In International Workshop on Knowledge Discovery in Databases (KDID), volume 3933 of LNCS, pages 104-123. Springer Verlag, 2005.
• [16] R.Meo, G. Psaila, and S. Ceri. An extension to sql for mining association rules. Data Mining and Knowledge Discovery, 9:275-300, 1997.
• [17] T. Turmeaux, A. Salleb, C. Vrain, and D. Cassard. Learning caracteristic rules relying on quantified paths. In PKDD, volume 2838 of LNCS, pages 471-482. Springer Verlag, 2003.
• [18] J.D. Ullman. Principles of Databases and Knowledge-Base Systems, volume 1. Computer Science Press, 1988.