THE EXPRESSIVE POWER OF CARDINALITY-BOUNDED SET VALUES IN OBJECT-BASED DATA MODELS

In object-based data models, complex values such as tuples or sets hav e no special status and are represented just as any other object. Howe ver, different objects may represent the same value, i.e., duplicates may occur. It is known that typical object-based models supporting fir st-order queries, standard object creation, and while-loops, cannot in general guarantee the duplicate-freeness of representations of set va lues. Tn this paper, we consider a number of extensions of the basic o bject-based model which provide exactly this ability, under the assump tion that a fixed bound is known on the cardinality of the set values. We show that these extensions are all equivalent to each other. Our m ain result is that increasing the cardinality bound from m to m + 1 yi elds strictly more expressive extensions, except for In = 0 and rn = 3 . We thus establish a noncollapsing hierarchy.