{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T00:28:21Z","timestamp":1778113701753,"version":"3.51.4"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2019,8,16]],"date-time":"2019-08-16T00:00:00Z","timestamp":1565913600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,8,16]],"date-time":"2019-08-16T00:00:00Z","timestamp":1565913600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001736","name":"German-Israeli Foundation for Scientific Research and Development","doi-asserted-by":"publisher","award":["I-2436-407.6\/2016"],"award-info":[{"award-number":["I-2436-407.6\/2016"]}],"id":[{"id":"10.13039\/501100001736","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["W1255-N23"],"award-info":[{"award-number":["W1255-N23"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["P25207-N23"],"award-info":[{"award-number":["P25207-N23"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["P25518-N23"],"award-info":[{"award-number":["P25518-N23"]}],"id":[{"id":"10.13039\/501100002428","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":[[2020,7]]},"DOI":"10.1007\/s00224-019-09937-9","type":"journal-article","created":{"date-parts":[[2019,8,16]],"date-time":"2019-08-16T01:02:34Z","timestamp":1565917354000},"page":"828-860","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Enumeration Complexity of Conjunctive Queries with Functional Dependencies"],"prefix":"10.1007","volume":"64","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0673-5510","authenticated-orcid":false,"given":"Nofar","family":"Carmeli","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Markus","family":"Kr\u00f6ll","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,8,16]]},"reference":[{"key":"9937_CR1","doi-asserted-by":"crossref","unstructured":"Abboud, A., Williams, V.V.: Popular conjectures imply strong lower bounds for dynamic problems. In: 2014 IEEE 55Th Annual Symposium on Foundations of Computer Science (FOCS), pp. 434\u2013443. IEEE (2014)","DOI":"10.1109\/FOCS.2014.53"},{"key":"9937_CR2","unstructured":"Arapinis, M., Figueira, D., Gaboardi, M.: Sensitivity of counting queries. In: 43Rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, pp. 120:1\u2013120:13. Rome (2016)"},{"key":"9937_CR3","doi-asserted-by":"crossref","unstructured":"Bagan, G., Durand, A., Grandjean, E.: On acyclic conjunctive queries and constant delay enumeration. In: International Workshop on Computer Science Logic, pp. 208\u2013222. Springer (2007)","DOI":"10.1007\/978-3-540-74915-8_18"},{"issue":"3","key":"9937_CR4","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1145\/2402.322389","volume":"30","author":"C Beeri","year":"1983","unstructured":"Beeri, C., Fagin, R., Maier, D., Yannakakis, M.: On the desirability of acyclic database schemes. J. ACM 30(3), 479\u2013513 (1983). \nhttps:\/\/doi.org\/10.1145\/2402.322389","journal-title":"J. ACM"},{"key":"9937_CR5","unstructured":"Berkholz, C., Keppeler, J., Schweikardt, N.: Answering conjunctive queries under updates. In: Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2017, pp. 303\u2013318. Chicago, May 14-19, 2017 (2017)"},{"key":"9937_CR6","unstructured":"Brault-Baron, J.: De La Pertinence De L\u00e9num\u00e9ration: Complexit\u00e9en Logiques Propositionnelle Et Du Premier Ordre. Ph.D. thesis, Universit\u00e9 de Caen (2013)"},{"issue":"12","key":"9937_CR7","first-page":"1231","volume":"7","author":"Y Cao","year":"2014","unstructured":"Cao, Y., Fan, W., Wo, T., Yu, W.: Bounded conjunctive queries. PVLDB 7(12), 1231\u20131242 (2014)","journal-title":"PVLDB"},{"key":"9937_CR8","doi-asserted-by":"publisher","unstructured":"Capelli, F., Strozecki, Y.: Incremental delay enumeration: Space and time. Discrete Applied Mathematics. \nhttps:\/\/doi.org\/10.1016\/j.dam.2018.06.038\n\n (2018)","DOI":"10.1016\/j.dam.2018.06.038"},{"key":"9937_CR9","doi-asserted-by":"publisher","unstructured":"Carmeli, N., Kr\u00f6ll, M.: Enumeration complexity of conjunctive queries with functional dependencies. In: Kimelfeld, B., Amsterdamer, Y. (eds.) 21st International Conference on Database Theory (ICDT 2018), Leibniz International Proceedings in Informatics (LIPIcs), vol. 98, pp 11:1\u201311:17. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2018). \nhttps:\/\/doi.org\/10.4230\/LIPIcs.ICDT.2018.11\n\n. \nhttp:\/\/drops.dagstuhl.de\/opus\/volltexte\/2018\/8598","DOI":"10.4230\/LIPIcs.ICDT.2018.11"},{"key":"9937_CR10","doi-asserted-by":"crossref","unstructured":"Creignou, N., Kr\u00f6ll, M., Pichler, R., Skritek, S., Vollmer, H.: On the complexity of hard enumeration problems. In: Language and Automata Theory and Applications - 11Th International Conference, LATA 2017, pp. 183\u2013195. Ume\u00e5 (2017)","DOI":"10.1007\/978-3-319-53733-7_13"},{"key":"9937_CR11","doi-asserted-by":"crossref","unstructured":"Durand, A., Schweikardt, N., Segoufin, L.: Enumerating answers to first-order queries over databases of low degree. In: Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS \u201914, pp. 121\u2013131 (2014)","DOI":"10.1145\/2594538.2594539"},{"issue":"6","key":"9937_CR12","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":"9937_CR13","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/BF02127798","volume":"16","author":"E Grandjean","year":"1996","unstructured":"Grandjean, E.: Sorting, linear time and the satisfiability problem. Ann. Math. Artif. Intell. 16, 183\u2013236 (1996). \nhttps:\/\/doi.org\/10.1007\/BF02127798","journal-title":"Ann. Math. Artif. Intell."},{"key":"9937_CR14","doi-asserted-by":"publisher","unstructured":"Kimelfeld, B.: A dichotomy in the complexity of deletion propagation with functional dependencies. In: Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS \u201912, pp 191\u2013202. ACM, New York (2012). \nhttps:\/\/doi.org\/10.1145\/2213556.2213584","DOI":"10.1145\/2213556.2213584"},{"key":"9937_CR15","doi-asserted-by":"publisher","unstructured":"Le Gall, F.: Powers of tensors and fast matrix multiplication. In: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ISSAC \u201914, pp 296\u2013303. ACM, New York (2014). \nhttps:\/\/doi.org\/10.1145\/2608628.2608664","DOI":"10.1145\/2608628.2608664"},{"key":"9937_CR16","unstructured":"Lincoln, A., Williams, V.V., Williams, R.R.: Tight hardness for shortest cycles and paths in sparse graphs. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pp. 1236\u20131252. New Orleans, January 7-10, 2018 (2018)"},{"issue":"3","key":"9937_CR17","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1006\/jcss.1999.1626","volume":"58","author":"CH Papadimitriou","year":"1999","unstructured":"Papadimitriou, C.H., Yannakakis, M.: On the complexity of database queries. J. Comput. Syst. Sci. 58(3), 407\u2013427 (1999)","journal-title":"J. Comput. Syst. Sci."},{"key":"9937_CR18","unstructured":"Segoufin, L., Vigny, A.: Constant delay enumeration for FO queries over databases with local bounded expansion. In: 20Th International Conference on Database Theory, ICDT 2017, pp. 20:1\u201320:16. Venice (2017)"},{"key":"9937_CR19","doi-asserted-by":"crossref","unstructured":"Williams, V.V., Williams, R.: Subcubic Equivalences between Path, Matrix and Triangle Problems. In: 51Th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, pp. 645\u2013654. Las Vegas (2010)","DOI":"10.1109\/FOCS.2010.67"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-019-09937-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-019-09937-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-019-09937-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,14]],"date-time":"2020-08-14T23:28:53Z","timestamp":1597447733000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-019-09937-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8,16]]},"references-count":19,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,7]]}},"alternative-id":["9937"],"URL":"https:\/\/doi.org\/10.1007\/s00224-019-09937-9","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,8,16]]},"assertion":[{"value":"16 August 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}