{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T13:13:55Z","timestamp":1778073235081,"version":"3.51.4"},"publisher-location":"New York, NY, USA","reference-count":156,"publisher":"ACM","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,5,31]]},"DOI":"10.1145\/3788852.3805597","type":"proceedings-article","created":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T12:24:47Z","timestamp":1778070287000},"page":"20-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Enumeration Theory through the Lens of Database Challenges"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2842-8223","authenticated-orcid":false,"given":"Florent","family":"Capelli","sequence":"first","affiliation":[{"name":"Artois University, Lens, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0673-5510","authenticated-orcid":false,"given":"Nofar","family":"Carmeli","sequence":"additional","affiliation":[{"name":"Inria, LIRMM, University of Montpellier, CNRS, Montpellier, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0770-2235","authenticated-orcid":false,"given":"Alessio","family":"Conte","sequence":"additional","affiliation":[{"name":"University of Pisa, Pisa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7156-1572","authenticated-orcid":false,"given":"Benny","family":"Kimelfeld","sequence":"additional","affiliation":[{"name":"Technion - Israel Institute of Technology & RelationalAI, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1760-122X","authenticated-orcid":false,"given":"Reinhard","family":"Pichler","sequence":"additional","affiliation":[{"name":"TU Wien, Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8342-2177","authenticated-orcid":false,"given":"Nikolaos","family":"Tziavelis","sequence":"additional","affiliation":[{"name":"UC Santa Cruz, Santa Cruz, California, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,5,30]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"SIGMOD Conference. ACM, 627","author":"Agrawal Sanjay","year":"2002","unstructured":"Sanjay Agrawal, Surajit Chaudhuri, and Gautam Das. 2002. DBXplorer: enabling keyword search over relational databases. In SIGMOD Conference. ACM, 627."},{"key":"e_1_3_2_1_2_1","volume-title":"ICDT (LIPIcs","volume":"18","author":"Amarilli Antoine","year":"2024","unstructured":"Antoine Amarilli, Pierre Bourhis, Florent Capelli, and Mika\u00ebl Monet. 2024. Ranked Enumeration for MSO on Trees via Knowledge Compilation. In ICDT (LIPIcs, Vol. 290). 25:1-25:18."},{"key":"e_1_3_2_1_3_1","first-page":"1","article-title":"A Circuit-Based Approach to Efficient Enumeration","volume":"111","author":"Amarilli Antoine","year":"2017","unstructured":"Antoine Amarilli, Pierre Bourhis, Louis Jachiet, and Stefan Mengel. 2017. A Circuit-Based Approach to Efficient Enumeration. In ICALP. 111:1-111:15.","journal-title":"ICALP."},{"key":"e_1_3_2_1_4_1","volume-title":"ICDT (LIPIcs","volume":"19","author":"Amarilli Antoine","year":"2019","unstructured":"Antoine Amarilli, Pierre Bourhis, Stefan Mengel, and Matthias Niewerth. 2019a. Constant-Delay Enumeration for Nondeterministic Document Spanners. In ICDT (LIPIcs, Vol. 127). 22:1-22:19."},{"key":"e_1_3_2_1_5_1","first-page":"89","article-title":"Enumeration on Trees with Tractable Combined Complexity and Efficient Updates","author":"Amarilli Antoine","year":"2019","unstructured":"Antoine Amarilli, Pierre Bourhis, Stefan Mengel, and Matthias Niewerth. 2019b. Enumeration on Trees with Tractable Combined Complexity and Efficient Updates. In PODS. ACM, 89-103.","journal-title":"PODS. ACM"},{"key":"e_1_3_2_1_6_1","volume-title":"Enumerating Regular Languages with Bounded Delay. In 40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023 (LIPIcs","volume":"18","author":"Amarilli Antoine","year":"2023","unstructured":"Antoine Amarilli and Mika\u00ebl Monet. 2023. Enumerating Regular Languages with Bounded Delay. In 40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023 (LIPIcs, Vol. 254). 8:1-8:18."},{"key":"e_1_3_2_1_7_1","volume-title":"Consistent Query Answers in Inconsistent Databases","author":"Arenas Marcelo","unstructured":"Marcelo Arenas, Leopoldo E. Bertossi, and Jan Chomicki. 1999. Consistent Query Answers in Inconsistent Databases. In PODS. ACM Press, 68-79."},{"key":"e_1_3_2_1_8_1","first-page":"1","article-title":"Reverse search for enumeration","volume":"65","author":"Avis David","year":"1996","unstructured":"David Avis and Komei Fukuda. 1996. Reverse search for enumeration. Discrete Appl. Math., Vol. 65, 1-3 (1996), 21-46.","journal-title":"Discrete Appl. Math."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/j.jcss.2019.08.006","article-title":"A trichotomy for regular simple path queries on graphs","volume":"108","author":"Bagan Guillaume","year":"2020","unstructured":"Guillaume Bagan, Angela Bonifati, and Beno^it Groz. 2020. A trichotomy for regular simple path queries on graphs. J. Comput. System Sci., Vol. 108 (2020), 29-48.","journal-title":"J. Comput. System Sci."},{"key":"e_1_3_2_1_10_1","first-page":"208","article-title":"On Acyclic Conjunctive Queries and Constant Delay Enumeration. In CSL (LNCS, Vol. 4646)","author":"Bagan Guillaume","year":"2007","unstructured":"Guillaume Bagan, Arnaud Durand, and Etienne Grandjean. 2007. On Acyclic Conjunctive Queries and Constant Delay Enumeration. In CSL (LNCS, Vol. 4646). Springer, 208-222.","journal-title":"Springer"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1051\/ita:2007046","article-title":"Computing the jth solution of a first-order query","volume":"42","author":"Bagan Guillaume","year":"2008","unstructured":"Guillaume Bagan, Arnaud Durand, Etienne Grandjean, and Fr\u00e9d\u00e9ric Olive. 2008. Computing the jth solution of a first-order query. RAIRO Theor. Informatics Appl., Vol. 42, 1 (2008), 147-164.","journal-title":"RAIRO Theor. Informatics Appl."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"crossref","first-page":"1990","DOI":"10.14778\/2556549.2556579","article-title":"Aggregation and ordering in factorised databases","volume":"6","author":"Bakibayev Nurzhan","year":"2013","unstructured":"Nurzhan Bakibayev, Tom\u00e1\u0161 Ko\u010disk\u00fd, Dan Olteanu, and Jakub Z\u00e1vodn'y. 2013. Aggregation and ordering in factorised databases. Proc. VLDB Endow., Vol. 6, 14 (2013), 1990\u20132001.","journal-title":"Proc. VLDB Endow."},{"key":"e_1_3_2_1_13_1","first-page":"409","article-title":"Subquadratic Algorithms for 3SUM. In WADS (LNCS, Vol. 3608)","author":"Baran Ilya","year":"2005","unstructured":"Ilya Baran, Erik D. Demaine, and Mihai P\u0103tra\u015fcu. 2005. Subquadratic Algorithms for 3SUM. In WADS (LNCS, Vol. 3608). Springer, 409-421.","journal-title":"Springer"},{"key":"e_1_3_2_1_14_1","first-page":"175","article-title":"Querying graph databases","author":"Baeza Pablo Barcel\u00f3","year":"2013","unstructured":"Pablo Barcel\u00f3 Baeza. 2013. Querying graph databases. In PODS. ACM, 175-188.","journal-title":"PODS. ACM"},{"key":"e_1_3_2_1_15_1","first-page":"303","article-title":"Answering Conjunctive Queries under Updates","author":"Berkholz Christoph","year":"2017","unstructured":"Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. 2017. Answering Conjunctive Queries under Updates. In PODS. ACM, 303-318.","journal-title":"PODS. ACM"},{"key":"e_1_3_2_1_16_1","volume-title":"MFCS (LIPIcs","volume":"15","author":"Berkholz Christoph","year":"2019","unstructured":"Christoph Berkholz and Nicole Schweikardt. 2019. Constant Delay Enumeration with FPT-Preprocessing for Conjunctive Queries of Bounded Submodular Width. In MFCS (LIPIcs, Vol. 138). 58:1-58:15."},{"key":"e_1_3_2_1_17_1","first-page":"431","article-title":"Efficient enumeration of maximal k-plexes","author":"Berlowitz Devora","year":"2015","unstructured":"Devora Berlowitz, Sara Cohen, and Benny Kimelfeld. 2015. Efficient enumeration of maximal k-plexes. In SIGMOD. 431-444.","journal-title":"SIGMOD."},{"key":"e_1_3_2_1_18_1","first-page":"431","article-title":"Keyword Searching and Browsing in Databases using BANKS","author":"Bhalotia Gaurav","year":"2002","unstructured":"Gaurav Bhalotia, Arvind Hulgeri, Charuta Nakhe, Soumen Chakrabarti, and S. Sudarshan. 2002. Keyword Searching and Browsing in Databases using BANKS. In ICDE. IEEE Computer Society, 431-440.","journal-title":"ICDE. IEEE Computer Society"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1023\/A:1024605820527","article-title":"On Maximal Frequent and Minimal Infrequent Sets in Binary","volume":"39","author":"Boros Endre","year":"2003","unstructured":"Endre Boros, Vladimir Gurvich, Leonid Khachiyan, and Kazuhisa Makino. 2003. On Maximal Frequent and Minimal Infrequent Sets in Binary Matrices. Ann. Math. Artif. Intell., Vol. 39, 3 (2003), 211-221.","journal-title":"Matrices. Ann. Math. Artif. Intell."},{"key":"e_1_3_2_1_20_1","volume-title":"CSL (LIPIcs","volume":"151","author":"Brault-Baron Johann","year":"2012","unstructured":"Johann Brault-Baron. 2012. A Negative Conjunctive Query is Easy if and only if it is Beta-Acyclic. In CSL (LIPIcs, Vol. 16). 137-151."},{"key":"e_1_3_2_1_21_1","unstructured":"Johann Brault-Baron. 2013. De la pertinence de l'\u00e9num\u00e9ration : complexit\u00e9 en logiques propositionnelle et du premier ordre. Ph.D. Dissertation. University of Caen Normandy France."},{"key":"e_1_3_2_1_22_1","volume-title":"ACM Comput. Surv.","volume":"49","author":"Brault-Baron Johann","year":"2016","unstructured":"Johann Brault-Baron. 2016. Hypergraph Acyclicity Revisited. ACM Comput. Surv., Vol. 49, 3, Article 54 (2016), 26 pages."},{"key":"e_1_3_2_1_23_1","volume-title":"Log. Methods Comput. Sci.","volume":"21","author":"Bringmann Karl","year":"2025","unstructured":"Karl Bringmann and Nofar Carmeli. 2025. Unbalanced Triangle Detection and Enumeration Hardness for Unions of Conjunctive Queries. Log. Methods Comput. Sci., Vol. 21, 1 (2025)."},{"key":"e_1_3_2_1_24_1","article-title":"Tight Fine-Grained Bounds for Direct Access on Join Queries","volume":"50","author":"Bringmann Karl","year":"2025","unstructured":"Karl Bringmann, Nofar Carmeli, and Stefan Mengel. 2025. Tight Fine-Grained Bounds for Direct Access on Join Queries. ACM Trans. Database Syst., Vol. 50, 1 (2025), 1:1-1:44.","journal-title":"ACM Trans. Database Syst."},{"key":"e_1_3_2_1_25_1","first-page":"2145","article-title":"A Fine-Grained Classification of Subquadratic Patterns for Subgraph Listing and Friends","author":"Bringmann Karl","year":"2025","unstructured":"Karl Bringmann and Egor Gorbachev. 2025. A Fine-Grained Classification of Subquadratic Patterns for Subgraph Listing and Friends. In STOC. 2145-2156.","journal-title":"STOC."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1145\/362342.362367","article-title":"Algorithm 457: finding all cliques of an undirected graph","volume":"16","author":"Bron Coen","year":"1973","unstructured":"Coen Bron and Joep Kerbosch. 1973. Algorithm 457: finding all cliques of an undirected graph. Commun. ACM, Vol. 16, 9 (1973), 575\u2013577.","journal-title":"Commun. ACM"},{"key":"e_1_3_2_1_27_1","first-page":"1","article-title":"Polynomial Delay Algorithm for Minimal Chordal Completions","volume":"229","author":"Brosse Caroline","year":"2022","unstructured":"Caroline Brosse, Vincent Limouzy, and Arnaud Mary. 2022. Polynomial Delay Algorithm for Minimal Chordal Completions. In ICALP, Vol. 229. 33:1-33:16.","journal-title":"ICALP"},{"key":"e_1_3_2_1_28_1","volume-title":"Enumerating maximal induced subgraphs. arXiv preprint arXiv:2004.09885","author":"Cao Yixin","year":"2020","unstructured":"Yixin Cao. 2020. Enumerating maximal induced subgraphs. arXiv preprint arXiv:2004.09885 (2020)."},{"key":"e_1_3_2_1_29_1","volume-title":"ICDT (LIPIcs","volume":"20","author":"Capelli Florent","year":"2024","unstructured":"Florent Capelli and Oliver Irwin. 2024. Direct Access for Conjunctive Queries with Negations. In ICDT (LIPIcs, Vol. 290). 13:1-13:20."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/j.dam.2018.06.038","article-title":"Incremental delay enumeration: Space and time","volume":"268","author":"Capelli Florent","year":"2019","unstructured":"Florent Capelli and Yann Strozecki. 2019. Incremental delay enumeration: Space and time. Discret. Appl. Math., Vol. 268 (2019), 179-190.","journal-title":"Discret. Appl. Math."},{"key":"e_1_3_2_1_31_1","volume-title":"STACS (LIPIcs","volume":"22","author":"Capelli Florent","year":"2023","unstructured":"Florent Capelli and Yann Strozecki. 2023. Geometric Amortization of Enumeration Algorithms. In STACS (LIPIcs, Vol. 254). 18:1-18:22."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1016\/j.dam.2020.05.034","article-title":"Efficiently enumerating minimal triangulations","volume":"303","author":"Carmeli Nofar","year":"2021","unstructured":"Nofar Carmeli, Batya Kenig, Benny Kimelfeld, and Markus Kr\u00f6ll. 2021. Efficiently enumerating minimal triangulations. Discret. Appl. Math., Vol. 303 (2021), 216-236.","journal-title":"Discret. Appl. Math."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"crossref","first-page":"828","DOI":"10.1007\/s00224-019-09937-9","article-title":"Enumeration Complexity of Conjunctive Queries with Functional Dependencies","volume":"64","author":"Carmeli Nofar","year":"2020","unstructured":"Nofar Carmeli and Markus Kr\u00f6ll. 2020. Enumeration Complexity of Conjunctive Queries with Functional Dependencies. Theory Comput. Syst., Vol. 64, 5 (2020), 828-860.","journal-title":"Theory Comput. Syst."},{"key":"e_1_3_2_1_34_1","article-title":"On the Enumeration Complexity of Unions of Conjunctive Queries","volume":"46","author":"Carmeli Nofar","year":"2021","unstructured":"Nofar Carmeli and Markus Kr\u00f6ll. 2021. On the Enumeration Complexity of Unions of Conjunctive Queries. ACM Trans. Database Syst., Vol. 46, 2 (2021), 5:1-5:41.","journal-title":"ACM Trans. Database Syst."},{"key":"e_1_3_2_1_35_1","first-page":"277","article-title":"Conjunctive Queries with Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis","author":"Carmeli Nofar","year":"2023","unstructured":"Nofar Carmeli and Luc Segoufin. 2023. Conjunctive Queries with Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis. In PODS. 277-289.","journal-title":"PODS."},{"key":"e_1_3_2_1_36_1","unstructured":"Nofar Carmeli and Nikolaos Tziavelis. 2025. Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum. arXiv:2510.19197"},{"key":"e_1_3_2_1_37_1","unstructured":"Nofar Carmeli and Nikolaos Tziavelis. 2026. Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum. In PODS. (to appear)."},{"key":"e_1_3_2_1_38_1","article-title":"Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries","volume":"48","author":"Carmeli Nofar","year":"2023","unstructured":"Nofar Carmeli, Nikolaos Tziavelis, Wolfgang Gatterbauer, Benny Kimelfeld, and Mirek Riedewald. 2023. Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries. ACM Trans. Database Syst., Vol. 48, 1, Article 1 (2023), 45 pages.","journal-title":"ACM Trans. Database Syst."},{"key":"e_1_3_2_1_39_1","article-title":"Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration","volume":"47","author":"Carmeli Nofar","year":"2022","unstructured":"Nofar Carmeli, Shai Zeevi, Christoph Berkholz, Alessio Conte, Benny Kimelfeld, and Nicole Schweikardt. 2022. Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration. ACM Trans. Database Syst., Vol. 47, 3, Article 9 (2022), 49 pages.","journal-title":"ACM Trans. Database Syst."},{"key":"e_1_3_2_1_40_1","volume-title":"Fine-Grained Complexity of Regular Path Queries. Logical Methods in Computer Science","volume":"19","author":"Casel Katrin","year":"2023","unstructured":"Katrin Casel and Markus L. Schmid. 2023. Fine-Grained Complexity of Regular Path Queries. Logical Methods in Computer Science, Vol. Volume 19, Issue 4, Article 15 (Nov 2023)."},{"key":"e_1_3_2_1_41_1","first-page":"739","article-title":"Full Disjunctions","author":"Cohen Sara","year":"2006","unstructured":"Sara Cohen, Itzhak Fadida, Yaron Kanza, Benny Kimelfeld, and Yehoshua Sagiv. 2006. Full Disjunctions: Polynomial-Delay Iterators in Action. In VLDB. 739-750.","journal-title":"Polynomial-Delay Iterators in Action. In VLDB."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"crossref","first-page":"1147","DOI":"10.1016\/j.jcss.2008.04.003","article-title":"Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties","volume":"74","author":"Cohen Sara","year":"2008","unstructured":"Sara Cohen, Benny Kimelfeld, and Yehoshua Sagiv. 2008. Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties. J. Comput. Syst. Sci., Vol. 74, 7 (2008), 1147-1159.","journal-title":"J. Comput. Syst. Sci."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"crossref","first-page":"648","DOI":"10.1016\/j.jcss.2006.10.015","article-title":"An incremental algorithm for computing ranked full disjunctions","volume":"73","author":"Cohen Sara","year":"2007","unstructured":"Sara Cohen and Yehoshua Sagiv. 2007. An incremental algorithm for computing ranked full disjunctions. J. Comput. Syst. Sci., Vol. 73, 4 (2007), 648-668.","journal-title":"J. Comput. Syst. Sci."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1016\/j.dam.2025.06.004","article-title":"Listing maximal H-free subgraphs","volume":"377","author":"Conte Alessio","year":"2025","unstructured":"Alessio Conte, Roberto Grossi, Mamadou Moustapha Kant\u00e9, Andrea Marino, and Takeaki Uno. 2025. Listing maximal H-free subgraphs. Discrete Appl. Math., Vol. 377 (2025), 18-31.","journal-title":"Discrete Appl. Math."},{"key":"e_1_3_2_1_45_1","first-page":"1","article-title":"Listing Subgraphs by Cartesian Decomposition","volume":"84","author":"Conte Alessio","year":"2018","unstructured":"Alessio Conte, Roberto Grossi, Andrea Marino, Romeo Rizzi, and Luca Versari. 2018. Listing Subgraphs by Cartesian Decomposition. In MFCS (LIPIcs). 84:1-84:16.","journal-title":"MFCS (LIPIcs)."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"crossref","first-page":"1580","DOI":"10.1137\/20M1375048","article-title":"Proximity Search for Maximal Subgraph Enumeration","volume":"51","author":"Conte Alessio","year":"2022","unstructured":"Alessio Conte, Roberto Grossi, Andrea Marino, Takeaki Uno, and Luca Versari. 2022. Proximity Search for Maximal Subgraph Enumeration. SIAM J. Comput., Vol. 51, 5 (2022), 1580-1625.","journal-title":"SIAM J. Comput."},{"key":"e_1_3_2_1_47_1","first-page":"1179","article-title":"New polynomial delay bounds for maximal subgraph enumeration by proximity search","author":"Conte Alessio","year":"2019","unstructured":"Alessio Conte and Takeaki Uno. 2019. New polynomial delay bounds for maximal subgraph enumeration by proximity search. In STOC. ACM, 1179-1190.","journal-title":"STOC. ACM"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/j.dam.2019.02.025","article-title":"A complexity theory for hard enumeration problems","volume":"268","author":"Creignou Nadia","year":"2019","unstructured":"Nadia Creignou, Markus Kr\u00f6ll, Reinhard Pichler, Sebastian Skritek, and Heribert Vollmer. 2019. A complexity theory for hard enumeration problems. Discret. Appl. Math., Vol. 268 (2019), 191-209.","journal-title":"Discret. Appl. Math."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"crossref","first-page":"737","DOI":"10.1007\/s00224-016-9702-4","article-title":"Paradigms for Parameterized Enumeration","volume":"60","author":"Creignou Nadia","year":"2017","unstructured":"Nadia Creignou, Arne Meier, Julian-Steffen M\u00fcller, Johannes Schmidt, and Heribert Vollmer. 2017. Paradigms for Parameterized Enumeration. Theory Comput. Syst., Vol. 60, 4 (2017), 737-758.","journal-title":"Theory Comput. Syst."},{"key":"e_1_3_2_1_50_1","volume-title":"Reinhard Pichler, and Daniel Unterberger.","author":"Creignou Nadia","year":"2026","unstructured":"Nadia Creignou, Timo Camillo Merkl, Reinhard Pichler, and Daniel Unterberger. 2026. From FPT Decision to FPT Enumeration. In FoIKS. Springer, 213-231."},{"key":"e_1_3_2_1_51_1","volume-title":"Parameterized Algorithms","author":"Cygan Marek","unstructured":"Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D\u00e1niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer."},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3651601","article-title":"Distinct shortest walk enumeration for RPQs","volume":"2","author":"David Claire","year":"2024","unstructured":"Claire David, Nadime Francis, and Victor Marsault. 2024. Distinct shortest walk enumeration for RPQs. Proceedings of the ACM on Management of Data, Vol. 2, 2 (2024), 1-22.","journal-title":"Proceedings of the ACM on Management of Data"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"crossref","first-page":"1024","DOI":"10.14778\/3510397.3510401","article-title":"Ranked enumeration of join queries with projections","volume":"15","author":"Deep Shaleen","year":"2022","unstructured":"Shaleen Deep, Xiao Hu, and Paraschos Koutris. 2022. Ranked enumeration of join queries with projections. Proc. VLDB Endow., Vol. 15, 5 (2022), 1024\u20131037.","journal-title":"Proc. VLDB Endow."},{"key":"e_1_3_2_1_54_1","volume-title":"Log. Methods Comput. Sci.","volume":"21","author":"Deep Shaleen","year":"2025","unstructured":"Shaleen Deep, Xiao Hu, and Paraschos Koutris. 2025. Enumeration Algorithms for Conjunctive Queries with Projection. Log. Methods Comput. Sci., Vol. 21, 3 (2025)."},{"key":"e_1_3_2_1_55_1","first-page":"307","article-title":"Compressed Representations of Conjunctive Query Results","author":"Deep Shaleen","year":"2018","unstructured":"Shaleen Deep and Paraschos Koutris. 2018. Compressed Representations of Conjunctive Query Results. In PODS. ACM, 307-322.","journal-title":"PODS. ACM"},{"key":"e_1_3_2_1_56_1","volume-title":"Log. Methods Comput. Sci.","volume":"21","author":"Deep Shaleen","year":"2025","unstructured":"Shaleen Deep and Paraschos Koutris. 2025. Ranked Enumeration of Conjunctive Query Results. Log. Methods Comput. Sci., Vol. 21, 2, Article 14 (2025)."},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1145\/3484622.3484624","article-title":"Database Principles and Challenges in Text Analysis","volume":"50","author":"Doleschal Johannes","year":"2021","unstructured":"Johannes Doleschal, Benny Kimelfeld, and Wim Martens. 2021. Database Principles and Challenges in Text Analysis. SIGMOD Rec., Vol. 50, 2 (2021), 6-17.","journal-title":"SIGMOD Rec."},{"key":"e_1_3_2_1_58_1","volume-title":"Fellows","author":"Downey Rodney G.","year":"1999","unstructured":"Rodney G. Downey and Michael R. Fellows. 1999. Parameterized Complexity."},{"key":"e_1_3_2_1_59_1","first-page":"331","article-title":"Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration","author":"Durand Arnaud","year":"2020","unstructured":"Arnaud Durand. 2020. Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration. In PODS. ACM, 331-346.","journal-title":"PODS. ACM"},{"key":"e_1_3_2_1_60_1","volume-title":"CSL (LIPIcs","volume":"202","author":"Durand Arnaud","year":"2011","unstructured":"Arnaud Durand and Yann Strozecki. 2011. Enumeration Complexity of Logical Query Problems with Second-order Variables. In CSL (LIPIcs, Vol. 12). 189-202."},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"crossref","first-page":"1278","DOI":"10.1137\/S0097539793250299","article-title":"Identifying the Minimal Transversals of a Hypergraph and Related Problems","volume":"24","author":"Eiter Thomas","year":"1995","unstructured":"Thomas Eiter and Georg Gottlob. 1995. Identifying the Minimal Transversals of a Hypergraph and Related Problems. SIAM J. Comput., Vol. 24, 6 (1995), 1278-1304.","journal-title":"SIAM J. Comput."},{"key":"e_1_3_2_1_62_1","series-title":"SIAM Journal on computing","volume-title":"New Results on Monotone Dualization and Generating Hypergraph Transversals","author":"Eiter Thomas","year":"2003","unstructured":"Thomas Eiter, Georg Gottlob, and Kazuhisa Makino. 2003. New Results on Monotone Dualization and Generating Hypergraph Transversals. SIAM Journal on computing, Vol. 32, 2 (2003), 514-537."},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"crossref","first-page":"273","DOI":"10.7155\/jgaa.00357","article-title":"A Polynomial Delay Algorithm for Generating Connected Induced Subgraphs of a Given Cardinality","volume":"19","author":"Elbassioni Khaled M.","year":"2015","unstructured":"Khaled M. Elbassioni. 2015. A Polynomial Delay Algorithm for Generating Connected Induced Subgraphs of a Given Cardinality. J. Graph Algorithms Appl., Vol. 19, 1 (2015), 273-280.","journal-title":"J. Graph Algorithms Appl."},{"key":"e_1_3_2_1_64_1","volume-title":"ICDT (LIPIcs","volume":"20","author":"Eldar Idan","year":"2024","unstructured":"Idan Eldar, Nofar Carmeli, and Benny Kimelfeld. 2024. Direct Access for Answers to Conjunctive Queries with Aggregation. In ICDT (LIPIcs, Vol. 290). 4:1-4:20."},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1016\/j.dam.2024.10.004","article-title":"Polynomial delay hybrid algorithms to enumerate candidate keys for a relation","volume":"360","author":"Ennaoui Karima","year":"2025","unstructured":"Karima Ennaoui and Lhouari Nourine. 2025. Polynomial delay hybrid algorithms to enumerate candidate keys for a relation. Discrete Appl. Math., Vol. 360, C (2025), 443\u2013450.","journal-title":"Discrete Appl. Math."},{"key":"e_1_3_2_1_66_1","series-title":"SIAM Journal on computing","volume-title":"Finding the k shortest paths","author":"Eppstein David","year":"1998","unstructured":"David Eppstein. 1998. Finding the k shortest paths. SIAM Journal on computing, Vol. 28, 2 (1998), 652-673."},{"key":"e_1_3_2_1_67_1","article-title":"Listing All Maximal Cliques in Large Sparse Real-World Graphs","volume":"18","author":"Eppstein David","year":"2013","unstructured":"David Eppstein, Maarten L\u00f6ffler, and Darren Strash. 2013. Listing All Maximal Cliques in Large Sparse Real-World Graphs. ACM J. Exp. Algorithmics, Vol. 18, Article 3.1 (Nov. 2013), 21 pages.","journal-title":"ACM J. Exp. Algorithmics"},{"key":"e_1_3_2_1_68_1","article-title":"Document Spanners: A Formal Approach to Information Extraction","volume":"62","author":"Fagin Ronald","year":"2015","unstructured":"Ronald Fagin, Benny Kimelfeld, Frederick Reiss, and Stijn Vansummeren. 2015. Document Spanners: A Formal Approach to Information Extraction. J. ACM, Vol. 62, 2 (2015), 12:1-12:51.","journal-title":"J. ACM"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"crossref","first-page":"683","DOI":"10.1109\/TKDE.2010.154","article-title":"Discovering Conditional Functional Dependencies","volume":"23","author":"Fan Wenfei","year":"2011","unstructured":"Wenfei Fan, Floris Geerts, Jianzhong Li, and Ming Xiong. 2011. Discovering Conditional Functional Dependencies. IEEE Trans. Knowl. Data Eng., Vol. 23, 5 (2011), 683-698.","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1007\/s00778-019-00556-x","article-title":"A survey of community search over big graphs","volume":"29","author":"Fang Yixiang","year":"2020","unstructured":"Yixiang Fang, Xin Huang, Lu Qin, Ying Zhang, Wenjie Zhang, Reynold Cheng, and Xuemin Lin. 2020. A survey of community search over big graphs. VLDB J., Vol. 29, 1 (2020), 353-392.","journal-title":"VLDB J."},{"key":"e_1_3_2_1_71_1","volume-title":"Pathfinder: Returning paths in graph queries","author":"Farias Benjam\u00edn","year":"2024","unstructured":"Benjam\u00edn Farias, Wim Martens, Carlos Rojas, and Domagoj Vrgo\u010d. 2024. Pathfinder: Returning paths in graph queries. In ISWC. Springer, 135-154."},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1007\/BF01240738","article-title":"Network Flow and 2-Satisfiability","volume":"11","author":"Feder Tom\u00e1s","year":"1994","unstructured":"Tom\u00e1s Feder. 1994. Network Flow and 2-Satisfiability. Algorithmica, Vol. 11, 3 (1994), 291-319.","journal-title":"Algorithmica"},{"key":"e_1_3_2_1_73_1","volume-title":"Project-connex Decompositions and Tractability of Aggregate Group-by Conjunctive Queries. CoRR","author":"Figueira Diego","year":"2025","unstructured":"Diego Figueira and Cibele Freire. 2025. Project-connex Decompositions and Tractability of Aggregate Group-by Conjunctive Queries. CoRR, Vol. abs\/2507.14101 (2025)."},{"key":"e_1_3_2_1_74_1","article-title":"Efficient Enumeration Algorithms for Regular Document Spanners","volume":"45","author":"Florenzano Fernando","year":"2020","unstructured":"Fernando Florenzano, Cristian Riveros, Mart\u00edn Ugarte, Stijn Vansummeren, and Domagoj Vrgoc. 2020. Efficient Enumeration Algorithms for Regular Document Spanners. ACM Trans. Database Syst., Vol. 45, 1 (2020), 3:1-3:42.","journal-title":"ACM Trans. Database Syst."},{"key":"e_1_3_2_1_75_1","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1016\/0304-3975(76)90078-5","article-title":"How good is the information theory bound in sorting","volume":"1","author":"Fredman Michael L.","year":"1976","unstructured":"Michael L. Fredman. 1976. How good is the information theory bound in sorting? Theor. Comput. Sci., Vol. 1, 4 (1976), 355-361.","journal-title":"Theor. Comput. Sci."},{"key":"e_1_3_2_1_76_1","doi-asserted-by":"crossref","first-page":"618","DOI":"10.1006\/jagm.1996.0062","article-title":"On the Complexity of Dualization of Monotone Disjunctive Normal Forms","volume":"21","author":"Fredman Michael L.","year":"1996","unstructured":"Michael L. Fredman and Leonid Khachiyan. 1996. On the Complexity of Dualization of Monotone Disjunctive Normal Forms. J. Algorithms, Vol. 21, 3 (1996), 618-628.","journal-title":"J. Algorithms"},{"key":"e_1_3_2_1_77_1","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1137\/0206011","article-title":"Two algorithms for generating weighted spanning trees in order","volume":"6","author":"Gabow Harold N","year":"1977","unstructured":"Harold N Gabow. 1977. Two algorithms for generating weighted spanning trees in order. SIAM J. Comput., Vol. 6, 1 (1977), 139-150.","journal-title":"SIAM J. Comput."},{"key":"e_1_3_2_1_78_1","volume-title":"SIGMOD Conference. ACM Press, 348-358","author":"Galindo-Legaria C\u00e9sar A.","year":"1994","unstructured":"C\u00e9sar A. Galindo-Legaria. 1994. Outerjoins as Disjunctions. In SIGMOD Conference. ACM Press, 348-358."},{"key":"e_1_3_2_1_79_1","volume-title":"ICDT (LIPIcs","volume":"17","author":"Golenberg Konstantin","year":"2016","unstructured":"Konstantin Golenberg and Yehoshua Sagiv. 2016. A Practically Efficient Algorithm for Generating Answers to Keyword Search Over Data Graphs. In ICDT (LIPIcs, Vol. 48). 23:1-23:17."},{"key":"e_1_3_2_1_80_1","volume-title":"Hypertree Decompositions: Questions and Answers. In PODS. 57\u201374.","author":"Gottlob Georg","year":"2016","unstructured":"Georg Gottlob, Gianluigi Greco, Nicola Leone, and Francesco Scarcello. 2016. Hypertree Decompositions: Questions and Answers. In PODS. 57\u201374."},{"key":"e_1_3_2_1_81_1","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/j.jcss.2017.11.005","article-title":"Tree projections and constraint optimization problems: Fixed-parameter tractability and parallel algorithms","volume":"94","author":"Gottlob Georg","year":"2018","unstructured":"Georg Gottlob, Gianluigi Greco, and Francesco Scarcello. 2018. Tree projections and constraint optimization problems: Fixed-parameter tractability and parallel algorithms. J. Comput. Syst. Sci., Vol. 94 (2018), 11-40.","journal-title":"J. Comput. Syst. Sci."},{"key":"e_1_3_2_1_82_1","volume-title":"Which arithmetic operations can be performed in constant time in the RAM model with addition? CoRR","author":"Grandjean Etienne","year":"2022","unstructured":"Etienne Grandjean and Louis Jachiet. 2022. Which arithmetic operations can be performed in constant time in the RAM model with addition? CoRR, Vol. abs\/2206.13851 (2022). arXiv:2206.13851"},{"key":"e_1_3_2_1_83_1","doi-asserted-by":"crossref","unstructured":"Todd J. Green Grigoris Karvounarakis and Val Tannen. 2007. Provenance Semirings. In PODS. ACM 31\u201340.","DOI":"10.1145\/1265530.1265535"},{"key":"e_1_3_2_1_84_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1206035.1206036","article-title":"The complexity of homomorphism and constraint satisfaction problems seen from the other side","volume":"54","author":"Grohe Martin","year":"2007","unstructured":"Martin Grohe. 2007. The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. ACM, Vol. 54, 1 (2007), 1-24.","journal-title":"J. ACM"},{"key":"e_1_3_2_1_85_1","first-page":"1155","article-title":"Semantics and complexity of GraphQL","author":"Hartig Olaf","year":"2018","unstructured":"Olaf Hartig and Jorge P\u00e9rez. 2018. Semantics and complexity of GraphQL. In WWW. ACM, 1155-1164.","journal-title":"WWW. ACM"},{"key":"e_1_3_2_1_86_1","volume-title":"Proc. ACM Manag. Data","volume":"3","author":"Hu Xiao","year":"2025","unstructured":"Xiao Hu and Qichen Wang. 2025. Towards Update-Dependent Analysis of Query Maintenance. Proc. ACM Manag. Data, Vol. 3, 2 (2025), 117:1-117:25."},{"key":"e_1_3_2_1_87_1","doi-asserted-by":"crossref","first-page":"581","DOI":"10.1145\/1014052.1014123","article-title":"SPIN: mining maximal frequent subgraphs from graph databases","author":"Huan Jun","year":"2004","unstructured":"Jun Huan, Wei Wang, Jan F. Prins, and Jiong Yang. 2004. SPIN: mining maximal frequent subgraphs from graph databases. In KDD. ACM, 581-586.","journal-title":"KDD. ACM"},{"key":"e_1_3_2_1_88_1","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1093\/comjnl\/42.2.100","article-title":"TANE","volume":"42","author":"Huhtala Yk\u00e4","year":"1999","unstructured":"Yk\u00e4 Huhtala, Juha K\u00e4rkk\u00e4inen, Pasi Porkka, and Hannu Toivonen. 1999. TANE: An Efficient Algorithm for Discovering Functional and Approximate Dependencies. Comput. J., Vol. 42, 2 (1999), 100-111.","journal-title":"Comput. J."},{"key":"e_1_3_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_3_2_1_90_1","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/0020-0190(88)90065-8","article-title":"On Generating All Maximal Independent","volume":"27","author":"Johnson David S.","year":"1988","unstructured":"David S. Johnson, Christos H. Papadimitriou, and Mihalis Yannakakis. 1988. On Generating All Maximal Independent Sets. Inf. Process. Lett., Vol. 27, 3 (1988), 119-123.","journal-title":"Sets. Inf. Process. Lett."},{"key":"e_1_3_2_1_91_1","first-page":"78","article-title":"Computing full disjunctions","author":"Kanza Yaron","year":"2003","unstructured":"Yaron Kanza and Yehoshua Sagiv. 2003. Computing full disjunctions. In PODS. ACM, 78-89.","journal-title":"PODS. ACM"},{"key":"e_1_3_2_1_92_1","volume-title":"ICDT (LIPIcs","volume":"21","author":"Kara Ahmet","year":"2025","unstructured":"Ahmet Kara, Zheng Luo, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. 2025. Tractable Conjunctive Queries over Static and Dynamic Relations. In ICDT (LIPIcs, Vol. 328). 12:1-12:21."},{"key":"e_1_3_2_1_93_1","article-title":"Maintaining Triangle Queries under Updates","volume":"45","author":"Kara Ahmet","year":"2020","unstructured":"Ahmet Kara, Hung Q. Ngo, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. 2020a. Maintaining Triangle Queries under Updates. ACM Trans. Database Syst., Vol. 45, 3 (2020), 11:1-11:46.","journal-title":"ACM Trans. Database Syst."},{"key":"e_1_3_2_1_94_1","first-page":"375","article-title":"Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries","author":"Kara Ahmet","year":"2020","unstructured":"Ahmet Kara, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. 2020b. Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries. In PODS. 375-392.","journal-title":"PODS."},{"key":"e_1_3_2_1_95_1","volume-title":"ICDT (LIPIcs","volume":"20","author":"Kara Ahmet","year":"2023","unstructured":"Ahmet Kara, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. 2023. Conjunctive Queries with Free Access Patterns Under Updates. In ICDT (LIPIcs, Vol. 255). 17:1-17:20."},{"key":"e_1_3_2_1_96_1","volume-title":"Complexity of Computer Computations","author":"Karp Richard M.","unstructured":"Richard M. Karp. 1972. Reducibility Among Combinatorial Problems. In Complexity of Computer Computations. Plenum Press, New York, 85-103."},{"key":"e_1_3_2_1_97_1","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1137\/0210017","article-title":"An Algorithm for Finding K Minimum Spanning Trees","volume":"10","author":"Katoh N.","year":"1981","unstructured":"N. Katoh, T. Ibaraki, and H. Mine. 1981. An Algorithm for Finding K Minimum Spanning Trees. SIAM J. Comput., Vol. 10, 2 (1981), 247-255.","journal-title":"SIAM J. Comput."},{"key":"e_1_3_2_1_98_1","first-page":"1","article-title":"Enumeration of Minimal Hitting Sets Parameterized by Treewidth","volume":"8","author":"Kenig Batya","year":"2025","unstructured":"Batya Kenig and Dan Shlomo Mizrahi. 2025. Enumeration of Minimal Hitting Sets Parameterized by Treewidth. In ICDT (LIPIcs). 8:1-8:20.","journal-title":"ICDT (LIPIcs)."},{"key":"e_1_3_2_1_99_1","first-page":"297","article-title":"Mining Approximate Acyclic Schemes from Relations","author":"Kenig Batya","year":"2020","unstructured":"Batya Kenig, Pranay Mundra, Guna Prasaad, Babak Salimi, and Dan Suciu. 2020. Mining Approximate Acyclic Schemes from Relations. In SIGMOD. 297-312.","journal-title":"SIGMOD."},{"key":"e_1_3_2_1_100_1","unstructured":"Jens Keppeler. 2020. Answering Conjunctive Queries and FOMOD Queries under Updates. Ph.D. Dissertation. Humboldt University of Berlin Germany."},{"key":"e_1_3_2_1_101_1","doi-asserted-by":"crossref","first-page":"2350","DOI":"10.1016\/j.dam.2006.04.012","article-title":"An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation","volume":"154","author":"Khachiyan Leonid","year":"2006","unstructured":"Leonid Khachiyan, Endre Boros, Khaled M. Elbassioni, and Vladimir Gurvich. 2006. An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation. Discret. Appl. Math., Vol. 154, 16 (2006), 2350-2372.","journal-title":"Discret. Appl. Math."},{"key":"e_1_3_2_1_102_1","volume-title":"Acyclic Conjunctive Regular Path Queries are no Harder than Corresponding Conjunctive Queries. arXiv preprint arXiv:2512.11129","author":"Khamis Mahmoud Abo","year":"2025","unstructured":"Mahmoud Abo Khamis, Alexandru-Mihai Hurjui, Ahmet Kara, Dan Olteanu, and Dan Suciu. 2025a. Acyclic Conjunctive Regular Path Queries are no Harder than Corresponding Conjunctive Queries. arXiv preprint arXiv:2512.11129 (2025)."},{"key":"e_1_3_2_1_103_1","volume-title":"Output-Sensitive Evaluation of Acyclic Conjunctive Regular Path Queries. arXiv preprint arXiv:2509.20204","author":"Khamis Mahmoud Abo","year":"2025","unstructured":"Mahmoud Abo Khamis, Alexandru-Mihai Hurjui, Ahmet Kara, Dan Olteanu, Dan Suciu, and Zilu Tian. 2025b. Output-Sensitive Evaluation of Acyclic Conjunctive Regular Path Queries. arXiv preprint arXiv:2509.20204 (2025)."},{"key":"e_1_3_2_1_104_1","volume-title":"Proc. ACM Manag. Data","volume":"2","author":"Khamis Mahmoud Abo","year":"2024","unstructured":"Mahmoud Abo Khamis, Ahmet Kara, Dan Olteanu, and Dan Suciu. 2024. Insert-Only versus Insert-Delete in Dynamic Query Evaluation. Proc. ACM Manag. Data, Vol. 2, 5 (2024), 219:1-219:26."},{"key":"e_1_3_2_1_105_1","first-page":"429","article-title":"What Do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog Have to Do with One Another?","author":"Khamis Mahmoud Abo","year":"2017","unstructured":"Mahmoud Abo Khamis, Hung Q. Ngo, and Dan Suciu. 2017. What Do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog Have to Do with One Another?. In PODS. ACM, 429-444.","journal-title":"PODS. ACM"},{"key":"e_1_3_2_1_106_1","article-title":"The Complexity of Mining Maximal Frequent Subgraphs","volume":"39","author":"Kimelfeld Benny","year":"2014","unstructured":"Benny Kimelfeld and Phokion G. Kolaitis. 2014. The Complexity of Mining Maximal Frequent Subgraphs. ACM Trans. Database Syst., Vol. 39, 4 (2014), 32:1-32:33.","journal-title":"ACM Trans. Database Syst."},{"key":"e_1_3_2_1_107_1","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/j.tcs.2020.05.016","article-title":"Counting and enumerating preferred database repairs","volume":"837","author":"Kimelfeld Benny","year":"2020","unstructured":"Benny Kimelfeld, Ester Livshits, and Liat Peterfreund. 2020. Counting and enumerating preferred database repairs. Theor. Comput. Sci., Vol. 837 (2020), 115-157.","journal-title":"Theor. Comput. Sci."},{"key":"e_1_3_2_1_108_1","first-page":"173","article-title":"Finding and approximating top-k answers in keyword proximity search","author":"Kimelfeld Benny","year":"2006","unstructured":"Benny Kimelfeld and Yehoshua Sagiv. 2006a. Finding and approximating top-k answers in keyword proximity search. In PODS. ACM, 173-182.","journal-title":"PODS. ACM"},{"key":"e_1_3_2_1_109_1","first-page":"141","volume-title":"NGITS","volume":"4032","author":"Kimelfeld Benny","year":"2006","unstructured":"Benny Kimelfeld and Yehoshua Sagiv. 2006b. Incrementally Computing Ordered Answers of Acyclic Conjunctive Queries. In NGITS, Vol. 4032. Springer, 141-152."},{"key":"e_1_3_2_1_110_1","first-page":"4","article-title":"Efficiently enumerating results of keyword search over data graphs","volume":"33","author":"Kimelfeld Benny","year":"2008","unstructured":"Benny Kimelfeld and Yehoshua Sagiv. 2008. Efficiently enumerating results of keyword search over data graphs. Inf. Syst., Vol. 33, 4-5 (2008), 335-359.","journal-title":"Inf. Syst."},{"key":"e_1_3_2_1_111_1","volume-title":"The art of computer programming","author":"Knuth Donald Ervin","unstructured":"Donald Ervin Knuth. 1998. The art of computer programming, Volume III, 2nd Edition. Addison-Wesley.","edition":"2"},{"key":"e_1_3_2_1_112_1","first-page":"301","article-title":"Linear-Delay Enumeration for Minimal Steiner Problems","author":"Kobayashi Yasuaki","year":"2022","unstructured":"Yasuaki Kobayashi, Kazuhiro Kurita, and Kunihiro Wasa. 2022. Linear-Delay Enumeration for Minimal Steiner Problems. In PODS. ACM, 301-313.","journal-title":"PODS. ACM"},{"key":"e_1_3_2_1_113_1","volume-title":"The Design and Analysis of Algorithms, Chap. 26","author":"Kozen Dexter","unstructured":"Dexter Kozen. 1992. Counting Problems and #P. In The Design and Analysis of Algorithms, Chap. 26. Springer, 138-143."},{"key":"e_1_3_2_1_114_1","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1145\/1519103.1519105","article-title":"SystemT: a system for declarative information extraction","volume":"37","author":"Krishnamurthy Rajasekar","year":"2008","unstructured":"Rajasekar Krishnamurthy, Yunyao Li, Sriram Raghavan, Frederick Reiss, Shivakumar Vaithyanathan, and Huaiyu Zhu. 2008. SystemT: a system for declarative information extraction. SIGMOD Rec., Vol. 37, 4 (2008), 7-13.","journal-title":"SIGMOD Rec."},{"key":"e_1_3_2_1_115_1","volume-title":"A procedure for computing the k best solutions to discrete optimization problems and its application to the shortest path problem. Management science","author":"Lawler Eugene L","year":"1972","unstructured":"Eugene L Lawler. 1972. A procedure for computing the k best solutions to discrete optimization problems and its application to the shortest path problem. Management science, Vol. 18, 7 (1972), 401-405."},{"key":"e_1_3_2_1_116_1","volume-title":"SIGMOD Conference. ACM, 903-914","author":"Li Guoliang","year":"2008","unstructured":"Guoliang Li, Beng Chin Ooi, Jianhua Feng, Jianyong Wang, and Lizhu Zhou. 2008. EASE: an effective 3-in-1 keyword search method for unstructured, semi-structured and structured data. In SIGMOD Conference. ACM, 903-914."},{"key":"e_1_3_2_1_117_1","doi-asserted-by":"crossref","first-page":"1682","DOI":"10.14778\/3401960.3401966","article-title":"Approximate Denial Constraints","volume":"13","author":"Livshits Ester","year":"2020","unstructured":"Ester Livshits, Alireza Heidari, Ihab F. Ilyas, and Benny Kimelfeld. 2020. Approximate Denial Constraints. Proc. VLDB Endow., Vol. 13, 10 (2020), 1682-1695.","journal-title":"Proc. VLDB Endow."},{"key":"e_1_3_2_1_118_1","first-page":"1","article-title":"MSO queries on trees: enumerating answers under updates","volume":"67","author":"Losemann Katja","year":"2014","unstructured":"Katja Losemann and Wim Martens. 2014. MSO queries on trees: enumerating answers under updates. In CSL-LICS. ACM, 67:1-67:10.","journal-title":"CSL-LICS. ACM"},{"key":"e_1_3_2_1_119_1","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1016\/0022-0000(78)90009-0","article-title":"Candidate Keys for Relations","volume":"17","author":"Lucchesi Claudio L.","year":"1978","unstructured":"Claudio L. Lucchesi and Sylvia L. Osborn. 1978. Candidate Keys for Relations. J. Comput. Syst. Sci., Vol. 17, 2 (1978), 270-279.","journal-title":"J. Comput. Syst. Sci."},{"key":"e_1_3_2_1_120_1","volume-title":"SIGMOD Conference. ACM, 115-126","author":"Luo Yi","year":"2007","unstructured":"Yi Luo, Xuemin Lin, Wei Wang, and Xiaofang Zhou. 2007. Spark: top-k keyword query in relational databases. In SIGMOD Conference. ACM, 115-126."},{"key":"e_1_3_2_1_121_1","unstructured":"Andrea Marino. 2012. Algorithms for Biological Graphs: Analysis and Enumeration. Ph.D. Dissertation. Universit\u00e0 degli Studi di Firenze Firenze Italy."},{"key":"e_1_3_2_1_122_1","volume-title":"Evaluation and Enumeration Problems for Regular Path Queries. In 21st International Conference on Database Theory, ICDT 2018","volume":"21","author":"Martens Wim","year":"2018","unstructured":"Wim Martens and Tina Trautner. 2018. Evaluation and Enumeration Problems for Regular Path Queries. In 21st International Conference on Database Theory, ICDT 2018, Vienna, Austria, March 26-29, 2018 (LIPIcs, Vol. 98). 19:1-19:21."},{"key":"e_1_3_2_1_123_1","article-title":"Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries","volume":"60","author":"Marx D\u00e1niel","year":"2013","unstructured":"D\u00e1niel Marx. 2013. Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries. J. ACM, Vol. 60, 6 (2013), 42:1-42:51.","journal-title":"J. ACM"},{"key":"e_1_3_2_1_124_1","volume-title":"Enumeration of minimal transversals of hypergraphs of bounded VC-dimension. CoRR","author":"Mary Arnaud","year":"2024","unstructured":"Arnaud Mary. 2024. Enumeration of minimal transversals of hypergraphs of bounded VC-dimension. CoRR, Vol. abs\/2407.00694 (2024). arXiv:2407.00694"},{"key":"e_1_3_2_1_125_1","volume-title":"Discret. Math. Theor. Comput. Sci.","volume":"21","author":"Mary Arnaud","year":"2019","unstructured":"Arnaud Mary and Yann Strozecki. 2019. Efficient enumeration of solutions produced by closure operations. Discret. Math. Theor. Comput. Sci., Vol. 21, 3 (2019)."},{"key":"e_1_3_2_1_126_1","unstructured":"Arne Meier. 2020. Parametrised Enumeration. Leibniz Universit\u00e4t Hannover Habilitationsschrift."},{"key":"e_1_3_2_1_127_1","doi-asserted-by":"crossref","first-page":"1235","DOI":"10.1137\/S009753979122370X","article-title":"Finding regular simple paths in graph databases","volume":"24","author":"Mendelzon Alberto O","year":"1995","unstructured":"Alberto O Mendelzon and Peter T Wood. 1995. Finding regular simple paths in graph databases. SIAM J. Comput., Vol. 24, 6 (1995), 1235-1258.","journal-title":"SIAM J. Comput."},{"key":"e_1_3_2_1_128_1","volume-title":"Lower Bounds for Conjunctive Query Evaluation. CoRR","author":"Mengel Stefan","year":"2025","unstructured":"Stefan Mengel. 2025. Lower Bounds for Conjunctive Query Evaluation. CoRR, Vol. abs\/2506.17702 (2025). arXiv:2506.17702"},{"key":"e_1_3_2_1_129_1","volume-title":"oz, Cristian Riveros, and Stijn Vansummeren","author":"Thomas Mu","year":"2024","unstructured":"Thomas Mu n, oz, Cristian Riveros, and Stijn Vansummeren. 2024. Enumeration and Updates for Conjunctive Linear Algebra Queries Through Expressibility. In ICDT (LIPIcs, Vol. 290). 12:1-12:20."},{"key":"e_1_3_2_1_130_1","doi-asserted-by":"crossref","first-page":"682","DOI":"10.1287\/opre.16.3.682","article-title":"An Algorithm for Ranking all the Assignments in Order of Increasing Cost","volume":"16","author":"Murty Katta G.","year":"1968","unstructured":"Katta G. Murty. 1968. An Algorithm for Ranking all the Assignments in Order of Increasing Cost. Operations Research, Vol. 16, 3 (1968), 682-687.","journal-title":"Operations Research"},{"key":"e_1_3_2_1_131_1","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"Niedermeier Rolf","unstructured":"Rolf Niedermeier. 2006. Invitation to Fixed-Parameter Algorithms. Oxford University Press."},{"key":"e_1_3_2_1_132_1","article-title":"Size Bounds for Factorised Representations of Query Results","volume":"40","author":"Olteanu Dan","year":"2015","unstructured":"Dan Olteanu and Jakub Z\u00e1vodn\u00fd. 2015. Size Bounds for Factorised Representations of Query Results. ACM Trans. Database Syst., Vol. 40, 1 (2015), 2:1-2:44.","journal-title":"ACM Trans. Database Syst."},{"key":"e_1_3_2_1_133_1","doi-asserted-by":"crossref","first-page":"266","DOI":"10.14778\/3368289.3368293","article-title":"Discovery of Approximate (and Exact) Denial Constraints","volume":"13","author":"Pena Eduardo H. M.","year":"2019","unstructured":"Eduardo H. M. Pena, Eduardo C. de Almeida, and Felix Naumann. 2019. Discovery of Approximate (and Exact) Denial Constraints. Proc. VLDB Endow., Vol. 13, 3 (2019), 266-278.","journal-title":"Proc. VLDB Endow."},{"key":"e_1_3_2_1_134_1","first-page":"320","article-title":"Complexity Bounds for Relational Algebra over Document Spanners","author":"Peterfreund Liat","year":"2019","unstructured":"Liat Peterfreund, Dominik D. Freydenberger, Benny Kimelfeld, and Markus Kr\u00f6ll. 2019. Complexity Bounds for Relational Algebra over Document Spanners. In PODS. ACM, 320-334.","journal-title":"PODS. ACM"},{"key":"e_1_3_2_1_135_1","unstructured":"Tina Popp. 2022. Evaluation and Enumeration of Regular Simple Path and Trail Queries. Ph.D. Dissertation."},{"key":"e_1_3_2_1_136_1","volume-title":"Combinatorial generation. Working version (1j-CSC 425\/520)","author":"Ruskey Frank","year":"2003","unstructured":"Frank Ruskey. 2003. Combinatorial generation. Working version (1j-CSC 425\/520) (2003)."},{"key":"e_1_3_2_1_137_1","article-title":"Enumeration for FO Queries over Nowhere Dense Graphs","volume":"69","author":"Schweikardt Nicole","year":"2022","unstructured":"Nicole Schweikardt, Luc Segoufin, and Alexandre Vigny. 2022. Enumeration for FO Queries over Nowhere Dense Graphs. J. ACM, Vol. 69, 3 (2022), 22:1-22:37.","journal-title":"J. ACM"},{"key":"e_1_3_2_1_138_1","first-page":"1033","article-title":"Declarative Information Extraction Using Datalog with Embedded Extraction Predicates","author":"Shen Warren","year":"2007","unstructured":"Warren Shen, AnHai Doan, Jeffrey F. Naughton, and Raghu Ramakrishnan. 2007. Declarative Information Extraction Using Datalog with Embedded Extraction Predicates. In VLDB. ACM, 1033-1044.","journal-title":"VLDB. ACM"},{"key":"e_1_3_2_1_139_1","first-page":"2","article-title":"Prioritized repairing and consistent query answering in relational databases","volume":"64","author":"Staworko Slawek","year":"2012","unstructured":"Slawek Staworko, Jan Chomicki, and Jerzy Marcinkowski. 2012. Prioritized repairing and consistent query answering in relational databases. Ann. Math. Artif. Intell., Vol. 64, 2-3 (2012), 209-246.","journal-title":"Ann. Math. Artif. Intell."},{"key":"e_1_3_2_1_140_1","volume-title":"Bull. EATCS","volume":"129","author":"Strozecki Yann","year":"2019","unstructured":"Yann Strozecki. 2019. Enumeration Complexity. Bull. EATCS, Vol. 129 (2019)."},{"key":"e_1_3_2_1_141_1","unstructured":"UNO Takeaki. 2003. Two general methods to reduce delay and change of enumeration algorithms. Technical Report."},{"key":"e_1_3_2_1_142_1","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1145\/3793217.3793219","article-title":"Split Theorems for Join Reporting and Sampling","volume":"54","author":"Tao Yufei","year":"2026","unstructured":"Yufei Tao and Ru Wang. 2026. Split Theorems for Join Reporting and Sampling. SIGMOD Rec., Vol. 54, 4 (2026), 7\u201318.","journal-title":"SIGMOD Rec."},{"key":"e_1_3_2_1_143_1","article-title":"MARGIN: Maximal frequent subgraph mining","volume":"4","author":"Thomas Lini T.","year":"2010","unstructured":"Lini T. Thomas, Satyanarayana R. Valluri, and Kamalakar Karlapalem. 2010. MARGIN: Maximal frequent subgraph mining. ACM Trans. Knowl. Discov. Data, Vol. 4, 3 (2010), 10:1-10:42.","journal-title":"ACM Trans. Knowl. Discov. Data"},{"key":"e_1_3_2_1_144_1","series-title":"SIAM Journal on computing","volume-title":"A new algorithm for generating all the maximal independent sets","author":"Tsukiyama Shuji","year":"1977","unstructured":"Shuji Tsukiyama, Mikio Ide, Hiromu Ariyoshi, and Isao Shirakawa. 1977. A new algorithm for generating all the maximal independent sets. SIAM Journal on computing, Vol. 6, 3 (1977), 505-517."},{"key":"e_1_3_2_1_145_1","doi-asserted-by":"crossref","unstructured":"Nikolaos Tziavelis Nofar Carmeli Wolfgang Gatterbauer Benny Kimelfeld and Mirek Riedewald. 2023. Efficient Computation of Quantiles over Joins. In PODS (Seattle WA USA). ACM 303\u2013315.","DOI":"10.1145\/3584372.3588670"},{"key":"e_1_3_2_1_146_1","doi-asserted-by":"crossref","first-page":"2599","DOI":"10.14778\/3476249.3476306","article-title":"Beyond Equi-joins","volume":"14","author":"Tziavelis Nikolaos","year":"2021","unstructured":"Nikolaos Tziavelis, Wolfgang Gatterbauer, and Mirek Riedewald. 2021. Beyond Equi-joins: Ranking, Enumeration and Factorization. Proc. VLDB Endow., Vol. 14, 11 (2021), 2599-2612.","journal-title":"Ranking, Enumeration and Factorization. Proc. VLDB Endow."},{"key":"e_1_3_2_1_147_1","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1145\/3703922.3703924","article-title":"Ranked Enumeration for Database Queries","volume":"53","author":"Tziavelis Nikolaos","year":"2024","unstructured":"Nikolaos Tziavelis, Wolfgang Gatterbauer, and Mirek Riedewald. 2024. Ranked Enumeration for Database Queries. SIGMOD Rec., Vol. 53, 3 (2024), 6-19.","journal-title":"SIGMOD Rec."},{"key":"e_1_3_2_1_148_1","article-title":"Any-k Algorithms for Enumerating Ranked Answers to Conjunctive Queries","volume":"51","author":"Tziavelis Nikolaos","year":"2025","unstructured":"Nikolaos Tziavelis, Wolfgang Gatterbauer, and Mirek Riedewald. 2025. Any-k Algorithms for Enumerating Ranked Answers to Conjunctive Queries. ACM Trans. Database Syst., Vol. 51, 1, Article 1 (2025), 47 pages.","journal-title":"ACM Trans. Database Syst."},{"key":"e_1_3_2_1_149_1","first-page":"593","article-title":"Constant Time Enumeration by Amortization. In WADS (Lecture Notes in Computer Science, Vol. 9214)","author":"Uno Takeaki","year":"2015","unstructured":"Takeaki Uno. 2015. Constant Time Enumeration by Amortization. In WADS (Lecture Notes in Computer Science, Vol. 9214). Springer, 593-605.","journal-title":"Springer"},{"key":"e_1_3_2_1_150_1","volume-title":"FIMI","volume":"126","author":"Uno Takeaki","year":"2004","unstructured":"Takeaki Uno, Masashi Kiyomi, and Hiroki Arimura. 2004. LCM ver. 2: Efficient Mining Algorithms for Frequent\/Closed\/Maximal Itemsets. In FIMI, Vol. 126."},{"key":"e_1_3_2_1_151_1","article-title":"Conjunctive Queries with Comparisons","volume":"51","author":"Wang Qichen","year":"2026","unstructured":"Qichen Wang and Ke Yi. 2026. Conjunctive Queries with Comparisons. ACM Trans. Database Syst., Vol. 51, 2 (2026), 7:1-7:37.","journal-title":"ACM Trans. Database Syst."},{"key":"e_1_3_2_1_152_1","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1007\/s41019-021-00154-4","article-title":"Keyword Search on Large Graphs: A Survey","volume":"6","author":"Yang Jianye","year":"2021","unstructured":"Jianye Yang, Wu Yao, and Wenjie Zhang. 2021. Keyword Search on Large Graphs: A Survey. Data Sci. Eng., Vol. 6, 2 (2021), 142-162.","journal-title":"Data Sci. Eng."},{"key":"e_1_3_2_1_153_1","first-page":"82","article-title":"Algorithms for Acyclic Database Schemes","author":"Yannakakis Mihalis","year":"1981","unstructured":"Mihalis Yannakakis. 1981. Algorithms for Acyclic Database Schemes. In VLDB. IEEE Computer Society, 82-94.","journal-title":"VLDB. IEEE Computer Society"},{"key":"e_1_3_2_1_154_1","doi-asserted-by":"crossref","first-page":"712","DOI":"10.1287\/mnsc.17.11.712","article-title":"Finding the k shortest loopless paths in a network","volume":"17","author":"Yen Jin Y","year":"1971","unstructured":"Jin Y Yen. 1971. Finding the k shortest loopless paths in a network. Management Science, Vol. 17, 11 (1971), 712-716.","journal-title":"Management Science"},{"key":"e_1_3_2_1_155_1","volume-title":"Keyword Search in Databases","author":"Yu Jeffrey Xu","unstructured":"Jeffrey Xu Yu, Lu Qin, and Lijun Chang. 2009. Keyword Search in Databases. Morgan & Claypool Publishers."},{"key":"e_1_3_2_1_156_1","first-page":"75","article-title":"Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization","volume":"2","author":"Zhao Hangdong","year":"2024","unstructured":"Hangdong Zhao, Austen Z. Fan, Xiating Ouyang, and Paraschos Koutris. 2024. Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization. Proc. ACM Manag. Data, Vol. 2, 2 (2024), 75.","journal-title":"Proc. ACM Manag. Data"}],"event":{"name":"SIGMOD\/PODS '26: International Conference on Management of Data","location":"Bengaluru India","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"]},"container-title":["Companion of the 45th Symposium on Principles of Database Systems"],"original-title":[],"deposited":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T12:25:21Z","timestamp":1778070321000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3788852.3805597"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,30]]},"references-count":156,"alternative-id":["10.1145\/3788852.3805597","10.1145\/3788852"],"URL":"https:\/\/doi.org\/10.1145\/3788852.3805597","relation":{},"subject":[],"published":{"date-parts":[[2026,5,30]]},"assertion":[{"value":"2026-05-30","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}