Languages PQL and FO+LFP remain equivalent even in the absence of order (Q677720)

Let \(\text{FO}+\text{LFP}\) be a first-order language completed with the least fixed-point operator. \textit{M. Y. Vardi} [``Complexity of relational query languages'', Proc. 14th ACM Symp. Theory of Computing, San Francisco 1982, 137-146 (1982)] and \textit{N. Immerman} [``Relational queries computable in polynomial time'', ibid. 146-152 (1982); see also Inf. Control 68, 86-104 (1986; Zbl 0612.68086)] have shown that, in the presence of an order, in the language \(\text{FO}+\text{LFP}\) all the polynomial time queries to relational databases are exactly expressible. The second author [\textit{A. B. Livchak}, ``The language of polynomial programs'', in: Design and optimization of thermotechnical and electrochemical objects by means of computer, Sverdlovsk, 1982, 40 (1982); ``The language of polynomial queries'', ibid. 41 (1982)] described the languages \(\text{RPC}+\) and \(\text{PQL}\) which possess an analogous property. A natural question arises: Whether the mentioned languages will be equivalent if the order is not present? Partial answer to this question was given by \textit{Y. Gurevich} and \textit{S. Shelah} [Ann. Pure Appl. Logic 32, 265-280 (1986; Zbl 0621.03013)], who proved that the languages \(\text{FO}+\text{LFP}\) and \(\text{RPC}+\) are equivalent as well in the general situation. It remains to clarify the interrelations of these languages with \(\text{PQL}\). This is the subject of the present article.