Domain independence and the relational calculus (Q1338897)

Several alternative semantics (or interpretations) of the relational (domain) calculus are studied here. It is shown that they all have the same expressive power, i.e., the selection of any of the semantics neither gains nor loses expressive power. Since the domain is potentially infinite, the answer to a relational calculus query is sometimes infinite (and hence not a relational). The following approaches which guarantee the finiteness of answers to queries are studied here: output-restricted unlimited interpretation, domain independental queries, output-restricted finite and countable invention, and limited interpretation. Of particular interest is the output- restricted unlimited interpretation -- although the output is restricted to the active domain of the input and query, the quantified variables range over the infinite underlying domain. While this is close to the intuitive interpretation given to calculus formulas, the naive approach to evaluating queries under this semantics calls for the impossible task of examining infinitely many values. We describe here a construction which, given a query \(Q\) under the output-restricted unlimited interpretation, yields a domain independent query \(Q'\), with length no more than exponential in the length of \(Q\), such that \(Q\) and \(Q'\) (under their respective semantics) express the same function.