Affiliations: Alfréd Rényi Institute of Mathematics
Hungarian Academy of Sciences Budapest, P.O.B.127, H-1364 Hungary. E-mail:
[email protected] | Massey University Information Science Research Centre
Private Bag 11 222, Palmerston North, New Zealand. E-mail:
[email protected]
Abstract: We investigate functional dependencies (FDs) in the presence of
several constructors for complex values. These constructors are the tuple
constructor, list-, set- and multiset-constructors, an optionality constructor,
and a disjoint union constructor. The disjoint union constructor implies
restructuring rules, which complicate the theory. In particular, they do not
permit a straightforward axiomatisation of the class of all FDs without a
detour via weak functional dependencies (wFDs), i.e. disjunctions of functional
dependencies, and even the axiomatisation of wFDs is not yet completely solved.
Therefore, we look at the restricted class of counter-free
functional dependencies (cfFDs). That is, we ignore subattributes that only
refer to counting the number of elements in sets or multisets or distinguish
only between empty or non-empty sets. We present a finite axiomatisation for
the class of cfFDs. Furthermore, we study keys ignoring again the counting
subattributes. We show that such keys are equivalent with certain ideals called
HL-ideals. Based on that we introduce an ordering between key sets, and
investigate systems of minimal keys. We give a sufficient condition for a
Sperner family of HL-ideals being a system of minimal keys, and determine lower
and upper bounds for the size of the smallest Armstrong-instance.
Keywords: functional dependencies, keys, type constructors, axiomatisation, Sperner families
