Analysis of existing databases at the logical level: the DBA companion project

ABSTRACT

Whereas physical database tuning has received a lot of attention over the last decade, logical database tuning seems to be under-studied. We have developed a project called DBA Companion devoted to the understanding of logical database constraints from which logical database tuning can be achieved.In this setting, two main data mining issues need to be addressed: the first one is the design of efficient algorithms for functional dependencies and inclusion dependencies inference and the second one is about the interestingness of the discovered knowledge. In this paper, we point out some relationships between database analysis and data mining. In this setting, we sketch the underlying themes of our approach. Some database applications that could benefit from our project are also described, including logical database tuning.

REFERENCES

• 1: Catriel Beeri , Martin Dowd , Ronald Fagin , Richard Statman, On the Structure of Armstrong Relations for Functional Dependencies, Journal of the ACM (JACM), v.31 n.1, p.30-46, Jan. 1984 [doi>10.1145/2422.322414]
• 2: Phil Bernstein , Michael Brodie , Stefano Ceri , David DeWitt , Mike Franklin , Hector Garcia-Molina , Jim Gray , Jerry Held , Joe Hellerstein , H. V. Jagadish , Michael Lesk , Dave Maier , Jeff Naughton , Hamid Pirahesh , Mike Stonebraker , Jeff Ullman, The Asilomar report on database research, ACM SIGMOD Record, v.27 n.4, p.74-80, Dec. 1998 [doi>10.1145/306101.306137]
• 3: Qi Cheng , Jarek Gryz , Fred Koo , T. Y. Cliff Leung , Linqi Liu , Xiaoyan Qian , K. Bernhard Schiefer, Implementation of Two Semantic Query Optimization Techniques in DB2 Universal Database, Proceedings of the 25th International Conference on Very Large Data Bases, p.687-698, September 07-10, 1999
• 4: Fabien De Marchi , Stéphane Lopes , Jean-Marc Petit, Efficient Algorithms for Mining Inclusion Dependencies, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.464-476, March 25-27, 2002
• 5: Fabien De Marchi , Stéphane Lopes , Jean-Marc Petit, Samples for Understanding Data-Semantics in Relations, Proceedings of the 13th International Symposium on Foundations of Intelligent Systems, p.565-573, June 27-29, 2002
• 6: F. De Marchi and J-M. Petit. Construction de petites bases de données d'Armstrong informatives. Revue d'intelligence artificielle RSTI-RIA (from EGC'03), 17:31--42, Jan. 2003.
• 7: J. Demetrovics and V.D. Thi. Some remarks on generating Armstrong and inferring functional dependencies relation. Acta Cybernetica, 12(2):167--180, 1995.
• 8: Ronald Fagin. Armstrong databases. Technical Report 5, IBM Research Laboratory, 1982.
• 9: G. Gottlob and L. Libkin. Investigations on Armstrong relations, dependency inference, and excluded functional dependencies. Acta Cybernetica, 9(4):385--402, 1990.
• 10: Jarek Gryz, Query Folding with Inclusion Dependencies, Proceedings of the Fourteenth International Conference on Data Engineering, p.126-133, February 23-27, 1998
• 11: Y. Huhtala, J. Kärkkäinen, P. Porkka, and H. Toivonen. Tane: An efficient algorithm for discovering functional and approximate dependencies. The Computer Journal, 42(3):100--111, 1999.
• 12: M. Kantola, H. Mannila, K-J. Räihä, and H. Siirtola. Discovering functional and inclusion dependencies in relational databases. Int. Journal of Intelligent Systems, 7:591--607, 1992.
• 13: Mark Levene , George Loizou, Guaranteeing no interaction between functional dependencies and tree-like inclusion dependencies, Theoretical Computer Science, v.254 n.1-2, p.683-690, March 6, 2001 [doi>10.1016/S0304-3975(00)00394-7]
• 14: S. Lopes, F. De Marchi, and J-M. Petit. DBA companion: un outil pour l'analyse de bases de données (demo session). In BDA '2002 (French database conference), pages 523--528, 2002.
• 15: S. Lopes, J-M. Petit, and L. Lakhal. Functional and approximate dependencies mining: Databases and FCA point of view. Special issue of JETAI, 14(2/3):93--114, 2002.
• 16: Stéphane Lopes , Jean-Marc Petit , Farouk Toumani, Discovering interesting inclusion dependencies: application to logical database tuning, Information Systems, v.27 n.1, p.1-19, March 2002 [doi>10.1016/S0306-4379(01)00027-8]
• 17: Heikki Mannila , Kari-Jouko Räihä, Design by exmple: An application of Armstrong relations, Journal of Computer and System Sciences, v.33 n.2, p.126-141, Oct. 1986 [doi>10.1016/0022-0000(86)90015-2]
• 18: Heikki Mannila , Kari-Jouko Räihä, Algorithms for inferring functional dependencies from relations, Data & Knowledge Engineering, v.12 n.1, p.83-99, Feb. 1994 [doi>10.1016/0169-023X(94)90023-X]
• 19: Renée J. Miller , Mauricio A. Hernández , Laura M. Haas , Lingling Yan , C. T. Howard Ho , Ronald Fagin , Lucian Popa, The Clio project: managing heterogeneity, ACM SIGMOD Record, v.30 n.1, p.78-83, March 2001 [doi>10.1145/373626.373713]
• 20: Functional and embedded dependency inference: a data mining point of view, Information Systems, v.26 n.7, p.477-506, November 2001 [doi>10.1016/S0306-4379(01)00032-1]
• 21: Jean-Marc Petit , Farouk Toumani , Jean-Francois Boulicaut , Jacques Kouloumdjian, Towards the Reverse Engineering of Denormalized Relational Databases, Proceedings of the Twelfth International Conference on Data Engineering, p.218-227, February 26-March 01, 1996
• 22: AutoAdmin project. Microsoft research, http://www.research.microsoft.com/dmx/autoadmin.
• 23: A. M. Silva and M. A. Melkanoff. A method for helping discover the dependencies of a relation. In Hervé Gallaire, Jean-Marie Nicolas, and Jack Minker, editors, Advances in Data Base Theory, pages 115--133, Toulouse, France, 1979.