{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T22:36:57Z","timestamp":1778279817603,"version":"3.51.4"},"reference-count":51,"publisher":"China Science Publishing & Media Ltd.","issue":"3","license":[{"start":{"date-parts":[[2023,9,12]],"date-time":"2023-09-12T00:00:00Z","timestamp":1694476800000},"content-version":"vor","delay-in-days":254,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["direct.mit.edu"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,8,1]]},"abstract":"<jats:title>ABSTRACT<\/jats:title>\n               <jats:p>In this systems paper, we present MillenniumDB: a novel graph database engine that is modular, persistent, and open source. MillenniumDB is based on a graph data model, which we call domain graphs, that provides a simple abstraction upon which a variety of popular graph models can be supported, thus providing a flexible data management engine for diverse types of knowledge graph. The engine itself is founded on a combination of tried and tested techniques from relational data management, state-of-the-art algorithms for worst-case-optimal joins, as well as graph-specific algorithms for evaluating path queries. In this paper, we present the main design principles underlying MillenniumDB, describing the abstract graph model and query semantics supported, the concrete data model and query syntax implemented, as well as the storage, indexing, query planning and query evaluation techniques used. We evaluate MillenniumDB over real-world data and queries from the Wikidata knowledge graph, where we find that it outperforms other popular persistent graph database engines (including both enterprise and open source alternatives) that support similar query features.<\/jats:p>","DOI":"10.1162\/dint_a_00229","type":"journal-article","created":{"date-parts":[[2023,9,12]],"date-time":"2023-09-12T15:37:54Z","timestamp":1694533074000},"page":"560-610","update-policy":"https:\/\/doi.org\/10.1162\/mitpressjournals.corrections.policy","source":"Crossref","is-referenced-by-count":14,"title":["MillenniumDB: An Open-Source Graph Database System"],"prefix":"10.3724","volume":"5","author":[{"given":"Domagoj","family":"Vrgo\u010d","sequence":"first","affiliation":[{"name":"Instituto Milenio Fundamentos de los Datos (IMFD)"},{"name":"Pontificia Universidad Cat\u00f3lica de Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carlos","family":"Rojas","sequence":"additional","affiliation":[{"name":"Instituto Milenio Fundamentos de los Datos (IMFD)"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Renzo","family":"Angles","sequence":"additional","affiliation":[{"name":"Instituto Milenio Fundamentos de los Datos (IMFD)"},{"name":"Universidad de Talca"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcelo","family":"Arenas","sequence":"additional","affiliation":[{"name":"Instituto Milenio Fundamentos de los Datos (IMFD)"},{"name":"Pontificia Universidad Cat\u00f3lica de Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Diego","family":"Arroyuelo","sequence":"additional","affiliation":[{"name":"Instituto Milenio Fundamentos de los Datos (IMFD)"},{"name":"Universidad T\u00e9cnica Federico Santa Mar\u00eda"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carlos","family":"Buil-Aranda","sequence":"additional","affiliation":[{"name":"Instituto Milenio Fundamentos de los Datos (IMFD)"},{"name":"Universidad T\u00e9cnica Federico Santa Mar\u00eda"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aidan","family":"Hogan","sequence":"additional","affiliation":[{"name":"Instituto Milenio Fundamentos de los Datos (IMFD)"},{"name":"DCC, Universidad de Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[{"name":"Instituto Milenio Fundamentos de los Datos (IMFD)"},{"name":"DCC, Universidad de Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cristian","family":"Riveros","sequence":"additional","affiliation":[{"name":"Instituto Milenio Fundamentos de los Datos (IMFD)"},{"name":"Pontificia Universidad Cat\u00f3lica de Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Juan","family":"Romero","sequence":"additional","affiliation":[{"name":"Instituto Milenio Fundamentos de los Datos (IMFD)"},{"name":"Pontificia Universidad Cat\u00f3lica de Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"2026","published-online":{"date-parts":[[2023,8,1]]},"reference":[{"issue":"1","key":"2023091215374657900_ref1","doi-asserted-by":"crossref","first-page":"1:1","DOI":"10.1145\/1322432.1322433","article-title":"Survey of graph database models. ACM Comput","volume":"40","author":"Angles","year":"2008","journal-title":"Surv."},{"issue":"5","key":"2023091215374657900_ref2","first-page":"68:1","article-title":"Foundations of Modern Query Languages for Graph Databases. ACM Comput","volume":"50","author":"Angles","year":"2017","journal-title":"Surv."},{"issue":"4","key":"2023091215374657900_ref3","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1145\/1978915.1978919","article-title":"Scalable SQL and NoSQL data stores","volume":"39","author":"Cattell","year":"2010","journal-title":"SIGMOD Rec."},{"key":"2023091215374657900_ref4","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-031-79432-2","article-title":"Linked Data: Evolving the Web into a Global Data Space","volume-title":"Synthesis Lectures on the Semantic Web","author":"Heath","year":"2011"},{"key":"2023091215374657900_ref5","article-title":"Knowledge Graphs","volume-title":"CoRR abs\/2003.02320","author":"Hogan","year":"2020"},{"key":"2023091215374657900_ref6","first-page":"217","article-title":"A programmatic introduction to Neo4j","volume-title":"Conference on Systems, Programming, and Applications: Software for Humanity, SPLASH \u201812","author":"Webber","year":"2012"},{"key":"2023091215374657900_ref7","first-page":"1433","article-title":"Cypher: An Evolving Query Language for Property Graphs","volume-title":"Proceedings of the 2018 International Conference on Management of Data, SIGMOD Conference 2018","author":"Francis","year":"2018"},{"key":"2023091215374657900_ref8","volume-title":"ArangoDB v3.7.11 Documentation","author":"ArangoDB Team","year":"2021"},{"key":"2023091215374657900_ref9","volume-title":"JanusGraph Documentation, v.0.5","author":"JanusGraph Team","year":"2022"},{"key":"2023091215374657900_ref10","volume-title":"OrientDB Manual - version 3.0.34","author":"OrientDB Team","year":"2022"},{"key":"2023091215374657900_ref11","volume-title":"TigerGraph Documentation - version 3.1","author":"TigerGraph Team","year":"2021"},{"key":"2023091215374657900_ref12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2815072.2815073","article-title":"The Gremlin graph traversal machine and language (invited talk)","volume-title":"Proceedings of the 15th Symposium on Database Programming Languages","author":"Rodriguez","year":"2015"},{"issue":"3","key":"2023091215374657900_ref13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00778-021-00711-3","article-title":"A survey of RDF stores & SPARQL engines for querying knowledge graphs","volume":"31","author":"Ali","year":"2022","journal-title":"VLDB J."},{"key":"2023091215374657900_ref14","volume-title":"AllegroGraph 7.1.0 Documentation","author":"AllegroGraph Team","year":"2021"},{"key":"2023091215374657900_ref15","volume-title":"What Is Amazon Neptune?","author":"Amazon Neptune Team","year":"2021"},{"key":"2023091215374657900_ref16","first-page":"193","article-title":"The Bigdata\u00ae RRDF Graph Database","volume-title":"Linked Data Management","author":"Thompson","year":"2014"},{"issue":"1","key":"2023091215374657900_ref17","doi-asserted-by":"crossref","first-page":"33","DOI":"10.3233\/SW-2011-0026","article-title":"OWLIM: A family of scalable semantic repositories","volume":"2","author":"Bishop","year":"2011","journal-title":"Semantic Web"},{"key":"2023091215374657900_ref18","volume-title":"TDB Documentation","author":"Jena Team","year":"2022"},{"key":"2023091215374657900_ref19","volume-title":"Stardog 7.6.3 Documentation","author":"Stardog Team","year":"2021"},{"issue":"1","key":"2023091215374657900_ref20","first-page":"3","article-title":"Virtuoso, a Hybrid RDBMS\/Graph Column Store. IEEE Data Eng","volume":"35","author":"Erling","year":"2012","journal-title":"Bull."},{"issue":"10","key":"2023091215374657900_ref21","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1145\/2629489","article-title":"Wikidata: a free collaborative knowledgebase. Commun","volume":"57","author":"Vrandecic","year":"2014","journal-title":"ACM"},{"key":"2023091215374657900_ref22","first-page":"376","article-title":"Getting the Most Out of Wikidata: Semantic Technology Usage in Wikipedia's Knowledge Graph","volume-title":"International Semantic Web Conference (ISWC)","author":"Malyshev","year":"2018"},{"key":"2023091215374657900_ref23","first-page":"32","article-title":"Reifying RDF: What Works Well With Wikidata?","volume-title":"Proceedings of the 11th International Workshop on Scalable Semantic Web Knowledge Base Systems co-located with 14th International Semantic Web Conference (ISWC 2015)","author":"Hern\u00e1ndez","year":"2015"},{"key":"2023091215374657900_ref24","first-page":"11:1","article-title":"Multilayer graphs: a unified data model for graph databases","volume-title":"GRADES-NDA \u201822: Proceedings of the 5th ACM SIGMOD Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA)","author":"Angles","year":"2022"},{"key":"2023091215374657900_ref25","volume-title":"MillenniumDB Source Code","author":"MillenniumDB Team","year":"2021"},{"key":"2023091215374657900_ref26","volume-title":"Wikidata Benchmark","author":"MillenniumDB Team","year":"2021"},{"key":"2023091215374657900_ref27","article-title":"RDF 1.1 Concepts and Abstract Syntax","volume-title":"W3C Recommendation","author":"Cyganiak","year":"2014"},{"key":"2023091215374657900_ref28","article-title":"Foundations of RDF\u2217 and SPARQL\u2217 (An Alternative Approach to Statement-Level Metadata in RDF)","volume-title":"Proceedings of the 11th Alberto Mendelzon International Workshop on Foundations of Data Management and the Web, Montevideo, Uruguay, June 7-9, 2017, volume 1912 of CEUR Workshop Proceedings","author":"Hartig","year":"2017"},{"key":"2023091215374657900_ref29","article-title":"RDF-star and SPARQL-star","volume-title":"W3C Draft Community Group Report","author":"Hartig","year":"2021"},{"key":"2023091215374657900_ref30","article-title":"SPARQL 1.1 Query Language","volume-title":"W3C Recommendation","author":"Harris","year":"2013"},{"issue":"2-3","key":"2023091215374657900_ref31","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1007\/s00778-019-00548-x","article-title":"The ubiquity of large graphs and surprising challenges of graph processing: extended survey","volume":"29","author":"Sahu","year":"2020","journal-title":"VLDB J."},{"key":"2023091215374657900_ref32","first-page":"278","article-title":"KGTK: A Toolkit for Large Knowledge Graph Manipulation and Analysis","volume-title":"International Semantic Web Conference (ISWC)","author":"Ilievski","year":"2020"},{"key":"2023091215374657900_ref33","article-title":"Graph? Yes! Which one?","volume-title":"Help! CoRR abs\/2110.13348","author":"Lassila","year":"2021"},{"issue":"2-3","key":"2023091215374657900_ref34","doi-asserted-by":"crossref","first-page":"655","DOI":"10.1007\/s00778-019-00558-9","article-title":"An analytical study of large SPARQL query logs","volume":"29","author":"Bonifati","year":"2020","journal-title":"VLDB J."},{"issue":"3","key":"2023091215374657900_ref35","doi-asserted-by":"crossref","first-page":"16:1","DOI":"10.1145\/1567274.1567278","article-title":"Semantics and complexity of SPARQL. ACM Trans","volume":"34","author":"P\u00e9rez","year":"2009","journal-title":"Database Syst."},{"key":"2023091215374657900_ref36","first-page":"1421","article-title":"G-CORE: A core for future graph query languages","volume-title":"Proceedings of the 2018 International Conference on Management of Data, SIGMOD Conference 2018, Houston, TX, USA, June 10-15, 2018","author":"Angles","year":"2018"},{"key":"2023091215374657900_ref37","volume-title":"Nebula Graph Query Language (nGQL)","author":"Nebula Team","year":"2021"},{"key":"2023091215374657900_ref38","first-page":"96","article-title":"Triejoin: A simple, worst-case optimal join algorithm","volume-title":"Proc. 17th International Conference on Database Theory (ICDT), Athens, Greece, March 24-28, 2014","author":"Veldhuizen","year":"2014"},{"key":"2023091215374657900_ref39","first-page":"165","article-title":"Evaluating navigational RDF queries over the web","volume-title":"Proceedings of the 28th ACM Conference on Hypertext and Social Media, HT 2017, Prague, Czech Republic, July 4-7, 2017","author":"Baier","year":"2017"},{"issue":"3","key":"2023091215374657900_ref40","first-page":"16:1","article-title":"Worst-case optimal join algorithms. J","volume":"65","author":"Ngo","year":"2018","journal-title":"ACM"},{"key":"2023091215374657900_ref41","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1016\/j.websem.2014.06.004","article-title":"Everything you always wanted to know about blank nodes","volume":"27-28","author":"Hogan","year":"2014","journal-title":"J. Web Semant."},{"key":"2023091215374657900_ref42","volume-title":"Database management systems","author":"Ramakrishnan","year":"2000"},{"key":"2023091215374657900_ref43","first-page":"258","article-title":"A worst-case optimal join algorithm for SPARQL","volume-title":"The Semantic Web - ISWC 2019 - 18th International Semantic Web Conference, Auckland, New Zealand, October 26-30, 2019, Proceedings, Part I, volume 11778 of Lecture Notes in Computer Science","author":"Hogan","year":"2019"},{"key":"2023091215374657900_ref44","article-title":"Database Design and Implementation - Second Edition","volume-title":"Data-Centric Systems and Applications","author":"Sciore","year":"2020"},{"key":"2023091215374657900_ref45","volume-title":"Database systems - the complete book","author":"Garcia-Molina","year":"2009","edition":"2. ed."},{"issue":"2","key":"2023091215374657900_ref46","doi-asserted-by":"crossref","first-page":"6:1","DOI":"10.1145\/3446980","article-title":"Optimizing One-time and Continuous Subgraph Queries using Worst-case Optimal Joins. ACM Trans","volume":"46","author":"Mhedhbi","year":"2021","journal-title":"Database Syst."},{"key":"2023091215374657900_ref47","first-page":"102","article-title":"Worstcase optimal graph joins in almost no space","volume-title":"SIGMOD \u201821: International Conference on Management of Data, Virtual Event, China, June 20-25, 2021","author":"Arroyuelo","year":"2021"},{"key":"2023091215374657900_ref48","first-page":"306","article-title":"An algorithm for tree-query membership of a distributed query","volume-title":"The IEEE Computer Society's Third International Computer Software and Applications Conference, COMPSAC 1979, 6-8 November, 1979","author":"Yu","year":"1979"},{"key":"2023091215374657900_ref49","first-page":"185","article-title":"Finding regular simple paths in graph databases","volume-title":"Proceedings of the Fifteenth International Conference on Very Large Data Bases, August 22-25, 1989, Amsterdam, The Netherlands","author":"Mendelzon","year":"1989"},{"key":"2023091215374657900_ref50","first-page":"175","article-title":"Querying graph databases","volume-title":"Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2013","author":"Baeza","year":"2013"},{"key":"2023091215374657900_ref51","volume-title":"Wikidata: database download","author":"Wikimedia Foundation","year":"2021"}],"container-title":["Data Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/direct.mit.edu\/dint\/article-pdf\/5\/3\/560\/2158194\/dint_a_00229.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/direct.mit.edu\/dint\/article-pdf\/5\/3\/560\/2158194\/dint_a_00229.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,4]],"date-time":"2025-03-04T23:06:24Z","timestamp":1741129584000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/dint\/article\/5\/3\/560\/117375\/MillenniumDB-An-Open-Source-Graph-Database-System"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"references-count":51,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,8,1]]}},"URL":"https:\/\/doi.org\/10.1162\/dint_a_00229","relation":{},"ISSN":["2641-435X"],"issn-type":[{"value":"2641-435X","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2023]]},"published":{"date-parts":[[2023]]}}}