{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T20:57:52Z","timestamp":1775595472084,"version":"3.50.1"},"reference-count":70,"publisher":"Association for Computing Machinery (ACM)","issue":"1","funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["1702&#x5c;&#x2f;24"],"award-info":[{"award-number":["1702&#x5c;&#x2f;24"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"name":"United States-Israel Binational Science Foundation","award":["2024101"],"award-info":[{"award-number":["2024101"]}]},{"name":"Israel Science Foundation","award":["934&#x5c;&#x2f;25"],"award-info":[{"award-number":["934&#x5c;&#x2f;25"]}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["863&#x5c;&#x2f;25"],"award-info":[{"award-number":["863&#x5c;&#x2f;25"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Israel Science Foundation","award":["3001&#x5c;&#x2f;24"],"award-info":[{"award-number":["3001&#x5c;&#x2f;24"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2026,4,2]]},"abstract":"<jats:p>Datasets often exhibit violations of expected monotonic trends\u2014for example, higher education level correlating with higher average salary, newer homes being more expensive, or diabetes prevalence increasing with age. We address the problem of quantifying how far a dataset deviates from such trends. To this end, we introduce Aggregate Order Dependencies (AODs), an aggregation-centric extension of the previously studied order dependencies. An AOD specifies that the aggregated value of a target attribute (e.g., mean salary) should monotonically increase or decrease with the grouping attribute (e.g., education level).<\/jats:p>\n                  <jats:p>We formulate the AOD repair problem as finding the smallest set of tuples to delete from a table so that the given AOD is satisfied. We analyze the computational complexity of this problem and propose a general algorithmic template for solving it. We instantiate the template for common aggregation functions, introduce optimization techniques that substantially improve the runtime of the template instances, and develop efficient heuristic alternatives. Our experimental study, carried out on both real-world and synthetic datasets, demonstrates the practical efficiency of the algorithms and provides insight into the performance of the heuristics. We also present case studies that uncover and explain unexpected AOD violations using our framework.<\/jats:p>","DOI":"10.1145\/3786624","type":"journal-article","created":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T17:54:13Z","timestamp":1775584453000},"page":"1-27","source":"Crossref","is-referenced-by-count":0,"title":["Analyzing Deviations from Monotonic Trends through Database Repair"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9605-4131","authenticated-orcid":false,"given":"Shunit","family":"Agmon","sequence":"first","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3948-5266","authenticated-orcid":false,"given":"Jonathan","family":"Gal","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3764-1958","authenticated-orcid":false,"given":"Amir","family":"Gilad","sequence":"additional","affiliation":[{"name":"Hebrew University, Jerusalem, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3485-9887","authenticated-orcid":false,"given":"Ester","family":"Livshits","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-2997-4775","authenticated-orcid":false,"given":"Or","family":"Mutay","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0031-5550","authenticated-orcid":false,"given":"Brit","family":"Youngmann","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"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, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,4,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Omer Abramovich Daniel Deutch Nave Frost Ahmet Kara and Dan Olteanu. 2025. Advancing Fact Attribution for Query Answering: Aggregate Queries and Novel Algorithms. arXiv:2506.16923 [cs.DB] https:\/\/arxiv.org\/abs\/2506.16923","DOI":"10.14778\/3749646.3749670"},{"key":"e_1_2_1_2_1","unstructured":"Shunit Agmon Jonathan Gal Amir Gilad Ester Livshits Or Mutay Brit Youngmann and Benny Kimelfeld. 2025. Analyzing Deviations from Monotonic Trends through Database Repair. arXiv:2512.08526 [cs.DB] https:\/\/arxiv.org\/abs\/2512.08526"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/3705829.3705857"},{"key":"e_1_2_1_4_1","first-page":"939","article-title":"On detecting cherry-picked trendlines","volume":"13","author":"Asudeh Abolfazl","year":"2020","unstructured":"Abolfazl Asudeh, Hosagrahar Visvesvaraya Jagadish, You Wu, and Cong Yu. 2020. On detecting cherry-picked trendlines. VLDB, Vol. 13, 6 (2020), 939-952.","journal-title":"VLDB"},{"key":"e_1_2_1_5_1","volume-title":"Cong Yu, and HV Jagadish.","author":"Asudeh Abolfazl","year":"2021","unstructured":"Abolfazl Asudeh, You Will Wu, Cong Yu, and HV Jagadish. 2021. Perturbation-based Detection and Resolution of Cherry-picking. A Quarterly bulletin of the Computer Soc. of the IEEE Technical Committee on Data Engineering, Vol. 45, 3 (2021), 39-51."},{"key":"e_1_2_1_6_1","volume-title":"The housing bubble and the financial crisis. Real-world economics review","author":"Baker Dean","year":"2008","unstructured":"Dean Baker. 2008. The housing bubble and the financial crisis. Real-world economics review, Vol. 46, 20 (2008), 73-81."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/2371212"},{"key":"e_1_2_1_8_1","first-page":"195","article-title":"Repair-Based Degrees of Database Inconsistency. In LPNMR (Lecture Notes in Computer Science, Vol. 11481)","author":"Bertossi Leopoldo E.","year":"2019","unstructured":"Leopoldo E. Bertossi. 2019. Repair-Based Degrees of Database Inconsistency. In LPNMR (Lecture Notes in Computer Science, Vol. 11481). Springer, 195-209.","journal-title":"Springer"},{"key":"e_1_2_1_9_1","first-page":"239","article-title":"Testing monotonicity of distributions over general partial orders","author":"Bhattacharyya Arnab","year":"2011","unstructured":"Arnab Bhattacharyya, Eldar Fischer, Ronitt Rubinfeld, and Paul Valiant. 2011. Testing monotonicity of distributions over general partial orders.. In ICS. Citeseer, 239-252.","journal-title":"ICS. Citeseer"},{"key":"e_1_2_1_10_1","volume-title":"2007 IEEE 23rd international conference on data engineering. IEEE, 746-755","author":"Bohannon Philip","year":"2006","unstructured":"Philip Bohannon, Wenfei Fan, Floris Geerts, Xibei Jia, and Anastasios Kementsietsidis. 2006. Conditional functional dependencies for data cleaning. In 2007 IEEE 23rd international conference on data engineering. IEEE, 746-755."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066175"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.3233\/SCS-230008"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335388"},{"key":"e_1_2_1_14_1","volume-title":"Maximum likelihood estimates of monotone parameters. The Annals of Mathematical Statistics","author":"Brunk Hugh D","year":"1955","unstructured":"Hugh D Brunk. 1955. Maximum likelihood estimates of monotone parameters. The Annals of Mathematical Statistics (1955), 607-616."},{"key":"e_1_2_1_15_1","volume-title":"Database Repairing with Soft Functional Dependencies. In 24th International Conference on Database Theory, ICDT 2021","volume":"17","author":"Carmeli Nofar","year":"2021","unstructured":"Nofar Carmeli, Martin Grohe, Benny Kimelfeld, Ester Livshits, and Muhammad Tibi. 2021. Database Repairing with Soft Functional Dependencies. In 24th International Conference on Database Theory, ICDT 2021, March 23-26, 2021, Nicosia, Cyprus (LIPIcs, Vol. 186), Ke Yi and Zhewei Wei (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 16:1-16:17."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2004.04.007"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2004.04.007"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544847"},{"key":"e_1_2_1_19_1","first-page":"409","article-title":"Discovering Order Dependencies through Order Compatibility","author":"Consonni Cristian","year":"2019","unstructured":"Cristian Consonni, Paolo Sottovia, Alberto Montresor, Yannis Velegrakis, et al., 2019. Discovering Order Dependencies through Order Compatibility.. In EDBT. 409-420.","journal-title":"EDBT."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/582353.582375"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-01892-3"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-75410-7_16"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1735886.1735893"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-1641-8"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536360.2536363"},{"key":"e_1_2_1_26_1","volume-title":"Testing monotonicity of regression. Annals of statistics","author":"Ghosal Subhashis","year":"2000","unstructured":"Subhashis Ghosal, Arusharka Sen, and Aad W Van Der Vaart. 2000. Testing monotonicity of regression. Annals of statistics (2000), 1054-1082."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389721"},{"key":"e_1_2_1_28_1","first-page":"1","article-title":"The Consistency of Probabilistic Databases with Independent Cells. In ICDT (LIPIcs, Vol. 255)","volume":"22","author":"Gilad Amir","year":"2023","unstructured":"Amir Gilad, Aviram Imber, and Benny Kimelfeld. 2023. The Consistency of Probabilistic Databases with Independent Cells. In ICDT (LIPIcs, Vol. 255). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 22:1-22:19.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90084-1"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/5925.5929"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.inffus.2023.102064"},{"key":"e_1_2_1_32_1","volume-title":"Testing for monotonicity of a regression mean by calibrating for linear functions. Annals of Statistics","author":"Hall Peter","year":"2000","unstructured":"Peter Hall and Nancy E Heckman. 2000. Testing for monotonicity of a regression mean by calibrating for linear functions. Annals of Statistics (2000), 20-39."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.24432\/C5NC77"},{"key":"e_1_2_1_34_1","first-page":"535","article-title":"Monotonic regression for the detection of temporal trends in environmental quality data","volume":"54","author":"Hussian Mohamed","year":"2005","unstructured":"Mohamed Hussian, Anders Grimvall, Oleg Burdakov, and Oleg Sysoev. 2005. Monotonic regression for the detection of temporal trends in environmental quality data. MATCH Commun. Math. Comput. Chem, Vol. 54 (2005), 535-550.","journal-title":"MATCH Commun. Math. Comput. Chem"},{"key":"e_1_2_1_35_1","volume-title":"Abdullah M. Albarrak, and Yanjun Zhang.","author":"Ibrahim Ibrahim A.","year":"2018","unstructured":"Ibrahim A. Ibrahim, Xue Li, Xin Zhao, Sanad Al Maskari, Abdullah M. Albarrak, and Yanjun Zhang. 2018. Automated Explanations of User-Expected Trends for Aggregate Queries. In Advances in Knowledge Discovery and Data Mining, Dinh Phung, Vincent S. Tseng, Geoffrey I. Webb, Bao Ho, Mohadeseh Ganji, and Lida Rashidi (Eds.). Springer International Publishing, Cham, 602-614."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00013"},{"key":"e_1_2_1_37_1","first-page":"1938","article-title":"Aggchecker: A fact-checking system for text summaries of relational data sets","volume":"12","author":"Jo Saehan","year":"2019","unstructured":"Saehan Jo, Immanuel Trummer, Weicheng Yu, Xuezhi Wang, Cong Yu, Daniel Liu, and Niyati Mehta. 2019. Aggchecker: A fact-checking system for text summaries of relational data sets. VLDB, Vol. 12, 12 (2019), 1938-1941.","journal-title":"VLDB"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.12983\/ijsrk-2015-p0220-0226"},{"key":"e_1_2_1_39_1","first-page":"1","article-title":"Repairing Databases over Metric Spaces with Coincidence Constraints. In ICDT (LIPIcs, Vol. 328)","volume":"14","author":"Kaminsky Youri","year":"2025","unstructured":"Youri Kaminsky, Benny Kimelfeld, Ester Livshits, Felix Naumann, and David Wajc. 2025. Repairing Databases over Metric Spaces with Coincidence Constraints. In ICDT (LIPIcs, Vol. 328). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 14:1-14:18.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_2_1_40_1","volume-title":"ICDT (ACM International Conference Proceeding Series","volume":"62","author":"Kolahi Solmaz","unstructured":"Solmaz Kolahi and Laks V. S. Lakshmanan. 2009. On approximating optimum repairs for functional dependency violations. In ICDT (ACM International Conference Proceeding Series, Vol. 361). ACM, 53-62."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0412-3"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.3982\/ECTA7145"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/3485450.3485457"},{"key":"e_1_2_1_44_1","first-page":"413","article-title":"Isolation forest. In 2008 eighth ieee international conference on data mining","author":"Liu Fei Tony","year":"2008","unstructured":"Fei Tony Liu, Kai Ming Ting, and Zhi-Hua Zhou. 2008. Isolation forest. In 2008 eighth ieee international conference on data mining. IEEE, 413-422.","journal-title":"IEEE"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3360904"},{"key":"e_1_2_1_46_1","volume-title":"Properties of Inconsistency Measures for Databases. In SIGMOD Conference. ACM, 1182-1194","author":"Livshits Ester","year":"2021","unstructured":"Ester Livshits, Rina Kochirgan, Segev Tsur, Ihab F. Ilyas, Benny Kimelfeld, and Sudeepa Roy. 2021. Properties of Inconsistency Measures for Databases. In SIGMOD Conference. ACM, 1182-1194."},{"key":"e_1_2_1_47_1","first-page":"23","article-title":"Computing Repairs Under Functional and Inclusion Dependencies via Argumentation. In FoIKS (Lecture Notes in Computer Science, Vol. 14589)","author":"Mahmood Yasir","year":"2024","unstructured":"Yasir Mahmood, Jonni Virtema, Timon Barlag, and Axel-Cyrille Ngonga Ngomo. 2024. Computing Repairs Under Functional and Inclusion Dependencies via Argumentation. In FoIKS (Lecture Notes in Computer Science, Vol. 14589). Springer, 23-42.","journal-title":"Springer"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.30.6.765"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-022-00738-0"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3725397"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0306-4379(99)00031-9"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/502030.502033"},{"key":"e_1_2_1_53_1","volume-title":"Freitas","author":"Ovchinnik Sergey","year":"2019","unstructured":"Sergey Ovchinnik, Fernando E. B. Otero, and Alex A. Freitas. 2019. Monotonicity Detection and Enforcement in Longitudinal Classification. In Artificial Intelligence XXXVI, Max Bramer and Miltos Petridis (Eds.). Springer International Publishing, Cham, 63-77."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jfineco.2010.06.006"},{"key":"e_1_2_1_55_1","unstructured":"Judea Pearl. 2009. Causality. Cambridge university press."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2008.09.004"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-3758(90)90012-J"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-91458-9_17"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1111\/1467-9868.00130"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137631"},{"key":"e_1_2_1_61_1","unstructured":"Joshua Robinson Rishabh Ranjan Weihua Hu Kexin Huang Jiaqi Han Alejandro Dobles Matthias Fey Jan E. Lenssen Yiwen Yuan Zecheng Zhang Xinwei He and Jure Leskovec. 2024. RelBench: A Benchmark for Deep Learning on Relational Databases. arXiv:2407.20060 [cs.LG] https:\/\/arxiv.org\/abs\/2407.20060"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.14778\/2856318.2856329"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2588578"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319901"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.929900"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536354.2536356"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732286.2732295"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/2996453"},{"key":"e_1_2_1_69_1","volume-title":"Enhancing data analysis with noise removal","author":"Xiong Hui","year":"2006","unstructured":"Hui Xiong, Gaurav Pandey, Michael Steinbach, and Vipin Kumar. 2006. Enhancing data analysis with noise removal. IEEE transactions on knowledge and data engineering, Vol. 18, 3 (2006), 304-319."},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dss.2016.05.001"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3786624","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T19:58:42Z","timestamp":1775591922000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3786624"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,2]]},"references-count":70,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,4,2]]}},"alternative-id":["10.1145\/3786624"],"URL":"https:\/\/doi.org\/10.1145\/3786624","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,2]]}}}