{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T12:43:51Z","timestamp":1780058631818,"version":"3.54.0"},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2012,7]]},"abstract":"<jats:p>\n            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\n            <jats:italic>order dependency<\/jats:italic>\n            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.\n          <\/jats:p>","DOI":"10.14778\/2350229.2350241","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"1220-1231","source":"Crossref","is-referenced-by-count":31,"title":["Fundamentals of order dependencies"],"prefix":"10.14778","volume":"5","author":[{"given":"Jaroslaw","family":"Szlichta","sequence":"first","affiliation":[{"name":"York University, Toronto, Canada and IBM Center for Advanced Studies, Toronto, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Parke","family":"Godfrey","sequence":"additional","affiliation":[{"name":"York University, Toronto, Canada and IBM Center for Advanced Studies, Toronto, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jarek","family":"Gryz","sequence":"additional","affiliation":[{"name":"York University, Toronto, Canada and IBM Center for Advanced Studies, Toronto, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2012,7]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"580","volume-title":"Proceedings of the IMP Congress","author":"Armstrong W. W.","year":"1974","unstructured":"W. W. Armstrong , Dependency structures of data base relationships . In Proceedings of the IMP Congress , pages 580 -- 583 , 1974 . W. W. Armstrong, Dependency structures of data base relationships. In Proceedings of the IMP Congress, pages 580--583, 1974."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/320493.320489"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/320064.320066"},{"key":"e_1_2_1_4_1","first-page":"687","volume-title":"VLDB","author":"Cheng Q.","year":"1999","unstructured":"Q. Cheng , J. Gryz ., F. Koo , T. Y. C. Leung , L. Liu , X. Qian and K. B. Schiefer . Implementation of two semantic query optimization techniques in DB2 Universal Database . In VLDB , pages 687 -- 698 , 1999 . Q. Cheng, J. Gryz., F. Koo, T. Y. C. Leung, L. Liu, X. Qian and K. B. Schiefer. Implementation of two semantic query optimization techniques in DB2 Universal Database. In VLDB, pages 687--698, 1999."},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1017\/CBO9780511809088","volume-title":"Introduction to lattices and order","author":"Davey B. A.","year":"2002","unstructured":"B. A. Davey and H. A. Priestley . Introduction to lattices and order , vol. 2 . Cambridge University Press , pages 1 -- 298 , 2002 . B. A. Davey and H. A. Priestley. Introduction to lattices and order, vol. 2. Cambridge University Press, pages 1--298, 2002."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/582353.582375"},{"key":"e_1_2_1_7_1","volume-title":"XP2 Workshop on Relational Database Theory","author":"Ginsburg S.","year":"1981","unstructured":"S. Ginsburg and R. Hull . Ordered attribute domains in the relational model . In XP2 Workshop on Relational Database Theory , 1981 . S. Ginsburg and R. Hull. Ordered attribute domains in the relational model. In XP2 Workshop on Relational Database Theory, 1981."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90084-1"},{"key":"e_1_2_1_9_1","first-page":"58","volume-title":"BTW","author":"Graefe G.","year":"2003","unstructured":"G. Graefe . Executing nested queries . In BTW , pages 58 -- 77 , 2003 . G. Graefe. Executing nested queries. In BTW, pages 58--77, 2003."},{"key":"e_1_2_1_10_1","first-page":"481","volume-title":"VLDB","author":"Guravannavar R.","year":"2005","unstructured":"R. Guravannavar , H. S. Ramanujam , and S. Sudarshan . Optimizing nested queries with parameter sort orders . In VLDB , pages 481 -- 492 , 2005 . R. Guravannavar, H. S. Ramanujam, and S. Sudarshan. Optimizing nested queries with parameter sort orders. In VLDB, pages 481--492, 2005."},{"key":"e_1_2_1_11_1","first-page":"219","volume-title":"The data warehouse toolkit. The complete guide to dimensional modeling","author":"Kimball R.","year":"2002","unstructured":"R. Kimball and M. Ross . The data warehouse toolkit. The complete guide to dimensional modeling , vol. 2 . John Wiley & amp; Sun, pages 219 -- 241 , 2002 . R. Kimball and M. Ross. The data warehouse toolkit. The complete guide to dimensional modeling, vol. 2. John Wiley &amp; Sun, pages 219--241, 2002."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.110"},{"key":"e_1_2_1_13_1","first-page":"279","volume-title":"IDEAS","author":"Ng W.","year":"1999","unstructured":"W. Ng . Lexicographically ordered functional dependencies and their application to temporal relations . In IDEAS , pages 279 -- 287 , 1999 . W. Ng. Lexicographically ordered functional dependencies and their application to temporal relations. In IDEAS, pages 279--287, 1999."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0306-4379(99)00031-9"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/502030.502033"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/582095.582099"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233320"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1951365.1951424"},{"key":"e_1_2_1_19_1","first-page":"168","volume-title":"AMW","author":"Szlichta J.","year":"2012","unstructured":"J. Szlichta , P. Godfrey and J. Gryz . Chasing polarized order dependencies . In AMW , pages 168 -- 179 , 2012 . J. Szlichta, P. Godfrey and J. Gryz. Chasing polarized order dependencies. In AMW, pages 168--179, 2012."},{"key":"e_1_2_1_20_1","first-page":"378","volume-title":"Computer Science Press","author":"Ullman J. D.","year":"1988","unstructured":"J. D. Ullman . Principles of database and knowledge-base systems, vol. 1 . Computer Science Press , pages 378 -- 379 , 1988 . J. D. Ullman. Principles of database and knowledge-base systems, vol. 1. Computer Science Press, pages 378--379, 1988."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2350229.2350241","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:26:29Z","timestamp":1672226789000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2350229.2350241"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7]]},"references-count":20,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2012,7]]}},"alternative-id":["10.14778\/2350229.2350241"],"URL":"https:\/\/doi.org\/10.14778\/2350229.2350241","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2012,7]]}}}