Bringing Order to Data

Abstract

Integrity constraints (ICs) are widely used in business intelligence to express and enforce application semantics. However, finding ICs manually is time consuming, requires the involvement of domain experts, and is prone to human error. Thus, techniques have been proposed to automatically find a variety of ICs. We propose an algorithm to automatically discover order dependencies (ODs). Prior work on OD discovery has factorial complexity, is not complete, and is not concise. We propose an algorithm that finds a complete set of ODs with exponential worst-case time complexity in the number of attributes and linear complexity in the number of tuples. We experimentally show that our algorithm is orders of magnitude faster than the prior state-of-the-art.

Keywords

• Integrity constraints Order Dependency Axiomatization

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–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, ID yr pos bin sal perc tax grp subg 1 16 sec 1 5K 20% 1K A III 2 16 dev 2 8K 25% 2K C II 3 16 dir 3 10K 30% 3K D I 1 15 sec 1 4K 20% 0.8K A III 2 15 dev 2 6K 25% 1.5K C I 3 15 dir 3 8K 25% 2K C II {A} {A,B} { } {B} {A,C} {A,B,C} {C} {B,C} which lead to optimizations of the OD discovery algorithm by avoiding redundant computation. This allows us to design a fast and effective OD discovery algorithm that has exponential worst-case complexity, O(2jRj), in the number of attributes jRj, and linear complexity in the number of tuples. We note that this short paper is a summary of our published results in [ 5, 6, 10 ]. 2

Order Dependency Discovery

2.1 Preliminaries

Order dependencies (ODs) describe relationships among lexicographical orderings of sets of tuples, as in the SQL order by statement. Let X = [A j T] be a list of attributes, where the attribute A is the head of the list, and the list T is the tail. For two tuples s and t, we write s X t iff sA < tA or (sA = tA and (T = [ ] or s T t)). Given two lists of attributes, X and Y, X 7! Y denotes an OD, read as X orders Y. Table r satisfies X 7! Y iff, for all s; t 2 r, s X t implies s Y t. Moreover, X and Y are order compatible, denoted as X Y iff XY $ YX. (For example, month and week of the year in the calendar are order compatible.)

We say that two tuples, s and t, are equivalent with respect to an attribute set X if sX = tX . Any attribute set X partitions tuples into equivalence classes [ 3 ]. We denote the equivalence class of a tuple t 2 r with respect to a given set X by E (tX ); i.e., E (tX ) = fs 2 r j sX = tX g. A partition of r over X is the set of equivalence classes, X = fE (tX ) j t 2 rg. For instance, in Table 1, E (t1fyearg) = E (t2fyearg) = E (t3fyearg) = ft1; t2; t3g and year = fft1; t2; t3g; ft4; t5; t6gg.

2.2 Canonical Mapping and Axioms

