Information Dependencies Mehmet M. Dalkilic and Edward L. Robertson   View Paper (PDF)   Return to Data Mining / 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 [epsilon]. InD measures suggest many valuable applications in areas such as data mining. References Note: References link to DBLP on the Web. [1] ... [2] Kevin S. Beyer , Raghu Ramakrishnan : Bottom-Up Computation of Sparse and Iceberg CUBEs. SIGMOD Conference 1999 : 359-370 [3] Christos Faloutsos , H. V. Jagadish , Nikolaos Sidiropoulos : Recovering Information from Summary Data. VLDB 1997 : 36-45 [4] ... [5] Usama M. Fayyad , Gregory Piatetsky-Shapiro , Padhraic Smyth : From Data Mining to Knowledge Discovery: An Overview. Advances in Knowledge Discovery and Data Mining 1996 : 1-34 [6] Seymour Ginsburg , Richard Hull : Characterizations for Functional Dependency and Boyce-CODD Normal Form Families. TCS 26 : 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 1(1) : 29-53(1997) [8] Jyrki Kivinen , Heikki Mannila : Approximate Inference of Functional Dependencies from Relations. TCS 149(1) : 129-149(1995) [9] J. Ross Quinlan : Induction of Decision Trees. Machine Learning 1(1) : 81-106(1986) [10] J. Ross Quinlan : C4.5: Programs for Machine Learning. Morgan Kaufmann 1993, ISBN 1-55860-238-0 [11] Sudhir Rao , Antonio Badia , Dirk Van Gucht : Providing Better Support for a Class of Decision Support Queries. SIGMOD Conf. 1996 : 217-227 [12] ... [13] Serge Abiteboul , Richard Hull , Victor Vianu : Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0 Contents [14] ... [15] Jeffrey D. Ullman : Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1 Contents BIBTEX @inproceedings{DBLP:conf/pods/DalkilicR00,   author    = {Mehmet M. Dalkilic and                 Edward L. Robertson},    title     = {Information Dependencies},    booktitle = {Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium                 on Principles of Database Systems, May 15-17, 2000, Dallas, Texas,                 USA},    publisher = {ACM},    year      = {2000},    isbn      = {1-58113-214-X},    pages     = {245-253},    crossref  = {DBLP:conf/pods/00},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, DiSC'01 Copyright ©2002 ACM Inc.