Title :
On the Expressive Power of the Relational Algebra on Finite Sets of Relation Pairs
Author :
Fletcher, George H L ; Gyssens, Marc ; Paredaens, Jan ; Van Gucht, Dirk
Author_Institution :
Sch. of Eng. & Comput. Sci., Washington State Univ., Vancouver, WA
fDate :
6/1/2009 12:00:00 AM
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 co-graph-isomorphism hard and in co NP. The main result is also applied in providing a new characterization of the generic relational queries.
Keywords :
query languages; relational algebra; cograph-isomorphism hard problem; finite set; generic relational queries; language-independent characterization; relational algebra; source-target relation instance pair; BP completeness; Data manipulation languages; Query design and implementation languages; Query languages; Relational databases; data integration; data mapping; definability; expressibility; genericity; graph isomorphism; monotonicity.; relational algebra;
Journal_Title :
Knowledge and Data Engineering, IEEE Transactions on
DOI :
10.1109/TKDE.2008.221
