{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,10,22]],"date-time":"2024-10-22T23:40:11Z","timestamp":1729640411639,"version":"3.28.0"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,5,26]]},"abstract":"We parameterize schemata in Boyce-Codd Normal Form (BCNF) by the number n of minimal keys they exhibit. We show that n quantifies a trade-off between access variety and update complexity. Indeed, access variety refers to the number of different ways by which every entity over the schema is represented uniquely, while update complexity refers to the number of attribute sets for which uniqueness needs to be preserved during updates. As normalization aims at minimizing the level of effort required to preserve data consistency during updates, we establish an algorithm that returns a lossless, dependency-preserving 3NF decomposition where the subset of output schemata not in BCNF is minimized and redundant BCNF schemata are eliminated from the highest to the lowest n exhibited. In particular, if a lossless, dependency-preserving BCNF decomposition exists, our algorithm returns one where the maximum n across all output schemata is minimized. Experiments with synthetic and real-world data quantify the impact of n on the update and query performance over schemata in BCNF with n minimal keys, and show insight into the efficacy of our algorithm suite.<\/jats:p>","DOI":"10.1145\/3588693","type":"journal-article","created":{"date-parts":[[2023,5,30]],"date-time":"2023-05-30T17:42:05Z","timestamp":1685468525000},"page":"1-25","source":"Crossref","is-referenced-by-count":2,"title":["Composite Object Normal Forms: Parameterizing Boyce-Codd Normal Form by the Number of Minimal Keys"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"http:\/\/orcid.org\/0000-0001-6736-4501","authenticated-orcid":false,"given":"Zhuoxing","family":"Zhang","sequence":"first","affiliation":[{"name":"University of Auckland, Auckland, New Zealand"}]},{"ORCID":"http:\/\/orcid.org\/0000-0002-5041-6122","authenticated-orcid":false,"given":"Wu","family":"Chen","sequence":"additional","affiliation":[{"name":"Southwest University, Chongqing, China"}]},{"ORCID":"http:\/\/orcid.org\/0000-0002-1816-2863","authenticated-orcid":false,"given":"Sebastian","family":"Link","sequence":"additional","affiliation":[{"name":"University of Auckland, Auckland, New Zealand"}]}],"member":"320","published-online":{"date-parts":[[2023,5,30]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1228268.1228284"},{"key":"e_1_2_2_2_1","volume-title":"Proceedings of the 6th IFIP Congress 1974","author":"Armstrong William Ward","year":"1974","unstructured":"William Ward Armstrong. 1974. Dependency Structures of Data Base Relationships. In Information Processing, Proceedings of the 6th IFIP Congress 1974, Stockholm, Sweden, August 5--10, 1974. 580--583."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/320064.320066"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1286643.1286659"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422.322414"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/320493.320489"},{"volume-title":"Sixth International Conference on Very Large Data Bases, October 1--3, 1980, Montreal, Quebec, Canada, Proceedings. 245--259","author":"Philip","key":"e_1_2_2_7_1","unstructured":"Philip A. Bernstein and Nathan Goodman. 1980. What does Boyce-Codd Normal Form Do?. In Sixth International Conference on Very Large Data Bases, October 1--3, 1980, Montreal, Quebec, Canada, Proceedings. 245--259."},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90065-3"},{"key":"e_1_2_2_9_1","first-page":"29","article-title":"Achievements of Relational Database Schema Design Theory Revisited. In Semantics in Databases, Selected Papers from a Workshop, Prague","volume":"1995","author":"Biskup Joachim","year":"1995","unstructured":"Joachim Biskup. 1995. Achievements of Relational Database Schema Design Theory Revisited. In Semantics in Databases, Selected Papers from a Workshop, Prague, Czech Republic, 1995. 29--54.","journal-title":"Czech Republic"},{"volume-title":"Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data","author":"Biskup Joachim","key":"e_1_2_2_10_1","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, Boston, Massachusetts, USA, May 30 - June 1. 143--151."},{"key":"e_1_2_2_11_1","first-page":"217","article-title":"On Relational Database Schemes Having Unique Minimal Key","volume":"27","author":"Biskup Joachim","year":"1991","unstructured":"Joachim Biskup, J\u00e1 nos Demetrovics, Leonid Libkin, and Ilya B. Muchnik. 1991. On Relational Database Schemes Having Unique Minimal Key. J. Inf. Process. Cybern., Vol. 27, 4 (1991), 217--225.","journal-title":"J. Inf. Process. Cybern."},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2007.09.007"},{"key":"e_1_2_2_13_1","volume-title":"Proceedings of the 6th IFIP Congress 1974","author":"Codd E. F.","year":"1974","unstructured":"E. F. Codd. 1974. Recent Investigations in Relational Data Base Systems. In Information Processing, Proceedings of the 6th IFIP Congress 1974, Stockholm, Sweden, August 5--10, 1974. 1017--1021."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/320263.320271"},{"key":"e_1_2_2_15_1","first-page":"205","article-title":"Normal Forms and Minimal Keys in the Relational Datamodel","volume":"11","author":"Demetrovics J\u00e1","year":"1994","unstructured":"J\u00e1 nos Demetrovics and Vu Duc Thi. 1994. Normal Forms and Minimal Keys in the Relational Datamodel. Acta Cybern., Vol. 11, 3 (1994), 205--215.","journal-title":"Acta Cybern."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/320557.320571"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/319587.319592"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/777943.777945"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1734714.1734717"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.536250"},{"key":"e_1_2_2_21_1","volume-title":"Second International Conference, AAIM 2006, Hong Kong, China, June 20--22, 2006, Proceedings. 102--113","author":"Henning K\u00f6","year":"2006","unstructured":"Henning K\u00f6 hler. 2006. Finding Faithful Boyce-Codd Normal Form Decompositions. In Algorithmic Aspects in Information and Management, Second International Conference, AAIM 2006, Hong Kong, China, June 20--22, 2006, Proceedings. 102--113."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2010.06.002"},{"key":"e_1_2_2_23_1","volume-title":"Proceedings of the 2016 International Conference on Management of Data, SIGMOD Conference 2016","author":"Henning","year":"2016","unstructured":"Henning K\u00f6 hler and Sebastian Link. 2016. SQL Schema Design: Foundations, Normal Forms, and Normalization. In Proceedings of the 2016 International Conference on Management of Data, SIGMOD Conference 2016, San Francisco, CA, USA, June 26 - July 01, 2016. 267--279."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2018.04.001"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.10.014"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2009.11.002"},{"key":"e_1_2_2_27_1","volume-title":"Reflections on Boyce-Codd Normal Form. In Eigth International Conference on Very Large Data Bases, September 8--10","author":"LeDoux Carol Helfgott","year":"1982","unstructured":"Carol Helfgott LeDoux and Douglas Stott Parker Jr. 1982. Reflections on Boyce-Codd Normal Form. In Eigth International Conference on Very Large Data Bases, September 8--10, 1982, Mexico City, Mexico, Proceedings. 131--141."},{"volume-title":"A guided tour of relational databases and beyond","author":"Levene Mark","key":"e_1_2_2_28_1","unstructured":"Mark Levene and George Loizou. 1999. A guided tour of relational databases and beyond. Springer."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.842267"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2019.04.003"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3459238"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(78)90009-0"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-023X(97)00029-3"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(86)90015-2"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.3991\/ijes.v4i4.6539"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/227604.227612"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90082-6"},{"key":"e_1_2_2_38_1","doi-asserted-by":"crossref","unstructured":"Thorsten Papenbrock and Felix Naumann. 2016. A Hybrid Approach to Functional Dependency Discovery. In SIGMOD. 821--833.","DOI":"10.1145\/2882903.2915203"},{"key":"e_1_2_2_39_1","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, Venice, Italy, March 21--24, 2017. 342--353."},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/278245.278247"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/990511.990513"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00050-9"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050157"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1016028.1016029"},{"key":"e_1_2_2_45_1","volume-title":"Discovery and Ranking of Functional Dependencies. In 35th IEEE International Conference on Data Engineering, ICDE 2019","author":"Wei Ziheng","year":"2019","unstructured":"Ziheng Wei and Sebastian Link. 2019. Discovery and Ranking of Functional Dependencies. In 35th IEEE International Conference on Data Engineering, ICDE 2019, Macao, China, April 8--11, 2019. 1526--1537."},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450518"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3588693","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,22]],"date-time":"2024-10-22T23:07:02Z","timestamp":1729638422000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588693"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,26]]},"references-count":46,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,5,26]]}},"alternative-id":["10.1145\/3588693"],"URL":"https:\/\/doi.org\/10.1145\/3588693","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2023,5,26]]}}}