Closed Sets of Boolean Terms in Relational Databases

Abstract

A number of approaches have been taken to represent compound, structured values in relational databases. We review a few such approaches and discuss a new approach, in which every set is represented as a Boolean term. We show that this approach generalizes the other approaches, leading to more flexible representation. Boolean term representation seems to be appropriate in handling incomplete information: this approach generalizes some other approaches (e.g. null value mark, null variables, etc). We consider definitions of algebraic operations on such sets, like join, union, selection, etc. Moreover, we introduce a measure of computational complexity of these operations.