Authors:
Stéphane Grumbach, Jianwen Su
Abstract:
AbstractIn this paper, we study the expressive power and the complexity of first-order logic with arithmetic, as a query language over relational and constraint databases. We consider constraints over various domains (N, Z, Q, and R), and with various arithmetical operations (⩽, +, ×, etc.).We first consider the data complexity of first-order queries. We prove in particular that linear queries can be evaluated in AC0 over finite integer databases, and in NC1 over linear constraint databases. This improves previously known bounds. We also sho (...)
AbstractIn this paper, we study the expressive power and the complexity of first-order logic with arithmetic, as a query language over relational and constraint databases. We consider constraints over various domains (N, Z, Q, and R), and with various arithmetical operations (⩽, +, ×, etc.).We first consider the data complexity of first-order queries. We prove in particular that linear queries can be evaluated in AC0 over finite integer databases, and in NC1 over linear constraint databases. This improves previously known bounds. We also show that over all domains, enough arithmetic lead to arithmetical queries, therefore, showing the frontiers of constraints for database purposes.We then tackle the problem of the expressive power, with the definability of the parity and the connectivity, which are the most classical examples of queries not expressible in first-order logic over finite structures. We prove that these two queries are first-order definable in the presence of (enough) arithmetic. Nevertheless, we show that they are not definable with constraints of interest for constraint databases such as linear constraints for instance. Finally, we developed reduction techniques for queries over constraint databases, that allow us to draw conclusions with respect to their undefinability in various constraint query languages.
(Read More)