PaperlayerView exact revision on arXiv

Source-linked AI summary

Can LLMs Normalize Databases? A Benchmark and Multi-Agent Framework for Schema Normalization

Dong-Jae Koh, Huisu Kim, SeongHwan Yoon, Lasse M. Jantsch, Chun-Hee Lee, Seonghyeon Lee, Young-Kyoon Suh

arXiv:2609.11141v1cs.CL

TL;DR

The paper asks whether LLMs can reliably normalize databases under dependency, lossless-join, and inter-table constraints. It introduces DNBENCH and MARS, finding that multi-agent decomposition improves DNB-SCORE by 82.0% over the baseline while revealing persistent foreign-key and BCNF reasoning difficulties.

  • Problem

    LLM reliability is insufficiently understood when database normalization requires functional-dependency reasoning, lossless decompositions, and valid inter-table constraints.

  • Method

    The paper introduces DNBENCH, a 3,275-sample benchmark with semantic, structural, and logical evaluation, and MARS, which separates normalization into specialized agent subtasks.

  • Results

    82.0% improvement in DNB-SCORE over the baseline is reported for MARS, while the benchmark identifies failures in dependency inference, decomposition, and inter-table constraint reconstruction.

  • Takeaways & Limitations

    DNBENCH and MARS provide a systematic basis for evaluating and decomposing LLM-driven database normalization.

  • Takeaways & Limitations

    Foreign-key reconstruction remains a bottleneck, and BCNF reasoning and recognition of already-normalized schemas remain unresolved.

Abstract

from arXiv · show

Large Language Models (LLMs) are increasingly used to generate structured outputs, but their reliability remains unclear when those outputs must satisfy database-level constraints. We study this issue through database normalization, involving reasoning about functional dependencies, lossless join decompositions, and inter-table constraints. We introduce a Database Normalization Benchmark (DNBENCH), comprising 3,275 samples for evaluating LLM-driven database normalization from 1NF to BCNF. DNBENCH uses a three-axis protocol to measure semantic equivalence, structural accuracy, and logical validity. Across Single, Complex, and Real World levels, DNBENCH uncovers recurring failures in dependency inference, schema decomposition, and inter-table constraint reconstruction. We further propose Multi-Agent Reasoning for Schemas (MARS), which separates evidence extraction, violation diagnosis, and decomposition planning from schema generation and verification. MARS improves the DNB-SCORE by 82.0% over the single-prompt baseline. All artifacts will be released upon acceptance.

1 Introduction

LLM-based database normalization requires both dependency reasoning and schema generation under formal relational constraints, but its reliability remains insufficiently understood. The paper addresses this gap with DNBENCH and MARS.

  • Database normalization challenges LLMs to reason over functional dependencies, candidate keys, lossless joins, and dependency preservation while generating valid schemas.Poor normalization can introduce redundancy, update anomalies, inconsistency, unnecessary query costs, and degraded data quality.
  • Prior studies provide limited evidence because related systems target table cleaning, anomaly detection, or narrower normalization settings rather than comprehensive schema normalization.The paper specifically contrasts these limitations with its benchmark and framework.
  • DNBENCH evaluates LLM normalization with 3,275 samples covering 1NF-to-BCNF violations and three axes: semantic, structural, and logical validity.Its contributions include a unified evaluation protocol for generated schemas.
  • 82.0% more reliable DDLs are produced by MARS than naive prompting while preserving inter-table constraints.The paper reports this average improvement in its experiments.
  • The paper identifies unreliable functional-dependency inference, invalid decomposition, and weak inter-table constraint reconstruction as major failure patterns.

2 Related Work

Prior normalization tools and LLM systems address pieces of the problem, but they do not provide a comprehensive benchmark for reliable database schema normalization. DNBENCH fills this gap with broader coverage and multifaceted evaluation.

  • DNBENCH provides a comprehensive benchmark and multifaceted protocol absent from prior normalization tools and LLM-based methods.Table 1 compares normalization coverage, complex multi-violation handling, and schema- and explanation-level evaluation.
  • Traditional tools such as RDBNorma and EDNA support normalization procedures but lack broad quantitative evaluation of semantic preservation, key validity, lossless decomposition, or robustness.RDBNorma focuses mainly on runtime and memory, while EDNA relies on user-specified functional dependencies.
  • NormTab performs value-level and structural cleaning of web tables for downstream question answering and fact verification rather than database schema normalization.It does not evaluate functional-dependency reasoning, lossless decomposition, or valid normalized schemas.
  • TABARD evaluates anomalous-cell detection and does not target normal-form violations, dependency diagnosis, or schema decomposition.
  • Miffie uses a dual-LLM generation and feedback loop for 1NF-to-3NF normalization, but its verifier lacks explicit checks for lossless join, key validity, and foreign-key connectivity.DNBENCH instead combines semantic judgment with explicit structural and logical checks.

