Estimating the confidence of conditional functional dependencies

ABSTRACT

Conditional functional dependencies (CFDs) have recently been proposed as extensions of classical functional dependencies that apply to a certain subset of the relation, as specified by a pattern tableau. Calculating the support and confidence of a CFD (i.e., the size of the applicable subset and the extent to which it satisfies the CFD)gives valuable information about data semantics and data quality. While computing the support is easier, computing the confidence exactly is expensive if the relation is large, and estimating it from a random sample of the relation is unreliable unless the sample is large.

We study how to efficiently estimate the confidence of a CFD with a small number of passes (one or two) over the input using small space. Our solutions are based on a variety of sampling and sketching techniques, and apply when the pattern tableau is known in advance, and also the harder case when this is given after the data have been seen. We analyze our algorithms, and show that they can guarantee a small additive error; we also show that relative errors guarantees are not possible. We demonstrate the power of these methods empirically, with a detailed study using both real and synthetic data. These experiments show that it is possible to estimate the CFD confidence very accurately with summaries which are much smaller than the size of the data they represent.

REFERENCES

• 1: M. Arlitt and T. Jin. 1998 world cup web site access logs. http://www.acm.org/sigcomm/ITA/, 1998.
• 2: Lakshminath Bhuvanagiri , Sumit Ganguly , Deepanjan Kesh , Chandan Saha, Simpler algorithm for estimating frequency moments of data streams, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.708-713, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109634]
• 3: Loreto Bravo , Wenfei Fan , Floris Geerts , Shuai Ma, Increasing the Expressivity of Conditional Functional Dependencies without Extra Complexity, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.516-525, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497460]
• 4: Loreto Bravo , Wenfei Fan , Shuai Ma, Extending dependencies with conditions, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 5: Andrei Z. Broder , Moses Charikar , Alan M. Frieze , Michael Mitzenmacher, Min-wise independent permutations (extended abstract), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.327-336, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276781]
• 6: Joshua Brody and Amit Chakrabarti. A multi-round communication lower bound for gap hamming and some consequences. CoRR, abs/0902.2399, 2009.
• 7: Paul G. Brown , Peter J. Hass, BHUNT: automatic discovery of Fuzzy algebraic constraints in relational data, Proceedings of the 29th international conference on Very large data bases, p.668-679, September 09-12, 2003, Berlin, Germany
• 8: Paul G. Brown , Peter J. Haas, Techniques for Warehousing of Sample Data, Proceedings of the 22nd International Conference on Data Engineering, p.6, April 03-07, 2006 [doi>10.1109/ICDE.2006.157]
• 9: Bin Chen , Peter Haas , Peter Scheuermann, A new two-phase sampling based algorithm for discovering association rules, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775114]
• 10: Fei Chiang , Renée J. Miller, Discovering data quality rules, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453980]
• 11: Gao Cong , Wenfei Fan , Floris Geerts , Xibei Jia , Shuai Ma, Improving data quality: consistency and accuracy, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 12: Graham Cormode , S. Muthukrishnan, Space efficient mining of multigraph streams, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065201]
• 13: G. Cormode and S. Muthukrishnan. Summarizing and mining skewed data streams. In SIAM Conference on Data Mining, 2005.
• 14: Wenfei Fan , Floris Geerts , Xibei Jia , Anastasios Kementsietsidis, Conditional functional dependencies for capturing data inconsistencies, ACM Transactions on Database Systems (TODS), v.33 n.2, p.1-48, June 2008 [doi>10.1145/1366102.1366103]
• 15: Wenfei Fan , Floris Geerts , Laks V. S. Lakshmanan , Ming Xiong, Discovering Conditional Functional Dependencies, Proceedings of the 2009 IEEE International Conference on Data Engineering, p.1231-1234, March 29-April 02, 2009 [doi>10.1109/ICDE.2009.208]
• 16: Wenfei Fan , Shuai Ma , Yanli Hu , Jie Liu , Yinghui Wu, Propagating functional dependencies with conditions, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453901]
• 17: Rainer Gemulla , Wolfgang Lehner , Peter J. Haas, A dip in the reservoir: maintaining sample synopses of evolving datasets, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 18: Lukasz Golab, Howard Karloff, Flip Korn, Divesh Srivastava, and Bei Yu. On generating near-optimal tableaux for conditional functional dependencies. In International Conference on Very Large Data Bases, 2008.
• 19: Y. Huhtala, J. Karkkainen, P. Porkka, and H. Toivonen. TANE: An efficient algorithm for discovering functional and approximate dependencies. The Computer Journal, 42(2):100--111, 1999.
• 20: Ihab F. Ilyas , Volker Markl , Peter Haas , Paul Brown , Ashraf Aboulnaga, CORDS: automatic discovery of correlations and soft functional dependencies, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007641]
• 21: T. S. Jayram, Ravi Kumar, and D. Sivakumar. The one-way communication complexity of hamming distance. Theory of Computing, 4(1):129--135, 2008.
• 22: Jyrki Kivinen , Heikki Mannila, The power of sampling in knowledge discovery, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.77-85, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182601]
• 23: Jyrki Kivinen , Heikki Mannila, Approximate inference of functional dependencies from relations, Theoretical Computer Science, v.149 n.1, p.129-149, Sept. 18, 1995
• 24: Eyal Kushilevitz , Noam Nisan, Communication complexity, Cambridge University Press, New York, NY, 1996
• 25: A. Metwally, D. Agrawal, and A. El Abbadi. Efficient computation of frequent and top-k elements in data streams. In International Conference on Database Theory, 2005.
• 26: Hannu Toivonen, Sampling Large Databases for Association Rules, Proceedings of the 22th International Conference on Very Large Data Bases, p.134-145, September 03-06, 1996
• 27: Jeffrey S. Vitter, Random sampling with a reservoir, ACM Transactions on Mathematical Software (TOMS), v.11 n.1, p.37-57, March 1985 [doi>10.1145/3147.3165]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration
          Subjects: Data warehouse and repository

General Terms:
Algorithms, Management, Theory

Keywords:
conditional functional dependencies