Discovery of Band Order Dependencies

Abstract

We introduce band ODs to model the semantics ofattributes that are monotonically related with small variationswithout there being an intrinsic violation of semantics. Tomake band ODs relevant to real-world applications, we makethem less strict to holdapproximatelywith some exceptions andconditionallyon subsets of the data with a mix of ascendingand descending directions. Formulating integrity constraintsmanually requires domain expertise, is prone to human errors,and time consuming. Thus, we study the problem of automaticabcOD discovery. We propose an algorithm that utilizes thenotion of a longest monotonic band (LMB) to identify longestsubsequences of tuples that satisfy a band OD. We formulate theabcOD discovery problem as a constraint optimization problem,and devise a dynamic programming algorithm that determinesthe optimal solution in polynomial time (super-cubic complexity).To further optimize the performance over large datasets, weadapt the algorithm to consider pieces (contiguous sequencesof tuples) in a greedy fashion. This improves the performanceby orders-of-magnitude without sacrificing precision in practice.We show that for unidirectional abcODs, with only ascending ordescending orderings, our pieces-based algorithm is guaranteedto find the optimal solution. Finally, we perform a thoroughexperimental evaluation of our techniques over real-world andsynthetic datasets.