{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,26]],"date-time":"2026-09-26T04:06:09Z","timestamp":1790395569995,"version":"4.1.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:p>Denial constraints (DCs) are an integrity constraint formalism widely used to detect inconsistencies in data. Several algorithms have been devised to discover DCs from data, as manually specifying them is burdensome and, worse yet, error-prone. The existing algorithms follow two basic steps: building an intermediate data structure from records, then enumerating the DCs from that intermediate. However, current algorithms are often inefficient in computing these intermediates. Also, it is still unclear which enumeration algorithm performs best since some of the available algorithms have not yet been compared to each other.<\/jats:p>\n                  <jats:p>In response, we present a set of new algorithms with improved design choices. We introduce a parallel pipeline for rapidly computing the intermediate using custom data representations, algorithms, and indexes. For DC enumeration, we propose an inverted index, pruning, and parallel search strategies. We present hybrid approaches that integrate our techniques with previous enumeration algorithms, improving their performance in many scenarios. Our experimental study shows that the proposed DC discovery algorithms are consistently much faster (up to an order of magnitude) than the current state-of-the-art.<\/jats:p>","DOI":"10.14778\/3574245.3574254","type":"journal-article","created":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T18:14:12Z","timestamp":1677003252000},"page":"684-696","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["Fast Algorithms for Denial Constraint Discovery"],"prefix":"10.14778","volume":"16","author":[{"given":"Eduardo H. M.","family":"Pena","sequence":"first","affiliation":[{"name":"Federal University of Technology, Campo Mour\u00e3o, Paran\u00e1, Brazil"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fabio","family":"Porto","sequence":"additional","affiliation":[{"name":"LNCC-DEXL, Petropolis, Rio de Janeiro, Brazil"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Felix","family":"Naumann","sequence":"additional","affiliation":[{"name":"Hasso Plattner Institute, University of Potsdam, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,2,21]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0389-y"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2021.11.020"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983323.2983781"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/3157794.3157800"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536258.2536262"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544847"},{"key":"e_1_2_1_7_1","volume-title":"AofA: Analysis of Algorithms","author":"Flajolet Philippe","unstructured":"Philippe Flajolet , \u00c9ric Fusy , Olivier Gandouet , and Fr\u00e9d\u00e9ric Meunier . 2007. HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm . In AofA: Analysis of Algorithms , Vol. DMTCS Proceedings vol. AH, Conference on Analysis of Algorithms (AofA). Discrete Mathematics and Theoretical Computer Science, 137-- 156 . Philippe Flajolet, \u00c9ric Fusy, Olivier Gandouet, and Fr\u00e9d\u00e9ric Meunier. 2007. HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm. In AofA: Analysis of Algorithms, Vol. DMTCS Proceedings vol. AH, Conference on Analysis of Algorithms (AofA). Discrete Mathematics and Theoretical Computer Science, 137--156."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1055024"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00586-5"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389775"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407815"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/3424573.3424577"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00028-U"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2009.08.006"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.2402"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.197"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3401960.3401966"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457310"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2014.01.012"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the International Conference on Database and Expert Systems Applications (DEXA). 53--68","author":"Eduardo H.","unstructured":"Eduardo H. M. Pena and Eduardo Cunha de Almeida. 2018. BFASTDC: A Bitwise Algorithm for Mining Denial Constraints . In Proceedings of the International Conference on Database and Expert Systems Applications (DEXA). 53--68 . Eduardo H. M. Pena and Eduardo Cunha de Almeida. 2018. BFASTDC: A Bitwise Algorithm for Mining Denial Constraints. In Proceedings of the International Conference on Database and Expert Systems Applications (DEXA). 53--68."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/3368289.3368293"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3503585.3503595"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31235-9_31"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137631"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342626"},{"key":"e_1_2_1_26_1","volume-title":"Robertson","author":"Wyss Catharine","year":"2001","unstructured":"Catharine Wyss , Chris Giannella , and Edward L . Robertson . 2001 . FastFDs: A Heuristic-Driven, Depth-First Algorithm for Mining Functional Dependencies from Relation Instances - Extended Abstract. In Proceedings of the International Conference on Data Warehousing and Knowledge Discovery (DaWaK). 101--110. Catharine Wyss, Chris Giannella, and Edward L. Robertson. 2001. FastFDs: A Heuristic-Driven, Depth-First Algorithm for Mining Functional Dependencies from Relation Instances - Extended Abstract. In Proceedings of the International Conference on Data Warehousing and Knowledge Discovery (DaWaK). 101--110."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915222"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3574245.3574254","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T18:20:14Z","timestamp":1677003614000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3574245.3574254"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["10.14778\/3574245.3574254"],"URL":"https:\/\/doi.org\/10.14778\/3574245.3574254","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,12]]},"assertion":[{"value":"2023-02-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}