Top

Data Mining and Knowledge Discovery

Published in:

23-12-2019

Mining relaxed functional dependencies from data

Authors: Loredana Caruccio, Vincenzo Deufemia, Giuseppe Polese

Published in: Data Mining and Knowledge Discovery | Issue 2/2020

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Relaxed functional dependencies (rfds) are properties expressing important relationships among data. Thanks to the introduction of approximations in data comparison and/or validity, they can capture constraints useful for several purposes, such as the identification of data inconsistencies or patterns of semantically related data. Nevertheless, rfds can provide benefits only if they can be automatically discovered from data. In this paper we present an rfd discovery algorithm relying on a lattice structured search space, previously used for fd discovery, new pruning strategies, and a new candidate rfd validation method. An experimental evaluation demonstrates the discovery performances of the proposed algorithm on real datasets, also providing a comparison with other algorithms.

previous article Identifying exceptional (dis)agreement between groups

next article Parameterized low-rank binary matrix approximation

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

https://hpi.de/naumann/projects/data-profiling-and-analytics/metanome-data-profiling.html.

The software and the datasets used in the evaluation are available online https://dastlab.github.io/dime/.

http://csxstatic.ist.psu.edu/.

Abedjan Z, Schulze P, Naumann F (2014) DFD: efficient functional dependency discovery. In: Proceedings of the 23rd ACM international conference on information and knowledge management, CIKM ’14, pp 949–958. https://doi.org/10.1145/2661829.2661884

Abedjan Z, Golab L, Naumann F (2015) Profiling relational data: a survey. VLDB J 24(4):557–581. https://doi.org/10.1007/s00778-015-0389-y CrossRef

Arenas M, Libkin L (2004) A normal form for XML documents. ACM Trans Database Syst 29(1):195–232. https://doi.org/10.1145/974750.974757 CrossRef

Berti-Équille L, Harmouch H, Naumann F, Novelli N, Thirumuruganathan S (2018) Discovery of genuine functional dependencies from relational data with missing values. Proc VLDB Endowment 11(8):880–892. https://doi.org/10.14778/3204028.3204032 CrossRef

Blake CL, Merz CJ (1998) UCI repository of machine learning databases. https://archive.ics.uci.edu/ml/index.php

Bohannon P, Fan W, Geerts F, Jia X, Kementsietsidis A (2007) Conditional functional dependencies for data cleaning. In: Proceedings of the 25th international conference on data engineering, ICDE ’07, pp 746–755. https://doi.org/10.1109/ICDE.2007.367920

Caruccio L, Deufemia V, Polese G (2016a) On the discovery of relaxed functional dependencies. In: Proceedings of the 20th international database engineering & applications symposium, IDEAS ’16, pp 53–61. https://doi.org/10.1145/2938503.2938519

Caruccio L, Deufemia V, Polese G (2016b) Relaxed functional dependencies–a survey of approaches. IEEE Trans Knowl Data Eng 28(1):147–165. https://doi.org/10.1109/TKDE.2015.2472010 CrossRef

Caruccio L, Deufemia V, Polese G (2019) Visualization of (multimedia) dependencies from big data. Multimedia Tools and Applications 78(23):33151–33167. https://doi.org/10.1007/s11042-019-07951-0 CrossRef

Chang SK, Deufemia V, Polese G, Vacca M (2007) A normalization framework for multimedia databases. IEEE Trans Knowl Data Eng 19(12):1666–1679. https://doi.org/10.1109/TKDE.2007.190651 CrossRef

Chardin B, Coquery E, Pailloux M, Petit JM (2017) RQL: a query language for rule discovery in databases. Theoret Comput Sci 658:357–374. https://doi.org/10.1016/j.tcs.2016.11.004 MathSciNetCrossRefMATH

Chiang F, Miller RJ (2008) Discovering data quality rules. Proc VLDB Endowment 1(1):1166–1177. https://doi.org/10.14778/1453856.1453980 CrossRef

Elmagarmid AK, Ipeirotis PG, Verykios VS (2007) Duplicate record detection: a survey. IEEE Trans Knowl Data Eng 19(1):1–16. https://doi.org/10.1109/TKDE.2007.250581 CrossRef

Fan W, Geerts F, Lakshmanan LVS, Xiong M (2009) Discovering conditional functional dependencies. In: Proceedings of the 25th international conference on data engineering, ICDE ’09, pp 1231–1234. https://doi.org/10.1109/ICDE.2009.208

