Quantifying the Loss of Acyclic Join Dependencies

Summary: Show KL-divergence between the universal relation and the acyclic join result exactly captures AJD loss, linking information-theoretic loss to the classic redundant-tuple measure. Prove a deterministic lower bound on redundant-tuple percentage and a high-probability upper bound under a random-database model, with both bounds coinciding asymptotically for large databases. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1909
Venue: PODS
Year: 2023
Pagerank: 5.2351259e-05
Overall Rank: 9,700 | 33.45%
DOI: 10.1145/3584372.3588658

Incoming Non-self Citations Over Time

Authors

1. Batya Kenig (Technion)
2. Nir Weinberger (Technion)

BibTeX Citation

@inproceedings{kenig_pods23,
        address = {New York, NY, USA},
        series = {{PODS} '23},
        title = {{Quantifying the Loss of Acyclic Join Dependencies}},
        url = {https://dl.acm.org/doi/10.1145/3584372.3588658},
        doi = {10.1145/3584372.3588658},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Kenig, Batya and Weinberger, Nir},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,652	Smallest Synthetic Witnesses for Conjunctive Queries	2025	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
536	Learning Linear Regression Models over Factorized Joins	2016	SIGMOD	0.0001693369
2,422	Normal forms and relational database operators	1979	SIGMOD	8.6023273e-05
2,769	A Layered Aggregate Engine for Analytics Workloads	2019	SIGMOD	8.1465406e-05
6,929	Mining Approximate Acyclic Schemes from Relations	2020	SIGMOD	5.7369354e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,678	Output-sensitive Conjunctive Query Evaluation	2024	PODS
2	4,401	Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins	2016	PODS
3	411	Worst-case Optimal Join Algorithms	2012	PODS
4	2,436	Computing Local Sensitivities of Counting Queries with Joins	2020	SIGMOD
5	13,227	Dependency Characterizations For Acyclic Database Schemes	1984	PODS
6	6,257	Join Size Bounds using l_p-Norms on Degree Sequences	2024	PODS
7	13,230	On the Decomposition of Join Dependencies	1984	PODS
8	13,241	A Less Costly Constraints Checking for Join Dependency	1984	VLDB
9	3,504	Elimination of Intersection Anomalies from Database Schemes (Extended Abstract)	1983	PODS
10	3,617	Scalable Computation of Acyclic Joins (Extended Abstract)	2006	PODS