skip to main content
10.1145/1055558.1055602acmconferencesArticle/Chapter ViewAbstractPublication PagespodsConference Proceedingsconference-collections
Article

On preservation under homomorphisms and unions of conjunctive queries

Published: 14 June 2004 Publication History

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 existential positive formulas are the only first-order formulas (up to logical equivalence) that are preserved under homomorphisms on all structures, finite and infinite. It is long-standing open problem in finite model theory, however, to determine whether the same homomorphism-preservation result holds in the finite, that is, whether every first-order formula preserved under homomorphisms on finite structures is logically equivalent to an existential positive formula on finite structures. In this paper, we show that the homomorphism-preservation theorem holds for several large 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.

References

[1]
S. Abiteboul, R. Hull, and V. Vianu, Foundations of Databases. Addison-Wesley, 1995.
[2]
M. Ajtai and Y. Gurevich. Monotone versus positive, Journal of the ACM, 34:1004--1015, 1987.
[3]
M. Ajtai and Y. Gurevich. Datalog vs first-order logic. J. of Computer and System Sciences, 49:562--588, 1994.
[4]
N. Alechina and Y. Gurevich. Syntax vs semantics on finite structures. In J. Mycielski, G. Rozenberg, and A. Salomaa, editors, Structures in Logic and Computer Science, volume 1261 of LNCS, pages 14--33. Springer, 1997.
[5]
A. K. Chandra and P. M. Merlin. Optimal implementation of conjunctive queries in relational databases. In Proc. 9th ACM Symp. on Theory of Computing, pages 77--90, 1977.
[6]
B. Courcelle, J. Engelfriet, and G. Rozenberg. Handle rewriting hypergraph grammars. Journal of Computer and System Sciences, 46:218--270, 1993.
[7]
V. Dalmau, Ph. G. Kolaitis, and M. Y. Vardi. Constraint satisfaction, bounded treewidth, and finite variable logics. In 8th International Conference on Principles and Practice of Constraint Programming - CP 2002, volume 2470 of Lecture Notes in Computer Science, pages 310--326. Springer, 2002.
[8]
R. Dechter and J. Pearl. Tree clustering for constraint networks. Artificial Intelligence, pages 353--366, 1989.
[9]
R. Diestel. Graph Theory. Springer, 1997.
[10]
R. G. Downey and M. R. Fellows. Parametrized Complexity. Springer-Verlag, 1999.
[11]
D. Epstein. Diameter and treewidth in minor-closed graph families. Algorithmica, 27:275--291, 2000.
[12]
P. Erdos and R. Rado. Intersection theorems for systems of sets. J. of London Mathematical Society, 35:85--90, 1960.
[13]
R. Fagin, P. G. Kolaitis, and L. Popa. Data Exchange: Getting to the Core. In Proc. 22nd ACM Symposium on Principles of Database Systems, pages 90--101, 2003.
[14]
T. Feder and M. Y. Vardi. Homomorphism closed vs existential positive. In Proc. of the 18th IEEE Symp. on Logic in Computer Science, pages 311--320, 2003.
[15]
M. Frick and M. Grohe. Deciding first-order properties of locally tree-decomposable functions. Journal of the Association for Computing Machinery, 48:1184--2006, 2000.
[16]
H. Gaifman. On local and nonlocal properties. In J. Stern, editor, Logic Colloquium '81, pages 105--135. North Holland, 1982.
[17]
R. L. Graham, B. L. Rothschild, and J. H. Spencer. Ramsey Theory. Wiley, 1980.
[18]
M. Grohe. 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, 2003.
[19]
M. Grohe, J. Flum, and M Frick. Query evaluation via tree-decompositions. Journal of the ACM, 49:716--752, 2002.
[20]
M. Grohe, T. Schwentick, and Segoufin. When is the evaluation of conjunctive queries tractable? In Proc. 32nd ACM Symp. on Theory of Computing, pages 657--666, 2001.
[21]
Y. Gurevich. Toward logic tailored for computational complexity. In M. Richter et al., editors, Computation and Proof Theory, pages 175--216. Springer Lecture Notes in Mathematics, 1984.
[22]
Y. Gurevich. On finite model theory. In S. R. Buss and P. J. Scott, editors, Feasible Mathematics, pages 211--219. Birkhäuser, 1990.
[23]
P. Hell and J. Nesetril. The core of a graph. Discrete Math., 109:117--126, 1992.
[24]
W. Hodges. Model Theory. Cambridge University Press, 1993.
[25]
Ph. G. Kolaitis and M. Y Vardi. On the expressive power of Datalog: Tools and a case study. Journal of Computer and System Sciences, 51:110--134, 1995.
[26]
Ph. G. Kolaitis and M. Y Vardi. Conjunctive query containment and constraint satisfaction. Journal of Computer and System Sciences, 61:302--332, 2000.
[27]
M. Kreidler and D. Seese. Monadic NP and graph minors. In CSL'98: Proc. of the Annual Conference of the European Association for Computer Science Logic, volume 1584 of LNCS, pages 126--141. Springer, 1999.
[28]
N. Robertson and P. D. Seymour. Graph minors V. Excluding a planar graph. Journal of Combinatorial Theory, Series B, 41:92--11, 1986.
[29]
E. Rosen. Some aspects of model theory and finite structures. Bulletin of Symbolic Logic, 8:380--403, 2002.
[30]
Y. Sagiv and M. Yannakakis. Equivalence between relational expressions with the union and difference operators. Journal of the Association for Computing Machinery, 27(4):633--655, 1981.
[31]
A. Stolboushkin. Finite monotone properties. In Proc. 10th IEEE Symp. on Logic in Computer Science, pages 324--330, 1995.
[32]
W. W. Tait. A counterexample to a conjecture of Scott and Suppes. Journal of Symbolic Logic, 24:15--16, 1959.
[33]
J. D. Ullman. Bottom-up beats top-down for Datalog. In Proc. 8th ACM Symp. on Principles of Database Systems, pages 140--149, 1989.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PODS '04: Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems
June 2004
350 pages
ISBN:158113858X
DOI:10.1145/1055558
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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 June 2004

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Article

