|
Title
|
|
|
|
On the expressive power of the relational algebra on finite sets of relation pairs
|
|
|
Author
|
|
|
|
|
|
|
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. |
|
|
|
Language
|
|
|
|
English
|
|
|
Source (journal)
|
|
|
|
IEEE transactions on knowledge and data engineering. - New York, N.Y.
|
|
|
Publication
|
|
|
|
New York, N.Y.
:
2009
|
|
|
ISSN
|
|
|
|
1041-4347
|
|
|
DOI
|
|
|
|
10.1109/TKDE.2008.221
|
|
|
Volume/pages
|
|
|
|
21
:6
(2009)
, p. 939-942
|
|
|
ISI
|
|
|
|
000265984900016
|
|
|
Full text (Publisher's DOI)
|
|
|
|
|
|