A Characterisation of Coincidence Ideals for Complex Values

Attila Sali (Alfréd Rényi Institute of Mathematics, Hungary)

Klaus-Dieter Schewe (Information Science Research Centre, New Zealand)

Abstract: We investigate properties of coincidence ideals in subattribute lattices that occur in complex value datamodels, i.e. sets of subattributes, on which two complex values coincide. We let complex values be defined by constructors for records, sets, multisets, lists, disjoint union and optionality, i.e. the constructors cover the gist of all complex value data models. Such lattices carry the structure of a Brouwer algebra as long as the union-constructor is absent, and for this case sufficient and necessary conditions for coincidence ideals are already known. In this paper, we extend the characterisation of coincidence ideals to the most general case. The presence of the disjoint union constructor complicates all results and proofs significantly. The reason for this is that the union-constructor causes non-trivial restructuring rules to hold. The characterisation of coincidence ideal is of decisive importance for the axiomatisation of (weak) functional dependencies.

Keywords: coincidence ideal, complex values, restructuring

Categories: F.4.1, H.2.1