Expressing ODs in a natural way relies on lists of attributes; e.g., in Table 1, sal 7! grp; subg is not the same as sal 7! 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 : [ ] 7! A, if X0 7! X0A for any permutation X0 of X (note that X functionally determines Y iff X 7! 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 X0A X0B. The set X is called a context. For example, in Table 1, bin is a constant in the context of pos, written as fposg: 1. Reflexivity

X : [ ] 7! A, 8A 2 X 2. Identity

X : A A 3. Commutativity

B

A X : A X : B

4. Strengthen

X :[ ] 7! A X A:[ ] 7! B X :[ ] 7! B 5. Propagate X :[ ] 7! A X : A B

6. Augmentation-I

X :[ ] 7! A

ZX :[ ] 7! A 7. Augmentation-II

B X : A ZX : A

B [ ] 7! bin since E (t1fposg) j= [ ] 7! bin, E (t2fposg) j= [ ] 7! bin and E (t3fposg) j= [ ] 7! bin. Also, fyearg: bin salary because E (t1fyearg) j= bin salary and E (t4fyearg) j= bin salary.

Theorem 1. X 7! Y iff 8j, X :[ ] 7! Yj and 8i; j, fX1, .., Xi 1, Y1, .., Yj 1g: Xi Yj .

Example 1. The OD [AB] 7! [CD] is mapped into the following set of canonical ODs: fA; Bg:[ ] 7! C, fA; Bg:[ ] 7! D, fg: A C, fAg: B C, fCg: A D, fA; Cg: B D.

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 :[ ] 7! A is trivial if A 2 X by Reflexivity (see also Example 2).

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

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 n A:[ ] 7! A (let X n A be shorthand for X n fAg, where A 2 X ) and X n fA; Bg: A B, where A, B 2 X and A 6= B. Furthermore, an OD X n A:[ ] 7! A should be minimal, that is, @ Y X such that Y n A:[ ] 7! A is valid.

The algorithm maintains information about minimal ODs, in the form of X nA:[ ] 7! A, in the candidate set Cc+(X ) [ 3 ] (as ODs subsume FDs [ 7, 9 ]), where Cc+(X ) = fA 2 R j 8B2X X n fA; Bg:[ ] 7! B does not holdg. Similarly, it stores information about minimal ODs in the form of X n fA; Bg: A B, in the candidate set Cs+(X ), where Cs+(X ) = ffA; Bg 2 X 2 j A 6= B and 8C2X X n fA; B; Cg: A B does not hold, and 8C2X X n fA; B; Cg:[ ] 7! C does not holdg. The following lemmas can be used to prune the search space: Lemma 1. An OD X n A:[ ] 7! A, where A 2 X , is minimal iff 8B2X A 2 Cc+(X n B). Lemma 2. An OD X n fA; Bg: A B, where A, B 2 X and A 6= B, is minimal iff 8C2X nfA;Bg fA; Bg 2 Cs+(X n C), and A 2 Cc+(X n B) and B 2 Cc+(X n A). According to Lemma 1, we do not need to check X n A:[ ] 7! A if A 2= X TB2X Cc+(X n B), and based on Lemma 2, we do not need to consider X n fA; Bg: A B if A 2= Cc+(X n B) or B 2= Cc+(X n A). Moreover, according to Lemma 3, we can delete nodes from the lattice under the following conditions: Lemma 3. Deleting node X from the lth lattice level, where l output set of minimal ODs if Cc+(X ) = fg and Cs+(X ) = fg. 2, has no effect on the Example 2. Let A:[ ] 7! B, B:[ ] 7! A and fg: A B. Since Cc+(fA; Bg) = fg and Cs+(fA; Bg) as well as l = 2, by the pruning levels rule (Lemma 3), the node fA; Bg is deleted and the node fA; B; Cg is not considered (see Figure 1). This is justified as fABg:[ ] 7! C is not minimal by the Strengthen axiom, fACg:[ ] 7! B is not minimal by Augmentation–I, fBCg:[ ] 7! A is not minimal by Augmentation–I, fCg: A B is not minimal by Augmentation–II, fAg: B C is not minimal by Propagate, and fBg: A C is not minimal by Propagate.

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 OCDDISCOVER 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 FASTOD 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. 3

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.

References

1. Consonni , C. , Sottovia , P. , Montresor , A. , Velegrakis , Y. : Discovering Order Dependencies through Order Compatibility . In: EDBT. pp. 409 - 420 ( 2019 )

2. Godfrey , P. , Golab , L. , Kargar , M. , Srivastava , D. , Szlichta , J.: Errata note: Discovering order dependencies through order compatibility . Technical Report , 5 pages, available at https://arxiv.org/abs/ 1905 . 02010 ( 2019 )

3. Huhtala , Y. , Karkkainen , J. , Porkka , P. , Toivonen , H.: Efficient Discovery of Functional and Approximate Dependencies Using Partitions . In: ICDE. pp. 392 - 401 ( 1998 )

4. Langer , P. , Naumann , F. : Efficient order dependency detection . VLDB J . 25 ( 2 ), 223 - 241 ( 2016 )

5. Mihaylov , A. , Godfrey , P. , Golab , L. , Kargar , M. , Srivastava , D. , Szlichta , J.: FASTOD: bringing order to data . In: 2018 IEEE 34th International Conference on Data Engineering (ICDE) . pp. 1561 - 1564 . IEEE ( 2018 )

6. Szlichta , J. , Godfrey , P. , Golab , L. , Kargar , M. , Srivastava , D. : Effective and Complete Discovery of Order Dependencies via Set-based Axiomatization . PVLDB 10 ( 7 ), 721 - 732 ( 2017 )

7. Szlichta , J. , Godfrey , P. , Gryz , J.: Fundamentals of Order Dependencies. PVLDB , 5 ( 11 ): 1220 - 1231 ( 2012 )

8. Szlichta , J. , Godfrey , P. , Gryz , J. , Ma, W. , Qiu , W. , Zuzarte , C. : Business-Intelligence Queries with Order Dependencies in DB2 . In: EDBT, 750 - 761 ( 2014 )

9. Szlichta , J. , Godfrey , P. , Gryz , J. , Zuzarte , C. : Expressiveness and Complexity of Order Dependencies . PVLDB 6 ( 14 ): 1858 - 1869 ( 2013 )

10. Szlichta , J. , Godfrey , P. , Golab , L. , Kargar , M. , Srivastava , D. : Effective and complete discovery of bidirectional order dependencies via set-based axioms . The VLDB Journal 27 ( 4 ), 573 - 591 ( 2018 )