On the expressive power of the relational algebra with partially ordered domains

Assuming data domains are partially ordered, we apply Paredaens ’ and Bancilhon’s Theorem to examine the expressiveness of the extended rela-tional algebra (the PORA), which allows the ordering predicate v to be used in formulae of the selection operator (σ). The PORA expresses exactly the set of all possible relations which are invariant under order-preserving automorphism of databases. Our main result shows that there is a one-to-one correspondence between three hierarchies of: (1) computable queries, (2) query languages and (3) partially ordered domains