article

SQL-based discovery of exact and approximate functional dependencies

Authors:

Victor Matos,

Becky GrasserAuthors Info & Claims

ACM SIGCSE Bulletin, Volume 36, Issue 4

Pages 58 - 63

https://doi.org/10.1145/1041624.1041658

Published: 28 June 2004 Publication History

Get Access

Abstract

Students in a typical database course are introduced to theoretical design from a functional dependency standpoint. Functional dependencies are rules of the form X→Y, where X and Y are attributes of a relation r(R). Those rules express the potential one-to-one, and many-to-one relationships among the atributes of R. Unfortunately finding the non-trivial rules X→Y from an existing arbitrary relation is a hard problem. We present an extension of the SQL-based algorithm of Bell and Brockhausen [1] to explore a relation and find its exact and approximate functional dependencies. We use the g3 measure of Kivinen and Mannila to express the degree of approximation of a dependency. This application could be used either as an example or a project in an advanced database course.

References

[1]

Bell. S. Brockhausen, P. {1995}. Discovery of Data Dependencies in Relational Databases. In Kodratoff, Y. Nakhaeizadeh, G., and Taylor C. (eds). Statistics, Machine Learning and Knowledge Discovery in Databases.]]

Google Scholar

[2]

Flach, P. A., Savnik, I. {1999}. Database dependency discovery: a machine learning approach. AI Communications. 12:3(139--160).]]

Digital Library

Google Scholar

[3]

Giannella, C., Robertson, E. {2001}. On an Information Theoretic Approximation Measure for Functional Dependencies. Technical Report TR555. University of Indiana. Bloomington, Indiana.]]

Google Scholar

[4]

Huhtala, Y., Käkkäinen, J., Porkka, P. Toivonen, H. {1998}. Efficient discovery of functional and approximate dependencies using partitions. Proc. International Conference on Data Engineering (ICDE'98). pps. 392--401.]]

Digital Library

Google Scholar

[5]

Huhtala, Y., Käkkäinen, J., Porkka, P. Toivonen, H. {1999}. TANE: An Efficient Algorithm for Discovering Functional and Approximate Dependencies. The Computer Journal. 42:2(100--111).]]

Google Scholar

[6]

Kiniven, J. and Mannila, H., Approximate inference of functional dependencies and Armstrong relations. Theoretical Computer Science, 149(1):129--149, 1995.]]

Digital Library

Google Scholar

[7]

Lopes S., Petit J., Lakhal L., "A framework for understanding existing databases". Proceeding of the International Database Engineering and Applications Symposium. 1098--8068/01, IEEE IDEAS 2001.]]

Digital Library

Google Scholar

[8]

Lopes S., Petit J.-M., and Lakhal, L., Efficient discovery of functional dependencies and armstrong relations. In C. Zaniolo, P. C. Lockemann, M. H. Scholl, and T. Grust, editors, Proceedings of the Sixth International Conference on Extending Database Technology, Konstanz, Germany, volume 1777 of Lecture Notes in Computer Science, pages 350--364. Springer, 2000.]]

Digital Library

Google Scholar

[9]

Maier, D., The Relational Theory of Databases. Computer Science Press. 1983.]]

Google Scholar

[10]

Mannila, H, Raiha K., The Design of Relational Databases. Addison-Wesley, 1994.]]

Digital Library

Google Scholar

[11]

Mannila, H., and Raiha, K. On the complexity of inferring functional dependencies, Discrete Appl. Math. 40 (1992) 237--243.]]

Digital Library

Google Scholar

Cited By

View all

Georgieva T(2019)Discovering branching and fractional dependencies in databasesData & Knowledge Engineering10.1016/j.datak.2008.04.00266:2(311-325)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1016/j.datak.2008.04.002
Kruse SNaumann F(2018)Efficient discovery of approximate dependenciesProceedings of the VLDB Endowment10.14778/3192965.319296811:7(759-772)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.14778/3192965.3192968
Abedjan ZNaumann F(2011)Advancing the discovery of unique column combinationsProceedings of the 20th ACM international conference on Information and knowledge management10.1145/2063576.2063801(1565-1570)Online publication date: 24-Oct-2011
https://dl.acm.org/doi/10.1145/2063576.2063801
Show More Cited By

Recommendations

SQL-based discovery of exact and approximate functional dependencies
ITiCSE-WGR '04: Working group reports from ITiCSE on Innovation and technology in computer science education

Students in a typical database course are introduced to theoretical design from a functional dependency standpoint. Functional dependencies are rules of the form X→Y, where X and Y are attributes of a relation r(R). Those rules express the potential one-...
Design by example for SQL table definitions with functional dependencies

A database is C-Armstrong for a given set of constraints in a class C if it satisfies every constraint of the set and violates every constraint in C not implied by the set. Therefore, Armstrong databases are test data that perfectly illustrate the ...
Mining functional dependencies from data

In this paper, we propose an efficient rule discovery algorithm, called FD_Mine, for mining functional dependencies from data. By exploiting Armstrong's Axioms for functional dependencies, we identify equivalences among attributes, which can be used to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ACM SIGCSE Bulletin Volume 36, Issue 4

December 2004

145 pages

ISSN:0097-8418

DOI:10.1145/1041624

Issue’s Table of Contents

ITiCSE-WGR '04: Working group reports from ITiCSE on Innovation and technology in computer science education
June 2004
152 pages
ISBN:9781450377942
DOI:10.1145/1044550
Publications Chair:
Henry M. Walker
Grinnell College, Grinnell, Iowa

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 28 June 2004

Published in SIGCSE Volume 36, Issue 4

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
623
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)1

Reflects downloads up to 17 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Georgieva T(2019)Discovering branching and fractional dependencies in databasesData & Knowledge Engineering10.1016/j.datak.2008.04.00266:2(311-325)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1016/j.datak.2008.04.002
Kruse SNaumann F(2018)Efficient discovery of approximate dependenciesProceedings of the VLDB Endowment10.14778/3192965.319296811:7(759-772)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.14778/3192965.3192968
Abedjan ZNaumann F(2011)Advancing the discovery of unique column combinationsProceedings of the 20th ACM international conference on Information and knowledge management10.1145/2063576.2063801(1565-1570)Online publication date: 24-Oct-2011
https://dl.acm.org/doi/10.1145/2063576.2063801
Bogdanova GGeorgieva T(2008)Using error-correcting dependencies for collaborative filteringData & Knowledge Engineering10.1016/j.datak.2008.04.00866:3(402-413)Online publication date: 1-Sep-2008
https://dl.acm.org/doi/10.1016/j.datak.2008.04.008
Fotache M(undefined)Why Normalization Failed to Become the Ultimate Guide for Database Designers?SSRN Electronic Journal10.2139/ssrn.905060
https://doi.org/10.2139/ssrn.905060
Engle JRobertson EDesai BSacca DGreco S(2009)Depth first algorithms and inferencing for AFD miningProceedings of the 2009 International Database Engineering & Applications Symposium10.1145/1620432.1620439(54-65)Online publication date: 16-Sep-2009
https://dl.acm.org/doi/10.1145/1620432.1620439
Engle JRobertson E(2008)HLSProceedings of the 25th British national conference on Databases: Sharing Data, Information and Knowledge10.1007/978-3-540-70504-8_4(28-39)Online publication date: 7-Jul-2008
https://dl.acm.org/doi/10.1007/978-3-540-70504-8_4

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Recommendations

SQL-based discovery of exact and approximate functional dependencies

Design by example for SQL table definitions with functional dependencies

Mining functional dependencies from data