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

Zijian Tang, Ying Zhang, Sibo Cai, Ruoxuan WangarXiv 2026 · DOI · arXiv

TL;DR

This paper introduces LLM-FK, a novel multi-agent framework that leverages Large Language Models (LLMs) to automatically detect missing Foreign Key (FK) constraints in large, complex databases. By breaking down the problem into specialized agent tasks, LLM-FK overcomes the limitations of traditional methods and naive LLM applications, achieving state-of-the-art accuracy and efficiency.

What Problem Does This Paper Address?

Foreign Key (FK) constraints are crucial for maintaining data integrity and enabling efficient data operations in relational databases. However, these constraints are often missing in real-world databases due to schema evolution, legacy system migration, or intentional omission. Manually identifying these missing FKs is infeasible for large-scale databases. Existing automated methods, primarily based on heuristics, struggle to capture the deep semantic dependencies that FKs represent, leading to poor performance on complex and heterogeneous schemas. Naively applying LLMs to this problem faces challenges like combinatorial explosion of candidate pairs, ambiguous reasoning due to limited context, and global inconsistencies arising from isolated predictions.

Methods

LLM-FK tackles these challenges through a sophisticated multi-agent architecture, with each agent designed to address a specific problem:

  • Profiler: This agent decomposes the FK detection problem into manageable column-pair validation tasks. It employs a "Unique-Key-Driven Schema Decomposition Strategy" to aggressively prune the search space by identifying plausible referenced unique keys, significantly reducing the number of candidate FKs without sacrificing recall.
  • Interpreter: This agent injects "Self-Augmented Domain Knowledge" by analyzing table names to infer the overall database domain and key entities. This global context helps disambiguate local reasoning tasks.
  • Refiner: This agent performs "Multi-Perspective Chain-of-Thought (CoT) Reasoning." It integrates domain knowledge with serialized structural representations (derived from SQL queries) to conduct deep, evidence-based inference on candidate FK pairs from syntactic, semantic, and statistical viewpoints.
  • Verifier: This agent ensures "Holistic Conflict Resolution" by constructing a schema-level dependency graph. It identifies and resolves structural violations like multiple references and cyclic references, guaranteeing a globally coherent FK set.

Datasets

The authors evaluated LLM-FK on five widely adopted relational database benchmarks:

  • TPC-H
  • Northwind
  • TPC-E
  • AdventureWorks
  • MusicBrainz

These datasets span diverse domains (commerce, retail, finance, manufacturing, entertainment) and vary in schema scale and complexity, providing a comprehensive testbed for the framework.

Key Insights and Ideas

  • Decomposition is Key: Breaking down the complex FK detection problem into specialized tasks handled by distinct agents is crucial for scalability and accuracy, especially in large databases.
  • Domain Knowledge is Power: Injecting global domain context (even inferred from table names) significantly improves the LLM's ability to resolve semantic ambiguities and make accurate FK predictions.
  • Multi-Perspective Reasoning: Combining syntactic, semantic, and statistical signals, rather than relying on any single one, leads to more robust and reliable FK detection, particularly in challenging scenarios like missing data or obscure naming conventions.
  • Unique Keys Over Primary Keys: Targeting minimal unique combinations (MinUCCs) for candidate referenced keys is more effective for pruning than relying on potentially missing or overly composite primary keys.

Key Results

  • LLM-FK consistently achieved F1-scores exceeding 93% across all five benchmark datasets.
  • It outperformed existing baselines by up to 15% on the large-scale MusicBrainz database.
  • The framework reduced the candidate search space by two to three orders of magnitude without losing any true FKs.
  • LLM-FK demonstrated strong robustness under challenging conditions like missing data and ambiguous semantic relationships.
  • The multi-agent approach effectively addressed the limitations of naive LLM applications, showing superior stability and generalizability.

Limitations and Future Work

  • Unexplored Domains: While tested on diverse benchmarks, LLM-FK's performance on extremely large-scale or highly heterogeneous database domains beyond those evaluated remains to be explored.
  • Domain-Agnostic Design: The framework is designed to be domain-agnostic, relying solely on schema-inherent signals. While this enhances generalizability, future work could explore how domain-specific knowledge could further enhance performance.
  • Modular Extension: The authors highlight the modular nature of the multi-agent design, suggesting seamless extension to new databases and potential integration with other database management tasks.

Summary updated

BibTeX
@misc{tang2026llm,
  author = {Zijian Tang and Ying Zhang and Sibo Cai and Ruoxuan Wang},
  title = {{LLM-FK: Multi-Agent LLM Reasoning for Foreign Key Detection in Large-Scale Complex Databases}},
  year = {2026},
  eprint = {2603.07278},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2603.07278},
}
Figure