Introduction

Ordered attributes, such as timestamps and numbers, are common in business data. Order Dependencies (ODs) capture monotonic relationships among such attributes. For instance, Table 1 shows employee tax records in which tax is calculated as a percentage (perc) of salary (sal). The OD sal orders perc holds: if we sort the table by salary, it is also sorted by percentage. Similarly, sal orders grp, subg: if we sort the table by salary, it is also sorted by group with ties broken by subgroup. With interest in data analytics at an all-time high, ODs can improve the consistency dimension of data quality and query optimization [4,[7][8][9]. ODs can describe business rules (data profiling); and their violations can point out possible data errors. Furthermore, query optimizers can use ODs to eliminate costly operators such as joins and sorts: ordered streams between query operators can exploit available indexes, enable pipelining, and eliminate intermediate partitioning steps. Finally, ODs subsume Function Dependencies (FDs) as any FD can be mapped to an equivalent OD by prefixing the left-hand-side attributes onto the right-hand-side [6].

It is time consuming to specify integrity constraints manually, motivating the need for their automatic discovery. However, since ODs are naturally expressed with lists rather than sets of attributes (as in the example above), existing solutions have factorial worst-case time complexity in the number of attributes [4]. We describe a more efficient algorithm to discover ODs from data. First, we show that ODs can be expressed with sets of attributes via a polynomial mapping into an equivalent set-based canonical form. Then, we introduce sound and complete axioms for set-based canonical ODs, We say that two tuples, s and t, are equivalent with respect to an attribute set X if s X = t X . Any attribute set X partitions tuples into equivalence classes [3]. We denote the equivalence class of a tuple t ∈ r with respect to a given set X by E(t X ); i.e., E(t

X ) = {s ∈ r | s X = t X }. A partition of r over X is the set of equivalence classes, Π X = {E(t X ) | t ∈ r}. For instance, in Table 1, E(t1 {year} ) = E(t2 {year} ) = E(t3 {year} ) = {t1,

t2, t3} and Π year = {{t1, t2, t3}, {t4, t5, t6}}.

Canonical Mapping and Axioms

Expressing ODs in a natural way relies on lists of attributes; e.g., in Table 1, sal → grp, subg is not the same as sal → subg, grp. In contrast, the order of attributes in an FD does not matter. However, the list representation leads to high complexity when discovering ODs [4]. Thus, we provide a polynomial mapping of list-based ODs into equivalent set-based canonical ODs [5,6,10]. The mapping allows us to develop an efficient OD discovery algorithm that traverses a much smaller set-containment lattice rather than the list-containment lattice used in [4].

The mapping presented in Theorem 1 (below) converts a list-based OD into canonical set-based ODs of two types. First, an attribute A is a constant within each equivalence class with respect to a set of attributes X , denoted as X : [ ] → A, if X → X A for any permutation X of X (note that X functionally determines Y iff X → XY, for any list X over the attributes of X and any list Y over the attributes of Y [6]). Second, two attributes, A and B, are order-compatible within each equivalence class with respect to the set of attributes X , denoted as X : A ∼ B, if X A ∼ X B. The set X is called a context. For example, in Table 1, bin is a constant in the context of pos, written as {pos}: We present a sound and complete set-based axiomatization for ODs in Fig. 2 [6]. The set-based axioms allow us to design effective pruning rules for our OD discovery algorithm. For example, OD X ] → A is trivial if A ∈ X by Reflexivity (see also Example 2).

1. Reflexivity X : [ ] → A, ∀A ∈ X 2. Identity X : A ∼ A 3. Commutativity X : A ∼ B X : B ∼ A 4. Strengthen X :[ ] → A X A:[ ] → B X :[ ] → B 5. Propagate X :[ ] → A X : A ∼ B 6. Augmentation-I X :[ ] → A ZX :[ ] → A 7. Augmentation-II X : A ∼ B ZX : A ∼ B 8. Chain X : A ∼ B1 ∀ i∈[1,n−1] ,X : Bi ∼ Bi+1 X : Bn ∼ C ∀ i∈[1,n] ,X Bi : A ∼ C X : A ∼ C

Theorem 2. The axiomatization for canonical ODs in Fig. 2 is sound and complete.

