Information Dependencies

Summary: Introduce an entropy-based information dependency (InD) measure quantifying residual uncertainty of Y given X in a relation and derive universal arithmetic InD inequalities that hold for any instance. Show FDs/MVDs arise as zero constraints (Armstrong’s axioms follow) and prove any constraint set consistent with the inequalities is approximately realizable, enabling principled numeric constraints and new data‑mining applications. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1217
Venue: PODS
Year: 2000
Pagerank: 7.7170066e-05
Overall Rank: 3,141 | 78.46%
DOI: 10.1145/335168.336059

Incoming Non-self Citations Over Time

Authors

1. Mehmet M. Dalkilic (Indiana University)
2. Edward L. Roberston (Indiana University)

BibTeX Citation

@inproceedings{dalkilic_pods00,
        address = {New York, NY, USA},
        series = {{PODS} '00},
        title = {{Information Dependencies}},
        url = {https://dl.acm.org/doi/10.1145/335168.336059},
        doi = {10.1145/335168.336059},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Dalkilic, Mehmet M. and Roberston, Edward L.},
        year = {2000}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,033	On Generating Near-Optimal Tableaux for Conditional Functional Dependencies	2008	VLDB	0.00012529852
1,913	Information-Theoretic Tools for Mining Database Structure from Large Data Sets	2004	SIGMOD	9.4928569e-05
3,432	An Information-Theoretic Approach to Normal Forms for Relational and XML Data	2003	PODS	7.4182332e-05
8,405	Information Theory for Data Management	2010	SIGMOD	5.4323037e-05
12,548	Information Theory For Data Management	2009	VLDB	5.093636e-05
12,679	On Redundancy vs Dependency Preservation in Normalization: An Information-Theoretic Study of 3NF	2006	PODS	5.093636e-05
12,726	Differential Constraints	2005	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
393	Bottom-Up Computation of Sparse and Iceberg CUBEs	1999	SIGMOD	0.0001934104
952	Recovering Information from Summary Data	1997	VLDB	0.00013010681

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	14,469	SMALL ARMSTRONG RELATIONS FOR DATABASE DESIGN (Extended abstract)	1985	PODS
2	162	Inclusion dependencies and their interaction with functional dependencies (Extended abstract)	1982	PODS
3	2,894	The Size of Projections of Relations Satisfying a Functional Dependency	1982	VLDB
4	3,461	Inference Rules for Functional and Inclusion Dependencies	1983	PODS
5	3,750	Dependency Satisfaction in Databases with Incomplete Information	1984	VLDB
6	413	Relative Information Capacity of Simple Relational Database Schemata	1984	PODS
7	14,504	Information Theoretic Aspects Of Data Bases	1983	PODS
8	1,913	Information-Theoretic Tools for Mining Database Structure from Large Data Sets	2004	SIGMOD
9	495	A Complete Axiomatization For Functional And Multivalued Dependencies In Database Relations	1977	SIGMOD
10	203	Dependency Inference	1987	VLDB