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: h67d9d315f737c039
Venue: PODS
Year: 2000
Pagerank: 7.5524237e-05
Overall Rank: 3,190 | 78.56%
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,031	On Generating Near-Optimal Tableaux for Conditional Functional Dependencies	2008	VLDB	0.00012405065
1,969	Information-Theoretic Tools for Mining Database Structure from Large Data Sets	2004	SIGMOD	9.2935435e-05
3,502	An Information-Theoretic Approach to Normal Forms for Relational and XML Data	2003	PODS	7.2525074e-05
8,568	Information Theory for Data Management	2010	SIGMOD	5.3134519e-05
12,838	Information Theory For Data Management	2009	VLDB	4.9793485e-05
12,969	On Redundancy vs Dependency Preservation in Normalization: An Information-Theoretic Study of 3NF	2006	PODS	4.9793485e-05
13,016	Differential Constraints	2005	PODS	4.9793485e-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
403	Bottom-Up Computation of Sparse and Iceberg CUBEs	1999	SIGMOD	0.0001910396
967	Recovering Information from Summary Data	1997	VLDB	0.00012794553

Semantically Similar Papers

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