Algorithms for the Discovery of Embedded Functional Dependencies

Show simple item record

dc.contributor.author Wei, Z en
dc.contributor.author Hartmann, S en
dc.contributor.author Link, S en
dc.date.accessioned 2022-01-14T03:42:09Z
dc.date.available 2022-01-14T03:42:09Z
dc.date.issued 2020 en
dc.identifier.citation CDMTCS Research Reports CDMTCS-542 (2020) en
dc.identifier.issn 1178-3540 en
dc.identifier.uri https://hdl.handle.net/2292/58005
dc.description.abstract Embedded functional dependencies (eFDs) were recently introduced to tailor relational schema design to data completeness requirements of applications. They also facilitate data cleaning and data integration. A problem that is essential to unlocking these applications is the discovery of all eFDs that hold on a given data set. We show that the discovery problem of eFDs is NP-complete, W[2]-complete in the output, and has a minimum solution space that is larger than the maximum solution space for functional dependencies. Despite these computational challenges, we use novel data structures and search strategies to develop row-efficient, columnefficient, and hybrid algorithms that can efficiently solve the discovery problem for eFDs on large real-world benchmark data sets. Our experiments also demonstrate that the algorithms scale well in terms of their design targets, and that ranking the eFDs by the number of redundant data values they cause can provide useful guidance in identifying meaningful eFDs for applications. Finally, we demonstrate the benefits of introducing completeness requirements and ranking by the number of redundant data values for approximate and genuine functional dependencies.
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 Algorithms for the Discovery of Embedded Functional Dependencies 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


Files in this item

Find Full text

This item appears in the following Collection(s)

Show simple item record

Share

Search ResearchSpace


Browse

Statistics