{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T01:14:46Z","timestamp":1772846086281,"version":"3.50.1"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,6,7]],"date-time":"2016-06-07T00:00:00Z","timestamp":1465257600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2016,6,7]],"date-time":"2016-06-07T00:00:00Z","timestamp":1465257600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-1247469"],"award-info":[{"award-number":["IIS-1247469"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-0911036"],"award-info":[{"award-number":["IIS-0911036"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["MoDas, agreement 291071"],"award-info":[{"award-number":["MoDas, agreement 291071"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006245","name":"Ministry of Science and Technology, Israel","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100006245","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2017,7]]},"DOI":"10.1007\/s00224-016-9684-2","type":"journal-article","created":{"date-parts":[[2016,6,7]],"date-time":"2016-06-07T05:49:57Z","timestamp":1465278597000},"page":"2-30","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Answering Conjunctive Queries with Inequalities"],"prefix":"10.1007","volume":"61","author":[{"given":"Paraschos","family":"Koutris","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tova","family":"Milo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sudeepa","family":"Roy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dan","family":"Suciu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,6,7]]},"reference":[{"key":"9684_CR1","unstructured":"Abiteboul, S., Hull, R., Vianu, V.: Foundations of databases Addison-Wesley, 1995."},{"key":"9684_CR2","doi-asserted-by":"crossref","unstructured":"Afrati, F., Li, C., Mitra, P.: Answering Queries Using Views with Arithmetic Comparisons. PODS, 209\u2013220 (2002).","DOI":"10.1145\/543613.543641"},{"issue":"3","key":"9684_CR3","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/BF02523189","volume":"17","author":"N Alon","year":"1997","unstructured":"Alon, N., Yuster, R., Zwick, U.: Finding and counting given length cycles. Algorithmica. 17 (3), 209\u2013223 (1997).","journal-title":"Algorithmica"},{"key":"9684_CR4","doi-asserted-by":"crossref","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color Coding. Encyclopedia of Algorithms. Edited by: Kao, M.Y. Springer (2008).","DOI":"10.1007\/978-0-387-30162-4_76"},{"key":"9684_CR5","doi-asserted-by":"crossref","unstructured":"Atserias, A., Grohe, M., Marx, D.: Size bounds and query plans for relational joins. FOCS 739\u2013748, 2008.","DOI":"10.1109\/FOCS.2008.43"},{"issue":"2","key":"9684_CR6","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/S0304-3975(99)00220-0","volume":"239","author":"C Chekuri","year":"2000","unstructured":"Chekuri, C., Rajaraman, A.: Conjunctive query containment revisited. Theor. Comput. Sci. 239 (2), 211\u2013229 (2000).","journal-title":"Theor. Comput. Sci"},{"key":"9684_CR7","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/j.tcs.2012.10.046","volume":"472","author":"M Demange","year":"2013","unstructured":"Demange, M., De Werra, D.: On some coloring problems in grids. Theor. Comput. Sci. 472, 9\u201327 (2013).","journal-title":"Theor. Comput. Sci"},{"key":"9684_CR8","unstructured":"Durand, A., Grandjean, E.: The complexity of acyclic conjunctive queries revisited coRR abs\/cs\/0605008, 2006."},{"issue":"6","key":"9684_CR9","doi-asserted-by":"publisher","first-page":"716","DOI":"10.1145\/602220.602222","volume":"49","author":"J Flum","year":"2002","unstructured":"Flum, J., Frick, M., Grohe, M.: Query evaluation via tree-decompositions. J. ACM. 49 (6), 716\u2013752 (2002).","journal-title":"J. ACM"},{"key":"9684_CR10","doi-asserted-by":"crossref","unstructured":"Gottlob, G., Leone, N., Scarcello, F.: Hypertree Decompositions and Tractable Queries. PODS, 21\u201332 (1999).","DOI":"10.1145\/303976.303979"},{"key":"9684_CR11","volume-title":"On the Universal Relation. Technical Report","author":"M Graham","year":"1979","unstructured":"Graham, M.: On the Universal Relation. Technical Report. University of Toronto, Ontario (1979)."},{"key":"9684_CR12","doi-asserted-by":"crossref","unstructured":"Grohe, M., Marx, D.: Constraint Solving via Fractional Edge Covers. SODA, 289\u2013298 (2006).","DOI":"10.1145\/1109557.1109590"},{"issue":"2","key":"9684_CR13","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/S0166-218X(96)00085-6","volume":"75","author":"K Jansen","year":"1997","unstructured":"Jansen, K., Scheffler, P.: Generalized coloring for tree-like graphs. Discret. Appl. Math. 75 (2), 135\u2013155 (1997).","journal-title":"Discret. Appl. Math."},{"issue":"13","key":"9684_CR14","first-page":"2074","volume":"8","author":"Z Khayyat","year":"2015","unstructured":"Khayyat, Z., Lucia, W., Singh, M., Ouzzani, M., Papotti, P., Quian\u00e9-Ruiz, J., Tang, N., Kalnis, P.: Lightning fast and space efficient inequality joins. PVLDB. 8 (13), 2074\u20132085 (2015). \n                    http:\/\/www.vldb.org\/pvldb\/vol8\/p2074-khayyat.pdf\n                    \n                  .","journal-title":"PVLDB"},{"issue":"1","key":"9684_CR15","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1145\/42267.42273","volume":"35","author":"A Klug","year":"1988","unstructured":"Klug, A.: On conjunctive queries containing inequalities. J. ACM. 35 (1), 146\u2013160 (1988).","journal-title":"J. ACM"},{"key":"9684_CR16","doi-asserted-by":"crossref","unstructured":"Kolaitis, P.G., Martin, D.L., Thakur, M.N.: On the Complexity of the Containment Problem for Conjunctive Queries with Built-In Predicates. PODS, 197\u2013204 (1998).","DOI":"10.1145\/275487.275510"},{"key":"9684_CR17","unstructured":"Koutris, P., Milo, T., Roy, S., Suciu, D.: Answering Conjunctive Queries with Inequalities. ICDT, 76\u201393 (2015)."},{"issue":"1","key":"9684_CR18","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1006\/jcss.1997.1455","volume":"54","author":"R van der Meyden","year":"1997","unstructured":"van der Meyden, R.: The complexity of querying indefinite data about linearly ordered domains. J. Comput. Syst. Sci. 54 (1), 113\u2013135 (1997). doi:\n                    http:\/\/dx.doi.org\/10.1006\/jcss.1997.1455\n                    \n                  .","journal-title":"J. Comput. Syst. Sci"},{"key":"9684_CR19","unstructured":"Monien, B.: How to Find Long Paths Efficiently. Analysis and Design of Algorithms for Combinatorial Problems, North-Holland Mathematics Studies, vol. 109, pp. 239\u2013254. North-Holland. Edited by: Ausiello, G., Lucertini, M. (1985)."},{"key":"9684_CR20","doi-asserted-by":"crossref","unstructured":"Ngo, H.Q., Porat, E., R\u00e9, C., Rudra, A.: Worst-Case Optimal Join Algorithms: [Extended Abstract]. PODS, 37\u201348 (2012).","DOI":"10.1145\/2213556.2213565"},{"key":"9684_CR21","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H., Yannakakis, M.: On the Complexity of Database Queries. PODS, 12\u201319 (1997).","DOI":"10.1145\/263661.263664"},{"issue":"1","key":"9684_CR22","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","volume":"36","author":"N Robertson","year":"1984","unstructured":"Robertson, N., Seymour, P.: Graph minors. iii. planar tree-width. J. Comb. Theory B. 36 (1), 49\u201364 (1984).","journal-title":"J. Comb. Theory B"},{"key":"9684_CR23","unstructured":"Veldhuizen, T.L.: Triejoin: a Simple, Worst-Case Optimal Join Algorithm. ICDT, 96\u2013106 (2014)."},{"key":"9684_CR24","unstructured":"Yannakakis, M.: Algorithms for Acyclic Database Schemes. VLDB, 82\u201394 (1981)."},{"key":"9684_CR25","unstructured":"Yu, C., Ozsoyoglu, M.Z.: An Algorithm for Tree-Query Membership of a Distributed Query. COMPSAC, 306\u2013312 (1979)."},{"issue":"2","key":"9684_CR26","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1137\/S0895480194274133","volume":"10","author":"R Yuster","year":"1997","unstructured":"Yuster, R., Zwick, U.: Finding even cycles even faster. SIAM J. Discrete Math. 10 (2), 209\u2013222 (1997).","journal-title":"SIAM J. Discrete Math."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-016-9684-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9684-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9684-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9684-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T05:37:06Z","timestamp":1589693826000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-016-9684-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,7]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,7]]}},"alternative-id":["9684"],"URL":"https:\/\/doi.org\/10.1007\/s00224-016-9684-2","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,6,7]]},"assertion":[{"value":"7 June 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}