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
Source: 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.
Keywords: Query languages; relational algebra; data mapping; data integration; definability; expressibility; BP completeness; graph isomorphism; genericity; monotonicity
Document URI: http://hdl.handle.net/1942/9764
ISSN: 1041-4347
e-ISSN: 1558-2191
DOI: 10.1109/TKDE.2008.221
ISI #: 000265984900016
Category: A1
Type: Journal Contribution
Validations: ecoom 2010
Appears in Collections:Research publications

Show full item record

SCOPUSTM   
Citations

15
checked on Sep 2, 2020

WEB OF SCIENCETM
Citations

8
checked on May 13, 2022

Page view(s)

48
checked on Feb 24, 2022

Google ScholarTM

Check

Altmetric


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