{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T02:12:01Z","timestamp":1772676721420,"version":"3.50.1"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,8,16]],"date-time":"2021-08-16T00:00:00Z","timestamp":1629072000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,8,16]],"date-time":"2021-08-16T00:00:00Z","timestamp":1629072000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Hasso-Plattner-Institut f\u00fcr Digital Engineering gGmbH"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2022,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Bidirectional order dependencies (bODs) capture order relationships between lists of attributes in a relational table. They can express that, for example, sorting books by <jats:italic>publication date<\/jats:italic> in ascending order also sorts them by <jats:italic>age<\/jats:italic> in descending order. The knowledge about order relationships is useful for many data management tasks, such as query optimization, data cleaning, or consistency checking. Because the bODs of a specific dataset are usually not explicitly given, they need to be discovered. The discovery of all minimal bODs (in set-based canonical form) is a task with exponential complexity in the number of attributes, though, which is why existing bOD discovery algorithms cannot process datasets of practically relevant size in a reasonable time. In this paper, we propose the <jats:italic>distributed<\/jats:italic> bOD discovery algorithm DISTOD, whose execution time scales with the available hardware. DISTOD is a scalable, robust, and elastic bOD discovery approach that combines efficient pruning techniques for bOD candidates in set-based canonical form with a novel, reactive, and distributed search strategy. Our evaluation on various datasets shows that DISTOD outperforms both single-threaded and distributed state-of-the-art bOD discovery algorithms by up to orders of magnitude; it can, in particular, process much larger datasets.<\/jats:p>","DOI":"10.1007\/s00778-021-00683-4","type":"journal-article","created":{"date-parts":[[2021,8,16]],"date-time":"2021-08-16T17:04:37Z","timestamp":1629133477000},"page":"49-74","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Efficient distributed discovery of bidirectional order dependencies"],"prefix":"10.1007","volume":"31","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6597-9809","authenticated-orcid":false,"given":"Sebastian","family":"Schmidl","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4019-8221","authenticated-orcid":false,"given":"Thorsten","family":"Papenbrock","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,8,16]]},"reference":[{"key":"683_CR1","doi-asserted-by":"crossref","unstructured":"Abadi, D., Madden, S., Ferreira, M.: Integrating compression and execution in column-oriented database systems. In: Proceedings of the International Conference on Management of Data (SIGMOD), pp. 671\u2013682 (2006)","DOI":"10.1145\/1142473.1142548"},{"key":"683_CR2","doi-asserted-by":"crossref","unstructured":"Abedjan, Z., Golab, L., Naumann, F., Papenbrock, T.: Data Profiling. Morgan & Claypool Publishers. ISBN: 978-1-68173-447-7 (2018)","DOI":"10.2200\/S00878ED1V01Y201810DTM052"},{"key":"683_CR3","doi-asserted-by":"crossref","unstructured":"Bayer, R., McCreight, E.: Organization and maintenance of large ordered indices. In: Proceedings of the Workshop on Data Description (SIGFIDET, Now SIGMOD), pp. 107\u2013141 (1970)","DOI":"10.21236\/AD0712079"},{"issue":"3","key":"683_CR4","doi-asserted-by":"publisher","first-page":"311","DOI":"10.14778\/3157794.3157800","volume":"11","author":"T Bleifu\u00df","year":"2017","unstructured":"Bleifu\u00df, T., Kruse, S., Naumann, F.: Efficient denial constraint discovery with hydra. Proc. VLDB Endow. 11(3), 311\u2013323 (2017)","journal-title":"Proc. VLDB Endow."},{"key":"683_CR5","unstructured":"Consonni, C., Montresor, A., Sottovia, P., Velegrakis, Y.: Discovering order dependencies through order compatibility. In: Proceedings of the International Conference on Extending Database Technology (EDBT), pp. 409\u2013420 (2019)"},{"key":"683_CR6","doi-asserted-by":"crossref","unstructured":"Dong, J., Hull, R.: Applying approximate order dependency to reduce indexing space. In: Proceedings of the International Conference on Management of Data (SIGMOD), pp. 119\u2013127 (1982)","DOI":"10.1145\/582353.582375"},{"issue":"1","key":"683_CR7","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0304-3975(83)90084-1","volume":"26","author":"S Ginsburg","year":"1983","unstructured":"Ginsburg, S., Hull, R.: Order dependency in the relational model. Theor. Comput. Sci. 26(1), 149\u2013195 (1983)","journal-title":"Theor. Comput. Sci."},{"key":"683_CR8","unstructured":"Hewitt, C., Bishop, P., Steiger, R.: A universal modular ACTOR formalism for artificial intelligence. In: Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp. 235\u2013245 (1973)"},{"key":"683_CR9","unstructured":"Huhtala, Y., K\u00e4rkk\u00e4inen, J., Porkka, P., Toivonen, H.: Efficient discovery of functional and approximate dependencies using partitions. In: Proceedings of the International Conference on Data Engineering (ICDE), pp. 392\u2013401 (1998)"},{"key":"683_CR10","doi-asserted-by":"crossref","unstructured":"Huhtala, Y., K\u00e4rkk\u00e4inen, J., Porkka, P., Toivonen, H.: Tane: an efficient algorithm for discovering functional and approximate dependencies. Comput. J. 42(2), 100\u2013111 (1999)","DOI":"10.1093\/comjnl\/42.2.100"},{"key":"683_CR11","doi-asserted-by":"crossref","unstructured":"Ilyas, I.F., Chu, X.: Trends in cleaning relational data: consistency and deduplication. Found. Trends Databases 5(4), 281\u2013393 (2015)","DOI":"10.1561\/1900000045"},{"key":"683_CR12","doi-asserted-by":"crossref","unstructured":"Jin, Y., Zhu, L., Tan, Z.: Efficient bidirectional order dependency discovery. In: Proceedings of the International Conference on Data Engineering (ICDE), pp. 61\u201373 (2020)","DOI":"10.1109\/ICDE48307.2020.00013"},{"key":"683_CR13","unstructured":"Karegar, R., Godfrey, P., Golab, L., Kargar, M., Srivastava, D., Szlichta, J.: Efficient discovery of approximate order dependencies. arXiv: 2101.02174 [cs] (2021)"},{"key":"683_CR14","unstructured":"Kruse, S., Papenbrock, T., Naumann, F.: Scaling out the discovery of inclusion dependencies. In: Proceedings of the Conference on Datenbanksysteme in Business, Technologie Und Web (BTW), pp. 445\u2013454 (2015)"},{"issue":"2","key":"683_CR15","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/s00778-015-0412-3","volume":"25","author":"P Langer","year":"2016","unstructured":"Langer, P., Naumann, F.: Efficient order dependency detection. VLDB J 25(2), 223\u2013241 (2016)","journal-title":"VLDB J"},{"issue":"2","key":"683_CR16","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1109\/TKDE.2010.197","volume":"24","author":"J Liu","year":"2012","unstructured":"Liu, J., Li, J., Liu, C., Chen, Y.: Discover dependencies from data\u2014a review. IEEE Trans. Knowl. Data Eng. 24(2), 251\u2013264 (2012)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"683_CR17","unstructured":"McSherry, F., Isard, M., Murray, D.G.: Scalability! But at what cost? In: Proceedings of the USENIX Conference on Hot Topics in Operating Systems (HotOS), p. 14 (2015)"},{"key":"683_CR18","unstructured":"Papenbrock, T., Naumann, F.: A hybrid approach for efficient unique column combination discovery. In: Proceedings of the Conference Datenbanksysteme in Business, Technologie Und Web (BTW), pp. 195\u2013204 (2017)"},{"key":"683_CR19","doi-asserted-by":"crossref","unstructured":"Papenbrock, T., Naumann, F.: A hybrid approach to functional dependency discovery. In: Proceedings of the International Conference on Management of Data (SIGMOD), pp. 821\u2013833 (2016)","DOI":"10.1145\/2882903.2915203"},{"issue":"10","key":"683_CR20","doi-asserted-by":"publisher","first-page":"12","DOI":"10.14778\/2794367.2794377","volume":"8","author":"T Papenbrock","year":"2015","unstructured":"Papenbrock, T., Ehrlich, J., Marten, J., Neubert, T., Rudolph, J.-P.: Functional dependency discovery: an experimental evaluation of seven algorithms. Proc. VLDB Endow. 8(10), 12 (2015)","journal-title":"Proc. VLDB Endow."},{"key":"683_CR21","doi-asserted-by":"crossref","unstructured":"Saxena, H., Golab, L., Ilyas, I.F.: Distributed discovery of functional dependencies. In: Proceedings of the International Conference on Data Engineering (ICDE), pp. 1590\u20131593 (2019)","DOI":"10.1109\/ICDE.2019.00149"},{"issue":"11","key":"683_CR22","doi-asserted-by":"publisher","first-page":"1624","DOI":"10.14778\/3342263.3342638","volume":"12","author":"H Saxena","year":"2019","unstructured":"Saxena, H., Golab, L., Ilyas, I.F.: Distributed implementations of dependency discovery algorithms. Proc. VLDB Endow. 12(11), 1624\u20131636 (2019)","journal-title":"Proc. VLDB Endow."},{"key":"683_CR23","doi-asserted-by":"crossref","unstructured":"Selinger, P.G., Astrahan, M.M., Chamberlin, D.D., Lorie, R.A., Price, T.G.: Access path selection in a relational database management system. In: Proceedings of the International Conference on Management of Data (SIGMOD), pp. 23\u201334 (1979)","DOI":"10.1145\/582095.582099"},{"key":"683_CR24","unstructured":"Lightbend Inc. 2020. Akka: build powerful reactive, concurrent, and distributed applications more easily. Version 2.6.3 (2020)"},{"issue":"4","key":"683_CR25","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1007\/s00778-018-0510-0","volume":"27","author":"J Szlichta","year":"2018","unstructured":"Szlichta, J., Godfrey, P., Golab, L., Kargar, M., Srivastava, D.: Effective and complete discovery of bidirectional order dependencies via set-based axioms. VLDB J. 27(4), 573\u2013591 (2018)","journal-title":"VLDB J."},{"issue":"7","key":"683_CR26","doi-asserted-by":"publisher","first-page":"721","DOI":"10.14778\/3067421.3067422","volume":"10","author":"J Szlichta","year":"2017","unstructured":"Szlichta, J., Godfrey, P., Golab, L., Kargar, M., Srivastava, D.: Effective and complete discovery of order dependencies via set-based axiomatization. Proc. VLDB Endow. 10(7), 721\u2013732 (2017)","journal-title":"Proc. VLDB Endow."},{"key":"683_CR27","unstructured":"Szlichta, J., Godfrey, P., Golab, L., Kargar, M., Srivastava, D.: Erratum for discovering order dependencies through order compatibility (EDBT 2019). In: Proceedings of the International Conference on Extending Database Technology (EDBT), pp. 659\u2013663 (2020)"},{"issue":"14","key":"683_CR28","doi-asserted-by":"publisher","first-page":"1858","DOI":"10.14778\/2556549.2556568","volume":"6","author":"J Szlichta","year":"2013","unstructured":"Szlichta, J., Godfrey, P., Gryz, J., Zuzarte, C.: Expressiveness and complexity of order dependencies. Proc. VLDB Endow. 6(14), 1858\u20131869 (2013)","journal-title":"Proc. VLDB Endow."},{"key":"683_CR29","doi-asserted-by":"crossref","unstructured":"Szlichta, J., Godfrey, P., Gryz, J.: Fundamentals of order dependencies. Proc. VLDB Endow. 5(11), 1220\u20131231 (2012)","DOI":"10.14778\/2350229.2350241"},{"key":"683_CR30","unstructured":"The Apache Software Foundation: Apache Flink - Stateful Computations over Data Streams (2019). Retrieved 08\/03\/2020 from https:\/\/flink.apache.org\/"},{"key":"683_CR31","unstructured":"The Apache Software Foundation: Apache Spark\u2014unified analytics engine for big data (2018). Retrieved 08\/03\/2020 from https:\/\/spark.apache.org\/"},{"key":"683_CR32","unstructured":"Vernon, V.: (2015). Reactive Messaging Patterns with the Actor Model: Applications and Integration in Scala and Akka. Addison-Wesley Professional. ISBN: 978-0-13-384690-4"},{"issue":"12","key":"683_CR33","doi-asserted-by":"publisher","first-page":"2663","DOI":"10.1109\/TPDS.2019.2925014","volume":"30","author":"G Zhu","year":"2019","unstructured":"Zhu, G., Wang, Q., Tang, Q., Rong, G., Yuan, C., Huang, Y.: Efficient and Scalable Functional Dependency Discovery on Distributed Data-Parallel Platforms. IEEE Trans. Parallel Distrib. Syst. 30(12), 2663\u20132676 (2019)","journal-title":"IEEE Trans. Parallel Distrib. Syst."}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-021-00683-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00778-021-00683-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-021-00683-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,28]],"date-time":"2022-01-28T11:07:50Z","timestamp":1643368070000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00778-021-00683-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,16]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1]]}},"alternative-id":["683"],"URL":"https:\/\/doi.org\/10.1007\/s00778-021-00683-4","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,8,16]]},"assertion":[{"value":"27 August 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 April 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 July 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 August 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}