Storage-Centric Relation Design via High-Quality Approximate Functional Dependencies

As storage costs continue to rise, reducing redundancy has become increasingly important. In relational databases, classical normalization addresses redundancy through exact functional dependencies (FDs), but this rule-based design paradigm is not inherently cost-aware and does not necessarily minimize storage in practice. Moreover, much real-world redundancy follows FD+Δ patterns, where FDs hold for most tuples but are violated by a small fraction. To address this, we propose RelaxRD, a storage-centric relaxed schema design that leverages approximate functional dependencies (AFDs) to reduce redundancy in FD+Δ. Rather than treating all AFDs as equally useful signals, we quantify the storage value of AFD subsets via duplicate gain and select a high-quality subset for decomposition. It decomposes tuples satisfying the selected AFDs while retaining violating tuples. The key issue is that selecting a high-quality subset is difficult due to conflicts and the exponential search space. To tackle this, we develop a family of efficient filtering techniques to eliminate low-value and unpromising candidates without exhaustive enumeration. Extensive experiments on real-world datasets demonstrate that RelaxRD consistently achieves substantial storage savings.