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

Summary: RelaxRD performs storage-centric schema decomposition using approximate FDs, targeting FD+Δ redundancy rather than exact normalization. It selects AFD subsets by duplicate gain and prunes the exponential search space with efficient filters while retaining violating tuples. (summarized by gpt-5.6-luna on Aug 17 2026)

Paper ID: h77a7139bf580c029
Venue: VLDB
Year: 2026
Pagerank: 4.9793485e-05
Overall Rank: 10,794 | 27.43%
DOI: 10.14778/3819518.3819558

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Rui Ding (Northeastern University)
2. Xiaochun Yang (Northeastern University)
3. Bin Wang (Northeastern University)
4. Quanqing Xu (Ant Financial)
5. Chuanhui Yang (Ant Financial)

BibTeX Citation

@article{ding_vldb26,
        title = {{Storage-Centric Relation Design via High-Quality Approximate Functional Dependencies}},
        author = {Ding, Rui and Yang, Xiaochun and Wang, Bin and Xu, Quanqing and Yang, Chuanhui},
        journal = {PVLDB},
        series = {{VLDB} '26},
        volume = {19},
        number = {9},
        pages = {2385--2397},
        doi = {10.14778/3819518.3819558},
        url = {https://doi.org/10.14778/3819518.3819558},
        year = {2026}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 20 of 20 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
34	The Design Of Postgres	1986	SIGMOD	0.00049142315
71	DuckDB: an Embeddable Analytical Database	2019	SIGMOD	0.00037720227
603	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD	0.00015699254
727	Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms	2015	VLDB	0.00014443394
1,343	PolarDB Serverless: A Cloud Native Database for Disaggregated Data Centers	2021	SIGMOD	0.00010963588
1,488	Efficient Discovery of Approximate Dependencies	2018	VLDB	0.00010517437
2,314	BtrBlocks: Efficient Columnar Compression for Data Lakes	2023	SIGMOD	8.6533171e-05
2,812	OceanBase: A 707 Million tpmC Distributed Relational Database System	2022	VLDB	7.9811649e-05
3,193	A Statistical Perspective on Discovering Functional Dependencies in Noisy Data	2020	SIGMOD	7.5505481e-05
3,475	Embedded Functional Dependencies and Data-completeness Tailored Database Design	2019	VLDB	7.2707661e-05
4,635	A Deep Dive into Common Open Formats for Analytical DBMSs	2023	VLDB	6.4932705e-05
6,589	Mining Approximate Acyclic Schemes from Relations	2020	SIGMOD	5.7427998e-05
6,737	CompressDB: Enabling Efficient Compressed Data Direct Processing for Various Databases	2022	SIGMOD	5.6925989e-05
8,203	Hitting Set Enumeration with Partial Information for Unique Column Combination Discovery	2020	VLDB	5.3786539e-05
9,107	DAFDiscover: Robust Mining Algorithm for Dynamic Approximate Functional Dependencies on Dirty Data	2024	VLDB	5.2283159e-05
9,951	Synthesizing Third Normal Form Schemata that Minimize Integrity Maintenance and Update Overheads: Parameterizing 3NF by the Numbers of Minimal Keys and Functional Dependencies	2025	SIGMOD	5.1038322e-05
9,965	Composite Object Normal Forms: Parameterizing Boyce-Codd Normal Form by the Number of Minimal Keys	2023	SIGMOD	5.1038322e-05
9,967	Logical Schema Design that Quantifies Update Inefficiency and Join Efficiency	2021	SIGMOD	5.1038322e-05
9,970	SQL Schema Design: Foundations, Normal Forms, and Normalization	2016	SIGMOD	5.1038322e-05
11,618	Native Distributed Databases: Problems, Challenges and Opportunities	2024	VLDB	4.9793485e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,475	Embedded Functional Dependencies and Data-completeness Tailored Database Design	2019	VLDB
2	6,695	The Partial Normalized Storage Model of Nested Relations	1988	VLDB
3	603	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD
4	9,967	Logical Schema Design that Quantifies Update Inefficiency and Join Efficiency	2021	SIGMOD
5	9,951	Synthesizing Third Normal Form Schemata that Minimize Integrity Maintenance and Update Overheads: Parameterizing 3NF by the Numbers of Minimal Keys and Functional Dependencies	2025	SIGMOD
6	9,512	Unifying Functional and Multivalued Dependencies for Relational Database Design	1986	PODS
7	9,970	SQL Schema Design: Foundations, Normal Forms, and Normalization	2016	SIGMOD
8	3,287	Comprehensive Approach to the Design of Relational Database Schemes	1984	VLDB
9	6,643	The Design of non-1NF Relational Databases into Nested Normal Form	1987	SIGMOD
10	11,254	Efficient Discovery of Relaxed Functional Dependencies	2025	VLDB