Counter-Free Keys and Functional Dependencies in Higher-Order Datamodels

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.