Most real-world data come with explicitly defined domain orders, e.g., lexicographic for strings. Our goal is to discover implicit domain orders that we do not already know, e.g., that the order of months in the Chinese Lunar calendar is Corner \(\prec \) Apricot \(\prec \) Peach, and so forth. We do so through order dependencies. We enumerate tractable special cases and proceed toward the most general case, which we prove is NP-complete. We next consider approximate implicit orders, ones that exist with some exceptions, and prove that all non-trivial cases are NP-complete. We show that the NP-complete cases nevertheless can be effectively handled by a SAT solver. We then devise an interestingness measure to rank the discovered approximate implicit domain orders. Based on experiments with real-world data, we establish the efficacy of our algorithms and the utility of the discovered approximate domain orders.
