{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T15:02:18Z","timestamp":1773154938178,"version":"3.50.1"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"1-2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2010,9]]},"abstract":"<jats:p>\n            A foreign\/primary key relationship between relational tables is one of the most important constraints in a database. From a data analysis perspective, discovering foreign keys is a crucial step in understanding and working with the data. Nevertheless, more often than not, foreign key constraints are not specified in the data, for various reasons; e.g., some associations are not known to designers but are inherent in the data, while others become invalid due to data inconsistencies. This work proposes a robust algorithm for discovering single-column and multi-column foreign keys. Previous work concentrated mostly on discovering single-column foreign keys using a variety of rules, like inclusion dependencies, column names, and minimum\/maximum values. We first propose a general rule, termed\n            <jats:italic>Randomness<\/jats:italic>\n            , that subsumes a variety of other rules. We then develop efficient approximation algorithms for evaluating randomness, using only two passes over the data. Finally, we validate our approach via extensive experiments using real and synthetic datasets.\n          <\/jats:p>","DOI":"10.14778\/1920841.1920944","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"805-814","source":"Crossref","is-referenced-by-count":59,"title":["On multi-column foreign key discovery"],"prefix":"10.14778","volume":"3","author":[{"given":"Meihui","family":"Zhang","sequence":"first","affiliation":[{"name":"National University of Singapore"}]},{"given":"Marios","family":"Hadjieleftheriou","sequence":"additional","affiliation":[{"name":"AT&amp;T Labs - Research"}]},{"given":"Beng Chin","family":"Ooi","sequence":"additional","affiliation":[{"name":"National University of Singapore"}]},{"given":"Cecilia M.","family":"Procopiuc","sequence":"additional","affiliation":[{"name":"AT&amp;T Labs - Research"}]},{"given":"Divesh","family":"Srivastava","sequence":"additional","affiliation":[{"name":"AT&amp;T Labs - Research"}]}],"member":"320","published-online":{"date-parts":[[2010,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.369032"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247504"},{"key":"e_1_2_1_3_1","first-page":"21","volume-title":"SEQUENCES","author":"Broder A.","year":"1997","unstructured":"A. Broder . On the resemblance and containment of documents . In SEQUENCES , pages 21 -- 30 , 1997 . A. Broder. On the resemblance and containment of documents. In SEQUENCES, pages 21--30, 1997."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/588111.588141"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1555349.1555379"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1508857.1508863"},{"key":"e_1_2_1_7_1","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2001","unstructured":"T. H. Cormen , C. Stein , R. L. Rivest , and C. E. Leiserson . Introduction to Algorithms . McGraw-Hill Higher Education , 2001 . T. H. Cormen, C. Stein, R. L. Rivest, and C. E. Leiserson. Introduction to Algorithms. McGraw-Hill Higher Education, 2001."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564719"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375670"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872783"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1316689.1316707"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2003.1260834"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0306-4379(01)00027-8"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10844-007-0048-x"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/951949.952179"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.192468"},{"key":"e_1_2_1_17_1","volume-title":"WebDB","author":"Rostin A.","year":"2009","unstructured":"A. Rostin , O. Albrecht , J. Bauckmann , F. Naumann , and U. Leser . A machine learning approach to foreign key discovery . In WebDB , 2009 . A. Rostin, O. Albrecht, J. Bauckmann, F. Naumann, and U. Leser. A machine learning approach to foreign key discovery. In WebDB, 2009."},{"key":"e_1_2_1_18_1","volume-title":"Nonparametric statistics for the behavioral sciences","author":"Siegel S.","year":"1988","unstructured":"S. Siegel and N. Castellan . Nonparametric statistics for the behavioral sciences . McGraw-Hill, Inc. , second edition, 1988 . S. Siegel and N. Castellan. Nonparametric statistics for the behavioral sciences. McGraw-Hill, Inc., second edition, 1988."},{"key":"e_1_2_1_19_1","first-page":"691","volume-title":"VLDB","author":"Sismanis Y.","year":"2006","unstructured":"Y. Sismanis , P. Brown , P. J. Haas , and B. Reinwald . Gordian: Efficient and scalable discovery of composite keys . In VLDB , pages 691 -- 702 , 2006 . Y. Sismanis, P. Brown, P. J. Haas, and B. Reinwald. Gordian: Efficient and scalable discovery of composite keys. In VLDB, pages 691--702, 2006."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1920841.1920944","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:37:22Z","timestamp":1672227442000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1920841.1920944"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,9]]},"references-count":19,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2010,9]]}},"alternative-id":["10.14778\/1920841.1920944"],"URL":"https:\/\/doi.org\/10.14778\/1920841.1920944","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2010,9]]}}}