Linear vs. Polynomial Constraints in Database Query Languages

We prove positive and negative results on the expressive power of the relational calculus augmented with linear constraints. We show non-expressibility of some properties expressed by polynomial constraints. We also show expressibility of some queries involving existence of lines, when the query output has a simple geometrical relation to the input. Finally, we compare the expressive power of linear vs. polynomial constraints in the presence of a discrete order. 1 Introduction An active area of recent research is concerned with integrating constraints into logical formalisms for programming languages [DG,JL87,Ma87,Sa] and database query languages [BJM93,KKR90, Kup90,Kup93,Re90]. Constraints are incorporated in logic programming systems such as CLP, Prolog III and CHIP. The class of linear constraints is of particular interest, because of its applicability and the potential for efficient implementation [HJLL90,JL87,La90]. Kanellakis et.al.[KKR90] describe a methodology to combine const..