Technical Summary: Database Normalization via Dual-LLM Self-Refinement

Problem Statement

Database normalization is a critical process for preserving data integrity in relational databases by eliminating redundancy and anomalies through adherence to normal forms (1NF, 2NF, 3NF, etc.). However, this process remains largely manual, requiring data engineers to identify functional dependencies and systematically decompose schemas. As data volumes grow, this manual approach becomes increasingly time-consuming and error-prone. While various data management tools exist, they typically rely on semi-automated processes that require users to manually specify functional dependencies, failing to handle real-world schemas where dependencies are often implicit or unclear. Furthermore, while Large Language Models (LLMs) have shown promise in symbolic reasoning, naively applying them to database normalization often yields inaccurate results due to the nuanced semantic relationships between columns that are difficult to capture without specific guidance.

Methodology: The Miffie Framework

To address these challenges, the authors propose Miffie, an LLM-based framework designed to automate database normalization with minimal human effort while maintaining high accuracy. The core of Miffie is a dual-model self-refinement architecture combined with task-specific zero-shot prompting.

1. Dual-Model Self-Refinement Architecture

Unlike traditional self-refinement approaches where a single model iteratively critiques and improves its own output, Miffie utilizes two distinct LLMs optimized for specific roles:

• Generation Module: Responsible for producing the normalized schema. The authors empirically determined that GPT-4 offers the most balanced accuracy across different normal forms for schema generation.
• Verification Module: Responsible for rigorously assessing the correctness of the generated schema. The authors found that o1-mini achieves near-perfect anomaly detection rates across all normal forms.

Workflow:

1. The user provides an initial, potentially anomalous schema.
2. The Generation Module produces a normalized schema.
3. The Verification Module checks the output against normalization criteria (1NF through 3NF).
4. If violations are detected, the Verification Module generates specific feedback (explaining the anomaly and suggesting resolutions, such as splitting tables).
5. The Generation Module uses this feedback to refine the schema.
6. This iterative loop continues until the schema passes verification or a maximum attempt threshold is reached.

2. Task-Specific Zero-Shot Prompting

To ensure high accuracy and cost efficiency, the authors designed specific zero-shot prompts rather than relying on few-shot examples (which increase token consumption).

• Generation Prompts: These provide structured instructions listing specific criteria and representative violation patterns for each normal form (e.g., prohibiting multivalued attributes for 1NF, identifying partial dependencies for 2NF, and transitive dependencies for 3NF). The prompts enforce a fixed SQL output format to prevent parsing errors.
• Verification Prompts: These instruct the model to perform binary compliance checks (1 for compliant, 0 for violation) for each normal form. Crucially, the verification follows the monotonic nature of normalization: if a lower normal form is violated, all higher forms are automatically marked as non-compliant. The verifier also provides brief explanations of detected anomalies to guide the next refinement.

Experimental Evaluation

The authors evaluated Miffie using a controlled benchmark suite consisting of three real-world domain schemas: Orders (E-commerce), Advertising (Online Services), and AirportDB (Logistics). To ensure precise ground truth, the authors systematically injected five distinct anomalies for each normal form (1NF, 2NF, 3NF) into these schemas.

Key Results

• Accuracy vs. Baselines: Miffie significantly outperformed a "vanilla" zero-shot prompt (unstructured instructions), achieving roughly 1.2× higher accuracy across all normal forms.
• Prompting Efficiency: The task-specific zero-shot prompt achieved accuracy comparable to or exceeding that of one-shot and few-shot prompts while consuming significantly fewer tokens (325 tokens vs. 628 for one-shot and 1.1K for few-shot).
• Dual-Model Superiority: Comparing Miffie against single-model architectures (using only GPT-4 or only o1-mini for both generation and verification), the dual-model approach achieved the highest accuracy and the highest elimination rate (72% of cases fully resolved within 3 tries). This confirms that separating generation and verification tasks leverages the specific strengths of different models.
• Convergence: Most normalization tasks converged within three iterations. The authors observed that beyond three iterations, the LLM struggled to resolve remaining anomalies, leading them to set the maximum refinement loop to three to balance accuracy and cost.
• Complexity Handling: Miffie maintained high accuracy on "Easy" and "Medium" complexity schemas. On "Hard" complexity schemas, accuracy slightly decreased with higher variance, which the authors attribute to inherent semantic ambiguities in complex real-world schemas allowing for multiple valid normalization paths, rather than model failure.

Significance and Contributions

The paper claims the following contributions:

1. First Automated Framework: Miffie is presented as the first LLM-based framework specifically designed to automate database normalization, significantly reducing human effort while preserving data integrity.
2. Novel Architecture: The proposal of a dual-model self-refinement architecture that utilizes different models for generation and verification, optimized via task-specific zero-shot prompting, represents a departure from standard single-model iterative refinement.
3. Empirical Validation: Comprehensive experiments demonstrate that Miffie is effective, robust, and cost-efficient, capable of normalizing complex, real-world database schemas with high accuracy.

The authors conclude that while their current work focuses on 1NF through 3NF, the prompt-driven nature of the framework allows for future extension to higher normal forms (such as BCNF and 4NF) by updating the verification instructions.