Vadalog: A modern architecture for automated reasoning with large knowledge graphs. Issue 105 (March 2022)

• Record Type: Journal Article
• Authors: Bellomarini, Luigi; Benedetto, Davide; Gottlob, Georg; Sallinger, Emanuel
• Is Part Of: Information systems. Issue 105(2022)
• Publication Date: 2022-03
• Subjects: Knowledge graphs -- Reasoning -- Query answering -- Datalog -- Vadalog; Database management -- Periodicals; Electronic data processing -- Periodicals; Bases de données -- Gestion -- Périodiques; Informatique -- Périodiques; Database management; Electronic data processing; Periodicals; 005.7
• DOI: 10.1016/j.is.2020.101528
• Languages: English
• ISSNs: 0306-4379

Abstract

Abstract: The introduction of novel Datalog +/- fragments with good theoretical properties, together with the growing use of enterprise knowledge graphs motivated the development of Vadalog, a knowledge graph management system developed at the University of Oxford. It adopts Warded Datalog +/- as the core of its language for knowledge representation and reasoning, which exhibits a very good tradeoff between computational complexity of reasoning and expressive power, capturing PTIME data complexity while allowing ontological reasoning and full recursion. In this paper, we provide a detailed illustration of the Vadalog system, presenting: the essentials of the first implementation of Warded Datalog +/-; a comprehensive overview of the architecture with specific focus on runtime execution model, memory management, graph traversal strategies and join algorithms; and a detailed experimental evaluation. This paper is a substantially expanded version of the AMW 2019 paper "Datalog-based reasoning for Knowledge Graphs". To stand apart from previous works on the topic, our focus in this work shall be a comprehensive presentation of the architecture of the Vadalog system and showing how our techniques work together to provide a full-fledged KGMS. In particular, roughly half of this paper is new material created particularly for this comprehensive architectural view. This includes a new series of experiments designed to shed light on architectural choices and alternatives. Highlights: Growing use of enterprise knowledge graphs motivated the development of Vadalog. Knowledge graph management system developed at the University of Oxford. Based on Warded Datalog plus–minus. Good trade-off between computational complexity of reasoning and expressive power. PTIME data complexity while allowing ontological reasoning and full recursion. This work: Comprehensive overview of the architecture. Specific focus on runtime execution model and memory management Discussion of graph traversal strategies and join algorithms.