Logical Schema Design that Quantifies Update Inefficiency and Join Efficiency

Summary: Introduces the l-Bounded Cardinality Normal Form (l-BCNF), a parameterized schema design that quantifies update effort and join efficiency under FDs (BCNF = l=1). Algorithms compute the smallest l across FD-preserving decompositions, with FD loss or prioritization enabling de-normalization and predicting materialized-view maintenance. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: he4c7c4775be94b60
Venue: SIGMOD
Year: 2021
Pagerank: 5.1038322e-05
Overall Rank: 9,967 | 32.99%
DOI: 10.1145/3448016.3459238

Incoming Non-self Citations Over Time

Authors

1. Sebastian Link (University of Auckland)
2. Ziheng Wei (University of Auckland)

BibTeX Citation

@inproceedings{link_sigmod21,
        title = {{Logical Schema Design that Quantifies Update Inefficiency and Join Efficiency}},
        author = {Link, Sebastian and Wei, Ziheng},
        series = {{SIGMOD} '21},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3448016.3459238},
        url = {https://dl.acm.org/doi/10.1145/3448016.3459238},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,798	Normalizing Property Graphs	2023	VLDB	5.9905343e-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
10,794	Storage-Centric Relation Design via High-Quality Approximate Functional Dependencies	2026	VLDB	4.9793485e-05
11,558	Mixed Covers of Keys and Functional Dependencies for Maintaining the Integrity of Data under Updates	2024	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
550	Synthesizing Independent Database Schemas	1979	SIGMOD	0.00016559635
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,488	Efficient Discovery of Approximate Dependencies	2018	VLDB	0.00010517437
2,470	Normal forms and relational database operators	1979	SIGMOD	8.4163872e-05
3,026	Functional Dependencies for Graphs	2016	SIGMOD	7.7387829e-05
7,956	Main Memory Adaptive Denormalization	2016	SIGMOD	5.4184993e-05
9,970	SQL Schema Design: Foundations, Normal Forms, and Normalization	2016	SIGMOD	5.1038322e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,834	Properties Of Database Schemata With Functional Dependencies	1984	PODS
2	3,502	An Information-Theoretic Approach to Normal Forms for Relational and XML Data	2003	PODS
3	13,460	Logical Design of Relational Database Schemes	1987	PODS
4	6,643	The Design of non-1NF Relational Databases into Nested Normal Form	1987	SIGMOD
5	5,798	Normalizing Property Graphs	2023	VLDB
6	12,969	On Redundancy vs Dependency Preservation in Normalization: An Information-Theoretic Study of 3NF	2006	PODS
7	3,476	Reflections on Boyce-Codd Normal Form	1982	VLDB
8	9,965	Composite Object Normal Forms: Parameterizing Boyce-Codd Normal Form by the Number of Minimal Keys	2023	SIGMOD
9	9,970	SQL Schema Design: Foundations, Normal Forms, and Normalization	2016	SIGMOD
10	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