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: 6133
Venue: SIGMOD
Year: 2021
Pagerank: 4.8937852e-05
Overall Rank: 6,887 | 52.09%
DOI: 10.1145/3448016.3457242

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,349	PrivLava: Synthesizing Relational Data with Foreign Keys under Differential Privacy	2023	SIGMOD	5.553869e-05
9,836	Projection-Compliant Database Generation	2022	VLDB	4.2747054e-05
10,500	PrivPetal: Relational Data Synthesis via Permutation Relations	2025	SIGMOD	4.1945683e-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
111	Privacy, Accuracy, and Consistency Too: A Holistic Solution to Contingency Table Release	2007	PODS	0.00047073785
145	Quickly Generating Billion-Record Synthetic Databases	1994	SIGMOD	0.0004138408
178	Boosting the Accuracy of Differentially Private Histograms Through Consistency	2010	VLDB	0.00037697111
192	HoloClean: Holistic Data Repairs with Probabilistic Inference	2017	VLDB	0.00035728858
555	Discovering Denial Constraints	2013	VLDB	0.00020254908
888	QAGen: Generating Query-Aware Test Databases	2007	SIGMOD	0.00015578618
934	Flexible Database Generators	2005	VLDB	0.00015227409
1,483	Simple and Realistic Data Generation	2006	VLDB	0.00011720317
1,738	PrivateSQL: A Differentially Private SQL Query Engine	2019	VLDB	0.00010720057
1,935	A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy	2014	VLDB	0.00010032967
2,227	Blowfish Privacy: Tuning Privacy-Utility Trade-offs using Policies	2014	SIGMOD	9.2421238e-05
2,291	Data Generation using Declarative Constraints	2011	SIGMOD	9.0926719e-05
2,434	Optimizing error of high-dimensional statistical queries under differential privacy	2018	VLDB	8.8278955e-05
2,483	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB	8.6864916e-05
3,042	Dichotomies in the Complexity of Preferred Repairs	2015	PODS	7.669374e-05
3,440	Approximate Denial Constraints	2020	VLDB	7.0918817e-05
4,517	Generating Databases for Query Workloads	2010	VLDB	6.1178732e-05
6,234	Just can't get enough - Synthesizing Big Data	2015	SIGMOD	5.1451686e-05
7,066	On Multiple Semantics for Declarative Database Repairs	2020	SIGMOD	4.8445108e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,359	Smallest Synthetic Witnesses for Conjunctive Queries	2025	PODS	4.1945683e-05
1,624	Sampling the Repairs of Functional Dependency Violations under Hard Constraints	2010	VLDB	0.00011099222
6,810	Record Linkage with Uniqueness Constraints and Erroneous Values	2010	VLDB	4.9203397e-05
10,019	Guardrail: Automated Integrity Constraint Synthesis From Noisy Data	2026	SIGMOD	4.1945683e-05
1,349	Formal Limits on the Automatic Generation and Maintenance of Integrity Constraints	1987	PODS	0.00012436377
8,871	On The Satisfiability Of Dependency Constraints In Entity-Relationship Schemata	1987	VLDB	4.431665e-05
1,102	On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases	2003	PODS	0.00014049364
2,243	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS	9.2166927e-05
265	A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification	2005	SIGMOD	0.00029763412
2,291	Data Generation using Declarative Constraints	2011	SIGMOD	9.0926719e-05