Document Server@UHasselt >
Research >
Research publications >

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

Title: The Expressive Power of Complex Values in Object-Based Data Models
Paredaens, Jan
Issue Date: 1995
Publisher: Academic Press
Citation: 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.
URI: http://hdl.handle.net/1942/695
DOI: 10.1006/inco.1995.1110
Type: Journal Contribution
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
N/A364.96 kBAdobe PDF

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