Synthesizing Linked Data Under Cardinality and Integrity Constraints

Summary: Synthesizing linked data under cardinality and integrity constraints with missing FKs; imputes FK values between related relations while preserving constraints. NP-hard; two-phase approach: Phase I builds a CC-consistent draft (ILP for one CC type, efficient for others); Phase II enforces ICs via conflict-hypergraph coloring, yielding scalable, low CC error. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h53c8f48afc183169
Venue: SIGMOD
Year: 2021
Pagerank: 5.6532847e-05
Overall Rank: 6,896 | 53.64%
DOI: 10.1145/3448016.3457242

Incoming Non-self Citations Over Time

Authors

1. Amir Gilad (Duke University)
2. Shweta Patwa (Duke University)
3. Ashwin Machanavajjhala (Duke University)

BibTeX Citation

@inproceedings{gilad_sigmod21,
        title = {{Synthesizing Linked Data Under Cardinality and Integrity Constraints}},
        author = {Gilad, Amir and Patwa, Shweta and Machanavajjhala, Ashwin},
        series = {{SIGMOD} '21},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3448016.3457242},
        url = {https://dl.acm.org/doi/10.1145/3448016.3457242},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,944	PrivLava: Synthesizing Relational Data with Foreign Keys under Differential Privacy	2023	SIGMOD	6.3439252e-05
10,176	Projection-Compliant Database Generation	2022	VLDB	5.0679291e-05
11,193	PrivPetal: Relational Data Synthesis via Permutation Relations	2025	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 19 of 19 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
104	HoloClean: Holistic Data Repairs with Probabilistic Inference	2017	VLDB	0.00033690989
106	Quickly Generating Billion-Record Synthetic Databases	1994	SIGMOD	0.00033526937
121	Boosting the Accuracy of Differentially Private Histograms Through Consistency	2010	VLDB	0.00031089378
133	Privacy, Accuracy, and Consistency Too: A Holistic Solution to Contingency Table Release	2007	PODS	0.0003006035
350	Discovering Denial Constraints	2013	VLDB	0.00020253521
747	QAGen: Generating Query-Aware Test Databases	2007	SIGMOD	0.00014283935
955	Flexible Database Generators	2005	VLDB	0.00012866364
1,166	PrivateSQL: A Differentially Private SQL Query Engine	2019	VLDB	0.00011731286
1,528	A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy	2014	VLDB	0.00010349919
1,602	Simple and Realistic Data Generation	2006	VLDB	0.00010101626
1,971	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB	9.2873596e-05
2,090	Optimizing error of high-dimensional statistical queries under differential privacy	2018	VLDB	9.0657103e-05
2,370	Blowfish Privacy: Tuning Privacy-Utility Trade-offs using Policies	2014	SIGMOD	8.5616358e-05
2,413	Data Generation using Declarative Constraints	2011	SIGMOD	8.5094338e-05
2,443	Approximate Denial Constraints	2020	VLDB	8.4586656e-05
2,762	Dichotomies in the Complexity of Preferred Repairs	2015	PODS	8.0441688e-05
4,090	Generating Databases for Query Workloads	2010	VLDB	6.8126942e-05
6,119	Just can't get enough - Synthesizing Big Data	2015	SIGMOD	5.881057e-05
6,728	On Multiple Semantics for Declarative Database Repairs	2020	SIGMOD	5.6946342e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,348	Sampling the Repairs of Functional Dependency Violations under Hard Constraints	2010	VLDB
2	6,849	Record Linkage with Uniqueness Constraints and Erroneous Values	2010	VLDB
3	10,526	Guardrail: Automated Integrity Constraint Synthesis From Noisy Data	2026	SIGMOD
4	4,179	Formal Limits on the Automatic Generation and Maintenance of Integrity Constraints	1987	PODS
5	9,198	On the Satisfiability of Dependency Constraints in Entity-Relationship Schemata	1987	VLDB
6	897	On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases	2003	PODS
7	1,361	Computing Optimal Repairs for Functional Dependencies	2018	PODS
8	1,735	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS
9	188	A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification	2005	SIGMOD
10	2,413	Data Generation using Declarative Constraints	2011	SIGMOD