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 di cult, 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. We propose a new algorithm Hydra, 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. Tobias Bleifuß, Sebastian Kruse, and Felix Naumann. E cient Denial Constraint Discovery with Hydra. PVLDB, 11(3): xxxx-323, 2017. DOI: 10.14778/3157794.3157800 The research area of data profiling [1] has borne several e cient algorithms to discover structural properties of datasets. In particular, the discovery of functional dependencies (FDs) [13] and unique column combinations (UCCs) [8] have attracted great attention. Lately, also order dependencies (ODs) [15] have been in focus. Each of these integrity constraints (ICs) serves di↵erent applications, such as schema normalization (FDs), key discovery (UCCs), and query optimization (ODs). Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Articles from this volume were invited to present their results at The 44th International Conference on Very Large Data Bases, August 2018, Rio de Janeiro, Brazil. However, this state of the art su↵ers from two major problems. First, each type of IC is of strongly limited expressiveness. The types of rules one can observe in actual datasets are much greater, though, as we demonstrate later in this section. This imbalance is accounted for by proposing new IC types every now and then. Second, the di↵erent ICs are logically isolated. That is, to reason on the interaction among ICs, e.g., for data cleaning, one has to explicitly provide interaction rules. Not only is this unwieldy -it also does not scale well with the number of considered IC types, but DCs can bridge that gap [4, 7] . Then, why are there so many di↵erent ICs rather than a single, general IC capable of avoiding such problems? A major reason is plain e ciency. For that matter, discovering FDs, UCCs, or ODs alone is already computationally expensive and the respective discovery algorithms employ highly specific data structures and pruning rules to operate e ciently. That being said, being able to e ciently discover more general ICs could solve aforementioned problems and would thus be very valuable. To this end, we propose Hydra, an e cient algorithm to discover all valid denial constraints (DCs) in a given relational dataset. But let us first define DCs and show that their expressiveness goes beyond UCCs, FDs, and ODs. In few words, a DC defines a set of predicates on n tuples. A relational instance satisfies that DC if for any n distinct tuples of that instance at least one predicate is violated. In the following, we set n = 2 and refer to the two involved tuples as t and t 0 . As we show by examples below, DCs over two tuples are su cient to express all of the aforementioned integrity constraints. For reasons of rapidly increasing computational complexity for n > 2, as well as questionable gains, related work applies the same restriction [3] .
Our approach is also related to the discovery of denial constraints in relational tables (denial constraints are generalizations of common constraints like functional dependencies) REF .
Efficient Denial Constraint Discovery with Hydra
PVLDB
PVLDB
Computer Science