Contextual Keys

Abstract

Much work has been done on extending the relational model of data to encompass incomplete information. In particular, a plethora of research has examined the semantics of integrity constraints in the presence of null markers. We propose a new approach whose semantics relies exclusively on fragments of complete data within an incomplete relation. For this purpose, we introduce the class of contextual keys. Users can specify the context of a key as a set of attributes that selects the sub-relation of tuples with no null marker occurrences on the attributes of the context. Then the key uniquely identifies the tuples within the sub-relation. The standard notion of a key over complete relations is the special case of a contextual key whose context consists of all attributes. SQL unique constraints form the special case of a contextual key whose context coincides with the set of key attributes. We establish structural and computational characterizations of the associated implication problem, and of their Armstrong databases. The computation of Armstrong databases has been implemented in a tool, and experiments provide insight into the actual run-time behavior of the algorithms that complement our detailed computational complexity analysis.