article

On preservation under homomorphisms and unions of conjunctive queries

Authors:

Albert Atserias,

Phokion G. KolaitisAuthors Info & Claims

Journal of the ACM (JACM), Volume 53, Issue 2

Pages 208 - 237

https://doi.org/10.1145/1131342.1131344

Published: 01 March 2006 Publication History

Editorial Notes

A corrigendum was issued for this paper on May 20, 2024. You can download the corrigendum from the Supplemental Material section of this citation page.

Abstract

Unions of conjunctive queries, also known as select-project-join-union queries, are the most frequently asked queries in relational database systems. These queries are definable by existential positive first-order formulas and are preserved under homomorphisms. A classical result of mathematical logic asserts that the existential positive formulas are the only first-order formulas (up to logical equivalence) that are preserved under homomorphisms on all structures, finite and infinite. The question of whether the homomorphism-preservation theorem holds for the class of all finite structures resisted solution for a long time. It was eventually shown that, unlike other classical preservation theorems, the homomorphism-preservation theorem does hold in the finite. In this article, we show that the homomorphism-preservation theorem holds also for several restricted classes of finite structures of interest in graph theory and database theory. Specifically, we show that this result holds for all classes of finite structures of bounded degree, all classes of finite structures of bounded treewidth, and, more generally, all classes of finite structures whose cores exclude at least one minor.

Supplemental Material

PDF File - 1131344-corrigendum

Corrigendum to "On preservation under homomorphisms and unions of conjunctive queries" by Atserias et al., Journal of the ACM, Volume 53, Issue 2 (JACM 53:2).

Download
96.05 KB

References

[1]

Abiteboul, S., Hull, R., and Vianu, V. 1995. Foundations of Databases. Addison-Wesley, Reading, MA.

Digital Library

[2]

Ajtai, M., and Gurevich, Y. 1987. Monotone versus positive. J. ACM 34, 1004--1015.

Digital Library

[3]

Ajtai, M., and Gurevich, Y. 1994. Datalog vs first-order logic. J. Comput. Syst. Sci. 49, 562--588.

Digital Library

[4]

Alechina, N., and Gurevich, Y. 1997. Syntax vs semantics on finite structures. In Structures in Logic and Computer Science, J. Mycielski, G. Rozenberg, and A. Salomaa, Eds. Lecture Notes in Computer Science, vol. 1261. Springer-Verlag, New York, 14--33.

Digital Library

[5]

Atserias, A., Dawar, A., and Grohe, M. 2005. Preservation under extensions on well-behaved finite structures. In Automata, Languages and Programming, 32nd International Colloquium, ICALP 2005. Lecture Notes in Computer Science, vol. 3580. Springer-Verlag, New York, 1437--1449.

Digital Library

[6]

Atserias, A., Dawar, A., and Kolaitis, P. G. 2004. On preservation under homomorphisms and unions of conjunctive queries. In Proceedings of the 23rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS). ACM, New York, 319--329.

Digital Library

[7]

Chandra, A., and Merlin, P. 1977. Optimal implementation of conjunctive queries in relational databases. In Proceedings of the 9th ACM Symposium on Theory of Computing. ACM, New York, 77--90.

Digital Library

[8]

Courcelle, B., Engelfriet, J., and Rozenberg, G. 1993. Handle rewriting hypergraph grammars. J. Comput. Syst. Sci. 46, 218--270.

Digital Library

[9]

Dalmau, V., Kolaitis, P. G., and Vardi, M. Y. 2002. Constraint satisfaction, bounded treewidth, and finite variable logics. In Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming---CP 2002. Lecture Notes in Computer Science, vol. 2470. Springer-Verlag, New York, 310--326.

Digital Library

[10]

Dechter, R., and Pearl, J. 1989. Tree clustering for constraint networks. Artif. Intel. 38, 3, 353--366.

Digital Library

[11]

Diestel, R. 1997. Graph Theory. Springer-Verlag, New York.

[12]

Downey, R., and Fellows, M. 1999. Parametrized Complexity. Springer-Verlag, New York.

[13]

Epstein, D. 2000. Diameter and treewidth in minor-closed graph families. Algorithmica 27, 275--291.

[14]

Erdös, P., and Rado, R. 1960. Intersection theorems for systems of sets. J. London Math. Soc. 35, 85--90.

[15]

Fagin, R., Kolaitis, P. G., and Popa, L. 2003. Data exchange: Getting to the core. In Proceedings of the 22nd ACM Symposium on Principles of Database Systems. ACM, New York, 90--101.

Digital Library

[16]

