On the Expressive Power of the Relational Algebra on Finite Sets of Relation Pairs
George Fletcher, Marc Gyssens, Jan Paredaens, Dirk Van Gucht · IEEE Transactions on Knowledge and Data Engineering · 2008
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.