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].
68P15 Database theory