On generating near-optimal tableaux for conditional functional dependencies

ABSTRACT

Conditional functional dependencies (CFDs) have recently been proposed as a useful integrity constraint to summarize data semantics and identify data inconsistencies. A CFD augments a functional dependency (FD) with a pattern tableau that defines the context (i.e., the subset of tuples) in which the underlying FD holds. While many aspects of CFDs have been studied, including static analysis and detecting and repairing violations, there has not been prior work on generating pattern tableaux, which is critical to realize the full potential of CFDs.

This paper is the first to formally characterize a "good" pattern tableau, based on naturally desirable properties of support, confidence and parsimony. We show that the problem of generating an optimal tableau for a given FD is NP-complete but can be approximated in polynomial time via a greedy algorithm. For large data sets, we propose an "on-demand" algorithm providing the same approximation bound, that outperforms the basic greedy algorithm in running time by an order of magnitude. For ordered attributes, we propose the range tableau as a generalization of a pattern tableau, which can achieve even more parsimony. The effectiveness and efficiency of our techniques are experimentally demonstrated on real data.

REFERENCES

• 1: Deepak Agarwal , Dhiman Barman , Dimitrios Gunopulos , Neal E. Young , Flip Korn , Divesh Srivastava, Efficient and effective explanation of change in hierarchical summaries, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281197]
• 2: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, ACM SIGMOD Record, v.22 n.2, p.207-216, June 1, 1993
• 3: Piotr Berman , Marek Karpinski, On Some Tighter Inapproximability Results (Extended Abstract), Proceedings of the 26th International Colloquium on Automata, Languages and Programming, p.200-209, July 11-15, 1999
• 4: P. Bohannon, W. Fan, F. Geerts, X. Jia, and A. Kementsietsidis. Conditional functional dependencies for data cleaning. In ICDE, 2007.
• 5: 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
• 6: 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
• 7: Toon Calders , Raymond T. Ng , Jef Wijsen, Searching for dependencies at multiple abstraction levels, ACM Transactions on Database Systems (TODS), v.27 n.3, p.229-260, September 2002 [doi>10.1145/581751.581752]
• 8: Stefano Ceri , Francesco Di Giunta , Pier Luca Lanzi, Mining constraint violations, ACM Transactions on Database Systems (TODS), v.32 n.1, p.6-es, March 2007 [doi>10.1145/1206049.1206055]
• 9: 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
• 10: Mehmet M. Dalkilic , Edward L. Roberston, Information dependencies, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.245-253, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.336059]
• 11: Rajiv Gandhi , Samir Khuller , Aravind Srinivasan, Approximation algorithms for partial covering problems, Journal of Algorithms, v.53 n.1, p.55-84, October 2004 [doi>10.1016/j.jalgor.2004.04.002]
• 12: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 13: Chris Giannella , Edward Robertson, On approximation measures for functional dependencies, Information Systems, v.29 n.6, p.483-507, September 2004 [doi>10.1016/j.is.2003.10.006]
• 14: 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.
• 15: 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]
• 16: Michael J. Kearns , Umesh V. Vazirani, An introduction to computational learning theory, MIT Press, Cambridge, MA, 1994
• 17: R. King and J. Legendre. Discovery of functional and approximate functional dependencies in relational databases. Journal of Applied Mathematics and Decision Sciences, 7(1):49--59, 2003.
• 18: Jyrki Kivinen , Heikki Mannila, Approximate inference of functional dependencies from relations, Theoretical Computer Science, v.149 n.1, p.129-149, Sept. 18, 1995
• 19: Ullas Nambiar , Subbarao Kambhampati, Mining approximate functional dependencies and concept similarities to answer imprecise queries, Proceedings of the 7th International Workshop on the Web and Databases: colocated with ACM SIGMOD/PODS 2004, June 17-18, 2004, Paris, France [doi>10.1145/1017074.1017093]
• 20: Sunita Sarawagi, Explaining Differences in Multidimensional Aggregates, Proceedings of the 25th International Conference on Very Large Data Bases, p.42-53, September 07-10, 1999
• 21: Ramakrishnan Srikant , Rakesh Agrawal, Mining quantitative association rules in large relational tables, ACM SIGMOD Record, v.25 n.2, p.1-12, June 1996
• 22: Y. Xu and R. Motwani. Random sampling based algorithms for efficient semi-key discovery. Stanford University Technical Report.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Generating functions

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration
          Subjects: Security, integrity, and protection
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Pattern analysis

General Terms:
Algorithms, Design, Management, Performance, Security