Elamur Research⌕
☰
home / papers / 2026 / LLM-FK: Multi-Agent LLM Reasoning for Foreign Key Detection in Large-Scale Complex Databases

LLM-FK: Multi-Agent LLM Reasoning for Foreign Key Detection in Large-Scale Complex Databases

Paper · 2026 · Zijian Tang, Ying Zhang, Sibo Cai et al.

Summary

Relational databases often lack declared foreign key (FK) constraints because of schema evolution, legacy migrations, or performance-driven omissions. Recovering them by hand does not scale. Heuristic and supervised detectors rely on name similarity and value inclusion, which break on sparse data or odd naming, and they need tuning or labels. The authors present LLM-FK, a multi-agent LLM pipeline that needs no supervision and targets three problems: an exploding candidate space, limited context, and globally inconsistent local decisions. It uses four agents:

  • a Profiler picks the likeliest referenced unique key per table to prune candidate column pairs;
  • an Interpreter infers domain knowledge from schema metadata;
  • a Refiner reasons over compact structural views from syntactic, semantic and statistical angles;
  • a Verifier builds a schema-wide dependency graph and resolves conflicts such as cyclic references.

On five public benchmarks, LLM-FK exceeds 93% F1 everywhere and cuts the search space drastically without missing true FKs. This makes automated FK recovery practical for large real-world schemas, supporting tasks such as reverse engineering and data integration.

Key points

  • Evaluated on TPC-H, Northwind, TPC-E, AdventureWorks and MusicBrainz, with F1 above 93% on all five.
  • On MusicBrainz (300+ tables), it beats heuristic and LLM baselines by about 15% F1.
  • Candidate pruning makes the search space 100 to 1,000 times smaller while still recalling every FK.
  • Multi-Perspective CoT adds up to 38% F1 when schema names are hidden (MusicBrainz), and F1 stays above 90% even with empty tables.
  • Holistic Conflict Resolution raises precision by 14–36% while largely keeping recall. All detected cycles were of length 2.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Fields, topics and concepts

📚 Shelves 6The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 worksInformation Systems · 1,437 worksComputer Networks and Communications · 64 works

🧭 Topics 1Research subjects and languages the work is about.Reasoning · 1,426 works

Cite

Cite as Zijian Tang, Ying Zhang, Sibo Cai and Ruoxuan Wang. 2026. LLM-FK: Multi-Agent LLM Reasoning for Foreign Key Detection in Large-Scale Complex Databases. Findings of the Association for Computational Linguistics: ACL 2026.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2026.findings-acl.1660

