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)
Incoming Non-self Citations Over Time
Authors
- 1. Batya Kenig
- 2. Nir Weinberger
Incoming Citations (Sorted by Pagerank)
Showing 1 of 1 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 10,359 | Smallest Synthetic Witnesses for Conjunctive Queries | 2025 | PODS | 4.1945683e-05 |
Previous
Page 1 / 1
Next
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 |
|---|---|---|---|---|
| 834 | Learning Linear Regression Models over Factorized Joins | 2016 | SIGMOD | 0.00016135159 |
| 1,884 | Normal forms and relational database operators | 1979 | SIGMOD | 0.00010215563 |
| 3,277 | A Layered Aggregate Engine for Analytics Workloads | 2019 | SIGMOD | 7.2871625e-05 |
| 7,076 | Mining Approximate Acyclic Schemes from Relations | 2020 | SIGMOD | 4.8426354e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 8,966 | Output-sensitive Conjunctive Query Evaluation | 2024 | PODS | 4.4193184e-05 |
| 4,432 | Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins | 2016 | PODS | 6.1938383e-05 |
| 502 | Worst-case Optimal Join Algorithms | 2012 | PODS | 0.00021526612 |
| 3,104 | Computing Local Sensitivities of Counting Queries with Joins | 2020 | SIGMOD | 7.5578613e-05 |
| 13,028 | Dependency Characterizations For Acyclic Database Schemes | 1984 | PODS | 4.1945683e-05 |
| 7,344 | Join Size Bounds using l_p-Norms on Degree Sequences | 2024 | PODS | 4.7565607e-05 |
| 13,031 | On the Decomposition of Join Dependencies | 1984 | PODS | 4.1945683e-05 |
| 13,042 | A Less Costly Constraints Checking for Join Dependency | 1984 | VLDB | 4.1945683e-05 |
| 3,198 | Elimination of Intersection Anomalies from Database Schemes (Extended Abstract) | 1983 | PODS | 7.3938086e-05 |
| 3,515 | Scalable Computation of Acyclic Joins (Extended Abstract) | 2006 | PODS | 7.0220813e-05 |