Fan W, Gao H, Jia X, Li J, Ma S (2011) Dynamic constraints for record matching. VLDB J 20(4):495–520. https://doi.org/10.1007/s00778-010-0206-6 CrossRef

Flach PA, Savnik I (1999) Database dependency discovery: a machine learning approach. AI Commun 12(3):139–160MathSciNet

Giannella C, Robertson E (2004) On approximation measures for functional dependencies. Inf Syst 29(6):483–507. https://doi.org/10.1016/j.is.2003.10.006 CrossRef

Golab L, Karloff H, Korn F, Srivastava D, Yu B (2008) On generating near-optimal tableaux for conditional functional dependencies. Proc VLDB Endowment 1(1):376–390. https://doi.org/10.14778/1453856.1453900 CrossRef

Huhtala Y, Kärkkäinen J, Porkka P, Toivonen H (1999) TANE: an efficient algorithm for discovering functional and approximate dependencies. Comput J 42(2):100–111. https://doi.org/10.1093/comjnl/42.2.100 CrossRefMATH

Ilyas IF, Markl V, Haas P, Brown P, Aboulnaga A (2004) CORDS: automatic discovery of correlations and soft functional dependencies. In: Proceedings of the 2004 ACM SIGMOD international conference on management of data, SIGMOD ’04, pp 647–658. https://doi.org/10.1145/1007568.1007641

Johnson DS, Garey MR (1979) Computers and intractability: a guide to the theory of NP-completeness. WH Freeman, New YorkMATH

Kim M, Candan KS (2016) Decomposition-by-normalization (DBN): leveraging approximate functional dependencies for efficient CP and tucker decompositions. Data Min Knowl Disc 30(1):1–46. https://doi.org/10.1007/s10618-015-0401-6 MathSciNetCrossRefMATH

King RS, Legendre JJ (2003) Discovery of functional and approximate functional dependencies in relational databases. Adv Decis Sci 7(1):49–59. https://doi.org/10.1155/S117391260300004X MathSciNetCrossRefMATH

Kivinen J, Mannila H (1995) Approximate inference of functional dependencies from relations. Theoret Comput Sci 149(1):129–149. https://doi.org/10.1016/0304-3975(95)00028-U MathSciNetCrossRefMATH

Kleinberg J, Tardos E (2006) Algorithm design. Pearson Education India, New Delhi

Kwashie S, Liu J, Li J, Ye F (2014) Mining differential dependencies: a subspace clustering approach. In: Proceedings of the 25th Australasian database conference, ADC ’14, pp 50–61. https://doi.org/10.1007/978-3-319-08608-8_5

Kwashie S, Liu J, Li J, Ye F (2015) Efficient discovery of differential dependencies through association rules mining. In: Proceedings of the 26th Australasian database conference, ADC ’15, pp 3–15. https://doi.org/10.1007/978-3-319-19548-3_1

Lee ML, Ling TW, Low WL (2002) Designing functional dependencies for XML. In: Proceedings of the 8th international conference on extending database technology, EDBT ’02, pp 124–141. https://doi.org/10.1007/3-540-45876-X_10

Levenshtein VI (1966) Binary codes capable of correcting deletions, insertions, and reversals. Sov Phys Dokl 10(8):707–710MathSciNet

Li J (2006) On optimal rule discovery. IEEE Trans Knowl Data Eng 18(4):460–471. https://doi.org/10.1109/TKDE.2006.1599385 CrossRef

Liu J, Li J, Liu C, Chen Y (2012) Discover dependencies from data–a review. IEEE Trans Knowl Data Eng 24(2):251–264. https://doi.org/10.1109/TKDE.2010.197 CrossRef

Lopes S, Petit JM, Lakhal L (2000) Efficient discovery of functional dependencies and Armstrong relations. In: Proceedings of the 7th international conference on extending database technology, EDBT ’00, pp 350–364. https://doi.org/10.1007/3-540-46439-5_24

Nambiar U, Kambhampati S (2004) Mining approximate functional dependencies and concept similarities to answer imprecise queries. In: Proceedings of the 7th international workshop on the web and databases, WebDB ’04, pp 73–78. https://doi.org/10.1145/1017074.1017093

Novelli N, Cicchetti R (2001) FUN: an efficient algorithm for mining functional and embedded dependencies. In: Proceedings of the 8th international conference database theory, ICDT ’01, pp 189–203. https://doi.org/10.1007/3-540-44503-X_13

