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

Assuming data domains are partially ordered, we define the partially ordere d relational algebra (PORA) by allowing the ordering predicate subset of or equal to to be used in Formulae of the selection operator sigma. We apply Paredaens and Bancilhon's Theorem to examine the expressiveness of the PORA , and show that the PORA expresses exactly the set of all possible relation s which are invariant under order-preserving automorphisms of databases. Th e extension is consistent with the two important extreme cases of unordered and linearly ordered domains. We also investigate the three hierarchies of : (1) computable queries, (2) query languages and (3) partially ordered dom ains, and show that there is a one-to-one correspondence between them.