Information dependencies

ABSTRACT

This paper uses the tools of information theory to examine and reason about the information content of the attributes within a relation instance. For two sets of attributes X and Y, an information dependency measure (InD measure) characterizes the uncertainty remaining about the values for the set Y when the values for the set X are known. A variety of arithmetic inequalities (InD inequalities) are shown to hold among InD measures; InD inequalities hold in any relation instance. Numeric constraints (InD constraints) on InD measures, consistent with the InD inequalities, can be applied to relation instances. Remarkably, functional and multivalued dependencies correspond to setting certain constraints to zero, with Armstrong's axioms shown to be consequences of the arithmetic inequalities applied to constraints. As an analog of completeness, for any set of constraints consistent with the inequalities, we may construct a relation instance that approximates these constraints within any positive &egr;. InD measures suggest many valuable applications in areas such as data mining.

REFERENCES

• 1: R. G. Bartle. The Elements of Real Analysis Second Edition. John Wiley & Sons, Inc., New York, New York, 1976.
• 2: Kevin Beyer , Raghu Ramakrishnan, Bottom-up computation of sparse and Iceberg CUBE, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.359-370, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 3: Christos Faloutsos , H. V. Jagadish , Nikolaos Sidiropoulos, Recovering Information from Summary Data, Proceedings of the 23rd International Conference on Very Large Data Bases, p.36-45, August 25-29, 1997
• 4: G. Piatetsky-Shapiro. Probabilistic data dependencies. In Machine Discovery Workshop (Aberdeen, Scotland), 1992.
• 5: Usama M. Fayyad , Gregory Piatetsky-Shapiro , Padhraic Smyth, From data mining to knowledge discovery: an overview, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
• 6: S. Ginsburg and R. Hull. Characterizations for functional dependency and boyce-codd normal form families. In Theoretical Computer Science, volume 26, pages 243-286, 1983.
• 7: Jim Gray , Surajit Chaudhuri , Adam Bosworth , Andrew Layman , Don Reichart , Murali Venkatrao , Frank Pellow , Hamid Pirahesh, Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals, Data Mining and Knowledge Discovery, v.1 n.1, p.29-53, 1997 [doi>10.1023/A:1009726021843]
• 8: Jyrki Kivinen , Heikki Mannila, Approximate inference of functional dependencies from relations, Theoretical Computer Science, v.149 n.1, p.129-149, Sept. 18, 1995
• 9: J. R. Quinlan, Induction of Decision Trees, Machine Learning, v.1 n.1, p.81-106 [doi>10.1023/A:1022643204877]
• 10: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 11: Sudhir G. Rao , Antonio Badia , Dirk van Gucht, Providing better support for a class of decision support queries, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.217-227, June 04-06, 1996, Montreal, Quebec, Canada
• 12: Steven Roman, Coding and information theory, Springer-Verlag New York, Inc., New York, NY, 1992
• 13: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 14: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 15: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.1 Systems and Information Theory
          Subjects: Information theory

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Design, Management, Theory

Keywords:
Armstrong's Axioms, entropy, functional dependency, information dependency, multivalued dependency