Feder, T., and Vardi, M. 2003. Homomorphism closed vs existential positive. In Proceedings of the 18th IEEE Symposium on Logic in Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 311--320.

Digital Library

[17]

Frick, M., and Grohe, M. 2000. Deciding first-order properties of locally tree-decomposable functions. J. ACM 48, 1184--2006.

Digital Library

[18]

Gaifman, H. 1982. On local and nonlocal properties. In Logic Colloquium '81, J. Stern, Ed. North Holland, Amsterdam, The Netherlands, 105--135.

[19]

Graham, R. L., Rothschild, B. L., and Spencer, J. H. 1980. Ramsey Theory. Wiley, New York.

[20]

Grohe, M. 2003. The complexity of homomorphism and constraint satisfaction problems seen from the other side. In Proceedings of the 44th IEEE Symposium on Foundations of Computer Science---FOCS 2003.

Digital Library

[21]

Grohe, M., Flum, J., and Frick, M. 2002. Query evaluation via tree-decompositions. J. ACM 49, 716--752.

Digital Library

[22]

Grohe, M., Schwentick, T., and Segoufin, L. 2001. When is the evaluation of conjunctive queries tractable? In Proceedings of the 32nd ACM Symposium on Theory of Computing. ACM, New York, 657--666.

Digital Library

[23]

Gurevich, Y. 1984. Toward logic tailored for computational complexity. In Computation and Proof Theory, M. Richter et al., Eds. Lecture Notes in Mathematics. Springer-Verlag, New York, 175--216.

[24]

Gurevich, Y. 1990. On finite model theory. In Feasible Mathematics, S. Buss and P. Scott, Eds. Birkhäuser, 211--219.

[25]

Hell, P., and Nesetril, J. 1992. The core of a graph. Discrete Mathematics 109, 117--126.

Digital Library

[26]

Hodges, W. 1993. Model Theory. Cambridge University Press, Cambridge, UK.

[27]

Kolaitis, P. G., and Vardi, M. Y. 1995. On the expressive power of Datalog: Tools and a case study. J. Comput. Syst. Sci. 51, 110--134.

Digital Library

[28]

Kolaitis, P. G., and Vardi, M. Y. 2000. Conjunctive query containment and constraint satisfaction. J. Comput. Syst. Sci. 61, 302--332.

Digital Library

[29]

Kreidler, M. 1999. Strukturinformation bei der Beschreibung monadischer NP-Probleme. Shaker-Verlag, New York.

[30]

Kreidler, M., and Seese, D. 1999. Monadic NP and graph minors. In CSL'98: Proceedings of the Annual Conference of the European Association for Computer Science Logic. Lecture Notes in Computer Science, vol. 1584. Springer-Verlag, New York, 126--141.

Digital Library

[31]

Robertson, N., and Seymour, P. 1986. Graph minors. V. Excluding a planar graph. J. Combinat. Theory, Ser. B 41, 92--11.

Digital Library

[32]

Rosen, E. 2002. Some aspects of model theory and finite strucrtures. Bull. Symb. Logic 8, 380--403.

[33]

Rossman, B. 2005. Existential positive types and preservation under homomorphisisms. In Proceedings of the 20th IEEE Symposium on Logic in Computer Science. 467--476.

Digital Library

[34]

Sagiv, Y., and Yannakakis, M. 1981. Equivalence between relational expressions with the union and difference operators. J. ACM 27, 4, 633--655.

Digital Library

[35]

Stolboushkin, A. 1995. Finite monotone properties. In Proceedings of the 10th IEEE Symposium on Logic in Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 324--330.

Digital Library

[36]

Tait, W. W. 1959. A counterexample to a conjecture of Scott and Suppes. J. Symb. Logic 24, 15--16.

[37]

Ullman, J. 1989. Bottom-up beats top-down for Datalog. In Proceedings of the 8th ACM Symposium on Principles of Database Systems. ACM, New York, 140--149.

Digital Library

Cited By

Dawar A(2024)Corrigendum to “Homomorphism preservation on quasi-wide classes” [J. Comput. Syst. Sci. 76 (5) (2010) 324–332]Journal of Computer and System Sciences10.1016/j.jcss.2024.103553145(103553)Online publication date: Nov-2024
https://doi.org/10.1016/j.jcss.2024.103553
Dawar A(2023)Constraint Satisfaction, Graph Isomorphism, and the Pebbling ComonadSamson Abramsky on Logic and Structure in Computer Science and Beyond10.1007/978-3-031-24117-8_18(671-699)Online publication date: 2-Aug-2023
https://doi.org/10.1007/978-3-031-24117-8_18
Lopez A(2022)When Locality Meets PreservationProceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3531130.3532498(1-14)Online publication date: 2-Aug-2022
https://dl.acm.org/doi/10.1145/3531130.3532498
Show More Cited By

