{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,15]],"date-time":"2026-06-15T13:57:47Z","timestamp":1781531867550,"version":"3.54.5"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2026,6,15]],"date-time":"2026-06-15T00:00:00Z","timestamp":1781481600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/legalcode"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2026,12,31]]},"abstract":"<jats:p>\n                    A witness is a sub-database that preserves the query results of the original database, but of a much smaller size. It has wide applications in query rewriting and debugging, query explanation, IoT analytics, multi-layer network routing, and so on. In this article, we study the smallest witness problem (\n                    <jats:monospace>SWP<\/jats:monospace>\n                    ) for the class of conjunctive queries (CQs) without self-joins.\n                  <\/jats:p>\n                  <jats:p>\n                    We first establish the dichotomy that\n                    <jats:monospace>SWP<\/jats:monospace>\n                    for a CQ can be computed in polynomial time if and only if it has\n                    <jats:italic toggle=\"yes\">head-cluster property<\/jats:italic>\n                    , unless\n                    <jats:monospace>P<\/jats:monospace>\n                    =\n                    <jats:monospace>NP<\/jats:monospace>\n                    . Furthermore, we discover the dichotomy that\n                    <jats:monospace>SWP<\/jats:monospace>\n                    for a CQ with head-cluster property can be computed in linear time if and only if it is acyclic, assuming some well-known conjectures. We next turn to the approximated version by relaxing the size of a witness from being minimum. We surprisingly find that the\n                    <jats:italic toggle=\"yes\">head-domination<\/jats:italic>\n                    property\u2014that has been identified for the deletion propagation problem [\n                    <jats:xref ref-type=\"bibr\">40<\/jats:xref>\n                    ]\u2014can also precisely capture the hardness of the approximated smallest witness problem. In polynomial time,\n                    <jats:monospace>SWP<\/jats:monospace>\n                    for any CQ with head-domination property can be approximated within a constant factor, while\n                    <jats:monospace>SWP<\/jats:monospace>\n                    for any CQ without such a property cannot be approximated within a logarithmic factor, unless\n                    <jats:monospace>P<\/jats:monospace>\n                    =\n                    <jats:monospace>NP<\/jats:monospace>\n                    .\n                  <\/jats:p>\n                  <jats:p>\n                    We further explore efficient approximation algorithms for CQs without the head-domination property: (1) we show a trivial algorithm that achieves a polynomially large approximation ratio for general CQs; (2) for any CQ with only one non-output attribute, such as star CQs, we show a greedy algorithm with a logarithmic approximation ratio; (3) for line CQs, which contain at least two non-output attributes, we relate\n                    <jats:monospace>SWP<\/jats:monospace>\n                    problem to the directed Steiner forest problem, whose algorithms can be applied to line CQs directly. Meanwhile, we establish an exponentially larger lower bound than above. It remains open to close the gap between the lower and upper bounds of the approximated\n                    <jats:monospace>SWP<\/jats:monospace>\n                    for CQs without the head-domination property.\n                  <\/jats:p>","DOI":"10.1145\/3786785","type":"journal-article","created":{"date-parts":[[2025,12,30]],"date-time":"2025-12-30T22:13:43Z","timestamp":1767132823000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Finding Smallest Witnesses for Conjunctive Queries"],"prefix":"10.1145","volume":"51","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7890-665X","authenticated-orcid":false,"given":"Xiao","family":"Hu","sequence":"first","affiliation":[{"name":"Cheriton School of Computer Science, University of Waterloo","place":["Waterloo, Canada"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2114-8886","authenticated-orcid":false,"given":"Stavros","family":"Sintos","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Illinois Chicago","place":["Chicago, United States"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,15]]},"reference":[{"key":"e_1_3_3_2_2","unstructured":"TPC-H. Retrieved from https:\/\/www.tpc.org\/tpch\/. (TPC-H)."},{"key":"e_1_3_3_3_2","first-page":"1865","volume-title":"SODA","author":"Abboud Amir","year":"2018","unstructured":"Amir Abboud and Greg Bodwin. 2018. Reachability preservers: New extremal bounds and approximation algorithms. In SODA. SIAM, 1865\u20131883."},{"key":"e_1_3_3_4_2","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1109\/FOCS.2014.53","volume-title":"Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science","author":"Abboud Amir","year":"2014","unstructured":"Amir Abboud and Virginia Vassilevska Williams. 2014. Popular conjectures imply strong lower bounds for dynamic problems. In Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science. IEEE, 434\u2013443."},{"key":"e_1_3_3_5_2","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1145\/2902251.2902280","volume-title":"PODS","author":"Khamis Mahmoud Abo","year":"2016","unstructured":"Mahmoud Abo Khamis, Hung Q Ngo, and Atri Rudra. 2016. FAQ: Questions asked frequently. In PODS. 13\u201328."},{"issue":"4","key":"e_1_3_3_6_2","doi-asserted-by":"crossref","first-page":"844","DOI":"10.1145\/210332.210337","article-title":"Color-coding","volume":"42","author":"Alon Noga","year":"1995","unstructured":"Noga Alon, Raphael Yuster, and Uri Zwick. 1995. Color-coding. Journal of the ACM (JACM) 42, 4 (1995), 844\u2013856.","journal-title":"Journal of the ACM (JACM)"},{"key":"e_1_3_3_7_2","first-page":"153","volume-title":"PODS","author":"Amsterdamer Yael","year":"2011","unstructured":"Yael Amsterdamer, Daniel Deutch, and Val Tannen. 2011. Provenance for aggregate queries. In PODS. 153\u2013164."},{"key":"e_1_3_3_8_2","first-page":"739","volume-title":"FOCS (FOCS \u201908)","author":"Atserias Albert","year":"2008","unstructured":"Albert Atserias, Martin Grohe, and D\u00e1niel Marx. 2008. Size bounds and query plans for relational joins. In FOCS (FOCS \u201908). 739\u2013748."},{"key":"e_1_3_3_9_2","first-page":"739","volume-title":"FOCS","author":"Atserias Albert","year":"2008","unstructured":"Albert Atserias, Martin Grohe, and D\u00e1niel Marx. 2008. Size bounds and query plans for relational joins. In FOCS. IEEE, 739\u2013748."},{"key":"e_1_3_3_10_2","first-page":"208","volume-title":"CSL","author":"Bagan Guillaume","year":"2007","unstructured":"Guillaume Bagan, Arnaud Durand, and Etienne Grandjean. 2007. On acyclic conjunctive queries and constant delay enumeration. In CSL. Springer, 208\u2013222."},{"issue":"3","key":"e_1_3_3_11_2","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1145\/2402.322389","article-title":"On the desirability of acyclic database schemes","volume":"30","author":"Beeri C.","year":"1983","unstructured":"C. Beeri, R. Fagin, D. Maier, and M. Yannakakis. 1983. On the desirability of acyclic database schemes. JACM 30, 3 (1983), 479\u2013513.","journal-title":"JACM"},{"key":"e_1_3_3_12_2","unstructured":"Bernhard Korte and Jens Vygen. 2008. Combinatorial Optimization: Theory and Algorithms. Springer."},{"key":"e_1_3_3_13_2","volume-title":"On the Relevance of \u00e9num\u00e9ration: Complexitye in Propositional and First Order Logics","author":"Brault-Baron Johann","year":"2013","unstructured":"Johann Brault-Baron. 2013. On the Relevance of \u00e9num\u00e9ration: Complexitye in Propositional and First Order Logics. Ph.D. Dissertation. University of Caen."},{"issue":"3","key":"e_1_3_3_14_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2983573","article-title":"Hypergraph acyclicity revisited","volume":"49","author":"Brault-Baron Johann","year":"2016","unstructured":"Johann Brault-Baron. 2016. Hypergraph acyclicity revisited. CSUR 49, 3 (2016), 1\u201326.","journal-title":"CSUR"},{"key":"e_1_3_3_15_2","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1145\/543613.543633","volume-title":"PODS","author":"Buneman Peter","year":"2002","unstructured":"Peter Buneman, Sanjeev Khanna, and Wang-Chiew Tan. 2002. On propagation of deletions and annotations through views. In PODS. 150\u2013158."},{"key":"e_1_3_3_16_2","first-page":"316","volume-title":"ICDT","author":"Buneman Peter","year":"2001","unstructured":"Peter Buneman, Sanjeev Khanna, and Tan Wang-Chiew. 2001. Why and where: A characterization of data provenance. In ICDT. Springer, 316\u2013330."},{"issue":"2","key":"e_1_3_3_17_2","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1145\/304181.304206","article-title":"On random sampling over joins","volume":"28","author":"Chaudhuri Surajit","year":"1999","unstructured":"Surajit Chaudhuri, Rajeev Motwani, and Vivek Narasayya. 1999. On random sampling over joins. ACM SIGMOD Record 28, 2 (1999), 263\u2013274.","journal-title":"ACM SIGMOD Record"},{"issue":"2","key":"e_1_3_3_18_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1921659.1921664","article-title":"Set connectivity problems in undirected graphs and the directed steiner network problem","volume":"7","author":"Chekuri Chandra","year":"2011","unstructured":"Chandra Chekuri, Guy Even, Anupam Gupta, and Danny Segev. 2011. Set connectivity problems in undirected graphs and the directed steiner network problem. TALG 7, 2 (2011), 1\u201317.","journal-title":"TALG"},{"key":"e_1_3_3_19_2","volume-title":"ICDT","author":"Chen Yu","year":"2020","unstructured":"Yu Chen and Ke Yi. 2020. Random sampling and size estimation over cyclic joins. In ICDT."},{"issue":"2","key":"e_1_3_3_20_2","first-page":"12","article-title":"Parameterized approximation algorithms for bidirected steiner network problems","volume":"17","author":"Chitnis Rajesh","year":"2021","unstructured":"Rajesh Chitnis, Andreas Emil Feldmann, and Pasin Manurangsi. 2021. Parameterized approximation algorithms for bidirected steiner network problems. ACM Trans. Algorithms 17, 2, Article 12 (apr2021), 68 pages.","journal-title":"ACM Trans. Algorithms"},{"key":"e_1_3_3_21_2","first-page":"632","volume-title":"CIKM","author":"Cong Gao","year":"2006","unstructured":"Gao Cong, Wenfei Fan, and Floris Geerts. 2006. Annotation propagation revisited for key preserving views. In CIKM. 632\u2013641."},{"issue":"1","key":"e_1_3_3_22_2","first-page":"1","article-title":"Synopses for massive data: Samples, histograms, wavelets, sketches","volume":"4","author":"Cormode Graham","year":"2011","unstructured":"Graham Cormode, Minos Garofalakis, Peter J. Haas, Chris Jermaine. 2011. Synopses for massive data: Samples, histograms, wavelets, sketches. Foundations and Trends\u00ae in Databases 4, 1\u20133 (2011), 1\u2013294.","journal-title":"Foundations and Trends\u00ae in Databases"},{"key":"e_1_3_3_23_2","doi-asserted-by":"crossref","DOI":"10.1017\/9781108769938","volume-title":"Small Summaries for Big Data","author":"Cormode Graham","year":"2020","unstructured":"Graham Cormode and Ke Yi. 2020. Small Summaries for Big Data. Cambridge University Press."},{"key":"e_1_3_3_24_2","doi-asserted-by":"crossref","first-page":"923","DOI":"10.1145\/3618260.3649663","volume-title":"Proceedings of the 56th Annual ACM Symposium on Theory of Computing","author":"Dalirrooyfard Mina","year":"2024","unstructured":"Mina Dalirrooyfard, Surya Mathialagan, Virginia Vassilevska Williams, and Yinzhan Xu. 2024. Towards optimal output-sensitive clique listing or: Listing cliques from smaller cliques. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing. 923\u2013934."},{"key":"e_1_3_3_25_2","first-page":"36:1\u201336:20","volume-title":"ITCS (LIPIcs)","author":"Dinur Irit","year":"2018","unstructured":"Irit Dinur and Pasin Manurangsi. 2018. ETH-hardness of approximating 2-CSPs and directed steiner network. In ITCS (LIPIcs), Anna R. Karlin (Ed.), Vol. 94. 36:1\u201336:20."},{"key":"e_1_3_3_26_2","first-page":"624","volume-title":"STOC","author":"Dinur Irit","year":"2014","unstructured":"Irit Dinur and David Steurer. 2014. Analytical approach to parallel repetition. In STOC. 624\u2013633."},{"key":"e_1_3_3_27_2","doi-asserted-by":"crossref","first-page":"750","DOI":"10.1145\/301250.301447","volume-title":"STOC","author":"Dodis Yevgeniy","year":"1999","unstructured":"Yevgeniy Dodis and Sanjeev Khanna. 1999. Design networks with bounded pairwise distance. In STOC. 750\u2013759."},{"issue":"1","key":"e_1_3_3_28_2","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/j.tcs.2004.05.009","article-title":"On the complexity of fixed parameter clique and dominating set","volume":"326","author":"Eisenbrand Friedrich","year":"2004","unstructured":"Friedrich Eisenbrand and Fabrizio Grandoni. 2004. On the complexity of fixed parameter clique and dominating set. Theoretical Computer Science 326, 1-3 (2004), 57\u201367.","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"e_1_3_3_29_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3725250","article-title":"Smallest synthetic witnesses for conjunctive queries","volume":"3","author":"Esmailpour Aryan","year":"2025","unstructured":"Aryan Esmailpour, Boris Glavic, Xiao Hu, and Stavros Sintos. 2025. Smallest synthetic witnesses for conjunctive queries. Proceedings of the ACM on Management of Data 3, 2 (2025), 1\u201325.","journal-title":"Proceedings of the ACM on Management of Data"},{"issue":"3","key":"e_1_3_3_30_2","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1145\/2402.322390","article-title":"Degrees of acyclicity for hypergraphs and relational database schemes","volume":"30","author":"Fagin R.","year":"1983","unstructured":"R. Fagin. 1983. Degrees of acyclicity for hypergraphs and relational database schemes. JACM 30, 3 (1983), 514\u2013550.","journal-title":"JACM"},{"issue":"4","key":"e_1_3_3_31_2","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/285055.285059","article-title":"A threshold of ln n for approximating set cover","volume":"45","author":"Feige Uriel","year":"1998","unstructured":"Uriel Feige. 1998. A threshold of ln n for approximating set cover. JACM 45, 4 (1998), 634\u2013652.","journal-title":"JACM"},{"issue":"1","key":"e_1_3_3_32_2","first-page":"279","article-title":"Improved approximation algorithms for directed steiner forest","volume":"78","author":"Feldman Moran","year":"2012","unstructured":"Moran Feldman, Guy Kortsarz, and Zeev Nutov. 2012. Improved approximation algorithms for directed steiner forest. JCSS 78, 1 (2012), 279\u2013292.","journal-title":"JCSS"},{"issue":"3","key":"e_1_3_3_33_2","first-page":"180","article-title":"The complexity of resilience and responsibility for self-join-free conjunctive queries","volume":"9","author":"Freire Cibele","year":"2015","unstructured":"Cibele Freire, Wolfgang Gatterbauer, Neil Immerman, and Alexandra Meliou. 2015. The complexity of resilience and responsibility for self-join-free conjunctive queries. PVLDB 9, 3 (2015), 180\u2013191.","journal-title":"PVLDB"},{"key":"e_1_3_3_34_2","first-page":"271","volume-title":"PODS","author":"Freire Cibele","year":"2020","unstructured":"Cibele Freire, Wolfgang Gatterbauer, Neil Immerman, and Alexandra Meliou. 2020. New results for the complexity of resilience for binary conjunctive queries with self-joins. In PODS. 271\u2013284."},{"issue":"1","key":"e_1_3_3_35_2","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/j.jalgor.2004.04.002","article-title":"Approximation algorithms for partial covering problems","volume":"53","author":"Gandhi Rajiv","year":"2004","unstructured":"Rajiv Gandhi, Samir Khuller, and Aravind Srinivasan. 2004. Approximation algorithms for partial covering problems. Journal of Algorithms 53, 1 (2004), 55\u201384.","journal-title":"Journal of Algorithms"},{"key":"e_1_3_3_36_2","unstructured":"Andrew V Goldberg. 1984. Finding a maximum density subgraph. (1984)."},{"key":"e_1_3_3_37_2","first-page":"31","volume-title":"PODS","author":"Green Todd J","year":"2007","unstructured":"Todd J Green, Grigoris Karvounarakis, and Val Tannen. 2007. Provenance semirings. In PODS. 31\u201340."},{"key":"e_1_3_3_38_2","first-page":"929","volume-title":"CIKM","author":"Hu Shuguang","year":"2017","unstructured":"Shuguang Hu, Xiaowei Wu, and TH Hubert Chan. 2017. Maintaining densest subsets efficiently in evolving hypergraphs. In CIKM. 929\u2013938."},{"issue":"2","key":"e_1_3_3_39_2","first-page":"228","article-title":"Aggregated deletion propagation for counting conjunctive query answers","volume":"14","author":"Hu Xiao","year":"2020","unstructured":"Xiao Hu, Shouzhuo Sun, Shweta Patwa, Debmalya Panigrahi, and Sudeepa Roy. 2020. Aggregated deletion propagation for counting conjunctive query answers. PVLDB 14, 2 (2020), 228\u2013240.","journal-title":"PVLDB"},{"key":"e_1_3_3_40_2","first-page":"597","volume-title":"ICALP","author":"Khuller Samir","year":"2009","unstructured":"Samir Khuller and Barna Saha. 2009. On finding dense subgraphs. In ICALP. Springer, 597\u2013608."},{"issue":"4","key":"e_1_3_3_41_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2389241.2389243","article-title":"Maximizing conjunctive views in deletion propagation","volume":"37","author":"Kimelfeld Benny","year":"2012","unstructured":"Benny Kimelfeld, Jan Vondr\u00e1k, and Ryan Williams. 2012. Maximizing conjunctive views in deletion propagation. TODS 37, 4 (2012), 1\u201337.","journal-title":"TODS"},{"issue":"13","key":"e_1_3_3_42_2","first-page":"1558","article-title":"Multi-tuple deletion propagation: Approximations and complexity","volume":"6","author":"Kimelfeld Benny","year":"2013","unstructured":"Benny Kimelfeld, Jan Vondr\u00e1k, and David P Woodruff. 2013. Multi-tuple deletion propagation: Approximations and complexity. PVLDB 6, 13 (2013), 1558\u20131569.","journal-title":"PVLDB"},{"key":"e_1_3_3_43_2","first-page":"1236","volume-title":"Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Lincoln Andrea","year":"2018","unstructured":"Andrea Lincoln, Virginia Vassilevska Williams, and Ryan Williams. 2018. Tight hardness for shortest cycles and paths in sparse graphs. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1236\u20131252."},{"issue":"2","key":"e_1_3_3_44_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3651605","article-title":"Minimally factorizing the provenance of self-join free conjunctive queries","volume":"2","author":"Makhija Neha","year":"2024","unstructured":"Neha Makhija and Wolfgang Gatterbauer. 2024. Minimally factorizing the provenance of self-join free conjunctive queries. Proceedings of the ACM on Management of Data 2, 2 (2024), 1\u201324.","journal-title":"Proceedings of the ACM on Management of Data"},{"key":"e_1_3_3_45_2","doi-asserted-by":"crossref","unstructured":"Neha Makhija and Wolfgang Gatterbauer. 2025. Is integer linear programming all you need for deletion propagation? A unified and practical approach for generalized deletion propagation. In Proceedings of the VLDB Endowment 18 8 (2025) 2667\u20132680.","DOI":"10.14778\/3742728.3742756"},{"key":"e_1_3_3_46_2","first-page":"503","volume-title":"SIGMOD","author":"Miao Zhengjie","year":"2019","unstructured":"Zhengjie Miao, Sudeepa Roy, and Jun Yang. 2019. Explaining wrong queries using small examples. In SIGMOD. 503\u2013520."},{"key":"e_1_3_3_47_2","first-page":"276","volume-title":"APPROX-RANDOM","author":"Moshkovitz Dana","year":"2012","unstructured":"Dana Moshkovitz. 2012. The projection games conjecture and the NP-hardness of ln n-approximating set-cover. In APPROX-RANDOM. Springer, 276\u2013287."},{"issue":"2","key":"e_1_3_3_48_2","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1145\/3003665.3003667","article-title":"Factorized databases","volume":"45","author":"Olteanu Dan","year":"2016","unstructured":"Dan Olteanu and Maximilian Schleich. 2016. Factorized databases. ACM SIGMOD Record 45, 2 (2016), 5\u201316.","journal-title":"ACM SIGMOD Record"},{"key":"e_1_3_3_49_2","unstructured":"Xiao Hu and Stavros Sintos. 2024. Finding smallest witnesses for conjunctive queries. In 27th International Conference on Database Theory (ICDT\u201924) Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik 24\u20131."},{"key":"e_1_3_3_50_2","volume-title":"CIDR","author":"Paparrizos John","year":"2021","unstructured":"John Paparrizos, Chunwei Liu, Bruno Barbarioli, Johnny Hwang, Ikraduya Edian, Aaron J Elmore, Michael J Franklin, and Sanjay Krishnan. 2021. VergeDB: A database for IoT analytics on edge devices.. In CIDR."},{"key":"e_1_3_3_51_2","first-page":"1269","volume-title":"Proceedings of the Handbook of Discrete and Computational Geometry","author":"Phillips Jeff M","year":"2017","unstructured":"Jeff M Phillips. 2017. Coresets and sketches. In Proceedings of the Handbook of Discrete and Computational Geometry. Chapman and Hall\/CRC, 1269\u20131288."},{"key":"e_1_3_3_52_2","doi-asserted-by":"crossref","unstructured":"Biao Qin Deying Li and Chunlai Zhou. 2022. The resilience of conjunctive queries with inequalities. Information Sciences 613 (2022) 982\u20131002.","DOI":"10.1016\/j.ins.2022.08.049"},{"key":"e_1_3_3_53_2","first-page":"137","volume-title":"STOC","author":"Vardi Moshe Y","year":"1982","unstructured":"Moshe Y Vardi. 1982. The complexity of relational query languages. In STOC. 137\u2013146."},{"key":"e_1_3_3_54_2","volume-title":"Approximation Algorithms","author":"Vazirani Vijay V","year":"2001","unstructured":"Vijay V Vazirani. 2001. Approximation Algorithms. Vol. 1. Springer."},{"key":"e_1_3_3_55_2","first-page":"82","volume-title":"VLDB","author":"Yannakakis Mihalis","year":"1981","unstructured":"Mihalis Yannakakis. 1981. Algorithms for acyclic database schemes. In VLDB, Vol. 81. 82\u201394."},{"key":"e_1_3_3_56_2","first-page":"1525","volume-title":"SIGMOD","author":"Zhao Zhuoyue","year":"2018","unstructured":"Zhuoyue Zhao, Robert Christensen, Feifei Li, Xiao Hu, and Ke Yi. 2018. Random sampling over joins revisited. In SIGMOD. 1525\u20131539."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3786785","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,15]],"date-time":"2026-06-15T13:09:35Z","timestamp":1781528975000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3786785"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,15]]},"references-count":55,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2026,12,31]]}},"alternative-id":["10.1145\/3786785"],"URL":"https:\/\/doi.org\/10.1145\/3786785","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,6,15]]},"assertion":[{"value":"2024-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-12-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}