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

Abstract

Assuming data domains are partially ordered, we define the partially ordered relational algebra (PORA) by allowing the ordering predicate ⊑ to be used in formulae of the selection operator σ. 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 relations which are invariant under order-preserving automorphisms of databases. The 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 domains, and show that there is a one-to-one correspondence between them.

Keywords:

• Partially ordered domains
• relational algebra
• relational databases

C.R. Categories:

• F.4.3
• H.2.1