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: 10318
Venue: VLDB
Year: 2010
Pagerank: 0.00010506299
Overall Rank: 1,521 | 89.57%
DOI: 10.14778/1920841.1920942

Incoming Non-self Citations Over Time

Authors

1. Meihui Zhang (National University of Singapore)
2. Marios Hadjieleftheriou (AT&T)
3. Beng Chin Ooi (National University of Singapore)
4. Cecilia M. Procopiuc (AT&T)
5. Divesh Srivastava (AT&T)

BibTeX Citation

@article{zhang_vldb10,
        title = {{On Multi-Column Foreign Key Discovery}},
        author = {Zhang, Meihui and Hadjieleftheriou, Marios and Ooi, Beng Chin and Procopiuc, Cecilia M. and Srivastava, Divesh},
        journal = {PVLDB},
        series = {{VLDB} '10},
        volume = {3},
        number = {1},
        pages = {805--816},
        doi = {10.14778/1920841.1920942},
        url = {https://doi.org/10.14778/1920841.1920942},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 21 of 21 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,041	Combining Quantitative and Logical Data Cleaning	2016	VLDB	9.2692538e-05
2,631	FastQRE: Fast Query Reverse Engineering	2018	SIGMOD	8.3231158e-05
2,744	Auto-Suggest: Learning-to-Recommend Data Preparation Steps Using Data Science Notebooks	2020	SIGMOD	8.1781662e-05
3,456	Automatic Discovery of Attributes in Relational Databases	2011	SIGMOD	7.3998323e-05
3,572	Summary Graphs for Relational Database Schemas	2011	VLDB	7.2980153e-05
3,746	Discovering Linkage Points over Web Data	2013	VLDB	7.1561558e-05
4,183	Scalable Discovery of Unique Column Combinations	2014	VLDB	6.8467773e-05
4,386	Divide & Conquer-based Inclusion Dependency Discovery	2015	VLDB	6.7309577e-05
5,099	Fast Foreign-Key Detection in Microsoft SQL Server PowerPivot for Excel	2014	VLDB	6.3646928e-05
5,257	Efficient Estimation of Inclusion Coefficient using HyperLogLog Sketches	2018	VLDB	6.2971456e-05
5,816	Observatory: Characterizing Embeddings of Relational Tables	2024	VLDB	6.0776454e-05
8,374	SPRINTER: A Fast n-ary Join Query Processing Method for Complex OLAP Queries	2020	SIGMOD	5.4399097e-05
9,340	RDFind: Scalable Conditional Inclusion Dependency Discovery in RDF Datasets	2016	SIGMOD	5.2869213e-05
9,380	Auto-Prep: Holistic Prediction of Data Preparation Steps for Self-Service Business Intelligence	2025	VLDB	5.2755515e-05
9,563	Retrofitting GDPR Compliance onto Legacy Databases	2022	VLDB	5.2528121e-05
9,599	Understanding Robustness Issues of Updatable Learned Indexes: [Experiments & Analysis]	2026	SIGMOD	5.2492748e-05
9,629	Auto-BI: Automatically Build BI-Models Leveraging Local Join Prediction and Global Schema Graph	2023	VLDB	5.2434488e-05
10,109	QueryArtisan: Generating Data Manipulation Codes for Ad-hoc Analysis in Data Lakes	2025	VLDB	5.1347137e-05
10,987	OmniMatch: Joinability Discovery in Data Products	2025	VLDB	5.093636e-05
11,025	A Demonstration of QueryArtisan: Real-Time Data Lake Analysis via Dynamically Generated Data Manipulation Code	2025	VLDB	5.093636e-05
11,515	Kyrix-J: Visual Discovery of Connected Datasets in a Data Lake	2022	CIDR	5.093636e-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
82	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00036378991
162	Inclusion dependencies and their interaction with functional dependencies (Extended abstract)	1982	PODS	0.00027886326
432	Mining Database Structure; Or, How to Build a Data Quality Browser	2002	SIGMOD	0.00018572055
689	On Synopses for Distinct-Value Estimation Under Multiset Operations	2007	SIGMOD	0.00014940023
808	On Schema Matching with Opaque Column Names and Data Values	2003	SIGMOD	0.00013884332
2,269	GORDIAN: Efficient and Scalable Discovery of Composite Keys	2006	VLDB	8.8328424e-05
3,785	Detecting Change in Data Streams	2004	VLDB	7.1265312e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,137	Discovery and Ranking of Embedded Uniqueness Constraints	2019	VLDB
2	1,707	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS
3	677	Query Optimization in the Presence of Foreign Functions	1993	VLDB
4	8,831	A Fast Randomized Algorithm for Multi-Objective Query Optimization	2016	SIGMOD
5	3,222	Comprehensive Approach to the Design of Relational Database Schemes	1984	VLDB
6	3,294	Multi-column Substring Matching for Database Schema Translation	2006	VLDB
7	7,120	An Algorithm For Servicing Multi-Relational Queries	1977	SIGMOD
8	7,808	A New Characterization of Independence	1983	SIGMOD
9	11,044	Mining Meaningful Keys and Foreign Keys with High Precision and Recall	2025	VLDB
10	3,456	Automatic Discovery of Attributes in Relational Databases	2011	SIGMOD