Armstrong axioms and Boyce-Codd-Heath normal form under bag semantics

Show simple item record Koehler, H en Link, Sebastian en 2011-12-07T20:55:47Z en 2010-07-31 en
dc.identifier.citation Information Processing Letters 110(16):717-724 31 Jul 2010 en
dc.identifier.issn 0020-0190 en
dc.identifier.uri en
dc.description.abstract The theory of functional dependencies is based on relations, i.e. sets of tuples. Over relations, the class of functional dependencies subsumes the class of keys. Commercial database systems permit the storage of bags of tuples where duplicate tuples can occur. Over bags, keys and functional dependencies interact differently from how they interact over relations. We establish finite ground axiomatizations of keys and functional dependencies over bags, and show a strong correspondence to goal and definite clauses in classical propositional logic. We define a syntactic Boyce–Codd–Heath Normal Form condition, and show that the condition characterizes schemata that will never have any redundant data value occurrences in their instances. The results close the gap between the existing set-based theory of data dependencies and database practice where bags are permitted. en
dc.publisher Elsevier B.V. en
dc.relation.ispartofseries Information Processing Letters 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 en
dc.rights.uri en
dc.subject database en
dc.subject multiset en
dc.subject key en
dc.subject functional dependency en
dc.subject Armstrong axioms en
dc.subject normal form en
dc.title Armstrong axioms and Boyce-Codd-Heath normal form under bag semantics en
dc.type Journal Article en
dc.identifier.doi 10.1016/j.ipl.2010.06.002 en
pubs.issue 16 en
pubs.begin-page 717 en
pubs.volume 110 en
dc.rights.holder Copyright: Elsevier B.V. en
pubs.end-page 724 en
dc.rights.accessrights en
pubs.subtype Article en
pubs.elements-id 257255 en Science en School of Computer Science en
pubs.record-created-at-source-date 2011-12-08 en

Files in this item

There are no files associated with this item.

Find Full text

This item appears in the following Collection(s)

Show simple item record


Search ResearchSpace