EUVIMEDEUVIMED entdecken
Crossref

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

Rui Ding, Xiaochun Yang, Bin Wang, Quanqing Xu, Chuanhui Yang

Proceedings of the VLDB Endowment · 01.05.2026 · 19 (9) · 2385-2397

DOI: 10.14778/3819518.3819558 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 19.08.2026. Verfasst von Rui Ding und 4 weiteren Autor:innen. Die Arbeit nennt 49 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Ding, R., Yang, X., Wang, B., Xu, Q., & Yang, C. (2026). Storage-Centric Relation Design via High-Quality Approximate Functional Dependencies. Proceedings of the VLDB Endowment, 19(9), 2385-2397. https://doi.org/10.14778/3819518.3819558

Vancouver

Ding R, Yang X, Wang B, Xu Q, Yang C. Storage-Centric Relation Design via High-Quality Approximate Functional Dependencies. Proceedings of the VLDB Endowment. 2026;19(9):2385-2397. doi:10.14778/3819518.3819558

BibTeX
@article{Ding2026,
  author = {Ding, Rui and Yang, Xiaochun and Wang, Bin and Xu, Quanqing and Yang, Chuanhui},
  title = {Storage-Centric Relation Design via High-Quality Approximate Functional Dependencies},
  journal = {Proceedings of the VLDB Endowment},
  year = {2026},
  volume = {19},
  number = {9},
  pages = {2385--2397},
  doi = {10.14778/3819518.3819558}
}
Kostenlos starten →