{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T16:30:51Z","timestamp":1778171451197,"version":"3.51.4"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"2","funder":[{"DOI":"10.13039\/501100006374","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["Discovery Grant"],"award-info":[{"award-number":["Discovery Grant"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"name":"NSF","award":["IIS-2420577, IIS-2420691, IIS-2348919"],"award-info":[{"award-number":["IIS-2420577, IIS-2420691, IIS-2348919"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,6,9]]},"abstract":"<jats:p>\n            Given a self-join-free conjunctive query\n            <jats:italic toggle=\"yes\">Q<\/jats:italic>\n            and a set of tuples\n            <jats:italic toggle=\"yes\">S<\/jats:italic>\n            , a\n            <jats:italic toggle=\"yes\">synthetic witness D<\/jats:italic>\n            is a database instance such that the result of\n            <jats:italic toggle=\"yes\">Q<\/jats:italic>\n            on\n            <jats:italic toggle=\"yes\">D<\/jats:italic>\n            is\n            <jats:italic toggle=\"yes\">S<\/jats:italic>\n            . In this work, we are interested in two problems. First, the existence problem ESW decides whether any synthetic witness\n            <jats:italic toggle=\"yes\">D<\/jats:italic>\n            exists. Second, given that a synthetic witness exists, the minimization problem SSW computes a synthetic witness of minimal size. The SSW problem is related to the\n            <jats:italic toggle=\"yes\">smallest witness problem<\/jats:italic>\n            recently studied by Hu and Sintos [22]; however, the objective and the results are inherently different. More specifically, we show that SSW is poly-time solvable for a wider range of queries. Interestingly, in some cases, SSW is related to optimization problems in other domains, such as the\n            <jats:italic toggle=\"yes\">role mining<\/jats:italic>\n            problem in data mining and the\n            <jats:italic toggle=\"yes\">edge concentration<\/jats:italic>\n            problem in graph drawing. Solutions to ESW and SSW are of practical interest, e.g., for\n            <jats:italic toggle=\"yes\">test database generation<\/jats:italic>\n            for applications accessing a database and for\n            <jats:italic toggle=\"yes\">data compression<\/jats:italic>\n            by encoding a dataset\n            <jats:italic toggle=\"yes\">S<\/jats:italic>\n            as a pair of a query\n            <jats:italic toggle=\"yes\">Q<\/jats:italic>\n            and database\n            <jats:italic toggle=\"yes\">D<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            We prove that ESW is in P, presenting a simple algorithm that, given any\n            <jats:italic toggle=\"yes\">S<\/jats:italic>\n            , decides whether a synthetic witness exists in polynomial time in the size of\n            <jats:italic toggle=\"yes\">S<\/jats:italic>\n            . Next, we focus on the SSW problem. We show an algorithm that computes a minimal synthetic witness in polynomial time with respect to the size of\n            <jats:italic toggle=\"yes\">S<\/jats:italic>\n            for any query\n            <jats:italic toggle=\"yes\">Q<\/jats:italic>\n            that has the\n            <jats:italic toggle=\"yes\">head-domination<\/jats:italic>\n            property. If\n            <jats:italic toggle=\"yes\">Q<\/jats:italic>\n            does not have such a property, then SSW is generally hard. More specifically, we show that for the class of\n            <jats:italic toggle=\"yes\">path queries<\/jats:italic>\n            (of any constant length), SSW cannot be solved in polynomial time unless P = NP. We then extend this hardness result to the class of\n            <jats:italic toggle=\"yes\">Berge-acyclic<\/jats:italic>\n            queries that do not have the head-domination property, obtaining a full dichotomy of SSW for Berge-acyclic queries. Finally, we investigate the hardness of SSW beyond Berge-acyclic queries by showing that SSW cannot be solved in polynomial time for some cyclic queries unless P = NP.\n          <\/jats:p>","DOI":"10.1145\/3725250","type":"journal-article","created":{"date-parts":[[2025,6,9]],"date-time":"2025-06-09T15:20:31Z","timestamp":1749482431000},"page":"1-25","source":"Crossref","is-referenced-by-count":2,"title":["Smallest Synthetic Witnesses for Conjunctive Queries"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-3798-9578","authenticated-orcid":false,"given":"Aryan","family":"Esmailpour","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Illinois Chicago, Chicago, IL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2887-2452","authenticated-orcid":false,"given":"Boris","family":"Glavic","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Illinois Chicago, Chicago, IL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7890-665X","authenticated-orcid":false,"given":"Xiao","family":"Hu","sequence":"additional","affiliation":[{"name":"Cheriton School of Computer Science, University of Waterloo, Waterloo, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"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, Chicago, IL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","unstructured":"Yael Amsterdamer Daniel Deutch and Val Tannen. 2011. Provenance for aggregate queries. In PODS. 153--164. doi:10.1145\/1989284.1989302","DOI":"10.1145\/1989284.1989302"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/110859440"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322389"},{"key":"e_1_2_1_4_1","volume-title":"Hypergraphs: combinatorics of finite sets","author":"Berge Claude","unstructured":"Claude Berge. 1984. Hypergraphs: combinatorics of finite sets. Vol. 45. Elsevier."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","unstructured":"Carsten Binnig Donald Kossmann Eric Lo and M. Tamer \u00d6zsu. 2007. QAGen: generating query-aware test databases. In SIGMOD Chee Yong Chan Beng Chin Ooi and Aoying Zhou (Eds.). 341--352. doi:10.1145\/1247480.1247520","DOI":"10.1145\/1247480.1247520"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","unstructured":"Peter Buneman Sanjeev Khanna and Wang-Chiew Tan. 2002. On Propagation of Deletions and Annotations through Views. In PODS. 150--158. doi:10.1145\/543613.543633","DOI":"10.1145\/543613.543633"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","unstructured":"Peter Buneman Sanjeev Khanna and Tan Wang-Chiew. 2001. Why and where: A characterization of data provenance. In ICDT. 316--330. doi:10.1007\/3--540--44503-X_20","DOI":"10.1007\/3--540--44503-X_20"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3559756"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304206"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","unstructured":"Yu Chen and Ke Yi. 2020. Random sampling and size estimation over cyclic joins. In ICDT. doi:10.4230\/LIPIcs.ICDT.2020.7","DOI":"10.4230\/LIPIcs.ICDT.2020.7"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","unstructured":"Gao Cong Wenfei Fan and Floris Geerts. 2006. Annotation propagation revisited for key preserving views. In CIKM. 632--641. doi:10.1145\/1183614.1183705","DOI":"10.1145\/1183614.1183705"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","unstructured":"Stephen A Cook. 2023. The complexity of theorem-proving procedures. In Logic automata and computational complexity: The works of Stephen A. Cook. ACM 143--152. doi:10.1145\/3588287","DOI":"10.1145\/3588287"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000004"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781108769938"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322390"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","unstructured":"Tom\u00e1s Feder and Rajeev Motwani. 1991. Clique partitions graph compression and speeding-up algorithms. In STOC. 123--133. doi:10.1145\/103418.103424","DOI":"10.1145\/103418.103424"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850592"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","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--284. doi:10.1145\/3375395.3387647","DOI":"10.1145\/3375395.3387647"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","unstructured":"M. R. Garey D. S. Johnson and L. Stockmeyer. 1974. Some simplified NP-complete problems. (1974) 47--63. doi:10.1145\/800119.803884","DOI":"10.1145\/800119.803884"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","unstructured":"Todd J Green Grigoris Karvounarakis and Val Tannen. 2007. Provenance semirings. In PODS. 31--40. doi:10.1145\/1265530.1265535","DOI":"10.1145\/1265530.1265535"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920869"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","unstructured":"Xiao Hu and Stavros Sintos. 2024. Finding Smallest Witnesses for Conjunctive Queries. In ICDT. doi:10.4230\/LIPIcs.ICDT.2024.24","DOI":"10.4230\/LIPIcs.ICDT.2024.24"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3425879.3425892"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","unstructured":"Xiao Hu and Ke Yi. 2016. Towards a worst-case I\/O-Optimal algorithm for acyclic joins. In PODS. 135--150. doi:10.1145\/2902251.2902292","DOI":"10.1145\/2902251.2902292"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","unstructured":"Batya Kenig Pranay Mundra Guna Prasaad Babak Salimi and Dan Suciu. 2020. Mining Approximate Acyclic Schemes from Relations. In SIGMOD. 297--312. doi:10.1145\/3318464.3380573","DOI":"10.1145\/3318464.3380573"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","unstructured":"Batya Kenig and Nir Weinberger. 2023. Quantifying the Loss of Acyclic Join Dependencies. In PODS. 329--338. doi:10.1145\/3584372.3588658","DOI":"10.1145\/3584372.3588658"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989308"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536258.2536267"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","unstructured":"Xi Liang Stavros Sintos Zechao Shang and Sanjay Krishnan. 2021. Combining aggregation and sampling (nearly) optimally for approximate query processing. In SIGMOD. 1129--1141. doi:10.1145\/3448016.3457277","DOI":"10.1145\/3448016.3457277"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166--218X(99)00207--3"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626715"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3651605"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2411.17603"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--319--42634--1_50"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","unstructured":"Zhengjie Miao Sudeepa Roy and Jun Yang. 2019. Explaining wrong queries using small examples. In SIGMOD. 503--520. doi:10.1145\/3299869.3319866","DOI":"10.1145\/3299869.3319866"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2871148"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3003665.3003667"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1601.00617"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2022.08.049"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2016.12.005"},{"key":"e_1_2_1_41_1","unstructured":"Tam\u00e1s G Tarjan. 1975. Complexity of Lattice-Configurations. (1975)."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2016.2519032"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579163"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.3233\/JCS-2009-0341"},{"key":"e_1_2_1_45_1","volume-title":"Provenance Analysis for Missing Answers and Integrity Repairs","author":"Xu Jane","year":"2018","unstructured":"Jane Xu, Waley Zhang, Abdussalam Alawini, and Val Tannen. 2018. Provenance Analysis for Missing Answers and Integrity Repairs. IEEE Data Engineering Bulletin (2018), 39."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","unstructured":"Zhuoyue Zhao Robert Christensen Feifei Li Xiao Hu and Ke Yi. 2018. Random sampling over joins revisited. In SIGMOD. 1525--1539. doi:10.1145\/3183713.3183739","DOI":"10.1145\/3183713.3183739"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725250","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T23:18:26Z","timestamp":1755904706000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725250"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,9]]},"references-count":46,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,9]]}},"alternative-id":["10.1145\/3725250"],"URL":"https:\/\/doi.org\/10.1145\/3725250","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,9]]}}}