dc.contributor.author |
Hannula, M |
en |
dc.contributor.author |
Link, S |
en |
dc.date.accessioned |
2019-01-09T02:23:03Z |
en |
dc.date.available |
2019-01-09T02:23:03Z |
en |
dc.date.issued |
2018 |
en |
dc.identifier.citation |
CDMTCS Research Reports CDMTCS-518 (2018) |
en |
dc.identifier.issn |
1178-3540 |
en |
dc.identifier.uri |
http://hdl.handle.net/2292/45066 |
en |
dc.description.abstract |
Infamously, the finite and unrestricted implication problems for the classes of i) functional and inclusion dependencies together, and ii) embedded multivalued dependencies alone are each undecidable. Famously, the restriction of i) to functional and unary inclusion dependencies in combination with the restriction of ii) to multivalued dependencies yield implication problems that are still different in the finite and unrestricted case, but each are finitely axiomatizable and decidable in low-degree polynomial time. An important embedded tractable fragment of embedded multivalued dependencies are independence atoms. These stipulate independence between two attribute sets in the sense that for every two tuples there is a third tuple that agrees with the first tuple on the first attribute set and with the second tuple on the second attribute set. Our main results show that finite and unrestricted implication deviate for the combined class of independence atoms, unary functional and unary inclusion dependencies, but both are axiomatizable and decidable in low-degree polynomial time. This combined class adds arbitrary independence atoms to unary keys and unary foreign keys, which frequently occur in practice as surrogate keys and references to them. |
en |
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 |
On the Interaction of Functional and Inclusion Dependencies with Independence Atoms |
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 |