Paper Info
Title
Full hierarchical dependencies in fixed and undetermined universes
Abstract
Full hierarchical dependencies (FHDs) constitute a large class of relational dependencies. A relation exhibits an FHD precisely when it is the natural join over at least two of its projections that all share the same join attributes. Therefore, FHDs generalise multivalued dependencies (MVDs) in which case the number of these projections is precisely two. The implication of FHDs has originally been defined in the context of some fixed finite universe. This paper identifies a sound and complete set of inference rules for the implication of FHDs. This axiomatisation is very reminiscent of that for MVDs. Then, an alternative notion of FHD implication is introduced in which the underlying set of attributes is left undetermined. The first main result establishes a finite axiomatisation for FHD implication in undetermined universes. It is then formally clarified that the complementation rule is only a mere means for database normalisation. In fact, the second main result establishes a finite axiomatisation for FHD implication in fixed universes which allows to infer FHDs either without using the complementation rule at all or only in the very last step of the inference. This also characterises the expressiveness of an incomplete set of inference rules in fixed universes. The results extend previous work on MVDs by Biskup.
Year
DOI
Venue
2007
10.1007/s10472-007-9067-0
Ann. Math. Artif. Intell.
Keywords
Field
DocType
Relational database,Full hierarchical dependency,Implication,Inference,68P15
Relational database,Inference,Theoretical computer science,Artificial intelligence,Universe,Machine learning,Mathematics
Journal
Volume
Issue
ISSN
50
1-2
1012-2443
Citations 
PageRank 
References 
10
0.43
29
Authors
3
Name
Order
Citations
PageRank
Sven Hartmann1654.02
Henning Koehler216716.06
Sebastian Link330719.17