{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,23]],"date-time":"2026-10-23T23:44:43Z","timestamp":1792799083940,"version":"4.5.0"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,3,23]],"date-time":"2024-03-23T00:00:00Z","timestamp":1711152000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ANID \u2013 Millennium Science Initiative Program \u2013 Code ICN17_002","award":["MCIN\/AEI\/10.13039\/5011000-11033, PID2020-114635RB-I00, MCIN\/AEI\/10.13039\/501100011033, PID2022-141027NB-C21, MCIN\/AEI\/10.13039\/501100011033"],"award-info":[{"award-number":["MCIN\/AEI\/10.13039\/5011000-11033, PID2020-114635RB-I00, MCIN\/AEI\/10.13039\/501100011033, PID2022-141027NB-C21, MCIN\/AEI\/10.13039\/501100011033"]}],"id":[{"id":"https:\/\/ror.org\/01c080z51","id-type":"ROR","asserted-by":"crossref"}]},{"name":"\u201cNext-GenerationEU\u201d\/PRTR","award":["TED2021-129245B-C21, PDC2021-120917-C21"],"award-info":[{"award-number":["TED2021-129245B-C21, PDC2021-120917-C21"]}]},{"name":"GAIN\/ Xunta de Galicia: GRC","award":["ED431C 2021\/53, and CIGUS 2023-2026"],"award-info":[{"award-number":["ED431C 2021\/53, and CIGUS 2023-2026"]}]},{"name":"FONDECYT","award":["1221926"],"award-info":[{"award-number":["1221926"]}],"id":[{"id":"https:\/\/ror.org\/016nafs32","id-type":"ROR","asserted-by":"crossref"}]},{"name":"FONDECYT","award":["1230755"],"award-info":[{"award-number":["1230755"]}],"id":[{"id":"https:\/\/ror.org\/016nafs32","id-type":"ROR","asserted-by":"crossref"}]},{"name":"FONDECYT","award":["1221799"],"award-info":[{"award-number":["1221799"]}],"id":[{"id":"https:\/\/ror.org\/016nafs32","id-type":"ROR","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2024,6,30]]},"abstract":"<jats:p>\n                    We present an indexing scheme for triple-based graphs that supports join queries in worst-case optimal (wco) time within compact space. This scheme, called a\n                    <jats:italic>ring<\/jats:italic>\n                    , regards each triple as a cyclic string of length 3. Each rotation of the triples is lexicographically sorted and the values of the last attribute are stored as a column, so we obtain the order of the next column by stably re-sorting the triples by its attribute. We show that, by representing the columns with a compact data structure called a wavelet tree, this ordering enables forward and backward navigation between columns without needing pointers. These wavelet trees further support wco join algorithms and cardinality estimations for query planning. While traditional data structures such as B-Trees, tries, and so on, require 6 index orders to support all possible wco joins over triples, we can use one ring to index them all. This ring replaces the graph and uses only sublinear extra space, thus supporting wco joins in almost no space beyond storing the graph itself. Experiments querying a large graph (Wikidata) in memory show that the ring offers nearly the best overall query times while using only a small fraction of the space required by several state-of-the-art approaches.\n                  <\/jats:p>\n                  <jats:p>\n                    We then turn our attention to some theoretical results for indexing tables of arity\n                    <jats:italic>d<\/jats:italic>\n                    higher than 3 in such a way that supports wco joins. While a single ring of length\n                    <jats:italic>d<\/jats:italic>\n                    no longer suffices to cover all\n                    <jats:italic>d<\/jats:italic>\n                    ! orders, we need much fewer rings to index them all:\n                    <jats:italic>O<\/jats:italic>\n                    (2\n                    <jats:sup>\n                      <jats:italic>d<\/jats:italic>\n                    <\/jats:sup>\n                    ) rings with a small constant. For example, we need 5 rings instead of 120 orders for\n                    <jats:italic>d<\/jats:italic>\n                    =5. We show that our rings become a particular case of what we dub\n                    <jats:italic>order graphs<\/jats:italic>\n                    , whose nodes are attribute orders and where stably sorting by some attribute leads us from an order to another, thereby inducing an edge labeled by the attribute. The index is then the set of columns associated with the edges, and a set of rings is just one possible graph shape. We show that other shapes, like for example a single ring instead of several ones of length\n                    <jats:italic>d<\/jats:italic>\n                    , can lead us to even smaller indexes, and that other more general shapes are also possible. For example, we handle\n                    <jats:italic>d<\/jats:italic>\n                    =5 attributes within space equivalent to 4 rings.\n                  <\/jats:p>","DOI":"10.1145\/3644824","type":"journal-article","created":{"date-parts":[[2024,2,8]],"date-time":"2024-02-08T07:06:56Z","timestamp":1707376016000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["The Ring: Worst-case Optimal Joins in Graph Databases using (Almost) No Extra Space"],"prefix":"10.1145","volume":"49","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2509-8097","authenticated-orcid":false,"given":"Diego","family":"Arroyuelo","sequence":"first","affiliation":[{"name":"DCC, Escuela de Ingenier\u00eda, Pontificia Universidad Cat\u00f3lica &amp; IMFD, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1216-2176","authenticated-orcid":false,"given":"Adri\u00e1n","family":"G\u00f3mez-Brand\u00f3n","sequence":"additional","affiliation":[{"name":"Universidade da Coru\u00f1a &amp; CITIC &amp; IMFD, A Coru\u00f1a, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9482-1982","authenticated-orcid":false,"given":"Aidan","family":"Hogan","sequence":"additional","affiliation":[{"name":"DCC, University of Chile &amp; IMFD, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2286-741X","authenticated-orcid":false,"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[{"name":"DCC, University of Chile &amp; IMFD, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2186-0312","authenticated-orcid":false,"given":"Juan","family":"Reutter","sequence":"additional","affiliation":[{"name":"DCC, Escuela de Ingenier\u00eda, Pontificia Universidad Cat\u00f3lica &amp; Instituto de Ingenier\u00eda Matem\u00e1tica y Computacional, Pontificia Universidad Cat\u00f3lica &amp; IMFD, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3208-1880","authenticated-orcid":false,"given":"Javiel","family":"Rojas-Ledesma","sequence":"additional","affiliation":[{"name":"DCC, Universidad de Chile &amp; IMFD, Penalolen, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7682-1639","authenticated-orcid":false,"given":"Adri\u00e1n","family":"Soto","sequence":"additional","affiliation":[{"name":"FIC, Universidad Adolfo Ib\u00e1\u00f1 ez &amp; IMFD, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,3,23]]},"reference":[{"key":"e_1_3_4_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3129246"},{"key":"e_1_3_4_3_2","first-page":"21:1\u201321:19","volume-title":"Proceedings of the 22nd International Conference on Database Theory","author":"Khamis M. Abo","year":"2019","unstructured":"M. Abo Khamis, H. Q. Ngo, D. Olteanu, and D. Suciu. 2019. Boolean tensor decomposition for conjunctive queries with negation. In Proceedings of the 22nd International Conference on Database Theory. 21:1\u201321:19."},{"key":"e_1_3_4_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-014-0770-y"},{"issue":"5","key":"e_1_3_4_5_2","first-page":"68:1\u201368:40","article-title":"Foundations of modern query languages for graph databases","volume":"50","author":"Angles R.","year":"2017","unstructured":"R. Angles, M. Arenas, P. Barcel\u00f3, A. Hogan, J. L. Reutter, and D. Vrgoc. 2017. Foundations of modern query languages for graph databases. ACM Computing Surveys 50, 5 (2017), 68:1\u201368:40.","journal-title":"ACM Computing Surveys"},{"key":"e_1_3_4_6_2","article-title":"Optimizing RPQs over a compact graph representation","author":"Arroyuelo D.","year":"2023","unstructured":"D. Arroyuelo, A. G\u00f3mez-Brand\u00f3n, A. Hogan, G. Navarro, and J. Rojas-Ledesma. 2023. Optimizing RPQs over a compact graph representation. The VLDB Journal 33, 2 (2023), 349\u2013374.","journal-title":"The VLDB Journal"},{"key":"e_1_3_4_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457256"},{"key":"e_1_3_4_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772696"},{"key":"e_1_3_4_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/110859440"},{"key":"e_1_3_4_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2013.10.003"},{"key":"e_1_3_4_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.02.002"},{"key":"e_1_3_4_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313472"},{"key":"e_1_3_4_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00558-9"},{"key":"e_1_3_4_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11227-022-04890-w"},{"key":"e_1_3_4_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2017.05.003"},{"key":"e_1_3_4_16_2","volume-title":"A Block Sorting Lossless Data Compression Algorithm","author":"Burrows M.","year":"1994","unstructured":"M. Burrows and D. Wheeler. 1994. A Block Sorting Lossless Data Compression Algorithm. Technical Report 124. Digital Equipment Corporation."},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2014.06.002"},{"key":"e_1_3_4_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-07443-6_21"},{"issue":"1","key":"e_1_3_4_19_2","first-page":"3","article-title":"Virtuoso, a hybrid RDBMS\/graph column store","volume":"35","author":"Erling O.","year":"2012","unstructured":"O. Erling. 2012. Virtuoso, a hybrid RDBMS\/graph column store. Data Engineering Bulletin 35, 1 (2012), 3\u20138.","journal-title":"Data Engineering Bulletin"},{"key":"e_1_3_4_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02184-8_2"},{"key":"e_1_3_4_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2013.01.002"},{"key":"e_1_3_4_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/1082036.1082039"},{"key":"e_1_3_4_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/1240233.1240243"},{"key":"e_1_3_4_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3190657"},{"key":"e_1_3_4_25_2","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407797"},{"key":"e_1_3_4_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.08.004"},{"key":"e_1_3_4_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.12.002"},{"key":"e_1_3_4_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-07959-2_28"},{"key":"e_1_3_4_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/2220357.2220363"},{"key":"e_1_3_4_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/303976.303979"},{"key":"e_1_3_4_31_2","first-page":"841","volume-title":"Proceedings of the 14th Symposium on Discrete Algorithms","author":"Grossi R.","year":"2003","unstructured":"R. Grossi, A. Gupta, and J. S. Vitter. 2003. High-order entropy-compressed text indexes. In Proceedings of the 14th Symposium on Discrete Algorithms. 841\u2013850. Accessed date: 2024-02-26."},{"key":"e_1_3_4_32_2","article-title":"SPARQL 1.1 Query Language","author":"Harris S.","year":"2013","unstructured":"S. Harris, A. Seaborne, and E. Prud\u2019hommeaux. 2013. SPARQL 1.1 Query Language. W3C Recommendation. Retrieved from https:\/\/www.w3.org\/TR\/sparql11-query\/","journal-title":"W3C Recommendation"},{"key":"e_1_3_4_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/LAWEB.2005.25"},{"key":"e_1_3_4_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-30793-6_15"},{"key":"e_1_3_4_35_2","first-page":"282","volume-title":"Proceedings of the 20th International Conference on Extending Database Technology","author":"Kalinsky O.","year":"2017","unstructured":"O. Kalinsky, Y. Etsion, and B. Kimelfeld. 2017. Flexible caching in trie joins. In Proceedings of the 20th International Conference on Extending Database Technology. 282\u2013293."},{"key":"e_1_3_4_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/2967101"},{"key":"e_1_3_4_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056105"},{"key":"e_1_3_4_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-00668-6_23"},{"key":"e_1_3_4_39_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2015.08.008"},{"key":"e_1_3_4_40_2","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342643"},{"key":"e_1_3_4_41_2","unstructured":"MonetDB. 2013. Retrieved 26 February 2024 from http:\/\/www.monetdb.org"},{"key":"e_1_3_4_42_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-62034-6_35"},{"key":"e_1_3_4_43_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.11.011"},{"key":"e_1_3_4_44_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2013.07.004"},{"key":"e_1_3_4_45_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781316588284"},{"key":"e_1_3_4_46_2","first-page":"21:1\u201321:21","volume-title":"Proceedings of the 23rd International Conference on Database Theory","author":"Navarro G.","year":"2020","unstructured":"G. Navarro, J. Reutter, and J. Rojas. 2020. Optimal joins using compact data structures. In Proceedings of the 23rd International Conference on Database Theory. 21:1\u201321:21."},{"key":"e_1_3_4_47_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-009-0165-y"},{"key":"e_1_3_4_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196990"},{"key":"e_1_3_4_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213565"},{"key":"e_1_3_4_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/2764947.2764948"},{"key":"e_1_3_4_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/3003665.3003667"},{"key":"e_1_3_4_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/2600428.2609615"},{"key":"e_1_3_4_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3320212"},{"key":"e_1_3_4_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/1290672.1290680"},{"key":"e_1_3_4_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/3226595.3226638"},{"key":"e_1_3_4_56_2","first-page":"193","volume-title":"Proceedings of the Linked Data Management","author":"Thompson B. B.","year":"2014","unstructured":"B. B. Thompson, M. Personick, and M. Cutcher. 2014. The bigdata\u00aeRDF graph database. In Proceedings of the Linked Data Management. Chapman and Hall\/CRC, 193\u2013237."},{"key":"e_1_3_4_57_2","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3383132"},{"key":"e_1_3_4_58_2","first-page":"96","volume-title":"Proceedings of the 17th International Conference on Database Theory","author":"Veldhuizen T. L.","year":"2014","unstructured":"T. L. Veldhuizen. 2014. Triejoin: A simple, worst-case optimal join algorithm. In Proceedings of the 17th International Conference on Database Theory. 96\u2013106."},{"key":"e_1_3_4_59_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.07.016"},{"key":"e_1_3_4_60_2","doi-asserted-by":"publisher","DOI":"10.1145\/2629489"},{"key":"e_1_3_4_61_2","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453965"},{"key":"e_1_3_4_62_2","first-page":"82","volume-title":"Proceedings of the 7th International Conference on Very Large Databases","author":"Yannakakis M.","year":"1981","unstructured":"M. Yannakakis. 1981. Algorithms for acyclic database schemes. In Proceedings of the 7th International Conference on Very Large Databases. 82\u201394."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3644824","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3644824","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:03:27Z","timestamp":1750277007000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3644824"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,23]]},"references-count":61,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,6,30]]}},"alternative-id":["10.1145\/3644824"],"URL":"https:\/\/doi.org\/10.1145\/3644824","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,23]]},"assertion":[{"value":"2022-08-24","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-01-24","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-03-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}