GORDIAN: Efficient and Scalable Discovery of Composite Keys

Summary: GORDIAN enables scalable, exact discovery of composite keys for modeling and indexing. Avoids brute-force searches; efficient on big data, supports key-column groups and XML leaf-nodes, enabling sampling for high-quality approximate keys. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 9674
Venue: VLDB
Year: 2006
Pagerank: 8.8328424e-05
Overall Rank: 2,269 | 84.44%
DOI: 10.14778/1164135.1164144

Incoming Non-self Citations Over Time

Authors

1. Yannis Sismanis (IBM)
2. Paul Brown (IBM)
3. Peter J. Haas (IBM)
4. Berthold Reinwald (IBM)

BibTeX Citation

@article{sismanis_vldb06,
        title = {{GORDIAN: Efficient and Scalable Discovery of Composite Keys}},
        author = {Sismanis, Yannis and Brown, Paul and Haas, Peter J. and Reinwald, Berthold},
        journal = {PVLDB},
        series = {{VLDB} '06},
        pages = {691--702},
        doi = {10.14778/1164135.1164144},
        url = {https://doi.org/10.14778/1164135.1164144},
        year = {2006}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,500	Efficient Discovery of Approximate Dependencies	2018	VLDB	0.00010561098
1,521	On Multi-Column Foreign Key Discovery	2010	VLDB	0.00010506299
1,741	Efficient Denial Constraint Discovery with Hydra	2018	VLDB	9.8755846e-05
4,183	Scalable Discovery of Unique Column Combinations	2014	VLDB	6.8467773e-05
4,228	Discovering Topical Structures of Databases	2008	SIGMOD	6.819835e-05
4,303	Possible and Certain SQL Keys	2015	VLDB	6.7711902e-05
7,187	Discovery Algorithms for Embedded Functional Dependencies	2020	SIGMOD	5.6776392e-05
8,137	Discovery and Ranking of Embedded Uniqueness Constraints	2019	VLDB	5.4809275e-05
8,757	Search Driven Analysis of Heterogeneous XML Data	2009	CIDR	5.3766157e-05
8,844	Hitting Set Enumeration with Partial Information for Unique Column Combination Discovery	2020	VLDB	5.3588479e-05
11,235	SplitDF: Splitting Dataframes for Memory-Efficient Data Analysis	2024	VLDB	5.093636e-05
13,802	Information Discovery in Loosely Integrated Data	2007	SIGMOD	-

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
100	LEO - DB2's LEarning Optimizer	2001	VLDB	0.00034385207
168	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00027541029
257	The History of Histograms (abridged)	2003	VLDB	0.00023154793
280	Selectivity Estimation using Probabilistic Models	2001	SIGMOD	0.00022454217
365	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00020041735
432	Mining Database Structure; Or, How to Build a Data Quality Browser	2002	SIGMOD	0.00018572055
606	Mining Quantitative Association Rules in Large Relational Tables	1996	SIGMOD	0.00015804851
664	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD	0.00015167825
692	Independence is Good: Dependency-Based Histogram Synopses for High-Dimensional Data	2001	SIGMOD	0.00014919816
781	Self-tuning Database Technology and Information Services: from Wishful Thinking to Viable Engineering	2002	VLDB	0.00014085674
1,648	BHUNT: Automatic Discovery of Fuzzy Algebraic Constraints in Relational Data	2003	VLDB	0.00010120668
2,318	Dwarf: Shrinking the PetaCube	2002	SIGMOD	8.7588859e-05
4,591	Automated Statistics Collection in DB2 UDB	2004	VLDB	6.614318e-05
6,902	The Polynomial Complexity of Fully Materialized Coalesced Cubes	2004	VLDB	5.7426524e-05
8,012	CORDS: Automatic Generation of Correlation Statistics in DB2	2004	VLDB	5.5073838e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,883	On Concise Set of Relative Candidate Keys	2014	VLDB
2	618	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD
3	5,405	GORDER: An Efficient Method for KNN Join Processing	2004	VLDB
4	349	Knowledge Discovery in Databases: An Attribute-Oriented Approach	1992	VLDB
5	37	DISCOVER: Keyword Search in Relational Databases	2002	VLDB
6	12,457	Keymantic: Semantic Keyword-based Searching in Data Integration Systems	2010	VLDB
7	1,521	On Multi-Column Foreign Key Discovery	2010	VLDB
8	3,456	Automatic Discovery of Attributes in Relational Databases	2011	SIGMOD
9	8,480	Discovering XSD Keys from XML Data	2013	SIGMOD
10	11,044	Mining Meaningful Keys and Foreign Keys with High Precision and Recall	2025	VLDB