Discovery Algorithm

Given the mapping of a list-based OD into equivalent set-based ODs, we present an algorithm, named FASTOD, that efficiently discovers a complete and minimal set of set-based ODs over a given relation instance. In contrast, the OD discovery algorithm from [4] traverses a lattice of all possible lists of attributes, which leads to factorial time complexity. FASTOD starts the search from singleton sets of attributes and works its way to larger attribute sets through a set-containment lattice (as in Figure 1), level by level (l = 0, 1, . . . ). When the algorithm is processing an attribute set X , it verifies ODs of the form X \ A:[ ] → A (let X \ A be shorthand for X \ {A}, where A ∈ X ) and X \ {A, B}: A ∼ B, where A, B ∈ X and A = B. Furthermore, an OD X \

A:[ ] → A should be minimal, that is, Y ⊂ X such that Y \ A:[ ] → A is valid.

The algorithm maintains information about minimal ODs, in the form of X \A:[ ] → A, in the candidate set C + c (X ) [3] (as ODs subsume FDs [7,9]), where

C + c (X ) = {A ∈ R | ∀ B∈X X \ {A, B}:[ ] → B does not hold}. Similarly, it stores information about minimal ODs in the form of X \ {A, B}: A ∼ B, in the candidate set C + s (X ), where C + s (X ) = {{A, B} ∈ X 2 | A = B and ∀ C∈X X \ {A, B, C}: A ∼ B does not hold, and ∀ C∈X X \ {A, B, C}:[ ] → C does not hold}.

The following lemmas can be used to prune the search space:

Lemma 1. An OD X \ A:[ ] → A, where A ∈ X , is minimal iff ∀ B∈X A ∈ C + c (X \ B). Lemma 2. An OD X \ {A, B}: A ∼ B, where A, B ∈ X and A = B, is minimal iff ∀ C∈X \{A,B} {A, B} ∈ C + s (X \ C), and A ∈ C + c (X \ B) and B ∈ C + c (X \ A).

According to Lemma 1, we do not need to check

X \ A:[ ] → A if A / ∈ X B∈X C + c (X \ B)

, and based on Lemma 2, we do not need to consider X \ {A, B}:

A ∼ B if A / ∈ C + c (X \ B) or B / ∈ C + c (X \ A).

Moreover, according to Lemma 3, we can delete nodes from the lattice under the following conditions: Note that while we provide theoretical guarantees for FASTOD to find a complete set of ODs, the ORDER algorithm [4] is not complete. Theorem 3. The FASTOD algorithm computes a complete and minimal set of ODs.

In [10], we extend our algorithm to discover bidirectional ODs, which allow a mix of ascending and descending (desc) orders. For example, a student with an alphabetically lower letter grade has a higher percentage grade than another student. We develop additional pruning rules and show that efficiency of discovery of bidirectional ODs remains the same as for one-directional ODs.

We experimentally compare FASTOD with previous approaches ( ORDER [4]). Our algorithm can be orders of magnitude faster. For instance, on the flight dataset from http://metanome.de with 1K tuples and 20 attributes, FASTOD finishes the computation in less than 1 second, whereas ORDER did not terminate after 5 hours. Moreover, FASTOD's candidate sets do not increase in size during the execution of the algorithm (unlike ORDER) because of the concise candidate representation (e.g., many ODs that are considered minimal by ORDER are found to be redundant by our algorithm).

Finally, in [2], we show that a recent approach to OD discovery called OCDDIS-COVER in Consonni et al. [1] is incorrect. We show that their claim of completeness of OD discovery is not true. Built upon their incorrect claim, OCDDISCOVER's pruning rules are overly aggressive, and prune parts of the search space that contain legitimate ODs. This is the reason their approach appears to be "faster" in practice than our FAS-TOD discovery algorithm despite being significantly worse in asymptotic complexity. Finally, we show that Consonni et al. [1] misinterpret our set-based canonical form for ODs, leading to an incorrect claim that our FASTOD implementation has an error.

Conclusions

We presented an efficient algorithm for discovering ODs. The technical innovation that made our algorithm possible is a novel mapping into a set-based canonical form and an axiomatization for set-based canonical ODs. In future work, we plan to study conditional ODs that hold over portions of data.