On the Expressive Power of the Relational Algebra on Finite Sets of Relation Pairs

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

Check