×

Datalog vs first-order logic. (English) Zbl 0824.68034

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.

MSC:

68P15 Database theory

Software:

Datalog
PDFBibTeX XMLCite
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.