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: h6671f4304af77c2c
Venue: VLDB
Year: 2010
Pagerank: 0.00010295575
Overall Rank: 1,538 | 89.70%
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,056	Combining Quantitative and Logical Data Cleaning	2016	VLDB	9.10022e-05
2,645	Auto-Suggest: Learning-to-Recommend Data Preparation Steps Using Data Science Notebooks	2020	SIGMOD	8.1641056e-05
2,686	FastQRE: Fast Query Reverse Engineering	2018	SIGMOD	8.1157127e-05
3,467	Automatic Discovery of Attributes in Relational Databases	2011	SIGMOD	7.2609187e-05
3,619	Summary Graphs for Relational Database Schemas	2011	VLDB	7.1360652e-05
3,756	Discovering Linkage Points over Web Data	2013	VLDB	7.0275986e-05
4,245	Scalable Discovery of Unique Column Combinations	2014	VLDB	6.6958006e-05
4,264	Divide & Conquer-based Inclusion Dependency Discovery	2015	VLDB	6.6809569e-05
5,132	Efficient Estimation of Inclusion Coefficient using HyperLogLog Sketches	2018	VLDB	6.2462533e-05
5,145	Fast Foreign-Key Detection in Microsoft SQL Server PowerPivot for Excel	2014	VLDB	6.2410756e-05
5,301	Observatory: Characterizing Embeddings of Relational Tables	2024	VLDB	6.1761723e-05
7,548	Auto-Prep: Holistic Prediction of Data Preparation Steps for Self-Service Business Intelligence	2025	VLDB	5.481283e-05
8,517	SPRINTER: A Fast n-ary Join Query Processing Method for Complex OLAP Queries	2020	SIGMOD	5.3110227e-05
8,599	OmniMatch: Joinability Discovery in Data Products	2025	VLDB	5.2921451e-05
9,008	Auto-BI: Automatically Build BI-Models Leveraging Local Join Prediction and Global Schema Graph	2023	VLDB	5.2245403e-05
9,556	RDFind: Scalable Conditional Inclusion Dependency Discovery in RDF Datasets	2016	SIGMOD	5.1487688e-05
9,775	Retrofitting GDPR Compliance onto Legacy Databases	2022	VLDB	5.115551e-05
9,814	Understanding Robustness Issues of Updatable Learned Indexes: [Experiments & Analysis]	2026	SIGMOD	5.1121061e-05
10,371	QueryArtisan: Generating Data Manipulation Codes for Ad-hoc Analysis in Data Lakes	2025	VLDB	5.0010514e-05
11,449	A Demonstration of QueryArtisan: Real-Time Data Lake Analysis via Dynamically Generated Data Manipulation Code	2025	VLDB	4.9605343e-05
11,874	Kyrix-J: Visual Discovery of Connected Datasets in a Data Lake	2022	CIDR	4.9605343e-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.00036097627
159	Inclusion dependencies and their interaction with functional dependencies (Extended abstract)	1982	PODS	0.00027867985
435	Mining Database Structure; Or, How to Build a Data Quality Browser	2002	SIGMOD	0.00018277436
711	On Synopses for Distinct-Value Estimation Under Multiset Operations	2007	SIGMOD	0.00014589586
823	On Schema Matching with Opaque Column Names and Data Values	2003	SIGMOD	0.00013610136
2,305	GORDIAN: Efficient and Scalable Discovery of Composite Keys	2006	VLDB	8.6550507e-05
3,689	Detecting Change in Data Streams	2004	VLDB	7.078365e-05

Semantically Similar Papers

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