Abstract
We show that the homomorphism preservation theorem fails for LFP, both in general and in restriction to finite structures. That is, there is a formula of LFP that is preserved under homomorphisms (in the finite) but is not equivalent (in the finite) to a Datalog program. This resolves a question posed by Atserias. The results are established by two different methods: (1) a method of diagonalisation that works only in the presence of infinite structures, but establishes a stronger result showing a hierarchy of homomorphism-preserved problems in LFP; and (2) a method based on a pumping lemma for Datalog due to Afrati, Cosmadakis and Yannakakis which establishes the result in restriction to finite structures. We refine the pumping lemma of Afrati et al. and relate it to the power of Monadic Second-Order Logic on tree decompositions of structures.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Directed Acyclic Graph
- Monotone Operator
- Constraint Satisfaction Problem
- Atomic Formula
- Tree Decomposition
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Open Problems List for the MathsCSP Workshop, Oxford (2006), http://www.cs.rhul.ac.uk/home/green/mathscsp/
Afrati, F., Cosmadakis, S., Yannakakis, M.: On Datalog vs. Polynomial Time. Journal of Computer and System Sciences 51, 177–196 (1995)
Atserias, A.: The homomorphism preservation property. In: Talk at International Workshop on Mathematics of Constraint Satisfaction, Oxford (2006)
Atserias, A., Bulatov, A., Dawar, A.: Affine systems of equations and counting infinitary logic. In: Proc. 34th International Colloquium on Automata, Languages and Programming. LNCS, vol. 4596, pp. 558–570. Springer, Heidelberg (2007)
Atserias, A., Dawar, A., Grohe, M.: Preservation under extensions on well-behaved finite structures. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 1437–1449. Springer, Heidelberg (2005)
Atserias, A., Dawar, A., Kolaitis, P.G.: On preservation under homomorphisms and unions of conjunctive queries. Journal of the ACM 53, 208–237 (2006)
Chandra, A.K., Merlin, P.M.: Optimal implementation of conjunctive queries in relational databases. In: Proc. 9th ACM Symp. on Theory of Computing, pp. 77–90 (1977)
Ebbinghaus, H.-D., Flum, J.: Finite Model Theory, 2nd edn. Springer, Heidelberg (1999)
Feder, T., Vardi, M.Y.: Computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory. SIAM Journal of Computing 28, 57–104 (1998)
Feder, T., Vardi, M.Y.: Homomorphism closed vs existential positive. In: Proc. of the 18th IEEE Symp. on Logic in Computer Science, pp. 311–320 (2003)
Grohe, M.: Logic, graphs, and algorithms. In: Flum, J., Grädel, E., Wilke, T. (eds.) Logic and Automata History and Perspectives, Amsterdam University Press (2007)
Hodges, W.: Model Theory. Cambridge University Press, Cambridge (1993)
Immerman, N.: Relational queries computable in polynomial time. Information and Control 68, 86–104 (1986)
Kolaitis, P.G., Vardi, M.Y.: Conjunctive query containment and constraint satisfaction. Journal of Computer and System Sciences 61, 302–332 (2000)
Makowsky, J.A.: Algorithmic uses of the Feferman-Vaught theorem. Annals of Pure and Applied Logic 126, 159–213 (2004)
Moschovakis, Y.N.: Elementary Induction on Abstract Structures. North Holland, Amsterdam (1974)
Rossman, B.: Existential positive types and preservation under homomorphisisms. In: 20th IEEE Symposium on Logic in Computer Science, pp. 467–476 (2005)
Vardi, M.Y.: The complexity of relational query languages. In: Proc. of the 14th ACM Symp. on the Theory of Computing, pp. 137–146 (1982)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dawar, A., Kreutzer, S. (2008). On Datalog vs. LFP. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds) Automata, Languages and Programming. ICALP 2008. Lecture Notes in Computer Science, vol 5126. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-70583-3_14
Download citation
DOI: https://doi.org/10.1007/978-3-540-70583-3_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-70582-6
Online ISBN: 978-3-540-70583-3
eBook Packages: Computer ScienceComputer Science (R0)