Abstract
Differential dependencies (DDs) extend functional dependencies (FDs) to capture the semantics of distance among data values. To mine DDs in a given relation is, thus, more challenging as the more general definition of DDs creates: a combinatorial large search space; and hugely sized minimal cover sets of DDs. This paper proposes a simple, yet effective and efficient approach to mine DDs in a given relation. We study and present a link between DDs and association rules (ARs): paving way for the adoption of existing ARs mining algorithms in the discovery of DDs. Furthermore, we propose a measure of interestingness for DDs to aid the discovery of essential DDs and avoid mining an extremely large set. Finally, we show the efficiency and scalability of our solution through experiments on three real-world benchmark data sets. The results indicate that our discovery approach is efficient and scalable.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Agrawal, R., Imieliski, T., Swami, A.: Mining Association Rules between Sets of Items in Large Databases. SIGMOD Rec. 22(2), 207–216 (1993)
Borgelt, C., Kruse, R.: Induction of association rules: apriori implementation. In: 15th Conference on Computational Statistics, pp. 395–400 (2002)
Chakravarthy, U.S., Grant, J., Minker, J.: Logic-based Approach to Semantic Query Optimization. ACM Trans. Database Syst. 15(2), 162–207 (1990)
Fan, W., Geerts, F., Li, J., Xiong, M.: Discovering Conditional Functional Dependencies. IEEE Trans. Knowl. Data Eng. 23(5), 683–698 (2011)
Fan, W., Jia, X., Li, J., Ma, S.: Reasoning about Record Matching Rules. PVLDB 2(1), 407–418 (2009)
Golab, L., Karloff, H., Korn, F., Srivastava, D., Yu, B.: On Generating Near-optimal Tableaux for Conditional Functional Dependencies. Proc. VLDB Endow. 1(1), 376–390 (2008)
Huhtala, Y., Krkkinen, J., Porkka, P., Toivonen, H.: Tane: An Efficient Algorithm for Discovering Functional and Approximate Dependencies. The Computer Journal 42(2), 100–111 (1999)
Koudas, N., Saha, A., Srivastava, D., Venkatasubramanian, S.: Metric functional dependencies. In: 25th International Conference on Data Engineering, pp. 1275–1278. IEEE Computer Society (2009)
Kwashie, S., Liu, J., Li, J., Ye, F.: Mining differential dependencies: a subspace clustering approach. In: Wang, H., Sharaf, M.A. (eds.) ADC 2014. LNCS, vol. 8506, pp. 50–61. Springer, Heidelberg (2014)
Li, J.: On optimal Rule Discovery. IEEE Trans. on Knowledge and Data Engineering 18(4), 460–471 (2006)
Li, J., Liu, J., Toivonen, H., Yong, J.: Effective Pruning for the Discovery of Conditional Functional Dependencies. Computer Journal 56(3), 378–392 (2013)
Liu, J., Ye, F., Li, J., Wang, J.: On Discovery of Functional Dependencies from Data. Data & Knowledge Engineering 86, 146–159 (2013)
Novelli, N., Cicchetti, R.: FUN: an efficient algorithm for mining functional and embedded dependencies. In: Van den Bussche, J., Vianu, V. (eds.) ICDT 2001. LNCS, vol. 1973, pp. 189–203. Springer, Heidelberg (2000)
Song, S., Chen, L.: Discovering matching dependencies. In: 18th ACM Conference on Information and Knowledge Management, pp. 1421–1424 (2009)
Song, S., Chen, L.: Differential Dependencies: Reasoning and Discovery. ACM Trans. Database Syst. 36(3), 16:1–16:41 (2011)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Kwashie, S., Liu, J., Li, J., Ye, F. (2015). Efficient Discovery of Differential Dependencies Through Association Rules Mining. In: Sharaf, M., Cheema, M., Qi, J. (eds) Databases Theory and Applications. ADC 2015. Lecture Notes in Computer Science(), vol 9093. Springer, Cham. https://doi.org/10.1007/978-3-319-19548-3_1
Download citation
DOI: https://doi.org/10.1007/978-3-319-19548-3_1
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-19547-6
Online ISBN: 978-3-319-19548-3
eBook Packages: Computer ScienceComputer Science (R0)