Relational Database Schema Mutation Reduction Using Column Clustering

Abstract

Mutation analysis is a powerful technique for evaluating test suite quality in relational database schemas, but its practical adoption is severely limited by the high computational cost of generating and executing thousands of mutants. Existing reduction techniques operate after mutant generation, wasting resources on mutants that will ultimately be discarded while struggling with the undecidable problem of detecting equivalent mutants. This paper introduces a novel pre-generation reduction approach that prevents redundant mutant generation at its source through column clustering. Columns are grouped by similarity based on a constraint vector encoding PRIMARY KEY, UNIQUE, NOT NULL, FOREIGN KEY, and CHECK constraints. From each cluster of columns with identical constraint configurations, a single representative column is selected for mutation generation, eliminating redundancy without requiring post-generation analysis. The method was evaluated on eight real-world database schemas comprising 2,472 columns with 542 constraints, including schemas with FOREIGN KEY and UNIQUE constraints. The proposed approach reduced total generated mutants from 12,084 to 934—a 92.3% reduction—while maintaining comparable mutation scores with an average difference of less than 0.5 percentage points. Operator-specific reduction rates ranged from 42.2% to 99.8%, with FOREIGN KEY-related operators achieving 66.7-75.0% reduction and UNIQUE-related operators achieving 78.9-85.3% reduction on schemas containing these constraints. Clustering overhead was minimal, requiring less than 2 seconds per schema, and net time savings ranged from 64% to 88%. These findings demonstrate that pre-generation mutant reduction through column clustering is both effective and practical, offering a scalable alternative to traditional post-generation approaches for mutation testing of relational database schemas.