Index Terms

On preservation under homomorphisms and unions of conjunctive queries
1. Information systems
  1. Data management systems
    1. Query languages
2. Theory of computation
  1. Logic
    1. Finite Model Theory

Recommendations

Homomorphism preservation theorems

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 ...
On preservation under homomorphisms and unions of conjunctive queries
PODS '04: Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems

Unions of conjunctive queries, also known as select-project-join-union queries, are the most frequently asked queries in relational database systems. These queries are definable by existential positive first-order formulas and are preserved under ...
Efficient approximations of conjunctive queries
PODS '12: Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on Principles of Database Systems

When finding exact answers to a query over a large database is infeasible, it is natural to approximate the query by a more efficient one that comes from a class with good bounds on the complexity of query evaluation. In this paper we study such ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 53, Issue 2

March 2006

99 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/1131342

Issue’s Table of Contents

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 March 2006

Published in JACM Volume 53, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Data Availability

1131344-corrigendum: Corrigendum to "On preservation under homomorphisms and unions of conjunctive queries" by Atserias et al., Journal of the ACM, Volume 53, Issue 2 (JACM 53:2). https://dl.acm.org/doi/10.1145/1131342.1131344#1131344_corrigendum.pdf

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

48
Total Citations
View Citations
937
Total Downloads

Downloads (Last 12 months)21
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Dawar A(2024)Corrigendum to “Homomorphism preservation on quasi-wide classes” [J. Comput. Syst. Sci. 76 (5) (2010) 324–332]Journal of Computer and System Sciences10.1016/j.jcss.2024.103553145(103553)Online publication date: Nov-2024
https://doi.org/10.1016/j.jcss.2024.103553
Dawar A(2023)Constraint Satisfaction, Graph Isomorphism, and the Pebbling ComonadSamson Abramsky on Logic and Structure in Computer Science and Beyond10.1007/978-3-031-24117-8_18(671-699)Online publication date: 2-Aug-2023
https://doi.org/10.1007/978-3-031-24117-8_18
Lopez A(2022)When Locality Meets PreservationProceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3531130.3532498(1-14)Online publication date: 2-Aug-2022
https://dl.acm.org/doi/10.1145/3531130.3532498
Bienvenu MCima GGutiérrez-Basulto VLibkin LBarceló P(2022)LACE: A Logical Approach to Collective Entity ResolutionProceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3517804.3526233(379-391)Online publication date: 12-Jun-2022
https://dl.acm.org/doi/10.1145/3517804.3526233
El-Mahgary SSoisalon-Soininen EOrponen PRönnholm PHyyppä H(2022)OVI-3: A NoSQL visual query system supporting efficient anti-joinsJournal of Intelligent Information Systems10.1007/s10844-022-00742-460:3(777-801)Online publication date: 21-Sep-2022
https://dl.acm.org/doi/10.1007/s10844-022-00742-4
Martinez MSimari G(2022)Explanation-Friendly Query Answering Under UncertaintyReasoning Web. Explainable Artificial Intelligence10.1007/978-3-030-31423-1_2(65-103)Online publication date: 10-Mar-2022
https://dl.acm.org/doi/10.1007/978-3-030-31423-1_2
Dellunde PVidal A(2019)Truth-Preservation under Fuzzy pp-FormulasInternational Journal of Uncertainty, Fuzziness and Knowledge-Based Systems10.1142/S021848851940005127:Supp01(89-105)Online publication date: 5-Nov-2019
https://doi.org/10.1142/S0218488519400051
Pilipczuk MSiebertz SToruńczyk S(2018)On the number of types in sparse graphsProceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3209108.3209178(799-808)Online publication date: 9-Jul-2018
https://dl.acm.org/doi/10.1145/3209108.3209178
Dellunde P(2018)Fuzzy Positive Primitive FormulasModeling Decisions for Artificial Intelligence10.1007/978-3-030-00202-2_13(156-168)Online publication date: 15-Oct-2018
https://dl.acm.org/doi/10.1007/978-3-030-00202-2_13
Abramsky SDawar AWang PAceto LIngólfsdóttir A(2017)The pebbling comonad in finite model theoryProceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science10.5555/3329995.3330064(1-12)Online publication date: 20-Jun-2017
https://dl.acm.org/doi/10.5555/3329995.3330064
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents