A linear algebraic approach to datalog evaluation. Issue 3 (22nd May 2017)

• Record Type: Journal Article
• Authors: SATO, TAISUKE
• Is Part Of: Theory and practice of logic programming. Volume 17:Issue 3(2017)
• Page Start: 244
• Page End: 265
• Publication Date: 2017-05-22
• Subjects: Datalog, -- least model, -- matrix, -- vector space; Logic programming -- Periodicals; Artificial intelligence -- Computer programs -- Periodicals; Constraint programming (Computer science) -- Periodicals; 005.115
• DOI: 10.1017/S1471068417000023
• Languages: English
• ISSNs: 1471-0684

Abstract

Abstract: We propose a fundamentally new approach to Datalog evaluation. Given a linear Datalog program DB written using N constants and binary predicates, we first translate if-and-only-if completions of clauses in DB into a setE q (DB) of matrix equations with a non-linear operation, where relations inM DB, the least Herbrand model of DB, are encoded as adjacency matrices. We then translateE q (DB) into another, but purely linear matrix equationsẼ q (DB). It is proved that the least solution ofẼ q (DB) in the sense of matrix ordering is converted to the least solution ofE q (DB) and the latter givesM DB as a set of adjacency matrices. Hence, computing the least solution ofẼ q (DB) is equivalent to computingM DB specified by DB. For a class of tail recursive programs and for some other types of programs, our approach achieves O ( N 3 ) time complexity irrespective of the number of variables in a clause since only matrix operations costing O ( N 3 ) or less are used. We conducted two experiments that compute the least Herbrand models of linear Datalog programs. The first experiment computes transitive closure of artificial data and real network data taken from the Koblenz Network Collection. The second one compared the proposed approach with the state-of-the-art symbolic systems including two Prolog systems and two ASP systems, in terms of computation time for a transitive closure program and the same generation program. In the experiment, it is observed that our linear algebraic approach runs 10 1 ~ 10 4 times faster than the symbolic systems when data is not sparse. Our approach is inspired by the emergence of big knowledge graphs and expected to contribute to the realization of rich and scalable logical inference for knowledge graphs.