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: 5848
Venue: SIGMOD
Year: 2020
Pagerank: 5.7369354e-05
Overall Rank: 6,929 | 52.47%
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 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,441	A Statistical Perspective on Discovering Functional Dependencies in Noisy Data	2020	SIGMOD	7.4138323e-05
9,700	Quantifying the Loss of Acyclic Join Dependencies	2023	PODS	5.2351259e-05
10,652	Smallest Synthetic Witnesses for Conjunctive Queries	2025	PODS	5.093636e-05
11,564	Statistical Schema Learning using Occam's Razor	2022	SIGMOD	5.093636e-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
358	FAQ: Questions Asked Frequently	2016	PODS	0.00020243592
495	A Complete Axiomatization For Functional And Multivalued Dependencies In Database Relations	1977	SIGMOD	0.00017513721
536	Learning Linear Regression Models over Factorized Joins	2016	SIGMOD	0.0001693369
618	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD	0.00015711835
863	Interventional Fairness : Causal Database Repair for Algorithmic Fairness	2019	SIGMOD	0.00013531835
1,374	Data Profiling with Metanome	2015	VLDB	0.00010986078
1,500	Efficient Discovery of Approximate Dependencies	2018	VLDB	0.00010561098
2,769	A Layered Aggregate Engine for Analytics Workloads	2019	SIGMOD	8.1465406e-05
9,337	Efficiently Enumerating Minimal Triangulations	2017	PODS	5.2876688e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,332	Unifying Functional and Multivalued Dependencies for Relational Database Design	1986	PODS
2	1,913	Information-Theoretic Tools for Mining Database Structure from Large Data Sets	2004	SIGMOD
3	6,698	Properties Of Database Schemata With Functional Dependencies	1984	PODS
4	1,535	Exploratory Mining and Pruning Optimizations of Constrained Association Rules	1998	SIGMOD
5	13,227	Dependency Characterizations For Acyclic Database Schemes	1984	PODS
6	203	Dependency Inference	1987	VLDB
7	11,743	Making DBMSes Dependency-Aware	2020	CIDR
8	10,812	Discovering Approximate Inclusion Dependencies	2025	VLDB
9	3,504	Elimination of Intersection Anomalies from Database Schemes (Extended Abstract)	1983	PODS
10	2,685	Approximate Denial Constraints	2020	VLDB