Effective and Complete Discovery of Order Dependencies via Set-based Axiomatization
Preprint
Abstract
Integrity constraints (ICs) provide a valuable tool for expressing and enforcing application semantics. However, formulating constraints manually requires domain expertise, is prone to human errors, and may be excessively time consuming, especially on large datasets. Hence, proposals for automatic discovery have been made for some classes of ICs, such as functional dependencies (FDs), and recently, order dependencies (ODs). ODs properly subsume FDs, as they can additionally express business rules involving order; e.g., an employee never has a higher salary while paying lower taxes compared with another employee. We address the limitations of prior work on OD discovery which has factorial complexity in the number of attributes, is incomplete (i.e., it does not discover valid ODs that cannot be inferred from the ones found) and is not concise (i.e., it can result in "redundant" discovery and overly large discovery sets). We improve significantly on complexity, offer completeness, and define a compact canonical form. This is based on a novel polynomial mapping to a canonical form for ODs, and a sound and complete set of axioms (inference rules) for canonical ODs. This allows us to develop an efficient set-containment, lattice-driven OD discovery algorithm that uses the inference rules to prune the search space. Our algorithm has exponential worst-case time complexity in the number of attributes and linear complexity in the number of tuples. We prove that it produces a complete, minimal set of ODs (i.e., minimal with regards to the canonical representation). Finally, using real and synthetic datasets, we experimentally show orders-of-magnitude performance improvements over the current state-of-the-art algorithm and demonstrate effectiveness of our techniques.Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Efficient order dependency detectionThe VLDB Journal, 2015
- Combining quantitative and logical data cleaningProceedings of the VLDB Endowment, 2015
- Scaling up copy detection2015
- Expressiveness and complexity of order dependenciesProceedings of the VLDB Endowment, 2013
- Detecting and exploiting near-sortedness for efficient relational query evaluation2011
- Predicate Derivation and Monotonicity Detection in DB2 UDB2005
- Efficient discovery of functional and approximate dependencies using partitions2002
- An extension of the relational data model to incorporate ordered domainsACM Transactions on Database Systems, 2001
- Order dependency in the relational modelTheoretical Computer Science, 1983
- Computational problems related to the design of normal form relational schemasACM Transactions on Database Systems, 1979