Carlos Rojas

In this paper we present TelarKG, a knowledge graph (KG) that consolidates multiple sources of information regarding the Chilean Constitutional process, particularly about the work of the members of the Constitutional Convention. TelarKG contains a wide range of public data, such as the materials from the commissions and information about the members' interventions and votes. In addition, the KG has been enriched with online user-generated content including posts from social networks related to the constitutional process, and transcriptions from the YouTube videos of the plenary sessions. Among other features, TelarKG leverages the semantic similarity search capabilities of the MillenniumDB endpoint to compute text similarity among convention members' Twitter messages. Additionally, we employ Entity Linking techniques to identify references to members of the Convention and Parties within these messages. TelarKG constitutes one of the most comprehensive historical archives on a political event, enabling users to query and navigate through diverse aspects of Chile's constitutional process.

Leapfrog Triejoin (LTJ) is arguably the most practical and popular worst-case-optimal (wco) algorithm for solving basic graph patterns in graph databases. Its main drawback is that it needs the database triples (subject, predicate, object) represented as paths in a trie, for each of the six orders of subject, predicate, and object. The resulting blowup in space makes most systems disregard LTJ or implement it only partially, and their corresponding algorithms be non-wco. In this paper we show that, by using compact data structures, it is possible to build an index that at the same matches the query time performance of the fastest classic wco index, and uses half the space of non-wco indices (which are much slower). Concretely, we make use of compact tree representations to store functional tries using one bit per trie edge, instead of one pointer. The resulting structure, called compactLTJ, uses 25% of the space of classic wco implementations and 45%-65% of classic non-wco systems. At solving queries, it is on par with the fastest classic wco system, and two orders of magnitude faster than non-wco systems. We further incorporate improved query resolution strategies into compactLTJ, which makes it considerably faster than any other alternative to display the first query results.

Current knowledge graphs encompass diverse data formats, including images, text, tables, audio files, and videos. Additionally, the graph database ecosystem is required to support multiple co-existing data models. Addressing these challenges is essential for promoting interoperability between data sources. This demo introduces MillenniumDB, a high-performing, open-source graph database handling this diversity of data formats and models. MillenniumDB is a multi-modal, multi-model graph database, supporting the popular property graph paradigm, the Semantic Web format RDF, and the multi-layered graph model, which combines and extends the two. In terms of querying, its provides support for a Cypher-like language over property graphs and multilayered graphs, as well as SPARQL 1.1 support over RDF. The engine is build on a solid theoretical foundation and it leverages worst-case optimal join algorithms in combination with traditional relational query optimization. It also support a wide array of graph-specific tasks such as path finding, pattern recognition, and similarity search on multi-modal data. In this demo, we will showcase how MillenniumDB is currently being used to host three public multi-modal knowledge graphs. The first one, a multi-layered graph called TelarKG, was developed at IMFD Chile to track the information about the Chilean constitutional reform. In the second one, called BibKG, we integrate information about Computer Science publications from different sources and make them available as a property graph. Finally, for RDF, we provide a SPARQL endpoint for Wikidata, the largest knowledge graph openly available online. We remark that our endpoints have stable links, allowing the audience to post queries using their Web browser with no restrictions, and will be available during the review process and during the demo.

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. 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.