dc.contributor.author |
Link, S |
en |
dc.contributor.author |
Wei, Z |
en |
dc.date.accessioned |
2022-01-14T03:42:10Z |
|
dc.date.available |
2022-01-14T03:42:10Z |
|
dc.date.issued |
2021 |
en |
dc.identifier.citation |
CDMTCS Research Reports CDMTCS-553 (2021) |
en |
dc.identifier.issn |
1178-3540 |
en |
dc.identifier.uri |
https://hdl.handle.net/2292/58015 |
|
dc.description.abstract |
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-Codd 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
`-Bounded Cardinality Normal Form, parameterized by a positive integer `. For
every `, 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 ` tuples. BCNF is captured when ` = 1. We demonstrate that schemata
in this normal form characterize the instances that are i) free from level ` data
redundancy and update inefficiency, and ii) permit level ` join efficiency. We establish algorithms that compute schemata in `-Bounded Cardinality Normal Form
for the smallest level ` attainable across all 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, level ` quantifies both the incremental maintenance and join support
of materialized views. 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. |
|
dc.publisher |
Department of Computer Science, The University of Auckland, New Zealand |
en |
dc.relation.ispartofseries |
CDMTCS Research Report Series |
en |
dc.rights |
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher. |
en |
dc.rights.uri |
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm |
en |
dc.source.uri |
https://www.cs.auckland.ac.nz/research/groups/CDMTCS/researchreports/index.php |
en |
dc.title |
Logical Schema Design that Quantifies Update Inefficiency and Join Efficiency |
en |
dc.type |
Technical Report |
en |
dc.subject.marsden |
Fields of Research |
en |
dc.rights.holder |
Copyright: The author(s) |
en |
dc.rights.accessrights |
http://purl.org/eprint/accessRights/OpenAccess |
en |