3 Database Normalization Benchmark

DNBENCH constructs controlled denormalization samples from realistic schemas and evaluates generated normalization outputs across semantic, structural, and logical criteria. Its dataset and protocol jointly test decomposition quality, constraint validity, and reasoning correctness.

  • Dataset construction: DNBENCH transforms real-world relational databases into controlled denormalized samples with gold violation labels, decompositions, and expected constraints.The benchmark evaluates generated DDL, violation labels, and explanations.
  • Dataset construction: 3,275 samples are built from realistic Spider and BIRD schemas using FK-aware subsampling, hybrid violation injection, and chain-rule labeling.Three database experts audited the generated samples and confirmed intended violation patterns and decompositions.
  • Dataset construction: Composite synthesis injects BCNF, 3NF, 2NF, and 1NF violations in reverse chain-rule order so lower-form injections do not erase higher-form violations.The resulting samples distinguish fixing only the earliest violation from normalizing the full violation chain.
  • Three-Axis Evaluation Protocol: Semantic evaluation checks whether generated relations losslessly rejoin to the input table, and any semantic failure reduces the final DNB-SCORE to zero.
  • Three-Axis Evaluation Protocol: Structural evaluation averages Column F1, Primary Key F1, and Foreign Key Score, with foreign-key validity requiring references to extant tables and columns.
  • Three-Axis Evaluation Protocol: Logical evaluation combines LLM-judge assessments of schemas and explanations with Violation F1 for predicted normal-form violations.The final score averages the judge score across three dimensions with Violation F1.

4 Database Normalization Analysis

DNBENCH evaluates LLM database normalization across increasing violation complexity and FD availability, revealing that models struggle most with dependency inference and global schema reconstruction.

  • Experimental Setup: DNBENCH uses 3,275 test samples and evaluates generated schemas with DNB-SCORE components covering semantic, structural, and logical quality.The benchmark includes denormalized inputs, row samples, violation labels, decompositions, and expected schema constraints.
  • Experimental Setup: The benchmark tests single-violation repair, multi-step decomposition, and latent-FD inference across Single, Complex, and Real World settings.These settings vary normalization scope and whether functional dependencies are explicitly provided.
  • Experimental Findings: 0.188 average DNB-SCORE in Real World, down from 0.328 in Single and 0.285 in Complex, shows the sharpest degradation when FDs must be inferred.The Real World setting withholds formal FDs and requires inference from table samples and business rules.
  • Baseline Analysis: Violation F1 reaches 0.678, but FK Score remains 0.10–0.17, indicating stronger violation detection than valid schema reconstruction.The component breakdown separates diagnosis from schema generation and highlights weak inter-table constraint reconstruction.
  • Failure Analysis: Models commonly struggle with multiple violations, BCNF reasoning, and already-normalized inputs, sometimes introducing unnecessary decompositions.These patterns motivate separating reasoning stages and adding explicit verification.

5 Multi-Agent Reasoning for Schemas

