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.721104e-05
Overall Rank: 6,600 | 55.76%
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,205	A Statistical Perspective on Discovering Functional Dependencies in Noisy Data	2020	SIGMOD	7.5221127e-05
9,915	Quantifying the Loss of Acyclic Join Dependencies	2023	PODS	5.0983269e-05
10,865	Storage-Centric Relation Design via High-Quality Approximate Functional Dependencies	2026	VLDB	4.9605343e-05
11,165	Smallest Synthetic Witnesses for Conjunctive Queries	2025	PODS	4.9605343e-05
11,923	Statistical Schema Learning using Occam's Razor	2022	SIGMOD	4.9605343e-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.00020048899
510	A Complete Axiomatization For Functional And Multivalued Dependencies In Database Relations	1977	SIGMOD	0.00017080094
522	Learning Linear Regression Models over Factorized Joins	2016	SIGMOD	0.00016893112
602	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD	0.00015670535
804	Interventional Fairness : Causal Database Repair for Algorithmic Fairness	2019	SIGMOD	0.00013788292
1,399	Data Profiling with Metanome	2015	VLDB	0.0001076306
1,490	Efficient Discovery of Approximate Dependencies	2018	VLDB	0.0001047928
2,673	A Layered Aggregate Engine for Analytics Workloads	2019	SIGMOD	8.1276375e-05
9,554	Efficiently Enumerating Minimal Triangulations	2017	PODS	5.1495584e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,550	Unifying Functional and Multivalued Dependencies for Relational Database Design	1986	PODS
2	1,979	Information-Theoretic Tools for Mining Database Structure from Large Data Sets	2004	SIGMOD
3	6,857	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,564	Dependency Characterizations For Acyclic Database Schemes	1984	PODS
6	211	Dependency Inference	1987	VLDB
7	12,096	Making DBMSes Dependency-Aware	2020	CIDR
8	10,096	Discovering Approximate Inclusion Dependencies	2025	VLDB
9	3,589	Elimination of Intersection Anomalies from Database Schemes (Extended Abstract)	1983	PODS
10	2,451	Approximate Denial Constraints	2020	VLDB