Please use this identifier to cite or link to this item:
Title: The Expressive Power of Complex Values in Object-Based Data Models
Authors: VAN DEN BUSSCHE, Jan 
Paredaens, Jan
Issue Date: 1995
Publisher: Academic Press
Source: Information and Computation, 120(2), p. 220-236
Abstract: In object-based data models, complex values such as tuples or sets have no special status and must therefore be represented by objects. As a consequence, different objects may represent the same value, i.e., duplicates may occur. This paper contains a study of the precise expressive power required for the representation of complex values in typical object-based data models supporting first-order queries, object creation, and while-leaps. Such models are sufficiently powerful to express any reasonable collection of complex values, provided duplicates are allowed. It is shown that in general, the presence of such duplicates is unavoidable in the case of set values. In contrast, duplicates of tuple values can easily be eliminated. A fundamental operation for elimination of duplicate set values, called abstraction, is considered and shown to be a tractable alternative to explicit powerset construction. Other means of avoiding duplicates, such as total order, equality axioms, or copy elimination, are also discussed.
Document URI:
DOI: 10.1006/inco.1995.1110
Type: Journal Contribution
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
values.pdf364.96 kBAdobe PDFView/Open
Show full item record


checked on Sep 2, 2020


checked on May 22, 2022

Page view(s)

checked on May 24, 2022


checked on May 24, 2022

Google ScholarTM



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