dc.contributor.author |
Hannula, Miika |
en |
dc.contributor.author |
Kontinen, J |
en |
dc.contributor.author |
Link, Sebastian |
en |
dc.date.accessioned |
2016-06-27T02:34:11Z |
en |
dc.date.available |
2016-02-15 |
en |
dc.date.issued |
2016-08-01 |
en |
dc.identifier.citation |
Journal of Computer and System Sciences, 2016, 82 (5), pp. 856 - 877 (22) |
en |
dc.identifier.issn |
0022-0000 |
en |
dc.identifier.uri |
http://hdl.handle.net/2292/29186 |
en |
dc.description.abstract |
We investigate implication problems for keys and independence atoms in relational databases. For keys and unary independence atoms we show that finite implication is not finitely axiomatizable, and establish a finite axiomatization for general implication. The same axiomatization is also sound and complete for finite and general implication of unary keys and independence atoms, which coincide. We show that the general implication of keys and unary independence atoms and of unary keys and general independence atoms is decidable in polynomial time. For these two classes we also show how to construct Armstrong relations. Finally, we establish tractable conditions that are sufficient for certain classes of keys and independence atoms not to interact. |
en |
dc.description.uri |
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000374425900014&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=6e41486220adb198d0efde5a3b153e7d |
en |
dc.language |
English |
en |
dc.publisher |
Elsevier |
en |
dc.relation.ispartofseries |
Journal of Computer and System Sciences |
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. Details obtained from http://www.sherpa.ac.uk/romeo/issn/0022-0000/
https://www.elsevier.com/about/company-information/policies/sharing |
en |
dc.rights.uri |
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm |
en |
dc.subject |
Science & Technology |
en |
dc.subject |
Technology |
en |
dc.subject |
Computer Science, Hardware & Architecture |
en |
dc.subject |
Computer Science, Theory & Methods |
en |
dc.subject |
Computer Science |
en |
dc.subject |
Armstrong relation |
en |
dc.subject |
Axiomatization |
en |
dc.subject |
Dependence logic |
en |
dc.subject |
Finite implication |
en |
dc.subject |
Implication |
en |
dc.subject |
Independence |
en |
dc.subject |
Key |
en |
dc.subject |
CONDITIONAL-INDEPENDENCE |
en |
dc.subject |
INCLUSION DEPENDENCIES |
en |
dc.subject |
FUNCTIONAL-DEPENDENCIES |
en |
dc.subject |
INTEGRITY CONSTRAINTS |
en |
dc.subject |
ALGORITHMIC PROPERTIES |
en |
dc.subject |
DATABASE DEPENDENCIES |
en |
dc.subject |
RELATIONAL DATABASE |
en |
dc.subject |
CANDIDATE KEYS |
en |
dc.subject |
XML |
en |
dc.subject |
NORMALIZATION |
en |
dc.title |
On the finite and general implication problems of independence atoms and keys |
en |
dc.type |
Journal Article |
en |
dc.identifier.doi |
10.1016/j.jcss.2016.02.007 |
en |
pubs.issue |
5 |
en |
pubs.begin-page |
856 |
en |
pubs.volume |
82 |
en |
dc.description.version |
AM - Accepted Manuscript |
en |
dc.rights.holder |
|
en |
pubs.author-url |
http://www.sciencedirect.com/science/article/pii/S0022000016000222 |
en |
pubs.end-page |
877 |
en |
pubs.publication-status |
Published |
en |
dc.rights.accessrights |
http://purl.org/eprint/accessRights/OpenAccess |
en |
pubs.subtype |
Article |
en |
pubs.elements-id |
530533 |
en |
pubs.org-id |
Science |
en |
pubs.org-id |
School of Computer Science |
en |
dc.identifier.eissn |
1090-2724 |
en |
pubs.record-created-at-source-date |
2016-06-23 |
en |