Dependencies have played a significant role in database design formany years. They have also been shown to be useful in queryoptimization. In this paper, we discuss dependencies betweenlexicographically ordered sets of tuples. We introduce formallythe concept of order dependency and present a set of axioms(inference rules) for them. We show how query rewrites based onthese axioms can be used for query optimization. We presentseveral interesting theorems that can be derived using theinference rules. We prove that functional dependencies aresubsumed by order dependencies and that our set of axioms fororder dependencies is sound and complete.

Download paper in PDF format.

The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.