On Multi-Column Foreign Key Discovery

Summary: Proposes a robust method for discovering single- and multi-column foreign keys in relational data. Introduces a general Randomness rule unifying prior heuristics and two-pass approximate algorithms to evaluate it, validated on real and synthetic data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10127
Venue: VLDB
Year: 2010
Pagerank: 0.00010976887
Overall Rank: 1,664 | 88.43%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 21 of 21 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,796	Summary Graphs for Relational Database Schemas	2011	VLDB	0.00010524897
2,460	Combining Quantitative and Logical Data Cleaning	2016	VLDB	8.7617484e-05
2,982	FastQRE: Fast Query Reverse Engineering	2018	SIGMOD	7.7801984e-05
3,252	Auto-Suggest: Learning-to-Recommend Data Preparation Steps Using Data Science Notebooks	2020	SIGMOD	7.3178277e-05
3,823	Automatic Discovery of Attributes in Relational Databases	2011	SIGMOD	6.7261168e-05
3,992	Discovering Linkage Points over Web Data	2013	VLDB	6.5544834e-05
4,682	Scalable Discovery of Unique Column Combinations	2014	VLDB	6.0022412e-05
4,784	Divide & Conquer-based Inclusion Dependency Discovery	2015	VLDB	5.9240851e-05
5,361	Efficient Estimation of Inclusion Coefficient using HyperLogLog Sketches	2018	VLDB	5.547935e-05
5,486	Fast Foreign-Key Detection in Microsoft SQL Server PowerPivot for Excel	2014	VLDB	5.4811603e-05
6,092	Observatory: Characterizing Embeddings of Relational Tables	2024	VLDB	5.2138566e-05
8,432	SPRINTER: A Fast n-ary Join Query Processing Method for Complex OLAP Queries	2020	SIGMOD	4.5153924e-05
9,176	RDFind: Scalable Conditional Inclusion Dependency Discovery in RDF Datasets	2016	SIGMOD	4.383548e-05
9,412	Retrofitting GDPR Compliance onto Legacy Databases	2022	VLDB	4.3441378e-05
9,490	Auto-BI: Automatically Build BI-Models Leveraging Local Join Prediction and Global Schema Graph	2023	VLDB	4.3341665e-05
9,961	QueryArtisan: Generating Data Manipulation Codes for Ad-hoc Analysis in Data Lakes	2025	VLDB	4.2294678e-05
10,038	Understanding Robustness Issues of Updatable Learned Indexes: [Experiments & Analysis]	2026	SIGMOD	4.1945683e-05
10,598	Auto-Prep: Holistic Prediction of Data Preparation Steps for Self-Service Business Intelligence	2025	VLDB	4.1945683e-05
10,754	OmniMatch: Joinability Discovery in Data Products	2025	VLDB	4.1945683e-05
10,797	A Demonstration of QueryArtisan: Real-Time Data Lake Analysis via Dynamically Generated Data Manipulation Code	2025	VLDB	4.1945683e-05
11,316	Kyrix-J: Visual Discovery of Connected Datasets in a Data Lake	2022	CIDR	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 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	Inclusion dependencies and their interaction with functional dependencies (Extended abstract)	1982	PODS	0.00048766186
126	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00044744986
475	Mining Database Structure; Or, How to Build a Data Quality Browser	2002	SIGMOD	0.00022303253
727	On Synopses for Distinct-Value Estimation Under Multiset Operations	2007	SIGMOD	0.00017508726
916	On Schema Matching with Opaque Column Names and Data Values	2003	SIGMOD	0.00015379422
2,549	GORDIAN: Efficient and Scalable Discovery of Composite Keys	2006	VLDB	8.5641554e-05
3,685	Detecting Change in Data Streams	2004	VLDB	6.8448674e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,085	Discovery and Ranking of Embedded Uniqueness Constraints	2019	VLDB	4.5902231e-05
2,243	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS	9.2166927e-05
421	Query Optimization in the Presence of Foreign Functions	1993	VLDB	0.00023711553
8,725	A Fast Randomized Algorithm for Multi-Objective Query Optimization	2016	SIGMOD	4.4600243e-05
3,047	Comprehensive Approach to the Design of Relational Database Schemes	1984	VLDB	7.6561027e-05
3,328	Multi-column Substring Matching for Database Schema Translation	2006	VLDB	7.2174278e-05
6,686	An Algorithm For Servicing Multi-Relational Queries	1977	SIGMOD	4.9624102e-05
8,161	A New Characterization of Independence	1983	SIGMOD	4.5725899e-05
10,817	Mining Meaningful Keys and Foreign Keys with High Precision and Recall	2025	VLDB	4.1945683e-05
3,823	Automatic Discovery of Attributes in Relational Databases	2011	SIGMOD	6.7261168e-05