Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/696

Title: The expressive power of cardinality-bounded set values in object-based data models
Van Gucht, Dirk
Issue Date: 1995
Publisher: Elsevier Science B.V.
Citation: 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.
URI: http://hdl.handle.net/1942/696
DOI: 10.1016/0304-3975(95)00025-R
Type: Journal Contribution
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
N/A291.17 kBAdobe PDF

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