Papenbrock T, Naumann F (2016) A hybrid approach to functional dependency discovery. In: Proceedings of the 2016 ACM SIGMOD international conference on management of data, SIGMOD ’16, pp 821–833. https://doi.org/10.1145/2882903.2915203

Papenbrock T, Bergmann T, Finke M, Zwiener J, Naumann F (2015a) Data profiling with Metanome. Proc VLDB Endowment 8(12):1860–1863. https://doi.org/10.14778/2824032.2824086 CrossRef

Papenbrock T, Ehrlich J, Marten J, Neubert T, Rudolph JP, Schönberg M, Zwiener J, Naumann F (2015b) Functional dependency discovery: an experimental evaluation of seven algorithms. Proc VLDB Endowment 8(10):1082–1093. https://doi.org/10.14778/2794367.2794377 CrossRef

Raju KVSVN, Majumdar AK (1988) Fuzzy functional dependencies and lossless join decomposition of fuzzy relational database systems. ACM Trans Database Syst 13(2):129–166. https://doi.org/10.1145/42338.42344 CrossRef

Sánchez D, Serrano JM, Blanco I, Martín-Bautista MJ, Vila MA (2008) Using association rules to mine for strong approximate dependencies. Data Min Knowl Disc 16(3):313–348. https://doi.org/10.1007/s10618-008-0092-3 MathSciNetCrossRef

Song S (2010) Data dependencies in the presence of difference. PhD thesis, The Hong Kong University

Song S, Chen L (2011) Differential dependencies: reasoning and discovery. ACM Trans Database Syst 36:16. https://doi.org/10.1145/2000824.2000826 CrossRef

Song S, Chen L (2013) Efficient discovery of similarity constraints for matching dependencies. Data Knowl Eng 87:146–166. https://doi.org/10.1016/j.datak.2013.06.003 CrossRef

Song S, Chen L, Cheng H (2014) Efficient determination of distance thresholds for differential dependencies. IEEE Trans Knowl Data Eng 26(9):2179–2192. https://doi.org/10.1109/TKDE.2013.84 CrossRef

Song S, Sun Y, Zhang A, Chen L, Wang J (2018) Enriching data imputation under similarity rule constraints. To appear in IEEE transactions on knowledge and data engineering

Szlichta J, Golab L, Srivastava D (2015) On axiomatization and inference complexity over a hierarchy of functional dependencies. In: Proceedings of the 9th Alberto Mendelzon international workshop on foundations of data management, AMW ’15

Vianu V (1987) Dynamic functional dependencies and database aging. J ACM 34(1):28–59. https://doi.org/10.1145/7531.7918 MathSciNetCrossRef

Wyss C, Giannella C, Robertson E (2001) FastFDs: a heuristic-driven, depth-first algorithm for mining functional dependencies from relation instances extended abstract. In: Proceedings of the 3rd international conference on data warehousing and knowledge discovery, DaWaK ’01, pp 101–110. https://doi.org/10.1007/3-540-44801-2_11

Yao H, Hamilton HJ (2007) Mining functional dependencies from data. Data Min Knowl Disc 16(2):197–219. https://doi.org/10.1007/s10618-007-0083-9 MathSciNetCrossRef

Yao H, Hamilton HJ, Butz CJ (2002) FD\_Mine: Discovering functional dependencies in a database using equivalences. In: Proceedings of the 2nd international conference on data mining, ICDM ’02, pp 729–732. https://doi.org/10.1109/ICDM.2002.1184040

Title: Mining relaxed functional dependencies from data
Authors: Loredana Caruccio
Vincenzo Deufemia
Giuseppe Polese
Publication date: 23-12-2019
Publisher: Springer US
Published in: Data Mining and Knowledge Discovery / Issue 2/2020
Print ISSN: 1384-5810
Electronic ISSN: 1573-756X
DOI: https://doi.org/10.1007/s10618-019-00667-7

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 2/2020

SIAS-miner: mining subjectively interesting attributed subgraphs

NegPSpan: efficient extraction of negative sequential patterns with embedding constraints

On normalization and algorithm selection for unsupervised outlier detection

Identifying exceptional (dis)agreement between groups

Integer programming ensemble of temporal relations classifiers

Parameterized low-rank binary matrix approximation

Premium Partner