Ajtai, Miklos; Gurevich, Yuri Datalog vs first-order logic. (English) Zbl 0824.68034 J. Comput. Syst. Sci. 49, No. 3, 562-588 (1994). Summary: Our main result is that every datalog query expressible in first-order logic is bounded; in terms of classical model theory it is a kind of compactness theorem for finite structures. In addition, we give some counter-examples delimiting the main result. Cited in 17 Documents MSC: 68P15 Database theory Keywords:query languages; datalog; first-order logic Software:Datalog PDFBibTeX XMLCite \textit{M. Ajtai} and \textit{Y. Gurevich}, J. Comput. Syst. Sci. 49, No. 3, 562--588 (1994; Zbl 0824.68034) Full Text: DOI References: [1] Ajtai, M.; Gurevich, Y., Datalog vs. first-order logic, (30th Annual Symposium on Foundations of Computer Science (1989), IEEE Computer Society: IEEE Computer Society Amsterdam), 142-147 [2] Cosmadakis, S. S., On the first-order expressibility of recursive queries, (Principles of Database Systems (1987), ACM), 311-323 [3] B. Courcelle, Private communication.; B. Courcelle, Private communication. [4] Gaifman, H., On local and non-local properties, (Stern, J., Proceedings of the Herbrand Symposium, Logic Colloquium ’81 (1982), North-Holland) · Zbl 0209.30801 [5] Y. Gurevich, Toward logic tailored for computational complexity, in “Computation and Proof Theory” (M. Richter et al., Ed.), Lecture Notes in Mathematics, Vol. 1104, pp. 175-216.; Y. Gurevich, Toward logic tailored for computational complexity, in “Computation and Proof Theory” (M. Richter et al., Ed.), Lecture Notes in Mathematics, Vol. 1104, pp. 175-216. [6] P. Kolaitis and M. Y. Vardi, Private communication.; P. Kolaitis and M. Y. Vardi, Private communication. [7] Robertson, N.; Seymour, P. D., Graph minors. III. Planar tree-width, J. Combin. Theory Ser. B, 36, 49-64 (1984) · Zbl 0548.05025 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.