@inproceedings{tang2026llm,
  title = {{LLM-FK: Multi-Agent LLM Reasoning for Foreign Key Detection in Large-Scale Complex Databases}},
  author = {Zijian Tang, Ying Zhang, Sibo Cai and Ruoxuan Wang},
  booktitle = {Findings of the Association for Computational Linguistics: ACL 2026},
  year = {2026},
  doi = {10.18653/v1/2026.findings-acl.1660},
  url = {https://doi.org/10.18653/v1/2026.findings-acl.1660}
}

References

69 references, 14 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Ziawasch Abedjan, Lukasz Golab, and Felix Naumann. 2015. Profiling relational data: a survey. The VLDB Journal, 24(4):557–581. find
  2. Zhoujun Cheng, Tianbao Xie, Peng Shi, Chengzu Li, Rahul Nadkarni, Yushi Hu, Caiming Xiong, Dragomir Radev, Mari Ostendorf, Luke Zettlemoyer, and 1 others. 2022. Binding language models in symbolic languages. arXiv preprint arXiv:2210.02875.
  3. Archita Agarwal, Marilyn George, Aaron Jeyaraj, and Malte Schwarzkopf. 2021. Retrofitting gdpr compliance onto legacy databases. Proceedings of the VLDB Endowment, 15(4). find
  4. Cody James Christopher, Kristen Moore, and David Liebowitz. 2021. Schemadb: Structures in relational datasets. arXiv preprint arXiv:2111.12835. — [arXiv:2111.12835](https://arxiv.org/abs/2111.12835) find
  5. Alibaba. 2022. Alibaba-Java-Coding-Guidelines: GitHub repository. GitHub Repository, accessed 2026-02-05. find
  6. Fabien De Marchi, Stéphane Lopes, and Jean-Marc Petit. 2002. Efficient algorithms for mining inclusion dependencies. In International Conference on Extending Database Technology, pages 464–476. Springer. find
  7. Michael Armbrust, Ali Ghodsi, Reynold Xin, Matei Zaharia, and 1 others. 2021. Lakehouse: a new generation of open platforms that unify data warehousing and advanced analytics. In Proceedings of CIDR, volume 8, page 28. sn. find
  8. Till Döhmen, Radu Geacu, Madelon Hulsebos, and Sebastian Schelter. 2024. Schemapile: a large collection of relational database schemas. Proceedings of the ACM on Management of Data, 2(3):1–25. find
  9. Simone Balloccu, Patrícia Schmidtová, Mateusz Lango, and Ondřej Dušek. 2024. Leak, cheat, repeat: Data contamination and evaluation malpractices in closed-source llms. In Proceedings of the 18th Conference of the European Chapter of the Association for Computational Linguistics (Volume 1: Long Pape…
  10. Falco Dürsch, Axel Stebner, Fabian Windheuser, Maxi Fischer, Tim Friedrich, Nils Strelow, Tobias Bleifuß, Hazar Harmouch, Lan Jiang, Thorsten Papenbrock, and 1 others. 2019. Inclusion dependency discovery: An experimental evaluation of thirteen algorithms. In Proceedings of the 28th ACM Internationa… find
  11. Jana Bauckmann, Ulf Leser, Felix Naumann, and Véronique Tietz. 2006. Efficiently detecting inclusion dependencies. In 2007 ieee 23rd international conference on data engineering, pages 1448–1450. IEEE. find
  12. Philip A Bernstein and Eric Newcomer. 2009. Principles of transaction processing. Morgan Kaufmann. find
  13. Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, and 1 others. 2020. Language models are few-shot learners. Advances in neural information processing systems, 33:1877–1901.
  14. Shimin Chen, Anastasia Ailamaki, Manos Athanas-soulis, Phillip B Gibbons, Ryan Johnson, Ippokratis Pandis, and Radu Stoica. 2011. Tpc-e vs. tpc-c: Characterizing the new tpc-e benchmark via an i/o comparison study. ACM Sigmod Record, 39(3):5–10. find
  15. Si-An Chen, Lesly Miculicich, Julian M Eisenschlos, Zifeng Wang, Zilong Wang, Yanfei Chen, Yasuhisa Fujii, Hsuan-Tien Lin, Chen-Yu Lee, and Tomas Pfister. 2024. Tablerag: Million-token table understanding with language models. Advances in Neural Information Processing Systems, 37:74899–74921. find
  16. Wenhu Chen. 2023. Large language models are few (1)-shot table reasoners. In Findings of the association for computational linguistics: EACL 2023, pages 1120–1130.
  17. Zhimin Chen, Vivek Narasayya, and Surajit Chaudhuri. 2014. Fast foreign-key detection in microsoft sql server powerpivot for excel. Proceedings of the VLDB Endowment, 7(13):1417–1428. find
  18. Raul Castro Fernandez, Ziawasch Abedjan, Famien Koko, Gina Yuan, Samuel Madden, and Michael Stonebraker. 2018. Aurum: A data discovery system. In 2018 IEEE 34th International conference on data engineering (ICDE), pages 1001–1012. IEEE. find
  19. Raul Castro Fernandez, Aaron J Elmore, Michael J Franklin, Sanjay Krishnan, and Chenhao Tan. 2023. How large language models will disrupt data management. Proceedings of the VLDB Endowment, 16(11):3302–3309. find
  20. Dawei Gao, Haibin Wang, Yaliang Li, Xiuyu Sun, Yichen Qian, Bolin Ding, and Jingren Zhou. 2023. Text-to-sql empowered by large language models: A benchmark evaluation. arXiv preprint arXiv:2308.15363.
  21. Cyril Goutte and Eric Gaussier. 2005. A probabilistic interpretation of precision, recall and f-score, with implication for evaluation. In European conference on information retrieval, pages 345–359. Springer. find
  22. Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Alex Vaughan, and 1 others. 2024. The llama 3 herd of models. arXiv preprint arXiv:2407.21783.
  23. Shuhao Guan and Derek Greene. 2024. Advancing post-ocr correction: A comparative study of synthetic data. In Findings of the Association for Computational Linguistics: ACL 2024, pages 6036–6047. find
  24. Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Peiyi Wang, Qihao Zhu, Runxin Xu, Ruoyu Zhang, Shirong Ma, Xiao Bi, and 1 others. 2025. find
  25. Deepseek-r1: Incentivizing reasoning capability in llms via reinforcement learning. arXiv preprint arXiv:2501.12948.
  26. Taicheng Guo, Xiuying Chen, Yaqi Wang, Ruidi Chang, Shichao Pei, Nitesh V Chawla, Olaf Wiest, and Xiangliang Zhang. 2024. Large language model based multi-agents: A survey of progress and challenges. arXiv preprint arXiv:2402.01680.
  27. Rihan Hai, Christos Koutras, Christoph Quix, and Matthias Jarke. 2023. Data lakes: A survey of functions and systems. IEEE Transactions on Knowledge and Data Engineering, 35(12):12571–12590. find
  28. Alon Halevy, Michael Franklin, and David Maier. 2006. Principles of dataspace systems. In Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 1–9. find
  29. Jan L Harrington. 2016. Relational database design and implementation. Morgan Kaufmann. find
  30. Gonzalo Jaimovitch-López, Cèsar Ferri, José Hernández-Orallo, Fernando Martínez-Plumed, and María José Ramírez-Quintana. 2023. Can language models automate data wrangling? Machine Learning, 112(6):2053–2082. find
  31. Lan Jiang and Felix Naumann. 2020. Holistic primary key and foreign key detection. Journal of Intelligent Information Systems, 54(3):439–461. find
  32. Theodore Johnson, Amit Marathe, and Tamraparni Dasu. 2003. Database exploration and bellman. IEEE Data Eng. Bull., 26(3):34–39. find
  33. Youri Kaminsky, Eduardo HM Pena, and Felix Naumann. 2023. Discovering similarity inclusion dependencies. Proceedings of the ACM on Management of Data, 1(1):1–24. find
  34. Moe Kayali, Anton Lykov, Ilias Fountalis, Nikolaos Vasiloglou, Dan Olteanu, and Dan Suciu. 2023. Chorus: foundation models for unified data discovery and exploration. arXiv preprint arXiv:2306.09610. — [arXiv:2306.09610](https://arxiv.org/abs/2306.09610) find
  35. Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, and Tie-Yan Liu. 2017. Lightgbm: A highly efficient gradient boosting decision tree. Advances in neural information processing systems, 30. find
  36. Yiming Lin, Yeye He, and Surajit Chaudhuri. 2023. Auto-bi: Automatically build bi-models leveraging local join prediction and global schema graph. arXiv preprint arXiv:2306.12515. — [arXiv:2306.12515](https://arxiv.org/abs/2306.12515) find
  37. Jim Melton and Alan R Simon. 2001. find
  38. SQL: 1999: understanding relational language components. Elsevier. find
  39. Microsoft. 2023a. AdventureWorks Sample Database: GitHub repository. GitHub Repository, accessed 2025-03-24. find
  40. Microsoft. 2023b. Northwind Sample Database: GitHub repository. GitHub Repository, accessed 2025-03-24. find
  41. Avanika Narayan, Ines Chami, Laurel Orr, Simran Arora, and Christopher Ré. 2022. Can foundation models wrangle your data? arXiv preprint arXiv:2205.09911. — [arXiv:2205.09911](https://arxiv.org/abs/2205.09911) find
  42. Sam Newman. 2021. Building microservices: designing fine-grained systems. " O’Reilly Media, Inc.". find
  43. Thorsten Papenbrock, Tanja Bergmann, Moritz Finke, Jakob Zwiener, and Felix Naumann. 2015a. Data profiling with metanome. Proceedings of the VLDB Endowment, 8(12):1860–1863. find
  44. Thorsten Papenbrock, Sebastian Kruse, Jorge-Arnulfo Quiané-Ruiz, and Felix Naumann. 2015b. Divide & conquer-based inclusion dependency discovery. Proceedings of the VLDB Endowment, 8(7):774–785. find
  45. Meikel Poess and Chris Floyd. 2000. New tpc benchmarks for decision support and web commerce. ACM Sigmod Record, 29(4):64–71. find
  46. Alexandra Rostin, Oliver Albrecht, Jana Bauckmann, Felix Naumann, and Ulf Leser. 2009. A machine learning approach to foreign key discovery. In WebDB. find
  47. Aaditya Singh, Adam Fry, Adam Perelman, Adam Tart, Adi Ganesh, Ahmed El-Kishky, Aidan McLaughlin, Aiden Low, AJ Ostrow, Akhila Ananthram, and 1 others. 2025. Openai gpt-5 system card. arXiv preprint arXiv:2601.03267.
  48. Georg Lausen. 2007. Relational databases in rdf: Keys and foreign keys. In Workshop on Ontologies-based techniques for DataBases and Information Systems, pages 43–56. Springer. find
  49. Songyuan Sui, Hongyi Liu, Serena Liu, Li Li, Soo-Hyun Choi, Rui Chen, and Xia Hu. 2025. Chain-of-query: Unleashing the power of llms in sql-aided table understanding via multi-agent collaboration. In Proceedings of the 14th International Joint Conference on Natural Language Processing and the 4th Co… find
  50. Jinyang Li, Binyuan Hui, Ge Qu, Jiaxi Yang, Binhua Li, Bowen Li, Bailin Wang, Bowen Qin, Ruiying Geng, Nan Huo, and 1 others. 2023. Can llm already serve as a database interface? a big bench for large-scale database grounded text-to-sqls. Advances in Neural Information Processing Systems, 36:42330–4…
  51. Yuan Sui, Mengyu Zhou, Mingjie Zhou, Shi Han, and Dongmei Zhang. 2024a. Table meets llm: Can large language models understand structured table data? a benchmark and empirical study. In Proceedings of the 17th ACM International Conference on Web Search and Data Mining, pages 645–654. find
  52. Robert E Kent. 2012. Database semantics. arXiv preprint arXiv:1209.3054. — [arXiv:1209.3054](https://arxiv.org/abs/1209.3054) find
  53. Yuan Sui, Jiaru Zou, Mengyu Zhou, Xinyi He, Lun Du, Shi Han, and Dongmei Zhang. 2024b. Tap4llm: Table provider on sampling, augmenting, and packing semi-structured data for large language model reasoning. In Findings of the Association for Computational Linguistics: EMNLP 2024, pages 10306– 10323. find
  54. Yunhu Ye, Binyuan Hui, Min Yang, Binhua Li, Fei Huang, and Yongbin Li. 2023. Large language models are versatile decomposers: Decomposing evidence and questions for table-based reasoning. In Proceedings of the 46th international ACM SIGIR conference on research and development in information retriev… find
  55. Aaron Swartz. 2002. Musicbrainz: A semantic web service. IEEE Intelligent Systems, 17(1):76–77. find
  56. Peiying Yu, Guoxin Chen, and Jingjing Wang. 2025. Table-critic: A multi-agent framework for collaborative criticism and refinement in table reasoning. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 17432–17451.
  57. Fabian Tschirschnitz, Thorsten Papenbrock, and Felix Naumann. 2017. Detecting inclusion dependencies on very many tables. ACM Transactions on Database Systems (TODS), 42(3):1–29. find
  58. Bing Wang, Changyu Ren, Jian Yang, Xinnian Liang, Jiaqi Bai, Linzheng Chai, Zhao Yan, Qian-Wen Zhang, Di Yin, Xing Sun, and 1 others. 2025a. Mac-sql: A multi-agent collaborative framework for text-to-sql. In Proceedings of the 31st International Conference on Computational Linguistics, pages 540–557…
  59. Xixi Wang, Miguel Costa, Jordanka Kovaceva, Shuai Wang, and Francisco C Pereira. 2025b. Plugging schema graph into multi-table qa: A human-guided framework for reducing llm reliance. In Findings of the Association for Computational Linguistics: EMNLP 2025, pages 5829–5842. find
  60. Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, and 1 others. 2022. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824– 24837.
  61. Jian Wu, Linyi Yang, Dongyuan Li, Yuliang Ji, Manabu Okumura, and Yue Zhang. 2025. Mmqa: Evaluating llms with multi-table multi-hop complex questions. In The thirteenth international conference on learning representations. find
  62. Xiaoyu Wu, Ning Wang, and Huaxi Liu. 2019. Discovering foreign keys on web tables with the crowd. Computing and Informatics, 38(3):621–646. find
  63. Wenxuan Xie, Gaochen Wu, and Bowen Zhou. 2024. Mag-sql: Multi-agent generative approach with soft schema linking and iterative sub-sql refinement for text-to-sql. arXiv preprint arXiv:2408.07930. — [arXiv:2408.07930](https://arxiv.org/abs/2408.07930) find
  64. Cong Yan and Yeye He. 2020. Auto-suggest: Learningto-recommend data preparation steps using data science notebooks. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, pages 1539–1554. find
  65. An Yang, Anfeng Li, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Gao, Chengen Huang, Chenxu Lv, and 1 others. 2025. Qwen3 technical report. arXiv preprint arXiv:2505.09388.
  66. Bin Zhang, Hangyu Mao, Lijuan Li, Zhiwei Xu, Dapeng Li, Rui Zhao, and Guoliang Fan. 2024. Sequential asynchronous action coordination in multi-agent systems: A stackelberg decision transformer approach. In Forty-first International Conference on Machine Learning. find
  67. Meihui Zhang, Marios Hadjieleftheriou, Beng Chin Ooi, Cecilia M Procopiuc, and Divesh Srivastava. 2010. On multi-column foreign key discovery. Proceedings of the VLDB Endowment, 3(1-2):805–814. find
  68. Wei Zhou, Mohsen Mesgar, Annemarie Friedrich, and Heike Adel. 2025. Efficient multi-agent collaboration with tool use for online planning in complex table question answering. In Findings of the Association for Computational Linguistics: NAACL 2025, pages 945–968. find
  69. Jun-Peng Zhu, Peng Cai, Kai Xu, Li Li, Yishen Sun, Shuai Zhou, Haihuang Su, Liu Tang, and Qi Liu. 2024. Autotqa: Towards autonomous tabular question answering through multi-agent large language models. Proceedings of the VLDB Endowment, 17(12):3920–3933. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/tang-2026-llm-fk-multi-agent-llm/