{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:13:57Z","timestamp":1779174837563,"version":"3.51.4"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2019,11]]},"abstract":"<jats:p>Maintaining data consistency is known to be hard. Recent approaches have relied on integrity constraints to deal with the problem - correct and complete constraints naturally work towards data consistency. State-of-the-art data cleaning frameworks have used the formalism known as denial constraint (DC) to handle a wide range of real-world constraints. Each DC expresses a relationship between predicates that indicate which combinations of attribute values are inconsistent. The design of DCs, however, must keep pace with the complexity of data and applications.<\/jats:p>\n          <jats:p>The alternative to designing DCs by hand is automatically discovering DCs from data, which is computationally expensive due to the large search space of DCs. To tackle this challenging task, we present a novel algorithm to efficiently discover DCs: DCFinder. The algorithm combines data structures called position list indexes with techniques based on predicate selectivity to efficiently validate DC candidates. Because the available data often contain errors, DCFinder is especially designed to discovering approximate DCs, i.e., DCs that may partially hold. Our experimental evaluation uses real and synthetic datasets and shows that DCFinder outperforms all the existing approximate DC discovery algorithms.<\/jats:p>","DOI":"10.14778\/3368289.3368293","type":"journal-article","created":{"date-parts":[[2020,9,11]],"date-time":"2020-09-11T03:17:35Z","timestamp":1599794255000},"page":"266-278","source":"Crossref","is-referenced-by-count":63,"title":["Discovery of approximate (and exact) denial constraints"],"prefix":"10.14778","volume":"13","author":[{"given":"Eduardo H. M.","family":"Pena","sequence":"first","affiliation":[{"name":"Federal University of Technology - Paran\u00e1, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eduardo C.","family":"de Almeida","sequence":"additional","affiliation":[{"name":"Federal University of Paran\u00e1, Curitiba, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Felix","family":"Naumann","sequence":"additional","affiliation":[{"name":"University of Potsdam, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,11]]},"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.1109\/ICDM.2003.1250958"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1632"},{"key":"e_1_2_1_4_1","first-page":"1","volume-title":"International Symposium on Parameterized and Exact Computation (IPEC)","author":"Bl\u00e4sius T.","year":"2016","unstructured":"T. Bl\u00e4sius , T. Friedrich , and M. Schirneck . The parameterized complexity of dependency detection in relational databases . In International Symposium on Parameterized and Exact Computation (IPEC) , pages 6: 1 -- 6 :13, 2016 . T. Bl\u00e4sius, T. Friedrich, and M. Schirneck. The parameterized complexity of dependency detection in relational databases. In International Symposium on Parameterized and Exact Computation (IPEC), pages 6:1--6:13, 2016."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/3157794.3157800"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2015.2472010"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453980"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536258.2536262"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544847"},{"key":"e_1_2_1_10_1","first-page":"409","volume-title":"Proceedings of the International Conference on Extending Database Technology (EDBT)","author":"Consonni C.","year":"2019","unstructured":"C. Consonni , P. Sottovia , A. Montresor , and Y. Velegrakis . Discovering order dependencies through order compatibility . In Proceedings of the International Conference on Extending Database Technology (EDBT) , pages 409 -- 420 , 2019 . C. Consonni, P. Sottovia, A. Montresor, and Y. Velegrakis. Discovering order dependencies through order compatibility. In Proceedings of the International Conference on Extending Database Technology (EDBT), pages 409--420, 2019."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594540"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2854006.2854008"},{"key":"e_1_2_1_13_1","volume-title":"Conditional functional dependencies for capturing data inconsistencies. ACM Transactions on Database Systems (TODS), 33(2):6:1--6:48","author":"Fan W.","year":"2008","unstructured":"W. Fan , F. Geerts , X. Jia , and A. Kementsietsidis . Conditional functional dependencies for capturing data inconsistencies. ACM Transactions on Database Systems (TODS), 33(2):6:1--6:48 , 2008 . W. Fan, F. Geerts, X. Jia, and A. Kementsietsidis. Conditional functional dependencies for capturing data inconsistencies. ACM Transactions on Database Systems (TODS), 33(2):6:1--6:48, 2008."},{"key":"e_1_2_1_14_1","volume-title":"Determining the currency of data. ACM Transactions on Database Systems (TODS), 37(4):25:1--25:46","author":"Fan W.","year":"2012","unstructured":"W. Fan , F. Geerts , and J. Wijsen . Determining the currency of data. ACM Transactions on Database Systems (TODS), 37(4):25:1--25:46 , 2012 . W. Fan, F. Geerts, and J. Wijsen. Determining the currency of data. ACM Transactions on Database Systems (TODS), 37(4):25:1--25:46, 2012."},{"key":"e_1_2_1_15_1","volume-title":"Interestingness measures for data mining: A survey. ACM Computing Surveys, 38(3)","author":"Geng L.","year":"2006","unstructured":"L. Geng and H. J. Hamilton . Interestingness measures for data mining: A survey. ACM Computing Surveys, 38(3) , 2006 . L. Geng and H. J. Hamilton. Interestingness measures for data mining: A survey. ACM Computing Surveys, 38(3), 2006."},{"key":"e_1_2_1_16_1","volume-title":"Discovering all most specific sentences. ACM Transactions on Database Systems (TODS), 28(2):140--174","author":"Gunopulos D.","year":"2003","unstructured":"D. Gunopulos , R. Khardon , H. Mannila , S. Saluja , H. Toivonen , and R. S. Sharma . Discovering all most specific sentences. ACM Transactions on Database Systems (TODS), 28(2):140--174 , 2003 . D. Gunopulos, R. Khardon, H. Mannila, S. Saluja, H. Toivonen, and R. S. Sharma. Discovering all most specific sentences. ACM Transactions on Database Systems (TODS), 28(2):140--174, 2003."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732240.2732248"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/42.2.100"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000045"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00028-U"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/3192965.3192968"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00506-9"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/2994509.2994519"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.197"},{"key":"e_1_2_1_25_1","volume-title":"Scalable data exchange with functional dependencies. PVLDB, 3(1--2):105--116","author":"Marnette B.","year":"2010","unstructured":"B. Marnette , G. Mecca , and P. Papotti . Scalable data exchange with functional dependencies. PVLDB, 3(1--2):105--116 , 2010 . B. Marnette, G. Mecca, and P. Papotti. Scalable data exchange with functional dependencies. PVLDB, 3(1--2):105--116, 2010."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/645504.656418"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824086"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/2794367.2794377"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915203"},{"key":"e_1_2_1_30_1","first-page":"342","volume-title":"Proceedings of the International Conference on Extending Database Technology (EDBT)","author":"Papenbrock T.","year":"2017","unstructured":"T. Papenbrock and F. Naumann . Data-driven schema normalization . In Proceedings of the International Conference on Extending Database Technology (EDBT) , pages 342 -- 353 , 2017 . T. Papenbrock and F. Naumann. Data-driven schema normalization. In Proceedings of the International Conference on Extending Database Technology (EDBT), pages 342--353, 2017."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-98809-2_4"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-10928-8_33"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137631"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-018-0510-0"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the ACM SIGMOD Workshop on the Web and Databases (WebDB)","author":"Wang D. Z.","year":"2009","unstructured":"D. Z. Wang , X. L. Dong , A. D. Sarma , M. J. Franklin , and A. Y. Halevy . Functional dependency generation and applications in pay-as-you-go data integration systems . In Proceedings of the ACM SIGMOD Workshop on the Web and Databases (WebDB) , 2009 . D. Z. Wang, X. L. Dong, A. D. Sarma, M. J. Franklin, and A. Y. Halevy. Functional dependency generation and applications in pay-as-you-go data integration systems. In Proceedings of the ACM SIGMOD Workshop on the Web and Databases (WebDB), 2009."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342626"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3368289.3368293","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:40:57Z","timestamp":1672220457000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3368289.3368293"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,11]]}},"alternative-id":["10.14778\/3368289.3368293"],"URL":"https:\/\/doi.org\/10.14778\/3368289.3368293","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2019,11]]}}}