Conference

SIGMOD/PODS04

Acceptance Rates

Overall Acceptance Rate 642 of 2,707 submissions, 24%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 30 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2018)Tarski’s Influence on Computer ScienceThe Lvov-Warsaw School. Past and Present10.1007/978-3-319-65430-0_29(391-404)Online publication date: 7-Mar-2018
  • (2014)First order properties on nowhere dense structuresThe Journal of Symbolic Logic10.2178/jsl/127868220475:3(868-887)Online publication date: 12-Mar-2014
  • (2008)Hypergraph Acyclicity and Extension Preservation TheoremsProceedings of the 2008 23rd Annual IEEE Symposium on Logic in Computer Science10.1109/LICS.2008.12(418-427)Online publication date: 24-Jun-2008
  • (2008)On digraph coloring problems and treewidth dualityEuropean Journal of Combinatorics10.1016/j.ejc.2007.11.00429:4(796-820)Online publication date: 1-May-2008
  • (2008)Structural Properties of Sparse GraphsBuilding Bridges10.1007/978-3-540-85221-6_13(369-426)Online publication date: 2008
  • (2006)On preservation under homomorphisms and unions of conjunctive queriesJournal of the ACM10.1145/1131342.113134453:2(208-237)Online publication date: 1-Mar-2006
  • (2006)The Boundedness Problem for Monadic Universal First-Order LogicProceedings of the 21st Annual IEEE Symposium on Logic in Computer Science10.1109/LICS.2006.50(37-48)Online publication date: 12-Aug-2006
  • (2005)On Digraph Coloring Problems and Treewidth DualityProceedings of the 20th Annual IEEE Symposium on Logic in Computer Science10.1109/LICS.2005.31(106-115)Online publication date: 26-Jun-2005
  • (2005)Existential Positive Types and Preservation under HomomorphisismsProceedings of the 20th Annual IEEE Symposium on Logic in Computer Science10.1109/LICS.2005.16(467-476)Online publication date: 26-Jun-2005
  • (2005)Preservation under extensions on well-behaved finite structuresProceedings of the 32nd international conference on Automata, Languages and Programming10.1007/11523468_116(1437-1449)Online publication date: 11-Jul-2005
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media