MARS decomposes database normalization into specialized reasoning, generation, verification, and targeted repair stages. In Real World evaluation, it improves normalized DDL quality over single-prompt and self-refinement baselines, while FD inference and foreign-key reconstruction remain bottlenecks.

  • 5.1 MARS Framework: MARS separates evidence extraction, violation diagnosis and decomposition planning, schema generation, and deterministic verification.The framework uses role-specialized agents and routes verification failures to targeted repair rounds.
  • 5.3 Experiment Results: MARS improves DNB-SCORE from 0.253 to 0.423 in zero-shot and from 0.209 to 0.418 in few-shot Real World evaluation.MARS achieves the highest score in both settings using Qwen3-30B as the shared backbone.
  • 5.2 Experiment Settings: MARS outperforms both the single-prompt Baseline and Miffie self-refinement framework under matched Real World evaluation settings.MARS and Miffie allow at most three generation attempts, while all Table 6 methods use Qwen3-30B.
  • 5.3 Experiment Results: Miffie improves local schema consistency but weakens diagnosis, with low FK performance and reduced Violation F1 despite stronger lossless-join and local-schema scores.Its LLM-based verifier also struggles to distinguish high- from low-quality normalized schemas.
  • 5.3 Experiment Results: MARS gains are concentrated in semantic and structural components, especially lossless join and FK Score, while Violation F1 remains close to the Baseline.The results attribute the DNB-SCORE improvement mainly to information preservation and more robust schema structure rather than better violation classification.
  • 5.3 Experiment Results: Stage-wise artifacts identify upstream FD inference and violation diagnosis as bottlenecks, while schema generation aligns more reliably once a plausible diagnosis plan exists.Errors in the upstream stages complicate later key selection and foreign-key reconstruction.

6 Conclusion

The paper introduces DNBENCH to evaluate LLM-driven database normalization across semantic, structural, and logical dimensions, and uses it to expose recurring weaknesses. MARS addresses these weaknesses by separating normalization stages and outperforms the single-prompt and self-refinement baselines.

  • 6 Conclusion: DNBENCH contains controlled denormalization data and evaluates semantic, structural, and logical validity with a three-axis protocol.The benchmark is designed to assess whether generated schemas preserve information and satisfy inter-table constraints.
  • 6 Conclusion: LLMs often identify normalization violations but struggle to generate information-preserving schemas with valid inter-table constraints when functional dependencies must be inferred.This conclusion summarizes the benchmark’s empirical finding about diagnosis versus schema reconstruction.
  • 6 Conclusion: MARS separates FD evidence extraction, violation diagnosis, decomposition planning, schema generation, and verification, outperforming single-prompt and self-refinement baselines.The paper presents this decomposition as the response to the identified normalization weaknesses.

Limitations

MARS improves normalization reliability but remains limited by foreign-key reconstruction, BCNF reasoning, unnecessary decomposition, inference cost, and sensitivity to upstream errors.

  • Foreign-Key Reconstruction: Foreign-key reconstruction remains a bottleneck because preserving local table information is easier than recovering reference structure across decomposed relations.The limitation involves relation boundaries, key choices, reference targets, and upstream dependency or diagnosis errors.
  • BCNF and NONE Cases: BCNF-only inputs and already-normalized schemas remain difficult, requiring stronger semantic reasoning about candidate keys and key structure.Intermediate validation does not resolve these cases, including unnecessary decomposition of NONE inputs.
  • Inference Cost: MARS requires a higher inference budget because it uses multiple LLM calls for evidence extraction, diagnosis, generation, and repair.The additional cost should be interpreted alongside its performance gains.
  • Upstream Sensitivity: Verifier-based repair handles local synthesis errors more effectively than incorrect functional-dependency evidence or decomposition plans.Future work is directed toward adaptive routing and stronger evidence extraction.

A Dataset Details

DNBENCH is built from realistic Spider and BIRD relational schemas, which are sampled and validated to preserve database structure before controlled denormalization.

  • Source Datasets: Spider contains 10,181 natural-language queries and 5,693 unique SQL queries across 200 databases and 138 domains.Its databases average 5.1 tables and foreign-key relationships.
  • Source Datasets: BIRD comprises 95 databases, 33.4 GB of data, 37 specialized domains, and 12,751 query–SQL pairs.
  • Source Dataset Selection: DNBENCH uses Spider and BIRD because their annotated keys, diverse schemas, and relational structure support controlled, structurally faithful denormalization.These properties enable FK-aware subsampling, violation injection, and structural evaluation of generated DDL.
  • Structure-Preserving Sampling: The sampling pipeline preserves primary-key uniqueness and foreign-key referential integrity before later violation injection.It builds an FK graph, expands selected keys through FK and self-FK closures, deduplicates by primary key, caps rows, inserts tables topologically, and removes residual violations.
  • Expert Validation: Three database experts reviewed generated samples for intended 1NF–BCNF violations, chain-rule labels, gold decompositions, and expected constraints.The review validates the generated DNBENCH samples used in the experiments.
  • Model Selection: The benchmark evaluates four open-weight models spanning dense and sparse architectures from 27B to 70B total parameters.The selection is intended to characterize behavior beyond a single model family.

