On the expressive power of the relational algebra on finite sets of relation pairs

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