www.uhasselt.be
DSpace

Document Server@UHasselt >
Research >
Research publications >

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

Title: On the Expressive Power of the Relational Algebra on Finite Sets of Relation Pairs
Authors: Fletcher, George H. L.
GYSSENS, Marc
Paredaens, Jan
Van Gucht, Dirk
Issue Date: 2009
Publisher: IEEE COMPUTER SOC
Citation: IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 21(6). p. 939-942
Abstract: We give a language-independent characterization of the expressive power of the relational algebra on finite sets of source-target relation instance pairs. The associated decision problem is shown to be cograph-isomorphism hard and in coNP. The main result is also applied in providing a new characterization of the generic relational queries.
Notes: [Fletcher, George H. L.] Washington State Univ, Sch Engn & Comp Sci, Vancouver, WA 98686 USA. [Gyssens, Marc] Hasselt Univ, Dept WNI, B-3590 Diepenbeek, Belgium. [Paredaens, Jan] Univ Antwerp, Dept Math & Comp Sci, B-2020 Antwerp, Belgium. [Van Gucht, Dirk] Indiana Univ, Dept Comp Sci, Bloomington, IN 47405 USA.
URI: http://hdl.handle.net/1942/9764
DOI: 10.1109/TKDE.2008.221
ISI #: 000265984900016
ISSN: 1041-4347
Category: A1
Type: Journal Contribution
Validation: ecoom, 2010
Appears in Collections: Research publications

Files in This Item:

There are no files associated with this item.

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