C Experiment Reproducibility

The extended experiments were run as inference-only evaluations with fixed hardware and software configurations, but all reported MARS and Miffie results come from a single run.

  • Hardware and Evaluation Mode: The evaluations used NVIDIA A100-SXM4-40GB GPUs, with one GPU for most models and MARS and two for Llama-3.3-70B.No model fine-tuning or parameter updates were performed.
  • Software Environment: Inference was served through an OpenAI-compatible vLLM server, and evaluation scripts ran in the same software environment.The environment used CUDA 12.2 and NVIDIA Driver 535.161.08.
  • Result Reporting: All MARS and Miffie experimental results were described from a single run.

D Extended Result Tables

The extended tables break down DNB-SCORE across datasets, models, prompting settings, violation paths, and MARS or Miffie configurations, revealing consistent model rankings and greater difficulty for more complex violations.

  • Per-Model Results: Model rankings remain consistent across BIRD and Spider, indicating that the reported ordering generalizes across both source corpora.
  • Violation-Path Results: DNB-SCORE decreases as the number of normal-form violations increases, with NONE highest and mixed 1NF–BCNF cases lowest for every model.
  • Evaluation Matrix: Table 7 provides DNB-SCORE and its three component scores for every dataset, model, prompting setting, and violation-path configuration.Its settings distinguish zero- and few-shot prompts and Single, Complex, and Real World experiments.
  • Agent Comparisons: Tables 8 and 9 provide corresponding Real World evaluation matrices for MARS and Miffie using Qwen3-30B.These tables support direct comparison with the single-prompt Qwen3-30B rows in Table 7.

E Validation of LLM-as-a-Judge

The study validates an LLM judge against expert scoring and finds strong agreement, while showing that human scoring itself includes substantial disagreement. The evaluation also defines a controlled comparison setting for Miffie.

  • The validation samples 50 instances scored independently by three database experts and the LLM judge on a normalized 0–5 rubric.
  • 0.818 average LLM–human QWK indicates strong agreement, compared with 0.852 average human–human QWK.
  • α = 0.633 among humans indicates substantial agreement, while also showing that experts sometimes score the same sample differently.
  • ρ = 0.753 indicates strong agreement between LLM and human score rankings.
  • The agreement gap is statistically indistinguishable from zero because ∆ = +0.034 has a 95% CI of [−0.031, +0.106].
  • Miffie is evaluated with Qwen3-30B in the Real World setting, where explicit FD annotations are not provided, using its generator–verifier refinement structure.

G.1 Miffie Artifact Analysis

Miffie’s iterative generator–verifier refinement performs best when it terminates after one iteration, with DNB-SCORE declining sharply as more iterations are required. Later verifier decisions also do not reliably identify higher-quality normalization outputs.

  • DNB-SCORE falls from 0.4627 after one iteration to 0.1659 after two and 0.0996 after three iterations.
  • Third-iteration verifier-passed samples score only 0.1141 versus 0.0981 for verifier-failed samples.
  • The results indicate that repeated refinement does not reliably recover difficult normalization cases or distinguish schema-level quality.
  • MARS shows higher plan-to-DDL exact match, indicating that schema generation more reliably implements an existing diagnosis plan than it performs FD inference.

G.2 MARS Artifact Analysis

MARS artifact analysis separates evidence extraction, violation diagnosis, planning, generation, and verification to identify where normalization errors arise. The results locate the main bottlenecks in upstream FD recovery and diagnosis, while repair performance worsens after repeated rounds.

  • Only 67 of 1,290 samples requiring two repair rounds pass final verification, while most remain unresolved.
  • Outputs passing verification initially achieve the highest DNB-SCORE, whereas two-repair samples have much lower average scores.
  • Low FD recall and moderate violation-type F1 identify evidence extraction and diagnosis as upstream bottlenecks.
  • The normalization examples decompose schemas into key, detail, sub-detail, and multivalued-detail tables while preserving primary-key and foreign-key relationships.
  • The prompt examples distinguish earliest violations: 1NF begins with multivalued attributes, while later cases proceed through 2NF, 3NF, and BCNF causes.
Loading 2609.11141v1…