# zbMATH — the first resource for mathematics

Expressive power: The infinite case. (English) Zbl 0989.68044
Kuper, Gabriel (ed.) et al., Constraint databases. Berlin: Springer. 89-107 (2000).
In chapter 4 the authors study the expressive power of constraint query languages over possibly infinite, finely representable databases. The chapter is divided into five sections. After an introduction, data complexity for first-order queries over constraint databases is investigated in section 4.2, namely, for three classes of constraints: $$\text{FO}(<)$$ (over dense order), $$\text{FO}+\text{LIN}$$, and $$\text{FO}+\text{POLY}$$. The main results are that the complexity upper bounds for these theories are, respectively, $$\text{AC}^0$$, $$\text{NC}^1$$, and NC. In section 4.3, the first-order definability of various representative queries that are of interest for applications of constraint databases is studied. The authors show that certain queries are not definable in $$\text{FO}+\text{LIN}$$ or $$\text{FO}+\text{POLY}$$. In section 4.4, a recursion is added. DATALOG$$^\neg$$ with inflationary negation on dense order databases is considered. It is shown that $$\text{FO}(<)$$ captures all PTIME order-generic queries over that domain. Concerning $$\text{FO}+\text{LIN}$$, while DATALOG$$^\neg$$, over this domain is too powerful (and not closed), a certain restricted class of queries captures precisely the PTIME queries. The chapter finishes with bibliographical notes.
For the entire collection see [Zbl 0935.00022].
##### MSC:
 68P15 Database theory