{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T04:34:39Z","timestamp":1775709279502,"version":"3.50.1"},"reference-count":35,"publisher":"Elsevier BV","issue":"4","license":[{"start":{"date-parts":[[2003,6,1]],"date-time":"2003-06-01T00:00:00Z","timestamp":1054425600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,8,22]],"date-time":"2013-08-22T00:00:00Z","timestamp":1377129600000},"content-version":"vor","delay-in-days":3735,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Computer and System Sciences"],"published-print":{"date-parts":[[2003,6]]},"DOI":"10.1016\/s0022-0000(03)00030-8","type":"journal-article","created":{"date-parts":[[2003,5,13]],"date-time":"2003-05-13T01:09:12Z","timestamp":1052788152000},"page":"775-808","source":"Crossref","is-referenced-by-count":76,"title":["Robbers, marshals, and guards: game theoretic and logical characterizations of hypertree width"],"prefix":"10.1016","volume":"66","author":[{"given":"Georg","family":"Gottlob","sequence":"first","affiliation":[]},{"given":"Nicola","family":"Leone","sequence":"additional","affiliation":[]},{"given":"Francesco","family":"Scarcello","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0022-0000(03)00030-8_BIB1","doi-asserted-by":"crossref","unstructured":"S. Abiteboul, O.M. Duschka, Complexity of answering queries using materialized views, in: Proceedings of the 17th ACM Symposium on Principles of Database Systems (PODS\u201998), Seattle, Washington, 1998, pp. 254\u2013263.","DOI":"10.1145\/275487.275516"},{"key":"10.1016\/S0022-0000(03)00030-8_BIB2","series-title":"Foundations of Databases","author":"Abiteboul","year":"1995"},{"key":"10.1016\/S0022-0000(03)00030-8_BIB3","unstructured":"I. Adler, Spiele als Hilfsmittel zu Strukturuntersuchungen bei Graphen und Hypergraphen (German), Diploma Thesis, Institut f\u00fcr mathematische Logik und Grundlagen der Informatik, Mathemartischa Fakult\u00e4t, University of Freiburg, Freiburg im Breisgau, Germany, 2002. Available at http:\/\/www.math.uni-freiburg.de\/archiv\/diplom\/isolde_adler.html"},{"key":"10.1016\/S0022-0000(03)00030-8_BIB4","unstructured":"J. Van Benthem, Dynamic bits and pieces, ILLC Research Report, University of Amsterdam, 1997."},{"key":"10.1016\/S0022-0000(03)00030-8_BIB5","doi-asserted-by":"crossref","unstructured":"A.K. Chandra, P.M. Merlin, Optimal implementation of conjunctive queries in relational databases, in: Proceedings of the ACM Symposium on Theory of Computing (STOC\u201977), 1977, pp. 77\u201390.","DOI":"10.1145\/800105.803397"},{"key":"10.1016\/S0022-0000(03)00030-8_BIB6","unstructured":"Ch. Chekuri, A. Rajaraman, Conjunctive query containment revisited, Theoret. Comput. Sci. 239(2) (2000) 211\u2013229. A preliminary version appeared in: Proceedings of ICDT\u201997, Lecture Notes in Computer Science, Vol. 1186, Springer, Berlin, 1997, pp. 56\u201370."},{"key":"10.1016\/S0022-0000(03)00030-8_BIB7","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1016\/0022-0000(93)90004-G","article-title":"Handle-rewriting hypergraph grammars","volume":"46","author":"Courcelle","year":"1993","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0022-0000(03)00030-8_BIB8","unstructured":"R. Dechter, Constraint networks, in: Encyclopedia of Artificial Intelligence, 2nd Edition, Wiley, New York, 1992, pp. 276\u2013285."},{"key":"10.1016\/S0022-0000(03)00030-8_BIB9","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1016\/0004-3702(89)90037-4","article-title":"Tree clustering for constraint networks","volume":"38","author":"Dechter","year":"1989","journal-title":"Artif. Intell."},{"key":"10.1016\/S0022-0000(03)00030-8_BIB10","doi-asserted-by":"crossref","unstructured":"J. Flum, M. Frick, M. Grohe, Query evaluation via tree-decomposition, in: Proceedings of ICDT\u201901, Lecture Notes in Computer Science, Vol. 1973, Springer, Berlin, 2001, pp. 22\u201338.","DOI":"10.1007\/3-540-44503-X_2"},{"issue":"4","key":"10.1016\/S0022-0000(03)00030-8_BIB11","doi-asserted-by":"crossref","first-page":"755","DOI":"10.1145\/4221.4225","article-title":"A sufficient condition for backtrack-bounded search","volume":"32","author":"Freuder","year":"1985","journal-title":"J. ACM"},{"issue":"1","key":"10.1016\/S0022-0000(03)00030-8_BIB12","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1145\/504077.504079","article-title":"Datalog LITE","volume":"3","author":"Gottlob","year":"2002","journal-title":"ACM Trans. Comput. Logic"},{"key":"10.1016\/S0022-0000(03)00030-8_BIB13","unstructured":"G. Gottlob, N. Leone, F. Scarcello, On tractable queries and constraints, in: Proceedings of Database and Expert Systems Applications (DEXA\u201999), Lecture Notes in Computer Science, Vol. 1677, Springer, Florence, August 1999, pp. 1\u201315."},{"key":"10.1016\/S0022-0000(03)00030-8_BIB14","unstructured":"G. Gottlob, N. Leone, F. Scarcello, A comparison of structural CSP decomposition methods, Artif. Intell. 124(2) (2000) 243\u2013282. A preliminary version appeared, in: Proceedings of the 16th International Joint Conference on Artificial Intelligence (IJCAI\u201999), Vol. 1, 1999, pp. 394\u2013399."},{"key":"10.1016\/S0022-0000(03)00030-8_BIB15","unstructured":"G. Gottlob, N. Leone, F. Scarcello, The complexity of acyclic conjunctive queries, J. ACM 48(3) (2000) 431\u2013498. An extended abstract concerning part of this work has been published, in: Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS\u201998), Palo Alto, CA, 1998, pp. 706\u2013715."},{"key":"10.1016\/S0022-0000(03)00030-8_BIB16","unstructured":"G. Gottlob, N. Leone, F. Scarcello, Hypertree decompositions and tractable queries, J. Comput. System Sci. 64(3) (2002) 579\u2013627. An extended abstract concerning part of this work has been published, in: Proceedings of the Eighteenth ACM Symposium on Principles of Database Systems (PODS\u201999), Philadelphia, Pennsylvania, May 1999, pp. 21\u201332."},{"key":"10.1016\/S0022-0000(03)00030-8_BIB17","unstructured":"G. Gottlob, N. Leone, F. Scarcello, Computing LOGCFL certificates, Theoret. Comput. Sci. 270(1\u20132) (2002) 761\u2013777. A preliminary version appeared, in: Proceedings of the 26th International Colloquium on Automata, Languages and Programming (ICALP\u201999), Lecture Notes in Computer Science, Vol. 1644, Springer, Prague, July, 1999, pp. 361\u2013371."},{"key":"10.1016\/S0022-0000(03)00030-8_BIB18","doi-asserted-by":"crossref","unstructured":"G. Gottlob, R. Pichler, Hypergraphs in model checking: acyclicity hypertree-width versus clique-width, in: Proceedings of ICALP 2001, 28th International Colloquium on Automata, Languages and Programming, Crete, Greece, July 8\u201312, 2001, pp. 708\u2013719.","DOI":"10.1007\/3-540-48224-5_58"},{"key":"10.1016\/S0022-0000(03)00030-8_BIB19","doi-asserted-by":"crossref","first-page":"1719","DOI":"10.2307\/2586808","article-title":"On the restraining power of guards","volume":"64","author":"Gr\u00e4del","year":"1999","journal-title":"J. Symbolic Logic"},{"key":"10.1016\/S0022-0000(03)00030-8_BIB20","doi-asserted-by":"crossref","unstructured":"M. Grohe, T. Schwentick, L. Segoufin, When is the evaluation of conjunctive queries tractable? in: Proceedings of the ACM Symposium on Theory of Computing (STOC\u201901), 2001.","DOI":"10.1145\/380752.380867"},{"key":"10.1016\/S0022-0000(03)00030-8_BIB21","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0004-3702(94)90003-5","article-title":"Decomposing constraint satisfaction problems using database techniques","volume":"66","author":"Gyssens","year":"1994","journal-title":"Artif. Intell."},{"key":"10.1016\/S0022-0000(03)00030-8_BIB22","doi-asserted-by":"crossref","unstructured":"M. Gyssens, J. Paredaens, A Decomposition Methodology for Cyclic Databases, in: Advances in Database Theory, Vol. 2, Plenum Press, New York, NY, 1984, pp. 85\u2013122.","DOI":"10.1007\/978-1-4615-9385-0_4"},{"key":"10.1016\/S0022-0000(03)00030-8_BIB23","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1006\/jcss.2000.1713","article-title":"Conjunctive-query containment and constraint satisfaction","volume":"61","author":"Kolaitis","year":"2000","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0022-0000(03)00030-8_BIB24","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1006\/jagm.1998.0965","article-title":"Acyclic hypergraph projections","volume":"30","author":"Lustig","year":"1999","journal-title":"J. Algorithms"},{"key":"10.1016\/S0022-0000(03)00030-8_BIB25","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","article-title":"Graph minors II, Algorithmic aspects of tree-width","volume":"7","author":"Robertson","year":"1986","journal-title":"J. Algorithms"},{"key":"10.1016\/S0022-0000(03)00030-8_BIB26","unstructured":"F. Rossi, C. Petrie, V. Dhar, On the equivalence of constraint satisfaction problems, in: Proceedings of the 9th European Conference on Artificial Intelligence (ECAI\u201990), Stockholm, Sweden, 1990, pp. 550\u2013556."},{"key":"10.1016\/S0022-0000(03)00030-8_BIB27","unstructured":"F. Scarcello, A. Mazzitelli, The hypertree decomposition homepage, http:\/\/wwwinfo.deis.unical.it\/~frank\/Hypertrees\/"},{"key":"10.1016\/S0022-0000(03)00030-8_BIB28","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1006\/jctb.1993.1027","article-title":"Graph searching and a min\u2013max theorem for tree-width","volume":"58","author":"Seymour","year":"1993","journal-title":"J. Combin. Theory Ser. B"},{"key":"10.1016\/S0022-0000(03)00030-8_BIB29","unstructured":"J.D. Ullman, Principles of Database and Knowledge Base Systems, Vol. II, Computer Science Press, Rockville, MD, 1989."},{"issue":"2","key":"10.1016\/S0022-0000(03)00030-8_BIB30","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/S0304-3975(99)00219-4","article-title":"Information integration using logical views","volume":"239","author":"Ullman","year":"2000","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0022-0000(03)00030-8_BIB31","doi-asserted-by":"crossref","unstructured":"M. Vardi, Complexity of relational query languages, in: Proceedings of the 14th ACM Symposium on Theory of Computing (STOC\u201982), 1982, pp. 137\u2013146.","DOI":"10.1145\/800070.802186"},{"key":"10.1016\/S0022-0000(03)00030-8_BIB32","unstructured":"M. Vardi, Constraint satisfaction and database theory, Tutorial at the 19th ACM Symposium on Principles of Database Systems (PODS\u201900). Currently available at: http:\/\/www.cs.rice.edu\/~vardi\/papers\/pods00t.ps.gz."},{"key":"10.1016\/S0022-0000(03)00030-8_BIB33","series-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB\u201981)","first-page":"82","article-title":"Algorithms for acyclic database schemes","author":"Yannakakis","year":"1981"},{"key":"10.1016\/S0022-0000(03)00030-8_BIB34","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0304-3975(92)90148-9","article-title":"Monadic second-order logic of graphs VII","volume":"101","author":"Courcelle","year":"1992","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0022-0000(03)00030-8_BIB35","doi-asserted-by":"crossref","first-page":"470","DOI":"10.1006\/jagm.1994.1022","article-title":"Bounded tree-width and LOGCFL","volume":"16","author":"Wanke","year":"1994","journal-title":"J. Algorithms"}],"container-title":["Journal of Computer and System Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000003000308?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000003000308?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,3,19]],"date-time":"2020-03-19T21:47:56Z","timestamp":1584654476000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0022000003000308"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,6]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2003,6]]}},"alternative-id":["S0022000003000308"],"URL":"https:\/\/doi.org\/10.1016\/s0022-0000(03)00030-8","relation":{},"ISSN":["0022-0000"],"issn-type":[{"value":"0022-0000","type":"print"}],"subject":[],"published":{"date-parts":[[2003,6]]}}}