  Dependencies have played a significant role in database design for many
years. They have also been shown to be useful in query optimization. In this
paper, we discuss dependencies between lexicographically ordered sets of
tuples. We introduce formally the concept of order dependency and present a set
of axioms (inference rules) for them. We show how query rewrites based on these
axioms can be used for query optimization. We present several interesting
theorems that can be derived using the inference rules. We prove that
functional dependencies are subsumed by order dependencies and that our set of
axioms for order dependencies is sound and complete.
