Please use this identifier to cite or link to this item:
Title: The expressive power of cardinality-bounded set values in object-based data models
Authors: VAN DEN BUSSCHE, Jan 
Van Gucht, Dirk
Issue Date: 1995
Publisher: Elsevier Science B.V.
Source: Theoretical Computer Science, 149(1), p. 49-66
Abstract: In object-based data models, complex values such as tuples or sets have no special status and are represented just as any other object. However, different objects may represent the same value, i.e., duplicates may occur. It is known that typical object-based models supporting first-order queries, standard object creation, and while-loops, cannot in general guarantee the duplicate-freeness of representations of set values. In this paper, we consider a number of extensions of the basic object-based model which provide exactly this ability, under the assumption 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 main result is that increasing the cardinality bound from m to m + 1 yields strictly more expressive extensions, for m = 0 and m = 3. We thus establish a noncollapsing hierarchy.
Document URI:
DOI: 10.1016/0304-3975(95)00025-R
Type: Journal Contribution
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
values_card.pdf291.17 kBAdobe PDFView/Open
Show full item record

Page view(s)

checked on May 25, 2022


checked on May 25, 2022

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.