{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T05:05:33Z","timestamp":1737435933802,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540414568"},{"type":"electronic","value":"9783540445036"}],"license":[{"start":{"date-parts":[[2001,1,1]],"date-time":"2001-01-01T00:00:00Z","timestamp":978307200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44503-x_2","type":"book-chapter","created":{"date-parts":[[2007,8,12]],"date-time":"2007-08-12T04:25:32Z","timestamp":1186892732000},"page":"22-38","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Query Evaluation via Tree-Decompositions"],"prefix":"10.1007","author":[{"given":"J\u00f6rg","family":"Flum","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Markus","family":"Frick","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Grohe","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,10,12]]},"reference":[{"key":"2_CR1","unstructured":"S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995."},{"key":"2_CR2","unstructured":"A.V. Aho, J.E. Hopcroft, and J.D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974."},{"key":"2_CR3","unstructured":"H. Andr\u00e9ka, J. van Benthem, and I. N\u00e9meti. Modal languages and bounded fragments of first-order logic, 1996. ILLC Research Report ML-96-03, University of Amsterdam."},{"key":"2_CR4","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S. Arnborg","year":"1991","unstructured":"S. Arnborg, J. Lagergren, and D. Seese. Easy problems for tree-decomposable graphs. Journal of Algorithms, 12:308\u2013340, 1991.","journal-title":"Journal of Algorithms"},{"key":"2_CR5","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"H.L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25:1305\u20131317, 1996.","journal-title":"SIAM Journal on Computing"},{"key":"2_CR6","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1007\/3-540-62222-5_36","volume-title":"Proceedings of the 5th International Conference on Database Theory","author":"Ch. Chekuri","year":"1997","unstructured":"Ch. Chekuri and A. Rajaraman. Conjunctive query containment revisited. In Ph. Kolaitis and F. Afrati, editors, Proceedings of the 5th International Conference on Database Theory, volume 1186 of Lecture Notes in Computer Science, pages 56\u201370. Springer-Verlag, 1997."},{"key":"2_CR7","doi-asserted-by":"crossref","unstructured":"B. Courcelle. Graph rewriting: An algebraic and logic approach. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume 2, pages 194\u2013242. Elsevier Science Publishers, 1990.","DOI":"10.1016\/B978-0-444-88074-1.50010-X"},{"key":"2_CR8","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0304-3975(93)90064-Z","volume":"103","author":"B. Courcelle","year":"1993","unstructured":"B. Courcelle and M. Mosbah. Monadic second-order evaluations on tree-decomposable graphs. Theoretical Computer Science, 103:49\u201382, 1993.","journal-title":"Theoretical Computer Science"},{"key":"2_CR9","doi-asserted-by":"crossref","unstructured":"T. Feder and M.Y. Vardi. Monotone monadic SNP and constraint satisfaction. In Proceedings of the 25th ACM Symposium on Theory of Computing, pages 612\u2013622, 1993.","DOI":"10.1145\/167088.167245"},{"key":"2_CR10","unstructured":"J. Flum and M. Frick and M. Grohe. Query evaluation via tree-decompositions. Full version of this paper, available at http:\/\/www.math.uic.edu\/~grohe\/pub.html ."},{"key":"2_CR11","unstructured":"G. Gottlob, E. Gr\u00e4del, and H. Veith. Datalog lite: Temporal versus deductive reasoning in verification. Technical Report DBAI-TR-98-22, Technische Universit\u00e4tWien, 1998."},{"key":"2_CR12","doi-asserted-by":"crossref","unstructured":"G. Gottlob, N. Leone, and F. Scarcello. The complexity of acyclic conjunctive queries. In Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, pages 706\u2013715, 1998.","DOI":"10.1109\/SFCS.1998.743521"},{"key":"2_CR13","doi-asserted-by":"crossref","unstructured":"G. Gottlob, N. Leone, and F. Scarcello. Hypertree decompositions and tractable queries. In Proceedings of the 18th ACM Symposium on Principles of Database Systems, pages 21\u201332, 1999.","DOI":"10.1145\/303976.303979"},{"key":"2_CR14","unstructured":"G. Gottlob, N. Leone, and F. Scarcello. A Comparison of Structural CSP Decomposition Methods. In Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, pages 394\u2013399, 1999."},{"key":"2_CR15","doi-asserted-by":"crossref","unstructured":"Ph.G. Kolaitis and M.Y. Vardi. Conjunctive-query containment and constraint satisfaction. In Proceedings of the 17th ACMSymposium on Principles of Database Systems, pages 205\u2013213, 1998.","DOI":"10.1145\/275487.275511"},{"key":"2_CR16","doi-asserted-by":"crossref","unstructured":"J. Makowsky. Model theory in computer science:An appetizer. In S. Abramsky, D.M. Gabbay, and T.S.E. Maibaum, editors, Handbook of Logic in Computer Science, volume 1, chapter 6. Oxford University Press, 1992.","DOI":"10.1093\/oso\/9780198537359.003.0006"},{"key":"2_CR17","unstructured":"L.J. Stockmeyer. The Complexity of Decision Problems in Automata Theory. PhD thesis, Department of Electrical Engineering, MIT, 1974."},{"key":"2_CR18","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1137\/0213035","volume":"13","author":"R.E. Tarjan","year":"1984","unstructured":"R.E. Tarjan and M. Yannakakis. Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM Journal on Computing, 13:566\u2013579, 1984.","journal-title":"SIAM Journal on Computing"},{"key":"2_CR19","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/BF01691346","volume":"2","author":"J.W. Thatcher","year":"1968","unstructured":"J.W. Thatcher and J.B. Wright. Generalized finite automata with an application to a decision problem of second order logic. Math. Syst. Theory, 2:57\u201382, 1968.","journal-title":"Math. Syst. Theory"},{"key":"2_CR20","unstructured":"C. Thomassen. Embeddings and minors. In R. Graham, M. Gr\u00f6tschel, and L. Lov\u00e1sz, editors, Handbook of Combinatorics, volume 1, chapter 5, pages 301\u2013349. Elsevier, 1995."},{"key":"2_CR21","doi-asserted-by":"crossref","unstructured":"P. van Emde Boas. Machine models and simulations. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume 1, pages 1\u201366. Elsevier Science Publishers, 1990.","DOI":"10.1016\/B978-0-444-88071-0.50006-0"},{"key":"2_CR22","doi-asserted-by":"crossref","unstructured":"M.Y. Vardi. The complexity of relational query languages. In Proceedings of the 14th ACM Symposium on Theory of Computing, pages 137\u2013146, 1982.","DOI":"10.1145\/800070.802186"},{"key":"2_CR23","doi-asserted-by":"crossref","unstructured":"M.Y. Vardi. On the complexity of bounded-variable queries. In Proceedings of the 14th ACM Symposium on Principles of Database Systems, pages 266\u2013276, 1995.","DOI":"10.1145\/212433.212474"},{"key":"2_CR24","unstructured":"M. Yannakakis. Algorithms for acyclic database schemes. In 7th International Conference on Very Large Data Bases, pages 82\u201394, 1981."}],"container-title":["Lecture Notes in Computer Science","Database Theory \u2014 ICDT 2001"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44503-X_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T08:37:26Z","timestamp":1737362246000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44503-X_2"}},"subtitle":["Extended Abstract"],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540414568","9783540445036"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-44503-x_2","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]},"assertion":[{"value":"12 October 2001","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}