{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,20]],"date-time":"2026-08-20T16:06:59Z","timestamp":1787242019300,"version":"build-2736575974"},"reference-count":70,"publisher":"Association for Computing Machinery (ACM)","issue":"4","funder":[{"DOI":"10.13039\/501100001509","name":"Royal Society Te Ap\u0101rangi","doi-asserted-by":"crossref","award":["MFP-UOA24209"],"award-info":[{"award-number":["MFP-UOA24209"]}],"id":[{"id":"10.13039\/501100001509","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2025,12,31]]},"abstract":"<jats:p>The goal of classical normalization is to maintain data consistency under updates, with a minimum level of effort. Given functional dependencies (FDs) alone, this goal is only achievable in the special case an FD-preserving Boyce\u2013Codd Normal Form (BCNF) decomposition exists. As we show, in all other cases the level of effort can be neither controlled nor quantified. In response, we establish the \u2113-Bounded Cardinality Normal Form, parameterized by a positive integer \u2113. For every \u2113, the normal form condition requires from every instance that every value combination over the left-hand side of every non-trivial FD does not occur in more than \u2113 tuples. BCNF is captured when \u2113 =1. We show that schemata in \u2113-Bounded Cardinality Normal Form characterize instances in which updates to at most \u2113 occurrences of any redundant data value are sufficient to maintain data consistency. In fact, for the smallest \u2113 in which a schema is in \u2113-Bounded Cardinality Normal Form we capture an equilibrium between worst-case update inefficiency and best-case join efficiency, where some redundant data value can be joined with up to \u2113 other data values. We then establish algorithms that compute schemata in \u2113-Bounded Cardinality Normal Form for the smallest level \u2113 attainable across all lossless, FD-preserving decompositions. Additional algorithms (i) attain even smaller levels of effort based on the loss of some FDs, and (ii) decompose schemata based on prioritized FDs that cause high levels of effort. Our framework informs de-normalization already during logical design. In particular, every materialized view exhibits an equilibrium level \u2113 that quantifies its worst-case incremental maintenance cost and its best-case support for join queries. Experiments with synthetic and real-world data illustrate which properties the schemata have that result from our algorithms, and how these properties predict the performance of update and query operations on instances over the schemata, without and with materialized views. We further demonstrate how our framework can automate the design of data warehouses by mining data for dimensions that exhibit high levels of data redundancy. In an effort to align data and the business rules that govern them, we use lattice theory to characterize \u2113-Bounded Cardinality Normal Form on database instances and schemata. As a consequence, any difference in constraints observed at instance and schema levels provides an opportunity to improve data quality, insight derived from analytics, and database performance.<\/jats:p>","DOI":"10.1145\/3744897","type":"journal-article","created":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T07:13:01Z","timestamp":1750144381000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["The Bounded Cardinality Normal Form for the Logical Design of Relational Database Schemata"],"prefix":"10.1145","volume":"50","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0973-3759","authenticated-orcid":false,"given":"Ziheng","family":"Wei","sequence":"first","affiliation":[{"name":"School of Computer Science, Wuhan University","place":["Wuhan, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1816-2863","authenticated-orcid":false,"given":"Sebastian","family":"Link","sequence":"additional","affiliation":[{"name":"School of Computer Science, The University of Auckland","place":["Auckland, New Zealand"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,7,24]]},"reference":[{"key":"e_1_3_3_2_2","volume-title":"Data Profiling","author":"Abedjan Ziawasch","year":"2018","unstructured":"Ziawasch Abedjan, Lukasz Golab, Felix Naumann, and Thorsten Papenbrock. 2018. Data Profiling. Morgan & Claypool Publishers."},{"issue":"4","key":"e_1_3_3_3_2","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1145\/1228268.1228284","article-title":"Normalization theory for XML","volume":"35","author":"Arenas Marcelo","year":"2006","unstructured":"Marcelo Arenas. 2006. Normalization theory for XML. SIGMOD Rec. 35, 4 (2006), 57\u201364.","journal-title":"SIGMOD Rec."},{"issue":"1","key":"e_1_3_3_4_2","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1145\/320064.320066","article-title":"Computational problems related to the design of normal form relational schemas","volume":"4","author":"Beeri Catriel","year":"1979","unstructured":"Catriel Beeri and Philip A. Bernstein. 1979. Computational problems related to the design of normal form relational schemas. ACM Trans. Database Syst. 4, 1 (1979), 30\u201359.","journal-title":"ACM Trans. Database Syst."},{"key":"e_1_3_3_5_2","first-page":"113","volume-title":"Proceedings of the 4th International Conference on Very Large Data Bases","author":"Beeri Catriel","year":"1978","unstructured":"Catriel Beeri, Philip A. Bernstein, and Nathan Goodman. 1978. A sophisticate\u2019s introduction to database normalization theory. In Proceedings of the 4th International Conference on Very Large Data Bases. 113\u2013124."},{"issue":"1","key":"e_1_3_3_6_2","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1145\/2422.322414","article-title":"On the structure of armstrong relations for functional dependencies","volume":"31","author":"Beeri Catriel","year":"1984","unstructured":"Catriel Beeri, Martin Dowd, Ronald Fagin, and Richard Statman. 1984. On the structure of armstrong relations for functional dependencies. J. ACM 31, 1 (1984), 30\u201346.","journal-title":"J. ACM"},{"key":"e_1_3_3_7_2","first-page":"245","volume-title":"Proceedings of the 6th International Conference on Very Large Data Bases","author":"Bernstein Philip A.","year":"1980","unstructured":"Philip A. Bernstein and Nathan Goodman. 1980. What does Boyce-Codd normal form do?. In Proceedings of the 6th International Conference on Very Large Data Bases. 245\u2013259."},{"key":"e_1_3_3_8_2","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1145\/582095.582118","volume-title":"Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data","author":"Biskup Joachim","year":"1979","unstructured":"Joachim Biskup, Umeshwar Dayal, and Philip A. Bernstein. 1979. Synthesizing independent database schemas. In Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data. 143\u2013151."},{"issue":"4","key":"e_1_3_3_9_2","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1145\/820127.820184","article-title":"Denormalization guidelines for base and transaction tables","volume":"34","author":"Bock Douglas B.","year":"2002","unstructured":"Douglas B. Bock and John F. Schrage. 2002. Denormalization guidelines for base and transaction tables. ACM SIGCSE Bull. 34, 4 (2002), 129\u2013133.","journal-title":"ACM SIGCSE Bull."},{"issue":"12","key":"e_1_3_3_10_2","doi-asserted-by":"crossref","first-page":"1721","DOI":"10.1109\/TKDE.2006.190","article-title":"Generating queries with cardinality constraints for DBMS testing","volume":"18","author":"Bruno Nicolas","year":"2006","unstructured":"Nicolas Bruno, Surajit Chaudhuri, and Dilys Thomas. 2006. Generating queries with cardinality constraints for DBMS testing. IEEE Trans. Knowl. Data Eng. 18, 12 (2006), 1721\u20131725.","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"1","key":"e_1_3_3_11_2","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1145\/320434.320440","article-title":"The entity-relationship model-toward a unified view of data","volume":"1","author":"Chen Peter","year":"1976","unstructured":"Peter Chen. 1976. The entity-relationship model-toward a unified view of data. ACM Trans. Database Syst. 1, 1 (1976), 9\u201336.","journal-title":"ACM Trans. Database Syst."},{"issue":"14","key":"e_1_3_3_12_2","doi-asserted-by":"crossref","first-page":"783","DOI":"10.1016\/j.ipl.2009.03.021","article-title":"Incorporating cardinality constraints and synonym rules into conditional functional dependencies","volume":"109","author":"Chen Wenguang","year":"2009","unstructured":"Wenguang Chen, Wenfei Fan, and Shuai Ma. 2009. Incorporating cardinality constraints and synonym rules into conditional functional dependencies. Inf. Process. Lett. 109, 14 (2009), 783\u2013789.","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"e_1_3_3_13_2","first-page":"295","article-title":"Materialized views","volume":"4","author":"Chirkova Rada","year":"2012","unstructured":"Rada Chirkova and Jun Yang. 2012. Materialized views. Found. Trends Databases 4, 4 (2012), 295\u2013405.","journal-title":"Found. Trends Databases"},{"key":"e_1_3_3_14_2","first-page":"258","volume-title":"Proceedings of the IEEE 28th International Conference on Data Engineering (ICDE 2012)","author":"Cormode Graham","year":"2012","unstructured":"Graham Cormode, Divesh Srivastava, Entong Shen, and Ting Yu. 2012. Aggregate query answering on possibilistic data with cardinality constraints. In Proceedings of the IEEE 28th International Conference on Data Engineering (ICDE 2012). 258\u2013269."},{"issue":"11","key":"e_1_3_3_15_2","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1145\/1400214.1400240","article-title":"Conceptually modeling windows and bounds for space and time in database constraints","volume":"51","author":"Currim Faiz","year":"2008","unstructured":"Faiz Currim and Sudha Ram. 2008. Conceptually modeling windows and bounds for space and time in database constraints. Commun. ACM 51, 11 (2008), 125\u2013129.","journal-title":"Commun. ACM"},{"issue":"3","key":"e_1_3_3_16_2","first-page":"141","article-title":"Normal form relation schemes: A new characterization","volume":"10","author":"Demetrovics J\u00e1nos","year":"1992","unstructured":"J\u00e1nos Demetrovics, G. Hencsey, Leonid Libkin, and Ilya B. Muchnik. 1992. Normal form relation schemes: A new characterization. Acta Cybern. 10, 3 (1992), 141\u2013153.","journal-title":"Acta Cybern."},{"issue":"2","key":"e_1_3_3_17_2","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0166-218X(92)90028-9","article-title":"Functional dependencies in relational databases: A lattice point of view","volume":"40","author":"Demetrovics J\u00e1nos","year":"1992","unstructured":"J\u00e1nos Demetrovics, Leonid Libkin, and Ilya B. Muchnik. 1992. Functional dependencies in relational databases: A lattice point of view. Discret. Appl. Math. 40, 2 (1992), 155\u2013185.","journal-title":"Discret. Appl. Math."},{"issue":"3","key":"e_1_3_3_18_2","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1145\/320557.320571","article-title":"Multivalued dependencies and a new normal form for relational databases","volume":"2","author":"Fagin Ronald","year":"1977","unstructured":"Ronald Fagin. 1977. Multivalued dependencies and a new normal form for relational databases. ACM Trans. Database Syst. 2, 3 (1977), 262\u2013278.","journal-title":"ACM Trans. Database Syst."},{"key":"e_1_3_3_19_2","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1145\/582095.582120","volume-title":"Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data","author":"Fagin Ronald","year":"1979","unstructured":"Ronald Fagin. 1979. Normal forms and relational database operators. In Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data. 153\u2013160."},{"key":"e_1_3_3_20_2","first-page":"1843","volume-title":"Proceedings of the 2016 International Conference on Management of Data, SIGMOD Conference 2016","author":"Fan Wenfei","year":"2016","unstructured":"Wenfei Fan, Yinghui Wu, and Jingbo Xu. 2016. Functional dependencies for graphs. In Proceedings of the 2016 International Conference on Management of Data, SIGMOD Conference 2016. 1843\u20131857."},{"key":"e_1_3_3_21_2","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/j.datak.2012.09.004","article-title":"Efficiency frontiers of XML cardinality constraints","volume":"87","author":"Ferrarotti Flavio","year":"2013","unstructured":"Flavio Ferrarotti, Sven Hartmann, and Sebastian Link. 2013. Efficiency frontiers of XML cardinality constraints. Data Knowl. Eng. 87 (2013), 297\u2013319.","journal-title":"Data Knowl. Eng."},{"key":"e_1_3_3_22_2","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1016\/0304-3975(85)90075-1","article-title":"Inferences for numerical dependencies","volume":"41","author":"Grant John","year":"1985","unstructured":"John Grant and Jack Minker. 1985. Inferences for numerical dependencies. Theor. Comput. Sci. 41 (1985), 271\u2013287.","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"e_1_3_3_23_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0019-9958(85)80017-6","article-title":"Normalization and axiomatization for numerical dependencies","volume":"65","author":"Grant John","year":"1985","unstructured":"John Grant and Jack Minker. 1985. Normalization and axiomatization for numerical dependencies. Inf. Control. 65, 1 (1985), 1\u201317.","journal-title":"Inf. Control."},{"key":"e_1_3_3_24_2","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1016\/j.datak.2015.06.002","article-title":"Cardinality constraints on qualitatively uncertain data","volume":"99","author":"Hall Neil","year":"2015","unstructured":"Neil Hall, Henning K\u00f6hler, Sebastian Link, Henri Prade, and Xiaofang Zhou. 2015. Cardinality constraints on qualitatively uncertain data. Data Knowl. Eng. 99 (2015), 126\u2013150.","journal-title":"Data Knowl. Eng."},{"key":"e_1_3_3_25_2","first-page":"105","volume-title":"Database Technologies 2003, Proceedings of the 14th Australasian Database Conference, ADC 2003","author":"Hartmann Sven","year":"2003","unstructured":"Sven Hartmann. 2003. Reasoning about participation constraints and Chen\u2019s constraints. In Database Technologies 2003, Proceedings of the 14th Australasian Database Conference, ADC 2003. 105\u2013113."},{"issue":"1","key":"e_1_3_3_26_2","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/s00778-011-0239-5","article-title":"Design by example for SQL table definitions with functional dependencies","volume":"21","author":"Hartmann Sven","year":"2012","unstructured":"Sven Hartmann, Markus Kirchberg, and Sebastian Link. 2012. Design by example for SQL table definitions with functional dependencies. VLDB J. 21, 1 (2012), 121\u2013144.","journal-title":"VLDB J."},{"issue":"2","key":"e_1_3_3_27_2","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1093\/comjnl\/42.2.100","article-title":"TANE: An efficient algorithm for discovering functional and approximate dependencies","volume":"42","author":"Huhtala Yk\u00e4","year":"1999","unstructured":"Yk\u00e4 Huhtala, Juha K\u00e4rkk\u00e4inen, Pasi Porkka, and Hannu Toivonen. 1999. TANE: An efficient algorithm for discovering functional and approximate dependencies. Comput. J. 42, 2 (1999), 100\u2013111.","journal-title":"Comput. J."},{"issue":"1","key":"e_1_3_3_28_2","first-page":"315","article-title":"Pawlak\u2019s information systems in terms of Galois connections and functional dependencies","volume":"75","author":"J\u00e4rvinen Jouni","year":"2007","unstructured":"Jouni J\u00e4rvinen. 2007. Pawlak\u2019s information systems in terms of Galois connections and functional dependencies. Fundam. Informaticae 75, 1\u20134 (2007), 315\u2013330.","journal-title":"Fundam. Informaticae"},{"issue":"4","key":"e_1_3_3_29_2","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1109\/69.536250","article-title":"Extending existing dependency theory to temporal databases","volume":"8","author":"Jensen Christian S.","year":"1996","unstructured":"Christian S. Jensen, Richard T. Snodgrass, and Michael D. Soo. 1996. Extending existing dependency theory to temporal databases. IEEE Trans. Knowl. Data Eng. 8, 4 (1996), 563\u2013582.","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"5","key":"e_1_3_3_30_2","doi-asserted-by":"crossref","first-page":"1295","DOI":"10.1109\/TKDE.2003.1232279","article-title":"Reasoning about uniqueness constraints in object relational databases","volume":"15","author":"Khizder Vitaliy L.","year":"2003","unstructured":"Vitaliy L. Khizder and Grant E. Weddell. 2003. Reasoning about uniqueness constraints in object relational databases. IEEE Trans. Knowl. Data Eng. 15, 5 (2003), 1295\u20131306.","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"e_1_3_3_31_2","first-page":"5393","volume-title":"Proceedings of the 40th IEEE International Conference on Data Engineering, ICDE 2024","author":"Koehler Henning","year":"2024","unstructured":"Henning Koehler and Sebastian Link. 2024. Entity\/relationship profiling. In Proceedings of the 40th IEEE International Conference on Data Engineering, ICDE 2024. 5393\u20135396."},{"key":"e_1_3_3_32_2","first-page":"102","volume-title":"Proceedings of the 2nd International Conference on Algorithmic Aspects in Information and Management, AAIM 2006","author":"K\u00f6hler Henning","year":"2006","unstructured":"Henning K\u00f6hler. 2006. Finding faithful Boyce-Codd normal form decompositions. In Proceedings of the 2nd International Conference on Algorithmic Aspects in Information and Management, AAIM 2006. 102\u2013113."},{"key":"e_1_3_3_33_2","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1145\/2882903.2915239","volume-title":"Proceedings of the 2016 International Conference on Management of Data","author":"K\u00f6hler Henning","year":"2016","unstructured":"Henning K\u00f6hler and Sebastian Link. 2016. SQL schema design: Foundations, normal forms, and normalization. In Proceedings of the 2016 International Conference on Management of Data. 267\u2013279."},{"issue":"2","key":"e_1_3_3_34_2","first-page":"21","article-title":"Discovering meaningful certain keys from incomplete and inconsistent relations","volume":"39","author":"K\u00f6hler Henning","year":"2016","unstructured":"Henning K\u00f6hler, Sebastian Link, and Xiaofang Zhou. 2016. Discovering meaningful certain keys from incomplete and inconsistent relations. IEEE Data Eng. Bull. 39, 2 (2016), 21\u201337.","journal-title":"IEEE Data Eng. Bull."},{"issue":"9","key":"e_1_3_3_35_2","first-page":"1707","article-title":"Equilibrium of redundancy in relational model for optimized data retrieval","volume":"32","author":"Kojic Nemanja","year":"2020","unstructured":"Nemanja Kojic and Dragan Milicev. 2020. Equilibrium of redundancy in relational model for optimized data retrieval. IEEE Trans. Knowl. Data Eng. 32, 9 (2020), 1707\u20131721.","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"1","key":"e_1_3_3_36_2","first-page":"5:1\u20135:32","article-title":"An information-theoretic analysis of worst-case redundancy in database design","volume":"35","author":"Kolahi Solmaz","year":"2010","unstructured":"Solmaz Kolahi and Leonid Libkin. 2010. An information-theoretic analysis of worst-case redundancy in database design. ACM Trans. Database Syst. 35, 1 (2010), 5:1\u20135:32.","journal-title":"ACM Trans. Database Syst."},{"issue":"7","key":"e_1_3_3_37_2","doi-asserted-by":"crossref","first-page":"759","DOI":"10.14778\/3192965.3192968","article-title":"Efficient discovery of approximate dependencies","volume":"11","author":"Kruse Sebastian","year":"2018","unstructured":"Sebastian Kruse and Felix Naumann. 2018. Efficient discovery of approximate dependencies. Proc. VLDB Endow. 11, 7 (2018), 759\u2013772.","journal-title":"Proc. VLDB Endow."},{"issue":"3","key":"e_1_3_3_38_2","doi-asserted-by":"crossref","first-page":"352","DOI":"10.1016\/j.is.2009.11.002","article-title":"Empirical evidence for the usefulness of armstrong relations in the acquisition of meaningful functional dependencies","volume":"35","author":"Langeveldt Warren-Dean","year":"2010","unstructured":"Warren-Dean Langeveldt and Sebastian Link. 2010. Empirical evidence for the usefulness of armstrong relations in the acquisition of meaningful functional dependencies. Inf. Syst. 35, 3 (2010), 352\u2013374.","journal-title":"Inf. Syst."},{"issue":"5","key":"e_1_3_3_39_2","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1016\/S0306-4379(02)00024-8","article-title":"Multidimensional normal forms for warehouse design","volume":"28","author":"Lechtenb\u00f6rger Jens","year":"2003","unstructured":"Jens Lechtenb\u00f6rger and Gottfried Vossen. 2003. Multidimensional normal forms for warehouse design. Inf. Syst. 28, 5 (2003), 415\u2013434.","journal-title":"Inf. Syst."},{"issue":"10","key":"e_1_3_3_40_2","doi-asserted-by":"crossref","first-page":"3159","DOI":"10.1002\/j.1538-7305.1983.tb03470.x","article-title":"An algebraic theory of relational databases","volume":"62","author":"Lee Tony T.","year":"1983","unstructured":"Tony T. Lee. 1983. An algebraic theory of relational databases. Bell Syst. Tech. J. 62, 10 (1983), 3159\u20133204.","journal-title":"Bell Syst. Tech. J."},{"key":"e_1_3_3_41_2","first-page":"529","volume-title":"Proceedings of the 3rd International Conference on Entity-Relationship Approach (ER\u201983)","author":"Lenzerini Maurizio","year":"1983","unstructured":"Maurizio Lenzerini and Gaetano Santucci. 1983. Cardinality constraints in the entity-relationship model. In Proceedings of the 3rd International Conference on Entity-Relationship Approach (ER\u201983). 529\u2013549."},{"issue":"3","key":"e_1_3_3_42_2","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/S0306-4379(02)00021-2","article-title":"Why is the snowflake schema a good data warehouse design?","volume":"28","author":"Levene Mark","year":"2003","unstructured":"Mark Levene and George Loizou. 2003. Why is the snowflake schema a good data warehouse design? Inf. Syst. 28, 3 (2003), 225\u2013240.","journal-title":"Inf. Syst."},{"issue":"2","key":"e_1_3_3_43_2","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1109\/69.842267","article-title":"Justification for inclusion dependency normal form","volume":"12","author":"Levene Mark","year":"2000","unstructured":"Mark Levene and Millist W. Vincent. 2000. Justification for inclusion dependency normal form. IEEE Trans. Knowl. Data Eng. 12, 2 (2000), 281\u2013291.","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"3","key":"e_1_3_3_44_2","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0169-023X(93)90024-J","article-title":"Cardinality constraints in semantic data models","volume":"11","author":"Liddle Stephen W.","year":"1993","unstructured":"Stephen W. Liddle, David W. Embley, and Scott N. Woodfield. 1993. Cardinality constraints in semantic data models. Data Knowl. Eng. 11, 3 (1993), 235\u2013270.","journal-title":"Data Knowl. Eng."},{"key":"e_1_3_3_45_2","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/j.is.2019.04.003","article-title":"Relational database schema design for uncertain data","volume":"84","author":"Link Sebastian","year":"2019","unstructured":"Sebastian Link and Henri Prade. 2019. Relational database schema design for uncertain data. Inf. Syst. 84 (2019), 88\u2013110.","journal-title":"Inf. Syst."},{"key":"e_1_3_3_46_2","first-page":"1169","volume-title":"SIGMOD \u201921: Proceedings of the International Conference on Management of Data","author":"Link Sebastian","year":"2021","unstructured":"Sebastian Link and Ziheng Wei. 2021. Logical schema design that quantifies update inefficiency and join efficiency. In SIGMOD \u201921: Proceedings of the International Conference on Management of Data. 1169\u20131181."},{"key":"e_1_3_3_47_2","first-page":"2253","volume-title":"Proceedings of the 2016 International Conference on Management of Data, SIGMOD Conference 2016","author":"Liu Zezhou","year":"2016","unstructured":"Zezhou Liu and Stratos Idreos. 2016. Main memory adaptive denormalization. In Proceedings of the 2016 International Conference on Management of Data, SIGMOD Conference 2016. 2253\u20132254."},{"key":"e_1_3_3_48_2","volume-title":"The Theory of Relational Databases","author":"Maier David","year":"1983","unstructured":"David Maier. 1983. The Theory of Relational Databases. Computer Science Press."},{"issue":"2","key":"e_1_3_3_49_2","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1016\/0022-0000(86)90015-2","article-title":"Design by example: An application of armstrong relations","volume":"33","author":"Mannila Heikki","year":"1986","unstructured":"Heikki Mannila and Kari-Jouko R\u00e4ih\u00e4. 1986. Design by example: An application of armstrong relations. J. Comput. Syst. Sci. 33, 2 (1986), 126\u2013141.","journal-title":"J. Comput. Syst. Sci."},{"key":"e_1_3_3_50_2","first-page":"155","volume-title":"VLDB\u201987, Proceedings of the 13th International Conference on Very Large Data Bases","author":"Mannila Heikki","year":"1987","unstructured":"Heikki Mannila and Kari-Jouko R\u00e4ih\u00e4. 1987. Dependency inference. In VLDB\u201987, Proceedings of the 13th International Conference on Very Large Data Bases. 155\u2013158."},{"issue":"1","key":"e_1_3_3_51_2","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1145\/227604.227612","article-title":"A normal form for precisely characterizing redundancy in nested relations","volume":"21","author":"Mok Wai Yin","year":"1996","unstructured":"Wai Yin Mok, Yiu-Kai Ng, and David W. Embley. 1996. A normal form for precisely characterizing redundancy in nested relations. ACM Trans. Database Syst. 21, 1 (1996), 77\u2013106.","journal-title":"ACM Trans. Database Syst."},{"key":"e_1_3_3_52_2","first-page":"83","volume-title":"Conceptual Modeling of Information Systems","author":"Oliv\u00e9 Antoni","year":"2007","unstructured":"Antoni Oliv\u00e9. 2007. Cardinality constraints. In Conceptual Modeling of Information Systems. Springer, 83\u2013102."},{"issue":"1","key":"e_1_3_3_53_2","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/0020-0190(79)90082-6","article-title":"Testing for existence of a covering Boyce-Codd normal form","volume":"8","author":"Osborn Sylvia L.","year":"1979","unstructured":"Sylvia L. Osborn. 1979. Testing for existence of a covering Boyce-Codd normal form. Inf. Process. Lett. 8, 1 (1979), 11\u201314.","journal-title":"Inf. Process. Lett."},{"issue":"10","key":"e_1_3_3_54_2","first-page":"1082","article-title":"Functional dependency discovery: An experimental evaluation of seven algorithms","volume":"8","author":"Papenbrock Thorsten","year":"2015","unstructured":"Thorsten Papenbrock, Jens Ehrlich, Jannik Marten, Tommy Neubert, Jan-Peer Rudolph, Martin Sch\u00f6nberg, Jakob Zwiener, and Felix Naumann. 2015. Functional dependency discovery: An experimental evaluation of seven algorithms. PVLDB 8, 10 (2015), 1082\u20131093.","journal-title":"PVLDB"},{"key":"e_1_3_3_55_2","first-page":"821","volume-title":"Proceedings of the 2016 International Conference on Management of Data, SIGMOD Conference 2016","author":"Papenbrock Thorsten","year":"2016","unstructured":"Thorsten Papenbrock and Felix Naumann. 2016. A hybrid approach to functional dependency discovery. In Proceedings of the 2016 International Conference on Management of Data, SIGMOD Conference 2016. 821\u2013833."},{"key":"e_1_3_3_56_2","first-page":"342","volume-title":"Proceedings of the 20th International Conference on Extending Database Technology, EDBT 2017","author":"Papenbrock Thorsten","year":"2017","unstructured":"Thorsten Papenbrock and Felix Naumann. 2017. Data-driven schema normalization. In Proceedings of the 20th International Conference on Extending Database Technology, EDBT 2017. 342\u2013353."},{"key":"e_1_3_3_57_2","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1109\/ICDE.1996.492110","volume-title":"Proceedings of the 12th International Conference on Data Engineering","author":"Petit Jean-Marc","year":"1996","unstructured":"Jean-Marc Petit, Farouk Toumani, Jean-Fran\u00e7ois Boulicaut, and Jacques Kouloumdjian. 1996. Towards the reverse engineering of denormalized relational databases. In Proceedings of the 12th International Conference on Data Engineering. 218\u2013227."},{"issue":"4","key":"e_1_3_3_58_2","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1145\/320576.320580","article-title":"Independent components of relations","volume":"2","author":"Rissanen Jorma","year":"1977","unstructured":"Jorma Rissanen. 1977. Independent components of relations. ACM Trans. Database Syst. 2, 4 (1977), 317\u2013325.","journal-title":"ACM Trans. Database Syst."},{"issue":"6","key":"e_1_3_3_59_2","doi-asserted-by":"crossref","first-page":"771","DOI":"10.1007\/s00778-018-0511-z","article-title":"Probabilistic cardinality constraints","volume":"27","author":"Roblot Tania","year":"2018","unstructured":"Tania Roblot, Miika Hannula, and Sebastian Link. 2018. Probabilistic cardinality constraints. VLDB J. 27, 6 (2018), 771\u2013795.","journal-title":"VLDB J."},{"key":"e_1_3_3_60_2","first-page":"441","volume-title":"Proceedings of the 39th International Conference on Conceptual Modeling, ER 2020","author":"Scherzinger Stefanie","year":"2020","unstructured":"Stefanie Scherzinger and Sebastian Sidortschuck. 2020. An empirical study on the design and evolution of NoSQL database schemas. In Proceedings of the 39th International Conference on Conceptual Modeling, ER 2020. 441\u2013455."},{"issue":"11","key":"e_1_3_3_61_2","doi-asserted-by":"crossref","first-page":"3031","DOI":"10.14778\/3611479.3611506","article-title":"Normalizing property graphs","volume":"16","author":"Skavantzos Philipp","year":"2023","unstructured":"Philipp Skavantzos and Sebastian Link. 2023. Normalizing property graphs. Proc. VLDB Endow. 16, 11 (2023), 3031\u20133043.","journal-title":"Proc. VLDB Endow."},{"issue":"1","key":"e_1_3_3_62_2","first-page":"40:1\u201340:26","article-title":"Entity\/relationship graphs: Principled design, modeling, and data integrity management of graph databases","volume":"3","author":"Skavantzos Philipp","year":"2025","unstructured":"Philipp Skavantzos and Sebastian Link. 2025. Entity\/relationship graphs: Principled design, modeling, and data integrity management of graph databases. Proc. ACM Manag. Data 3, 1 (2025), 40:1\u201340:26.","journal-title":"Proc. ACM Manag. Data"},{"issue":"2","key":"e_1_3_3_63_2","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/s00778-025-00902-2","article-title":"Third and Boyce-Codd normal form for property graphs","volume":"34","author":"Skavantzos Philipp","year":"2025","unstructured":"Philipp Skavantzos and Sebastian Link. 2025. Third and Boyce-Codd normal form for property graphs. VLDB J. 34, 2 (2025), 23.","journal-title":"VLDB J."},{"issue":"2","key":"e_1_3_3_64_2","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/S0169-023X(98)00017-2","article-title":"Relational database reverse engineering: Algorithms to extract cardinality constraints","volume":"28","author":"Soutou Christian","year":"1998","unstructured":"Christian Soutou. 1998. Relational database reverse engineering: Algorithms to extract cardinality constraints. Data Knowl. Eng. 28, 2 (1998), 161\u2013207.","journal-title":"Data Knowl. Eng."},{"key":"e_1_3_3_65_2","first-page":"7","volume-title":"Entity-Relationship Approach - ER\u201992, Proceedings of the 11th International Conference on the Entity-Relationship Approach","author":"Thalheim Bernhard","year":"1992","unstructured":"Bernhard Thalheim. 1992. Fundamentals of cardinality constraints. In Entity-Relationship Approach - ER\u201992, Proceedings of the 11th International Conference on the Entity-Relationship Approach. 7\u201323."},{"key":"e_1_3_3_66_2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04058-4","volume-title":"Entity-Relationship Modeling - Foundations of Database Technology","author":"Thalheim Bernhard","year":"2000","unstructured":"Bernhard Thalheim. 2000. Entity-Relationship Modeling - Foundations of Database Technology. Springer."},{"issue":"3","key":"e_1_3_3_67_2","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/s002360050157","article-title":"Semantic foundations of 4NF in relational database design","volume":"36","author":"Vincent Millist W.","year":"1999","unstructured":"Millist W. Vincent. 1999. Semantic foundations of 4NF in relational database design. Acta Inf. 36, 3 (1999), 173\u2013213.","journal-title":"Acta Inf."},{"key":"e_1_3_3_68_2","doi-asserted-by":"crossref","first-page":"102224","DOI":"10.1016\/j.is.2023.102224","article-title":"Towards the efficient discovery of meaningful functional dependencies","volume":"116","author":"Wei Ziheng","year":"2023","unstructured":"Ziheng Wei and Sebastian Link. 2023. Towards the efficient discovery of meaningful functional dependencies. Inf. Syst. 116 (2023), 102224.","journal-title":"Inf. Syst."},{"issue":"1","key":"e_1_3_3_69_2","first-page":"243","article-title":"Migration from RDBMS to NoSQL using column-level denormalization and atomic aggregates","volume":"34","author":"Yoo Jaejun","year":"2018","unstructured":"Jaejun Yoo, Ki-Hoon Lee, and Young-Ho Jeon. 2018. Migration from RDBMS to NoSQL using column-level denormalization and atomic aggregates. J. Inf. Sci. Eng. 34, 1 (2018), 243\u2013259.","journal-title":"J. Inf. Sci. Eng."},{"issue":"1","key":"e_1_3_3_70_2","first-page":"13:1\u201313:25","article-title":"Composite object normal forms: Parameterizing Boyce-Codd normal form by the number of minimal keys","volume":"1","author":"Zhang Zhuoxing","year":"2023","unstructured":"Zhuoxing Zhang, Wu Chen, and Sebastian Link. 2023. Composite object normal forms: Parameterizing Boyce-Codd normal form by the number of minimal keys. Proc. ACM Manag. Data 1, 1 (2023), 13:1\u201313:25.","journal-title":"Proc. ACM Manag. Data"},{"issue":"3","key":"e_1_3_3_71_2","first-page":"225:1\u2013225:25","article-title":"Synthesizing third normal form schemata that minimize integrity maintenance and update overheads: Parameterizing 3NF by the numbers of minimal keys and functional dependencies","volume":"3","author":"Zhang Zhuoxing","year":"2025","unstructured":"Zhuoxing Zhang and Sebastian Link. 2025. Synthesizing third normal form schemata that minimize integrity maintenance and update overheads: Parameterizing 3NF by the numbers of minimal keys and functional dependencies. Proc. ACM Manag. Data 3, 3 (2025), 225:1\u2013225:25.","journal-title":"Proc. ACM Manag. Data"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3744897","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,24]],"date-time":"2025-07-24T12:28:27Z","timestamp":1753360107000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3744897"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,24]]},"references-count":70,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,12,31]]}},"alternative-id":["10.1145\/3744897"],"URL":"https:\/\/doi.org\/10.1145\/3744897","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,7,24]]},"assertion":[{"value":"2022-04-29","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-06-07","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-07-24","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}