QUERIES WITH ARITHMETICAL CONSTRAINTS

In this paper, we study the expressive power and the complexity of fir st-order logic with arithmetic, as a query language over relational an d constraint databases. We consider constraints over various domains ( N,Z,Q, and R), and with various arithmetical operations (less than or equal to, +, x, etc.). We first consider the data complexity of first- order queries. We prove in particular that linear queries can be evalu ated in AC(0) over finite integer databases, and in NC1 over linear co nstraint databases. This improves previously known bounds. We also sho w that over all domains, enough arithmetic lead to arithmetical querie s, therefore, showing the frontiers of constraints for database purpos es. We then tackle the problem of the expressive power, with the defin ability of the parity and the connectivity, which are the most classic al examples of queries not expressible in first-order logic over finit e structures. We prove that these two queries are first-order definabl e in the presence of (enough) arithmetic. Nevertheless, we show that t hey are not definable with constraints of interest for constraint data bases such as linear constraints for instance. Finally, we developed r eduction techniques for queries over constraint databases, that allow us to draw conclusions with respect to their undefinability in various constraint query languages.