Paper Info
Title
On multivalued dependencies in fixed and undetermined universes
Abstract
The implication of multivalued dependencies (MVDs) in relational databases has originally been defined in the context of some fixed finite universe. While axiomatisability and implication problem have been intensely studied with respect to this notion, almost no research has been devoted towards the alternative notion of implication in which the underlying universe of attributes is left undetermined. Based on a set of common inference rules we reveal all axiomatisations in undetermined universes, and all axiomatisations in fixed universes that indicate the role of the complementation rule as a means of database normalisation. This characterises the expressiveness of several incomplete sets of inference rules. We also establish relationships between axiomatisations in fixed and undetermined universes, and study the time complexity of the implication problem in undetermined universes.
Year
DOI
Venue
2006
10.1007/11663881_15
FoIKS
Keywords
Field
DocType
complementation rule,fixed universe,multivalued dependency,fixed finite universe,database normalisation,underlying universe,alternative notion,implication problem,undetermined universe,inference rule,common inference rule,time complexity,relational database
Multivalued dependency,Algebra,Relational database,Computer science,Algorithm,Theoretical computer science,Boolean algebra,Universe,Time complexity,Rule of inference,Expressivity
Conference
Volume
ISSN
ISBN
3861
0302-9743
3-540-31782-1
Citations 
PageRank 
References 
8
0.43
31
Authors
1
Name
Order
Citations
PageRank
Sebastian Link130719.17