Homomorphism preservation theorems

ABSTRACT

The homomorphism preservation theorem (h.p.t.), a result in classical model theory, states that a first-order formula is preserved under homomorphisms on all structures (finite and infinite) if and only if it is equivalent to an existential-positive formula. Answering a long-standing question in finite model theory, we prove that the h.p.t. remains valid when restricted to finite structures (unlike many other classical preservation theorems, including the Łoś--Tarski theorem and Lyndon's positivity theorem). Applications of this result extend to constraint satisfaction problems and to database theory via a correspondence between existential-positive formulas and unions of conjunctive queries. A further result of this article strengthens the classical h.p.t.: we show that a first-order formula is preserved under homomorphisms on all structures if and only if it is equivalent to an existential-positive formula of equal quantifier-rank.

REFERENCES

• 1: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 2: Miklos Ajtai , Yuri Gurevich, Monotone versus positive, Journal of the ACM (JACM), v.34 n.4, p.1004-1015, Oct. 1987 [doi>10.1145/31846.31852]
• 3: Miklos Ajtai , Yuri Gurevich, Datalog vs. first-order logic, Journal of Computer and System Sciences, v.49 n.3, p.562-588, Dec. 1994
• 4: Natasha Alechina , Yuri Gurevich, Syntax vs. Semantics on Finite Structures, Structures in Logic and Computer Science, A Selection of Essays in Honor of Andrzej Ehrenfeucht, p.14-33, January 1997
• 5: Albert Atserias, On Digraph Coloring Problems and Treewidth Duality, Proceedings of the 20th Annual IEEE Symposium on Logic in Computer Science, p.106-115, June 26-29, 2005 [doi>10.1109/LICS.2005.31]
• 6: Albert Atserias , Anuj Dawar , Phokion G. Kolaitis, On preservation under homomorphisms and unions of conjunctive queries, Journal of the ACM (JACM), v.53 n.2, p.208-237, March 2006 [doi>10.1145/1131342.1131344]
• 7: Baldwin, J. 2000. Finite and infinite model theory—A historical perspective. Log. J. IGPL 8, 5, 605--628.
• 8: Blass, A., and Rossman, B. 2005. Explicit graphs with extension properties. Bull. Eur. Assoc. Theor. Comput. Sci. 86, 166--175.
• 9: Ashok K. Chandra , Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing, p.77-90, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803397]
• 10: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• 11: Jitender S. Deogun , Ton Kloks , Dieter Kratsch , Haiko Müller, On Vertex Ranking for Permutations and Other Graphs, Proceedings of the 11th Annual Symposium on Theoretical Aspects of Computer Science, p.747-758, February 24-26, 1994
• 12: Ebbinghaus, H., and Flum, J. 1996. Finite Model Theory. Springer-Verlag, New York.
• 13: Tomás Feder , Moshe Y. Vardi, Homomorphism Closed vs. Existential Positive, Proceedings of the 18th Annual IEEE Symposium on Logic in Computer Science, p.311, June 22-25, 2003
• 14: Feferman, S., and Vaught, R. L. 1959. The first order properties of products of algebraic systems. Fund. Math. 47, 57--103.
• 15: Grädel, E., Kolaitis, P., Libkin, L., Marx, M., Spencer, J., Vardi, M., Venema, Y., and Weinstein, S. 2007. Finite Model Theory and Its Applications. Springer-Verlag, New York.
• 16: Grädel, E., and Rosen, E. 1999. On preservation theorems for two-variable logic. Math. Logic Quart. 45, 315--325.
• 17: Gurevich, Y. 1984. Toward logic tailored for computational complexity. In Computation and Proof Theory, Lecture Notes in Mathematics, Springer-Verlag, New York, 175--216.
• 18: Gurevich, Y. 1988. Logic and the challenge of computer science. In Current Trends in Theoretical Computer Science, E. Boerger, Ed. 1--57.
• 19: Gurevich, Y. 1990. On finite model theory (extended abstract). In Feasible Mathematics, S. R. Buss and P. J. Scott, Eds. Birkhäuser, 211--219.
• 20: Pavol Hell , Jaroslav Nešetřil, The core of a graph, Discrete Mathematics, v.109 n.1-3, p.117-126, Nov. 12, 1992 [doi>10.1016/0012-365X(92)90282-K]
• 21: Hell, P., and Nešetřil, J. 2004. Graphs and Homomorphisms. Oxford University Press.
• 22: Hodges, W. 1993. Model Theory. Cambridge University Press, Cambridge, MA.
• 23: Phokion G. Kolaitis , Moshe Y. Vardi, Conjunctive-query containment and constraint satisfaction, Journal of Computer and System Sciences, v.61 n.2, p.302-332, Oct. 2000 [doi>10.1006/jcss.2000.1713]
• 24: Kolaitis, P. G. 1993. A tutorial on finite model theory (abstract). In Proceedings of the 8th IEEE Symposium on Logic in Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 122.
• 25: Leonid Libkin, Elements Of Finite Model Theory (Texts in Theoretical Computer Science. An Eatcs Series), SpringerVerlag, 2004
• 26: Lyndon, R. 1959. Properties preserved under homomorphism. Pacific J. Math. 9, 129--142.
• 27: Jaroslav Nešetřil , Patrice Ossona de Mendez, Tree-depth, subgraph coloring and homomorphism bounds, European Journal of Combinatorics, v.27 n.6, p.1022-1041, August 2006 [doi>10.1016/j.ejc.2005.01.010]
• 28: Jaroslav Nešetřil , Patrice Ossona de Mendez, Grad and classes with bounded expansion I. Decompositions, European Journal of Combinatorics, v.29 n.3, p.760-776, April, 2008 [doi>10.1016/j.ejc.2006.07.013]
• 29: Jaroslav Nešetřil , Saharon Shelah, On the order of countable graphs, European Journal of Combinatorics, v.24 n.6, p.649-663, August 2003 [doi>10.1016/S0195-6698(03)00064-7]
• 30: Eric Barry Rosen, Finite model theory and finite variable logics, University of Pennsylvania, Philadelphia, PA, 1996
• 31: Rosen, E. 2002. Some aspects of model theory and finite structures. Bull. Symbolic Logic 8, 380--403.
• 32: Eric Rosen , Scott Weinstein, Preservation Theorems in Finite Model Theory, Selected Papers from the International Workshop on Logical and Computational Complexity, p.480-502, October 13-16, 1994
• 33: Benjamin Rossman, Existential Positive Types and Preservation under Homomorphisisms, Proceedings of the 20th Annual IEEE Symposium on Logic in Computer Science, p.467-476, June 26-29, 2005 [doi>10.1109/LICS.2005.16]
• 34: Alexei P. Stolboushkin, Finitely Monotone Properties, Proceedings of the 10th Annual IEEE Symposium on Logic in Computer Science, p.324, June 26-29, 1995
• 35: Tait, W. 1959. A counterexample to a conjecture of Scott and Suppes. J. Symb. Logic 24, 15--16.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Model theory

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

Keywords:
Finite model theory, conjunctive queries, first-order logic, homomorphisms, preservation theorems, quantifier-rank, tree-depth