{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:13:19Z","timestamp":1779174799795,"version":"3.51.4"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2020,6]]},"abstract":"<jats:p>The problem of mining integrity constraints from data has been extensively studied over the past two decades for commonly used types of constraints, including the classic Functional Dependencies (FDs) and the more general Denial Constraints (DCs). In this paper, we investigate the problem of mining from data approximate DCs, that is, DCs that are \"almost\" satisfied. Approximation allows us to discover more accurate constraints in inconsistent databases and detect rules that are generally correct but may have a few exceptions. It also allows to avoid overfitting and obtain constraints that are more general, more natural, and less contrived. We introduce the algorithm ADCMiner for mining approximate DCs. An important feature of this algorithm is that it does not assume any specific approximation function for DCs, but rather allows for arbitrary approximation functions that satisfy some natural axioms that we define in the paper. We also show how our algorithm can be combined with sampling to return highly accurate results considerably faster.<\/jats:p>","DOI":"10.14778\/3401960.3401966","type":"journal-article","created":{"date-parts":[[2021,3,10]],"date-time":"2021-03-10T19:15:14Z","timestamp":1615403714000},"page":"1682-1695","source":"Crossref","is-referenced-by-count":36,"title":["Approximate denial constraints"],"prefix":"10.14778","volume":"13","author":[{"given":"Ester","family":"Livshits","sequence":"first","affiliation":[{"name":"Technion"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alireza","family":"Heidari","sequence":"additional","affiliation":[{"name":"University of Waterloo"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ihab F.","family":"Ilyas","sequence":"additional","affiliation":[{"name":"University of Waterloo"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benny","family":"Kimelfeld","sequence":"additional","affiliation":[{"name":"Technion"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,3,10]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"SARA","author":"Abreu R.","year":"2009","unstructured":"R. Abreu and A. J. C. van Gemund . A low-cost approximate minimal hitting set algorithm and its application to model-based diagnosis . In SARA , 2009 . R. Abreu and A. J. C. van Gemund. A low-cost approximate minimal hitting set algorithm and its application to model-based diagnosis. In SARA, 2009."},{"key":"e_1_2_1_2_1","volume-title":"Constructing blockmodels: How and why. Journal of mathematical psychology, 17(1):21--63","author":"Arabie P.","year":"1978","unstructured":"P. Arabie , S. A. Boorman , and P. R. Levitt . Constructing blockmodels: How and why. Journal of mathematical psychology, 17(1):21--63 , 1978 . P. Arabie, S. A. Boorman, and P. R. Levitt. Constructing blockmodels: How and why. Journal of mathematical psychology, 17(1):21--63, 1978."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(81)90020-1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/3157794.3157800"},{"key":"e_1_2_1_5_1","volume-title":"Universal approximation of edge density in large graphs. arXiv preprint arXiv:1508.01340","author":"Boull\u00e9 M.","year":"2015","unstructured":"M. Boull\u00e9 . Universal approximation of edge density in large graphs. arXiv preprint arXiv:1508.01340 , 2015 . M. Boull\u00e9. Universal approximation of edge density in large graphs. arXiv preprint arXiv:1508.01340, 2015."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2017.12.018"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39955-8_3"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133084"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453980"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1709465.1709573"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536258.2536262"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.compbiomed.2014.08.004"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.154"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704447304"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1216155.1216159"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2009.11.002"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1055024"},{"key":"e_1_2_1_18_1","volume-title":"Electronic Colloquim on Computational Complexity (ECCC)","author":"Goldreich O.","year":"2004","unstructured":"O. Goldreich and D. Ron . On estimating the average degree of a graph . Electronic Colloquim on Computational Complexity (ECCC) , 2004 . O. Goldreich and D. Ron. On estimating the average degree of a graph. Electronic Colloquim on Computational Complexity (ECCC), 2004."},{"key":"e_1_2_1_19_1","volume-title":"The most probable database problem","author":"Gribkoff E.","year":"2014","unstructured":"E. Gribkoff , G. V. den Broeck , and D. Suciu . The most probable database problem . 2014 . E. Gribkoff, G. V. den Broeck, and D. Suciu. The most probable database problem. 2014."},{"key":"e_1_2_1_20_1","volume-title":"UAI, page 152","author":"Heidari A.","year":"2019","unstructured":"A. Heidari , I. F. Ilyas , and T. Rekatsinas . Approximate inference in structured instances with noisy categorical observations . In UAI, page 152 . AUAI Press , 2019 . A. Heidari, I. F. Ilyas, and T. Rekatsinas. Approximate inference in structured instances with noisy categorical observations. In UAI, page 152. AUAI Press, 2019."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319888"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(83)90021-7"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/42.2.100"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/645500.655906"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-45817-5_23"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.197"},{"key":"e_1_2_1_27_1","volume-title":"Approximate denial constraints. CoRR, abs\/2005.08540","author":"Livshits E.","year":"2020","unstructured":"E. Livshits , A. Heidari , I. F. Ilyas , and B. Kimelfeld . Approximate denial constraints. CoRR, abs\/2005.08540 , 2020 . E. Livshits, A. Heidari, I. F. Ilyas, and B. Kimelfeld. Approximate denial constraints. CoRR, abs\/2005.08540, 2020."},{"key":"e_1_2_1_28_1","volume-title":"Principles of progress indicators for database repairing. CoRR, abs\/1904.06492","author":"Livshits E.","year":"2019","unstructured":"E. Livshits , I. F. Ilyas , B. Kimelfeld , and S. Roy . Principles of progress indicators for database repairing. CoRR, abs\/1904.06492 , 2019 . E. Livshits, I. F. Ilyas, B. Kimelfeld, and S. Roy. Principles of progress indicators for database repairing. CoRR, abs\/1904.06492, 2019."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3360904"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/11965893_13"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/645339.650138"},{"key":"e_1_2_1_32_1","volume-title":"Structural equivalence of individuals in social networks. The Journal of mathematical sociology, 1(1):49--80","author":"Lorrain F.","year":"1971","unstructured":"F. Lorrain and H. C. White . Structural equivalence of individuals in social networks. The Journal of mathematical sociology, 1(1):49--80 , 1971 . F. Lorrain and H. C. White. Structural equivalence of individuals in social networks. The Journal of mathematical sociology, 1(1):49--80, 1971."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2014.01.012"},{"key":"e_1_2_1_34_1","first-page":"123","volume-title":"CLA","author":"Nourine L.","year":"2015","unstructured":"L. Nourine , A. Quilliot , and H. Toussaint . Partial enumeration of minimal transversals of a hypergraph . In CLA , pages 123 -- 134 , 2015 . L. Nourine, A. Quilliot, and H. Toussaint. Partial enumeration of minimal transversals of a hypergraph. In CLA, pages 123--134, 2015."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/645504.656418"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/2794367.2794377"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-98809-2_4"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/3368289.3368293"},{"key":"e_1_2_1_39_1","series-title":"Lecture Notes in Computer Science","first-page":"552","volume-title":"ECML\/PKDD (2)","author":"Rammelaere J.","year":"2018","unstructured":"J. Rammelaere and F. Geerts . Revisiting conditional functional dependency discovery: Splitting the \"c\" from the \"fd \". In ECML\/PKDD (2) , volume 11052 of Lecture Notes in Computer Science , pages 552 -- 568 . Springer , 2018 . J. Rammelaere and F. Geerts. Revisiting conditional functional dependency discovery: Splitting the \"c\" from the \"fd\". In ECML\/PKDD (2), volume 11052 of Lecture Notes in Computer Science, pages 552--568. Springer, 2018."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2007.05.001"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0888-613X(00)00051-7"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/646110.679455"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3401960.3401966","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:11:41Z","timestamp":1672225901000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3401960.3401966"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6]]},"references-count":42,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2020,6]]}},"alternative-id":["10.14778\/3401960.3401966"],"URL":"https:\/\/doi.org\/10.14778\/3401960.3401966","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2020,6]]}}}