A linear algebraic approach to Datalog evaluation

DOI10.1017/S1471068417000023zbMATH Open1379.68082arXiv1608.00139OpenAlexW2963275055MaRDI QIDQ4593086FDOQ4593086

Authors: Taisuke Sato 

Publication date: 9 November 2017

Published in: Theory and Practice of Logic Programming (Search for Journal in Brave)

Abstract: In this paper, 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 set Eq(DB) of matrix equations with a non-linear operation where relations in M_DB, the least Herbrand model of DB, are encoded as adjacency matrices. We then translate Eq(DB) into another, but purely linear matrix equations tilde_Eq(DB). It is proved that the least solution of tilde_Eq(DB) in the sense of matrix ordering is converted to the least solution of Eq(DB) and the latter gives M_DB as a set of adjacency matrices. Hence computing the least solution of tilde_Eq(DB) is equivalent to computing M_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. To appear in Theory and Practice of Logic Programming (TPLP).

Full work available at URL: https://arxiv.org/abs/1608.00139

Recommendations

• The Complexity of Datalog on Linear Orders
• Datalog: A self-contained tutorial. II
• scientific article; zbMATH DE number 1149474
• scientific article; zbMATH DE number 638303
• Linearisability on Datalog programs

zbMATH Keywords

matrixvector spaceDatalogleast model

Mathematics Subject Classification ID

Logic programming (68N17)

Cites Work

• XSB: extending Prolog with tabled logic programming
• Algorithm 432 [C2]: Solution of the matrix equation AX + XB = C [F4]
• Tensor Decompositions and Applications
• Computational Methods for Linear Matrix Equations
• A Hessenberg-Schur method for the problem AX + XB= C
• Depth-First Search and Linear Graph Algorithms
• Matrix multiplication via arithmetic progressions
• Recursive blocked algorithms for solving triangular systems—Part I
• Filtering theory. With applications to fault detection, isolation, and estimation.
• Title not available (Why is that?)
• RECSY and SCASY Library Software: Recursive Blocked and Parallel Algorithms for Sylvester-Type Matrix Equations with Some Applications

Cited In (10)

• Logic programming in tensor spaces
• A closed-form evaluation for Datalog queries with integer (gap)-order constraints
• A Datalog hammer for supervisor verification conditions modulo simple linear arithmetic
• A semantic approach to optimize linear datalog programs
• Title not available (Why is that?)
• Modular materialisation of Datalog programs
• On the expressive power of query languages for matrices
• Datalog LITE
• Memory-saving evaluation plans for Datalog
• Title not available (Why is that?)

Uses Software

• SCASY
• recsy
• DLV
• XSB
• Datalog

This page was built for publication: A linear algebraic approach to Datalog evaluation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4593086)