{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T09:01:14Z","timestamp":1775638874313,"version":"3.50.1"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2018,10]]},"abstract":"<jats:p>\n            Datalog has been applied to several use cases that require very high performance on large rulesets and factsets. It is common to create indexes for relations to improve search performance. However, the existing indexing schemes either require manual index selection or result in insufficient performance on very large tasks. In this paper, we propose an automatic scheme to select indexes. We automatically create the minimum number of indexes to speed up all the searches in a given Datalog program. We have integrated our indexing scheme into an open-source Datalog engine S\n            <jats:sc>OUFFL\u00c9.<\/jats:sc>\n            We obtain performance on a par with what users have accepted from hand-optimized Datalog programs running on state-of-the-art Datalog engines, while we do not require the effort of manual index selection. Extensive experiments on large real Datalog programs demonstrate that our indexing scheme results in considerable speedups (up to 2x) and significantly less memory usage (up to 6x) compared with other automated index selections.\n          <\/jats:p>","DOI":"10.14778\/3282495.3282500","type":"journal-article","created":{"date-parts":[[2019,1,4]],"date-time":"2019-01-04T13:35:28Z","timestamp":1546608928000},"page":"141-153","source":"Crossref","is-referenced-by-count":28,"title":["Automatic index selection for large-scale datalog computation"],"prefix":"10.14778","volume":"12","author":[{"given":"Pavle","family":"Suboti\u0107","sequence":"first","affiliation":[{"name":"University College London"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Herbert","family":"Jordan","sequence":"additional","affiliation":[{"name":"University of Innsbruck"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lijun","family":"Chang","sequence":"additional","affiliation":[{"name":"The University of Sydney"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alan","family":"Fekete","sequence":"additional","affiliation":[{"name":"The University of Sydney"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bernhard","family":"Scholz","sequence":"additional","affiliation":[{"name":"The University of Sydney"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,10]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Foundations of Databases","author":"Abiteboul S.","year":"1995","unstructured":"S. Abiteboul , R. Hull , and V. Vianu . Foundations of Databases . Addison-Wesley , 1995 . S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3088515.3088522"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742796"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1167473.1167488"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989328"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1640089.1640108"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1639949.1640108"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","DOI":"10.1201\/b10711","volume-title":"Automated Physical Database Design and Tuning","author":"Bruno N.","year":"2011","unstructured":"N. Bruno . Automated Physical Database Design and Tuning . CRC Press, Inc. , Boca Raton, FL, USA , 1 st edition, 2011 . N. Bruno. Automated Physical Database Design and Tuning. CRC Press, Inc., Boca Raton, FL, USA, 1st edition, 2011.","edition":"1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.43410"},{"key":"e_1_2_1_10_1","volume-title":"Autoadmin \"what-if\" index analysis utility","author":"Chaudhuri S.","year":"1998","unstructured":"S. Chaudhuri and V. Narasayya . Autoadmin \"what-if\" index analysis utility . Association for Computing Machinery, Inc. , June 1998 . S. Chaudhuri and V. Narasayya. Autoadmin \"what-if\" index analysis utility. Association for Computing Machinery, Inc., June 1998."},{"key":"e_1_2_1_11_1","first-page":"146","volume-title":"Proc. VLDB","author":"Chaudhuri S.","year":"1997","unstructured":"S. Chaudhuri and V. R. Narasayya . An efficient cost-driven index selection tool for Microsoft SQL Server . In Proc. VLDB , pages 146 -- 155 , 1997 . S. Chaudhuri and V. R. Narasayya. An efficient cost-driven index selection tool for Microsoft SQL Server. In Proc. VLDB, pages 146--155, 1997."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/320289.320296"},{"key":"e_1_2_1_13_1","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2001","unstructured":"T. H. Cormen , C. Stein , R. L. Rivest , and C. E. Leiserson . Introduction to Algorithms . McGraw-Hill Higher Education , 2 nd edition, 2001 . T. H. Cormen, C. Stein, R. L. Rivest, and C. E. Leiserson. Introduction to Algorithms. McGraw-Hill Higher Education, 2nd edition, 2001.","edition":"2"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2814270.2814307"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.2307\/1969503"},{"issue":"4","key":"e_1_2_1_16_1","first-page":"701","article-title":"Note on dilworth's decomposition theorem for partially ordered sets","volume":"7","author":"Fulkerson D. R.","year":"1956","unstructured":"D. R. Fulkerson . Note on dilworth's decomposition theorem for partially ordered sets . Proc. Amer. Math. Soc. , 7 ( 4 ):pp. 701 -- 702 , 1956 . D. R. Fulkerson. Note on dilworth's decomposition theorem for partially ordered sets. Proc. Amer. Math. Soc., 7(4):pp. 701--702, 1956.","journal-title":"Proc. Amer. Math. Soc."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276486"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000017"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/2032305.2032341"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1983.236458"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-41540-6_23"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/1765642.1765670"},{"key":"e_1_2_1_23_1","volume-title":"http:\/\/snf-705535.vm.okeanos.grnet.gr\/agreement.html,2018. {Online","author":"Datalog P.","year":"2018","unstructured":"LogicBlox and P. (UoA). PA- Datalog . http:\/\/snf-705535.vm.okeanos.grnet.gr\/agreement.html,2018. {Online ; accessed 30- Jan- 2018 }. LogicBlox and P. (UoA). PA-Datalog. http:\/\/snf-705535.vm.okeanos.grnet.gr\/agreement.html,2018. {Online; accessed 30-Jan-2018}."},{"key":"e_1_2_1_24_1","unstructured":"LogicBlox Inc. Declartive cloud platform for applications that combine transactions & analytics. http:\/\/www.logicblox.com.  LogicBlox Inc. Declartive cloud platform for applications that combine transactions & analytics. http:\/\/www.logicblox.com."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2908080.2908096"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/984523.984530"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1155\/2013\/692645"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-3506-5_11"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(94)00039-9"},{"issue":"2","key":"e_1_2_1_30_1","first-page":"107","article-title":"An introduction to deductive database languages and systems","volume":"3","author":"Ramamohanarao K.","year":"1994","unstructured":"K. Ramamohanarao and J. Harland . An introduction to deductive database languages and systems . PVLDB , 3 ( 2 ): 107 -- 122 , 1994 . K. Ramamohanarao and J. Harland. An introduction to deductive database languages and systems. PVLDB, 3(2):107--122, 1994.","journal-title":"PVLDB"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0306-4379(75)90003-4"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/2140436.2140444"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2892208.2892226"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/582095.582099"},{"key":"e_1_2_1_35_1","first-page":"11","article-title":"Serverless Architectures with AWS Lambda. Technical report","author":"Services A. W.","year":"2017","unstructured":"A. W. Services . Serverless Architectures with AWS Lambda. Technical report , Amazon Web Services , 11 2017 . A. W. Services. Serverless Architectures with AWS Lambda. Technical report, Amazon Web Services, 11 2017.","journal-title":"Amazon Web Services"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915229"},{"key":"e_1_2_1_37_1","unstructured":"Y. Smaragdaiks M. Bravenboer and G. Kastrinis. Doop: A framework for java pointer analysis. http:\/\/doop.program-analysis.org\/.  Y. Smaragdaiks M. Bravenboer and G. Kastrinis. Doop: A framework for java pointer analysis. http:\/\/doop.program-analysis.org\/."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/11575467_8"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-016-0448-z"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3282495.3282500","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:32:26Z","timestamp":1672223546000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3282495.3282500"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10]]},"references-count":39,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,10]]}},"alternative-id":["10.14778\/3282495.3282500"],"URL":"https:\/\/doi.org\/10.14778\/3282495.3282500","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2018,10]]}}}