JUCS - Journal of Universal Computer Science 15(1): 304-354, doi: 10.3217/jucs-015-01-0304
A Characterisation of Coincidence Ideals for Complex Values
expand article infoAttila Sali, Klaus-Dieter Schewe§
‡ Alfréd Rényi Institute of Mathematics, Budapest, Hungary§ Johannes Kepler University Linz, Linz, Austria
Open Access
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
complex values, restructuring, coincidence ideal