{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T07:34:09Z","timestamp":1648884849698},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2006,3]]},"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.<\/jats:p>","DOI":"10.1145\/1131342.1131344","type":"journal-article","created":{"date-parts":[[2006,7,25]],"date-time":"2006-07-25T14:14:26Z","timestamp":1153836866000},"page":"208-237","source":"Crossref","is-referenced-by-count":37,"title":["On preservation under homomorphisms and unions of conjunctive queries"],"prefix":"10.1145","volume":"53","author":[{"given":"Albert","family":"Atserias","sequence":"first","affiliation":[{"name":"Universitat Polit\u00e8cnica de Catalunya, Barcelona, Spain"}]},{"given":"Anuj","family":"Dawar","sequence":"additional","affiliation":[{"name":"University of Cambridge Computer Laboratory, Cambridge, U.K."}]},{"given":"Phokion G.","family":"Kolaitis","sequence":"additional","affiliation":[{"name":"IBM Almaden Research Center, San Jose, California"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_1","unstructured":"Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley Reading MA. Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley Reading MA."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/31846.31852"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80071-6"},{"key":"e_1_2_1_4_1","volume-title":"Eds. Lecture Notes in Computer Science","volume":"1261","author":"Alechina N."},{"key":"e_1_2_1_5_1","volume-title":"32nd International Colloquium, ICALP","volume":"3580","author":"Atserias A.","year":"2005"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 23rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS). ACM","author":"Atserias A."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 9th ACM Symposium on Theory of Computing. ACM","author":"Chandra A."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90004-G"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming---CP","volume":"2470","author":"Dalmau V.","year":"2002"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(89)90037-4"},{"key":"e_1_2_1_11_1","volume-title":"Graph Theory","author":"Diestel R."},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Downey R. and Fellows M. 1999. Parametrized Complexity. Springer-Verlag New York. Downey R. and Fellows M. 1999. Parametrized Complexity. Springer-Verlag New York.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/s004530010020","article-title":"Diameter and treewidth in minor-closed graph families","volume":"27","author":"Epstein D.","year":"2000","journal-title":"Algorithmica"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1112\/jlms\/s1-35.1.85","article-title":"Intersection theorems for systems of sets","volume":"35","author":"Erd\u00f6s P.","year":"1960","journal-title":"J. London Math. Soc."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 22nd ACM Symposium on Principles of Database Systems. ACM","author":"Fagin R."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 18th IEEE Symposium on Logic in Computer Science. IEEE Computer Society Press","author":"Feder T."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/504794.504798"},{"key":"e_1_2_1_18_1","volume-title":"Logic Colloquium '81","author":"Gaifman H.","year":"1982"},{"key":"e_1_2_1_19_1","unstructured":"Graham R. L. Rothschild B. L. and Spencer J. H. 1980. Ramsey Theory. Wiley New York. Graham R. L. Rothschild B. L. and Spencer J. H. 1980. Ramsey Theory. Wiley New York."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 44th IEEE Symposium on Foundations of Computer Science---FOCS","author":"Grohe M.","year":"2003"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/602220.602222"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 32nd ACM Symposium on Theory of Computing. ACM","author":"Grohe M."},{"key":"e_1_2_1_23_1","series-title":"Lecture Notes in Mathematics","volume-title":"Toward logic tailored for computational complexity","author":"Gurevich Y."},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Gurevich Y. 1990. On finite model theory. In Feasible Mathematics S. Buss and P. Scott Eds. Birkh\u00e4user 211--219. Gurevich Y. 1990. On finite model theory. In Feasible Mathematics S. Buss and P. Scott Eds. Birkh\u00e4user 211--219.","DOI":"10.1007\/978-1-4612-3466-1_12"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90282-K"},{"key":"e_1_2_1_26_1","volume-title":"Model Theory","author":"Hodges W."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1055"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1713"},{"key":"e_1_2_1_29_1","volume-title":"Strukturinformation bei der Beschreibung monadischer NP-Probleme","author":"Kreidler M."},{"key":"e_1_2_1_30_1","volume-title":"CSL'98: Proceedings of the Annual Conference of the European Association for Computer Science Logic. Lecture Notes in Computer Science","volume":"1584","author":"Kreidler M."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90030-4"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","first-page":"380","DOI":"10.2178\/bsl\/1182353894","article-title":"Some aspects of model theory and finite strucrtures","volume":"8","author":"Rosen E.","year":"2002","journal-title":"Bull. Symb. Logic"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 20th IEEE Symposium on Logic in Computer Science. 467--476","author":"Rossman B.","year":"2005"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322221"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 10th IEEE Symposium on Logic in Computer Science. IEEE Computer Society Press","author":"Stolboushkin A.","year":"1995"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","first-page":"15","DOI":"10.2307\/2964569","article-title":"A counterexample to a conjecture of Scott and Suppes","volume":"24","author":"Tait W. W.","year":"1959","journal-title":"J. Symb. Logic"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 8th ACM Symposium on Principles of Database Systems. ACM","author":"Ullman J.","year":"1989"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1131342.1131344","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,17]],"date-time":"2021-02-17T20:43:17Z","timestamp":1613594597000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1131342.1131344"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,3]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2006,3]]}},"alternative-id":["10.1145\/1131342.1131344"],"URL":"http:\/\/dx.doi.org\/10.1145\/1131342.1131344","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[2006,3]]}}}