Mining Approximate Acyclic Schemes from Relations

Summary: Maimon mines approximate MVDs to derive acyclic schemes from data. It uses information-theoretic approximation to jointly mine approximate MVDs and reconstruct acyclic schemas, scalable to 1M rows and 30 columns, and robust to noise. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h92ea2c1e05192624
Venue: SIGMOD
Year: 2020
Pagerank: 5.7400812e-05
Overall Rank: 6,591 | 55.71%
DOI: 10.1145/3318464.3380573

Incoming Non-self Citations Over Time

Authors

1. Batya Kenig (University of Washington)
2. Pranay Mundra (University of Washington)
3. Guna Prasaad (University of Washington)
4. Babak Salimi (University of Washington)
5. Dan Suciu (University of Washington)

BibTeX Citation

@inproceedings{kenig_sigmod20,
        title = {{Mining Approximate Acyclic Schemes from Relations}},
        author = {Kenig, Batya and Mundra, Pranay and Prasaad, Guna and Salimi, Babak and Suciu, Dan},
        series = {{SIGMOD} '20},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3318464.3380573},
        url = {https://dl.acm.org/doi/10.1145/3318464.3380573},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,194	A Statistical Perspective on Discovering Functional Dependencies in Noisy Data	2020	SIGMOD	7.5469742e-05
9,882	Quantifying the Loss of Acyclic Join Dependencies	2023	PODS	5.115241e-05
10,804	Storage-Centric Relation Design via High-Quality Approximate Functional Dependencies	2026	VLDB	4.9769913e-05
11,104	Smallest Synthetic Witnesses for Conjunctive Queries	2025	PODS	4.9769913e-05
11,879	Statistical Schema Learning using Occam's Razor	2022	SIGMOD	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
357	FAQ: Questions Asked Frequently	2016	PODS	0.00020013731
506	A Complete Axiomatization For Functional And Multivalued Dependencies In Database Relations	1977	SIGMOD	0.0001713431
521	Learning Linear Regression Models over Factorized Joins	2016	SIGMOD	0.00016923519
603	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD	0.00015692059
804	Interventional Fairness : Causal Database Repair for Algorithmic Fairness	2019	SIGMOD	0.00013830311
1,394	Data Profiling with Metanome	2015	VLDB	0.00010791559
1,488	Efficient Discovery of Approximate Dependencies	2018	VLDB	0.00010513265
2,663	A Layered Aggregate Engine for Analytics Workloads	2019	SIGMOD	8.1542952e-05
9,527	Efficiently Enumerating Minimal Triangulations	2017	PODS	5.1666108e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,523	Unifying Functional and Multivalued Dependencies for Relational Database Design	1986	PODS
2	1,970	Information-Theoretic Tools for Mining Database Structure from Large Data Sets	2004	SIGMOD
3	6,839	Properties Of Database Schemata With Functional Dependencies	1984	PODS
4	1,561	Exploratory Mining and Pruning Optimizations of Constrained Association Rules	1998	SIGMOD
5	13,523	Dependency Characterizations For Acyclic Database Schemes	1984	PODS
6	209	Dependency Inference	1987	VLDB
7	10,063	Discovering Approximate Inclusion Dependencies	2025	VLDB
8	12,052	Making DBMSes Dependency-Aware	2020	CIDR
9	3,578	Elimination of Intersection Anomalies from Database Schemes (Extended Abstract)	1983	PODS
10	2,445	Approximate Denial Constraints	2020	VLDB