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: 6134
Venue: SIGMOD
Year: 2021
Pagerank: 4.8904572e-05
Overall Rank: 6,886 | 52.15%
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,264	PrivLava: Synthesizing Relational Data with Foreign Keys under Differential Privacy	2023	SIGMOD	5.5951175e-05
9,835	Projection-Compliant Database Generation	2022	VLDB	4.2706095e-05
10,509	PrivPetal: Relational Data Synthesis via Permutation Relations	2025	SIGMOD	4.1905499e-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.00047047599
145	Quickly Generating Billion-Record Synthetic Databases	1994	SIGMOD	0.00041403894
178	Boosting the Accuracy of Differentially Private Histograms Through Consistency	2010	VLDB	0.00037726596
192	HoloClean: Holistic Data Repairs with Probabilistic Inference	2017	VLDB	0.00035692958
556	Discovering Denial Constraints	2013	VLDB	0.00020214701
882	QAGen: Generating Query-Aware Test Databases	2007	SIGMOD	0.00015634206
933	Flexible Database Generators	2005	VLDB	0.00015220613
1,482	Simple and Realistic Data Generation	2006	VLDB	0.00011715248
1,740	PrivateSQL: A Differentially Private SQL Query Engine	2019	VLDB	0.00010696383
1,928	A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy	2014	VLDB	0.00010062105
2,228	Blowfish Privacy: Tuning Privacy-Utility Trade-offs using Policies	2014	SIGMOD	9.2488181e-05
2,295	Data Generation using Declarative Constraints	2011	SIGMOD	9.0842571e-05
2,436	Optimizing error of high-dimensional statistical queries under differential privacy	2018	VLDB	8.8217855e-05
2,484	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB	8.6737275e-05
3,045	Dichotomies in the Complexity of Preferred Repairs	2015	PODS	7.6618214e-05
3,448	Approximate Denial Constraints	2020	VLDB	7.081095e-05
4,441	Generating Databases for Query Workloads	2010	VLDB	6.1795515e-05
6,229	Just can't get enough - Synthesizing Big Data	2015	SIGMOD	5.140274e-05
7,062	On Multiple Semantics for Declarative Database Repairs	2020	SIGMOD	4.8398632e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,371	Smallest Synthetic Witnesses for Conjunctive Queries	2025	PODS	4.1905499e-05
1,625	Sampling the Repairs of Functional Dependency Violations under Hard Constraints	2010	VLDB	0.0001109361
6,808	Record Linkage with Uniqueness Constraints and Erroneous Values	2010	VLDB	4.9155856e-05
10,019	Guardrail: Automated Integrity Constraint Synthesis From Noisy Data	2026	SIGMOD	4.1905499e-05
1,353	Formal Limits on the Automatic Generation and Maintenance of Integrity Constraints	1987	PODS	0.00012431009
8,871	On The Satisfiability Of Dependency Constraints In Entity-Relationship Schemata	1987	VLDB	4.4274172e-05
1,101	On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases	2003	PODS	0.00014037952
2,246	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS	9.2039096e-05
268	A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification	2005	SIGMOD	0.00029739054
2,295	Data Generation using Declarative Constraints	2011	SIGMOD	9.0842571e-05