J. Vandenbussche et D. Vangucht, THE EXPRESSIVE POWER OF CARDINALITY-BOUNDED SET VALUES IN OBJECT-BASED DATA MODELS, Theoretical computer science, 149(1), 1995, pp. 49-66
Citations number
21
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
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.