{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,27]],"date-time":"2026-09-27T13:56:01Z","timestamp":1790517361781,"version":"4.1.0"},"reference-count":16,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2017,11]]},"abstract":"Denial constraints (DCs) are a generalization of many other integrity constraints (ICs) widely used in databases, such as key constraints, functional dependencies, or order dependencies. Therefore, they can serve as a unified reasoning framework for all of these ICs and express business rules that cannot be expressed by the more restrictive IC types. The process of formulating DCs by hand is difficult, because it requires not only domain expertise but also database knowledge, and due to DCs' inherent complexity, this process is tedious and error-prone. Hence, an automatic DC discovery is highly desirable: we search for all valid denial constraints in a given database instance. However, due to the large search space, the problem of DC discovery is computationally expensive.<\/jats:p>\n \n We propose a new algorithm H\n ydra<\/jats:sc>\n , which overcomes the quadratic runtime complexity in the number of tuples of state-of-the-art DC discovery methods. The new algorithm's experimentally determined runtime grows only linearly in the number of tuples. This results in a speedup by orders of magnitude, especially for datasets with a large number of tuples. Hydra can deliver results in a matter of seconds that to date took hours to compute.\n <\/jats:p>","DOI":"10.14778\/3157794.3157800","type":"journal-article","created":{"date-parts":[[2017,12,12]],"date-time":"2017-12-12T13:33:38Z","timestamp":1513085618000},"page":"311-323","source":"Crossref","is-referenced-by-count":65,"title":["Efficient denial constraint discovery with hydra"],"prefix":"10.14778","volume":"11","author":[{"given":"Tobias","family":"Bleifu\u00df","sequence":"first","affiliation":[{"name":"Hasso-Plattner-Institut, Potsdam, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sebastian","family":"Kruse","sequence":"additional","affiliation":[{"name":"Hasso-Plattner-Institut, Potsdam, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Felix","family":"Naumann","sequence":"additional","affiliation":[{"name":"Hasso-Plattner-Institut, Potsdam, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,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.1145\/2983323.2983781"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536258.2536262"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544847"},{"key":"e_1_2_1_5_1","first-page":"305","volume-title":"Proceedings of the International Conference on Extending Database Technology (EDBT)","author":"Ehrlich J.","year":"2016","unstructured":"J. Ehrlich , M. Roick , L. Schulze , J. Zwiener , T. Papenbrock , and F. Naumann . Holistic data profiling: Simultaneous discovery of various metadata . In Proceedings of the International Conference on Extending Database Technology (EDBT) , pages 305 -- 316 , 2016 . J. Ehrlich, M. Roick, L. Schulze, J. Zwiener, T. Papenbrock, and F. Naumann. Holistic data profiling: Simultaneous discovery of various metadata. In Proceedings of the International Conference on Extending Database Technology (EDBT), pages 305--316, 2016."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1216155.1216159"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536360.2536363"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732240.2732248"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/42.2.100"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/2831360.2831362"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824086"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/2794367.2794377"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915203"},{"key":"e_1_2_1_14_1","first-page":"691","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB)","author":"Sismanis Y.","year":"2006","unstructured":"Y. Sismanis , P. Brown , P. J. Haas , and B. Reinwald . Gordian: Efficient and scalable discovery of composite keys . In Proceedings of the International Conference on Very Large Databases (VLDB) , pages 691 -- 702 , 2006 . Y. Sismanis, P. Brown, P. J. Haas, and B. Reinwald. Gordian: Efficient and scalable discovery of composite keys. In Proceedings of the International Conference on Very Large Databases (VLDB), pages 691--702, 2006."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/3067421.3067422"},{"key":"e_1_2_1_16_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\/3157794.3157800","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T04:37:20Z","timestamp":1672202240000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3157794.3157800"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,11]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,11]]}},"alternative-id":["10.14778\/3157794.3157800"],"URL":"https:\/\/doi.org\/10.14778\/3157794.3157800","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2017,11]]}}}